Chris Lattner | 65e96e5 | 2002-05-07 19:04:39 +0000 | [diff] [blame] | 1 | //===- RaiseAllocations.cpp - Convert %malloc & %free calls to insts ------===// |
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 | 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) {} |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 36 | |
Chris Lattner | a92f696 | 2002-10-01 22:38:41 +0000 | [diff] [blame] | 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); |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +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 | }; |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 46 | |
Chris Lattner | 7f8897f | 2006-08-27 22:42:52 +0000 | [diff] [blame] | 47 | RegisterPass<RaiseAllocations> |
Chris Lattner | a6275cc | 2002-07-26 21:12:46 +0000 | [diff] [blame] | 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())) { |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 137 | |
Chris Lattner | 2dbfa03 | 2003-09-01 03:14:56 +0000 | [diff] [blame] | 138 | Value *Source = *CS.arg_begin(); |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 139 | |
Chris Lattner | 2dbfa03 | 2003-09-01 03:14:56 +0000 | [diff] [blame] | 140 | // If no prototype was provided for malloc, we may need to cast the |
| 141 | // source size. |
| 142 | if (Source->getType() != Type::UIntTy) |
Reid Spencer | 3da59db | 2006-11-27 01:05:10 +0000 | [diff] [blame^] | 143 | Source = |
| 144 | CastInst::createInferredCast(Source, Type::UIntTy, |
| 145 | "MallocAmtCast", I); |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 146 | |
Chris Lattner | 2dbfa03 | 2003-09-01 03:14:56 +0000 | [diff] [blame] | 147 | std::string Name(I->getName()); I->setName(""); |
| 148 | MallocInst *MI = new MallocInst(Type::SByteTy, Source, Name, I); |
| 149 | I->replaceAllUsesWith(MI); |
Chris Lattner | cc83834 | 2003-09-16 19:42:21 +0000 | [diff] [blame] | 150 | |
| 151 | // If the old instruction was an invoke, add an unconditional branch |
| 152 | // before the invoke, which will become the new terminator. |
| 153 | if (InvokeInst *II = dyn_cast<InvokeInst>(I)) |
| 154 | new BranchInst(II->getNormalDest(), I); |
| 155 | |
| 156 | // Delete the old call site |
Chris Lattner | 2dbfa03 | 2003-09-01 03:14:56 +0000 | [diff] [blame] | 157 | MI->getParent()->getInstList().erase(I); |
| 158 | Changed = true; |
| 159 | ++NumRaised; |
| 160 | } |
Reid Spencer | 518310c | 2004-07-18 00:44:37 +0000 | [diff] [blame] | 161 | } else if (GlobalValue *GV = dyn_cast<GlobalValue>(U)) { |
| 162 | Users.insert(Users.end(), GV->use_begin(), GV->use_end()); |
| 163 | EqPointers.push_back(GV); |
Chris Lattner | eb12cd6 | 2003-12-07 01:42:08 +0000 | [diff] [blame] | 164 | } else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(U)) { |
Reid Spencer | 3da59db | 2006-11-27 01:05:10 +0000 | [diff] [blame^] | 165 | if (CE->isCast()) { |
Chris Lattner | eb12cd6 | 2003-12-07 01:42:08 +0000 | [diff] [blame] | 166 | Users.insert(Users.end(), CE->use_begin(), CE->use_end()); |
| 167 | EqPointers.push_back(CE); |
| 168 | } |
Chris Lattner | ade686e | 2002-05-07 19:02:48 +0000 | [diff] [blame] | 169 | } |
Chris Lattner | 2dbfa03 | 2003-09-01 03:14:56 +0000 | [diff] [blame] | 170 | } |
| 171 | } |
| 172 | |
| 173 | // Next, process all free calls... |
| 174 | if (FreeFunc) { |
| 175 | std::vector<User*> Users(FreeFunc->use_begin(), FreeFunc->use_end()); |
Chris Lattner | eb12cd6 | 2003-12-07 01:42:08 +0000 | [diff] [blame] | 176 | std::vector<Value*> EqPointers; // Values equal to FreeFunc |
Chris Lattner | 2dbfa03 | 2003-09-01 03:14:56 +0000 | [diff] [blame] | 177 | |
| 178 | while (!Users.empty()) { |
Chris Lattner | eb12cd6 | 2003-12-07 01:42:08 +0000 | [diff] [blame] | 179 | User *U = Users.back(); |
| 180 | Users.pop_back(); |
| 181 | |
| 182 | if (Instruction *I = dyn_cast<Instruction>(U)) { |
Chris Lattner | 2dbfa03 | 2003-09-01 03:14:56 +0000 | [diff] [blame] | 183 | CallSite CS = CallSite::get(I); |
Chris Lattner | eb12cd6 | 2003-12-07 01:42:08 +0000 | [diff] [blame] | 184 | if (CS.getInstruction() && CS.arg_begin() != CS.arg_end() && |
| 185 | (CS.getCalledFunction() == FreeFunc || |
| 186 | std::find(EqPointers.begin(), EqPointers.end(), |
| 187 | CS.getCalledValue()) != EqPointers.end())) { |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 188 | |
Chris Lattner | 2dbfa03 | 2003-09-01 03:14:56 +0000 | [diff] [blame] | 189 | // If no prototype was provided for free, we may need to cast the |
| 190 | // source pointer. This should be really uncommon, but it's necessary |
Chris Lattner | da895d6 | 2005-02-27 06:18:25 +0000 | [diff] [blame] | 191 | // just in case we are dealing with weird code like this: |
Chris Lattner | 2dbfa03 | 2003-09-01 03:14:56 +0000 | [diff] [blame] | 192 | // free((long)ptr); |
| 193 | // |
| 194 | Value *Source = *CS.arg_begin(); |
| 195 | if (!isa<PointerType>(Source->getType())) |
Reid Spencer | 3da59db | 2006-11-27 01:05:10 +0000 | [diff] [blame^] | 196 | Source = CastInst::createInferredCast( |
| 197 | Source, PointerType::get(Type::SByteTy), "FreePtrCast", I); |
Chris Lattner | 2dbfa03 | 2003-09-01 03:14:56 +0000 | [diff] [blame] | 198 | new FreeInst(Source, I); |
Chris Lattner | cc83834 | 2003-09-16 19:42:21 +0000 | [diff] [blame] | 199 | |
| 200 | // If the old instruction was an invoke, add an unconditional branch |
| 201 | // before the invoke, which will become the new terminator. |
| 202 | if (InvokeInst *II = dyn_cast<InvokeInst>(I)) |
| 203 | new BranchInst(II->getNormalDest(), I); |
| 204 | |
| 205 | // Delete the old call site |
Chris Lattner | 52f20f8 | 2004-11-09 05:10:56 +0000 | [diff] [blame] | 206 | if (I->getType() != Type::VoidTy) |
| 207 | I->replaceAllUsesWith(UndefValue::get(I->getType())); |
| 208 | I->eraseFromParent(); |
Chris Lattner | 2dbfa03 | 2003-09-01 03:14:56 +0000 | [diff] [blame] | 209 | Changed = true; |
| 210 | ++NumRaised; |
| 211 | } |
Reid Spencer | 518310c | 2004-07-18 00:44:37 +0000 | [diff] [blame] | 212 | } else if (GlobalValue *GV = dyn_cast<GlobalValue>(U)) { |
| 213 | Users.insert(Users.end(), GV->use_begin(), GV->use_end()); |
| 214 | EqPointers.push_back(GV); |
Chris Lattner | eb12cd6 | 2003-12-07 01:42:08 +0000 | [diff] [blame] | 215 | } else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(U)) { |
Reid Spencer | 3da59db | 2006-11-27 01:05:10 +0000 | [diff] [blame^] | 216 | if (CE->isCast()) { |
Chris Lattner | eb12cd6 | 2003-12-07 01:42:08 +0000 | [diff] [blame] | 217 | Users.insert(Users.end(), CE->use_begin(), CE->use_end()); |
| 218 | EqPointers.push_back(CE); |
| 219 | } |
Chris Lattner | 2dbfa03 | 2003-09-01 03:14:56 +0000 | [diff] [blame] | 220 | } |
Chris Lattner | ade686e | 2002-05-07 19:02:48 +0000 | [diff] [blame] | 221 | } |
Chris Lattner | ade686e | 2002-05-07 19:02:48 +0000 | [diff] [blame] | 222 | } |
| 223 | |
| 224 | return Changed; |
| 225 | } |