summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Transforms
Commit message (Collapse)AuthorAgeFilesLines
* Implement switch->br and br->switch folding by ripping out the switch->switchChris Lattner2004-02-281-178/+174
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 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. llvm-svn: 11964
* if there is already a prototype for malloc/free, use it, even if it's incorrect.Chris Lattner2004-02-281-10/+42
| | | | | | Do not just inject a new prototype. llvm-svn: 11951
* Rename AddUsesToWorkList -> AddUsersToWorkList, as that is what it does.Chris Lattner2004-02-281-19/+54
| | | | | | | Create a new AddUsesToWorkList method optimize memmove/set/cpy of zero bytes to a noop. llvm-svn: 11941
* Turn 'free null' into nothingChris Lattner2004-02-281-0/+8
| | | | llvm-svn: 11940
* Right, it's really Extractor, not Extraction.Misha Brukman2004-02-281-2/+2
| | | | llvm-svn: 11939
* A pass that uses the generic CodeExtractor to rip out *every* loop in everyMisha Brukman2004-02-281-0/+69
| | | | | | | function, as long as the loop isn't the only one in that function. This should help debugging passes easier with BugPoint. llvm-svn: 11936
* A generic code extractor: given a list of BasicBlocks, it will rip them out intoMisha Brukman2004-02-281-0/+573
| | | | | | a new function, taking care of inputs and outputs. llvm-svn: 11935
* setcond instructions don't have aliasing implications.Chris Lattner2004-02-271-2/+2
| | | | llvm-svn: 11919
* Implement test/Regression/Transforms/InstCombine/canonicalize_branch.llChris Lattner2004-02-271-1/+23
| | | | | | | This is a really minor thing, but might help out the 'switch statement induction' code in simplifycfg. llvm-svn: 11900
* Since LLVM uses structure type equivalence, it isn't useful to keep aroundChris Lattner2004-02-261-10/+11
| | | | | | | multiple type names for the same structural type. Make DTE eliminate all but one of the type names llvm-svn: 11879
* turn things like:Chris Lattner2004-02-261-0/+74
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 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. llvm-svn: 11870
* My faith in programmers has been found to be totally misplaced. One wouldChris Lattner2004-02-251-0/+82
| | | | | | | | | | | | | | | | | | | | | | | | | | | assume that if they don't intend to write to a global variable, that they would mark it as constant. However, there are people that don't understand that the compiler can do nice things for them if they give it the information it needs. This pass looks for blatently obvious globals that are only ever read from. Though it uses a trivially simple "alias analysis" of sorts, it is still able to do amazing things to important benchmarks. 253.perlbmk, for example, contains several ***GIANT*** function pointer tables that are not marked constant and should be. Marking them constant allows the optimizer to turn a whole bunch of indirect calls into direct calls. Note that only a link-time optimizer can do this transformation, but perlbmk does have several strings and other minor globals that can be marked constant by this pass when run from GCCAS. 176.gcc has a ton of strings and large tables that are marked constant, both at compile time (38 of them) and at link time (48 more). Other benchmarks give similar results, though it seems like big ones have disproportionally more than small ones. This pass is extremely quick and does good things. I'm going to enable it in gccas & gccld. Not bad for 50 SLOC. llvm-svn: 11836
* Fix incorrect debug codeChris Lattner2004-02-251-1/+2
| | | | llvm-svn: 11821
* Fix a faulty optimization on FP valuesChris Lattner2004-02-241-1/+2
| | | | llvm-svn: 11801
* If a block is made dead, make sure to promptly remove it.Chris Lattner2004-02-241-0/+8
| | | | llvm-svn: 11799
* Implement SimplifyCFG/switch_switch_fold.llChris Lattner2004-02-241-2/+150
| | | | | | | | | | | | | | | 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) llvm-svn: 11797
* Rearrange code a bitChris Lattner2004-02-241-30/+27
| | | | llvm-svn: 11793
* Implement: test/Regression/Transforms/SimplifyCFG/switch_create.llChris Lattner2004-02-241-7/+140
| | | | | | | | | | This turns code like this: if (X == 4 | X == 7) and if (X != 4 & X != 7) into switch instructions. llvm-svn: 11792
* Generate much more efficient code in programs like pifftChris Lattner2004-02-231-0/+8
| | | | llvm-svn: 11775
* Fix a small typeo in my checkin last night that broke vortex and other ↵Chris Lattner2004-02-231-1/+1
| | | | | | programs :( llvm-svn: 11774
* Fix InstCombine/2004-02-23-ShiftShiftOverflow.llChris Lattner2004-02-231-3/+10
| | | | | | Also, turn 'shr int %X, 1234' into 'shr int %X, 31' llvm-svn: 11768
* Implement cast.ll::test14/15Chris Lattner2004-02-231-0/+37
| | | | llvm-svn: 11742
* Refactor some code. In the mul - setcc folding case, we really care aboutChris Lattner2004-02-231-32/+63
| | | | | | whether this is the sign bit or not, so check unsigned comparisons as well. llvm-svn: 11740
* Implement mul.ll:test11Chris Lattner2004-02-231-6/+7
| | | | llvm-svn: 11737
* Implement "strength reduction" of X <= C and X >= CChris Lattner2004-02-231-0/+9
| | | | llvm-svn: 11735
* Implement InstCombine/mul.ll:test10, which is a case that occurs when dealingChris Lattner2004-02-231-0/+40
| | | | | | with "predication" llvm-svn: 11734
* Implement Transforms/InstCombine/cast.ll:test13, a case which occurs in aChris Lattner2004-02-222-4/+35
| | | | | | hot 164.gzip loop. llvm-svn: 11702
* Fix PR245: Linking weak and strong global variables is dependent on link orderChris Lattner2004-02-171-1/+3
| | | | llvm-svn: 11565
* Implement test/Regression/Transforms/SimplifyCFG/UncondBranchToReturn.ll,Chris Lattner2004-02-161-0/+48
| | | | | | see the testcase for the reasoning. llvm-svn: 11496
* Fold PHI nodes of constants which are only used by a single cast. This ↵Chris Lattner2004-02-161-0/+29
| | | | | | | | implements phi.ll:test4 llvm-svn: 11494
* Teach LLVM to unravel the "swap idiom". This implements:Chris Lattner2004-02-161-2/+13
| | | | | | Regression/Transforms/InstCombine/xor.ll:test20 llvm-svn: 11492
* Implement Transforms/InstCombine/xor.ll:test19Chris Lattner2004-02-161-2/+13
| | | | llvm-svn: 11490
* Instead of producing calls to setjmp/longjmp, produce uses of theChris Lattner2004-02-151-2/+2
| | | | | | llvm.setjmp/llvm.longjmp intrinsics. llvm-svn: 11482
* Adjustments to support the new ConstantAggregateZero classChris Lattner2004-02-154-13/+30
| | | | llvm-svn: 11474
* Remove dependence on return type of ConstantStruct::getChris Lattner2004-02-151-1/+1
| | | | llvm-svn: 11466
* Remove dependence on the return type of ConstantArray::getChris Lattner2004-02-151-1/+1
| | | | llvm-svn: 11463
* Fix compilation of 126.gcc: intrinsic functions cannot throw, so they are notChris Lattner2004-02-131-28/+33
| | | | | | | 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! llvm-svn: 11384
* Intrinsic functions cannot throwChris Lattner2004-02-131-1/+1
| | | | llvm-svn: 11383
* Expose a pass ID that can be 'required'Chris Lattner2004-02-131-0/+2
| | | | llvm-svn: 11376
* Remove obsolete comment. Unreachable blocks will automatically be left at theChris Lattner2004-02-111-2/+0
| | | | | | end of the function. llvm-svn: 11313
* Add an _embarassingly simple_ implementation of basic block layout. This isChris Lattner2004-02-111-0/+141
| | | | | | | | more of a testcase for profiling information than anything that should reasonably be used, but it's a starting point. When I have more time I will whip this into better shape. llvm-svn: 11311
* Implement SimplifyCFG/PhiEliminate.llChris Lattner2004-02-111-5/+234
| | | | | | | 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. llvm-svn: 11307
* The hasConstantReferences predicate always returns false.Chris Lattner2004-02-111-52/+49
| | | | llvm-svn: 11301
* initialization calls now return argc. If the program uses the argc valueChris Lattner2004-02-101-17/+24
| | | | | | | passed into main, make sure they use the return value of the init call instead of the one passed in. llvm-svn: 11262
* Only add the global variable with the abort message if an unwind actuallyChris Lattner2004-02-091-14/+26
| | | | | | occurs in the program. llvm-svn: 11249
* Don't depend on auto data conversionChris Lattner2004-02-091-1/+1
| | | | llvm-svn: 11229
* Adjust to the changed StructType interface. In particular, ↵Chris Lattner2004-02-094-11/+9
| | | | | | getElementTypes() is gone. llvm-svn: 11228
* Start using the new and improve interface to FunctionType argumentsChris Lattner2004-02-093-21/+18
| | | | llvm-svn: 11224
* The ConstantExpr::getCast call can cause a CPR to be generated. If so,Chris Lattner2004-02-091-0/+4
| | | | | | strip it off. llvm-svn: 11213
* Fix grammar-o.Misha Brukman2004-02-081-1/+1
| | | | llvm-svn: 11210
OpenPOWER on IntegriCloud