aboutsummaryrefslogtreecommitdiff
path: root/lib/Transforms/Utils/SimplifyCFG.cpp
AgeCommit message (Collapse)Author
2004-07-21These files don't need to include <iostream> since they include ↵Brian Gaeke
"Support/Debug.h". git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@15089 91177308-0d34-0410-b5e6-96231b3b80d8
2004-07-20Implement SimplifyCFG/BrUnwind.llChris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@15022 91177308-0d34-0410-b5e6-96231b3b80d8
2004-07-18bug 122:Reid Spencer
- Minimize redundant isa<GlobalValue> usage git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@14948 91177308-0d34-0410-b5e6-96231b3b80d8
2004-07-15Progress on PR341Chris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@14840 91177308-0d34-0410-b5e6-96231b3b80d8
2004-07-04Add #include <iostream> since Value.h does not #include it any more.Reid Spencer
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@14622 91177308-0d34-0410-b5e6-96231b3b80d8
2004-06-21*FINALLY* Fix a really nasty nondeterministic bug that has been haunting usChris Lattner
since May 1st. In this code, the pred iterator was being invalidated sometimes causing the wrong entries to be added to PHI nodes. The fix for this is to defererence and safe the *PI value before we hack on branch instructions, which changes use/def chains, which SOMETIMES invalidates the iterator. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@14278 91177308-0d34-0410-b5e6-96231b3b80d8
2004-06-20Add some DEBUG output to the simplifycfg routinesChris Lattner
Fix another non-deterministic behavior, this one should actually speed up the code though as it was doing silly things. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@14258 91177308-0d34-0410-b5e6-96231b3b80d8
2004-06-19Do not sort by the address of LLVM ConstantInt* objects. This producesChris Lattner
nondeterministic results that depend on where these objects land in memory. Instead, sort by the value of the constant, which is stable. Before this patch, the -simplifycfg pass run from two different compilers could cause different code to be generated, though it was semantically the same: @@ -12258,8 +12258,8 @@ %s_addr.1 = phi sbyte* [ %s, %entry ], [ %inc.0, %no_exit ] ; <sbyte*> [#uses=5] %tmp.1 = load sbyte* %s_addr.1 ; <sbyte> [#uses=1] switch sbyte %tmp.1, label %no_exit [ - sbyte 0, label %loopexit sbyte 46, label %loopexit + sbyte 0, label %loopexit ] We need to stomp all of this stuff out. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@14243 91177308-0d34-0410-b5e6-96231b3b80d8
2004-05-02Do not clone arbitrary condition instructions.Chris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@13316 91177308-0d34-0410-b5e6-96231b3b80d8
2004-05-02Do not infinitely "unroll" single BB loops.Chris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@13315 91177308-0d34-0410-b5e6-96231b3b80d8
2004-05-02Dont' merge terminators that are needed to select PHI node values.Chris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@13312 91177308-0d34-0410-b5e6-96231b3b80d8
2004-05-01Implement SimplifyCFG/branch-cond-merge.llChris Lattner
Turning "if (A < B && B < C)" into "if (A < B & B < C)" git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@13311 91177308-0d34-0410-b5e6-96231b3b80d8
2004-05-01Fix my missing parensChris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@13307 91177308-0d34-0410-b5e6-96231b3b80d8
2004-05-01Implement SimplifyCFG/branch-cond-prop.llChris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@13306 91177308-0d34-0410-b5e6-96231b3b80d8
2004-04-09Fold code like:Chris Lattner
if (C) V1 |= V2; into: Vx = V1 | V2; V1 = select C, V1, Vx when the expression can be evaluated unconditionally and is *cheap* to execute. This limited form of if conversion is quite handy in lots of cases. For example, it turns this testcase into straight-line code: int in0 ; int in1 ; int in2 ; int in3 ; int in4 ; int in5 ; int in6 ; int in7 ; int in8 ; int in9 ; int in10; int in11; int in12; int in13; int in14; int in15; long output; void mux(void) { output = (in0 ? 0x00000001 : 0) | (in1 ? 0x00000002 : 0) | (in2 ? 0x00000004 : 0) | (in3 ? 0x00000008 : 0) | (in4 ? 0x00000010 : 0) | (in5 ? 0x00000020 : 0) | (in6 ? 0x00000040 : 0) | (in7 ? 0x00000080 : 0) | (in8 ? 0x00000100 : 0) | (in9 ? 0x00000200 : 0) | (in10 ? 0x00000400 : 0) | (in11 ? 0x00000800 : 0) | (in12 ? 0x00001000 : 0) | (in13 ? 0x00002000 : 0) | (in14 ? 0x00004000 : 0) | (in15 ? 0x00008000 : 0) ; } git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@12798 91177308-0d34-0410-b5e6-96231b3b80d8
2004-04-02Fix the obvious bug in my previous checkinChris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@12618 91177308-0d34-0410-b5e6-96231b3b80d8
2004-04-02Implement Transforms/SimplifyCFG/return-merge.llChris Lattner
This actually causes us to turn code like: return C ? A : B; into a select instruction. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@12617 91177308-0d34-0410-b5e6-96231b3b80d8
2004-03-30Now that all the code generators support the select instruction, and the ↵Chris Lattner
instcombine pass can eliminate many nasty cases of them, start generating them in the optimizers git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@12545 91177308-0d34-0410-b5e6-96231b3b80d8
2004-03-17Fix compilation of mesa, which I broke earlier todayChris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@12465 91177308-0d34-0410-b5e6-96231b3b80d8
2004-03-16Do not copy gigantic switch instructionsChris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@12441 91177308-0d34-0410-b5e6-96231b3b80d8
2004-02-28Implement switch->br and br->switch folding by ripping out the switch->switchChris Lattner
and br->br code and generalizing it. This allows us to compile code like this: int test(Instruction *I) { if (isa<CastInst>(I)) return foo(7); else if (isa<BranchInst>(I)) return foo(123); else if (isa<UnwindInst>(I)) return foo(1241); else if (isa<SetCondInst>(I)) return foo(1); else if (isa<VAArgInst>(I)) return foo(42); return foo(-1); } into: int %_Z4testPN4llvm11InstructionE("struct.llvm::Instruction"* %I) { entry: %tmp.1.i.i.i.i.i.i.i = getelementptr "struct.llvm::Instruction"* %I, long 0, ubyte 4 ; <uint*> [#uses=1] %tmp.2.i.i.i.i.i.i.i = load uint* %tmp.1.i.i.i.i.i.i.i ; <uint> [#uses=2] %tmp.2.i.i.i.i.i.i = seteq uint %tmp.2.i.i.i.i.i.i.i, 27 ; <bool> [#uses=0] switch uint %tmp.2.i.i.i.i.i.i.i, label %endif.0 [ uint 27, label %then.0 uint 2, label %then.1 uint 5, label %then.2 uint 14, label %then.3 uint 15, label %then.3 uint 16, label %then.3 uint 17, label %then.3 uint 18, label %then.3 uint 19, label %then.3 uint 32, label %then.4 ] ... As well as handling the cases in 176.gcc and many other programs more effectively. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11964 91177308-0d34-0410-b5e6-96231b3b80d8
2004-02-26turn things like:Chris Lattner
if (X == 0 || X == 2) ...where the comparisons and branches are in different blocks... into a switch instruction. This comes up a lot in various programs, and works well with the switch/switch merging code I checked earlier. For example, this testcase: int switchtest(int C) { return C == 0 ? f(123) : C == 1 ? f(3123) : C == 4 ? f(312) : C == 5 ? f(1234): f(444); } is converted into this: switch int %C, label %cond_false.3 [ int 0, label %cond_true.0 int 1, label %cond_true.1 int 4, label %cond_true.2 int 5, label %cond_true.3 ] instead of a whole bunch of conditional branches. Admittedly the code is ugly, and incomplete. To be complete, we need to add br -> switch merging and switch -> br merging. For example, this testcase: struct foo { int Q, R, Z; }; #define A (X->Q+X->R * 123) int test(struct foo *X) { return A == 123 ? X1() : A == 12321 ? X2(): (A == 111 || A == 222) ? X3() : A == 875 ? X4() : X5(); } Gets compiled to this: switch int %tmp.7, label %cond_false.2 [ int 123, label %cond_true.0 int 12321, label %cond_true.1 int 111, label %cond_true.2 int 222, label %cond_true.2 ] ... cond_false.2: ; preds = %entry %tmp.52 = seteq int %tmp.7, 875 ; <bool> [#uses=1] br bool %tmp.52, label %cond_true.3, label %cond_false.3 where the branch could be folded into the switch. This kind of thing occurs *ALL OF THE TIME*, especially in programs like 176.gcc, which is a horrible mess of code. It contains stuff like *shudder*: #define SWITCH_TAKES_ARG(CHAR) \ ( (CHAR) == 'D' \ || (CHAR) == 'U' \ || (CHAR) == 'o' \ || (CHAR) == 'e' \ || (CHAR) == 'u' \ || (CHAR) == 'I' \ || (CHAR) == 'm' \ || (CHAR) == 'L' \ || (CHAR) == 'A' \ || (CHAR) == 'h' \ || (CHAR) == 'z') and #define CONST_OK_FOR_LETTER_P(VALUE, C) \ ((C) == 'I' ? SMALL_INTVAL (VALUE) \ : (C) == 'J' ? SMALL_INTVAL (-(VALUE)) \ : (C) == 'K' ? (unsigned)(VALUE) < 32 \ : (C) == 'L' ? ((VALUE) & 0xffff) == 0 \ : (C) == 'M' ? integer_ok_for_set (VALUE) \ : (C) == 'N' ? (VALUE) < 0 \ : (C) == 'O' ? (VALUE) == 0 \ : (C) == 'P' ? (VALUE) >= 0 \ : 0) and #define LEGITIMIZE_ADDRESS(X,OLDX,MODE,WIN) \ { \ if (GET_CODE (X) == PLUS && CONSTANT_ADDRESS_P (XEXP (X, 1))) \ (X) = gen_rtx (PLUS, SImode, XEXP (X, 0), \ copy_to_mode_reg (SImode, XEXP (X, 1))); \ if (GET_CODE (X) == PLUS && CONSTANT_ADDRESS_P (XEXP (X, 0))) \ (X) = gen_rtx (PLUS, SImode, XEXP (X, 1), \ copy_to_mode_reg (SImode, XEXP (X, 0))); \ if (GET_CODE (X) == PLUS && GET_CODE (XEXP (X, 0)) == MULT) \ (X) = gen_rtx (PLUS, SImode, XEXP (X, 1), \ force_operand (XEXP (X, 0), 0)); \ if (GET_CODE (X) == PLUS && GET_CODE (XEXP (X, 1)) == MULT) \ (X) = gen_rtx (PLUS, SImode, XEXP (X, 0), \ force_operand (XEXP (X, 1), 0)); \ if (GET_CODE (X) == PLUS && GET_CODE (XEXP (X, 0)) == PLUS) \ (X) = gen_rtx (PLUS, Pmode, force_operand (XEXP (X, 0), NULL_RTX),\ XEXP (X, 1)); \ if (GET_CODE (X) == PLUS && GET_CODE (XEXP (X, 1)) == PLUS) \ (X) = gen_rtx (PLUS, Pmode, XEXP (X, 0), \ force_operand (XEXP (X, 1), NULL_RTX)); \ if (GET_CODE (X) == SYMBOL_REF || GET_CODE (X) == CONST \ || GET_CODE (X) == LABEL_REF) \ (X) = legitimize_address (flag_pic, X, 0, 0); \ if (memory_address_p (MODE, X)) \ goto WIN; } and others. These macros get used multiple times of course. These are such lovely candidates for macros, aren't they? :) This code also nicely handles LLVM constructs that look like this: if (isa<CastInst>(I)) ... else if (isa<BranchInst>(I)) ... else if (isa<SetCondInst>(I)) ... else if (isa<UnwindInst>(I)) ... else if (isa<VAArgInst>(I)) ... where the isa can obviously be a dyn_cast as well. Switch instructions are a good thing. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11870 91177308-0d34-0410-b5e6-96231b3b80d8
2004-02-24If a block is made dead, make sure to promptly remove it.Chris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11799 91177308-0d34-0410-b5e6-96231b3b80d8
2004-02-24Implement SimplifyCFG/switch_switch_fold.llChris Lattner
This case occurs many times in various benchmarks, especially when combined with the previous patch. This allows it to get stuff like: if (X == 4 || X == 3) if (X == 5 || X == 8) and switch (X) { case 4: case 5: case 6: if (X == 4 || X == 5) git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11797 91177308-0d34-0410-b5e6-96231b3b80d8
2004-02-24Rearrange code a bitChris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11793 91177308-0d34-0410-b5e6-96231b3b80d8
2004-02-24Implement: test/Regression/Transforms/SimplifyCFG/switch_create.llChris Lattner
This turns code like this: if (X == 4 | X == 7) and if (X != 4 & X != 7) into switch instructions. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11792 91177308-0d34-0410-b5e6-96231b3b80d8
2004-02-16Implement test/Regression/Transforms/SimplifyCFG/UncondBranchToReturn.ll,Chris Lattner
see the testcase for the reasoning. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11496 91177308-0d34-0410-b5e6-96231b3b80d8
2004-02-11Implement SimplifyCFG/PhiEliminate.llChris Lattner
Having a proper 'select' instruction would allow the elimination of a lot of the special case cruft in this patch, but we don't have one yet. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11307 91177308-0d34-0410-b5e6-96231b3b80d8
2004-02-11The hasConstantReferences predicate always returns false.Chris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11301 91177308-0d34-0410-b5e6-96231b3b80d8
2004-02-08rename the "exceptional" destination of an invoke instruction to the ↵Chris Lattner
'unwind' dest git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11202 91177308-0d34-0410-b5e6-96231b3b80d8
2004-01-09Finegrainify namespacificationChris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@10727 91177308-0d34-0410-b5e6-96231b3b80d8
2003-11-11Put all LLVM code into the llvm namespace, as per bug 109.Brian Gaeke
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@9903 91177308-0d34-0410-b5e6-96231b3b80d8
2003-10-20Added LLVM project notice to the top of every C++ source file.John Criswell
Header files will be on the way. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@9298 91177308-0d34-0410-b5e6-96231b3b80d8
2003-10-10Fix spelling.Misha Brukman
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@9027 91177308-0d34-0410-b5e6-96231b3b80d8
2003-09-08Eliminate support for the llvm.unwind intrinisic, using the Unwind ↵Chris Lattner
instruction instead git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@8411 91177308-0d34-0410-b5e6-96231b3b80d8
2003-08-24Implement SimplifyCFG/InvokeEliminate.llChris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@8126 91177308-0d34-0410-b5e6-96231b3b80d8
2003-08-17Fix bug: SimplifyCFG/2003-08-17-BranchFoldOrdering.llChris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@7921 91177308-0d34-0410-b5e6-96231b3b80d8
2003-08-05Fix bug: SimplifyCFG/2003-08-05-InvokeCrash.llChris Lattner
Fix bug: SimplifyCFG/2003-08-05-MishandleInvoke.ll git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@7599 91177308-0d34-0410-b5e6-96231b3b80d8
2003-04-23Remove unnecesary &*'sChris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@5872 91177308-0d34-0410-b5e6-96231b3b80d8
2003-03-07Fix bug: SimplifyCFG/2003-03-07-DominateProblem.llChris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@5722 91177308-0d34-0410-b5e6-96231b3b80d8
2003-03-05Implement CFGSimplify/PhiBlockMerge*.llChris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@5702 91177308-0d34-0410-b5e6-96231b3b80d8
2003-03-05Implement testcase CFGSimplify/EqualPHIEdgeBlockMerge.llChris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@5699 91177308-0d34-0410-b5e6-96231b3b80d8
2002-10-29Fix spelling of `propagate'.Misha Brukman
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@4423 91177308-0d34-0410-b5e6-96231b3b80d8
2002-10-08Changes to support PHINode::removeIncoming changesChris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@4079 91177308-0d34-0410-b5e6-96231b3b80d8
2002-09-24Fix bug: SimplifyCFG/2002-09-24-PHIAssertion.llChris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@3913 91177308-0d34-0410-b5e6-96231b3b80d8
2002-09-24Minor cleanupsChris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@3904 91177308-0d34-0410-b5e6-96231b3b80d8
2002-07-29Allow folding of basic blocks that have PHI nodes in them, fixing "bug":Chris Lattner
test/Regression/Transforms/SimplifyCFG/2002-06-24-PHINode.ll git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@3128 91177308-0d34-0410-b5e6-96231b3b80d8
2002-06-25*** empty log message ***Chris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@2777 91177308-0d34-0410-b5e6-96231b3b80d8
2002-05-21Add implementation of SimplifyCFGChris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@2701 91177308-0d34-0410-b5e6-96231b3b80d8
generated by cgit v1.2.3-18-g5258 (git 2.32.0) at 2025-05-02 21:14:43 +0000