Chris Lattner | cf3056d | 2003-10-13 03:32:08 +0000 | [diff] [blame] | 1 | //===- LevelRaise.cpp - Code to change LLVM to higher level ---------------===// |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 2 | // |
John Criswell | b576c94 | 2003-10-20 19:43:21 +0000 | [diff] [blame] | 3 | // The LLVM Compiler Infrastructure |
| 4 | // |
| 5 | // This file was developed by the LLVM research group and is distributed under |
| 6 | // the University of Illinois Open Source License. See LICENSE.TXT for details. |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 7 | // |
John Criswell | b576c94 | 2003-10-20 19:43:21 +0000 | [diff] [blame] | 8 | //===----------------------------------------------------------------------===// |
Chris Lattner | d32a961 | 2001-11-01 02:42:08 +0000 | [diff] [blame] | 9 | // |
| 10 | // This file implements the 'raising' part of the LevelChange API. This is |
| 11 | // useful because, in general, it makes the LLVM code terser and easier to |
Chris Lattner | 3cc7dde | 2001-11-26 16:58:14 +0000 | [diff] [blame] | 12 | // analyze. |
Chris Lattner | d32a961 | 2001-11-01 02:42:08 +0000 | [diff] [blame] | 13 | // |
| 14 | //===----------------------------------------------------------------------===// |
| 15 | |
Chris Lattner | bf88100 | 2003-09-01 20:45:33 +0000 | [diff] [blame] | 16 | #include "llvm/Transforms/Scalar.h" |
Chris Lattner | 497c60c | 2002-05-07 18:12:18 +0000 | [diff] [blame] | 17 | #include "llvm/Transforms/Utils/Local.h" |
Chris Lattner | 59cd9f1 | 2001-11-04 23:24:06 +0000 | [diff] [blame] | 18 | #include "TransformInternals.h" |
Alkis Evlogimenos | eb62bc7 | 2004-07-29 12:17:34 +0000 | [diff] [blame] | 19 | #include "llvm/Instructions.h" |
Chris Lattner | bd0ef77 | 2002-02-26 21:46:54 +0000 | [diff] [blame] | 20 | #include "llvm/Pass.h" |
Chris Lattner | 497c60c | 2002-05-07 18:12:18 +0000 | [diff] [blame] | 21 | #include "llvm/Transforms/Utils/BasicBlockUtils.h" |
Reid Spencer | 551ccae | 2004-09-01 22:55:40 +0000 | [diff] [blame] | 22 | #include "llvm/Support/CommandLine.h" |
| 23 | #include "llvm/Support/Debug.h" |
| 24 | #include "llvm/ADT/Statistic.h" |
| 25 | #include "llvm/ADT/STLExtras.h" |
Chris Lattner | d32a961 | 2001-11-01 02:42:08 +0000 | [diff] [blame] | 26 | #include <algorithm> |
Chris Lattner | dac58ad | 2006-01-22 23:32:06 +0000 | [diff] [blame^] | 27 | #include <iostream> |
Chris Lattner | e799902 | 2003-12-23 07:43:38 +0000 | [diff] [blame] | 28 | using namespace llvm; |
Brian Gaeke | d0fde30 | 2003-11-11 22:41:34 +0000 | [diff] [blame] | 29 | |
Chris Lattner | 3378a5b | 2002-07-16 23:49:24 +0000 | [diff] [blame] | 30 | // StartInst - This enables the -raise-start-inst=foo option to cause the level |
| 31 | // raising pass to start at instruction "foo", which is immensely useful for |
| 32 | // debugging! |
| 33 | // |
Chris Lattner | 5ff62e9 | 2002-07-22 02:10:13 +0000 | [diff] [blame] | 34 | static cl::opt<std::string> |
| 35 | StartInst("raise-start-inst", cl::Hidden, cl::value_desc("inst name"), |
| 36 | cl::desc("Start raise pass at the instruction with the specified name")); |
Chris Lattner | 3378a5b | 2002-07-16 23:49:24 +0000 | [diff] [blame] | 37 | |
Chris Lattner | 5ff62e9 | 2002-07-22 02:10:13 +0000 | [diff] [blame] | 38 | static Statistic<> |
Chris Lattner | 6ee6bbe | 2002-10-01 22:38:37 +0000 | [diff] [blame] | 39 | NumLoadStorePeepholes("raise", "Number of load/store peepholes"); |
Chris Lattner | 5ff62e9 | 2002-07-22 02:10:13 +0000 | [diff] [blame] | 40 | |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 41 | static Statistic<> |
Chris Lattner | 6ee6bbe | 2002-10-01 22:38:37 +0000 | [diff] [blame] | 42 | NumGEPInstFormed("raise", "Number of other getelementptr's formed"); |
Chris Lattner | 5ff62e9 | 2002-07-22 02:10:13 +0000 | [diff] [blame] | 43 | |
| 44 | static Statistic<> |
Chris Lattner | 6ee6bbe | 2002-10-01 22:38:37 +0000 | [diff] [blame] | 45 | NumExprTreesConv("raise", "Number of expression trees converted"); |
Chris Lattner | 5ff62e9 | 2002-07-22 02:10:13 +0000 | [diff] [blame] | 46 | |
| 47 | static Statistic<> |
Chris Lattner | 6ee6bbe | 2002-10-01 22:38:37 +0000 | [diff] [blame] | 48 | NumCastOfCast("raise", "Number of cast-of-self removed"); |
Chris Lattner | 5ff62e9 | 2002-07-22 02:10:13 +0000 | [diff] [blame] | 49 | |
| 50 | static Statistic<> |
Chris Lattner | 6ee6bbe | 2002-10-01 22:38:37 +0000 | [diff] [blame] | 51 | NumDCEorCP("raise", "Number of insts DCEd or constprop'd"); |
Chris Lattner | 3c01937 | 2002-05-10 15:29:25 +0000 | [diff] [blame] | 52 | |
Chris Lattner | 61b92c0 | 2002-10-08 22:19:25 +0000 | [diff] [blame] | 53 | static Statistic<> |
| 54 | NumVarargCallChanges("raise", "Number of vararg call peepholes"); |
| 55 | |
Chris Lattner | d32a961 | 2001-11-01 02:42:08 +0000 | [diff] [blame] | 56 | #define PRINT_PEEPHOLE(ID, NUM, I) \ |
Chris Lattner | b3abf9d | 2002-05-22 17:27:12 +0000 | [diff] [blame] | 57 | DEBUG(std::cerr << "Inst P/H " << ID << "[" << NUM << "] " << I) |
Chris Lattner | d32a961 | 2001-11-01 02:42:08 +0000 | [diff] [blame] | 58 | |
| 59 | #define PRINT_PEEPHOLE1(ID, I1) do { PRINT_PEEPHOLE(ID, 0, I1); } while (0) |
| 60 | #define PRINT_PEEPHOLE2(ID, I1, I2) \ |
| 61 | do { PRINT_PEEPHOLE(ID, 0, I1); PRINT_PEEPHOLE(ID, 1, I2); } while (0) |
| 62 | #define PRINT_PEEPHOLE3(ID, I1, I2, I3) \ |
| 63 | do { PRINT_PEEPHOLE(ID, 0, I1); PRINT_PEEPHOLE(ID, 1, I2); \ |
| 64 | PRINT_PEEPHOLE(ID, 2, I3); } while (0) |
Chris Lattner | d5b48ca | 2001-11-14 11:02:49 +0000 | [diff] [blame] | 65 | #define PRINT_PEEPHOLE4(ID, I1, I2, I3, I4) \ |
| 66 | do { PRINT_PEEPHOLE(ID, 0, I1); PRINT_PEEPHOLE(ID, 1, I2); \ |
| 67 | PRINT_PEEPHOLE(ID, 2, I3); PRINT_PEEPHOLE(ID, 3, I4); } while (0) |
Chris Lattner | d32a961 | 2001-11-01 02:42:08 +0000 | [diff] [blame] | 68 | |
Chris Lattner | 16125fb | 2003-04-24 18:25:27 +0000 | [diff] [blame] | 69 | namespace { |
| 70 | struct RPR : public FunctionPass { |
| 71 | virtual bool runOnFunction(Function &F); |
| 72 | |
| 73 | virtual void getAnalysisUsage(AnalysisUsage &AU) const { |
| 74 | AU.setPreservesCFG(); |
| 75 | AU.addRequired<TargetData>(); |
| 76 | } |
| 77 | |
| 78 | private: |
| 79 | bool DoRaisePass(Function &F); |
| 80 | bool PeepholeOptimize(BasicBlock *BB, BasicBlock::iterator &BI); |
| 81 | }; |
| 82 | |
| 83 | RegisterOpt<RPR> X("raise", "Raise Pointer References"); |
| 84 | } |
| 85 | |
Brian Gaeke | d0fde30 | 2003-11-11 22:41:34 +0000 | [diff] [blame] | 86 | |
Chris Lattner | ded6d0c | 2004-09-20 04:43:57 +0000 | [diff] [blame] | 87 | FunctionPass *llvm::createRaisePointerReferencesPass() { |
Chris Lattner | 16125fb | 2003-04-24 18:25:27 +0000 | [diff] [blame] | 88 | return new RPR(); |
| 89 | } |
| 90 | |
| 91 | |
Chris Lattner | d32a961 | 2001-11-01 02:42:08 +0000 | [diff] [blame] | 92 | // isReinterpretingCast - Return true if the cast instruction specified will |
| 93 | // cause the operand to be "reinterpreted". A value is reinterpreted if the |
| 94 | // cast instruction would cause the underlying bits to change. |
| 95 | // |
| 96 | static inline bool isReinterpretingCast(const CastInst *CI) { |
Misha Brukman | f117cc9 | 2003-05-20 18:45:36 +0000 | [diff] [blame] | 97 | return!CI->getOperand(0)->getType()->isLosslesslyConvertibleTo(CI->getType()); |
Chris Lattner | d32a961 | 2001-11-01 02:42:08 +0000 | [diff] [blame] | 98 | } |
| 99 | |
Chris Lattner | 16125fb | 2003-04-24 18:25:27 +0000 | [diff] [blame] | 100 | bool RPR::PeepholeOptimize(BasicBlock *BB, BasicBlock::iterator &BI) { |
Chris Lattner | 7e70829 | 2002-06-25 16:13:24 +0000 | [diff] [blame] | 101 | Instruction *I = BI; |
Chris Lattner | 16125fb | 2003-04-24 18:25:27 +0000 | [diff] [blame] | 102 | const TargetData &TD = getAnalysis<TargetData>(); |
Chris Lattner | d32a961 | 2001-11-01 02:42:08 +0000 | [diff] [blame] | 103 | |
| 104 | if (CastInst *CI = dyn_cast<CastInst>(I)) { |
| 105 | Value *Src = CI->getOperand(0); |
| 106 | Instruction *SrcI = dyn_cast<Instruction>(Src); // Nonnull if instr source |
| 107 | const Type *DestTy = CI->getType(); |
| 108 | |
Chris Lattner | e99c66b | 2001-11-01 17:05:27 +0000 | [diff] [blame] | 109 | // Peephole optimize the following instruction: |
| 110 | // %V2 = cast <ty> %V to <ty> |
| 111 | // |
| 112 | // Into: <nothing> |
| 113 | // |
| 114 | if (DestTy == Src->getType()) { // Check for a cast to same type as src!! |
Chris Lattner | 30b4344 | 2004-07-15 02:06:12 +0000 | [diff] [blame] | 115 | PRINT_PEEPHOLE1("cast-of-self-ty", *CI); |
Chris Lattner | d32a961 | 2001-11-01 02:42:08 +0000 | [diff] [blame] | 116 | CI->replaceAllUsesWith(Src); |
| 117 | if (!Src->hasName() && CI->hasName()) { |
Chris Lattner | 697954c | 2002-01-20 22:54:45 +0000 | [diff] [blame] | 118 | std::string Name = CI->getName(); |
Chris Lattner | f3b976e | 2001-11-04 20:21:12 +0000 | [diff] [blame] | 119 | CI->setName(""); |
Chris Lattner | 7acff25 | 2005-03-05 19:05:20 +0000 | [diff] [blame] | 120 | Src->setName(Name); |
Chris Lattner | d32a961 | 2001-11-01 02:42:08 +0000 | [diff] [blame] | 121 | } |
Chris Lattner | 3c01937 | 2002-05-10 15:29:25 +0000 | [diff] [blame] | 122 | |
| 123 | // DCE the instruction now, to avoid having the iterative version of DCE |
| 124 | // have to worry about it. |
| 125 | // |
Chris Lattner | 7e70829 | 2002-06-25 16:13:24 +0000 | [diff] [blame] | 126 | BI = BB->getInstList().erase(BI); |
Chris Lattner | 3c01937 | 2002-05-10 15:29:25 +0000 | [diff] [blame] | 127 | |
| 128 | ++NumCastOfCast; |
Chris Lattner | d32a961 | 2001-11-01 02:42:08 +0000 | [diff] [blame] | 129 | return true; |
| 130 | } |
| 131 | |
Chris Lattner | d32a961 | 2001-11-01 02:42:08 +0000 | [diff] [blame] | 132 | // Check to see if it's a cast of an instruction that does not depend on the |
| 133 | // specific type of the operands to do it's job. |
Chris Lattner | f3b976e | 2001-11-04 20:21:12 +0000 | [diff] [blame] | 134 | if (!isReinterpretingCast(CI)) { |
Chris Lattner | b980e18 | 2001-11-04 21:32:11 +0000 | [diff] [blame] | 135 | ValueTypeCache ConvertedTypes; |
Chris Lattner | a8b6d43 | 2001-12-05 06:34:00 +0000 | [diff] [blame] | 136 | |
Chris Lattner | d20a98e | 2002-05-24 20:41:51 +0000 | [diff] [blame] | 137 | // Check to see if we can convert the source of the cast to match the |
| 138 | // destination type of the cast... |
Chris Lattner | a8b6d43 | 2001-12-05 06:34:00 +0000 | [diff] [blame] | 139 | // |
Chris Lattner | d554380 | 2001-12-14 16:37:52 +0000 | [diff] [blame] | 140 | ConvertedTypes[CI] = CI->getType(); // Make sure the cast doesn't change |
Misha Brukman | f117cc9 | 2003-05-20 18:45:36 +0000 | [diff] [blame] | 141 | if (ExpressionConvertibleToType(Src, DestTy, ConvertedTypes, TD)) { |
Chris Lattner | 30b4344 | 2004-07-15 02:06:12 +0000 | [diff] [blame] | 142 | PRINT_PEEPHOLE3("CAST-SRC-EXPR-CONV:in ", *Src, *CI, *BB->getParent()); |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 143 | |
Chris Lattner | 6806f56 | 2003-08-01 22:15:03 +0000 | [diff] [blame] | 144 | DEBUG(std::cerr << "\nCONVERTING SRC EXPR TYPE:\n"); |
Chris Lattner | b1b4262 | 2002-07-17 17:11:33 +0000 | [diff] [blame] | 145 | { // ValueMap must be destroyed before function verified! |
| 146 | ValueMapCache ValueMap; |
Chris Lattner | 16125fb | 2003-04-24 18:25:27 +0000 | [diff] [blame] | 147 | Value *E = ConvertExpressionToType(Src, DestTy, ValueMap, TD); |
Chris Lattner | c0b90e7 | 2001-11-08 20:19:56 +0000 | [diff] [blame] | 148 | |
Chris Lattner | b1b4262 | 2002-07-17 17:11:33 +0000 | [diff] [blame] | 149 | if (Constant *CPV = dyn_cast<Constant>(E)) |
| 150 | CI->replaceAllUsesWith(CPV); |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 151 | |
Chris Lattner | 30b4344 | 2004-07-15 02:06:12 +0000 | [diff] [blame] | 152 | PRINT_PEEPHOLE1("CAST-SRC-EXPR-CONV:out", *E); |
Chris Lattner | 6806f56 | 2003-08-01 22:15:03 +0000 | [diff] [blame] | 153 | DEBUG(std::cerr << "DONE CONVERTING SRC EXPR TYPE: \n" |
Chris Lattner | 30b4344 | 2004-07-15 02:06:12 +0000 | [diff] [blame] | 154 | << *BB->getParent()); |
Chris Lattner | b1b4262 | 2002-07-17 17:11:33 +0000 | [diff] [blame] | 155 | } |
Chris Lattner | 3378a5b | 2002-07-16 23:49:24 +0000 | [diff] [blame] | 156 | |
Chris Lattner | b1b4262 | 2002-07-17 17:11:33 +0000 | [diff] [blame] | 157 | BI = BB->begin(); // Rescan basic block. BI might be invalidated. |
Chris Lattner | 3c01937 | 2002-05-10 15:29:25 +0000 | [diff] [blame] | 158 | ++NumExprTreesConv; |
Chris Lattner | d554380 | 2001-12-14 16:37:52 +0000 | [diff] [blame] | 159 | return true; |
| 160 | } |
| 161 | |
Chris Lattner | d20a98e | 2002-05-24 20:41:51 +0000 | [diff] [blame] | 162 | // Check to see if we can convert the users of the cast value to match the |
| 163 | // source type of the cast... |
Chris Lattner | d554380 | 2001-12-14 16:37:52 +0000 | [diff] [blame] | 164 | // |
| 165 | ConvertedTypes.clear(); |
Chris Lattner | 61b92c0 | 2002-10-08 22:19:25 +0000 | [diff] [blame] | 166 | // Make sure the source doesn't change type |
| 167 | ConvertedTypes[Src] = Src->getType(); |
Misha Brukman | f117cc9 | 2003-05-20 18:45:36 +0000 | [diff] [blame] | 168 | if (ValueConvertibleToType(CI, Src->getType(), ConvertedTypes, TD)) { |
Chris Lattner | 5e2e272 | 2004-08-08 01:27:56 +0000 | [diff] [blame] | 169 | //PRINT_PEEPHOLE3("CAST-DEST-EXPR-CONV:in ", *Src, *CI, |
| 170 | // *BB->getParent()); |
Chris Lattner | d554380 | 2001-12-14 16:37:52 +0000 | [diff] [blame] | 171 | |
Chris Lattner | 6806f56 | 2003-08-01 22:15:03 +0000 | [diff] [blame] | 172 | DEBUG(std::cerr << "\nCONVERTING EXPR TYPE:\n"); |
Chris Lattner | b1b4262 | 2002-07-17 17:11:33 +0000 | [diff] [blame] | 173 | { // ValueMap must be destroyed before function verified! |
| 174 | ValueMapCache ValueMap; |
Chris Lattner | 16125fb | 2003-04-24 18:25:27 +0000 | [diff] [blame] | 175 | ConvertValueToNewType(CI, Src, ValueMap, TD); // This will delete CI! |
Chris Lattner | b1b4262 | 2002-07-17 17:11:33 +0000 | [diff] [blame] | 176 | } |
Chris Lattner | d554380 | 2001-12-14 16:37:52 +0000 | [diff] [blame] | 177 | |
Chris Lattner | 30b4344 | 2004-07-15 02:06:12 +0000 | [diff] [blame] | 178 | PRINT_PEEPHOLE1("CAST-DEST-EXPR-CONV:out", *Src); |
| 179 | DEBUG(std::cerr << "DONE CONVERTING EXPR TYPE: \n\n" << |
| 180 | *BB->getParent()); |
Chris Lattner | 3378a5b | 2002-07-16 23:49:24 +0000 | [diff] [blame] | 181 | |
Chris Lattner | b1b4262 | 2002-07-17 17:11:33 +0000 | [diff] [blame] | 182 | BI = BB->begin(); // Rescan basic block. BI might be invalidated. |
Chris Lattner | 3c01937 | 2002-05-10 15:29:25 +0000 | [diff] [blame] | 183 | ++NumExprTreesConv; |
Chris Lattner | a8b6d43 | 2001-12-05 06:34:00 +0000 | [diff] [blame] | 184 | return true; |
Chris Lattner | f3b976e | 2001-11-04 20:21:12 +0000 | [diff] [blame] | 185 | } |
Chris Lattner | f17a09d | 2001-12-06 18:06:13 +0000 | [diff] [blame] | 186 | } |
| 187 | |
Chris Lattner | e99c66b | 2001-11-01 17:05:27 +0000 | [diff] [blame] | 188 | // Check to see if we are casting from a structure pointer to a pointer to |
| 189 | // the first element of the structure... to avoid munching other peepholes, |
| 190 | // we only let this happen if there are no add uses of the cast. |
| 191 | // |
| 192 | // Peephole optimize the following instructions: |
| 193 | // %t1 = cast {<...>} * %StructPtr to <ty> * |
| 194 | // |
| 195 | // Into: %t2 = getelementptr {<...>} * %StructPtr, <0, 0, 0, ...> |
| 196 | // %t1 = cast <eltype> * %t1 to <ty> * |
| 197 | // |
Chris Lattner | 3cc7dde | 2001-11-26 16:58:14 +0000 | [diff] [blame] | 198 | if (const CompositeType *CTy = getPointedToComposite(Src->getType())) |
Chris Lattner | e99c66b | 2001-11-01 17:05:27 +0000 | [diff] [blame] | 199 | if (const PointerType *DestPTy = dyn_cast<PointerType>(DestTy)) { |
| 200 | |
| 201 | // Loop over uses of the cast, checking for add instructions. If an add |
| 202 | // exists, this is probably a part of a more complex GEP, so we don't |
| 203 | // want to mess around with the cast. |
| 204 | // |
| 205 | bool HasAddUse = false; |
| 206 | for (Value::use_iterator I = CI->use_begin(), E = CI->use_end(); |
| 207 | I != E; ++I) |
| 208 | if (isa<Instruction>(*I) && |
| 209 | cast<Instruction>(*I)->getOpcode() == Instruction::Add) { |
| 210 | HasAddUse = true; break; |
| 211 | } |
| 212 | |
| 213 | // If it doesn't have an add use, check to see if the dest type is |
Misha Brukman | f117cc9 | 2003-05-20 18:45:36 +0000 | [diff] [blame] | 214 | // losslessly convertible to one of the types in the start of the struct |
Chris Lattner | e99c66b | 2001-11-01 17:05:27 +0000 | [diff] [blame] | 215 | // type. |
| 216 | // |
| 217 | if (!HasAddUse) { |
Chris Lattner | 7a17675 | 2001-12-04 00:03:30 +0000 | [diff] [blame] | 218 | const Type *DestPointedTy = DestPTy->getElementType(); |
Chris Lattner | e99c66b | 2001-11-01 17:05:27 +0000 | [diff] [blame] | 219 | unsigned Depth = 1; |
Chris Lattner | 3cc7dde | 2001-11-26 16:58:14 +0000 | [diff] [blame] | 220 | const CompositeType *CurCTy = CTy; |
Chris Lattner | e99c66b | 2001-11-01 17:05:27 +0000 | [diff] [blame] | 221 | const Type *ElTy = 0; |
Chris Lattner | 3cc7dde | 2001-11-26 16:58:14 +0000 | [diff] [blame] | 222 | |
| 223 | // Build the index vector, full of all zeros |
Chris Lattner | 697954c | 2002-01-20 22:54:45 +0000 | [diff] [blame] | 224 | std::vector<Value*> Indices; |
Chris Lattner | 559d519 | 2004-01-09 05:53:38 +0000 | [diff] [blame] | 225 | |
Chris Lattner | 28977af | 2004-04-05 01:30:19 +0000 | [diff] [blame] | 226 | Indices.push_back(Constant::getNullValue(Type::UIntTy)); |
Chris Lattner | d554380 | 2001-12-14 16:37:52 +0000 | [diff] [blame] | 227 | while (CurCTy && !isa<PointerType>(CurCTy)) { |
Chris Lattner | 3cc7dde | 2001-11-26 16:58:14 +0000 | [diff] [blame] | 228 | if (const StructType *CurSTy = dyn_cast<StructType>(CurCTy)) { |
| 229 | // Check for a zero element struct type... if we have one, bail. |
Chris Lattner | d21cd80 | 2004-02-09 04:37:31 +0000 | [diff] [blame] | 230 | if (CurSTy->getNumElements() == 0) break; |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 231 | |
Chris Lattner | 3cc7dde | 2001-11-26 16:58:14 +0000 | [diff] [blame] | 232 | // Grab the first element of the struct type, which must lie at |
| 233 | // offset zero in the struct. |
| 234 | // |
Chris Lattner | d21cd80 | 2004-02-09 04:37:31 +0000 | [diff] [blame] | 235 | ElTy = CurSTy->getElementType(0); |
Chris Lattner | 3cc7dde | 2001-11-26 16:58:14 +0000 | [diff] [blame] | 236 | } else { |
Chris Lattner | 7d719c3 | 2005-01-19 16:16:35 +0000 | [diff] [blame] | 237 | ElTy = cast<SequentialType>(CurCTy)->getElementType(); |
Chris Lattner | 3cc7dde | 2001-11-26 16:58:14 +0000 | [diff] [blame] | 238 | } |
| 239 | |
| 240 | // Insert a zero to index through this type... |
Chris Lattner | 28977af | 2004-04-05 01:30:19 +0000 | [diff] [blame] | 241 | Indices.push_back(Constant::getNullValue(Type::UIntTy)); |
Chris Lattner | e99c66b | 2001-11-01 17:05:27 +0000 | [diff] [blame] | 242 | |
| 243 | // Did we find what we're looking for? |
Misha Brukman | f117cc9 | 2003-05-20 18:45:36 +0000 | [diff] [blame] | 244 | if (ElTy->isLosslesslyConvertibleTo(DestPointedTy)) break; |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 245 | |
Chris Lattner | e99c66b | 2001-11-01 17:05:27 +0000 | [diff] [blame] | 246 | // Nope, go a level deeper. |
| 247 | ++Depth; |
Chris Lattner | 3cc7dde | 2001-11-26 16:58:14 +0000 | [diff] [blame] | 248 | CurCTy = dyn_cast<CompositeType>(ElTy); |
Chris Lattner | e99c66b | 2001-11-01 17:05:27 +0000 | [diff] [blame] | 249 | ElTy = 0; |
| 250 | } |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 251 | |
Chris Lattner | e99c66b | 2001-11-01 17:05:27 +0000 | [diff] [blame] | 252 | // Did we find what we were looking for? If so, do the transformation |
| 253 | if (ElTy) { |
Chris Lattner | 30b4344 | 2004-07-15 02:06:12 +0000 | [diff] [blame] | 254 | PRINT_PEEPHOLE1("cast-for-first:in", *CI); |
Chris Lattner | e99c66b | 2001-11-01 17:05:27 +0000 | [diff] [blame] | 255 | |
Chris Lattner | 2a7c23e | 2002-09-10 17:04:02 +0000 | [diff] [blame] | 256 | std::string Name = CI->getName(); CI->setName(""); |
| 257 | |
Chris Lattner | e99c66b | 2001-11-01 17:05:27 +0000 | [diff] [blame] | 258 | // Insert the new T cast instruction... stealing old T's name |
| 259 | GetElementPtrInst *GEP = new GetElementPtrInst(Src, Indices, |
Chris Lattner | 2a7c23e | 2002-09-10 17:04:02 +0000 | [diff] [blame] | 260 | Name, BI); |
Chris Lattner | e99c66b | 2001-11-01 17:05:27 +0000 | [diff] [blame] | 261 | |
| 262 | // Make the old cast instruction reference the new GEP instead of |
| 263 | // the old src value. |
| 264 | // |
| 265 | CI->setOperand(0, GEP); |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 266 | |
Chris Lattner | 30b4344 | 2004-07-15 02:06:12 +0000 | [diff] [blame] | 267 | PRINT_PEEPHOLE2("cast-for-first:out", *GEP, *CI); |
Chris Lattner | 3c01937 | 2002-05-10 15:29:25 +0000 | [diff] [blame] | 268 | ++NumGEPInstFormed; |
Chris Lattner | e99c66b | 2001-11-01 17:05:27 +0000 | [diff] [blame] | 269 | return true; |
| 270 | } |
| 271 | } |
| 272 | } |
Chris Lattner | e99c66b | 2001-11-01 17:05:27 +0000 | [diff] [blame] | 273 | |
Chris Lattner | 8d38e54 | 2001-11-01 03:12:34 +0000 | [diff] [blame] | 274 | } else if (StoreInst *SI = dyn_cast<StoreInst>(I)) { |
| 275 | Value *Val = SI->getOperand(0); |
Chris Lattner | 65ea171 | 2001-11-14 11:27:58 +0000 | [diff] [blame] | 276 | Value *Pointer = SI->getPointerOperand(); |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 277 | |
Chris Lattner | dedee7b | 2001-11-01 05:57:59 +0000 | [diff] [blame] | 278 | // Peephole optimize the following instructions: |
Misha Brukman | f117cc9 | 2003-05-20 18:45:36 +0000 | [diff] [blame] | 279 | // %t = cast <T1>* %P to <T2> * ;; If T1 is losslessly convertible to T2 |
Chris Lattner | dedee7b | 2001-11-01 05:57:59 +0000 | [diff] [blame] | 280 | // store <T2> %V, <T2>* %t |
| 281 | // |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 282 | // Into: |
Chris Lattner | dedee7b | 2001-11-01 05:57:59 +0000 | [diff] [blame] | 283 | // %t = cast <T2> %V to <T1> |
| 284 | // store <T1> %t2, <T1>* %P |
| 285 | // |
Chris Lattner | d554380 | 2001-12-14 16:37:52 +0000 | [diff] [blame] | 286 | // Note: This is not taken care of by expr conversion because there might |
| 287 | // not be a cast available for the store to convert the incoming value of. |
| 288 | // This code is basically here to make sure that pointers don't have casts |
| 289 | // if possible. |
| 290 | // |
Chris Lattner | dedee7b | 2001-11-01 05:57:59 +0000 | [diff] [blame] | 291 | if (CastInst *CI = dyn_cast<CastInst>(Pointer)) |
| 292 | if (Value *CastSrc = CI->getOperand(0)) // CSPT = CastSrcPointerType |
Chris Lattner | 7e70829 | 2002-06-25 16:13:24 +0000 | [diff] [blame] | 293 | if (const PointerType *CSPT = dyn_cast<PointerType>(CastSrc->getType())) |
Misha Brukman | f117cc9 | 2003-05-20 18:45:36 +0000 | [diff] [blame] | 294 | // convertible types? |
| 295 | if (Val->getType()->isLosslesslyConvertibleTo(CSPT->getElementType())) { |
Chris Lattner | 30b4344 | 2004-07-15 02:06:12 +0000 | [diff] [blame] | 296 | PRINT_PEEPHOLE3("st-src-cast:in ", *Pointer, *Val, *SI); |
Chris Lattner | dedee7b | 2001-11-01 05:57:59 +0000 | [diff] [blame] | 297 | |
| 298 | // Insert the new T cast instruction... stealing old T's name |
Chris Lattner | 2a7c23e | 2002-09-10 17:04:02 +0000 | [diff] [blame] | 299 | std::string Name(CI->getName()); CI->setName(""); |
Chris Lattner | 7a17675 | 2001-12-04 00:03:30 +0000 | [diff] [blame] | 300 | CastInst *NCI = new CastInst(Val, CSPT->getElementType(), |
Chris Lattner | 2a7c23e | 2002-09-10 17:04:02 +0000 | [diff] [blame] | 301 | Name, BI); |
Chris Lattner | dedee7b | 2001-11-01 05:57:59 +0000 | [diff] [blame] | 302 | |
| 303 | // Replace the old store with a new one! |
| 304 | ReplaceInstWithInst(BB->getInstList(), BI, |
| 305 | SI = new StoreInst(NCI, CastSrc)); |
Chris Lattner | 30b4344 | 2004-07-15 02:06:12 +0000 | [diff] [blame] | 306 | PRINT_PEEPHOLE3("st-src-cast:out", *NCI, *CastSrc, *SI); |
Chris Lattner | 3c01937 | 2002-05-10 15:29:25 +0000 | [diff] [blame] | 307 | ++NumLoadStorePeepholes; |
Chris Lattner | dedee7b | 2001-11-01 05:57:59 +0000 | [diff] [blame] | 308 | return true; |
| 309 | } |
| 310 | |
Chris Lattner | c99428f | 2002-05-14 05:23:45 +0000 | [diff] [blame] | 311 | } else if (LoadInst *LI = dyn_cast<LoadInst>(I)) { |
| 312 | Value *Pointer = LI->getOperand(0); |
| 313 | const Type *PtrElType = |
| 314 | cast<PointerType>(Pointer->getType())->getElementType(); |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 315 | |
Chris Lattner | c99428f | 2002-05-14 05:23:45 +0000 | [diff] [blame] | 316 | // Peephole optimize the following instructions: |
Misha Brukman | f117cc9 | 2003-05-20 18:45:36 +0000 | [diff] [blame] | 317 | // %Val = cast <T1>* to <T2>* ;; If T1 is losslessly convertible to T2 |
Chris Lattner | c99428f | 2002-05-14 05:23:45 +0000 | [diff] [blame] | 318 | // %t = load <T2>* %P |
| 319 | // |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 320 | // Into: |
Chris Lattner | c99428f | 2002-05-14 05:23:45 +0000 | [diff] [blame] | 321 | // %t = load <T1>* %P |
| 322 | // %Val = cast <T1> to <T2> |
| 323 | // |
| 324 | // Note: This is not taken care of by expr conversion because there might |
| 325 | // not be a cast available for the store to convert the incoming value of. |
| 326 | // This code is basically here to make sure that pointers don't have casts |
| 327 | // if possible. |
| 328 | // |
| 329 | if (CastInst *CI = dyn_cast<CastInst>(Pointer)) |
| 330 | if (Value *CastSrc = CI->getOperand(0)) // CSPT = CastSrcPointerType |
Chris Lattner | 7e70829 | 2002-06-25 16:13:24 +0000 | [diff] [blame] | 331 | if (const PointerType *CSPT = dyn_cast<PointerType>(CastSrc->getType())) |
Misha Brukman | f117cc9 | 2003-05-20 18:45:36 +0000 | [diff] [blame] | 332 | // convertible types? |
| 333 | if (PtrElType->isLosslesslyConvertibleTo(CSPT->getElementType())) { |
Chris Lattner | 30b4344 | 2004-07-15 02:06:12 +0000 | [diff] [blame] | 334 | PRINT_PEEPHOLE2("load-src-cast:in ", *Pointer, *LI); |
Chris Lattner | c99428f | 2002-05-14 05:23:45 +0000 | [diff] [blame] | 335 | |
| 336 | // Create the new load instruction... loading the pre-casted value |
Chris Lattner | 2a7c23e | 2002-09-10 17:04:02 +0000 | [diff] [blame] | 337 | LoadInst *NewLI = new LoadInst(CastSrc, LI->getName(), BI); |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 338 | |
Chris Lattner | c99428f | 2002-05-14 05:23:45 +0000 | [diff] [blame] | 339 | // Insert the new T cast instruction... stealing old T's name |
| 340 | CastInst *NCI = new CastInst(NewLI, LI->getType(), CI->getName()); |
Chris Lattner | c99428f | 2002-05-14 05:23:45 +0000 | [diff] [blame] | 341 | |
| 342 | // Replace the old store with a new one! |
| 343 | ReplaceInstWithInst(BB->getInstList(), BI, NCI); |
Chris Lattner | 30b4344 | 2004-07-15 02:06:12 +0000 | [diff] [blame] | 344 | PRINT_PEEPHOLE3("load-src-cast:out", *NCI, *CastSrc, *NewLI); |
Chris Lattner | c99428f | 2002-05-14 05:23:45 +0000 | [diff] [blame] | 345 | ++NumLoadStorePeepholes; |
| 346 | return true; |
| 347 | } |
| 348 | |
Chris Lattner | 61b92c0 | 2002-10-08 22:19:25 +0000 | [diff] [blame] | 349 | } else if (CallInst *CI = dyn_cast<CallInst>(I)) { |
| 350 | // If we have a call with all varargs arguments, convert the call to use the |
| 351 | // actual argument types present... |
| 352 | // |
| 353 | const PointerType *PTy = cast<PointerType>(CI->getCalledValue()->getType()); |
| 354 | const FunctionType *FTy = cast<FunctionType>(PTy->getElementType()); |
| 355 | |
| 356 | // Is the call to a vararg variable with no real parameters? |
Chris Lattner | cdeb81d | 2003-05-01 21:02:53 +0000 | [diff] [blame] | 357 | if (FTy->isVarArg() && FTy->getNumParams() == 0 && |
| 358 | !CI->getCalledFunction()) { |
Chris Lattner | 61b92c0 | 2002-10-08 22:19:25 +0000 | [diff] [blame] | 359 | // If so, insert a new cast instruction, casting it to a function type |
| 360 | // that matches the current arguments... |
| 361 | // |
| 362 | std::vector<const Type *> Params; // Parameter types... |
| 363 | for (unsigned i = 1, e = CI->getNumOperands(); i != e; ++i) |
| 364 | Params.push_back(CI->getOperand(i)->getType()); |
| 365 | |
| 366 | FunctionType *NewFT = FunctionType::get(FTy->getReturnType(), |
| 367 | Params, false); |
| 368 | PointerType *NewPFunTy = PointerType::get(NewFT); |
| 369 | |
| 370 | // Create a new cast, inserting it right before the function call... |
Chris Lattner | 9554928 | 2003-04-28 01:25:38 +0000 | [diff] [blame] | 371 | Value *NewCast; |
| 372 | Constant *ConstantCallSrc = 0; |
| 373 | if (Constant *CS = dyn_cast<Constant>(CI->getCalledValue())) |
| 374 | ConstantCallSrc = CS; |
Chris Lattner | 9554928 | 2003-04-28 01:25:38 +0000 | [diff] [blame] | 375 | |
| 376 | if (ConstantCallSrc) |
| 377 | NewCast = ConstantExpr::getCast(ConstantCallSrc, NewPFunTy); |
| 378 | else |
| 379 | NewCast = new CastInst(CI->getCalledValue(), NewPFunTy, |
| 380 | CI->getCalledValue()->getName()+"_c",CI); |
Chris Lattner | 61b92c0 | 2002-10-08 22:19:25 +0000 | [diff] [blame] | 381 | |
| 382 | // Create a new call instruction... |
| 383 | CallInst *NewCall = new CallInst(NewCast, |
| 384 | std::vector<Value*>(CI->op_begin()+1, CI->op_end())); |
Chris Lattner | 65af1ab | 2005-05-14 12:28:32 +0000 | [diff] [blame] | 385 | if (CI->isTailCall()) NewCall->setTailCall(); |
| 386 | NewCall->setCallingConv(CI->getCallingConv()); |
Chris Lattner | 61b92c0 | 2002-10-08 22:19:25 +0000 | [diff] [blame] | 387 | ++BI; |
| 388 | ReplaceInstWithInst(CI, NewCall); |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 389 | |
Chris Lattner | 61b92c0 | 2002-10-08 22:19:25 +0000 | [diff] [blame] | 390 | ++NumVarargCallChanges; |
| 391 | return true; |
| 392 | } |
| 393 | |
Chris Lattner | d32a961 | 2001-11-01 02:42:08 +0000 | [diff] [blame] | 394 | } |
| 395 | |
| 396 | return false; |
| 397 | } |
| 398 | |
| 399 | |
| 400 | |
| 401 | |
Chris Lattner | 16125fb | 2003-04-24 18:25:27 +0000 | [diff] [blame] | 402 | bool RPR::DoRaisePass(Function &F) { |
Chris Lattner | d32a961 | 2001-11-01 02:42:08 +0000 | [diff] [blame] | 403 | bool Changed = false; |
Chris Lattner | 7e70829 | 2002-06-25 16:13:24 +0000 | [diff] [blame] | 404 | for (Function::iterator BB = F.begin(), BBE = F.end(); BB != BBE; ++BB) |
Chris Lattner | d32a961 | 2001-11-01 02:42:08 +0000 | [diff] [blame] | 405 | for (BasicBlock::iterator BI = BB->begin(); BI != BB->end();) { |
Brian Gaeke | a9160a0 | 2004-07-01 19:27:10 +0000 | [diff] [blame] | 406 | DEBUG(std::cerr << "LevelRaising: " << *BI); |
Misha Brukman | 82c89b9 | 2003-05-20 21:01:22 +0000 | [diff] [blame] | 407 | if (dceInstruction(BI) || doConstantPropagation(BI)) { |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 408 | Changed = true; |
Chris Lattner | 3c01937 | 2002-05-10 15:29:25 +0000 | [diff] [blame] | 409 | ++NumDCEorCP; |
Chris Lattner | 6806f56 | 2003-08-01 22:15:03 +0000 | [diff] [blame] | 410 | DEBUG(std::cerr << "***\t\t^^-- Dead code eliminated!\n"); |
Chris Lattner | 7e70829 | 2002-06-25 16:13:24 +0000 | [diff] [blame] | 411 | } else if (PeepholeOptimize(BB, BI)) { |
Chris Lattner | d32a961 | 2001-11-01 02:42:08 +0000 | [diff] [blame] | 412 | Changed = true; |
Chris Lattner | 7e70829 | 2002-06-25 16:13:24 +0000 | [diff] [blame] | 413 | } else { |
Chris Lattner | d32a961 | 2001-11-01 02:42:08 +0000 | [diff] [blame] | 414 | ++BI; |
Chris Lattner | 7e70829 | 2002-06-25 16:13:24 +0000 | [diff] [blame] | 415 | } |
Chris Lattner | d32a961 | 2001-11-01 02:42:08 +0000 | [diff] [blame] | 416 | } |
Chris Lattner | 7e70829 | 2002-06-25 16:13:24 +0000 | [diff] [blame] | 417 | |
Chris Lattner | d32a961 | 2001-11-01 02:42:08 +0000 | [diff] [blame] | 418 | return Changed; |
| 419 | } |
| 420 | |
| 421 | |
Chris Lattner | 16125fb | 2003-04-24 18:25:27 +0000 | [diff] [blame] | 422 | // runOnFunction - Raise a function representation to a higher level. |
| 423 | bool RPR::runOnFunction(Function &F) { |
Chris Lattner | 6806f56 | 2003-08-01 22:15:03 +0000 | [diff] [blame] | 424 | DEBUG(std::cerr << "\n\n\nStarting to work on Function '" << F.getName() |
| 425 | << "'\n"); |
Chris Lattner | 68b07b7 | 2001-11-01 07:00:51 +0000 | [diff] [blame] | 426 | |
Chris Lattner | 3cc7dde | 2001-11-26 16:58:14 +0000 | [diff] [blame] | 427 | // Insert casts for all incoming pointer pointer values that are treated as |
| 428 | // arrays... |
Chris Lattner | d32a961 | 2001-11-01 02:42:08 +0000 | [diff] [blame] | 429 | // |
Chris Lattner | 3cc7dde | 2001-11-26 16:58:14 +0000 | [diff] [blame] | 430 | bool Changed = false, LocalChange; |
Chris Lattner | 3378a5b | 2002-07-16 23:49:24 +0000 | [diff] [blame] | 431 | |
| 432 | // If the StartInst option was specified, then Peephole optimize that |
| 433 | // instruction first if it occurs in this function. |
| 434 | // |
| 435 | if (!StartInst.empty()) { |
| 436 | for (Function::iterator BB = F.begin(), BBE = F.end(); BB != BBE; ++BB) |
| 437 | for (BasicBlock::iterator BI = BB->begin(); BI != BB->end(); ++BI) |
| 438 | if (BI->getName() == StartInst) { |
| 439 | bool SavedDebug = DebugFlag; // Save the DEBUG() controlling flag. |
| 440 | DebugFlag = true; // Turn on DEBUG's |
| 441 | Changed |= PeepholeOptimize(BB, BI); |
| 442 | DebugFlag = SavedDebug; // Restore DebugFlag to previous state |
| 443 | } |
| 444 | } |
| 445 | |
Chris Lattner | 4b770a3 | 2001-12-04 08:12:53 +0000 | [diff] [blame] | 446 | do { |
Chris Lattner | 6806f56 | 2003-08-01 22:15:03 +0000 | [diff] [blame] | 447 | DEBUG(std::cerr << "Looping: \n" << F); |
Chris Lattner | a8b6d43 | 2001-12-05 06:34:00 +0000 | [diff] [blame] | 448 | |
Chris Lattner | f57b845 | 2002-04-27 06:56:12 +0000 | [diff] [blame] | 449 | // Iterate over the function, refining it, until it converges on a stable |
Chris Lattner | 3cc7dde | 2001-11-26 16:58:14 +0000 | [diff] [blame] | 450 | // state |
Chris Lattner | d554380 | 2001-12-14 16:37:52 +0000 | [diff] [blame] | 451 | LocalChange = false; |
Chris Lattner | 2fbfdcf | 2002-04-07 20:49:59 +0000 | [diff] [blame] | 452 | while (DoRaisePass(F)) LocalChange = true; |
Chris Lattner | 3cc7dde | 2001-11-26 16:58:14 +0000 | [diff] [blame] | 453 | Changed |= LocalChange; |
| 454 | |
| 455 | } while (LocalChange); |
Chris Lattner | d32a961 | 2001-11-01 02:42:08 +0000 | [diff] [blame] | 456 | |
| 457 | return Changed; |
| 458 | } |
Brian Gaeke | d0fde30 | 2003-11-11 22:41:34 +0000 | [diff] [blame] | 459 | |