aboutsummaryrefslogtreecommitdiff
path: root/test/Transforms/JumpThreading
AgeCommit message (Collapse)Author
2010-01-23fix a crash in jump threading, PR6119Chris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@94319 91177308-0d34-0410-b5e6-96231b3b80d8
2010-01-121) Use the new SimplifyInstructionsInBlock routine instead of the copyChris Lattner
in JT. 2) When cloning blocks for PHI or xor conditions, use instsimplify to simplify the code as we go. This allows us to squish common cases early in JT which opens up opportunities for subsequent iterations, and allows it to completely simplify the testcase. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@93253 91177308-0d34-0410-b5e6-96231b3b80d8
2010-01-12Teach jump threading to duplicate small blocks when the branchChris Lattner
condition is a xor with a phi node. This eliminates nonsense like this from 176.gcc in several places: LBB166_84: testl %eax, %eax - setne %al - xorb %cl, %al - notb %al - testb $1, %al - je LBB166_85 + je LBB166_69 + jmp LBB166_85 This is rdar://7391699 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@93221 91177308-0d34-0410-b5e6-96231b3b80d8
2009-12-06fix PR5698Chris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@90708 91177308-0d34-0410-b5e6-96231b3b80d8
2009-12-01fix PR5640 by tracking whether a block is the header of a loop moreChris Lattner
precisely, which prevents us from infinitely peeling the loop. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@90211 91177308-0d34-0410-b5e6-96231b3b80d8
2009-11-12typoGabor Greif
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@86980 91177308-0d34-0410-b5e6-96231b3b80d8
2009-11-12use getPredicateOnEdge to fold comparisons through PHI nodes,Chris Lattner
which implements GCC PR18046. This also gets us 360 more jump threads on 176.gcc. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@86953 91177308-0d34-0410-b5e6-96231b3b80d8
2009-11-12should not commit when distracted.Chris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@86929 91177308-0d34-0410-b5e6-96231b3b80d8
2009-11-12We now thread some impossible condition information with LVI.Chris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@86927 91177308-0d34-0410-b5e6-96231b3b80d8
2009-11-12with the new code we can thread non-instruction values. ThisChris Lattner
allows us to handle the test10 testcase. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@86924 91177308-0d34-0410-b5e6-96231b3b80d8
2009-11-12move some stuff into DEBUG's and turn on lazy-value-info forChris Lattner
the basic.ll testcase. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@86918 91177308-0d34-0410-b5e6-96231b3b80d8
2009-11-11oops, didn't mean to commit this, no harm, but add a todoops, didn't mean to ↵Chris Lattner
commit this, no harm, but add a todoo git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@86768 91177308-0d34-0410-b5e6-96231b3b80d8
2009-11-11Stub out a new lazy value info pass, which will eventuallyChris Lattner
vend value constraint information to the optimizer. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@86767 91177308-0d34-0410-b5e6-96231b3b80d8
2009-11-10implement a TODO by teaching jump threading about "xor x, 1".Chris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@86739 91177308-0d34-0410-b5e6-96231b3b80d8
2009-11-10Make jump threading eliminate blocks that just contain phi nodes,Chris Lattner
debug intrinsics, and an unconditional branch when possible. This reuses the TryToSimplifyUncondBranchFromEmptyBlock function split out of simplifycfg. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@86722 91177308-0d34-0410-b5e6-96231b3b80d8
2009-11-10make jump threading recursively simplify expressions instead of doing it Chris Lattner
just one level deep. On the testcase we go from getting this: F1: ; preds = %T2 %F = and i1 true, %cond ; <i1> [#uses=1] br i1 %F, label %X, label %Y to a fully threaded: F1: ; preds = %T2 br label %Y This changes gets us to the point where we're forming (too many) switch instructions on doug's strswitch testcase. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@86646 91177308-0d34-0410-b5e6-96231b3b80d8
2009-11-07reapply 86289, 86278, 86270, 86267, 86266 & 86264 plus a fixChris Lattner
(making pred factoring only happen if threading is guaranteed to be successful). This now survives an X86-64 bootstrap of llvm-gcc. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@86355 91177308-0d34-0410-b5e6-96231b3b80d8
2009-11-07Revert following patches to fix llvmgcc bootstrap.Devang Patel
86289, 86278, 86270, 86267, 86266 & 86264 Chris, please take a look. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@86321 91177308-0d34-0410-b5e6-96231b3b80d8
2009-11-06Fix a problem discovered on self host.Chris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@86278 91177308-0d34-0410-b5e6-96231b3b80d8
2009-11-06Extend jump threading to support much more general threadingChris Lattner
predicates. This allows us to jump thread things like: _ZN12StringSwitchI5ColorE4CaseILj7EEERS1_RAT__KcRKS0_.exit119: %tmp1.i24166 = phi i8 [ 1, %bb5.i117 ], [ %tmp1.i24165, %_Z....exit ], [ %tmp1.i24165, %bb4.i114 ] %toBoolnot.i87 = icmp eq i8 %tmp1.i24166, 0 ; <i1> [#uses=1] %tmp4.i90 = icmp eq i32 %tmp2.i, 6 ; <i1> [#uses=1] %or.cond173 = and i1 %toBoolnot.i87, %tmp4.i90 ; <i1> [#uses=1] br i1 %or.cond173, label %bb4.i96, label %_ZN12... Where it is "obvious" that when coming from %bb5.i117 that the 'and' is always false. This triggers a surprisingly high number of times in the testsuite, and gets us closer to generating good code for doug's strswitch testcase. This also make a bunch of other code in jump threading redundant, I'll rip out in the next patch. This survived an enable-checking llvm-gcc bootstrap. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@86264 91177308-0d34-0410-b5e6-96231b3b80d8
2009-11-05merge a few crash tests into crash.llChris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@86119 91177308-0d34-0410-b5e6-96231b3b80d8
2009-10-24Make these tests more interesting by usingDan Gohman
-verify-dom-info and -verify-loop-info, which enable additional (expensive) consistency checks. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@85017 91177308-0d34-0410-b5e6-96231b3b80d8
2009-10-20alternate fix for PR5258 which avoids worklist problems, with reduced testcase.Chris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@84667 91177308-0d34-0410-b5e6-96231b3b80d8
2009-10-20Fix PR5258, jump-threading creating invalid PHIs.Torok Edwin
When an incoming value for a PHI is updated, we must also updated all other incoming values for the same BB to match, otherwise we create invalid PHIs. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@84638 91177308-0d34-0410-b5e6-96231b3b80d8
2009-10-11when folding duplicate conditions, delete the Chris Lattner
now-probably-dead instruction tree feeding it. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@83778 91177308-0d34-0410-b5e6-96231b3b80d8
2009-10-11implement a transformation in jump threading that is currentlyChris Lattner
done by condprop, but do it in a much more general form. The basic idea is that we can do a limited form of tail duplication in the case when we have a branch on a phi. Moving the branch up in to the predecessor block makes instruction selection much easier and encourages chained jump threadings. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@83759 91177308-0d34-0410-b5e6-96231b3b80d8
2009-10-11another testcase jump threading shouldn't crash on.Chris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@83758 91177308-0d34-0410-b5e6-96231b3b80d8
2009-10-11rename a file, remove a poorly reduced testcase.Chris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@83757 91177308-0d34-0410-b5e6-96231b3b80d8
2009-10-11make jump threading on a phi with undef inputs happen.Chris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@83754 91177308-0d34-0410-b5e6-96231b3b80d8
2009-10-11merge two tests.Chris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@83751 91177308-0d34-0410-b5e6-96231b3b80d8
2009-10-11simplify some run lines, convert a test to filecheck.Chris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@83750 91177308-0d34-0410-b5e6-96231b3b80d8
2009-09-11Change tests from "opt %s" to "opt < %s" so that opt doesn't see theDan Gohman
input filename so that opt doesn't print the input filename in the output so that grep lines in the tests don't unintentionally match strings in the input filename. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@81537 91177308-0d34-0410-b5e6-96231b3b80d8
2009-09-09Eliminate more uses of llvm-as and llvm-dis.Dan Gohman
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@81293 91177308-0d34-0410-b5e6-96231b3b80d8
2009-09-08Use opt -S instead of piping bitcode output through llvm-dis.Dan Gohman
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@81257 91177308-0d34-0410-b5e6-96231b3b80d8
2009-09-08Change these tests to feed the assembly files to opt directly, insteadDan Gohman
of using llvm-as, now that opt supports this. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@81226 91177308-0d34-0410-b5e6-96231b3b80d8
2009-06-19make jump threading handle lexically identical compare instructionsChris Lattner
as if they were multiple uses of the same instruction. This interacts well with the existing loadpre that j-t does to open up many new jump threads earlier. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@73768 91177308-0d34-0410-b5e6-96231b3b80d8
2009-06-19Teach jump threading to look at comparisons between phi nodes and non-constants.Nick Lewycky
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@73755 91177308-0d34-0410-b5e6-96231b3b80d8
2009-05-04Restore minor deletion.Mike Stump
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@70892 91177308-0d34-0410-b5e6-96231b3b80d8
2009-01-19Fix PR3353, infinitely jump threading an infinite loop make from switches.Chris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@62529 91177308-0d34-0410-b5e6-96231b3b80d8
2009-01-09Fix PR3298, a crash in Jump Threading. Apparently even Chris Lattner
jump threading can have bugs, who knew? ;-) git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@61983 91177308-0d34-0410-b5e6-96231b3b80d8
2008-12-03testcase for br undef folding.Chris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60471 91177308-0d34-0410-b5e6-96231b3b80d8
2008-12-03Teach jump threading some more simple tricks:Chris Lattner
1) have it fold "br undef", which does occur with surprising frequency as jump threading iterates. 2) teach j-t to delete dead blocks. This removes the successor edges, reducing the in-edges of other blocks, allowing recursive simplification. 3) Fold things like: br COND, BBX, BBY BBX: br COND, BBZ, BBW which also happens because jump threading iterates. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60470 91177308-0d34-0410-b5e6-96231b3b80d8
2008-11-28don't call MergeBasicBlockIntoOnlyPred on a block whose onlyChris Lattner
predecessor is itself. This doesn't make sense, and this is a dead infinite loop anyway. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60210 91177308-0d34-0410-b5e6-96231b3b80d8
2008-11-27Fix PR3138: if we merge the entry block into another block, make sure toChris Lattner
move the other block back up into the entry position! git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60179 91177308-0d34-0410-b5e6-96231b3b80d8
2008-11-27Make jump threading substantially more powerful, in the following ways:Chris Lattner
1. Make it fold blocks separated by an unconditional branch. This enables jump threading to see a broader scope. 2. Make jump threading able to eliminate locally redundant loads when they feed the branch condition of a block. This frequently occurs due to reg2mem running. 3. Make jump threading able to eliminate *partially redundant* loads when they feed the branch condition of a block. This is common in code with lots of loads and stores like C++ code and 255.vortex. This implements thread-loads.ll and rdar://6402033. Per the fixme's, several pieces of this should be moved into Transforms/Utils. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60148 91177308-0d34-0410-b5e6-96231b3b80d8
2008-05-05Fix a crash when threading a block that includes a MRV call result.Chris Lattner
DemoteRegToStack doesn't work with MRVs yet, because it relies on the ability to load/store things. This fixes PR2285. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@50667 91177308-0d34-0410-b5e6-96231b3b80d8
2008-04-25Don't infininitely thread branches when a threaded edgeChris Lattner
goes back to the block, e.g.: Threading edge through bool from 'bb37.us.thread3829' to 'bb37.us' with cost: 1, across block: bb37.us: ; preds = %bb37.us.thread3829, %bb37.us, %bb33 %D1361.1.us = phi i32 [ %tmp36, %bb33 ], [ %D1361.1.us, %bb37.us ], [ 0, %bb37.us.thread3829 ] ; <i32> [#uses=2] %tmp39.us = icmp eq i32 %D1361.1.us, 0 ; <i1> [#uses=1] br i1 %tmp39.us, label %bb37.us, label %bb42.us git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@50251 91177308-0d34-0410-b5e6-96231b3b80d8
2008-04-22Start doing the significantly useful part of jump threading: handle casesChris Lattner
where a comparison has a phi input and that phi is a constant. For example, stuff like: Threading edge through bool from 'bb2149' to 'bb2231' with cost: 1, across block: bb2237: ; preds = %bb2231, %bb2149 %tmp2328.rle = phi i32 [ %tmp2232, %bb2231 ], [ %tmp2232439, %bb2149 ] ; <i32> [#uses=2] %done.0 = phi i32 [ %done.2, %bb2231 ], [ 0, %bb2149 ] ; <i32> [#uses=1] %tmp2239 = icmp eq i32 %done.0, 0 ; <i1> [#uses=1] br i1 %tmp2239, label %bb2231, label %bb2327 or bb38.i298: ; preds = %bb33.i295, %bb1693 %tmp39.i296.rle = phi %struct.ibox* [ null, %bb1693 ], [ %tmp39.i296.rle1109, %bb33.i295 ] ; <%struct.ibox*> [#uses=2] %minspan.1.i291.reg2mem.1 = phi i32 [ 32000, %bb1693 ], [ %minspan.0.i288, %bb33.i295 ] ; <i32> [#uses=1] %tmp40.i297 = icmp eq %struct.ibox* %tmp39.i296.rle, null ; <i1> [#uses=1] br i1 %tmp40.i297, label %implfeeds.exit311, label %bb43.i301 This triggers thousands of times in spec. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@50110 91177308-0d34-0410-b5e6-96231b3b80d8
2008-04-22Dig through multiple levels of AND to thread jumps if needed.Chris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@50106 91177308-0d34-0410-b5e6-96231b3b80d8
2008-04-22Teach jump threading to thread through blocks like:Chris Lattner
br (and X, phi(Y, Z, false)), label L1, label L2 This triggers once on 252.eon and 6 times on 176.gcc. Blocks in question often look like this: bb262: ; preds = %bb261, %bb248 %iftmp.251.0 = phi i1 [ true, %bb261 ], [ false, %bb248 ] ; <i1> [#uses=4] %tmp270 = icmp eq %struct.rtx_def* %tmp.0.i, null ; <i1> [#uses=1] %bothcond = or i1 %iftmp.251.0, %tmp270 ; <i1> [#uses=1] br i1 %bothcond, label %bb288, label %bb273 In this case, it is clear that it doesn't matter if tmp.0.i is null when coming from bb261. When coming from bb248, it is all that matters. Another random example: check_asm_operands.exit: ; preds = %check_asm_operands.exit.thr_comm, %bb30.i, %bb12.i, %bb6.i413 %tmp.0.i420 = phi i1 [ true, %bb6.i413 ], [ true, %bb12.i ], [ true, %bb30.i ], [ false, %check_asm_operands.exit.thr_comm ; <i1> [#uses=1] call void @llvm.stackrestore( i8* %savedstack ) nounwind %tmp4389 = icmp eq i32 %added_sets_1.0, 0 ; <i1> [#uses=1] %tmp4394 = icmp eq i32 %added_sets_2.0, 0 ; <i1> [#uses=1] %bothcond80 = and i1 %tmp4389, %tmp4394 ; <i1> [#uses=1] %bothcond81 = and i1 %bothcond80, %tmp.0.i420 ; <i1> [#uses=1] br i1 %bothcond81, label %bb4398, label %bb4397 Here is the case from 252.eon: bb290.i.i: ; preds = %bb23.i57.i.i, %bb8.i39.i.i, %bb100.i.i, %bb100.i.i, %bb85.i.i110 %myEOF.1.i.i = phi i1 [ true, %bb100.i.i ], [ true, %bb100.i.i ], [ true, %bb85.i.i110 ], [ true, %bb8.i39.i.i ], [ false, %bb23.i57.i.i ] ; <i1> [#uses=2] %i.4.i.i = phi i32 [ %i.1.i.i, %bb85.i.i110 ], [ %i.0.i.i, %bb100.i.i ], [ %i.0.i.i, %bb100.i.i ], [ %i.3.i.i, %bb8.i39.i.i ], [ %i.3.i.i, %bb23.i57.i.i ] ; <i32> [#uses=3] %tmp292.i.i = load i8* %tmp16.i.i100, align 1 ; <i8> [#uses=1] %tmp293.not.i.i = icmp ne i8 %tmp292.i.i, 0 ; <i1> [#uses=1] %bothcond.i.i = and i1 %tmp293.not.i.i, %myEOF.1.i.i ; <i1> [#uses=1] br i1 %bothcond.i.i, label %bb202.i.i, label %bb301.i.i Factoring out 3 common predecessors. On the path from any blocks other than bb23.i57.i.i, the load and compare are dead. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@50096 91177308-0d34-0410-b5e6-96231b3b80d8
generated by cgit v1.2.3-70-g09d2 (git 2.46.0) at 2025-12-25 14:45:27 +0000