summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Transforms/Scalar/JumpThreading.cpp
Commit message (Collapse)AuthorAgeFilesLines
* Reverting [JumpThreading] Preservation of DT and LVI across the passBrian M. Rzycki2017-12-131-136/+39
| | | | | | | Stage 2 bootstrap failed: http://lab.llvm.org:8011/builders/clang-x86_64-linux-selfhost-modules-2/builds/14434 llvm-svn: 320641
* [JumpThreading] Preservation of DT and LVI across the passBrian M. Rzycki2017-12-131-39/+136
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: See D37528 for a previous (non-deferred) version of this patch and its description. Preserves dominance in a deferred manner using a new class DeferredDominance. This reduces the performance impact of updating the DominatorTree at every edge insertion and deletion. A user may call DDT->flush() within JumpThreading for an up-to-date DT. This patch currently has one flush() at the end of runImpl() to ensure DT is preserved across the pass. LVI is also preserved to help subsequent passes such as CorrelatedValuePropagation. LVI is simpler to maintain and is done immediately (not deferred). The code to perfom the preversation was minimally altered and was simply marked as preserved for the PassManager to be informed. This extends the analysis available to JumpThreading for future enhancements. One example is loop boundary threading. Reviewers: dberlin, kuhar, sebpop Reviewed By: kuhar, sebpop Subscribers: hiraditya, llvm-commits Differential Revision: https://reviews.llvm.org/D40146 llvm-svn: 320612
* [JumpThreading] Minor comment cleanup. NFC. (test commit)Brian M. Rzycki2017-12-081-2/+2
| | | | llvm-svn: 320179
* Fix comment /NFCXinliang David Li2017-11-061-3/+4
| | | | llvm-svn: 317514
* [JumpThreading] Move two PredValueInfoTy vectors to a scope closer to their ↵Craig Topper2017-10-161-2/+2
| | | | | | usage. NFCI llvm-svn: 315941
* Revert r314435: "[JumpThreading] Preserve DT and LVI across the pass"Daniel Jasper2017-09-301-80/+29
| | | | | | | Causes a segfault on a builtbot (and in our internal bootstrapping of Clang). See Eli's response on the commit thread. llvm-svn: 314589
* [JumpThreading] Preserve DT and LVI across the passEvandro Menezes2017-09-281-29/+80
| | | | | | | | | | | | | | | | | JumpThreading now preserves dominance and lazy value information across the entire pass. The pass manager is also informed of this preservation with the goal of DT and LVI being recalculated fewer times overall during compilation. This change prepares JumpThreading for enhanced opportunities; particularly those across loop boundaries. Patch by: Brian Rzycki <b.rzycki@samsung.com>, Sebastian Pop <s.pop@samsung.com> Differential revision: https://reviews.llvm.org/D37528 llvm-svn: 314435
* [Transforms] Fix some Clang-tidy modernize-use-using and Include What You ↵Eugene Zelenko2017-09-131-23/+50
| | | | | | Use warnings; other minor fixes (NFC). llvm-svn: 313198
* Disable jump threading into loop headersKrzysztof Parzyszek2017-09-061-4/+9
| | | | | | | | | | | | | | | | | | | | | | Consider this type of a loop: for (...) { ... if (...) continue; ... } Normally, the "continue" would branch to the loop control code that checks whether the loop should continue iterating and which contains the (often) unique loop latch branch. In certain cases jump threading can "thread" the inner branch directly to the loop header, creating a second loop latch. Loop canonicalization would then transform this loop into a loop nest. The problem with this is that in such a loop nest neither loop is countable even if the original loop was. This may inhibit subsequent loop optimizations and be detrimental to performance. Differential Revision: https://reviews.llvm.org/D36404 llvm-svn: 312664
* [Profile] backward propagate profile info in JumpThreadingXinliang David Li2017-08-241-1/+115
| | | | | | | | Take-2 after fixing bugs in the original patch. Differential Revsion: http://reviews.llvm.org/D36864 llvm-svn: 311727
* Revert 311208, 311209Xinliang David Li2017-08-211-112/+1
| | | | llvm-svn: 311341
* Fix comment /NFCXinliang David Li2017-08-181-1/+1
| | | | llvm-svn: 311209
* [Profile] backward propagate profile info in JumpThreadingXinliang David Li2017-08-181-1/+112
| | | | | | Differential Revsion: http://reviews.llvm.org/D36864 llvm-svn: 311208
* [Value Tracking] Default argument to true and rename accordingly. NFC.Chad Rosier2017-08-011-4/+3
| | | | | | IMHO this is a bit more readable. llvm-svn: 309739
* [JumpThreading] Stop falsely preserving LazyValueInfo.Davide Italiano2017-07-281-1/+0
| | | | | | | | | | | | | | | | | | | | | | | | | | | JumpThreading claims to preserve LVI, but it doesn't preserve the analyses which LVI holds a reference to (e.g. the Dominator). In the current pass manager infrastructure, after JT runs, the PM frees these analyses (including DominatorTree) but preserves LVI. CorrelatedValuePropagation runs immediately after and queries a corrupted domtree, causing weird miscompiles. This commit disables the preservation of LVI for the time being. Eventually, we should either move LVI to a proper dependency tracking mechanism (i.e. an analyses shouldn't hold references to other analyses and compute them on demand if needed), or we should teach all the passes preserving LVI to preserve the analyses LVI depends on. The new pass manager has a mechanism to invalidate LVI in case one of the analyses it depends on becomes invalid, so this problem shouldn't exist (at least not in this immediate form), but handling of analyses holding references is still a very delicate subject. Fixes PR33917 (and rustc). llvm-svn: 309355
* [JumpThreading] Add an option to dump LazyValueInfo after the run.Davide Italiano2017-07-281-2/+15
| | | | | | Differential Revision: https://reviews.llvm.org/D35973 llvm-svn: 309353
* [SimplifyCFG] Defer folding unconditional branches to LateSimplifyCFG if it ↵Balaram Makam2017-07-191-4/+6
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | can destroy canonical loop structure. Summary: When simplifying unconditional branches from empty blocks, we pre-test if the BB belongs to a set of loop headers and keep the block to prevent passes from destroying canonical loop structure. However, the current algorithm fails if the destination of the branch is a loop header. Especially when such a loop's latch block is folded into loop header it results in additional backedges and LoopSimplify turns it into a nested loop which prevent later optimizations from being applied (e.g., loop unrolling and loop interleaving). This patch augments the existing algorithm by further checking if the destination of the branch belongs to a set of loop headers and defer eliminating it if yes to LateSimplifyCFG. Fixes PR33605: https://bugs.llvm.org/show_bug.cgi?id=33605 Reviewers: efriedma, mcrosier, pacxx, hsung, davidxl Reviewed By: efriedma Subscribers: ashutosh.nema, gberry, javed.absar, llvm-commits Differential Revision: https://reviews.llvm.org/D35411 llvm-svn: 308422
* [JumpThreading] Add a pattern to TryToUnfoldSelectInCurrBB()Haicheng Wu2017-07-141-32/+50
| | | | | | | | | | | | | | | | Add the following pattern to TryToUnfoldSelectInCurrBB() bb: %p = phi [0, %bb1], [1, %bb2], [0, %bb3], [1, %bb4], ... %c = cmp %p, 0 %s = select %c, trueval, falseval The Select in the above pattern will be unfolded and then jump-threaded. The current implementation does not allow CMP in the middle of PHI and Select. Differential Revision: https://reviews.llvm.org/D34762 llvm-svn: 308050
* Enhance synchscope representationKonstantin Zhuravlyov2017-07-111-1/+1
| | | | | | | | | | | | | | | | | | | | | | | | | | | OpenCL 2.0 introduces the notion of memory scopes in atomic operations to global and local memory. These scopes restrict how synchronization is achieved, which can result in improved performance. This change extends existing notion of synchronization scopes in LLVM to support arbitrary scopes expressed as target-specific strings, in addition to the already defined scopes (single thread, system). The LLVM IR and MIR syntax for expressing synchronization scopes has changed to use *syncscope("<scope>")*, where <scope> can be "singlethread" (this replaces *singlethread* keyword), or a target-specific name. As before, if the scope is not specified, it defaults to CrossThread/System scope. Implementation details: - Mapping from synchronization scope name/string to synchronization scope id is stored in LLVM context; - CrossThread/System and SingleThread scopes are pre-defined to efficiently check for known scopes without comparing strings; - Synchronization scope names are stored in SYNC_SCOPE_NAMES_BLOCK in the bitcode. Differential Revision: https://reviews.llvm.org/D21723 llvm-svn: 307722
* [JumpThreading] Teach jump threading how to analyze (and (cmp A, C1), (cmp ↵Craig Topper2017-06-231-0/+41
| | | | | | | | | | | | | | A, C2)) after InstCombine has turned it into (cmp (add A, C3), C4) Currently JumpThreading can use LazyValueInfo to analyze an 'and' or 'or' of compare if the compare is fed by a livein of a basic block. This can be used to to prove the condition can't be met for some predecessor and the jump from that predecessor can be moved to the false path of the condition. But if the compare is something that InstCombine turns into an add and a single compare, it can't be analyzed because the livein is now an input to the add and not the compare. This patch adds a new method to LVI to get a ConstantRange on an edge. Then we teach jump threading to detect the add livein feeding a compare and to get the ConstantRange and propagate it. Differential Revision: https://reviews.llvm.org/D33262 llvm-svn: 306085
* [JumpThreading] Use some temporary variables to reduce the number of times ↵Craig Topper2017-06-231-12/+16
| | | | | | | | we call the same methods. NFC A future patch will add even more uses of these variables. llvm-svn: 306084
* [JumpThreading][LVI] Invalidate LVI information after blocks are mergedAnna Thomas2017-06-191-0/+31
| | | | | | | | | | | | | | | | | | | Summary: After a single predecessor is merged into a basic block, we need to invalidate the LVI information for the new merged block, when LVI is not provably true for all of instructions in the new block. The test cases added show the correct LVI information using the LVI printer pass. Reviewers: reames, dberlin, davide, sanjoy Reviewed by: dberlin, davide Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D34108 llvm-svn: 305699
* [BPI] Don't assume that strcmp returning >0 is more likely than <0John Brawn2017-06-081-2/+2
| | | | | | | | | | | | | | | | | | | | The zero heuristic assumes that integers are more likely positive than negative, but this also has the effect of assuming that strcmp return values are more likely positive than negative. Given that for nonzero strcmp return values it's the ordering of arguments that determines the sign of the result there's no reason to assume that's true. Fix this by inspecting the LHS of the compare and using TargetLibraryInfo to decide if it's strcmp-like, and if so only assume that nonzero is more likely than zero i.e. strings are more often different than the same. This causes a slight code generation change in the spec2006 benchmark 403.gcc, but with no noticeable performance impact. The intent of this patch is to allow better optimisation of dhrystone on Cortex-M cpus, but currently it won't as there are also some changes that need to be made to if-conversion. Differential Revision: https://reviews.llvm.org/D33934 llvm-svn: 304970
* Sort the remaining #include lines in include/... and lib/....Chandler Carruth2017-06-061-3/+3
| | | | | | | | | | | | | | | | | | | | | | | | | I did this a long time ago with a janky python script, but now clang-format has built-in support for this. I fed clang-format every line with a #include and let it re-sort things according to the precise LLVM rules for include ordering baked into clang-format these days. I've reverted a number of files where the results of sorting includes isn't healthy. Either places where we have legacy code relying on particular include ordering (where possible, I'll fix these separately) or where we have particular formatting around #include lines that I didn't want to disturb in this patch. This patch is *entirely* mechanical. If you get merge conflicts or anything, just ignore the changes in this patch and run clang-format over your #include lines in the files. Sorry for any noise here, but it is important to keep these things stable. I was seeing an increasing number of patches with irrelevant re-ordering of #include lines because clang-format was used. This patch at least isolates that churn, makes it easy to skip when resolving conflicts, and gets us to a clean baseline (again). llvm-svn: 304787
* [JumpThreading] Safely replace uses of conditionAnna Thomas2017-05-231-2/+40
| | | | | | | | | | | | | | | | | | | | | | This patch builds over https://reviews.llvm.org/rL303349 and replaces the use of the condition only if it is safe to do so. We should not blindly RAUW the condition if experimental.guard or assume is a use of that condition. This is because LVI may have used the guard/assume to identify the value of the condition, and RUAWing will fold the guard/assume and uses before the guards/assumes. Reviewers: sanjoy, reames, trentxintong, mkazantsev Reviewed by: sanjoy, reames Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D33257 llvm-svn: 303633
* [IR] De-virtualize ~Value to save a vptrReid Kleckner2017-05-181-1/+1
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: Implements PR889 Removing the virtual table pointer from Value saves 1% of RSS when doing LTO of llc on Linux. The impact on time was positive, but too noisy to conclusively say that performance improved. Here is a link to the spreadsheet with the original data: https://docs.google.com/spreadsheets/d/1F4FHir0qYnV0MEp2sYYp_BuvnJgWlWPhWOwZ6LbW7W4/edit?usp=sharing This change makes it invalid to directly delete a Value, User, or Instruction pointer. Instead, such code can be rewritten to a null check and a call Value::deleteValue(). Value objects tend to have their lifetimes managed through iplist, so for the most part, this isn't a big deal. However, there are some places where LLVM deletes values, and those places had to be migrated to deleteValue. I have also created llvm::unique_value, which has a custom deleter, so it can be used in place of std::unique_ptr<Value>. I had to add the "DerivedUser" Deleter escape hatch for MemorySSA, which derives from User outside of lib/IR. Code in IR cannot include MemorySSA headers or call the MemoryAccess object destructors without introducing a circular dependency, so we need some level of indirection. Unfortunately, no class derived from User may have any virtual methods, because adding a virtual method would break User::getHungOffOperands(), which assumes that it can find the use list immediately prior to the User object. I've added a static_assert to the appropriate OperandTraits templates to help people avoid this trap. Reviewers: chandlerc, mehdi_amini, pete, dberlin, george.burgess.iv Reviewed By: chandlerc Subscribers: krytarowski, eraman, george.burgess.iv, mzolotukhin, Prazek, nlewycky, hans, inglorion, pcc, tejohnson, dberlin, llvm-commits Differential Revision: https://reviews.llvm.org/D31261 llvm-svn: 303362
* [JumpThreading] Dont RAUW condition incorrectlyAnna Thomas2017-05-181-17/+14
| | | | | | | | | | | | | | | | | | | Summary: We have a bug when RAUWing the condition if experimental.guard or assumes is a use of that condition. This is because LazyValueInfo may have used the guards/assumes to identify the value of the condition at the end of the block. RAUW replaces the uses at the guard/assume as well as uses before the guard/assume. Both of these are incorrect. For now, disable RAUW for conditions and fix the logic as a next step: https://reviews.llvm.org/D33257 Reviewers: sanjoy, reames, trentxintong Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D33279 llvm-svn: 303349
* [JumpThreading] When processing compares, explicitly check that the result ↵Craig Topper2017-05-041-1/+1
| | | | | | | | type is not a vector rather than check for it being an integer. Compares always return a scalar integer or vector of integers. isIntegerTy returns false for vectors, but that's not completely obvious. So using isVectorTy is less confusing. llvm-svn: 302198
* [JumpThreading] Change a dyn_cast that is already protected by an isa check ↵Craig Topper2017-05-041-16/+14
| | | | | | | | to a static cast. Combine the with another static cast. NFC Differential Revision: https://reviews.llvm.org/D32874 llvm-svn: 302197
* Take indirect branch into account as well when folding.Xin Tong2017-05-011-6/+10
| | | | | | | | We may not be able to rewrite indirect branch target, but we also want to take it into account when folding, i.e. if it and all its successor's predecessors go to the same destination, we can fold, i.e. no need to thread. llvm-svn: 301816
* [JumpThread] Add some assertions for expected ConstantInt/BlockAddressXin Tong2017-05-011-2/+5
| | | | llvm-svn: 301808
* [JumpThread] Do RAUW in case Cond folds to a constant in the CFGXin Tong2017-05-011-8/+24
| | | | | | | | | | | | | | Summary: [JumpThread] Do RAUW in case Cond folds to a constant in the CFG Reviewers: sanjoy Reviewed By: sanjoy Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D32407 llvm-svn: 301804
* Kill off the old SimplifyInstruction API by converting remaining users.Daniel Berlin2017-04-281-3/+4
| | | | llvm-svn: 301673
* [JumpThread] We want to fold (not thread) when all predecessor go to single ↵Xin Tong2017-04-231-0/+30
| | | | | | | | | | | | | | | | | | | | | BB's successor. Summary: In case all predecessor go to a single successor of current BB. We want to fold (not thread). I failed to update the phi nodes properly in the last patch https://reviews.llvm.org/rL300657. Phi nodes values are per predecessor in LLVM. Reviewers: sanjoy Reviewed By: sanjoy Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D32400 llvm-svn: 301139
* 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
OpenPOWER on IntegriCloud