contrib/llvm/lib/CodeGen/GlobalISel/RegBankSelect.cpp

   1 //===- llvm/CodeGen/GlobalISel/RegBankSelect.cpp - RegBankSelect -*- 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 /// \file
  10 /// This file implements the RegBankSelect class.
  11 //===----------------------------------------------------------------------===//
  12
  13 #include "llvm/CodeGen/GlobalISel/RegBankSelect.h"
  14 #include "llvm/ADT/PostOrderIterator.h"
  15 #include "llvm/CodeGen/GlobalISel/RegisterBank.h"
  16 #include "llvm/CodeGen/MachineBlockFrequencyInfo.h"
  17 #include "llvm/CodeGen/MachineBranchProbabilityInfo.h"
  18 #include "llvm/CodeGen/MachineRegisterInfo.h"
  19 #include "llvm/IR/Function.h"
  20 #include "llvm/Support/BlockFrequency.h"
  21 #include "llvm/Support/CommandLine.h"
  22 #include "llvm/Support/Debug.h"
  23 #include "llvm/Target/TargetSubtargetInfo.h"
  24
  25 #define DEBUG_TYPE "regbankselect"
  26
  27 using namespace llvm;
  28
  29 static cl::opt<RegBankSelect::Mode> RegBankSelectMode(
  30     cl::desc("Mode of the RegBankSelect pass"), cl::Hidden, cl::Optional,
  31     cl::values(clEnumValN(RegBankSelect::Mode::Fast, "regbankselect-fast",
  32                           "Run the Fast mode (default mapping)"),
  33                clEnumValN(RegBankSelect::Mode::Greedy, "regbankselect-greedy",
  34                           "Use the Greedy mode (best local mapping)"),
  35                clEnumValEnd));
  36
  37 char RegBankSelect::ID = 0;
  38 INITIALIZE_PASS_BEGIN(RegBankSelect, "regbankselect",
  39                       "Assign register bank of generic virtual registers",
  40                       false, false);
  41 INITIALIZE_PASS_DEPENDENCY(MachineBlockFrequencyInfo)
  42 INITIALIZE_PASS_DEPENDENCY(MachineBranchProbabilityInfo)
  43 INITIALIZE_PASS_END(RegBankSelect, "regbankselect",
  44                     "Assign register bank of generic virtual registers", false,
  45                     false);
  46
  47 RegBankSelect::RegBankSelect(Mode RunningMode)
  48     : MachineFunctionPass(ID), RBI(nullptr), MRI(nullptr), TRI(nullptr),
  49       MBFI(nullptr), MBPI(nullptr), OptMode(RunningMode) {
  50   initializeRegBankSelectPass(*PassRegistry::getPassRegistry());
  51   if (RegBankSelectMode.getNumOccurrences() != 0) {
  52     OptMode = RegBankSelectMode;
  53     if (RegBankSelectMode != RunningMode)
  54       DEBUG(dbgs() << "RegBankSelect mode overrided by command line\n");
  55   }
  56 }
  57
  58 void RegBankSelect::init(MachineFunction &MF) {
  59   RBI = MF.getSubtarget().getRegBankInfo();
  60   assert(RBI && "Cannot work without RegisterBankInfo");
  61   MRI = &MF.getRegInfo();
  62   TRI = MF.getSubtarget().getRegisterInfo();
  63   if (OptMode != Mode::Fast) {
  64     MBFI = &getAnalysis<MachineBlockFrequencyInfo>();
  65     MBPI = &getAnalysis<MachineBranchProbabilityInfo>();
  66   } else {
  67     MBFI = nullptr;
  68     MBPI = nullptr;
  69   }
  70   MIRBuilder.setMF(MF);
  71 }
  72
  73 void RegBankSelect::getAnalysisUsage(AnalysisUsage &AU) const {
  74   if (OptMode != Mode::Fast) {
  75     // We could preserve the information from these two analysis but
  76     // the APIs do not allow to do so yet.
  77     AU.addRequired<MachineBlockFrequencyInfo>();
  78     AU.addRequired<MachineBranchProbabilityInfo>();
  79   }
  80   MachineFunctionPass::getAnalysisUsage(AU);
  81 }
  82
  83 bool RegBankSelect::assignmentMatch(
  84     unsigned Reg, const RegisterBankInfo::ValueMapping &ValMapping,
  85     bool &OnlyAssign) const {
  86   // By default we assume we will have to repair something.
  87   OnlyAssign = false;
  88   // Each part of a break down needs to end up in a different register.
  89   // In other word, Reg assignement does not match.
  90   if (ValMapping.BreakDown.size() > 1)
  91     return false;
  92
  93   const RegisterBank *CurRegBank = RBI->getRegBank(Reg, *MRI, *TRI);
  94   const RegisterBank *DesiredRegBrank = ValMapping.BreakDown[0].RegBank;
  95   // Reg is free of assignment, a simple assignment will make the
  96   // register bank to match.
  97   OnlyAssign = CurRegBank == nullptr;
  98   DEBUG(dbgs() << "Does assignment already match: ";
  99         if (CurRegBank) dbgs() << *CurRegBank; else dbgs() << "none";
 100         dbgs() << " against ";
 101         assert(DesiredRegBrank && "The mapping must be valid");
 102         dbgs() << *DesiredRegBrank << '\n';);
 103   return CurRegBank == DesiredRegBrank;
 104 }
 105
 106 void RegBankSelect::repairReg(
 107     MachineOperand &MO, const RegisterBankInfo::ValueMapping &ValMapping,
 108     RegBankSelect::RepairingPlacement &RepairPt,
 109     const iterator_range<SmallVectorImpl<unsigned>::const_iterator> &NewVRegs) {
 110   assert(ValMapping.BreakDown.size() == 1 && "Not yet implemented");
 111   // An empty range of new register means no repairing.
 112   assert(NewVRegs.begin() != NewVRegs.end() && "We should not have to repair");
 113
 114   // Assume we are repairing a use and thus, the original reg will be
 115   // the source of the repairing.
 116   unsigned Src = MO.getReg();
 117   unsigned Dst = *NewVRegs.begin();
 118
 119   // If we repair a definition, swap the source and destination for
 120   // the repairing.
 121   if (MO.isDef())
 122     std::swap(Src, Dst);
 123
 124   assert((RepairPt.getNumInsertPoints() == 1 ||
 125           TargetRegisterInfo::isPhysicalRegister(Dst)) &&
 126          "We are about to create several defs for Dst");
 127
 128   // Build the instruction used to repair, then clone it at the right places.
 129   MachineInstr *MI = MIRBuilder.buildInstr(TargetOpcode::COPY, Dst, Src);
 130   MI->removeFromParent();
 131   DEBUG(dbgs() << "Copy: " << PrintReg(Src) << " to: " << PrintReg(Dst)
 132                << '\n');
 133   // TODO:
 134   // Check if MI is legal. if not, we need to legalize all the
 135   // instructions we are going to insert.
 136   std::unique_ptr<MachineInstr *[]> NewInstrs(
 137       new MachineInstr *[RepairPt.getNumInsertPoints()]);
 138   bool IsFirst = true;
 139   unsigned Idx = 0;
 140   for (const std::unique_ptr<InsertPoint> &InsertPt : RepairPt) {
 141     MachineInstr *CurMI;
 142     if (IsFirst)
 143       CurMI = MI;
 144     else
 145       CurMI = MIRBuilder.getMF().CloneMachineInstr(MI);
 146     InsertPt->insert(*CurMI);
 147     NewInstrs[Idx++] = CurMI;
 148     IsFirst = false;
 149   }
 150   // TODO:
 151   // Legalize NewInstrs if need be.
 152 }
 153
 154 uint64_t RegBankSelect::getRepairCost(
 155     const MachineOperand &MO,
 156     const RegisterBankInfo::ValueMapping &ValMapping) const {
 157   assert(MO.isReg() && "We should only repair register operand");
 158   assert(!ValMapping.BreakDown.empty() && "Nothing to map??");
 159
 160   bool IsSameNumOfValues = ValMapping.BreakDown.size() == 1;
 161   const RegisterBank *CurRegBank = RBI->getRegBank(MO.getReg(), *MRI, *TRI);
 162   // If MO does not have a register bank, we should have just been
 163   // able to set one unless we have to break the value down.
 164   assert((!IsSameNumOfValues || CurRegBank) && "We should not have to repair");
 165   // Def: Val <- NewDefs
 166   //     Same number of values: copy
 167   //     Different number: Val = build_sequence Defs1, Defs2, ...
 168   // Use: NewSources <- Val.
 169   //     Same number of values: copy.
 170   //     Different number: Src1, Src2, ... =
 171   //           extract_value Val, Src1Begin, Src1Len, Src2Begin, Src2Len, ...
 172   // We should remember that this value is available somewhere else to
 173   // coalesce the value.
 174
 175   if (IsSameNumOfValues) {
 176     const RegisterBank *DesiredRegBrank = ValMapping.BreakDown[0].RegBank;
 177     // If we repair a definition, swap the source and destination for
 178     // the repairing.
 179     if (MO.isDef())
 180       std::swap(CurRegBank, DesiredRegBrank);
 181     // TODO: It may be possible to actually avoid the copy.
 182     // If we repair something where the source is defined by a copy
 183     // and the source of that copy is on the right bank, we can reuse
 184     // it for free.
 185     // E.g.,
 186     // RegToRepair<BankA> = copy AlternativeSrc<BankB>
 187     // = op RegToRepair<BankA>
 188     // We can simply propagate AlternativeSrc instead of copying RegToRepair
 189     // into a new virtual register.
 190     // We would also need to propagate this information in the
 191     // repairing placement.
 192     unsigned Cost =
 193         RBI->copyCost(*DesiredRegBrank, *CurRegBank,
 194                       RegisterBankInfo::getSizeInBits(MO.getReg(), *MRI, *TRI));
 195     // TODO: use a dedicated constant for ImpossibleCost.
 196     if (Cost != UINT_MAX)
 197       return Cost;
 198     assert(false && "Legalization not available yet");
 199     // Return the legalization cost of that repairing.
 200   }
 201   assert(false && "Complex repairing not implemented yet");
 202   return 1;
 203 }
 204
 205 RegisterBankInfo::InstructionMapping &RegBankSelect::findBestMapping(
 206     MachineInstr &MI, RegisterBankInfo::InstructionMappings &PossibleMappings,
 207     SmallVectorImpl<RepairingPlacement> &RepairPts) {
 208
 209   RegisterBankInfo::InstructionMapping *BestMapping = nullptr;
 210   MappingCost Cost = MappingCost::ImpossibleCost();
 211   SmallVector<RepairingPlacement, 4> LocalRepairPts;
 212   for (RegisterBankInfo::InstructionMapping &CurMapping : PossibleMappings) {
 213     MappingCost CurCost = computeMapping(MI, CurMapping, LocalRepairPts, &Cost);
 214     if (CurCost < Cost) {
 215       Cost = CurCost;
 216       BestMapping = &CurMapping;
 217       RepairPts.clear();
 218       for (RepairingPlacement &RepairPt : LocalRepairPts)
 219         RepairPts.emplace_back(std::move(RepairPt));
 220     }
 221   }
 222   assert(BestMapping && "No suitable mapping for instruction");
 223   return *BestMapping;
 224 }
 225
 226 void RegBankSelect::tryAvoidingSplit(
 227     RegBankSelect::RepairingPlacement &RepairPt, const MachineOperand &MO,
 228     const RegisterBankInfo::ValueMapping &ValMapping) const {
 229   const MachineInstr &MI = *MO.getParent();
 230   assert(RepairPt.hasSplit() && "We should not have to adjust for split");
 231   // Splitting should only occur for PHIs or between terminators,
 232   // because we only do local repairing.
 233   assert((MI.isPHI() || MI.isTerminator()) && "Why do we split?");
 234
 235   assert(&MI.getOperand(RepairPt.getOpIdx()) == &MO &&
 236          "Repairing placement does not match operand");
 237
 238   // If we need splitting for phis, that means it is because we
 239   // could not find an insertion point before the terminators of
 240   // the predecessor block for this argument. In other words,
 241   // the input value is defined by one of the terminators.
 242   assert((!MI.isPHI() || !MO.isDef()) && "Need split for phi def?");
 243
 244   // We split to repair the use of a phi or a terminator.
 245   if (!MO.isDef()) {
 246     if (MI.isTerminator()) {
 247       assert(&MI != &(*MI.getParent()->getFirstTerminator()) &&
 248              "Need to split for the first terminator?!");
 249     } else {
 250       // For the PHI case, the split may not be actually required.
 251       // In the copy case, a phi is already a copy on the incoming edge,
 252       // therefore there is no need to split.
 253       if (ValMapping.BreakDown.size() == 1)
 254         // This is a already a copy, there is nothing to do.
 255         RepairPt.switchTo(RepairingPlacement::RepairingKind::Reassign);
 256     }
 257     return;
 258   }
 259
 260   // At this point, we need to repair a defintion of a terminator.
 261
 262   // Technically we need to fix the def of MI on all outgoing
 263   // edges of MI to keep the repairing local. In other words, we
 264   // will create several definitions of the same register. This
 265   // does not work for SSA unless that definition is a physical
 266   // register.
 267   // However, there are other cases where we can get away with
 268   // that while still keeping the repairing local.
 269   assert(MI.isTerminator() && MO.isDef() &&
 270          "This code is for the def of a terminator");
 271
 272   // Since we use RPO traversal, if we need to repair a definition
 273   // this means this definition could be:
 274   // 1. Used by PHIs (i.e., this VReg has been visited as part of the
 275   //    uses of a phi.), or
 276   // 2. Part of a target specific instruction (i.e., the target applied
 277   //    some register class constraints when creating the instruction.)
 278   // If the constraints come for #2, the target said that another mapping
 279   // is supported so we may just drop them. Indeed, if we do not change
 280   // the number of registers holding that value, the uses will get fixed
 281   // when we get to them.
 282   // Uses in PHIs may have already been proceeded though.
 283   // If the constraints come for #1, then, those are weak constraints and
 284   // no actual uses may rely on them. However, the problem remains mainly
 285   // the same as for #2. If the value stays in one register, we could
 286   // just switch the register bank of the definition, but we would need to
 287   // account for a repairing cost for each phi we silently change.
 288   //
 289   // In any case, if the value needs to be broken down into several
 290   // registers, the repairing is not local anymore as we need to patch
 291   // every uses to rebuild the value in just one register.
 292   //
 293   // To summarize:
 294   // - If the value is in a physical register, we can do the split and
 295   //   fix locally.
 296   // Otherwise if the value is in a virtual register:
 297   // - If the value remains in one register, we do not have to split
 298   //   just switching the register bank would do, but we need to account
 299   //   in the repairing cost all the phi we changed.
 300   // - If the value spans several registers, then we cannot do a local
 301   //   repairing.
 302
 303   // Check if this is a physical or virtual register.
 304   unsigned Reg = MO.getReg();
 305   if (TargetRegisterInfo::isPhysicalRegister(Reg)) {
 306     // We are going to split every outgoing edges.
 307     // Check that this is possible.
 308     // FIXME: The machine representation is currently broken
 309     // since it also several terminators in one basic block.
 310     // Because of that we would technically need a way to get
 311     // the targets of just one terminator to know which edges
 312     // we have to split.
 313     // Assert that we do not hit the ill-formed representation.
 314
 315     // If there are other terminators before that one, some of
 316     // the outgoing edges may not be dominated by this definition.
 317     assert(&MI == &(*MI.getParent()->getFirstTerminator()) &&
 318            "Do not know which outgoing edges are relevant");
 319     const MachineInstr *Next = MI.getNextNode();
 320     assert((!Next || Next->isUnconditionalBranch()) &&
 321            "Do not know where each terminator ends up");
 322     if (Next)
 323       // If the next terminator uses Reg, this means we have
 324       // to split right after MI and thus we need a way to ask
 325       // which outgoing edges are affected.
 326       assert(!Next->readsRegister(Reg) && "Need to split between terminators");
 327     // We will split all the edges and repair there.
 328   } else {
 329     // This is a virtual register defined by a terminator.
 330     if (ValMapping.BreakDown.size() == 1) {
 331       // There is nothing to repair, but we may actually lie on
 332       // the repairing cost because of the PHIs already proceeded
 333       // as already stated.
 334       // Though the code will be correct.
 335       assert(0 && "Repairing cost may not be accurate");
 336     } else {
 337       // We need to do non-local repairing. Basically, patch all
 338       // the uses (i.e., phis) that we already proceeded.
 339       // For now, just say this mapping is not possible.
 340       RepairPt.switchTo(RepairingPlacement::RepairingKind::Impossible);
 341     }
 342   }
 343 }
 344
 345 RegBankSelect::MappingCost RegBankSelect::computeMapping(
 346     MachineInstr &MI, const RegisterBankInfo::InstructionMapping &InstrMapping,
 347     SmallVectorImpl<RepairingPlacement> &RepairPts,
 348     const RegBankSelect::MappingCost *BestCost) {
 349   assert((MBFI || !BestCost) && "Costs comparison require MBFI");
 350
 351   // If mapped with InstrMapping, MI will have the recorded cost.
 352   MappingCost Cost(MBFI ? MBFI->getBlockFreq(MI.getParent()) : 1);
 353   bool Saturated = Cost.addLocalCost(InstrMapping.getCost());
 354   assert(!Saturated && "Possible mapping saturated the cost");
 355   DEBUG(dbgs() << "Evaluating mapping cost for: " << MI);
 356   DEBUG(dbgs() << "With: " << InstrMapping << '\n');
 357   RepairPts.clear();
 358   if (BestCost && Cost > *BestCost)
 359     return Cost;
 360
 361   // Moreover, to realize this mapping, the register bank of each operand must
 362   // match this mapping. In other words, we may need to locally reassign the
 363   // register banks. Account for that repairing cost as well.
 364   // In this context, local means in the surrounding of MI.
 365   for (unsigned OpIdx = 0, EndOpIdx = MI.getNumOperands(); OpIdx != EndOpIdx;
 366        ++OpIdx) {
 367     const MachineOperand &MO = MI.getOperand(OpIdx);
 368     if (!MO.isReg())
 369       continue;
 370     unsigned Reg = MO.getReg();
 371     if (!Reg)
 372       continue;
 373     DEBUG(dbgs() << "Opd" << OpIdx);
 374     const RegisterBankInfo::ValueMapping &ValMapping =
 375         InstrMapping.getOperandMapping(OpIdx);
 376     // If Reg is already properly mapped, this is free.
 377     bool Assign;
 378     if (assignmentMatch(Reg, ValMapping, Assign)) {
 379       DEBUG(dbgs() << " is free (match).\n");
 380       continue;
 381     }
 382     if (Assign) {
 383       DEBUG(dbgs() << " is free (simple assignment).\n");
 384       RepairPts.emplace_back(RepairingPlacement(MI, OpIdx, *TRI, *this,
 385                                                 RepairingPlacement::Reassign));
 386       continue;
 387     }
 388
 389     // Find the insertion point for the repairing code.
 390     RepairPts.emplace_back(
 391         RepairingPlacement(MI, OpIdx, *TRI, *this, RepairingPlacement::Insert));
 392     RepairingPlacement &RepairPt = RepairPts.back();
 393
 394     // If we need to split a basic block to materialize this insertion point,
 395     // we may give a higher cost to this mapping.
 396     // Nevertheless, we may get away with the split, so try that first.
 397     if (RepairPt.hasSplit())
 398       tryAvoidingSplit(RepairPt, MO, ValMapping);
 399
 400     // Check that the materialization of the repairing is possible.
 401     if (!RepairPt.canMaterialize())
 402       return MappingCost::ImpossibleCost();
 403
 404     // Account for the split cost and repair cost.
 405     // Unless the cost is already saturated or we do not care about the cost.
 406     if (!BestCost || Saturated)
 407       continue;
 408
 409     // To get accurate information we need MBFI and MBPI.
 410     // Thus, if we end up here this information should be here.
 411     assert(MBFI && MBPI && "Cost computation requires MBFI and MBPI");
 412
 413     // FIXME: We will have to rework the repairing cost model.
 414     // The repairing cost depends on the register bank that MO has.
 415     // However, when we break down the value into different values,
 416     // MO may not have a register bank while still needing repairing.
 417     // For the fast mode, we don't compute the cost so that is fine,
 418     // but still for the repairing code, we will have to make a choice.
 419     // For the greedy mode, we should choose greedily what is the best
 420     // choice based on the next use of MO.
 421
 422     // Sums up the repairing cost of MO at each insertion point.
 423     uint64_t RepairCost = getRepairCost(MO, ValMapping);
 424     // Bias used for splitting: 5%.
 425     const uint64_t PercentageForBias = 5;
 426     uint64_t Bias = (RepairCost * PercentageForBias + 99) / 100;
 427     // We should not need more than a couple of instructions to repair
 428     // an assignment. In other words, the computation should not
 429     // overflow because the repairing cost is free of basic block
 430     // frequency.
 431     assert(((RepairCost < RepairCost * PercentageForBias) &&
 432             (RepairCost * PercentageForBias <
 433              RepairCost * PercentageForBias + 99)) &&
 434            "Repairing involves more than a billion of instructions?!");
 435     for (const std::unique_ptr<InsertPoint> &InsertPt : RepairPt) {
 436       assert(InsertPt->canMaterialize() && "We should not have made it here");
 437       // We will applied some basic block frequency and those uses uint64_t.
 438       if (!InsertPt->isSplit())
 439         Saturated = Cost.addLocalCost(RepairCost);
 440       else {
 441         uint64_t CostForInsertPt = RepairCost;
 442         // Again we shouldn't overflow here givent that
 443         // CostForInsertPt is frequency free at this point.
 444         assert(CostForInsertPt + Bias > CostForInsertPt &&
 445                "Repairing + split bias overflows");
 446         CostForInsertPt += Bias;
 447         uint64_t PtCost = InsertPt->frequency(*this) * CostForInsertPt;
 448         // Check if we just overflowed.
 449         if ((Saturated = PtCost < CostForInsertPt))
 450           Cost.saturate();
 451         else
 452           Saturated = Cost.addNonLocalCost(PtCost);
 453       }
 454
 455       // Stop looking into what it takes to repair, this is already
 456       // too expensive.
 457       if (BestCost && Cost > *BestCost)
 458         return Cost;
 459
 460       // No need to accumulate more cost information.
 461       // We need to still gather the repairing information though.
 462       if (Saturated)
 463         break;
 464     }
 465   }
 466   return Cost;
 467 }
 468
 469 void RegBankSelect::applyMapping(
 470     MachineInstr &MI, const RegisterBankInfo::InstructionMapping &InstrMapping,
 471     SmallVectorImpl<RegBankSelect::RepairingPlacement> &RepairPts) {
 472   // OpdMapper will hold all the information needed for the rewritting.
 473   RegisterBankInfo::OperandsMapper OpdMapper(MI, InstrMapping, *MRI);
 474
 475   // First, place the repairing code.
 476   for (RepairingPlacement &RepairPt : RepairPts) {
 477     assert(RepairPt.canMaterialize() &&
 478            RepairPt.getKind() != RepairingPlacement::Impossible &&
 479            "This mapping is impossible");
 480     assert(RepairPt.getKind() != RepairingPlacement::None &&
 481            "This should not make its way in the list");
 482     unsigned OpIdx = RepairPt.getOpIdx();
 483     MachineOperand &MO = MI.getOperand(OpIdx);
 484     const RegisterBankInfo::ValueMapping &ValMapping =
 485         InstrMapping.getOperandMapping(OpIdx);
 486     unsigned BreakDownSize = ValMapping.BreakDown.size();
 487     (void)BreakDownSize;
 488     unsigned Reg = MO.getReg();
 489
 490     switch (RepairPt.getKind()) {
 491     case RepairingPlacement::Reassign:
 492       assert(BreakDownSize == 1 &&
 493              "Reassignment should only be for simple mapping");
 494       MRI->setRegBank(Reg, *ValMapping.BreakDown[0].RegBank);
 495       break;
 496     case RepairingPlacement::Insert:
 497       OpdMapper.createVRegs(OpIdx);
 498       repairReg(MO, ValMapping, RepairPt, OpdMapper.getVRegs(OpIdx));
 499       break;
 500     default:
 501       llvm_unreachable("Other kind should not happen");
 502     }
 503   }
 504   // Second, rewrite the instruction.
 505   DEBUG(dbgs() << "Actual mapping of the operands: " << OpdMapper << '\n');
 506   RBI->applyMapping(OpdMapper);
 507 }
 508
 509 void RegBankSelect::assignInstr(MachineInstr &MI) {
 510   DEBUG(dbgs() << "Assign: " << MI);
 511   // Remember the repairing placement for all the operands.
 512   SmallVector<RepairingPlacement, 4> RepairPts;
 513
 514   RegisterBankInfo::InstructionMapping BestMapping;
 515   if (OptMode == RegBankSelect::Mode::Fast) {
 516     BestMapping = RBI->getInstrMapping(MI);
 517     MappingCost DefaultCost = computeMapping(MI, BestMapping, RepairPts);
 518     (void)DefaultCost;
 519     assert(DefaultCost != MappingCost::ImpossibleCost() &&
 520            "Default mapping is not suited");
 521   } else {
 522     RegisterBankInfo::InstructionMappings PossibleMappings =
 523         RBI->getInstrPossibleMappings(MI);
 524     assert(!PossibleMappings.empty() &&
 525            "Do not know how to map this instruction");
 526     BestMapping = std::move(findBestMapping(MI, PossibleMappings, RepairPts));
 527   }
 528   // Make sure the mapping is valid for MI.
 529   assert(BestMapping.verify(MI) && "Invalid instruction mapping");
 530
 531   DEBUG(dbgs() << "Mapping: " << BestMapping << '\n');
 532
 533   // After this call, MI may not be valid anymore.
 534   // Do not use it.
 535   applyMapping(MI, BestMapping, RepairPts);
 536 }
 537
 538 bool RegBankSelect::runOnMachineFunction(MachineFunction &MF) {
 539   DEBUG(dbgs() << "Assign register banks for: " << MF.getName() << '\n');
 540   const Function *F = MF.getFunction();
 541   Mode SaveOptMode = OptMode;
 542   if (F->hasFnAttribute(Attribute::OptimizeNone))
 543     OptMode = Mode::Fast;
 544   init(MF);
 545   // Walk the function and assign register banks to all operands.
 546   // Use a RPOT to make sure all registers are assigned before we choose
 547   // the best mapping of the current instruction.
 548   ReversePostOrderTraversal<MachineFunction*> RPOT(&MF);
 549   for (MachineBasicBlock *MBB : RPOT) {
 550     // Set a sensible insertion point so that subsequent calls to
 551     // MIRBuilder.
 552     MIRBuilder.setMBB(*MBB);
 553     for (MachineBasicBlock::iterator MII = MBB->begin(), End = MBB->end();
 554          MII != End;) {
 555       // MI might be invalidated by the assignment, so move the
 556       // iterator before hand.
 557       assignInstr(*MII++);
 558     }
 559   }
 560   OptMode = SaveOptMode;
 561   return false;
 562 }
 563
 564 //------------------------------------------------------------------------------
 565 //                  Helper Classes Implementation
 566 //------------------------------------------------------------------------------
 567 RegBankSelect::RepairingPlacement::RepairingPlacement(
 568     MachineInstr &MI, unsigned OpIdx, const TargetRegisterInfo &TRI, Pass &P,
 569     RepairingPlacement::RepairingKind Kind)
 570     // Default is, we are going to insert code to repair OpIdx.
 571     : Kind(Kind),
 572       OpIdx(OpIdx),
 573       CanMaterialize(Kind != RepairingKind::Impossible),
 574       HasSplit(false),
 575       P(P) {
 576   const MachineOperand &MO = MI.getOperand(OpIdx);
 577   assert(MO.isReg() && "Trying to repair a non-reg operand");
 578
 579   if (Kind != RepairingKind::Insert)
 580     return;
 581
 582   // Repairings for definitions happen after MI, uses happen before.
 583   bool Before = !MO.isDef();
 584
 585   // Check if we are done with MI.
 586   if (!MI.isPHI() && !MI.isTerminator()) {
 587     addInsertPoint(MI, Before);
 588     // We are done with the initialization.
 589     return;
 590   }
 591
 592   // Now, look for the special cases.
 593   if (MI.isPHI()) {
 594     // - PHI must be the first instructions:
 595     //   * Before, we have to split the related incoming edge.
 596     //   * After, move the insertion point past the last phi.
 597     if (!Before) {
 598       MachineBasicBlock::iterator It = MI.getParent()->getFirstNonPHI();
 599       if (It != MI.getParent()->end())
 600         addInsertPoint(*It, /*Before*/ true);
 601       else
 602         addInsertPoint(*(--It), /*Before*/ false);
 603       return;
 604     }
 605     // We repair a use of a phi, we may need to split the related edge.
 606     MachineBasicBlock &Pred = *MI.getOperand(OpIdx + 1).getMBB();
 607     // Check if we can move the insertion point prior to the
 608     // terminators of the predecessor.
 609     unsigned Reg = MO.getReg();
 610     MachineBasicBlock::iterator It = Pred.getLastNonDebugInstr();
 611     for (auto Begin = Pred.begin(); It != Begin && It->isTerminator(); --It)
 612       if (It->modifiesRegister(Reg, &TRI)) {
 613         // We cannot hoist the repairing code in the predecessor.
 614         // Split the edge.
 615         addInsertPoint(Pred, *MI.getParent());
 616         return;
 617       }
 618     // At this point, we can insert in Pred.
 619
 620     // - If It is invalid, Pred is empty and we can insert in Pred
 621     //   wherever we want.
 622     // - If It is valid, It is the first non-terminator, insert after It.
 623     if (It == Pred.end())
 624       addInsertPoint(Pred, /*Beginning*/ false);
 625     else
 626       addInsertPoint(*It, /*Before*/ false);
 627   } else {
 628     // - Terminators must be the last instructions:
 629     //   * Before, move the insert point before the first terminator.
 630     //   * After, we have to split the outcoming edges.
 631     unsigned Reg = MO.getReg();
 632     if (Before) {
 633       // Check whether Reg is defined by any terminator.
 634       MachineBasicBlock::iterator It = MI;
 635       for (auto Begin = MI.getParent()->begin();
 636            --It != Begin && It->isTerminator();)
 637         if (It->modifiesRegister(Reg, &TRI)) {
 638           // Insert the repairing code right after the definition.
 639           addInsertPoint(*It, /*Before*/ false);
 640           return;
 641         }
 642       addInsertPoint(*It, /*Before*/ true);
 643       return;
 644     }
 645     // Make sure Reg is not redefined by other terminators, otherwise
 646     // we do not know how to split.
 647     for (MachineBasicBlock::iterator It = MI, End = MI.getParent()->end();
 648          ++It != End;)
 649       // The machine verifier should reject this kind of code.
 650       assert(It->modifiesRegister(Reg, &TRI) && "Do not know where to split");
 651     // Split each outcoming edges.
 652     MachineBasicBlock &Src = *MI.getParent();
 653     for (auto &Succ : Src.successors())
 654       addInsertPoint(Src, Succ);
 655   }
 656 }
 657
 658 void RegBankSelect::RepairingPlacement::addInsertPoint(MachineInstr &MI,
 659                                                        bool Before) {
 660   addInsertPoint(*new InstrInsertPoint(MI, Before));
 661 }
 662
 663 void RegBankSelect::RepairingPlacement::addInsertPoint(MachineBasicBlock &MBB,
 664                                                        bool Beginning) {
 665   addInsertPoint(*new MBBInsertPoint(MBB, Beginning));
 666 }
 667
 668 void RegBankSelect::RepairingPlacement::addInsertPoint(MachineBasicBlock &Src,
 669                                                        MachineBasicBlock &Dst) {
 670   addInsertPoint(*new EdgeInsertPoint(Src, Dst, P));
 671 }
 672
 673 void RegBankSelect::RepairingPlacement::addInsertPoint(
 674     RegBankSelect::InsertPoint &Point) {
 675   CanMaterialize &= Point.canMaterialize();
 676   HasSplit |= Point.isSplit();
 677   InsertPoints.emplace_back(&Point);
 678 }
 679
 680 RegBankSelect::InstrInsertPoint::InstrInsertPoint(MachineInstr &Instr,
 681                                                   bool Before)
 682     : InsertPoint(), Instr(Instr), Before(Before) {
 683   // Since we do not support splitting, we do not need to update
 684   // liveness and such, so do not do anything with P.
 685   assert((!Before || !Instr.isPHI()) &&
 686          "Splitting before phis requires more points");
 687   assert((!Before || !Instr.getNextNode() || !Instr.getNextNode()->isPHI()) &&
 688          "Splitting between phis does not make sense");
 689 }
 690
 691 void RegBankSelect::InstrInsertPoint::materialize() {
 692   if (isSplit()) {
 693     // Slice and return the beginning of the new block.
 694     // If we need to split between the terminators, we theoritically
 695     // need to know where the first and second set of terminators end
 696     // to update the successors properly.
 697     // Now, in pratice, we should have a maximum of 2 branch
 698     // instructions; one conditional and one unconditional. Therefore
 699     // we know how to update the successor by looking at the target of
 700     // the unconditional branch.
 701     // If we end up splitting at some point, then, we should update
 702     // the liveness information and such. I.e., we would need to
 703     // access P here.
 704     // The machine verifier should actually make sure such cases
 705     // cannot happen.
 706     llvm_unreachable("Not yet implemented");
 707   }
 708   // Otherwise the insertion point is just the current or next
 709   // instruction depending on Before. I.e., there is nothing to do
 710   // here.
 711 }
 712
 713 bool RegBankSelect::InstrInsertPoint::isSplit() const {
 714   // If the insertion point is after a terminator, we need to split.
 715   if (!Before)
 716     return Instr.isTerminator();
 717   // If we insert before an instruction that is after a terminator,
 718   // we are still after a terminator.
 719   return Instr.getPrevNode() && Instr.getPrevNode()->isTerminator();
 720 }
 721
 722 uint64_t RegBankSelect::InstrInsertPoint::frequency(const Pass &P) const {
 723   // Even if we need to split, because we insert between terminators,
 724   // this split has actually the same frequency as the instruction.
 725   const MachineBlockFrequencyInfo *MBFI =
 726       P.getAnalysisIfAvailable<MachineBlockFrequencyInfo>();
 727   if (!MBFI)
 728     return 1;
 729   return MBFI->getBlockFreq(Instr.getParent()).getFrequency();
 730 }
 731
 732 uint64_t RegBankSelect::MBBInsertPoint::frequency(const Pass &P) const {
 733   const MachineBlockFrequencyInfo *MBFI =
 734       P.getAnalysisIfAvailable<MachineBlockFrequencyInfo>();
 735   if (!MBFI)
 736     return 1;
 737   return MBFI->getBlockFreq(&MBB).getFrequency();
 738 }
 739
 740 void RegBankSelect::EdgeInsertPoint::materialize() {
 741   // If we end up repairing twice at the same place before materializing the
 742   // insertion point, we may think we have to split an edge twice.
 743   // We should have a factory for the insert point such that identical points
 744   // are the same instance.
 745   assert(Src.isSuccessor(DstOrSplit) && DstOrSplit->isPredecessor(&Src) &&
 746          "This point has already been split");
 747   MachineBasicBlock *NewBB = Src.SplitCriticalEdge(DstOrSplit, P);
 748   assert(NewBB && "Invalid call to materialize");
 749   // We reuse the destination block to hold the information of the new block.
 750   DstOrSplit = NewBB;
 751 }
 752
 753 uint64_t RegBankSelect::EdgeInsertPoint::frequency(const Pass &P) const {
 754   const MachineBlockFrequencyInfo *MBFI =
 755       P.getAnalysisIfAvailable<MachineBlockFrequencyInfo>();
 756   if (!MBFI)
 757     return 1;
 758   if (WasMaterialized)
 759     return MBFI->getBlockFreq(DstOrSplit).getFrequency();
 760
 761   const MachineBranchProbabilityInfo *MBPI =
 762       P.getAnalysisIfAvailable<MachineBranchProbabilityInfo>();
 763   if (!MBPI)
 764     return 1;
 765   // The basic block will be on the edge.
 766   return (MBFI->getBlockFreq(&Src) * MBPI->getEdgeProbability(&Src, DstOrSplit))
 767       .getFrequency();
 768 }
 769
 770 bool RegBankSelect::EdgeInsertPoint::canMaterialize() const {
 771   // If this is not a critical edge, we should not have used this insert
 772   // point. Indeed, either the successor or the predecessor should
 773   // have do.
 774   assert(Src.succ_size() > 1 && DstOrSplit->pred_size() > 1 &&
 775          "Edge is not critical");
 776   return Src.canSplitCriticalEdge(DstOrSplit);
 777 }
 778
 779 RegBankSelect::MappingCost::MappingCost(const BlockFrequency &LocalFreq)
 780     : LocalCost(0), NonLocalCost(0), LocalFreq(LocalFreq.getFrequency()) {}
 781
 782 bool RegBankSelect::MappingCost::addLocalCost(uint64_t Cost) {
 783   // Check if this overflows.
 784   if (LocalCost + Cost < LocalCost) {
 785     saturate();
 786     return true;
 787   }
 788   LocalCost += Cost;
 789   return isSaturated();
 790 }
 791
 792 bool RegBankSelect::MappingCost::addNonLocalCost(uint64_t Cost) {
 793   // Check if this overflows.
 794   if (NonLocalCost + Cost < NonLocalCost) {
 795     saturate();
 796     return true;
 797   }
 798   NonLocalCost += Cost;
 799   return isSaturated();
 800 }
 801
 802 bool RegBankSelect::MappingCost::isSaturated() const {
 803   return LocalCost == UINT64_MAX - 1 && NonLocalCost == UINT64_MAX &&
 804          LocalFreq == UINT64_MAX;
 805 }
 806
 807 void RegBankSelect::MappingCost::saturate() {
 808   *this = ImpossibleCost();
 809   --LocalCost;
 810 }
 811
 812 RegBankSelect::MappingCost RegBankSelect::MappingCost::ImpossibleCost() {
 813   return MappingCost(UINT64_MAX, UINT64_MAX, UINT64_MAX);
 814 }
 815
 816 bool RegBankSelect::MappingCost::operator<(const MappingCost &Cost) const {
 817   // Sort out the easy cases.
 818   if (*this == Cost)
 819     return false;
 820   // If one is impossible to realize the other is cheaper unless it is
 821   // impossible as well.
 822   if ((*this == ImpossibleCost()) || (Cost == ImpossibleCost()))
 823     return (*this == ImpossibleCost()) < (Cost == ImpossibleCost());
 824   // If one is saturated the other is cheaper, unless it is saturated
 825   // as well.
 826   if (isSaturated() || Cost.isSaturated())
 827     return isSaturated() < Cost.isSaturated();
 828   // At this point we know both costs hold sensible values.
 829
 830   // If both values have a different base frequency, there is no much
 831   // we can do but to scale everything.
 832   // However, if they have the same base frequency we can avoid making
 833   // complicated computation.
 834   uint64_t ThisLocalAdjust;
 835   uint64_t OtherLocalAdjust;
 836   if (LLVM_LIKELY(LocalFreq == Cost.LocalFreq)) {
 837
 838     // At this point, we know the local costs are comparable.
 839     // Do the case that do not involve potential overflow first.
 840     if (NonLocalCost == Cost.NonLocalCost)
 841       // Since the non-local costs do not discriminate on the result,
 842       // just compare the local costs.
 843       return LocalCost < Cost.LocalCost;
 844
 845     // The base costs are comparable so we may only keep the relative
 846     // value to increase our chances of avoiding overflows.
 847     ThisLocalAdjust = 0;
 848     OtherLocalAdjust = 0;
 849     if (LocalCost < Cost.LocalCost)
 850       OtherLocalAdjust = Cost.LocalCost - LocalCost;
 851     else
 852       ThisLocalAdjust = LocalCost - Cost.LocalCost;
 853
 854   } else {
 855     ThisLocalAdjust = LocalCost;
 856     OtherLocalAdjust = Cost.LocalCost;
 857   }
 858
 859   // The non-local costs are comparable, just keep the relative value.
 860   uint64_t ThisNonLocalAdjust = 0;
 861   uint64_t OtherNonLocalAdjust = 0;
 862   if (NonLocalCost < Cost.NonLocalCost)
 863     OtherNonLocalAdjust = Cost.NonLocalCost - NonLocalCost;
 864   else
 865     ThisNonLocalAdjust = NonLocalCost - Cost.NonLocalCost;
 866   // Scale everything to make them comparable.
 867   uint64_t ThisScaledCost = ThisLocalAdjust * LocalFreq;
 868   // Check for overflow on that operation.
 869   bool ThisOverflows = ThisLocalAdjust && (ThisScaledCost < ThisLocalAdjust ||
 870                                            ThisScaledCost < LocalFreq);
 871   uint64_t OtherScaledCost = OtherLocalAdjust * Cost.LocalFreq;
 872   // Check for overflow on the last operation.
 873   bool OtherOverflows =
 874       OtherLocalAdjust &&
 875       (OtherScaledCost < OtherLocalAdjust || OtherScaledCost < Cost.LocalFreq);
 876   // Add the non-local costs.
 877   ThisOverflows |= ThisNonLocalAdjust &&
 878                    ThisScaledCost + ThisNonLocalAdjust < ThisNonLocalAdjust;
 879   ThisScaledCost += ThisNonLocalAdjust;
 880   OtherOverflows |= OtherNonLocalAdjust &&
 881                     OtherScaledCost + OtherNonLocalAdjust < OtherNonLocalAdjust;
 882   OtherScaledCost += OtherNonLocalAdjust;
 883   // If both overflows, we cannot compare without additional
 884   // precision, e.g., APInt. Just give up on that case.
 885   if (ThisOverflows && OtherOverflows)
 886     return false;
 887   // If one overflows but not the other, we can still compare.
 888   if (ThisOverflows || OtherOverflows)
 889     return ThisOverflows < OtherOverflows;
 890   // Otherwise, just compare the values.
 891   return ThisScaledCost < OtherScaledCost;
 892 }
 893
 894 bool RegBankSelect::MappingCost::operator==(const MappingCost &Cost) const {
 895   return LocalCost == Cost.LocalCost && NonLocalCost == Cost.NonLocalCost &&
 896          LocalFreq == Cost.LocalFreq;
 897 }