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