1 
2 #include <magic/support/EDIType.h>
3 
4 using namespace llvm;
5 
6 namespace llvm {
7 
8 #define DEBUG_EDI_EQUALS        0
9 int debugEDIEquals = 0;
10 
11 //===----------------------------------------------------------------------===//
12 // Constructors, destructor, and operators
13 //===----------------------------------------------------------------------===//
14 
EDIType(const MDNode * N,bool norm,bool checkOpaqueTypes)15 EDIType::EDIType(const MDNode *N, bool norm, bool checkOpaqueTypes) : aDIType(N) {
16     init(norm, checkOpaqueTypes);
17 }
18 
EDIType(bool norm,bool checkOpaqueTypes)19 EDIType::EDIType(bool norm, bool checkOpaqueTypes) : aDIType() {
20     init(norm, checkOpaqueTypes);
21 }
22 
EDIType(const DIType aDIType,bool norm,bool checkOpaqueTypes)23 EDIType::EDIType(const DIType aDIType, bool norm, bool checkOpaqueTypes) : aDIType(aDIType) {
24     init(norm, checkOpaqueTypes);
25 }
26 
operator ==(const EDIType & aEDIType) const27 bool EDIType::operator == (const EDIType& aEDIType) const {
28     const DIType oDIType = *(aEDIType.getDIType());
29     return (aDIType == oDIType);
30 }
31 
32 //===----------------------------------------------------------------------===//
33 // Getters
34 //===----------------------------------------------------------------------===//
35 
getDescription(int skipUnions,int skipStructs,int allowMultiNames) const36 const std::string EDIType::getDescription(int skipUnions, int skipStructs, int allowMultiNames) const {
37     std::string string;
38     raw_string_ostream ostream(string);
39     printDescription(ostream, skipUnions, skipStructs, allowMultiNames);
40     ostream.flush();
41     return string;
42 }
43 
getContainedType(unsigned i,bool norm) const44 const EDIType& EDIType::getContainedType(unsigned i, bool norm) const {
45     static EDIType subType;
46     EDIType_assert(!isBasicType() && !isVoidTy() && !isEnumTy());
47     bool isArrayOrVectorTy = isArrayTy() || isVectorTy();
48     if(isDerivedType() || isArrayOrVectorTy) {
49         EDIType_assert(i == 0);
50         if(isArrayOrVectorTy && getCurrentDimension() < getNumDimensions()-1) {
51             subType = *this;
52             subType.setCurrentDimension(getCurrentDimension() + 1);
53         }
54         else {
55             subType = getTypeDerivedFrom();
56         }
57         return subType;
58     }
59     if (isFunctionTy()) {
60         DITypeArray DTA = ((const DISubroutineType)aDIType).getTypeArray();
61         subType = PassUtil::getDITypeFromRef(DTA.getElement(i));
62     } else {
63         DIArray aDIArray = getTypeArray();
64         unsigned numContainedTypes = aDIArray.getNumElements();
65         assert(i < numContainedTypes);
66         EDIType tmpType((const DIType) aDIArray.getElement(i), norm);
67         subType = tmpType;
68     }
69     return subType;
70 }
71 
getNumContainedTypes() const72 unsigned EDIType::getNumContainedTypes() const {
73     if(isBasicType() || isVoidTy() || isEnumTy()) {
74         return 0;
75     }
76     bool isArrayOrVectorTy = isArrayTy() || isVectorTy();
77     if(isDerivedType() || isArrayOrVectorTy) {
78         return 1;
79     }
80     return getTypeArrayNum();
81 }
82 
getMember(unsigned i) const83 const DIDerivedType& EDIType::getMember(unsigned i) const {
84     static DIDerivedType aDIDerivedType;
85     EDIType_assert(isUnionOrStructTy());
86     DIArray aDIArray = getTypeArray();
87     DIDescriptor aDIDescriptor = aDIArray.getElement(i);
88     assert(aDIDescriptor.getTag() == dwarf::DW_TAG_member);
89     aDIDerivedType = (DIDerivedType) aDIDescriptor;
90     return aDIDerivedType;
91 }
92 
isUnionOrStructTy(bool isStruct,bool isUnion) const93 bool EDIType::isUnionOrStructTy(bool isStruct, bool isUnion) const {
94     if(isOpaqueTy()) {
95         return false;
96     }
97     if((isStruct && getTag() == dwarf::DW_TAG_structure_type) ||
98         (isUnion && getTag() == dwarf::DW_TAG_union_type)) {
99         EDIType_assert(isCompositeType());
100         return true;
101     }
102     return false;
103 }
104 
hasInnerPointers() const105 bool EDIType::hasInnerPointers() const {
106     if(isOpaqueTy() || isFunctionTy()) {
107         return false;
108     }
109     if(isPointerTy()) {
110         return true;
111     }
112 
113     unsigned numContainedTypes = getNumContainedTypes();
114     if(numContainedTypes == 0) {
115         return false;
116     }
117     else if(isArrayTy() || isVectorTy()) {
118         const EDIType subType = getContainedType(0);
119         return subType.hasInnerPointers();
120     }
121     else {
122         assert(isUnionOrStructTy());
123         for(unsigned i=0;i<numContainedTypes;i++) {
124             const EDIType subType = getContainedType(i);
125             if(subType.hasInnerPointers()) {
126                 return true;
127             }
128         }
129    }
130 
131    return false;
132 }
133 
getTypeArrayNum() const134 unsigned int EDIType::getTypeArrayNum() const {
135     EDIType_assert(isCompositeType());
136     /* This function is used from isOpaqueTy(), so do not use isFunctionTy() here. */
137     if (getTag() == dwarf::DW_TAG_subroutine_type) {
138         DITypeArray DTA = ((const DISubroutineType)aDIType).getTypeArray();
139         return DTA.getNumElements();
140     } else {
141         return getTypeArray().getNumElements();
142     }
143 }
144 
getTypeArray() const145 DIArray EDIType::getTypeArray() const {
146     static std::set<std::string> nonOpaqueEmptyTypes;
147     static std::set<std::string>::iterator nonOpaqueEmptyTypesIt;
148     EDIType_assert(isCompositeType());
149     EDIType_assert(getTag() != dwarf::DW_TAG_subroutine_type); /* as above, no isFunctionTy() */
150     DIArray aDIArray = ((const DICompositeType)aDIType).getElements();
151     if(aDIArray.getNumElements() == 0 && checkOpaqueTypes && myNames.size() > 0) {
152         const EDIType *aType = NULL;
153         std::string name;
154         for(int i=myNames.size()-1;i>=0;i--) {
155             name = myNames[i];
156             aType = getStructEDITypeByName(name);
157             if(aType) {
158                 break;
159             }
160         }
161         if(aType) {
162             aDIArray = ((const DICompositeType *)aType->getDIType())->getElements();
163             nonOpaqueEmptyTypesIt = nonOpaqueEmptyTypes.find(name);
164             if(nonOpaqueEmptyTypesIt == nonOpaqueEmptyTypes.end()) {
165                 EDITypeLog("Found a non-opaque composite type with 0 members! Name is: " << name);
166                 nonOpaqueEmptyTypes.insert(name);
167             }
168         }
169     }
170     return aDIArray;
171 }
172 
getTopStructType(unsigned index) const173 const EDIType* EDIType::getTopStructType(unsigned index) const {
174     static unsigned level = 0;
175     static unsigned structsLeft;
176     static EDIType targetType;
177 
178     if(level == 0) {
179         structsLeft = index;
180     }
181 
182     if(isUnionOrStructTy() || isOpaqueTy()) {
183         if(structsLeft == 0) {
184             targetType = *this;
185             return &targetType;
186         }
187         else {
188             structsLeft--;
189             return NULL;
190         }
191     }
192     unsigned numContainedTypes = getNumContainedTypes();
193     for(unsigned i=0;i<numContainedTypes;i++) {
194         const EDIType containedType(getContainedType(i));
195         level++;
196         const EDIType *topStructType = containedType.getTopStructType(index);
197         level--;
198         if(topStructType != NULL) {
199             return topStructType;
200         }
201     }
202     return NULL;
203 }
204 
205 //===----------------------------------------------------------------------===//
206 // Other public methods
207 //===----------------------------------------------------------------------===//
208 
print(raw_ostream & OS) const209 void EDIType::print(raw_ostream &OS) const {
210      OS << getDescription();
211 }
212 
printDescription(raw_ostream & OS,int skipUnions,int skipStructs,int allowMultiNames) const213 void EDIType::printDescription(raw_ostream &OS, int skipUnions, int skipStructs, int allowMultiNames) const {
214     static std::vector<const EDIType*> nestedTypes;
215     int printMultiNames = allowMultiNames && myNames.size() > 1;
216     if(allowMultiNames && !printMultiNames && isPointerTy() && myName.compare("")) {
217         printMultiNames = 1;
218     }
219 
220     if(isOpaqueTy()) {
221         OS << "opaque";
222         return;
223     }
224 
225     unsigned numContainedTypes = getNumContainedTypes();
226     if(numContainedTypes == 0) {
227         OS << (printMultiNames ? getNamesString() : getName());
228         return;
229     }
230 
231     if(isPointerTy() && getContainedType(0).isUnionOrStructTy()) {
232         bool isNestedType = false;
233         unsigned j;
234         for(j=0;j<nestedTypes.size();j++) {
235             if(nestedTypes[j]->equals(this)) {
236                 isNestedType = true;
237                 break;
238             }
239         }
240         if(isNestedType) {
241             OS << "\\" << nestedTypes.size() - j;
242             return;
243         }
244     }
245 
246     nestedTypes.push_back(this);
247     if(isPointerTy()) {
248         const EDIType subType = getContainedType(0);
249         subType.printDescription(OS, skipUnions, skipStructs, allowMultiNames);
250         OS << "*";
251         if(printMultiNames) {
252             OS << "|" << getNamesString();
253         }
254     }
255     else if(isArrayTy() || isVectorTy()) {
256         const EDIType subType = getContainedType(0);
257         unsigned numElements = getNumElements();
258         char startSep = isArrayTy() ? '[' : '<';
259         char endSep = isArrayTy() ? ']' : '>';
260         OS << startSep;
261         if(numElements) {
262             OS << numElements << " x ";
263         }
264         subType.printDescription(OS, skipUnions, skipStructs, allowMultiNames);
265         OS << endSep;
266     }
267     else if(isUnionOrStructTy()) {
268         if(skipUnions && isUnionTy()) {
269             OS << "(U) $" << (printMultiNames ? getNamesString() : (myName.compare("") ? myName : "ANONYMOUS"));
270             nestedTypes.pop_back();
271             return;
272         }
273         if(skipStructs && isStructTy()) {
274             OS << "$" << (printMultiNames ? getNamesString() : (myName.compare("") ? myName : "ANONYMOUS"));
275             nestedTypes.pop_back();
276             return;
277         }
278         unsigned numContainedTypes = getNumContainedTypes();
279         OS << "{ ";
280         if(isUnionTy()) {
281             OS << "(U) ";
282         }
283         OS << "$" << (printMultiNames ? getNamesString() : (myName.compare("") ? myName : "ANONYMOUS")) << " ";
284         for(unsigned i=0;i<numContainedTypes;i++) {
285             if(i > 0) {
286                 OS << ", ";
287             }
288             EDIType subType = getContainedType(i);
289             subType.printDescription(OS, skipUnions, skipStructs, allowMultiNames);
290         }
291         OS << " }";
292    }
293    else if(isFunctionTy()) {
294        unsigned numContainedTypes = getNumContainedTypes();
295        assert(numContainedTypes > 0);
296        EDIType subType = getContainedType(0);
297        subType.printDescription(OS, skipUnions, skipStructs, allowMultiNames);
298        numContainedTypes--;
299        OS << " (";
300        for(unsigned i=0;i<numContainedTypes;i++) {
301            if(i > 0) {
302                OS << ", ";
303            }
304            subType = getContainedType(i+1);
305            subType.printDescription(OS, skipUnions, skipStructs, allowMultiNames);
306        }
307        OS << ")";
308    }
309    else {
310        OS << "???";
311    }
312    nestedTypes.pop_back();
313 }
314 
equals(const EDIType * other) const315 bool EDIType::equals(const EDIType *other) const {
316     static std::set<std::pair<MDNode*, MDNode*> > compatibleMDNodes;
317     static std::set<std::pair<MDNode*, MDNode*> >::iterator compatibleMDNodesIt;
318     static int max_recursive_steps = -1;
319 #if DEBUG_EDI_EQUALS
320     if(debugEDIEquals>1) EDITypeErr("COMPARING :" << getTag() << ":" << getName() << " VS " << other->getTag() << ":" << other->getName());
321 #endif
322     if(isOpaqueTy() || other->isOpaqueTy()) {
323 #if DEBUG_EDI_EQUALS
324         if(debugEDIEquals) EDITypeErr("----> ???1");
325 #endif
326         return isOpaqueTy() && other->isOpaqueTy();
327     }
328     if(getTag() != other->getTag()) {
329 #if DEBUG_EDI_EQUALS
330         if(debugEDIEquals) EDITypeErr("----> false1");
331 #endif
332         return false;
333     }
334     unsigned numContainedTypes = getNumContainedTypes();
335     unsigned numOtherContainedTypes = other->getNumContainedTypes();
336     if(numContainedTypes != numOtherContainedTypes) {
337 #if DEBUG_EDI_EQUALS
338         if(debugEDIEquals) EDITypeErr("----> false2");
339 #endif
340         return false;
341     }
342     if(getNumElements() != other->getNumElements()) {
343 #if DEBUG_EDI_EQUALS
344         if(debugEDIEquals) EDITypeErr("----> false3");
345 #endif
346         return false;
347     }
348     if(myName.compare(other->getName())) {
349 #if DEBUG_EDI_EQUALS
350         if(debugEDIEquals) EDITypeErr("----> false4");
351 #endif
352         return false;
353     }
354     if((myNames.size() > 0 || other->getNames().size() > 0) && getNamesString().compare(other->getNamesString())) {
355 #if DEBUG_EDI_EQUALS
356         if(debugEDIEquals) EDITypeErr("----> false5");
357 #endif
358         return false;
359     }
360     if(numContainedTypes == 0) {
361 #if DEBUG_EDI_EQUALS
362         if(debugEDIEquals) EDITypeErr("----> true1");
363 #endif
364         return true;
365     }
366     MDNode *aNode = *(&aDIType);
367     MDNode *otherNode = *(other->getDIType());
368     if(aNode == otherNode) {
369 #if DEBUG_EDI_EQUALS
370         if(debugEDIEquals) EDITypeErr("----> true2");
371 #endif
372         return true;
373     }
374     int isUnionOrStruct = isUnionOrStructTy();
375     int isNonAnonUnionOrStruct = isUnionOrStruct && myName.size() > 0;
376     int saved_max_recursive_steps = max_recursive_steps;
377     if(max_recursive_steps == -1 && isNonAnonUnionOrStruct) {
378         //A simple way to break recursion for recursive non-anonymous structs/unions.
379         max_recursive_steps = 10;
380     }
381     else if(max_recursive_steps == 0) {
382 #if DEBUG_EDI_EQUALS
383         if(debugEDIEquals) EDITypeErr("----> true4");
384 #endif
385         return true;
386     }
387     else {
388         max_recursive_steps--;
389     }
390     for(unsigned i=0;i<numContainedTypes;i++) {
391         const EDIType &subEDIType = getContainedType(i);
392         const EDIType &subOtherEDIType = other->getContainedType(i);
393         if(!subEDIType.equals(&subOtherEDIType)) {
394             max_recursive_steps = saved_max_recursive_steps;
395             return false;
396         }
397     }
398     max_recursive_steps = saved_max_recursive_steps;
399     return true;
400 }
401 
402 //===----------------------------------------------------------------------===//
403 // Public static methods
404 //===----------------------------------------------------------------------===//
405 
lookupTypedefName(std::string & typedefName)406 std::string EDIType::lookupTypedefName(std::string &typedefName) {
407     static std::string noName;
408     for (const DIType aDITypeIt : DIFinder.types()) {
409         DIType aDIType(aDITypeIt);
410         if(aDIType.getTag() == dwarf::DW_TAG_typedef && aDIType.getName().compare(typedefName)) {
411             while(aDIType.getTag() == dwarf::DW_TAG_typedef) {
412                 aDIType = PassUtil::getDITypeDerivedFrom((const DIDerivedType)aDIType);
413             }
414             if(aDIType.getName().compare("")) {
415                 return aDIType.getName();
416             }
417         }
418     }
419     return noName;
420 }
421 
lookupUnionMemberName(TYPECONST Type * type)422 std::string EDIType::lookupUnionMemberName(TYPECONST Type* type) {
423     std::string string;
424     std::string error;
425     if(!type->isStructTy() || type->getNumContainedTypes() != 1) {
426         return "";
427     }
428     raw_string_ostream ostream(string);
429     writeTypeSymbolic(ostream, type->getContainedType(0), EDIType::module);
430     ostream.flush();
431     Regex unionRegex("%(union|struct)\\.([^ ]+)", 0);
432     assert(unionRegex.isValid(error));
433     SmallVector<StringRef, 8> unionMatches;
434     if(unionRegex.match(string, &unionMatches)) {
435         return unionMatches[2];
436     }
437     return "";
438 }
439 
getStructEDITypeByName(std::string & typeName)440 const EDIType* EDIType::getStructEDITypeByName(std::string &typeName) {
441     static EDIType aEDIType;
442     assert(module);
443     for (const DIType aDIType : DIFinder.types()) {
444         //skip zero-element stuct types, necessary to avoid infinite recursion during opaque type lookup
445         //xxx opaque type lookup should not be necessary but is there a bug in the frontend that leaves certain concrete types unnecessarily opaque?
446         const EDIType tmpEDIType(aDIType, NORMALIZE, DO_NOT_CHECK_OPAQUE_TYPES);
447         aEDIType = tmpEDIType;
448         if(typeName.compare(aEDIType.getName())) {
449             continue;
450         }
451         if(aEDIType.isUnionOrStructTy()) {
452             return &aEDIType;
453         }
454     }
455     return NULL;
456 }
457 
setModule(Module * M)458 void EDIType::setModule(Module *M) {
459     assert(module == NULL);
460     module = M;
461     DIFinder.processModule(*module);
462 }
463 
464 //===----------------------------------------------------------------------===//
465 // Private methods
466 //===----------------------------------------------------------------------===//
init(bool norm,bool checkOpaqueTypes)467 void EDIType::init(bool norm, bool checkOpaqueTypes) {
468     EDIType_assert(isType());
469     currentDimension = 0;
470     this->checkOpaqueTypes = checkOpaqueTypes;
471     myName = "";
472     if(norm) {
473         normalize();
474     }
475     if(myNames.size() == 0) {
476         //nobody assigned names yet, do it here
477         myName = isVoidTy() ? voidName : aDIType.getName();
478         if(myName.compare("")) {
479             myNames.push_back(myName);
480         }
481     }
482 }
483 
normalize()484 void EDIType::normalize() {
485     if(getTag() == dwarf::DW_TAG_typedef) {
486         normalizeTypedef();
487     }
488     if(isBasicType() || isVoidTy() || isEnumTy() || isOpaqueTy()) {
489         return;
490     }
491     if(isDerivedType()) {
492         if(isPointerTy() || isUnionOrStructTy()) {
493            return;
494         }
495         aDIType = PassUtil::getDITypeDerivedFrom((const DIDerivedType)aDIType);
496         normalize();
497         return;
498     }
499     EDIType_assert(isCompositeType());
500     if(isAggregateType() || isVectorTy() || isFunctionTy()) {
501        return;
502     }
503     EDIType_assert(getNumContainedTypes() == 1);
504     aDIType = *(getContainedType(0, DO_NOT_NORMALIZE).getDIType());
505     normalize();
506 }
507 
normalizeTypedef()508 void EDIType::normalizeTypedef() {
509     myNames.clear();
510     while(aDIType.getTag() == dwarf::DW_TAG_typedef) {
511         if(aDIType.getName().compare("")) {
512             myNames.push_back(aDIType.getName());
513         }
514         aDIType = PassUtil::getDITypeDerivedFrom((const DIDerivedType)aDIType);
515     }
516     myName = isVoidTy() ? voidName : aDIType.getName();
517     if(!myName.compare("")) {
518         //anonymous typedefed type, use the deepest typedef name
519         assert(!isBasicType());
520         assert(myNames.size() > 0);
521         myName = myNames[myNames.size()-1];
522     }
523     else {
524         myNames.push_back(myName);
525     }
526 }
527 
528 StringRef EDIType::voidName("void");
529 Module *EDIType::module = NULL;
530 DebugInfoFinder EDIType::DIFinder;
531 
532 }
533