minix/llvm/passes/magic/MagicPass.cpp

   1 #include <magic/MagicPass.h>
   2
   3 using namespace llvm;
   4
   5 PASS_COMMON_INIT_ONCE();
   6
   7 // command-line arguments
   8 static cl::opt<std::string>
   9 DLLFName("magic-dll-function",
  10     cl::desc("Specify the name of the deepest long-lived function whose stack "
  11         "needs to be instrumented"),
  12     cl::init(MAGIC_ENTRY_POINT), cl::NotHidden, cl::ValueRequired);
  13
  14 static cl::opt<std::string>
  15 LibPathRegex("magic-lib-path-regex",
  16     cl::desc("Specify all the colon-separated path regexes that identify directories containing "
  17         "libraries. Deprecated. Use -magic-ext-lib-sections instead."),
  18     cl::init(""), cl::NotHidden, cl::ValueRequired);
  19
  20 static cl::opt<std::string>
  21 VoidTypeAlias("magic-void-alias",
  22     cl::desc("Specify all the colon-separated type names that are to be treated as void, typically "
  23         "used in custom memory management implementations"),
  24     cl::init(""), cl::NotHidden, cl::ValueRequired);
  25
  26 static cl::opt<std::string>
  27 MMFuncPrefix("magic-mmfunc-prefix",
  28     cl::desc("Specify all the colon-separated prefixes that are to be used when extracting "
  29         "memory management functions used in custom memory management implementations"),
  30     cl::init(""), cl::NotHidden, cl::ValueRequired);
  31
  32 static cl::opt<std::string>
  33 MMFuncPair("magic-mmfunc-pair",
  34     cl::desc("Specify all the colon-separated pairs of malloc/free style memory management functions "
  35         "used in custom memory management implementations. Each function is to be listed together "
  36         "with a number indicating which of the input parameters is the one corresponding to its "
  37         "malloc(size)/free(pointer) counterpart. Example: "
  38         "\"my_smart_alloc/3;my_smart_free/3:my_custom_alloc/2;my_custom_free/1\". "
  39         "The counter for arguments starts from 1."),
  40     cl::init(""), cl::NotHidden, cl::ValueRequired);
  41
  42 static cl::opt<std::string>
  43 MMPoolFunc("magic-mm-poolfunc",
  44     cl::desc("Specify a pool memory management set of functions for creating pools, destroying pools, "
  45                 "managing the pool buffers, reseting (reusing) pools and allocating memory blocks from the pool. "
  46                 "All the functions are to be listed together with a number indicating which of the input parameters"
  47                 "(numbering starts at 1) corresponds to the pool object. For the creation function, the pool object "
  48                 "can be the return value (specify 0 for return value). The block allocation function additionally "
  49                 "requires the number of the parameter denoting the size. Separate sets of functions using ':' and "
  50                 "separate multiple functions of the same type using ';'. "
  51                 "Example: \"my_pool_block_alloc/1/2:my_pool_create/0:my_pool_destroy/1:my_pool_alloc/1;"
  52                 "another_pool_alloc/1;my_pool_free/1:my_pool_reset/1\"."
  53                 "If there are no additional management functions, skip them. "
  54                 "Example: \"pool_block_alloc/1/2:pool_create:pool_destroy/1\"."),
  55     cl::init(""), cl::NotHidden, cl::ValueRequired);
  56
  57 static cl::opt<bool>
  58 EnablePoolMemReuse("magic-mpool-enable-reuse",
  59     cl::desc("Enable memory reuse across pools."),
  60     cl::init(false), cl::NotHidden);
  61
  62 static cl::opt<std::string>
  63 MMAPCtlFunction("magic-mmap-ctlfunc",
  64     cl::desc("Specify all the colon-separated mmap control functions that change low-level properties"
  65         "of memory-mapped memory regions taking the start address as an argument"),
  66     cl::init(""), cl::NotHidden, cl::ValueRequired);
  67
  68 static cl::opt<std::string>
  69 MagicDataSections("magic-data-sections",
  70     cl::desc("Specify all the colon-separated magic data section regexes not to instrument"),
  71     cl::init("^" MAGIC_STATIC_VARS_SECTION_PREFIX ".*$:^" UNBL_SECTION_PREFIX ".*$"), cl::NotHidden, cl::ValueRequired);
  72
  73 static cl::opt<std::string>
  74 MagicFunctionSections("magic-function-sections",
  75     cl::desc("Specify all the colon-separated magic function section regexes not to instrument"),
  76     cl::init("^" MAGIC_STATIC_FUNCTIONS_SECTION ".*$:^" UNBL_SECTION_PREFIX ".*$"), cl::NotHidden, cl::ValueRequired);
  77
  78 static cl::opt<std::string>
  79 ExtLibSections("magic-ext-lib-sections",
  80     cl::desc("Specify all the colon-separated external lib section regexes"),
  81     cl::init(MAGIC_DEFAULT_EXT_LIB_SECTION_REGEX), cl::NotHidden, cl::ValueRequired);
  82
  83 static cl::opt<std::string>
  84 baseBuildDir("magic-base-build-dir",
  85     cl::desc("Specify the base build directory from which the pass derives relative directories for debug symbols"),
  86     cl::init(""), cl::NotHidden, cl::ValueRequired);
  87
  88 static cl::opt<bool>
  89 EnableShadowing("magic-enable-shadowing",
  90     cl::desc("Enable state shadowing"),
  91     cl::init(false), cl::NotHidden);
  92
  93 static cl::opt<bool>
  94 DisableMemFunctions("magic-disable-mem-functions",
  95     cl::desc("Disable hooking of memory functions"),
  96     cl::init(false), cl::NotHidden);
  97
  98 static cl::opt<bool>
  99 DisableMallocSkip("magic-disable-malloc-skip",
 100     cl::desc("Disable ignoring malloc data variables"),
 101     cl::init(false), cl::NotHidden);
 102
 103 static cl::opt<bool>
 104 SkipAll("magic-skip-all",
 105     cl::desc("Exit immediately"),
 106     cl::init(false), cl::NotHidden);
 107
 108 #if MAGIC_USE_QPROF_INSTRUMENTATION
 109 QPROF_DECLARE_ALL_OPTS(magic,
 110     magicLLSitestacks,
 111     magicDeepestLLLoops,
 112     magicDeepestLLLibs,
 113     magicTaskClasses
 114 );
 115 #endif
 116
 117 #define DEBUG_TYPE_INFOS            0
 118 #define DEBUG_FILL_TYPE_INFOS       0
 119 #define DEBUG_FILL_EXT_TYPE_INFOS   0
 120 #define DEBUG_ALLOC_LEVEL           0
 121 #define DEBUG_ALLOC_BAD_TYPES       0
 122 #define DEBUG_CASTS                 0
 123 #define DEBUG_DUPLICATED_TYPE_INFOS 0
 124 #define DEBUG_VALUE_SET             0
 125 #define DEBUG_QPROF                 0
 126
 127 namespace llvm {
 128
 129 //===----------------------------------------------------------------------===//
 130 // Constructors, destructor, and operators
 131 //===----------------------------------------------------------------------===//
 132
 133 MagicPass::MagicPass() : ModulePass(ID) {}
 134
 135 unsigned TypeInfo::maxNameLength = 0;
 136 unsigned TypeInfo::maxTypeStringLength = 0;
 137 std::map<TYPECONST Type*, std::set<int> > TypeInfo::intCastTypes;
 138 std::map<TYPECONST Type*, std::set<TYPECONST Type*> > TypeInfo::bitCastTypes;
 139 std::map<TYPECONST Type*, std::set<TypeInfo*> > TypeInfo::typeMap;
 140
 141 bool SmartType::forceRawUnions = MAGIC_FORCE_RAW_UNIONS;
 142 bool SmartType::forceRawBitfields = MAGIC_FORCE_RAW_BITFIELDS;
 143
 144 Function *MagicMemFunction::lastAllocWrapper = NULL;
 145 std::map<std::string, Function*> MagicMemFunction::allocWrapperCache;
 146 std::set<Function*> MagicMemFunction::customWrapperSet;
 147
 148 //===----------------------------------------------------------------------===//
 149 // Public methods
 150 //===----------------------------------------------------------------------===//
 151
 152 bool MagicPass::runOnModule(Module &M) {
 153     unsigned i;
 154
 155     if (SkipAll) {
 156         return false;
 157     }
 158
 159     magicPassLog("Running...");
 160     EDIType::setModule(&M);
 161     PassUtil::setModule(&M);
 162
 163     // initialize qprof instrumentation
 164     qprofInstrumentationInit(M);
 165
 166     //look up magic entry point function
 167     Function *magicEntryPointFunc = M.getFunction(MAGIC_ENTRY_POINT);
 168     if( !magicEntryPointFunc ){
 169         //if no valid entry point, we are not compiling a valid program, skip pass
 170         magicPassLog("Error: no " << MAGIC_ENTRY_POINT << "() found");
 171         return false;
 172     }
 173
 174     //look up magic enabled variable
 175     GlobalVariable* magicEnabled = M.getNamedGlobal(MAGIC_ENABLED);
 176     if(!magicEnabled) {
 177         magicPassErr("Error: no " << MAGIC_ENABLED << " variable found");
 178         exit(1);
 179     }
 180
 181     //look up magic root variable
 182     GlobalVariable* magicRootVar = M.getNamedGlobal(MAGIC_ROOT_VAR_NAME);
 183     if(!magicRootVar) {
 184         magicPassErr("Error: no " << MAGIC_ROOT_VAR_NAME << " variable found");
 185         exit(1);
 186     }
 187
 188     //look up magic data init function and get the last instruction to add stuff in it
 189     Function *magicDataInitFunc = M.getFunction(MAGIC_DATA_INIT_FUNC_NAME);
 190     if(!magicDataInitFunc){
 191         magicPassErr("Error: no " << MAGIC_DATA_INIT_FUNC_NAME << "() found");
 192         exit(1);
 193     }
 194     Instruction *magicArrayBuildFuncInst = magicDataInitFunc->back().getTerminator();
 195
 196     //look up pointer to magic memory instrumentation flag
 197     Value* magicNoMemInst = MagicUtil::getMagicRStructFieldPtr(M, magicArrayBuildFuncInst, magicRootVar, MAGIC_RSTRUCT_FIELD_NO_MEM_INST);
 198     if(!magicNoMemInst) {
 199         magicPassErr("Error: no " << MAGIC_RSTRUCT_FIELD_NO_MEM_INST << " field found");
 200         exit(1);
 201     }
 202
 203     //look up pointer to magic array and magic struct type
 204     Value* magicArrayPtr = MagicUtil::getMagicRStructFieldPtr(M, magicArrayBuildFuncInst, magicRootVar, MAGIC_RSTRUCT_FIELD_SENTRIES);
 205     if(!magicArrayPtr) {
 206         magicPassErr("Error: no " << MAGIC_RSTRUCT_FIELD_SENTRIES << " field found");
 207         exit(1);
 208     }
 209     TYPECONST StructType* magicStructType = (TYPECONST StructType*) ((TYPECONST PointerType*)((TYPECONST PointerType*)magicArrayPtr->getType())->getElementType())->getElementType();
 210
 211     //look up pointer to magic array size
 212     Value *magicArraySize = MagicUtil::getMagicRStructFieldPtr(M, magicArrayBuildFuncInst, magicRootVar, MAGIC_RSTRUCT_FIELD_SENTRIES_NUM);
 213     if(!magicArraySize) {
 214         magicPassErr("Error: no " << MAGIC_RSTRUCT_FIELD_SENTRIES_NUM << " field found");
 215         exit(1);
 216     }
 217
 218     //look up pointer to magic array string size
 219     Value *magicArrayStrSize = MagicUtil::getMagicRStructFieldPtr(M, magicArrayBuildFuncInst, magicRootVar, MAGIC_RSTRUCT_FIELD_SENTRIES_STR_NUM);
 220     if(!magicArrayStrSize) {
 221         magicPassErr("Error: no " << MAGIC_RSTRUCT_FIELD_SENTRIES_STR_NUM << " field found");
 222         exit(1);
 223     }
 224
 225     //look up pointer to magic next id
 226     Value *magicNextId = MagicUtil::getMagicRStructFieldPtr(M, magicArrayBuildFuncInst, magicRootVar, MAGIC_RSTRUCT_FIELD_SENTRIES_NEXT_ID);
 227     if(!magicNextId) {
 228         magicPassErr("Error: no " << MAGIC_RSTRUCT_FIELD_SENTRIES_NEXT_ID << " field found");
 229         exit(1);
 230     }
 231
 232     //look up pointer to magic dsindex array and magic dsindex struct type
 233     Value* magicDsindexArrayPtr = MagicUtil::getMagicRStructFieldPtr(M, magicArrayBuildFuncInst, magicRootVar, MAGIC_RSTRUCT_FIELD_DSINDEXES);
 234     if(!magicDsindexArrayPtr) {
 235         magicPassErr("Error: no " << MAGIC_RSTRUCT_FIELD_DSINDEXES << " field found");
 236         exit(1);
 237     }
 238     TYPECONST StructType* magicDsindexStructType = (TYPECONST StructType*) ((TYPECONST PointerType*)((TYPECONST PointerType*)magicDsindexArrayPtr->getType())->getElementType())->getElementType();
 239
 240     //look up pointer to magic dsindex array size
 241     Value *magicDsindexArraySize = MagicUtil::getMagicRStructFieldPtr(M, magicArrayBuildFuncInst, magicRootVar, MAGIC_RSTRUCT_FIELD_DSINDEXES_NUM);
 242     if(!magicDsindexArraySize) {
 243         magicPassErr("Error: no " << MAGIC_RSTRUCT_FIELD_DSINDEXES_NUM << " field found");
 244         exit(1);
 245     }
 246
 247     //look up pointer to magic type array and magic type struct type
 248     Value *magicTypeArrayPtr = MagicUtil::getMagicRStructFieldPtr(M, magicArrayBuildFuncInst, magicRootVar, MAGIC_RSTRUCT_FIELD_TYPES);
 249     if(!magicTypeArrayPtr) {
 250         magicPassErr("Error: no " << MAGIC_RSTRUCT_FIELD_TYPES << " field found");
 251         exit(1);
 252     }
 253     TYPECONST StructType* magicTypeStructType = (TYPECONST StructType*) ((TYPECONST PointerType*)((TYPECONST PointerType*)magicTypeArrayPtr->getType())->getElementType())->getElementType();
 254
 255     //look up pointer to magic type array size
 256     Value *magicTypeArraySize = MagicUtil::getMagicRStructFieldPtr(M, magicArrayBuildFuncInst, magicRootVar, MAGIC_RSTRUCT_FIELD_TYPES_NUM);
 257     if(!magicTypeArraySize) {
 258         magicPassErr("Error: no " << MAGIC_RSTRUCT_FIELD_TYPES_NUM << " field found");
 259         exit(1);
 260     }
 261
 262     //look up pointer to magic type next id
 263     Value *magicTypeNextId = MagicUtil::getMagicRStructFieldPtr(M, magicArrayBuildFuncInst, magicRootVar, MAGIC_RSTRUCT_FIELD_TYPES_NEXT_ID);
 264     if(!magicTypeNextId) {
 265         magicPassErr("Error: no " << MAGIC_RSTRUCT_FIELD_TYPES_NEXT_ID << " field found");
 266         exit(1);
 267     }
 268
 269     //look up pointer to magic function array and magic function struct type
 270     Value *magicFunctionArrayPtr = MagicUtil::getMagicRStructFieldPtr(M, magicArrayBuildFuncInst, magicRootVar, MAGIC_RSTRUCT_FIELD_FUNCTIONS);
 271     if(!magicFunctionArrayPtr) {
 272         magicPassErr("Error: no " << MAGIC_RSTRUCT_FIELD_FUNCTIONS << " field found");
 273         exit(1);
 274     }
 275     TYPECONST StructType* magicFunctionStructType = (TYPECONST StructType*) ((TYPECONST PointerType*)((TYPECONST PointerType*)magicFunctionArrayPtr->getType())->getElementType())->getElementType();
 276
 277     //look up pointer to magic function array size
 278     Value *magicFunctionArraySize = MagicUtil::getMagicRStructFieldPtr(M, magicArrayBuildFuncInst, magicRootVar, MAGIC_RSTRUCT_FIELD_FUNCTIONS_NUM);
 279     if(!magicFunctionArraySize) {
 280         magicPassErr("Error: no " << MAGIC_RSTRUCT_FIELD_FUNCTIONS_NUM << " field found");
 281         exit(1);
 282     }
 283
 284     //look up pointer to magic function next id
 285     Value *magicFunctionNextId = MagicUtil::getMagicRStructFieldPtr(M, magicArrayBuildFuncInst, magicRootVar, MAGIC_RSTRUCT_FIELD_FUNCTIONS_NEXT_ID);
 286     if(!magicFunctionNextId) {
 287         magicPassErr("Error: no " << MAGIC_RSTRUCT_FIELD_FUNCTIONS_NEXT_ID << " field found");
 288         exit(1);
 289     }
 290
 291     //look up magic dsentry struct type
 292     Value *magicFirstDsentyPtr = MagicUtil::getMagicRStructFieldPtr(M, magicArrayBuildFuncInst, magicRootVar, MAGIC_RSTRUCT_FIELD_FIRST_DSENTRY);
 293     if(!magicFirstDsentyPtr) {
 294         magicPassErr("Error: no " << MAGIC_RSTRUCT_FIELD_FIRST_DSENTRY << " field found");
 295         exit(1);
 296     }
 297     TYPECONST StructType* magicDsentryStructType = (TYPECONST StructType*) ((TYPECONST PointerType*)((TYPECONST PointerType*)magicFirstDsentyPtr->getType())->getElementType())->getElementType();
 298
 299     //look up magic init function
 300     Function *magicInitFunc = M.getFunction(MAGIC_INIT_FUNC_NAME);
 301     if( !magicInitFunc ){
 302         magicPassErr("Error: no " << MAGIC_INIT_FUNC_NAME << "() found");
 303         exit(1);
 304     }
 305
 306     //look up magic dsentry stack functions
 307     Function *magicStackDsentryCreateFunc = M.getFunction(MAGIC_STACK_DSENTRIES_CREATE_FUNC_NAME);
 308     if (!magicStackDsentryCreateFunc) {
 309         magicPassErr("Error: no " << MAGIC_STACK_DSENTRIES_CREATE_FUNC_NAME << "() found");
 310         exit(1);
 311     }
 312     Function *magicStackDsentryDestroyFunc = M.getFunction(MAGIC_STACK_DSENTRIES_DESTROY_FUNC_NAME);
 313     if (!magicStackDsentryDestroyFunc) {
 314         magicPassErr("Error: no " << MAGIC_STACK_DSENTRIES_DESTROY_FUNC_NAME << "() found");
 315         exit(1);
 316     }
 317
 318     //look up deepest long-lived function
 319     Function *deepestLLFunction = M.getFunction(DLLFName);
 320     if (!deepestLLFunction) {
 321         magicPassErr("Error: no " << DLLFName << "() found");
 322         exit(1);
 323     }
 324
 325     //lookup magic get page size function
 326     Function *magicGetPageSizeFunc = M.getFunction(MAGIC_GET_PAGE_SIZE_FUNC_NAME);
 327     if(!magicGetPageSizeFunc){
 328         magicPassErr("Error: no " << MAGIC_GET_PAGE_SIZE_FUNC_NAME << "() found");
 329         exit(1);
 330     }
 331
 332     //look up magic void pointer
 333     GlobalVariable *magicVoidPtr = M.getNamedGlobal(MAGIC_VOID_PTR_NAME);
 334     if(!magicVoidPtr) {
 335         magicPassErr("Error: no " << MAGIC_VOID_PTR_NAME << "variable found");
 336         exit(1);
 337     }
 338     assert(!isMagicGV(M, magicVoidPtr));
 339
 340     //look up magic void array
 341     GlobalVariable *magicVoidArr = M.getNamedGlobal(MAGIC_VOID_ARRAY_NAME);
 342     if(!magicVoidArr) {
 343         magicPassErr("Error: no " << MAGIC_VOID_ARRAY_NAME << "variable found");
 344         exit(1);
 345     }
 346     assert(!isMagicGV(M, magicVoidArr));
 347
 348     //look up magic void * type pointer
 349     GlobalVariable *magicVoidPtrTypePtr = M.getNamedGlobal(MAGIC_VOID_PTR_TYPE_PTR_NAME);
 350     if(!magicVoidPtrTypePtr) {
 351         magicPassErr("Error: no " << MAGIC_VOID_PTR_TYPE_PTR_NAME << "variable found");
 352         exit(1);
 353     }
 354
 355     //determine lib path regexes
 356     PassUtil::parseStringListOpt(libPathRegexes, LibPathRegex);
 357
 358     //determine void type aliases
 359     PassUtil::parseStringListOpt(voidTypeAliases, VoidTypeAlias);
 360     std::copy( voidTypeAliases.begin(), voidTypeAliases.end(), std::inserter( voidTypeAliasesSet, voidTypeAliasesSet.end() ) );
 361
 362     //determine mm function prefixes
 363     PassUtil::parseStringListOpt(mmFuncPrefixes, MMFuncPrefix);
 364
 365     //determine custom malloc/free style custom mm functions
 366     PassUtil::parseStringPairListOpt(mmFuncPairs, MMFuncPair);
 367
 368     //determine the pool management sets of functions
 369     PassUtil::parseStringListOpt(mmPoolFunctions, MMPoolFunc);
 370
 371     //determine mmap ctl functions
 372     PassUtil::parseStringListOpt(mmapCtlFunctions, MMAPCtlFunction);
 373
 374     //determine magic data section regexes
 375     std::string DataSections = MagicDataSections;
 376     if (!DisableMallocSkip)
 377         DataSections += ":^" MAGIC_MALLOC_VARS_SECTION_PREFIX ".*$";
 378     PassUtil::parseRegexListOpt(magicDataSectionRegexes, DataSections);
 379
 380     //determine magic function section regexes
 381     PassUtil::parseRegexListOpt(magicFunctionSectionRegexes, MagicFunctionSections);
 382
 383     //determine magic ext lib section regexes
 384     PassUtil::parseRegexListOpt(extLibSectionRegexes, ExtLibSections);
 385
 386     //look up inttoptr type casts
 387     Module::GlobalListType &globalList = M.getGlobalList();
 388     Module::FunctionListType &functionList = M.getFunctionList();
 389     std::vector<TYPECONST Type*> intCastTypes;
 390     std::vector<int> intCastValues;
 391     std::map<TYPECONST Type*, std::set<TYPECONST Type*> > bitCastMap;
 392     for (Module::iterator it = functionList.begin(); it != functionList.end(); ++it) {
 393         Function *F = it;
 394         if(isMagicFunction(M, F)) {
 395             continue;
 396         }
 397         for (inst_iterator I2 = inst_begin(F), E2 = inst_end(F); I2 != E2; ++I2) {
 398             indexCasts(M, &(*I2), intCastTypes, intCastValues, bitCastMap);
 399         }
 400     }
 401     for (Module::global_iterator it = globalList.begin(); it != globalList.end(); ++it) {
 402         GlobalVariable *GV = it;
 403         StringRef GVName = GV->getName();
 404         if(isMagicGV(M, GV) || GVName.startswith(".str") || GVName.startswith(".arr") || GVName.startswith("C.")) {
 405             continue;
 406         }
 407         if(GV->hasInitializer()) {
 408             indexCasts(M, GV->getInitializer(), intCastTypes, intCastValues, bitCastMap);
 409         }
 410     }
 411
 412     //index and set cast maps
 413     std::map<TYPECONST Type*, std::set<int> > intCastMap;
 414     std::map<TYPECONST Type*, std::set<int> >::iterator intCastMapIt;
 415     for(i=0;i<intCastTypes.size();i++) {
 416         TYPECONST Type* type = intCastTypes[i];
 417         int value = intCastValues[i];
 418         intCastMapIt = intCastMap.find(type);
 419         if(intCastMapIt == intCastMap.end()) {
 420             std::set<int> valueSet;
 421             intCastMap.insert(std::pair<TYPECONST Type*, std::set<int> >(type, valueSet));
 422             intCastMapIt = intCastMap.find(type);
 423         }
 424         assert(intCastMapIt != intCastMap.end());
 425         std::set<int> *setPtr = &(intCastMapIt->second);
 426         if(setPtr->size() == 1 && *(setPtr->begin()) == 0) {
 427             continue;
 428         }
 429         if(value == 0) {
 430             setPtr->clear();
 431         }
 432         setPtr->insert(value);
 433     }
 434     TypeInfo::setIntCastTypes(intCastMap);
 435     TypeInfo::setBitCastTypes(bitCastMap);
 436
 437 #if MAGIC_INSTRUMENT_MEM_FUNCS
 438     std::vector<MagicMemFunction> magicMemFunctions;
 439     std::set<Function*> originalMagicMemFunctions;
 440     std::vector<MagicDebugFunction> magicDebugFunctions;
 441     std::vector<MagicMmapCtlFunction> magicMmapCtlFunctions;
 442     if (!DisableMemFunctions) {
 443         //look up magic memory functions and corresponding wrappers
 444         #define __X(P) #P
 445         std::string magicMemFuncNames[] = { MAGIC_MEM_FUNC_NAMES };
 446         std::string magicMemDeallocFuncNames[] = { MAGIC_MEMD_FUNC_NAMES };
 447         std::string magicMemNestedFuncNames[] = { MAGIC_MEMN_FUNC_NAMES };
 448         #undef __X
 449         int magicMemFuncAllocFlags[] = { MAGIC_MEM_FUNC_ALLOC_FLAGS };
 450         std::string magicMemPrefixes[] = { MAGIC_MEM_PREFIX_STRS };
 451         std::vector<std::string> llvmCallPrefixes;
 452         for (std::vector<std::string>::iterator it = mmFuncPrefixes.begin(); it != mmFuncPrefixes.end(); ++it) {
 453             llvmCallPrefixes.push_back(*it);
 454         }
 455         llvmCallPrefixes.push_back("");
 456         llvmCallPrefixes.push_back("\01"); //llvm uses odd prefixes for some functions, sometimes (e.g. mmap64)
 457         for(i=0;magicMemFuncNames[i].compare("");i++) {
 458             int allocFlags = magicMemFuncAllocFlags[i];
 459             for(unsigned j=0;j<llvmCallPrefixes.size();j++) {
 460                 std::string fName = magicMemFuncNames[i];
 461                 Function *f = M.getFunction(llvmCallPrefixes[j] + fName);
 462                 if(!f) {
 463                     continue;
 464                 }
 465                 TYPECONST FunctionType *fType = f->getFunctionType();
 466                 if(fType->getNumParams() == 0 && fType->isVarArg()) {
 467                     //missing function prototype, i.e. no realistic caller. Skip.
 468                     continue;
 469                 }
 470                 if(!fName.compare("brk")) {
 471                     brkFunctions.insert(f);
 472                 }
 473                 if(!fName.compare("sbrk")) {
 474                     sbrkFunctions.insert(f);
 475                 }
 476                 bool isDeallocFunction = false;
 477                 for(unsigned k=0;magicMemDeallocFuncNames[k].compare("");k++) {
 478                     if(!magicMemDeallocFuncNames[k].compare(fName)) {
 479                         isDeallocFunction = true;
 480                         break;
 481                     }
 482                 }
 483                 bool makeNestedFunction = false;
 484                 for(unsigned k=0;magicMemNestedFuncNames[k].compare("");k++) {
 485                     if (!magicMemNestedFuncNames[k].compare(fName)) {
 486                         makeNestedFunction = true;
 487                         break;
 488                     }
 489                 }
 490
 491                 Function* w = findWrapper(M, magicMemPrefixes, f, fName);
 492                 MagicMemFunction memFunction(M, f, w, isDeallocFunction, false, allocFlags);
 493                 magicMemFunctions.push_back(memFunction);
 494                 if (makeNestedFunction) {
 495                     w = findWrapper(M, magicMemPrefixes, f, MAGIC_NESTED_PREFIX_STR + fName);
 496                     MagicMemFunction memFunction(M, f, w, isDeallocFunction, true, allocFlags);
 497                     magicMemFunctions.push_back(memFunction);
 498                 }
 499                 originalMagicMemFunctions.insert(f);
 500
 501 #if DEBUG_ALLOC_LEVEL >= 1
 502                 magicPassErr("Memory management function/wrapper found: " << f->getName() << "()/" << w->getName() << "()");
 503 #endif
 504             }
 505         }
 506
 507         //look up custom memory management functions and build the corresponding wrappers
 508         int stdAllocFlags = 0;
 509         Function *stdAllocFunc, *stdAllocWrapperFunc;
 510         stdAllocFunc = M.getFunction(MAGIC_MALLOC_FUNC_NAME);
 511         assert(stdAllocFunc && "Could not find the standard allocation function.");
 512         for(i=0;magicMemFuncNames[i].compare("");i++) {
 513             if (!magicMemFuncNames[i].compare(MAGIC_MALLOC_FUNC_NAME)) {
 514                 stdAllocFlags = magicMemFuncAllocFlags[i];
 515                 break;
 516             }
 517         }
 518         assert(magicMemFuncNames[i].compare("") && "Could not find the flags for the standard allocation function.");
 519         std::string wName;
 520         for(i=0;magicMemPrefixes[i].compare("");i++) {
 521             wName = magicMemPrefixes[i] + MAGIC_MALLOC_FUNC_NAME;
 522             stdAllocWrapperFunc = M.getFunction(wName);
 523             if (stdAllocWrapperFunc) {
 524                 break;
 525             }
 526         }
 527         assert(stdAllocWrapperFunc && "Could not find a wrapper for the standard allocation function.");
 528         for (std::set<std::pair<std::string, std::string> >::iterator it = mmFuncPairs.begin(); it != mmFuncPairs.end(); ++it) {
 529             std::vector<std::string> allocTokens;
 530             PassUtil::parseStringListOpt(allocTokens, (*it).first, "/");
 531                     assert((allocTokens.size() == stdAllocFunc->getFunctionType()->getNumParams() + 1) && "Bad option format, format is: customFuncName/stdFuncArg1Mapping/.../stdFuncArgNMapping");
 532
 533                     // build custom wrapper for the allocation function
 534                     Function *allocFunction = MagicUtil::getFunction(M, allocTokens[0]);
 535                     if (!allocFunction) {
 536                             continue;
 537                     }
 538                     std::vector<unsigned> allocArgMapping;
 539                     int param;
 540                     for (unsigned i = 0; i < stdAllocFunc->getFunctionType()->getNumParams(); i++) {
 541                             int ret = StringRef(allocTokens[i + 1]).getAsInteger(10, param);
 542                             assert(!ret && "Bad option format, format is: customFuncName/stdFuncArg1Mapping/.../stdFuncArgNMapping");
 543                             assert(param > 0 && "The numbering of function parameters starts from 1.");
 544                             allocArgMapping.push_back(param);
 545                     }
 546                     FunctionType *allocFuncType = getFunctionType(allocFunction->getFunctionType(), allocArgMapping);
 547                     if(!isCompatibleMagicMemFuncType(allocFuncType, stdAllocWrapperFunc->getFunctionType())) {
 548                             magicPassErr("Error: standard wrapper function " << stdAllocWrapperFunc->getName() << " has incompatible type.");
 549                             magicPassErr(TypeUtil::getDescription(allocFuncType, MAGIC_TYPE_STR_PRINT_MAX, MAGIC_TYPE_STR_PRINT_MAX_LEVEL) << " != " << TypeUtil::getDescription(stdAllocWrapperFunc->getFunctionType(), MAGIC_TYPE_STR_PRINT_MAX, MAGIC_TYPE_STR_PRINT_MAX_LEVEL));
 550                             exit(1);
 551                     }
 552                     Function *allocWrapper = MagicMemFunction::getCustomWrapper(allocFunction, stdAllocFunc, stdAllocWrapperFunc, allocArgMapping, false);
 553
 554                     // register the wrapper
 555                     MagicMemFunction memFunctionAlloc(M, allocFunction, allocWrapper, false, false, stdAllocFlags);
 556                     magicMemFunctions.push_back(memFunctionAlloc);
 557                     originalMagicMemFunctions.insert(allocFunction);
 558 #if DEBUG_ALLOC_LEVEL >= 1
 559             magicPassErr("Allocation function/custom wrapper added: " << allocFunction->getName() << "()/" << allocWrapper->getName() << "()");
 560 #endif
 561         }
 562
 563         //lookup memory pool management functions and add the corresponding wrapper calls
 564         int mempoolAllocFlags = MAGIC_STATE_HEAP;
 565             Function *mempoolBlockAllocTemplate, *mempoolBlockAllocTemplateWrapper;
 566             mempoolBlockAllocTemplate = MagicUtil::getFunction(M,  MAGIC_MEMPOOL_BLOCK_ALLOC_TEMPLATE_FUNC_NAME);
 567             assert(mempoolBlockAllocTemplate && "Could not find the pool block allocation template function.");
 568             for(i = 0; magicMemPrefixes[i].compare(""); i++) {
 569                     wName = magicMemPrefixes[i] + MAGIC_MEMPOOL_BLOCK_ALLOC_TEMPLATE_FUNC_NAME;
 570                     mempoolBlockAllocTemplateWrapper = MagicUtil::getFunction(M, wName);
 571                     if (mempoolBlockAllocTemplateWrapper) {
 572                             break;
 573                     }
 574             }
 575             assert(mempoolBlockAllocTemplateWrapper && "Could not find a wrapper for the pool block allocation template function.");
 576 #define __X(P) #P
 577         // C++11 Initializer Lists are not yet supported as of Clang 3.0 ...
 578         std::pair<std::string, std::string> magicMempoolFuncNames[] = {
 579                     std::pair<std::string, std::string>(MAGIC_MEMPOOL_CREATE_FUNCS),
 580                     std::pair<std::string, std::string>(MAGIC_MEMPOOL_DESTROY_FUNCS),
 581                     std::pair<std::string, std::string>(MAGIC_MEMPOOL_MGMT_FUNCS),
 582                     std::pair<std::string, std::string>(MAGIC_MEMPOOL_RESET_FUNCS)
 583         };
 584 #undef __X
 585         int magicMempoolFuncFlags[] = { MAGIC_MEMPOOL_FUNC_FLAGS };
 586         unsigned numMagicMempoolFuncPairs = sizeof(magicMempoolFuncNames) / sizeof(magicMempoolFuncNames[0]);
 587         std::vector<std::pair<Function*, Function*> > magicMempoolFuncs(numMagicMempoolFuncPairs, std::pair<Function*, Function*>());
 588         for (i = 0; i < numMagicMempoolFuncPairs; i++) {
 589             magicMempoolFuncs[i].first = MagicUtil::getFunction(M, magicMempoolFuncNames[i].first);
 590             if (!magicMempoolFuncs[i].first) {
 591                             magicPassErr("Could not find one of the memory pool wrapper functions: " + magicMempoolFuncNames[i].first);
 592                             exit(1);
 593                     }
 594             magicMempoolFuncs[i].second = MagicUtil::getFunction(M, magicMempoolFuncNames[i].second);
 595             if (!magicMempoolFuncs[i].second) {
 596                             magicPassErr("Could not find one of the memory pool wrapper functions: " + magicMempoolFuncNames[i].second);
 597                             exit(1);
 598                     }
 599         }
 600
 601         if (mmPoolFunctions.size()) {
 602                     assert(mmPoolFunctions.size() >= 3 && mmPoolFunctions.size() <= 5 &&
 603                                                     "Specify at least 3 and at most 5 of the pool management types of functions: block alloc,pool create,pool destroy,pool management functions,pool reset functions.");
 604                     std::vector<std::string>::iterator mmPoolFuncsIt = mmPoolFunctions.begin();
 605                     std::vector<MagicMemFunction> mempoolMagicMemFunctions;
 606
 607                     // memory pool block allocation functions
 608                     std::vector<std::string> mempoolBlockAllocFuncs;
 609                     PassUtil::parseStringListOpt(mempoolBlockAllocFuncs, *(mmPoolFuncsIt++), ";");
 610
 611                     for (std::vector<std::string>::iterator funcIt = mempoolBlockAllocFuncs.begin(); funcIt != mempoolBlockAllocFuncs.end(); ++funcIt) {
 612                             std::vector<std::string> funcTokens;
 613                             PassUtil::parseStringListOpt(funcTokens, *funcIt, "/");
 614                             assert(funcTokens.size() == 3 && "Bad option format, format is: block_alloc_func/pool_ptr_arg_number/size_arg_number");
 615                             Function* blockAllocFunc = MagicUtil::getFunction(M, funcTokens[0]);
 616                             if (!blockAllocFunc) {
 617                                 magicPassErr("Memory pool block allocation function not found - " + funcTokens[0] + ". Skipping instrumentation!");
 618                                 mempoolMagicMemFunctions.clear();
 619                                 break;
 620                             }
 621                             std::vector<unsigned> argMapping;
 622                             unsigned param;
 623                             for (unsigned i = 1; i < funcTokens.size(); i++) {
 624                                     assert(!StringRef(funcTokens[i]).getAsInteger(10, param) && "Bad option format, format is: block_alloc_func/pool_ptr_arg_number/size_arg_number");
 625                                     assert(param > 0 && param <= blockAllocFunc->getFunctionType()->getNumParams()
 626                                                     && "Bad option format. The function parameter number is not valid.");
 627                                     argMapping.push_back(param);
 628                             }
 629                             FunctionType *blockAllocFuncType = getFunctionType(mempoolBlockAllocTemplate->getFunctionType(), argMapping);
 630                             if(!isCompatibleMagicMemFuncType(blockAllocFuncType, mempoolBlockAllocTemplateWrapper->getFunctionType())) {
 631                                     magicPassErr("Error: standard wrapper function " << mempoolBlockAllocTemplateWrapper->getName() << " has incompatible type.");
 632                                     magicPassErr(TypeUtil::getDescription(blockAllocFuncType, MAGIC_TYPE_STR_PRINT_MAX, MAGIC_TYPE_STR_PRINT_MAX_LEVEL) << " != " << TypeUtil::getDescription(mempoolBlockAllocTemplateWrapper->getFunctionType(), MAGIC_TYPE_STR_PRINT_MAX, MAGIC_TYPE_STR_PRINT_MAX_LEVEL));
 633                                     exit(1);
 634                             }
 635                             Function *blockAllocWrapper = MagicMemFunction::getCustomWrapper(blockAllocFunc, mempoolBlockAllocTemplate, mempoolBlockAllocTemplateWrapper, argMapping, false);
 636                             MagicMemFunction memFunctionBlockAlloc(M, blockAllocFunc, blockAllocWrapper, false, false, mempoolAllocFlags);
 637                             mempoolMagicMemFunctions.push_back(memFunctionBlockAlloc);
 638                     }
 639                     if (!mempoolMagicMemFunctions.empty()) { // only if the block allocation functions have been successfully processed
 640                             // continue with the rest of the memory pool management functions, which do not require a magic wrapper
 641                             std::vector<std::vector<Function*> >::iterator magicMempoolFuncIt;
 642                             std::vector<std::vector<int> >::iterator magicMempoolFuncFlagsIt;
 643                             for (unsigned magicMempoolFuncIndex = 1; mmPoolFuncsIt != mmPoolFunctions.end(); ++mmPoolFuncsIt, ++magicMempoolFuncIndex) {
 644                                     std::vector<std::string> mempoolMgmtFuncs;
 645                                     PassUtil::parseStringListOpt(mempoolMgmtFuncs, *mmPoolFuncsIt, ";");
 646                                     for (std::vector<std::string>::iterator funcIt = mempoolMgmtFuncs.begin(); funcIt != mempoolMgmtFuncs.end(); ++funcIt) {
 647                                             std::vector<std::string> funcTokens;
 648                                             PassUtil::parseStringListOpt(funcTokens, *funcIt, "/");
 649                                             assert(funcTokens.size() == 2 && "Bad option format, format is: mempool_mgmt_func/pool_ptr_arg_number");
 650                                             Function* mempoolMgmtFunc = MagicUtil::getFunction(M, funcTokens[0]);
 651                                             assert(mempoolMgmtFunc && "Bad memory pool configuration, instrumentation aborted!");
 652                                             std::vector<unsigned> argMapping;
 653                                             unsigned param;
 654                                             for (unsigned i = 1; i < funcTokens.size(); i++) {
 655                                                     assert(!StringRef(funcTokens[i]).getAsInteger(10, param) && "Bad option format, format is: mempool_mgmt_func/pool_ptr_arg_number");
 656                                                     assert(param <= mempoolMgmtFunc->getFunctionType()->getNumParams() &&
 657                                                                     "Bad option format. The function parameter number is not valid.");
 658                                                     argMapping.push_back(param);
 659                                             }
 660                                             std::vector<Value*> trailingArgs;
 661                                             if (magicMempoolFuncIndex == 1) { // pool create funcs
 662                                                     TYPECONST Type* poolType = mempoolMgmtFunc->getFunctionType()->getContainedType(argMapping[0]);
 663                                                     int level = MagicUtil::getPointerIndirectionLevel(poolType);
 664                                                     trailingArgs.push_back(ConstantInt::get(Type::getInt32Ty(M.getContext()), (level > 1)));
 665                                             } else if (magicMempoolFuncIndex == 2) { // pool destroy funcs
 666                                                     trailingArgs.push_back(ConstantInt::get(Type::getInt32Ty(M.getContext()), (EnablePoolMemReuse ? 1 : 0)));
 667                                             }
 668                                             if (magicMempoolFuncFlags[magicMempoolFuncIndex - 1] & MAGIC_HOOK_DEBUG_MASK) {
 669                                                     MagicDebugFunction magicDebugFunction(mempoolMgmtFunc);
 670                                                     magicDebugFunction.addHooks(magicMempoolFuncs[magicMempoolFuncIndex - 1], magicMempoolFuncFlags[magicMempoolFuncIndex - 1], argMapping, trailingArgs);
 671                                                     magicDebugFunctions.push_back(magicDebugFunction);
 672                                             } else {
 673                                                     bool ret = MagicDebugFunction::inlineHookCalls(mempoolMgmtFunc,
 674                                                                     magicMempoolFuncs[magicMempoolFuncIndex - 1], magicMempoolFuncFlags[magicMempoolFuncIndex - 1], argMapping, trailingArgs);
 675                                                     if (!ret) {
 676                                                             magicPassErr("Unable to inline wrapper function calls for " + funcTokens[0]);
 677                                                             exit(1);
 678                                                     }
 679                                             }
 680                                     }
 681                             }
 682                             for (std::vector<MagicMemFunction>::iterator magicIt = mempoolMagicMemFunctions.begin(); magicIt != mempoolMagicMemFunctions.end(); ++magicIt) {
 683                                     magicMemFunctions.push_back(*magicIt);
 684                                     originalMagicMemFunctions.insert(magicIt->getFunction());
 685                             }
 686                     }
 687         }
 688
 689         //lookup mmap ctl functions whose call arguments need to be fixed
 690         for (std::vector<std::string>::iterator it = mmapCtlFunctions.begin(); it != mmapCtlFunctions.end(); ++it) {
 691             std::vector<std::string> tokens;
 692             tokens.clear();
 693             PassUtil::parseStringListOpt(tokens, *it, "/");
 694             assert(tokens.size() == 3 && "Bad option format, format is: function/[ptr_arg_name]/[len_arg_name]");
 695
 696             Function *function = M.getFunction(tokens[0]);
 697             if(!function) {
 698                 continue;
 699             }
 700             std::string &ptrArgName = tokens[1];
 701             std::string &lenArgName = tokens[2];
 702             MagicMmapCtlFunction magicMmapCtlFunction(function, PointerType::get(IntegerType::get(M.getContext(), 8), 0), ptrArgName, lenArgName);
 703             magicMmapCtlFunctions.push_back(magicMmapCtlFunction);
 704         }
 705     }
 706 #endif /*MAGIC_INSTRUMENT_MEM_FUNCS*/
 707
 708     //everything as expected, set magic enabled variable to TRUE
 709     magicEnabled->setInitializer(ConstantInt::get(M.getContext(), APInt(32, 1)));
 710
 711     //scan the list of global variables
 712     unsigned strGlobalVariables = 0;
 713     unsigned constGlobalVariables = 0;
 714     for (Module::global_iterator it = globalList.begin(); it != globalList.end(); ++it) {
 715         GlobalVariable *GV = it;
 716         StringRef GVName = GV->getName();
 717         TYPECONST Type *GVType = GV->getType()->getElementType();
 718         bool isPrimitiveOrPointerType = !GVType->isAggregateType();
 719         DATA_LAYOUT_TY DL = DATA_LAYOUT_TY(&M);
 720         bool isExternal = GV->hasExternalLinkage() || GV->hasExternalWeakLinkage();
 721         int typeSize = isExternal ? 0 : DL.getTypeSizeInBits(GVType)/8;
 722         int align = MAGIC_FORCE_ALIGN;
 723
 724         if(isMagicGV(M, GV)) {
 725             magicPassLog("Skipping magic variable: " << GVName);
 726             continue;
 727         }
 728         assert(!MAGIC_STRINGREF_HAS_MAGIC_HIDDEN_PREFIX(GVName));
 729         if(GVName.startswith("C.")) {
 730             //LLVM code we are not interested in
 731             continue;
 732         }
 733         if(MagicUtil::isLocalConstant(M, GV)) {
 734             //Local constants we are not interested in
 735             continue;
 736         }
 737 #if GLOBAL_VARS_IN_SECTION
 738         MagicUtil::setGlobalVariableSection(GV, GV->isConstant() ? GLOBAL_VARS_SECTION_RO : GLOBAL_VARS_SECTION_DATA);
 739 #endif
 740         if(GVName.startswith(".str")) {
 741             assert(GV->hasInitializer());
 742 #if LLVM_VERSION >= 31
 743             /* XXX Check. */
 744             ConstantDataArray *initializer = dyn_cast<ConstantDataArray>(GV->getInitializer());
 745 #else
 746             ConstantArray *initializer = dyn_cast<ConstantArray>(GV->getInitializer());
 747 #endif
 748             if(initializer) {
 749                 assert(initializer->isString());
 750                 MagicUtil::putStringRefCache(M, initializer->getAsString(), GV);
 751             }
 752             else {
 753                 MagicUtil::putStringRefCache(M, "", GV);
 754             }
 755
 756             strGlobalVariables++;
 757             Value *stringOwner = MagicUtil::getStringOwner(GV);
 758             if(stringOwner) {
 759                 GlobalVariable *GVOwner = dyn_cast<GlobalVariable>(stringOwner);
 760                 AllocaInst *AIOwner = dyn_cast<AllocaInst>(stringOwner);
 761                 assert(GVOwner || AIOwner);
 762                 bool stringOwnerFound = false;
 763                 std::string ownerName;
 764                 raw_string_ostream ostream(ownerName);
 765                 if(GVOwner && !isMagicGV(M, GVOwner)) {
 766                     ostream << "#" << MagicUtil::getGVSourceName(M, GVOwner, NULL, baseBuildDir);
 767                     stringOwnerFound = true;
 768                 }
 769                 else if(AIOwner && !isMagicFunction(M, AIOwner->getParent()->getParent())) {
 770                     ostream << MagicUtil::getFunctionSourceName(M, AIOwner->getParent()->getParent(), NULL, baseBuildDir) << "#" << MagicUtil::getLVSourceName(M, AIOwner);
 771                     stringOwnerFound = true;
 772                 }
 773                 if(stringOwnerFound) {
 774                     ostream.flush();
 775                     stringOwnerMapIt = stringOwnerMap.find(ownerName);
 776                     if(stringOwnerMapIt == stringOwnerMap.end()) {
 777                         stringOwnerMap.insert(std::pair<std::string, GlobalVariable*>(ownerName, GV));
 778                         stringOwnerInvertedMap.insert(std::pair<GlobalVariable*, std::string>(GV, ownerName));
 779                     }
 780                     else {
 781                         stringOwnerInvertedMapIt = stringOwnerInvertedMap.find(stringOwnerMapIt->second);
 782                         if(stringOwnerInvertedMapIt != stringOwnerInvertedMap.end()) {
 783                             stringOwnerInvertedMap.erase(stringOwnerInvertedMapIt);
 784                         }
 785                     }
 786                 }
 787             }
 788         }
 789         else if(GV->isConstant()) {
 790             constGlobalVariables++;
 791         }
 792         if(!isPrimitiveOrPointerType && align) {
 793             GV->setAlignment(align);
 794             if(typeSize % align) {
 795                 typeSize = typeSize - (typeSize % align) + align;
 796             }
 797         }
 798         else if(MAGIC_OFF_BY_N_PROTECTION_N && GVType->isArrayTy() && typeSize>0) {
 799             unsigned alignment = typeSize + (DL.getTypeSizeInBits(GVType->getContainedType(0))/8) * MAGIC_OFF_BY_N_PROTECTION_N;
 800             unsigned a = 2;
 801             while(a < alignment) a = a << 1;
 802             GV->setAlignment(a);
 803         }
 804         globalVariableSizes.push_back(typeSize);
 805         globalVariables.push_back(GV);
 806         if(MagicUtil::hasAddressTaken(GV)) {
 807             globalVariablesWithAddressTaken.insert(GV);
 808         }
 809     }
 810     magicPassLog(">>>> Number of global variables found: " << globalVariables.size() << " of which " << strGlobalVariables << " .str variables, " << constGlobalVariables << " constants, and " << globalVariables.size()-strGlobalVariables-constGlobalVariables << " regular variables");
 811
 812     //build the list of functions having their address taken (include the last function no matter what to get the function ranges right)
 813     std::vector<const SmartType *> functionTypes;
 814     std::vector<GlobalValue *> functionTypeParents;
 815     std::vector<TYPECONST FunctionType *> externalFunctionTypes;
 816     std::vector<GlobalValue *> externalFunctionTypeParents;
 817     for (Module::iterator it = functionList.begin(); it != functionList.end(); ++it) {
 818         Function *F = it;
 819         if(F->hasAddressTaken() || it == --functionList.end() || F->getName().startswith(MAGIC_EVAL_FUNC_PREFIX)) {
 820             if(isMagicFunction(M, F)) {
 821                 continue;
 822             }
 823             functions.push_back(F);
 824             const SmartType *FSmartType = SmartType::getSmartTypeFromFunction(M, F);
 825             if(FSmartType && !FSmartType->isTypeConsistent()) {
 826                 delete FSmartType;
 827                 //pretend the function is external if an invalid type has been found.
 828                 FSmartType = NULL;
 829             }
 830             if(!FSmartType) {
 831                 externalFunctionTypes.push_back(F->getFunctionType());
 832                 externalFunctionTypeParents.push_back(F);
 833             }
 834             else {
 835                 functionTypes.push_back(FSmartType);
 836                 functionTypeParents.push_back(F);
 837             }
 838         }
 839     }
 840     magicPassLog(">>>> Number of functions with address taken found: " << functions.size() << ", of which " << functionTypes.size() << " internal and " << externalFunctionTypes.size() << " external...");
 841
 842     //build the list of global types
 843     std::vector<const SmartType *> smartTypes;
 844     std::vector<GlobalValue *> smartTypeParents;
 845     std::vector<TYPECONST Type *> externalTypes;
 846     std::vector<GlobalValue *> externalTypeParents;
 847     for(i=0;i<globalVariables.size();i++) {
 848         GlobalVariable *GV = globalVariables[i];
 849         TYPECONST Type* GVType = GV->getType()->getElementType();
 850
 851         const SmartType *GVSmartType = SmartType::getSmartTypeFromGV(M, GV);
 852
 853         if(!GV->hasAppendingLinkage()){
 854             // llvm.global_ctors and llvm.global_dtors have appending linkage, don't have compile unit debug info, and therefore cannot be linked to GV debug info, and so are skipped.
 855             if(!GVSmartType) {
 856                 bool isExternal = GV->hasExternalLinkage() || GV->hasExternalWeakLinkage();
 857                 if (!isExternal && !GV->isConstant()) {
 858                     magicPassErr("var is: " << GV->getName());
 859                     magicPassErr("type is: " << TypeUtil::getDescription(GV->getType()->getElementType(), MAGIC_TYPE_STR_PRINT_MAX, MAGIC_TYPE_STR_PRINT_MAX_LEVEL));
 860                 }
 861                 assert(isExternal || GV->isConstant());
 862                 externalTypes.push_back(GVType);
 863                 externalTypeParents.push_back(GV);
 864             }
 865             else {
 866                 smartTypes.push_back(GVSmartType);
 867                 smartTypeParents.push_back(GV);
 868             }
 869         }
 870     }
 871     magicPassLog(">>>> Number of global types found: " << globalVariables.size() << ", of which " << smartTypes.size() << " internal and " << externalTypes.size() << " external...");
 872
 873     //build type infos
 874     TypeInfo* magicVoidPtrTypeInfo = NULL;
 875     TypeInfo* magicVoidArrTypeInfo = NULL;
 876     TypeInfo* magicVoidTypeInfo = NULL;
 877     for(i=0;i<smartTypes.size();i++) {
 878         TypeInfo sourceTypeInfo(smartTypes[i]);
 879         sourceTypeInfo.addParent(smartTypeParents[i]);
 880         TypeInfo *aTypeInfo = fillTypeInfos(sourceTypeInfo, globalTypeInfos);
 881         if(smartTypeParents[i] == magicVoidPtr) {
 882             //get a pointer to void and void* types
 883             magicVoidPtrTypeInfo = aTypeInfo;
 884             assert(magicVoidPtrTypeInfo->getTypeID() == MAGIC_TYPE_POINTER);
 885             magicVoidTypeInfo = magicVoidPtrTypeInfo->getContainedType(0);
 886             assert(magicVoidTypeInfo->getTypeID() == MAGIC_TYPE_VOID);
 887         }
 888         else if(smartTypeParents[i] == magicVoidArr) {
 889             //get a pointer to void array types
 890             magicVoidArrTypeInfo = aTypeInfo;
 891             assert(magicVoidArrTypeInfo->getTypeID() == MAGIC_TYPE_ARRAY);
 892         }
 893     }
 894     assert(magicVoidPtrTypeInfo && magicVoidTypeInfo && magicVoidArrTypeInfo);
 895     std::vector<TypeInfo*> magicVoidTypeInfoArr;
 896     magicVoidTypeInfoArr.push_back(magicVoidTypeInfo);
 897     magicVoidArrTypeInfo->setContainedTypes(magicVoidTypeInfoArr);
 898     magicPassLog(">>>> Number of types found: " << globalTypeInfos.size());
 899     for(i=0;i<functionTypes.size();i++) {
 900         TypeInfo sourceTypeInfo(functionTypes[i]);
 901         sourceTypeInfo.addParent(functionTypeParents[i]);
 902         fillTypeInfos(sourceTypeInfo, globalTypeInfos);
 903     }
 904     magicPassLog(">>>> Number of types + function types found: " << globalTypeInfos.size());
 905
 906     //add external function types
 907     for(i=0;i<externalFunctionTypes.size();i++) {
 908         TypeInfo sourceTypeInfo(externalFunctionTypes[i]);
 909         sourceTypeInfo.addParent(externalFunctionTypeParents[i]);
 910         fillTypeInfos(sourceTypeInfo, globalTypeInfos);
 911     }
 912     magicPassLog(">>>> Number of types + function types + external function types found: " << globalTypeInfos.size());
 913
 914     //add external variable types
 915     for(i=0;i<externalTypes.size();i++) {
 916         TypeInfo* aTypeInfo = fillExternalTypeInfos(externalTypes[i], externalTypeParents[i], globalTypeInfos);
 917         if(aTypeInfo == NULL) {
 918             magicPassErr("var is: " << externalTypeParents[i]->getName());
 919             magicPassErr("type is: " << TypeUtil::getDescription(externalTypes[i], MAGIC_TYPE_STR_PRINT_MAX, MAGIC_TYPE_STR_PRINT_MAX_LEVEL));
 920         }
 921         assert(aTypeInfo != NULL && "External type not supported!");
 922     }
 923     magicPassLog(">>>> Number of types + external types + function types + external function types found: " << globalTypeInfos.size());
 924
 925     //process types, split them when some parent has a valid value set
 926     std::vector<TypeInfo*> splitTypeInfos;
 927     for(i=0;i<globalTypeInfos.size();i++) {
 928         bool isTypeInfoSplit = globalTypeInfos[i]->splitByParentValueSet(splitTypeInfos, globalVariablesWithAddressTaken);
 929         if(isTypeInfoSplit) {
 930 #if DEBUG_VALUE_SET
 931             unsigned splitTypeInfosSize = splitTypeInfos.size();
 932             errs() << "MagicPass: Found type info split with different parents and value sets: original type is: " << globalTypeInfos[i]->getDescription() << ", type splits are:\n";
 933             for(unsigned j=splitTypeInfosSize;j<splitTypeInfos.size();j++) {
 934                 errs() << " - value set is: [ ";
 935                 std::vector<int> valueSet = splitTypeInfos[j]->getValueSet();
 936                 for(unsigned k=1;k<valueSet.size();k++) {
 937                     errs() << (k==1 ? "" : ", ") << valueSet[k];
 938                 }
 939                 errs() << " ], parents are: [ ";
 940                 std::vector<GlobalValue*> parents = splitTypeInfos[j]->getParents();
 941                 for(unsigned k=0;k<parents.size();k++) {
 942                     errs() << (k==0 ? "" : ", ") << parents[k]->getName();
 943                 }
 944                 errs() << " ]\n";
 945             }
 946 #endif
 947         }
 948     }
 949
 950     //index type parents
 951     globalTypeInfos.clear();
 952     for(i=0;i<splitTypeInfos.size();i++) {
 953         TypeInfo *aTypeInfo = splitTypeInfos[i];
 954         std::vector<GlobalValue*> parents = aTypeInfo->getParents();
 955         for(unsigned j=0;j<parents.size();j++) {
 956             parentMapIt = globalParentMap.find(parents[j]);
 957             assert(parentMapIt == globalParentMap.end());
 958             globalParentMap.insert(std::pair<GlobalValue*, TypeInfo*>(parents[j], aTypeInfo));
 959         }
 960         globalTypeInfos.push_back(aTypeInfo);
 961     }
 962
 963     std::vector< TypeInfo* > magicDsindexTypeInfoList;
 964     std::vector< std::pair<std::string,std::string> > magicDsindexNamesList;
 965     std::vector<int> magicDsindexFlagsList;
 966
 967 #if MAGIC_INSTRUMENT_MEM_FUNCS
 968     std::vector<MagicMemFunction> magicMemFunctionCalls;
 969     if (!DisableMemFunctions) {
 970         //gather magic memory function calls to replace and figure out the type (adding more (local) types if needed)
 971         std::map< std::pair<std::string,std::string>, int> namesMap;
 972         int allocFlags;
 973         std::set<Function*> extendedMagicMemFunctions;
 974         for (std::set<Function*>::iterator it = originalMagicMemFunctions.begin(); it != originalMagicMemFunctions.end(); ++it) {
 975             PassUtil::getFunctionsInDirectBUCallgraph(*it, extendedMagicMemFunctions);
 976         }
 977         while(!magicMemFunctions.empty()) {
 978             MagicMemFunction magicMemFunction = magicMemFunctions.front();
 979             magicMemFunctions.erase(magicMemFunctions.begin());
 980             std::vector<User*> Users(magicMemFunction.getFunction()->user_begin(), magicMemFunction.getFunction()->user_end());
 981             std::vector<Value*> EqPointers;
 982             while (!Users.empty()) {
 983               int annotation;
 984               User *U = Users.back();
 985               Users.pop_back();
 986
 987               if (Instruction *I = dyn_cast<Instruction>(U)) {
 988                 Function *parent = I->getParent()->getParent();
 989                 if (isMagicFunction(M, parent) || MagicMemFunction::isCustomWrapper(parent)) {
 990                     continue;
 991                 }
 992                 CallSite CS = MagicUtil::getCallSiteFromInstruction(I);
 993                 if (CS.getInstruction() &&
 994                     (!CS.arg_empty() || magicMemFunction.getWrapper() == NULL) &&
 995                     (MagicUtil::getCalledFunctionFromCS(CS) == magicMemFunction.getFunction() ||
 996                      std::find(EqPointers.begin(), EqPointers.end(),
 997                                CS.getCalledValue()) != EqPointers.end())) {
 998                   bool isDeallocFunction = magicMemFunction.isDeallocFunction();
 999                   bool wrapParent = false;
1000                   bool isNested = false;
1001                   TypeInfo *typeInfo = magicVoidTypeInfo;
1002                   std::string allocName = "";
1003                   std::string allocParentName = "";
1004                   //check if we have to skip
1005                   //if this call site is only called from some predefined mem function, it is nested
1006                   //some function wrappers are for such nested calls, some are not. this must match.
1007                   isNested = (extendedMagicMemFunctions.find(CS.getInstruction()->getParent()->getParent()) != extendedMagicMemFunctions.end());
1008                   if (isNested != magicMemFunction.isNestedFunction()) {
1009                       continue;
1010                   }
1011                   if(sbrkFunctions.find(MagicUtil::getCalledFunctionFromCS(CS)) != sbrkFunctions.end()) {
1012                       ConstantInt *arg = dyn_cast<ConstantInt>(CS.getArgument(0));
1013                       if(arg && arg->getZExtValue() == 0) {
1014                           //ignore sbrk(0) calls. This does not skip calls with a variable argument (when arg == NULL)
1015 #if DEBUG_ALLOC_LEVEL >= 1
1016                           magicPassErr("Skipping instrumentation of sbrk(0) MM call found in " << parent->getName() << "():");
1017                           I->print(errs());
1018                           errs() << "\n";
1019 #endif
1020                           continue;
1021                       }
1022                   }
1023                   else if(MagicUtil::getCallAnnotation(M, CS, &annotation)
1024                       && annotation == MAGIC_CALL_MEM_SKIP_INSTRUMENTATION) {
1025                       //ignore calls we are supposed to skip
1026 #if DEBUG_ALLOC_LEVEL >= 1
1027                       magicPassErr("Skipping instrumentation of annotated MM call found in " << parent->getName() << "():");
1028                       I->print(errs());
1029                       errs() << "\n";
1030 #endif
1031                       continue;
1032                   }
1033                   //figure out the type and the names
1034                   if(!isDeallocFunction && !isNested) {
1035                       int allocCounter = 1;
1036                       int ret;
1037                       std::map< std::pair<std::string,std::string>, int>::iterator namesMapIt;
1038                       //get alloc types and names
1039                       TypeInfo *allocTypeInfo = getAllocTypeInfo(M, magicVoidPtrTypeInfo, CS, allocName, allocParentName);
1040 #if !MAGIC_INSTRUMENT_MEM_CUSTOM_WRAPPERS
1041                       if(!allocTypeInfo) {
1042                           allocTypeInfo = voidTypeInfo;
1043                       }
1044 #endif
1045                       if(allocTypeInfo) {
1046                           typeInfo = allocTypeInfo;
1047                       }
1048                       else {
1049                           int pointerParam = MagicMemFunction::getMemFunctionPointerParam(I->getParent()->getParent(), brkFunctions, magicVoidPtrTypeInfo);
1050                           if(pointerParam >= 0 /* && !I->getParent()->getParent()->hasAddressTaken() */) {
1051                               //the parent is a valid magic mem function to wrap
1052                               wrapParent = true;
1053                           }
1054                       }
1055                       if(!wrapParent) {
1056                           assert(allocParentName.compare("") && "Empty parent name!");
1057                           if(!allocName.compare("")) {
1058                              allocName = MAGIC_ALLOC_NONAME;
1059                           }
1060
1061 #if (MAGIC_NAMED_ALLOC_USE_DBG_INFO || (MAGIC_MEM_USAGE_OUTPUT_CTL == 1))
1062                           //extend names with debug information when requested
1063                           if (MDNode *N = I->getMetadata("dbg")) {
1064                              DILocation Loc(N);
1065                              std::string string;
1066                              raw_string_ostream ostream(string);
1067                              ostream << allocName << MAGIC_ALLOC_NAME_SEP << Loc.getFilename() << MAGIC_ALLOC_NAME_SEP << Loc.getLineNumber();
1068                              ostream.flush();
1069                              allocName = string;
1070                           }
1071 #endif
1072
1073 #if MAGIC_FORCE_ALLOC_EXT_NAMES
1074                           if (isExtLibrary(parent, NULL)) {
1075                              allocName = MAGIC_ALLOC_EXT_NAME;
1076                              allocName = MAGIC_ALLOC_EXT_PARENT_NAME;
1077                           }
1078     #endif
1079
1080                           //avoid duplicates
1081                           namesMapIt = namesMap.find(std::pair<std::string, std::string>(allocParentName, allocName));
1082                           if(namesMapIt != namesMap.end()) {
1083                              allocCounter = namesMapIt->second + 1;
1084                              ret = namesMap.erase(std::pair<std::string, std::string>(allocParentName, allocName));
1085                              assert(ret == 1);
1086                              namesMap.insert(std::pair<std::pair<std::string, std::string>, int>(std::pair<std::string, std::string>(allocParentName, allocName), allocCounter));
1087                              std::string string;
1088                              raw_string_ostream ostream(string);
1089                              ostream << allocName << MAGIC_ALLOC_NAME_SUFFIX << allocCounter;
1090                              ostream.flush();
1091                              allocName = string;
1092                           }
1093                           else {
1094                              namesMap.insert(std::pair<std::pair<std::string, std::string>, int>(std::pair<std::string, std::string>(allocParentName, allocName), allocCounter));
1095                              allocName += MAGIC_ALLOC_NAME_SUFFIX;
1096                           }
1097                           magicMemFunction.setInstructionTypeInfo(typeInfo, allocName, allocParentName);
1098                           //add dsindex entries
1099                           magicDsindexTypeInfoList.push_back(typeInfo);
1100                           magicDsindexNamesList.push_back(std::pair<std::string, std::string>(allocParentName, allocName));
1101                           allocFlags = magicMemFunction.getAllocFlags();
1102                           assert(allocFlags);
1103                           magicDsindexFlagsList.push_back(allocFlags);
1104                       }
1105                   }
1106                   magicMemFunction.setInstruction(I);
1107                   Function *instructionParent = I->getParent()->getParent();
1108                   //see if we can find the parent in our lists
1109                   MagicMemFunction *magicMemParent = NULL;
1110                   for(unsigned k=0;k<magicMemFunctions.size();k++) {
1111                       if(magicMemFunctions[k].getFunction() == instructionParent) {
1112                           magicMemParent = &magicMemFunctions[k];
1113                           break;
1114                       }
1115                   }
1116                   if(!magicMemParent) {
1117                       for(unsigned k=0;k<magicMemFunctionCalls.size();k++) {
1118                           if(magicMemFunctionCalls[k].getFunction() == instructionParent) {
1119                               magicMemParent = &magicMemFunctionCalls[k];
1120                               break;
1121                           }
1122                       }
1123                   }
1124                   if(!magicMemParent && wrapParent) {
1125                       //if there is no existing parent but we have to wrap the parent, create a parent now and add it to the function queue
1126                       assert(!isNested);
1127                       MagicMemFunction newMagicMemFunction(M, instructionParent, NULL, false, false, 0);
1128                       magicMemFunctions.push_back(newMagicMemFunction);
1129                       magicMemParent = &magicMemFunctions[magicMemFunctions.size()-1];
1130                   }
1131                   if(magicMemParent) {
1132                       //if we have a parent, add a dependency
1133                       magicMemParent->addInstructionDep(magicMemFunction);
1134                       assert(magicMemParent->getAllocFlags());
1135                   }
1136                   else {
1137                       //if there is no parent, add it to the call queue
1138                       magicMemFunctionCalls.push_back(magicMemFunction);
1139                   }
1140                 }
1141               } else if (GlobalValue *GV = dyn_cast<GlobalValue>(U)) {
1142                 Users.insert(Users.end(), GV->user_begin(), GV->user_end());
1143                 EqPointers.push_back(GV);
1144               } else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(U)) {
1145                 if (CE->isCast()) {
1146                   Users.insert(Users.end(), CE->user_begin(), CE->user_end());
1147                   EqPointers.push_back(CE);
1148                 }
1149               }
1150             }
1151         }
1152     }
1153 #endif /*MAGIC_INSTRUMENT_MEM_FUNCS*/
1154
1155 #if MAGIC_INSTRUMENT_STACK
1156     std::vector<std::map<AllocaInst*, std::pair<TypeInfo*, std::string> > > localTypeInfoMaps;
1157     std::map<AllocaInst*, std::pair<TypeInfo*, std::string> > localTypeInfoMap;
1158     std::vector<Function*> stackIntrumentedFuncs;
1159     fillStackInstrumentedFunctions(stackIntrumentedFuncs, deepestLLFunction);
1160     std::string stackIntrumentedFuncsStr;
1161     for(i=0;i<stackIntrumentedFuncs.size();i++) {
1162         localTypeInfoMap.clear();
1163         indexLocalTypeInfos(M, stackIntrumentedFuncs[i], localTypeInfoMap);
1164         localTypeInfoMaps.push_back(localTypeInfoMap);
1165         stackIntrumentedFuncsStr += (i==0 ? "" : ", ") + stackIntrumentedFuncs[i]->getName().str() + "()";
1166     }
1167     magicPassLog(">>>> Set of stack-instrumented functions expanded from function " << deepestLLFunction->getName() << "(): " << stackIntrumentedFuncsStr);
1168     magicPassLog(">>>> Number of types + external types + function types + external function types + local types found: " << globalTypeInfos.size());
1169 #endif
1170
1171     //add raw types
1172     std::vector<TypeInfo*> rawTypeInfos;
1173     for(i=0;i<globalTypeInfos.size();i++) {
1174         TypeInfo* aTypeInfo = globalTypeInfos[i];
1175         if(!aTypeInfo->hasRawTypeRepresentation()) {
1176             continue;
1177         }
1178         assert(aTypeInfo->getNumContainedTypes() == 0);
1179         TypeInfo* aRawTypeInfo = new TypeInfo(*magicVoidArrTypeInfo);
1180         aRawTypeInfo->setPersistent();
1181         aRawTypeInfo->removeAllParents();
1182         rawTypeInfos.push_back(aRawTypeInfo);
1183         std::vector<TypeInfo*> aTypeInfoContainedTypes;
1184         aTypeInfoContainedTypes.push_back(aRawTypeInfo);
1185         aTypeInfo->setContainedTypes(aTypeInfoContainedTypes);
1186         assert(aTypeInfo->getContainedType(0)->getContainedType(0) == magicVoidTypeInfo);
1187     }
1188     for(i=0;i<rawTypeInfos.size();i++) {
1189         globalTypeInfos.push_back(rawTypeInfos[i]);
1190         assert(rawTypeInfos[i]->getNumContainedTypes() == 1);
1191     }
1192     magicPassLog(">>>> Number of types + external types + function types + external function types + local types found + raw types: " << globalTypeInfos.size());
1193
1194     //find max recursive sequence length
1195     unsigned length, maxRecursiveSequenceLength = 0;
1196     for(i=0;i<globalTypeInfos.size();i++) {
1197         if(globalTypeInfos[i]->getParents().size() > 0) {
1198             length = getMaxRecursiveSequenceLength(globalTypeInfos[i]);
1199             if(length > maxRecursiveSequenceLength) {
1200                 maxRecursiveSequenceLength = length;
1201             }
1202         }
1203     }
1204     magicPassLog(">>>> Max recursive sequence length: " << maxRecursiveSequenceLength);
1205
1206     //debug type infos when needed
1207 #if DEBUG_TYPE_INFOS
1208         for(i=0;i<globalTypeInfos.size();i++) {
1209             std::vector<GlobalValue*> parents = globalTypeInfos[i]->getParents();
1210             if(parents.size() > 0) {
1211                 std::string parentString, typeString;
1212                 for(unsigned j=0;j<parents.size();j++) {
1213                     parentString.append((j>0 ? ", " : "") + parents[j]->getName().str());
1214                 }
1215                 typeString = globalTypeInfos[i]->getDescription();
1216                 magicPassErr("     Global type group found, parents=( " << parentString << "), type=" << typeString << ", name=" << globalTypeInfos[i]->getName() << ", names_string=" << globalTypeInfos[i]->getNamesString());
1217                 if(DEBUG_TYPE_INFOS >= 2) {
1218                     printInterestingTypes(globalTypeInfos[i]);
1219                 }
1220             }
1221         }
1222         for(i=0;i<globalTypeInfos.size();i++) {
1223             std::string name = globalTypeInfos[i]->getName();
1224             if(name.compare("")) {
1225                 magicPassErr("     Named type found: " << name << " (names string: " << globalTypeInfos[i]->getNamesString() << ", id: " << i << ")");
1226             }
1227         }
1228 #endif
1229
1230 #if DEBUG_DUPLICATED_TYPE_INFOS
1231     std::map<std::string, TypeInfo*> duplicatedTypeInfoMap;
1232     std::map<std::string, TypeInfo*>::iterator duplicatedTypeInfoMapIt;
1233     for(i=0;i<globalTypeInfos.size();i++) {
1234         if(globalTypeInfos[i]->getType()->isStructTy()) {
1235             std::string name = globalTypeInfos[i]->getName();
1236             if(!name.compare("")) {
1237                 continue;
1238             }
1239             duplicatedTypeInfoMapIt = duplicatedTypeInfoMap.find(name);
1240             if(duplicatedTypeInfoMapIt != duplicatedTypeInfoMap.end()) {
1241                 magicPassErr("Duplicated struct name found: " << name << ": " << globalTypeInfos[i]->getVerboseDescription() << " != " << (duplicatedTypeInfoMapIt->second)->getVerboseDescription());
1242             }
1243             else {
1244                 duplicatedTypeInfoMap.insert(std::pair<std::string, TypeInfo*>(name, globalTypeInfos[i]));
1245             }
1246         }
1247     }
1248 #endif
1249
1250     //allocate magic type array
1251     ArrayType* magicTypeArrayType = ArrayType::get(magicTypeStructType, globalTypeInfos.size());
1252     magicTypeArray = new GlobalVariable(M, magicTypeArrayType, false, GlobalValue::InternalLinkage, ConstantAggregateZero::get(magicTypeArrayType), MAGIC_TYPE_ARRAY_NAME);
1253     MagicUtil::setGlobalVariableSection(magicTypeArray, MAGIC_STATIC_VARS_SECTION_DATA);
1254
1255     //allocate magic array
1256     ArrayType* magicArrayType = ArrayType::get(magicStructType, globalVariables.size());
1257     magicArray = new GlobalVariable(M, magicArrayType, false, GlobalValue::InternalLinkage, ConstantAggregateZero::get(magicArrayType), MAGIC_ARRAY_NAME);
1258     MagicUtil::setGlobalVariableSection(magicArray, MAGIC_STATIC_VARS_SECTION_DATA);
1259
1260     //allocate magic function array
1261     ArrayType* magicFunctionArrayType = ArrayType::get(magicFunctionStructType, functions.size());
1262     magicFunctionArray = new GlobalVariable(M, magicFunctionArrayType, false, GlobalValue::InternalLinkage, ConstantAggregateZero::get(magicFunctionArrayType), MAGIC_FUNC_ARRAY_NAME);
1263     MagicUtil::setGlobalVariableSection(magicFunctionArray, MAGIC_STATIC_VARS_SECTION_DATA);
1264
1265     //build magic type array in build function
1266     i=0;
1267     std::map<TypeInfo*, Constant*> magicArrayTypePtrMap;
1268     std::map<TypeInfo*, Constant*>::iterator magicArrayTypePtrMapIt;
1269     std::map<TypeInfo*, unsigned> magicArrayTypeIndexMap;
1270     std::map<TypeInfo*, unsigned>::iterator magicArrayTypeIndexMapIt;
1271     std::vector<Value*> arrayIndexes;
1272     for(;i<globalTypeInfos.size();i++) {
1273         TypeInfo* aTypeInfo = globalTypeInfos[i];
1274         TYPECONST Type *aType = aTypeInfo->getType();
1275         arrayIndexes.clear();
1276         arrayIndexes.push_back(ConstantInt::get(M.getContext(), APInt(64, 0, 10)));     //pointer to A[]
1277         arrayIndexes.push_back(ConstantInt::get(M.getContext(), APInt(64, i, 10))); //pointer to A[index]
1278         Constant* magicTypeArrayPtr = MagicUtil::getGetElementPtrConstant(magicTypeArray, arrayIndexes);
1279         magicArrayTypePtrMap.insert(std::pair<TypeInfo*, Constant*>(aTypeInfo, magicTypeArrayPtr));
1280         magicArrayTypeIndexMap.insert(std::pair<TypeInfo*, unsigned>(aTypeInfo, i));
1281
1282         //storing id field
1283         Value* structIdField = MagicUtil::getMagicTStructFieldPtr(M, magicArrayBuildFuncInst, magicTypeArray, ConstantInt::get(M.getContext(), APInt(64, i, 10)), MAGIC_TSTRUCT_FIELD_ID);
1284         Constant* idValue = ConstantInt::get(M.getContext(), APInt(32, i+1, 10));
1285         new StoreInst(idValue, structIdField, false, magicArrayBuildFuncInst);
1286
1287         //storing name field
1288         Value* structNameField = MagicUtil::getMagicTStructFieldPtr(M, magicArrayBuildFuncInst, magicTypeArray, ConstantInt::get(M.getContext(), APInt(64, i, 10)), MAGIC_TSTRUCT_FIELD_NAME);
1289         Constant* nameValue = MagicUtil::getArrayPtr(M, MagicUtil::getStringRef(M, aTypeInfo->getName()));
1290         new StoreInst(nameValue, structNameField, false, magicArrayBuildFuncInst);
1291
1292         //storing names field
1293         std::vector<std::string> names = aTypeInfo->getNames();
1294         Value* structNamesField = MagicUtil::getMagicTStructFieldPtr(M, magicArrayBuildFuncInst, magicTypeArray, ConstantInt::get(M.getContext(), APInt(64, i, 10)), MAGIC_TSTRUCT_FIELD_NAMES);
1295         Constant* namesValue;
1296         if(names.size() > 0) {
1297             namesValue = MagicUtil::getArrayPtr(M, MagicUtil::getStringArrayRef(M, names.size(), &names));
1298         }
1299         else {
1300             namesValue = ConstantPointerNull::get((TYPECONST PointerType*) ((TYPECONST PointerType*)structNamesField->getType())->getElementType());
1301         }
1302         new StoreInst(namesValue, structNamesField, false, magicArrayBuildFuncInst);
1303
1304         //storing num_names field
1305         Value* structNumNamesField = MagicUtil::getMagicTStructFieldPtr(M, magicArrayBuildFuncInst, magicTypeArray, ConstantInt::get(M.getContext(), APInt(64, i, 10)), MAGIC_TSTRUCT_FIELD_NUM_NAMES);
1306         Constant* numNamesValue = ConstantInt::get(M.getContext(), APInt(32, names.size(), 10));
1307         new StoreInst(numNamesValue, structNumNamesField, false, magicArrayBuildFuncInst);
1308
1309         //storing type_str field
1310         Value* structTypeStrField = MagicUtil::getMagicTStructFieldPtr(M, magicArrayBuildFuncInst, magicTypeArray, ConstantInt::get(M.getContext(), APInt(64, i, 10)), MAGIC_TSTRUCT_FIELD_TYPE_STR);
1311         Constant* typeStrValue = MagicUtil::getArrayPtr(M, MagicUtil::getStringRef(M, aTypeInfo->getTypeString()));
1312         new StoreInst(typeStrValue, structTypeStrField, false, magicArrayBuildFuncInst);
1313
1314         //filling size field
1315         Value* structSizeField = MagicUtil::getMagicTStructFieldPtr(M, magicArrayBuildFuncInst, magicTypeArray, ConstantInt::get(M.getContext(), APInt(64, i, 10)), MAGIC_TSTRUCT_FIELD_SIZE);
1316         Value* typeSizeValue;
1317         if(aType->isFunctionTy() || TypeUtil::isOpaqueTy(aType) || aType->isVoidTy()) {
1318             typeSizeValue = ConstantInt::get(M.getContext(), APInt(32, 1, 10));
1319         }
1320         else {
1321             assert(aType->isSized());
1322             typeSizeValue = ConstantExpr::getIntegerCast(ConstantExpr::getSizeOf(aType), (TYPECONST IntegerType*)((TYPECONST PointerType*)structSizeField->getType())->getElementType(), true);
1323         }
1324         new StoreInst(typeSizeValue, structSizeField, false, magicArrayBuildFuncInst);
1325
1326         //storing num_child_types field
1327         Value* structNumChildTypesField = MagicUtil::getMagicTStructFieldPtr(M, magicArrayBuildFuncInst, magicTypeArray, ConstantInt::get(M.getContext(), APInt(64, i, 10)), MAGIC_TSTRUCT_FIELD_NUM_CHILD_TYPES);
1328         Constant* numChildTypesValue = ConstantInt::get(M.getContext(), APInt(32, aTypeInfo->getNumChildTypes(), 10));
1329         new StoreInst(numChildTypesValue, structNumChildTypesField, false, magicArrayBuildFuncInst);
1330
1331         //storing member_names field
1332         std::vector<std::string> memberNames = aTypeInfo->getMemberNames();
1333         Value* structMemberNamesField = MagicUtil::getMagicTStructFieldPtr(M, magicArrayBuildFuncInst, magicTypeArray, ConstantInt::get(M.getContext(), APInt(64, i, 10)), MAGIC_TSTRUCT_FIELD_MEMBER_NAMES);
1334         Constant* memberNamesValue;
1335         if(memberNames.size() > 0) {
1336             assert(aType->isStructTy());
1337             assert(aTypeInfo->getNumContainedTypes() == memberNames.size());
1338             memberNamesValue = MagicUtil::getArrayPtr(M, MagicUtil::getStringArrayRef(M, memberNames.size(), &memberNames));
1339         }
1340         else {
1341             memberNamesValue = ConstantPointerNull::get((TYPECONST PointerType*) ((TYPECONST PointerType*)structMemberNamesField->getType())->getElementType());
1342         }
1343         new StoreInst(memberNamesValue, structMemberNamesField, false, magicArrayBuildFuncInst);
1344
1345         //storing member_offsets field
1346         Value* structMemberOffsetsField = MagicUtil::getMagicTStructFieldPtr(M, magicArrayBuildFuncInst, magicTypeArray, ConstantInt::get(M.getContext(), APInt(64, i, 10)), MAGIC_TSTRUCT_FIELD_MEMBER_OFFSETS);
1347         Constant* memberOffsetsValue;
1348         if(memberNames.size() > 0) {
1349             assert(aType->isStructTy());
1350             assert(aTypeInfo->getNumContainedTypes() == aTypeInfo->getNumChildTypes());
1351             bool isConstant = false;
1352             GlobalVariable *memberOffsetArray = MagicUtil::getIntArrayRef(M, aTypeInfo->getNumChildTypes(), NULL, isConstant);
1353             for(unsigned j=0;j<aTypeInfo->getNumChildTypes();j++) {
1354                 std::vector<Value*> arrayIndexes;
1355                 arrayIndexes.clear();
1356                 arrayIndexes.push_back(ConstantInt::get(M.getContext(), APInt(64, 0, 10))); //pointer to A[]
1357                 arrayIndexes.push_back(ConstantInt::get(M.getContext(), APInt(64, j, 10))); //pointer to A[j]
1358                 Constant* memberOffsetArrayPtr = MagicUtil::getGetElementPtrConstant(memberOffsetArray, arrayIndexes);
1359
1360                 Value* memberOffsetValue = ConstantExpr::getIntegerCast(ConstantExpr::getOffsetOf((TYPECONST StructType*) aTypeInfo->getType(), j), (TYPECONST IntegerType*)((TYPECONST PointerType*)memberOffsetArrayPtr->getType())->getElementType(), true);
1361                 new StoreInst(memberOffsetValue, memberOffsetArrayPtr, false, magicArrayBuildFuncInst);
1362             }
1363             memberOffsetsValue = MagicUtil::getArrayPtr(M, memberOffsetArray);
1364         }
1365         else {
1366             memberOffsetsValue = ConstantPointerNull::get((TYPECONST PointerType*) ((TYPECONST PointerType*)structMemberOffsetsField->getType())->getElementType());
1367         }
1368         new StoreInst(memberOffsetsValue, structMemberOffsetsField, false, magicArrayBuildFuncInst);
1369
1370         //storing value set field (for enum values and value set analysis)
1371         std::vector<int> valueSet = aTypeInfo->getValueSet();
1372         Value* structValueSetField = MagicUtil::getMagicTStructFieldPtr(M, magicArrayBuildFuncInst, magicTypeArray, ConstantInt::get(M.getContext(), APInt(64, i, 10)), MAGIC_TSTRUCT_FIELD_VALUE_SET);
1373         Constant* valueSetValue;
1374         if(valueSet.size() > 0) {
1375             valueSetValue = ConstantExpr::getCast(Instruction::BitCast, MagicUtil::getArrayPtr(M, MagicUtil::getIntArrayRef(M, valueSet.size(), &valueSet)), magicVoidPtrTypeInfo->getType());
1376         }
1377         else {
1378             valueSetValue = ConstantPointerNull::get((TYPECONST PointerType*)magicVoidPtrTypeInfo->getType());
1379         }
1380         new StoreInst(valueSetValue, structValueSetField, false, magicArrayBuildFuncInst);
1381
1382         //storing type_id field
1383         Value* structTypeIDField = MagicUtil::getMagicTStructFieldPtr(M, magicArrayBuildFuncInst, magicTypeArray, ConstantInt::get(M.getContext(), APInt(64, i, 10)), MAGIC_TSTRUCT_FIELD_TYPE_ID);
1384         Constant* typeIDValue = ConstantInt::get(M.getContext(), APInt(32, aTypeInfo->getTypeID(), 10));
1385         new StoreInst(typeIDValue, structTypeIDField, false, magicArrayBuildFuncInst);
1386
1387         //storing flags field
1388         Value* structFlagsField = MagicUtil::getMagicTStructFieldPtr(M, magicArrayBuildFuncInst, magicTypeArray, ConstantInt::get(M.getContext(), APInt(64, i, 10)), MAGIC_TSTRUCT_FIELD_FLAGS);
1389         Constant* flagsValue = ConstantInt::get(M.getContext(), APInt(32, aTypeInfo->getFlags(), 10));
1390         new StoreInst(flagsValue, structFlagsField, false, magicArrayBuildFuncInst);
1391
1392         //storing bit_width field
1393         Value* structBitWidthField = MagicUtil::getMagicTStructFieldPtr(M, magicArrayBuildFuncInst, magicTypeArray, ConstantInt::get(M.getContext(), APInt(64, i, 10)), MAGIC_TSTRUCT_FIELD_BIT_WIDTH);
1394         Constant* bitWidthValue = ConstantInt::get(M.getContext(), APInt(32, aTypeInfo->getBitWidth(), 10));
1395         new StoreInst(bitWidthValue, structBitWidthField, false, magicArrayBuildFuncInst);
1396     }
1397
1398     i=0;
1399     //build contained types pointers
1400     unsigned dstIndex, voidTypeIndex;
1401     magicArrayTypeIndexMapIt = magicArrayTypeIndexMap.find(magicVoidTypeInfo);
1402     assert(magicArrayTypeIndexMapIt != magicArrayTypeIndexMap.end());
1403     voidTypeIndex = magicArrayTypeIndexMapIt->second;
1404     for(;i<globalTypeInfos.size();i++) {
1405         TypeInfo* aTypeInfo = globalTypeInfos[i];
1406         std::vector<Constant*> containedTypePtrs;
1407         for(unsigned j=0;j<aTypeInfo->getNumContainedTypes();j++) {
1408             TypeInfo* containedType = aTypeInfo->getContainedType(j);
1409             magicArrayTypePtrMapIt = magicArrayTypePtrMap.find(containedType);
1410             assert(magicArrayTypePtrMapIt != magicArrayTypePtrMap.end());
1411
1412             containedTypePtrs.push_back(magicArrayTypePtrMapIt->second);
1413         }
1414         Value* structContainedTypesField = MagicUtil::getMagicTStructFieldPtr(M, magicArrayBuildFuncInst, magicTypeArray, ConstantInt::get(M.getContext(), APInt(64, i, 10)), MAGIC_TSTRUCT_FIELD_CONTAINED_TYPES);
1415         Constant *containedTypesValue;
1416         if(containedTypePtrs.size() > 0) {
1417             containedTypesValue = MagicUtil::getArrayPtr(M, MagicUtil::getGenericArrayRef(M, containedTypePtrs));
1418         }
1419         else {
1420             containedTypesValue = ConstantPointerNull::get((TYPECONST PointerType*) ((TYPECONST PointerType*)structContainedTypesField->getType())->getElementType());
1421         }
1422         new StoreInst(containedTypesValue, structContainedTypesField, false, magicArrayBuildFuncInst);
1423         if(!aTypeInfo->hasRawTypeRepresentation()) {
1424             continue;
1425         }
1426
1427         //handle raw array types
1428         assert(aTypeInfo->getNumContainedTypes() == 1 && aTypeInfo->getContainedType(0)->getType()->isArrayTy());
1429         magicArrayTypeIndexMapIt = magicArrayTypeIndexMap.find(aTypeInfo->getContainedType(0));
1430         assert(magicArrayTypeIndexMapIt != magicArrayTypeIndexMap.end());
1431         dstIndex = magicArrayTypeIndexMapIt->second;
1432
1433         //fix size field (inherited by parent type)
1434         Value* srcStructSizeField = MagicUtil::getMagicTStructFieldPtr(M, magicArrayBuildFuncInst, magicTypeArray, ConstantInt::get(M.getContext(), APInt(64, i, 10)), MAGIC_TSTRUCT_FIELD_SIZE);
1435         Value* dstStructSizeField = MagicUtil::getMagicTStructFieldPtr(M, magicArrayBuildFuncInst, magicTypeArray, ConstantInt::get(M.getContext(), APInt(64, dstIndex, 10)), MAGIC_TSTRUCT_FIELD_SIZE);
1436         Value* srcStructSizeValue = new LoadInst(srcStructSizeField, "", false, magicArrayBuildFuncInst);
1437         new StoreInst(srcStructSizeValue, dstStructSizeField, false, magicArrayBuildFuncInst);
1438
1439         //fix num_child_types field
1440         Value* dstStructNumChildTypesField = MagicUtil::getMagicTStructFieldPtr(M, magicArrayBuildFuncInst, magicTypeArray, ConstantInt::get(M.getContext(), APInt(64, dstIndex, 10)), MAGIC_TSTRUCT_FIELD_NUM_CHILD_TYPES);
1441         Value* voidStructSizeField = MagicUtil::getMagicTStructFieldPtr(M, magicArrayBuildFuncInst, magicTypeArray, ConstantInt::get(M.getContext(), APInt(64, voidTypeIndex, 10)), MAGIC_TSTRUCT_FIELD_SIZE);
1442         Value* voidStructSizeValue = new LoadInst(voidStructSizeField, "", false, magicArrayBuildFuncInst);
1443         BinaryOperator* numChildTypesValue = BinaryOperator::Create(Instruction::SDiv, srcStructSizeValue, voidStructSizeValue, "", magicArrayBuildFuncInst);
1444         new StoreInst(numChildTypesValue, dstStructNumChildTypesField, false, magicArrayBuildFuncInst);
1445     }
1446
1447     i=0;
1448     //build cast types pointers
1449     for(;i<globalTypeInfos.size();i++) {
1450         TypeInfo* aTypeInfo = globalTypeInfos[i];
1451         std::vector<Constant*> castTypePtrs;
1452         std::vector<TypeInfo*> castTypes = aTypeInfo->getCastTypes();
1453
1454         Value* structCompatibleTypesField = MagicUtil::getMagicTStructFieldPtr(M, magicArrayBuildFuncInst, magicTypeArray, ConstantInt::get(M.getContext(), APInt(64, i, 10)), MAGIC_TSTRUCT_FIELD_COMPATIBLE_TYPES);
1455         TYPECONST PointerType* nullArrayType = (TYPECONST PointerType*) ((TYPECONST PointerType*)structCompatibleTypesField->getType())->getElementType();
1456         for(unsigned j=0;j<castTypes.size();j++) {
1457             TypeInfo* castType = castTypes[j];
1458             if(castType == NULL) {
1459                 castTypePtrs.push_back(ConstantPointerNull::get((TYPECONST PointerType*) nullArrayType->getContainedType(0)));
1460             }
1461             else {
1462                 magicArrayTypePtrMapIt = magicArrayTypePtrMap.find(castType);
1463                 assert(magicArrayTypePtrMapIt != magicArrayTypePtrMap.end());
1464
1465                 castTypePtrs.push_back(magicArrayTypePtrMapIt->second);
1466             }
1467         }
1468
1469         Constant *compatibleTypesValue;
1470         if(castTypePtrs.size() > 0) {
1471             compatibleTypesValue = MagicUtil::getArrayPtr(M, MagicUtil::getGenericArrayRef(M, castTypePtrs));
1472         }
1473         else {
1474             compatibleTypesValue = ConstantPointerNull::get(nullArrayType);
1475         }
1476         new StoreInst(compatibleTypesValue, structCompatibleTypesField, false, magicArrayBuildFuncInst);
1477     }
1478
1479     //build magic array in build function
1480     i=0;
1481     strGlobalVariables = 0;
1482     PointerType* voidPointerType = PointerType::get(IntegerType::get(M.getContext(), 8), 0);
1483     for(;i<globalVariables.size();i++) {
1484         GlobalVariable *GV = globalVariables[i];
1485         DIGlobalVariable *DIGV = NULL;
1486         StringRef GVName;
1487         bool isFromLibrary, hasAddressTaken, isString, isNamedString;
1488         isString = GV->getName().startswith(".str");
1489         isNamedString = false;
1490         if(isString) {
1491             stringOwnerInvertedMapIt = stringOwnerInvertedMap.find(GV);
1492             if(stringOwnerInvertedMapIt != stringOwnerInvertedMap.end()) {
1493                 isNamedString = true;
1494                 DIGV = NULL;
1495                 GVName = ".str#" + stringOwnerInvertedMapIt->second;
1496             }
1497         }
1498         if(!isNamedString) {
1499             GVName = MagicUtil::getGVSourceName(M, GV, &DIGV, baseBuildDir);
1500         }
1501         isFromLibrary = isExtLibrary(GV, DIGV);
1502         hasAddressTaken = globalVariablesWithAddressTaken.find(GV) != globalVariablesWithAddressTaken.end();
1503         std::string GVNameStr(GVName.str());
1504
1505         //storing id field
1506         Value* structIdField = MagicUtil::getMagicSStructFieldPtr(M, magicArrayBuildFuncInst, magicArray, ConstantInt::get(M.getContext(), APInt(64, i, 10)), MAGIC_SSTRUCT_FIELD_ID);
1507         Constant* idValue = ConstantInt::get(M.getContext(), APInt(32, i+1, 10));
1508         new StoreInst(idValue, structIdField, false, magicArrayBuildFuncInst);
1509
1510         //storing name field
1511         Value* structNameField = MagicUtil::getMagicSStructFieldPtr(M, magicArrayBuildFuncInst, magicArray, ConstantInt::get(M.getContext(), APInt(64, i, 10)), MAGIC_SSTRUCT_FIELD_NAME);
1512         Constant* nameValue = MagicUtil::getArrayPtr(M, MagicUtil::getStringRef(M, GVNameStr));
1513         new StoreInst(nameValue, structNameField, false, magicArrayBuildFuncInst);
1514
1515         //storing type field
1516         parentMapIt = globalParentMap.find(GV);
1517         if(parentMapIt == globalParentMap.end()) {
1518             continue;
1519         }
1520         assert(parentMapIt != globalParentMap.end());
1521         TypeInfo* aTypeInfo = parentMapIt->second;
1522         magicArrayTypePtrMapIt = magicArrayTypePtrMap.find(aTypeInfo);
1523         assert(magicArrayTypePtrMapIt != magicArrayTypePtrMap.end());
1524         Value* structTypeField = MagicUtil::getMagicSStructFieldPtr(M, magicArrayBuildFuncInst, magicArray, ConstantInt::get(M.getContext(), APInt(64, i, 10)), MAGIC_SSTRUCT_FIELD_TYPE);
1525         Constant* typeValue = magicArrayTypePtrMapIt->second;
1526         new StoreInst(typeValue, structTypeField, false, magicArrayBuildFuncInst);
1527
1528         //filling flags field
1529         int annotation, flags = MAGIC_STATE_DATA;
1530         if(GV->hasExternalLinkage() || GV->hasExternalWeakLinkage()) {
1531             flags |= MAGIC_STATE_EXTERNAL;
1532         }
1533         if(GV->isConstant()) {
1534             flags |= MAGIC_STATE_CONSTANT;
1535         }
1536         if(GV->isThreadLocal()) {
1537             flags |= MAGIC_STATE_THREAD_LOCAL;
1538         }
1539         if(isFromLibrary) {
1540             flags |= MAGIC_STATE_LIB;
1541         }
1542         if(!hasAddressTaken) {
1543             flags |= MAGIC_STATE_ADDR_NOT_TAKEN;
1544         }
1545         if(isString) {
1546             flags |= MAGIC_STATE_STRING;
1547             if(isNamedString) {
1548                 flags |= MAGIC_STATE_NAMED_STRING;
1549             }
1550             strGlobalVariables++;
1551         }
1552         if(MagicUtil::getVarAnnotation(M, GV, &annotation)) {
1553             magicPassLog("Magic annotation found for global variable: " << GV->getName());
1554             flags |= (annotation & MAGIC_STATE_ANNOTATION_MASK);
1555         }
1556         Value* structFlagsField = MagicUtil::getMagicSStructFieldPtr(M, magicArrayBuildFuncInst, magicArray, ConstantInt::get(M.getContext(), APInt(64, i, 10)), MAGIC_SSTRUCT_FIELD_FLAGS);
1557         Constant* flagsValue = ConstantInt::get(M.getContext(), APInt(32, flags, 10));
1558         new StoreInst(flagsValue, structFlagsField, false, magicArrayBuildFuncInst);
1559
1560         //filling address field
1561         Value* structAddressField = MagicUtil::getMagicSStructFieldPtr(M, magicArrayBuildFuncInst, magicArray, ConstantInt::get(M.getContext(), APInt(64, i, 10)), MAGIC_SSTRUCT_FIELD_ADDRESS);
1562         Constant* varAddressValue = ConstantExpr::getCast(Instruction::BitCast, GV, voidPointerType);
1563         new StoreInst(varAddressValue, structAddressField, false, magicArrayBuildFuncInst);
1564
1565         //filling shadow address field
1566         Value* structShadowAddressField = MagicUtil::getMagicSStructFieldPtr(M, magicArrayBuildFuncInst, magicArray, ConstantInt::get(M.getContext(), APInt(64, i, 10)), MAGIC_SSTRUCT_FIELD_SHADOW_ADDRESS);
1567         Constant* varShadowAddressValue;
1568         if(EnableShadowing && !GV->isConstant()) {
1569             GlobalVariable* varShadow = MagicUtil::getShadowRef(M, GV);
1570             shadowGlobalVariables.push_back(varShadow);
1571             varShadowAddressValue = ConstantExpr::getCast(Instruction::BitCast, varShadow, voidPointerType);
1572         }
1573         else {
1574             varShadowAddressValue = ConstantPointerNull::get((TYPECONST PointerType*) ((TYPECONST PointerType*)structShadowAddressField->getType())->getElementType());
1575         }
1576         new StoreInst(varShadowAddressValue, structShadowAddressField, false, magicArrayBuildFuncInst);
1577     }
1578
1579     //build magic function array in build function
1580     i=0;
1581     for(;i<functions.size();i++) {
1582         Function *F = functions[i];
1583         DISubprogram *DIS = NULL;
1584         StringRef FName = MagicUtil::getFunctionSourceName(M, F, &DIS, baseBuildDir);
1585         std::string FNameStr(FName.str());
1586         bool isFromLibrary = isExtLibrary(F, DIS);
1587
1588         //storing id field
1589         Value* structIdField = MagicUtil::getMagicFStructFieldPtr(M, magicArrayBuildFuncInst, magicFunctionArray, ConstantInt::get(M.getContext(), APInt(64, i, 10)), MAGIC_FSTRUCT_FIELD_ID);
1590         Constant* idValue = ConstantInt::get(M.getContext(), APInt(32, i+1, 10));
1591         new StoreInst(idValue, structIdField, false, magicArrayBuildFuncInst);
1592
1593         //storing name field
1594         Value* structNameField = MagicUtil::getMagicFStructFieldPtr(M, magicArrayBuildFuncInst, magicFunctionArray, ConstantInt::get(M.getContext(), APInt(64, i, 10)), MAGIC_FSTRUCT_FIELD_NAME);
1595         Constant* nameValue = MagicUtil::getArrayPtr(M, MagicUtil::getStringRef(M, FNameStr));
1596         new StoreInst(nameValue, structNameField, false, magicArrayBuildFuncInst);
1597
1598         //storing type field
1599         parentMapIt = globalParentMap.find(F);
1600         assert(parentMapIt != globalParentMap.end());
1601         TypeInfo* aTypeInfo = parentMapIt->second;
1602         magicArrayTypePtrMapIt = magicArrayTypePtrMap.find(aTypeInfo);
1603         assert(magicArrayTypePtrMapIt != magicArrayTypePtrMap.end());
1604         Value* structTypeField = MagicUtil::getMagicFStructFieldPtr(M, magicArrayBuildFuncInst, magicFunctionArray, ConstantInt::get(M.getContext(), APInt(64, i, 10)), MAGIC_FSTRUCT_FIELD_TYPE);
1605         Constant* typeValue = magicArrayTypePtrMapIt->second;
1606         new StoreInst(typeValue, structTypeField, false, magicArrayBuildFuncInst);
1607
1608         //filling flags field
1609         int flags = MAGIC_STATE_TEXT|MAGIC_STATE_CONSTANT;
1610         if(isFromLibrary) {
1611             flags |= MAGIC_STATE_LIB;
1612         }
1613         if(!F->hasAddressTaken()) {
1614             flags |= MAGIC_STATE_ADDR_NOT_TAKEN;
1615         }
1616         Value* structFlagsField = MagicUtil::getMagicFStructFieldPtr(M, magicArrayBuildFuncInst, magicFunctionArray, ConstantInt::get(M.getContext(), APInt(64, i, 10)), MAGIC_FSTRUCT_FIELD_FLAGS);
1617         Constant* flagsValue = ConstantInt::get(M.getContext(), APInt(32, flags, 10));
1618         new StoreInst(flagsValue, structFlagsField, false, magicArrayBuildFuncInst);
1619
1620         //filling address field
1621         Value* structAddressField = MagicUtil::getMagicFStructFieldPtr(M, magicArrayBuildFuncInst, magicFunctionArray, ConstantInt::get(M.getContext(), APInt(64, i, 10)), MAGIC_FSTRUCT_FIELD_ADDRESS);
1622         Constant* varAddressValue = ConstantExpr::getCast(Instruction::BitCast, F, voidPointerType);
1623         new StoreInst(varAddressValue, structAddressField, false, magicArrayBuildFuncInst);
1624     }
1625
1626 #if MAGIC_INSTRUMENT_MEM_FUNCS
1627     if (!DisableMemFunctions) {
1628         //replace magic memory function calls with their wrappers
1629         for(i=0;i<magicMemFunctionCalls.size();i++) {
1630             MagicMemFunction *magicMemFunctionCall = &magicMemFunctionCalls[i];
1631             magicMemFunctionCall->replaceInstruction(magicArrayTypePtrMap, magicVoidPtrTypeInfo);
1632         }
1633
1634         //fix debug function calls and their arguments
1635         for (i=0;i<magicDebugFunctions.size();i++) {
1636             MagicDebugFunction *magicDebugFunction = &magicDebugFunctions[i];
1637             magicDebugFunction->fixCalls(M, baseBuildDir);
1638         }
1639
1640         //fix mmap ctl function calls and their arguments
1641         for (i=0;i<magicMmapCtlFunctions.size();i++) {
1642             MagicMmapCtlFunction *magicMmapCtlFunction = &magicMmapCtlFunctions[i];
1643             magicMmapCtlFunction->fixCalls(M, magicGetPageSizeFunc);
1644         }
1645     }
1646 #endif /*MAGIC_INSTRUMENT_MEM_FUNCS*/
1647
1648 #if MAGIC_INSTRUMENT_STACK
1649     //instrument the stack for the relevant set of functions and add dsindex entries
1650     for(i=0;i<stackIntrumentedFuncs.size();i++) {
1651         addMagicStackDsentryFuncCalls(M, stackIntrumentedFuncs[i], stackIntrumentedFuncs[i], magicStackDsentryCreateFunc, magicStackDsentryDestroyFunc,
1652             magicDsentryStructType, localTypeInfoMaps[i], magicArrayTypePtrMap, magicVoidPtrTypeInfo, magicDsindexTypeInfoList, magicDsindexNamesList, magicDsindexFlagsList);
1653     }
1654 #endif
1655
1656     //allocate magic dsindex array
1657     ArrayType* magicDsindexArrayType = ArrayType::get(magicDsindexStructType, magicDsindexTypeInfoList.size());
1658     magicDsindexArray = new GlobalVariable(M, magicDsindexArrayType, false, GlobalValue::InternalLinkage, ConstantAggregateZero::get(magicDsindexArrayType), MAGIC_DSINDEX_ARRAY_NAME);
1659     MagicUtil::setGlobalVariableSection(magicDsindexArray, MAGIC_STATIC_VARS_SECTION_DATA);
1660
1661     //build magic dsindex array in build function
1662     i=0;
1663     for(;i<magicDsindexTypeInfoList.size();i++) {
1664         //storing type field
1665         TypeInfo* aTypeInfo = magicDsindexTypeInfoList[i];
1666         magicArrayTypePtrMapIt = magicArrayTypePtrMap.find(aTypeInfo);
1667         assert(magicArrayTypePtrMapIt != magicArrayTypePtrMap.end());
1668         Value* structTypeField = MagicUtil::getMagicDStructFieldPtr(M, magicArrayBuildFuncInst, magicDsindexArray, ConstantInt::get(M.getContext(), APInt(64, i, 10)), MAGIC_DSTRUCT_FIELD_TYPE);
1669         Constant* typeValue = magicArrayTypePtrMapIt->second;
1670         new StoreInst(typeValue, structTypeField, false, magicArrayBuildFuncInst);
1671
1672         //storing name field
1673         Value* structNameField = MagicUtil::getMagicDStructFieldPtr(M, magicArrayBuildFuncInst, magicDsindexArray, ConstantInt::get(M.getContext(), APInt(64, i, 10)), MAGIC_DSTRUCT_FIELD_NAME);
1674         Constant* nameValue = MagicUtil::getArrayPtr(M, MagicUtil::getStringRef(M, magicDsindexNamesList[i].second));
1675         new StoreInst(nameValue, structNameField, false, magicArrayBuildFuncInst);
1676
1677         //storing parent name field
1678         Value* structParentNameField = MagicUtil::getMagicDStructFieldPtr(M, magicArrayBuildFuncInst, magicDsindexArray, ConstantInt::get(M.getContext(), APInt(64, i, 10)), MAGIC_DSTRUCT_FIELD_PARENT_NAME);
1679         Constant* parentNameValue = MagicUtil::getArrayPtr(M, MagicUtil::getStringRef(M, magicDsindexNamesList[i].first));
1680         new StoreInst(parentNameValue, structParentNameField, false, magicArrayBuildFuncInst);
1681
1682         //storing flags field
1683         Value* structFlagsField = MagicUtil::getMagicDStructFieldPtr(M, magicArrayBuildFuncInst, magicDsindexArray, ConstantInt::get(M.getContext(), APInt(64, i, 10)), MAGIC_DSTRUCT_FIELD_FLAGS);
1684         Constant* flagsValue = ConstantInt::get(M.getContext(), APInt(32, magicDsindexFlagsList[i], 10));
1685         new StoreInst(flagsValue, structFlagsField, false, magicArrayBuildFuncInst);
1686     }
1687
1688     // apply qprof instrumentation
1689     qprofInstrumentationApply(M);
1690
1691     //set pointer to magic type array in build function
1692     new StoreInst(MagicUtil::getArrayPtr(M, magicTypeArray), magicTypeArrayPtr, false, magicArrayBuildFuncInst);
1693
1694     // set runtime flags
1695     new StoreInst(ConstantInt::get(M.getContext(), APInt(32, DisableMemFunctions ? 1 : 0)), magicNoMemInst, false, magicArrayBuildFuncInst);
1696
1697     //set magic type array size in build function
1698     new StoreInst(ConstantInt::get(M.getContext(), APInt(32, globalTypeInfos.size())), magicTypeArraySize, false, magicArrayBuildFuncInst);
1699
1700     //set magic type next id in build function
1701     new StoreInst(ConstantInt::get(M.getContext(), APInt(32, globalTypeInfos.size()+1)), magicTypeNextId, false, magicArrayBuildFuncInst);
1702
1703     //set pointer to magic array in build function
1704     new StoreInst(MagicUtil::getArrayPtr(M, magicArray), magicArrayPtr, false, magicArrayBuildFuncInst);
1705
1706     //set magic array size in build function
1707     new StoreInst(ConstantInt::get(M.getContext(), APInt(32, globalVariables.size())), magicArraySize, false, magicArrayBuildFuncInst);
1708
1709     //set magic array string size in build function
1710     new StoreInst(ConstantInt::get(M.getContext(), APInt(32, strGlobalVariables)), magicArrayStrSize, false, magicArrayBuildFuncInst);
1711
1712     //set magic next id in build function
1713     new StoreInst(ConstantInt::get(M.getContext(), APInt(32, globalVariables.size()+1)), magicNextId, false, magicArrayBuildFuncInst);
1714
1715     //set pointer to magic function array in build function
1716     new StoreInst(MagicUtil::getArrayPtr(M, magicFunctionArray), magicFunctionArrayPtr, false, magicArrayBuildFuncInst);
1717
1718     //set magic function array size in build function
1719     new StoreInst(ConstantInt::get(M.getContext(), APInt(32, functions.size())), magicFunctionArraySize, false, magicArrayBuildFuncInst);
1720
1721     //set magic function next id in build function
1722     new StoreInst(ConstantInt::get(M.getContext(), APInt(32, functions.size()+1)), magicFunctionNextId, false, magicArrayBuildFuncInst);
1723
1724     //set pointer to magic dsindex array in build function
1725     new StoreInst(MagicUtil::getArrayPtr(M, magicDsindexArray), magicDsindexArrayPtr, false, magicArrayBuildFuncInst);
1726
1727     //set magic dsindex array size in build function
1728     new StoreInst(ConstantInt::get(M.getContext(), APInt(32, magicDsindexTypeInfoList.size())), magicDsindexArraySize, false, magicArrayBuildFuncInst);
1729
1730     //set magic void type pointer in build function
1731     magicArrayTypePtrMapIt = magicArrayTypePtrMap.find(magicVoidPtrTypeInfo);
1732     assert(magicArrayTypePtrMapIt != magicArrayTypePtrMap.end());
1733     Constant* magicVoidPtrTypeValue = magicArrayTypePtrMapIt->second;
1734     new StoreInst(magicVoidPtrTypeValue, magicVoidPtrTypePtr, false, magicArrayBuildFuncInst);
1735
1736     //inject magic init call at the beginning of magic entry point function
1737     std::vector<Value*> args;
1738     MagicUtil::createCallInstruction(magicInitFunc, args, "", magicEntryPointFunc->getBasicBlockList().begin()->begin());
1739
1740     //check invariants
1741 #if MAGIC_CHECK_INVARIANTS
1742     if(maxRecursiveSequenceLength > MAGIC_MAX_RECURSIVE_TYPES) {
1743         magicPassErr("Max recursive sequence length is: " << maxRecursiveSequenceLength);
1744     }
1745     assert(maxRecursiveSequenceLength <= MAGIC_MAX_RECURSIVE_TYPES && "MAGIC_MAX_RECURSIVE_TYPES is too small!");
1746     if(TypeInfo::getMaxNameLength() > MAGIC_MAX_NAME_LEN) {
1747         magicPassErr("Max name length is: " << TypeInfo::getMaxNameLength());
1748     }
1749     assert(TypeInfo::getMaxNameLength() <= MAGIC_MAX_NAME_LEN && "MAGIC_MAX_NAME_LEN is too small!");
1750     if(TypeInfo::getMaxTypeStringLength() > MAGIC_MAX_TYPE_STR_LEN) {
1751         magicPassErr("Max type string length is: " << TypeInfo::getMaxTypeStringLength());
1752     }
1753     assert(TypeInfo::getMaxTypeStringLength() <= MAGIC_MAX_TYPE_STR_LEN && "MAGIC_MAX_TYPE_STR_LEN is too small!");
1754 #endif
1755
1756     return true;
1757 }
1758
1759 //===----------------------------------------------------------------------===//
1760 // Private methods
1761 //===----------------------------------------------------------------------===//
1762
1763 static std::vector<int> currPtrVarIndexes;
1764 static std::set< std::pair<Value*,std::vector<int> > > visitedValues;
1765
1766 bool MagicPass::checkPointerVariableIndexes(TYPECONST Type *type, std::vector<int> &ptrVarIndexes, unsigned offset)
1767 {
1768     if(offset >= ptrVarIndexes.size()) {
1769         return true;
1770     }
1771     unsigned ptrVarIndex = (unsigned) ptrVarIndexes[ptrVarIndexes.size()-1 - offset];
1772     if(ptrVarIndex >= type->getNumContainedTypes()) {
1773         return false;
1774     }
1775     return checkPointerVariableIndexes(type->getContainedType(ptrVarIndex), ptrVarIndexes, offset+1);
1776 }
1777
1778 void MagicPass::findPointerVariables(Function* function, Value *value, std::vector<Value*> &ptrVars, std::vector<std::vector<int> > &ptrVarIndexes, Value *parent, bool isUser)
1779 {
1780
1781 #define RETURN_IF(X) do{ if(X){ return; } } while(0)
1782 #define DEBUG_VALUE(M, V) do{ if(DEBUG_ALLOC_LEVEL >= 2) { errs() << M; V->print(errs()); errs() << "\n"; } } while(0)
1783 #define DEBUG_INDEXES() do{ if(DEBUG_ALLOC_LEVEL >= 3) { errs() << ">>> Indexes: "; for(unsigned i=0;i<currPtrVarIndexes.size();i++) errs() << currPtrVarIndexes[i] << " "; errs() << "\n"; } } while(0)
1784
1785     std::pair<Value*,std::vector<int> > visitedPair(value, currPtrVarIndexes);
1786     if(visitedValues.find(visitedPair) != visitedValues.end()) {
1787         return;
1788     }
1789
1790     DEBUG_VALUE(" >>>> findPointerVariables: Value is: ", value);
1791     DEBUG_VALUE(" >>>> findPointerVariables: Parent value is: ", parent);
1792     DEBUG_INDEXES();
1793     std::vector<int> savedPtrVarIndexes;
1794     visitedValues.insert(visitedPair);
1795     ConstantExpr *constantExpr = dyn_cast<ConstantExpr>(value);
1796     if(currPtrVarIndexes.size() == 0) {
1797         if(DEBUG_ALLOC_LEVEL >= 2) {
1798             magicPassErr("Empty indexes, skipping search path!");
1799         }
1800         RETURN_IF(true);
1801     }
1802     else if(GlobalVariable *GV = dyn_cast<GlobalVariable>(value)) {
1803         if(DEBUG_ALLOC_LEVEL >= 2) {
1804             magicPassErr("Found global variable!");
1805         }
1806         ptrVars.push_back(GV);
1807         ptrVarIndexes.push_back(currPtrVarIndexes);
1808         assert(!isUser);
1809         if(GV->getType()->getElementType() != PointerType::get(IntegerType::get(function->getParent()->getContext(), 8), 0)) {
1810             RETURN_IF(true);
1811         }
1812     }
1813     else if(AllocaInst *AI = dyn_cast<AllocaInst>(value)) {
1814         if(DEBUG_ALLOC_LEVEL >= 2) {
1815             magicPassErr("Found local variable!");
1816         }
1817         ptrVars.push_back(AI);
1818         ptrVarIndexes.push_back(currPtrVarIndexes);
1819         assert(!isUser);
1820         if(AI->getAllocatedType() != PointerType::get(IntegerType::get(function->getParent()->getContext(), 8), 0)) {
1821             RETURN_IF(true);
1822         }
1823     }
1824     else if(dyn_cast<ReturnInst>(value)) {
1825         if(DEBUG_ALLOC_LEVEL >= 2) {
1826             magicPassErr("Found return variable!");
1827         }
1828         assert(isUser);
1829         RETURN_IF(true);
1830     }
1831     else if(StoreInst *SI = dyn_cast<StoreInst>(value)) {
1832         DEBUG_VALUE(" >>>> findPointerVariables: Digging store instruction: ", value);
1833         assert(isUser);
1834         if(parent == SI->getOperand(1)) {
1835             assert(currPtrVarIndexes.size() > 0 && currPtrVarIndexes[currPtrVarIndexes.size()-1] == 0);
1836             currPtrVarIndexes.pop_back();
1837             findPointerVariables(function, SI->getOperand(0), ptrVars, ptrVarIndexes, value);
1838             currPtrVarIndexes.push_back(0);
1839         }
1840         else {
1841             currPtrVarIndexes.push_back(0);
1842             findPointerVariables(function, SI->getOperand(1), ptrVars, ptrVarIndexes, value);
1843             currPtrVarIndexes.pop_back();
1844         }
1845     }
1846     else if(LoadInst *LI = dyn_cast<LoadInst>(value)) {
1847         DEBUG_VALUE(" >>>> findPointerVariables: Digging load instruction: ", value);
1848         if(isUser) {
1849             assert(currPtrVarIndexes.size() > 0 && currPtrVarIndexes[currPtrVarIndexes.size()-1] == 0);
1850             savedPtrVarIndexes.push_back(currPtrVarIndexes.back());
1851             currPtrVarIndexes.pop_back();
1852         }
1853         else {
1854             currPtrVarIndexes.push_back(0);
1855             findPointerVariables(function, LI->getOperand(0), ptrVars, ptrVarIndexes, value);
1856             currPtrVarIndexes.pop_back();
1857         }
1858     }
1859     else if(GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(value)) {
1860         if(GEPI->getNumIndices() == 1) {
1861             DEBUG_VALUE(" >>>> findPointerVariables: Digging GEP instruction: ", value);
1862             findPointerVariables(function, GEPI->getOperand(0), ptrVars, ptrVarIndexes, value);
1863         }
1864         else {
1865             RETURN_IF(isUser);
1866             DEBUG_VALUE(" >>>> findPointerVariables: Digging GEP instruction: ", value);
1867             unsigned k = 0;
1868             int index;
1869             assert(currPtrVarIndexes.size() > 0 && currPtrVarIndexes[currPtrVarIndexes.size()-1] == 0);
1870             currPtrVarIndexes.pop_back(); //pop 0
1871             for(GetElementPtrInst::const_op_iterator i=GEPI->idx_end()-1, b=GEPI->idx_begin();i>b;i--,k++) {
1872                 index = 0;
1873                 if(ConstantInt *CI = dyn_cast<ConstantInt>(*i)) {
1874                     index = CI->getSExtValue();
1875                 }
1876                 currPtrVarIndexes.push_back(index);
1877             }
1878             currPtrVarIndexes.push_back(0); //push 0
1879             findPointerVariables(function, GEPI->getOperand(0), ptrVars, ptrVarIndexes, value);
1880             currPtrVarIndexes.pop_back();   //pop 0
1881             while(k-->0) {
1882                 currPtrVarIndexes.pop_back();
1883             }
1884             currPtrVarIndexes.push_back(0); //push 0
1885         }
1886     }
1887     else if(constantExpr && constantExpr->getOpcode() == Instruction::GetElementPtr) {
1888         assert(constantExpr->getNumOperands() >= 2);
1889         if(constantExpr->getNumOperands() == 2) {
1890             DEBUG_VALUE(" >>>> findPointerVariables: Digging GEP expression: ", value);
1891             findPointerVariables(function, constantExpr->getOperand(0), ptrVars, ptrVarIndexes, value);
1892         }
1893         else {
1894             RETURN_IF(isUser);
1895             DEBUG_VALUE(" >>>> findPointerVariables: Digging GEP expression: ", value);
1896             unsigned k = 0;
1897             int index;
1898             assert(currPtrVarIndexes.size() > 0 && currPtrVarIndexes[currPtrVarIndexes.size()-1] == 0);
1899             currPtrVarIndexes.pop_back(); //pop 0
1900             for(unsigned i=constantExpr->getNumOperands()-1;i>1;i--,k++) {
1901                 index = 0;
1902                 if(ConstantInt *CI = dyn_cast<ConstantInt>(constantExpr->getOperand(i))) {
1903                     index = CI->getSExtValue();
1904                 }
1905                 currPtrVarIndexes.push_back(index);
1906             }
1907             currPtrVarIndexes.push_back(0); //push 0
1908             findPointerVariables(function, constantExpr->getOperand(0), ptrVars, ptrVarIndexes, value);
1909             currPtrVarIndexes.pop_back();   //pop 0
1910             while(k-->0) {
1911                 currPtrVarIndexes.pop_back();
1912             }
1913             currPtrVarIndexes.push_back(0); //push 0
1914         }
1915     }
1916     else if(BitCastInst *CI = dyn_cast<BitCastInst>(value)) {
1917         if((isUser && !checkPointerVariableIndexes(CI->getType(), currPtrVarIndexes))
1918             || (!isUser && !checkPointerVariableIndexes(CI->getOperand(0)->getType(), currPtrVarIndexes))) {
1919             DEBUG_VALUE(" >>>> findPointerVariables: Skipping unsafe cast instruction: ", value);
1920             RETURN_IF(true);
1921         }
1922         DEBUG_VALUE(" >>>> findPointerVariables: Digging cast instruction: ", value);
1923         findPointerVariables(function, CI->getOperand(0), ptrVars, ptrVarIndexes, value);
1924     }
1925     else if(dyn_cast<CallInst>(value) || dyn_cast<InvokeInst>(value)) {
1926         RETURN_IF(isUser);
1927         DEBUG_VALUE(" >>>> findPointerVariables: found call instruction: ", value);
1928     }
1929     else if(CmpInst *CI = dyn_cast<CmpInst>(value)) {
1930         assert(isUser);
1931         DEBUG_VALUE(" >>>> findPointerVariables: Digging cmp instruction: ", value);
1932         findPointerVariables(function, CI->getOperand(0), ptrVars, ptrVarIndexes, value);
1933         findPointerVariables(function, CI->getOperand(1), ptrVars, ptrVarIndexes, value);
1934         RETURN_IF(true);
1935     }
1936     else if(SelectInst *SI = dyn_cast<SelectInst>(value)) {
1937         DEBUG_VALUE(" >>>> findPointerVariables: Digging select instruction: ", value);
1938         findPointerVariables(function, SI->getOperand(1), ptrVars, ptrVarIndexes, value);
1939         findPointerVariables(function, SI->getOperand(2), ptrVars, ptrVarIndexes, value);
1940     }
1941     else if(constantExpr && constantExpr->getOpcode() == Instruction::Select) {
1942         DEBUG_VALUE(" >>>> findPointerVariables: Digging select expression: ", value);
1943         findPointerVariables(function, constantExpr->getOperand(1), ptrVars, ptrVarIndexes, value);
1944         findPointerVariables(function, constantExpr->getOperand(2), ptrVars, ptrVarIndexes, value);
1945     }
1946     else if(PHINode *PN = dyn_cast<PHINode>(value)) {
1947         DEBUG_VALUE(" >>>> findPointerVariables: Digging PHI instruction: ", value);
1948         for(unsigned i=0;i<PN->getNumIncomingValues();i++) {
1949             findPointerVariables(function, PN->getIncomingValue(i), ptrVars, ptrVarIndexes, value);
1950         }
1951     }
1952     else if(Argument *ARG = dyn_cast<Argument>(value)) {
1953         DEBUG_VALUE(" >>>> findPointerVariables: Digging Argument: ", value);
1954         AllocaInst *AI = MagicUtil::getAllocaInstFromArgument(ARG);
1955         assert(AI);
1956         currPtrVarIndexes.push_back(0);
1957         findPointerVariables(function, AI, ptrVars, ptrVarIndexes, value);
1958         currPtrVarIndexes.pop_back();
1959         RETURN_IF(true);
1960     }
1961     else {
1962         DEBUG_VALUE(" ************************************************************ findPointerVariables: Unknown value: ", value);
1963         RETURN_IF(true);
1964     }
1965     for (Value::user_iterator i = value->user_begin(), e = value->user_end(); i != e; ++i) {
1966         User *user = *i;
1967         Instruction *instruction = dyn_cast<Instruction>(user);
1968         if(!instruction || instruction->getParent()->getParent() != function) {
1969             continue;
1970         }
1971         DEBUG_VALUE(" >>>> findPointerVariables: Found user: ", user);
1972         findPointerVariables(function, user, ptrVars, ptrVarIndexes, value, true);
1973     }
1974     while(savedPtrVarIndexes.size() > 0) {
1975         currPtrVarIndexes.push_back(savedPtrVarIndexes.back());
1976         savedPtrVarIndexes.pop_back();
1977     }
1978 }
1979
1980 TypeInfo* MagicPass::typeInfoFromPointerVariables(Module &M, TypeInfo *voidPtrTypeInfo, std::vector<Value*> &ptrVars, std::vector<std::vector<int> > &ptrVarIndexes, std::string &allocName)
1981 {
1982     std::vector<TypeInfo*> validTypeInfos;
1983     std::set<TypeInfo*> validTypeInfoSet;
1984     std::vector<unsigned> validTypeTags;
1985     std::vector<unsigned> voidTypeTags;
1986     std::vector<int> indexes;
1987     TypeInfo *aTypeInfo = NULL;
1988     TypeInfo *voidTypeInfo = voidPtrTypeInfo->getContainedType(0);
1989     allocName = "";
1990     if(ptrVars.size()==0) {
1991         return voidTypeInfo;
1992     }
1993
1994     for(unsigned i=0;i<ptrVars.size();i++) {
1995         DIVariable DIV;
1996         unsigned tag = 0;
1997         std::string varName = "";
1998         if(GlobalVariable *GV = dyn_cast<GlobalVariable>(ptrVars[i])) {
1999             parentMapIt = globalParentMap.find(GV);
2000             assert(parentMapIt != globalParentMap.end());
2001             aTypeInfo = parentMapIt->second;
2002             tag = dwarf::DW_TAG_variable;
2003             varName = MagicUtil::getGVSourceName(M, GV, NULL, baseBuildDir);
2004         }
2005         else {
2006             AllocaInst *AI = dyn_cast<AllocaInst>(ptrVars[i]);
2007             assert(AI);
2008             if(DEBUG_ALLOC_LEVEL >= 4) {
2009                 AI->print(errs()); errs() << "\n";
2010             }
2011             const SmartType *aSmartType = SmartType::getSmartTypeFromLV(M, AI, &DIV);
2012             if(aSmartType == (const SmartType *)-1) {
2013                 //a temporary variable
2014                 if(DEBUG_ALLOC_LEVEL >= 4) {
2015                     magicPassErr("typeInfoFromPointerVariables: Skipping temporary variable");
2016                 }
2017                 continue;
2018             }
2019             else if(!aSmartType) {
2020                 //a return variable
2021                 if(DEBUG_ALLOC_LEVEL >= 4) {
2022                     magicPassErr("typeInfoFromPointerVariables: Processing return variable");
2023                 }
2024                 if(AI->getAllocatedType() == voidPtrTypeInfo->getType()) {
2025                     aTypeInfo = voidPtrTypeInfo;
2026                 }
2027                 else {
2028                     aTypeInfo = fillExternalTypeInfos(AI->getAllocatedType(), NULL, globalTypeInfos);
2029                     if(aTypeInfo == NULL) {
2030                         magicPassErr("typeInfoFromPointerVariables: type is: " << TypeUtil::getDescription(AI->getAllocatedType(), MAGIC_TYPE_STR_PRINT_MAX, MAGIC_TYPE_STR_PRINT_MAX_LEVEL));
2031                         if(!MAGIC_ABORT_ON_UNSUPPORTED_LOCAL_EXTERNAL_TYPE) {
2032                             magicPassErr("typeInfoFromPointerVariables: Warning: Local external type not supported, resorting to void* type...");
2033                             aTypeInfo = voidPtrTypeInfo;
2034                         }
2035                         else {
2036                             assert(aTypeInfo != NULL && "Local external type not supported!");
2037                         }
2038                     }
2039                 }
2040                 tag = dwarf::DW_TAG_unspecified_type;
2041             }
2042             else {
2043                 //a regular variable (potentially returning a value to the caller)
2044                 if(DEBUG_ALLOC_LEVEL >= 4) {
2045                     magicPassErr("typeInfoFromPointerVariables: Processing regular variable");
2046                 }
2047                 TypeInfo newTypeInfo(aSmartType);
2048                 aTypeInfo = fillTypeInfos(newTypeInfo, globalTypeInfos);
2049                 if(aTypeInfo->getSmartType() != aSmartType) {
2050                     delete aSmartType;
2051                 }
2052                 if (PassUtil::isReturnedValue(AI->getParent()->getParent(), AI)) {
2053                     // treat this variable as a return variable
2054                     tag = dwarf::DW_TAG_unspecified_type;
2055                 }
2056                 else {
2057                     tag = DIV.getTag();
2058                 }
2059             }
2060             varName = DIV.getName();
2061         }
2062         //see if the target type is an alias for void*
2063         assert(aTypeInfo);
2064         if(aTypeInfo->getType()->isPointerTy()) {
2065             stringSetIt = voidTypeAliasesSet.find(aTypeInfo->getContainedType(0)->getName());
2066             if(stringSetIt != voidTypeAliasesSet.end()) {
2067                 aTypeInfo = voidPtrTypeInfo;
2068             }
2069         }
2070         //fix tag if needed
2071         if(tag == dwarf::DW_TAG_unspecified_type) {
2072             TYPECONST Type *type = aTypeInfo->getType();
2073             if(!type->isPointerTy() || type->getContainedType(0)->isPointerTy()) {
2074                 //not a good return type, switch to a regular variable
2075                 tag = dwarf::DW_TAG_auto_variable;
2076             }
2077         }
2078         if(tag == dwarf::DW_TAG_arg_variable) {
2079             TYPECONST Type *type = aTypeInfo->getType();
2080             if(!type->isPointerTy() || !type->getContainedType(0)->isPointerTy() || type->getContainedType(0)->getContainedType(0)->isPointerTy()) {
2081                 //not a good arg type, switch to a regular variable
2082                 tag = dwarf::DW_TAG_auto_variable;
2083             }
2084         }
2085         if(DEBUG_ALLOC_LEVEL >= 3) {
2086             switch(tag) {
2087                 case dwarf::DW_TAG_unspecified_type:
2088                     magicPassErr("typeInfoFromPointerVariables: Found return variable: " << varName);
2089                 break;
2090                 case dwarf::DW_TAG_variable:
2091                     magicPassErr("typeInfoFromPointerVariables: Found global variable:" << varName);
2092                 break;
2093                 case dwarf::DW_TAG_auto_variable:
2094                     magicPassErr("typeInfoFromPointerVariables: Found local variable:" << varName);
2095                 break;
2096                 case dwarf::DW_TAG_arg_variable:
2097                     magicPassErr("typeInfoFromPointerVariables: Found argument variable:" << varName);
2098                 break;
2099                 default:
2100                     assert(0 && "Should never get here!");
2101                 break;
2102             }
2103         }
2104         indexes = ptrVarIndexes[i];
2105         assert(indexes.back() == 0);
2106         indexes.pop_back();
2107         if(DEBUG_ALLOC_LEVEL >= 4) {
2108             magicPassErr("typeInfoFromPointerVariables: " << indexes.size() << " indexes to process.");
2109         }
2110         while(!indexes.empty()) {
2111             int index = indexes.back();
2112             if(aTypeInfo->hasRawTypeRepresentation()) {
2113                 if(DEBUG_ALLOC_LEVEL >= 4) {
2114                     magicPassErr("typeInfoFromPointerVariables: Skipping index (raw type representation): " << index << ", type is: " << aTypeInfo->getVerboseDescription());
2115                 }
2116                 aTypeInfo = voidTypeInfo;
2117                 break;
2118             }
2119             if(!aTypeInfo->getType()->isStructTy()) {
2120                 index = 0;
2121             }
2122             aTypeInfo = aTypeInfo->getContainedType(index);
2123             if(DEBUG_ALLOC_LEVEL >= 4) {
2124                 magicPassErr("typeInfoFromPointerVariables: Processing index: " << index << ", type is: " << aTypeInfo->getVerboseDescription());
2125             }
2126             indexes.pop_back();
2127         }
2128         if(aTypeInfo == voidTypeInfo) {
2129             voidTypeTags.push_back(tag);
2130         }
2131         else {
2132             validTypeInfos.push_back(aTypeInfo);
2133             validTypeInfoSet.insert(aTypeInfo);
2134             validTypeTags.push_back(tag);
2135         }
2136         if(!allocName.compare("")) {
2137             allocName = varName;
2138         }
2139     }
2140     //see if we have a valid void return type
2141     bool hasValidVoidReturnType = false;
2142     for(unsigned i=0;i<voidTypeTags.size();i++) {
2143         if(voidTypeTags[i] == dwarf::DW_TAG_unspecified_type || voidTypeTags[i] == dwarf::DW_TAG_arg_variable) {
2144             hasValidVoidReturnType = true;
2145             break;
2146         }
2147     }
2148
2149     //count the number of weak local types
2150     unsigned numWeakLocalTypes = 0;
2151     unsigned nonWeakTypeIndex = 0;
2152     unsigned index = 0;
2153     for (std::set<TypeInfo*>::iterator it=validTypeInfoSet.begin() ; it != validTypeInfoSet.end(); it++ ) {
2154         if((*it)->getType() == voidTypeInfo->getType()) {
2155             numWeakLocalTypes++;
2156         } else {
2157             nonWeakTypeIndex = index;
2158         }
2159         index++;
2160     }
2161     bool hasOnlyWeakLocalTypes = (numWeakLocalTypes == validTypeInfoSet.size());
2162     bool hasOnlyOneNonWeakLocalType = (validTypeInfoSet.size() - numWeakLocalTypes == 1);
2163
2164     if(DEBUG_ALLOC_LEVEL >= 3) {
2165         magicPassErr("typeInfoFromPointerVariables: Status: voidTypeTagsSize=" << voidTypeTags.size() << ", hasValidVoidReturnType=" << hasValidVoidReturnType << ", hasOnlyWeakLocalTypes=" << hasOnlyWeakLocalTypes << ", hasOnlyOneNonWeakLocalType=" << hasOnlyOneNonWeakLocalType);
2166     }
2167
2168     //return NULL (treat the function as a wrapper) if we have a valid return type and only weak local types
2169     if(hasValidVoidReturnType && hasOnlyWeakLocalTypes) {
2170         if(DEBUG_ALLOC_LEVEL >= 3) {
2171             magicPassErr("typeInfoFromPointerVariables: Returning no type at all: treat the function as a wrapper");
2172         }
2173         return NULL;
2174     }
2175
2176     //a single valid type has been found, return it
2177     if(hasOnlyOneNonWeakLocalType || (hasOnlyWeakLocalTypes && validTypeInfoSet.size() > 0)) {
2178         if(validTypeTags[nonWeakTypeIndex] == dwarf::DW_TAG_unspecified_type) {
2179             if(DEBUG_ALLOC_BAD_TYPES) {
2180                 magicPassErr("typeInfoFromPointerVariables: warning: non-void return type");
2181             }
2182         }
2183         if(validTypeTags[nonWeakTypeIndex] == dwarf::DW_TAG_arg_variable) {
2184             if(DEBUG_ALLOC_BAD_TYPES) {
2185                 magicPassErr("typeInfoFromPointerVariables: warning: non-void arg type");
2186             }
2187         }
2188         if(DEBUG_ALLOC_LEVEL >= 3) {
2189             magicPassErr("typeInfoFromPointerVariables: Returning single valid type");
2190         }
2191         return validTypeInfos[nonWeakTypeIndex];
2192     }
2193     //multiple valid types found, print warning and resort to void
2194     else if(validTypeInfoSet.size() > 1 && DEBUG_ALLOC_BAD_TYPES) {
2195         magicPassErr("typeInfoFromPointerVariables: warning: multiple valid types found:");
2196         for (std::set<TypeInfo*>::iterator it=validTypeInfoSet.begin() ; it != validTypeInfoSet.end(); it++ ) {
2197             magicPassErr(" - " << (*it)->getVerboseDescription());
2198         }
2199         if(DEBUG_ALLOC_LEVEL >= 3) {
2200             magicPassErr("typeInfoFromPointerVariables: Multiple valid types found");
2201         }
2202     }
2203
2204     if(DEBUG_ALLOC_LEVEL >= 3) {
2205         magicPassErr("typeInfoFromPointerVariables: Returning default void type");
2206     }
2207     return voidTypeInfo;
2208 }
2209
2210 TypeInfo* MagicPass::getAllocTypeInfo(Module &M, TypeInfo *voidPtrTypeInfo, const CallSite &CS, std::string &allocName, std::string &allocParentName)
2211 {
2212     Value *allocPointer = NULL;
2213     Function *function = MagicUtil::getCalledFunctionFromCS(CS);
2214     Function *parentFunction = CS.getInstruction()->getParent()->getParent();
2215     if(DEBUG_ALLOC_LEVEL >= 1) {
2216         magicPassErr("Function is: " << function->getName());
2217         magicPassErr("Parent is: " << parentFunction->getName());
2218     }
2219     std::vector<Value*> ptrVars;
2220     std::vector<std::vector<int> > ptrVarIndexes;
2221     currPtrVarIndexes.clear();
2222     visitedValues.clear();
2223     int pointerParam = MagicMemFunction::getMemFunctionPointerParam(function, brkFunctions, voidPtrTypeInfo);
2224     assert(pointerParam >= 0 && "Invalid wrapper function!");
2225     if(pointerParam == 0) {
2226         allocPointer = CS.getInstruction();
2227         currPtrVarIndexes.push_back(0);
2228     }
2229     else {
2230         allocPointer = CS.getArgument(pointerParam-1);
2231         currPtrVarIndexes.push_back(0);
2232         //brk is a special case and takes the pointer by value
2233         if(brkFunctions.find(function) == brkFunctions.end()) {
2234             currPtrVarIndexes.push_back(0);
2235         }
2236     }
2237     findPointerVariables(parentFunction, allocPointer, ptrVars, ptrVarIndexes);
2238     TypeInfo* aTypeInfo = typeInfoFromPointerVariables(M, voidPtrTypeInfo, ptrVars, ptrVarIndexes, allocName);
2239     allocParentName = MagicUtil::getFunctionSourceName(M, parentFunction, NULL, baseBuildDir);
2240     if(DEBUG_ALLOC_LEVEL >= 1) {
2241         magicPassErr("**************** type found: " << (aTypeInfo ? aTypeInfo->getType()->isStructTy() ? "struct " + aTypeInfo->getName() : aTypeInfo->getVerboseDescription() : "NULL"));
2242     }
2243     return aTypeInfo;
2244 }
2245
2246 TypeInfo* MagicPass::fillTypeInfos(TypeInfo &sourceTypeInfo, std::vector<TypeInfo*> &typeInfos) {
2247     static std::vector<TypeInfo*> nestedTypes;
2248     static unsigned level = 0;
2249     if(DEBUG_FILL_TYPE_INFOS) {
2250         magicPassErr("Entering level: " << level << ", Examining type: " << sourceTypeInfo.getDescription() << ", types so far: " << typeInfos.size());
2251     }
2252
2253     if(sourceTypeInfo.getType()) {
2254         TYPECONST Type* type = sourceTypeInfo.getType();
2255         for(unsigned i=0;i<nestedTypes.size();i++) {
2256             if(type == nestedTypes[i]->getType()) {
2257                 const SmartType *nestedSType = nestedTypes[i]->getSmartType();
2258                 const SmartType *sourceSType = sourceTypeInfo.getSmartType();
2259                 if((!nestedSType && !sourceSType) || (nestedSType && sourceSType && nestedSType->getEDIType()->equals(sourceSType->getEDIType()))) {
2260                     nestedTypes[i]->addParents(sourceTypeInfo.getParents());
2261                     return nestedTypes[i];
2262                 }
2263             }
2264         }
2265     }
2266     assert(sourceTypeInfo.getParents().size() <= 1);
2267     for(unsigned i=0;i<typeInfos.size();i++) {
2268         if(typeInfos[i]->equals(&sourceTypeInfo)) {
2269             typeInfos[i]->addParents(sourceTypeInfo.getParents());
2270             return typeInfos[i];
2271         }
2272     }
2273     TypeInfo *aTypeInfo = new TypeInfo(sourceTypeInfo);
2274     aTypeInfo->setPersistent();
2275     const SmartType *aSmartType = aTypeInfo->getSmartType();
2276     unsigned numContainedTypes = aSmartType ? aSmartType->getNumContainedTypes() : 0;
2277     const SmartType* containedSmartType = NULL;
2278     TypeInfo* addedTypeInfo = NULL;
2279     std::vector<TypeInfo*> aTypeInfoContainedTypes;
2280     nestedTypes.push_back(aTypeInfo);
2281     level++;
2282     for(unsigned i=0;i<numContainedTypes;i++) {
2283         containedSmartType = aSmartType->getContainedType(i);
2284         if(!containedSmartType->isFunctionTy() || containedSmartType->isTypeConsistent()) {
2285             TypeInfo containedTypeInfo(containedSmartType);
2286             addedTypeInfo = fillTypeInfos(containedTypeInfo, typeInfos);
2287         }
2288         else {
2289             TYPECONST FunctionType* type = (TYPECONST FunctionType*) containedSmartType->getType();
2290             TypeInfo containedTypeInfo(type);
2291             addedTypeInfo = fillTypeInfos(containedTypeInfo, typeInfos);
2292         }
2293         if(addedTypeInfo->getSmartType() != containedSmartType) {
2294             delete containedSmartType;
2295         }
2296         aTypeInfoContainedTypes.push_back(addedTypeInfo);
2297     }
2298     level--;
2299     nestedTypes.pop_back();
2300     aTypeInfo->setContainedTypes(aTypeInfoContainedTypes);
2301     typeInfos.push_back(aTypeInfo);
2302     if(DEBUG_FILL_TYPE_INFOS) {
2303         magicPassErr("Exiting level: " << level << ", types so far: " << typeInfos.size());
2304     }
2305     return aTypeInfo;
2306 }
2307
2308 TypeInfo* MagicPass::fillExternalTypeInfos(TYPECONST Type *sourceType, GlobalValue* parent, std::vector<TypeInfo*> &typeInfos) {
2309     static std::map<TYPECONST Type *, TypeInfo*> externalTypeInfoCache;
2310     std::map<TYPECONST Type*, TypeInfo*>::iterator externalTypeInfoCacheIt;
2311     TypeInfo* aTypeInfo = NULL;
2312     std::vector<TypeInfo*> compatibleTypeInfos;
2313     //see if we already have the type in the cache first
2314     externalTypeInfoCacheIt = externalTypeInfoCache.find(sourceType);
2315     if(externalTypeInfoCacheIt != externalTypeInfoCache.end()) {
2316         aTypeInfo = externalTypeInfoCacheIt->second;
2317         if(parent) {
2318             aTypeInfo->addParent(parent);
2319         }
2320         return aTypeInfo;
2321     }
2322
2323     for(unsigned i=0;i<typeInfos.size();i++) {
2324         if(typeInfos[i]->getSmartType() && typeInfos[i]->getSmartType()->getType() == sourceType && (!sourceType->isArrayTy() || typeInfos[i]->getTypeID() == MAGIC_TYPE_ARRAY)) {
2325             compatibleTypeInfos.push_back(typeInfos[i]);
2326         }
2327     }
2328     if(compatibleTypeInfos.size() > 0) {
2329         unsigned minStringTypeInfo = 0;
2330         if(compatibleTypeInfos.size() > 1) {
2331             /* Select the first type in alphabetical order to ensure deterministic behavior. */
2332             for(unsigned i=1;i<compatibleTypeInfos.size();i++) {
2333                 if(compatibleTypeInfos[i]->getSmartType()->getEDIType()->getDescription().compare(compatibleTypeInfos[minStringTypeInfo]->getSmartType()->getEDIType()->getDescription()) < 0) {
2334                     minStringTypeInfo = i;
2335                 }
2336             }
2337         }
2338         aTypeInfo = compatibleTypeInfos[minStringTypeInfo];
2339     }
2340     if(DEBUG_FILL_EXT_TYPE_INFOS && compatibleTypeInfos.size() > 1) {
2341         std::string typeString;
2342         for(unsigned i=0;i<compatibleTypeInfos.size();i++) {
2343             assert(compatibleTypeInfos[i]->getSmartType());
2344             typeString += (i==0 ? "" : ", ") + compatibleTypeInfos[i]->getSmartType()->getEDIType()->getDescription();
2345         }
2346         magicPassErr("Multiple compatible types found for external type " << TypeUtil::getDescription(sourceType, MAGIC_TYPE_STR_PRINT_MAX, MAGIC_TYPE_STR_PRINT_MAX_LEVEL) << ": " << typeString << "; selecting the first type in alphabetical order: " << aTypeInfo->getSmartType()->getEDIType()->getDescription());
2347     }
2348     if(aTypeInfo == NULL) {
2349         TypeInfo *targetTypeInfo = NULL;
2350         if(TypeUtil::isOpaqueTy(sourceType)) {
2351             aTypeInfo = new TypeInfo((TYPECONST StructType*) sourceType, TYPEINFO_PERSISTENT);
2352             typeInfos.push_back(aTypeInfo);
2353         }
2354         else if(sourceType->isPointerTy()) {
2355             TYPECONST Type *targetType = sourceType->getContainedType(0);
2356             targetTypeInfo = fillExternalTypeInfos(targetType, NULL, typeInfos);
2357             if(targetTypeInfo == NULL) {
2358                 return NULL;
2359             }
2360             aTypeInfo = new TypeInfo((TYPECONST PointerType*) sourceType, TYPEINFO_PERSISTENT);
2361         }
2362         else if(sourceType->isArrayTy()) {
2363             TYPECONST Type *targetType = sourceType->getContainedType(0);
2364             targetTypeInfo = fillExternalTypeInfos(targetType, NULL, typeInfos);
2365             if(targetTypeInfo == NULL) {
2366                 return NULL;
2367             }
2368             aTypeInfo = new TypeInfo((TYPECONST ArrayType*) sourceType, TYPEINFO_PERSISTENT);
2369         }
2370         else if(sourceType->isIntegerTy()) {
2371             aTypeInfo = new TypeInfo((TYPECONST IntegerType*) sourceType, TYPEINFO_PERSISTENT);
2372             typeInfos.push_back(aTypeInfo);
2373         }
2374         else if(sourceType->isFunctionTy()) {
2375             aTypeInfo = new TypeInfo((TYPECONST FunctionType*) sourceType, TYPEINFO_PERSISTENT);
2376             typeInfos.push_back(aTypeInfo);
2377         }
2378         if(targetTypeInfo != NULL) {
2379             std::vector<TypeInfo*> containedTypes;
2380             containedTypes.push_back(targetTypeInfo);
2381             aTypeInfo->setContainedTypes(containedTypes);
2382             typeInfos.push_back(aTypeInfo);
2383         }
2384     }
2385     if(aTypeInfo && parent) {
2386         aTypeInfo->addParent(parent);
2387     }
2388     externalTypeInfoCache.insert(std::pair<TYPECONST Type*, TypeInfo*>(sourceType, aTypeInfo));
2389     return aTypeInfo;
2390 }
2391
2392 void MagicPass::printInterestingTypes(TYPECONST TypeInfo *aTypeInfo) {
2393     static std::vector<TYPECONST TypeInfo*> nestedTypes;
2394     static std::vector<unsigned> nestedIndexes;
2395     static std::vector<TYPECONST TypeInfo*> interestingTypesSoFar;
2396     static std::string typeName;
2397     static unsigned level = 0;
2398     for(unsigned i=0;i<nestedTypes.size();i++) {
2399         if(aTypeInfo == nestedTypes[i]) {
2400             return;
2401         }
2402     }
2403
2404     bool isInterestingType = false;
2405     const SmartType *aSmartType = aTypeInfo->getSmartType();
2406     if(aSmartType) {
2407         if(aSmartType->isStructTy() && !aTypeInfo->getName().compare("")) {
2408             isInterestingType = true;
2409             typeName = "Anonymous";
2410         }
2411         if(aSmartType->getEDIType()->isEnumTy()) {
2412             isInterestingType = true;
2413             typeName = "Enum";
2414         }
2415         if(aSmartType->isOpaqueTy()) {
2416             isInterestingType = true;
2417             typeName = "Opaque";
2418         }
2419     }
2420     if(isInterestingType) {
2421         bool isNewInterestingType = true;
2422         for(unsigned i=0;i<interestingTypesSoFar.size();i++) {
2423             if(aTypeInfo == interestingTypesSoFar[i]) {
2424                 isNewInterestingType = false;
2425                 break;
2426             }
2427         }
2428         if(isNewInterestingType) {
2429             interestingTypesSoFar.push_back(aTypeInfo);
2430             if(nestedTypes.size() == 0) {
2431                 dbgs() << "**** " << typeName << " top type found, printing it: \n";
2432                 dbgs() << aSmartType->getDescription();
2433                 aSmartType->getEDIType()->getDIType()->print(dbgs());
2434             }
2435             else {
2436                 dbgs() << "**** " << typeName << " type found, printing path: \n";
2437                 dbgs() << "**************** LEVEL 0\n";
2438                 dbgs() << "**************** NAME: " << nestedTypes[0]->getName() << "\n";
2439                 dbgs() << nestedTypes[0]->getSmartType()->getDescription();
2440                 unsigned i;
2441                 for(i=1;i<nestedTypes.size();i++) {
2442                     dbgs() << "**************** LEVEL " << i << "\n";
2443                     dbgs() << "**************** NAME: " << nestedTypes[i]->getName() << "\n";
2444                     dbgs() << "**************** PARENT INDEX " << nestedIndexes[i-1] << "\n";
2445                     dbgs() << nestedTypes[i]->getSmartType()->getDescription();
2446                 }
2447                 dbgs() << "**************** LAST LEVEL " << i << "\n";
2448                 dbgs() << "**************** PARENT INDEX " << nestedIndexes[i-1] << "\n";
2449                 dbgs() << aSmartType->getDescription();
2450                 aSmartType->getEDIType()->getDIType()->print(dbgs());
2451                 dbgs() << "*****************************************\n";
2452             }
2453         }
2454     }
2455
2456     unsigned numContainedTypes = aTypeInfo->getNumContainedTypes();
2457     nestedTypes.push_back(aTypeInfo);
2458     level++;
2459     for(unsigned i=0;i<numContainedTypes;i++) {
2460         nestedIndexes.push_back(i);
2461         printInterestingTypes(aTypeInfo->getContainedType(i));
2462         nestedIndexes.pop_back();
2463     }
2464     level--;
2465     nestedTypes.pop_back();
2466 }
2467
2468 unsigned MagicPass::getMaxRecursiveSequenceLength(TYPECONST TypeInfo *aTypeInfo) {
2469     static std::vector<TYPECONST TypeInfo*> nestedTypes;
2470     static unsigned level = 0;
2471     for(unsigned i=0;i<nestedTypes.size();i++) {
2472         if(aTypeInfo == nestedTypes[i]) {
2473             return nestedTypes.size()+1;
2474         }
2475     }
2476
2477     unsigned numContainedTypes = aTypeInfo->getNumContainedTypes();
2478     unsigned length, maxLength = 0;
2479     nestedTypes.push_back(aTypeInfo);
2480     level++;
2481     for(unsigned i=0;i<numContainedTypes;i++) {
2482         length = getMaxRecursiveSequenceLength(aTypeInfo->getContainedType(i));
2483         if(length > maxLength) {
2484             maxLength = length;
2485         }
2486     }
2487     level--;
2488     nestedTypes.pop_back();
2489     return maxLength;
2490 }
2491
2492 FunctionType* MagicPass::getFunctionType(TYPECONST FunctionType *baseType, std::vector<unsigned> selectedArgs) {
2493         std::vector<TYPECONST Type*> ArgTypes;
2494         for (unsigned i = 0; i < selectedArgs.size(); i++) {
2495                 ArgTypes.push_back(baseType->getParamType(selectedArgs[i] - 1));
2496         }
2497         // Create a new function type...
2498         FunctionType *FTy = FunctionType::get(baseType->getReturnType(), ArgTypes, baseType->isVarArg());
2499         return FTy;
2500 }
2501
2502 bool MagicPass::isCompatibleMagicMemFuncType(TYPECONST FunctionType *type, TYPECONST FunctionType* magicType) {
2503     if(type->getReturnType() != magicType->getReturnType()) {
2504         return false;
2505     }
2506     unsigned numContainedTypes = type->getNumContainedTypes();
2507     unsigned numContainedMagicTypes = magicType->getNumContainedTypes();
2508     if(numContainedTypes > numContainedMagicTypes) {
2509         return false;
2510     }
2511     for(unsigned i=0;i<numContainedTypes-1;i++) {
2512         TYPECONST Type* cType = type->getContainedType(numContainedTypes-1-i);
2513         TYPECONST Type* cMagicType = magicType->getContainedType(numContainedMagicTypes-1-i);
2514         if (!MagicUtil::isCompatibleType(cType, cMagicType)) {
2515                 return false;
2516         }
2517     }
2518     return true;
2519 }
2520
2521 Function* MagicPass::findWrapper(Module &M, std::string *magicMemPrefixes, Function *f, std::string fName)
2522 {
2523     std::string wName, wName2;
2524     Function *w = NULL, *w2 = NULL;
2525     for(unsigned k=0;magicMemPrefixes[k].compare("");k++) {
2526         wName = magicMemPrefixes[k] + fName;
2527         w = M.getFunction(wName);
2528         if(w) {
2529             wName2 = wName + "_";
2530             break;
2531         }
2532     }
2533     if(!w) {
2534         magicPassErr("Error: no wrapper function found for " << fName << "()");
2535         exit(1);
2536     }
2537     while(!isCompatibleMagicMemFuncType(f->getFunctionType(), w->getFunctionType()) && (w2 = M.getFunction(wName2))) {
2538         w = w2;
2539         wName2.append("_");
2540     }
2541     if(!isCompatibleMagicMemFuncType(f->getFunctionType(), w->getFunctionType())) {
2542         magicPassErr("Error: wrapper function with incompatible type " << wName << "() found");
2543         magicPassErr(TypeUtil::getDescription(f->getFunctionType(), MAGIC_TYPE_STR_PRINT_MAX, MAGIC_TYPE_STR_PRINT_MAX_LEVEL) << " != " << TypeUtil::getDescription(w->getFunctionType(), MAGIC_TYPE_STR_PRINT_MAX, MAGIC_TYPE_STR_PRINT_MAX_LEVEL));
2544         exit(1);
2545     }
2546     return w;
2547 }
2548
2549 #if MAGIC_INDEX_BIT_CAST
2550 static void processBitCast(Module &M, std::map<TYPECONST Type*, std::set<TYPECONST Type*> > &bitCastMap, TYPECONST Type* srcType, TYPECONST Type* dstType);
2551
2552 static void processFunctionBitCast(Module &M, std::map<TYPECONST Type*, std::set<TYPECONST Type*> > &bitCastMap, TYPECONST Type* srcType, TYPECONST Type* dstType) {
2553     // The rough intuition: we are casting one function to another, so we expect these functions to be
2554     // compatible, so their respective parameters must also be compatible, if they are different at all.
2555     // We limit ourselves to pointer parameters because we are only interested in pointer compatibility.
2556     // This routine basically aims to mark two structure pointers as compatible when one structure has
2557     // an opaque pointer and the other one does not.
2558     TYPECONST FunctionType* srcF = dyn_cast<TYPECONST FunctionType>(srcType);
2559     TYPECONST FunctionType* dstF = dyn_cast<TYPECONST FunctionType>(dstType);
2560
2561     // Both functions must have the same number of parameters.
2562     unsigned int numParams = srcF->getNumParams();
2563
2564     if (numParams != dstF->getNumParams()) return;
2565
2566     TYPECONST Type* voidPtrType = PointerType::get(IntegerType::get(M.getContext(), 8), 0);
2567
2568     // If any of the parameters are pointers for different types, these types must be compatible.
2569     for (unsigned int i = 0; i < numParams; i++) {
2570         TYPECONST Type* spType = srcF->getParamType(i);
2571         TYPECONST Type* dpType = dstF->getParamType(i);
2572
2573         // The parameters must have different types, but they must both be pointers.
2574         if (spType == dpType) continue;
2575
2576         if (!spType->isPointerTy() || !dpType->isPointerTy()) continue;
2577
2578         // We ignore certain types, depending on our configuration.
2579         TYPECONST Type* dpElType = TypeUtil::getRecursiveElementType(dpType);
2580
2581         if (!((MAGIC_INDEX_FUN_PTR_BIT_CAST && dpElType->isFunctionTy()) ||
2582             (MAGIC_INDEX_STR_PTR_BIT_CAST && dpElType->isStructTy()) ||
2583             MAGIC_INDEX_OTH_PTR_BIT_CAST)) continue;
2584
2585         // TODO: this needs configuration testing as well.
2586         if (spType == voidPtrType || dpType == voidPtrType) continue;
2587
2588 #if DEBUG_CASTS
2589         errs() << "Compatible function parameter " << i << ": " << TypeUtil::getDescription(spType) <<
2590             " -> " << TypeUtil::getDescription(dpType) << "\n";
2591 #endif
2592
2593         // The two pointers should be compatible, so mark them as such.
2594         // TODO: prevent infinite recursion
2595         processBitCast(M, bitCastMap, spType, dpType);
2596     }
2597 }
2598
2599 #if 0
2600 static void processStructBitCast(Module &M, std::map<TYPECONST Type*, std::set<TYPECONST Type*> > &bitCastMap, TYPECONST Type* srcType, TYPECONST Type* dstType) {
2601     // The rough intuition: the given structure types are subject to pointer casting. This does not
2602     // mean they are compatible by itself (struct sockaddr..). HOWEVER, if they differ only by
2603     // elements which are different only (recursively) by opaque pointers in one of them, and
2604     // non-opaque pointer in the other, then those pointers are highly likely to be compatible.
2605     TYPECONST StructType* srcS = dyn_cast<TYPECONST StructType>(srcType);
2606     TYPECONST StructType* dstS = dyn_cast<TYPECONST StructType>(dstType);
2607
2608     // The structures must be similar..
2609     if (srcS->isPacked() != dstS->isPacked()) return false;
2610
2611     unsigned int numElements = srcS->getNumElements();
2612
2613     if (numElements != dstS->getNumElements()) return false;
2614
2615     // ..but not the same.
2616     if (srcS->isLayoutIdentical(dstS)) return false;
2617
2618     // Pass 1: see if the structures differ only by opaque (sub)elements.
2619     for (unsigned int i = 0; i < numElements; i++) {
2620         TYPECONST Type* seType = srcS->getElementType(i);
2621         TYPECONST Type* deType = dstS->getElementType(i);
2622
2623         if (seType != deType) {
2624             if (seType->isPointerTy() && deType->isPointerTy()) {
2625                 TYPECONST PointerType* sePtrType = dyn_cast<PointerType>(seType);
2626                 TYPECONST PointerType* dePtrType = dyn_cast<PointerType>(deType);
2627
2628                 // ..TODO..
2629                 // this may involve recursive testing!
2630             }
2631
2632             // ..TODO..
2633         }
2634     }
2635
2636     // Pass 2: register all pointers to compatible elements.
2637     // ..TODO..
2638     // this may involve recursive registration!
2639 }
2640 #endif
2641
2642 static void processBitCast(Module &M, std::map<TYPECONST Type*, std::set<TYPECONST Type*> > &bitCastMap, TYPECONST Type* srcType, TYPECONST Type* dstType) {
2643     std::map<TYPECONST Type*, std::set<TYPECONST Type*> >::iterator bitCastMapIt;
2644     unsigned int dstDepth, srcDepth;
2645     TYPECONST PointerType* ptrType;
2646
2647     // The pointers are compatible, so add them to the bitcast map.
2648     bitCastMapIt = bitCastMap.find(dstType);
2649     if(bitCastMapIt == bitCastMap.end()) {
2650         std::set<TYPECONST Type*> typeSet;
2651         typeSet.insert(srcType);
2652         bitCastMap.insert(std::pair<TYPECONST Type*, std::set<TYPECONST Type*> >(dstType, typeSet));
2653     }
2654     else {
2655         std::set<TYPECONST Type*> *typeSet = &(bitCastMapIt->second);
2656         typeSet->insert(srcType);
2657     }
2658
2659     // Unfortunately, this is not the whole story. The compiler may pull crazy stunts like storing
2660     // a well-defined pointer in a structure, and then bitcast that structure to an almost-equivalent
2661     // structure which has the pointer marked as opaque. Worse yet, it may bitcast between functions
2662     // with such structures as parameters.  In those case, we never see a cast of the actual pointer,
2663     // even though they are compatible. Failing to mark them as such could cause runtime failures.
2664     // The code below is a first attempt to deal with a subset of cases that we have actually run
2665     // into in practice. A better approach would be a separate pass that eliminates opaque pointers
2666     // whenever possible altogether, but that would be even more work. TODO! Note that in general,
2667     // it seems that there is no way to get to know which pointers the linker decided are equivalent,
2668     // so this procedure is inherently going to involve guessing, with false positives and negatives.
2669
2670     // Follow the pointers to see what they actually point to.
2671     // The caller may already have done so, but without getting the depth.
2672     for (dstDepth = 0; (ptrType = dyn_cast<PointerType>(dstType)); dstDepth++)
2673         dstType = ptrType->getElementType();
2674
2675     for (srcDepth = 0; (ptrType = dyn_cast<PointerType>(srcType)); srcDepth++)
2676         srcType = ptrType->getElementType();
2677
2678     // The pointers' indirection levels must be the same.
2679     if (srcDepth != dstDepth) return;
2680
2681     // Do more processing for certain types.
2682     if (dstType->isFunctionTy() && srcType->isFunctionTy())
2683         processFunctionBitCast(M, bitCastMap, srcType, dstType);
2684     // TODO: add support for structures and their elements
2685 #if 0
2686     else if (dstType->isStructTy() && srcType->isStructTy())
2687         processStructBitCast(M, bitCastMap, srcType, dstType);
2688 #endif
2689 }
2690 #endif /* MAGIC_INDEX_BIT_CAST */
2691
2692 void MagicPass::indexCasts(Module &M, User *U, std::vector<TYPECONST Type*> &intCastTypes, std::vector<int> &intCastValues, std::map<TYPECONST Type*, std::set<TYPECONST Type*> > &bitCastMap) {
2693     unsigned i;
2694     TYPECONST Type* voidPtrType = PointerType::get(IntegerType::get(M.getContext(), 8), 0);
2695
2696     //look at instructions first
2697 #if MAGIC_INDEX_INT_CAST
2698     if(CastInst* CI = dyn_cast<IntToPtrInst>(U)) {
2699         TYPECONST Type* type = TypeUtil::getArrayFreePointerType(CI->getDestTy());
2700         TYPECONST Type* elType = TypeUtil::getRecursiveElementType(type);
2701         if((MAGIC_INDEX_FUN_PTR_INT_CAST && elType->isFunctionTy()) || (MAGIC_INDEX_STR_PTR_INT_CAST && elType->isStructTy()) || MAGIC_INDEX_OTH_PTR_INT_CAST) {
2702             if(MAGIC_INDEX_VOID_PTR_INT_CAST || type != voidPtrType) {
2703                 intCastTypes.push_back(type);
2704                 ConstantInt *value = dyn_cast<ConstantInt>(CI->getOperand(0));
2705                 intCastValues.push_back(value ? value->getSExtValue() : 0);
2706 #if DEBUG_CASTS
2707                 CI->print(errs()); errs() << "\n";
2708 #endif
2709             }
2710         }
2711     }
2712 #endif
2713
2714 #if MAGIC_INDEX_BIT_CAST
2715     if(BitCastInst* CI = dyn_cast<BitCastInst>(U)) {
2716         TYPECONST Type* type = TypeUtil::getArrayFreePointerType(CI->getDestTy());
2717         TYPECONST Type* elType = TypeUtil::getRecursiveElementType(type);
2718         if((MAGIC_INDEX_FUN_PTR_BIT_CAST && elType->isFunctionTy()) || (MAGIC_INDEX_STR_PTR_BIT_CAST && elType->isStructTy()) || MAGIC_INDEX_OTH_PTR_BIT_CAST) {
2719             if(MAGIC_INDEX_VOID_PTR_BIT_CAST || type != voidPtrType) {
2720                 TYPECONST Type* srcType = TypeUtil::getArrayFreePointerType(CI->getSrcTy());
2721                 if(srcType != type && (!MAGIC_SKIP_TOVOID_PTR_BIT_CAST || srcType != voidPtrType)) {
2722 #if DEBUG_CASTS
2723                     CI->print(errs()); errs() << "\n";
2724 #endif
2725                     processBitCast(M, bitCastMap, srcType, type);
2726                 }
2727             }
2728         }
2729     }
2730 #endif
2731
2732     //now dig looking for constant expressions
2733     std::vector<User*> users;
2734     users.push_back(U);
2735     while(!users.empty()) {
2736         User *user = users.front();
2737         users.erase(users.begin());
2738         ConstantExpr *CE = dyn_cast<ConstantExpr>(user);
2739
2740 #if MAGIC_INDEX_INT_CAST
2741         if(CE && CE->getOpcode() == Instruction::IntToPtr) {
2742             TYPECONST Type* type = TypeUtil::getArrayFreePointerType(CE->getType());
2743             TYPECONST Type* elType = TypeUtil::getRecursiveElementType(type);
2744             if((MAGIC_INDEX_FUN_PTR_INT_CAST && elType->isFunctionTy()) || (MAGIC_INDEX_STR_PTR_INT_CAST && elType->isStructTy()) || MAGIC_INDEX_OTH_PTR_INT_CAST) {
2745                 if(MAGIC_INDEX_VOID_PTR_INT_CAST || type != voidPtrType) {
2746 #if DEBUG_CASTS
2747                     CE->print(errs()); errs() << "\n";
2748 #endif
2749                     intCastTypes.push_back(type);
2750                     ConstantInt *value = dyn_cast<ConstantInt>(CE->getOperand(0));
2751                     intCastValues.push_back(value ? value->getSExtValue() : 0);
2752                 }
2753             }
2754         }
2755 #endif
2756
2757 #if MAGIC_INDEX_BIT_CAST
2758         if(CE && CE->getOpcode() == Instruction::BitCast) {
2759             TYPECONST Type* type = TypeUtil::getArrayFreePointerType(CE->getType());
2760             TYPECONST Type* elType = TypeUtil::getRecursiveElementType(type);
2761             if((MAGIC_INDEX_FUN_PTR_BIT_CAST && elType->isFunctionTy()) || (MAGIC_INDEX_STR_PTR_BIT_CAST && elType->isStructTy()) || MAGIC_INDEX_OTH_PTR_BIT_CAST) {
2762                 if(MAGIC_INDEX_VOID_PTR_BIT_CAST || type != voidPtrType) {
2763                     TYPECONST Type* srcType = TypeUtil::getArrayFreePointerType(CE->getOperand(0)->getType());
2764                     if(srcType != type && (!MAGIC_SKIP_TOVOID_PTR_BIT_CAST || srcType != voidPtrType)) {
2765 #if DEBUG_CASTS
2766                         CE->print(errs()); errs() << "\n";
2767 #endif
2768                         processBitCast(M, bitCastMap, srcType, type);
2769                     }
2770                 }
2771             }
2772         }
2773 #endif
2774
2775         for(i=0;i<user->getNumOperands();i++) {
2776             User *operand = dyn_cast<User>(user->getOperand(i));
2777             if(operand && !isa<Instruction>(operand) && !isa<GlobalVariable>(operand)) {
2778                 users.push_back(operand);
2779             }
2780         }
2781     }
2782 }
2783
2784 void MagicPass::fillStackInstrumentedFunctions(std::vector<Function*> &stackIntrumentedFuncs, Function *deepestLLFunction) {
2785     assert(!deepestLLFunction->hasAddressTaken() && "Indirect calls not supported for detection of long-lived functions");
2786     for(unsigned i=0;i<stackIntrumentedFuncs.size();i++) {
2787         if(stackIntrumentedFuncs[i] == deepestLLFunction) {
2788             return;
2789         }
2790     }
2791     stackIntrumentedFuncs.push_back(deepestLLFunction);
2792     for (Value::user_iterator i = deepestLLFunction->user_begin(), e = deepestLLFunction->user_end(); i != e; ++i) {
2793         User *user = *i;
2794         if(Instruction *I = dyn_cast<Instruction>(user)) {
2795             fillStackInstrumentedFunctions(stackIntrumentedFuncs, I->getParent()->getParent());
2796         }
2797     }
2798 }
2799
2800 void MagicPass::indexLocalTypeInfos(Module &M, Function *F, std::map<AllocaInst*, std::pair<TypeInfo*, std::string> > &localMap) {
2801   DIVariable DIV;
2802   for (inst_iterator it = inst_begin(F), et = inst_end(F); it != et; ++it) {
2803       AllocaInst *AI = dyn_cast<AllocaInst>(&(*it));
2804       if(!AI) {
2805           break;
2806       }
2807       const SmartType *aSmartType = SmartType::getSmartTypeFromLV(M, AI, &DIV);
2808       if(!aSmartType || aSmartType == (const SmartType *)-1) {
2809           // skip return and temporary variables
2810           continue;
2811       }
2812       TypeInfo newTypeInfo(aSmartType);
2813       TypeInfo *aTypeInfo = fillTypeInfos(newTypeInfo, globalTypeInfos);
2814       if(aTypeInfo->getSmartType() != aSmartType) {
2815           delete aSmartType;
2816       }
2817       std::string name = MagicUtil::getLVSourceName(M, AI).data();
2818       std::pair<TypeInfo*, std::string> infoNamePair(aTypeInfo, name);
2819       localMap.insert(std::pair<AllocaInst*, std::pair<TypeInfo*, std::string> >(AI, infoNamePair));
2820   }
2821 }
2822
2823 void MagicPass::addMagicStackDsentryFuncCalls(Module &M, Function *insertCallsInFunc, Function *localsFromFunc, Function *dsentryCreateFunc, Function *dsentryDestroyFunc, TYPECONST StructType *dsentryStructType, std::map<AllocaInst*, std::pair<TypeInfo*, std::string> > localTypeInfoMap, std::map<TypeInfo*, Constant*> &magicArrayTypePtrMap, TypeInfo *voidPtrTypeInfo, std::vector<TypeInfo*> &typeInfoList, std::vector<std::pair<std::string, std::string> > &namesList, std::vector<int> &flagsList) {
2824   std::vector<Value*> locals;
2825   std::map<AllocaInst*, std::pair<TypeInfo*, std::string> >::iterator localTypeInfoMapIt;
2826   std::map<TypeInfo*, Constant*>::iterator magicArrayTypePtrMapIt;
2827   std::vector<TypeInfo*> localTypeInfos;
2828   std::vector<Value*> localTypeInfoValues;
2829   std::vector<Value*> localDsentryValues;
2830   std::string allocName, allocParentName;
2831   Instruction *allocaI = NULL, *dsentryCreateI = NULL, *dsentryDestroyI = NULL;
2832   // find local variables and types
2833   for (inst_iterator it = inst_begin(localsFromFunc), et = inst_end(localsFromFunc); it != et; ++it) {
2834       AllocaInst *AI = dyn_cast<AllocaInst>(&(*it));
2835       if(!AI) {
2836           break;
2837       }
2838       localTypeInfoMapIt = localTypeInfoMap.find(AI);
2839       if(localTypeInfoMapIt != localTypeInfoMap.end()) {
2840           assert(AI->hasName());
2841           TypeInfo *aTypeInfo = localTypeInfoMapIt->second.first;
2842           magicArrayTypePtrMapIt = magicArrayTypePtrMap.find(aTypeInfo);
2843           assert(magicArrayTypePtrMapIt != magicArrayTypePtrMap.end());
2844           Constant *aTypeInfoValue = magicArrayTypePtrMapIt->second;
2845           localTypeInfos.push_back(aTypeInfo);
2846           localTypeInfoValues.push_back(aTypeInfoValue);
2847           locals.push_back(AI);
2848       }
2849   }
2850   // find the first and the last valid instruction to place a call and the alloca point
2851   dsentryCreateI = MagicUtil::getFirstNonAllocaInst(insertCallsInFunc);
2852   dsentryDestroyI = insertCallsInFunc->back().getTerminator();
2853   allocaI = MagicUtil::getFirstNonAllocaInst(insertCallsInFunc, false);
2854
2855   // create one dsentry for each local variable
2856   for(unsigned i=0;i<locals.size();i++) {
2857       AllocaInst *AI = new AllocaInst(dsentryStructType, "dsentry_" + (locals[i]->hasName() ? locals[i]->getName() : "anon"), allocaI);
2858       localDsentryValues.push_back(AI);
2859   }
2860   assert(localTypeInfoValues.size() == localDsentryValues.size());
2861
2862   // create one dsentry and value set array for the return address
2863   localTypeInfos.push_back(voidPtrTypeInfo);
2864   localTypeInfoValues.push_back(new AllocaInst(ArrayType::get(IntegerType::get(M.getContext(), 32), 2), "dsentry_ret_addr_value_set", allocaI)); //pass the value set pointer as though it were a type pointer
2865   localDsentryValues.push_back(new AllocaInst(dsentryStructType, "dsentry_ret_addr", allocaI));
2866
2867   // create one dsentry pointer to remember the last stack dsentry
2868   AllocaInst *prevLastStackDsentry = new AllocaInst(PointerType::get(dsentryStructType, 0), "prev_last_stack_dsentry", allocaI);
2869
2870   // get the frame address of the function and pass the value as though it were a data pointer
2871   Function *frameAddrIntrinsic = MagicUtil::getIntrinsicFunction(M, Intrinsic::frameaddress);
2872   std::vector<Value*> frameAddrArgs;
2873   frameAddrArgs.push_back(ConstantInt::get(M.getContext(), APInt(32, 0)));
2874   CallInst *callInst = MagicUtil::createCallInstruction(frameAddrIntrinsic, frameAddrArgs, "", dsentryCreateI);
2875   locals.push_back(callInst);
2876
2877   // place calls
2878   std::vector<Value*> dsentryCreateArgs;
2879   std::vector<Value*> dsentryDestroyArgs;
2880   dsentryCreateArgs.push_back(prevLastStackDsentry);
2881   dsentryDestroyArgs.push_back(prevLastStackDsentry);
2882   dsentryCreateArgs.push_back(ConstantInt::get(M.getContext(), APInt(32, locals.size())));
2883   dsentryDestroyArgs.push_back(ConstantInt::get(M.getContext(), APInt(32, locals.size())));
2884   allocParentName = MagicUtil::getFunctionSourceName(M, insertCallsInFunc, NULL, baseBuildDir);
2885   int allocFlags = MAGIC_STATE_STACK;
2886   for(unsigned i=0;i<locals.size();i++) {
2887       //get name
2888       if(AllocaInst *AI = dyn_cast<AllocaInst>(locals[i])) {
2889           // local variable
2890           localTypeInfoMapIt = localTypeInfoMap.find(AI);
2891           assert(localTypeInfoMapIt != localTypeInfoMap.end());
2892           allocName = localTypeInfoMapIt->second.second;
2893       }
2894       else {
2895           // return address
2896           allocName = MAGIC_ALLOC_RET_ADDR_NAME;
2897       }
2898       //add args
2899       dsentryCreateArgs.push_back(localDsentryValues[i]);
2900       dsentryCreateArgs.push_back(localTypeInfoValues[i]);
2901       dsentryCreateArgs.push_back(locals[i]);
2902       dsentryCreateArgs.push_back(MagicUtil::getStringRef(M, allocParentName));
2903       dsentryCreateArgs.push_back(MagicUtil::getStringRef(M, allocName));
2904       dsentryDestroyArgs.push_back(localDsentryValues[i]);
2905       //add elements to type and names lists
2906       typeInfoList.push_back(localTypeInfos[i]);
2907       namesList.push_back(std::pair<std::string, std::string>(allocParentName, allocName));
2908       flagsList.push_back(allocFlags);
2909   }
2910   MagicUtil::createCallInstruction(dsentryCreateFunc, dsentryCreateArgs, "", dsentryCreateI);
2911   if(isa<ReturnInst>(dsentryDestroyI)) {
2912       MagicUtil::createCallInstruction(dsentryDestroyFunc, dsentryDestroyArgs, "", dsentryDestroyI);
2913   }
2914 }
2915
2916 bool MagicPass::isExtLibrary(GlobalValue *GV, DIDescriptor *DID)
2917 {
2918     static bool regexesInitialized = false;
2919     static std::vector<Regex*> regexes;
2920     if(!regexesInitialized) {
2921         std::vector<std::string>::iterator it;
2922         for (it = libPathRegexes.begin(); it != libPathRegexes.end(); ++it) {
2923             Regex* regex = new Regex(*it, 0);
2924             std::string error;
2925             assert(regex->isValid(error));
2926             regexes.push_back(regex);
2927         }
2928         regexesInitialized = true;
2929     }
2930     if (DID) {
2931         std::string relPath;
2932         PassUtil::getDbgLocationInfo(*DID, baseBuildDir, NULL, NULL, &relPath);
2933         for(unsigned i=0;i<regexes.size();i++) {
2934             if(regexes[i]->match(relPath, NULL)) {
2935                 return true;
2936             }
2937         }
2938     }
2939     return PassUtil::matchRegexes(GV->getSection(), extLibSectionRegexes);
2940 }
2941
2942 bool MagicPass::isMagicGV(Module &M, GlobalVariable *GV)
2943 {
2944     if (GV->isThreadLocal() && (GV->getName().startswith(MAGIC_PREFIX_STR) || GV->getName().startswith("rcu"))) {
2945         return true;
2946     }
2947     if (!StringRef(GV->getSection()).compare(MAGIC_LLVM_METADATA_SECTION)) {
2948         return true;
2949     }
2950     if (GV->getName().startswith("__start") || GV->getName().startswith("__stop") || GV->getName().startswith("llvm.")) {
2951         return true;
2952     }
2953     return PassUtil::matchRegexes(GV->getSection(), magicDataSectionRegexes);
2954 }
2955
2956 bool MagicPass::isMagicFunction(Module &M, Function *F)
2957 {
2958         if (F->getName().startswith("llvm.")) return true;
2959     return PassUtil::matchRegexes(F->getSection(), magicFunctionSectionRegexes);
2960 }
2961
2962 #if MAGIC_USE_QPROF_INSTRUMENTATION
2963
2964 void MagicPass::qprofInstrumentationInit(Module &M)
2965 {
2966     // look up qprof configuration
2967     qprofConf = QProfConf::get(M, &magicLLSitestacks,
2968         &magicDeepestLLLoops,
2969         &magicDeepestLLLibs,
2970         &magicTaskClasses);
2971     qprofConf->mergeAllTaskClassesWithSameDeepestLLLoops();
2972
2973 #if DEBUG_QPROF
2974     qprofConf->print(errs());
2975 #endif
2976 }
2977
2978 void MagicPass::qprofInstrumentationApply(Module &M)
2979 {
2980     Function *hook;
2981     std::vector<Value*> hookParams;
2982     QProfSite* site;
2983     std::vector<TYPECONST Type*>functionTyArgs;
2984     FunctionType *hookFunctionTy;
2985
2986     /*
2987      * Instrument deepest long-lived loops. This creates a function
2988      * pointer of the form void (*MAGIC_DEEPEST_LL_LOOP_HOOK_NAME)(char*, int)
2989      * called (if set by instrumentation libraries) at the top of every loop.
2990      */
2991     functionTyArgs.push_back(PointerType::get(IntegerType::get(M.getContext(), 8), 0));
2992     functionTyArgs.push_back(IntegerType::get(M.getContext(), 32));
2993     hookFunctionTy = PassUtil::getFunctionType(Type::getVoidTy(M.getContext()), functionTyArgs, false);
2994     std::vector<QProfSite*> deepestLLLoops = qprofConf->getDeepestLLLoops();
2995     hook = PassUtil::getOrInsertFunction(M, MAGIC_DEEPEST_LL_LOOP_HOOK_NAME, hookFunctionTy,
2996         PASS_UTIL_LINKAGE_WEAK_POINTER, PASS_UTIL_FLAG(PASS_UTIL_PROP_PRESERVE));
2997     assert(hook);
2998     for (unsigned i=0;i<deepestLLLoops.size();i++) {
2999         site = deepestLLLoops[i];
3000         hookParams.clear();
3001         Constant* siteString = MagicUtil::getArrayPtr(M, MagicUtil::getStringRef(M, site->toString()));
3002         hookParams.push_back(siteString);
3003         hookParams.push_back(ConstantInt::get(M.getContext(), APInt(32, site->taskClassID, 10)));
3004         PassUtil::createCallInstruction(hook, hookParams, "", site->siteInstruction);
3005     }
3006
3007     /*
3008      * Instrument deepest long-lived library calls. This creates a function
3009      * pointer of the form void (*MAGIC_DEEPEST_LL_LIB_HOOK_NAME)(char*, int, int, int)
3010      * called (if set by instrumentation libraries) before every library call.
3011      */
3012     functionTyArgs.clear();
3013     functionTyArgs.push_back(PointerType::get(IntegerType::get(M.getContext(), 8), 0));
3014     functionTyArgs.push_back(IntegerType::get(M.getContext(), 32));
3015     functionTyArgs.push_back(IntegerType::get(M.getContext(), 32));
3016     functionTyArgs.push_back(IntegerType::get(M.getContext(), 32));
3017     hookFunctionTy = PassUtil::getFunctionType(Type::getVoidTy(M.getContext()), functionTyArgs, false);
3018     std::vector<QProfSite*> deepestLLLibs = qprofConf->getDeepestLLLibs();
3019     hook = PassUtil::getOrInsertFunction(M, MAGIC_DEEPEST_LL_LIB_HOOK_NAME, hookFunctionTy,
3020         PASS_UTIL_LINKAGE_WEAK_POINTER, PASS_UTIL_FLAG(PASS_UTIL_PROP_PRESERVE));
3021     assert(hook);
3022     for (unsigned i=0;i<deepestLLLibs.size();i++) {
3023         site = deepestLLLibs[i];
3024         hookParams.clear();
3025         Constant* siteString = MagicUtil::getArrayPtr(M, MagicUtil::getStringRef(M, site->toString()));
3026         hookParams.push_back(siteString);
3027         hookParams.push_back(ConstantInt::get(M.getContext(), APInt(32, site->taskClassID, 10)));
3028         hookParams.push_back(ConstantInt::get(M.getContext(), APInt(32, site->taskSiteID, 10)));
3029         hookParams.push_back(ConstantInt::get(M.getContext(), APInt(32, site->libFlags, 10)));
3030         PassUtil::createCallInstruction(hook, hookParams, "", site->siteInstruction);
3031     }
3032
3033     /*
3034      * Create relevant exported variables in use by the libraries.
3035      */
3036     MagicUtil::getExportedIntGlobalVar(M, MAGIC_NUM_LL_TASK_CLASSES_NAME, qprofConf->getNumLLTaskClasses());
3037     MagicUtil::getExportedIntGlobalVar(M, MAGIC_NUM_LL_BLOCK_EXT_TASK_CLASSES_NAME, qprofConf->getNumLLBlockExtTaskClasses());
3038     MagicUtil::getExportedIntGlobalVar(M, MAGIC_NUM_LL_BLOCK_INT_TASK_CLASSES_NAME, qprofConf->getNumLLBlockIntTaskClasses());
3039     MagicUtil::getExportedIntGlobalVar(M, MAGIC_NUM_LL_BLOCK_EXT_LIBS_NAME, qprofConf->getNumLLBlockExtLibs());
3040     MagicUtil::getExportedIntGlobalVar(M, MAGIC_NUM_LL_BLOCK_INT_LIBS_NAME, qprofConf->getNumLLBlockIntLibs());
3041 }
3042
3043 #else
3044
3045 void MagicPass::qprofInstrumentationInit(Module &M) {}
3046 void MagicPass::qprofInstrumentationApply(Module &M) {}
3047
3048 #endif
3049
3050 } // end namespace
3051
3052 char MagicPass::ID = 0;
3053 RegisterPass<MagicPass> MP("magic", "Magic Pass to Build a Table of Global Variables");
3054