summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Transforms/Utils/SimplifyCFG.cpp
Commit message (Collapse)AuthorAgeFilesLines
* simplify this a bit.Chris Lattner2010-12-181-2/+1
| | | | llvm-svn: 122156
* SimplifyCFG: Ranges can be larger than 64 bits. Fixes Release-selfhost build.Benjamin Kramer2010-12-171-1/+1
| | | | llvm-svn: 122054
* improve switch formation to handle small range Chris Lattner2010-12-171-2/+25
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | comparisons formed by comparisons. For example, this: void foo(unsigned x) { if (x == 0 || x == 1 || x == 3 || x == 4 || x == 6) bar(); } compiles into: _foo: ## @foo ## BB#0: ## %entry cmpl $6, %edi ja LBB0_2 ## BB#1: ## %entry movl %edi, %eax movl $91, %ecx btq %rax, %rcx jb LBB0_3 instead of: _foo: ## @foo ## BB#0: ## %entry cmpl $2, %edi jb LBB0_4 ## BB#1: ## %switch.early.test cmpl $6, %edi ja LBB0_3 ## BB#2: ## %switch.early.test movl %edi, %eax movl $88, %ecx btq %rax, %rcx jb LBB0_4 This catches a bunch of cases in GCC, which look like this: %804 = load i32* @which_alternative, align 4, !tbaa !0 %805 = icmp ult i32 %804, 2 %806 = icmp eq i32 %804, 3 %or.cond121 = or i1 %805, %806 %807 = icmp eq i32 %804, 4 %or.cond124 = or i1 %or.cond121, %807 br i1 %or.cond124, label %.thread, label %808 turning this into a range comparison. llvm-svn: 122045
* make qsort predicate more conformant by returning 0 for equal values.Chris Lattner2010-12-151-1/+5
| | | | llvm-svn: 121838
* - Insert new instructions before DomBlock's terminator,Chris Lattner2010-12-141-7/+16
| | | | | | | | | | which is simpler than finding a place to insert in BB. - Don't perform the 'if condition hoisting' xform on certain i1 PHIs, as it interferes with switch formation. This re-fixes "example 7", without breaking the world hopefully. llvm-svn: 121764
* fix two significant issues with FoldTwoEntryPHINode:Chris Lattner2010-12-141-1/+11
| | | | | | | | | | | | | first, it can kick in on blocks whose conditions have been folded to a constant, even though one of the edges will be trivially folded. second, it doesn't clean up the "if diamond" that it just eliminated away. This is a problem because other simplifycfg xforms kick in depending on the order of block visitation, causing pointless work. llvm-svn: 121762
* remove the instsimplify logic I added in r121754. It is apparentlyChris Lattner2010-12-141-11/+1
| | | | | | breaking the selfhost builds, though I can't fathom how. llvm-svn: 121761
* clean up logic, convert std::set to SmallPtrSet, handle the caseChris Lattner2010-12-141-56/+61
| | | | | | when all 2-entry phis are simplified away. llvm-svn: 121760
* tidy up a bit, move DEBUG down to when we commit to doing the transform so we Chris Lattner2010-12-141-7/+5
| | | | | | don't print it unless the xform happens. llvm-svn: 121758
* use SimplifyInstruction instead of reimplementing part of it.Chris Lattner2010-12-141-10/+7
| | | | llvm-svn: 121757
* simplify GetIfCondition by using getSinglePredecessor.Chris Lattner2010-12-141-28/+24
| | | | llvm-svn: 121756
* use AddPredecessorToBlock in 3 places instead of a manual loop.Chris Lattner2010-12-141-18/+6
| | | | llvm-svn: 121755
* make FoldTwoEntryPHINode use instsimplify a bit, makeChris Lattner2010-12-141-12/+21
| | | | | | | GetIfCondition faster by avoiding pred_iterator. No really interesting change. llvm-svn: 121754
* improve DEBUG's a bit, switch to eraseFromParent() to simplifyChris Lattner2010-12-141-26/+28
| | | | | | code a bit, switch from constant folding to instsimplify. llvm-svn: 121751
* reapply my recent change that disables a piece of the switch formationChris Lattner2010-12-141-5/+13
| | | | | | work, but fixes 400.perlbmk. llvm-svn: 121749
* Fix recent buildbot breakage by pulling SimplifyCFG back to its state as of ↵Owen Anderson2010-12-131-14/+6
| | | | | | | | r121694, the most recent state where I'm confident there were no crashes or miscompilations. XFAIL the test added since then for now. llvm-svn: 121733
* temporarily disable part of my previous patch, which causes an iterator ↵Chris Lattner2010-12-131-1/+1
| | | | | | invalidation issue, causing a crash on some versions of perlbmk. llvm-svn: 121728
* add some DEBUG's.Chris Lattner2010-12-131-3/+8
| | | | llvm-svn: 121711
* Fix sort predicate. qsort(3)'s predicate semantics differ from std::sort's. ↵Benjamin Kramer2010-12-131-1/+1
| | | | | | Fixes PR 8780. llvm-svn: 121705
* reinstate my patch: the miscompile was caused by an inverted branch in theChris Lattner2010-12-131-3/+6
| | | | | | 'and' case. llvm-svn: 121695
* Completely disable the optimization I added in r121680 untilChris Lattner2010-12-131-3/+6
| | | | | | | I can track down a miscompile. This should bring the buildbots back to life llvm-svn: 121693
* Make simplifycfg reprocess newly formed "br (cond1 | cond2)" conditionsChris Lattner2010-12-131-5/+12
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | when simplifying, allowing them to be eagerly turned into switches. This is the last step required to get "Example 7" from this blog post: http://blog.regehr.org/archives/320 On X86, we now generate this machine code, which (to my eye) seems better than the ICC generated code: _crud: ## @crud ## BB#0: ## %entry cmpb $33, %dil jb LBB0_4 ## BB#1: ## %switch.early.test addb $-34, %dil cmpb $58, %dil ja LBB0_3 ## BB#2: ## %switch.early.test movzbl %dil, %eax movabsq $288230376537592865, %rcx ## imm = 0x400000017001421 btq %rax, %rcx jb LBB0_4 LBB0_3: ## %lor.rhs xorl %eax, %eax ret LBB0_4: ## %lor.end movl $1, %eax ret llvm-svn: 121690
* make this logic a bit simpler.Chris Lattner2010-12-131-21/+20
| | | | llvm-svn: 121689
* split all the guts of SimplifyCFGOpt::run out into one functionChris Lattner2010-12-131-374/+441
| | | | | | per terminator kind. llvm-svn: 121688
* fix a bug in r121680 that upset the various buildbots.Chris Lattner2010-12-131-0/+7
| | | | llvm-svn: 121687
* refactor the speculative execution logic to be factored into the cond branch ↵Chris Lattner2010-12-131-26/+22
| | | | | | | | code instead of doing a cfg search for every block simplified. llvm-svn: 121686
* simplify a bunch of code.Chris Lattner2010-12-131-15/+4
| | | | llvm-svn: 121685
* move HoistThenElseCodeToIf up to a more logical and efficient-to-handle place.Chris Lattner2010-12-131-7/+11
| | | | llvm-svn: 121684
* move 'MergeBlocksIntoPredecessor' call earlier. UseChris Lattner2010-12-131-20/+9
| | | | | | getSinglePredecessor to simplify code. llvm-svn: 121683
* factor new code out to a SimplifyBranchOnICmpChain helper function.Chris Lattner2010-12-131-77/+91
| | | | llvm-svn: 121681
* enhance the "change or icmp's into switch" xform to handle one value in an Chris Lattner2010-12-131-3/+45
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 'or sequence' that it doesn't understand. This allows us to optimize something insane like this: int crud (unsigned char c, unsigned x) { if(((((((((( (int) c <= 32 || (int) c == 46) || (int) c == 44) || (int) c == 58) || (int) c == 59) || (int) c == 60) || (int) c == 62) || (int) c == 34) || (int) c == 92) || (int) c == 39) != 0) foo(); } into: define i32 @crud(i8 zeroext %c, i32 %x) nounwind ssp noredzone { entry: %cmp = icmp ult i8 %c, 33 br i1 %cmp, label %if.then, label %switch.early.test switch.early.test: ; preds = %entry switch i8 %c, label %if.end [ i8 39, label %if.then i8 44, label %if.then i8 58, label %if.then i8 59, label %if.then i8 60, label %if.then i8 62, label %if.then i8 46, label %if.then i8 92, label %if.then i8 34, label %if.then ] by pulling the < comparison out ahead of the newly formed switch. llvm-svn: 121680
* merge two very similar functions into one that has a bool argument.Chris Lattner2010-12-131-47/+26
| | | | llvm-svn: 121678
* don't bother handling non-canonical icmp'sChris Lattner2010-12-131-11/+9
| | | | llvm-svn: 121676
* inline a function, making the result much simpler.Chris Lattner2010-12-131-27/+11
| | | | llvm-svn: 121675
* Fix my previous patch to handle a degenerate case that the llvm-gccChris Lattner2010-12-131-0/+16
| | | | | | bootstrap buildbot tripped over. llvm-svn: 121674
* convert some methods to be static functionsChris Lattner2010-12-131-25/+23
| | | | llvm-svn: 121673
* zap two more std::sorts.Chris Lattner2010-12-131-2/+2
| | | | llvm-svn: 121672
* fix a fairly serious oversight with switch formation fromChris Lattner2010-12-131-1/+97
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | or'd conditions. Previously we'd compile something like this: int crud (unsigned char c) { return c == 62 || c == 34 || c == 92; } into: switch i8 %c, label %lor.rhs [ i8 62, label %lor.end i8 34, label %lor.end ] lor.rhs: ; preds = %entry %cmp8 = icmp eq i8 %c, 92 br label %lor.end lor.end: ; preds = %entry, %entry, %lor.rhs %0 = phi i1 [ true, %entry ], [ %cmp8, %lor.rhs ], [ true, %entry ] %lor.ext = zext i1 %0 to i32 ret i32 %lor.ext which failed to merge the compare-with-92 into the switch. With this patch we simplify this all the way to: switch i8 %c, label %lor.rhs [ i8 62, label %lor.end i8 34, label %lor.end i8 92, label %lor.end ] lor.rhs: ; preds = %entry br label %lor.end lor.end: ; preds = %entry, %entry, %entry, %lor.rhs %0 = phi i1 [ true, %entry ], [ false, %lor.rhs ], [ true, %entry ], [ true, %entry ] %lor.ext = zext i1 %0 to i32 ret i32 %lor.ext which is much better for codegen's switch lowering stuff. This kicks in 33 times on 176.gcc (for example) cutting 103 instructions off the generated code. llvm-svn: 121671
* convert an std::sort to array_pod_sort.Chris Lattner2010-12-131-2/+8
| | | | llvm-svn: 121669
* move the "br (X == 0 | X == 1), T, F" -> switch optimization to a newChris Lattner2010-12-131-57/+56
| | | | | | | | | | | location in simplifycfg. In the old days, SimplifyCFG was never run on the entry block, so we had to scan over all preds of the BB passed into simplifycfg to do this xform, now we can just check blocks ending with a condbranch. This avoids a scan over all preds of every simplified block, which should be a significant compile-time perf win on functions with lots of edges. No functionality change. llvm-svn: 121668
* reduce indentation and generally simplify code, no functionality change.Chris Lattner2010-12-131-333/+309
| | | | llvm-svn: 121667
* use getFirstNonPHIOrDbg to simplify this code.Chris Lattner2010-12-131-9/+5
| | | | llvm-svn: 121664
* Teach SimplifyCFG to turnFrits van Bommel2010-12-051-2/+72
| | | | | | | | | (indirectbr (select cond, blockaddress(@fn, BlockA), blockaddress(@fn, BlockB))) into (br cond, BlockA, BlockB). llvm-svn: 120943
* Fix PR8445: a block with no predecessors may be the entry block, in which caseDuncan Sands2010-10-241-12/+10
| | | | | | | | | it isn't unreachable and should not be zapped. The check for the entry block was missing in one case: a block containing a unwind instruction. While there, do some small cleanups: "M" is not a great name for a Function* (it would be more appropriate for a Module*), change it to "Fn"; use Fn in more places. llvm-svn: 117224
* Instead, teach SimplifyCFG to trim non-address-taken blocks fromDan Gohman2010-08-161-2/+3
| | | | | | indirectbr destination lists. llvm-svn: 111122
* Teach SimplifyCFG how to simplify indirectbr instructions.Dan Gohman2010-08-141-13/+40
| | | | | | | | | | | - Eliminate redundant successors. - Convert an indirectbr with one successor into a direct branch. Also, generalize SimplifyCFG to be able to be run on a function entry block. It knows quite a few simplifications which are applicable to the entry block, and it only needs a few checks to avoid trouble with the entry block. llvm-svn: 111060
* pass dereferenced iterator to dyn_castGabor Greif2010-07-221-1/+1
| | | | llvm-svn: 109098
* Remove unneeded check, and correct style.Owen Anderson2010-07-151-3/+2
| | | | llvm-svn: 108427
* Extend SimplifyCFG's common-destination folding heuristic to allow a singleOwen Anderson2010-07-141-5/+67
| | | | | | | | | | "bonus" instruction to be speculatively executed. Add a heuristic to ensure we're not tripping up out-of-order execution by checking that this bonus instruction only uses values that were already guaranteed to be available. This allows us to eliminate the short circuit in (x&1)&&(x&2). llvm-svn: 108351
* cache dereferenced iteratorsGabor Greif2010-07-121-4/+6
| | | | llvm-svn: 108133
OpenPOWER on IntegriCloud