Chris Lattner | bda28f7 | 2002-03-28 18:08:31 +0000 | [diff] [blame] | 1 | //===-- PoolAllocate.cpp - Pool Allocation Pass ---------------------------===// |
| 2 | // |
| 3 | // This transform changes programs so that disjoint data structures are |
| 4 | // allocated out of different pools of memory, increasing locality and shrinking |
| 5 | // pointer size. |
| 6 | // |
Chris Lattner | 09b9212 | 2002-04-15 22:42:23 +0000 | [diff] [blame] | 7 | // This pass requires a DCE & instcombine pass to be run after it for best |
| 8 | // results. |
| 9 | // |
Chris Lattner | bda28f7 | 2002-03-28 18:08:31 +0000 | [diff] [blame] | 10 | //===----------------------------------------------------------------------===// |
| 11 | |
| 12 | #include "llvm/Transforms/IPO/PoolAllocate.h" |
Chris Lattner | a744451 | 2002-03-29 19:05:48 +0000 | [diff] [blame] | 13 | #include "llvm/Transforms/CloneFunction.h" |
Chris Lattner | bda28f7 | 2002-03-28 18:08:31 +0000 | [diff] [blame] | 14 | #include "llvm/Analysis/DataStructure.h" |
Chris Lattner | 4c7f3df | 2002-03-30 04:02:31 +0000 | [diff] [blame] | 15 | #include "llvm/Analysis/DataStructureGraph.h" |
Chris Lattner | d2d3a16 | 2002-03-29 03:40:59 +0000 | [diff] [blame] | 16 | #include "llvm/Module.h" |
| 17 | #include "llvm/Function.h" |
Chris Lattner | 42a4127 | 2002-04-09 18:37:46 +0000 | [diff] [blame] | 18 | #include "llvm/BasicBlock.h" |
Chris Lattner | d2d3a16 | 2002-03-29 03:40:59 +0000 | [diff] [blame] | 19 | #include "llvm/iMemory.h" |
Chris Lattner | 54ce13f | 2002-03-29 05:50:20 +0000 | [diff] [blame] | 20 | #include "llvm/iTerminators.h" |
Chris Lattner | 5146a7d | 2002-04-12 20:23:15 +0000 | [diff] [blame] | 21 | #include "llvm/iPHINode.h" |
Chris Lattner | 54ce13f | 2002-03-29 05:50:20 +0000 | [diff] [blame] | 22 | #include "llvm/iOther.h" |
Chris Lattner | 5146a7d | 2002-04-12 20:23:15 +0000 | [diff] [blame] | 23 | #include "llvm/DerivedTypes.h" |
Chris Lattner | 31bcdb8 | 2002-04-28 19:55:58 +0000 | [diff] [blame^] | 24 | #include "llvm/Constants.h" |
Chris Lattner | 54ce13f | 2002-03-29 05:50:20 +0000 | [diff] [blame] | 25 | #include "llvm/Target/TargetData.h" |
Chris Lattner | 9d3493e | 2002-03-29 21:25:19 +0000 | [diff] [blame] | 26 | #include "llvm/Support/InstVisitor.h" |
Chris Lattner | 73e2142 | 2002-04-09 19:48:49 +0000 | [diff] [blame] | 27 | #include "llvm/Argument.h" |
Chris Lattner | 4c7f3df | 2002-03-30 04:02:31 +0000 | [diff] [blame] | 28 | #include "Support/DepthFirstIterator.h" |
Chris Lattner | 54ce13f | 2002-03-29 05:50:20 +0000 | [diff] [blame] | 29 | #include "Support/STLExtras.h" |
Chris Lattner | d2d3a16 | 2002-03-29 03:40:59 +0000 | [diff] [blame] | 30 | #include <algorithm> |
Chris Lattner | bda28f7 | 2002-03-28 18:08:31 +0000 | [diff] [blame] | 31 | |
Chris Lattner | 5146a7d | 2002-04-12 20:23:15 +0000 | [diff] [blame] | 32 | // DEBUG_CREATE_POOLS - Enable this to turn on debug output for the pool |
| 33 | // creation phase in the top level function of a transformed data structure. |
| 34 | // |
Chris Lattner | 3e0e520 | 2002-04-14 06:14:41 +0000 | [diff] [blame] | 35 | //#define DEBUG_CREATE_POOLS 1 |
| 36 | |
| 37 | // DEBUG_TRANSFORM_PROGRESS - Enable this to get lots of debug output on what |
| 38 | // the transformation is doing. |
| 39 | // |
| 40 | //#define DEBUG_TRANSFORM_PROGRESS 1 |
Chris Lattner | 5146a7d | 2002-04-12 20:23:15 +0000 | [diff] [blame] | 41 | |
Chris Lattner | 09b9212 | 2002-04-15 22:42:23 +0000 | [diff] [blame] | 42 | // DEBUG_POOLBASE_LOAD_ELIMINATOR - Turn this on to get statistics about how |
| 43 | // many static loads were eliminated from a function... |
| 44 | // |
| 45 | #define DEBUG_POOLBASE_LOAD_ELIMINATOR 1 |
| 46 | |
Chris Lattner | 441d25a | 2002-04-13 23:13:18 +0000 | [diff] [blame] | 47 | #include "Support/CommandLine.h" |
| 48 | enum PtrSize { |
| 49 | Ptr8bits, Ptr16bits, Ptr32bits |
| 50 | }; |
| 51 | |
| 52 | static cl::Enum<enum PtrSize> ReqPointerSize("ptrsize", 0, |
Chris Lattner | 3e0e520 | 2002-04-14 06:14:41 +0000 | [diff] [blame] | 53 | "Set pointer size for -poolalloc pass", |
Chris Lattner | 441d25a | 2002-04-13 23:13:18 +0000 | [diff] [blame] | 54 | clEnumValN(Ptr32bits, "32", "Use 32 bit indices for pointers"), |
| 55 | clEnumValN(Ptr16bits, "16", "Use 16 bit indices for pointers"), |
| 56 | clEnumValN(Ptr8bits , "8", "Use 8 bit indices for pointers"), 0); |
| 57 | |
Chris Lattner | 09b9212 | 2002-04-15 22:42:23 +0000 | [diff] [blame] | 58 | static cl::Flag DisableRLE("no-pool-load-elim", "Disable pool load elimination after poolalloc pass", cl::Hidden); |
| 59 | |
Chris Lattner | 5146a7d | 2002-04-12 20:23:15 +0000 | [diff] [blame] | 60 | const Type *POINTERTYPE; |
Chris Lattner | d250f42 | 2002-03-29 17:13:46 +0000 | [diff] [blame] | 61 | |
Chris Lattner | 54ce13f | 2002-03-29 05:50:20 +0000 | [diff] [blame] | 62 | // FIXME: This is dependant on the sparc backend layout conventions!! |
| 63 | static TargetData TargetData("test"); |
| 64 | |
Chris Lattner | 441d25a | 2002-04-13 23:13:18 +0000 | [diff] [blame] | 65 | static const Type *getPointerTransformedType(const Type *Ty) { |
| 66 | if (PointerType *PT = dyn_cast<PointerType>(Ty)) { |
| 67 | return POINTERTYPE; |
| 68 | } else if (StructType *STy = dyn_cast<StructType>(Ty)) { |
| 69 | vector<const Type *> NewElTypes; |
| 70 | NewElTypes.reserve(STy->getElementTypes().size()); |
| 71 | for (StructType::ElementTypes::const_iterator |
| 72 | I = STy->getElementTypes().begin(), |
| 73 | E = STy->getElementTypes().end(); I != E; ++I) |
| 74 | NewElTypes.push_back(getPointerTransformedType(*I)); |
| 75 | return StructType::get(NewElTypes); |
| 76 | } else if (ArrayType *ATy = dyn_cast<ArrayType>(Ty)) { |
| 77 | return ArrayType::get(getPointerTransformedType(ATy->getElementType()), |
| 78 | ATy->getNumElements()); |
| 79 | } else { |
| 80 | assert(Ty->isPrimitiveType() && "Unknown derived type!"); |
| 81 | return Ty; |
| 82 | } |
| 83 | } |
| 84 | |
Chris Lattner | bda28f7 | 2002-03-28 18:08:31 +0000 | [diff] [blame] | 85 | namespace { |
Chris Lattner | 5146a7d | 2002-04-12 20:23:15 +0000 | [diff] [blame] | 86 | struct PoolInfo { |
| 87 | DSNode *Node; // The node this pool allocation represents |
| 88 | Value *Handle; // LLVM value of the pool in the current context |
| 89 | const Type *NewType; // The transformed type of the memory objects |
| 90 | const Type *PoolType; // The type of the pool |
| 91 | |
| 92 | const Type *getOldType() const { return Node->getType(); } |
| 93 | |
| 94 | PoolInfo() { // Define a default ctor for map::operator[] |
| 95 | cerr << "Map subscript used to get element that doesn't exist!\n"; |
| 96 | abort(); // Invalid |
| 97 | } |
| 98 | |
| 99 | PoolInfo(DSNode *N, Value *H, const Type *NT, const Type *PT) |
| 100 | : Node(N), Handle(H), NewType(NT), PoolType(PT) { |
| 101 | // Handle can be null... |
| 102 | assert(N && NT && PT && "Pool info null!"); |
| 103 | } |
| 104 | |
| 105 | PoolInfo(DSNode *N) : Node(N), Handle(0), NewType(0), PoolType(0) { |
| 106 | assert(N && "Invalid pool info!"); |
| 107 | |
| 108 | // The new type of the memory object is the same as the old type, except |
| 109 | // that all of the pointer values are replaced with POINTERTYPE values. |
Chris Lattner | 441d25a | 2002-04-13 23:13:18 +0000 | [diff] [blame] | 110 | NewType = getPointerTransformedType(getOldType()); |
Chris Lattner | 5146a7d | 2002-04-12 20:23:15 +0000 | [diff] [blame] | 111 | } |
| 112 | }; |
| 113 | |
Chris Lattner | d250f42 | 2002-03-29 17:13:46 +0000 | [diff] [blame] | 114 | // ScalarInfo - Information about an LLVM value that we know points to some |
| 115 | // datastructure we are processing. |
| 116 | // |
| 117 | struct ScalarInfo { |
Chris Lattner | cfb5f4c | 2002-03-30 09:12:35 +0000 | [diff] [blame] | 118 | Value *Val; // Scalar value in Current Function |
Chris Lattner | 5146a7d | 2002-04-12 20:23:15 +0000 | [diff] [blame] | 119 | PoolInfo Pool; // The pool the scalar points into |
Chris Lattner | d250f42 | 2002-03-29 17:13:46 +0000 | [diff] [blame] | 120 | |
Chris Lattner | 5146a7d | 2002-04-12 20:23:15 +0000 | [diff] [blame] | 121 | ScalarInfo(Value *V, const PoolInfo &PI) : Val(V), Pool(PI) { |
| 122 | assert(V && "Null value passed to ScalarInfo ctor!"); |
Chris Lattner | cfb5f4c | 2002-03-30 09:12:35 +0000 | [diff] [blame] | 123 | } |
Chris Lattner | d250f42 | 2002-03-29 17:13:46 +0000 | [diff] [blame] | 124 | }; |
| 125 | |
Chris Lattner | 4c7f3df | 2002-03-30 04:02:31 +0000 | [diff] [blame] | 126 | // CallArgInfo - Information on one operand for a call that got expanded. |
| 127 | struct CallArgInfo { |
Chris Lattner | cfb5f4c | 2002-03-30 09:12:35 +0000 | [diff] [blame] | 128 | int ArgNo; // Call argument number this corresponds to |
| 129 | DSNode *Node; // The graph node for the pool |
| 130 | Value *PoolHandle; // The LLVM value that is the pool pointer |
Chris Lattner | 4c7f3df | 2002-03-30 04:02:31 +0000 | [diff] [blame] | 131 | |
Chris Lattner | cfb5f4c | 2002-03-30 09:12:35 +0000 | [diff] [blame] | 132 | CallArgInfo(int Arg, DSNode *N, Value *PH) |
| 133 | : ArgNo(Arg), Node(N), PoolHandle(PH) { |
| 134 | assert(Arg >= -1 && N && PH && "Illegal values to CallArgInfo ctor!"); |
Chris Lattner | 4c7f3df | 2002-03-30 04:02:31 +0000 | [diff] [blame] | 135 | } |
| 136 | |
Chris Lattner | cfb5f4c | 2002-03-30 09:12:35 +0000 | [diff] [blame] | 137 | // operator< when sorting, sort by argument number. |
Chris Lattner | 4c7f3df | 2002-03-30 04:02:31 +0000 | [diff] [blame] | 138 | bool operator<(const CallArgInfo &CAI) const { |
| 139 | return ArgNo < CAI.ArgNo; |
| 140 | } |
| 141 | }; |
| 142 | |
Chris Lattner | d250f42 | 2002-03-29 17:13:46 +0000 | [diff] [blame] | 143 | // TransformFunctionInfo - Information about how a function eeds to be |
| 144 | // transformed. |
| 145 | // |
| 146 | struct TransformFunctionInfo { |
| 147 | // ArgInfo - Maintain information about the arguments that need to be |
Chris Lattner | 5146a7d | 2002-04-12 20:23:15 +0000 | [diff] [blame] | 148 | // processed. Each CallArgInfo corresponds to an argument that needs to |
| 149 | // have a pool pointer passed into the transformed function with it. |
Chris Lattner | d250f42 | 2002-03-29 17:13:46 +0000 | [diff] [blame] | 150 | // |
| 151 | // As a special case, "argument" number -1 corresponds to the return value. |
| 152 | // |
Chris Lattner | 4c7f3df | 2002-03-30 04:02:31 +0000 | [diff] [blame] | 153 | vector<CallArgInfo> ArgInfo; |
Chris Lattner | d250f42 | 2002-03-29 17:13:46 +0000 | [diff] [blame] | 154 | |
| 155 | // Func - The function to be transformed... |
| 156 | Function *Func; |
| 157 | |
Chris Lattner | cfb5f4c | 2002-03-30 09:12:35 +0000 | [diff] [blame] | 158 | // The call instruction that is used to map CallArgInfo PoolHandle values |
| 159 | // into the new function values. |
| 160 | CallInst *Call; |
| 161 | |
Chris Lattner | d250f42 | 2002-03-29 17:13:46 +0000 | [diff] [blame] | 162 | // default ctor... |
Chris Lattner | cfb5f4c | 2002-03-30 09:12:35 +0000 | [diff] [blame] | 163 | TransformFunctionInfo() : Func(0), Call(0) {} |
Chris Lattner | d250f42 | 2002-03-29 17:13:46 +0000 | [diff] [blame] | 164 | |
Chris Lattner | 4c7f3df | 2002-03-30 04:02:31 +0000 | [diff] [blame] | 165 | bool operator<(const TransformFunctionInfo &TFI) const { |
Chris Lattner | a744451 | 2002-03-29 19:05:48 +0000 | [diff] [blame] | 166 | if (Func < TFI.Func) return true; |
| 167 | if (Func > TFI.Func) return false; |
Chris Lattner | a744451 | 2002-03-29 19:05:48 +0000 | [diff] [blame] | 168 | if (ArgInfo.size() < TFI.ArgInfo.size()) return true; |
| 169 | if (ArgInfo.size() > TFI.ArgInfo.size()) return false; |
Chris Lattner | 4c7f3df | 2002-03-30 04:02:31 +0000 | [diff] [blame] | 170 | return ArgInfo < TFI.ArgInfo; |
Chris Lattner | d250f42 | 2002-03-29 17:13:46 +0000 | [diff] [blame] | 171 | } |
| 172 | |
| 173 | void finalizeConstruction() { |
| 174 | // Sort the vector so that the return value is first, followed by the |
Chris Lattner | cfb5f4c | 2002-03-30 09:12:35 +0000 | [diff] [blame] | 175 | // argument records, in order. Note that this must be a stable sort so |
| 176 | // that the entries with the same sorting criteria (ie they are multiple |
| 177 | // pool entries for the same argument) are kept in depth first order. |
| 178 | stable_sort(ArgInfo.begin(), ArgInfo.end()); |
Chris Lattner | d250f42 | 2002-03-29 17:13:46 +0000 | [diff] [blame] | 179 | } |
Chris Lattner | 3b87167 | 2002-04-18 14:43:30 +0000 | [diff] [blame] | 180 | |
| 181 | // addCallInfo - For a specified function call CI, figure out which pool |
| 182 | // descriptors need to be passed in as arguments, and which arguments need |
| 183 | // to be transformed into indices. If Arg != -1, the specified call |
| 184 | // argument is passed in as a pointer to a data structure. |
| 185 | // |
| 186 | void addCallInfo(DataStructure *DS, CallInst *CI, int Arg, |
| 187 | DSNode *GraphNode, map<DSNode*, PoolInfo> &PoolDescs); |
| 188 | |
| 189 | // Make sure that all dependant arguments are added to this transformation |
| 190 | // info. For example, if we call foo(null, P) and foo treats it's first and |
| 191 | // second arguments as belonging to the same data structure, the we MUST add |
| 192 | // entries to know that the null needs to be transformed into an index as |
| 193 | // well. |
| 194 | // |
| 195 | void ensureDependantArgumentsIncluded(DataStructure *DS, |
| 196 | map<DSNode*, PoolInfo> &PoolDescs); |
Chris Lattner | d250f42 | 2002-03-29 17:13:46 +0000 | [diff] [blame] | 197 | }; |
| 198 | |
| 199 | |
| 200 | // Define the pass class that we implement... |
Chris Lattner | 5146a7d | 2002-04-12 20:23:15 +0000 | [diff] [blame] | 201 | struct PoolAllocate : public Pass { |
Chris Lattner | d2d3a16 | 2002-03-29 03:40:59 +0000 | [diff] [blame] | 202 | PoolAllocate() { |
Chris Lattner | 441d25a | 2002-04-13 23:13:18 +0000 | [diff] [blame] | 203 | switch (ReqPointerSize) { |
| 204 | case Ptr32bits: POINTERTYPE = Type::UIntTy; break; |
| 205 | case Ptr16bits: POINTERTYPE = Type::UShortTy; break; |
| 206 | case Ptr8bits: POINTERTYPE = Type::UByteTy; break; |
| 207 | } |
Chris Lattner | d2d3a16 | 2002-03-29 03:40:59 +0000 | [diff] [blame] | 208 | |
| 209 | CurModule = 0; DS = 0; |
| 210 | PoolInit = PoolDestroy = PoolAlloc = PoolFree = 0; |
Chris Lattner | bda28f7 | 2002-03-28 18:08:31 +0000 | [diff] [blame] | 211 | } |
| 212 | |
Chris Lattner | 5146a7d | 2002-04-12 20:23:15 +0000 | [diff] [blame] | 213 | // getPoolType - Get the type used by the backend for a pool of a particular |
| 214 | // type. This pool record is used to allocate nodes of type NodeType. |
| 215 | // |
| 216 | // Here, PoolTy = { NodeType*, sbyte*, uint }* |
| 217 | // |
| 218 | const StructType *getPoolType(const Type *NodeType) { |
| 219 | vector<const Type*> PoolElements; |
| 220 | PoolElements.push_back(PointerType::get(NodeType)); |
| 221 | PoolElements.push_back(PointerType::get(Type::SByteTy)); |
| 222 | PoolElements.push_back(Type::UIntTy); |
Chris Lattner | 027a675 | 2002-04-13 19:25:57 +0000 | [diff] [blame] | 223 | StructType *Result = StructType::get(PoolElements); |
| 224 | |
| 225 | // Add a name to the symbol table to correspond to the backend |
| 226 | // representation of this pool... |
| 227 | assert(CurModule && "No current module!?"); |
| 228 | string Name = CurModule->getTypeName(NodeType); |
| 229 | if (Name.empty()) Name = CurModule->getTypeName(PoolElements[0]); |
| 230 | CurModule->addTypeName(Name+"oolbe", Result); |
| 231 | |
| 232 | return Result; |
Chris Lattner | 5146a7d | 2002-04-12 20:23:15 +0000 | [diff] [blame] | 233 | } |
| 234 | |
Chris Lattner | d2d3a16 | 2002-03-29 03:40:59 +0000 | [diff] [blame] | 235 | bool run(Module *M); |
| 236 | |
Chris Lattner | f57b845 | 2002-04-27 06:56:12 +0000 | [diff] [blame] | 237 | // getAnalysisUsage - This function requires data structure information |
Chris Lattner | d2d3a16 | 2002-03-29 03:40:59 +0000 | [diff] [blame] | 238 | // to be able to see what is pool allocatable. |
Chris Lattner | bda28f7 | 2002-03-28 18:08:31 +0000 | [diff] [blame] | 239 | // |
Chris Lattner | f57b845 | 2002-04-27 06:56:12 +0000 | [diff] [blame] | 240 | virtual void getAnalysisUsage(AnalysisUsage &AU) const { |
| 241 | AU.addRequired(DataStructure::ID); |
Chris Lattner | bda28f7 | 2002-03-28 18:08:31 +0000 | [diff] [blame] | 242 | } |
Chris Lattner | d2d3a16 | 2002-03-29 03:40:59 +0000 | [diff] [blame] | 243 | |
Chris Lattner | 9d3493e | 2002-03-29 21:25:19 +0000 | [diff] [blame] | 244 | public: |
Chris Lattner | d2d3a16 | 2002-03-29 03:40:59 +0000 | [diff] [blame] | 245 | // CurModule - The module being processed. |
| 246 | Module *CurModule; |
| 247 | |
| 248 | // DS - The data structure graph for the module being processed. |
| 249 | DataStructure *DS; |
| 250 | |
| 251 | // Prototypes that we add to support pool allocation... |
Chris Lattner | 8e34333 | 2002-04-27 02:29:32 +0000 | [diff] [blame] | 252 | Function *PoolInit, *PoolDestroy, *PoolAlloc, *PoolAllocArray, *PoolFree; |
Chris Lattner | d2d3a16 | 2002-03-29 03:40:59 +0000 | [diff] [blame] | 253 | |
Chris Lattner | cfb5f4c | 2002-03-30 09:12:35 +0000 | [diff] [blame] | 254 | // The map of already transformed functions... note that the keys of this |
| 255 | // map do not have meaningful values for 'Call' or the 'PoolHandle' elements |
| 256 | // of the ArgInfo elements. |
| 257 | // |
Chris Lattner | d250f42 | 2002-03-29 17:13:46 +0000 | [diff] [blame] | 258 | map<TransformFunctionInfo, Function*> TransformedFunctions; |
| 259 | |
| 260 | // getTransformedFunction - Get a transformed function, or return null if |
| 261 | // the function specified hasn't been transformed yet. |
| 262 | // |
| 263 | Function *getTransformedFunction(TransformFunctionInfo &TFI) const { |
| 264 | map<TransformFunctionInfo, Function*>::const_iterator I = |
| 265 | TransformedFunctions.find(TFI); |
| 266 | if (I != TransformedFunctions.end()) return I->second; |
| 267 | return 0; |
| 268 | } |
| 269 | |
| 270 | |
Chris Lattner | 5146a7d | 2002-04-12 20:23:15 +0000 | [diff] [blame] | 271 | // addPoolPrototypes - Add prototypes for the pool functions to the |
| 272 | // specified module and update the Pool* instance variables to point to |
| 273 | // them. |
Chris Lattner | d2d3a16 | 2002-03-29 03:40:59 +0000 | [diff] [blame] | 274 | // |
| 275 | void addPoolPrototypes(Module *M); |
| 276 | |
Chris Lattner | 9d89190 | 2002-03-29 06:21:38 +0000 | [diff] [blame] | 277 | |
| 278 | // CreatePools - Insert instructions into the function we are processing to |
| 279 | // create all of the memory pool objects themselves. This also inserts |
| 280 | // destruction code. Add an alloca for each pool that is allocated to the |
Chris Lattner | 5146a7d | 2002-04-12 20:23:15 +0000 | [diff] [blame] | 281 | // PoolDescs map. |
Chris Lattner | 9d89190 | 2002-03-29 06:21:38 +0000 | [diff] [blame] | 282 | // |
| 283 | void CreatePools(Function *F, const vector<AllocDSNode*> &Allocs, |
Chris Lattner | 5146a7d | 2002-04-12 20:23:15 +0000 | [diff] [blame] | 284 | map<DSNode*, PoolInfo> &PoolDescs); |
Chris Lattner | 9d89190 | 2002-03-29 06:21:38 +0000 | [diff] [blame] | 285 | |
Chris Lattner | d2d3a16 | 2002-03-29 03:40:59 +0000 | [diff] [blame] | 286 | // processFunction - Convert a function to use pool allocation where |
| 287 | // available. |
| 288 | // |
| 289 | bool processFunction(Function *F); |
Chris Lattner | d250f42 | 2002-03-29 17:13:46 +0000 | [diff] [blame] | 290 | |
Chris Lattner | cfb5f4c | 2002-03-30 09:12:35 +0000 | [diff] [blame] | 291 | // transformFunctionBody - This transforms the instruction in 'F' to use the |
Chris Lattner | 5146a7d | 2002-04-12 20:23:15 +0000 | [diff] [blame] | 292 | // pools specified in PoolDescs when modifying data structure nodes |
| 293 | // specified in the PoolDescs map. IPFGraph is the closed data structure |
| 294 | // graph for F, of which the PoolDescriptor nodes come from. |
Chris Lattner | cfb5f4c | 2002-03-30 09:12:35 +0000 | [diff] [blame] | 295 | // |
| 296 | void transformFunctionBody(Function *F, FunctionDSGraph &IPFGraph, |
Chris Lattner | 5146a7d | 2002-04-12 20:23:15 +0000 | [diff] [blame] | 297 | map<DSNode*, PoolInfo> &PoolDescs); |
Chris Lattner | d250f42 | 2002-03-29 17:13:46 +0000 | [diff] [blame] | 298 | |
| 299 | // transformFunction - Transform the specified function the specified way. |
| 300 | // It we have already transformed that function that way, don't do anything. |
Chris Lattner | cfb5f4c | 2002-03-30 09:12:35 +0000 | [diff] [blame] | 301 | // The nodes in the TransformFunctionInfo come out of callers data structure |
Chris Lattner | 5146a7d | 2002-04-12 20:23:15 +0000 | [diff] [blame] | 302 | // graph, and the PoolDescs passed in are the caller's. |
Chris Lattner | d250f42 | 2002-03-29 17:13:46 +0000 | [diff] [blame] | 303 | // |
Chris Lattner | cfb5f4c | 2002-03-30 09:12:35 +0000 | [diff] [blame] | 304 | void transformFunction(TransformFunctionInfo &TFI, |
Chris Lattner | 5146a7d | 2002-04-12 20:23:15 +0000 | [diff] [blame] | 305 | FunctionDSGraph &CallerIPGraph, |
| 306 | map<DSNode*, PoolInfo> &PoolDescs); |
Chris Lattner | d250f42 | 2002-03-29 17:13:46 +0000 | [diff] [blame] | 307 | |
Chris Lattner | bda28f7 | 2002-03-28 18:08:31 +0000 | [diff] [blame] | 308 | }; |
| 309 | } |
| 310 | |
Chris Lattner | d250f42 | 2002-03-29 17:13:46 +0000 | [diff] [blame] | 311 | // isNotPoolableAlloc - This is a predicate that returns true if the specified |
Chris Lattner | d2d3a16 | 2002-03-29 03:40:59 +0000 | [diff] [blame] | 312 | // allocation node in a data structure graph is eligable for pool allocation. |
| 313 | // |
| 314 | static bool isNotPoolableAlloc(const AllocDSNode *DS) { |
Chris Lattner | 54ce13f | 2002-03-29 05:50:20 +0000 | [diff] [blame] | 315 | if (DS->isAllocaNode()) return true; // Do not pool allocate alloca's. |
Chris Lattner | 54ce13f | 2002-03-29 05:50:20 +0000 | [diff] [blame] | 316 | return false; |
Chris Lattner | d2d3a16 | 2002-03-29 03:40:59 +0000 | [diff] [blame] | 317 | } |
| 318 | |
Chris Lattner | d2d3a16 | 2002-03-29 03:40:59 +0000 | [diff] [blame] | 319 | // processFunction - Convert a function to use pool allocation where |
| 320 | // available. |
| 321 | // |
| 322 | bool PoolAllocate::processFunction(Function *F) { |
| 323 | // Get the closed datastructure graph for the current function... if there are |
| 324 | // any allocations in this graph that are not escaping, we need to pool |
| 325 | // allocate them here! |
| 326 | // |
| 327 | FunctionDSGraph &IPGraph = DS->getClosedDSGraph(F); |
| 328 | |
| 329 | // Get all of the allocations that do not escape the current function. Since |
| 330 | // they are still live (they exist in the graph at all), this means we must |
| 331 | // have scalar references to these nodes, but the scalars are never returned. |
| 332 | // |
Chris Lattner | d250f42 | 2002-03-29 17:13:46 +0000 | [diff] [blame] | 333 | vector<AllocDSNode*> Allocs; |
Chris Lattner | d2d3a16 | 2002-03-29 03:40:59 +0000 | [diff] [blame] | 334 | IPGraph.getNonEscapingAllocations(Allocs); |
| 335 | |
| 336 | // Filter out allocations that we cannot handle. Currently, this includes |
| 337 | // variable sized array allocations and alloca's (which we do not want to |
| 338 | // pool allocate) |
| 339 | // |
| 340 | Allocs.erase(remove_if(Allocs.begin(), Allocs.end(), isNotPoolableAlloc), |
| 341 | Allocs.end()); |
| 342 | |
| 343 | |
| 344 | if (Allocs.empty()) return false; // Nothing to do. |
| 345 | |
Chris Lattner | 3b87167 | 2002-04-18 14:43:30 +0000 | [diff] [blame] | 346 | #ifdef DEBUG_TRANSFORM_PROGRESS |
| 347 | cerr << "Transforming Function: " << F->getName() << "\n"; |
| 348 | #endif |
| 349 | |
Chris Lattner | d250f42 | 2002-03-29 17:13:46 +0000 | [diff] [blame] | 350 | // Insert instructions into the function we are processing to create all of |
| 351 | // the memory pool objects themselves. This also inserts destruction code. |
Chris Lattner | 5146a7d | 2002-04-12 20:23:15 +0000 | [diff] [blame] | 352 | // This fills in the PoolDescs map to associate the alloc node with the |
Chris Lattner | 4c7f3df | 2002-03-30 04:02:31 +0000 | [diff] [blame] | 353 | // allocation of the memory pool corresponding to it. |
Chris Lattner | d250f42 | 2002-03-29 17:13:46 +0000 | [diff] [blame] | 354 | // |
Chris Lattner | 5146a7d | 2002-04-12 20:23:15 +0000 | [diff] [blame] | 355 | map<DSNode*, PoolInfo> PoolDescs; |
| 356 | CreatePools(F, Allocs, PoolDescs); |
Chris Lattner | d250f42 | 2002-03-29 17:13:46 +0000 | [diff] [blame] | 357 | |
Chris Lattner | 3e0e520 | 2002-04-14 06:14:41 +0000 | [diff] [blame] | 358 | #ifdef DEBUG_TRANSFORM_PROGRESS |
Chris Lattner | 5146a7d | 2002-04-12 20:23:15 +0000 | [diff] [blame] | 359 | cerr << "Transformed Entry Function: \n" << F; |
Chris Lattner | 3e0e520 | 2002-04-14 06:14:41 +0000 | [diff] [blame] | 360 | #endif |
Chris Lattner | 5146a7d | 2002-04-12 20:23:15 +0000 | [diff] [blame] | 361 | |
| 362 | // Now we need to figure out what called functions we need to transform, and |
Chris Lattner | d250f42 | 2002-03-29 17:13:46 +0000 | [diff] [blame] | 363 | // how. To do this, we look at all of the scalars, seeing which functions are |
| 364 | // either used as a scalar value (so they return a data structure), or are |
| 365 | // passed one of our scalar values. |
| 366 | // |
Chris Lattner | 5146a7d | 2002-04-12 20:23:15 +0000 | [diff] [blame] | 367 | transformFunctionBody(F, IPGraph, PoolDescs); |
Chris Lattner | d250f42 | 2002-03-29 17:13:46 +0000 | [diff] [blame] | 368 | |
| 369 | return true; |
| 370 | } |
| 371 | |
Chris Lattner | 9d3493e | 2002-03-29 21:25:19 +0000 | [diff] [blame] | 372 | |
Chris Lattner | 5146a7d | 2002-04-12 20:23:15 +0000 | [diff] [blame] | 373 | //===----------------------------------------------------------------------===// |
| 374 | // |
| 375 | // NewInstructionCreator - This class is used to traverse the function being |
| 376 | // modified, changing each instruction visit'ed to use and provide pointer |
| 377 | // indexes instead of real pointers. This is what changes the body of a |
| 378 | // function to use pool allocation. |
| 379 | // |
| 380 | class NewInstructionCreator : public InstVisitor<NewInstructionCreator> { |
Chris Lattner | 9d3493e | 2002-03-29 21:25:19 +0000 | [diff] [blame] | 381 | PoolAllocate &PoolAllocator; |
| 382 | vector<ScalarInfo> &Scalars; |
| 383 | map<CallInst*, TransformFunctionInfo> &CallMap; |
Chris Lattner | 5146a7d | 2002-04-12 20:23:15 +0000 | [diff] [blame] | 384 | map<Value*, Value*> &XFormMap; // Map old pointers to new indexes |
Chris Lattner | 9d3493e | 2002-03-29 21:25:19 +0000 | [diff] [blame] | 385 | |
Chris Lattner | 5146a7d | 2002-04-12 20:23:15 +0000 | [diff] [blame] | 386 | struct RefToUpdate { |
| 387 | Instruction *I; // Instruction to update |
| 388 | unsigned OpNum; // Operand number to update |
| 389 | Value *OldVal; // The old value it had |
| 390 | |
| 391 | RefToUpdate(Instruction *i, unsigned o, Value *ov) |
| 392 | : I(i), OpNum(o), OldVal(ov) {} |
| 393 | }; |
| 394 | vector<RefToUpdate> ReferencesToUpdate; |
| 395 | |
| 396 | const ScalarInfo &getScalarRef(const Value *V) { |
Chris Lattner | 9d3493e | 2002-03-29 21:25:19 +0000 | [diff] [blame] | 397 | for (unsigned i = 0, e = Scalars.size(); i != e; ++i) |
| 398 | if (Scalars[i].Val == V) return Scalars[i]; |
Chris Lattner | 3b87167 | 2002-04-18 14:43:30 +0000 | [diff] [blame] | 399 | |
| 400 | cerr << "Could not find scalar " << V << " in scalar map!\n"; |
Chris Lattner | 9d3493e | 2002-03-29 21:25:19 +0000 | [diff] [blame] | 401 | assert(0 && "Scalar not found in getScalar!"); |
| 402 | abort(); |
| 403 | return Scalars[0]; |
| 404 | } |
Chris Lattner | 5146a7d | 2002-04-12 20:23:15 +0000 | [diff] [blame] | 405 | |
| 406 | const ScalarInfo *getScalar(const Value *V) { |
Chris Lattner | 9d3493e | 2002-03-29 21:25:19 +0000 | [diff] [blame] | 407 | for (unsigned i = 0, e = Scalars.size(); i != e; ++i) |
Chris Lattner | 5146a7d | 2002-04-12 20:23:15 +0000 | [diff] [blame] | 408 | if (Scalars[i].Val == V) return &Scalars[i]; |
| 409 | return 0; |
Chris Lattner | 9d3493e | 2002-03-29 21:25:19 +0000 | [diff] [blame] | 410 | } |
| 411 | |
Chris Lattner | 5146a7d | 2002-04-12 20:23:15 +0000 | [diff] [blame] | 412 | BasicBlock::iterator ReplaceInstWith(Instruction *I, Instruction *New) { |
| 413 | BasicBlock *BB = I->getParent(); |
| 414 | BasicBlock::iterator RI = find(BB->begin(), BB->end(), I); |
| 415 | BB->getInstList().replaceWith(RI, New); |
| 416 | XFormMap[I] = New; |
| 417 | return RI; |
| 418 | } |
| 419 | |
| 420 | LoadInst *createPoolBaseInstruction(Value *PtrVal) { |
| 421 | const ScalarInfo &SC = getScalarRef(PtrVal); |
| 422 | vector<Value*> Args(3); |
| 423 | Args[0] = ConstantUInt::get(Type::UIntTy, 0); // No pointer offset |
| 424 | Args[1] = ConstantUInt::get(Type::UByteTy, 0); // Field #0 of pool descriptr |
| 425 | Args[2] = ConstantUInt::get(Type::UByteTy, 0); // Field #0 of poolalloc val |
| 426 | return new LoadInst(SC.Pool.Handle, Args, PtrVal->getName()+".poolbase"); |
| 427 | } |
| 428 | |
| 429 | |
Chris Lattner | 9d3493e | 2002-03-29 21:25:19 +0000 | [diff] [blame] | 430 | public: |
Chris Lattner | 5146a7d | 2002-04-12 20:23:15 +0000 | [diff] [blame] | 431 | NewInstructionCreator(PoolAllocate &PA, vector<ScalarInfo> &S, |
| 432 | map<CallInst*, TransformFunctionInfo> &C, |
| 433 | map<Value*, Value*> &X) |
| 434 | : PoolAllocator(PA), Scalars(S), CallMap(C), XFormMap(X) {} |
Chris Lattner | 9d3493e | 2002-03-29 21:25:19 +0000 | [diff] [blame] | 435 | |
Chris Lattner | 5146a7d | 2002-04-12 20:23:15 +0000 | [diff] [blame] | 436 | |
| 437 | // updateReferences - The NewInstructionCreator is responsible for creating |
| 438 | // new instructions to replace the old ones in the function, and then link up |
| 439 | // references to values to their new values. For it to do this, however, it |
| 440 | // keeps track of information about the value mapping of old values to new |
| 441 | // values that need to be patched up. Given this value map and a set of |
| 442 | // instruction operands to patch, updateReferences performs the updates. |
| 443 | // |
| 444 | void updateReferences() { |
| 445 | for (unsigned i = 0, e = ReferencesToUpdate.size(); i != e; ++i) { |
| 446 | RefToUpdate &Ref = ReferencesToUpdate[i]; |
| 447 | Value *NewVal = XFormMap[Ref.OldVal]; |
| 448 | |
| 449 | if (NewVal == 0) { |
| 450 | if (isa<Constant>(Ref.OldVal) && // Refering to a null ptr? |
| 451 | cast<Constant>(Ref.OldVal)->isNullValue()) { |
| 452 | // Transform the null pointer into a null index... caching in XFormMap |
Chris Lattner | 8e34333 | 2002-04-27 02:29:32 +0000 | [diff] [blame] | 453 | XFormMap[Ref.OldVal] = NewVal = Constant::getNullValue(POINTERTYPE); |
Chris Lattner | 5146a7d | 2002-04-12 20:23:15 +0000 | [diff] [blame] | 454 | //} else if (isa<Argument>(Ref.OldVal)) { |
| 455 | } else { |
| 456 | cerr << "Unknown reference to: " << Ref.OldVal << "\n"; |
| 457 | assert(XFormMap[Ref.OldVal] && |
| 458 | "Reference to value that was not updated found!"); |
| 459 | } |
| 460 | } |
| 461 | |
| 462 | Ref.I->setOperand(Ref.OpNum, NewVal); |
| 463 | } |
| 464 | ReferencesToUpdate.clear(); |
Chris Lattner | 9d3493e | 2002-03-29 21:25:19 +0000 | [diff] [blame] | 465 | } |
| 466 | |
Chris Lattner | 5146a7d | 2002-04-12 20:23:15 +0000 | [diff] [blame] | 467 | //===--------------------------------------------------------------------===// |
| 468 | // Transformation methods: |
| 469 | // These methods specify how each type of instruction is transformed by the |
| 470 | // NewInstructionCreator instance... |
| 471 | //===--------------------------------------------------------------------===// |
| 472 | |
| 473 | void visitGetElementPtrInst(GetElementPtrInst *I) { |
| 474 | assert(0 && "Cannot transform get element ptr instructions yet!"); |
| 475 | } |
| 476 | |
| 477 | // Replace the load instruction with a new one. |
| 478 | void visitLoadInst(LoadInst *I) { |
| 479 | Instruction *PoolBase = createPoolBaseInstruction(I->getOperand(0)); |
| 480 | |
| 481 | // Cast our index to be a UIntTy so we can use it to index into the pool... |
Chris Lattner | 8e34333 | 2002-04-27 02:29:32 +0000 | [diff] [blame] | 482 | CastInst *Index = new CastInst(Constant::getNullValue(POINTERTYPE), |
Chris Lattner | 5146a7d | 2002-04-12 20:23:15 +0000 | [diff] [blame] | 483 | Type::UIntTy, I->getOperand(0)->getName()); |
| 484 | |
| 485 | ReferencesToUpdate.push_back(RefToUpdate(Index, 0, I->getOperand(0))); |
| 486 | |
| 487 | vector<Value*> Indices(I->idx_begin(), I->idx_end()); |
Chris Lattner | 8e34333 | 2002-04-27 02:29:32 +0000 | [diff] [blame] | 488 | Instruction *IdxInst = |
| 489 | BinaryOperator::create(Instruction::Add, Indices[0], Index, |
| 490 | I->getName()+".idx"); |
| 491 | Indices[0] = IdxInst; |
Chris Lattner | 5146a7d | 2002-04-12 20:23:15 +0000 | [diff] [blame] | 492 | Instruction *NewLoad = new LoadInst(PoolBase, Indices, I->getName()); |
| 493 | |
| 494 | // Replace the load instruction with the new load instruction... |
| 495 | BasicBlock::iterator II = ReplaceInstWith(I, NewLoad); |
| 496 | |
| 497 | // Add the pool base calculator instruction before the load... |
| 498 | II = NewLoad->getParent()->getInstList().insert(II, PoolBase) + 1; |
| 499 | |
Chris Lattner | 8e34333 | 2002-04-27 02:29:32 +0000 | [diff] [blame] | 500 | // Add the idx calculator instruction before the load... |
| 501 | II = NewLoad->getParent()->getInstList().insert(II, Index) + 1; |
| 502 | |
Chris Lattner | 5146a7d | 2002-04-12 20:23:15 +0000 | [diff] [blame] | 503 | // Add the cast before the load instruction... |
Chris Lattner | 8e34333 | 2002-04-27 02:29:32 +0000 | [diff] [blame] | 504 | NewLoad->getParent()->getInstList().insert(II, IdxInst); |
Chris Lattner | 5146a7d | 2002-04-12 20:23:15 +0000 | [diff] [blame] | 505 | |
| 506 | // If not yielding a pool allocated pointer, use the new load value as the |
| 507 | // value in the program instead of the old load value... |
| 508 | // |
| 509 | if (!getScalar(I)) |
| 510 | I->replaceAllUsesWith(NewLoad); |
| 511 | } |
| 512 | |
| 513 | // Replace the store instruction with a new one. In the store instruction, |
| 514 | // the value stored could be a pointer type, meaning that the new store may |
| 515 | // have to change one or both of it's operands. |
| 516 | // |
| 517 | void visitStoreInst(StoreInst *I) { |
| 518 | assert(getScalar(I->getOperand(1)) && |
| 519 | "Store inst found only storing pool allocated pointer. " |
| 520 | "Not imp yet!"); |
| 521 | |
| 522 | Value *Val = I->getOperand(0); // The value to store... |
| 523 | // Check to see if the value we are storing is a data structure pointer... |
Chris Lattner | 8e34333 | 2002-04-27 02:29:32 +0000 | [diff] [blame] | 524 | //if (const ScalarInfo *ValScalar = getScalar(I->getOperand(0))) |
| 525 | if (isa<PointerType>(I->getOperand(0)->getType())) |
| 526 | Val = Constant::getNullValue(POINTERTYPE); // Yes, store a dummy |
Chris Lattner | 5146a7d | 2002-04-12 20:23:15 +0000 | [diff] [blame] | 527 | |
| 528 | Instruction *PoolBase = createPoolBaseInstruction(I->getOperand(1)); |
| 529 | |
| 530 | // Cast our index to be a UIntTy so we can use it to index into the pool... |
Chris Lattner | 8e34333 | 2002-04-27 02:29:32 +0000 | [diff] [blame] | 531 | CastInst *Index = new CastInst(Constant::getNullValue(POINTERTYPE), |
Chris Lattner | 5146a7d | 2002-04-12 20:23:15 +0000 | [diff] [blame] | 532 | Type::UIntTy, I->getOperand(1)->getName()); |
| 533 | ReferencesToUpdate.push_back(RefToUpdate(Index, 0, I->getOperand(1))); |
| 534 | |
| 535 | vector<Value*> Indices(I->idx_begin(), I->idx_end()); |
Chris Lattner | 8e34333 | 2002-04-27 02:29:32 +0000 | [diff] [blame] | 536 | Instruction *IdxInst = |
| 537 | BinaryOperator::create(Instruction::Add, Indices[0], Index, "idx"); |
| 538 | Indices[0] = IdxInst; |
| 539 | |
Chris Lattner | 5146a7d | 2002-04-12 20:23:15 +0000 | [diff] [blame] | 540 | Instruction *NewStore = new StoreInst(Val, PoolBase, Indices); |
| 541 | |
| 542 | if (Val != I->getOperand(0)) // Value stored was a pointer? |
| 543 | ReferencesToUpdate.push_back(RefToUpdate(NewStore, 0, I->getOperand(0))); |
| 544 | |
| 545 | |
| 546 | // Replace the store instruction with the cast instruction... |
| 547 | BasicBlock::iterator II = ReplaceInstWith(I, Index); |
| 548 | |
| 549 | // Add the pool base calculator instruction before the index... |
| 550 | II = Index->getParent()->getInstList().insert(II, PoolBase) + 2; |
| 551 | |
Chris Lattner | 8e34333 | 2002-04-27 02:29:32 +0000 | [diff] [blame] | 552 | // Add the indexing instruction... |
| 553 | II = Index->getParent()->getInstList().insert(II, IdxInst) + 1; |
| 554 | |
Chris Lattner | 5146a7d | 2002-04-12 20:23:15 +0000 | [diff] [blame] | 555 | // Add the store after the cast instruction... |
| 556 | Index->getParent()->getInstList().insert(II, NewStore); |
| 557 | } |
| 558 | |
| 559 | |
| 560 | // Create call to poolalloc for every malloc instruction |
Chris Lattner | 9d3493e | 2002-03-29 21:25:19 +0000 | [diff] [blame] | 561 | void visitMallocInst(MallocInst *I) { |
Chris Lattner | 8e34333 | 2002-04-27 02:29:32 +0000 | [diff] [blame] | 562 | const ScalarInfo &SCI = getScalarRef(I); |
Chris Lattner | 9d3493e | 2002-03-29 21:25:19 +0000 | [diff] [blame] | 563 | vector<Value*> Args; |
Chris Lattner | 8e34333 | 2002-04-27 02:29:32 +0000 | [diff] [blame] | 564 | |
| 565 | CallInst *Call; |
| 566 | if (!I->isArrayAllocation()) { |
| 567 | Args.push_back(SCI.Pool.Handle); |
| 568 | Call = new CallInst(PoolAllocator.PoolAlloc, Args, I->getName()); |
| 569 | } else { |
| 570 | Args.push_back(I->getArraySize()); |
| 571 | Args.push_back(SCI.Pool.Handle); |
| 572 | Call = new CallInst(PoolAllocator.PoolAllocArray, Args, I->getName()); |
| 573 | } |
| 574 | |
Chris Lattner | 5146a7d | 2002-04-12 20:23:15 +0000 | [diff] [blame] | 575 | ReplaceInstWith(I, Call); |
Chris Lattner | 9d3493e | 2002-03-29 21:25:19 +0000 | [diff] [blame] | 576 | } |
| 577 | |
Chris Lattner | 5146a7d | 2002-04-12 20:23:15 +0000 | [diff] [blame] | 578 | // Convert a call to poolfree for every free instruction... |
Chris Lattner | 9d3493e | 2002-03-29 21:25:19 +0000 | [diff] [blame] | 579 | void visitFreeInst(FreeInst *I) { |
Chris Lattner | 9d3493e | 2002-03-29 21:25:19 +0000 | [diff] [blame] | 580 | // Create a new call to poolfree before the free instruction |
| 581 | vector<Value*> Args; |
Chris Lattner | 8e34333 | 2002-04-27 02:29:32 +0000 | [diff] [blame] | 582 | Args.push_back(Constant::getNullValue(POINTERTYPE)); |
Chris Lattner | 5146a7d | 2002-04-12 20:23:15 +0000 | [diff] [blame] | 583 | Args.push_back(getScalarRef(I->getOperand(0)).Pool.Handle); |
| 584 | Instruction *NewCall = new CallInst(PoolAllocator.PoolFree, Args); |
| 585 | ReplaceInstWith(I, NewCall); |
Chris Lattner | 7b5577b | 2002-04-18 22:11:30 +0000 | [diff] [blame] | 586 | ReferencesToUpdate.push_back(RefToUpdate(NewCall, 1, I->getOperand(0))); |
Chris Lattner | 9d3493e | 2002-03-29 21:25:19 +0000 | [diff] [blame] | 587 | } |
| 588 | |
| 589 | // visitCallInst - Create a new call instruction with the extra arguments for |
| 590 | // all of the memory pools that the call needs. |
| 591 | // |
| 592 | void visitCallInst(CallInst *I) { |
| 593 | TransformFunctionInfo &TI = CallMap[I]; |
Chris Lattner | 9d3493e | 2002-03-29 21:25:19 +0000 | [diff] [blame] | 594 | |
| 595 | // Start with all of the old arguments... |
| 596 | vector<Value*> Args(I->op_begin()+1, I->op_end()); |
| 597 | |
Chris Lattner | 5146a7d | 2002-04-12 20:23:15 +0000 | [diff] [blame] | 598 | for (unsigned i = 0, e = TI.ArgInfo.size(); i != e; ++i) { |
| 599 | // Replace all of the pointer arguments with our new pointer typed values. |
| 600 | if (TI.ArgInfo[i].ArgNo != -1) |
Chris Lattner | 8e34333 | 2002-04-27 02:29:32 +0000 | [diff] [blame] | 601 | Args[TI.ArgInfo[i].ArgNo] = Constant::getNullValue(POINTERTYPE); |
Chris Lattner | 5146a7d | 2002-04-12 20:23:15 +0000 | [diff] [blame] | 602 | |
| 603 | // Add all of the pool arguments... |
Chris Lattner | 4c7f3df | 2002-03-30 04:02:31 +0000 | [diff] [blame] | 604 | Args.push_back(TI.ArgInfo[i].PoolHandle); |
Chris Lattner | 5146a7d | 2002-04-12 20:23:15 +0000 | [diff] [blame] | 605 | } |
Chris Lattner | 9d3493e | 2002-03-29 21:25:19 +0000 | [diff] [blame] | 606 | |
| 607 | Function *NF = PoolAllocator.getTransformedFunction(TI); |
Chris Lattner | 5146a7d | 2002-04-12 20:23:15 +0000 | [diff] [blame] | 608 | Instruction *NewCall = new CallInst(NF, Args, I->getName()); |
| 609 | ReplaceInstWith(I, NewCall); |
Chris Lattner | 9d3493e | 2002-03-29 21:25:19 +0000 | [diff] [blame] | 610 | |
Chris Lattner | 5146a7d | 2002-04-12 20:23:15 +0000 | [diff] [blame] | 611 | // Keep track of the mapping of operands so that we can resolve them to real |
| 612 | // values later. |
| 613 | Value *RetVal = NewCall; |
| 614 | for (unsigned i = 0, e = TI.ArgInfo.size(); i != e; ++i) |
| 615 | if (TI.ArgInfo[i].ArgNo != -1) |
| 616 | ReferencesToUpdate.push_back(RefToUpdate(NewCall, TI.ArgInfo[i].ArgNo+1, |
| 617 | I->getOperand(TI.ArgInfo[i].ArgNo+1))); |
| 618 | else |
| 619 | RetVal = 0; // If returning a pointer, don't change retval... |
Chris Lattner | 9d3493e | 2002-03-29 21:25:19 +0000 | [diff] [blame] | 620 | |
Chris Lattner | 5146a7d | 2002-04-12 20:23:15 +0000 | [diff] [blame] | 621 | // If not returning a pointer, use the new call as the value in the program |
| 622 | // instead of the old call... |
| 623 | // |
| 624 | if (RetVal) |
| 625 | I->replaceAllUsesWith(RetVal); |
| 626 | } |
| 627 | |
| 628 | // visitPHINode - Create a new PHI node of POINTERTYPE for all of the old Phi |
| 629 | // nodes... |
| 630 | // |
| 631 | void visitPHINode(PHINode *PN) { |
Chris Lattner | 8e34333 | 2002-04-27 02:29:32 +0000 | [diff] [blame] | 632 | Value *DummyVal = Constant::getNullValue(POINTERTYPE); |
Chris Lattner | 5146a7d | 2002-04-12 20:23:15 +0000 | [diff] [blame] | 633 | PHINode *NewPhi = new PHINode(POINTERTYPE, PN->getName()); |
| 634 | for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { |
| 635 | NewPhi->addIncoming(DummyVal, PN->getIncomingBlock(i)); |
| 636 | ReferencesToUpdate.push_back(RefToUpdate(NewPhi, i*2, |
| 637 | PN->getIncomingValue(i))); |
Chris Lattner | 9d3493e | 2002-03-29 21:25:19 +0000 | [diff] [blame] | 638 | } |
| 639 | |
Chris Lattner | 5146a7d | 2002-04-12 20:23:15 +0000 | [diff] [blame] | 640 | ReplaceInstWith(PN, NewPhi); |
Chris Lattner | 9d3493e | 2002-03-29 21:25:19 +0000 | [diff] [blame] | 641 | } |
| 642 | |
Chris Lattner | 5146a7d | 2002-04-12 20:23:15 +0000 | [diff] [blame] | 643 | // visitReturnInst - Replace ret instruction with a new return... |
Chris Lattner | 072d3a0 | 2002-03-30 20:53:14 +0000 | [diff] [blame] | 644 | void visitReturnInst(ReturnInst *I) { |
Chris Lattner | 8e34333 | 2002-04-27 02:29:32 +0000 | [diff] [blame] | 645 | Instruction *Ret = new ReturnInst(Constant::getNullValue(POINTERTYPE)); |
Chris Lattner | 5146a7d | 2002-04-12 20:23:15 +0000 | [diff] [blame] | 646 | ReplaceInstWith(I, Ret); |
| 647 | ReferencesToUpdate.push_back(RefToUpdate(Ret, 0, I->getOperand(0))); |
Chris Lattner | 072d3a0 | 2002-03-30 20:53:14 +0000 | [diff] [blame] | 648 | } |
| 649 | |
Chris Lattner | 5146a7d | 2002-04-12 20:23:15 +0000 | [diff] [blame] | 650 | // visitSetCondInst - Replace a conditional test instruction with a new one |
Chris Lattner | f719694 | 2002-04-01 00:45:33 +0000 | [diff] [blame] | 651 | void visitSetCondInst(SetCondInst *SCI) { |
Chris Lattner | 5146a7d | 2002-04-12 20:23:15 +0000 | [diff] [blame] | 652 | BinaryOperator *I = (BinaryOperator*)SCI; |
Chris Lattner | 8e34333 | 2002-04-27 02:29:32 +0000 | [diff] [blame] | 653 | Value *DummyVal = Constant::getNullValue(POINTERTYPE); |
Chris Lattner | 5146a7d | 2002-04-12 20:23:15 +0000 | [diff] [blame] | 654 | BinaryOperator *New = BinaryOperator::create(I->getOpcode(), DummyVal, |
| 655 | DummyVal, I->getName()); |
| 656 | ReplaceInstWith(I, New); |
| 657 | |
| 658 | ReferencesToUpdate.push_back(RefToUpdate(New, 0, I->getOperand(0))); |
| 659 | ReferencesToUpdate.push_back(RefToUpdate(New, 1, I->getOperand(1))); |
| 660 | |
| 661 | // Make sure branches refer to the new condition... |
| 662 | I->replaceAllUsesWith(New); |
Chris Lattner | f719694 | 2002-04-01 00:45:33 +0000 | [diff] [blame] | 663 | } |
| 664 | |
Chris Lattner | 9d3493e | 2002-03-29 21:25:19 +0000 | [diff] [blame] | 665 | void visitInstruction(Instruction *I) { |
Chris Lattner | 5146a7d | 2002-04-12 20:23:15 +0000 | [diff] [blame] | 666 | cerr << "Unknown instruction to FunctionBodyTransformer:\n" << I; |
Chris Lattner | 9d3493e | 2002-03-29 21:25:19 +0000 | [diff] [blame] | 667 | } |
Chris Lattner | 9d3493e | 2002-03-29 21:25:19 +0000 | [diff] [blame] | 668 | }; |
| 669 | |
| 670 | |
Chris Lattner | 09b9212 | 2002-04-15 22:42:23 +0000 | [diff] [blame] | 671 | // PoolBaseLoadEliminator - Every load and store through a pool allocated |
| 672 | // pointer causes a load of the real pool base out of the pool descriptor. |
| 673 | // Iterate through the function, doing a local elimination pass of duplicate |
| 674 | // loads. This attempts to turn the all too common: |
| 675 | // |
| 676 | // %reg109.poolbase22 = load %root.pool* %root.pool, uint 0, ubyte 0, ubyte 0 |
| 677 | // %reg207 = load %root.p* %reg109.poolbase22, uint %reg109, ubyte 0, ubyte 0 |
| 678 | // %reg109.poolbase23 = load %root.pool* %root.pool, uint 0, ubyte 0, ubyte 0 |
| 679 | // store double %reg207, %root.p* %reg109.poolbase23, uint %reg109, ... |
| 680 | // |
| 681 | // into: |
| 682 | // %reg109.poolbase22 = load %root.pool* %root.pool, uint 0, ubyte 0, ubyte 0 |
| 683 | // %reg207 = load %root.p* %reg109.poolbase22, uint %reg109, ubyte 0, ubyte 0 |
| 684 | // store double %reg207, %root.p* %reg109.poolbase22, uint %reg109, ... |
| 685 | // |
| 686 | // |
| 687 | class PoolBaseLoadEliminator : public InstVisitor<PoolBaseLoadEliminator> { |
| 688 | // PoolDescValues - Keep track of the values in the current function that are |
| 689 | // pool descriptors (loads from which we want to eliminate). |
| 690 | // |
| 691 | vector<Value*> PoolDescValues; |
| 692 | |
| 693 | // PoolDescMap - As we are analyzing a BB, keep track of which load to use |
| 694 | // when referencing a pool descriptor. |
| 695 | // |
| 696 | map<Value*, LoadInst*> PoolDescMap; |
| 697 | |
| 698 | // These two fields keep track of statistics of how effective we are, if |
| 699 | // debugging is enabled. |
| 700 | // |
| 701 | unsigned Eliminated, Remaining; |
| 702 | public: |
| 703 | // Compact the pool descriptor map into a list of the pool descriptors in the |
| 704 | // current context that we should know about... |
| 705 | // |
| 706 | PoolBaseLoadEliminator(const map<DSNode*, PoolInfo> &PoolDescs) { |
| 707 | Eliminated = Remaining = 0; |
| 708 | for (map<DSNode*, PoolInfo>::const_iterator I = PoolDescs.begin(), |
| 709 | E = PoolDescs.end(); I != E; ++I) |
| 710 | PoolDescValues.push_back(I->second.Handle); |
| 711 | |
| 712 | // Remove duplicates from the list of pool values |
| 713 | sort(PoolDescValues.begin(), PoolDescValues.end()); |
| 714 | PoolDescValues.erase(unique(PoolDescValues.begin(), PoolDescValues.end()), |
| 715 | PoolDescValues.end()); |
| 716 | } |
| 717 | |
| 718 | #ifdef DEBUG_POOLBASE_LOAD_ELIMINATOR |
| 719 | void visitFunction(Function *F) { |
| 720 | cerr << "Pool Load Elim '" << F->getName() << "'\t"; |
| 721 | } |
| 722 | ~PoolBaseLoadEliminator() { |
| 723 | unsigned Total = Eliminated+Remaining; |
| 724 | if (Total) |
| 725 | cerr << "removed " << Eliminated << "[" |
| 726 | << Eliminated*100/Total << "%] loads, leaving " |
| 727 | << Remaining << ".\n"; |
| 728 | } |
| 729 | #endif |
| 730 | |
| 731 | // Loop over the function, looking for loads to eliminate. Because we are a |
| 732 | // local transformation, we reset all of our state when we enter a new basic |
| 733 | // block. |
| 734 | // |
| 735 | void visitBasicBlock(BasicBlock *) { |
| 736 | PoolDescMap.clear(); // Forget state. |
| 737 | } |
| 738 | |
| 739 | // Starting with an empty basic block, we scan it looking for loads of the |
| 740 | // pool descriptor. When we find a load, we add it to the PoolDescMap, |
| 741 | // indicating that we have a value available to recycle next time we see the |
| 742 | // poolbase of this instruction being loaded. |
| 743 | // |
| 744 | void visitLoadInst(LoadInst *LI) { |
| 745 | Value *LoadAddr = LI->getPointerOperand(); |
| 746 | map<Value*, LoadInst*>::iterator VIt = PoolDescMap.find(LoadAddr); |
| 747 | if (VIt != PoolDescMap.end()) { // We already have a value for this load? |
| 748 | LI->replaceAllUsesWith(VIt->second); // Make the current load dead |
| 749 | ++Eliminated; |
| 750 | } else { |
| 751 | // This load might not be a load of a pool pointer, check to see if it is |
| 752 | if (LI->getNumOperands() == 4 && // load pool, uint 0, ubyte 0, ubyte 0 |
| 753 | find(PoolDescValues.begin(), PoolDescValues.end(), LoadAddr) != |
| 754 | PoolDescValues.end()) { |
| 755 | |
| 756 | assert("Make sure it's a load of the pool base, not a chaining field" && |
Chris Lattner | 8e34333 | 2002-04-27 02:29:32 +0000 | [diff] [blame] | 757 | LI->getOperand(1) == Constant::getNullValue(Type::UIntTy) && |
| 758 | LI->getOperand(2) == Constant::getNullValue(Type::UByteTy) && |
| 759 | LI->getOperand(3) == Constant::getNullValue(Type::UByteTy)); |
Chris Lattner | 09b9212 | 2002-04-15 22:42:23 +0000 | [diff] [blame] | 760 | |
| 761 | // If it is a load of a pool base, keep track of it for future reference |
| 762 | PoolDescMap.insert(make_pair(LoadAddr, LI)); |
| 763 | ++Remaining; |
| 764 | } |
| 765 | } |
| 766 | } |
| 767 | |
| 768 | // If we run across a function call, forget all state... Calls to |
| 769 | // poolalloc/poolfree can invalidate the pool base pointer, so it should be |
| 770 | // reloaded the next time it is used. Furthermore, a call to a random |
| 771 | // function might call one of these functions, so be conservative. Through |
| 772 | // more analysis, this could be improved in the future. |
| 773 | // |
| 774 | void visitCallInst(CallInst *) { |
| 775 | PoolDescMap.clear(); |
| 776 | } |
| 777 | }; |
| 778 | |
Chris Lattner | 3b87167 | 2002-04-18 14:43:30 +0000 | [diff] [blame] | 779 | static void addNodeMapping(DSNode *SrcNode, const PointerValSet &PVS, |
| 780 | map<DSNode*, PointerValSet> &NodeMapping) { |
| 781 | for (unsigned i = 0, e = PVS.size(); i != e; ++i) |
| 782 | if (NodeMapping[SrcNode].add(PVS[i])) { // Not in map yet? |
| 783 | assert(PVS[i].Index == 0 && "Node indexing not supported yet!"); |
| 784 | DSNode *DestNode = PVS[i].Node; |
| 785 | |
| 786 | // Loop over all of the outgoing links in the mapped graph |
| 787 | for (unsigned l = 0, le = DestNode->getNumOutgoingLinks(); l != le; ++l) { |
| 788 | PointerValSet &SrcSet = SrcNode->getOutgoingLink(l); |
| 789 | const PointerValSet &DestSet = DestNode->getOutgoingLink(l); |
| 790 | |
| 791 | // Add all of the node mappings now! |
| 792 | for (unsigned si = 0, se = SrcSet.size(); si != se; ++si) { |
| 793 | assert(SrcSet[si].Index == 0 && "Can't handle node offset!"); |
| 794 | addNodeMapping(SrcSet[si].Node, DestSet, NodeMapping); |
| 795 | } |
| 796 | } |
| 797 | } |
| 798 | } |
| 799 | |
| 800 | // CalculateNodeMapping - There is a partial isomorphism between the graph |
| 801 | // passed in and the graph that is actually used by the function. We need to |
| 802 | // figure out what this mapping is so that we can transformFunctionBody the |
| 803 | // instructions in the function itself. Note that every node in the graph that |
| 804 | // we are interested in must be both in the local graph of the called function, |
| 805 | // and in the local graph of the calling function. Because of this, we only |
| 806 | // define the mapping for these nodes [conveniently these are the only nodes we |
| 807 | // CAN define a mapping for...] |
| 808 | // |
| 809 | // The roots of the graph that we are transforming is rooted in the arguments |
| 810 | // passed into the function from the caller. This is where we start our |
| 811 | // mapping calculation. |
| 812 | // |
| 813 | // The NodeMapping calculated maps from the callers graph to the called graph. |
| 814 | // |
| 815 | static void CalculateNodeMapping(Function *F, TransformFunctionInfo &TFI, |
| 816 | FunctionDSGraph &CallerGraph, |
| 817 | FunctionDSGraph &CalledGraph, |
| 818 | map<DSNode*, PointerValSet> &NodeMapping) { |
| 819 | int LastArgNo = -2; |
| 820 | for (unsigned i = 0, e = TFI.ArgInfo.size(); i != e; ++i) { |
| 821 | // Figure out what nodes in the called graph the TFI.ArgInfo[i].Node node |
| 822 | // corresponds to... |
| 823 | // |
| 824 | // Only consider first node of sequence. Extra nodes may may be added |
| 825 | // to the TFI if the data structure requires more nodes than just the |
| 826 | // one the argument points to. We are only interested in the one the |
| 827 | // argument points to though. |
| 828 | // |
| 829 | if (TFI.ArgInfo[i].ArgNo != LastArgNo) { |
| 830 | if (TFI.ArgInfo[i].ArgNo == -1) { |
| 831 | addNodeMapping(TFI.ArgInfo[i].Node, CalledGraph.getRetNodes(), |
| 832 | NodeMapping); |
| 833 | } else { |
| 834 | // Figure out which node argument # ArgNo points to in the called graph. |
| 835 | Value *Arg = F->getArgumentList()[TFI.ArgInfo[i].ArgNo]; |
| 836 | addNodeMapping(TFI.ArgInfo[i].Node, CalledGraph.getValueMap()[Arg], |
| 837 | NodeMapping); |
| 838 | } |
| 839 | LastArgNo = TFI.ArgInfo[i].ArgNo; |
| 840 | } |
| 841 | } |
| 842 | } |
Chris Lattner | 5146a7d | 2002-04-12 20:23:15 +0000 | [diff] [blame] | 843 | |
| 844 | |
Chris Lattner | 3b87167 | 2002-04-18 14:43:30 +0000 | [diff] [blame] | 845 | |
| 846 | |
| 847 | // addCallInfo - For a specified function call CI, figure out which pool |
| 848 | // descriptors need to be passed in as arguments, and which arguments need to be |
| 849 | // transformed into indices. If Arg != -1, the specified call argument is |
| 850 | // passed in as a pointer to a data structure. |
| 851 | // |
| 852 | void TransformFunctionInfo::addCallInfo(DataStructure *DS, CallInst *CI, |
| 853 | int Arg, DSNode *GraphNode, |
| 854 | map<DSNode*, PoolInfo> &PoolDescs) { |
Chris Lattner | 9acfbee | 2002-03-31 07:17:46 +0000 | [diff] [blame] | 855 | assert(CI->getCalledFunction() && "Cannot handle indirect calls yet!"); |
Chris Lattner | 3b87167 | 2002-04-18 14:43:30 +0000 | [diff] [blame] | 856 | assert(Func == 0 || Func == CI->getCalledFunction() && |
Chris Lattner | 9acfbee | 2002-03-31 07:17:46 +0000 | [diff] [blame] | 857 | "Function call record should always call the same function!"); |
Chris Lattner | 3b87167 | 2002-04-18 14:43:30 +0000 | [diff] [blame] | 858 | assert(Call == 0 || Call == CI && |
Chris Lattner | 9acfbee | 2002-03-31 07:17:46 +0000 | [diff] [blame] | 859 | "Call element already filled in with different value!"); |
Chris Lattner | 3b87167 | 2002-04-18 14:43:30 +0000 | [diff] [blame] | 860 | Func = CI->getCalledFunction(); |
| 861 | Call = CI; |
| 862 | //FunctionDSGraph &CalledGraph = DS->getClosedDSGraph(Func); |
Chris Lattner | 4c7f3df | 2002-03-30 04:02:31 +0000 | [diff] [blame] | 863 | |
| 864 | // For now, add the entire graph that is pointed to by the call argument. |
| 865 | // This graph can and should be pruned to only what the function itself will |
| 866 | // use, because often this will be a dramatically smaller subset of what we |
| 867 | // are providing. |
| 868 | // |
Chris Lattner | 3b87167 | 2002-04-18 14:43:30 +0000 | [diff] [blame] | 869 | // FIXME: This should use pool links instead of extra arguments! |
| 870 | // |
Chris Lattner | cfb5f4c | 2002-03-30 09:12:35 +0000 | [diff] [blame] | 871 | for (df_iterator<DSNode*> I = df_begin(GraphNode), E = df_end(GraphNode); |
Chris Lattner | 5146a7d | 2002-04-12 20:23:15 +0000 | [diff] [blame] | 872 | I != E; ++I) |
Chris Lattner | 3b87167 | 2002-04-18 14:43:30 +0000 | [diff] [blame] | 873 | ArgInfo.push_back(CallArgInfo(Arg, *I, PoolDescs[*I].Handle)); |
| 874 | } |
| 875 | |
| 876 | static void markReachableNodes(const PointerValSet &Vals, |
| 877 | set<DSNode*> &ReachableNodes) { |
| 878 | for (unsigned n = 0, ne = Vals.size(); n != ne; ++n) { |
| 879 | DSNode *N = Vals[n].Node; |
| 880 | if (ReachableNodes.count(N) == 0) // Haven't already processed node? |
| 881 | ReachableNodes.insert(df_begin(N), df_end(N)); // Insert all |
| 882 | } |
| 883 | } |
| 884 | |
| 885 | // Make sure that all dependant arguments are added to this transformation info. |
| 886 | // For example, if we call foo(null, P) and foo treats it's first and second |
| 887 | // arguments as belonging to the same data structure, the we MUST add entries to |
| 888 | // know that the null needs to be transformed into an index as well. |
| 889 | // |
| 890 | void TransformFunctionInfo::ensureDependantArgumentsIncluded(DataStructure *DS, |
| 891 | map<DSNode*, PoolInfo> &PoolDescs) { |
| 892 | // FIXME: This does not work for indirect function calls!!! |
| 893 | if (Func == 0) return; // FIXME! |
| 894 | |
| 895 | // Make sure argument entries are sorted. |
| 896 | finalizeConstruction(); |
| 897 | |
| 898 | // Loop over the function signature, checking to see if there are any pointer |
| 899 | // arguments that we do not convert... if there is something we haven't |
| 900 | // converted, set done to false. |
| 901 | // |
| 902 | unsigned PtrNo = 0; |
| 903 | bool Done = true; |
| 904 | if (isa<PointerType>(Func->getReturnType())) // Make sure we convert retval |
| 905 | if (PtrNo < ArgInfo.size() && ArgInfo[PtrNo++].ArgNo == -1) { |
| 906 | // We DO transform the ret val... skip all possible entries for retval |
| 907 | while (PtrNo < ArgInfo.size() && ArgInfo[PtrNo].ArgNo == -1) |
| 908 | PtrNo++; |
| 909 | } else { |
| 910 | Done = false; |
| 911 | } |
| 912 | |
| 913 | for (unsigned i = 0, e = Func->getArgumentList().size(); i != e; ++i) { |
| 914 | Argument *Arg = Func->getArgumentList()[i]; |
| 915 | if (isa<PointerType>(Arg->getType())) { |
| 916 | if (PtrNo < ArgInfo.size() && ArgInfo[PtrNo++].ArgNo == (int)i) { |
| 917 | // We DO transform this arg... skip all possible entries for argument |
| 918 | while (PtrNo < ArgInfo.size() && ArgInfo[PtrNo].ArgNo == (int)i) |
| 919 | PtrNo++; |
| 920 | } else { |
| 921 | Done = false; |
| 922 | break; |
| 923 | } |
| 924 | } |
| 925 | } |
| 926 | |
| 927 | // If we already have entries for all pointer arguments and retvals, there |
| 928 | // certainly is no work to do. Bail out early to avoid building relatively |
| 929 | // expensive data structures. |
| 930 | // |
| 931 | if (Done) return; |
| 932 | |
| 933 | #ifdef DEBUG_TRANSFORM_PROGRESS |
| 934 | cerr << "Must ensure dependant arguments for: " << Func->getName() << "\n"; |
| 935 | #endif |
| 936 | |
| 937 | // Otherwise, we MIGHT have to add the arguments/retval if they are part of |
| 938 | // the same datastructure graph as some other argument or retval that we ARE |
| 939 | // processing. |
| 940 | // |
| 941 | // Get the data structure graph for the called function. |
| 942 | // |
| 943 | FunctionDSGraph &CalledDS = DS->getClosedDSGraph(Func); |
| 944 | |
| 945 | // Build a mapping between the nodes in our current graph and the nodes in the |
| 946 | // called function's graph. We build it based on our _incomplete_ |
| 947 | // transformation information, because it contains all of the info that we |
| 948 | // should need. |
| 949 | // |
| 950 | map<DSNode*, PointerValSet> NodeMapping; |
| 951 | CalculateNodeMapping(Func, *this, |
| 952 | DS->getClosedDSGraph(Call->getParent()->getParent()), |
| 953 | CalledDS, NodeMapping); |
| 954 | |
| 955 | // Build the inverted version of the node mapping, that maps from a node in |
| 956 | // the called functions graph to a single node in the caller graph. |
| 957 | // |
| 958 | map<DSNode*, DSNode*> InverseNodeMap; |
| 959 | for (map<DSNode*, PointerValSet>::iterator I = NodeMapping.begin(), |
| 960 | E = NodeMapping.end(); I != E; ++I) { |
| 961 | PointerValSet &CalledNodes = I->second; |
| 962 | for (unsigned i = 0, e = CalledNodes.size(); i != e; ++i) |
| 963 | InverseNodeMap[CalledNodes[i].Node] = I->first; |
| 964 | } |
| 965 | NodeMapping.clear(); // Done with information, free memory |
| 966 | |
| 967 | // Build a set of reachable nodes from the arguments/retval that we ARE |
| 968 | // passing in... |
| 969 | set<DSNode*> ReachableNodes; |
| 970 | |
| 971 | // Loop through all of the arguments, marking all of the reachable data |
| 972 | // structure nodes reachable if they are from this pointer... |
| 973 | // |
| 974 | for (unsigned i = 0, e = ArgInfo.size(); i != e; ++i) { |
| 975 | if (ArgInfo[i].ArgNo == -1) { |
| 976 | if (i == 0) // Only process retvals once (performance opt) |
| 977 | markReachableNodes(CalledDS.getRetNodes(), ReachableNodes); |
| 978 | } else { // If it's an argument value... |
| 979 | Argument *Arg = Func->getArgumentList()[ArgInfo[i].ArgNo]; |
| 980 | if (isa<PointerType>(Arg->getType())) |
| 981 | markReachableNodes(CalledDS.getValueMap()[Arg], ReachableNodes); |
| 982 | } |
| 983 | } |
| 984 | |
| 985 | // Now that we know which nodes are already reachable, see if any of the |
| 986 | // arguments that we are not passing values in for can reach one of the |
| 987 | // existing nodes... |
| 988 | // |
| 989 | |
| 990 | // <FIXME> IN THEORY, we should allow arbitrary paths from the argument to |
| 991 | // nodes we know about. The problem is that if we do this, then I don't know |
| 992 | // how to get pool pointers for this head list. Since we are completely |
| 993 | // deadline driven, I'll just allow direct accesses to the graph. </FIXME> |
| 994 | // |
| 995 | |
| 996 | PtrNo = 0; |
| 997 | if (isa<PointerType>(Func->getReturnType())) // Make sure we convert retval |
| 998 | if (PtrNo < ArgInfo.size() && ArgInfo[PtrNo++].ArgNo == -1) { |
| 999 | // We DO transform the ret val... skip all possible entries for retval |
| 1000 | while (PtrNo < ArgInfo.size() && ArgInfo[PtrNo].ArgNo == -1) |
| 1001 | PtrNo++; |
| 1002 | } else { |
| 1003 | // See what the return value points to... |
| 1004 | |
| 1005 | // FIXME: This should generalize to any number of nodes, just see if any |
| 1006 | // are reachable. |
| 1007 | assert(CalledDS.getRetNodes().size() == 1 && |
| 1008 | "Assumes only one node is returned"); |
| 1009 | DSNode *N = CalledDS.getRetNodes()[0].Node; |
| 1010 | |
| 1011 | // If the return value is not marked as being passed in, but it NEEDS to |
| 1012 | // be transformed, then make it known now. |
| 1013 | // |
| 1014 | if (ReachableNodes.count(N)) { |
| 1015 | #ifdef DEBUG_TRANSFORM_PROGRESS |
| 1016 | cerr << "ensure dependant arguments adds return value entry!\n"; |
| 1017 | #endif |
| 1018 | addCallInfo(DS, Call, -1, InverseNodeMap[N], PoolDescs); |
| 1019 | |
| 1020 | // Keep sorted! |
| 1021 | finalizeConstruction(); |
| 1022 | } |
| 1023 | } |
| 1024 | |
| 1025 | for (unsigned i = 0, e = Func->getArgumentList().size(); i != e; ++i) { |
| 1026 | Argument *Arg = Func->getArgumentList()[i]; |
| 1027 | if (isa<PointerType>(Arg->getType())) { |
| 1028 | if (PtrNo < ArgInfo.size() && ArgInfo[PtrNo++].ArgNo == (int)i) { |
| 1029 | // We DO transform this arg... skip all possible entries for argument |
| 1030 | while (PtrNo < ArgInfo.size() && ArgInfo[PtrNo].ArgNo == (int)i) |
| 1031 | PtrNo++; |
| 1032 | } else { |
| 1033 | // This should generalize to any number of nodes, just see if any are |
| 1034 | // reachable. |
| 1035 | assert(CalledDS.getValueMap()[Arg].size() == 1 && |
| 1036 | "Only handle case where pointing to one node so far!"); |
| 1037 | |
| 1038 | // If the arg is not marked as being passed in, but it NEEDS to |
| 1039 | // be transformed, then make it known now. |
| 1040 | // |
| 1041 | DSNode *N = CalledDS.getValueMap()[Arg][0].Node; |
| 1042 | if (ReachableNodes.count(N)) { |
| 1043 | #ifdef DEBUG_TRANSFORM_PROGRESS |
| 1044 | cerr << "ensure dependant arguments adds for arg #" << i << "\n"; |
| 1045 | #endif |
| 1046 | addCallInfo(DS, Call, i, InverseNodeMap[N], PoolDescs); |
| 1047 | |
| 1048 | // Keep sorted! |
| 1049 | finalizeConstruction(); |
| 1050 | } |
| 1051 | } |
| 1052 | } |
| 1053 | } |
Chris Lattner | 4c7f3df | 2002-03-30 04:02:31 +0000 | [diff] [blame] | 1054 | } |
| 1055 | |
Chris Lattner | cfb5f4c | 2002-03-30 09:12:35 +0000 | [diff] [blame] | 1056 | |
| 1057 | // transformFunctionBody - This transforms the instruction in 'F' to use the |
Chris Lattner | 5146a7d | 2002-04-12 20:23:15 +0000 | [diff] [blame] | 1058 | // pools specified in PoolDescs when modifying data structure nodes specified in |
| 1059 | // the PoolDescs map. Specifically, scalar values specified in the Scalars |
| 1060 | // vector must be remapped. IPFGraph is the closed data structure graph for F, |
| 1061 | // of which the PoolDescriptor nodes come from. |
Chris Lattner | cfb5f4c | 2002-03-30 09:12:35 +0000 | [diff] [blame] | 1062 | // |
| 1063 | void PoolAllocate::transformFunctionBody(Function *F, FunctionDSGraph &IPFGraph, |
Chris Lattner | 5146a7d | 2002-04-12 20:23:15 +0000 | [diff] [blame] | 1064 | map<DSNode*, PoolInfo> &PoolDescs) { |
Chris Lattner | cfb5f4c | 2002-03-30 09:12:35 +0000 | [diff] [blame] | 1065 | |
| 1066 | // Loop through the value map looking for scalars that refer to nonescaping |
| 1067 | // allocations. Add them to the Scalars vector. Note that we may have |
| 1068 | // multiple entries in the Scalars vector for each value if it points to more |
| 1069 | // than one object. |
| 1070 | // |
| 1071 | map<Value*, PointerValSet> &ValMap = IPFGraph.getValueMap(); |
| 1072 | vector<ScalarInfo> Scalars; |
| 1073 | |
Chris Lattner | 3e0e520 | 2002-04-14 06:14:41 +0000 | [diff] [blame] | 1074 | #ifdef DEBUG_TRANSFORM_PROGRESS |
Chris Lattner | 8e34333 | 2002-04-27 02:29:32 +0000 | [diff] [blame] | 1075 | cerr << "Building scalar map for fn '" << F->getName() << "' body:\n"; |
Chris Lattner | 3e0e520 | 2002-04-14 06:14:41 +0000 | [diff] [blame] | 1076 | #endif |
Chris Lattner | 072d3a0 | 2002-03-30 20:53:14 +0000 | [diff] [blame] | 1077 | |
Chris Lattner | cfb5f4c | 2002-03-30 09:12:35 +0000 | [diff] [blame] | 1078 | for (map<Value*, PointerValSet>::iterator I = ValMap.begin(), |
| 1079 | E = ValMap.end(); I != E; ++I) { |
| 1080 | const PointerValSet &PVS = I->second; // Set of things pointed to by scalar |
| 1081 | |
Chris Lattner | cfb5f4c | 2002-03-30 09:12:35 +0000 | [diff] [blame] | 1082 | // Check to see if the scalar points to a data structure node... |
| 1083 | for (unsigned i = 0, e = PVS.size(); i != e; ++i) { |
Chris Lattner | 8e34333 | 2002-04-27 02:29:32 +0000 | [diff] [blame] | 1084 | if (PVS[i].Index) { cerr << "Problem in " << F->getName() << " for " << I->first << "\n"; } |
Chris Lattner | cfb5f4c | 2002-03-30 09:12:35 +0000 | [diff] [blame] | 1085 | assert(PVS[i].Index == 0 && "Nonzero not handled yet!"); |
| 1086 | |
| 1087 | // If the allocation is in the nonescaping set... |
Chris Lattner | 5146a7d | 2002-04-12 20:23:15 +0000 | [diff] [blame] | 1088 | map<DSNode*, PoolInfo>::iterator AI = PoolDescs.find(PVS[i].Node); |
| 1089 | if (AI != PoolDescs.end()) { // Add it to the list of scalars |
| 1090 | Scalars.push_back(ScalarInfo(I->first, AI->second)); |
Chris Lattner | 3e0e520 | 2002-04-14 06:14:41 +0000 | [diff] [blame] | 1091 | #ifdef DEBUG_TRANSFORM_PROGRESS |
Chris Lattner | 5146a7d | 2002-04-12 20:23:15 +0000 | [diff] [blame] | 1092 | cerr << "\nScalar Mapping from:" << I->first |
| 1093 | << "Scalar Mapping to: "; PVS.print(cerr); |
Chris Lattner | 3e0e520 | 2002-04-14 06:14:41 +0000 | [diff] [blame] | 1094 | #endif |
Chris Lattner | 5146a7d | 2002-04-12 20:23:15 +0000 | [diff] [blame] | 1095 | } |
Chris Lattner | cfb5f4c | 2002-03-30 09:12:35 +0000 | [diff] [blame] | 1096 | } |
| 1097 | } |
| 1098 | |
Chris Lattner | 3e0e520 | 2002-04-14 06:14:41 +0000 | [diff] [blame] | 1099 | #ifdef DEBUG_TRANSFORM_PROGRESS |
Chris Lattner | 072d3a0 | 2002-03-30 20:53:14 +0000 | [diff] [blame] | 1100 | cerr << "\nIn '" << F->getName() |
Chris Lattner | d2d3a16 | 2002-03-29 03:40:59 +0000 | [diff] [blame] | 1101 | << "': Found the following values that point to poolable nodes:\n"; |
| 1102 | |
| 1103 | for (unsigned i = 0, e = Scalars.size(); i != e; ++i) |
Chris Lattner | 5146a7d | 2002-04-12 20:23:15 +0000 | [diff] [blame] | 1104 | cerr << Scalars[i].Val; |
| 1105 | cerr << "\n"; |
Chris Lattner | 3e0e520 | 2002-04-14 06:14:41 +0000 | [diff] [blame] | 1106 | #endif |
Chris Lattner | 54ce13f | 2002-03-29 05:50:20 +0000 | [diff] [blame] | 1107 | |
Chris Lattner | d250f42 | 2002-03-29 17:13:46 +0000 | [diff] [blame] | 1108 | // CallMap - Contain an entry for every call instruction that needs to be |
| 1109 | // transformed. Each entry in the map contains information about what we need |
| 1110 | // to do to each call site to change it to work. |
| 1111 | // |
| 1112 | map<CallInst*, TransformFunctionInfo> CallMap; |
Chris Lattner | 9d89190 | 2002-03-29 06:21:38 +0000 | [diff] [blame] | 1113 | |
Chris Lattner | 5146a7d | 2002-04-12 20:23:15 +0000 | [diff] [blame] | 1114 | // Now we need to figure out what called functions we need to transform, and |
Chris Lattner | d250f42 | 2002-03-29 17:13:46 +0000 | [diff] [blame] | 1115 | // how. To do this, we look at all of the scalars, seeing which functions are |
| 1116 | // either used as a scalar value (so they return a data structure), or are |
| 1117 | // passed one of our scalar values. |
| 1118 | // |
| 1119 | for (unsigned i = 0, e = Scalars.size(); i != e; ++i) { |
| 1120 | Value *ScalarVal = Scalars[i].Val; |
| 1121 | |
| 1122 | // Check to see if the scalar _IS_ a call... |
| 1123 | if (CallInst *CI = dyn_cast<CallInst>(ScalarVal)) |
| 1124 | // If so, add information about the pool it will be returning... |
Chris Lattner | 3b87167 | 2002-04-18 14:43:30 +0000 | [diff] [blame] | 1125 | CallMap[CI].addCallInfo(DS, CI, -1, Scalars[i].Pool.Node, PoolDescs); |
Chris Lattner | d250f42 | 2002-03-29 17:13:46 +0000 | [diff] [blame] | 1126 | |
| 1127 | // Check to see if the scalar is an operand to a call... |
| 1128 | for (Value::use_iterator UI = ScalarVal->use_begin(), |
| 1129 | UE = ScalarVal->use_end(); UI != UE; ++UI) { |
| 1130 | if (CallInst *CI = dyn_cast<CallInst>(*UI)) { |
| 1131 | // Find out which operand this is to the call instruction... |
| 1132 | User::op_iterator OI = find(CI->op_begin(), CI->op_end(), ScalarVal); |
| 1133 | assert(OI != CI->op_end() && "Call on use list but not an operand!?"); |
| 1134 | assert(OI != CI->op_begin() && "Pointer operand is call destination?"); |
| 1135 | |
| 1136 | // FIXME: This is broken if the same pointer is passed to a call more |
| 1137 | // than once! It will get multiple entries for the first pointer. |
| 1138 | |
| 1139 | // Add the operand number and pool handle to the call table... |
Chris Lattner | 3b87167 | 2002-04-18 14:43:30 +0000 | [diff] [blame] | 1140 | CallMap[CI].addCallInfo(DS, CI, OI-CI->op_begin()-1, |
| 1141 | Scalars[i].Pool.Node, PoolDescs); |
Chris Lattner | d250f42 | 2002-03-29 17:13:46 +0000 | [diff] [blame] | 1142 | } |
| 1143 | } |
| 1144 | } |
| 1145 | |
Chris Lattner | 3b87167 | 2002-04-18 14:43:30 +0000 | [diff] [blame] | 1146 | // Make sure that all dependant arguments are added as well. For example, if |
| 1147 | // we call foo(null, P) and foo treats it's first and second arguments as |
| 1148 | // belonging to the same data structure, the we MUST set up the CallMap to |
| 1149 | // know that the null needs to be transformed into an index as well. |
| 1150 | // |
| 1151 | for (map<CallInst*, TransformFunctionInfo>::iterator I = CallMap.begin(); |
| 1152 | I != CallMap.end(); ++I) |
| 1153 | I->second.ensureDependantArgumentsIncluded(DS, PoolDescs); |
| 1154 | |
Chris Lattner | 3e0e520 | 2002-04-14 06:14:41 +0000 | [diff] [blame] | 1155 | #ifdef DEBUG_TRANSFORM_PROGRESS |
Chris Lattner | d250f42 | 2002-03-29 17:13:46 +0000 | [diff] [blame] | 1156 | // Print out call map... |
| 1157 | for (map<CallInst*, TransformFunctionInfo>::iterator I = CallMap.begin(); |
| 1158 | I != CallMap.end(); ++I) { |
Chris Lattner | 5146a7d | 2002-04-12 20:23:15 +0000 | [diff] [blame] | 1159 | cerr << "For call: " << I->first; |
Chris Lattner | cfb5f4c | 2002-03-30 09:12:35 +0000 | [diff] [blame] | 1160 | cerr << I->second.Func->getName() << " must pass pool pointer for args #"; |
Chris Lattner | d250f42 | 2002-03-29 17:13:46 +0000 | [diff] [blame] | 1161 | for (unsigned i = 0; i < I->second.ArgInfo.size(); ++i) |
Chris Lattner | cfb5f4c | 2002-03-30 09:12:35 +0000 | [diff] [blame] | 1162 | cerr << I->second.ArgInfo[i].ArgNo << ", "; |
Chris Lattner | 5146a7d | 2002-04-12 20:23:15 +0000 | [diff] [blame] | 1163 | cerr << "\n\n"; |
Chris Lattner | d250f42 | 2002-03-29 17:13:46 +0000 | [diff] [blame] | 1164 | } |
Chris Lattner | 3e0e520 | 2002-04-14 06:14:41 +0000 | [diff] [blame] | 1165 | #endif |
Chris Lattner | d250f42 | 2002-03-29 17:13:46 +0000 | [diff] [blame] | 1166 | |
| 1167 | // Loop through all of the call nodes, recursively creating the new functions |
| 1168 | // that we want to call... This uses a map to prevent infinite recursion and |
| 1169 | // to avoid duplicating functions unneccesarily. |
| 1170 | // |
| 1171 | for (map<CallInst*, TransformFunctionInfo>::iterator I = CallMap.begin(), |
| 1172 | E = CallMap.end(); I != E; ++I) { |
Chris Lattner | cfb5f4c | 2002-03-30 09:12:35 +0000 | [diff] [blame] | 1173 | // Transform all of the functions we need, or at least ensure there is a |
| 1174 | // cached version available. |
Chris Lattner | 5146a7d | 2002-04-12 20:23:15 +0000 | [diff] [blame] | 1175 | transformFunction(I->second, IPFGraph, PoolDescs); |
Chris Lattner | d250f42 | 2002-03-29 17:13:46 +0000 | [diff] [blame] | 1176 | } |
| 1177 | |
Chris Lattner | 9d3493e | 2002-03-29 21:25:19 +0000 | [diff] [blame] | 1178 | // Now that all of the functions that we want to call are available, transform |
Chris Lattner | 5146a7d | 2002-04-12 20:23:15 +0000 | [diff] [blame] | 1179 | // the local function so that it uses the pools locally and passes them to the |
Chris Lattner | 9d3493e | 2002-03-29 21:25:19 +0000 | [diff] [blame] | 1180 | // functions that we just hacked up. |
| 1181 | // |
| 1182 | |
| 1183 | // First step, find the instructions to be modified. |
| 1184 | vector<Instruction*> InstToFix; |
| 1185 | for (unsigned i = 0, e = Scalars.size(); i != e; ++i) { |
| 1186 | Value *ScalarVal = Scalars[i].Val; |
| 1187 | |
| 1188 | // Check to see if the scalar _IS_ an instruction. If so, it is involved. |
| 1189 | if (Instruction *Inst = dyn_cast<Instruction>(ScalarVal)) |
| 1190 | InstToFix.push_back(Inst); |
| 1191 | |
| 1192 | // All all of the instructions that use the scalar as an operand... |
| 1193 | for (Value::use_iterator UI = ScalarVal->use_begin(), |
| 1194 | UE = ScalarVal->use_end(); UI != UE; ++UI) |
Chris Lattner | 5146a7d | 2002-04-12 20:23:15 +0000 | [diff] [blame] | 1195 | InstToFix.push_back(cast<Instruction>(*UI)); |
Chris Lattner | 9d3493e | 2002-03-29 21:25:19 +0000 | [diff] [blame] | 1196 | } |
| 1197 | |
Chris Lattner | 441d25a | 2002-04-13 23:13:18 +0000 | [diff] [blame] | 1198 | // Make sure that we get return instructions that return a null value from the |
| 1199 | // function... |
| 1200 | // |
| 1201 | if (!IPFGraph.getRetNodes().empty()) { |
| 1202 | assert(IPFGraph.getRetNodes().size() == 1 && "Can only return one node?"); |
| 1203 | PointerVal RetNode = IPFGraph.getRetNodes()[0]; |
| 1204 | assert(RetNode.Index == 0 && "Subindexing not implemented yet!"); |
| 1205 | |
| 1206 | // Only process return instructions if the return value of this function is |
| 1207 | // part of one of the data structures we are transforming... |
| 1208 | // |
| 1209 | if (PoolDescs.count(RetNode.Node)) { |
| 1210 | // Loop over all of the basic blocks, adding return instructions... |
| 1211 | for (Function::iterator I = F->begin(), E = F->end(); I != E; ++I) |
| 1212 | if (ReturnInst *RI = dyn_cast<ReturnInst>((*I)->getTerminator())) |
| 1213 | InstToFix.push_back(RI); |
| 1214 | } |
| 1215 | } |
| 1216 | |
| 1217 | |
| 1218 | |
Chris Lattner | 9d3493e | 2002-03-29 21:25:19 +0000 | [diff] [blame] | 1219 | // Eliminate duplicates by sorting, then removing equal neighbors. |
| 1220 | sort(InstToFix.begin(), InstToFix.end()); |
| 1221 | InstToFix.erase(unique(InstToFix.begin(), InstToFix.end()), InstToFix.end()); |
| 1222 | |
Chris Lattner | 5146a7d | 2002-04-12 20:23:15 +0000 | [diff] [blame] | 1223 | // Loop over all of the instructions to transform, creating the new |
| 1224 | // replacement instructions for them. This also unlinks them from the |
| 1225 | // function so they can be safely deleted later. |
| 1226 | // |
| 1227 | map<Value*, Value*> XFormMap; |
| 1228 | NewInstructionCreator NIC(*this, Scalars, CallMap, XFormMap); |
Chris Lattner | d250f42 | 2002-03-29 17:13:46 +0000 | [diff] [blame] | 1229 | |
Chris Lattner | 5146a7d | 2002-04-12 20:23:15 +0000 | [diff] [blame] | 1230 | // Visit all instructions... creating the new instructions that we need and |
| 1231 | // unlinking the old instructions from the function... |
| 1232 | // |
Chris Lattner | 3e0e520 | 2002-04-14 06:14:41 +0000 | [diff] [blame] | 1233 | #ifdef DEBUG_TRANSFORM_PROGRESS |
Chris Lattner | 5146a7d | 2002-04-12 20:23:15 +0000 | [diff] [blame] | 1234 | for (unsigned i = 0, e = InstToFix.size(); i != e; ++i) { |
| 1235 | cerr << "Fixing: " << InstToFix[i]; |
| 1236 | NIC.visit(InstToFix[i]); |
| 1237 | } |
Chris Lattner | 3e0e520 | 2002-04-14 06:14:41 +0000 | [diff] [blame] | 1238 | #else |
| 1239 | NIC.visit(InstToFix.begin(), InstToFix.end()); |
| 1240 | #endif |
Chris Lattner | 5146a7d | 2002-04-12 20:23:15 +0000 | [diff] [blame] | 1241 | |
| 1242 | // Make all instructions we will delete "let go" of their operands... so that |
| 1243 | // we can safely delete Arguments whose types have changed... |
| 1244 | // |
| 1245 | for_each(InstToFix.begin(), InstToFix.end(), |
| 1246 | mem_fun(&Instruction::dropAllReferences)); |
| 1247 | |
| 1248 | // Loop through all of the pointer arguments coming into the function, |
| 1249 | // replacing them with arguments of POINTERTYPE to match the function type of |
| 1250 | // the function. |
| 1251 | // |
| 1252 | FunctionType::ParamTypes::const_iterator TI = |
| 1253 | F->getFunctionType()->getParamTypes().begin(); |
| 1254 | for (Function::ArgumentListType::iterator I = F->getArgumentList().begin(), |
| 1255 | E = F->getArgumentList().end(); I != E; ++I, ++TI) { |
| 1256 | Argument *Arg = *I; |
| 1257 | if (Arg->getType() != *TI) { |
| 1258 | assert(isa<PointerType>(Arg->getType()) && *TI == POINTERTYPE); |
| 1259 | Argument *NewArg = new Argument(*TI, Arg->getName()); |
| 1260 | XFormMap[Arg] = NewArg; // Map old arg into new arg... |
| 1261 | |
Chris Lattner | 5146a7d | 2002-04-12 20:23:15 +0000 | [diff] [blame] | 1262 | // Replace the old argument and then delete it... |
| 1263 | delete F->getArgumentList().replaceWith(I, NewArg); |
| 1264 | } |
| 1265 | } |
| 1266 | |
| 1267 | // Now that all of the new instructions have been created, we can update all |
| 1268 | // of the references to dummy values to be references to the actual values |
| 1269 | // that are computed. |
| 1270 | // |
| 1271 | NIC.updateReferences(); |
| 1272 | |
Chris Lattner | 3e0e520 | 2002-04-14 06:14:41 +0000 | [diff] [blame] | 1273 | #ifdef DEBUG_TRANSFORM_PROGRESS |
Chris Lattner | 5146a7d | 2002-04-12 20:23:15 +0000 | [diff] [blame] | 1274 | cerr << "TRANSFORMED FUNCTION:\n" << F; |
Chris Lattner | 3e0e520 | 2002-04-14 06:14:41 +0000 | [diff] [blame] | 1275 | #endif |
Chris Lattner | 5146a7d | 2002-04-12 20:23:15 +0000 | [diff] [blame] | 1276 | |
| 1277 | // Delete all of the "instructions to fix" |
| 1278 | for_each(InstToFix.begin(), InstToFix.end(), deleter<Instruction>); |
Chris Lattner | d250f42 | 2002-03-29 17:13:46 +0000 | [diff] [blame] | 1279 | |
Chris Lattner | 09b9212 | 2002-04-15 22:42:23 +0000 | [diff] [blame] | 1280 | // Eliminate pool base loads that we can easily prove are redundant |
| 1281 | if (!DisableRLE) |
| 1282 | PoolBaseLoadEliminator(PoolDescs).visit(F); |
| 1283 | |
Chris Lattner | 9d3493e | 2002-03-29 21:25:19 +0000 | [diff] [blame] | 1284 | // Since we have liberally hacked the function to pieces, we want to inform |
| 1285 | // the datastructure pass that its internal representation is out of date. |
| 1286 | // |
| 1287 | DS->invalidateFunction(F); |
Chris Lattner | d250f42 | 2002-03-29 17:13:46 +0000 | [diff] [blame] | 1288 | } |
| 1289 | |
Chris Lattner | cfb5f4c | 2002-03-30 09:12:35 +0000 | [diff] [blame] | 1290 | |
| 1291 | |
| 1292 | // transformFunction - Transform the specified function the specified way. It |
| 1293 | // we have already transformed that function that way, don't do anything. The |
| 1294 | // nodes in the TransformFunctionInfo come out of callers data structure graph. |
| 1295 | // |
| 1296 | void PoolAllocate::transformFunction(TransformFunctionInfo &TFI, |
Chris Lattner | 5146a7d | 2002-04-12 20:23:15 +0000 | [diff] [blame] | 1297 | FunctionDSGraph &CallerIPGraph, |
| 1298 | map<DSNode*, PoolInfo> &CallerPoolDesc) { |
Chris Lattner | d250f42 | 2002-03-29 17:13:46 +0000 | [diff] [blame] | 1299 | if (getTransformedFunction(TFI)) return; // Function xformation already done? |
| 1300 | |
Chris Lattner | 3e0e520 | 2002-04-14 06:14:41 +0000 | [diff] [blame] | 1301 | #ifdef DEBUG_TRANSFORM_PROGRESS |
Chris Lattner | 5146a7d | 2002-04-12 20:23:15 +0000 | [diff] [blame] | 1302 | cerr << "********** Entering transformFunction for " |
Chris Lattner | 9acfbee | 2002-03-31 07:17:46 +0000 | [diff] [blame] | 1303 | << TFI.Func->getName() << ":\n"; |
| 1304 | for (unsigned i = 0, e = TFI.ArgInfo.size(); i != e; ++i) |
| 1305 | cerr << " ArgInfo[" << i << "] = " << TFI.ArgInfo[i].ArgNo << "\n"; |
| 1306 | cerr << "\n"; |
Chris Lattner | 3e0e520 | 2002-04-14 06:14:41 +0000 | [diff] [blame] | 1307 | #endif |
Chris Lattner | 9acfbee | 2002-03-31 07:17:46 +0000 | [diff] [blame] | 1308 | |
Chris Lattner | cfb5f4c | 2002-03-30 09:12:35 +0000 | [diff] [blame] | 1309 | const FunctionType *OldFuncType = TFI.Func->getFunctionType(); |
Chris Lattner | d250f42 | 2002-03-29 17:13:46 +0000 | [diff] [blame] | 1310 | |
Chris Lattner | a744451 | 2002-03-29 19:05:48 +0000 | [diff] [blame] | 1311 | assert(!OldFuncType->isVarArg() && "Vararg functions not handled yet!"); |
Chris Lattner | d250f42 | 2002-03-29 17:13:46 +0000 | [diff] [blame] | 1312 | |
Chris Lattner | a744451 | 2002-03-29 19:05:48 +0000 | [diff] [blame] | 1313 | // Build the type for the new function that we are transforming |
| 1314 | vector<const Type*> ArgTys; |
Chris Lattner | 5146a7d | 2002-04-12 20:23:15 +0000 | [diff] [blame] | 1315 | ArgTys.reserve(OldFuncType->getNumParams()+TFI.ArgInfo.size()); |
Chris Lattner | a744451 | 2002-03-29 19:05:48 +0000 | [diff] [blame] | 1316 | for (unsigned i = 0, e = OldFuncType->getNumParams(); i != e; ++i) |
| 1317 | ArgTys.push_back(OldFuncType->getParamType(i)); |
| 1318 | |
Chris Lattner | 5146a7d | 2002-04-12 20:23:15 +0000 | [diff] [blame] | 1319 | const Type *RetType = OldFuncType->getReturnType(); |
| 1320 | |
Chris Lattner | a744451 | 2002-03-29 19:05:48 +0000 | [diff] [blame] | 1321 | // Add one pool pointer for every argument that needs to be supplemented. |
Chris Lattner | 5146a7d | 2002-04-12 20:23:15 +0000 | [diff] [blame] | 1322 | for (unsigned i = 0, e = TFI.ArgInfo.size(); i != e; ++i) { |
| 1323 | if (TFI.ArgInfo[i].ArgNo == -1) |
| 1324 | RetType = POINTERTYPE; // Return a pointer |
| 1325 | else |
| 1326 | ArgTys[TFI.ArgInfo[i].ArgNo] = POINTERTYPE; // Pass a pointer |
| 1327 | ArgTys.push_back(PointerType::get(CallerPoolDesc.find(TFI.ArgInfo[i].Node) |
| 1328 | ->second.PoolType)); |
| 1329 | } |
Chris Lattner | a744451 | 2002-03-29 19:05:48 +0000 | [diff] [blame] | 1330 | |
| 1331 | // Build the new function type... |
Chris Lattner | 5146a7d | 2002-04-12 20:23:15 +0000 | [diff] [blame] | 1332 | const FunctionType *NewFuncType = FunctionType::get(RetType, ArgTys, |
| 1333 | OldFuncType->isVarArg()); |
Chris Lattner | a744451 | 2002-03-29 19:05:48 +0000 | [diff] [blame] | 1334 | |
| 1335 | // The new function is internal, because we know that only we can call it. |
| 1336 | // This also helps subsequent IP transformations to eliminate duplicated pool |
Chris Lattner | 5146a7d | 2002-04-12 20:23:15 +0000 | [diff] [blame] | 1337 | // pointers (which look like the same value is always passed into a parameter, |
| 1338 | // allowing it to be easily eliminated). |
Chris Lattner | a744451 | 2002-03-29 19:05:48 +0000 | [diff] [blame] | 1339 | // |
| 1340 | Function *NewFunc = new Function(NewFuncType, true, |
Chris Lattner | cfb5f4c | 2002-03-30 09:12:35 +0000 | [diff] [blame] | 1341 | TFI.Func->getName()+".poolxform"); |
Chris Lattner | a744451 | 2002-03-29 19:05:48 +0000 | [diff] [blame] | 1342 | CurModule->getFunctionList().push_back(NewFunc); |
| 1343 | |
Chris Lattner | 5146a7d | 2002-04-12 20:23:15 +0000 | [diff] [blame] | 1344 | |
Chris Lattner | 3e0e520 | 2002-04-14 06:14:41 +0000 | [diff] [blame] | 1345 | #ifdef DEBUG_TRANSFORM_PROGRESS |
Chris Lattner | 5146a7d | 2002-04-12 20:23:15 +0000 | [diff] [blame] | 1346 | cerr << "Created function prototype: " << NewFunc << "\n"; |
Chris Lattner | 3e0e520 | 2002-04-14 06:14:41 +0000 | [diff] [blame] | 1347 | #endif |
Chris Lattner | 5146a7d | 2002-04-12 20:23:15 +0000 | [diff] [blame] | 1348 | |
Chris Lattner | a744451 | 2002-03-29 19:05:48 +0000 | [diff] [blame] | 1349 | // Add the newly formed function to the TransformedFunctions table so that |
| 1350 | // infinite recursion does not occur! |
| 1351 | // |
| 1352 | TransformedFunctions[TFI] = NewFunc; |
| 1353 | |
| 1354 | // Add arguments to the function... starting with all of the old arguments |
| 1355 | vector<Value*> ArgMap; |
Chris Lattner | cfb5f4c | 2002-03-30 09:12:35 +0000 | [diff] [blame] | 1356 | for (unsigned i = 0, e = TFI.Func->getArgumentList().size(); i != e; ++i) { |
Chris Lattner | 73e2142 | 2002-04-09 19:48:49 +0000 | [diff] [blame] | 1357 | const Argument *OFA = TFI.Func->getArgumentList()[i]; |
| 1358 | Argument *NFA = new Argument(OFA->getType(), OFA->getName()); |
Chris Lattner | a744451 | 2002-03-29 19:05:48 +0000 | [diff] [blame] | 1359 | NewFunc->getArgumentList().push_back(NFA); |
| 1360 | ArgMap.push_back(NFA); // Keep track of the arguments |
| 1361 | } |
| 1362 | |
| 1363 | // Now add all of the arguments corresponding to pools passed in... |
| 1364 | for (unsigned i = 0, e = TFI.ArgInfo.size(); i != e; ++i) { |
Chris Lattner | 5146a7d | 2002-04-12 20:23:15 +0000 | [diff] [blame] | 1365 | CallArgInfo &AI = TFI.ArgInfo[i]; |
Chris Lattner | a744451 | 2002-03-29 19:05:48 +0000 | [diff] [blame] | 1366 | string Name; |
Chris Lattner | 5146a7d | 2002-04-12 20:23:15 +0000 | [diff] [blame] | 1367 | if (AI.ArgNo == -1) |
| 1368 | Name = "ret"; |
Chris Lattner | a744451 | 2002-03-29 19:05:48 +0000 | [diff] [blame] | 1369 | else |
Chris Lattner | 5146a7d | 2002-04-12 20:23:15 +0000 | [diff] [blame] | 1370 | Name = ArgMap[AI.ArgNo]->getName(); // Get the arg name |
| 1371 | const Type *Ty = PointerType::get(CallerPoolDesc[AI.Node].PoolType); |
| 1372 | Argument *NFA = new Argument(Ty, Name+".pool"); |
Chris Lattner | a744451 | 2002-03-29 19:05:48 +0000 | [diff] [blame] | 1373 | NewFunc->getArgumentList().push_back(NFA); |
| 1374 | } |
| 1375 | |
| 1376 | // Now clone the body of the old function into the new function... |
Chris Lattner | cfb5f4c | 2002-03-30 09:12:35 +0000 | [diff] [blame] | 1377 | CloneFunctionInto(NewFunc, TFI.Func, ArgMap); |
Chris Lattner | a744451 | 2002-03-29 19:05:48 +0000 | [diff] [blame] | 1378 | |
Chris Lattner | 9d3493e | 2002-03-29 21:25:19 +0000 | [diff] [blame] | 1379 | // Okay, now we have a function that is identical to the old one, except that |
Chris Lattner | cfb5f4c | 2002-03-30 09:12:35 +0000 | [diff] [blame] | 1380 | // it has extra arguments for the pools coming in. Now we have to get the |
| 1381 | // data structure graph for the function we are replacing, and figure out how |
| 1382 | // our graph nodes map to the graph nodes in the dest function. |
| 1383 | // |
Chris Lattner | 072d3a0 | 2002-03-30 20:53:14 +0000 | [diff] [blame] | 1384 | FunctionDSGraph &DSGraph = DS->getClosedDSGraph(NewFunc); |
Chris Lattner | 9d3493e | 2002-03-29 21:25:19 +0000 | [diff] [blame] | 1385 | |
Chris Lattner | 5146a7d | 2002-04-12 20:23:15 +0000 | [diff] [blame] | 1386 | // NodeMapping - Multimap from callers graph to called graph. We are |
| 1387 | // guaranteed that the called function graph has more nodes than the caller, |
| 1388 | // or exactly the same number of nodes. This is because the called function |
| 1389 | // might not know that two nodes are merged when considering the callers |
| 1390 | // context, but the caller obviously does. Because of this, a single node in |
| 1391 | // the calling function's data structure graph can map to multiple nodes in |
| 1392 | // the called functions graph. |
Chris Lattner | cfb5f4c | 2002-03-30 09:12:35 +0000 | [diff] [blame] | 1393 | // |
| 1394 | map<DSNode*, PointerValSet> NodeMapping; |
Chris Lattner | 9d3493e | 2002-03-29 21:25:19 +0000 | [diff] [blame] | 1395 | |
Chris Lattner | 072d3a0 | 2002-03-30 20:53:14 +0000 | [diff] [blame] | 1396 | CalculateNodeMapping(NewFunc, TFI, CallerIPGraph, DSGraph, |
Chris Lattner | cfb5f4c | 2002-03-30 09:12:35 +0000 | [diff] [blame] | 1397 | NodeMapping); |
| 1398 | |
| 1399 | // Print out the node mapping... |
Chris Lattner | 3e0e520 | 2002-04-14 06:14:41 +0000 | [diff] [blame] | 1400 | #ifdef DEBUG_TRANSFORM_PROGRESS |
Chris Lattner | 072d3a0 | 2002-03-30 20:53:14 +0000 | [diff] [blame] | 1401 | cerr << "\nNode mapping for call of " << NewFunc->getName() << "\n"; |
Chris Lattner | cfb5f4c | 2002-03-30 09:12:35 +0000 | [diff] [blame] | 1402 | for (map<DSNode*, PointerValSet>::iterator I = NodeMapping.begin(); |
| 1403 | I != NodeMapping.end(); ++I) { |
| 1404 | cerr << "Map: "; I->first->print(cerr); |
| 1405 | cerr << "To: "; I->second.print(cerr); |
| 1406 | cerr << "\n"; |
| 1407 | } |
Chris Lattner | 3e0e520 | 2002-04-14 06:14:41 +0000 | [diff] [blame] | 1408 | #endif |
Chris Lattner | cfb5f4c | 2002-03-30 09:12:35 +0000 | [diff] [blame] | 1409 | |
| 1410 | // Fill in the PoolDescriptor information for the transformed function so that |
| 1411 | // it can determine which value holds the pool descriptor for each data |
| 1412 | // structure node that it accesses. |
| 1413 | // |
Chris Lattner | 5146a7d | 2002-04-12 20:23:15 +0000 | [diff] [blame] | 1414 | map<DSNode*, PoolInfo> PoolDescs; |
Chris Lattner | cfb5f4c | 2002-03-30 09:12:35 +0000 | [diff] [blame] | 1415 | |
Chris Lattner | 3e0e520 | 2002-04-14 06:14:41 +0000 | [diff] [blame] | 1416 | #ifdef DEBUG_TRANSFORM_PROGRESS |
Chris Lattner | 072d3a0 | 2002-03-30 20:53:14 +0000 | [diff] [blame] | 1417 | cerr << "\nCalculating the pool descriptor map:\n"; |
Chris Lattner | 3e0e520 | 2002-04-14 06:14:41 +0000 | [diff] [blame] | 1418 | #endif |
Chris Lattner | cfb5f4c | 2002-03-30 09:12:35 +0000 | [diff] [blame] | 1419 | |
Chris Lattner | 5146a7d | 2002-04-12 20:23:15 +0000 | [diff] [blame] | 1420 | // Calculate as much of the pool descriptor map as possible. Since we have |
| 1421 | // the node mapping between the caller and callee functions, and we have the |
| 1422 | // pool descriptor information of the caller, we can calculate a partical pool |
| 1423 | // descriptor map for the called function. |
| 1424 | // |
| 1425 | // The nodes that we do not have complete information for are the ones that |
| 1426 | // are accessed by loading pointers derived from arguments passed in, but that |
| 1427 | // are not passed in directly. In this case, we have all of the information |
| 1428 | // except a pool value. If the called function refers to this pool, the pool |
| 1429 | // value will be loaded from the pool graph and added to the map as neccesary. |
| 1430 | // |
| 1431 | for (map<DSNode*, PointerValSet>::iterator I = NodeMapping.begin(); |
| 1432 | I != NodeMapping.end(); ++I) { |
| 1433 | DSNode *CallerNode = I->first; |
| 1434 | PoolInfo &CallerPI = CallerPoolDesc[CallerNode]; |
Chris Lattner | cfb5f4c | 2002-03-30 09:12:35 +0000 | [diff] [blame] | 1435 | |
Chris Lattner | 5146a7d | 2002-04-12 20:23:15 +0000 | [diff] [blame] | 1436 | // Check to see if we have a node pointer passed in for this value... |
| 1437 | Value *CalleeValue = 0; |
| 1438 | for (unsigned a = 0, ae = TFI.ArgInfo.size(); a != ae; ++a) |
| 1439 | if (TFI.ArgInfo[a].Node == CallerNode) { |
| 1440 | // Calculate the argument number that the pool is to the function |
| 1441 | // call... The call instruction should not have the pool operands added |
| 1442 | // yet. |
| 1443 | unsigned ArgNo = TFI.Call->getNumOperands()-1+a; |
Chris Lattner | 3e0e520 | 2002-04-14 06:14:41 +0000 | [diff] [blame] | 1444 | #ifdef DEBUG_TRANSFORM_PROGRESS |
Chris Lattner | 5146a7d | 2002-04-12 20:23:15 +0000 | [diff] [blame] | 1445 | cerr << "Should be argument #: " << ArgNo << "[i = " << a << "]\n"; |
Chris Lattner | 3e0e520 | 2002-04-14 06:14:41 +0000 | [diff] [blame] | 1446 | #endif |
Chris Lattner | 5146a7d | 2002-04-12 20:23:15 +0000 | [diff] [blame] | 1447 | assert(ArgNo < NewFunc->getArgumentList().size() && |
| 1448 | "Call already has pool arguments added??"); |
Chris Lattner | cfb5f4c | 2002-03-30 09:12:35 +0000 | [diff] [blame] | 1449 | |
Chris Lattner | 5146a7d | 2002-04-12 20:23:15 +0000 | [diff] [blame] | 1450 | // Map the pool argument into the called function... |
| 1451 | CalleeValue = NewFunc->getArgumentList()[ArgNo]; |
| 1452 | break; // Found value, quit loop |
| 1453 | } |
Chris Lattner | cfb5f4c | 2002-03-30 09:12:35 +0000 | [diff] [blame] | 1454 | |
Chris Lattner | 5146a7d | 2002-04-12 20:23:15 +0000 | [diff] [blame] | 1455 | // Loop over all of the data structure nodes that this incoming node maps to |
| 1456 | // Creating a PoolInfo structure for them. |
| 1457 | for (unsigned i = 0, e = I->second.size(); i != e; ++i) { |
| 1458 | assert(I->second[i].Index == 0 && "Doesn't handle subindexing yet!"); |
| 1459 | DSNode *CalleeNode = I->second[i].Node; |
| 1460 | |
| 1461 | // Add the descriptor. We already know everything about it by now, much |
| 1462 | // of it is the same as the caller info. |
| 1463 | // |
| 1464 | PoolDescs.insert(make_pair(CalleeNode, |
| 1465 | PoolInfo(CalleeNode, CalleeValue, |
| 1466 | CallerPI.NewType, |
| 1467 | CallerPI.PoolType))); |
Chris Lattner | cfb5f4c | 2002-03-30 09:12:35 +0000 | [diff] [blame] | 1468 | } |
Chris Lattner | 072d3a0 | 2002-03-30 20:53:14 +0000 | [diff] [blame] | 1469 | } |
| 1470 | |
| 1471 | // We must destroy the node mapping so that we don't have latent references |
| 1472 | // into the data structure graph for the new function. Otherwise we get |
| 1473 | // assertion failures when transformFunctionBody tries to invalidate the |
| 1474 | // graph. |
| 1475 | // |
| 1476 | NodeMapping.clear(); |
Chris Lattner | cfb5f4c | 2002-03-30 09:12:35 +0000 | [diff] [blame] | 1477 | |
| 1478 | // Now that we know everything we need about the function, transform the body |
| 1479 | // now! |
| 1480 | // |
Chris Lattner | 5146a7d | 2002-04-12 20:23:15 +0000 | [diff] [blame] | 1481 | transformFunctionBody(NewFunc, DSGraph, PoolDescs); |
| 1482 | |
Chris Lattner | 3e0e520 | 2002-04-14 06:14:41 +0000 | [diff] [blame] | 1483 | #ifdef DEBUG_TRANSFORM_PROGRESS |
Chris Lattner | 5146a7d | 2002-04-12 20:23:15 +0000 | [diff] [blame] | 1484 | cerr << "Function after transformation:\n" << NewFunc; |
Chris Lattner | 3e0e520 | 2002-04-14 06:14:41 +0000 | [diff] [blame] | 1485 | #endif |
Chris Lattner | 9d89190 | 2002-03-29 06:21:38 +0000 | [diff] [blame] | 1486 | } |
| 1487 | |
Chris Lattner | 027a675 | 2002-04-13 19:25:57 +0000 | [diff] [blame] | 1488 | static unsigned countPointerTypes(const Type *Ty) { |
| 1489 | if (isa<PointerType>(Ty)) { |
| 1490 | return 1; |
| 1491 | } else if (StructType *STy = dyn_cast<StructType>(Ty)) { |
| 1492 | unsigned Num = 0; |
| 1493 | for (unsigned i = 0, e = STy->getElementTypes().size(); i != e; ++i) |
| 1494 | Num += countPointerTypes(STy->getElementTypes()[i]); |
| 1495 | return Num; |
| 1496 | } else if (ArrayType *ATy = dyn_cast<ArrayType>(Ty)) { |
| 1497 | return countPointerTypes(ATy->getElementType()); |
| 1498 | } else { |
| 1499 | assert(Ty->isPrimitiveType() && "Unknown derived type!"); |
| 1500 | return 0; |
| 1501 | } |
| 1502 | } |
Chris Lattner | 9d89190 | 2002-03-29 06:21:38 +0000 | [diff] [blame] | 1503 | |
| 1504 | // CreatePools - Insert instructions into the function we are processing to |
| 1505 | // create all of the memory pool objects themselves. This also inserts |
| 1506 | // destruction code. Add an alloca for each pool that is allocated to the |
Chris Lattner | 5146a7d | 2002-04-12 20:23:15 +0000 | [diff] [blame] | 1507 | // PoolDescs vector. |
Chris Lattner | 9d89190 | 2002-03-29 06:21:38 +0000 | [diff] [blame] | 1508 | // |
| 1509 | void PoolAllocate::CreatePools(Function *F, const vector<AllocDSNode*> &Allocs, |
Chris Lattner | 5146a7d | 2002-04-12 20:23:15 +0000 | [diff] [blame] | 1510 | map<DSNode*, PoolInfo> &PoolDescs) { |
| 1511 | // Find all of the return nodes in the function... |
Chris Lattner | 54ce13f | 2002-03-29 05:50:20 +0000 | [diff] [blame] | 1512 | vector<BasicBlock*> ReturnNodes; |
| 1513 | for (Function::iterator I = F->begin(), E = F->end(); I != E; ++I) |
| 1514 | if (isa<ReturnInst>((*I)->getTerminator())) |
| 1515 | ReturnNodes.push_back(*I); |
Chris Lattner | 54ce13f | 2002-03-29 05:50:20 +0000 | [diff] [blame] | 1516 | |
Chris Lattner | 3b87167 | 2002-04-18 14:43:30 +0000 | [diff] [blame] | 1517 | #ifdef DEBUG_CREATE_POOLS |
| 1518 | cerr << "Allocs that we are pool allocating:\n"; |
| 1519 | for (unsigned i = 0, e = Allocs.size(); i != e; ++i) |
| 1520 | Allocs[i]->dump(); |
| 1521 | #endif |
| 1522 | |
Chris Lattner | 5146a7d | 2002-04-12 20:23:15 +0000 | [diff] [blame] | 1523 | map<DSNode*, PATypeHolder> AbsPoolTyMap; |
| 1524 | |
| 1525 | // First pass over the allocations to process... |
| 1526 | for (unsigned i = 0, e = Allocs.size(); i != e; ++i) { |
| 1527 | // Create the pooldescriptor mapping... with null entries for everything |
| 1528 | // except the node & NewType fields. |
| 1529 | // |
| 1530 | map<DSNode*, PoolInfo>::iterator PI = |
| 1531 | PoolDescs.insert(make_pair(Allocs[i], PoolInfo(Allocs[i]))).first; |
| 1532 | |
Chris Lattner | 027a675 | 2002-04-13 19:25:57 +0000 | [diff] [blame] | 1533 | // Add a symbol table entry for the new type if there was one for the old |
| 1534 | // type... |
| 1535 | string OldName = CurModule->getTypeName(Allocs[i]->getType()); |
Chris Lattner | 8e34333 | 2002-04-27 02:29:32 +0000 | [diff] [blame] | 1536 | if (OldName.empty()) OldName = "node"; |
| 1537 | CurModule->addTypeName(OldName+".p", PI->second.NewType); |
Chris Lattner | 027a675 | 2002-04-13 19:25:57 +0000 | [diff] [blame] | 1538 | |
Chris Lattner | 5146a7d | 2002-04-12 20:23:15 +0000 | [diff] [blame] | 1539 | // Create the abstract pool types that will need to be resolved in a second |
| 1540 | // pass once an abstract type is created for each pool. |
| 1541 | // |
| 1542 | // Can only handle limited shapes for now... |
Chris Lattner | 8e34333 | 2002-04-27 02:29:32 +0000 | [diff] [blame] | 1543 | const Type *OldNodeTy = Allocs[i]->getType(); |
Chris Lattner | 5146a7d | 2002-04-12 20:23:15 +0000 | [diff] [blame] | 1544 | vector<const Type*> PoolTypes; |
| 1545 | |
| 1546 | // Pool type is the first element of the pool descriptor type... |
| 1547 | PoolTypes.push_back(getPoolType(PoolDescs[Allocs[i]].NewType)); |
Chris Lattner | 027a675 | 2002-04-13 19:25:57 +0000 | [diff] [blame] | 1548 | |
| 1549 | unsigned NumPointers = countPointerTypes(OldNodeTy); |
| 1550 | while (NumPointers--) // Add a different opaque type for each pointer |
| 1551 | PoolTypes.push_back(OpaqueType::get()); |
| 1552 | |
Chris Lattner | 5146a7d | 2002-04-12 20:23:15 +0000 | [diff] [blame] | 1553 | assert(Allocs[i]->getNumLinks() == PoolTypes.size()-1 && |
| 1554 | "Node should have same number of pointers as pool!"); |
| 1555 | |
Chris Lattner | 027a675 | 2002-04-13 19:25:57 +0000 | [diff] [blame] | 1556 | StructType *PoolType = StructType::get(PoolTypes); |
| 1557 | |
| 1558 | // Add a symbol table entry for the pooltype if possible... |
Chris Lattner | 8e34333 | 2002-04-27 02:29:32 +0000 | [diff] [blame] | 1559 | CurModule->addTypeName(OldName+".pool", PoolType); |
Chris Lattner | 027a675 | 2002-04-13 19:25:57 +0000 | [diff] [blame] | 1560 | |
Chris Lattner | 5146a7d | 2002-04-12 20:23:15 +0000 | [diff] [blame] | 1561 | // Create the pool type, with opaque values for pointers... |
Chris Lattner | 027a675 | 2002-04-13 19:25:57 +0000 | [diff] [blame] | 1562 | AbsPoolTyMap.insert(make_pair(Allocs[i], PoolType)); |
Chris Lattner | 5146a7d | 2002-04-12 20:23:15 +0000 | [diff] [blame] | 1563 | #ifdef DEBUG_CREATE_POOLS |
| 1564 | cerr << "POOL TY: " << AbsPoolTyMap.find(Allocs[i])->second.get() << "\n"; |
| 1565 | #endif |
| 1566 | } |
| 1567 | |
| 1568 | // Now that we have types for all of the pool types, link them all together. |
| 1569 | for (unsigned i = 0, e = Allocs.size(); i != e; ++i) { |
| 1570 | PATypeHolder &PoolTyH = AbsPoolTyMap.find(Allocs[i])->second; |
| 1571 | |
| 1572 | // Resolve all of the outgoing pointer types of this pool node... |
| 1573 | for (unsigned p = 0, pe = Allocs[i]->getNumLinks(); p != pe; ++p) { |
| 1574 | PointerValSet &PVS = Allocs[i]->getLink(p); |
| 1575 | assert(!PVS.empty() && "Outgoing edge is empty, field unused, can" |
| 1576 | " probably just leave the type opaque or something dumb."); |
| 1577 | unsigned Out; |
| 1578 | for (Out = 0; AbsPoolTyMap.count(PVS[Out].Node) == 0; ++Out) |
| 1579 | assert(Out != PVS.size() && "No edge to an outgoing allocation node!?"); |
| 1580 | |
| 1581 | assert(PVS[Out].Index == 0 && "Subindexing not implemented yet!"); |
| 1582 | |
| 1583 | // The actual struct type could change each time through the loop, so it's |
| 1584 | // NOT loop invariant. |
| 1585 | StructType *PoolTy = cast<StructType>(PoolTyH.get()); |
| 1586 | |
| 1587 | // Get the opaque type... |
| 1588 | DerivedType *ElTy = |
| 1589 | cast<DerivedType>(PoolTy->getElementTypes()[p+1].get()); |
| 1590 | |
| 1591 | #ifdef DEBUG_CREATE_POOLS |
| 1592 | cerr << "Refining " << ElTy << " of " << PoolTy << " to " |
| 1593 | << AbsPoolTyMap.find(PVS[Out].Node)->second.get() << "\n"; |
| 1594 | #endif |
| 1595 | |
| 1596 | const Type *RefPoolTy = AbsPoolTyMap.find(PVS[Out].Node)->second.get(); |
| 1597 | ElTy->refineAbstractTypeTo(PointerType::get(RefPoolTy)); |
| 1598 | |
| 1599 | #ifdef DEBUG_CREATE_POOLS |
| 1600 | cerr << "Result pool type is: " << PoolTyH.get() << "\n"; |
| 1601 | #endif |
| 1602 | } |
| 1603 | } |
| 1604 | |
| 1605 | // Create the code that goes in the entry and exit nodes for the function... |
Chris Lattner | 54ce13f | 2002-03-29 05:50:20 +0000 | [diff] [blame] | 1606 | vector<Instruction*> EntryNodeInsts; |
| 1607 | for (unsigned i = 0, e = Allocs.size(); i != e; ++i) { |
Chris Lattner | 5146a7d | 2002-04-12 20:23:15 +0000 | [diff] [blame] | 1608 | PoolInfo &PI = PoolDescs[Allocs[i]]; |
| 1609 | |
| 1610 | // Fill in the pool type for this pool... |
| 1611 | PI.PoolType = AbsPoolTyMap.find(Allocs[i])->second.get(); |
| 1612 | assert(!PI.PoolType->isAbstract() && |
| 1613 | "Pool type should not be abstract anymore!"); |
| 1614 | |
Chris Lattner | 54ce13f | 2002-03-29 05:50:20 +0000 | [diff] [blame] | 1615 | // Add an allocation and a free for each pool... |
Chris Lattner | ddcbd34 | 2002-04-13 19:52:54 +0000 | [diff] [blame] | 1616 | AllocaInst *PoolAlloc |
| 1617 | = new AllocaInst(PointerType::get(PI.PoolType), 0, |
| 1618 | CurModule->getTypeName(PI.PoolType)); |
Chris Lattner | 5146a7d | 2002-04-12 20:23:15 +0000 | [diff] [blame] | 1619 | PI.Handle = PoolAlloc; |
Chris Lattner | 54ce13f | 2002-03-29 05:50:20 +0000 | [diff] [blame] | 1620 | EntryNodeInsts.push_back(PoolAlloc); |
Chris Lattner | 54ce13f | 2002-03-29 05:50:20 +0000 | [diff] [blame] | 1621 | AllocationInst *AI = Allocs[i]->getAllocation(); |
| 1622 | |
| 1623 | // Initialize the pool. We need to know how big each allocation is. For |
| 1624 | // our purposes here, we assume we are allocating a scalar, or array of |
| 1625 | // constant size. |
| 1626 | // |
Chris Lattner | 3e0e520 | 2002-04-14 06:14:41 +0000 | [diff] [blame] | 1627 | unsigned ElSize = TargetData.getTypeSize(PI.NewType); |
Chris Lattner | 54ce13f | 2002-03-29 05:50:20 +0000 | [diff] [blame] | 1628 | |
| 1629 | vector<Value*> Args; |
Chris Lattner | 54ce13f | 2002-03-29 05:50:20 +0000 | [diff] [blame] | 1630 | Args.push_back(ConstantUInt::get(Type::UIntTy, ElSize)); |
Chris Lattner | 5146a7d | 2002-04-12 20:23:15 +0000 | [diff] [blame] | 1631 | Args.push_back(PoolAlloc); // Pool to initialize |
Chris Lattner | 54ce13f | 2002-03-29 05:50:20 +0000 | [diff] [blame] | 1632 | EntryNodeInsts.push_back(new CallInst(PoolInit, Args)); |
| 1633 | |
Chris Lattner | 5146a7d | 2002-04-12 20:23:15 +0000 | [diff] [blame] | 1634 | // Add code to destroy the pool in all of the exit nodes of the function... |
Chris Lattner | 027a675 | 2002-04-13 19:25:57 +0000 | [diff] [blame] | 1635 | Args.clear(); |
| 1636 | Args.push_back(PoolAlloc); // Pool to initialize |
| 1637 | |
Chris Lattner | 54ce13f | 2002-03-29 05:50:20 +0000 | [diff] [blame] | 1638 | for (unsigned EN = 0, ENE = ReturnNodes.size(); EN != ENE; ++EN) { |
| 1639 | Instruction *Destroy = new CallInst(PoolDestroy, Args); |
| 1640 | |
| 1641 | // Insert it before the return instruction... |
| 1642 | BasicBlock *RetNode = ReturnNodes[EN]; |
| 1643 | RetNode->getInstList().insert(RetNode->end()-1, Destroy); |
| 1644 | } |
| 1645 | } |
| 1646 | |
Chris Lattner | ddcbd34 | 2002-04-13 19:52:54 +0000 | [diff] [blame] | 1647 | // Now that all of the pool descriptors have been created, link them together |
| 1648 | // so that called functions can get links as neccesary... |
| 1649 | // |
| 1650 | for (unsigned i = 0, e = Allocs.size(); i != e; ++i) { |
| 1651 | PoolInfo &PI = PoolDescs[Allocs[i]]; |
| 1652 | |
| 1653 | // For every pointer in the data structure, initialize a link that |
| 1654 | // indicates which pool to access... |
| 1655 | // |
| 1656 | vector<Value*> Indices(2); |
| 1657 | Indices[0] = ConstantUInt::get(Type::UIntTy, 0); |
| 1658 | for (unsigned l = 0, le = PI.Node->getNumLinks(); l != le; ++l) |
| 1659 | // Only store an entry for the field if the field is used! |
| 1660 | if (!PI.Node->getLink(l).empty()) { |
| 1661 | assert(PI.Node->getLink(l).size() == 1 && "Should have only one link!"); |
| 1662 | PointerVal PV = PI.Node->getLink(l)[0]; |
| 1663 | assert(PV.Index == 0 && "Subindexing not supported yet!"); |
| 1664 | PoolInfo &LinkedPool = PoolDescs[PV.Node]; |
| 1665 | Indices[1] = ConstantUInt::get(Type::UByteTy, 1+l); |
| 1666 | |
| 1667 | EntryNodeInsts.push_back(new StoreInst(LinkedPool.Handle, PI.Handle, |
| 1668 | Indices)); |
| 1669 | } |
| 1670 | } |
| 1671 | |
Chris Lattner | 54ce13f | 2002-03-29 05:50:20 +0000 | [diff] [blame] | 1672 | // Insert the entry node code into the entry block... |
| 1673 | F->getEntryNode()->getInstList().insert(F->getEntryNode()->begin()+1, |
| 1674 | EntryNodeInsts.begin(), |
| 1675 | EntryNodeInsts.end()); |
Chris Lattner | d2d3a16 | 2002-03-29 03:40:59 +0000 | [diff] [blame] | 1676 | } |
| 1677 | |
| 1678 | |
Chris Lattner | 5146a7d | 2002-04-12 20:23:15 +0000 | [diff] [blame] | 1679 | // addPoolPrototypes - Add prototypes for the pool functions to the specified |
Chris Lattner | d2d3a16 | 2002-03-29 03:40:59 +0000 | [diff] [blame] | 1680 | // module and update the Pool* instance variables to point to them. |
| 1681 | // |
| 1682 | void PoolAllocate::addPoolPrototypes(Module *M) { |
Chris Lattner | 5146a7d | 2002-04-12 20:23:15 +0000 | [diff] [blame] | 1683 | // Get poolinit function... |
Chris Lattner | 54ce13f | 2002-03-29 05:50:20 +0000 | [diff] [blame] | 1684 | vector<const Type*> Args; |
Chris Lattner | 54ce13f | 2002-03-29 05:50:20 +0000 | [diff] [blame] | 1685 | Args.push_back(Type::UIntTy); // Num bytes per element |
Chris Lattner | 5146a7d | 2002-04-12 20:23:15 +0000 | [diff] [blame] | 1686 | FunctionType *PoolInitTy = FunctionType::get(Type::VoidTy, Args, true); |
Chris Lattner | 54ce13f | 2002-03-29 05:50:20 +0000 | [diff] [blame] | 1687 | PoolInit = M->getOrInsertFunction("poolinit", PoolInitTy); |
Chris Lattner | d2d3a16 | 2002-03-29 03:40:59 +0000 | [diff] [blame] | 1688 | |
Chris Lattner | 54ce13f | 2002-03-29 05:50:20 +0000 | [diff] [blame] | 1689 | // Get pooldestroy function... |
| 1690 | Args.pop_back(); // Only takes a pool... |
Chris Lattner | 5146a7d | 2002-04-12 20:23:15 +0000 | [diff] [blame] | 1691 | FunctionType *PoolDestroyTy = FunctionType::get(Type::VoidTy, Args, true); |
Chris Lattner | 54ce13f | 2002-03-29 05:50:20 +0000 | [diff] [blame] | 1692 | PoolDestroy = M->getOrInsertFunction("pooldestroy", PoolDestroyTy); |
| 1693 | |
Chris Lattner | 54ce13f | 2002-03-29 05:50:20 +0000 | [diff] [blame] | 1694 | // Get the poolalloc function... |
Chris Lattner | 5146a7d | 2002-04-12 20:23:15 +0000 | [diff] [blame] | 1695 | FunctionType *PoolAllocTy = FunctionType::get(POINTERTYPE, Args, true); |
Chris Lattner | 54ce13f | 2002-03-29 05:50:20 +0000 | [diff] [blame] | 1696 | PoolAlloc = M->getOrInsertFunction("poolalloc", PoolAllocTy); |
| 1697 | |
| 1698 | // Get the poolfree function... |
Chris Lattner | 5146a7d | 2002-04-12 20:23:15 +0000 | [diff] [blame] | 1699 | Args.push_back(POINTERTYPE); // Pointer to free |
| 1700 | FunctionType *PoolFreeTy = FunctionType::get(Type::VoidTy, Args, true); |
Chris Lattner | 54ce13f | 2002-03-29 05:50:20 +0000 | [diff] [blame] | 1701 | PoolFree = M->getOrInsertFunction("poolfree", PoolFreeTy); |
| 1702 | |
Chris Lattner | 8e34333 | 2002-04-27 02:29:32 +0000 | [diff] [blame] | 1703 | Args[0] = Type::UIntTy; // Number of slots to allocate |
| 1704 | FunctionType *PoolAllocArrayTy = FunctionType::get(POINTERTYPE, Args, true); |
| 1705 | PoolAllocArray = M->getOrInsertFunction("poolallocarray", PoolAllocArrayTy); |
Chris Lattner | d2d3a16 | 2002-03-29 03:40:59 +0000 | [diff] [blame] | 1706 | } |
| 1707 | |
| 1708 | |
| 1709 | bool PoolAllocate::run(Module *M) { |
| 1710 | addPoolPrototypes(M); |
| 1711 | CurModule = M; |
| 1712 | |
| 1713 | DS = &getAnalysis<DataStructure>(); |
| 1714 | bool Changed = false; |
Chris Lattner | a744451 | 2002-03-29 19:05:48 +0000 | [diff] [blame] | 1715 | |
| 1716 | // We cannot use an iterator here because it will get invalidated when we add |
| 1717 | // functions to the module later... |
| 1718 | for (unsigned i = 0; i != M->size(); ++i) |
Chris Lattner | 9d3493e | 2002-03-29 21:25:19 +0000 | [diff] [blame] | 1719 | if (!M->getFunctionList()[i]->isExternal()) { |
Chris Lattner | a744451 | 2002-03-29 19:05:48 +0000 | [diff] [blame] | 1720 | Changed |= processFunction(M->getFunctionList()[i]); |
Chris Lattner | 9d3493e | 2002-03-29 21:25:19 +0000 | [diff] [blame] | 1721 | if (Changed) { |
| 1722 | cerr << "Only processing one function\n"; |
| 1723 | break; |
| 1724 | } |
| 1725 | } |
Chris Lattner | d2d3a16 | 2002-03-29 03:40:59 +0000 | [diff] [blame] | 1726 | |
| 1727 | CurModule = 0; |
| 1728 | DS = 0; |
| 1729 | return false; |
| 1730 | } |
| 1731 | |
| 1732 | |
| 1733 | // createPoolAllocatePass - Global function to access the functionality of this |
| 1734 | // pass... |
| 1735 | // |
Chris Lattner | bda28f7 | 2002-03-28 18:08:31 +0000 | [diff] [blame] | 1736 | Pass *createPoolAllocatePass() { return new PoolAllocate(); } |