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