summaryrefslogtreecommitdiffstats
path: root/llvm/test/Transforms/JumpThreading
Commit message (Collapse)AuthorAgeFilesLines
* Backport 4878aa36d4a [ValueLattice] Add new state for undef constants.Florian Hahn2020-05-181-0/+61
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: NOTE: I mostly put it on Phabricator to make it easy for other people to fetch & check if that fixes a bug. This patch backports 4878aa36d4a and required earlier patches onto the release/10.x branch. It includes the following patches: aa5ebfdf205de6d599c1fed3161da3b63b6f0bef [ValueLattice] Make mark* functions public, return if value changed. c1943b42c5b7feff5d0e0c1358d02889e2be165f [ValueLattice] Update markConstantRange to return false equal ranges. e30c257811f62fea21704caa961c61e4559de202 [CVP,SCCP] Precommit test for D75055. 4878aa36d4aa27df644430139fab2734fde4a000 [ValueLattice] Add new state for undef constants. All patches except the last one apply cleanly. For the last one, the changes to SCCP.cpp were stripped, because SCCP does not yet use ValueLattice on release/10.x. Otherwise we would have to pull in more additional changes. Subscribers: tstellar, hiraditya, llvm-commits Tags: #llvm Differential Revision: https://reviews.llvm.org/D76596
* Revert "[JumpThreading] Thread jumps through two basic blocks"Kazu Hirata2020-01-082-115/+0
| | | | | | | | It looks like my patch breaks the sanitizer-windows build: http://lab.llvm.org:8011/builders/sanitizer-windows/builds/56324 This reverts commit ead815924e6ebeaf02c31c37ebf7a560b5fdf67b.
* [JumpThreading] Thread jumps through two basic blocksKazu Hirata2020-01-082-0/+115
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: This patch teaches JumpThreading.cpp to thread through two basic blocks like: bb3: %var = phi i32* [ null, %bb1 ], [ @a, %bb2 ] %tobool = icmp eq i32 %cond, 0 br i1 %tobool, label %bb4, label ... bb4: %cmp = icmp eq i32* %var, null br i1 %cmp, label bb5, label bb6 by duplicating basic blocks like bb3 above. Once we duplicate bb3 as bb3.dup and redirect edge bb2->bb3 to bb2->bb3.dup, we have: bb3: %var = phi i32* [ @a, %bb2 ] %tobool = icmp eq i32 %cond, 0 br i1 %tobool, label %bb4, label ... bb3.dup: %var = phi i32* [ null, %bb1 ] %tobool = icmp eq i32 %cond, 0 br i1 %tobool, label %bb4, label ... bb4: %cmp = icmp eq i32* %var, null br i1 %cmp, label bb5, label bb6 Then the existing code in JumpThreading.cpp can thread edge bb3.dup->bb4 through bb4 and eventually create bb3.dup->bb5. Reviewers: wmi Subscribers: hiraditya, jfb, llvm-commits Tags: #llvm Differential Revision: https://reviews.llvm.org/D70247
* Migrate function attribute "no-frame-pointer-elim"="false" to ↵Fangrui Song2019-12-241-1/+1
| | | | "frame-pointer"="none" as cleanups after D56351
* Temporarily revert "Reapply [LVI] Normalize pointer behavior" and "[LVI] ↵Jordan Rupprecht2019-12-201-2/+1
| | | | | | Restructure caching" This reverts commits 7e18aeba5062cd4324a9efb7bc25c9dbc4a34c2c (D70376) 21fbd5587cdfa11dabb3aeb0ead2d3d5fd0b490d (D69914) due to increased memory usage.
* Reapply [LVI] Normalize pointer behaviorNikita Popov2019-12-131-1/+2
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This is a rebase of the change over D70376, which fixes an LVI cache invalidation issue that also affected this patch. ----- Related to D69686. As noted there, LVI currently behaves differently for integer and pointer values: For integers, the block value is always valid inside the basic block, while for pointers it is only valid at the end of the basic block. I believe the integer behavior is the correct one, and CVP relies on it via its getConstantRange() uses. The reason for the special pointer behavior is that LVI checks whether a pointer is dereferenced in a given basic block and marks it as non-null in that case. Of course, this information is valid only after the dereferencing instruction, or in conservative approximation, at the end of the block. This patch changes the treatment of dereferencability: Instead of including it inside the block value, we instead treat it as something similar to an assume (it essentially is a non-nullness assume) and incorporate this information in intersectAssumeOrGuardBlockValueConstantRange() if the context instruction is the terminator of the basic block. This happens either when determining an edge-value internally in LVI, or when a terminator was explicitly passed to getValueAt(). The latter case makes this change not fully NFC, because we can now fold terminator icmps based on the dereferencability information in the same block. This is the reason why I changed one JumpThreading test (it would optimize the condition away without the change). Of course, we do not want to recompute dereferencability on each intersectAssume call, so we need a new cache for this. The dereferencability analysis requires walking the entire basic block and computing underlying objects of all memory operands. This was previously done separately for each queried pointer value. In the new implementation (both because this makes the caching simpler, and because it is faster), I instead only walk the full BB once and cache all the dereferenced pointers. So the traversal is now performed only once per BB, instead of once per queried pointer value. I think the overall model now makes more sense than before, and there will be no more pitfalls due to differing integer/pointer behavior. Differential Revision: https://reviews.llvm.org/D69914
* [JumpThreading] Use profile data even with the new pass managerKazu Hirata2019-11-221-0/+1
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: Without this patch, the jump threading pass ignores profiling data whenever we invoke the pass with the new pass manager. Specifically, JumpThreadingPass::run calls runImpl with class variable HasProfileData always set to false. In turn, runImpl sets HasProfileData to false again: HasProfileData = HasProfileData_; In the end, we don't use profiling data at all with the new pass manager. This patch fixes the problem by passing F.hasProfileData() to runImpl. The bug appears to have been introduced at: https://reviews.llvm.org/D41461 which removed local variable HasProfileData in JumpThreadingPass::run even though there was one more use left in the same function. As a result, the remaining use ended referring to the class variable instead. Note that F.hasProfileData is an extremely lightweight function, so I don't see the need to cache its result. Once this patch is approved, I'm planning to stop caching the result of F.hasProfileData in runOnFunction. Reviewers: wmi, eli.friedman Subscribers: hiraditya, jfb, llvm-commits Tags: #llvm Differential Revision: https://reviews.llvm.org/D70509
* Temporarily Revert "Reapply [LVI] Normalize pointer behavior" as it's broken ↵Eric Christopher2019-11-121-2/+1
| | | | | | | | python 3.6. Reverting to figure out if it's a problem in python or the compiler for now. This reverts commit 885a05f48a5d320946c89590b73a764e5884fe4f.
* Reapply [LVI] Normalize pointer behaviorNikita Popov2019-11-081-1/+2
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Fix cache invalidation by not guarding the dereferenced pointer cache erasure by SeenBlocks. SeenBlocks is only populated when actually caching a value in the block, which doesn't necessarily have to happen just because dereferenced pointers were calculated. ----- Related to D69686. As noted there, LVI currently behaves differently for integer and pointer values: For integers, the block value is always valid inside the basic block, while for pointers it is only valid at the end of the basic block. I believe the integer behavior is the correct one, and CVP relies on it via its getConstantRange() uses. The reason for the special pointer behavior is that LVI checks whether a pointer is dereferenced in a given basic block and marks it as non-null in that case. Of course, this information is valid only after the dereferencing instruction, or in conservative approximation, at the end of the block. This patch changes the treatment of dereferencability: Instead of including it inside the block value, we instead treat it as something similar to an assume (it essentially is a non-nullness assume) and incorporate this information in intersectAssumeOrGuardBlockValueConstantRange() if the context instruction is the terminator of the basic block. This happens either when determining an edge-value internally in LVI, or when a terminator was explicitly passed to getValueAt(). The latter case makes this change not fully NFC, because we can now fold terminator icmps based on the dereferencability information in the same block. This is the reason why I changed one JumpThreading test (it would optimize the condition away without the change). Of course, we do not want to recompute dereferencability on each intersectAssume call, so we need a new cache for this. The dereferencability analysis requires walking the entire basic block and computing underlying objects of all memory operands. This was previously done separately for each queried pointer value. In the new implementation (both because this makes the caching simpler, and because it is faster), I instead only walk the full BB once and cache all the dereferenced pointers. So the traversal is now performed only once per BB, instead of once per queried pointer value. I think the overall model now makes more sense than before, and there will be no more pitfalls due to differing integer/pointer behavior. Differential Revision: https://reviews.llvm.org/D69914
* Revert "[LVI] Normalize pointer behavior"Nikita Popov2019-11-081-2/+1
| | | | | | | This reverts commit 15bc4dc9a8949f9cffd46ec647baf0818d28fb28. clang-cmake-x86_64-sde-avx512-linux buildbot reported quite a few compile-time regressions in test-suite, will investigate.
* [LVI] Normalize pointer behaviorNikita Popov2019-11-081-1/+2
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Related to D69686. As noted there, LVI currently behaves differently for integer and pointer values: For integers, the block value is always valid inside the basic block, while for pointers it is only valid at the end of the basic block. I believe the integer behavior is the correct one, and CVP relies on it via its getConstantRange() uses. The reason for the special pointer behavior is that LVI checks whether a pointer is dereferenced in a given basic block and marks it as non-null in that case. Of course, this information is valid only after the dereferencing instruction, or in conservative approximation, at the end of the block. This patch changes the treatment of dereferencability: Instead of including it inside the block value, we instead treat it as something similar to an assume (it essentially is a non-nullness assume) and incorporate this information in intersectAssumeOrGuardBlockValueConstantRange() if the context instruction is the terminator of the basic block. This happens either when determining an edge-value internally in LVI, or when a terminator was explicitly passed to getValueAt(). The latter case makes this change not fully NFC, because we can now fold terminator icmps based on the dereferencability information in the same block. This is the reason why I changed one JumpThreading test (it would optimize the condition away without the change). Of course, we do not want to recompute dereferencability on each intersectAssume call, so we need a new cache for this. The dereferencability analysis requires walking the entire basic block and computing underlying objects of all memory operands. This was previously done separately for each queried pointer value. In the new implementation (both because this makes the caching simpler, and because it is faster), I instead only walk the full BB once and cache all the dereferenced pointers. So the traversal is now performed only once per BB, instead of once per queried pointer value. I think the overall model now makes more sense than before, and there will be no more pitfalls due to differing integer/pointer behavior. Differential Revision: https://reviews.llvm.org/D69914
* [JT][CVP] Regenerate test checks, againNikita Popov2019-11-013-5/+5
| | | | | The changes to update_test_checks format have been disabled again, so regenerate these tests. Also regenerate select.ll.
* [LVI] Regenerate test checks; NFCNikita Popov2019-10-313-56/+100
|
* IR: print value numbers for unnamed function argumentsTim Northover2019-08-031-1/+1
| | | | | | | | | | For consistency with normal instructions and clarity when reading IR, it's best to print the %0, %1, ... names of function arguments in definitions. Also modifies the parser to accept IR in that form for obvious reasons. llvm-svn: 367755
* [JumpThreading] Stop searching predecessor when the current bb is in aWei Mi2019-07-261-0/+63
| | | | | | | | | | | | | | | | | | | unreachable loop. updatePredecessorProfileMetadata in jumpthreading tries to find the first dominating predecessor block for a PHI value by searching upwards the predecessor block chain. But jumpthreading may see some temporary IR state which contains unreachable bb not being cleaned up. If an unreachable loop happens to be on the predecessor block chain, keeping chasing the predecessor block will run into an infinite loop. The patch fixes it. Differential Revision: https://reviews.llvm.org/D65310 llvm-svn: 367154
* [JumpThreading] Fix threading with unusual PHI nodes.Eli Friedman2019-07-034-22/+65
| | | | | | | | | | | | | | | | | | | | If the block being cloned contains a PHI node, in general, we need to clone that PHI node, even though it's trivial. If the operand of the PHI is an instruction in the block being cloned, the correct value for the operand doesn't exist until SSAUpdater constructs it. We usually don't hit this issue because we try to avoid threading across loop headers, but it's possible to hit this in some cases involving irreducible CFGs. I added a flag to allow threading across loop headers to make the testcase easier to understand. Thanks to Brian Rzycki for reducing the testcase. Fixes https://bugs.llvm.org/show_bug.cgi?id=42085. Differential Revision: https://reviews.llvm.org/D63913 llvm-svn: 365094
* [JumpThreading] A bug fix for stale loop info after unfold selectHiroshi Yamauchi2019-05-151-0/+30
| | | | | | | | | | | | | | | | | | | | Summary: The return value of a TryToUnfoldSelect call was not checked, which led to an incorrectly preserved loop info and some crash. The original crash was reported on https://reviews.llvm.org/D59514. Reviewers: davidxl, amehsan Reviewed By: davidxl Subscribers: fhahn, brzycki, llvm-commits Tags: #llvm Differential Revision: https://reviews.llvm.org/D61920 llvm-svn: 360780
* Revert "Temporarily Revert "Add basic loop fusion pass.""Eric Christopher2019-04-1756-0/+6405
| | | | | | | | The reversion apparently deleted the test/Transforms directory. Will be re-reverting again. llvm-svn: 358552
* Temporarily Revert "Add basic loop fusion pass."Eric Christopher2019-04-1756-6405/+0
| | | | | | | | As it's causing some bot failures (and per request from kbarton). This reverts commit r358543/ab70da07286e618016e78247e4a24fcb84077fda. llvm-svn: 358546
* [JumpThreading] Fix incorrect fold conditional after indirectbr/callbrBrian M. Rzycki2019-04-081-0/+44
| | | | | | | | | | | | | | | | | | | | | Fixes bug 40992: https://bugs.llvm.org/show_bug.cgi?id=40992 There is potential for miscompiled code emitted from JumpThreading when analyzing a block with one or more indirectbr or callbr predecessors. The ProcessThreadableEdges() function incorrectly folds conditional branches into an unconditional branch. This patch prevents incorrect branch folding without fully pessimizing other potential threading opportunities through the same basic block. This IR shape was manually fed in via opt and is unclear if clang and the full pass pipeline will ever emit similar code shapes. Thanks to Matthias Liedtke for the bug report and simplified IR example. Differential Revision: https://reviews.llvm.org/D60284 llvm-svn: 357930
* Tighten up tests that use -debugify as a shortcut. NFCPaul Robinson2019-03-141-4/+4
| | | | | | | | These now verify that a given instruction has a specific source location, rather than any old location. We want to make sure we propagate the correct locations from one instruction to another. llvm-svn: 356217
* [JumpThreading] Retain debug info when replacing branch instructionsJeremy Morse2019-03-111-0/+41
| | | | | | | | | | | | | | | | | | | | Fixes bug 37966: https://bugs.llvm.org/show_bug.cgi?id=37966 The Jump Threading pass will replace certain conditional branch instructions with unconditional branches when it can prove that only one branch can occur. Prior to this patch, it would not carry the debug info from the old instruction to the new one. This patch fixes the bug described by copying the debug info from the conditional branch instruction to the new unconditional branch instruction, and adds a regression test for the Jump Threading pass that covers this case. Patch by Stephen Tozer! Differential Revision: https://reviews.llvm.org/D58963 llvm-svn: 355822
* Implementation of asm-goto support in LLVMCraig Topper2019-02-081-0/+58
| | | | | | | | | | | | | | | | | | | | | | | | | This patch accompanies the RFC posted here: http://lists.llvm.org/pipermail/llvm-dev/2018-October/127239.html This patch adds a new CallBr IR instruction to support asm-goto inline assembly like gcc as used by the linux kernel. This instruction is both a call instruction and a terminator instruction with multiple successors. Only inline assembly usage is supported today. This also adds a new INLINEASM_BR opcode to SelectionDAG and MachineIR to represent an INLINEASM block that is also considered a terminator instruction. There will likely be more bug fixes and optimizations to follow this, but we felt it had reached a point where we would like to switch to an incremental development model. Patch by Craig Topper, Alexander Ivchenko, Mikhail Dvoretckii Differential Revision: https://reviews.llvm.org/D53765 llvm-svn: 353563
* [Jump Threading] Unfold a select insn that feeds a switch via a phi nodeEhsan Amiri2019-01-111-0/+78
| | | | | | | | | | | Currently when a select has a constant value in one branch and the select feeds a conditional branch (via a compare/ phi and compare) we unfold the select statement. This results in threading the conditional branch later on. Similar opportunity exists when a select (with a constant in one branch) feeds a switch (via a phi node). The patch unfolds select under this condition. A testcase is provided. llvm-svn: 350931
* [JumpThreading] Fix exponential time algorithm computing known values.Eli Friedman2018-11-091-1/+61
| | | | | | | | | | | | | | | | | | | ComputeValueKnownInPredecessors has a "visited" set to prevent infinite loops, since a value can be visited more than once. However, the implementation didn't prevent the algorithm from taking exponential time. Instead of removing elements from the RecursionSet one at a time, we should keep around the whole set until ComputeValueKnownInPredecessors finishes, then discard it. The testcase is synthetic because I was having trouble effectively reducing the original. But it's basically the same idea. Instead of failing, we could theoretically cache the result instead. But I don't think it would help substantially in practice. Differential Revision: https://reviews.llvm.org/D54239 llvm-svn: 346562
* [Local] Keep K's range if K does not move when combining metadata.Florian Hahn2018-10-271-4/+8
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | As K has to dominate I, IIUC I's range metadata must be a subset of K's. After Eli's recent clarification to the LangRef, loading a value outside of the range is undefined behavior. Therefore if I's range contains elements outside of K's range and we would load one such value, K would cause undefined behavior. In cases like hoisting/sinking, we still want the most generic range over all code paths to/from the hoist/sink point. As suggested in the patches related to D47339, I will refactor the handling of those scenarios and try to decouple it from this function as follow up, once we switched to a similar handling of metadata in most of combineMetadata. I updated some tests checking mostly the merging of metadata to keep the metadata of to dominating load. The most interesting one is probably test8 in test/Transforms/JumpThreading/thread-loads.ll. It contained a comment about the alias metadata preventing us to eliminate the branch, but it seem like the actual problem currently is that we merge the ranges of both loads and cannot eliminate the icmp afterwards. With this patch, we manage to eliminate the icmp, as the range of the first load excludes 8. Reviewers: efriedma, nlopes, davide Reviewed By: efriedma Differential Revision: https://reviews.llvm.org/D51629 llvm-svn: 345456
* [Local] Make DoesKMove required for combineMetadata.Florian Hahn2018-08-241-0/+122
| | | | | | | | | | | | | | | This patch makes the DoesKMove argument non-optional, to force people to think about it. Most cases where it is false are either code hoisting or code sinking, where we pick one instruction from a set of equal instructions among different code paths. Reviewers: dberlin, nlopes, efriedma, davide Reviewed By: efriedma Differential Revision: https://reviews.llvm.org/D47475 llvm-svn: 340606
* [JumpThreading] Don't try to rewrite a use if it's already valid.Michael Zolotukhin2018-06-261-0/+19
| | | | | | | | | | | | | | | | | | | 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
* Fix the issue that ComputeValueKnownInPredecessors only handles the case whenWei Mi2018-05-011-0/+38
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 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
* Fix typo in a test.Michael Zolotukhin2018-04-201-1/+1
| | | | llvm-svn: 330434
* Revert "Revert r330403 and r330413."Michael Zolotukhin2018-04-201-0/+54
| | | | | | | | | | | 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-28/+0
| | | | | | | | | | | | | | | | 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
* Reapply "[PR16756] Use SSAUpdaterBulk in JumpThreading." one more time.Michael Zolotukhin2018-04-201-0/+28
| | | | | | | | | 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-28/+0
| | | | | | This reverts r330175. There are still stage3/stage4 miscompares. llvm-svn: 330180
* Reapply "[PR16756] Use SSAUpdaterBulk in JumpThreading." again.Michael Zolotukhin2018-04-171-0/+28
| | | | | | | | | 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
* [SSAUpdaterBulk] Handle CFG with unreachable from entry blocks.Michael Zolotukhin2018-04-101-0/+26
| | | | llvm-svn: 329660
* [JumpThreading] Don't select an edge that we know we can't threadHaicheng Wu2018-03-291-0/+99
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 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
* [JumpThreading] Track unreachable BBs to avoid processingBrian M. Rzycki2018-03-162-5/+16
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | 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
* [LazyValueInfo] PR33357 prevent infinite recursion on BinaryOperatorBrian M. Rzycki2018-03-131-0/+37
| | | | | | | | | | | | | | | | | | | | | | Summary: It is possible for LVI to encounter instructions that are not in valid SSA form and reference themselves. One example is the following: %tmp4 = and i1 %tmp4, undef Before this patch LVI would recurse until running out of stack memory and crashed. This patch marks these self-referential instructions as Overdefined and aborts analysis on the instruction. Fixes https://bugs.llvm.org/show_bug.cgi?id=33357 Reviewers: craig.topper, anna, efriedma, dberlin, sebpop, kuhar Reviewed by: dberlin Subscribers: uabelho, spatel, a.elovikov, fhahn, eli.friedman, mzolotukhin, spop, evandro, davide, llvm-commits Differential Revision: https://reviews.llvm.org/D34135 llvm-svn: 327432
* [JumpThreading] Don't restrict cast-traversal to i1Chad Rosier2018-03-091-0/+28
| | | | | | | | | | | | | | | | | | | 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
* [JumpThreading] PR36133 enable/disable DominatorTree for LVI analysisBrian M. Rzycki2018-02-161-0/+44
| | | | | | | | | | | | | | | | | | | | | | 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
* [Dominators] Visit affected node candidates found at different root levelsJakub Kuderski2018-01-192-0/+118
| | | | | | | | | | | | | | | | | | | Summary: This patch attempts to fix the DomTree incremental insertion bug found here [[ https://bugs.llvm.org/show_bug.cgi?id=35969 | PR35969 ]] . When performing an insertion into a piece of unreachable CFG, we may find the same not at different levels. When this happens, the node can turn out to be affected when we find it starting from a node with a lower level in the tree. The level at which we start visitation affects if we consider a node affected or not. This patch tracks the lowest level at which each node was visited during insertion and allows it to be visited multiple times, if it can cause it to be considered affected. Reviewers: brzycki, davide, dberlin, grosser Reviewed By: brzycki Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D42231 llvm-svn: 322993
* [JumpThreading] Preservation of DT and LVI across the passBrian M. Rzycki2018-01-123-0/+355
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 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-042-315/+0
| | | | | | | 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-042-0/+315
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 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
* [JumpThreading] Restrict PRE across instructions that don't pass control to ↵Max Kazantsev2017-12-191-0/+103
| | | | | | | | | | | | | | 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-132-315/+0
| | | | | | | 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-132-0/+315
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 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
* Fix some misc. -enable-var-scope violationsMatt Arsenault2017-11-131-18/+18
| | | | llvm-svn: 318006
* Disable jump threading into loop headersKrzysztof Parzyszek2017-09-061-14/+23
| | | | | | | | | | | | | | | | | | | | | | 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
OpenPOWER on IntegriCloud