summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Transforms/Scalar/JumpThreading.cpp
Commit message (Collapse)AuthorAgeFilesLines
* Revert r300657 due to crashes in stage2 of bootstraps:Chandler Carruth2017-04-191-27/+0
| | | | | | | | | | | | http://lab.llvm.org:8011/builders/clang-with-lto-ubuntu/builds/2476/steps/build-stage2-LLVMgold.so/logs/stdio http://bb.pgr.jp/builders/clang-3stage-x86_64-linux/builds/15036/steps/build_llvmclang/logs/stdio I've updated the commit thread, reverting to get the bots back to green. Original commit summary: [JumpThread] We want to fold (not thread) when all predecessor go to single BB's successor. llvm-svn: 300662
* [JumpThread] We want to fold (not thread) when all predecessor go to single ↵Xin Tong2017-04-191-0/+27
| | | | | | | | | | | | | | | | BB's successor. . Summary: In case all predecessor go to a single successor of current BB. We want to fold (not thread). Reviewers: efriedma, sanjoy Reviewed By: sanjoy Subscribers: dberlin, majnemer, llvm-commits Differential Revision: https://reviews.llvm.org/D30869 llvm-svn: 300657
* [IR] Redesign the case iterator in SwitchInst to actually be an iteratorChandler Carruth2017-04-121-1/+1
| | | | | | | | | | | | | | | | and to expose a handle to represent the actual case rather than having the iterator return a reference to itself. All of this allows the iterator to be used with common STL facilities, standard algorithms, etc. Doing this exposed some missing facilities in the iterator facade that I've fixed and required some work to the actual iterator to fully support the necessary API. Differential Revision: https://reviews.llvm.org/D31548 llvm-svn: 300032
* Correct a rebase mistake.Xin Tong2017-03-191-2/+2
| | | | | | Left out AA in jumpthreading SimplifyPartiallyRedundantLoad llvm-svn: 298219
* [JumpThreading] Perform phi-translation in SimplifyPartiallyRedundantLoad.Xin Tong2017-03-191-18/+33
| | | | | | | | | | | | | | | | | | | Summary: In case we are loading on a phi-load in SimplifyPartiallyRedundantLoad. Try to phi translate it into incoming values in the predecessors before we search for available loads. This needs https://reviews.llvm.org/D30524 Reviewers: davide, sanjoy, efriedma, dberlin, rengolin Reviewed By: dberlin Subscribers: junbuml, llvm-commits Differential Revision: https://reviews.llvm.org/D30543 llvm-svn: 298217
* [JumpThread] Use AA in SimplifyPartiallyRedundantLoad()Jun Bum Lim2017-03-081-11/+20
| | | | | | | | | | | | | | Summary: Use AA when scanning to find an available load value. Reviewers: rengolin, mcrosier, hfinkel, trentxintong, dberlin Reviewed By: rengolin, dberlin Subscribers: aemerson, dberlin, llvm-commits Differential Revision: https://reviews.llvm.org/D30352 llvm-svn: 297284
* [JumpThread] Simplify CmpInst-as-Condition branch-folding a bit.Xin Tong2017-03-071-4/+11
| | | | | | | | | | | | | | Summary: Simplify CmpInst-as-Condition branch-folding a bit. Reviewers: sanjoy, efriedma Reviewed By: efriedma Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D30429 llvm-svn: 297186
* Fix typo. NFCIXin Tong2017-03-021-1/+1
| | | | llvm-svn: 296735
* Empty line. NFCIXin Tong2017-02-281-1/+0
| | | | llvm-svn: 296438
* Empty line. NFCIXin Tong2017-02-271-1/+0
| | | | llvm-svn: 296392
* Update comments. NFCIXin Tong2017-02-261-2/+2
| | | | llvm-svn: 296298
* Empty line. NFCIXin Tong2017-02-251-1/+0
| | | | llvm-svn: 296250
* [JumpThreading] Re-enable JumpThreading for guardsSanjoy Das2017-02-171-15/+158
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: JumpThreading for guards feature has been reverted at https://reviews.llvm.org/rL295200 due to the following problem: the feature used the following algorithm for detection of diamond patters: 1. Find a block with 2 predecessors; 2. Check that these blocks have a common single parent; 3. Check that the parent's terminator is a branch instruction. The problem is that these checks are insufficient. They may pass for a non-diamond construction in case if those two predecessors are actually the same block. This may happen if parent's terminator is a br (either conditional or unconditional) to a block that ends with "switch" instruction with exactly two branches going to one block. This patch re-enables the JumpThreading for guards and fixes this issue by adding the check that those found predecessors are actually different blocks. This guarantees that parent's terminator is a conditional branch with exactly 2 different successors, which is now ensured by assertions. It also adds two more tests for this situation (with parent's terminator being a conditional and an unconditional branch). Patch by Max Kazantsev! Reviewers: anna, sanjoy, reames Reviewed By: sanjoy Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D30036 llvm-svn: 295410
* Revert "[JumpThreading] Thread through guards"Anna Thomas2017-02-151-152/+15
| | | | | | | | | This reverts commit r294617. We fail on an assert while trying to get a condition from an unconditional branch. llvm-svn: 295200
* [JumpThreading] Thread through guardsSanjoy Das2017-02-091-15/+152
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: This patch allows JumpThreading also thread through guards. Virtually, guard(cond) is equivalent to the following construction: if (cond) { do something } else {deoptimize} Yet it is not explicitly converted into IFs before lowering. This patch enables early threading through guards in simple cases. Currently it covers the following situation: if (cond1) { // code A } else { // code B } // code C guard(cond2) // code D If there is implication cond1 => cond2 or !cond1 => cond2, we can transform this construction into the following: if (cond1) { // code A // code C } else { // code B // code C guard(cond2) } // code D Thus, removing the guard from one of execution branches. Patch by Max Kazantsev! Reviewers: reames, apilipenko, igor-laevsky, anna, sanjoy Reviewed By: sanjoy Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D29620 llvm-svn: 294617
* [JumpThread] Enhance finding partial redundant loads by continuing scanning ↵Jun Bum Lim2017-02-021-4/+19
| | | | | | | | | | | | | | | | single predecessor Summary: While scanning predecessors to find an available loaded value, if the predecessor has a single predecessor, we can continue scanning through the single predecessor. Reviewers: mcrosier, rengolin, reames, davidxl, haicheng Reviewed By: rengolin Subscribers: zzheng, llvm-commits Differential Revision: https://reviews.llvm.org/D29200 llvm-svn: 293896
* [JumpThread] No need to erase BB from LoopHeaders. NFC.Jun Bum Lim2017-02-011-14/+1
| | | | | | | | | | | | | | Summary: No need to try to ease BB from LoopHeaders as we already know that BB is not in LoopHeaders. Reviewers: hsung, majnemer, mcrosier, haicheng, rengolin Reviewed By: rengolin Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D29232 llvm-svn: 293802
* [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
OpenPOWER on IntegriCloud