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