lib/CodeGen/MachineModuleInfo.cpp

   1 //===-- llvm/CodeGen/MachineModuleInfo.cpp ----------------------*- C++ -*-===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9
  10 #include "llvm/CodeGen/MachineModuleInfo.h"
  11
  12 #include "llvm/Constants.h"
  13 #include "llvm/Analysis/ValueTracking.h"
  14 #include "llvm/CodeGen/MachineFunctionPass.h"
  15 #include "llvm/CodeGen/MachineFunction.h"
  16 #include "llvm/CodeGen/MachineLocation.h"
  17 #include "llvm/CodeGen/MachineDebugInfoDesc.h"
  18 #include "llvm/Target/TargetInstrInfo.h"
  19 #include "llvm/Target/TargetMachine.h"
  20 #include "llvm/Target/TargetOptions.h"
  21 #include "llvm/DerivedTypes.h"
  22 #include "llvm/GlobalVariable.h"
  23 #include "llvm/Intrinsics.h"
  24 #include "llvm/Instructions.h"
  25 #include "llvm/Module.h"
  26 #include "llvm/Support/Dwarf.h"
  27 #include "llvm/Support/Streams.h"
  28 using namespace llvm;
  29 using namespace llvm::dwarf;
  30
  31 // Handle the Pass registration stuff necessary to use TargetData's.
  32 static RegisterPass<MachineModuleInfo>
  33 X("machinemoduleinfo", "Module Information");
  34 char MachineModuleInfo::ID = 0;
  35
  36 //===----------------------------------------------------------------------===//
  37
  38 /// getGlobalVariablesUsing - Return all of the GlobalVariables which have the
  39 /// specified value in their initializer somewhere.
  40 static void
  41 getGlobalVariablesUsing(Value *V, std::vector<GlobalVariable*> &Result) {
  42   // Scan though value users.
  43   for (Value::use_iterator I = V->use_begin(), E = V->use_end(); I != E; ++I) {
  44     if (GlobalVariable *GV = dyn_cast<GlobalVariable>(*I)) {
  45       // If the user is a GlobalVariable then add to result.
  46       Result.push_back(GV);
  47     } else if (Constant *C = dyn_cast<Constant>(*I)) {
  48       // If the user is a constant variable then scan its users
  49       getGlobalVariablesUsing(C, Result);
  50     }
  51   }
  52 }
  53
  54 /// getGlobalVariablesUsing - Return all of the GlobalVariables that use the
  55 /// named GlobalVariable.
  56 static void
  57 getGlobalVariablesUsing(Module &M, const std::string &RootName,
  58                         std::vector<GlobalVariable*> &Result) {
  59   std::vector<const Type*> FieldTypes;
  60   FieldTypes.push_back(Type::Int32Ty);
  61   FieldTypes.push_back(Type::Int32Ty);
  62
  63   // Get the GlobalVariable root.
  64   GlobalVariable *UseRoot = M.getGlobalVariable(RootName,
  65                                                 StructType::get(FieldTypes));
  66
  67   // If present and linkonce then scan for users.
  68   if (UseRoot && UseRoot->hasLinkOnceLinkage())
  69     getGlobalVariablesUsing(UseRoot, Result);
  70 }
  71
  72 /// isStringValue - Return true if the given value can be coerced to a string.
  73 ///
  74 static bool isStringValue(Value *V) {
  75   if (GlobalVariable *GV = dyn_cast<GlobalVariable>(V)) {
  76     if (GV->hasInitializer() && isa<ConstantArray>(GV->getInitializer())) {
  77       ConstantArray *Init = cast<ConstantArray>(GV->getInitializer());
  78       return Init->isString();
  79     }
  80   } else if (Constant *C = dyn_cast<Constant>(V)) {
  81     if (GlobalValue *GV = dyn_cast<GlobalValue>(C))
  82       return isStringValue(GV);
  83     else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(C)) {
  84       if (CE->getOpcode() == Instruction::GetElementPtr) {
  85         if (CE->getNumOperands() == 3 &&
  86             cast<Constant>(CE->getOperand(1))->isNullValue() &&
  87             isa<ConstantInt>(CE->getOperand(2))) {
  88           return isStringValue(CE->getOperand(0));
  89         }
  90       }
  91     }
  92   }
  93   return false;
  94 }
  95
  96 /// getGlobalVariable - Return either a direct or cast Global value.
  97 ///
  98 static GlobalVariable *getGlobalVariable(Value *V) {
  99   if (GlobalVariable *GV = dyn_cast<GlobalVariable>(V)) {
 100     return GV;
 101   } else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V)) {
 102     if (CE->getOpcode() == Instruction::BitCast) {
 103       return dyn_cast<GlobalVariable>(CE->getOperand(0));
 104     } else if (CE->getOpcode() == Instruction::GetElementPtr) {
 105       for (unsigned int i=1; i<CE->getNumOperands(); i++) {
 106         if (!CE->getOperand(i)->isNullValue())
 107           return NULL;
 108       }
 109       return dyn_cast<GlobalVariable>(CE->getOperand(0));
 110     }
 111   }
 112   return NULL;
 113 }
 114
 115 /// isGlobalVariable - Return true if the given value can be coerced to a
 116 /// GlobalVariable.
 117 static bool isGlobalVariable(Value *V) {
 118   if (isa<GlobalVariable>(V) || isa<ConstantPointerNull>(V)) {
 119     return true;
 120   } else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V)) {
 121     if (CE->getOpcode() == Instruction::BitCast) {
 122       return isa<GlobalVariable>(CE->getOperand(0));
 123     } else if (CE->getOpcode() == Instruction::GetElementPtr) {
 124       for (unsigned int i=1; i<CE->getNumOperands(); i++) {
 125         if (!CE->getOperand(i)->isNullValue())
 126           return false;
 127       }
 128       return isa<GlobalVariable>(CE->getOperand(0));
 129     }
 130   }
 131   return false;
 132 }
 133
 134 //===----------------------------------------------------------------------===//
 135
 136 /// ApplyToFields - Target the visitor to each field of the debug information
 137 /// descriptor.
 138 void DIVisitor::ApplyToFields(DebugInfoDesc *DD) {
 139   DD->ApplyToFields(this);
 140 }
 141
 142 namespace {
 143
 144 //===----------------------------------------------------------------------===//
 145 /// DICountVisitor - This DIVisitor counts all the fields in the supplied debug
 146 /// the supplied DebugInfoDesc.
 147 class DICountVisitor : public DIVisitor {
 148 private:
 149   unsigned Count;                       // Running count of fields.
 150
 151 public:
 152   DICountVisitor() : DIVisitor(), Count(0) {}
 153
 154   // Accessors.
 155   unsigned getCount() const { return Count; }
 156
 157   /// Apply - Count each of the fields.
 158   ///
 159   virtual void Apply(int &Field)             { ++Count; }
 160   virtual void Apply(unsigned &Field)        { ++Count; }
 161   virtual void Apply(int64_t &Field)         { ++Count; }
 162   virtual void Apply(uint64_t &Field)        { ++Count; }
 163   virtual void Apply(bool &Field)            { ++Count; }
 164   virtual void Apply(std::string &Field)     { ++Count; }
 165   virtual void Apply(DebugInfoDesc *&Field)  { ++Count; }
 166   virtual void Apply(GlobalVariable *&Field) { ++Count; }
 167   virtual void Apply(std::vector<DebugInfoDesc *> &Field) {
 168     ++Count;
 169   }
 170 };
 171
 172 //===----------------------------------------------------------------------===//
 173 /// DIDeserializeVisitor - This DIVisitor deserializes all the fields in the
 174 /// supplied DebugInfoDesc.
 175 class DIDeserializeVisitor : public DIVisitor {
 176 private:
 177   DIDeserializer &DR;                   // Active deserializer.
 178   unsigned I;                           // Current operand index.
 179   ConstantStruct *CI;                   // GlobalVariable constant initializer.
 180
 181 public:
 182   DIDeserializeVisitor(DIDeserializer &D, GlobalVariable *GV)
 183     : DIVisitor(), DR(D), I(0), CI(cast<ConstantStruct>(GV->getInitializer()))
 184   {}
 185
 186   /// Apply - Set the value of each of the fields.
 187   ///
 188   virtual void Apply(int &Field) {
 189     Constant *C = CI->getOperand(I++);
 190     Field = cast<ConstantInt>(C)->getSExtValue();
 191   }
 192   virtual void Apply(unsigned &Field) {
 193     Constant *C = CI->getOperand(I++);
 194     Field = cast<ConstantInt>(C)->getZExtValue();
 195   }
 196   virtual void Apply(int64_t &Field) {
 197     Constant *C = CI->getOperand(I++);
 198     Field = cast<ConstantInt>(C)->getSExtValue();
 199   }
 200   virtual void Apply(uint64_t &Field) {
 201     Constant *C = CI->getOperand(I++);
 202     Field = cast<ConstantInt>(C)->getZExtValue();
 203   }
 204   virtual void Apply(bool &Field) {
 205     Constant *C = CI->getOperand(I++);
 206     Field = cast<ConstantInt>(C)->getZExtValue();
 207   }
 208   virtual void Apply(std::string &Field) {
 209     Constant *C = CI->getOperand(I++);
 210     // Fills in the string if it succeeds
 211     if (!GetConstantStringInfo(C, Field))
 212       Field.clear();
 213   }
 214   virtual void Apply(DebugInfoDesc *&Field) {
 215     Constant *C = CI->getOperand(I++);
 216     Field = DR.Deserialize(C);
 217   }
 218   virtual void Apply(GlobalVariable *&Field) {
 219     Constant *C = CI->getOperand(I++);
 220     Field = getGlobalVariable(C);
 221   }
 222   virtual void Apply(std::vector<DebugInfoDesc *> &Field) {
 223     Field.resize(0);
 224     Constant *C = CI->getOperand(I++);
 225     GlobalVariable *GV = getGlobalVariable(C);
 226     if (GV->hasInitializer()) {
 227       if (ConstantArray *CA = dyn_cast<ConstantArray>(GV->getInitializer())) {
 228         for (unsigned i = 0, N = CA->getNumOperands(); i < N; ++i) {
 229           GlobalVariable *GVE = getGlobalVariable(CA->getOperand(i));
 230           DebugInfoDesc *DE = DR.Deserialize(GVE);
 231           Field.push_back(DE);
 232         }
 233       } else if (GV->getInitializer()->isNullValue()) {
 234         if (const ArrayType *T =
 235             dyn_cast<ArrayType>(GV->getType()->getElementType())) {
 236           Field.resize(T->getNumElements());
 237         }
 238       }
 239     }
 240   }
 241 };
 242
 243 //===----------------------------------------------------------------------===//
 244 /// DISerializeVisitor - This DIVisitor serializes all the fields in
 245 /// the supplied DebugInfoDesc.
 246 class DISerializeVisitor : public DIVisitor {
 247 private:
 248   DISerializer &SR;                     // Active serializer.
 249   std::vector<Constant*> &Elements;     // Element accumulator.
 250
 251 public:
 252   DISerializeVisitor(DISerializer &S, std::vector<Constant*> &E)
 253   : DIVisitor()
 254   , SR(S)
 255   , Elements(E)
 256   {}
 257
 258   /// Apply - Set the value of each of the fields.
 259   ///
 260   virtual void Apply(int &Field) {
 261     Elements.push_back(ConstantInt::get(Type::Int32Ty, int32_t(Field)));
 262   }
 263   virtual void Apply(unsigned &Field) {
 264     Elements.push_back(ConstantInt::get(Type::Int32Ty, uint32_t(Field)));
 265   }
 266   virtual void Apply(int64_t &Field) {
 267     Elements.push_back(ConstantInt::get(Type::Int64Ty, int64_t(Field)));
 268   }
 269   virtual void Apply(uint64_t &Field) {
 270     Elements.push_back(ConstantInt::get(Type::Int64Ty, uint64_t(Field)));
 271   }
 272   virtual void Apply(bool &Field) {
 273     Elements.push_back(ConstantInt::get(Type::Int1Ty, Field));
 274   }
 275   virtual void Apply(std::string &Field) {
 276     Elements.push_back(SR.getString(Field));
 277   }
 278   virtual void Apply(DebugInfoDesc *&Field) {
 279     GlobalVariable *GV = NULL;
 280
 281     // If non-NULL then convert to global.
 282     if (Field) GV = SR.Serialize(Field);
 283
 284     // FIXME - At some point should use specific type.
 285     const PointerType *EmptyTy = SR.getEmptyStructPtrType();
 286
 287     if (GV) {
 288       // Set to pointer to global.
 289       Elements.push_back(ConstantExpr::getBitCast(GV, EmptyTy));
 290     } else {
 291       // Use NULL.
 292       Elements.push_back(ConstantPointerNull::get(EmptyTy));
 293     }
 294   }
 295   virtual void Apply(GlobalVariable *&Field) {
 296     const PointerType *EmptyTy = SR.getEmptyStructPtrType();
 297     if (Field) {
 298       Elements.push_back(ConstantExpr::getBitCast(Field, EmptyTy));
 299     } else {
 300       Elements.push_back(ConstantPointerNull::get(EmptyTy));
 301     }
 302   }
 303   virtual void Apply(std::vector<DebugInfoDesc *> &Field) {
 304     const PointerType *EmptyTy = SR.getEmptyStructPtrType();
 305     unsigned N = Field.size();
 306     ArrayType *AT = ArrayType::get(EmptyTy, N);
 307     std::vector<Constant *> ArrayElements;
 308
 309     for (unsigned i = 0; i < N; ++i) {
 310       if (DebugInfoDesc *Element = Field[i]) {
 311         GlobalVariable *GVE = SR.Serialize(Element);
 312         Constant *CE = ConstantExpr::getBitCast(GVE, EmptyTy);
 313         ArrayElements.push_back(cast<Constant>(CE));
 314       } else {
 315         ArrayElements.push_back(ConstantPointerNull::get(EmptyTy));
 316       }
 317     }
 318
 319     Constant *CA = ConstantArray::get(AT, ArrayElements);
 320     GlobalVariable *CAGV = new GlobalVariable(AT, true,
 321                                               GlobalValue::InternalLinkage,
 322                                               CA, "llvm.dbg.array",
 323                                               SR.getModule());
 324     CAGV->setSection("llvm.metadata");
 325     Constant *CAE = ConstantExpr::getBitCast(CAGV, EmptyTy);
 326     Elements.push_back(CAE);
 327   }
 328 };
 329
 330 //===----------------------------------------------------------------------===//
 331 /// DIGetTypesVisitor - This DIVisitor gathers all the field types in
 332 /// the supplied DebugInfoDesc.
 333 class DIGetTypesVisitor : public DIVisitor {
 334 private:
 335   DISerializer &SR;                     // Active serializer.
 336   std::vector<const Type*> &Fields;     // Type accumulator.
 337
 338 public:
 339   DIGetTypesVisitor(DISerializer &S, std::vector<const Type*> &F)
 340   : DIVisitor()
 341   , SR(S)
 342   , Fields(F)
 343   {}
 344
 345   /// Apply - Set the value of each of the fields.
 346   ///
 347   virtual void Apply(int &Field) {
 348     Fields.push_back(Type::Int32Ty);
 349   }
 350   virtual void Apply(unsigned &Field) {
 351     Fields.push_back(Type::Int32Ty);
 352   }
 353   virtual void Apply(int64_t &Field) {
 354     Fields.push_back(Type::Int64Ty);
 355   }
 356   virtual void Apply(uint64_t &Field) {
 357     Fields.push_back(Type::Int64Ty);
 358   }
 359   virtual void Apply(bool &Field) {
 360     Fields.push_back(Type::Int1Ty);
 361   }
 362   virtual void Apply(std::string &Field) {
 363     Fields.push_back(SR.getStrPtrType());
 364   }
 365   virtual void Apply(DebugInfoDesc *&Field) {
 366     // FIXME - At some point should use specific type.
 367     const PointerType *EmptyTy = SR.getEmptyStructPtrType();
 368     Fields.push_back(EmptyTy);
 369   }
 370   virtual void Apply(GlobalVariable *&Field) {
 371     const PointerType *EmptyTy = SR.getEmptyStructPtrType();
 372     Fields.push_back(EmptyTy);
 373   }
 374   virtual void Apply(std::vector<DebugInfoDesc *> &Field) {
 375     const PointerType *EmptyTy = SR.getEmptyStructPtrType();
 376     Fields.push_back(EmptyTy);
 377   }
 378 };
 379
 380 //===----------------------------------------------------------------------===//
 381 /// DIVerifyVisitor - This DIVisitor verifies all the field types against
 382 /// a constant initializer.
 383 class DIVerifyVisitor : public DIVisitor {
 384 private:
 385   DIVerifier &VR;                       // Active verifier.
 386   bool IsValid;                         // Validity status.
 387   unsigned I;                           // Current operand index.
 388   ConstantStruct *CI;                   // GlobalVariable constant initializer.
 389
 390 public:
 391   DIVerifyVisitor(DIVerifier &V, GlobalVariable *GV)
 392   : DIVisitor()
 393   , VR(V)
 394   , IsValid(true)
 395   , I(0)
 396   , CI(cast<ConstantStruct>(GV->getInitializer()))
 397   {
 398   }
 399
 400   // Accessors.
 401   bool isValid() const { return IsValid; }
 402
 403   /// Apply - Set the value of each of the fields.
 404   ///
 405   virtual void Apply(int &Field) {
 406     Constant *C = CI->getOperand(I++);
 407     IsValid = IsValid && isa<ConstantInt>(C);
 408   }
 409   virtual void Apply(unsigned &Field) {
 410     Constant *C = CI->getOperand(I++);
 411     IsValid = IsValid && isa<ConstantInt>(C);
 412   }
 413   virtual void Apply(int64_t &Field) {
 414     Constant *C = CI->getOperand(I++);
 415     IsValid = IsValid && isa<ConstantInt>(C);
 416   }
 417   virtual void Apply(uint64_t &Field) {
 418     Constant *C = CI->getOperand(I++);
 419     IsValid = IsValid && isa<ConstantInt>(C);
 420   }
 421   virtual void Apply(bool &Field) {
 422     Constant *C = CI->getOperand(I++);
 423     IsValid = IsValid && isa<ConstantInt>(C) && C->getType() == Type::Int1Ty;
 424   }
 425   virtual void Apply(std::string &Field) {
 426     Constant *C = CI->getOperand(I++);
 427     IsValid = IsValid &&
 428               (!C || isStringValue(C) || C->isNullValue());
 429   }
 430   virtual void Apply(DebugInfoDesc *&Field) {
 431     // FIXME - Prepare the correct descriptor.
 432     Constant *C = CI->getOperand(I++);
 433     IsValid = IsValid && isGlobalVariable(C);
 434   }
 435   virtual void Apply(GlobalVariable *&Field) {
 436     Constant *C = CI->getOperand(I++);
 437     IsValid = IsValid && isGlobalVariable(C);
 438   }
 439   virtual void Apply(std::vector<DebugInfoDesc *> &Field) {
 440     Constant *C = CI->getOperand(I++);
 441     IsValid = IsValid && isGlobalVariable(C);
 442     if (!IsValid) return;
 443
 444     GlobalVariable *GV = getGlobalVariable(C);
 445     IsValid = IsValid && GV && GV->hasInitializer();
 446     if (!IsValid) return;
 447
 448     ConstantArray *CA = dyn_cast<ConstantArray>(GV->getInitializer());
 449     IsValid = IsValid && CA;
 450     if (!IsValid) return;
 451
 452     for (unsigned i = 0, N = CA->getNumOperands(); IsValid && i < N; ++i) {
 453       IsValid = IsValid && isGlobalVariable(CA->getOperand(i));
 454       if (!IsValid) return;
 455
 456       GlobalVariable *GVE = getGlobalVariable(CA->getOperand(i));
 457       VR.Verify(GVE);
 458     }
 459   }
 460 };
 461
 462 }
 463
 464 //===----------------------------------------------------------------------===//
 465
 466 DebugInfoDesc *DIDeserializer::Deserialize(Value *V) {
 467   return Deserialize(getGlobalVariable(V));
 468 }
 469 DebugInfoDesc *DIDeserializer::Deserialize(GlobalVariable *GV) {
 470   // Handle NULL.
 471   if (!GV) return NULL;
 472
 473   // Check to see if it has been already deserialized.
 474   DebugInfoDesc *&Slot = GlobalDescs[GV];
 475   if (Slot) return Slot;
 476
 477   // Get the Tag from the global.
 478   unsigned Tag = DebugInfoDesc::TagFromGlobal(GV);
 479
 480   // Create an empty instance of the correct sort.
 481   Slot = DebugInfoDesc::DescFactory(Tag);
 482
 483   // If not a user defined descriptor.
 484   if (Slot) {
 485     // Deserialize the fields.
 486     DIDeserializeVisitor DRAM(*this, GV);
 487     DRAM.ApplyToFields(Slot);
 488   }
 489
 490   return Slot;
 491 }
 492
 493 //===----------------------------------------------------------------------===//
 494
 495 /// getStrPtrType - Return a "sbyte *" type.
 496 ///
 497 const PointerType *DISerializer::getStrPtrType() {
 498   // If not already defined.
 499   if (!StrPtrTy) {
 500     // Construct the pointer to signed bytes.
 501     StrPtrTy = PointerType::getUnqual(Type::Int8Ty);
 502   }
 503
 504   return StrPtrTy;
 505 }
 506
 507 /// getEmptyStructPtrType - Return a "{ }*" type.
 508 ///
 509 const PointerType *DISerializer::getEmptyStructPtrType() {
 510   // If not already defined.
 511   if (EmptyStructPtrTy) return EmptyStructPtrTy;
 512
 513   // Construct the pointer to empty structure type.
 514   const StructType *EmptyStructTy =
 515     StructType::get(std::vector<const Type*>());
 516
 517   // Construct the pointer to empty structure type.
 518   EmptyStructPtrTy = PointerType::getUnqual(EmptyStructTy);
 519   return EmptyStructPtrTy;
 520 }
 521
 522 /// getTagType - Return the type describing the specified descriptor (via tag.)
 523 ///
 524 const StructType *DISerializer::getTagType(DebugInfoDesc *DD) {
 525   // Attempt to get the previously defined type.
 526   StructType *&Ty = TagTypes[DD->getTag()];
 527
 528   // If not already defined.
 529   if (!Ty) {
 530     // Set up fields vector.
 531     std::vector<const Type*> Fields;
 532     // Get types of fields.
 533     DIGetTypesVisitor GTAM(*this, Fields);
 534     GTAM.ApplyToFields(DD);
 535
 536     // Construct structured type.
 537     Ty = StructType::get(Fields);
 538
 539     // Register type name with module.
 540     M->addTypeName(DD->getTypeString(), Ty);
 541   }
 542
 543   return Ty;
 544 }
 545
 546 /// getString - Construct the string as constant string global.
 547 ///
 548 Constant *DISerializer::getString(const std::string &String) {
 549   // Check string cache for previous edition.
 550   Constant *&Slot = StringCache[String.c_str()];
 551
 552   // Return Constant if previously defined.
 553   if (Slot) return Slot;
 554
 555   // If empty string then use a sbyte* null instead.
 556   if (String.empty()) {
 557     Slot = ConstantPointerNull::get(getStrPtrType());
 558   } else {
 559     // Construct string as an llvm constant.
 560     Constant *ConstStr = ConstantArray::get(String);
 561
 562     // Otherwise create and return a new string global.
 563     GlobalVariable *StrGV = new GlobalVariable(ConstStr->getType(), true,
 564                                                GlobalVariable::InternalLinkage,
 565                                                ConstStr, ".str", M);
 566     StrGV->setSection("llvm.metadata");
 567
 568     // Convert to generic string pointer.
 569     Slot = ConstantExpr::getBitCast(StrGV, getStrPtrType());
 570   }
 571
 572   return Slot;
 573
 574 }
 575
 576 /// Serialize - Recursively cast the specified descriptor into a GlobalVariable
 577 /// so that it can be serialized to a .bc or .ll file.
 578 GlobalVariable *DISerializer::Serialize(DebugInfoDesc *DD) {
 579   // Check if the DebugInfoDesc is already in the map.
 580   GlobalVariable *&Slot = DescGlobals[DD];
 581
 582   // See if DebugInfoDesc exists, if so return prior GlobalVariable.
 583   if (Slot) return Slot;
 584
 585   // Get the type associated with the Tag.
 586   const StructType *Ty = getTagType(DD);
 587
 588   // Create the GlobalVariable early to prevent infinite recursion.
 589   GlobalVariable *GV =
 590     new GlobalVariable(Ty, true,
 591                        (GlobalValue::LinkageTypes)DD->getLinkage(),
 592                        NULL, DD->getDescString(), M);
 593   GV->setSection("llvm.metadata");
 594
 595   // Insert new GlobalVariable in DescGlobals map.
 596   Slot = GV;
 597
 598   // Set up elements vector
 599   std::vector<Constant*> Elements;
 600   // Add fields.
 601   DISerializeVisitor SRAM(*this, Elements);
 602   SRAM.ApplyToFields(DD);
 603
 604   // Set the globals initializer.
 605   GV->setInitializer(ConstantStruct::get(Ty, Elements));
 606
 607   return GV;
 608 }
 609
 610 /// addDescriptor - Directly connect DD with existing GV.
 611 void DISerializer::addDescriptor(DebugInfoDesc *DD,
 612                                  GlobalVariable *GV) {
 613   DescGlobals[DD] = GV;
 614 }
 615
 616 //===----------------------------------------------------------------------===//
 617
 618 /// Verify - Return true if the GlobalVariable appears to be a valid
 619 /// serialization of a DebugInfoDesc.
 620 bool DIVerifier::Verify(Value *V) {
 621   return !V || Verify(getGlobalVariable(V));
 622 }
 623 bool DIVerifier::Verify(GlobalVariable *GV) {
 624   // NULLs are valid.
 625   if (!GV) return true;
 626
 627   // Check prior validity.
 628   unsigned &ValiditySlot = Validity[GV];
 629
 630   // If visited before then use old state.
 631   if (ValiditySlot) return ValiditySlot == Valid;
 632
 633   // Assume validity for the time being (recursion.)
 634   ValiditySlot = Valid;
 635
 636   // Make sure the global is internal or link once (anchor.)
 637   if (GV->getLinkage() != GlobalValue::InternalLinkage &&
 638       GV->getLinkage() != GlobalValue::LinkOnceLinkage) {
 639     ValiditySlot = Invalid;
 640     return false;
 641   }
 642
 643   // Get the Tag.
 644   unsigned Tag = DebugInfoDesc::TagFromGlobal(GV);
 645
 646   // Check for user defined descriptors.
 647   if (Tag == DW_TAG_invalid) {
 648     ValiditySlot = Valid;
 649     return true;
 650   }
 651
 652   // Get the Version.
 653   unsigned Version = DebugInfoDesc::VersionFromGlobal(GV);
 654
 655   // Check for version mismatch.
 656   if (Version != LLVMDebugVersion) {
 657     ValiditySlot = Invalid;
 658     return false;
 659   }
 660
 661   // Construct an empty DebugInfoDesc.
 662   DebugInfoDesc *DD = DebugInfoDesc::DescFactory(Tag);
 663
 664   // Allow for user defined descriptors.
 665   if (!DD) return true;
 666
 667   // Get the initializer constant.
 668   ConstantStruct *CI = cast<ConstantStruct>(GV->getInitializer());
 669
 670   // Get the operand count.
 671   unsigned N = CI->getNumOperands();
 672
 673   // Get the field count.
 674   unsigned &CountSlot = Counts[Tag];
 675   if (!CountSlot) {
 676     // Check the operand count to the field count
 677     DICountVisitor CTAM;
 678     CTAM.ApplyToFields(DD);
 679     CountSlot = CTAM.getCount();
 680   }
 681
 682   // Field count must be at most equal operand count.
 683   if (CountSlot >  N) {
 684     delete DD;
 685     ValiditySlot = Invalid;
 686     return false;
 687   }
 688
 689   // Check each field for valid type.
 690   DIVerifyVisitor VRAM(*this, GV);
 691   VRAM.ApplyToFields(DD);
 692
 693   // Release empty DebugInfoDesc.
 694   delete DD;
 695
 696   // If fields are not valid.
 697   if (!VRAM.isValid()) {
 698     ValiditySlot = Invalid;
 699     return false;
 700   }
 701
 702   return true;
 703 }
 704
 705 /// isVerified - Return true if the specified GV has already been
 706 /// verified as a debug information descriptor.
 707 bool DIVerifier::isVerified(GlobalVariable *GV) {
 708   unsigned &ValiditySlot = Validity[GV];
 709   if (ValiditySlot) return ValiditySlot == Valid;
 710   return false;
 711 }
 712
 713 //===----------------------------------------------------------------------===//
 714
 715 DebugScope::~DebugScope() {
 716   for (unsigned i = 0, e = Scopes.size(); i < e; ++i) delete Scopes[i];
 717   for (unsigned i = 0, e = Variables.size(); i < e; ++i) delete Variables[i];
 718 }
 719
 720 //===----------------------------------------------------------------------===//
 721
 722 MachineModuleInfo::MachineModuleInfo()
 723 : ImmutablePass((intptr_t)&ID)
 724 , DR()
 725 , VR()
 726 , CompileUnits()
 727 , Directories()
 728 , SourceFiles()
 729 , Lines()
 730 , LabelIDList()
 731 , ScopeMap()
 732 , RootScope(NULL)
 733 , FrameMoves()
 734 , LandingPads()
 735 , Personalities()
 736 , CallsEHReturn(0)
 737 , CallsUnwindInit(0)
 738 {
 739   // Always emit "no personality" info
 740   Personalities.push_back(NULL);
 741 }
 742 MachineModuleInfo::~MachineModuleInfo() {
 743
 744 }
 745
 746 /// doInitialization - Initialize the state for a new module.
 747 ///
 748 bool MachineModuleInfo::doInitialization() {
 749   return false;
 750 }
 751
 752 /// doFinalization - Tear down the state after completion of a module.
 753 ///
 754 bool MachineModuleInfo::doFinalization() {
 755   return false;
 756 }
 757
 758 /// BeginFunction - Begin gathering function meta information.
 759 ///
 760 void MachineModuleInfo::BeginFunction(MachineFunction *MF) {
 761   // Coming soon.
 762 }
 763
 764 /// EndFunction - Discard function meta information.
 765 ///
 766 void MachineModuleInfo::EndFunction() {
 767   // Clean up scope information.
 768   if (RootScope) {
 769     delete RootScope;
 770     ScopeMap.clear();
 771     RootScope = NULL;
 772   }
 773
 774   // Clean up line info.
 775   Lines.clear();
 776
 777   // Clean up frame info.
 778   FrameMoves.clear();
 779
 780   // Clean up exception info.
 781   LandingPads.clear();
 782   TypeInfos.clear();
 783   FilterIds.clear();
 784   FilterEnds.clear();
 785   CallsEHReturn = 0;
 786   CallsUnwindInit = 0;
 787 }
 788
 789 /// getDescFor - Convert a Value to a debug information descriptor.
 790 ///
 791 // FIXME - use new Value type when available.
 792 DebugInfoDesc *MachineModuleInfo::getDescFor(Value *V) {
 793   return DR.Deserialize(V);
 794 }
 795
 796 /// AnalyzeModule - Scan the module for global debug information.
 797 ///
 798 void MachineModuleInfo::AnalyzeModule(Module &M) {
 799   SetupCompileUnits(M);
 800
 801   // Insert functions in the llvm.used array into UsedFunctions.
 802   GlobalVariable *GV = M.getGlobalVariable("llvm.used");
 803   if (!GV || !GV->hasInitializer()) return;
 804
 805   // Should be an array of 'i8*'.
 806   ConstantArray *InitList = dyn_cast<ConstantArray>(GV->getInitializer());
 807   if (InitList == 0) return;
 808
 809   for (unsigned i = 0, e = InitList->getNumOperands(); i != e; ++i) {
 810     if (ConstantExpr *CE = dyn_cast<ConstantExpr>(InitList->getOperand(i)))
 811       if (CE->getOpcode() == Instruction::BitCast)
 812         if (Function *F = dyn_cast<Function>(CE->getOperand(0)))
 813           UsedFunctions.insert(F);
 814   }
 815 }
 816
 817 /// SetupCompileUnits - Set up the unique vector of compile units.
 818 ///
 819 void MachineModuleInfo::SetupCompileUnits(Module &M) {
 820   std::vector<void*> CUList;
 821   CompileUnitDesc CUD;
 822   getAnchoredDescriptors(M, &CUD, CUList);
 823
 824   for (unsigned i = 0, e = CUList.size(); i < e; i++)
 825     CompileUnits.insert((CompileUnitDesc*)CUList[i]);
 826 }
 827
 828 /// getCompileUnits - Return a vector of debug compile units.
 829 ///
 830 const UniqueVector<CompileUnitDesc *> MachineModuleInfo::getCompileUnits()const{
 831   return CompileUnits;
 832 }
 833
 834 /// getAnchoredDescriptors - Return a vector of anchored debug descriptors.
 835 ///
 836 void
 837 MachineModuleInfo::getAnchoredDescriptors(Module &M, const AnchoredDesc *Desc,
 838                                           std::vector<void*> &AnchoredDescs) {
 839   std::vector<GlobalVariable*> Globals;
 840   getGlobalVariablesUsing(M, Desc->getAnchorString(), Globals);
 841
 842   for (unsigned i = 0, e = Globals.size(); i < e; ++i) {
 843     GlobalVariable *GV = Globals[i];
 844
 845     // FIXME - In the short term, changes are too drastic to continue.
 846     if (DebugInfoDesc::TagFromGlobal(GV) == Desc->getTag() &&
 847         DebugInfoDesc::VersionFromGlobal(GV) == LLVMDebugVersion)
 848       AnchoredDescs.push_back(DR.Deserialize(GV));
 849   }
 850 }
 851
 852 /// getGlobalVariablesUsing - Return all of the GlobalVariables that use the
 853 /// named GlobalVariable.
 854 void
 855 MachineModuleInfo::getGlobalVariablesUsing(Module &M,
 856                                            const std::string &RootName,
 857                                         std::vector<GlobalVariable*> &Globals) {
 858   return ::getGlobalVariablesUsing(M, RootName, Globals);
 859 }
 860
 861 /// RecordSourceLine - Records location information and associates it with a
 862 /// debug label.  Returns a unique label ID used to generate a label and
 863 /// provide correspondence to the source line list.
 864 unsigned MachineModuleInfo::RecordSourceLine(unsigned Line, unsigned Column,
 865                                              unsigned Source) {
 866   unsigned ID = NextLabelID();
 867   Lines.push_back(SourceLineInfo(Line, Column, Source, ID));
 868   return ID;
 869 }
 870
 871 /// RecordSource - Register a source file with debug info. Returns an source
 872 /// ID.
 873 unsigned MachineModuleInfo::RecordSource(const std::string &Directory,
 874                                          const std::string &Source) {
 875   unsigned DirectoryID = Directories.insert(Directory);
 876   return SourceFiles.insert(SourceFileInfo(DirectoryID, Source));
 877 }
 878 unsigned MachineModuleInfo::RecordSource(const CompileUnitDesc *CompileUnit) {
 879   return RecordSource(CompileUnit->getDirectory(),
 880                       CompileUnit->getFileName());
 881 }
 882
 883 /// RecordRegionStart - Indicate the start of a region.
 884 ///
 885 unsigned MachineModuleInfo::RecordRegionStart(Value *V) {
 886   // FIXME - need to be able to handle split scopes because of bb cloning.
 887   DebugInfoDesc *ScopeDesc = DR.Deserialize(V);
 888   DebugScope *Scope = getOrCreateScope(ScopeDesc);
 889   unsigned ID = NextLabelID();
 890   if (!Scope->getStartLabelID()) Scope->setStartLabelID(ID);
 891   return ID;
 892 }
 893
 894 /// RecordRegionEnd - Indicate the end of a region.
 895 ///
 896 unsigned MachineModuleInfo::RecordRegionEnd(Value *V) {
 897   // FIXME - need to be able to handle split scopes because of bb cloning.
 898   DebugInfoDesc *ScopeDesc = DR.Deserialize(V);
 899   DebugScope *Scope = getOrCreateScope(ScopeDesc);
 900   unsigned ID = NextLabelID();
 901   Scope->setEndLabelID(ID);
 902   return ID;
 903 }
 904
 905 /// RecordVariable - Indicate the declaration of  a local variable.
 906 ///
 907 void MachineModuleInfo::RecordVariable(GlobalValue *GV, unsigned FrameIndex) {
 908   VariableDesc *VD = cast<VariableDesc>(DR.Deserialize(GV));
 909   DebugScope *Scope = getOrCreateScope(VD->getContext());
 910   DebugVariable *DV = new DebugVariable(VD, FrameIndex);
 911   Scope->AddVariable(DV);
 912 }
 913
 914 /// getOrCreateScope - Returns the scope associated with the given descriptor.
 915 ///
 916 DebugScope *MachineModuleInfo::getOrCreateScope(DebugInfoDesc *ScopeDesc) {
 917   DebugScope *&Slot = ScopeMap[ScopeDesc];
 918   if (!Slot) {
 919     // FIXME - breaks down when the context is an inlined function.
 920     DebugInfoDesc *ParentDesc = NULL;
 921     if (BlockDesc *Block = dyn_cast<BlockDesc>(ScopeDesc)) {
 922       ParentDesc = Block->getContext();
 923     }
 924     DebugScope *Parent = ParentDesc ? getOrCreateScope(ParentDesc) : NULL;
 925     Slot = new DebugScope(Parent, ScopeDesc);
 926     if (Parent) {
 927       Parent->AddScope(Slot);
 928     } else if (RootScope) {
 929       // FIXME - Add inlined function scopes to the root so we can delete
 930       // them later.  Long term, handle inlined functions properly.
 931       RootScope->AddScope(Slot);
 932     } else {
 933       // First function is top level function.
 934       RootScope = Slot;
 935     }
 936   }
 937   return Slot;
 938 }
 939
 940 //===-EH-------------------------------------------------------------------===//
 941
 942 /// getOrCreateLandingPadInfo - Find or create an LandingPadInfo for the
 943 /// specified MachineBasicBlock.
 944 LandingPadInfo &
 945 MachineModuleInfo::getOrCreateLandingPadInfo(MachineBasicBlock *LandingPad) {
 946   unsigned N = LandingPads.size();
 947
 948   for (unsigned i = 0; i < N; ++i) {
 949     LandingPadInfo &LP = LandingPads[i];
 950     if (LP.LandingPadBlock == LandingPad)
 951       return LP;
 952   }
 953
 954   LandingPads.push_back(LandingPadInfo(LandingPad));
 955   return LandingPads[N];
 956 }
 957
 958 /// addInvoke - Provide the begin and end labels of an invoke style call and
 959 /// associate it with a try landing pad block.
 960 void MachineModuleInfo::addInvoke(MachineBasicBlock *LandingPad,
 961                                   unsigned BeginLabel, unsigned EndLabel) {
 962   LandingPadInfo &LP = getOrCreateLandingPadInfo(LandingPad);
 963   LP.BeginLabels.push_back(BeginLabel);
 964   LP.EndLabels.push_back(EndLabel);
 965 }
 966
 967 /// addLandingPad - Provide the label of a try LandingPad block.
 968 ///
 969 unsigned MachineModuleInfo::addLandingPad(MachineBasicBlock *LandingPad) {
 970   unsigned LandingPadLabel = NextLabelID();
 971   LandingPadInfo &LP = getOrCreateLandingPadInfo(LandingPad);
 972   LP.LandingPadLabel = LandingPadLabel;
 973   return LandingPadLabel;
 974 }
 975
 976 /// addPersonality - Provide the personality function for the exception
 977 /// information.
 978 void MachineModuleInfo::addPersonality(MachineBasicBlock *LandingPad,
 979                                        Function *Personality) {
 980   LandingPadInfo &LP = getOrCreateLandingPadInfo(LandingPad);
 981   LP.Personality = Personality;
 982
 983   for (unsigned i = 0, e = Personalities.size(); i < e; ++i)
 984     if (Personalities[i] == Personality)
 985       return;
 986
 987   Personalities.push_back(Personality);
 988 }
 989
 990 /// addCatchTypeInfo - Provide the catch typeinfo for a landing pad.
 991 ///
 992 void MachineModuleInfo::addCatchTypeInfo(MachineBasicBlock *LandingPad,
 993                                         std::vector<GlobalVariable *> &TyInfo) {
 994   LandingPadInfo &LP = getOrCreateLandingPadInfo(LandingPad);
 995   for (unsigned N = TyInfo.size(); N; --N)
 996     LP.TypeIds.push_back(getTypeIDFor(TyInfo[N - 1]));
 997 }
 998
 999 /// addFilterTypeInfo - Provide the filter typeinfo for a landing pad.
1000 ///
1001 void MachineModuleInfo::addFilterTypeInfo(MachineBasicBlock *LandingPad,
1002                                         std::vector<GlobalVariable *> &TyInfo) {
1003   LandingPadInfo &LP = getOrCreateLandingPadInfo(LandingPad);
1004   unsigned TyInfoSize = TyInfo.size();
1005   std::vector<unsigned> IdsInFilter(TyInfoSize);
1006
1007   for (unsigned I = 0; I != TyInfoSize; ++I)
1008     IdsInFilter[I] = getTypeIDFor(TyInfo[I]);
1009
1010   LP.TypeIds.push_back(getFilterIDFor(IdsInFilter));
1011 }
1012
1013 /// addCleanup - Add a cleanup action for a landing pad.
1014 ///
1015 void MachineModuleInfo::addCleanup(MachineBasicBlock *LandingPad) {
1016   LandingPadInfo &LP = getOrCreateLandingPadInfo(LandingPad);
1017   LP.TypeIds.push_back(0);
1018 }
1019
1020 /// TidyLandingPads - Remap landing pad labels and remove any deleted landing
1021 /// pads.
1022 void MachineModuleInfo::TidyLandingPads() {
1023   for (unsigned i = 0; i != LandingPads.size(); ) {
1024     LandingPadInfo &LandingPad = LandingPads[i];
1025     LandingPad.LandingPadLabel = MappedLabel(LandingPad.LandingPadLabel);
1026
1027     // Special case: we *should* emit LPs with null LP MBB. This indicates
1028     // "nounwind" case.
1029     if (!LandingPad.LandingPadLabel && LandingPad.LandingPadBlock) {
1030       LandingPads.erase(LandingPads.begin() + i);
1031       continue;
1032     }
1033
1034     for (unsigned j = 0; j != LandingPads[i].BeginLabels.size(); ) {
1035       unsigned BeginLabel = MappedLabel(LandingPad.BeginLabels[j]);
1036       unsigned EndLabel = MappedLabel(LandingPad.EndLabels[j]);
1037
1038       if (!BeginLabel || !EndLabel) {
1039         LandingPad.BeginLabels.erase(LandingPad.BeginLabels.begin() + j);
1040         LandingPad.EndLabels.erase(LandingPad.EndLabels.begin() + j);
1041         continue;
1042       }
1043
1044       LandingPad.BeginLabels[j] = BeginLabel;
1045       LandingPad.EndLabels[j] = EndLabel;
1046       ++j;
1047     }
1048
1049     // Remove landing pads with no try-ranges.
1050     if (LandingPads[i].BeginLabels.empty()) {
1051       LandingPads.erase(LandingPads.begin() + i);
1052       continue;
1053     }
1054
1055     // If there is no landing pad, ensure that the list of typeids is empty.
1056     // If the only typeid is a cleanup, this is the same as having no typeids.
1057     if (!LandingPad.LandingPadBlock ||
1058         (LandingPad.TypeIds.size() == 1 && !LandingPad.TypeIds[0]))
1059       LandingPad.TypeIds.clear();
1060
1061     ++i;
1062   }
1063 }
1064
1065 /// getTypeIDFor - Return the type id for the specified typeinfo.  This is
1066 /// function wide.
1067 unsigned MachineModuleInfo::getTypeIDFor(GlobalVariable *TI) {
1068   for (unsigned i = 0, e = TypeInfos.size(); i != e; ++i)
1069     if (TypeInfos[i] == TI)
1070       return i + 1;
1071
1072   TypeInfos.push_back(TI);
1073   return TypeInfos.size();
1074 }
1075
1076 /// getFilterIDFor - Return the filter id for the specified typeinfos.  This is
1077 /// function wide.
1078 int MachineModuleInfo::getFilterIDFor(std::vector<unsigned> &TyIds) {
1079   // If the new filter coincides with the tail of an existing filter, then
1080   // re-use the existing filter.  Folding filters more than this requires
1081   // re-ordering filters and/or their elements - probably not worth it.
1082   for (std::vector<unsigned>::iterator I = FilterEnds.begin(),
1083        E = FilterEnds.end(); I != E; ++I) {
1084     unsigned i = *I, j = TyIds.size();
1085
1086     while (i && j)
1087       if (FilterIds[--i] != TyIds[--j])
1088         goto try_next;
1089
1090     if (!j)
1091       // The new filter coincides with range [i, end) of the existing filter.
1092       return -(1 + i);
1093
1094 try_next:;
1095   }
1096
1097   // Add the new filter.
1098   int FilterID = -(1 + FilterIds.size());
1099   FilterIds.reserve(FilterIds.size() + TyIds.size() + 1);
1100
1101   for (unsigned I = 0, N = TyIds.size(); I != N; ++I)
1102     FilterIds.push_back(TyIds[I]);
1103
1104   FilterEnds.push_back(FilterIds.size());
1105   FilterIds.push_back(0); // terminator
1106   return FilterID;
1107 }
1108
1109 /// getPersonality - Return the personality function for the current function.
1110 Function *MachineModuleInfo::getPersonality() const {
1111   // FIXME: Until PR1414 will be fixed, we're using 1 personality function per
1112   // function
1113   return !LandingPads.empty() ? LandingPads[0].Personality : NULL;
1114 }
1115
1116 /// getPersonalityIndex - Return unique index for current personality
1117 /// function. NULL personality function should always get zero index.
1118 unsigned MachineModuleInfo::getPersonalityIndex() const {
1119   const Function* Personality = NULL;
1120
1121   // Scan landing pads. If there is at least one non-NULL personality - use it.
1122   for (unsigned i = 0, e = LandingPads.size(); i != e; ++i)
1123     if (LandingPads[i].Personality) {
1124       Personality = LandingPads[i].Personality;
1125       break;
1126     }
1127
1128   for (unsigned i = 0, e = Personalities.size(); i < e; ++i)
1129     if (Personalities[i] == Personality)
1130       return i;
1131
1132   // This should never happen
1133   assert(0 && "Personality function should be set!");
1134   return 0;
1135 }
1136
1137 //===----------------------------------------------------------------------===//
1138 /// DebugLabelFolding pass - This pass prunes out redundant labels.  This allows
1139 /// a info consumer to determine if the range of two labels is empty, by seeing
1140 /// if the labels map to the same reduced label.
1141
1142 namespace llvm {
1143
1144 struct DebugLabelFolder : public MachineFunctionPass {
1145   static char ID;
1146   DebugLabelFolder() : MachineFunctionPass((intptr_t)&ID) {}
1147
1148   virtual bool runOnMachineFunction(MachineFunction &MF);
1149   virtual const char *getPassName() const { return "Label Folder"; }
1150 };
1151
1152 char DebugLabelFolder::ID = 0;
1153
1154 bool DebugLabelFolder::runOnMachineFunction(MachineFunction &MF) {
1155   // Get machine module info.
1156   MachineModuleInfo *MMI = getAnalysisToUpdate<MachineModuleInfo>();
1157   if (!MMI) return false;
1158
1159   // Track if change is made.
1160   bool MadeChange = false;
1161   // No prior label to begin.
1162   unsigned PriorLabel = 0;
1163
1164   // Iterate through basic blocks.
1165   for (MachineFunction::iterator BB = MF.begin(), E = MF.end();
1166        BB != E; ++BB) {
1167     // Iterate through instructions.
1168     for (MachineBasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ) {
1169       // Is it a label.
1170       if (I->isDebugLabel()) {
1171         // The label ID # is always operand #0, an immediate.
1172         unsigned NextLabel = I->getOperand(0).getImm();
1173
1174         // If there was an immediate prior label.
1175         if (PriorLabel) {
1176           // Remap the current label to prior label.
1177           MMI->RemapLabel(NextLabel, PriorLabel);
1178           // Delete the current label.
1179           I = BB->erase(I);
1180           // Indicate a change has been made.
1181           MadeChange = true;
1182           continue;
1183         } else {
1184           // Start a new round.
1185           PriorLabel = NextLabel;
1186         }
1187        } else {
1188         // No consecutive labels.
1189         PriorLabel = 0;
1190       }
1191
1192       ++I;
1193     }
1194   }
1195
1196   return MadeChange;
1197 }
1198
1199 FunctionPass *createDebugLabelFoldingPass() { return new DebugLabelFolder(); }
1200
1201 }