Chris Lattner | ade686e | 2002-05-07 19:02:48 +0000 | [diff] [blame] | 1 | //===- LowerAllocations.cpp - Reduce malloc & free insts to calls ---------===// |
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 | 1bffea0 | 2001-10-15 17:31:51 +0000 | [diff] [blame] | 9 | // |
Misha Brukman | 7c791ed | 2004-01-28 20:43:01 +0000 | [diff] [blame] | 10 | // The LowerAllocations transformation is a target-dependent tranformation |
Chris Lattner | ade686e | 2002-05-07 19:02:48 +0000 | [diff] [blame] | 11 | // because it depends on the size of data types and alignment constraints. |
Chris Lattner | 1bffea0 | 2001-10-15 17:31:51 +0000 | [diff] [blame] | 12 | // |
| 13 | //===----------------------------------------------------------------------===// |
| 14 | |
Chris Lattner | e9ee3e5 | 2002-07-23 22:04:17 +0000 | [diff] [blame] | 15 | #include "llvm/Transforms/Scalar.h" |
Chris Lattner | 8d89e7b | 2006-05-09 04:13:41 +0000 | [diff] [blame] | 16 | #include "llvm/Transforms/Utils/UnifyFunctionExitNodes.h" |
Chris Lattner | 793c6b8 | 2002-01-31 00:45:11 +0000 | [diff] [blame] | 17 | #include "llvm/Module.h" |
Chris Lattner | 1bffea0 | 2001-10-15 17:31:51 +0000 | [diff] [blame] | 18 | #include "llvm/DerivedTypes.h" |
Misha Brukman | 47b14a4 | 2004-07-29 17:30:56 +0000 | [diff] [blame] | 19 | #include "llvm/Instructions.h" |
Chris Lattner | 497c60c | 2002-05-07 18:12:18 +0000 | [diff] [blame] | 20 | #include "llvm/Constants.h" |
Chris Lattner | bd0ef77 | 2002-02-26 21:46:54 +0000 | [diff] [blame] | 21 | #include "llvm/Pass.h" |
Reid Spencer | 551ccae | 2004-09-01 22:55:40 +0000 | [diff] [blame] | 22 | #include "llvm/ADT/Statistic.h" |
Chris Lattner | de97b57 | 2004-12-13 20:00:02 +0000 | [diff] [blame] | 23 | #include "llvm/Target/TargetData.h" |
Chris Lattner | a4f0b3a | 2006-08-27 12:54:02 +0000 | [diff] [blame] | 24 | #include "llvm/Support/Compiler.h" |
Chris Lattner | d745602 | 2004-01-09 06:02:20 +0000 | [diff] [blame] | 25 | using namespace llvm; |
Brian Gaeke | d0fde30 | 2003-11-11 22:41:34 +0000 | [diff] [blame] | 26 | |
Chris Lattner | bd0ef77 | 2002-02-26 21:46:54 +0000 | [diff] [blame] | 27 | namespace { |
Chris Lattner | a92f696 | 2002-10-01 22:38:41 +0000 | [diff] [blame] | 28 | Statistic<> NumLowered("lowerallocs", "Number of allocations lowered"); |
Chris Lattner | bd0ef77 | 2002-02-26 21:46:54 +0000 | [diff] [blame] | 29 | |
Chris Lattner | 3b2106f | 2002-09-25 23:47:47 +0000 | [diff] [blame] | 30 | /// LowerAllocations - Turn malloc and free instructions into %malloc and |
| 31 | /// %free calls. |
| 32 | /// |
Chris Lattner | 9525528 | 2006-06-28 23:17:24 +0000 | [diff] [blame] | 33 | class VISIBILITY_HIDDEN LowerAllocations : public BasicBlockPass { |
Chris Lattner | 3b2106f | 2002-09-25 23:47:47 +0000 | [diff] [blame] | 34 | Function *MallocFunc; // Functions in the module we are processing |
| 35 | Function *FreeFunc; // Initialized by doInitialization |
Chris Lattner | 5f792c2 | 2005-03-03 01:03:43 +0000 | [diff] [blame] | 36 | bool LowerMallocArgToInteger; |
Chris Lattner | 3b2106f | 2002-09-25 23:47:47 +0000 | [diff] [blame] | 37 | public: |
Chris Lattner | 5f792c2 | 2005-03-03 01:03:43 +0000 | [diff] [blame] | 38 | LowerAllocations(bool LowerToInt = false) |
| 39 | : MallocFunc(0), FreeFunc(0), LowerMallocArgToInteger(LowerToInt) {} |
Chris Lattner | bd0ef77 | 2002-02-26 21:46:54 +0000 | [diff] [blame] | 40 | |
Chris Lattner | de97b57 | 2004-12-13 20:00:02 +0000 | [diff] [blame] | 41 | virtual void getAnalysisUsage(AnalysisUsage &AU) const { |
| 42 | AU.addRequired<TargetData>(); |
| 43 | AU.setPreservesCFG(); |
Chris Lattner | 8d89e7b | 2006-05-09 04:13:41 +0000 | [diff] [blame] | 44 | |
Chris Lattner | ed96fe8 | 2006-05-17 21:05:27 +0000 | [diff] [blame] | 45 | // This is a cluster of orthogonal Transforms: |
Chris Lattner | 8d89e7b | 2006-05-09 04:13:41 +0000 | [diff] [blame] | 46 | AU.addPreserved<UnifyFunctionExitNodes>(); |
| 47 | AU.addPreservedID(PromoteMemoryToRegisterID); |
| 48 | AU.addPreservedID(LowerSelectID); |
| 49 | AU.addPreservedID(LowerSwitchID); |
Chris Lattner | ed96fe8 | 2006-05-17 21:05:27 +0000 | [diff] [blame] | 50 | AU.addPreservedID(LowerInvokePassID); |
Chris Lattner | de97b57 | 2004-12-13 20:00:02 +0000 | [diff] [blame] | 51 | } |
| 52 | |
Chris Lattner | 3b2106f | 2002-09-25 23:47:47 +0000 | [diff] [blame] | 53 | /// doPassInitialization - For the lower allocations pass, this ensures that |
| 54 | /// a module contains a declaration for a malloc and a free function. |
| 55 | /// |
| 56 | bool doInitialization(Module &M); |
Reid Spencer | 791a959 | 2004-12-07 08:11:36 +0000 | [diff] [blame] | 57 | |
Chris Lattner | de97b57 | 2004-12-13 20:00:02 +0000 | [diff] [blame] | 58 | virtual bool doInitialization(Function &F) { |
| 59 | return BasicBlockPass::doInitialization(F); |
| 60 | } |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 61 | |
Chris Lattner | 3b2106f | 2002-09-25 23:47:47 +0000 | [diff] [blame] | 62 | /// runOnBasicBlock - This method does the actual work of converting |
| 63 | /// instructions over, assuming that the pass has already been initialized. |
| 64 | /// |
| 65 | bool runOnBasicBlock(BasicBlock &BB); |
| 66 | }; |
Chris Lattner | bd0ef77 | 2002-02-26 21:46:54 +0000 | [diff] [blame] | 67 | |
Chris Lattner | 7f8897f | 2006-08-27 22:42:52 +0000 | [diff] [blame] | 68 | RegisterPass<LowerAllocations> |
Chris Lattner | 3b2106f | 2002-09-25 23:47:47 +0000 | [diff] [blame] | 69 | X("lowerallocs", "Lower allocations from instructions to calls"); |
Chris Lattner | ade686e | 2002-05-07 19:02:48 +0000 | [diff] [blame] | 70 | } |
Chris Lattner | bd0ef77 | 2002-02-26 21:46:54 +0000 | [diff] [blame] | 71 | |
Chris Lattner | b3674e4 | 2006-05-02 04:24:36 +0000 | [diff] [blame] | 72 | // Publically exposed interface to pass... |
| 73 | const PassInfo *llvm::LowerAllocationsID = X.getPassInfo(); |
Chris Lattner | ade686e | 2002-05-07 19:02:48 +0000 | [diff] [blame] | 74 | // createLowerAllocationsPass - Interface to this file... |
Chris Lattner | 5f792c2 | 2005-03-03 01:03:43 +0000 | [diff] [blame] | 75 | FunctionPass *llvm::createLowerAllocationsPass(bool LowerMallocArgToInteger) { |
| 76 | return new LowerAllocations(LowerMallocArgToInteger); |
Chris Lattner | ade686e | 2002-05-07 19:02:48 +0000 | [diff] [blame] | 77 | } |
Chris Lattner | 96c466b | 2002-04-29 14:57:45 +0000 | [diff] [blame] | 78 | |
Chris Lattner | 1bffea0 | 2001-10-15 17:31:51 +0000 | [diff] [blame] | 79 | |
Chris Lattner | f4de63f | 2002-01-21 07:31:50 +0000 | [diff] [blame] | 80 | // doInitialization - For the lower allocations pass, this ensures that a |
Chris Lattner | 1bffea0 | 2001-10-15 17:31:51 +0000 | [diff] [blame] | 81 | // module contains a declaration for a malloc and a free function. |
| 82 | // |
| 83 | // This function is always successful. |
| 84 | // |
Chris Lattner | 7e70829 | 2002-06-25 16:13:24 +0000 | [diff] [blame] | 85 | bool LowerAllocations::doInitialization(Module &M) { |
Chris Lattner | 7d8a86a | 2003-08-31 00:22:27 +0000 | [diff] [blame] | 86 | const Type *SBPTy = PointerType::get(Type::SByteTy); |
Chris Lattner | b99df4f | 2004-02-28 18:51:45 +0000 | [diff] [blame] | 87 | MallocFunc = M.getNamedFunction("malloc"); |
| 88 | FreeFunc = M.getNamedFunction("free"); |
| 89 | |
Chris Lattner | de97b57 | 2004-12-13 20:00:02 +0000 | [diff] [blame] | 90 | if (MallocFunc == 0) { |
| 91 | // Prototype malloc as "void* malloc(...)", because we don't know in |
| 92 | // doInitialization whether size_t is int or long. |
| 93 | FunctionType *FT = FunctionType::get(SBPTy,std::vector<const Type*>(),true); |
| 94 | MallocFunc = M.getOrInsertFunction("malloc", FT); |
| 95 | } |
Chris Lattner | b99df4f | 2004-02-28 18:51:45 +0000 | [diff] [blame] | 96 | if (FreeFunc == 0) |
Jeff Cohen | 66c5fd6 | 2005-10-23 04:37:20 +0000 | [diff] [blame] | 97 | FreeFunc = M.getOrInsertFunction("free" , Type::VoidTy, SBPTy, (Type *)0); |
Chris Lattner | 1bffea0 | 2001-10-15 17:31:51 +0000 | [diff] [blame] | 98 | |
Chris Lattner | ade686e | 2002-05-07 19:02:48 +0000 | [diff] [blame] | 99 | return true; |
Chris Lattner | 1bffea0 | 2001-10-15 17:31:51 +0000 | [diff] [blame] | 100 | } |
| 101 | |
Chris Lattner | 8445372 | 2002-01-21 23:34:02 +0000 | [diff] [blame] | 102 | // runOnBasicBlock - This method does the actual work of converting |
Chris Lattner | 1bffea0 | 2001-10-15 17:31:51 +0000 | [diff] [blame] | 103 | // instructions over, assuming that the pass has already been initialized. |
| 104 | // |
Chris Lattner | 7e70829 | 2002-06-25 16:13:24 +0000 | [diff] [blame] | 105 | bool LowerAllocations::runOnBasicBlock(BasicBlock &BB) { |
Chris Lattner | 42c9c2c | 2001-10-18 05:27:33 +0000 | [diff] [blame] | 106 | bool Changed = false; |
Chris Lattner | 7e70829 | 2002-06-25 16:13:24 +0000 | [diff] [blame] | 107 | assert(MallocFunc && FreeFunc && "Pass not initialized!"); |
| 108 | |
| 109 | BasicBlock::InstListType &BBIL = BB.getInstList(); |
Chris Lattner | 1bffea0 | 2001-10-15 17:31:51 +0000 | [diff] [blame] | 110 | |
Chris Lattner | 5f792c2 | 2005-03-03 01:03:43 +0000 | [diff] [blame] | 111 | const TargetData &TD = getAnalysis<TargetData>(); |
| 112 | const Type *IntPtrTy = TD.getIntPtrType(); |
Chris Lattner | de97b57 | 2004-12-13 20:00:02 +0000 | [diff] [blame] | 113 | |
Chris Lattner | 1bffea0 | 2001-10-15 17:31:51 +0000 | [diff] [blame] | 114 | // Loop over all of the instructions, looking for malloc or free instructions |
Chris Lattner | 7e70829 | 2002-06-25 16:13:24 +0000 | [diff] [blame] | 115 | for (BasicBlock::iterator I = BB.begin(), E = BB.end(); I != E; ++I) { |
Chris Lattner | e408e25 | 2003-04-23 16:37:45 +0000 | [diff] [blame] | 116 | if (MallocInst *MI = dyn_cast<MallocInst>(I)) { |
Chris Lattner | 7e70829 | 2002-06-25 16:13:24 +0000 | [diff] [blame] | 117 | const Type *AllocTy = MI->getType()->getElementType(); |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 118 | |
Chris Lattner | 8bfc2f1 | 2004-07-15 01:08:08 +0000 | [diff] [blame] | 119 | // malloc(type) becomes sbyte *malloc(size) |
Chris Lattner | 5f792c2 | 2005-03-03 01:03:43 +0000 | [diff] [blame] | 120 | Value *MallocArg; |
| 121 | if (LowerMallocArgToInteger) |
Reid Spencer | b83eb64 | 2006-10-20 07:07:24 +0000 | [diff] [blame] | 122 | MallocArg = ConstantInt::get(Type::ULongTy, TD.getTypeSize(AllocTy)); |
Chris Lattner | 5f792c2 | 2005-03-03 01:03:43 +0000 | [diff] [blame] | 123 | else |
| 124 | MallocArg = ConstantExpr::getSizeOf(AllocTy); |
| 125 | MallocArg = ConstantExpr::getCast(cast<Constant>(MallocArg), IntPtrTy); |
| 126 | |
Chris Lattner | 8bfc2f1 | 2004-07-15 01:08:08 +0000 | [diff] [blame] | 127 | if (MI->isArrayAllocation()) { |
Chris Lattner | de97b57 | 2004-12-13 20:00:02 +0000 | [diff] [blame] | 128 | if (isa<ConstantInt>(MallocArg) && |
Reid Spencer | b83eb64 | 2006-10-20 07:07:24 +0000 | [diff] [blame] | 129 | cast<ConstantInt>(MallocArg)->getZExtValue() == 1) { |
Chris Lattner | 8bfc2f1 | 2004-07-15 01:08:08 +0000 | [diff] [blame] | 130 | MallocArg = MI->getOperand(0); // Operand * 1 = Operand |
| 131 | } else if (Constant *CO = dyn_cast<Constant>(MI->getOperand(0))) { |
Chris Lattner | de97b57 | 2004-12-13 20:00:02 +0000 | [diff] [blame] | 132 | CO = ConstantExpr::getCast(CO, IntPtrTy); |
Chris Lattner | 8bfc2f1 | 2004-07-15 01:08:08 +0000 | [diff] [blame] | 133 | MallocArg = ConstantExpr::getMul(CO, cast<Constant>(MallocArg)); |
| 134 | } else { |
Chris Lattner | de97b57 | 2004-12-13 20:00:02 +0000 | [diff] [blame] | 135 | Value *Scale = MI->getOperand(0); |
| 136 | if (Scale->getType() != IntPtrTy) |
Reid Spencer | 3da59db | 2006-11-27 01:05:10 +0000 | [diff] [blame^] | 137 | Scale = CastInst::createInferredCast(Scale, IntPtrTy, "", I); |
Chris Lattner | de97b57 | 2004-12-13 20:00:02 +0000 | [diff] [blame] | 138 | |
Chris Lattner | 8bfc2f1 | 2004-07-15 01:08:08 +0000 | [diff] [blame] | 139 | // Multiply it by the array size if necessary... |
Chris Lattner | de97b57 | 2004-12-13 20:00:02 +0000 | [diff] [blame] | 140 | MallocArg = BinaryOperator::create(Instruction::Mul, Scale, |
Chris Lattner | 8bfc2f1 | 2004-07-15 01:08:08 +0000 | [diff] [blame] | 141 | MallocArg, "", I); |
| 142 | } |
Chris Lattner | 1bffea0 | 2001-10-15 17:31:51 +0000 | [diff] [blame] | 143 | } |
Chris Lattner | b99df4f | 2004-02-28 18:51:45 +0000 | [diff] [blame] | 144 | |
| 145 | const FunctionType *MallocFTy = MallocFunc->getFunctionType(); |
| 146 | std::vector<Value*> MallocArgs; |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 147 | |
Chris Lattner | b99df4f | 2004-02-28 18:51:45 +0000 | [diff] [blame] | 148 | if (MallocFTy->getNumParams() > 0 || MallocFTy->isVarArg()) { |
Chris Lattner | de97b57 | 2004-12-13 20:00:02 +0000 | [diff] [blame] | 149 | if (MallocFTy->isVarArg()) { |
| 150 | if (MallocArg->getType() != IntPtrTy) |
Reid Spencer | 3da59db | 2006-11-27 01:05:10 +0000 | [diff] [blame^] | 151 | MallocArg = CastInst::createInferredCast(MallocArg, IntPtrTy, "", |
| 152 | I); |
Chris Lattner | de97b57 | 2004-12-13 20:00:02 +0000 | [diff] [blame] | 153 | } else if (MallocFTy->getNumParams() > 0 && |
| 154 | MallocFTy->getParamType(0) != Type::UIntTy) |
Reid Spencer | 3da59db | 2006-11-27 01:05:10 +0000 | [diff] [blame^] | 155 | MallocArg = |
| 156 | CastInst::createInferredCast(MallocArg, MallocFTy->getParamType(0), |
| 157 | "",I); |
Chris Lattner | b99df4f | 2004-02-28 18:51:45 +0000 | [diff] [blame] | 158 | MallocArgs.push_back(MallocArg); |
| 159 | } |
| 160 | |
| 161 | // If malloc is prototyped to take extra arguments, pass nulls. |
| 162 | for (unsigned i = 1; i < MallocFTy->getNumParams(); ++i) |
| 163 | MallocArgs.push_back(Constant::getNullValue(MallocFTy->getParamType(i))); |
| 164 | |
Chris Lattner | 8445372 | 2002-01-21 23:34:02 +0000 | [diff] [blame] | 165 | // Create the call to Malloc... |
Chris Lattner | b99df4f | 2004-02-28 18:51:45 +0000 | [diff] [blame] | 166 | CallInst *MCall = new CallInst(MallocFunc, MallocArgs, "", I); |
Chris Lattner | a9e9211 | 2005-05-06 06:48:21 +0000 | [diff] [blame] | 167 | MCall->setTailCall(); |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 168 | |
Chris Lattner | 8445372 | 2002-01-21 23:34:02 +0000 | [diff] [blame] | 169 | // Create a cast instruction to convert to the right type... |
Chris Lattner | b99df4f | 2004-02-28 18:51:45 +0000 | [diff] [blame] | 170 | Value *MCast; |
| 171 | if (MCall->getType() != Type::VoidTy) |
Reid Spencer | 3da59db | 2006-11-27 01:05:10 +0000 | [diff] [blame^] | 172 | MCast = CastInst::createInferredCast(MCall, MI->getType(), "", I); |
Chris Lattner | b99df4f | 2004-02-28 18:51:45 +0000 | [diff] [blame] | 173 | else |
| 174 | MCast = Constant::getNullValue(MI->getType()); |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 175 | |
Chris Lattner | 8445372 | 2002-01-21 23:34:02 +0000 | [diff] [blame] | 176 | // Replace all uses of the old malloc inst with the cast inst |
| 177 | MI->replaceAllUsesWith(MCast); |
Chris Lattner | 1d608ab | 2002-09-10 22:38:47 +0000 | [diff] [blame] | 178 | I = --BBIL.erase(I); // remove and delete the malloc instr... |
Chris Lattner | 8445372 | 2002-01-21 23:34:02 +0000 | [diff] [blame] | 179 | Changed = true; |
Chris Lattner | 3dec1f2 | 2002-05-10 15:38:35 +0000 | [diff] [blame] | 180 | ++NumLowered; |
Chris Lattner | e408e25 | 2003-04-23 16:37:45 +0000 | [diff] [blame] | 181 | } else if (FreeInst *FI = dyn_cast<FreeInst>(I)) { |
Chris Lattner | b99df4f | 2004-02-28 18:51:45 +0000 | [diff] [blame] | 182 | const FunctionType *FreeFTy = FreeFunc->getFunctionType(); |
| 183 | std::vector<Value*> FreeArgs; |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 184 | |
Chris Lattner | b99df4f | 2004-02-28 18:51:45 +0000 | [diff] [blame] | 185 | if (FreeFTy->getNumParams() > 0 || FreeFTy->isVarArg()) { |
| 186 | Value *MCast = FI->getOperand(0); |
| 187 | if (FreeFTy->getNumParams() > 0 && |
| 188 | FreeFTy->getParamType(0) != MCast->getType()) |
Reid Spencer | 3da59db | 2006-11-27 01:05:10 +0000 | [diff] [blame^] | 189 | MCast = CastInst::createInferredCast(MCast, FreeFTy->getParamType(0), |
| 190 | "", I); |
Chris Lattner | b99df4f | 2004-02-28 18:51:45 +0000 | [diff] [blame] | 191 | FreeArgs.push_back(MCast); |
| 192 | } |
| 193 | |
| 194 | // If malloc is prototyped to take extra arguments, pass nulls. |
| 195 | for (unsigned i = 1; i < FreeFTy->getNumParams(); ++i) |
| 196 | FreeArgs.push_back(Constant::getNullValue(FreeFTy->getParamType(i))); |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 197 | |
Chris Lattner | 8445372 | 2002-01-21 23:34:02 +0000 | [diff] [blame] | 198 | // Insert a call to the free function... |
Chris Lattner | a9e9211 | 2005-05-06 06:48:21 +0000 | [diff] [blame] | 199 | (new CallInst(FreeFunc, FreeArgs, "", I))->setTailCall(); |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 200 | |
Chris Lattner | 8445372 | 2002-01-21 23:34:02 +0000 | [diff] [blame] | 201 | // Delete the old free instruction |
Chris Lattner | 1d608ab | 2002-09-10 22:38:47 +0000 | [diff] [blame] | 202 | I = --BBIL.erase(I); |
Chris Lattner | 8445372 | 2002-01-21 23:34:02 +0000 | [diff] [blame] | 203 | Changed = true; |
Chris Lattner | 3dec1f2 | 2002-05-10 15:38:35 +0000 | [diff] [blame] | 204 | ++NumLowered; |
Chris Lattner | 1bffea0 | 2001-10-15 17:31:51 +0000 | [diff] [blame] | 205 | } |
| 206 | } |
| 207 | |
Chris Lattner | 42c9c2c | 2001-10-18 05:27:33 +0000 | [diff] [blame] | 208 | return Changed; |
Chris Lattner | 1bffea0 | 2001-10-15 17:31:51 +0000 | [diff] [blame] | 209 | } |
Brian Gaeke | d0fde30 | 2003-11-11 22:41:34 +0000 | [diff] [blame] | 210 | |