1 #include <magic/support/TypeUtil.h>
2
3 using namespace llvm;
4
5 namespace llvm {
6
7 //===----------------------------------------------------------------------===//
8 // Public static methods
9 //===----------------------------------------------------------------------===//
10
isPaddedType(TYPECONST Type * type)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
lookupTopStructType(TYPECONST Type * type,unsigned index)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
parseTopStructTypes(Module & M,TYPECONST Type * type,std::vector<std::string> * names,std::vector<unsigned> * flags)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
findTopStructTypeIndex(Module & M,TYPECONST Type * type,std::string & name,unsigned flagsToAccept)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
getRecursiveElementType(TYPECONST Type * type)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
getArrayFreePointerType(TYPECONST Type * type)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
hasInnerPointers(TYPECONST Type * type)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
isArrayAsStructTy(TYPECONST Type * type)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
getHash(TYPECONST Type * type)169 unsigned TypeUtil::getHash(TYPECONST Type* type) {
170 return (unsigned) PassUtil::getTypeHash(type);
171 }
172
getDescription(TYPECONST Type * type,size_t max_chars,size_t max_levels)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
getDescription(const EDIType * aEDIType)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
getDescription(TYPECONST Type * type,const EDIType * aEDIType,size_t max_chars,size_t max_levels)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
getFormattedDescription(std::string & description)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
printFormattedTypeString(raw_ostream & OS,std::string & typeStr,int start,int length)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
printTypeString(raw_ostream & OS,TYPECONST Type * type,size_t max_chars,size_t max_levels)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
typeToBits(TYPECONST Type * type)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