aboutsummaryrefslogtreecommitdiffstats
path: root/lib/Bytecode/Writer/SlotCalculator.cpp
blob: 3211e728ff2ceab10b0893cfb5123addfbcbc9df (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
//===-- SlotCalculator.cpp - Calculate what slots values land in ------------=//
//
// This file implements a useful analysis step to figure out what numbered 
// slots values in a program will land in (keeping track of per plane
// information as required.
//
// This is used primarily for when writing a file to disk, either in bytecode
// or source format.
//
//===----------------------------------------------------------------------===//

#include "llvm/Analysis/SlotCalculator.h"
#include "llvm/Analysis/ConstantsScanner.h"
#include "llvm/Method.h"
#include "llvm/GlobalVariable.h"
#include "llvm/Module.h"
#include "llvm/BasicBlock.h"
#include "llvm/ConstPoolVals.h"
#include "llvm/iOther.h"
#include "llvm/DerivedTypes.h"
#include "llvm/SymbolTable.h"
#include "llvm/Support/STLExtras.h"
#include "llvm/Support/DepthFirstIterator.h"
#include <algorithm>

#if 0
#define SC_DEBUG(X) cerr << X
#else
#define SC_DEBUG(X)
#endif

SlotCalculator::SlotCalculator(const Module *M, bool IgnoreNamed) {
  IgnoreNamedNodes = IgnoreNamed;
  TheModule = M;

  // Preload table... Make sure that all of the primitive types are in the table
  // and that their Primitive ID is equal to their slot #
  //
  for (unsigned i = 0; i < Type::FirstDerivedTyID; ++i) {
    assert(Type::getPrimitiveType((Type::PrimitiveID)i));
    insertVal(Type::getPrimitiveType((Type::PrimitiveID)i), true);
  }

  if (M == 0) return;   // Empty table...
  processModule();
}

SlotCalculator::SlotCalculator(const Method *M, bool IgnoreNamed) {
  IgnoreNamedNodes = IgnoreNamed;
  TheModule = M ? M->getParent() : 0;

  // Preload table... Make sure that all of the primitive types are in the table
  // and that their Primitive ID is equal to their slot #
  //
  for (unsigned i = 0; i < Type::FirstDerivedTyID; ++i) {
    assert(Type::getPrimitiveType((Type::PrimitiveID)i));
    insertVal(Type::getPrimitiveType((Type::PrimitiveID)i), true);
  }

  if (TheModule == 0) return;   // Empty table...

  processModule();              // Process module level stuff
  incorporateMethod(M);         // Start out in incorporated state
}


// processModule - Process all of the module level method declarations and
// types that are available.
//
void SlotCalculator::processModule() {
  SC_DEBUG("begin processModule!\n");

  // Add all of the constants that the global variables might refer to first.
  //
  for (Module::const_giterator I = TheModule->gbegin(), E = TheModule->gend();
       I != E; ++I) {
    if ((*I)->hasInitializer())
      insertValue((*I)->getInitializer());
  }

  // Add all of the global variables to the value table...
  //
  for_each(TheModule->gbegin(), TheModule->gend(),
	   bind_obj(this, &SlotCalculator::insertValue));

  // Scavenge the types out of the methods, then add the methods themselves to
  // the value table...
  //
  for_each(TheModule->begin(), TheModule->end(),  // Insert methods...
	   bind_obj(this, &SlotCalculator::insertValue));

  // Insert constants that are named at module level into the slot pool so that
  // the module symbol table can refer to them...
  //
  if (TheModule->hasSymbolTable() && !IgnoreNamedNodes) {
    SC_DEBUG("Inserting SymbolTable values:\n");
    processSymbolTable(TheModule->getSymbolTable());
  }

  SC_DEBUG("end processModule!\n");
}

// processSymbolTable - Insert all of the values in the specified symbol table
// into the values table...
//
void SlotCalculator::processSymbolTable(const SymbolTable *ST) {
  for (SymbolTable::const_iterator I = ST->begin(), E = ST->end(); I != E; ++I)
    for (SymbolTable::type_const_iterator TI = I->second.begin(), 
	   TE = I->second.end(); TI != TE; ++TI)
      insertValue(TI->second);
}

void SlotCalculator::processSymbolTableConstants(const SymbolTable *ST) {
  for (SymbolTable::const_iterator I = ST->begin(), E = ST->end(); I != E; ++I)
    for (SymbolTable::type_const_iterator TI = I->second.begin(), 
	   TE = I->second.end(); TI != TE; ++TI)
      if (isa<ConstPoolVal>(TI->second))
	insertValue(TI->second);
}


void SlotCalculator::incorporateMethod(const Method *M) {
  assert(ModuleLevel.size() == 0 && "Module already incorporated!");

  SC_DEBUG("begin processMethod!\n");

  // Save the Table state before we process the method...
  for (unsigned i = 0; i < Table.size(); ++i)
    ModuleLevel.push_back(Table[i].size());

  SC_DEBUG("Inserting method arguments\n");

  // Iterate over method arguments, adding them to the value table...
  for_each(M->getArgumentList().begin(), M->getArgumentList().end(),
	   bind_obj(this, &SlotCalculator::insertValue));

  // Iterate over all of the instructions in the method, looking for constant
  // values that are referenced.  Add these to the value pools before any
  // nonconstant values.  This will be turned into the constant pool for the
  // bytecode writer.
  //
  if (!IgnoreNamedNodes) {                // Assembly writer does not need this!
    SC_DEBUG("Inserting method constants:\n";
	     for (constant_iterator I = constant_begin(M), E = constant_end(M);
		  I != E; ++I) {
	       cerr << "  " << I->getType()->getDescription() 
		    << " " << I->getStrValue() << endl;
	     });

    // Emit all of the constants that are being used by the instructions in the
    // method...
    for_each(constant_begin(M), constant_end(M),
	     bind_obj(this, &SlotCalculator::insertValue));

    // If there is a symbol table, it is possible that the user has names for
    // constants that are not being used.  In this case, we will have problems
    // if we don't emit the constants now, because otherwise we will get 
    // symboltable references to constants not in the output.  Scan for these
    // constants now.
    //
    if (M->hasSymbolTable())
      processSymbolTableConstants(M->getSymbolTable());
  }

  SC_DEBUG("Inserting Labels:\n");

  // Iterate over basic blocks, adding them to the value table...
  for_each(M->begin(), M->end(),
	   bind_obj(this, &SlotCalculator::insertValue));

  SC_DEBUG("Inserting Instructions:\n");

  // Add all of the instructions to the type planes...
  for_each(M->inst_begin(), M->inst_end(),
	   bind_obj(this, &SlotCalculator::insertValue));

  if (M->hasSymbolTable() && !IgnoreNamedNodes) {
    SC_DEBUG("Inserting SymbolTable values:\n");
    processSymbolTable(M->getSymbolTable());
  }

  SC_DEBUG("end processMethod!\n");
}

void SlotCalculator::purgeMethod() {
  assert(ModuleLevel.size() != 0 && "Module not incorporated!");
  unsigned NumModuleTypes = ModuleLevel.size();

  SC_DEBUG("begin purgeMethod!\n");

  // First, remove values from existing type planes
  for (unsigned i = 0; i < NumModuleTypes; ++i) {
    unsigned ModuleSize = ModuleLevel[i];  // Size of plane before method came
    TypePlane &CurPlane = Table[i];
    //SC_DEBUG("Processing Plane " <<i<< " of size " << CurPlane.size() <<endl);
	     
    while (CurPlane.size() != ModuleSize) {
      //SC_DEBUG("  Removing [" << i << "] Value=" << CurPlane.back() << "\n");
      map<const Value *, unsigned>::iterator NI = NodeMap.find(CurPlane.back());
      assert(NI != NodeMap.end() && "Node not in nodemap?");
      NodeMap.erase(NI);   // Erase from nodemap
      CurPlane.pop_back();                            // Shrink plane
    }
  }

  // We don't need this state anymore, free it up.
  ModuleLevel.clear();

  // Next, remove any type planes defined by the method...
  while (NumModuleTypes != Table.size()) {
    TypePlane &Plane = Table.back();
    SC_DEBUG("Removing Plane " << (Table.size()-1) << " of size "
	     << Plane.size() << endl);
    while (Plane.size()) {
      NodeMap.erase(NodeMap.find(Plane.back()));   // Erase from nodemap
      Plane.pop_back();                            // Shrink plane
    }

    Table.pop_back();                      // Nuke the plane, we don't like it.
  }

  SC_DEBUG("end purgeMethod!\n");
}

int SlotCalculator::getValSlot(const Value *D) const {
  map<const Value*, unsigned>::const_iterator I = NodeMap.find(D);
  if (I == NodeMap.end()) return -1;
 
  return (int)I->second;
}


int SlotCalculator::insertValue(const Value *D) {
  if (isa<ConstPoolVal>(D) || isa<GlobalVariable>(D)) {
    const User *U = cast<const User>(D);
    // This makes sure that if a constant has uses (for example an array
    // of const ints), that they are inserted also.  Same for global variable
    // initializers.
    //
    for(User::op_const_iterator I = U->op_begin(), E = U->op_end(); I != E; ++I)
      if (!isa<GlobalValue>(*I))  // Don't chain insert global values
	insertValue(*I);
  }

  int SlotNo = getValSlot(D);        // Check to see if it's already in!
  if (SlotNo != -1) return SlotNo;
  return insertVal(D); 
}


int SlotCalculator::insertVal(const Value *D, bool dontIgnore = false) {
  assert(D && "Can't insert a null value!");
  assert(getValSlot(D) == -1 && "Value is already in the table!");

  // If this node does not contribute to a plane, or if the node has a 
  // name and we don't want names, then ignore the silly node... Note that types
  // do need slot numbers so that we can keep track of where other values land.
  //
  if (!dontIgnore)                               // Don't ignore nonignorables!
    if (D->getType() == Type::VoidTy ||          // Ignore void type nodes
	(IgnoreNamedNodes &&                     // Ignore named and constants
	 (D->hasName() || isa<ConstPoolVal>(D)) && !isa<Type>(D))) {
      SC_DEBUG("ignored value " << D << endl);
      return -1;                  // We do need types unconditionally though
    }

  // If it's a type, make sure that all subtypes of the type are included...
  if (const Type *TheTy = dyn_cast<const Type>(D)) {

    // Insert the current type before any subtypes.  This is important because
    // recursive types elements are inserted in a bottom up order.  Changing
    // this here can break things.  For example:
    //
    //    global { \2 * } { { \2 }* null }
    //
    int ResultSlot;
    if ((ResultSlot = getValSlot(TheTy)) == -1) {
      ResultSlot = doInsertVal(TheTy);
      SC_DEBUG("  Inserted type: " << TheTy->getDescription() << " slot=" <<
	       ResultSlot << endl);
    }

    // Loop over any contained types in the definition... in reverse depth first
    // order.  This assures that all of the leafs of a type are output before
    // the type itself is. This also assures us that we will not hit infinite
    // recursion on recursive types...
    //
    for (df_iterator<const Type*> I = df_begin(TheTy, true), 
                                  E = df_end(TheTy); I != E; ++I)
      if (*I != TheTy) {
	// If we haven't seen this sub type before, add it to our type table!
	const Type *SubTy = *I;
	if (getValSlot(SubTy) == -1) {
	  SC_DEBUG("  Inserting subtype: " << SubTy->getDescription() << endl);
	  int Slot = doInsertVal(SubTy);
	  SC_DEBUG("  Inserted subtype: " << SubTy->getDescription() << 
		   " slot=" << Slot << endl);
	}
      }
    return ResultSlot;
  }

  // Okay, everything is happy, actually insert the silly value now...
  return doInsertVal(D);
}


// doInsertVal - This is a small helper function to be called only be insertVal.
//
int SlotCalculator::doInsertVal(const Value *D) {
  const Type *Typ = D->getType();
  unsigned Ty;

  // Used for debugging DefSlot=-1 assertion...
  //if (Typ == Type::TypeTy)
  //  cerr << "Inserting type '" << cast<Type>(D)->getDescription() << "'!\n";

  if (Typ->isDerivedType()) {
    int DefSlot = getValSlot(Typ);
    if (DefSlot == -1) {                // Have we already entered this type?
      // Nope, this is the first we have seen the type, process it.
      DefSlot = insertVal(Typ, true);
      assert(DefSlot != -1 && "ProcessType returned -1 for a type?");
    }
    Ty = (unsigned)DefSlot;
  } else {
    Ty = Typ->getPrimitiveID();
  }
  
  if (Table.size() <= Ty)    // Make sure we have the type plane allocated...
    Table.resize(Ty+1, TypePlane());
  
  // Insert node into table and NodeMap...
  unsigned DestSlot = NodeMap[D] = Table[Ty].size();
  Table[Ty].push_back(D);

  SC_DEBUG("  Inserting value [" << Ty << "] = " << D << " slot=" << 
	   DestSlot << " [");
  // G = Global, C = ConstPoolVal, T = Type, M = Method, o = other
  SC_DEBUG((isa<GlobalVariable>(D) ? "G" : (isa<ConstPoolVal>(D) ? "C" : 
           (isa<Type>(D) ? "T" : (isa<Method>(D) ? "M" : "o")))));
  SC_DEBUG("]\n");
  return (int)DestSlot;
}