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