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 | // |
Chris Lattner | 4ee451d | 2007-12-29 20:36:04 +0000 | [diff] [blame] | 5 | // This file is distributed under the University of Illinois Open Source |
| 6 | // 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 | d216e8b | 2006-12-19 22:17:40 +0000 | [diff] [blame] | 15 | #define DEBUG_TYPE "lowerallocs" |
Chris Lattner | e9ee3e5 | 2002-07-23 22:04:17 +0000 | [diff] [blame] | 16 | #include "llvm/Transforms/Scalar.h" |
Chris Lattner | 8d89e7b | 2006-05-09 04:13:41 +0000 | [diff] [blame] | 17 | #include "llvm/Transforms/Utils/UnifyFunctionExitNodes.h" |
Chris Lattner | 793c6b8 | 2002-01-31 00:45:11 +0000 | [diff] [blame] | 18 | #include "llvm/Module.h" |
Chris Lattner | 1bffea0 | 2001-10-15 17:31:51 +0000 | [diff] [blame] | 19 | #include "llvm/DerivedTypes.h" |
Misha Brukman | 47b14a4 | 2004-07-29 17:30:56 +0000 | [diff] [blame] | 20 | #include "llvm/Instructions.h" |
Chris Lattner | 497c60c | 2002-05-07 18:12:18 +0000 | [diff] [blame] | 21 | #include "llvm/Constants.h" |
Chris Lattner | bd0ef77 | 2002-02-26 21:46:54 +0000 | [diff] [blame] | 22 | #include "llvm/Pass.h" |
Reid Spencer | 551ccae | 2004-09-01 22:55:40 +0000 | [diff] [blame] | 23 | #include "llvm/ADT/Statistic.h" |
Chris Lattner | de97b57 | 2004-12-13 20:00:02 +0000 | [diff] [blame] | 24 | #include "llvm/Target/TargetData.h" |
Chris Lattner | a4f0b3a | 2006-08-27 12:54:02 +0000 | [diff] [blame] | 25 | #include "llvm/Support/Compiler.h" |
Chris Lattner | d745602 | 2004-01-09 06:02:20 +0000 | [diff] [blame] | 26 | using namespace llvm; |
Brian Gaeke | d0fde30 | 2003-11-11 22:41:34 +0000 | [diff] [blame] | 27 | |
Chris Lattner | d216e8b | 2006-12-19 22:17:40 +0000 | [diff] [blame] | 28 | STATISTIC(NumLowered, "Number of allocations lowered"); |
Chris Lattner | bd0ef77 | 2002-02-26 21:46:54 +0000 | [diff] [blame] | 29 | |
Chris Lattner | d216e8b | 2006-12-19 22:17:40 +0000 | [diff] [blame] | 30 | namespace { |
Chris Lattner | 3b2106f | 2002-09-25 23:47:47 +0000 | [diff] [blame] | 31 | /// LowerAllocations - Turn malloc and free instructions into %malloc and |
| 32 | /// %free calls. |
| 33 | /// |
Chris Lattner | 9525528 | 2006-06-28 23:17:24 +0000 | [diff] [blame] | 34 | class VISIBILITY_HIDDEN LowerAllocations : public BasicBlockPass { |
Chris Lattner | b76efb7 | 2007-01-07 08:12:01 +0000 | [diff] [blame] | 35 | Constant *MallocFunc; // Functions in the module we are processing |
| 36 | Constant *FreeFunc; // Initialized by doInitialization |
Chris Lattner | 5f792c2 | 2005-03-03 01:03:43 +0000 | [diff] [blame] | 37 | bool LowerMallocArgToInteger; |
Chris Lattner | 3b2106f | 2002-09-25 23:47:47 +0000 | [diff] [blame] | 38 | public: |
Devang Patel | 1997473 | 2007-05-03 01:11:54 +0000 | [diff] [blame] | 39 | static char ID; // Pass ID, replacement for typeid |
Dan Gohman | c2bbfc1 | 2007-08-01 15:32:29 +0000 | [diff] [blame] | 40 | explicit LowerAllocations(bool LowerToInt = false) |
Dan Gohman | ae73dc1 | 2008-09-04 17:05:41 +0000 | [diff] [blame] | 41 | : BasicBlockPass(&ID), MallocFunc(0), FreeFunc(0), |
Devang Patel | 794fd75 | 2007-05-01 21:15:47 +0000 | [diff] [blame] | 42 | LowerMallocArgToInteger(LowerToInt) {} |
Chris Lattner | bd0ef77 | 2002-02-26 21:46:54 +0000 | [diff] [blame] | 43 | |
Chris Lattner | de97b57 | 2004-12-13 20:00:02 +0000 | [diff] [blame] | 44 | virtual void getAnalysisUsage(AnalysisUsage &AU) const { |
| 45 | AU.addRequired<TargetData>(); |
| 46 | AU.setPreservesCFG(); |
Chris Lattner | 8d89e7b | 2006-05-09 04:13:41 +0000 | [diff] [blame] | 47 | |
Anton Korobeynikov | bed2946 | 2007-04-16 18:10:23 +0000 | [diff] [blame] | 48 | // This is a cluster of orthogonal Transforms: |
Chris Lattner | 8d89e7b | 2006-05-09 04:13:41 +0000 | [diff] [blame] | 49 | AU.addPreserved<UnifyFunctionExitNodes>(); |
| 50 | AU.addPreservedID(PromoteMemoryToRegisterID); |
Chris Lattner | 8d89e7b | 2006-05-09 04:13:41 +0000 | [diff] [blame] | 51 | AU.addPreservedID(LowerSwitchID); |
Chris Lattner | ed96fe8 | 2006-05-17 21:05:27 +0000 | [diff] [blame] | 52 | AU.addPreservedID(LowerInvokePassID); |
Chris Lattner | de97b57 | 2004-12-13 20:00:02 +0000 | [diff] [blame] | 53 | } |
| 54 | |
Chris Lattner | 3b2106f | 2002-09-25 23:47:47 +0000 | [diff] [blame] | 55 | /// doPassInitialization - For the lower allocations pass, this ensures that |
| 56 | /// a module contains a declaration for a malloc and a free function. |
| 57 | /// |
| 58 | bool doInitialization(Module &M); |
Reid Spencer | 791a959 | 2004-12-07 08:11:36 +0000 | [diff] [blame] | 59 | |
Chris Lattner | de97b57 | 2004-12-13 20:00:02 +0000 | [diff] [blame] | 60 | virtual bool doInitialization(Function &F) { |
Devang Patel | 4f3096b | 2008-11-18 18:43:07 +0000 | [diff] [blame] | 61 | return doInitialization(*F.getParent()); |
Chris Lattner | de97b57 | 2004-12-13 20:00:02 +0000 | [diff] [blame] | 62 | } |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 63 | |
Chris Lattner | 3b2106f | 2002-09-25 23:47:47 +0000 | [diff] [blame] | 64 | /// runOnBasicBlock - This method does the actual work of converting |
| 65 | /// instructions over, assuming that the pass has already been initialized. |
| 66 | /// |
| 67 | bool runOnBasicBlock(BasicBlock &BB); |
| 68 | }; |
Chris Lattner | ade686e | 2002-05-07 19:02:48 +0000 | [diff] [blame] | 69 | } |
Chris Lattner | bd0ef77 | 2002-02-26 21:46:54 +0000 | [diff] [blame] | 70 | |
Dan Gohman | 844731a | 2008-05-13 00:00:25 +0000 | [diff] [blame] | 71 | char LowerAllocations::ID = 0; |
| 72 | static RegisterPass<LowerAllocations> |
| 73 | X("lowerallocs", "Lower allocations from instructions to calls"); |
| 74 | |
Chris Lattner | b3674e4 | 2006-05-02 04:24:36 +0000 | [diff] [blame] | 75 | // Publically exposed interface to pass... |
Dan Gohman | 6ddba2b | 2008-05-13 02:05:11 +0000 | [diff] [blame] | 76 | const PassInfo *const llvm::LowerAllocationsID = &X; |
Chris Lattner | ade686e | 2002-05-07 19:02:48 +0000 | [diff] [blame] | 77 | // createLowerAllocationsPass - Interface to this file... |
Devang Patel | 4d447f5 | 2007-01-25 23:23:25 +0000 | [diff] [blame] | 78 | Pass *llvm::createLowerAllocationsPass(bool LowerMallocArgToInteger) { |
Chris Lattner | 5f792c2 | 2005-03-03 01:03:43 +0000 | [diff] [blame] | 79 | return new LowerAllocations(LowerMallocArgToInteger); |
Chris Lattner | ade686e | 2002-05-07 19:02:48 +0000 | [diff] [blame] | 80 | } |
Chris Lattner | 96c466b | 2002-04-29 14:57:45 +0000 | [diff] [blame] | 81 | |
Chris Lattner | 1bffea0 | 2001-10-15 17:31:51 +0000 | [diff] [blame] | 82 | |
Chris Lattner | f4de63f | 2002-01-21 07:31:50 +0000 | [diff] [blame] | 83 | // doInitialization - For the lower allocations pass, this ensures that a |
Chris Lattner | 1bffea0 | 2001-10-15 17:31:51 +0000 | [diff] [blame] | 84 | // module contains a declaration for a malloc and a free function. |
| 85 | // |
| 86 | // This function is always successful. |
| 87 | // |
Chris Lattner | 7e70829 | 2002-06-25 16:13:24 +0000 | [diff] [blame] | 88 | bool LowerAllocations::doInitialization(Module &M) { |
Christopher Lamb | 43ad6b3 | 2007-12-17 01:12:55 +0000 | [diff] [blame] | 89 | const Type *BPTy = PointerType::getUnqual(Type::Int8Ty); |
Chris Lattner | b76efb7 | 2007-01-07 08:12:01 +0000 | [diff] [blame] | 90 | // Prototype malloc as "char* malloc(...)", because we don't know in |
| 91 | // doInitialization whether size_t is int or long. |
| 92 | FunctionType *FT = FunctionType::get(BPTy, std::vector<const Type*>(), true); |
| 93 | MallocFunc = M.getOrInsertFunction("malloc", FT); |
| 94 | FreeFunc = M.getOrInsertFunction("free" , Type::VoidTy, BPTy, (Type *)0); |
Chris Lattner | ade686e | 2002-05-07 19:02:48 +0000 | [diff] [blame] | 95 | return true; |
Chris Lattner | 1bffea0 | 2001-10-15 17:31:51 +0000 | [diff] [blame] | 96 | } |
| 97 | |
Chris Lattner | 8445372 | 2002-01-21 23:34:02 +0000 | [diff] [blame] | 98 | // runOnBasicBlock - This method does the actual work of converting |
Chris Lattner | 1bffea0 | 2001-10-15 17:31:51 +0000 | [diff] [blame] | 99 | // instructions over, assuming that the pass has already been initialized. |
| 100 | // |
Chris Lattner | 7e70829 | 2002-06-25 16:13:24 +0000 | [diff] [blame] | 101 | bool LowerAllocations::runOnBasicBlock(BasicBlock &BB) { |
Chris Lattner | 42c9c2c | 2001-10-18 05:27:33 +0000 | [diff] [blame] | 102 | bool Changed = false; |
Chris Lattner | 7e70829 | 2002-06-25 16:13:24 +0000 | [diff] [blame] | 103 | assert(MallocFunc && FreeFunc && "Pass not initialized!"); |
| 104 | |
| 105 | BasicBlock::InstListType &BBIL = BB.getInstList(); |
Chris Lattner | 1bffea0 | 2001-10-15 17:31:51 +0000 | [diff] [blame] | 106 | |
Chris Lattner | 5f792c2 | 2005-03-03 01:03:43 +0000 | [diff] [blame] | 107 | const TargetData &TD = getAnalysis<TargetData>(); |
| 108 | const Type *IntPtrTy = TD.getIntPtrType(); |
Chris Lattner | de97b57 | 2004-12-13 20:00:02 +0000 | [diff] [blame] | 109 | |
Chris Lattner | 1bffea0 | 2001-10-15 17:31:51 +0000 | [diff] [blame] | 110 | // Loop over all of the instructions, looking for malloc or free instructions |
Chris Lattner | 7e70829 | 2002-06-25 16:13:24 +0000 | [diff] [blame] | 111 | for (BasicBlock::iterator I = BB.begin(), E = BB.end(); I != E; ++I) { |
Chris Lattner | e408e25 | 2003-04-23 16:37:45 +0000 | [diff] [blame] | 112 | if (MallocInst *MI = dyn_cast<MallocInst>(I)) { |
Chris Lattner | 7e70829 | 2002-06-25 16:13:24 +0000 | [diff] [blame] | 113 | const Type *AllocTy = MI->getType()->getElementType(); |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 114 | |
Chris Lattner | 8bfc2f1 | 2004-07-15 01:08:08 +0000 | [diff] [blame] | 115 | // malloc(type) becomes sbyte *malloc(size) |
Chris Lattner | 5f792c2 | 2005-03-03 01:03:43 +0000 | [diff] [blame] | 116 | Value *MallocArg; |
| 117 | if (LowerMallocArgToInteger) |
Duncan Sands | ceb4d1a | 2009-01-12 20:38:59 +0000 | [diff] [blame] | 118 | MallocArg = ConstantInt::get(Type::Int64Ty, |
Duncan Sands | 777d230 | 2009-05-09 07:06:46 +0000 | [diff] [blame^] | 119 | TD.getTypeAllocSize(AllocTy)); |
Chris Lattner | 5f792c2 | 2005-03-03 01:03:43 +0000 | [diff] [blame] | 120 | else |
| 121 | MallocArg = ConstantExpr::getSizeOf(AllocTy); |
Reid Spencer | daa8e3c | 2006-12-12 09:17:08 +0000 | [diff] [blame] | 122 | MallocArg = ConstantExpr::getTruncOrBitCast(cast<Constant>(MallocArg), |
| 123 | IntPtrTy); |
Chris Lattner | 5f792c2 | 2005-03-03 01:03:43 +0000 | [diff] [blame] | 124 | |
Chris Lattner | 8bfc2f1 | 2004-07-15 01:08:08 +0000 | [diff] [blame] | 125 | if (MI->isArrayAllocation()) { |
Chris Lattner | de97b57 | 2004-12-13 20:00:02 +0000 | [diff] [blame] | 126 | if (isa<ConstantInt>(MallocArg) && |
Reid Spencer | 4cf735b | 2007-03-02 23:03:17 +0000 | [diff] [blame] | 127 | cast<ConstantInt>(MallocArg)->isOne()) { |
Chris Lattner | 8bfc2f1 | 2004-07-15 01:08:08 +0000 | [diff] [blame] | 128 | MallocArg = MI->getOperand(0); // Operand * 1 = Operand |
| 129 | } else if (Constant *CO = dyn_cast<Constant>(MI->getOperand(0))) { |
Reid Spencer | daa8e3c | 2006-12-12 09:17:08 +0000 | [diff] [blame] | 130 | CO = ConstantExpr::getIntegerCast(CO, IntPtrTy, false /*ZExt*/); |
Chris Lattner | 8bfc2f1 | 2004-07-15 01:08:08 +0000 | [diff] [blame] | 131 | MallocArg = ConstantExpr::getMul(CO, cast<Constant>(MallocArg)); |
| 132 | } else { |
Chris Lattner | de97b57 | 2004-12-13 20:00:02 +0000 | [diff] [blame] | 133 | Value *Scale = MI->getOperand(0); |
| 134 | if (Scale->getType() != IntPtrTy) |
Gabor Greif | 7cbd8a3 | 2008-05-16 19:29:10 +0000 | [diff] [blame] | 135 | Scale = CastInst::CreateIntegerCast(Scale, IntPtrTy, false /*ZExt*/, |
Reid Spencer | 7b06bd5 | 2006-12-13 00:50:17 +0000 | [diff] [blame] | 136 | "", I); |
Chris Lattner | de97b57 | 2004-12-13 20:00:02 +0000 | [diff] [blame] | 137 | |
Chris Lattner | 8bfc2f1 | 2004-07-15 01:08:08 +0000 | [diff] [blame] | 138 | // Multiply it by the array size if necessary... |
Gabor Greif | 7cbd8a3 | 2008-05-16 19:29:10 +0000 | [diff] [blame] | 139 | MallocArg = BinaryOperator::Create(Instruction::Mul, Scale, |
Chris Lattner | 8bfc2f1 | 2004-07-15 01:08:08 +0000 | [diff] [blame] | 140 | MallocArg, "", I); |
| 141 | } |
Chris Lattner | 1bffea0 | 2001-10-15 17:31:51 +0000 | [diff] [blame] | 142 | } |
Chris Lattner | b99df4f | 2004-02-28 18:51:45 +0000 | [diff] [blame] | 143 | |
Chris Lattner | b76efb7 | 2007-01-07 08:12:01 +0000 | [diff] [blame] | 144 | // Create the call to Malloc. |
Gabor Greif | 051a950 | 2008-04-06 20:25:17 +0000 | [diff] [blame] | 145 | CallInst *MCall = CallInst::Create(MallocFunc, MallocArg, "", I); |
Chris Lattner | a9e9211 | 2005-05-06 06:48:21 +0000 | [diff] [blame] | 146 | MCall->setTailCall(); |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 147 | |
Chris Lattner | 8445372 | 2002-01-21 23:34:02 +0000 | [diff] [blame] | 148 | // Create a cast instruction to convert to the right type... |
Chris Lattner | b99df4f | 2004-02-28 18:51:45 +0000 | [diff] [blame] | 149 | Value *MCast; |
| 150 | if (MCall->getType() != Type::VoidTy) |
Reid Spencer | 7b06bd5 | 2006-12-13 00:50:17 +0000 | [diff] [blame] | 151 | MCast = new BitCastInst(MCall, MI->getType(), "", I); |
Chris Lattner | b99df4f | 2004-02-28 18:51:45 +0000 | [diff] [blame] | 152 | else |
| 153 | MCast = Constant::getNullValue(MI->getType()); |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 154 | |
Chris Lattner | 8445372 | 2002-01-21 23:34:02 +0000 | [diff] [blame] | 155 | // Replace all uses of the old malloc inst with the cast inst |
| 156 | MI->replaceAllUsesWith(MCast); |
Chris Lattner | 1d608ab | 2002-09-10 22:38:47 +0000 | [diff] [blame] | 157 | I = --BBIL.erase(I); // remove and delete the malloc instr... |
Chris Lattner | 8445372 | 2002-01-21 23:34:02 +0000 | [diff] [blame] | 158 | Changed = true; |
Chris Lattner | 3dec1f2 | 2002-05-10 15:38:35 +0000 | [diff] [blame] | 159 | ++NumLowered; |
Chris Lattner | e408e25 | 2003-04-23 16:37:45 +0000 | [diff] [blame] | 160 | } else if (FreeInst *FI = dyn_cast<FreeInst>(I)) { |
Christopher Lamb | 43ad6b3 | 2007-12-17 01:12:55 +0000 | [diff] [blame] | 161 | Value *PtrCast = |
| 162 | new BitCastInst(FI->getOperand(0), |
| 163 | PointerType::getUnqual(Type::Int8Ty), "", I); |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 164 | |
Chris Lattner | 8445372 | 2002-01-21 23:34:02 +0000 | [diff] [blame] | 165 | // Insert a call to the free function... |
Gabor Greif | 051a950 | 2008-04-06 20:25:17 +0000 | [diff] [blame] | 166 | CallInst::Create(FreeFunc, PtrCast, "", I)->setTailCall(); |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 167 | |
Chris Lattner | 8445372 | 2002-01-21 23:34:02 +0000 | [diff] [blame] | 168 | // Delete the old free instruction |
Chris Lattner | 1d608ab | 2002-09-10 22:38:47 +0000 | [diff] [blame] | 169 | I = --BBIL.erase(I); |
Chris Lattner | 8445372 | 2002-01-21 23:34:02 +0000 | [diff] [blame] | 170 | Changed = true; |
Chris Lattner | 3dec1f2 | 2002-05-10 15:38:35 +0000 | [diff] [blame] | 171 | ++NumLowered; |
Chris Lattner | 1bffea0 | 2001-10-15 17:31:51 +0000 | [diff] [blame] | 172 | } |
| 173 | } |
| 174 | |
Chris Lattner | 42c9c2c | 2001-10-18 05:27:33 +0000 | [diff] [blame] | 175 | return Changed; |
Chris Lattner | 1bffea0 | 2001-10-15 17:31:51 +0000 | [diff] [blame] | 176 | } |
Brian Gaeke | d0fde30 | 2003-11-11 22:41:34 +0000 | [diff] [blame] | 177 | |