summaryrefslogtreecommitdiffstats
path: root/llvm/test/Transforms/JumpThreading
Commit message (Collapse)AuthorAgeFilesLines
...
* Fix a problem discovered on self host.Chris Lattner2009-11-061-0/+22
| | | | llvm-svn: 86278
* Extend jump threading to support much more general threadingChris Lattner2009-11-061-0/+31
| | | | | | | | | | | | | | | | | | | | 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. llvm-svn: 86264
* merge a few crash tests into crash.llChris Lattner2009-11-054-88/+82
| | | | llvm-svn: 86119
* Make these tests more interesting by usingDan Gohman2009-10-241-1/+1
| | | | | | | -verify-dom-info and -verify-loop-info, which enable additional (expensive) consistency checks. llvm-svn: 85017
* alternate fix for PR5258 which avoids worklist problems, with reduced testcase.Chris Lattner2009-10-202-348/+35
| | | | llvm-svn: 84667
* Fix PR5258, jump-threading creating invalid PHIs.Torok Edwin2009-10-201-0/+348
| | | | | | | 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. llvm-svn: 84638
* when folding duplicate conditions, delete the Chris Lattner2009-10-112-30/+33
| | | | | | now-probably-dead instruction tree feeding it. llvm-svn: 83778
* implement a transformation in jump threading that is currentlyChris Lattner2009-10-111-0/+34
| | | | | | | | | | 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. llvm-svn: 83759
* another testcase jump threading shouldn't crash on.Chris Lattner2009-10-111-0/+31
| | | | llvm-svn: 83758
* rename a file, remove a poorly reduced testcase.Chris Lattner2009-10-112-142/+0
| | | | llvm-svn: 83757
* make jump threading on a phi with undef inputs happen.Chris Lattner2009-10-111-2/+32
| | | | llvm-svn: 83754
* merge two tests.Chris Lattner2009-10-112-13/+19
| | | | llvm-svn: 83751
* simplify some run lines, convert a test to filecheck.Chris Lattner2009-10-116-7/+13
| | | | llvm-svn: 83750
* Change tests from "opt %s" to "opt < %s" so that opt doesn't see theDan Gohman2009-09-1114-18/+18
| | | | | | | | 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. llvm-svn: 81537
* Eliminate more uses of llvm-as and llvm-dis.Dan Gohman2009-09-091-1/+1
| | | | llvm-svn: 81293
* Use opt -S instead of piping bitcode output through llvm-dis.Dan Gohman2009-09-0810-14/+14
| | | | llvm-svn: 81257
* Change these tests to feed the assembly files to opt directly, insteadDan Gohman2009-09-0814-18/+18
| | | | | | of using llvm-as, now that opt supports this. llvm-svn: 81226
* make jump threading handle lexically identical compare instructionsChris Lattner2009-06-191-0/+30
| | | | | | | | 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. llvm-svn: 73768
* Teach jump threading to look at comparisons between phi nodes and non-constants.Nick Lewycky2009-06-191-0/+21
| | | | llvm-svn: 73755
* * Sink 4 duplicates of edge threading validity checks and DOUT prints intoChris Lattner2009-05-041-0/+38
| | | | | | | | | | ThreadEdge directly. This shares the code, but is just a refactoring. * Make JumpThreading compute the set of loop headers and avoid threading across them. This prevents jump threading from forming irreducible loops (goodness) but also prevents it from threading in other cases that are beneficial (see the comment above FindFunctionBackedges). llvm-svn: 70820
* Fix PR3353, infinitely jump threading an infinite loop make from switches.Chris Lattner2009-01-191-0/+21
| | | | llvm-svn: 62529
* Fix PR3298, a crash in Jump Threading. Apparently even Chris Lattner2009-01-091-0/+49
| | | | | | jump threading can have bugs, who knew? ;-) llvm-svn: 61983
* testcase for br undef folding.Chris Lattner2008-12-031-0/+12
| | | | llvm-svn: 60471
* Teach jump threading some more simple tricks:Chris Lattner2008-12-031-0/+22
| | | | | | | | | | | | | | | | 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. llvm-svn: 60470
* don't call MergeBasicBlockIntoOnlyPred on a block whose onlyChris Lattner2008-11-281-0/+17
| | | | | | | predecessor is itself. This doesn't make sense, and this is a dead infinite loop anyway. llvm-svn: 60210
* Fix PR3138: if we merge the entry block into another block, make sure toChris Lattner2008-11-271-0/+13
| | | | | | move the other block back up into the entry position! llvm-svn: 60179
* Make jump threading substantially more powerful, in the following ways:Chris Lattner2008-11-271-0/+34
| | | | | | | | | | | | | | | | | 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. llvm-svn: 60148
* Fix a crash when threading a block that includes a MRV call result.Chris Lattner2008-05-051-0/+25
| | | | | | | | | DemoteRegToStack doesn't work with MRVs yet, because it relies on the ability to load/store things. This fixes PR2285. llvm-svn: 50667
* Don't infininitely thread branches when a threaded edgeChris Lattner2008-04-251-0/+142
| | | | | | | | | | | | | 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 llvm-svn: 50251
* Start doing the significantly useful part of jump threading: handle casesChris Lattner2008-04-221-0/+30
| | | | | | | | | | | | | | | | | | | | | | | | 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. llvm-svn: 50110
* Dig through multiple levels of AND to thread jumps if needed.Chris Lattner2008-04-221-0/+33
| | | | llvm-svn: 50106
* Teach jump threading to thread through blocks like:Chris Lattner2008-04-221-0/+32
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 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. llvm-svn: 50096
* add a basic testcase.Chris Lattner2008-04-222-0/+34
llvm-svn: 50093
OpenPOWER on IntegriCloud