1 #include <magic/support/TypeUtil.h>
2 
3 using namespace llvm;
4 
5 namespace llvm {
6 
7 //===----------------------------------------------------------------------===//
8 // Public static methods
9 //===----------------------------------------------------------------------===//
10 
11 bool TypeUtil::isPaddedType(TYPECONST Type *type) {
12     if(type->getNumContainedTypes() < 2) {
13         return false;
14     }
15     TYPECONST Type *lastContainedType = type->getContainedType(type->getNumContainedTypes() - 1);
16     bool paddedTy = lastContainedType->isIntegerTy() || (lastContainedType->isArrayTy() &&
17         lastContainedType->getContainedType(0)->isIntegerTy());
18     return paddedTy;
19 }
20 
21 TYPECONST Type* TypeUtil::lookupTopStructType(TYPECONST Type *type, unsigned index) {
22     static unsigned level = 0;
23     static unsigned structsLeft;
24 
25     if(level == 0) {
26         structsLeft = index;
27     }
28 
29     if(type->isStructTy() || TypeUtil::isOpaqueTy(type)) {
30         if(structsLeft == 0) {
31             return type;
32         }
33         else {
34             structsLeft--;
35             return NULL;
36         }
37     }
38     unsigned numContainedTypes = type->getNumContainedTypes();
39     for(unsigned i=0;i<numContainedTypes;i++) {
40         TYPECONST Type *containedType = type->getContainedType(i);
41         level++;
42         TYPECONST Type *topStructType = lookupTopStructType(containedType, index);
43         level--;
44         if(topStructType != NULL) {
45             return topStructType;
46         }
47     }
48     return NULL;
49 }
50 
51 void TypeUtil::parseTopStructTypes(Module &M, TYPECONST Type *type, std::vector<std::string> *names, std::vector<unsigned> *flags) {
52     std::string string;
53     raw_string_ostream ostream(string);
54     EDIType::writeTypeSymbolic(ostream, type, &M);
55     ostream.flush();
56     Regex anonRegex("%(union|struct)\\.(\\.*[0-9]*anon)", 0);
57     Regex regularRegex("%(union|struct)\\.([^{}(), *]+)", 0);
58     Regex unnamedRegex("%(%)?([0-9]+)", 0);
59     std::string error;
60     assert(anonRegex.isValid(error) && regularRegex.isValid(error) && unnamedRegex.isValid(error));
61     size_t index = -1;
62     while((index=string.find("%", index+1))!=std::string::npos) {
63         std::string entryString = string.substr(index);
64         if(entryString[entryString.size()-1] == ']') {
65             entryString = entryString.substr(0, entryString.size()-1);
66         }
67         StringRef entryStringRef(entryString);
68         SmallVector<StringRef, 8> entryMatches;
69         unsigned entryFlags;
70         entryMatches.clear();
71         entryFlags = 0;
72         if(anonRegex.match(entryString, &entryMatches)) {
73             entryFlags |= TypeUtil::TYPE_ANONYMOUS;
74         }
75         else if(unnamedRegex.match(entryString, &entryMatches)) {
76             entryFlags |= TypeUtil::TYPE_UNNAMED;
77         }
78         else {
79             assert(regularRegex.match(entryString, &entryMatches) && "Unsupported struct type");
80         }
81         assert(entryStringRef.startswith(entryMatches[0]));
82         std::string prefix = entryMatches[1];
83         std::string name = entryMatches[2];
84         entryFlags |= !prefix.compare("union") ? TypeUtil::TYPE_UNION : TypeUtil::TYPE_STRUCT;
85         if(names) names->push_back(name);
86         if(flags) flags->push_back(entryFlags);
87     }
88 }
89 
90 int TypeUtil::findTopStructTypeIndex(Module &M, TYPECONST Type *type, std::string &name, unsigned flagsToAccept) {
91     std::vector<std::string> names;
92     std::vector<unsigned> flags;
93     parseTopStructTypes(M, type, &names, &flags);
94     int index = -1;
95     for(unsigned i=0;i<names.size();i++) {
96         if(!name.compare(names[i]) && (flagsToAccept | flags[i]) == flagsToAccept) {
97             index = i;
98             break;
99         }
100     }
101     return index;
102 }
103 
104 TYPECONST Type* TypeUtil::getRecursiveElementType(TYPECONST Type *type) {
105     TYPECONST PointerType* pointerType = dyn_cast<PointerType>(type);
106     if(!pointerType) {
107         return type;
108     }
109     return getRecursiveElementType(pointerType->getElementType());
110 }
111 
112 TYPECONST Type* TypeUtil::getArrayFreePointerType(TYPECONST Type *type) {
113     if(type->isPointerTy() || type->isArrayTy()) {
114         TYPECONST Type* elementType = getArrayFreePointerType(type->getContainedType(0));
115         type = PointerType::get(elementType, 0);
116     }
117     return type;
118 }
119 
120 bool TypeUtil::hasInnerPointers(TYPECONST Type *type) {
121     if(TypeUtil::isOpaqueTy(type) || type->isFunctionTy()) {
122         return false;
123     }
124     if(type->isPointerTy()) {
125         return true;
126     }
127 
128     unsigned numContainedTypes = type->getNumContainedTypes();
129     if(numContainedTypes == 0) {
130         return false;
131     }
132     else if(type->isArrayTy() || type->isVectorTy()) {
133         return hasInnerPointers(type->getContainedType(0));
134     }
135     else {
136         assert(type->isStructTy());
137         for(unsigned i=0;i<numContainedTypes;i++) {
138             if(hasInnerPointers(type->getContainedType(i))) {
139                 return true;
140             }
141         }
142    }
143 
144    return false;
145 }
146 
147 bool TypeUtil::isArrayAsStructTy(TYPECONST Type *type) {
148    if(!type->isStructTy()) {
149        return false;
150    }
151    return type->getNumContainedTypes() == 1 || type->getContainedType(0) == type->getContainedType(1);
152 }
153 
154 unsigned TypeUtil::getHash(TYPECONST Type* type) {
155     return (unsigned) PassUtil::getTypeHash(type);
156 }
157 
158 const std::string TypeUtil::getDescription(TYPECONST Type* type,
159     size_t max_chars /*= 0*/, size_t max_levels /*= 0*/) {
160     std::string string;
161     if(!PRINT_SKIP_UNIONS && !PRINT_SKIP_STRUCTS && PRINT_USE_BUILTIN_PRINTING) {
162     string = PassUtil::getTypeDescription(type);
163     }
164     else {
165         raw_string_ostream ostream(string);
166         printTypeString(ostream, type, max_chars, max_levels);
167         ostream.flush();
168     }
169     if(VERBOSE_LEVEL > 0) {
170         string = getFormattedDescription(string);
171     }
172     return string;
173 }
174 
175 const std::string TypeUtil::getDescription(const EDIType* aEDIType) {
176     std::string string;
177     string = aEDIType->getDescription(PRINT_SKIP_UNIONS, PRINT_SKIP_STRUCTS, PRINT_MULTI_NAMES);
178     if(VERBOSE_LEVEL > 0) {
179         string = getFormattedDescription(string);
180     }
181     if(VERBOSE_LEVEL > 1) {
182         raw_string_ostream ostream(string);
183         ostream << "\n\t";
184         aEDIType->getDIType()->print(ostream);
185         ostream.flush();
186     }
187     return string;
188 }
189 
190 const std::string TypeUtil::getDescription(TYPECONST Type* type, const EDIType* aEDIType,
191     size_t max_chars /*= 0*/, size_t max_levels /*= 0*/) {
192     std::string string;
193     string = "[\ntype = \n";
194     string.append(TypeUtil::getDescription(type, max_chars, max_levels));
195     string.append("\nEDIType =\n");
196     string.append(TypeUtil::getDescription(aEDIType));
197     string.append("\n]");
198     return string;
199 }
200 
201 const std::string TypeUtil::getFormattedDescription(std::string &description) {
202     std::string string;
203     raw_string_ostream ostream(string);
204     printFormattedTypeString(ostream, description, 0, description.size());
205     ostream.flush();
206     return string;
207 }
208 
209 void TypeUtil::printFormattedTypeString(raw_ostream &OS, std::string &typeStr, int start, int length) {
210     static int indent = 0;
211     for(int k=0;k<indent;k++) OS << " ";
212     for(int i=start;i<start+length;i++) {
213         OS << typeStr[i];
214         if(typeStr[i] == '{') {
215             int newLength = 0;
216             int structsFound = 0;
217             int j;
218             for(j=i+2;j<start+length;j++) {
219                 switch(typeStr[j]) {
220                     case '{':
221                         structsFound++;
222                     break;
223                     case '}':
224                         if(structsFound == 0) {
225                             newLength = j-i-3;
226                         }
227                         else {
228                             structsFound--;
229                         }
230                     break;
231                 }
232                 if(newLength != 0) {
233                     break;
234                 }
235             }
236             assert(newLength > 0);
237             OS << "\n";
238             indent += 2;
239             printFormattedTypeString(OS, typeStr, i+2, newLength);
240             indent -= 2;
241             OS << "\n";
242             for(int k=0;k<indent;k++) OS << " ";
243             i = j;
244             OS << typeStr[i];
245         }
246     }
247 }
248 
249 void TypeUtil::printTypeString(raw_ostream &OS, TYPECONST Type* type,
250     size_t max_chars /*= 0*/, size_t max_levels /*= 0*/) {
251     static std::vector<TYPECONST Type*> nestedTypes;
252     static unsigned level = 0;
253     static unsigned counter;
254 
255     if (level == 0) {
256         counter = 0;
257     }
258     else if(max_chars && counter >= max_chars) {
259         OS << "%%";
260         return;
261     }
262     else if(max_levels && level >= max_levels) {
263         OS << "%%";
264         return;
265     }
266 
267     if(TypeUtil::isOpaqueTy(type)) {
268         OS << "opaque";
269         counter += 6;
270         return;
271     }
272 
273     unsigned numContainedTypes = type->getNumContainedTypes();
274     if(numContainedTypes == 0) {
275         assert(!type->isStructTy());
276         type->print(OS);
277         counter += 2;
278         return;
279     }
280 
281     if(type->isPointerTy() && type->getContainedType(0)->isStructTy()) {
282         bool isNestedType = false;
283         unsigned j;
284         for(j=0;j<nestedTypes.size();j++) {
285             if(nestedTypes[j] == type) {
286                 isNestedType = true;
287                 break;
288             }
289         }
290         if(isNestedType) {
291             OS << "\\" << nestedTypes.size() - j;
292             counter += 2;
293             return;
294         }
295     }
296 
297     nestedTypes.push_back(type);
298     if(type->isPointerTy()) {
299         TYPECONST Type* subType = type->getContainedType(0);
300         level++;
301         printTypeString(OS, subType);
302         level--;
303         OS << "*";
304         counter++;
305     }
306     else if(type->isArrayTy() || type->isVectorTy()) {
307         TYPECONST Type* subType = type->getContainedType(0);
308         unsigned numElements = type->isArrayTy() ? ((TYPECONST ArrayType*) type)->getNumElements() : ((TYPECONST VectorType*) type)->getNumElements();
309         char startSep = type->isArrayTy() ? '[' : '<';
310         char endSep = type->isArrayTy() ? ']' : '>';
311         OS << startSep;
312         if(numElements) {
313             OS << numElements << " x ";
314         }
315         level++;
316         printTypeString(OS, subType);
317         level--;
318         OS << endSep;
319         counter += 4;
320     }
321     else if(type->isStructTy()) {
322         if(PRINT_SKIP_STRUCTS || PRINT_SKIP_UNIONS) {
323             OS << "$STRUCT/UNION";
324             counter += 13;
325             nestedTypes.pop_back();
326             return;
327         }
328         unsigned numContainedTypes = type->getNumContainedTypes();
329         OS << "{ ";
330         OS << "$STRUCT/UNION ";
331         for(unsigned i=0;i<numContainedTypes;i++) {
332             if(i > 0) {
333                 OS << ", ";
334             }
335             TYPECONST Type* subType = type->getContainedType(i);
336             level++;
337             printTypeString(OS, subType);
338             level--;
339         }
340         OS << " }";
341         counter += 18 + 2*numContainedTypes;
342    }
343    else if(type->isFunctionTy()) {
344        unsigned numContainedTypes = type->getNumContainedTypes();
345        assert(numContainedTypes > 0);
346        TYPECONST Type* subType = type->getContainedType(0);
347        level++;
348        printTypeString(OS, subType);
349        level--;
350        numContainedTypes--;
351        OS << " (";
352        for(unsigned i=0;i<numContainedTypes;i++) {
353            if(i > 0) {
354                OS << ", ";
355            }
356            subType = type->getContainedType(i+1);
357            level++;
358            printTypeString(OS, subType);
359            level--;
360        }
361        OS << ")";
362        counter += 3 + 2*numContainedTypes;
363    }
364    else {
365        OS << "???";
366        counter +=3;
367    }
368    nestedTypes.pop_back();
369 }
370 
371 unsigned TypeUtil::typeToBits(TYPECONST Type *type) {
372     if (type->isIntegerTy()) {
373         return ((IntegerType*)type)->getBitWidth();
374     }
375     else if (type->isArrayTy() && type->getContainedType(0)->isIntegerTy()) {
376         TYPECONST Type *containedType = type->getContainedType(0);
377         return ((IntegerType*)containedType)->getBitWidth() * ((ArrayType*)containedType)->getNumElements();
378     }
379     return 0;
380 }
381 
382 int TypeUtil::VERBOSE_LEVEL = 1;
383 int TypeUtil::PRINT_SKIP_UNIONS = 0;
384 int TypeUtil::PRINT_SKIP_STRUCTS = 0;
385 int TypeUtil::PRINT_USE_BUILTIN_PRINTING = 0;
386 int TypeUtil::PRINT_MULTI_NAMES = 0;
387 
388 }
389