summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Transforms/Scalar/JumpThreading.cpp
Commit message (Collapse)AuthorAgeFilesLines
* [PM] Replace the hard invalidate in JumpThreading for LVI with correctChandler Carruth2017-01-231-4/+0
| | | | | | | | | | | | | | | | | | | | | invalidation of deleted functions in GlobalDCE. This was always testing a bug really triggered in GlobalDCE. Right now we have analyses with asserting value handles into IR. As long as those remain, when *deleting* an IR unit, we cannot wait for the normal invalidation scheme to kick in even though it was designed to work correctly in the face of these kinds of deletions. Instead, the pass needs to directly handle invalidating the analysis results pointing at that IR unit. I've tought the Inliner about this and this patch teaches GlobalDCE. This will handle the asserting VH case in the existing test as well as other issues of the same fundamental variety. I've moved the test into the GlobalDCE directory and added a comment explaining what is going on. Note that we cannot simply require LVI here because LVI is too lazy. llvm-svn: 292773
* Fix spelling mistakes in Transforms comments. NFC.Simon Pilgrim2016-11-201-1/+1
| | | | | | Identified by Pedro Giffuni in PR27636. llvm-svn: 287488
* Revert "[JumpThreading] Unfold selects that depend on the same condition"Pablo Barrio2016-11-151-77/+38
| | | | | | This reverts commit ac54d0066c478a09c7cd28d15d0f9ff8af984afc. llvm-svn: 286976
* Revert "[JumpThreading] Prevent non-deterministic use lists"Pablo Barrio2016-11-151-7/+8
| | | | | | This reverts commit f2c2f5354070469dac253373c66527ca971ddc66. llvm-svn: 286975
* [JumpThreading] Prevent non-deterministic use listsPablo Barrio2016-11-141-8/+7
| | | | | | | | | | | | | | | | | Summary: Unfolding selects was previously done with the help of a vector of pointers that was then sorted to be able to remove duplicates. As this sorting depends on the memory addresses, it was non-deterministic. A SetVector is used now so that duplicates are removed without the need of sorting first. Reviewers: mgrang, efriedma Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D26450 llvm-svn: 286807
* [JumpThreading] Unfold selects that depend on the same conditionPablo Barrio2016-11-081-38/+77
| | | | | | | | | | | | | | | | | | Summary: These are good candidates for jump threading. This enables later opts (such as InstCombine) to combine instructions from the selects with instructions out of the selects. SimplifyCFG will fold the select again if unfolding wasn't worth it. Patch by James Molloy and Pablo Barrio. Reviewers: rengolin, haicheng, sebpop Subscribers: jojo, jmolloy, llvm-commits Differential Revision: https://reviews.llvm.org/D26391 llvm-svn: 286236
* Revert 284971.Nico Weber2016-10-241-73/+38
| | | | | | | | | It seems to break selfhost on some bots, see e.g. http://lab.llvm.org:8011/builders/clang-x86-windows-msvc2015/builds/21 http://lab.llvm.org:8011/builders/clang-ppc64be-linux-multistage/builds/20 http://lab.llvm.org:8011/builders/clang-ppc64be-linux-lnt/builds/22 llvm-svn: 284979
* [JumpThreading] Unfold selects that depend on the same conditionPablo Barrio2016-10-241-38/+73
| | | | | | | | | | | | | | | | | | Summary: These are good candidates for jump threading. This enables later opts (such as InstCombine) to combine instructions from the selects with instructions out of the selects. SimplifyCFG will fold the select again if unfolding wasn't worth it. Patch by James Molloy and Pablo Barrio. Reviewers: reames, bkramer, mcrosier, gberry, haicheng, jmolloy, sebpop Subscribers: jojo, rengolin, llvm-commits Differential Revision: https://reviews.llvm.org/D25477 llvm-svn: 284971
* Jump threading: avoid trying to split edge into landingpad block (PR27840)Hans Wennborg2016-10-031-0/+4
| | | | | | | | | Splitting the edge is nontrivial because of the landing pad, and we would currently assert trying to do it. Differential Revision: https://reviews.llvm.org/D24680 llvm-svn: 283129
* [JumpThreading] Only write back branch-weight MDs for blocks that originally ↵Adam Nemet2016-09-061-1/+52
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | had PGO info Currently the pass updates branch weights in the IR if the function has any PGO info (entry frequency is set). However we could still have regions of the CFG that does not have branch weights collected (e.g. a cold region). In this case we'd use static estimates. Since static estimates for branches are determined independently, they are inconsistent. Updating them can "randomly" inflate block frequencies. I've run into this in a completely cold loop of h264ref from SPEC. -Rpass-with-hotness showed the loop to be completely cold during inlining (before JT) but completely hot during vectorization (after JT). The new testcase demonstrate the problem. We check array elements against 1, 2 and 3 in a loop. The check against 3 is the loop-exiting check. The block names should be self-explanatory. In this example, jump threading incorrectly updates the weight of the loop-exiting branch to 0, drastically inflating the frequency of the loop (in the range of billions). There is no run-time profile info for edges inside the loop, so branch probabilities are estimated. These are the resulting branch and block frequencies for the loop body: check_1 (16) (8) / | eq_1 | (8) \ | check_2 (16) (8) / | eq_2 | (8) \ | check_3 (16) (1) / | (loop exit) | (15) | (back edge) First we thread eq_1 -> check_2 to check_3. Frequencies are updated to remove the frequency of eq_1 from check_2 and then from the false edge leaving check_2. Changed frequencies are highlighted with * *: check_1 (16) (8) / | eq_1~ | (8) / | / check_2 (*8*) / (8) / | \ eq_2 | (*0*) \ \ | ` --- check_3 (16) (1) / | (loop exit) | (15) | (back edge) Next we thread eq_1 -> check_3 and eq_2 -> check_3 to check_1 as new back edges. Frequencies are updated to remove the frequency of eq_1 and eq_3 from check_3 and then the false edge leaving check_3 (changed frequencies are highlighted with * *): check_1 (16) (8) / | eq_1~ | (8) / | / check_2 (*8*) / (8) / | /-- eq_2~ | (*0*) (back edge) | check_3 (*0*) (*0*) / | (loop exit) | (*0*) | (back edge) As a result, the loop exit edge ends up with 0 frequency which in turn makes the loop header to have maximum frequency. There are a few potential problems here: 1. The profile data seems odd. There is a single profile sample of the loop being entered. On the other hand, there are no weights inside the loop. 2. Based on static estimation we shouldn't set edges to "extreme" values, i.e. extremely likely or unlikely. 3. We shouldn't create profile metadata that is calculated from static estimation. I am not sure what policy is but it seems to make sense to treat profile metadata as something that is known to originate from profiling. Estimated probabilities should only be reflected in BPI/BFI. Any one of these would probably fix the immediate problem. I went for 3 because I think it's a good policy to have and added a FIXME about 2. Differential Revision: https://reviews.llvm.org/D24118 llvm-svn: 280713
* Use the range variant of find instead of unpacking begin/endDavid Majnemer2016-08-111-2/+1
| | | | | | | | | If the result of the find is only used to compare against end(), just use is_contained instead. No functionality change is intended. llvm-svn: 278433
* Consistently use FunctionAnalysisManagerSean Silva2016-08-091-1/+1
| | | | | | | | | | | Besides a general consistently benefit, the extra layer of indirection allows the mechanical part of https://reviews.llvm.org/D23256 that requires touching every transformation and analysis to be factored out cleanly. Thanks to David for the suggestion. llvm-svn: 278077
* [JumpThreading] Fix handling of aliasing metadata.Eli Friedman2016-08-081-6/+16
| | | | | | | | | | | | | | | | | | Summary: The correctness fix here is that when we CSE a load with another load, we need to combine the metadata on the two loads. This matches the behavior of other passes, like instcombine and GVN. There's also a minor optimization improvement here: for load PRE, the aliasing metadata on the inserted load should be the same as the metadata on the original load. Not sure why the old code was throwing it away. Issue found by inspection. Differential Revision: http://reviews.llvm.org/D21460 llvm-svn: 277977
* Don't remove side effecting instructions due to ConstantFoldInstructionDavid Majnemer2016-07-221-1/+2
| | | | | | | | | Just because we can constant fold the result of an instruction does not imply that we can delete the instruction. It may have side effects. This fixes PR28655. llvm-svn: 276389
* [JumpThreading] PRE unordered loadsSanjoy Das2016-07-141-5/+6
| | | | | | | | | | | | Summary: Extend JumpThreading's PRE to unordered atomic loads. Reviewers: hfinkel, reames Subscribers: mcrosier, llvm-commits Differential Revision: http://reviews.llvm.org/D22326 llvm-svn: 275456
* [JumpThreading] Delete commented out debug code; NFCSanjoy Das2016-07-131-3/+0
| | | | llvm-svn: 275346
* Work around PR28400 a bit harder.Sean Silva2016-07-061-2/+5
| | | | | | | | | | We were still crashing in the "no change" case because LVI was not getting invalidated. See the thread "Should analyses be able to hold AssertingVH to IR? (related to PR28400)" for more discussion. llvm-svn: 274656
* PR28400: Partly undo r274440 to bring test-suite back to life with the new PMSean Silva2016-07-031-1/+2
| | | | | | | | | PR28400 seems to be not an isolated issue, but a general problem related to caching analyses. We will need to discuss on llvm-dev. A test case is in the PR. llvm-svn: 274457
* [PM] Fix a small typo from when I ported JumpThreadingSean Silva2016-07-021-1/+1
| | | | llvm-svn: 274440
* Reinstate r273711David Majnemer2016-06-251-2/+7
| | | | | | | | | | r273711 was reverted by r273743. The inliner needs to know about any call sites in the inlined function. These were obscured if we replaced a call to undef with an undef but kept the call around. This fixes PR28298. llvm-svn: 273753
* Revert r273711, it caused PR28298.Nico Weber2016-06-241-7/+2
| | | | llvm-svn: 273743
* SimplifyInstruction does not imply DCEDavid Majnemer2016-06-241-2/+7
| | | | | | | We cannot remove an instruction with no uses just because SimplifyInstruction succeeds. It may have side effects. llvm-svn: 273711
* Revert r272891 "[JumpThreading] Prevent dangling pointer problems in ↵Igor Laevsky2016-06-161-12/+4
| | | | | | | | BranchProbabilityInfo" It was causing failures in Profile-i386 and Profile-x86_64 tests. llvm-svn: 272912
* [JumpThreading] Prevent dangling pointer problems in BranchProbabilityInfoIgor Laevsky2016-06-161-4/+12
| | | | | | | | | We should update results of the BranchProbabilityInfo after removing block in JumpThreading. Otherwise we will get dangling pointer inside BranchProbabilityInfo cache. Differential Revision: http://reviews.llvm.org/D20957 llvm-svn: 272891
* Bring back "[PM] Port JumpThreading to the new PM" with a fixSean Silva2016-06-141-113/+82
| | | | | | | | | | | This reverts commit r272603 and adds a fix. Big thanks to Davide for pointing me at r216244 which gives some insight into how to fix this VS2013 issue. VS2013 can't synthesize a move constructor. So the fix here is to add one explicitly to the JumpThreadingPass class. llvm-svn: 272607
* Revert "[PM] Port JumpThreading to the new PM"Sean Silva2016-06-141-82/+113
| | | | | | | | This reverts commit r272597. Will investigate issue with VS2013 compilation and then recommit. llvm-svn: 272603
* [PM] Port JumpThreading to the new PMSean Silva2016-06-131-113/+82
| | | | | | | | | | | | This follows the approach in r263208 (for GVN) pretty closely: - move the bulk of the body of the function to the new PM class. - expose a runImpl method on the new-PM class that takes the IRUnitT and pointers/references to any analyses and use that to implement the old-PM class. - use a private namespace in the header for stuff that used to be file scope llvm-svn: 272597
* [PM] Port LVI to the new PM.Sean Silva2016-06-131-4/+4
| | | | | | | | | | | | | | | | | | | This is a bit gnarly since LVI is maintaining its own cache. I think this port could be somewhat cleaner, but I'd rather not spend too much time on it while we still have the old pass hanging around and limiting how much we can clean things up. Once the old pass is gone it will be easier (less time spent) to clean it up anyway. This is the last dependency needed for porting JumpThreading which I'll do in a follow-up commit (there's no printer pass for LVI or anything to test it, so porting a pass that depends on it seems best). I've been mostly following: r269370 / D18834 which ported Dependence Analysis r268601 / D19839 which ported BPI llvm-svn: 272593
* [ValueTracking] Improve isImpliedCondition when the dominating cond is false.Chad Rosier2016-04-251-2/+5
| | | | llvm-svn: 267430
* Re-commit optimization bisect support (r267022) without new pass manager ↵Andrew Kaylor2016-04-221-1/+1
| | | | | | | | | | support. The original commit was reverted because of a buildbot problem with LazyCallGraph::SCC handling (not related to the OptBisect handling). Differential Revision: http://reviews.llvm.org/D19172 llvm-svn: 267231
* Revert "Initial implementation of optimization bisect support."Vedant Kumar2016-04-221-1/+1
| | | | | | | | This reverts commit r267022, due to an ASan failure: http://lab.llvm.org:8080/green/job/clang-stage2-cmake-RgSan_check/1549 llvm-svn: 267115
* Initial implementation of optimization bisect support.Andrew Kaylor2016-04-211-1/+1
| | | | | | | | | | | | This patch implements a optimization bisect feature, which will allow optimizations to be selectively disabled at compile time in order to track down test failures that are caused by incorrect optimizations. The bisection is enabled using a new command line option (-opt-bisect-limit). Individual passes that may be skipped call the OptBisect object (via an LLVMContext) to see if they should be skipped based on the bisect limit. A finer level of control (disabling individual transformations) can be managed through an addition OptBisect method, but this is not yet used. The skip checking in this implementation is based on (and replaces) the skipOptnoneFunction check. Where that check was being called, a new call has been inserted in its place which checks the bisect limit and the optnone attribute. A new function call has been added for module and SCC passes that behaves in a similar way. Differential Revision: http://reviews.llvm.org/D19172 llvm-svn: 267022
* [ValueTracking] Make isImpliedCondition return an Optional<bool>. NFC.Chad Rosier2016-04-201-4/+5
| | | | | | Phabricator Revision: http://reviews.llvm.org/D19277 llvm-svn: 266904
* [ValueTracking] Improve isImpliedCondition for conditions with matching ↵Chad Rosier2016-04-191-3/+4
| | | | | | | | | | | | | | | operands. This patch improves SimplifyCFG to catch cases like: if (a < b) { if (a > b) <- known to be false unreachable; } Phabricator Revision: http://reviews.llvm.org/D18905 llvm-svn: 266767
* [SimlifyCFG] Prevent passes from destroying canonical loop structure, ↵Hyojin Sung2016-03-291-1/+4
| | | | | | | | | | | | | | | | | especially for nested loops When eliminating or merging almost empty basic blocks, the existence of non-trivial PHI nodes is currently used to recognize potential loops of which the block is the header and keep the block. However, the current algorithm fails if the loops' exit condition is evaluated only with volatile values hence no PHI nodes in the header. Especially when such a loop is an outer loop of a nested loop, the loop is collapsed into a single loop which prevent later optimizations from being applied (e.g., transforming nested loops into simplified forms and loop vectorization). The patch augments the existing PHI node-based check by adding a pre-test if the BB actually belongs to a set of loop headers and not eliminating it if yes. llvm-svn: 264697
* Revert "[SimlifyCFG] Prevent passes from destroying canonical loop ↵Reid Kleckner2016-03-281-4/+1
| | | | | | | | | | structure, especially for nested loops" This reverts commit r264596. It does not compile. llvm-svn: 264604
* [SimlifyCFG] Prevent passes from destroying canonical loop structure, ↵Hyojin Sung2016-03-281-1/+4
| | | | | | | | | | | | | | | | especially for nested loops When eliminating or merging almost empty basic blocks, the existence of non-trivial PHI nodes is currently used to recognize potential loops of which the block is the header and keep the block. However, the current algorithm fails if the loops' exit condition is evaluated only with volatile values hence no PHI nodes in the header. Especially when such a loop is an outer loop of a nested loop, the loop is collapsed into a single loop which prevent later optimizations from being applied (e.g., transforming nested loops into simplified forms and loop vectorization). The patch augments the existing PHI node-based check by adding a pre-test if the BB actually belongs to a set of loop headers and not eliminating it if yes. llvm-svn: 264596
* [JumpThreading] See through Cast InstructionsHaicheng Wu2016-03-161-0/+19
| | | | | | To capture more jump-thread opportunity. llvm-svn: 263618
* Revert "[JumpThreading] Simplify Instructions first in ↵Haicheng Wu2016-03-151-35/+20
| | | | | | | | ComputeValueKnownInPredecessors()" Not sure it handles undef properly. llvm-svn: 263605
* [JumpThreading] Simplify Instructions first in ComputeValueKnownInPredecessors()Haicheng Wu2016-02-261-20/+35
| | | | | | This change tries to find more opportunities to thread over basic blocks. llvm-svn: 261981
* [JumpThreading] Change a return of ComputeValueKnownInPredecessors()Haicheng Wu2016-02-081-1/+1
| | | | | | | | | Change a return statement of ComputeValueKnownInPredecessors() to be the same as the rest return statements of the function. Otherwise, it might return true with an empty Result when the current basic block has no predecessors and trigger the first assert of JumpThreading::ProcessThreadableEdges(). llvm-svn: 260110
* [opaque pointer types] [NFC] FindAvailableLoadedValue: take LoadInst instead ↵Eduard Burtescu2016-01-221-2/+2
| | | | | | | | | | | | of just the pointer. Reviewers: mjacob, dblaikie Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D16422 llvm-svn: 258477
* [JumpThreading] Don't forget to report that the IR changedDavid Majnemer2016-01-101-2/+3
| | | | | | | | | | | | | | JumpThreading's runOnFunction is supposed to return true if it made any changes. JumpThreading has a call to removeUnreachableBlocks which may result in changes to the IR but runOnFunction didn't appropriate account for this possibility, leading to badness. While we are here, make sure to call LazyValueInfo::eraseBlock in removeUnreachableBlocks; JumpThreading preserves LVI. This fixes PR26096. llvm-svn: 257279
* [JumpThreading] Use range-based for loops.Benjamin Kramer2016-01-091-82/+68
| | | | | | No functionality change intended. llvm-svn: 257262
* [JumpThreading] Split select that has constant conditions coming from the ↵Haicheng Wu2016-01-081-0/+63
| | | | | | | | | | | | | | | | | | | | PHI node Look for PHI/Select in the same BB of the form bb: %p = phi [false, %bb1], [true, %bb2], [false, %bb3], [true, %bb4], ... %s = select p, trueval, falseval And expand the select into a branch structure. This later enables jump-threading over bb in this pass. Using the similar approach of SimplifyCFG::FoldCondBranchOnPHI(), unfold select if the associated PHI has at least one constant. If the unfolded select is not jump-threaded, it will be folded again in the later optimizations. llvm-svn: 257198
* [JumpThreading] Fix opcode bonus in getJumpThreadDuplicationCost()Geoff Berry2015-12-291-10/+16
| | | | | | | | | | | | The code that was meant to adjust the duplication cost based on the terminator opcode was not being executed in cases where the initial threshold was hit inside the loop. Subscribers: mcrosier, llvm-commits Differential Revision: http://reviews.llvm.org/D15536 llvm-svn: 256568
* [BPI] Fix two potential divide-by-zero operations that are introduced in ↵Cong Hou2015-12-221-7/+12
| | | | | | r256263. llvm-svn: 256303
* [BPI] Replace weights by probabilities in BPI.Cong Hou2015-12-221-10/+18
| | | | | | | | | | | | This patch removes all weight-related interfaces from BPI and replace them by probability versions. With this patch, we won't use edge weight anymore in either IR or MC passes. Edge probabilitiy is a better representation in terms of CFG update and validation. Differential revision: http://reviews.llvm.org/D15519 llvm-svn: 256263
* [ValueTracking] Add parameters to isImpliedCondition; NFCSanjoy Das2015-11-061-1/+3
| | | | | | | | | | | | | | | | Summary: This change makes the `isImpliedCondition` interface similar to the rest of the functions in ValueTracking (in that it takes a DataLayout, AssumptionCache etc.). This is an NFC, intended to make a later diff less noisy. Depends on D14369 Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D14391 llvm-svn: 252333
* [JumpThreading] Use dominating conditions to prove implicationsSanjoy Das2015-10-281-2/+40
| | | | | | | | | | | | | | | Summary: If P branches to Q conditional on C and Q branches to R conditional on C' and C => C' then the branch conditional on C' can be folded to an unconditional branch. Reviewers: reames Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D13972 llvm-svn: 251557
OpenPOWER on IntegriCloud