Chris Lattner | 65e96e5 | 2002-05-07 19:04:39 +0000 | [diff] [blame] | 1 | //===- RaiseAllocations.cpp - Convert %malloc & %free calls to insts ------===// |
John Criswell | b576c94 | 2003-10-20 19:43:21 +0000 | [diff] [blame] | 2 | // |
| 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. |
| 7 | // |
| 8 | //===----------------------------------------------------------------------===// |
Chris Lattner | ade686e | 2002-05-07 19:02:48 +0000 | [diff] [blame] | 9 | // |
Chris Lattner | 65e96e5 | 2002-05-07 19:04:39 +0000 | [diff] [blame] | 10 | // This file defines the RaiseAllocations pass which convert malloc and free |
| 11 | // calls to malloc and free instructions. |
Chris Lattner | ade686e | 2002-05-07 19:02:48 +0000 | [diff] [blame] | 12 | // |
| 13 | //===----------------------------------------------------------------------===// |
| 14 | |
Chris Lattner | 2dbfa03 | 2003-09-01 03:14:56 +0000 | [diff] [blame] | 15 | #include "llvm/Transforms/IPO.h" |
Chris Lattner | eb12cd6 | 2003-12-07 01:42:08 +0000 | [diff] [blame] | 16 | #include "llvm/Constants.h" |
Chris Lattner | ade686e | 2002-05-07 19:02:48 +0000 | [diff] [blame] | 17 | #include "llvm/DerivedTypes.h" |
Chris Lattner | eb12cd6 | 2003-12-07 01:42:08 +0000 | [diff] [blame] | 18 | #include "llvm/Module.h" |
Misha Brukman | 47b14a4 | 2004-07-29 17:30:56 +0000 | [diff] [blame] | 19 | #include "llvm/Instructions.h" |
Chris Lattner | ade686e | 2002-05-07 19:02:48 +0000 | [diff] [blame] | 20 | #include "llvm/Pass.h" |
Chris Lattner | 2dbfa03 | 2003-09-01 03:14:56 +0000 | [diff] [blame] | 21 | #include "llvm/Support/CallSite.h" |
Reid Spencer | 551ccae | 2004-09-01 22:55:40 +0000 | [diff] [blame] | 22 | #include "llvm/ADT/Statistic.h" |
Chris Lattner | 1e2385b | 2003-11-21 21:54:22 +0000 | [diff] [blame] | 23 | using namespace llvm; |
Brian Gaeke | d0fde30 | 2003-11-11 22:41:34 +0000 | [diff] [blame] | 24 | |
Chris Lattner | ade686e | 2002-05-07 19:02:48 +0000 | [diff] [blame] | 25 | namespace { |
Chris Lattner | a92f696 | 2002-10-01 22:38:41 +0000 | [diff] [blame] | 26 | Statistic<> NumRaised("raiseallocs", "Number of allocations raised"); |
Chris Lattner | ade686e | 2002-05-07 19:02:48 +0000 | [diff] [blame] | 27 | |
Chris Lattner | a92f696 | 2002-10-01 22:38:41 +0000 | [diff] [blame] | 28 | // RaiseAllocations - Turn %malloc and %free calls into the appropriate |
| 29 | // instruction. |
Chris Lattner | ade686e | 2002-05-07 19:02:48 +0000 | [diff] [blame] | 30 | // |
Chris Lattner | b12914b | 2004-09-20 04:48:05 +0000 | [diff] [blame] | 31 | class RaiseAllocations : public ModulePass { |
Chris Lattner | a92f696 | 2002-10-01 22:38:41 +0000 | [diff] [blame] | 32 | Function *MallocFunc; // Functions in the module we are processing |
| 33 | Function *FreeFunc; // Initialized by doPassInitializationVirt |
| 34 | public: |
| 35 | RaiseAllocations() : MallocFunc(0), FreeFunc(0) {} |
| 36 | |
| 37 | // doPassInitialization - For the raise allocations pass, this finds a |
| 38 | // declaration for malloc and free if they exist. |
| 39 | // |
Chris Lattner | 2dbfa03 | 2003-09-01 03:14:56 +0000 | [diff] [blame] | 40 | void doInitialization(Module &M); |
Chris Lattner | a92f696 | 2002-10-01 22:38:41 +0000 | [diff] [blame] | 41 | |
Chris Lattner | 2dbfa03 | 2003-09-01 03:14:56 +0000 | [diff] [blame] | 42 | // run - This method does the actual work of converting instructions over. |
Chris Lattner | a92f696 | 2002-10-01 22:38:41 +0000 | [diff] [blame] | 43 | // |
Chris Lattner | b12914b | 2004-09-20 04:48:05 +0000 | [diff] [blame] | 44 | bool runOnModule(Module &M); |
Chris Lattner | a92f696 | 2002-10-01 22:38:41 +0000 | [diff] [blame] | 45 | }; |
| 46 | |
Chris Lattner | a6275cc | 2002-07-26 21:12:46 +0000 | [diff] [blame] | 47 | RegisterOpt<RaiseAllocations> |
| 48 | X("raiseallocs", "Raise allocations from calls to instructions"); |
Chris Lattner | ade686e | 2002-05-07 19:02:48 +0000 | [diff] [blame] | 49 | } // end anonymous namespace |
| 50 | |
| 51 | |
| 52 | // createRaiseAllocationsPass - The interface to this file... |
Chris Lattner | b12914b | 2004-09-20 04:48:05 +0000 | [diff] [blame] | 53 | ModulePass *llvm::createRaiseAllocationsPass() { |
Chris Lattner | ade686e | 2002-05-07 19:02:48 +0000 | [diff] [blame] | 54 | return new RaiseAllocations(); |
| 55 | } |
| 56 | |
| 57 | |
Chris Lattner | 2dbfa03 | 2003-09-01 03:14:56 +0000 | [diff] [blame] | 58 | // If the module has a symbol table, they might be referring to the malloc and |
| 59 | // free functions. If this is the case, grab the method pointers that the |
| 60 | // module is using. |
| 61 | // |
| 62 | // Lookup %malloc and %free in the symbol table, for later use. If they don't |
| 63 | // exist, or are not external, we do not worry about converting calls to that |
| 64 | // function into the appropriate instruction. |
| 65 | // |
| 66 | void RaiseAllocations::doInitialization(Module &M) { |
Chris Lattner | ade686e | 2002-05-07 19:02:48 +0000 | [diff] [blame] | 67 | const FunctionType *MallocType = // Get the type for malloc |
| 68 | FunctionType::get(PointerType::get(Type::SByteTy), |
Chris Lattner | 0b5909e | 2002-07-18 00:18:01 +0000 | [diff] [blame] | 69 | std::vector<const Type*>(1, Type::ULongTy), false); |
Chris Lattner | ade686e | 2002-05-07 19:02:48 +0000 | [diff] [blame] | 70 | |
| 71 | const FunctionType *FreeType = // Get the type for free |
| 72 | FunctionType::get(Type::VoidTy, |
| 73 | std::vector<const Type*>(1, PointerType::get(Type::SByteTy)), |
| 74 | false); |
| 75 | |
Chris Lattner | 0b5909e | 2002-07-18 00:18:01 +0000 | [diff] [blame] | 76 | // Get Malloc and free prototypes if they exist! |
Chris Lattner | 7e70829 | 2002-06-25 16:13:24 +0000 | [diff] [blame] | 77 | MallocFunc = M.getFunction("malloc", MallocType); |
| 78 | FreeFunc = M.getFunction("free" , FreeType); |
Chris Lattner | ade686e | 2002-05-07 19:02:48 +0000 | [diff] [blame] | 79 | |
Chris Lattner | 0b5909e | 2002-07-18 00:18:01 +0000 | [diff] [blame] | 80 | // Check to see if the prototype is wrong, giving us sbyte*(uint) * malloc |
| 81 | // This handles the common declaration of: 'void *malloc(unsigned);' |
| 82 | if (MallocFunc == 0) { |
| 83 | MallocType = FunctionType::get(PointerType::get(Type::SByteTy), |
| 84 | std::vector<const Type*>(1, Type::UIntTy), false); |
| 85 | MallocFunc = M.getFunction("malloc", MallocType); |
| 86 | } |
| 87 | |
Chris Lattner | 47e0f3a | 2002-05-24 20:29:18 +0000 | [diff] [blame] | 88 | // Check to see if the prototype is missing, giving us sbyte*(...) * malloc |
Chris Lattner | 0b5909e | 2002-07-18 00:18:01 +0000 | [diff] [blame] | 89 | // This handles the common declaration of: 'void *malloc();' |
Chris Lattner | 47e0f3a | 2002-05-24 20:29:18 +0000 | [diff] [blame] | 90 | if (MallocFunc == 0) { |
| 91 | MallocType = FunctionType::get(PointerType::get(Type::SByteTy), |
| 92 | std::vector<const Type*>(), true); |
Chris Lattner | 7e70829 | 2002-06-25 16:13:24 +0000 | [diff] [blame] | 93 | MallocFunc = M.getFunction("malloc", MallocType); |
Chris Lattner | 47e0f3a | 2002-05-24 20:29:18 +0000 | [diff] [blame] | 94 | } |
| 95 | |
| 96 | // Check to see if the prototype was forgotten, giving us void (...) * free |
| 97 | // This handles the common forward declaration of: 'void free();' |
| 98 | if (FreeFunc == 0) { |
| 99 | FreeType = FunctionType::get(Type::VoidTy, std::vector<const Type*>(),true); |
Chris Lattner | 7e70829 | 2002-06-25 16:13:24 +0000 | [diff] [blame] | 100 | FreeFunc = M.getFunction("free", FreeType); |
Chris Lattner | 47e0f3a | 2002-05-24 20:29:18 +0000 | [diff] [blame] | 101 | } |
| 102 | |
Chris Lattner | 1f28e8c | 2003-08-11 15:05:08 +0000 | [diff] [blame] | 103 | // One last try, check to see if we can find free as 'int (...)* free'. This |
| 104 | // handles the case where NOTHING was declared. |
| 105 | if (FreeFunc == 0) { |
| 106 | FreeType = FunctionType::get(Type::IntTy, std::vector<const Type*>(),true); |
| 107 | FreeFunc = M.getFunction("free", FreeType); |
| 108 | } |
| 109 | |
Chris Lattner | ade686e | 2002-05-07 19:02:48 +0000 | [diff] [blame] | 110 | // Don't mess with locally defined versions of these functions... |
| 111 | if (MallocFunc && !MallocFunc->isExternal()) MallocFunc = 0; |
| 112 | if (FreeFunc && !FreeFunc->isExternal()) FreeFunc = 0; |
Chris Lattner | ade686e | 2002-05-07 19:02:48 +0000 | [diff] [blame] | 113 | } |
| 114 | |
Chris Lattner | 2dbfa03 | 2003-09-01 03:14:56 +0000 | [diff] [blame] | 115 | // run - Transform calls into instructions... |
Chris Lattner | ade686e | 2002-05-07 19:02:48 +0000 | [diff] [blame] | 116 | // |
Chris Lattner | b12914b | 2004-09-20 04:48:05 +0000 | [diff] [blame] | 117 | bool RaiseAllocations::runOnModule(Module &M) { |
Chris Lattner | 2dbfa03 | 2003-09-01 03:14:56 +0000 | [diff] [blame] | 118 | // Find the malloc/free prototypes... |
| 119 | doInitialization(M); |
| 120 | |
Chris Lattner | ade686e | 2002-05-07 19:02:48 +0000 | [diff] [blame] | 121 | bool Changed = false; |
Chris Lattner | ade686e | 2002-05-07 19:02:48 +0000 | [diff] [blame] | 122 | |
Chris Lattner | 2dbfa03 | 2003-09-01 03:14:56 +0000 | [diff] [blame] | 123 | // First, process all of the malloc calls... |
| 124 | if (MallocFunc) { |
| 125 | std::vector<User*> Users(MallocFunc->use_begin(), MallocFunc->use_end()); |
Chris Lattner | eb12cd6 | 2003-12-07 01:42:08 +0000 | [diff] [blame] | 126 | std::vector<Value*> EqPointers; // Values equal to MallocFunc |
Chris Lattner | 2dbfa03 | 2003-09-01 03:14:56 +0000 | [diff] [blame] | 127 | while (!Users.empty()) { |
Chris Lattner | eb12cd6 | 2003-12-07 01:42:08 +0000 | [diff] [blame] | 128 | User *U = Users.back(); |
| 129 | Users.pop_back(); |
| 130 | |
| 131 | if (Instruction *I = dyn_cast<Instruction>(U)) { |
Chris Lattner | 2dbfa03 | 2003-09-01 03:14:56 +0000 | [diff] [blame] | 132 | CallSite CS = CallSite::get(I); |
Chris Lattner | eb12cd6 | 2003-12-07 01:42:08 +0000 | [diff] [blame] | 133 | if (CS.getInstruction() && CS.arg_begin() != CS.arg_end() && |
| 134 | (CS.getCalledFunction() == MallocFunc || |
| 135 | std::find(EqPointers.begin(), EqPointers.end(), |
| 136 | CS.getCalledValue()) != EqPointers.end())) { |
| 137 | |
Chris Lattner | 2dbfa03 | 2003-09-01 03:14:56 +0000 | [diff] [blame] | 138 | Value *Source = *CS.arg_begin(); |
| 139 | |
| 140 | // If no prototype was provided for malloc, we may need to cast the |
| 141 | // source size. |
| 142 | if (Source->getType() != Type::UIntTy) |
| 143 | Source = new CastInst(Source, Type::UIntTy, "MallocAmtCast", I); |
| 144 | |
| 145 | std::string Name(I->getName()); I->setName(""); |
| 146 | MallocInst *MI = new MallocInst(Type::SByteTy, Source, Name, I); |
| 147 | I->replaceAllUsesWith(MI); |
Chris Lattner | cc83834 | 2003-09-16 19:42:21 +0000 | [diff] [blame] | 148 | |
| 149 | // If the old instruction was an invoke, add an unconditional branch |
| 150 | // before the invoke, which will become the new terminator. |
| 151 | if (InvokeInst *II = dyn_cast<InvokeInst>(I)) |
| 152 | new BranchInst(II->getNormalDest(), I); |
| 153 | |
| 154 | // Delete the old call site |
Chris Lattner | 2dbfa03 | 2003-09-01 03:14:56 +0000 | [diff] [blame] | 155 | MI->getParent()->getInstList().erase(I); |
| 156 | Changed = true; |
| 157 | ++NumRaised; |
| 158 | } |
Reid Spencer | 518310c | 2004-07-18 00:44:37 +0000 | [diff] [blame] | 159 | } else if (GlobalValue *GV = dyn_cast<GlobalValue>(U)) { |
| 160 | Users.insert(Users.end(), GV->use_begin(), GV->use_end()); |
| 161 | EqPointers.push_back(GV); |
Chris Lattner | eb12cd6 | 2003-12-07 01:42:08 +0000 | [diff] [blame] | 162 | } else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(U)) { |
| 163 | if (CE->getOpcode() == Instruction::Cast) { |
| 164 | Users.insert(Users.end(), CE->use_begin(), CE->use_end()); |
| 165 | EqPointers.push_back(CE); |
| 166 | } |
Chris Lattner | ade686e | 2002-05-07 19:02:48 +0000 | [diff] [blame] | 167 | } |
Chris Lattner | 2dbfa03 | 2003-09-01 03:14:56 +0000 | [diff] [blame] | 168 | } |
| 169 | } |
| 170 | |
| 171 | // Next, process all free calls... |
| 172 | if (FreeFunc) { |
| 173 | std::vector<User*> Users(FreeFunc->use_begin(), FreeFunc->use_end()); |
Chris Lattner | eb12cd6 | 2003-12-07 01:42:08 +0000 | [diff] [blame] | 174 | std::vector<Value*> EqPointers; // Values equal to FreeFunc |
Chris Lattner | 2dbfa03 | 2003-09-01 03:14:56 +0000 | [diff] [blame] | 175 | |
| 176 | while (!Users.empty()) { |
Chris Lattner | eb12cd6 | 2003-12-07 01:42:08 +0000 | [diff] [blame] | 177 | User *U = Users.back(); |
| 178 | Users.pop_back(); |
| 179 | |
| 180 | if (Instruction *I = dyn_cast<Instruction>(U)) { |
Chris Lattner | 2dbfa03 | 2003-09-01 03:14:56 +0000 | [diff] [blame] | 181 | CallSite CS = CallSite::get(I); |
Chris Lattner | eb12cd6 | 2003-12-07 01:42:08 +0000 | [diff] [blame] | 182 | if (CS.getInstruction() && CS.arg_begin() != CS.arg_end() && |
| 183 | (CS.getCalledFunction() == FreeFunc || |
| 184 | std::find(EqPointers.begin(), EqPointers.end(), |
| 185 | CS.getCalledValue()) != EqPointers.end())) { |
Chris Lattner | 2dbfa03 | 2003-09-01 03:14:56 +0000 | [diff] [blame] | 186 | |
| 187 | // If no prototype was provided for free, we may need to cast the |
| 188 | // source pointer. This should be really uncommon, but it's necessary |
Chris Lattner | da895d6 | 2005-02-27 06:18:25 +0000 | [diff] [blame^] | 189 | // just in case we are dealing with weird code like this: |
Chris Lattner | 2dbfa03 | 2003-09-01 03:14:56 +0000 | [diff] [blame] | 190 | // free((long)ptr); |
| 191 | // |
| 192 | Value *Source = *CS.arg_begin(); |
| 193 | if (!isa<PointerType>(Source->getType())) |
| 194 | Source = new CastInst(Source, PointerType::get(Type::SByteTy), |
| 195 | "FreePtrCast", I); |
| 196 | new FreeInst(Source, I); |
Chris Lattner | cc83834 | 2003-09-16 19:42:21 +0000 | [diff] [blame] | 197 | |
| 198 | // If the old instruction was an invoke, add an unconditional branch |
| 199 | // before the invoke, which will become the new terminator. |
| 200 | if (InvokeInst *II = dyn_cast<InvokeInst>(I)) |
| 201 | new BranchInst(II->getNormalDest(), I); |
| 202 | |
| 203 | // Delete the old call site |
Chris Lattner | 52f20f8 | 2004-11-09 05:10:56 +0000 | [diff] [blame] | 204 | if (I->getType() != Type::VoidTy) |
| 205 | I->replaceAllUsesWith(UndefValue::get(I->getType())); |
| 206 | I->eraseFromParent(); |
Chris Lattner | 2dbfa03 | 2003-09-01 03:14:56 +0000 | [diff] [blame] | 207 | Changed = true; |
| 208 | ++NumRaised; |
| 209 | } |
Reid Spencer | 518310c | 2004-07-18 00:44:37 +0000 | [diff] [blame] | 210 | } else if (GlobalValue *GV = dyn_cast<GlobalValue>(U)) { |
| 211 | Users.insert(Users.end(), GV->use_begin(), GV->use_end()); |
| 212 | EqPointers.push_back(GV); |
Chris Lattner | eb12cd6 | 2003-12-07 01:42:08 +0000 | [diff] [blame] | 213 | } else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(U)) { |
| 214 | if (CE->getOpcode() == Instruction::Cast) { |
| 215 | Users.insert(Users.end(), CE->use_begin(), CE->use_end()); |
| 216 | EqPointers.push_back(CE); |
| 217 | } |
Chris Lattner | 2dbfa03 | 2003-09-01 03:14:56 +0000 | [diff] [blame] | 218 | } |
Chris Lattner | ade686e | 2002-05-07 19:02:48 +0000 | [diff] [blame] | 219 | } |
Chris Lattner | ade686e | 2002-05-07 19:02:48 +0000 | [diff] [blame] | 220 | } |
| 221 | |
| 222 | return Changed; |
| 223 | } |