aboutsummaryrefslogtreecommitdiff
path: root/lib/Transforms/Utils
AgeCommit message (Collapse)Author
2004-03-15Assert that input blocks meet the invariants we expectChris Lattner
Simplify the input/output finder. All elements of a basic block are instructions. Any used arguments are also inputs. An instruction can only be used by another instruction. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@12405 91177308-0d34-0410-b5e6-96231b3b80d8
2004-03-14No correctness fixes here, just minor qoi fixes:Chris Lattner
* Don't insert a branch to the switch instruction after the call, just make it a single block. * Insert the new alloca instructions in the entry block of the original function instead of having them execute dynamically * Don't make the default edge of the switch instruction go back to the switch. The loop extractor shouldn't create new loops! * Give meaningful names to the alloca slots and the reload instructions * Some minor code simplifications git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@12402 91177308-0d34-0410-b5e6-96231b3b80d8
2004-03-14Simplify code a bit, and fix bug CodeExtractor/2004-03-14-NoSwitchSupport.llChris Lattner
This also implements a two minor improvements: * Don't insert live-out stores IN the region, insert them on the code path that exits the region * If the region is exited to the same block from multiple paths, share the switch statement entry, live-out store code, and the basic block. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@12401 91177308-0d34-0410-b5e6-96231b3b80d8
2004-03-14Simplify the code a bit by making the collection of basic blocks to extractChris Lattner
a member of the class. While we're at it, turn the collection into a set instead of a vector to improve efficiency and make queries simpler. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@12400 91177308-0d34-0410-b5e6-96231b3b80d8
2004-03-14Do not create empty basic blocks when the lowerswitch pass expects blocks toChris Lattner
be non-empty! This fixes LowerSwitch/2004-03-13-SwitchIsDefaultCrash.ll git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@12384 91177308-0d34-0410-b5e6-96231b3b80d8
2004-03-14Minor random cleanupsChris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@12382 91177308-0d34-0410-b5e6-96231b3b80d8
2004-03-14If a block is dead, dominators will not be calculated for it. Because of thisChris Lattner
loop information won't see it, and we could have unreachable blocks pointing to the non-header node of blocks in a natural loop. This isn't tidy, so have the loopsimplify pass clean it up. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@12380 91177308-0d34-0410-b5e6-96231b3b80d8
2004-03-14Verify functions as they are produced if -debug is specified. ReduceChris Lattner
curly braceage git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@12378 91177308-0d34-0410-b5e6-96231b3b80d8
2004-03-14Move to the IPO library. Utils shouldn't contain passes.Chris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@12372 91177308-0d34-0410-b5e6-96231b3b80d8
2004-03-14DemoteRegToStack got moved from DemoteRegToStack.h to Local.hChris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@12368 91177308-0d34-0410-b5e6-96231b3b80d8
2004-03-13This little patch speeds up the loop used to update the dominator set analysis.Chris Lattner
On the testcase from GCC PR12440, which has a LOT of loops (1392 of which require preheaders to be inserted), this speeds up the loopsimplify pass from 1.931s to 0.1875s. The loop in question goes from 1.65s -> 0.0097s, which isn't bad. All of these times are a debug build. This adds a dependency on DominatorTree analysis that was not there before, but we always had dominatortree available anyway, because LICM requires both loop simplify and DT, so this doesn't add any extra analysis in practice. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@12362 91177308-0d34-0410-b5e6-96231b3b80d8
2004-03-12Add constant folding wrapper support for select instructions.Chris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@12319 91177308-0d34-0410-b5e6-96231b3b80d8
2004-03-03Don't emit things like malloc(16*1). Allocation instructions are fixed ↵Chris Lattner
arity now. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@12086 91177308-0d34-0410-b5e6-96231b3b80d8
2004-03-02Implement ExtractCodeRegion()Misha Brukman
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@12070 91177308-0d34-0410-b5e6-96231b3b80d8
2004-03-02Make a note that this is usually used via bugpoint.Misha Brukman
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@12068 91177308-0d34-0410-b5e6-96231b3b80d8
2004-03-01* Add implementation of ExtractBasicBlock()Misha Brukman
* Add comments to ExtractLoop() git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@12053 91177308-0d34-0410-b5e6-96231b3b80d8
2004-03-01Disable tail duplication in a case that breaks on Olden/tspChris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@12021 91177308-0d34-0410-b5e6-96231b3b80d8
2004-02-29Fix bug: test/Regression/Transforms/LowerInvoke/2004-02-29-PHICrash.llxChris Lattner
... which tickled the lowerinvoke pass because it used the BCE routines. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@12012 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-28if there is already a prototype for malloc/free, use it, even if it's incorrect.Chris Lattner
Do not just inject a new prototype. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11951 91177308-0d34-0410-b5e6-96231b3b80d8
2004-02-28Right, it's really Extractor, not Extraction.Misha Brukman
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11939 91177308-0d34-0410-b5e6-96231b3b80d8
2004-02-28A pass that uses the generic CodeExtractor to rip out *every* loop in everyMisha Brukman
function, as long as the loop isn't the only one in that function. This should help debugging passes easier with BugPoint. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11936 91177308-0d34-0410-b5e6-96231b3b80d8
2004-02-28A generic code extractor: given a list of BasicBlocks, it will rip them out intoMisha Brukman
a new function, taking care of inputs and outputs. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11935 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-25Fix incorrect debug codeChris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11821 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-17Fix PR245: Linking weak and strong global variables is dependent on link orderChris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11565 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-15Instead of producing calls to setjmp/longjmp, produce uses of theChris Lattner
llvm.setjmp/llvm.longjmp intrinsics. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11482 91177308-0d34-0410-b5e6-96231b3b80d8
2004-02-15Adjustments to support the new ConstantAggregateZero classChris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11474 91177308-0d34-0410-b5e6-96231b3b80d8
2004-02-13Fix compilation of 126.gcc: intrinsic functions cannot throw, so they are notChris Lattner
allowed in invoke instructions. Thus, if we are inlining a call to an intrinsic function into an invoke site, we don't need to turn the call into an invoke! git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11384 91177308-0d34-0410-b5e6-96231b3b80d8
2004-02-13Expose a pass ID that can be 'required'Chris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11376 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-09Only add the global variable with the abort message if an unwind actuallyChris Lattner
occurs in the program. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11249 91177308-0d34-0410-b5e6-96231b3b80d8
2004-02-08Fix grammar-o.Misha Brukman
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11210 91177308-0d34-0410-b5e6-96231b3b80d8
2004-02-08Improve compatibility with programs that already have a prototype for 'write',Chris Lattner
even if it is wierd in some way. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11207 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-02-08Implement proper invoke/unwind lowering.Chris Lattner
This fixed PR16 "[lowerinvoke] The -lowerinvoke pass does not insert calls to setjmp/longjmp" git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11195 91177308-0d34-0410-b5e6-96231b3b80d8
2004-02-08Add a call to 'write' right before the call to abort() in the unwind path.Chris Lattner
This causes the JIT, or LLC'd program to print out a nice message, explaining WHY the program aborted. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11184 91177308-0d34-0410-b5e6-96231b3b80d8
2004-02-05Fix another dominator update bug. These bugs keep getting exposed because GCSEChris Lattner
keeps finding more code motion opportunities now that the dominators are correct! git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11142 91177308-0d34-0410-b5e6-96231b3b80d8
2004-02-05Fix bug updating dominatorsChris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11140 91177308-0d34-0410-b5e6-96231b3b80d8
2004-02-05Fix PR223: Loopsimplify incorrectly updates dominator informationChris Lattner
The problem is that the dominator update code didn't "realize" that it's possible for the newly inserted basic block to dominate anything. Because it IS possible, stuff was getting updated wrong. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11137 91177308-0d34-0410-b5e6-96231b3b80d8
2004-02-04Minor speedup, don't query ValueMap each time through the loopChris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11123 91177308-0d34-0410-b5e6-96231b3b80d8
2004-02-04Two changes:Chris Lattner
1. Don't scan to the end of alloca instructions in the caller function to insert inlined allocas, just insert at the top. This saves a lot of time inlining into functions with a lot of allocas. 2. Use splice to move the alloca instructions over, instead of remove/insert. This allows us to transfer a block at a time, and eliminates a bunch of silly symbol table manipulations. This speeds up the inliner on the testcase in PR209 from 1.73s -> 1.04s (67%) git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11118 91177308-0d34-0410-b5e6-96231b3b80d8
2004-02-04Optimize the case where we are inlining a function that contains only one ↵Chris Lattner
basic block, and that basic block ends with a return instruction. In this case, we can just splice the cloned "body" of the function directly into the source basic block, avoiding a lot of rearrangement and splitBasicBlock's linear scan over the split block. This speeds up the inliner on the testcase in PR209 from 2.3s to 1.7s, a 35% reduction. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11116 91177308-0d34-0410-b5e6-96231b3b80d8
2004-02-04Adjust to the new BasicBlock ctor, which requires a function parameterChris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11114 91177308-0d34-0410-b5e6-96231b3b80d8
generated by cgit v1.2.3-18-g5258 (git 2.32.0) at 2025-07-19 03:41:38 +0000