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