summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Transforms/Scalar/JumpThreading.cpp
Commit message (Collapse)AuthorAgeFilesLines
* Revert r332168: "Reapply "[PR16756] Use SSAUpdaterBulk in JumpThreading.""Michael Zolotukhin2018-07-051-19/+15
| | | | | | | There were a couple of issues reported (PR38047, PR37929) - I'll reland the patch when I figure out and fix the rootcause. llvm-svn: 336393
* [JumpThreading] Don't try to rewrite a use if it's already valid.Michael Zolotukhin2018-06-261-10/+12
| | | | | | | | | | | | | | | | | | | Summary: When recording uses we need to rewrite after cloning a loop we need to check if the use is not dominated by the original def. The initial assumption was that the cloned basic block will introduce a new path and thus the original def will only dominate the use if they are in the same BB, but as the reproducer from PR37745 shows it's not always the case. This fixes PR37745. Reviewers: haicheng, Ka-Ka Subscribers: hiraditya, llvm-commits Differential Revision: https://reviews.llvm.org/D48111 llvm-svn: 335675
* [NFC] fix trivial typos in commentsHiroshi Inoue2018-06-141-3/+3
| | | | llvm-svn: 334687
* Move Analysis/Utils/Local.h back to TransformsDavid Blaikie2018-06-041-1/+1
| | | | | | | | | | Review feedback from r328165. Split out just the one function from the file that's used by Analysis. (As chandlerc pointed out, the original change only moved the header and not the implementation anyway - which was fine for the one function that was used (since it's a template/inlined in the header) but not in general) llvm-svn: 333954
* [JumpThreading] Fix some strange formatting of code inside LLVM_DEBUG. NFCCraig Topper2018-05-311-5/+5
| | | | | | I don't know if clang-format got confused here or what. llvm-svn: 333675
* Rename DEBUG macro to LLVM_DEBUG.Nicola Zaghen2018-05-141-38/+41
| | | | | | | | | | | | | | | | The DEBUG() macro is very generic so it might clash with other projects. The renaming was done as follows: - git grep -l 'DEBUG' | xargs sed -i 's/\bDEBUG\s\?(/LLVM_DEBUG(/g' - git diff -U0 master | ../clang/tools/clang-format/clang-format-diff.py -i -p1 -style LLVM - Manual change to APInt - Manually chage DOCS as regex doesn't match it. In the transition period the DEBUG() macro is still present and aliased to the LLVM_DEBUG() one. Differential Revision: https://reviews.llvm.org/D43624 llvm-svn: 332240
* Reapply "[PR16756] Use SSAUpdaterBulk in JumpThreading."Michael Zolotukhin2018-05-121-26/+30
| | | | | | | | | Stage3/stage4 bootstrap miscompares should be fixed by a non-determinism fix in IDF (r332167). This reverts commit r330446. llvm-svn: 332168
* [STLExtras] Add distance() for ranges, pred_size(), and succ_size()Vedant Kumar2018-05-101-4/+3
| | | | | | | | | | | This commit adds a wrapper for std::distance() which works with ranges. As it would be a common case to write `distance(predecessors(BB))`, this also introduces `pred_size()` and `succ_size()` helpers to make that easier to write. Differential Revision: https://reviews.llvm.org/D46668 llvm-svn: 332057
* Fix the issue that ComputeValueKnownInPredecessors only handles the case whenWei Mi2018-05-011-3/+15
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | phi is on lhs of a comparison op. For the following testcase, L1: %t0 = add i32 %m, 7 %t3 = icmp eq i32* %t2, null br i1 %t3, label %L3, label %L2 L2: %t4 = load i32, i32* %t2, align 4 br label %L3 L3: %t5 = phi i32 [ %t0, %L1 ], [ %t4, %L2 ] %t6 = icmp eq i32 %t0, %t5 br i1 %t6, label %L4, label %L5 We know if we go through the path L1 --> L3, %t6 should always be true. However currently, if the rhs of the eq comparison is phi, JumpThreading fails to evaluate %t6 to true. And we know that Instcombine cannot guarantee always canonicalizing phi to the left hand side of the comparison operation according to the operand priority comparison mechanism in instcombine. The patch handles the case when rhs of the comparison op is a phi. Differential Revision: https://reviews.llvm.org/D46275 llvm-svn: 331266
* Revert r330431.Michael Zolotukhin2018-04-201-30/+26
| | | | | | There are still stage3/stage4 miscompares :( llvm-svn: 330446
* Revert "Revert r330403 and r330413."Michael Zolotukhin2018-04-201-26/+30
| | | | | | | | | | | Reapply the patches with a fix. Thanks Ilya and Hans for the reproducer! This reverts commit r330416. The issue was that removing predecessors invalidated uses that we stored for rewrite. The fix is to finish manipulating with CFG before we select uses for rewrite. llvm-svn: 330431
* Revert r330403 and r330413.Ilya Biryukov2018-04-201-20/+16
| | | | | | | | | | | | | | | | Revert r330413: "[SSAUpdaterBulk] Use SmallVector instead of DenseMap for storing rewrites." Revert r330403 "Reapply "[PR16756] Use SSAUpdaterBulk in JumpThreading." one more time." r330403 commit seems to crash clang during our integrate while doing PGO build with the following stacktrace: #2 llvm::SSAUpdaterBulk::RewriteAllUses(llvm::DominatorTree*, llvm::SmallVectorImpl<llvm::PHINode*>*) #3 llvm::JumpThreadingPass::ThreadEdge(llvm::BasicBlock*, llvm::SmallVectorImpl<llvm::BasicBlock*> const&, llvm::BasicBlock*) #4 llvm::JumpThreadingPass::ProcessThreadableEdges(llvm::Value*, llvm::BasicBlock*, llvm::jumpthreading::ConstantPreference, llvm::Instruction*) #5 llvm::JumpThreadingPass::ProcessBlock(llvm::BasicBlock*) The crash happens while compiling 'lib/Analysis/CallGraph.cpp'. r3340413 is reverted due to conflicting changes. llvm-svn: 330416
* [SSAUpdaterBulk] Use SmallVector instead of DenseMap for storing rewrites.Michael Zolotukhin2018-04-201-3/+1
| | | | llvm-svn: 330413
* Reapply "[PR16756] Use SSAUpdaterBulk in JumpThreading." one more time.Michael Zolotukhin2018-04-201-16/+22
| | | | | | | | | Hopefully, changing set to vector removes nondeterminism detected by some bots, or the new assert will catch something. This reverts commit r330180. llvm-svn: 330403
* Revert "Reapply "[PR16756] Use SSAUpdaterBulk in JumpThreading." again."Michael Zolotukhin2018-04-171-22/+15
| | | | | | This reverts r330175. There are still stage3/stage4 miscompares. llvm-svn: 330180
* Reapply "[PR16756] Use SSAUpdaterBulk in JumpThreading." again.Michael Zolotukhin2018-04-171-15/+22
| | | | | | | | | One more, hopefully the last, bug is fixed: when forming UsesToRewrite we should ignore phi operands coming from edges that we want to delete. This reverts r329910. llvm-svn: 330175
* Revert "Reapply "[PR16756] Use SSAUpdaterBulk in JumpThreading." one more time."Benjamin Kramer2018-04-121-18/+13
| | | | | | This reverts commit r329865. Causes stage2/stage3 miscompare. llvm-svn: 329910
* Reapply "[PR16756] Use SSAUpdaterBulk in JumpThreading." one more time.Michael Zolotukhin2018-04-111-13/+18
| | | | | | This reapplies commit r329644. llvm-svn: 329865
* Revert "[PR16756] Use SSAUpdaterBulk in JumpThreading." one more time.Michael Zolotukhin2018-04-101-18/+13
| | | | | | This reverts r329661. Bots are still unhappy. llvm-svn: 329666
* Revert "Revert "[PR16756] Use SSAUpdaterBulk in JumpThreading.""Michael Zolotukhin2018-04-101-13/+18
| | | | | | This reapplies commit r329644. llvm-svn: 329661
* Revert "[PR16756] Use SSAUpdaterBulk in JumpThreading."Michael Zolotukhin2018-04-101-18/+13
| | | | | | This reverts commit r329644. llvm-svn: 329650
* [PR16756] Use SSAUpdaterBulk in JumpThreading.Michael Zolotukhin2018-04-091-13/+18
| | | | | | | | | | | | | | | | | Summary: SSAUpdater is a bottleneck in JumpThreading, and this patch improves the situation by using SSAUpdaterBulk instead. Compile time impact: no noticable changes on CTMark, a big improvement on the test from PR16756. Reviewers: dberlin, davide, MatzeB Subscribers: llvm-commits, hiraditya Differential Revision: https://reviews.llvm.org/D44282 llvm-svn: 329644
* [JumpThreading] Don't select an edge that we know we can't threadHaicheng Wu2018-03-291-1/+16
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | In r312664 (D36404), JumpThreading stopped threading edges into loop headers. Unfortunately, I observed a significant performance regression as a result of this change. Upon further investigation, the problematic pattern looked something like this (after many high level optimizations): while (true) { bool cond = ...; if (!cond) { <body> } if (cond) break; } Now, naturally we want jump threading to essentially eliminate the second if check and hook up the edges appropriately. However, the above mentioned change, prevented it from doing this because it would have to thread an edge into the loop header. Upon further investigation, what is happening is that since both branches are threadable, JumpThreading picks one of them at arbitrarily. In my case, because of the way that the IR ended up, it tended to pick the one to the loop header, bailing out immediately after. However, if it had picked the one to the exit block, everything would have worked out fine (because the only remaining branch would then be folded, not thraded which is acceptable). Thus, to fix this problem, we can simply eliminate loop headers from consideration as possible threading targets earlier, to make sure that if there are multiple eligible branches, we can still thread one of the ones that don't target a loop header. Patch by Keno Fischer! Differential Revision: https://reviews.llvm.org/D42260 llvm-svn: 328798
* Fix a couple of layering violations in TransformsDavid Blaikie2018-03-211-1/+1
| | | | | | | | | | | | | Remove #include of Transforms/Scalar.h from Transform/Utils to fix layering. Transforms depends on Transforms/Utils, not the other way around. So remove the header and the "createStripGCRelocatesPass" function declaration (& definition) that is unused and motivated this dependency. Move Transforms/Utils/Local.h into Analysis because it's used by Analysis/MemoryBuiltins.cpp. llvm-svn: 328165
* [JumpThreading] Track unreachable BBs to avoid processingBrian M. Rzycki2018-03-161-47/+37
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | JumpThreading iterates over F until the IR quiesces. Transforming unreachable BBs increases compile time and it is also possible to never stabilize causing JumpThreading to hang. An older attempt at fixing this problem was D3991 where removeUnreachableBlocks(F) was called before JumpThreading began. This has a few drawbacks: * expensive - the routine attempts to fix up the IR to identify additional BBs that can be removed along with unreachable BBs. * aggressive - does not identify and preserve the shape of the IR. At a minimum it does not preserve loop hierarchies. * invasive - altering reachable blocks it may disrupt IR shapes that could have otherwise been JumpThreaded. This patch avoids removeUnreachableBlocks(F) and instead tracks unreachable BBs in a SmallPtrSet using DominatorTree to validate the initial state of all BBs. We then rely on subsequent passes to identify and remove these unreachable blocks from F. Reviewers: dberlin, sebpop, kuhar, dinesh.d Reviewed by: sebpop, kuhar Subscribers: hiraditya, uabelho, llvm-commits Differential Revision: https://reviews.llvm.org/D44177 llvm-svn: 327713
* [JumpThreading] Don't restrict cast-traversal to i1Chad Rosier2018-03-091-3/+1
| | | | | | | | | | | | | | | | | | | In r263618, JumpThreading learned to look trough simple cast instructions, but only if the source of those cast instructions was a phi/cmp i1 (in an effort to limit compile time effects). I think this condition is too restrictive. For switches with limited value range, InstCombine will readily introduce an extra trunc instruction to a smaller integer type (e.g. from i8 to i2), leaving us in the somewhat perverse situation that jump-threading would work before running instcombine, but not after. Since instcombine produces this pattern, I think we need to consider it canonical and support it in JumpThreading. In general, for limiting recursion, I think the existing restriction to phi and cmp nodes should be sufficient to avoid looking through unprofitable chains of instructions. Patch by Keno Fischer! Differential Revision: https://reviews.llvm.org/D42262 llvm-svn: 327150
* [NFC] Factor out a helper function for checking if a block has a potential ↵Philip Reames2018-03-081-3/+1
| | | | | | early implicit exit. llvm-svn: 327065
* [JumpThreading] PR36133 enable/disable DominatorTree for LVI analysisBrian M. Rzycki2018-02-161-0/+37
| | | | | | | | | | | | | | | | | | | | | | Summary: The LazyValueInfo pass caches a copy of the DominatorTree when available. Whenever there are pending DominatorTree updates within JumpThreading's DeferredDominance object we cannot use the cached DT for LVI analysis. This commit adds the new methods enableDT() and disableDT() to LVI. JumpThreading also sets the appropriate usage model before calling LVI analysis methods. Fixes https://bugs.llvm.org/show_bug.cgi?id=36133 Reviewers: sebpop, dberlin, kuhar Reviewed by: sebpop, kuhar Subscribers: uabelho, llvm-commits, aprantl, hiraditya, a.elovikov Differential Revision: https://reviews.llvm.org/D42717 llvm-svn: 325356
* [JumpThreading][NFC] Rename LoadInst variablesBrian M. Rzycki2018-01-291-43/+46
| | | | | | | | | | | | | | | | | | Summary: The JumpThreading pass has several locations where to the variable name LI refers to a LoadInst type. This is confusing and inhibits the ability to use LI for LoopInfo as a member of the JumpThreading class. Minor formatting and comments were also altered to reflect this change. Reviewers: dberlin, kuba, spop, sebpop Reviewed by: sebpop Subscribers: sebpop, hiraditya, llvm-commits Differential Revision: https://reviews.llvm.org/D42601 llvm-svn: 323695
* [JumpThreading] Preservation of DT and LVI across the passBrian M. Rzycki2018-01-121-39/+135
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 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 perform the preversation was minimally altered and simply marked as preserved for the PassManager to be informed. This extends the analysis available to JumpThreading for future enhancements such as threading across loop headers. Reviewers: dberlin, kuhar, sebpop Reviewed By: kuhar, sebpop Subscribers: mgorny, dmgreen, kuba, rnk, rsmith, hiraditya, llvm-commits Differential Revision: https://reviews.llvm.org/D40146 llvm-svn: 322401
* Revert "[JumpThreading] Preservation of DT and LVI across the pass"Reid Kleckner2018-01-041-135/+39
| | | | | | | This reverts r321825, it causes crashes in Chromium. Reproducer forthcoming. llvm-svn: 321832
* [JumpThreading] Preservation of DT and LVI across the passBrian M. Rzycki2018-01-041-39/+135
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 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: 321825
* Use phi ranges to simplify code. No functionality change intended.Benjamin Kramer2017-12-301-4/+3
| | | | llvm-svn: 321585
* Add hasProfileData() to check if a function has profile data. NFC.Easwaran Raman2017-12-221-3/+2
| | | | | | | | | | | | | | | | | | | Summary: This replaces calls to getEntryCount().hasValue() with hasProfileData that does the same thing. This refactoring is useful to do before adding synthetic function entry counts but also a useful cleanup IMO even otherwise. I have used hasProfileData instead of hasRealProfileData as David had earlier suggested since I think profile implies "real" and I use the phrase "synthetic entry count" and not "synthetic profile count" but I am fine calling it hasRealProfileData if you prefer. Reviewers: davidxl, silvas Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D41461 llvm-svn: 321331
* [JumpThreading] Restrict PRE across instructions that don't pass control to ↵Max Kazantsev2017-12-191-0/+14
| | | | | | | | | | | | | | successors PRE in JumpThreading should not be able to hoist copy of non-speculable loads across instructions that don't always transfer execution to their successors, otherwise they may introduce an unsafe load which otherwise would not be executed. The same problem for GVN was fixed as rL316975. Differential Revision: https://reviews.llvm.org/D40347 llvm-svn: 321063
* 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
OpenPOWER on IntegriCloud