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

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