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    if (type->getNumContainedTypes() == 1) {
152        return true;
153    }
154    /*
155     * This check is no longer used, because it may wrongly fail in the case of
156     * an array of instances of a structure that contains a union that is
157     * initialized in different ways for array element 0 and 1.  What we really
158     * need is a check to see whether the elements are *compatible*, but we do
159     * not appear to have the means to do that here.  We warn if the check fails
160     * so as to make sure that its removal is not the source of new problems.
161     */
162    if (type->getContainedType(0) != type->getContainedType(1)) {
163        TypeUtilLog("strict isArrayAsStructTy test failed");
164        //return false;
165    }
166    return true;
167 }
168 
169 unsigned TypeUtil::getHash(TYPECONST Type* type) {
170     return (unsigned) PassUtil::getTypeHash(type);
171 }
172 
173 const std::string TypeUtil::getDescription(TYPECONST Type* type,
174     size_t max_chars /*= 0*/, size_t max_levels /*= 0*/) {
175     std::string string;
176     if(!PRINT_SKIP_UNIONS && !PRINT_SKIP_STRUCTS && PRINT_USE_BUILTIN_PRINTING) {
177     string = PassUtil::getTypeDescription(type);
178     }
179     else {
180         raw_string_ostream ostream(string);
181         printTypeString(ostream, type, max_chars, max_levels);
182         ostream.flush();
183     }
184     if(VERBOSE_LEVEL > 0) {
185         string = getFormattedDescription(string);
186     }
187     return string;
188 }
189 
190 const std::string TypeUtil::getDescription(const EDIType* aEDIType) {
191     std::string string;
192     string = aEDIType->getDescription(PRINT_SKIP_UNIONS, PRINT_SKIP_STRUCTS, PRINT_MULTI_NAMES);
193     if(VERBOSE_LEVEL > 0) {
194         string = getFormattedDescription(string);
195     }
196     if(VERBOSE_LEVEL > 1) {
197         raw_string_ostream ostream(string);
198         ostream << "\n\t";
199         aEDIType->getDIType()->print(ostream);
200         ostream.flush();
201     }
202     return string;
203 }
204 
205 const std::string TypeUtil::getDescription(TYPECONST Type* type, const EDIType* aEDIType,
206     size_t max_chars /*= 0*/, size_t max_levels /*= 0*/) {
207     std::string string;
208     string = "[\ntype = \n";
209     string.append(TypeUtil::getDescription(type, max_chars, max_levels));
210     string.append("\nEDIType =\n");
211     string.append(TypeUtil::getDescription(aEDIType));
212     string.append("\n]");
213     return string;
214 }
215 
216 const std::string TypeUtil::getFormattedDescription(std::string &description) {
217     std::string string;
218     raw_string_ostream ostream(string);
219     printFormattedTypeString(ostream, description, 0, description.size());
220     ostream.flush();
221     return string;
222 }
223 
224 void TypeUtil::printFormattedTypeString(raw_ostream &OS, std::string &typeStr, int start, int length) {
225     static int indent = 0;
226     for(int k=0;k<indent;k++) OS << " ";
227     for(int i=start;i<start+length;i++) {
228         OS << typeStr[i];
229         if(typeStr[i] == '{') {
230             int newLength = 0;
231             int structsFound = 0;
232             int j;
233             for(j=i+2;j<start+length;j++) {
234                 switch(typeStr[j]) {
235                     case '{':
236                         structsFound++;
237                     break;
238                     case '}':
239                         if(structsFound == 0) {
240                             newLength = j-i-3;
241                         }
242                         else {
243                             structsFound--;
244                         }
245                     break;
246                 }
247                 if(newLength != 0) {
248                     break;
249                 }
250             }
251             assert(newLength > 0);
252             OS << "\n";
253             indent += 2;
254             printFormattedTypeString(OS, typeStr, i+2, newLength);
255             indent -= 2;
256             OS << "\n";
257             for(int k=0;k<indent;k++) OS << " ";
258             i = j;
259             OS << typeStr[i];
260         }
261     }
262 }
263 
264 void TypeUtil::printTypeString(raw_ostream &OS, TYPECONST Type* type,
265     size_t max_chars /*= 0*/, size_t max_levels /*= 0*/) {
266     static std::vector<TYPECONST Type*> nestedTypes;
267     static unsigned level = 0;
268     static unsigned counter;
269 
270     if (level == 0) {
271         counter = 0;
272     }
273     else if(max_chars && counter >= max_chars) {
274         OS << "%%";
275         return;
276     }
277     else if(max_levels && level >= max_levels) {
278         OS << "%%";
279         return;
280     }
281 
282     if(TypeUtil::isOpaqueTy(type)) {
283         OS << "opaque";
284         counter += 6;
285         return;
286     }
287 
288     unsigned numContainedTypes = type->getNumContainedTypes();
289     if(numContainedTypes == 0) {
290         assert(!type->isStructTy());
291         type->print(OS);
292         counter += 2;
293         return;
294     }
295 
296     if(type->isPointerTy() && type->getContainedType(0)->isStructTy()) {
297         bool isNestedType = false;
298         unsigned j;
299         for(j=0;j<nestedTypes.size();j++) {
300             if(nestedTypes[j] == type) {
301                 isNestedType = true;
302                 break;
303             }
304         }
305         if(isNestedType) {
306             OS << "\\" << nestedTypes.size() - j;
307             counter += 2;
308             return;
309         }
310     }
311 
312     nestedTypes.push_back(type);
313     if(type->isPointerTy()) {
314         TYPECONST Type* subType = type->getContainedType(0);
315         level++;
316         printTypeString(OS, subType);
317         level--;
318         OS << "*";
319         counter++;
320     }
321     else if(type->isArrayTy() || type->isVectorTy()) {
322         TYPECONST Type* subType = type->getContainedType(0);
323         unsigned numElements = type->isArrayTy() ? ((TYPECONST ArrayType*) type)->getNumElements() : ((TYPECONST VectorType*) type)->getNumElements();
324         char startSep = type->isArrayTy() ? '[' : '<';
325         char endSep = type->isArrayTy() ? ']' : '>';
326         OS << startSep;
327         if(numElements) {
328             OS << numElements << " x ";
329         }
330         level++;
331         printTypeString(OS, subType);
332         level--;
333         OS << endSep;
334         counter += 4;
335     }
336     else if(type->isStructTy()) {
337         if(PRINT_SKIP_STRUCTS || PRINT_SKIP_UNIONS) {
338             OS << "$STRUCT/UNION";
339             counter += 13;
340             nestedTypes.pop_back();
341             return;
342         }
343         unsigned numContainedTypes = type->getNumContainedTypes();
344         OS << "{ ";
345         OS << "$STRUCT/UNION ";
346         for(unsigned i=0;i<numContainedTypes;i++) {
347             if(i > 0) {
348                 OS << ", ";
349             }
350             TYPECONST Type* subType = type->getContainedType(i);
351             level++;
352             printTypeString(OS, subType);
353             level--;
354         }
355         OS << " }";
356         counter += 18 + 2*numContainedTypes;
357    }
358    else if(type->isFunctionTy()) {
359        unsigned numContainedTypes = type->getNumContainedTypes();
360        assert(numContainedTypes > 0);
361        TYPECONST Type* subType = type->getContainedType(0);
362        level++;
363        printTypeString(OS, subType);
364        level--;
365        numContainedTypes--;
366        OS << " (";
367        for(unsigned i=0;i<numContainedTypes;i++) {
368            if(i > 0) {
369                OS << ", ";
370            }
371            subType = type->getContainedType(i+1);
372            level++;
373            printTypeString(OS, subType);
374            level--;
375        }
376        OS << ")";
377        counter += 3 + 2*numContainedTypes;
378    }
379    else {
380        OS << "???";
381        counter +=3;
382    }
383    nestedTypes.pop_back();
384 }
385 
386 unsigned TypeUtil::typeToBits(TYPECONST Type *type) {
387     if (type->isIntegerTy()) {
388         return ((IntegerType*)type)->getBitWidth();
389     }
390     else if (type->isArrayTy() && type->getContainedType(0)->isIntegerTy()) {
391         TYPECONST Type *containedType = type->getContainedType(0);
392         return ((IntegerType*)containedType)->getBitWidth() * ((ArrayType*)containedType)->getNumElements();
393     }
394     return 0;
395 }
396 
397 int TypeUtil::VERBOSE_LEVEL = 1;
398 int TypeUtil::PRINT_SKIP_UNIONS = 0;
399 int TypeUtil::PRINT_SKIP_STRUCTS = 0;
400 int TypeUtil::PRINT_USE_BUILTIN_PRINTING = 0;
401 int TypeUtil::PRINT_MULTI_NAMES = 0;
402 
403 }
404