summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Transforms/Utils/SimplifyCFG.cpp
Commit message (Collapse)AuthorAgeFilesLines
* SimplifyCFG: Track the number of used icmps when turning a icmp chain into a ↵Benjamin Kramer2011-02-071-7/+22
| | | | | | | | switch. If we used only one icmp, don't turn it into a switch. Also prevent the switch-to-icmp transform from creating identity adds, noticed by Marius Wachtler. llvm-svn: 125056
* SimplifyCFG: Also transform switches that represent a range comparison but ↵Benjamin Kramer2011-02-031-6/+17
| | | | | | | | are not sorted into sub+icmp. This transforms another 1000 switches in gcc.c. llvm-svn: 124826
* SimplifyCFG: Turn switches into sub+icmp+branch if possible.Benjamin Kramer2011-02-021-0/+32
| | | | | | | | | | | | | | | | | This makes the job of the later optzn passes easier, allowing the vast amount of icmp transforms to chew on it. We transform 840 switches in gcc.c, leading to a 16k byte shrink of the resulting binary on i386-linux. The testcase from README.txt now compiles into decl %edi cmpl $3, %edi sbbl %eax, %eax andl $1, %eax ret llvm-svn: 124724
* Re-apply r124518 with fix. Watch out for invalidated iterator.Evan Cheng2011-01-291-18/+7
| | | | llvm-svn: 124526
* Revert r124518. It broke Linux self-host.Evan Cheng2011-01-291-7/+18
| | | | llvm-svn: 124522
* Re-commit r124462 with fixes. Tail recursion elim will now dup ret into ↵Evan Cheng2011-01-291-18/+7
| | | | | | unconditional predecessor to enable TCE on demand. llvm-svn: 124518
* Revert r124462. There are a few big regressions that I need to fix first.Evan Cheng2011-01-281-6/+1
| | | | llvm-svn: 124478
* - Stop simplifycfg from duplicating "ret" instructions into unconditionalEvan Cheng2011-01-281-1/+6
| | | | | | | | branches. PR8575, rdar://5134905, rdar://8911460. - Allow codegen tail duplication to dup small return blocks after register allocation is done. llvm-svn: 124462
* Factor the actual simplification out of SimplifyIndirectBrOnSelect and into ↵Frits van Bommel2011-01-111-26/+37
| | | | | | | | a new helper function so it can be reused in e.g. an upcoming SimplifySwitchOnSelect. No functional change. llvm-svn: 123234
* 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
OpenPOWER on IntegriCloud