LCOV - code coverage report
Current view: top level - lib/CodeGen/GlobalISel - RegBankSelect.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 218 356 61.2 %
Date: 2017-09-14 15:23:50 Functions: 27 38 71.1 %
Legend: Lines: hit not hit

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

Generated by: LCOV version 1.13