1 #ifndef _PASS_COMMON_H
2 #define _PASS_COMMON_H
3 
4 #if LLVM_VERSION >= 33
5 #define ATTRIBUTE_SET_TY              AttributeSet
6 #include <llvm/IR/Function.h>
7 #include <llvm/IR/Module.h>
8 #include <llvm/IR/Instructions.h>
9 #include <llvm/IR/Type.h>
10 #include <llvm/IR/Constants.h>
11 #include <llvm/IR/Intrinsics.h>
12 #include <llvm/IR/DerivedTypes.h>
13 #include <llvm/IR/LLVMContext.h>
14 #include <llvm/IR/IntrinsicInst.h>
15 #include <llvm/IR/DataLayout.h>
16 #include <llvm/IR/IRBuilder.h>
17 #else /* LLVM_VERSION < 33 */
18 #define ATTRIBUTE_SET_TY              AttrListPtr
19 #include <llvm/Function.h>
20 #include <llvm/Module.h>
21 #include <llvm/Instructions.h>
22 #include <llvm/Type.h>
23 #include <llvm/Constants.h>
24 #include <llvm/Intrinsics.h>
25 #include <llvm/DerivedTypes.h>
26 #include <llvm/LLVMContext.h>
27 #include <llvm/IntrinsicInst.h>
28 #endif /* LLVM_VERSION >= 33 */
29 
30 #if LLVM_VERSION >= 32
31 #define DATA_LAYOUT_TY 		      DataLayout
32 #define ATTRIBUTE_SET_RET_IDX         ATTRIBUTE_SET_TY::ReturnIndex
33 #define ATTRIBUTE_SET_FN_IDX          ATTRIBUTE_SET_TY::FunctionIndex
34 #include <llvm/DebugInfo.h>
35 #if LLVM_VERSION == 32
36 #include <llvm/DataLayout.h>
37 #include <llvm/IRBuilder.h>
38 #endif
39 #else /* LLVM_VERSION < 32 */
40 #define DATA_LAYOUT_TY 		      TargetData
41 #define ATTRIBUTE_SET_RET_IDX         0
42 #define ATTRIBUTE_SET_FN_IDX          (~0U)
43 #include <llvm/Target/TargetData.h>
44 #include <llvm/Analysis/DebugInfo.h>
45 #include <llvm/Support/IRBuilder.h>
46 #endif /* LLVM_VERSION >= 32 */
47 
48 #if LLVM_VERSION >= 31
49 /* XXX Check. */
50 #define CONSTANT_ARRAY_INITIALIZER_TY ConstantDataArray
51 
52 #else /* LLVM_VERSION < 31 */
53 #define CONSTANT_ARRAY_INITIALIZER_TY ConstantArray
54 #endif /* LLVM_VERSION >= 31 */
55 
56 #if LLVM_VERSION >= 30
57 #define BASE_PARSER                   parser
58 
59 #define TYPECONST
60 #else /* LLVM_VERSION < 30 */
61 #define BASE_PARSER                   basic_parser
62 
63 #define TYPECONST const
64 #endif /* LLVM_VERSION >= 30 */
65 
66 #if LLVM_VERSION >= 29
67 #define VALUE_TO_VALUE_MAP_TY ValueToValueMapTy
68 #else  /* LLVM_VERSION < 29 */
69 #define VALUE_TO_VALUE_MAP_TY ValueMap<const Value*, Value*>
70 #endif /* LLVM_VERSION >= 29 */
71 
72 #define ZERO_CONSTANT_INT(M) ConstantInt::get((M).getContext(), APInt(32, 0, 10))
73 #define VOID_PTR_TY(M)       PointerType::get(IntegerType::get((M).getContext(), 8), 0)
74 #define VOID_PTR_PTR_TY(M)   PointerType::get(PointerType::get(IntegerType::get((M).getContext(), 8), 0), 0)
75 
76 #define FOREACH_FUNC(M, F, B) do { \
77     Module::FunctionListType &__FL = (M).getFunctionList(); \
78     for (Module::iterator __MI = __FL.begin(); __MI != __FL.end(); ++__MI) { \
79         const Function *F = __MI; \
80         if (F->isIntrinsic()) \
81             continue; \
82         B \
83     } \
84 } while(0)
85 
86 #define FOREACH_FUNC_INS(F, I, B) do { \
87     for (Function::const_iterator __FI = F->begin(), __FE = F->end(); __FI != __FE; ++__FI) { \
88         for (BasicBlock::const_iterator __BI = __FI->begin(), BE = __FI->end(); __BI != BE; ++__BI) { \
89             Instruction *I = (Instruction*) ((unsigned long) &(*__BI)); \
90             B \
91         } \
92     } \
93 } while(0)
94 
95 #define FOREACH_FUNC_CS(F, CS, B) do { \
96     FOREACH_FUNC_INS(F, I, \
97         CallSite CS = PassUtil::getCallSiteFromInstruction(I); \
98         if (!CS.getInstruction()) \
99             continue; \
100         B \
101     ); \
102 } while(0)
103 
104 #define DEBUG_LLVM_DEBUG_API 0
105 
106 typedef enum PassUtilLinkageTypeE {
107     PASS_UTIL_LINKAGE_NONE = 0,
108     PASS_UTIL_LINKAGE_WEAK,
109     PASS_UTIL_LINKAGE_COMMON,
110     PASS_UTIL_LINKAGE_EXTERNAL,
111     PASS_UTIL_LINKAGE_EXTERNAL_WEAK,
112     PASS_UTIL_LINKAGE_WEAK_POINTER,
113     PASS_UTIL_LINKAGE_PRIVATE,
114     __NUM_PASS_UTIL_LINKAGE_TYPES
115     /* Values here should only be appended at the end, external components (e.g., scripts) may be relying on them.*/
116 } PassUtilLinkageType;
117 
118 #define PASS_UTIL_LINKAGE_TYPE_STRINGS \
119     "NONE", \
120     "WEAK", \
121     "COMMON", \
122     "EXTERNAL", \
123     "EXTERNAL_WEAK", \
124     "WEAK_POINTER", \
125     "PRIVATE"
126 
127 typedef enum PassUtilPropE {
128     PASS_UTIL_PROP_NONE,
129     PASS_UTIL_PROP_NOINLINE,
130     PASS_UTIL_PROP_USED,
131     PASS_UTIL_PROP_PRESERVE,
132     __NUM_PASS_UTIL_PROPS
133 } PassUtilProp;
134 
135 #define PASS_UTIL_FLAG(F) (1 << F)
136 
137 #define PASS_COMMON_INIT_ONCE() \
138     Module *PassUtil::M = NULL; \
139 
140 using namespace llvm;
141 
142 namespace llvm {
143 
144 class PassUtil {
145   public:
146       static void writeTypeSymbolic(raw_string_ostream &OS, TYPECONST Type *type, const Module *M);
147       static const std::string getTypeDescription(TYPECONST Type* type);
148       static Value *findDbgGlobalDeclare(GlobalVariable *V);
149       static Value *findDbgSubprogramDeclare(const Function *F);
150       static void getDbgLocationInfoRelPath(const std::string &baseDir, const std::string &filename, const std::string &directory, std::string &relPath);
151       static void getDbgLocationInfo(DIDescriptor &DID, const std::string &baseDir, std::string *filename, std::string *directory, std::string *relPath);
152       static bool getInstrDbgLocationInfo(Instruction *I, const std::string &baseDir, std::string *filename, std::string *directory, std::string *relPath, unsigned int *lineNum, bool expand=true);
153       static unsigned getDbgSubrangeNumElements(const DISubrange &subrange);
154       static bool isDbgVectorTy(const DIType &type);
155       static DIType getDITypeDerivedFrom(const DIDerivedType &type);
156       static bool isOpaqueTy(TYPECONST Type *type);
157       static Constant* getGetElementPtrConstant(Constant *constant, std::vector<Value*> &indexes);
158       static GetElementPtrInst* createGetElementPtrInstruction(Value *ptr, std::vector<Value*> &indexes, const Twine &NameStr="", Instruction *InsertBefore=0);
159       static GetElementPtrInst* createGetElementPtrInstruction(Value *ptr, std::vector<Value*> &indexes, const Twine &NameStr="", BasicBlock *InsertAtEnd=0);
160       static CallInst* createCallInstruction(Value *F, std::vector<Value*> &args, const Twine &NameStr="", Instruction *InsertBefore=0);
161       static CallInst* createCallInstruction(Value *F, std::vector<Value*> &args, const Twine &NameStr="", BasicBlock *InsertAtEnd=0);
162       static Function* getIntrinsicFunction(Module &M, Intrinsic::ID id, TYPECONST Type** types=NULL, unsigned size=0);
163       static FunctionType* getFunctionType(TYPECONST Type* Result, std::vector<TYPECONST Type*> &argsTy, bool isVarArg=false);
164       static Function* setFunctionProperties(Function *F, unsigned long properties);
165       static Function* createFunctionWeakPtrWrapper(Module &M, StringRef Name, FunctionType *Ty);
166       static Function* getOrInsertFunction(Module &M, StringRef Name, FunctionType *Ty, PassUtilLinkageType insertLinkage, unsigned long properties);
167       static PassUtilLinkageType getFunctionPassUtilLinkageType(Function *F);
168       static std::string getPassUtilLinkageTypeString(PassUtilLinkageType linkageType);
169       static void getFunctionEntryExits(Function *F, BasicBlock **entryBlock, std::vector<BasicBlock*> *exitBlocks);
170       static bool isReturnedValue(Function *F, Value *V);
171       static CallSite getCallSiteFromInstruction(Instruction *I);
172       static CallSite getCallSiteFromUser(User *U);
173       static void getFunctionsInDirectBUCallgraph(Function* F, std::set<Function*> &funcs);
174       static void getAllocaInfo(Function *F, Instruction **allocaInsertionPoint, Instruction **firstNonAllocaInst);
175       static Constant* getStringConstantArray(Module &M, const std::string &string);
176       static GlobalVariable* getStringGlobalVariable(Module &M, const std::string &string, const std::string &varName = ".str.pu", const std::string &varSection = "", Constant **getElementPtrExpr=NULL, bool cacheable=false);
177       static ATTRIBUTE_SET_TY remapCallSiteAttributes(CallSite &CS, int argOffset);
178       static void parseStringListOpt(std::vector<std::string> &vector, const std::string &string, const std::string &separator = ":");
179       static void parseStringPairListOpt(std::set<std::pair<std::string, std::string> > &set, const std::string &string, const std::string &listSeparator = ":", const std::string &pairSeparator = ";");
180       static void parseRegexListOpt(std::vector<Regex*> &list, const std::string &string);
181       static bool matchRegexes(std::string string, std::vector<Regex*> &regexes);
182       static void setModule(Module *M);
183       static void getModuleName(Module &M, std::string *fullName, std::string *dirName, std::string *baseName);
184       static unsigned long getTypeHash(TYPECONST Type* type, unsigned maxLevel=11);
185   private:
186       static Module *M;
187 };
188 
189 inline void PassUtil::writeTypeSymbolic(raw_string_ostream &OS, TYPECONST Type *type, const Module *M) {
190 #if LLVM_VERSION >= 30
191     /* XXX Check. */
192     type->print(OS);
193     return;
194 #else
195     return WriteTypeSymbolic(OS, type, M);
196 #endif
197 }
198 
199 inline const std::string PassUtil::getTypeDescription(TYPECONST Type* type) {
200     std::string string;
201 #if LLVM_VERSION >= 30
202     /* XXX Check. */
203     raw_string_ostream ostream(string);
204     type->print(ostream);
205     ostream.flush();
206 #else
207     string = type->getDescription();
208 #endif
209 
210     return string;
211 }
212 
213 inline Value *PassUtil::findDbgGlobalDeclare(GlobalVariable *V) {
214 #if LLVM_VERSION >= 30
215   const Module *M = V->getParent();
216   NamedMDNode *NMD = M->getNamedMetadata("llvm.dbg.cu");
217   if (!NMD)
218     return 0;
219 
220   for (unsigned i = 0, e = NMD->getNumOperands(); i != e; ++i) {
221       DICompileUnit CU(NMD->getOperand(i));
222       DIArray GVs = CU.getGlobalVariables();
223       for (unsigned i = 0, e = GVs.getNumElements(); i != e; ++i) {
224         DIDescriptor DIG(GVs.getElement(i));
225         if (DIGlobalVariable(DIG).getGlobal() == V)
226           return DIG;
227       }
228   }
229   return 0;
230 #else
231   const Module *M = V->getParent();
232   NamedMDNode *NMD = M->getNamedMetadata("llvm.dbg.gv");
233   if (!NMD)
234     return 0;
235 
236   for (unsigned i = 0, e = NMD->getNumOperands(); i != e; ++i) {
237     DIDescriptor DIG(cast<MDNode>(NMD->getOperand(i)));
238     if (!DIG.isGlobalVariable())
239       continue;
240     if (DIGlobalVariable(DIG).getGlobal() == V)
241       return DIG;
242   }
243   return 0;
244 #endif
245 }
246 
247 inline Value *PassUtil::findDbgSubprogramDeclare(const Function *V) {
248 #if LLVM_VERSION >= 30
249   const Module *M = V->getParent();
250   NamedMDNode *NMD = M->getNamedMetadata("llvm.dbg.cu");
251   if (!NMD)
252     return 0;
253 
254   for (unsigned i = 0, e = NMD->getNumOperands(); i != e; ++i) {
255       DICompileUnit CU(NMD->getOperand(i));
256       DIArray SPs = CU.getSubprograms();
257       for (unsigned i = 0, e = SPs.getNumElements(); i != e; ++i) {
258            DISubprogram DIS(SPs.getElement(i));
259            if (DIS.getFunction() == V) {
260            	return DIS;
261            }
262       }
263   }
264   return 0;
265 #else
266   const Module *M = V->getParent();
267   NamedMDNode *NMD = M->getNamedMetadata("llvm.dbg.sp");
268   if (!NMD)
269     return 0;
270 
271   for (unsigned i = 0, e = NMD->getNumOperands(); i != e; ++i) {
272     DIDescriptor DIG(cast<MDNode>(NMD->getOperand(i)));
273     if (!DIG.isSubprogram())
274       continue;
275     if (DISubprogram(DIG).getFunction() == V)
276       return DIG;
277   }
278   return 0;
279 #endif
280 }
281 
282 inline void PassUtil::getDbgLocationInfoRelPath(const std::string &baseDir, const std::string &filename, const std::string &directory, std::string &relPath) {
283     StringRef directoryRef(directory);
284     std::pair<StringRef, StringRef> stringPair = directoryRef.split(baseDir);
285     relPath = (stringPair.second.compare("") ? stringPair.second.str() : stringPair.first.str()) + "/" + filename;
286 #if DEBUG_LLVM_DEBUG_API
287     errs() << " - getDbgLocationInfoRelPath: Location Info is: " << directory << " | " << filename << " | " << relPath << "\n";
288 #endif
289 }
290 
291 inline void PassUtil::getDbgLocationInfo(DIDescriptor &DID, const std::string &baseDir, std::string *filename, std::string *directory, std::string *relPath) {
292   StringRef _directory;
293   StringRef _filename;
294   if (DID.isGlobalVariable()) {
295 #if LLVM_VERSION >= 30
296     _directory = ((DIGlobalVariable*)&DID)->getDirectory();
297     _filename = ((DIGlobalVariable*)&DID)->getFilename();
298 #else
299     _directory = ((DIGlobalVariable*)&DID)->getCompileUnit().getDirectory();
300     _filename = ((DIGlobalVariable*)&DID)->getCompileUnit().getFilename();
301 #endif
302 #if DEBUG_LLVM_DEBUG_API
303     errs() << "DIGlobalVariable name is: " << ((DIGlobalVariable*)&DID)->getName() << "\n";
304 #endif
305   }
306   else if (DID.isSubprogram()) {
307     _directory = ((DISubprogram*)&DID)->getDirectory();
308     _filename = ((DISubprogram*)&DID)->getFilename();
309 #if DEBUG_LLVM_DEBUG_API
310     errs() << "DISubprogram name is: " << ((DISubprogram*)&DID)->getName() << "\n";
311 #endif
312   }
313   else {
314     DIScope DIS;
315     assert (DID.isVariable());
316     DIS = ((DIVariable*)&DID)->getContext();
317     if (DIS.isSubprogram()) {
318         _directory = ((DISubprogram*)&DIS)->getDirectory();
319         _filename = ((DISubprogram*)&DIS)->getFilename();
320 #if DEBUG_LLVM_DEBUG_API
321         errs() << "DIVariable (SP) name is: " << ((DIVariable*)&DID)->getName() << "\n";
322 #endif
323     }
324     else if (DIS.isLexicalBlock()) {
325         _directory = ((DILexicalBlock*)&DIS)->getDirectory();
326         _filename = ((DILexicalBlock*)&DIS)->getFilename();
327 #if DEBUG_LLVM_DEBUG_API
328         errs() << "DIVariable (LB) name is: " << ((DIVariable*)&DID)->getName() << "\n";
329 #endif
330     }
331     else {
332 #if LLVM_VERSION >= 30
333         assert(DIS.isLexicalBlockFile());
334         _directory = ((DILexicalBlockFile*)&DIS)->getDirectory();
335         _filename = ((DILexicalBlockFile*)&DIS)->getFilename();
336 #if DEBUG_LLVM_DEBUG_API
337         errs() << "DIVariable (LBF) name is: " << ((DIVariable*)&DID)->getName() << "\n";
338 #endif
339 #else
340 	assert(0 && "Unexpected DIScope instance!");
341 #endif
342     }
343   }
344   if (filename) {
345     *filename = _filename;
346   }
347   if (directory) {
348     *directory = _directory;
349   }
350   if (relPath) {
351     getDbgLocationInfoRelPath(baseDir, _filename, _directory, *relPath);
352   }
353 }
354 
355 inline bool PassUtil::getInstrDbgLocationInfo(Instruction *I, const std::string &baseDir, std::string *filename, std::string *directory, std::string *relPath, unsigned int *lineNum, bool expand) {
356     BasicBlock::iterator BI = I;
357     MDNode *N = BI->getMetadata("dbg");
358     if (!N && !expand) {
359         return false;
360     }
361     while(!N) {
362         if (BI->isTerminator()) {
363             BranchInst *BInst = dyn_cast<BranchInst>(BI);
364             if (BInst && BInst->isUnconditional()) {
365                 BI = BInst->getSuccessor(0)->front();
366                 N = BI->getMetadata("dbg");
367                 continue;
368             }
369             return false;
370         }
371         BI++;
372         N = BI->getMetadata("dbg");
373     }
374 
375     DILocation DIL(N);
376     StringRef _directory = DIL.getDirectory();
377     StringRef _filename = DIL.getFilename();
378     if (filename) {
379         *filename = _filename;
380     }
381     if (directory) {
382         *directory = _directory;
383     }
384     if (relPath) {
385       getDbgLocationInfoRelPath(baseDir, _filename, _directory, *relPath);
386     }
387     if (lineNum) {
388         *lineNum = DIL.getLineNumber();
389     }
390 
391     return true;
392 }
393 
394 inline unsigned PassUtil::getDbgSubrangeNumElements(const DISubrange &subrange) {
395 #if LLVM_VERSION >= 33
396     const unsigned numElements = (unsigned) subrange.getCount();
397 #else
398     const unsigned low = (unsigned) subrange.getLo();
399     const unsigned high = (unsigned) subrange.getHi();
400     const unsigned numElements = high - low + 1;
401 #endif
402 
403     return numElements;
404 }
405 
406 inline bool PassUtil::isDbgVectorTy(const DIType &type) {
407 #if LLVM_VERSION >= 33
408     return type.isVector();
409 #else
410     return type.getTag() == dwarf::DW_TAG_vector_type;
411 #endif
412 }
413 
414 inline DIType PassUtil::getDITypeDerivedFrom(const DIDerivedType &type) {
415 #if LLVM_VERSION >= 34
416     static DITypeIdentifierMap TypeIdentifierMap;
417     static bool TypeMapInitialized = false;
418     if (!TypeMapInitialized) {
419         assert(PassUtil::M && "Set module first!");
420         if (NamedMDNode *CU_Nodes = PassUtil::M->getNamedMetadata("llvm.dbg.cu")) {
421           TypeIdentifierMap = generateDITypeIdentifierMap(CU_Nodes);
422           TypeMapInitialized = true;
423         }
424     }
425     return type.getTypeDerivedFrom().resolve(TypeIdentifierMap);
426 #else
427     return type.getTypeDerivedFrom();
428 #endif
429 }
430 
431 inline bool PassUtil::isOpaqueTy(TYPECONST Type *type) {
432 #if LLVM_VERSION >= 30
433     return type->isStructTy() && (((TYPECONST StructType*)type)->isOpaque() || type->getNumContainedTypes() == 0);
434 #else
435     return type->isOpaqueTy();
436 #endif
437 }
438 
439 inline Constant* PassUtil::getGetElementPtrConstant(Constant *constant, std::vector<Value*> &indexes) {
440 #if LLVM_VERSION >= 30
441     ArrayRef<Value*> ref(indexes);
442     return ConstantExpr::getGetElementPtr(constant, ref);
443 #else
444     return ConstantExpr::getGetElementPtr(constant, &indexes[0], indexes.size());
445 #endif
446 }
447 
448 inline GetElementPtrInst* PassUtil::createGetElementPtrInstruction(Value *ptr, std::vector<Value*> &indexes, const Twine &NameStr, Instruction *InsertBefore) {
449 #if LLVM_VERSION >= 30
450     ArrayRef<Value*> ref(indexes);
451     return GetElementPtrInst::Create(ptr, ref, NameStr, InsertBefore);
452 #else
453     return GetElementPtrInst::Create(ptr, indexes.begin(), indexes.end(), NameStr, InsertBefore);
454 #endif
455 }
456 
457 inline GetElementPtrInst* PassUtil::createGetElementPtrInstruction(Value *ptr, std::vector<Value*> &indexes, const Twine &NameStr, BasicBlock *InsertAtEnd) {
458 #if LLVM_VERSION >= 30
459     ArrayRef<Value*> ref(indexes);
460     return GetElementPtrInst::Create(ptr, ref, NameStr, InsertAtEnd);
461 #else
462     return GetElementPtrInst::Create(ptr, indexes.begin(), indexes.end(), NameStr, InsertAtEnd);
463 #endif
464 }
465 
466 inline CallInst* PassUtil::createCallInstruction(Value *F, std::vector<Value*> &args, const Twine &NameStr, Instruction *InsertBefore) {
467 #if LLVM_VERSION >= 30
468     ArrayRef<Value*> ref(args);
469     return CallInst::Create(F, ref, NameStr, InsertBefore);
470 #else
471     return CallInst::Create(F, args.begin(), args.end(), NameStr, InsertBefore);
472 #endif
473 }
474 
475 inline CallInst* PassUtil::createCallInstruction(Value *F, std::vector<Value*> &args, const Twine &NameStr, BasicBlock *InsertAtEnd) {
476 #if LLVM_VERSION >= 30
477     ArrayRef<Value*> ref(args);
478     return CallInst::Create(F, ref, NameStr, InsertAtEnd);
479 #else
480     return CallInst::Create(F, args.begin(), args.end(), NameStr, InsertAtEnd);
481 #endif
482 }
483 
484 inline Function* PassUtil::getIntrinsicFunction(Module &M, Intrinsic::ID id, TYPECONST Type** types, unsigned size) {
485 #if LLVM_VERSION >= 30
486     std::vector<TYPECONST Type*> typeVector;
487     for(unsigned i=0;i<size;i++) {
488         typeVector.push_back(types[i]);
489     }
490     ArrayRef<TYPECONST Type*> ref(typeVector);
491     return Intrinsic::getDeclaration(&M, id, ref);
492 #else
493     return Intrinsic::getDeclaration(&M, id, types, size);
494 #endif
495 }
496 
497 inline FunctionType* PassUtil::getFunctionType(TYPECONST Type* Result, std::vector<TYPECONST Type*> &argsTy, bool isVarArg)
498 {
499 #if LLVM_VERSION >= 30
500     ArrayRef<TYPECONST Type*> ref(argsTy);
501     return FunctionType::get(Result, ref, isVarArg);
502 #else
503     return FunctionType::get(Result, argsTy, isVarArg);
504 #endif
505 }
506 
507 inline Function* PassUtil::setFunctionProperties(Function *F, unsigned long props)
508 {
509     assert(F);
510     bool preserve = props & (PASS_UTIL_FLAG(PASS_UTIL_PROP_NOINLINE)|PASS_UTIL_FLAG(PASS_UTIL_PROP_USED)|PASS_UTIL_FLAG(PASS_UTIL_PROP_PRESERVE));
511 
512     if (F->isDeclaration()) {
513         return F;
514     }
515     if (preserve) {
516         Instruction *I;
517         getAllocaInfo(F, NULL, &I);
518         assert(I);
519 
520         /* Add a volatile store to a new global variable to preserve it. */
521         PointerType* voidPointerTy = PointerType::get(IntegerType::get(F->getContext(), 8), 0);
522         GlobalVariable* volatileVar = new GlobalVariable(*F->getParent(),
523             voidPointerTy, false, GlobalValue::CommonLinkage,
524             0, F->getName() + "_llvm_propvar");
525         volatileVar->setInitializer(ConstantPointerNull::get(voidPointerTy));
526         new StoreInst(ConstantExpr::getCast(Instruction::BitCast, F, voidPointerTy), volatileVar, true, I);
527     }
528     return F;
529 }
530 
531 inline Function* PassUtil::createFunctionWeakPtrWrapper(Module &M, StringRef Name, FunctionType *Ty)
532 {
533     unsigned i;
534     Function *F = getOrInsertFunction(M, Name.str() + "_llvm_weakptrwrapper" , Ty, PASS_UTIL_LINKAGE_COMMON, 0);
535     TYPECONST Type *RetTy = Ty->getReturnType();
536     PointerType *FPtrTy = PointerType::get(Ty, 0);
537     Constant *FPtrNull = Constant::getNullValue(FPtrTy);
538 
539     /* Create the global function pointer variable. */
540     GlobalVariable* weakPtrVar = new GlobalVariable(M, FPtrTy, false,
541         GlobalValue::CommonLinkage, 0, Name);
542     weakPtrVar->setInitializer(FPtrNull);
543 
544     /* Create the wrapper function body. */
545     F->dropAllReferences();
546     BasicBlock* entryBB = BasicBlock::Create(M.getContext(), "entry",F,0);
547     BasicBlock* weakPtrOverridenBB = BasicBlock::Create(M.getContext(), "have." + Name.str(),F,0);
548     BasicBlock* endBB = BasicBlock::Create(M.getContext(), "end",F,0);
549     AllocaInst* retval = NULL;
550 
551     /* Parse arguments. */
552     std::vector<AllocaInst*> argsAllocaInsts;
553     for (Function::arg_iterator args = F->arg_begin(); args != F->arg_end(); args++) {
554         Value *argValue = args;
555         AllocaInst *allocaInst = new AllocaInst(argValue->getType(), ".llvm.pu.args", entryBB);
556         argsAllocaInsts.push_back(allocaInst);
557     }
558     if (!RetTy->isVoidTy()) {
559         retval = new AllocaInst(RetTy, "retval", entryBB);
560     }
561     i=0;
562     for (Function::arg_iterator args = F->arg_begin(); args != F->arg_end(); args++, i++) {
563         Value *argValue = args;
564         AllocaInst *allocaInst = argsAllocaInsts[i];
565         new StoreInst(argValue, allocaInst, true, entryBB);
566     }
567     if (retval) {
568         new StoreInst(Constant::getNullValue(RetTy), retval, true, entryBB);
569     }
570 
571     /* Build entry block. */
572     LoadInst* weakPtr = new LoadInst(weakPtrVar, "", true, entryBB);
573     ICmpInst* cmpInst = new ICmpInst(*entryBB, ICmpInst::ICMP_NE, weakPtr, FPtrNull, "");
574     BranchInst::Create(weakPtrOverridenBB, endBB, cmpInst, entryBB);
575 
576     /* Build weakPtrOverriden block, only executed with a non-NULL weakPtr */
577     std::vector<Value*> weakPtrCallParams;
578     i=0;
579     for (Function::arg_iterator args = F->arg_begin(); args != F->arg_end(); args++, i++) {
580         AllocaInst *allocaInst = argsAllocaInsts[i];
581         weakPtrCallParams.push_back(new LoadInst(allocaInst, "", true, weakPtrOverridenBB));
582     }
583     weakPtr = new LoadInst(weakPtrVar, "", true, weakPtrOverridenBB);
584     CallInst* weakPtrCall = createCallInstruction(weakPtr, weakPtrCallParams, "", weakPtrOverridenBB);
585     weakPtrCall->setCallingConv(CallingConv::C);
586 
587     if (retval) {
588         new StoreInst(weakPtrCall, retval, false, weakPtrOverridenBB);
589     }
590     BranchInst::Create(endBB, weakPtrOverridenBB);
591 
592     /* Build end block. */
593     if (!retval) {
594         ReturnInst::Create(M.getContext(), endBB);
595     }
596     else {
597         LoadInst* retvalValue = new LoadInst(retval, "", false, endBB);
598         ReturnInst::Create(M.getContext(), retvalValue, endBB);
599     }
600     return F;
601 }
602 
603 inline Function* PassUtil::getOrInsertFunction(Module &M, StringRef Name, FunctionType *Ty, PassUtilLinkageType insertLinkage, unsigned long properties)
604 {
605     static std::map<std::string, Function *> functionMap;
606     std::map<std::string, Function *>::iterator functionMapIt;
607     Function *F = NULL;
608     bool needsEmptyBody = true;
609     bool needsProperties = true;
610     bool needsIncludsion = true;
611 
612     functionMapIt = functionMap.find(Name);
613     if (functionMapIt != functionMap.end()) {
614         return functionMapIt->second;
615     }
616     F = M.getFunction(Name);
617 
618     if (F) {
619         /* If the function exists, check the type and return it. */
620         if (F->getFunctionType() != Ty) {
621             return NULL;
622         }
623         functionMap.insert(std::pair<std::string, Function *>(Name, F));
624         setFunctionProperties(F, properties);
625         return F;
626     }
627 
628     /* Has the user requested creation of the function otherwise? */
629     if (insertLinkage == PASS_UTIL_LINKAGE_NONE) {
630         return NULL;
631     }
632     switch(insertLinkage) {
633     case PASS_UTIL_LINKAGE_WEAK:
634         /* Create empty function that can optionally be overriden at link time*/
635         F = Function::Create(Ty, GlobalVariable::WeakAnyLinkage, Name);
636     break;
637     case PASS_UTIL_LINKAGE_COMMON:
638         /* Creates empty function, non overridable. */
639         F = Function::Create(Ty, GlobalVariable::InternalLinkage, Name);
640     break;
641     case PASS_UTIL_LINKAGE_EXTERNAL:
642         /* Creates function declaration that must be defined at link time. */
643         F = Function::Create(Ty, GlobalVariable::ExternalLinkage, Name);
644         needsEmptyBody = false;
645     break;
646     case PASS_UTIL_LINKAGE_EXTERNAL_WEAK:
647         /* Creates weak function declaration that can optionally be defined
648          * at link time (if undefined the linker will emit a NULL symbol).
649          */
650         F = Function::Create(Ty, GlobalVariable::ExternalWeakLinkage, Name);
651         needsEmptyBody = false;
652     break;
653     case PASS_UTIL_LINKAGE_WEAK_POINTER:
654         /* Creates function pointer initialized to NULL that can optionally
655          * be initialized at runtime. Invocations are wrapped to ensure that
656          * indirect call is performed on a NULL pointer. This is to emulate
657          * Mac OS' weak_pointer attribute, which allows weak symbols to be
658          * overriden in LD_PRELOADED libraries at runtime.
659          */
660         F = PassUtil::createFunctionWeakPtrWrapper(M, Name, Ty);
661         needsProperties = false;
662         needsIncludsion = false;
663     break;
664     default:
665         return NULL;
666     break;
667     }
668     if (needsIncludsion) {
669         M.getFunctionList().push_back(F);
670     }
671     if (needsEmptyBody) {
672         BasicBlock* block = BasicBlock::Create(M.getContext(), "entry", F);
673         IRBuilder<> builder(block);
674         TYPECONST Type *RetTy = Ty->getReturnType();
675         if (RetTy->isVoidTy()) {
676             builder.CreateRetVoid();
677         }
678         else {
679             builder.CreateRet(Constant::getNullValue(RetTy));
680         }
681     }
682     functionMap.insert(std::pair<std::string, Function *>(Name, F));
683     if (needsProperties) {
684         setFunctionProperties(F, properties);
685     }
686     return F;
687 }
688 
689 inline PassUtilLinkageType PassUtil::getFunctionPassUtilLinkageType(Function *F)
690 {
691     if (F->isDeclaration()) {
692         return PASS_UTIL_LINKAGE_EXTERNAL;
693     }
694     if (F->hasInternalLinkage()) {
695         return PASS_UTIL_LINKAGE_PRIVATE;
696     }
697     return PASS_UTIL_LINKAGE_COMMON;
698 }
699 
700 inline std::string PassUtil::getPassUtilLinkageTypeString(PassUtilLinkageType linkageType)
701 {
702     const char *strArray[] = { PASS_UTIL_LINKAGE_TYPE_STRINGS };
703     std::string str(strArray[linkageType]);
704     return str;
705 }
706 
707 inline void PassUtil::getFunctionEntryExits(Function *F, BasicBlock **entryBlock, std::vector<BasicBlock*> *exitBlocks)
708 {
709     if (entryBlock) {
710         *entryBlock = &F->front();
711     }
712     if (exitBlocks) {
713         for(Function::iterator I = F->begin(), E = F->end(); I != E; ++I) {
714             if (isa<ReturnInst>(I->getTerminator()) || isa<UnreachableInst>(I->getTerminator()))
715                 exitBlocks->push_back(I);
716         }
717     }
718 }
719 
720 inline bool PassUtil::isReturnedValue(Function *F, Value *V)
721 {
722     std::vector<BasicBlock*> exitBlocks;
723     PassUtil::getFunctionEntryExits(F, NULL, &exitBlocks);
724     for (unsigned i=0;i<exitBlocks.size();i++) {
725         Instruction *I = exitBlocks[i]->getTerminator();
726         ReturnInst *RI = dyn_cast<ReturnInst>(I);
727         if (RI && RI->getReturnValue()) {
728             Value *RV = RI->getReturnValue();
729             if (RV == V) {
730                 return true;
731             }
732             if (LoadInst *LI = dyn_cast<LoadInst>(RV)) {
733                 if (LI->getPointerOperand() == V) {
734                     return true;
735                 }
736             }
737         }
738     }
739     return false;
740 }
741 
742 inline CallSite PassUtil::getCallSiteFromInstruction(Instruction *I)
743 {
744   return getCallSiteFromUser(I);
745 }
746 
747 inline CallSite PassUtil::getCallSiteFromUser(User *U)
748 {
749   CallSite CS(U->stripPointerCasts());
750   CallSite emptyCS;
751   Instruction *I = CS.getInstruction();
752   if (!I)
753       return emptyCS;
754   if (isa<CallInst>(I) && dyn_cast<CallInst>(I)->isInlineAsm())
755       return emptyCS;
756   Function *F = CS.getCalledFunction();
757   if (F && F->isIntrinsic())
758       return emptyCS;
759   return CS;
760 }
761 
762 inline void PassUtil::getFunctionsInDirectBUCallgraph(Function* F, std::set<Function*> &funcs) {
763   if (funcs.find(F) != funcs.end())
764       return;
765   funcs.insert(F);
766   FOREACH_FUNC_CS(F, CS,
767       if (!CS.getCalledFunction())
768           continue;
769       getFunctionsInDirectBUCallgraph(CS.getCalledFunction(), funcs);
770   );
771 }
772 
773 inline void PassUtil::getAllocaInfo(Function *F, Instruction **allocaInsertionPoint, Instruction **firstNonAllocaInst)
774 {
775     assert(!F->isDeclaration());
776     BasicBlock::iterator allocaIP = F->front().begin();
777     while (isa<AllocaInst>(allocaIP)) ++allocaIP;
778     BasicBlock::iterator firstNonAI = allocaIP;
779     if (firstNonAI->getName().equals("alloca point")) {
780     	firstNonAI++;
781     }
782     if(allocaInsertionPoint) {
783     	*allocaInsertionPoint = allocaIP;
784     }
785     if(firstNonAllocaInst) {
786     	*firstNonAllocaInst = firstNonAI;
787     }
788 }
789 
790 inline Constant* PassUtil::getStringConstantArray(Module &M, const std::string &string)
791 {
792   std::vector<Constant*> elements;
793   elements.reserve(string.size() + 1);
794   for (unsigned i = 0; i < string.size(); ++i)
795     elements.push_back(ConstantInt::get(Type::getInt8Ty(M.getContext()), string[i]));
796 
797   // Add a null terminator to the string...
798   elements.push_back(ConstantInt::get(Type::getInt8Ty(M.getContext()), 0));
799 
800   ArrayType *ATy = ArrayType::get(Type::getInt8Ty(M.getContext()), elements.size());
801   return ConstantArray::get(ATy, elements);
802 }
803 
804 inline GlobalVariable* PassUtil::getStringGlobalVariable(Module &M, const std::string &string, const std::string &varName, const std::string &varSection, Constant **getElementPtrExpr, bool cacheable)
805 {
806     static std::map<std::string, GlobalVariable*> stringCache;
807     std::map<std::string, GlobalVariable*>::iterator stringCacheIt;
808     std::string stringCacheKey;
809     GlobalVariable *strGV = NULL;
810 
811     if (cacheable) {
812     	stringCacheKey = string + "~!~!" + varName + "~!~!" + varSection;
813         stringCacheIt = stringCache.find(stringCacheKey);
814         if (stringCacheIt != stringCache.end()) {
815             strGV = stringCacheIt->second;
816             cacheable = false;
817         }
818     }
819 
820     if (!strGV) {
821         //create a constant internal string reference
822         Constant *stringValue = PassUtil::getStringConstantArray(M, string);
823 
824         //create the global variable, cache it, and record it in the module
825         strGV = new GlobalVariable(M, stringValue->getType(), true,
826             GlobalValue::InternalLinkage, stringValue, varName);
827         if (varSection.compare("")) {
828             strGV->setSection(varSection);
829         }
830     }
831     if (getElementPtrExpr) {
832     	    std::vector<Value*> strConstantIndices;
833     	    strConstantIndices.push_back(ZERO_CONSTANT_INT(M));
834     	    strConstantIndices.push_back(ZERO_CONSTANT_INT(M));
835     	    *getElementPtrExpr = PassUtil::getGetElementPtrConstant(strGV, strConstantIndices);
836     }
837 
838     if (cacheable) {
839         stringCache.insert(std::pair<std::string, GlobalVariable*>(stringCacheKey, strGV));
840     }
841 
842     return strGV;
843 }
844 
845 inline ATTRIBUTE_SET_TY PassUtil::remapCallSiteAttributes(CallSite &CS, int argOffset)
846 {
847     ATTRIBUTE_SET_TY Attrs = CS.getAttributes();
848     ATTRIBUTE_SET_TY NewAttrs;
849 #if LLVM_VERSION >= 33
850     Instruction *I = CS.getInstruction();
851     NewAttrs.addAttributes(I->getContext(), ATTRIBUTE_SET_RET_IDX, Attrs.getRetAttributes());
852     NewAttrs.addAttributes(I->getContext(), ATTRIBUTE_SET_FN_IDX, Attrs.getFnAttributes());
853     for (unsigned i=1;i<=CS.arg_size();i++) {
854         NewAttrs.addAttributes(I->getContext(), i+argOffset, Attrs.getParamAttributes(i));
855     }
856 #elif LLVM_VERSION == 32
857     Instruction *I = CS.getInstruction();
858     NewAttrs.addAttr(I->getContext(), ATTRIBUTE_SET_RET_IDX, Attrs.getRetAttributes());
859     NewAttrs.addAttr(I->getContext(), ATTRIBUTE_SET_FN_IDX, Attrs.getFnAttributes());
860     for (unsigned i=1;i<=CS.arg_size();i++) {
861         NewAttrs.addAttr(I->getContext(), i+argOffset, Attrs.getParamAttributes(i));
862     }
863 #else
864     NewAttrs.addAttr(ATTRIBUTE_SET_RET_IDX, Attrs.getRetAttributes());
865     NewAttrs.addAttr(ATTRIBUTE_SET_FN_IDX, Attrs.getFnAttributes());
866     for (unsigned i=1;i<=CS.arg_size();i++) {
867         NewAttrs.addAttr(i+argOffset, Attrs.getParamAttributes(i));
868     }
869 #endif
870 
871     return NewAttrs;
872 }
873 
874 inline void PassUtil::parseStringListOpt(std::vector<std::string> &list, const std::string &string, const std::string &separator)
875 {
876     if(string.compare("")) {
877         SmallVector< StringRef, 8 > vector;
878         StringRef sref(string);
879         sref.split(vector, separator, -1, false);
880         list.insert(list.end(), vector.begin(), vector.end());
881     }
882 }
883 
884 inline void PassUtil::parseStringPairListOpt(std::set<std::pair<std::string, std::string> > &set, const std::string &string, const std::string &listSeparator, const std::string &pairSeparator)
885 {
886 	if(string.compare("")) {
887 		SmallVector< StringRef, 8 > vector;
888 		StringRef sref(string);
889 		sref.split(vector, listSeparator, -1, false);
890 		SmallVector< StringRef, 8 > parts;
891 		while(!vector.empty()) {
892 			StringRef token = vector.pop_back_val();
893 			parts.clear();
894 			token.split(parts, pairSeparator, -1, false);
895 			assert(parts.size() == 2 && "Two tokens were expected.");
896 			set.insert(std::pair<std::string, std::string>(parts.front(), parts.back()));
897 		}
898 	}
899 }
900 
901 inline void PassUtil::parseRegexListOpt(std::vector<Regex*> &list, const std::string &string)
902 {
903     std::vector<std::string> stringList;
904     std::vector<std::string>::iterator it;
905     PassUtil::parseStringListOpt(stringList, string);
906 
907     for (it = stringList.begin(); it != stringList.end(); ++it) {
908         Regex* regex = new Regex(*it, 0);
909         std::string error;
910         assert(regex->isValid(error));
911         list.push_back(regex);
912     }
913 }
914 
915 inline bool PassUtil::matchRegexes(std::string string, std::vector<Regex*> &regexes)
916 {
917     for (std::vector<Regex*>::iterator it = regexes.begin(); it != regexes.end(); ++it) {
918     	Regex *regex = *it;
919     	if(regex->match(string, NULL)) {
920     	    return true;
921     	}
922     }
923 
924     return false;
925 }
926 
927 inline void PassUtil::setModule(Module *M)
928 {
929     PassUtil::M = M;
930 }
931 
932 inline void PassUtil::getModuleName(Module &M, std::string *fullName, std::string *dirName, std::string *baseName)
933 {
934     std::string _fullName, _dirName, _baseName;
935     _fullName = M.getModuleIdentifier();
936     SmallVector< StringRef, 8 > vector;
937     StringRef fullNameRef(_fullName);
938     fullNameRef.split(vector, "/", -1, false);
939     if (vector.size() > 1) {
940         _baseName = vector.pop_back_val();
941         for (unsigned i=0;i<vector.size();i++) {
942             _dirName.append("/");
943             _dirName.append(vector[i]);
944         }
945     }
946     else {
947         _baseName = _fullName;
948         _dirName = "/";
949     }
950     vector.clear();
951     StringRef baseNameRef(_baseName);
952     baseNameRef.split(vector, ".", -1, false);
953     if (vector.size() > 1) {
954         _baseName = vector[0];
955     }
956     if (fullName)
957         *fullName = _fullName;
958     if (dirName)
959         *dirName = _dirName;
960     if (baseName)
961         *baseName = _baseName;
962 }
963 
964 inline unsigned long PassUtil::getTypeHash(TYPECONST Type* type, unsigned maxLevel)
965 {
966     static std::vector<TYPECONST Type*> nestedTypes;
967     static unsigned level = 0;
968     static unsigned counter;
969     unsigned long hash = 7;
970     if(level == 0) {
971         counter = 0;
972     }
973     unsigned numContainedTypes = type->getNumContainedTypes();
974     unsigned nestedIndex = 0;
975     for(unsigned i=0;i<nestedTypes.size();i++) {
976         if(type == nestedTypes[i]) {
977             nestedIndex = i+1;
978             break;
979         }
980     }
981     hash = (13*hash) ^ level;
982     hash = (13*hash) ^ counter++;
983     hash = (13*hash) ^ type->getTypeID();
984     hash = (13*hash) ^ nestedIndex;
985     if(TYPECONST IntegerType *intType = dyn_cast<IntegerType>(type)) {
986         hash = (13*hash) ^ intType->getBitWidth();
987     }
988     else if(TYPECONST PointerType *ptrType = dyn_cast<PointerType>(type)) {
989         hash = (13*hash) ^ ptrType->getElementType()->getTypeID();
990     }
991     if(nestedIndex > 0 || level >= maxLevel) {
992         return hash;
993     }
994     if(numContainedTypes == 0) {
995         return hash;
996     }
997     level++;
998     nestedTypes.push_back(type);
999     hash = (13*hash) ^ numContainedTypes;
1000     for(unsigned i=0;i<numContainedTypes;i++) {
1001         hash = (13*hash) ^ getTypeHash(type->getContainedType(i), maxLevel);
1002     }
1003     nestedTypes.pop_back();
1004     level--;
1005 
1006     return hash;
1007 }
1008 
1009 }
1010 
1011 #endif /* _PASS_COMMON_H */
1012