1 #include <magic/support/SmartType.h>
2 #include <limits.h>
3 
4 using namespace llvm;
5 
6 namespace llvm {
7 
8 #define DEBUG_EQUALS        0
9 #define DEBUG_BFAS          0
10 #define DEBUG_UNIONS        0
11 int debugEquals = 0;
12 
13 //===----------------------------------------------------------------------===//
14 // Constructors, destructor, and operators
15 //===----------------------------------------------------------------------===//
16 SmartType::SmartType(const SmartType& et) {
17     cloneFrom(et);
18 }
19 
20 SmartType::SmartType(TYPECONST Type *type, const DIType *aDIType, bool useExceptions, bool forceRawTypeRepresentation) {
21     EDIType tmp(*aDIType);
22     init(type, &tmp, useExceptions, forceRawTypeRepresentation);
23     normalize();
24 }
25 
26 SmartType::SmartType(TYPECONST Type *type, const EDIType *aEDIType, bool useExceptions, bool forceRawTypeRepresentation) {
27     init(type, aEDIType, useExceptions, forceRawTypeRepresentation);
28     normalize();
29 }
30 
31 SmartType::~SmartType() {
32     if(hasExplicitContainedEDITypes) {
33         for(unsigned i=0;i<explicitContainedEDITypes.size();i++) {
34             const EDIType* aEDIType = explicitContainedEDITypes[i];
35             delete aEDIType;
36         }
37     }
38 }
39 
40 SmartType& SmartType::operator=(const SmartType& et) {
41     if (this != &et) {
42         cloneFrom(et);
43     }
44     return *this;
45 }
46 
47 void SmartType::cloneFrom(const SmartType& et) {
48     init(et.type, &et.aEDIType, et.useExceptions, false);
49     if(et.hasExplicitContainedEDITypes) {
50         hasExplicitContainedEDITypes = true;
51         for(unsigned i=0;i<et.explicitContainedEDITypes.size();i++) {
52             const EDIType* aEDIType = et.explicitContainedEDITypes[i];
53             explicitContainedEDITypes.push_back(new EDIType(*aEDIType));
54         }
55     }
56     isInconsistent = et.isInconsistent;
57     rawTypeRepresentation = et.rawTypeRepresentation;
58     bfas = et.bfas;
59 }
60 
61 //===----------------------------------------------------------------------===//
62 // Getters
63 //===----------------------------------------------------------------------===//
64 
65 const std::string SmartType::getDescription() const {
66     return TypeUtil::getDescription(type, &aEDIType);
67 }
68 
69 const SmartType* SmartType::getContainedType(unsigned i) const {
70     assert(!rawTypeRepresentation);
71     bool hasBitFields = false;
72     TYPECONST Type *subType = type->getContainedType(i);
73     const SmartType* retSmartType = NULL;
74     if(hasExplicitContainedEDITypes) {
75         const EDIType subEDIType(*(explicitContainedEDITypes[i]));
76         retSmartType = new SmartType(subType, &subEDIType, useExceptions);
77     }
78     else {
79         if(aEDIType.isUnionTy()) {
80             assert(i == 0);
81             i = unionMemberIdx;
82         }
83         else if(bfas.size() > 0) {
84             i = getBFAFreeIdx(i, bfas);
85             hasBitFields = true;
86         }
87         const EDIType subEDIType(aEDIType.getContainedType(i));
88         retSmartType = new SmartType(subType, &subEDIType, useExceptions, hasBitFields && subEDIType.isIntegerTy() && subType->isArrayTy());
89     }
90     return retSmartType;
91 }
92 
93 unsigned SmartType::getNumContainedTypes() const {
94     if(rawTypeRepresentation || aEDIType.isComplexFloatingPointTy() || isOpaqueTy()) {
95         return 0;
96     }
97     unsigned numContainedTypes = type->getNumContainedTypes();
98     unsigned numContainedEDITypes;
99     if(hasExplicitContainedEDITypes) {
100         numContainedEDITypes = explicitContainedEDITypes.size();
101     }
102     else {
103         if(aEDIType.isUnionTy()) {
104             numContainedEDITypes = 1;
105         }
106         else {
107             numContainedEDITypes = aEDIType.getNumContainedTypes();
108             if(bfas.size() > 0) {
109                 for(unsigned i=0;i<bfas.size();i++) {
110                     numContainedEDITypes -= (bfas[i].getSize() - 1);
111                 }
112             }
113         }
114     }
115     if(numContainedTypes == numContainedEDITypes+1 && isPaddedTy()) {
116         numContainedTypes--;
117     }
118     if(numContainedTypes != numContainedEDITypes) {
119         if(isArrayTy() && TypeUtil::isArrayAsStructTy(type)) {
120             numContainedTypes = 1;
121         }
122     }
123     SmartType_assert(numContainedTypes == numContainedEDITypes);
124     return numContainedTypes;
125 }
126 
127 const DIDerivedType& SmartType::getMember(unsigned i) const {
128     assert(!rawTypeRepresentation);
129     if(bfas.size() > 0) {
130         i = getBFAFreeIdx(i, bfas);
131     }
132     return aEDIType.getMember(i);
133 }
134 
135 unsigned SmartType::getUnionMemberIdx() const {
136     assert(!rawTypeRepresentation);
137     SmartType_assert(isTy(type->isStructTy(), aEDIType.isUnionTy(), "getUnionMemberIdx"));
138     SmartType_assert(getNumContainedTypes() == 1);
139     TYPECONST Type* uMemberType = type->getContainedType(0);
140     unsigned numSubEDITypes = aEDIType.getNumContainedTypes();
141     std::vector<unsigned> indexes;
142     int maxWeakConsistencyLevel = -1;
143     unsigned maxWeakConsistencyIndex = -1;
144     int maxWeakConsistencyLevelEntries;
145     unsigned index;
146     for(unsigned i=0;i<numSubEDITypes;i++) {
147         int weakConsistencyLevel;
148         EDIType subEDIType = aEDIType.getContainedType(i);
149         if(isTypeConsistent(uMemberType, &subEDIType, true, &weakConsistencyLevel)) {
150             indexes.push_back(i);
151             if(weakConsistencyLevel > maxWeakConsistencyLevel) {
152                 maxWeakConsistencyLevel = weakConsistencyLevel;
153                 maxWeakConsistencyIndex = i;
154                 maxWeakConsistencyLevelEntries = 1;
155             }
156             else if(weakConsistencyLevel == maxWeakConsistencyLevel) {
157                 maxWeakConsistencyLevelEntries++;
158             }
159         }
160     }
161     if(indexes.size() == 0) {
162         //try to match names if we failed before
163         std::string name = EDIType::lookupUnionMemberName(type);
164         if(name.compare("")) {
165             for(unsigned i=0;i<numSubEDITypes;i++) {
166                 EDIType subEDIType = aEDIType.getContainedType(i);
167                 if(!subEDIType.getName().compare(name)) {
168                     indexes.push_back(i);
169                     maxWeakConsistencyIndex = i;
170                 }
171             }
172         }
173     }
174     if(indexes.size() == 0) {
175         //No valid union member found
176 #if DEBUG_UNIONS
177         SmartTypeErr("getUnionMemberIdx: resorting to a raw type. No valid union member found for: " << getDescription());
178 #endif
179         return UINT_MAX;
180     }
181     index = maxWeakConsistencyIndex;
182     if(indexes.size() > 1) {
183         SmartTypeLog("getUnionMemberIdx: warning: multiple valid union members found, automatically selecting the first most-consistent member:");
184         SmartTypeLog(" - target member type is: " << TypeUtil::getDescription(uMemberType));
185         SmartTypeLog(" - selected index is: " << index);
186         for(unsigned i=0;i<indexes.size();i++) {
187             EDIType subEDIType = aEDIType.getContainedType(indexes[i]);
188             SmartTypeLog(" - " << indexes[i] << ". " << TypeUtil::getDescription(&subEDIType));
189         }
190     }
191 
192     return index;
193 }
194 
195 const SmartType* SmartType::getTopStructType(unsigned index) const {
196     TYPECONST Type *topType = TypeUtil::lookupTopStructType(type, index);
197     const EDIType *topEDIType = aEDIType.getTopStructType(index);
198     assert((topType && topEDIType) || (!topType && !topEDIType));
199     if(topType) {
200         const SmartType* retSmartType = new SmartType(topType, topEDIType);
201         return retSmartType;
202     }
203     return NULL;
204 }
205 
206 //===----------------------------------------------------------------------===//
207 // Other public methods
208 //===----------------------------------------------------------------------===//
209 
210 void SmartType::verify() const {
211     SmartType_assert(isTypeConsistent());
212 }
213 
214 void SmartType::print(raw_ostream &OS) const {
215      OS << getDescription();
216 }
217 
218 bool SmartType::equals(const SmartType* other, bool isDebug) const {
219     static std::set<std::pair<MDNode*, MDNode*> > compatibleMDNodes;
220     static std::set<std::pair<MDNode*, MDNode*> >::iterator compatibleMDNodesIt;
221 #if DEBUG_EQUALS
222     if(debugEquals) SmartTypeErr("COMPARING :" << getDescription() << " VS " << other->getDescription());
223 #endif
224     if(type != other->getType()) {
225 #if DEBUG_EQUALS
226         if(debugEquals) SmartTypeErr("----> false1");
227 #endif
228         return false;
229     }
230     if(isOpaqueTy() || other->isOpaqueTy()) {
231         return isOpaqueTy() && other->isOpaqueTy();
232     }
233     if(aEDIType.getTag() != other->getEDIType()->getTag()) {
234 #if DEBUG_EQUALS
235         if(debugEquals) SmartTypeErr("----> false1b");
236 #endif
237         return false;
238     }
239     if(isFunctionTy() && (!isTypeConsistent() || !other->isTypeConsistent())) {
240         //we just compare the types for inconsistent functions types
241         return true;
242     }
243     if(hasRawTypeRepresentation() || other->hasRawTypeRepresentation()) {
244         return !aEDIType.getNamesString().compare(other->getEDIType()->getNamesString());
245     }
246     unsigned numContainedTypes = getNumContainedTypes();
247     unsigned otherNumContainedTypes = other->getNumContainedTypes();
248     if(numContainedTypes != otherNumContainedTypes) {
249 #if DEBUG_EQUALS
250         if(debugEquals) SmartTypeErr("----> false2");
251 #endif
252         return false;
253     }
254     unsigned numElements = aEDIType.getNumElements();
255     unsigned otherNumElements = other->getEDIType()->getNumElements();
256     if(numElements != otherNumElements) {
257 #if DEBUG_EQUALS
258         if(debugEquals) SmartTypeErr("----> false2b");
259 #endif
260         return false;
261     }
262     std::string name = aEDIType.getName();
263     std::string otherName = other->getEDIType()->getName();
264     if(name.compare(otherName)) {
265 #if DEBUG_EQUALS
266         if(debugEquals) SmartTypeErr("----> false3: " <<  name <<  " vs " <<  otherName);
267 #endif
268         return false;
269     }
270     if(aEDIType.getNames().size() > 1 || other->getEDIType()->getNames().size() > 1) {
271         std::string namesString = aEDIType.getNamesString();
272         std::string otherNamesString = other->getEDIType()->getNamesString();
273         if(namesString.compare(otherNamesString)) {
274 #if DEBUG_EQUALS
275             if(debugEquals) SmartTypeErr("----> false4: " <<  namesString <<  " vs " <<  otherNamesString);
276 #endif
277             return false;
278         }
279     }
280     if(numContainedTypes == 0) {
281 #if DEBUG_EQUALS
282         if(debugEquals) SmartTypeErr("----> true4");
283 #endif
284         return true;
285     }
286     MDNode *node = *(aEDIType.getDIType());
287     MDNode *otherNode = *(other->getEDIType()->getDIType());
288     if(node == otherNode) {
289         return true;
290     }
291     for(unsigned i=0;i<SmartType::equalsNestedTypes.size();i++) {
292         if(type == SmartType::equalsNestedTypes[i]) {
293 #if DEBUG_EQUALS
294             if(debugEquals) SmartTypeErr("----> true5");
295 #endif
296             return true;
297         }
298     }
299     //before digging the type tree, see if we have these 2 metadata nodes in cache
300     //this gives us an impressive speedup
301     MDNode *minNode = node < otherNode ? node : otherNode;
302     MDNode *maxNode = node < otherNode ? otherNode : node;
303     compatibleMDNodesIt = compatibleMDNodes.find(std::pair<MDNode*, MDNode*>(minNode, maxNode));
304     if(compatibleMDNodesIt != compatibleMDNodes.end()) {
305         return true;
306     }
307     SmartType::equalsNestedTypes.push_back(type);
308     const SmartType* containedType = NULL;
309     const SmartType* otherContainedType = NULL;
310     bool sameContainedTypes = true;
311     for(unsigned i=0;i<numContainedTypes;i++) {
312         containedType = getContainedType(i);
313         otherContainedType = other->getContainedType(i);
314         sameContainedTypes = containedType->equals(otherContainedType);
315         delete containedType;
316         delete otherContainedType;
317         if(!sameContainedTypes) {
318             break;
319         }
320     }
321     SmartType::equalsNestedTypes.pop_back();
322     if(!sameContainedTypes) {
323 #if DEBUG_EQUALS
324         if(debugEquals) SmartTypeErr("----> false6");
325 #endif
326         return false;
327     }
328 #if DEBUG_EQUALS
329     if(debugEquals) SmartTypeErr("----> true7");
330 #endif
331     compatibleMDNodes.insert(std::pair<MDNode*, MDNode*>(minNode, maxNode));
332     return true;
333 }
334 
335 //===----------------------------------------------------------------------===//
336 // Public static methods
337 //===----------------------------------------------------------------------===//
338 
339 const SmartType* SmartType::getSmartTypeFromGV(Module &M, GlobalVariable *GV, DIGlobalVariable *DIG) {
340     //ignore anonymous strings
341     if(GV->getName().startswith(".str")) {
342         return NULL;
343     }
344     Value *DIGV = Backports::findDbgGlobalDeclare(GV);
345     if (!DIGV) {
346         return NULL;
347     }
348     DIGlobalVariable Var(cast<MDNode>(DIGV));
349     DIType aDIType = Var.getType();
350     const SmartType* retSmartType = new SmartType(GV->getType()->getElementType(), &aDIType);
351     if(DIG) {
352         *DIG = Var;
353     }
354     return retSmartType;
355 }
356 
357 const SmartType* SmartType::getSmartTypeFromLV(Module &M, AllocaInst *AI, DIVariable *DIV) {
358     const DbgDeclareInst *DDI = Backports::FindAllocaDbgDeclare(AI);
359     if (!DDI) {
360         return NULL;
361     }
362     if(DDI == (const DbgDeclareInst *) -1) {
363         return (const SmartType*)-1;
364     }
365     DIVariable Var(cast<MDNode>(DDI->getVariable()));
366     DIType aDIType = Var.getType();
367     if(DIV) {
368         *DIV = Var;
369     }
370     const SmartType* aSmartType = new SmartType(AI->getAllocatedType(), &aDIType);
371     return aSmartType;
372 }
373 
374 const SmartType* SmartType::getSmartTypeFromFunction(Module &M, Function *F, DISubprogram *DIS) {
375     Value *DIF = Backports::findDbgSubprogramDeclare(F);
376     if (!DIF) {
377         return NULL;
378     }
379     DISubprogram Sub(cast<MDNode>(DIF));
380     DIType aDIType = Sub.getType();
381     const SmartType* retSmartType = new SmartType(F->getType()->getElementType(), &aDIType);
382     if(DIS) {
383         *DIS = Sub;
384     }
385     return retSmartType;
386 }
387 
388 const SmartType* SmartType::getStructSmartTypeByName(Module &M, GlobalVariable* GV, std::string &name, bool isUnion) {
389     std::string structName((isUnion ? "union." : "struct.") + name);
390 
391     TYPECONST Type *targetType = M.getTypeByName(structName);
392     const EDIType *targetEDIType = EDIType::getStructEDITypeByName(name);
393 
394     const SmartType *retSmartType = NULL;
395     if(targetType && targetEDIType) {
396         retSmartType = new SmartType(targetType, targetEDIType);
397     }
398     return retSmartType;
399 }
400 
401 std::vector<const SmartType*>* SmartType::getTopStructSmartTypes(Module &M, GlobalVariable* GV) {
402     std::vector<std::string> names;
403     std::vector<unsigned> flags;
404     TypeUtil::parseTopStructTypes(M, GV->getType()->getElementType(), &names, &flags);
405     std::vector<const SmartType*> *vector = new std::vector<const SmartType*>;
406     for(unsigned i=0;i<names.size();i++) {
407         std::string entryName = names[i];
408         unsigned entryFlags = flags[i];
409         const SmartType *aSmartType = NULL;
410         if(!(entryFlags & TypeUtil::TYPE_ANONYMOUS) && !(entryFlags & TypeUtil::TYPE_UNNAMED)) {
411             aSmartType = getStructSmartTypeByName(M, GV, entryName, (entryFlags & TypeUtil::TYPE_UNION));
412         }
413         if(aSmartType == NULL) {
414             //this method can fail due to name clashing but is the only one possible for anonymous or unnamed struct types
415             const SmartType *GVSmartType = getSmartTypeFromGV(M, GV);
416             assert(GVSmartType && "Unable to find a match for anonymous or unnamed struct type");
417             aSmartType = GVSmartType->getTopStructType(i);
418             delete GVSmartType;
419             assert(aSmartType != NULL);
420         }
421         vector->push_back(aSmartType);
422     }
423 
424     return vector;
425 }
426 
427 //===----------------------------------------------------------------------===//
428 // Private methods
429 //===----------------------------------------------------------------------===//
430 
431 void SmartType::init(TYPECONST Type *type, const EDIType *aEDIType, bool useExceptions, bool forceRawTypeRepresentation) {
432     this->type = type;
433     this->aEDIType = *aEDIType;
434     this->useExceptions = useExceptions;
435     hasExplicitContainedEDITypes = false;
436     isInconsistent = false;
437     rawTypeRepresentation = false;
438     unionMemberIdx = 0;
439     if(aEDIType->isUnionTy()) {
440         if(forceRawUnions) {
441             rawTypeRepresentation = true;
442         }
443         else {
444             unionMemberIdx = getUnionMemberIdx();
445             if(unionMemberIdx == UINT_MAX) {
446                 rawTypeRepresentation = true;
447                 unionMemberIdx = 0;
448             }
449         }
450     }
451     else if(forceRawTypeRepresentation || (forceRawBitfields && BitFieldAggregation::hasBitFields(type, &(this->aEDIType)))) {
452         rawTypeRepresentation = true;
453     }
454 }
455 
456 void SmartType::normalize() {
457     if(isFunctionTy() && !hasExplicitContainedEDITypes) {
458         flattenFunctionTy();
459         hasExplicitContainedEDITypes = true;
460     }
461     if(!hasExplicitContainedEDITypes && !rawTypeRepresentation) {
462         if(!BitFieldAggregation::getBitFieldAggregations(type, &aEDIType, bfas, true)) {
463             //failed to determine bfas
464 #if DEBUG_BFAS
465             SmartTypeErr("normalize: resorting to a raw type. Cannot determine bfas for: " << getDescription());
466 #endif
467             rawTypeRepresentation = true;
468         }
469     }
470 }
471 
472 void SmartType::flattenFunctionTy() {
473     SmartType_assert(isFunctionTy() && !hasExplicitContainedEDITypes);
474     SmartType_assert(explicitContainedEDITypes.size() == 0);
475 #if MAGIC_FLATTEN_FUNCTION_ARGS
476     int ret = flattenFunctionArgs(type, &aEDIType, 0);
477     if(ret < 0 || explicitContainedEDITypes.size() != type->getNumContainedTypes()) {
478         SmartTypeLog("Warning: function flattening produced an inconsistent type!");
479         isInconsistent = true;
480     }
481 #else
482     isInconsistent = true;
483 #endif
484 }
485 
486 int SmartType::flattenFunctionArgs(TYPECONST Type *type, const EDIType *aEDIType, unsigned nextContainedType) {
487     unsigned containedTypes = type->getNumContainedTypes();
488     unsigned containedEDITypes = aEDIType->isUnionTy() ? 1 : aEDIType->getNumContainedTypes();
489     unsigned containedEDIOptions = aEDIType->isUnionTy() ? aEDIType->getNumContainedTypes() : 1;
490     int ret;
491 
492     unsigned nextContainedEDIType = 0;
493     while(nextContainedEDIType < containedEDITypes) {
494         SmartType_assert(nextContainedType < containedTypes);
495         TYPECONST Type *containedType = type->getContainedType(nextContainedType);
496         unsigned currExplicitEDITypes = explicitContainedEDITypes.size();
497         unsigned i;
498         for(i=nextContainedEDIType;i<nextContainedEDIType+containedEDIOptions;i++) {
499             const EDIType containedEDIType = aEDIType->getContainedType(i);
500             if(isTypeConsistent(containedType, &containedEDIType)) {
501                 explicitContainedEDITypes.push_back(new EDIType(containedEDIType));
502                 break;
503             }
504             if(!containedEDIType.isAggregateType()) {
505                 continue;
506             }
507             ret = flattenFunctionArgs(type, &containedEDIType, nextContainedType);
508             if(ret == 0) {
509                 break;
510             }
511         }
512         if(i >= nextContainedEDIType+containedEDIOptions) {
513             while(explicitContainedEDITypes.size() > currExplicitEDITypes) {
514                 EDIType* aEDIType = explicitContainedEDITypes[explicitContainedEDITypes.size()-1];
515                 explicitContainedEDITypes.pop_back();
516                 delete aEDIType;
517             }
518             return -1;
519         }
520         nextContainedType += (explicitContainedEDITypes.size() - currExplicitEDITypes);
521         nextContainedEDIType++;
522     }
523     return 0;
524 }
525 
526 bool SmartType::isTy(bool isTyType, bool isTyEDIType, const char* source) const {
527     bool check = (isTyType && isTyEDIType) || (!isTyType && !isTyEDIType);
528     if(!check) {
529         SmartTypeErr(source << " failed");
530     }
531     SmartType_assert(check);
532     return isTyType;
533 }
534 
535 //===----------------------------------------------------------------------===//
536 // Private static methods
537 //===----------------------------------------------------------------------===//
538 unsigned SmartType::getBFAFreeIdx(unsigned i, const std::vector<BitFieldAggregation> &inputBfas) {
539     for(unsigned j=0;j<inputBfas.size();j++) {
540         if(i<inputBfas[j].getEDITypeIndex()) {
541             break;
542         }
543         else if(i>inputBfas[j].getEDITypeIndex()) {
544             i += (inputBfas[j].getSize() - 1);
545         }
546         else {
547             i = inputBfas[j].getRepresentativeEDITypeIndex();
548             break;
549         }
550     }
551     return i;
552 }
553 
554 bool SmartType::isRawTypeConsistent(TYPECONST Type *type, const EDIType *aEDIType) {
555     if(aEDIType->isVoidTy()) {
556         return type->isVoidTy() || (type->isIntegerTy() && ((IntegerType*)type)->getBitWidth() == 8);
557     }
558     if(type->isFloatingPointTy()) {
559         return aEDIType->isFloatingPointTy();
560     }
561     if(type->isIntegerTy()) {
562         if(aEDIType->isCharTy() || aEDIType->isBoolTy()) {
563             return (((IntegerType*)type)->getBitWidth() <= 8);
564         }
565         return aEDIType->isIntegerTy() || aEDIType->isEnumTy();
566     }
567     if(type->isFunctionTy()) {
568         return aEDIType->isFunctionTy();
569     }
570     if(TypeUtil::isOpaqueTy(type)) {
571         return (aEDIType->isOpaqueTy());
572     }
573     return false;
574 }
575 
576 bool SmartType::isTypeConsistent2(std::vector<TYPECONST Type*> &nestedTypes, std::vector<const EDIType*> &nestedEDITypes, const SmartType *aSmartType) {
577     assert(aSmartType->isUseExceptions());
578     TYPECONST Type *type = aSmartType->getType();
579     const EDIType *aEDIType = aSmartType->getEDIType();
580     if(aEDIType->isPointerTy() || aEDIType->isUnionOrStructTy()) {
581         for(unsigned j=0;j<nestedTypes.size();j++) {
582             if(nestedTypes[j] == type && nestedEDITypes[j]->equals(aEDIType)) {
583                 return true;
584             }
585         }
586     }
587 
588     unsigned nTypes = type->getNumContainedTypes();
589     unsigned nEDITypes = aEDIType->getNumContainedTypes();
590     if(nTypes == 0 || nEDITypes == 0) {
591         if(nTypes != 0 || nEDITypes != 0) {
592             return false;
593         }
594         return isRawTypeConsistent(type, aEDIType);
595     }
596     if(!aSmartType->verifyTy()) {
597         return false;
598     }
599     unsigned numContainedTypes = aSmartType->getNumContainedTypes();
600     nestedTypes.push_back(type);
601     nestedEDITypes.push_back(aEDIType);
602     for(unsigned i=0;i<numContainedTypes;i++) {
603         const SmartType *containedSmartType = aSmartType->getContainedType(i);
604         assert(containedSmartType->isUseExceptions());
605         SmartType clonedSmartType(*containedSmartType);
606         assert(clonedSmartType.isUseExceptions());
607         delete containedSmartType;
608         if(!isTypeConsistent2(nestedTypes, nestedEDITypes, &clonedSmartType)) {
609             return false;
610         }
611     }
612     nestedTypes.pop_back();
613     nestedEDITypes.pop_back();
614     return true;
615 }
616 
617 bool SmartType::isTypeConsistent2(TYPECONST Type *type, const EDIType *aEDIType) {
618     /* Exception-handling based isTypeConsistent(). Broken with -fno-exceptions. */
619     static std::vector<TYPECONST Type*> nestedTypes;
620     static std::vector<const EDIType*> nestedEDITypes;
621     static unsigned level = 0;
622 
623     if(level == 0) {
624         nestedTypes.clear();
625         nestedEDITypes.clear();
626     }
627 
628     bool checkTypeConsistent = false;
629     bool useExceptions = true;
630     level++;
631     assert(useExceptions);
632     TRY(
633         const SmartType aSmartType(type, aEDIType, useExceptions);
634         checkTypeConsistent = isTypeConsistent2(nestedTypes, nestedEDITypes, &aSmartType);
635     )
636     CATCH(std::exception& e,
637         checkTypeConsistent = false;
638     )
639     level--;
640     return checkTypeConsistent;
641 }
642 
643 bool SmartType::isTypeConsistent(TYPECONST Type *type, const EDIType *aEDIType, bool useBfas, int *weakConsistencyLevel) {
644     static std::vector<TYPECONST Type*> nestedTypes;
645     static std::vector<const EDIType*> nestedEDITypes;
646     static unsigned level = 0;
647 
648     if(level == 0) {
649         if(weakConsistencyLevel) {
650             *weakConsistencyLevel = INT_MAX;
651         }
652     }
653 
654     if(aEDIType->isPointerTy() || aEDIType->isUnionOrStructTy()) {
655         for(unsigned j=0;j<nestedTypes.size();j++) {
656             if(nestedTypes[j] == type && nestedEDITypes[j]->equals(aEDIType)) {
657                 return true;
658             }
659         }
660     }
661 
662     unsigned nTypes = type->getNumContainedTypes();
663     unsigned nEDITypes = aEDIType->getNumContainedTypes();
664     if(nTypes == 0 || nEDITypes == 0) {
665         if(nTypes != 0 || nEDITypes != 0) {
666             return false;
667         }
668         return isRawTypeConsistent(type, aEDIType);
669     }
670 
671     if(aEDIType->isOpaqueTy()) {
672         return (TypeUtil::isOpaqueTy(type));
673     }
674 
675     bool isArrayOrVectorTy = aEDIType->isArrayTy() || aEDIType->isVectorTy();
676     unsigned nEDINumElements = aEDIType->getNumElements();
677     if(aEDIType->isDerivedType() || isArrayOrVectorTy) {
678         TYPECONST Type *nextType = type;
679         if(aEDIType->isPointerTy()) {
680             if(!type->isPointerTy()) {
681                 return false;
682             }
683             nextType = type->getContainedType(0);
684         }
685         else if(aEDIType->isArrayTy()) {
686             if(!type->isArrayTy() || ((ArrayType*)type)->getNumElements() != nEDINumElements) {
687                 return false;
688             }
689             nextType = type->getContainedType(0);
690         }
691         else if(aEDIType->isVectorTy()) {
692             if(!type->isVectorTy() || ((VectorType*)type)->getNumElements() != nEDINumElements) {
693                 return false;
694             }
695             nextType = type->getContainedType(0);
696         }
697         const EDIType aEDISubType(aEDIType->getContainedType(0));
698         nestedEDITypes.push_back(aEDIType);
699         nestedTypes.push_back(type);
700         level++;
701         bool ret = isTypeConsistent(nextType, &aEDISubType, useBfas, weakConsistencyLevel);
702         level--;
703         nestedTypes.pop_back();
704         nestedEDITypes.pop_back();
705         return ret;
706     }
707     else if(aEDIType->isCompositeType()) {
708         if(!aEDIType->isUnionOrStructTy() && !aEDIType->isVectorTy() && !aEDIType->isFunctionTy()) {
709             return false;
710         }
711         if(aEDIType->isUnionOrStructTy() && !type->isStructTy()) {
712             return false;
713         }
714         if(aEDIType->isVectorTy() && !type->isVectorTy()) {
715             return false;
716         }
717         if(aEDIType->isFunctionTy() && !type->isFunctionTy()) {
718             return false;
719         }
720         if(aEDIType->isUnionTy() || aEDIType->isFunctionTy()) {
721             if(weakConsistencyLevel) {
722                 *weakConsistencyLevel = level;
723             }
724             return true; //xxx we should be less conservative here
725         }
726         unsigned numContainedEDITypes = aEDIType->getNumContainedTypes();
727         std::vector<BitFieldAggregation> myBfas;
728         if(numContainedEDITypes != type->getNumContainedTypes()) {
729             if(!useBfas) {
730                 return false;
731             }
732             if(!BitFieldAggregation::getBitFieldAggregations(type, aEDIType, myBfas, true)) {
733                 return false;
734             }
735             for(unsigned i=0;i<myBfas.size();i++) {
736                 numContainedEDITypes -= (myBfas[i].getSize() - 1);
737             }
738             if(numContainedEDITypes != type->getNumContainedTypes()) {
739                 return false;
740             }
741             nestedEDITypes.push_back(aEDIType);
742             nestedTypes.push_back(type);
743             level++;
744             for(unsigned i=0;i<numContainedEDITypes;i++) {
745                 const EDIType aEDISubType(aEDIType->getContainedType(getBFAFreeIdx(i, myBfas)));
746                 if(!isTypeConsistent(type->getContainedType(i), &aEDISubType, useBfas, weakConsistencyLevel)) {
747                     level--;
748                     nestedTypes.pop_back();
749                     nestedEDITypes.pop_back();
750                     return false;
751                 }
752             }
753             level--;
754             nestedTypes.pop_back();
755             nestedEDITypes.pop_back();
756             return true;
757         }
758         nestedEDITypes.push_back(aEDIType);
759         nestedTypes.push_back(type);
760         level++;
761         for(unsigned i=0;i<numContainedEDITypes;i++) {
762             const EDIType aEDISubType(aEDIType->getContainedType(i));
763             if(!isTypeConsistent(type->getContainedType(i), &aEDISubType, useBfas, weakConsistencyLevel)) {
764                 level--;
765                 nestedTypes.pop_back();
766                 nestedEDITypes.pop_back();
767                 return false;
768             }
769         }
770         level--;
771         nestedTypes.pop_back();
772         nestedEDITypes.pop_back();
773         return true;
774     }
775     return false;
776 }
777 
778 std::vector<TYPECONST Type*> SmartType::equalsNestedTypes;
779 
780 }
781