summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Transforms/Scalar/JumpThreading.cpp
Commit message (Collapse)AuthorAgeFilesLines
* Fix a debug info dependency in jump threading.Dale Johannesen2009-03-171-2/+5
| | | | llvm-svn: 67064
* this wasn't intended to go in.Chris Lattner2009-03-061-34/+0
| | | | llvm-svn: 66252
* Change various llvm utilities to use PrettyStackTraceProgram inChris Lattner2009-03-061-0/+34
| | | | | | | their main routines. This makes the tools print their argc/argv commands if they crash. llvm-svn: 66248
* Fix PR3353, infinitely jump threading an infinite loop make from switches.Chris Lattner2009-01-191-0/+5
| | | | llvm-svn: 62529
* Fix PR3298, a crash in Jump Threading. Apparently even Chris Lattner2009-01-091-0/+4
| | | | | | jump threading can have bugs, who knew? ;-) llvm-svn: 61983
* remove DebugIterations option. Despite the accusations, Chris Lattner2008-12-081-14/+1
| | | | | | | jump threading has been shown to only expose problems not have bugs itself. I'm sure it's completely bug free! ;-) llvm-svn: 60725
* Start simplifying a switch that has a successor that is a switch.Chris Lattner2008-12-041-0/+74
| | | | llvm-svn: 60534
* add a debugging option to help track down j-t problems.Chris Lattner2008-12-041-1/+14
| | | | llvm-svn: 60514
* Teach jump threading some more simple tricks:Chris Lattner2008-12-031-16/+156
| | | | | | | | | | | | | | | | 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
* switch a couple more calls to use array_pod_sort.Chris Lattner2008-12-011-1/+2
| | | | llvm-svn: 60337
* Teach jump threading to clean up after itself, DCE and constfolding theChris Lattner2008-12-011-1/+24
| | | | | | | | | new instructions it simplifies. Because we're threading jumps on edges with constants coming in from PHI's, we inherently are exposing a lot more constants to the new block. Folding them and deleting dead conditions allows the cost model in jump threading to be more accurate as it iterates. llvm-svn: 60327
* don't call MergeBasicBlockIntoOnlyPred on a block whose onlyChris Lattner2008-11-281-1/+2
| | | | | | | 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/+6
| | | | | | move the other block back up into the entry position! llvm-svn: 60179
* move FindAvailableLoadedValue from JumpThreading to Transforms/Utils.Chris Lattner2008-11-271-63/+3
| | | | llvm-svn: 60166
* move MergeBasicBlockIntoOnlyPred to Transforms/Utils.Chris Lattner2008-11-271-31/+0
| | | | llvm-svn: 60162
* rename ThreadBlock to ProcessBlock, since it does other things thanChris Lattner2008-11-271-4/+4
| | | | | | just simple threading. llvm-svn: 60157
* Make jump threading substantially more powerful, in the following ways:Chris Lattner2008-11-271-0/+273
| | | | | | | | | | | | | | | | | 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
* Tidy up several unbeseeming casts from pointer to intptr_t.Dan Gohman2008-09-041-1/+1
| | | | llvm-svn: 55779
* Enable first-class aggregates support.Dan Gohman2008-07-231-14/+1
| | | | | | | | | | | | Remove the GetResultInst instruction. It is still accepted in LLVM assembly and bitcode, where it is now auto-upgraded to ExtractValueInst. Also, remove support for return instructions with multiple values. These are auto-upgraded to use InsertValueInst instructions. The IRBuilder still accepts multiple-value returns, and auto-upgrades them to InsertValueInst instructions. llvm-svn: 53941
* Fix some constructs that gcc-4.4 warns about.Duncan Sands2008-05-271-2/+2
| | | | llvm-svn: 51591
* Tidy up BasicBlock::getFirstNonPHI, and change a bunch of places toDan Gohman2008-05-231-2/+1
| | | | | | use it instead of duplicating its functionality. llvm-svn: 51499
* Fix typo.Matthijs Kooijman2008-05-201-1/+1
| | | | llvm-svn: 51303
* Clean up the use of static and anonymous namespaces. This turned upDan Gohman2008-05-131-2/+4
| | | | | | | several things that were neither in an anonymous namespace nor static but not intended to be global. llvm-svn: 51017
* restore doxygen comment.Chris Lattner2008-05-091-17/+16
| | | | llvm-svn: 50881
* Improve pass documentation and comments.Gordon Henriksen2008-05-081-16/+17
| | | | | | Patch by Matthijs Kooijman! llvm-svn: 50861
* fix typo Duncan noticedChris Lattner2008-05-061-1/+1
| | | | llvm-svn: 50699
* Fix a crash when threading a block that includes a MRV call result.Chris Lattner2008-05-051-4/+19
| | | | | | | | | 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/+22
| | | | | | | | | | | | | 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-7/+83
| | | | | | | | | | | | | | | | | | | | | | | | 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-14/+22
| | | | llvm-svn: 50106
* Teach jump threading to thread through blocks like:Chris Lattner2008-04-221-20/+106
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 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
* refactor some code, no functionality change.Chris Lattner2008-04-221-2/+13
| | | | llvm-svn: 50094
* fix grammar-o, thanks to Duncan for noticing.Chris Lattner2008-04-211-1/+1
| | | | llvm-svn: 50047
* Use the new SplitBlockPredecessors to implement a todo.Chris Lattner2008-04-211-4/+16
| | | | llvm-svn: 50022
* finish the first cut of a jump threading pass implementation.Chris Lattner2008-04-201-21/+141
| | | | llvm-svn: 50006
* we can only thread blocks when there is a pred we can determine the succ of.Chris Lattner2008-04-201-2/+17
| | | | llvm-svn: 50003
* improve comments, infrastructure, and add some validity checks for threading.Chris Lattner2008-04-201-9/+106
| | | | | | Add a cost function. llvm-svn: 50002
* Add a new Jump Threading pass, which will handle casesChris Lattner2008-04-201-0/+52
such as those in PR2235. Right now the pass is not very effective. :) llvm-svn: 50000
OpenPOWER on IntegriCloud