Mercurial > hg > CbC > CbC_llvm

comparison lib/Bitcode/Writer/ValueEnumerator.cpp @ 0:95c75e76d11b LLVM3.4

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
LLVM 3.4
author Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
date Thu, 12 Dec 2013 13:56:28 +0900
parents
children 54457678186b
comparison
equal deleted inserted replaced
-1:000000000000 0:95c75e76d11b
1 //===-- ValueEnumerator.cpp - Number values and types for bitcode writer --===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This file implements the ValueEnumerator class.
11 //
12 //===----------------------------------------------------------------------===//
13
14 #include "ValueEnumerator.h"
15 #include "llvm/ADT/STLExtras.h"
16 #include "llvm/ADT/SmallPtrSet.h"
17 #include "llvm/IR/Constants.h"
18 #include "llvm/IR/DerivedTypes.h"
19 #include "llvm/IR/Instructions.h"
20 #include "llvm/IR/Module.h"
21 #include "llvm/IR/ValueSymbolTable.h"
22 #include "llvm/Support/Debug.h"
23 #include "llvm/Support/raw_ostream.h"
24 #include <algorithm>
25 using namespace llvm;
26
27 static bool isIntOrIntVectorValue(const std::pair<const Value*, unsigned> &V) {
28 return V.first->getType()->isIntOrIntVectorTy();
29 }
30
31 /// ValueEnumerator - Enumerate module-level information.
32 ValueEnumerator::ValueEnumerator(const Module *M) {
33 // Enumerate the global variables.
34 for (Module::const_global_iterator I = M->global_begin(),
35 E = M->global_end(); I != E; ++I)
36 EnumerateValue(I);
37
38 // Enumerate the functions.
39 for (Module::const_iterator I = M->begin(), E = M->end(); I != E; ++I) {
40 EnumerateValue(I);
41 EnumerateAttributes(cast<Function>(I)->getAttributes());
42 }
43
44 // Enumerate the aliases.
45 for (Module::const_alias_iterator I = M->alias_begin(), E = M->alias_end();
46 I != E; ++I)
47 EnumerateValue(I);
48
49 // Remember what is the cutoff between globalvalue's and other constants.
50 unsigned FirstConstant = Values.size();
51
52 // Enumerate the global variable initializers.
53 for (Module::const_global_iterator I = M->global_begin(),
54 E = M->global_end(); I != E; ++I)
55 if (I->hasInitializer())
56 EnumerateValue(I->getInitializer());
57
58 // Enumerate the aliasees.
59 for (Module::const_alias_iterator I = M->alias_begin(), E = M->alias_end();
60 I != E; ++I)
61 EnumerateValue(I->getAliasee());
62
63 // Enumerate the prefix data constants.
64 for (Module::const_iterator I = M->begin(), E = M->end(); I != E; ++I)
65 if (I->hasPrefixData())
66 EnumerateValue(I->getPrefixData());
67
68 // Insert constants and metadata that are named at module level into the slot
69 // pool so that the module symbol table can refer to them...
70 EnumerateValueSymbolTable(M->getValueSymbolTable());
71 EnumerateNamedMetadata(M);
72
73 SmallVector<std::pair<unsigned, MDNode*>, 8> MDs;
74
75 // Enumerate types used by function bodies and argument lists.
76 for (Module::const_iterator F = M->begin(), E = M->end(); F != E; ++F) {
77
78 for (Function::const_arg_iterator I = F->arg_begin(), E = F->arg_end();
79 I != E; ++I)
80 EnumerateType(I->getType());
81
82 for (Function::const_iterator BB = F->begin(), E = F->end(); BB != E; ++BB)
83 for (BasicBlock::const_iterator I = BB->begin(), E = BB->end(); I!=E;++I){
84 for (User::const_op_iterator OI = I->op_begin(), E = I->op_end();
85 OI != E; ++OI) {
86 if (MDNode *MD = dyn_cast<MDNode>(*OI))
87 if (MD->isFunctionLocal() && MD->getFunction())
88 // These will get enumerated during function-incorporation.
89 continue;
90 EnumerateOperandType(*OI);
91 }
92 EnumerateType(I->getType());
93 if (const CallInst *CI = dyn_cast<CallInst>(I))
94 EnumerateAttributes(CI->getAttributes());
95 else if (const InvokeInst *II = dyn_cast<InvokeInst>(I))
96 EnumerateAttributes(II->getAttributes());
97
98 // Enumerate metadata attached with this instruction.
99 MDs.clear();
100 I->getAllMetadataOtherThanDebugLoc(MDs);
101 for (unsigned i = 0, e = MDs.size(); i != e; ++i)
102 EnumerateMetadata(MDs[i].second);
103
104 if (!I->getDebugLoc().isUnknown()) {
105 MDNode *Scope, *IA;
106 I->getDebugLoc().getScopeAndInlinedAt(Scope, IA, I->getContext());
107 if (Scope) EnumerateMetadata(Scope);
108 if (IA) EnumerateMetadata(IA);
109 }
110 }
111 }
112
113 // Optimize constant ordering.
114 OptimizeConstants(FirstConstant, Values.size());
115 }
116
117 unsigned ValueEnumerator::getInstructionID(const Instruction *Inst) const {
118 InstructionMapType::const_iterator I = InstructionMap.find(Inst);
119 assert(I != InstructionMap.end() && "Instruction is not mapped!");
120 return I->second;
121 }
122
123 void ValueEnumerator::setInstructionID(const Instruction *I) {
124 InstructionMap[I] = InstructionCount++;
125 }
126
127 unsigned ValueEnumerator::getValueID(const Value *V) const {
128 if (isa<MDNode>(V) || isa<MDString>(V)) {
129 ValueMapType::const_iterator I = MDValueMap.find(V);
130 assert(I != MDValueMap.end() && "Value not in slotcalculator!");
131 return I->second-1;
132 }
133
134 ValueMapType::const_iterator I = ValueMap.find(V);
135 assert(I != ValueMap.end() && "Value not in slotcalculator!");
136 return I->second-1;
137 }
138
139 void ValueEnumerator::dump() const {
140 print(dbgs(), ValueMap, "Default");
141 dbgs() << '\n';
142 print(dbgs(), MDValueMap, "MetaData");
143 dbgs() << '\n';
144 }
145
146 void ValueEnumerator::print(raw_ostream &OS, const ValueMapType &Map,
147 const char *Name) const {
148
149 OS << "Map Name: " << Name << "\n";
150 OS << "Size: " << Map.size() << "\n";
151 for (ValueMapType::const_iterator I = Map.begin(),
152 E = Map.end(); I != E; ++I) {
153
154 const Value *V = I->first;
155 if (V->hasName())
156 OS << "Value: " << V->getName();
157 else
158 OS << "Value: [null]\n";
159 V->dump();
160
161 OS << " Uses(" << std::distance(V->use_begin(),V->use_end()) << "):";
162 for (Value::const_use_iterator UI = V->use_begin(), UE = V->use_end();
163 UI != UE; ++UI) {
164 if (UI != V->use_begin())
165 OS << ",";
166 if((*UI)->hasName())
167 OS << " " << (*UI)->getName();
168 else
169 OS << " [null]";
170
171 }
172 OS << "\n\n";
173 }
174 }
175
176 // Optimize constant ordering.
177 namespace {
178 struct CstSortPredicate {
179 ValueEnumerator &VE;
180 explicit CstSortPredicate(ValueEnumerator &ve) : VE(ve) {}
181 bool operator()(const std::pair<const Value*, unsigned> &LHS,
182 const std::pair<const Value*, unsigned> &RHS) {
183 // Sort by plane.
184 if (LHS.first->getType() != RHS.first->getType())
185 return VE.getTypeID(LHS.first->getType()) <
186 VE.getTypeID(RHS.first->getType());
187 // Then by frequency.
188 return LHS.second > RHS.second;
189 }
190 };
191 }
192
193 /// OptimizeConstants - Reorder constant pool for denser encoding.
194 void ValueEnumerator::OptimizeConstants(unsigned CstStart, unsigned CstEnd) {
195 if (CstStart == CstEnd || CstStart+1 == CstEnd) return;
196
197 CstSortPredicate P(*this);
198 std::stable_sort(Values.begin()+CstStart, Values.begin()+CstEnd, P);
199
200 // Ensure that integer and vector of integer constants are at the start of the
201 // constant pool. This is important so that GEP structure indices come before
202 // gep constant exprs.
203 std::partition(Values.begin()+CstStart, Values.begin()+CstEnd,
204 isIntOrIntVectorValue);
205
206 // Rebuild the modified portion of ValueMap.
207 for (; CstStart != CstEnd; ++CstStart)
208 ValueMap[Values[CstStart].first] = CstStart+1;
209 }
210
211
212 /// EnumerateValueSymbolTable - Insert all of the values in the specified symbol
213 /// table into the values table.
214 void ValueEnumerator::EnumerateValueSymbolTable(const ValueSymbolTable &VST) {
215 for (ValueSymbolTable::const_iterator VI = VST.begin(), VE = VST.end();
216 VI != VE; ++VI)
217 EnumerateValue(VI->getValue());
218 }
219
220 /// EnumerateNamedMetadata - Insert all of the values referenced by
221 /// named metadata in the specified module.
222 void ValueEnumerator::EnumerateNamedMetadata(const Module *M) {
223 for (Module::const_named_metadata_iterator I = M->named_metadata_begin(),
224 E = M->named_metadata_end(); I != E; ++I)
225 EnumerateNamedMDNode(I);
226 }
227
228 void ValueEnumerator::EnumerateNamedMDNode(const NamedMDNode *MD) {
229 for (unsigned i = 0, e = MD->getNumOperands(); i != e; ++i)
230 EnumerateMetadata(MD->getOperand(i));
231 }
232
233 /// EnumerateMDNodeOperands - Enumerate all non-function-local values
234 /// and types referenced by the given MDNode.
235 void ValueEnumerator::EnumerateMDNodeOperands(const MDNode *N) {
236 for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) {
237 if (Value *V = N->getOperand(i)) {
238 if (isa<MDNode>(V) || isa<MDString>(V))
239 EnumerateMetadata(V);
240 else if (!isa<Instruction>(V) && !isa<Argument>(V))
241 EnumerateValue(V);
242 } else
243 EnumerateType(Type::getVoidTy(N->getContext()));
244 }
245 }
246
247 void ValueEnumerator::EnumerateMetadata(const Value *MD) {
248 assert((isa<MDNode>(MD) || isa<MDString>(MD)) && "Invalid metadata kind");
249
250 // Enumerate the type of this value.
251 EnumerateType(MD->getType());
252
253 const MDNode *N = dyn_cast<MDNode>(MD);
254
255 // In the module-level pass, skip function-local nodes themselves, but
256 // do walk their operands.
257 if (N && N->isFunctionLocal() && N->getFunction()) {
258 EnumerateMDNodeOperands(N);
259 return;
260 }
261
262 // Check to see if it's already in!
263 unsigned &MDValueID = MDValueMap[MD];
264 if (MDValueID) {
265 // Increment use count.
266 MDValues[MDValueID-1].second++;
267 return;
268 }
269 MDValues.push_back(std::make_pair(MD, 1U));
270 MDValueID = MDValues.size();
271
272 // Enumerate all non-function-local operands.
273 if (N)
274 EnumerateMDNodeOperands(N);
275 }
276
277 /// EnumerateFunctionLocalMetadataa - Incorporate function-local metadata
278 /// information reachable from the given MDNode.
279 void ValueEnumerator::EnumerateFunctionLocalMetadata(const MDNode *N) {
280 assert(N->isFunctionLocal() && N->getFunction() &&
281 "EnumerateFunctionLocalMetadata called on non-function-local mdnode!");
282
283 // Enumerate the type of this value.
284 EnumerateType(N->getType());
285
286 // Check to see if it's already in!
287 unsigned &MDValueID = MDValueMap[N];
288 if (MDValueID) {
289 // Increment use count.
290 MDValues[MDValueID-1].second++;
291 return;
292 }
293 MDValues.push_back(std::make_pair(N, 1U));
294 MDValueID = MDValues.size();
295
296 // To incoroporate function-local information visit all function-local
297 // MDNodes and all function-local values they reference.
298 for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
299 if (Value *V = N->getOperand(i)) {
300 if (MDNode *O = dyn_cast<MDNode>(V)) {
301 if (O->isFunctionLocal() && O->getFunction())
302 EnumerateFunctionLocalMetadata(O);
303 } else if (isa<Instruction>(V) || isa<Argument>(V))
304 EnumerateValue(V);
305 }
306
307 // Also, collect all function-local MDNodes for easy access.
308 FunctionLocalMDs.push_back(N);
309 }
310
311 void ValueEnumerator::EnumerateValue(const Value *V) {
312 assert(!V->getType()->isVoidTy() && "Can't insert void values!");
313 assert(!isa<MDNode>(V) && !isa<MDString>(V) &&
314 "EnumerateValue doesn't handle Metadata!");
315
316 // Check to see if it's already in!
317 unsigned &ValueID = ValueMap[V];
318 if (ValueID) {
319 // Increment use count.
320 Values[ValueID-1].second++;
321 return;
322 }
323
324 // Enumerate the type of this value.
325 EnumerateType(V->getType());
326
327 if (const Constant *C = dyn_cast<Constant>(V)) {
328 if (isa<GlobalValue>(C)) {
329 // Initializers for globals are handled explicitly elsewhere.
330 } else if (C->getNumOperands()) {
331 // If a constant has operands, enumerate them. This makes sure that if a
332 // constant has uses (for example an array of const ints), that they are
333 // inserted also.
334
335 // We prefer to enumerate them with values before we enumerate the user
336 // itself. This makes it more likely that we can avoid forward references
337 // in the reader. We know that there can be no cycles in the constants
338 // graph that don't go through a global variable.
339 for (User::const_op_iterator I = C->op_begin(), E = C->op_end();
340 I != E; ++I)
341 if (!isa<BasicBlock>(*I)) // Don't enumerate BB operand to BlockAddress.
342 EnumerateValue(*I);
343
344 // Finally, add the value. Doing this could make the ValueID reference be
345 // dangling, don't reuse it.
346 Values.push_back(std::make_pair(V, 1U));
347 ValueMap[V] = Values.size();
348 return;
349 }
350 }
351
352 // Add the value.
353 Values.push_back(std::make_pair(V, 1U));
354 ValueID = Values.size();
355 }
356
357
358 void ValueEnumerator::EnumerateType(Type *Ty) {
359 unsigned *TypeID = &TypeMap[Ty];
360
361 // We've already seen this type.
362 if (*TypeID)
363 return;
364
365 // If it is a non-anonymous struct, mark the type as being visited so that we
366 // don't recursively visit it. This is safe because we allow forward
367 // references of these in the bitcode reader.
368 if (StructType *STy = dyn_cast<StructType>(Ty))
369 if (!STy->isLiteral())
370 *TypeID = ~0U;
371
372 // Enumerate all of the subtypes before we enumerate this type. This ensures
373 // that the type will be enumerated in an order that can be directly built.
374 for (Type::subtype_iterator I = Ty->subtype_begin(), E = Ty->subtype_end();
375 I != E; ++I)
376 EnumerateType(*I);
377
378 // Refresh the TypeID pointer in case the table rehashed.
379 TypeID = &TypeMap[Ty];
380
381 // Check to see if we got the pointer another way. This can happen when
382 // enumerating recursive types that hit the base case deeper than they start.
383 //
384 // If this is actually a struct that we are treating as forward ref'able,
385 // then emit the definition now that all of its contents are available.
386 if (*TypeID && *TypeID != ~0U)
387 return;
388
389 // Add this type now that its contents are all happily enumerated.
390 Types.push_back(Ty);
391
392 *TypeID = Types.size();
393 }
394
395 // Enumerate the types for the specified value. If the value is a constant,
396 // walk through it, enumerating the types of the constant.
397 void ValueEnumerator::EnumerateOperandType(const Value *V) {
398 EnumerateType(V->getType());
399
400 if (const Constant *C = dyn_cast<Constant>(V)) {
401 // If this constant is already enumerated, ignore it, we know its type must
402 // be enumerated.
403 if (ValueMap.count(V)) return;
404
405 // This constant may have operands, make sure to enumerate the types in
406 // them.
407 for (unsigned i = 0, e = C->getNumOperands(); i != e; ++i) {
408 const Value *Op = C->getOperand(i);
409
410 // Don't enumerate basic blocks here, this happens as operands to
411 // blockaddress.
412 if (isa<BasicBlock>(Op)) continue;
413
414 EnumerateOperandType(Op);
415 }
416
417 if (const MDNode *N = dyn_cast<MDNode>(V)) {
418 for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
419 if (Value *Elem = N->getOperand(i))
420 EnumerateOperandType(Elem);
421 }
422 } else if (isa<MDString>(V) || isa<MDNode>(V))
423 EnumerateMetadata(V);
424 }
425
426 void ValueEnumerator::EnumerateAttributes(AttributeSet PAL) {
427 if (PAL.isEmpty()) return; // null is always 0.
428
429 // Do a lookup.
430 unsigned &Entry = AttributeMap[PAL];
431 if (Entry == 0) {
432 // Never saw this before, add it.
433 Attribute.push_back(PAL);
434 Entry = Attribute.size();
435 }
436
437 // Do lookups for all attribute groups.
438 for (unsigned i = 0, e = PAL.getNumSlots(); i != e; ++i) {
439 AttributeSet AS = PAL.getSlotAttributes(i);
440 unsigned &Entry = AttributeGroupMap[AS];
441 if (Entry == 0) {
442 AttributeGroups.push_back(AS);
443 Entry = AttributeGroups.size();
444 }
445 }
446 }
447
448 void ValueEnumerator::incorporateFunction(const Function &F) {
449 InstructionCount = 0;
450 NumModuleValues = Values.size();
451 NumModuleMDValues = MDValues.size();
452
453 // Adding function arguments to the value table.
454 for (Function::const_arg_iterator I = F.arg_begin(), E = F.arg_end();
455 I != E; ++I)
456 EnumerateValue(I);
457
458 FirstFuncConstantID = Values.size();
459
460 // Add all function-level constants to the value table.
461 for (Function::const_iterator BB = F.begin(), E = F.end(); BB != E; ++BB) {
462 for (BasicBlock::const_iterator I = BB->begin(), E = BB->end(); I!=E; ++I)
463 for (User::const_op_iterator OI = I->op_begin(), E = I->op_end();
464 OI != E; ++OI) {
465 if ((isa<Constant>(*OI) && !isa<GlobalValue>(*OI)) ||
466 isa<InlineAsm>(*OI))
467 EnumerateValue(*OI);
468 }
469 BasicBlocks.push_back(BB);
470 ValueMap[BB] = BasicBlocks.size();
471 }
472
473 // Optimize the constant layout.
474 OptimizeConstants(FirstFuncConstantID, Values.size());
475
476 // Add the function's parameter attributes so they are available for use in
477 // the function's instruction.
478 EnumerateAttributes(F.getAttributes());
479
480 FirstInstID = Values.size();
481
482 SmallVector<MDNode *, 8> FnLocalMDVector;
483 // Add all of the instructions.
484 for (Function::const_iterator BB = F.begin(), E = F.end(); BB != E; ++BB) {
485 for (BasicBlock::const_iterator I = BB->begin(), E = BB->end(); I!=E; ++I) {
486 for (User::const_op_iterator OI = I->op_begin(), E = I->op_end();
487 OI != E; ++OI) {
488 if (MDNode *MD = dyn_cast<MDNode>(*OI))
489 if (MD->isFunctionLocal() && MD->getFunction())
490 // Enumerate metadata after the instructions they might refer to.
491 FnLocalMDVector.push_back(MD);
492 }
493
494 SmallVector<std::pair<unsigned, MDNode*>, 8> MDs;
495 I->getAllMetadataOtherThanDebugLoc(MDs);
496 for (unsigned i = 0, e = MDs.size(); i != e; ++i) {
497 MDNode *N = MDs[i].second;
498 if (N->isFunctionLocal() && N->getFunction())
499 FnLocalMDVector.push_back(N);
500 }
501
502 if (!I->getType()->isVoidTy())
503 EnumerateValue(I);
504 }
505 }
506
507 // Add all of the function-local metadata.
508 for (unsigned i = 0, e = FnLocalMDVector.size(); i != e; ++i)
509 EnumerateFunctionLocalMetadata(FnLocalMDVector[i]);
510 }
511
512 void ValueEnumerator::purgeFunction() {
513 /// Remove purged values from the ValueMap.
514 for (unsigned i = NumModuleValues, e = Values.size(); i != e; ++i)
515 ValueMap.erase(Values[i].first);
516 for (unsigned i = NumModuleMDValues, e = MDValues.size(); i != e; ++i)
517 MDValueMap.erase(MDValues[i].first);
518 for (unsigned i = 0, e = BasicBlocks.size(); i != e; ++i)
519 ValueMap.erase(BasicBlocks[i]);
520
521 Values.resize(NumModuleValues);
522 MDValues.resize(NumModuleMDValues);
523 BasicBlocks.clear();
524 FunctionLocalMDs.clear();
525 }
526
527 static void IncorporateFunctionInfoGlobalBBIDs(const Function *F,
528 DenseMap<const BasicBlock*, unsigned> &IDMap) {
529 unsigned Counter = 0;
530 for (Function::const_iterator BB = F->begin(), E = F->end(); BB != E; ++BB)
531 IDMap[BB] = ++Counter;
532 }
533
534 /// getGlobalBasicBlockID - This returns the function-specific ID for the
535 /// specified basic block. This is relatively expensive information, so it
536 /// should only be used by rare constructs such as address-of-label.
537 unsigned ValueEnumerator::getGlobalBasicBlockID(const BasicBlock *BB) const {
538 unsigned &Idx = GlobalBasicBlockIDs[BB];
539 if (Idx != 0)
540 return Idx-1;
541
542 IncorporateFunctionInfoGlobalBBIDs(BB->getParent(), GlobalBasicBlockIDs);
543 return getGlobalBasicBlockID(BB);
544 }
545