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