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