contrib/llvm/lib/CodeGen/MachineFunction.cpp

   1 //===- MachineFunction.cpp ------------------------------------------------===//
   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 // Collect native machine code information for a function.  This allows
  11 // target-specific information about the generated code to be stored with each
  12 // function.
  13 //
  14 //===----------------------------------------------------------------------===//
  15
  16 #include "llvm/CodeGen/MachineFunction.h"
  17 #include "llvm/ADT/BitVector.h"
  18 #include "llvm/ADT/DenseMap.h"
  19 #include "llvm/ADT/DenseSet.h"
  20 #include "llvm/ADT/STLExtras.h"
  21 #include "llvm/ADT/SmallString.h"
  22 #include "llvm/ADT/SmallVector.h"
  23 #include "llvm/ADT/StringRef.h"
  24 #include "llvm/ADT/Twine.h"
  25 #include "llvm/Analysis/ConstantFolding.h"
  26 #include "llvm/Analysis/EHPersonalities.h"
  27 #include "llvm/CodeGen/MachineBasicBlock.h"
  28 #include "llvm/CodeGen/MachineConstantPool.h"
  29 #include "llvm/CodeGen/MachineFrameInfo.h"
  30 #include "llvm/CodeGen/MachineInstr.h"
  31 #include "llvm/CodeGen/MachineJumpTableInfo.h"
  32 #include "llvm/CodeGen/MachineMemOperand.h"
  33 #include "llvm/CodeGen/MachineModuleInfo.h"
  34 #include "llvm/CodeGen/MachineRegisterInfo.h"
  35 #include "llvm/CodeGen/PseudoSourceValue.h"
  36 #include "llvm/CodeGen/TargetFrameLowering.h"
  37 #include "llvm/CodeGen/TargetLowering.h"
  38 #include "llvm/CodeGen/TargetRegisterInfo.h"
  39 #include "llvm/CodeGen/TargetSubtargetInfo.h"
  40 #include "llvm/CodeGen/WinEHFuncInfo.h"
  41 #include "llvm/IR/Attributes.h"
  42 #include "llvm/IR/BasicBlock.h"
  43 #include "llvm/IR/Constant.h"
  44 #include "llvm/IR/DataLayout.h"
  45 #include "llvm/IR/DerivedTypes.h"
  46 #include "llvm/IR/Function.h"
  47 #include "llvm/IR/GlobalValue.h"
  48 #include "llvm/IR/Instruction.h"
  49 #include "llvm/IR/Instructions.h"
  50 #include "llvm/IR/Metadata.h"
  51 #include "llvm/IR/Module.h"
  52 #include "llvm/IR/ModuleSlotTracker.h"
  53 #include "llvm/IR/Value.h"
  54 #include "llvm/MC/MCContext.h"
  55 #include "llvm/MC/MCSymbol.h"
  56 #include "llvm/MC/SectionKind.h"
  57 #include "llvm/Support/Casting.h"
  58 #include "llvm/Support/CommandLine.h"
  59 #include "llvm/Support/Compiler.h"
  60 #include "llvm/Support/DOTGraphTraits.h"
  61 #include "llvm/Support/Debug.h"
  62 #include "llvm/Support/ErrorHandling.h"
  63 #include "llvm/Support/GraphWriter.h"
  64 #include "llvm/Support/raw_ostream.h"
  65 #include "llvm/Target/TargetMachine.h"
  66 #include <algorithm>
  67 #include <cassert>
  68 #include <cstddef>
  69 #include <cstdint>
  70 #include <iterator>
  71 #include <string>
  72 #include <utility>
  73 #include <vector>
  74
  75 using namespace llvm;
  76
  77 #define DEBUG_TYPE "codegen"
  78
  79 static cl::opt<unsigned>
  80 AlignAllFunctions("align-all-functions",
  81                   cl::desc("Force the alignment of all functions."),
  82                   cl::init(0), cl::Hidden);
  83
  84 static const char *getPropertyName(MachineFunctionProperties::Property Prop) {
  85   using P = MachineFunctionProperties::Property;
  86
  87   switch(Prop) {
  88   case P::FailedISel: return "FailedISel";
  89   case P::IsSSA: return "IsSSA";
  90   case P::Legalized: return "Legalized";
  91   case P::NoPHIs: return "NoPHIs";
  92   case P::NoVRegs: return "NoVRegs";
  93   case P::RegBankSelected: return "RegBankSelected";
  94   case P::Selected: return "Selected";
  95   case P::TracksLiveness: return "TracksLiveness";
  96   }
  97   llvm_unreachable("Invalid machine function property");
  98 }
  99
 100 void MachineFunctionProperties::print(raw_ostream &OS) const {
 101   const char *Separator = "";
 102   for (BitVector::size_type I = 0; I < Properties.size(); ++I) {
 103     if (!Properties[I])
 104       continue;
 105     OS << Separator << getPropertyName(static_cast<Property>(I));
 106     Separator = ", ";
 107   }
 108 }
 109
 110 //===----------------------------------------------------------------------===//
 111 // MachineFunction implementation
 112 //===----------------------------------------------------------------------===//
 113
 114 // Out-of-line virtual method.
 115 MachineFunctionInfo::~MachineFunctionInfo() = default;
 116
 117 void ilist_alloc_traits<MachineBasicBlock>::deleteNode(MachineBasicBlock *MBB) {
 118   MBB->getParent()->DeleteMachineBasicBlock(MBB);
 119 }
 120
 121 static inline unsigned getFnStackAlignment(const TargetSubtargetInfo *STI,
 122                                            const Function &F) {
 123   if (F.hasFnAttribute(Attribute::StackAlignment))
 124     return F.getFnStackAlignment();
 125   return STI->getFrameLowering()->getStackAlignment();
 126 }
 127
 128 MachineFunction::MachineFunction(const Function &F, const TargetMachine &Target,
 129                                  const TargetSubtargetInfo &STI,
 130                                  unsigned FunctionNum, MachineModuleInfo &mmi)
 131     : F(F), Target(Target), STI(&STI), Ctx(mmi.getContext()), MMI(mmi) {
 132   FunctionNumber = FunctionNum;
 133   init();
 134 }
 135
 136 void MachineFunction::init() {
 137   // Assume the function starts in SSA form with correct liveness.
 138   Properties.set(MachineFunctionProperties::Property::IsSSA);
 139   Properties.set(MachineFunctionProperties::Property::TracksLiveness);
 140   if (STI->getRegisterInfo())
 141     RegInfo = new (Allocator) MachineRegisterInfo(this);
 142   else
 143     RegInfo = nullptr;
 144
 145   MFInfo = nullptr;
 146   // We can realign the stack if the target supports it and the user hasn't
 147   // explicitly asked us not to.
 148   bool CanRealignSP = STI->getFrameLowering()->isStackRealignable() &&
 149                       !F.hasFnAttribute("no-realign-stack");
 150   FrameInfo = new (Allocator) MachineFrameInfo(
 151       getFnStackAlignment(STI, F), /*StackRealignable=*/CanRealignSP,
 152       /*ForceRealign=*/CanRealignSP &&
 153           F.hasFnAttribute(Attribute::StackAlignment));
 154
 155   if (F.hasFnAttribute(Attribute::StackAlignment))
 156     FrameInfo->ensureMaxAlignment(F.getFnStackAlignment());
 157
 158   ConstantPool = new (Allocator) MachineConstantPool(getDataLayout());
 159   Alignment = STI->getTargetLowering()->getMinFunctionAlignment();
 160
 161   // FIXME: Shouldn't use pref alignment if explicit alignment is set on F.
 162   // FIXME: Use Function::optForSize().
 163   if (!F.hasFnAttribute(Attribute::OptimizeForSize))
 164     Alignment = std::max(Alignment,
 165                          STI->getTargetLowering()->getPrefFunctionAlignment());
 166
 167   if (AlignAllFunctions)
 168     Alignment = AlignAllFunctions;
 169
 170   JumpTableInfo = nullptr;
 171
 172   if (isFuncletEHPersonality(classifyEHPersonality(
 173           F.hasPersonalityFn() ? F.getPersonalityFn() : nullptr))) {
 174     WinEHInfo = new (Allocator) WinEHFuncInfo();
 175   }
 176
 177   assert(Target.isCompatibleDataLayout(getDataLayout()) &&
 178          "Can't create a MachineFunction using a Module with a "
 179          "Target-incompatible DataLayout attached\n");
 180
 181   PSVManager =
 182     llvm::make_unique<PseudoSourceValueManager>(*(getSubtarget().
 183                                                   getInstrInfo()));
 184 }
 185
 186 MachineFunction::~MachineFunction() {
 187   clear();
 188 }
 189
 190 void MachineFunction::clear() {
 191   Properties.reset();
 192   // Don't call destructors on MachineInstr and MachineOperand. All of their
 193   // memory comes from the BumpPtrAllocator which is about to be purged.
 194   //
 195   // Do call MachineBasicBlock destructors, it contains std::vectors.
 196   for (iterator I = begin(), E = end(); I != E; I = BasicBlocks.erase(I))
 197     I->Insts.clearAndLeakNodesUnsafely();
 198
 199   InstructionRecycler.clear(Allocator);
 200   OperandRecycler.clear(Allocator);
 201   BasicBlockRecycler.clear(Allocator);
 202   CodeViewAnnotations.clear();
 203   VariableDbgInfos.clear();
 204   if (RegInfo) {
 205     RegInfo->~MachineRegisterInfo();
 206     Allocator.Deallocate(RegInfo);
 207   }
 208   if (MFInfo) {
 209     MFInfo->~MachineFunctionInfo();
 210     Allocator.Deallocate(MFInfo);
 211   }
 212
 213   FrameInfo->~MachineFrameInfo();
 214   Allocator.Deallocate(FrameInfo);
 215
 216   ConstantPool->~MachineConstantPool();
 217   Allocator.Deallocate(ConstantPool);
 218
 219   if (JumpTableInfo) {
 220     JumpTableInfo->~MachineJumpTableInfo();
 221     Allocator.Deallocate(JumpTableInfo);
 222   }
 223
 224   if (WinEHInfo) {
 225     WinEHInfo->~WinEHFuncInfo();
 226     Allocator.Deallocate(WinEHInfo);
 227   }
 228 }
 229
 230 const DataLayout &MachineFunction::getDataLayout() const {
 231   return F.getParent()->getDataLayout();
 232 }
 233
 234 /// Get the JumpTableInfo for this function.
 235 /// If it does not already exist, allocate one.
 236 MachineJumpTableInfo *MachineFunction::
 237 getOrCreateJumpTableInfo(unsigned EntryKind) {
 238   if (JumpTableInfo) return JumpTableInfo;
 239
 240   JumpTableInfo = new (Allocator)
 241     MachineJumpTableInfo((MachineJumpTableInfo::JTEntryKind)EntryKind);
 242   return JumpTableInfo;
 243 }
 244
 245 /// Should we be emitting segmented stack stuff for the function
 246 bool MachineFunction::shouldSplitStack() const {
 247   return getFunction().hasFnAttribute("split-stack");
 248 }
 249
 250 /// This discards all of the MachineBasicBlock numbers and recomputes them.
 251 /// This guarantees that the MBB numbers are sequential, dense, and match the
 252 /// ordering of the blocks within the function.  If a specific MachineBasicBlock
 253 /// is specified, only that block and those after it are renumbered.
 254 void MachineFunction::RenumberBlocks(MachineBasicBlock *MBB) {
 255   if (empty()) { MBBNumbering.clear(); return; }
 256   MachineFunction::iterator MBBI, E = end();
 257   if (MBB == nullptr)
 258     MBBI = begin();
 259   else
 260     MBBI = MBB->getIterator();
 261
 262   // Figure out the block number this should have.
 263   unsigned BlockNo = 0;
 264   if (MBBI != begin())
 265     BlockNo = std::prev(MBBI)->getNumber() + 1;
 266
 267   for (; MBBI != E; ++MBBI, ++BlockNo) {
 268     if (MBBI->getNumber() != (int)BlockNo) {
 269       // Remove use of the old number.
 270       if (MBBI->getNumber() != -1) {
 271         assert(MBBNumbering[MBBI->getNumber()] == &*MBBI &&
 272                "MBB number mismatch!");
 273         MBBNumbering[MBBI->getNumber()] = nullptr;
 274       }
 275
 276       // If BlockNo is already taken, set that block's number to -1.
 277       if (MBBNumbering[BlockNo])
 278         MBBNumbering[BlockNo]->setNumber(-1);
 279
 280       MBBNumbering[BlockNo] = &*MBBI;
 281       MBBI->setNumber(BlockNo);
 282     }
 283   }
 284
 285   // Okay, all the blocks are renumbered.  If we have compactified the block
 286   // numbering, shrink MBBNumbering now.
 287   assert(BlockNo <= MBBNumbering.size() && "Mismatch!");
 288   MBBNumbering.resize(BlockNo);
 289 }
 290
 291 /// Allocate a new MachineInstr. Use this instead of `new MachineInstr'.
 292 MachineInstr *MachineFunction::CreateMachineInstr(const MCInstrDesc &MCID,
 293                                                   const DebugLoc &DL,
 294                                                   bool NoImp) {
 295   return new (InstructionRecycler.Allocate<MachineInstr>(Allocator))
 296     MachineInstr(*this, MCID, DL, NoImp);
 297 }
 298
 299 /// Create a new MachineInstr which is a copy of the 'Orig' instruction,
 300 /// identical in all ways except the instruction has no parent, prev, or next.
 301 MachineInstr *
 302 MachineFunction::CloneMachineInstr(const MachineInstr *Orig) {
 303   return new (InstructionRecycler.Allocate<MachineInstr>(Allocator))
 304              MachineInstr(*this, *Orig);
 305 }
 306
 307 MachineInstr &MachineFunction::CloneMachineInstrBundle(MachineBasicBlock &MBB,
 308     MachineBasicBlock::iterator InsertBefore, const MachineInstr &Orig) {
 309   MachineInstr *FirstClone = nullptr;
 310   MachineBasicBlock::const_instr_iterator I = Orig.getIterator();
 311   while (true) {
 312     MachineInstr *Cloned = CloneMachineInstr(&*I);
 313     MBB.insert(InsertBefore, Cloned);
 314     if (FirstClone == nullptr) {
 315       FirstClone = Cloned;
 316     } else {
 317       Cloned->bundleWithPred();
 318     }
 319
 320     if (!I->isBundledWithSucc())
 321       break;
 322     ++I;
 323   }
 324   return *FirstClone;
 325 }
 326
 327 /// Delete the given MachineInstr.
 328 ///
 329 /// This function also serves as the MachineInstr destructor - the real
 330 /// ~MachineInstr() destructor must be empty.
 331 void
 332 MachineFunction::DeleteMachineInstr(MachineInstr *MI) {
 333   // Strip it for parts. The operand array and the MI object itself are
 334   // independently recyclable.
 335   if (MI->Operands)
 336     deallocateOperandArray(MI->CapOperands, MI->Operands);
 337   // Don't call ~MachineInstr() which must be trivial anyway because
 338   // ~MachineFunction drops whole lists of MachineInstrs wihout calling their
 339   // destructors.
 340   InstructionRecycler.Deallocate(Allocator, MI);
 341 }
 342
 343 /// Allocate a new MachineBasicBlock. Use this instead of
 344 /// `new MachineBasicBlock'.
 345 MachineBasicBlock *
 346 MachineFunction::CreateMachineBasicBlock(const BasicBlock *bb) {
 347   return new (BasicBlockRecycler.Allocate<MachineBasicBlock>(Allocator))
 348              MachineBasicBlock(*this, bb);
 349 }
 350
 351 /// Delete the given MachineBasicBlock.
 352 void
 353 MachineFunction::DeleteMachineBasicBlock(MachineBasicBlock *MBB) {
 354   assert(MBB->getParent() == this && "MBB parent mismatch!");
 355   MBB->~MachineBasicBlock();
 356   BasicBlockRecycler.Deallocate(Allocator, MBB);
 357 }
 358
 359 MachineMemOperand *MachineFunction::getMachineMemOperand(
 360     MachinePointerInfo PtrInfo, MachineMemOperand::Flags f, uint64_t s,
 361     unsigned base_alignment, const AAMDNodes &AAInfo, const MDNode *Ranges,
 362     SyncScope::ID SSID, AtomicOrdering Ordering,
 363     AtomicOrdering FailureOrdering) {
 364   return new (Allocator)
 365       MachineMemOperand(PtrInfo, f, s, base_alignment, AAInfo, Ranges,
 366                         SSID, Ordering, FailureOrdering);
 367 }
 368
 369 MachineMemOperand *
 370 MachineFunction::getMachineMemOperand(const MachineMemOperand *MMO,
 371                                       int64_t Offset, uint64_t Size) {
 372   if (MMO->getValue())
 373     return new (Allocator)
 374                MachineMemOperand(MachinePointerInfo(MMO->getValue(),
 375                                                     MMO->getOffset()+Offset),
 376                                  MMO->getFlags(), Size, MMO->getBaseAlignment(),
 377                                  AAMDNodes(), nullptr, MMO->getSyncScopeID(),
 378                                  MMO->getOrdering(), MMO->getFailureOrdering());
 379   return new (Allocator)
 380              MachineMemOperand(MachinePointerInfo(MMO->getPseudoValue(),
 381                                                   MMO->getOffset()+Offset),
 382                                MMO->getFlags(), Size, MMO->getBaseAlignment(),
 383                                AAMDNodes(), nullptr, MMO->getSyncScopeID(),
 384                                MMO->getOrdering(), MMO->getFailureOrdering());
 385 }
 386
 387 MachineMemOperand *
 388 MachineFunction::getMachineMemOperand(const MachineMemOperand *MMO,
 389                                       const AAMDNodes &AAInfo) {
 390   MachinePointerInfo MPI = MMO->getValue() ?
 391              MachinePointerInfo(MMO->getValue(), MMO->getOffset()) :
 392              MachinePointerInfo(MMO->getPseudoValue(), MMO->getOffset());
 393
 394   return new (Allocator)
 395              MachineMemOperand(MPI, MMO->getFlags(), MMO->getSize(),
 396                                MMO->getBaseAlignment(), AAInfo,
 397                                MMO->getRanges(), MMO->getSyncScopeID(),
 398                                MMO->getOrdering(), MMO->getFailureOrdering());
 399 }
 400
 401 MachineInstr::mmo_iterator
 402 MachineFunction::allocateMemRefsArray(unsigned long Num) {
 403   return Allocator.Allocate<MachineMemOperand *>(Num);
 404 }
 405
 406 std::pair<MachineInstr::mmo_iterator, MachineInstr::mmo_iterator>
 407 MachineFunction::extractLoadMemRefs(MachineInstr::mmo_iterator Begin,
 408                                     MachineInstr::mmo_iterator End) {
 409   // Count the number of load mem refs.
 410   unsigned Num = 0;
 411   for (MachineInstr::mmo_iterator I = Begin; I != End; ++I)
 412     if ((*I)->isLoad())
 413       ++Num;
 414
 415   // Allocate a new array and populate it with the load information.
 416   MachineInstr::mmo_iterator Result = allocateMemRefsArray(Num);
 417   unsigned Index = 0;
 418   for (MachineInstr::mmo_iterator I = Begin; I != End; ++I) {
 419     if ((*I)->isLoad()) {
 420       if (!(*I)->isStore())
 421         // Reuse the MMO.
 422         Result[Index] = *I;
 423       else {
 424         // Clone the MMO and unset the store flag.
 425         MachineMemOperand *JustLoad =
 426           getMachineMemOperand((*I)->getPointerInfo(),
 427                                (*I)->getFlags() & ~MachineMemOperand::MOStore,
 428                                (*I)->getSize(), (*I)->getBaseAlignment(),
 429                                (*I)->getAAInfo(), nullptr,
 430                                (*I)->getSyncScopeID(), (*I)->getOrdering(),
 431                                (*I)->getFailureOrdering());
 432         Result[Index] = JustLoad;
 433       }
 434       ++Index;
 435     }
 436   }
 437   return std::make_pair(Result, Result + Num);
 438 }
 439
 440 std::pair<MachineInstr::mmo_iterator, MachineInstr::mmo_iterator>
 441 MachineFunction::extractStoreMemRefs(MachineInstr::mmo_iterator Begin,
 442                                      MachineInstr::mmo_iterator End) {
 443   // Count the number of load mem refs.
 444   unsigned Num = 0;
 445   for (MachineInstr::mmo_iterator I = Begin; I != End; ++I)
 446     if ((*I)->isStore())
 447       ++Num;
 448
 449   // Allocate a new array and populate it with the store information.
 450   MachineInstr::mmo_iterator Result = allocateMemRefsArray(Num);
 451   unsigned Index = 0;
 452   for (MachineInstr::mmo_iterator I = Begin; I != End; ++I) {
 453     if ((*I)->isStore()) {
 454       if (!(*I)->isLoad())
 455         // Reuse the MMO.
 456         Result[Index] = *I;
 457       else {
 458         // Clone the MMO and unset the load flag.
 459         MachineMemOperand *JustStore =
 460           getMachineMemOperand((*I)->getPointerInfo(),
 461                                (*I)->getFlags() & ~MachineMemOperand::MOLoad,
 462                                (*I)->getSize(), (*I)->getBaseAlignment(),
 463                                (*I)->getAAInfo(), nullptr,
 464                                (*I)->getSyncScopeID(), (*I)->getOrdering(),
 465                                (*I)->getFailureOrdering());
 466         Result[Index] = JustStore;
 467       }
 468       ++Index;
 469     }
 470   }
 471   return std::make_pair(Result, Result + Num);
 472 }
 473
 474 const char *MachineFunction::createExternalSymbolName(StringRef Name) {
 475   char *Dest = Allocator.Allocate<char>(Name.size() + 1);
 476   std::copy(Name.begin(), Name.end(), Dest);
 477   Dest[Name.size()] = 0;
 478   return Dest;
 479 }
 480
 481 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
 482 LLVM_DUMP_METHOD void MachineFunction::dump() const {
 483   print(dbgs());
 484 }
 485 #endif
 486
 487 StringRef MachineFunction::getName() const {
 488   return getFunction().getName();
 489 }
 490
 491 void MachineFunction::print(raw_ostream &OS, const SlotIndexes *Indexes) const {
 492   OS << "# Machine code for function " << getName() << ": ";
 493   getProperties().print(OS);
 494   OS << '\n';
 495
 496   // Print Frame Information
 497   FrameInfo->print(*this, OS);
 498
 499   // Print JumpTable Information
 500   if (JumpTableInfo)
 501     JumpTableInfo->print(OS);
 502
 503   // Print Constant Pool
 504   ConstantPool->print(OS);
 505
 506   const TargetRegisterInfo *TRI = getSubtarget().getRegisterInfo();
 507
 508   if (RegInfo && !RegInfo->livein_empty()) {
 509     OS << "Function Live Ins: ";
 510     for (MachineRegisterInfo::livein_iterator
 511          I = RegInfo->livein_begin(), E = RegInfo->livein_end(); I != E; ++I) {
 512       OS << printReg(I->first, TRI);
 513       if (I->second)
 514         OS << " in " << printReg(I->second, TRI);
 515       if (std::next(I) != E)
 516         OS << ", ";
 517     }
 518     OS << '\n';
 519   }
 520
 521   ModuleSlotTracker MST(getFunction().getParent());
 522   MST.incorporateFunction(getFunction());
 523   for (const auto &BB : *this) {
 524     OS << '\n';
 525     BB.print(OS, MST, Indexes);
 526   }
 527
 528   OS << "\n# End machine code for function " << getName() << ".\n\n";
 529 }
 530
 531 namespace llvm {
 532
 533   template<>
 534   struct DOTGraphTraits<const MachineFunction*> : public DefaultDOTGraphTraits {
 535     DOTGraphTraits(bool isSimple = false) : DefaultDOTGraphTraits(isSimple) {}
 536
 537     static std::string getGraphName(const MachineFunction *F) {
 538       return ("CFG for '" + F->getName() + "' function").str();
 539     }
 540
 541     std::string getNodeLabel(const MachineBasicBlock *Node,
 542                              const MachineFunction *Graph) {
 543       std::string OutStr;
 544       {
 545         raw_string_ostream OSS(OutStr);
 546
 547         if (isSimple()) {
 548           OSS << printMBBReference(*Node);
 549           if (const BasicBlock *BB = Node->getBasicBlock())
 550             OSS << ": " << BB->getName();
 551         } else
 552           Node->print(OSS);
 553       }
 554
 555       if (OutStr[0] == '\n') OutStr.erase(OutStr.begin());
 556
 557       // Process string output to make it nicer...
 558       for (unsigned i = 0; i != OutStr.length(); ++i)
 559         if (OutStr[i] == '\n') {                            // Left justify
 560           OutStr[i] = '\\';
 561           OutStr.insert(OutStr.begin()+i+1, 'l');
 562         }
 563       return OutStr;
 564     }
 565   };
 566
 567 } // end namespace llvm
 568
 569 void MachineFunction::viewCFG() const
 570 {
 571 #ifndef NDEBUG
 572   ViewGraph(this, "mf" + getName());
 573 #else
 574   errs() << "MachineFunction::viewCFG is only available in debug builds on "
 575          << "systems with Graphviz or gv!\n";
 576 #endif // NDEBUG
 577 }
 578
 579 void MachineFunction::viewCFGOnly() const
 580 {
 581 #ifndef NDEBUG
 582   ViewGraph(this, "mf" + getName(), true);
 583 #else
 584   errs() << "MachineFunction::viewCFGOnly is only available in debug builds on "
 585          << "systems with Graphviz or gv!\n";
 586 #endif // NDEBUG
 587 }
 588
 589 /// Add the specified physical register as a live-in value and
 590 /// create a corresponding virtual register for it.
 591 unsigned MachineFunction::addLiveIn(unsigned PReg,
 592                                     const TargetRegisterClass *RC) {
 593   MachineRegisterInfo &MRI = getRegInfo();
 594   unsigned VReg = MRI.getLiveInVirtReg(PReg);
 595   if (VReg) {
 596     const TargetRegisterClass *VRegRC = MRI.getRegClass(VReg);
 597     (void)VRegRC;
 598     // A physical register can be added several times.
 599     // Between two calls, the register class of the related virtual register
 600     // may have been constrained to match some operation constraints.
 601     // In that case, check that the current register class includes the
 602     // physical register and is a sub class of the specified RC.
 603     assert((VRegRC == RC || (VRegRC->contains(PReg) &&
 604                              RC->hasSubClassEq(VRegRC))) &&
 605             "Register class mismatch!");
 606     return VReg;
 607   }
 608   VReg = MRI.createVirtualRegister(RC);
 609   MRI.addLiveIn(PReg, VReg);
 610   return VReg;
 611 }
 612
 613 /// Return the MCSymbol for the specified non-empty jump table.
 614 /// If isLinkerPrivate is specified, an 'l' label is returned, otherwise a
 615 /// normal 'L' label is returned.
 616 MCSymbol *MachineFunction::getJTISymbol(unsigned JTI, MCContext &Ctx,
 617                                         bool isLinkerPrivate) const {
 618   const DataLayout &DL = getDataLayout();
 619   assert(JumpTableInfo && "No jump tables");
 620   assert(JTI < JumpTableInfo->getJumpTables().size() && "Invalid JTI!");
 621
 622   StringRef Prefix = isLinkerPrivate ? DL.getLinkerPrivateGlobalPrefix()
 623                                      : DL.getPrivateGlobalPrefix();
 624   SmallString<60> Name;
 625   raw_svector_ostream(Name)
 626     << Prefix << "JTI" << getFunctionNumber() << '_' << JTI;
 627   return Ctx.getOrCreateSymbol(Name);
 628 }
 629
 630 /// Return a function-local symbol to represent the PIC base.
 631 MCSymbol *MachineFunction::getPICBaseSymbol() const {
 632   const DataLayout &DL = getDataLayout();
 633   return Ctx.getOrCreateSymbol(Twine(DL.getPrivateGlobalPrefix()) +
 634                                Twine(getFunctionNumber()) + "$pb");
 635 }
 636
 637 /// \name Exception Handling
 638 /// \{
 639
 640 LandingPadInfo &
 641 MachineFunction::getOrCreateLandingPadInfo(MachineBasicBlock *LandingPad) {
 642   unsigned N = LandingPads.size();
 643   for (unsigned i = 0; i < N; ++i) {
 644     LandingPadInfo &LP = LandingPads[i];
 645     if (LP.LandingPadBlock == LandingPad)
 646       return LP;
 647   }
 648
 649   LandingPads.push_back(LandingPadInfo(LandingPad));
 650   return LandingPads[N];
 651 }
 652
 653 void MachineFunction::addInvoke(MachineBasicBlock *LandingPad,
 654                                 MCSymbol *BeginLabel, MCSymbol *EndLabel) {
 655   LandingPadInfo &LP = getOrCreateLandingPadInfo(LandingPad);
 656   LP.BeginLabels.push_back(BeginLabel);
 657   LP.EndLabels.push_back(EndLabel);
 658 }
 659
 660 MCSymbol *MachineFunction::addLandingPad(MachineBasicBlock *LandingPad) {
 661   MCSymbol *LandingPadLabel = Ctx.createTempSymbol();
 662   LandingPadInfo &LP = getOrCreateLandingPadInfo(LandingPad);
 663   LP.LandingPadLabel = LandingPadLabel;
 664   return LandingPadLabel;
 665 }
 666
 667 void MachineFunction::addCatchTypeInfo(MachineBasicBlock *LandingPad,
 668                                        ArrayRef<const GlobalValue *> TyInfo) {
 669   LandingPadInfo &LP = getOrCreateLandingPadInfo(LandingPad);
 670   for (unsigned N = TyInfo.size(); N; --N)
 671     LP.TypeIds.push_back(getTypeIDFor(TyInfo[N - 1]));
 672 }
 673
 674 void MachineFunction::addFilterTypeInfo(MachineBasicBlock *LandingPad,
 675                                         ArrayRef<const GlobalValue *> TyInfo) {
 676   LandingPadInfo &LP = getOrCreateLandingPadInfo(LandingPad);
 677   std::vector<unsigned> IdsInFilter(TyInfo.size());
 678   for (unsigned I = 0, E = TyInfo.size(); I != E; ++I)
 679     IdsInFilter[I] = getTypeIDFor(TyInfo[I]);
 680   LP.TypeIds.push_back(getFilterIDFor(IdsInFilter));
 681 }
 682
 683 void MachineFunction::tidyLandingPads(DenseMap<MCSymbol*, uintptr_t> *LPMap) {
 684   for (unsigned i = 0; i != LandingPads.size(); ) {
 685     LandingPadInfo &LandingPad = LandingPads[i];
 686     if (LandingPad.LandingPadLabel &&
 687         !LandingPad.LandingPadLabel->isDefined() &&
 688         (!LPMap || (*LPMap)[LandingPad.LandingPadLabel] == 0))
 689       LandingPad.LandingPadLabel = nullptr;
 690
 691     // Special case: we *should* emit LPs with null LP MBB. This indicates
 692     // "nounwind" case.
 693     if (!LandingPad.LandingPadLabel && LandingPad.LandingPadBlock) {
 694       LandingPads.erase(LandingPads.begin() + i);
 695       continue;
 696     }
 697
 698     for (unsigned j = 0, e = LandingPads[i].BeginLabels.size(); j != e; ++j) {
 699       MCSymbol *BeginLabel = LandingPad.BeginLabels[j];
 700       MCSymbol *EndLabel = LandingPad.EndLabels[j];
 701       if ((BeginLabel->isDefined() ||
 702            (LPMap && (*LPMap)[BeginLabel] != 0)) &&
 703           (EndLabel->isDefined() ||
 704            (LPMap && (*LPMap)[EndLabel] != 0))) continue;
 705
 706       LandingPad.BeginLabels.erase(LandingPad.BeginLabels.begin() + j);
 707       LandingPad.EndLabels.erase(LandingPad.EndLabels.begin() + j);
 708       --j;
 709       --e;
 710     }
 711
 712     // Remove landing pads with no try-ranges.
 713     if (LandingPads[i].BeginLabels.empty()) {
 714       LandingPads.erase(LandingPads.begin() + i);
 715       continue;
 716     }
 717
 718     // If there is no landing pad, ensure that the list of typeids is empty.
 719     // If the only typeid is a cleanup, this is the same as having no typeids.
 720     if (!LandingPad.LandingPadBlock ||
 721         (LandingPad.TypeIds.size() == 1 && !LandingPad.TypeIds[0]))
 722       LandingPad.TypeIds.clear();
 723     ++i;
 724   }
 725 }
 726
 727 void MachineFunction::addCleanup(MachineBasicBlock *LandingPad) {
 728   LandingPadInfo &LP = getOrCreateLandingPadInfo(LandingPad);
 729   LP.TypeIds.push_back(0);
 730 }
 731
 732 void MachineFunction::addSEHCatchHandler(MachineBasicBlock *LandingPad,
 733                                          const Function *Filter,
 734                                          const BlockAddress *RecoverBA) {
 735   LandingPadInfo &LP = getOrCreateLandingPadInfo(LandingPad);
 736   SEHHandler Handler;
 737   Handler.FilterOrFinally = Filter;
 738   Handler.RecoverBA = RecoverBA;
 739   LP.SEHHandlers.push_back(Handler);
 740 }
 741
 742 void MachineFunction::addSEHCleanupHandler(MachineBasicBlock *LandingPad,
 743                                            const Function *Cleanup) {
 744   LandingPadInfo &LP = getOrCreateLandingPadInfo(LandingPad);
 745   SEHHandler Handler;
 746   Handler.FilterOrFinally = Cleanup;
 747   Handler.RecoverBA = nullptr;
 748   LP.SEHHandlers.push_back(Handler);
 749 }
 750
 751 void MachineFunction::setCallSiteLandingPad(MCSymbol *Sym,
 752                                             ArrayRef<unsigned> Sites) {
 753   LPadToCallSiteMap[Sym].append(Sites.begin(), Sites.end());
 754 }
 755
 756 unsigned MachineFunction::getTypeIDFor(const GlobalValue *TI) {
 757   for (unsigned i = 0, N = TypeInfos.size(); i != N; ++i)
 758     if (TypeInfos[i] == TI) return i + 1;
 759
 760   TypeInfos.push_back(TI);
 761   return TypeInfos.size();
 762 }
 763
 764 int MachineFunction::getFilterIDFor(std::vector<unsigned> &TyIds) {
 765   // If the new filter coincides with the tail of an existing filter, then
 766   // re-use the existing filter.  Folding filters more than this requires
 767   // re-ordering filters and/or their elements - probably not worth it.
 768   for (std::vector<unsigned>::iterator I = FilterEnds.begin(),
 769        E = FilterEnds.end(); I != E; ++I) {
 770     unsigned i = *I, j = TyIds.size();
 771
 772     while (i && j)
 773       if (FilterIds[--i] != TyIds[--j])
 774         goto try_next;
 775
 776     if (!j)
 777       // The new filter coincides with range [i, end) of the existing filter.
 778       return -(1 + i);
 779
 780 try_next:;
 781   }
 782
 783   // Add the new filter.
 784   int FilterID = -(1 + FilterIds.size());
 785   FilterIds.reserve(FilterIds.size() + TyIds.size() + 1);
 786   FilterIds.insert(FilterIds.end(), TyIds.begin(), TyIds.end());
 787   FilterEnds.push_back(FilterIds.size());
 788   FilterIds.push_back(0); // terminator
 789   return FilterID;
 790 }
 791
 792 void llvm::addLandingPadInfo(const LandingPadInst &I, MachineBasicBlock &MBB) {
 793   MachineFunction &MF = *MBB.getParent();
 794   if (const auto *PF = dyn_cast<Function>(
 795           I.getParent()->getParent()->getPersonalityFn()->stripPointerCasts()))
 796     MF.getMMI().addPersonality(PF);
 797
 798   if (I.isCleanup())
 799     MF.addCleanup(&MBB);
 800
 801   // FIXME: New EH - Add the clauses in reverse order. This isn't 100% correct,
 802   //        but we need to do it this way because of how the DWARF EH emitter
 803   //        processes the clauses.
 804   for (unsigned i = I.getNumClauses(); i != 0; --i) {
 805     Value *Val = I.getClause(i - 1);
 806     if (I.isCatch(i - 1)) {
 807       MF.addCatchTypeInfo(&MBB,
 808                           dyn_cast<GlobalValue>(Val->stripPointerCasts()));
 809     } else {
 810       // Add filters in a list.
 811       Constant *CVal = cast<Constant>(Val);
 812       SmallVector<const GlobalValue *, 4> FilterList;
 813       for (User::op_iterator II = CVal->op_begin(), IE = CVal->op_end();
 814            II != IE; ++II)
 815         FilterList.push_back(cast<GlobalValue>((*II)->stripPointerCasts()));
 816
 817       MF.addFilterTypeInfo(&MBB, FilterList);
 818     }
 819   }
 820 }
 821
 822 /// \}
 823
 824 //===----------------------------------------------------------------------===//
 825 //  MachineJumpTableInfo implementation
 826 //===----------------------------------------------------------------------===//
 827
 828 /// Return the size of each entry in the jump table.
 829 unsigned MachineJumpTableInfo::getEntrySize(const DataLayout &TD) const {
 830   // The size of a jump table entry is 4 bytes unless the entry is just the
 831   // address of a block, in which case it is the pointer size.
 832   switch (getEntryKind()) {
 833   case MachineJumpTableInfo::EK_BlockAddress:
 834     return TD.getPointerSize();
 835   case MachineJumpTableInfo::EK_GPRel64BlockAddress:
 836     return 8;
 837   case MachineJumpTableInfo::EK_GPRel32BlockAddress:
 838   case MachineJumpTableInfo::EK_LabelDifference32:
 839   case MachineJumpTableInfo::EK_Custom32:
 840     return 4;
 841   case MachineJumpTableInfo::EK_Inline:
 842     return 0;
 843   }
 844   llvm_unreachable("Unknown jump table encoding!");
 845 }
 846
 847 /// Return the alignment of each entry in the jump table.
 848 unsigned MachineJumpTableInfo::getEntryAlignment(const DataLayout &TD) const {
 849   // The alignment of a jump table entry is the alignment of int32 unless the
 850   // entry is just the address of a block, in which case it is the pointer
 851   // alignment.
 852   switch (getEntryKind()) {
 853   case MachineJumpTableInfo::EK_BlockAddress:
 854     return TD.getPointerABIAlignment(0);
 855   case MachineJumpTableInfo::EK_GPRel64BlockAddress:
 856     return TD.getABIIntegerTypeAlignment(64);
 857   case MachineJumpTableInfo::EK_GPRel32BlockAddress:
 858   case MachineJumpTableInfo::EK_LabelDifference32:
 859   case MachineJumpTableInfo::EK_Custom32:
 860     return TD.getABIIntegerTypeAlignment(32);
 861   case MachineJumpTableInfo::EK_Inline:
 862     return 1;
 863   }
 864   llvm_unreachable("Unknown jump table encoding!");
 865 }
 866
 867 /// Create a new jump table entry in the jump table info.
 868 unsigned MachineJumpTableInfo::createJumpTableIndex(
 869                                const std::vector<MachineBasicBlock*> &DestBBs) {
 870   assert(!DestBBs.empty() && "Cannot create an empty jump table!");
 871   JumpTables.push_back(MachineJumpTableEntry(DestBBs));
 872   return JumpTables.size()-1;
 873 }
 874
 875 /// If Old is the target of any jump tables, update the jump tables to branch
 876 /// to New instead.
 877 bool MachineJumpTableInfo::ReplaceMBBInJumpTables(MachineBasicBlock *Old,
 878                                                   MachineBasicBlock *New) {
 879   assert(Old != New && "Not making a change?");
 880   bool MadeChange = false;
 881   for (size_t i = 0, e = JumpTables.size(); i != e; ++i)
 882     ReplaceMBBInJumpTable(i, Old, New);
 883   return MadeChange;
 884 }
 885
 886 /// If Old is a target of the jump tables, update the jump table to branch to
 887 /// New instead.
 888 bool MachineJumpTableInfo::ReplaceMBBInJumpTable(unsigned Idx,
 889                                                  MachineBasicBlock *Old,
 890                                                  MachineBasicBlock *New) {
 891   assert(Old != New && "Not making a change?");
 892   bool MadeChange = false;
 893   MachineJumpTableEntry &JTE = JumpTables[Idx];
 894   for (size_t j = 0, e = JTE.MBBs.size(); j != e; ++j)
 895     if (JTE.MBBs[j] == Old) {
 896       JTE.MBBs[j] = New;
 897       MadeChange = true;
 898     }
 899   return MadeChange;
 900 }
 901
 902 void MachineJumpTableInfo::print(raw_ostream &OS) const {
 903   if (JumpTables.empty()) return;
 904
 905   OS << "Jump Tables:\n";
 906
 907   for (unsigned i = 0, e = JumpTables.size(); i != e; ++i) {
 908     OS << printJumpTableEntryReference(i) << ": ";
 909     for (unsigned j = 0, f = JumpTables[i].MBBs.size(); j != f; ++j)
 910       OS << ' ' << printMBBReference(*JumpTables[i].MBBs[j]);
 911   }
 912
 913   OS << '\n';
 914 }
 915
 916 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
 917 LLVM_DUMP_METHOD void MachineJumpTableInfo::dump() const { print(dbgs()); }
 918 #endif
 919
 920 Printable llvm::printJumpTableEntryReference(unsigned Idx) {
 921   return Printable([Idx](raw_ostream &OS) { OS << "%jump-table." << Idx; });
 922 }
 923
 924 //===----------------------------------------------------------------------===//
 925 //  MachineConstantPool implementation
 926 //===----------------------------------------------------------------------===//
 927
 928 void MachineConstantPoolValue::anchor() {}
 929
 930 Type *MachineConstantPoolEntry::getType() const {
 931   if (isMachineConstantPoolEntry())
 932     return Val.MachineCPVal->getType();
 933   return Val.ConstVal->getType();
 934 }
 935
 936 bool MachineConstantPoolEntry::needsRelocation() const {
 937   if (isMachineConstantPoolEntry())
 938     return true;
 939   return Val.ConstVal->needsRelocation();
 940 }
 941
 942 SectionKind
 943 MachineConstantPoolEntry::getSectionKind(const DataLayout *DL) const {
 944   if (needsRelocation())
 945     return SectionKind::getReadOnlyWithRel();
 946   switch (DL->getTypeAllocSize(getType())) {
 947   case 4:
 948     return SectionKind::getMergeableConst4();
 949   case 8:
 950     return SectionKind::getMergeableConst8();
 951   case 16:
 952     return SectionKind::getMergeableConst16();
 953   case 32:
 954     return SectionKind::getMergeableConst32();
 955   default:
 956     return SectionKind::getReadOnly();
 957   }
 958 }
 959
 960 MachineConstantPool::~MachineConstantPool() {
 961   // A constant may be a member of both Constants and MachineCPVsSharingEntries,
 962   // so keep track of which we've deleted to avoid double deletions.
 963   DenseSet<MachineConstantPoolValue*> Deleted;
 964   for (unsigned i = 0, e = Constants.size(); i != e; ++i)
 965     if (Constants[i].isMachineConstantPoolEntry()) {
 966       Deleted.insert(Constants[i].Val.MachineCPVal);
 967       delete Constants[i].Val.MachineCPVal;
 968     }
 969   for (DenseSet<MachineConstantPoolValue*>::iterator I =
 970        MachineCPVsSharingEntries.begin(), E = MachineCPVsSharingEntries.end();
 971        I != E; ++I) {
 972     if (Deleted.count(*I) == 0)
 973       delete *I;
 974   }
 975 }
 976
 977 /// Test whether the given two constants can be allocated the same constant pool
 978 /// entry.
 979 static bool CanShareConstantPoolEntry(const Constant *A, const Constant *B,
 980                                       const DataLayout &DL) {
 981   // Handle the trivial case quickly.
 982   if (A == B) return true;
 983
 984   // If they have the same type but weren't the same constant, quickly
 985   // reject them.
 986   if (A->getType() == B->getType()) return false;
 987
 988   // We can't handle structs or arrays.
 989   if (isa<StructType>(A->getType()) || isa<ArrayType>(A->getType()) ||
 990       isa<StructType>(B->getType()) || isa<ArrayType>(B->getType()))
 991     return false;
 992
 993   // For now, only support constants with the same size.
 994   uint64_t StoreSize = DL.getTypeStoreSize(A->getType());
 995   if (StoreSize != DL.getTypeStoreSize(B->getType()) || StoreSize > 128)
 996     return false;
 997
 998   Type *IntTy = IntegerType::get(A->getContext(), StoreSize*8);
 999
1000   // Try constant folding a bitcast of both instructions to an integer.  If we
1001   // get two identical ConstantInt's, then we are good to share them.  We use
1002   // the constant folding APIs to do this so that we get the benefit of
1003   // DataLayout.
1004   if (isa<PointerType>(A->getType()))
1005     A = ConstantFoldCastOperand(Instruction::PtrToInt,
1006                                 const_cast<Constant *>(A), IntTy, DL);
1007   else if (A->getType() != IntTy)
1008     A = ConstantFoldCastOperand(Instruction::BitCast, const_cast<Constant *>(A),
1009                                 IntTy, DL);
1010   if (isa<PointerType>(B->getType()))
1011     B = ConstantFoldCastOperand(Instruction::PtrToInt,
1012                                 const_cast<Constant *>(B), IntTy, DL);
1013   else if (B->getType() != IntTy)
1014     B = ConstantFoldCastOperand(Instruction::BitCast, const_cast<Constant *>(B),
1015                                 IntTy, DL);
1016
1017   return A == B;
1018 }
1019
1020 /// Create a new entry in the constant pool or return an existing one.
1021 /// User must specify the log2 of the minimum required alignment for the object.
1022 unsigned MachineConstantPool::getConstantPoolIndex(const Constant *C,
1023                                                    unsigned Alignment) {
1024   assert(Alignment && "Alignment must be specified!");
1025   if (Alignment > PoolAlignment) PoolAlignment = Alignment;
1026
1027   // Check to see if we already have this constant.
1028   //
1029   // FIXME, this could be made much more efficient for large constant pools.
1030   for (unsigned i = 0, e = Constants.size(); i != e; ++i)
1031     if (!Constants[i].isMachineConstantPoolEntry() &&
1032         CanShareConstantPoolEntry(Constants[i].Val.ConstVal, C, DL)) {
1033       if ((unsigned)Constants[i].getAlignment() < Alignment)
1034         Constants[i].Alignment = Alignment;
1035       return i;
1036     }
1037
1038   Constants.push_back(MachineConstantPoolEntry(C, Alignment));
1039   return Constants.size()-1;
1040 }
1041
1042 unsigned MachineConstantPool::getConstantPoolIndex(MachineConstantPoolValue *V,
1043                                                    unsigned Alignment) {
1044   assert(Alignment && "Alignment must be specified!");
1045   if (Alignment > PoolAlignment) PoolAlignment = Alignment;
1046
1047   // Check to see if we already have this constant.
1048   //
1049   // FIXME, this could be made much more efficient for large constant pools.
1050   int Idx = V->getExistingMachineCPValue(this, Alignment);
1051   if (Idx != -1) {
1052     MachineCPVsSharingEntries.insert(V);
1053     return (unsigned)Idx;
1054   }
1055
1056   Constants.push_back(MachineConstantPoolEntry(V, Alignment));
1057   return Constants.size()-1;
1058 }
1059
1060 void MachineConstantPool::print(raw_ostream &OS) const {
1061   if (Constants.empty()) return;
1062
1063   OS << "Constant Pool:\n";
1064   for (unsigned i = 0, e = Constants.size(); i != e; ++i) {
1065     OS << "  cp#" << i << ": ";
1066     if (Constants[i].isMachineConstantPoolEntry())
1067       Constants[i].Val.MachineCPVal->print(OS);
1068     else
1069       Constants[i].Val.ConstVal->printAsOperand(OS, /*PrintType=*/false);
1070     OS << ", align=" << Constants[i].getAlignment();
1071     OS << "\n";
1072   }
1073 }
1074
1075 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1076 LLVM_DUMP_METHOD void MachineConstantPool::dump() const { print(dbgs()); }
1077 #endif