Chris Lattner | cf3056d | 2003-10-13 03:32:08 +0000 | [diff] [blame] | 1 | //===-- SlotCalculator.cpp - Calculate what slots values land in ----------===// |
John Criswell | b576c94 | 2003-10-20 19:43:21 +0000 | [diff] [blame] | 2 | // |
| 3 | // The LLVM Compiler Infrastructure |
| 4 | // |
| 5 | // This file was developed by the LLVM research group and is distributed under |
| 6 | // the University of Illinois Open Source License. See LICENSE.TXT for details. |
| 7 | // |
| 8 | //===----------------------------------------------------------------------===// |
Chris Lattner | 0095054 | 2001-06-06 20:29:01 +0000 | [diff] [blame] | 9 | // |
Chris Lattner | 68e3dbc | 2004-01-20 00:57:32 +0000 | [diff] [blame] | 10 | // This file implements a useful analysis step to figure out what numbered slots |
| 11 | // values in a program will land in (keeping track of per plane information). |
Chris Lattner | 0095054 | 2001-06-06 20:29:01 +0000 | [diff] [blame] | 12 | // |
Chris Lattner | 68e3dbc | 2004-01-20 00:57:32 +0000 | [diff] [blame] | 13 | // This is used when writing a file to disk, either in bytecode or assembly. |
Chris Lattner | 0095054 | 2001-06-06 20:29:01 +0000 | [diff] [blame] | 14 | // |
| 15 | //===----------------------------------------------------------------------===// |
| 16 | |
Chris Lattner | f2d577b | 2004-01-20 19:50:34 +0000 | [diff] [blame^] | 17 | #include "llvm/Analysis/SlotCalculator.h" |
Chris Lattner | dcea630 | 2004-01-14 23:34:39 +0000 | [diff] [blame] | 18 | #include "llvm/Constants.h" |
Chris Lattner | 0095054 | 2001-06-06 20:29:01 +0000 | [diff] [blame] | 19 | #include "llvm/DerivedTypes.h" |
Chris Lattner | dcea630 | 2004-01-14 23:34:39 +0000 | [diff] [blame] | 20 | #include "llvm/iOther.h" |
| 21 | #include "llvm/Module.h" |
Chris Lattner | 9a29790 | 2001-09-07 16:31:52 +0000 | [diff] [blame] | 22 | #include "llvm/SymbolTable.h" |
Chris Lattner | f2d577b | 2004-01-20 19:50:34 +0000 | [diff] [blame^] | 23 | #include "llvm/Analysis/ConstantsScanner.h" |
Alkis Evlogimenos | 088eb45 | 2003-10-31 03:02:34 +0000 | [diff] [blame] | 24 | #include "Support/PostOrderIterator.h" |
Chris Lattner | cee8f9a | 2001-11-27 00:03:19 +0000 | [diff] [blame] | 25 | #include "Support/STLExtras.h" |
Chris Lattner | 9a29790 | 2001-09-07 16:31:52 +0000 | [diff] [blame] | 26 | #include <algorithm> |
Chris Lattner | 31f8499 | 2003-11-21 20:23:48 +0000 | [diff] [blame] | 27 | using namespace llvm; |
Brian Gaeke | d0fde30 | 2003-11-11 22:41:34 +0000 | [diff] [blame] | 28 | |
Chris Lattner | 9a29790 | 2001-09-07 16:31:52 +0000 | [diff] [blame] | 29 | #if 0 |
Chris Lattner | 3413d15 | 2003-03-19 20:57:22 +0000 | [diff] [blame] | 30 | #define SC_DEBUG(X) std::cerr << X |
Chris Lattner | 9a29790 | 2001-09-07 16:31:52 +0000 | [diff] [blame] | 31 | #else |
| 32 | #define SC_DEBUG(X) |
| 33 | #endif |
Chris Lattner | 0095054 | 2001-06-06 20:29:01 +0000 | [diff] [blame] | 34 | |
Chris Lattner | 8ce7501 | 2004-01-14 02:49:34 +0000 | [diff] [blame] | 35 | SlotCalculator::SlotCalculator(const Module *M, bool buildBytecodeInfo) { |
| 36 | BuildBytecodeInfo = buildBytecodeInfo; |
Chris Lattner | 614cdcd | 2004-01-18 21:07:07 +0000 | [diff] [blame] | 37 | ModuleContainsAllFunctionConstants = false; |
Chris Lattner | 0095054 | 2001-06-06 20:29:01 +0000 | [diff] [blame] | 38 | TheModule = M; |
| 39 | |
| 40 | // Preload table... Make sure that all of the primitive types are in the table |
| 41 | // and that their Primitive ID is equal to their slot # |
| 42 | // |
Alkis Evlogimenos | 5d1bdcd | 2003-10-29 03:12:12 +0000 | [diff] [blame] | 43 | SC_DEBUG("Inserting primitive types:\n"); |
Chris Lattner | 0095054 | 2001-06-06 20:29:01 +0000 | [diff] [blame] | 44 | for (unsigned i = 0; i < Type::FirstDerivedTyID; ++i) { |
| 45 | assert(Type::getPrimitiveType((Type::PrimitiveID)i)); |
Alkis Evlogimenos | 6059638 | 2003-10-17 02:02:40 +0000 | [diff] [blame] | 46 | insertValue(Type::getPrimitiveType((Type::PrimitiveID)i), true); |
Chris Lattner | 0095054 | 2001-06-06 20:29:01 +0000 | [diff] [blame] | 47 | } |
| 48 | |
| 49 | if (M == 0) return; // Empty table... |
Chris Lattner | 9a29790 | 2001-09-07 16:31:52 +0000 | [diff] [blame] | 50 | processModule(); |
Chris Lattner | 0095054 | 2001-06-06 20:29:01 +0000 | [diff] [blame] | 51 | } |
| 52 | |
Chris Lattner | 8ce7501 | 2004-01-14 02:49:34 +0000 | [diff] [blame] | 53 | SlotCalculator::SlotCalculator(const Function *M, bool buildBytecodeInfo) { |
| 54 | BuildBytecodeInfo = buildBytecodeInfo; |
Chris Lattner | 614cdcd | 2004-01-18 21:07:07 +0000 | [diff] [blame] | 55 | ModuleContainsAllFunctionConstants = false; |
Chris Lattner | 0095054 | 2001-06-06 20:29:01 +0000 | [diff] [blame] | 56 | TheModule = M ? M->getParent() : 0; |
| 57 | |
| 58 | // Preload table... Make sure that all of the primitive types are in the table |
| 59 | // and that their Primitive ID is equal to their slot # |
| 60 | // |
Alkis Evlogimenos | 5d1bdcd | 2003-10-29 03:12:12 +0000 | [diff] [blame] | 61 | SC_DEBUG("Inserting primitive types:\n"); |
Chris Lattner | 0095054 | 2001-06-06 20:29:01 +0000 | [diff] [blame] | 62 | for (unsigned i = 0; i < Type::FirstDerivedTyID; ++i) { |
| 63 | assert(Type::getPrimitiveType((Type::PrimitiveID)i)); |
Alkis Evlogimenos | 6059638 | 2003-10-17 02:02:40 +0000 | [diff] [blame] | 64 | insertValue(Type::getPrimitiveType((Type::PrimitiveID)i), true); |
Chris Lattner | 0095054 | 2001-06-06 20:29:01 +0000 | [diff] [blame] | 65 | } |
| 66 | |
| 67 | if (TheModule == 0) return; // Empty table... |
| 68 | |
Chris Lattner | 9a29790 | 2001-09-07 16:31:52 +0000 | [diff] [blame] | 69 | processModule(); // Process module level stuff |
Chris Lattner | 68e3dbc | 2004-01-20 00:57:32 +0000 | [diff] [blame] | 70 | incorporateFunction(M); // Start out in incorporated state |
Chris Lattner | 0095054 | 2001-06-06 20:29:01 +0000 | [diff] [blame] | 71 | } |
| 72 | |
Chris Lattner | 614cdcd | 2004-01-18 21:07:07 +0000 | [diff] [blame] | 73 | unsigned SlotCalculator::getGlobalSlot(const Value *V) const { |
| 74 | assert(!CompactionTable.empty() && |
| 75 | "This method can only be used when compaction is enabled!"); |
| 76 | if (const ConstantPointerRef *CPR = dyn_cast<ConstantPointerRef>(V)) |
| 77 | V = CPR->getValue(); |
| 78 | std::map<const Value*, unsigned>::const_iterator I = NodeMap.find(V); |
Chris Lattner | 68e3dbc | 2004-01-20 00:57:32 +0000 | [diff] [blame] | 79 | assert(I != NodeMap.end() && "Didn't find global slot entry!"); |
Chris Lattner | 614cdcd | 2004-01-18 21:07:07 +0000 | [diff] [blame] | 80 | return I->second; |
| 81 | } |
| 82 | |
Chris Lattner | 68e3dbc | 2004-01-20 00:57:32 +0000 | [diff] [blame] | 83 | SlotCalculator::TypePlane &SlotCalculator::getPlane(unsigned Plane) { |
| 84 | unsigned PIdx = Plane; |
| 85 | if (CompactionTable.empty()) { // No compaction table active? |
| 86 | // fall out |
| 87 | } else if (!CompactionTable[Plane].empty()) { // Compaction table active. |
| 88 | assert(Plane < CompactionTable.size()); |
| 89 | return CompactionTable[Plane]; |
| 90 | } else { |
| 91 | // Final case: compaction table active, but this plane is not |
| 92 | // compactified. If the type plane is compactified, unmap back to the |
| 93 | // global type plane corresponding to "Plane". |
| 94 | if (!CompactionTable[Type::TypeTyID].empty()) { |
| 95 | const Type *Ty = cast<Type>(CompactionTable[Type::TypeTyID][Plane]); |
| 96 | std::map<const Value*, unsigned>::iterator It = NodeMap.find(Ty); |
| 97 | assert(It != NodeMap.end() && "Type not in global constant map?"); |
| 98 | PIdx = It->second; |
| 99 | } |
| 100 | } |
| 101 | |
| 102 | // Okay we are just returning an entry out of the main Table. Make sure the |
| 103 | // plane exists and return it. |
| 104 | if (PIdx >= Table.size()) |
| 105 | Table.resize(PIdx+1); |
| 106 | return Table[PIdx]; |
| 107 | } |
Chris Lattner | 614cdcd | 2004-01-18 21:07:07 +0000 | [diff] [blame] | 108 | |
Chris Lattner | 9a29790 | 2001-09-07 16:31:52 +0000 | [diff] [blame] | 109 | |
Chris Lattner | 2fbfdcf | 2002-04-07 20:49:59 +0000 | [diff] [blame] | 110 | // processModule - Process all of the module level function declarations and |
Chris Lattner | 9a29790 | 2001-09-07 16:31:52 +0000 | [diff] [blame] | 111 | // types that are available. |
| 112 | // |
| 113 | void SlotCalculator::processModule() { |
| 114 | SC_DEBUG("begin processModule!\n"); |
Chris Lattner | 70cc339 | 2001-09-10 07:58:01 +0000 | [diff] [blame] | 115 | |
Chris Lattner | 3413d15 | 2003-03-19 20:57:22 +0000 | [diff] [blame] | 116 | // Add all of the global variables to the value table... |
Chris Lattner | f1fef65 | 2001-10-13 06:35:09 +0000 | [diff] [blame] | 117 | // |
| 118 | for (Module::const_giterator I = TheModule->gbegin(), E = TheModule->gend(); |
Chris Lattner | 479b54b | 2002-10-14 00:48:57 +0000 | [diff] [blame] | 119 | I != E; ++I) |
Alkis Evlogimenos | 6059638 | 2003-10-17 02:02:40 +0000 | [diff] [blame] | 120 | getOrCreateSlot(I); |
Chris Lattner | 70cc339 | 2001-09-10 07:58:01 +0000 | [diff] [blame] | 121 | |
Chris Lattner | 2fbfdcf | 2002-04-07 20:49:59 +0000 | [diff] [blame] | 122 | // Scavenge the types out of the functions, then add the functions themselves |
| 123 | // to the value table... |
Chris Lattner | 9a29790 | 2001-09-07 16:31:52 +0000 | [diff] [blame] | 124 | // |
Chris Lattner | 3413d15 | 2003-03-19 20:57:22 +0000 | [diff] [blame] | 125 | for (Module::const_iterator I = TheModule->begin(), E = TheModule->end(); |
| 126 | I != E; ++I) |
Alkis Evlogimenos | 6059638 | 2003-10-17 02:02:40 +0000 | [diff] [blame] | 127 | getOrCreateSlot(I); |
Chris Lattner | 9a29790 | 2001-09-07 16:31:52 +0000 | [diff] [blame] | 128 | |
Chris Lattner | 3413d15 | 2003-03-19 20:57:22 +0000 | [diff] [blame] | 129 | // Add all of the module level constants used as initializers |
| 130 | // |
| 131 | for (Module::const_giterator I = TheModule->gbegin(), E = TheModule->gend(); |
| 132 | I != E; ++I) |
| 133 | if (I->hasInitializer()) |
Alkis Evlogimenos | 6059638 | 2003-10-17 02:02:40 +0000 | [diff] [blame] | 134 | getOrCreateSlot(I->getInitializer()); |
Chris Lattner | 3413d15 | 2003-03-19 20:57:22 +0000 | [diff] [blame] | 135 | |
Chris Lattner | dcea630 | 2004-01-14 23:34:39 +0000 | [diff] [blame] | 136 | // Now that all global constants have been added, rearrange constant planes |
| 137 | // that contain constant strings so that the strings occur at the start of the |
| 138 | // plane, not somewhere in the middle. |
| 139 | // |
| 140 | if (BuildBytecodeInfo) { |
| 141 | TypePlane &Types = Table[Type::TypeTyID]; |
| 142 | for (unsigned plane = 0, e = Table.size(); plane != e; ++plane) { |
| 143 | if (const ArrayType *AT = dyn_cast<ArrayType>(Types[plane])) |
| 144 | if (AT->getElementType() == Type::SByteTy || |
| 145 | AT->getElementType() == Type::UByteTy) { |
| 146 | TypePlane &Plane = Table[plane]; |
| 147 | unsigned FirstNonStringID = 0; |
| 148 | for (unsigned i = 0, e = Plane.size(); i != e; ++i) |
| 149 | if (cast<ConstantArray>(Plane[i])->isString()) { |
| 150 | // Check to see if we have to shuffle this string around. If not, |
| 151 | // don't do anything. |
| 152 | if (i != FirstNonStringID) { |
| 153 | // Swap the plane entries.... |
| 154 | std::swap(Plane[i], Plane[FirstNonStringID]); |
| 155 | |
| 156 | // Keep the NodeMap up to date. |
| 157 | NodeMap[Plane[i]] = i; |
| 158 | NodeMap[Plane[FirstNonStringID]] = FirstNonStringID; |
| 159 | } |
| 160 | ++FirstNonStringID; |
| 161 | } |
| 162 | } |
| 163 | } |
| 164 | } |
| 165 | |
Chris Lattner | a14b0d4 | 2004-01-10 23:46:13 +0000 | [diff] [blame] | 166 | // If we are emitting a bytecode file, scan all of the functions for their |
| 167 | // constants, which allows us to emit more compact modules. This is optional, |
| 168 | // and is just used to compactify the constants used by different functions |
| 169 | // together. |
Chris Lattner | 614cdcd | 2004-01-18 21:07:07 +0000 | [diff] [blame] | 170 | // |
| 171 | // This functionality is completely optional for the bytecode writer, but |
| 172 | // tends to produce smaller bytecode files. This should not be used in the |
| 173 | // future by clients that want to, for example, build and emit functions on |
| 174 | // the fly. For now, however, it is unconditionally enabled when building |
| 175 | // bytecode information. |
| 176 | // |
Chris Lattner | 8ce7501 | 2004-01-14 02:49:34 +0000 | [diff] [blame] | 177 | if (BuildBytecodeInfo) { |
Chris Lattner | 614cdcd | 2004-01-18 21:07:07 +0000 | [diff] [blame] | 178 | ModuleContainsAllFunctionConstants = true; |
| 179 | |
Chris Lattner | a14b0d4 | 2004-01-10 23:46:13 +0000 | [diff] [blame] | 180 | SC_DEBUG("Inserting function constants:\n"); |
| 181 | for (Module::const_iterator F = TheModule->begin(), E = TheModule->end(); |
Chris Lattner | 614cdcd | 2004-01-18 21:07:07 +0000 | [diff] [blame] | 182 | F != E; ++F) { |
| 183 | for (const_inst_iterator I = inst_begin(F), E = inst_end(F); I != E; ++I){ |
| 184 | for (unsigned op = 0, e = I->getNumOperands(); op != e; ++op) |
| 185 | if (isa<Constant>(I->getOperand(op))) |
| 186 | getOrCreateSlot(I->getOperand(op)); |
| 187 | getOrCreateSlot(I->getType()); |
| 188 | if (const VANextInst *VAN = dyn_cast<VANextInst>(*I)) |
| 189 | getOrCreateSlot(VAN->getArgType()); |
| 190 | } |
| 191 | processSymbolTableConstants(&F->getSymbolTable()); |
| 192 | } |
Chris Lattner | a14b0d4 | 2004-01-10 23:46:13 +0000 | [diff] [blame] | 193 | } |
Chris Lattner | a14b0d4 | 2004-01-10 23:46:13 +0000 | [diff] [blame] | 194 | |
Chris Lattner | 70cc339 | 2001-09-10 07:58:01 +0000 | [diff] [blame] | 195 | // Insert constants that are named at module level into the slot pool so that |
| 196 | // the module symbol table can refer to them... |
| 197 | // |
Chris Lattner | 8ce7501 | 2004-01-14 02:49:34 +0000 | [diff] [blame] | 198 | if (BuildBytecodeInfo) { |
Chris Lattner | 9a29790 | 2001-09-07 16:31:52 +0000 | [diff] [blame] | 199 | SC_DEBUG("Inserting SymbolTable values:\n"); |
Chris Lattner | 6e6026b | 2002-11-20 18:36:02 +0000 | [diff] [blame] | 200 | processSymbolTable(&TheModule->getSymbolTable()); |
Chris Lattner | 9a29790 | 2001-09-07 16:31:52 +0000 | [diff] [blame] | 201 | } |
| 202 | |
Chris Lattner | a14b0d4 | 2004-01-10 23:46:13 +0000 | [diff] [blame] | 203 | // Now that we have collected together all of the information relevant to the |
| 204 | // module, compactify the type table if it is particularly big and outputting |
| 205 | // a bytecode file. The basic problem we run into is that some programs have |
| 206 | // a large number of types, which causes the type field to overflow its size, |
| 207 | // which causes instructions to explode in size (particularly call |
| 208 | // instructions). To avoid this behavior, we "sort" the type table so that |
| 209 | // all non-value types are pushed to the end of the type table, giving nice |
| 210 | // low numbers to the types that can be used by instructions, thus reducing |
| 211 | // the amount of explodage we suffer. |
Chris Lattner | 8ce7501 | 2004-01-14 02:49:34 +0000 | [diff] [blame] | 212 | if (BuildBytecodeInfo && Table[Type::TypeTyID].size() >= 64) { |
Chris Lattner | a14b0d4 | 2004-01-10 23:46:13 +0000 | [diff] [blame] | 213 | // Scan through the type table moving value types to the start of the table. |
Chris Lattner | 9380297 | 2004-01-11 23:29:26 +0000 | [diff] [blame] | 214 | TypePlane *Types = &Table[Type::TypeTyID]; |
Chris Lattner | a14b0d4 | 2004-01-10 23:46:13 +0000 | [diff] [blame] | 215 | unsigned FirstNonValueTypeID = 0; |
Chris Lattner | 9380297 | 2004-01-11 23:29:26 +0000 | [diff] [blame] | 216 | for (unsigned i = 0, e = Types->size(); i != e; ++i) |
| 217 | if (cast<Type>((*Types)[i])->isFirstClassType() || |
| 218 | cast<Type>((*Types)[i])->isPrimitiveType()) { |
Chris Lattner | a14b0d4 | 2004-01-10 23:46:13 +0000 | [diff] [blame] | 219 | // Check to see if we have to shuffle this type around. If not, don't |
| 220 | // do anything. |
| 221 | if (i != FirstNonValueTypeID) { |
Chris Lattner | 9380297 | 2004-01-11 23:29:26 +0000 | [diff] [blame] | 222 | assert(i != Type::TypeTyID && FirstNonValueTypeID != Type::TypeTyID && |
| 223 | "Cannot move around the type plane!"); |
| 224 | |
Chris Lattner | a14b0d4 | 2004-01-10 23:46:13 +0000 | [diff] [blame] | 225 | // Swap the type ID's. |
Chris Lattner | 9380297 | 2004-01-11 23:29:26 +0000 | [diff] [blame] | 226 | std::swap((*Types)[i], (*Types)[FirstNonValueTypeID]); |
Chris Lattner | a14b0d4 | 2004-01-10 23:46:13 +0000 | [diff] [blame] | 227 | |
| 228 | // Keep the NodeMap up to date. |
Chris Lattner | 9380297 | 2004-01-11 23:29:26 +0000 | [diff] [blame] | 229 | NodeMap[(*Types)[i]] = i; |
| 230 | NodeMap[(*Types)[FirstNonValueTypeID]] = FirstNonValueTypeID; |
Chris Lattner | a14b0d4 | 2004-01-10 23:46:13 +0000 | [diff] [blame] | 231 | |
| 232 | // When we move a type, make sure to move its value plane as needed. |
Chris Lattner | 9380297 | 2004-01-11 23:29:26 +0000 | [diff] [blame] | 233 | if (Table.size() > FirstNonValueTypeID) { |
| 234 | if (Table.size() <= i) Table.resize(i+1); |
| 235 | std::swap(Table[i], Table[FirstNonValueTypeID]); |
| 236 | Types = &Table[Type::TypeTyID]; |
| 237 | } |
Chris Lattner | a14b0d4 | 2004-01-10 23:46:13 +0000 | [diff] [blame] | 238 | } |
| 239 | ++FirstNonValueTypeID; |
| 240 | } |
| 241 | } |
| 242 | |
Chris Lattner | 9a29790 | 2001-09-07 16:31:52 +0000 | [diff] [blame] | 243 | SC_DEBUG("end processModule!\n"); |
| 244 | } |
| 245 | |
| 246 | // processSymbolTable - Insert all of the values in the specified symbol table |
| 247 | // into the values table... |
| 248 | // |
| 249 | void SlotCalculator::processSymbolTable(const SymbolTable *ST) { |
| 250 | for (SymbolTable::const_iterator I = ST->begin(), E = ST->end(); I != E; ++I) |
| 251 | for (SymbolTable::type_const_iterator TI = I->second.begin(), |
| 252 | TE = I->second.end(); TI != TE; ++TI) |
Alkis Evlogimenos | 6059638 | 2003-10-17 02:02:40 +0000 | [diff] [blame] | 253 | getOrCreateSlot(TI->second); |
Chris Lattner | 9a29790 | 2001-09-07 16:31:52 +0000 | [diff] [blame] | 254 | } |
| 255 | |
| 256 | void SlotCalculator::processSymbolTableConstants(const SymbolTable *ST) { |
| 257 | for (SymbolTable::const_iterator I = ST->begin(), E = ST->end(); I != E; ++I) |
| 258 | for (SymbolTable::type_const_iterator TI = I->second.begin(), |
| 259 | TE = I->second.end(); TI != TE; ++TI) |
Chris Lattner | d5c59d5 | 2004-01-15 20:24:09 +0000 | [diff] [blame] | 260 | if (isa<Constant>(TI->second) || isa<Type>(TI->second)) |
Alkis Evlogimenos | 6059638 | 2003-10-17 02:02:40 +0000 | [diff] [blame] | 261 | getOrCreateSlot(TI->second); |
Chris Lattner | 9a29790 | 2001-09-07 16:31:52 +0000 | [diff] [blame] | 262 | } |
| 263 | |
| 264 | |
Chris Lattner | ce439b5 | 2003-10-20 19:10:06 +0000 | [diff] [blame] | 265 | void SlotCalculator::incorporateFunction(const Function *F) { |
Chris Lattner | 0095054 | 2001-06-06 20:29:01 +0000 | [diff] [blame] | 266 | assert(ModuleLevel.size() == 0 && "Module already incorporated!"); |
| 267 | |
Chris Lattner | 2fbfdcf | 2002-04-07 20:49:59 +0000 | [diff] [blame] | 268 | SC_DEBUG("begin processFunction!\n"); |
Chris Lattner | 9a29790 | 2001-09-07 16:31:52 +0000 | [diff] [blame] | 269 | |
Chris Lattner | 614cdcd | 2004-01-18 21:07:07 +0000 | [diff] [blame] | 270 | // If we emitted all of the function constants, build a compaction table. |
| 271 | if (BuildBytecodeInfo && ModuleContainsAllFunctionConstants) |
| 272 | buildCompactionTable(F); |
Chris Lattner | 68e3dbc | 2004-01-20 00:57:32 +0000 | [diff] [blame] | 273 | |
| 274 | // Update the ModuleLevel entries to be accurate. |
| 275 | ModuleLevel.resize(getNumPlanes()); |
| 276 | for (unsigned i = 0, e = getNumPlanes(); i != e; ++i) |
| 277 | ModuleLevel[i] = getPlane(i).size(); |
Chris Lattner | 9a29790 | 2001-09-07 16:31:52 +0000 | [diff] [blame] | 278 | |
Chris Lattner | 2fbfdcf | 2002-04-07 20:49:59 +0000 | [diff] [blame] | 279 | // Iterate over function arguments, adding them to the value table... |
Chris Lattner | ce439b5 | 2003-10-20 19:10:06 +0000 | [diff] [blame] | 280 | for(Function::const_aiterator I = F->abegin(), E = F->aend(); I != E; ++I) |
Alkis Evlogimenos | 6059638 | 2003-10-17 02:02:40 +0000 | [diff] [blame] | 281 | getOrCreateSlot(I); |
Chris Lattner | 9a29790 | 2001-09-07 16:31:52 +0000 | [diff] [blame] | 282 | |
Chris Lattner | 614cdcd | 2004-01-18 21:07:07 +0000 | [diff] [blame] | 283 | if (BuildBytecodeInfo && // Assembly writer does not need this! |
| 284 | !ModuleContainsAllFunctionConstants) { |
| 285 | // Iterate over all of the instructions in the function, looking for |
| 286 | // constant values that are referenced. Add these to the value pools |
| 287 | // before any nonconstant values. This will be turned into the constant |
| 288 | // pool for the bytecode writer. |
| 289 | // |
| 290 | |
| 291 | // Emit all of the constants that are being used by the instructions in |
| 292 | // the function... |
Chris Lattner | ce439b5 | 2003-10-20 19:10:06 +0000 | [diff] [blame] | 293 | for_each(constant_begin(F), constant_end(F), |
Chris Lattner | 614cdcd | 2004-01-18 21:07:07 +0000 | [diff] [blame] | 294 | bind_obj(this, &SlotCalculator::getOrCreateSlot)); |
| 295 | |
Chris Lattner | 9a29790 | 2001-09-07 16:31:52 +0000 | [diff] [blame] | 296 | // If there is a symbol table, it is possible that the user has names for |
| 297 | // constants that are not being used. In this case, we will have problems |
| 298 | // if we don't emit the constants now, because otherwise we will get |
Chris Lattner | a14b0d4 | 2004-01-10 23:46:13 +0000 | [diff] [blame] | 299 | // symbol table references to constants not in the output. Scan for these |
Chris Lattner | 9a29790 | 2001-09-07 16:31:52 +0000 | [diff] [blame] | 300 | // constants now. |
| 301 | // |
Chris Lattner | ce439b5 | 2003-10-20 19:10:06 +0000 | [diff] [blame] | 302 | processSymbolTableConstants(&F->getSymbolTable()); |
Chris Lattner | 0095054 | 2001-06-06 20:29:01 +0000 | [diff] [blame] | 303 | } |
| 304 | |
Chris Lattner | 9a29790 | 2001-09-07 16:31:52 +0000 | [diff] [blame] | 305 | SC_DEBUG("Inserting Instructions:\n"); |
| 306 | |
| 307 | // Add all of the instructions to the type planes... |
Chris Lattner | d5c59d5 | 2004-01-15 20:24:09 +0000 | [diff] [blame] | 308 | for (Function::const_iterator BB = F->begin(), E = F->end(); BB != E; ++BB) { |
| 309 | getOrCreateSlot(BB); |
Chris Lattner | 389dbfb | 2003-10-21 17:39:59 +0000 | [diff] [blame] | 310 | for (BasicBlock::const_iterator I = BB->begin(), E = BB->end(); I!=E; ++I) { |
| 311 | getOrCreateSlot(I); |
Chris Lattner | 2765c41 | 2003-10-21 17:40:54 +0000 | [diff] [blame] | 312 | if (const VANextInst *VAN = dyn_cast<VANextInst>(I)) |
| 313 | getOrCreateSlot(VAN->getArgType()); |
Chris Lattner | 389dbfb | 2003-10-21 17:39:59 +0000 | [diff] [blame] | 314 | } |
Chris Lattner | 9a29790 | 2001-09-07 16:31:52 +0000 | [diff] [blame] | 315 | } |
| 316 | |
Chris Lattner | 68e3dbc | 2004-01-20 00:57:32 +0000 | [diff] [blame] | 317 | // If we are building a compaction table, prune out planes that do not benefit |
| 318 | // from being compactified. |
| 319 | if (!CompactionTable.empty()) |
| 320 | pruneCompactionTable(); |
| 321 | |
Chris Lattner | 2fbfdcf | 2002-04-07 20:49:59 +0000 | [diff] [blame] | 322 | SC_DEBUG("end processFunction!\n"); |
Chris Lattner | 0095054 | 2001-06-06 20:29:01 +0000 | [diff] [blame] | 323 | } |
| 324 | |
Chris Lattner | b579400 | 2002-04-07 22:49:37 +0000 | [diff] [blame] | 325 | void SlotCalculator::purgeFunction() { |
Chris Lattner | 0095054 | 2001-06-06 20:29:01 +0000 | [diff] [blame] | 326 | assert(ModuleLevel.size() != 0 && "Module not incorporated!"); |
| 327 | unsigned NumModuleTypes = ModuleLevel.size(); |
| 328 | |
Chris Lattner | 2fbfdcf | 2002-04-07 20:49:59 +0000 | [diff] [blame] | 329 | SC_DEBUG("begin purgeFunction!\n"); |
Chris Lattner | 9a29790 | 2001-09-07 16:31:52 +0000 | [diff] [blame] | 330 | |
Chris Lattner | 614cdcd | 2004-01-18 21:07:07 +0000 | [diff] [blame] | 331 | // First, free the compaction map if used. |
| 332 | CompactionNodeMap.clear(); |
| 333 | |
| 334 | // Next, remove values from existing type planes |
Chris Lattner | 68e3dbc | 2004-01-20 00:57:32 +0000 | [diff] [blame] | 335 | for (unsigned i = 0; i != NumModuleTypes; ++i) { |
| 336 | // Size of plane before function came |
| 337 | unsigned ModuleLev = getModuleLevel(i); |
| 338 | assert(int(ModuleLev) >= 0 && "BAD!"); |
| 339 | |
| 340 | TypePlane &Plane = getPlane(i); |
| 341 | |
| 342 | assert(ModuleLev <= Plane.size() && "module levels higher than elements?"); |
| 343 | while (Plane.size() != ModuleLev) { |
| 344 | assert(!isa<GlobalValue>(Plane.back()) && |
| 345 | "Functions cannot define globals!"); |
| 346 | NodeMap.erase(Plane.back()); // Erase from nodemap |
| 347 | Plane.pop_back(); // Shrink plane |
Chris Lattner | 0095054 | 2001-06-06 20:29:01 +0000 | [diff] [blame] | 348 | } |
Chris Lattner | 68e3dbc | 2004-01-20 00:57:32 +0000 | [diff] [blame] | 349 | } |
Chris Lattner | 0095054 | 2001-06-06 20:29:01 +0000 | [diff] [blame] | 350 | |
| 351 | // We don't need this state anymore, free it up. |
| 352 | ModuleLevel.clear(); |
| 353 | |
Chris Lattner | 68e3dbc | 2004-01-20 00:57:32 +0000 | [diff] [blame] | 354 | // Finally, remove any type planes defined by the function... |
Chris Lattner | 614cdcd | 2004-01-18 21:07:07 +0000 | [diff] [blame] | 355 | if (!CompactionTable.empty()) { |
| 356 | CompactionTable.clear(); |
| 357 | } else { |
Chris Lattner | 68e3dbc | 2004-01-20 00:57:32 +0000 | [diff] [blame] | 358 | while (Table.size() > NumModuleTypes) { |
Chris Lattner | 614cdcd | 2004-01-18 21:07:07 +0000 | [diff] [blame] | 359 | TypePlane &Plane = Table.back(); |
| 360 | SC_DEBUG("Removing Plane " << (Table.size()-1) << " of size " |
| 361 | << Plane.size() << "\n"); |
| 362 | while (Plane.size()) { |
Chris Lattner | 68e3dbc | 2004-01-20 00:57:32 +0000 | [diff] [blame] | 363 | assert(!isa<GlobalValue>(Plane.back()) && |
| 364 | "Functions cannot define globals!"); |
| 365 | NodeMap.erase(Plane.back()); // Erase from nodemap |
| 366 | Plane.pop_back(); // Shrink plane |
Chris Lattner | 614cdcd | 2004-01-18 21:07:07 +0000 | [diff] [blame] | 367 | } |
| 368 | |
Chris Lattner | 68e3dbc | 2004-01-20 00:57:32 +0000 | [diff] [blame] | 369 | Table.pop_back(); // Nuke the plane, we don't like it. |
Chris Lattner | 0095054 | 2001-06-06 20:29:01 +0000 | [diff] [blame] | 370 | } |
Chris Lattner | 0095054 | 2001-06-06 20:29:01 +0000 | [diff] [blame] | 371 | } |
Chris Lattner | 68e3dbc | 2004-01-20 00:57:32 +0000 | [diff] [blame] | 372 | |
Chris Lattner | 2fbfdcf | 2002-04-07 20:49:59 +0000 | [diff] [blame] | 373 | SC_DEBUG("end purgeFunction!\n"); |
Chris Lattner | 0095054 | 2001-06-06 20:29:01 +0000 | [diff] [blame] | 374 | } |
| 375 | |
Chris Lattner | 614cdcd | 2004-01-18 21:07:07 +0000 | [diff] [blame] | 376 | static inline bool hasNullValue(unsigned TyID) { |
| 377 | return TyID != Type::LabelTyID && TyID != Type::TypeTyID && |
| 378 | TyID != Type::VoidTyID; |
| 379 | } |
| 380 | |
| 381 | /// getOrCreateCompactionTableSlot - This method is used to build up the initial |
| 382 | /// approximation of the compaction table. |
| 383 | unsigned SlotCalculator::getOrCreateCompactionTableSlot(const Value *V) { |
| 384 | std::map<const Value*, unsigned>::iterator I = |
| 385 | CompactionNodeMap.lower_bound(V); |
| 386 | if (I != CompactionNodeMap.end() && I->first == V) |
| 387 | return I->second; // Already exists? |
| 388 | |
| 389 | // Make sure the type is in the table. |
Chris Lattner | 68e3dbc | 2004-01-20 00:57:32 +0000 | [diff] [blame] | 390 | unsigned Ty; |
| 391 | if (!CompactionTable[Type::TypeTyID].empty()) |
| 392 | Ty = getOrCreateCompactionTableSlot(V->getType()); |
| 393 | else // If the type plane was decompactified, use the global plane ID |
| 394 | Ty = getSlot(V->getType()); |
Chris Lattner | 614cdcd | 2004-01-18 21:07:07 +0000 | [diff] [blame] | 395 | if (CompactionTable.size() <= Ty) |
| 396 | CompactionTable.resize(Ty+1); |
| 397 | |
| 398 | assert(!isa<Type>(V) || ModuleLevel.empty()); |
| 399 | |
| 400 | TypePlane &TyPlane = CompactionTable[Ty]; |
| 401 | |
| 402 | // Make sure to insert the null entry if the thing we are inserting is not a |
| 403 | // null constant. |
| 404 | if (TyPlane.empty() && hasNullValue(V->getType()->getPrimitiveID())) { |
| 405 | Value *ZeroInitializer = Constant::getNullValue(V->getType()); |
| 406 | if (V != ZeroInitializer) { |
| 407 | TyPlane.push_back(ZeroInitializer); |
| 408 | CompactionNodeMap[ZeroInitializer] = 0; |
| 409 | } |
| 410 | } |
| 411 | |
| 412 | unsigned SlotNo = TyPlane.size(); |
| 413 | TyPlane.push_back(V); |
| 414 | CompactionNodeMap.insert(std::make_pair(V, SlotNo)); |
| 415 | return SlotNo; |
| 416 | } |
| 417 | |
| 418 | |
| 419 | /// buildCompactionTable - Since all of the function constants and types are |
| 420 | /// stored in the module-level constant table, we don't need to emit a function |
| 421 | /// constant table. Also due to this, the indices for various constants and |
| 422 | /// types might be very large in large programs. In order to avoid blowing up |
| 423 | /// the size of instructions in the bytecode encoding, we build a compaction |
| 424 | /// table, which defines a mapping from function-local identifiers to global |
| 425 | /// identifiers. |
| 426 | void SlotCalculator::buildCompactionTable(const Function *F) { |
| 427 | assert(CompactionNodeMap.empty() && "Compaction table already built!"); |
| 428 | // First step, insert the primitive types. |
| 429 | CompactionTable.resize(Type::TypeTyID+1); |
| 430 | for (unsigned i = 0; i != Type::FirstDerivedTyID; ++i) { |
| 431 | const Type *PrimTy = Type::getPrimitiveType((Type::PrimitiveID)i); |
| 432 | CompactionTable[Type::TypeTyID].push_back(PrimTy); |
| 433 | CompactionNodeMap[PrimTy] = i; |
| 434 | } |
| 435 | |
| 436 | // Next, include any types used by function arguments. |
| 437 | for (Function::const_aiterator I = F->abegin(), E = F->aend(); I != E; ++I) |
| 438 | getOrCreateCompactionTableSlot(I->getType()); |
| 439 | |
| 440 | // Next, find all of the types and values that are referred to by the |
| 441 | // instructions in the program. |
| 442 | for (const_inst_iterator I = inst_begin(F), E = inst_end(F); I != E; ++I) { |
| 443 | getOrCreateCompactionTableSlot(I->getType()); |
| 444 | for (unsigned op = 0, e = I->getNumOperands(); op != e; ++op) |
| 445 | if (isa<Constant>(I->getOperand(op)) || |
| 446 | isa<GlobalValue>(I->getOperand(op))) |
| 447 | getOrCreateCompactionTableSlot(I->getOperand(op)); |
| 448 | if (const VANextInst *VAN = dyn_cast<VANextInst>(*I)) |
| 449 | getOrCreateCompactionTableSlot(VAN->getArgType()); |
| 450 | } |
| 451 | |
| 452 | const SymbolTable &ST = F->getSymbolTable(); |
| 453 | for (SymbolTable::const_iterator I = ST.begin(), E = ST.end(); I != E; ++I) |
| 454 | for (SymbolTable::type_const_iterator TI = I->second.begin(), |
| 455 | TE = I->second.end(); TI != TE; ++TI) |
| 456 | if (isa<Constant>(TI->second) || isa<Type>(TI->second) || |
| 457 | isa<GlobalValue>(TI->second)) |
| 458 | getOrCreateCompactionTableSlot(TI->second); |
| 459 | |
| 460 | // Now that we have all of the values in the table, and know what types are |
| 461 | // referenced, make sure that there is at least the zero initializer in any |
| 462 | // used type plane. Since the type was used, we will be emitting instructions |
| 463 | // to the plane even if there are no constants in it. |
| 464 | CompactionTable.resize(CompactionTable[Type::TypeTyID].size()); |
| 465 | for (unsigned i = 0, e = CompactionTable.size(); i != e; ++i) |
| 466 | if (CompactionTable[i].empty() && i != Type::VoidTyID && |
| 467 | i != Type::LabelTyID) { |
| 468 | const Type *Ty = cast<Type>(CompactionTable[Type::TypeTyID][i]); |
| 469 | getOrCreateCompactionTableSlot(Constant::getNullValue(Ty)); |
| 470 | } |
| 471 | |
| 472 | // Okay, now at this point, we have a legal compaction table. Since we want |
Chris Lattner | 68e3dbc | 2004-01-20 00:57:32 +0000 | [diff] [blame] | 473 | // to emit the smallest possible binaries, do not compactify the type plane if |
| 474 | // it will not save us anything. Because we have not yet incorporated the |
| 475 | // function body itself yet, we don't know whether or not it's a good idea to |
| 476 | // compactify other planes. We will defer this decision until later. |
| 477 | TypePlane &GlobalTypes = Table[Type::TypeTyID]; |
| 478 | |
| 479 | // All of the values types will be scrunched to the start of the types plane |
| 480 | // of the global table. Figure out just how many there are. |
| 481 | assert(!GlobalTypes.empty() && "No global types???"); |
| 482 | unsigned NumFCTypes = GlobalTypes.size()-1; |
| 483 | while (!cast<Type>(GlobalTypes[NumFCTypes])->isFirstClassType()) |
| 484 | --NumFCTypes; |
Chris Lattner | 614cdcd | 2004-01-18 21:07:07 +0000 | [diff] [blame] | 485 | |
Chris Lattner | 68e3dbc | 2004-01-20 00:57:32 +0000 | [diff] [blame] | 486 | // If there are fewer that 64 types, no instructions will be exploded due to |
| 487 | // the size of the type operands. Thus there is no need to compactify types. |
| 488 | // Also, if the compaction table contains most of the entries in the global |
| 489 | // table, there really is no reason to compactify either. |
| 490 | if (NumFCTypes < 64) { |
| 491 | // Decompactifying types is tricky, because we have to move type planes all |
| 492 | // over the place. At least we don't need to worry about updating the |
| 493 | // CompactionNodeMap for non-types though. |
| 494 | std::vector<TypePlane> TmpCompactionTable; |
| 495 | std::swap(CompactionTable, TmpCompactionTable); |
| 496 | TypePlane Types; |
| 497 | std::swap(Types, TmpCompactionTable[Type::TypeTyID]); |
| 498 | |
| 499 | // Move each plane back over to the uncompactified plane |
| 500 | while (!Types.empty()) { |
| 501 | const Type *Ty = cast<Type>(Types.back()); |
| 502 | Types.pop_back(); |
| 503 | CompactionNodeMap.erase(Ty); // Decompactify type! |
Chris Lattner | 614cdcd | 2004-01-18 21:07:07 +0000 | [diff] [blame] | 504 | |
Chris Lattner | 68e3dbc | 2004-01-20 00:57:32 +0000 | [diff] [blame] | 505 | if (Ty != Type::TypeTy) { |
| 506 | // Find the global slot number for this type. |
| 507 | int TySlot = getSlot(Ty); |
| 508 | assert(TySlot != -1 && "Type doesn't exist in global table?"); |
| 509 | |
| 510 | // Now we know where to put the compaction table plane. |
| 511 | if (CompactionTable.size() <= unsigned(TySlot)) |
| 512 | CompactionTable.resize(TySlot+1); |
| 513 | // Move the plane back into the compaction table. |
| 514 | std::swap(CompactionTable[TySlot], TmpCompactionTable[Types.size()]); |
Chris Lattner | 614cdcd | 2004-01-18 21:07:07 +0000 | [diff] [blame] | 515 | |
Chris Lattner | 68e3dbc | 2004-01-20 00:57:32 +0000 | [diff] [blame] | 516 | // And remove the empty plane we just moved in. |
| 517 | TmpCompactionTable.pop_back(); |
| 518 | } |
| 519 | } |
| 520 | } |
Chris Lattner | 614cdcd | 2004-01-18 21:07:07 +0000 | [diff] [blame] | 521 | } |
| 522 | |
Chris Lattner | 68e3dbc | 2004-01-20 00:57:32 +0000 | [diff] [blame] | 523 | |
| 524 | /// pruneCompactionTable - Once the entire function being processed has been |
| 525 | /// incorporated into the current compaction table, look over the compaction |
| 526 | /// table and check to see if there are any values whose compaction will not |
| 527 | /// save us any space in the bytecode file. If compactifying these values |
| 528 | /// serves no purpose, then we might as well not even emit the compactification |
| 529 | /// information to the bytecode file, saving a bit more space. |
| 530 | /// |
| 531 | /// Note that the type plane has already been compactified if possible. |
| 532 | /// |
| 533 | void SlotCalculator::pruneCompactionTable() { |
| 534 | TypePlane &TyPlane = CompactionTable[Type::TypeTyID]; |
| 535 | for (unsigned ctp = 0, e = CompactionTable.size(); ctp != e; ++ctp) |
| 536 | if (ctp != Type::TypeTyID && !CompactionTable[ctp].empty()) { |
| 537 | TypePlane &CPlane = CompactionTable[ctp]; |
| 538 | unsigned GlobalSlot = ctp; |
| 539 | if (!TyPlane.empty()) |
| 540 | GlobalSlot = getGlobalSlot(TyPlane[ctp]); |
| 541 | |
| 542 | if (GlobalSlot >= Table.size()) |
| 543 | Table.resize(GlobalSlot+1); |
| 544 | TypePlane &GPlane = Table[GlobalSlot]; |
| 545 | |
| 546 | unsigned ModLevel = getModuleLevel(ctp); |
| 547 | unsigned NumFunctionObjs = CPlane.size()-ModLevel; |
| 548 | |
| 549 | // If the maximum index required if all entries in this plane were merged |
| 550 | // into the global plane is less than 64, go ahead and eliminate the |
| 551 | // plane. |
| 552 | bool PrunePlane = GPlane.size() + NumFunctionObjs < 64; |
| 553 | |
| 554 | // If there are no function-local values defined, and the maximum |
| 555 | // referenced global entry is less than 64, we don't need to compactify. |
| 556 | if (!PrunePlane && NumFunctionObjs == 0) { |
| 557 | unsigned MaxIdx = 0; |
| 558 | for (unsigned i = 0; i != ModLevel; ++i) { |
| 559 | unsigned Idx = NodeMap[CPlane[i]]; |
| 560 | if (Idx > MaxIdx) MaxIdx = Idx; |
| 561 | } |
| 562 | PrunePlane = MaxIdx < 64; |
| 563 | } |
| 564 | |
| 565 | // Ok, finally, if we decided to prune this plane out of the compaction |
| 566 | // table, do so now. |
| 567 | if (PrunePlane) { |
| 568 | TypePlane OldPlane; |
| 569 | std::swap(OldPlane, CPlane); |
| 570 | |
| 571 | // Loop over the function local objects, relocating them to the global |
| 572 | // table plane. |
| 573 | for (unsigned i = ModLevel, e = OldPlane.size(); i != e; ++i) { |
| 574 | const Value *V = OldPlane[i]; |
| 575 | CompactionNodeMap.erase(V); |
| 576 | assert(NodeMap.count(V) == 0 && "Value already in table??"); |
| 577 | getOrCreateSlot(V); |
| 578 | } |
| 579 | |
| 580 | // For compactified global values, just remove them from the compaction |
| 581 | // node map. |
| 582 | for (unsigned i = 0; i != ModLevel; ++i) |
| 583 | CompactionNodeMap.erase(OldPlane[i]); |
| 584 | |
| 585 | // Update the new modulelevel for this plane. |
| 586 | assert(ctp < ModuleLevel.size() && "Cannot set modulelevel!"); |
| 587 | ModuleLevel[ctp] = GPlane.size()-NumFunctionObjs; |
| 588 | assert((int)ModuleLevel[ctp] >= 0 && "Bad computation!"); |
| 589 | } |
| 590 | } |
| 591 | } |
| 592 | |
| 593 | |
Chris Lattner | 8c202cd | 2004-01-15 18:47:15 +0000 | [diff] [blame] | 594 | int SlotCalculator::getSlot(const Value *V) const { |
Chris Lattner | 614cdcd | 2004-01-18 21:07:07 +0000 | [diff] [blame] | 595 | // If there is a CompactionTable active... |
| 596 | if (!CompactionNodeMap.empty()) { |
| 597 | std::map<const Value*, unsigned>::const_iterator I = |
| 598 | CompactionNodeMap.find(V); |
| 599 | if (I != CompactionNodeMap.end()) |
| 600 | return (int)I->second; |
Chris Lattner | 68e3dbc | 2004-01-20 00:57:32 +0000 | [diff] [blame] | 601 | // Otherwise, if it's not in the compaction table, it must be in a |
| 602 | // non-compactified plane. |
Chris Lattner | 614cdcd | 2004-01-18 21:07:07 +0000 | [diff] [blame] | 603 | } |
| 604 | |
Chris Lattner | 8c202cd | 2004-01-15 18:47:15 +0000 | [diff] [blame] | 605 | std::map<const Value*, unsigned>::const_iterator I = NodeMap.find(V); |
| 606 | if (I != NodeMap.end()) |
| 607 | return (int)I->second; |
| 608 | |
| 609 | // Do not number ConstantPointerRef's at all. They are an abomination. |
| 610 | if (const ConstantPointerRef *CPR = dyn_cast<ConstantPointerRef>(V)) |
| 611 | return getSlot(CPR->getValue()); |
| 612 | |
| 613 | return -1; |
Chris Lattner | 0095054 | 2001-06-06 20:29:01 +0000 | [diff] [blame] | 614 | } |
| 615 | |
Chris Lattner | 9a29790 | 2001-09-07 16:31:52 +0000 | [diff] [blame] | 616 | |
Alkis Evlogimenos | 6059638 | 2003-10-17 02:02:40 +0000 | [diff] [blame] | 617 | int SlotCalculator::getOrCreateSlot(const Value *V) { |
Chris Lattner | 68e3dbc | 2004-01-20 00:57:32 +0000 | [diff] [blame] | 618 | if (V->getType() == Type::VoidTy) return -1; |
| 619 | |
Alkis Evlogimenos | 6059638 | 2003-10-17 02:02:40 +0000 | [diff] [blame] | 620 | int SlotNo = getSlot(V); // Check to see if it's already in! |
Chris Lattner | 9a29790 | 2001-09-07 16:31:52 +0000 | [diff] [blame] | 621 | if (SlotNo != -1) return SlotNo; |
Chris Lattner | 3413d15 | 2003-03-19 20:57:22 +0000 | [diff] [blame] | 622 | |
Chris Lattner | 8c202cd | 2004-01-15 18:47:15 +0000 | [diff] [blame] | 623 | // Do not number ConstantPointerRef's at all. They are an abomination. |
| 624 | if (const ConstantPointerRef *CPR = dyn_cast<ConstantPointerRef>(V)) |
| 625 | return getOrCreateSlot(CPR->getValue()); |
| 626 | |
Chris Lattner | 614cdcd | 2004-01-18 21:07:07 +0000 | [diff] [blame] | 627 | if (!isa<GlobalValue>(V)) // Initializers for globals are handled explicitly |
Chris Lattner | 3413d15 | 2003-03-19 20:57:22 +0000 | [diff] [blame] | 628 | if (const Constant *C = dyn_cast<Constant>(V)) { |
Chris Lattner | 614cdcd | 2004-01-18 21:07:07 +0000 | [diff] [blame] | 629 | assert(CompactionNodeMap.empty() && |
| 630 | "All needed constants should be in the compaction map already!"); |
| 631 | |
Chris Lattner | dcea630 | 2004-01-14 23:34:39 +0000 | [diff] [blame] | 632 | // If we are emitting a bytecode file, do not index the characters that |
| 633 | // make up constant strings. We emit constant strings as special |
| 634 | // entities that don't require their individual characters to be emitted. |
| 635 | if (!BuildBytecodeInfo || !isa<ConstantArray>(C) || |
| 636 | !cast<ConstantArray>(C)->isString()) { |
| 637 | // This makes sure that if a constant has uses (for example an array of |
| 638 | // const ints), that they are inserted also. |
| 639 | // |
| 640 | for (User::const_op_iterator I = C->op_begin(), E = C->op_end(); |
| 641 | I != E; ++I) |
| 642 | getOrCreateSlot(*I); |
| 643 | } else { |
| 644 | assert(ModuleLevel.empty() && |
| 645 | "How can a constant string be directly accessed in a function?"); |
| 646 | // Otherwise, if we are emitting a bytecode file and this IS a string, |
| 647 | // remember it. |
| 648 | if (!C->isNullValue()) |
| 649 | ConstantStrings.push_back(cast<ConstantArray>(C)); |
| 650 | } |
Chris Lattner | 3413d15 | 2003-03-19 20:57:22 +0000 | [diff] [blame] | 651 | } |
| 652 | |
Alkis Evlogimenos | 6059638 | 2003-10-17 02:02:40 +0000 | [diff] [blame] | 653 | return insertValue(V); |
Chris Lattner | 9a29790 | 2001-09-07 16:31:52 +0000 | [diff] [blame] | 654 | } |
| 655 | |
| 656 | |
Alkis Evlogimenos | 6059638 | 2003-10-17 02:02:40 +0000 | [diff] [blame] | 657 | int SlotCalculator::insertValue(const Value *D, bool dontIgnore) { |
Chris Lattner | 9a29790 | 2001-09-07 16:31:52 +0000 | [diff] [blame] | 658 | assert(D && "Can't insert a null value!"); |
Alkis Evlogimenos | 6059638 | 2003-10-17 02:02:40 +0000 | [diff] [blame] | 659 | assert(getSlot(D) == -1 && "Value is already in the table!"); |
Chris Lattner | 0095054 | 2001-06-06 20:29:01 +0000 | [diff] [blame] | 660 | |
Chris Lattner | 614cdcd | 2004-01-18 21:07:07 +0000 | [diff] [blame] | 661 | // If we are building a compaction map, and if this plane is being compacted, |
| 662 | // insert the value into the compaction map, not into the global map. |
| 663 | if (!CompactionNodeMap.empty()) { |
| 664 | if (D->getType() == Type::VoidTy) return -1; // Do not insert void values |
| 665 | assert(!isa<Type>(D) && !isa<Constant>(D) && !isa<GlobalValue>(D) && |
| 666 | "Types, constants, and globals should be in global SymTab!"); |
| 667 | |
Chris Lattner | 68e3dbc | 2004-01-20 00:57:32 +0000 | [diff] [blame] | 668 | int Plane = getSlot(D->getType()); |
| 669 | assert(Plane != -1 && CompactionTable.size() > (unsigned)Plane && |
| 670 | "Didn't find value type!"); |
| 671 | if (!CompactionTable[Plane].empty()) |
| 672 | return getOrCreateCompactionTableSlot(D); |
Chris Lattner | 614cdcd | 2004-01-18 21:07:07 +0000 | [diff] [blame] | 673 | } |
| 674 | |
Chris Lattner | 0095054 | 2001-06-06 20:29:01 +0000 | [diff] [blame] | 675 | // If this node does not contribute to a plane, or if the node has a |
Chris Lattner | 9a29790 | 2001-09-07 16:31:52 +0000 | [diff] [blame] | 676 | // name and we don't want names, then ignore the silly node... Note that types |
| 677 | // do need slot numbers so that we can keep track of where other values land. |
Chris Lattner | 0095054 | 2001-06-06 20:29:01 +0000 | [diff] [blame] | 678 | // |
Chris Lattner | 9b50c15 | 2001-07-26 16:28:37 +0000 | [diff] [blame] | 679 | if (!dontIgnore) // Don't ignore nonignorables! |
| 680 | if (D->getType() == Type::VoidTy || // Ignore void type nodes |
Chris Lattner | 8ce7501 | 2004-01-14 02:49:34 +0000 | [diff] [blame] | 681 | (!BuildBytecodeInfo && // Ignore named and constants |
Chris Lattner | e9bb2df | 2001-12-03 22:26:30 +0000 | [diff] [blame] | 682 | (D->hasName() || isa<Constant>(D)) && !isa<Type>(D))) { |
Chris Lattner | 3413d15 | 2003-03-19 20:57:22 +0000 | [diff] [blame] | 683 | SC_DEBUG("ignored value " << *D << "\n"); |
Chris Lattner | 9a29790 | 2001-09-07 16:31:52 +0000 | [diff] [blame] | 684 | return -1; // We do need types unconditionally though |
| 685 | } |
Chris Lattner | 0095054 | 2001-06-06 20:29:01 +0000 | [diff] [blame] | 686 | |
Chris Lattner | 9a29790 | 2001-09-07 16:31:52 +0000 | [diff] [blame] | 687 | // If it's a type, make sure that all subtypes of the type are included... |
Chris Lattner | 949a362 | 2003-07-23 15:30:06 +0000 | [diff] [blame] | 688 | if (const Type *TheTy = dyn_cast<Type>(D)) { |
Chris Lattner | f1fef65 | 2001-10-13 06:35:09 +0000 | [diff] [blame] | 689 | |
| 690 | // Insert the current type before any subtypes. This is important because |
| 691 | // recursive types elements are inserted in a bottom up order. Changing |
| 692 | // this here can break things. For example: |
| 693 | // |
| 694 | // global { \2 * } { { \2 }* null } |
| 695 | // |
Alkis Evlogimenos | 6059638 | 2003-10-17 02:02:40 +0000 | [diff] [blame] | 696 | int ResultSlot = doInsertValue(TheTy); |
| 697 | SC_DEBUG(" Inserted type: " << TheTy->getDescription() << " slot=" << |
| 698 | ResultSlot << "\n"); |
Chris Lattner | 9a29790 | 2001-09-07 16:31:52 +0000 | [diff] [blame] | 699 | |
Alkis Evlogimenos | 088eb45 | 2003-10-31 03:02:34 +0000 | [diff] [blame] | 700 | // Loop over any contained types in the definition... in post |
| 701 | // order. |
Chris Lattner | 9a29790 | 2001-09-07 16:31:52 +0000 | [diff] [blame] | 702 | // |
Alkis Evlogimenos | 088eb45 | 2003-10-31 03:02:34 +0000 | [diff] [blame] | 703 | for (po_iterator<const Type*> I = po_begin(TheTy), E = po_end(TheTy); |
Alkis Evlogimenos | 74fa84f | 2003-10-30 21:04:44 +0000 | [diff] [blame] | 704 | I != E; ++I) { |
Chris Lattner | 9a29790 | 2001-09-07 16:31:52 +0000 | [diff] [blame] | 705 | if (*I != TheTy) { |
Alkis Evlogimenos | 74fa84f | 2003-10-30 21:04:44 +0000 | [diff] [blame] | 706 | const Type *SubTy = *I; |
Alkis Evlogimenos | 088eb45 | 2003-10-31 03:02:34 +0000 | [diff] [blame] | 707 | // If we haven't seen this sub type before, add it to our type table! |
| 708 | if (getSlot(SubTy) == -1) { |
| 709 | SC_DEBUG(" Inserting subtype: " << SubTy->getDescription() << "\n"); |
| 710 | int Slot = doInsertValue(SubTy); |
| 711 | SC_DEBUG(" Inserted subtype: " << SubTy->getDescription() << |
| 712 | " slot=" << Slot << "\n"); |
| 713 | } |
Alkis Evlogimenos | 74fa84f | 2003-10-30 21:04:44 +0000 | [diff] [blame] | 714 | } |
| 715 | } |
Chris Lattner | f1fef65 | 2001-10-13 06:35:09 +0000 | [diff] [blame] | 716 | return ResultSlot; |
Chris Lattner | 9a29790 | 2001-09-07 16:31:52 +0000 | [diff] [blame] | 717 | } |
| 718 | |
| 719 | // Okay, everything is happy, actually insert the silly value now... |
Alkis Evlogimenos | 6059638 | 2003-10-17 02:02:40 +0000 | [diff] [blame] | 720 | return doInsertValue(D); |
Chris Lattner | 9a29790 | 2001-09-07 16:31:52 +0000 | [diff] [blame] | 721 | } |
| 722 | |
Alkis Evlogimenos | 6059638 | 2003-10-17 02:02:40 +0000 | [diff] [blame] | 723 | // doInsertValue - This is a small helper function to be called only |
| 724 | // be insertValue. |
Chris Lattner | 9a29790 | 2001-09-07 16:31:52 +0000 | [diff] [blame] | 725 | // |
Alkis Evlogimenos | 6059638 | 2003-10-17 02:02:40 +0000 | [diff] [blame] | 726 | int SlotCalculator::doInsertValue(const Value *D) { |
Chris Lattner | 0095054 | 2001-06-06 20:29:01 +0000 | [diff] [blame] | 727 | const Type *Typ = D->getType(); |
Chris Lattner | 9b50c15 | 2001-07-26 16:28:37 +0000 | [diff] [blame] | 728 | unsigned Ty; |
| 729 | |
| 730 | // Used for debugging DefSlot=-1 assertion... |
| 731 | //if (Typ == Type::TypeTy) |
Chris Lattner | cfe26c9 | 2001-10-01 18:26:53 +0000 | [diff] [blame] | 732 | // cerr << "Inserting type '" << cast<Type>(D)->getDescription() << "'!\n"; |
Chris Lattner | 9b50c15 | 2001-07-26 16:28:37 +0000 | [diff] [blame] | 733 | |
Chris Lattner | 0095054 | 2001-06-06 20:29:01 +0000 | [diff] [blame] | 734 | if (Typ->isDerivedType()) { |
Chris Lattner | 68e3dbc | 2004-01-20 00:57:32 +0000 | [diff] [blame] | 735 | int ValSlot; |
| 736 | if (CompactionTable.empty()) |
| 737 | ValSlot = getSlot(Typ); |
| 738 | else |
| 739 | ValSlot = getGlobalSlot(Typ); |
Chris Lattner | 3413d15 | 2003-03-19 20:57:22 +0000 | [diff] [blame] | 740 | if (ValSlot == -1) { // Have we already entered this type? |
Chris Lattner | 9a29790 | 2001-09-07 16:31:52 +0000 | [diff] [blame] | 741 | // Nope, this is the first we have seen the type, process it. |
Alkis Evlogimenos | 6059638 | 2003-10-17 02:02:40 +0000 | [diff] [blame] | 742 | ValSlot = insertValue(Typ, true); |
Chris Lattner | 3413d15 | 2003-03-19 20:57:22 +0000 | [diff] [blame] | 743 | assert(ValSlot != -1 && "ProcessType returned -1 for a type?"); |
Chris Lattner | 0095054 | 2001-06-06 20:29:01 +0000 | [diff] [blame] | 744 | } |
Chris Lattner | 3413d15 | 2003-03-19 20:57:22 +0000 | [diff] [blame] | 745 | Ty = (unsigned)ValSlot; |
Chris Lattner | 9b50c15 | 2001-07-26 16:28:37 +0000 | [diff] [blame] | 746 | } else { |
| 747 | Ty = Typ->getPrimitiveID(); |
Chris Lattner | 0095054 | 2001-06-06 20:29:01 +0000 | [diff] [blame] | 748 | } |
| 749 | |
| 750 | if (Table.size() <= Ty) // Make sure we have the type plane allocated... |
| 751 | Table.resize(Ty+1, TypePlane()); |
Chris Lattner | 3413d15 | 2003-03-19 20:57:22 +0000 | [diff] [blame] | 752 | |
| 753 | // If this is the first value to get inserted into the type plane, make sure |
| 754 | // to insert the implicit null value... |
Chris Lattner | 80b9734 | 2004-01-17 23:25:43 +0000 | [diff] [blame] | 755 | if (Table[Ty].empty() && BuildBytecodeInfo && hasNullValue(Ty)) { |
Chris Lattner | 3413d15 | 2003-03-19 20:57:22 +0000 | [diff] [blame] | 756 | Value *ZeroInitializer = Constant::getNullValue(Typ); |
| 757 | |
| 758 | // If we are pushing zeroinit, it will be handled below. |
| 759 | if (D != ZeroInitializer) { |
| 760 | Table[Ty].push_back(ZeroInitializer); |
| 761 | NodeMap[ZeroInitializer] = 0; |
| 762 | } |
| 763 | } |
| 764 | |
Chris Lattner | 9a29790 | 2001-09-07 16:31:52 +0000 | [diff] [blame] | 765 | // Insert node into table and NodeMap... |
| 766 | unsigned DestSlot = NodeMap[D] = Table[Ty].size(); |
Chris Lattner | 0095054 | 2001-06-06 20:29:01 +0000 | [diff] [blame] | 767 | Table[Ty].push_back(D); |
Chris Lattner | 9a29790 | 2001-09-07 16:31:52 +0000 | [diff] [blame] | 768 | |
Chris Lattner | f1fef65 | 2001-10-13 06:35:09 +0000 | [diff] [blame] | 769 | SC_DEBUG(" Inserting value [" << Ty << "] = " << D << " slot=" << |
| 770 | DestSlot << " ["); |
Chris Lattner | 2fbfdcf | 2002-04-07 20:49:59 +0000 | [diff] [blame] | 771 | // G = Global, C = Constant, T = Type, F = Function, o = other |
Chris Lattner | e9bb2df | 2001-12-03 22:26:30 +0000 | [diff] [blame] | 772 | SC_DEBUG((isa<GlobalVariable>(D) ? "G" : (isa<Constant>(D) ? "C" : |
Chris Lattner | 2fbfdcf | 2002-04-07 20:49:59 +0000 | [diff] [blame] | 773 | (isa<Type>(D) ? "T" : (isa<Function>(D) ? "F" : "o"))))); |
Chris Lattner | f1fef65 | 2001-10-13 06:35:09 +0000 | [diff] [blame] | 774 | SC_DEBUG("]\n"); |
Chris Lattner | 9a29790 | 2001-09-07 16:31:52 +0000 | [diff] [blame] | 775 | return (int)DestSlot; |
Chris Lattner | 0095054 | 2001-06-06 20:29:01 +0000 | [diff] [blame] | 776 | } |