1115 lines · 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-exception6//7//===----------------------------------------------------------------------===//8/// \file9/// 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/Utils.h"18#include "llvm/CodeGen/MachineBasicBlock.h"19#include "llvm/CodeGen/MachineBlockFrequencyInfo.h"20#include "llvm/CodeGen/MachineBranchProbabilityInfo.h"21#include "llvm/CodeGen/MachineFunction.h"22#include "llvm/CodeGen/MachineInstr.h"23#include "llvm/CodeGen/MachineOperand.h"24#include "llvm/CodeGen/MachineOptimizationRemarkEmitter.h"25#include "llvm/CodeGen/MachineRegisterInfo.h"26#include "llvm/CodeGen/RegisterBank.h"27#include "llvm/CodeGen/RegisterBankInfo.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/Function.h"34#include "llvm/InitializePasses.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 51using namespace llvm;52 53static 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 60char RegBankSelect::ID = 0;61 62INITIALIZE_PASS_BEGIN(RegBankSelect, DEBUG_TYPE,63 "Assign register bank of generic virtual registers",64 false, false);65INITIALIZE_PASS_DEPENDENCY(MachineBlockFrequencyInfoWrapperPass)66INITIALIZE_PASS_DEPENDENCY(MachineBranchProbabilityInfoWrapperPass)67INITIALIZE_PASS_DEPENDENCY(TargetPassConfig)68INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE,69 "Assign register bank of generic virtual registers", false,70 false)71 72RegBankSelect::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 81void 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<MachineBlockFrequencyInfoWrapperPass>().getMBFI();89 MBPI = &getAnalysis<MachineBranchProbabilityInfoWrapperPass>().getMBPI();90 } else {91 MBFI = nullptr;92 MBPI = nullptr;93 }94 MIRBuilder.setMF(MF);95 MORE = std::make_unique<MachineOptimizationRemarkEmitter>(MF, MBFI);96}97 98void RegBankSelect::getAnalysisUsage(AnalysisUsage &AU) const {99 if (OptMode != Mode::Fast) {100 // We could preserve the information from these two analysis but101 // the APIs do not allow to do so yet.102 AU.addRequired<MachineBlockFrequencyInfoWrapperPass>();103 AU.addRequired<MachineBranchProbabilityInfoWrapperPass>();104 }105 AU.addRequired<TargetPassConfig>();106 getSelectionDAGFallbackAnalysisUsage(AU);107 MachineFunctionPass::getAnalysisUsage(AU);108}109 110bool 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 *DesiredRegBank = ValMapping.BreakDown[0].RegBank;122 // Reg is free of assignment, a simple assignment will make the123 // 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(DesiredRegBank && "The mapping must be valid");129 dbgs() << *DesiredRegBank << '\n';);130 return CurRegBank == DesiredRegBank;131}132 133bool 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(!NewVRegs.empty() && "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 be147 // 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 for152 // the repairing.153 if (MO.isDef())154 std::swap(Src, Dst);155 156 assert((RepairPt.getNumInsertPoints() == 1 || Dst.isPhysical()) &&157 "We are about to create several defs for Dst");158 159 // Build the instruction used to repair, then clone it at the right160 // places. Avoiding buildCopy bypasses the check that Src and Dst have the161 // same types because the type is a placeholder when this function is called.162 MI = MIRBuilder.buildInstrNoInsert(TargetOpcode::COPY)163 .addDef(Dst)164 .addUse(Src);165 LLVM_DEBUG(dbgs() << "Copy: " << printReg(Src) << ':'166 << printRegClassOrBank(Src, *MRI, TRI)167 << " to: " << printReg(Dst) << ':'168 << printRegClassOrBank(Dst, *MRI, TRI) << '\n');169 } else {170 // TODO: Support with G_IMPLICIT_DEF + G_INSERT sequence or G_EXTRACT171 // sequence.172 assert(ValMapping.partsAllUniform() && "irregular breakdowns not supported");173 174 LLT RegTy = MRI->getType(MO.getReg());175 if (MO.isDef()) {176 unsigned MergeOp;177 if (RegTy.isVector()) {178 if (ValMapping.NumBreakDowns == RegTy.getNumElements())179 MergeOp = TargetOpcode::G_BUILD_VECTOR;180 else {181 assert(182 (ValMapping.BreakDown[0].Length * ValMapping.NumBreakDowns ==183 RegTy.getSizeInBits()) &&184 (ValMapping.BreakDown[0].Length % RegTy.getScalarSizeInBits() ==185 0) &&186 "don't understand this value breakdown");187 188 MergeOp = TargetOpcode::G_CONCAT_VECTORS;189 }190 } else191 MergeOp = TargetOpcode::G_MERGE_VALUES;192 193 auto MergeBuilder =194 MIRBuilder.buildInstrNoInsert(MergeOp)195 .addDef(MO.getReg());196 197 for (Register SrcReg : NewVRegs)198 MergeBuilder.addUse(SrcReg);199 200 MI = MergeBuilder;201 } else {202 MachineInstrBuilder UnMergeBuilder =203 MIRBuilder.buildInstrNoInsert(TargetOpcode::G_UNMERGE_VALUES);204 for (Register DefReg : NewVRegs)205 UnMergeBuilder.addDef(DefReg);206 207 UnMergeBuilder.addUse(MO.getReg());208 MI = UnMergeBuilder;209 }210 }211 212 if (RepairPt.getNumInsertPoints() != 1)213 report_fatal_error("need testcase to support multiple insertion points");214 215 // TODO:216 // Check if MI is legal. if not, we need to legalize all the217 // instructions we are going to insert.218 std::unique_ptr<MachineInstr *[]> NewInstrs(219 new MachineInstr *[RepairPt.getNumInsertPoints()]);220 bool IsFirst = true;221 unsigned Idx = 0;222 for (const std::unique_ptr<InsertPoint> &InsertPt : RepairPt) {223 MachineInstr *CurMI;224 if (IsFirst)225 CurMI = MI;226 else227 CurMI = MIRBuilder.getMF().CloneMachineInstr(MI);228 InsertPt->insert(*CurMI);229 NewInstrs[Idx++] = CurMI;230 IsFirst = false;231 }232 // TODO:233 // Legalize NewInstrs if need be.234 return true;235}236 237uint64_t RegBankSelect::getRepairCost(238 const MachineOperand &MO,239 const RegisterBankInfo::ValueMapping &ValMapping) const {240 assert(MO.isReg() && "We should only repair register operand");241 assert(ValMapping.NumBreakDowns && "Nothing to map??");242 243 bool IsSameNumOfValues = ValMapping.NumBreakDowns == 1;244 const RegisterBank *CurRegBank = RBI->getRegBank(MO.getReg(), *MRI, *TRI);245 // If MO does not have a register bank, we should have just been246 // able to set one unless we have to break the value down.247 assert(CurRegBank || MO.isDef());248 249 // Def: Val <- NewDefs250 // Same number of values: copy251 // Different number: Val = build_sequence Defs1, Defs2, ...252 // Use: NewSources <- Val.253 // Same number of values: copy.254 // Different number: Src1, Src2, ... =255 // extract_value Val, Src1Begin, Src1Len, Src2Begin, Src2Len, ...256 // We should remember that this value is available somewhere else to257 // coalesce the value.258 259 if (ValMapping.NumBreakDowns != 1)260 return RBI->getBreakDownCost(ValMapping, CurRegBank);261 262 if (IsSameNumOfValues) {263 const RegisterBank *DesiredRegBank = ValMapping.BreakDown[0].RegBank;264 // If we repair a definition, swap the source and destination for265 // the repairing.266 if (MO.isDef())267 std::swap(CurRegBank, DesiredRegBank);268 // TODO: It may be possible to actually avoid the copy.269 // If we repair something where the source is defined by a copy270 // and the source of that copy is on the right bank, we can reuse271 // it for free.272 // E.g.,273 // RegToRepair<BankA> = copy AlternativeSrc<BankB>274 // = op RegToRepair<BankA>275 // We can simply propagate AlternativeSrc instead of copying RegToRepair276 // into a new virtual register.277 // We would also need to propagate this information in the278 // repairing placement.279 unsigned Cost = RBI->copyCost(*DesiredRegBank, *CurRegBank,280 RBI->getSizeInBits(MO.getReg(), *MRI, *TRI));281 // TODO: use a dedicated constant for ImpossibleCost.282 if (Cost != std::numeric_limits<unsigned>::max())283 return Cost;284 // Return the legalization cost of that repairing.285 }286 return std::numeric_limits<unsigned>::max();287}288 289const RegisterBankInfo::InstructionMapping &RegBankSelect::findBestMapping(290 MachineInstr &MI, RegisterBankInfo::InstructionMappings &PossibleMappings,291 SmallVectorImpl<RepairingPlacement> &RepairPts) {292 assert(!PossibleMappings.empty() &&293 "Do not know how to map this instruction");294 295 const RegisterBankInfo::InstructionMapping *BestMapping = nullptr;296 MappingCost Cost = MappingCost::ImpossibleCost();297 SmallVector<RepairingPlacement, 4> LocalRepairPts;298 for (const RegisterBankInfo::InstructionMapping *CurMapping :299 PossibleMappings) {300 MappingCost CurCost =301 computeMapping(MI, *CurMapping, LocalRepairPts, &Cost);302 if (CurCost < Cost) {303 LLVM_DEBUG(dbgs() << "New best: " << CurCost << '\n');304 Cost = CurCost;305 BestMapping = CurMapping;306 RepairPts.clear();307 for (RepairingPlacement &RepairPt : LocalRepairPts)308 RepairPts.emplace_back(std::move(RepairPt));309 }310 }311 if (!BestMapping && !TPC->isGlobalISelAbortEnabled()) {312 // If none of the mapping worked that means they are all impossible.313 // Thus, pick the first one and set an impossible repairing point.314 // It will trigger the failed isel mode.315 BestMapping = *PossibleMappings.begin();316 RepairPts.emplace_back(317 RepairingPlacement(MI, 0, *TRI, *this, RepairingPlacement::Impossible));318 } else319 assert(BestMapping && "No suitable mapping for instruction");320 return *BestMapping;321}322 323void RegBankSelect::tryAvoidingSplit(324 RegBankSelect::RepairingPlacement &RepairPt, const MachineOperand &MO,325 const RegisterBankInfo::ValueMapping &ValMapping) const {326 const MachineInstr &MI = *MO.getParent();327 assert(RepairPt.hasSplit() && "We should not have to adjust for split");328 // Splitting should only occur for PHIs or between terminators,329 // because we only do local repairing.330 assert((MI.isPHI() || MI.isTerminator()) && "Why do we split?");331 332 assert(&MI.getOperand(RepairPt.getOpIdx()) == &MO &&333 "Repairing placement does not match operand");334 335 // If we need splitting for phis, that means it is because we336 // could not find an insertion point before the terminators of337 // the predecessor block for this argument. In other words,338 // the input value is defined by one of the terminators.339 assert((!MI.isPHI() || !MO.isDef()) && "Need split for phi def?");340 341 // We split to repair the use of a phi or a terminator.342 if (!MO.isDef()) {343 if (MI.isTerminator()) {344 assert(&MI != &(*MI.getParent()->getFirstTerminator()) &&345 "Need to split for the first terminator?!");346 } else {347 // For the PHI case, the split may not be actually required.348 // In the copy case, a phi is already a copy on the incoming edge,349 // therefore there is no need to split.350 if (ValMapping.NumBreakDowns == 1)351 // This is a already a copy, there is nothing to do.352 RepairPt.switchTo(RepairingPlacement::RepairingKind::Reassign);353 }354 return;355 }356 357 // At this point, we need to repair a defintion of a terminator.358 359 // Technically we need to fix the def of MI on all outgoing360 // edges of MI to keep the repairing local. In other words, we361 // will create several definitions of the same register. This362 // does not work for SSA unless that definition is a physical363 // register.364 // However, there are other cases where we can get away with365 // that while still keeping the repairing local.366 assert(MI.isTerminator() && MO.isDef() &&367 "This code is for the def of a terminator");368 369 // Since we use RPO traversal, if we need to repair a definition370 // this means this definition could be:371 // 1. Used by PHIs (i.e., this VReg has been visited as part of the372 // uses of a phi.), or373 // 2. Part of a target specific instruction (i.e., the target applied374 // some register class constraints when creating the instruction.)375 // If the constraints come for #2, the target said that another mapping376 // is supported so we may just drop them. Indeed, if we do not change377 // the number of registers holding that value, the uses will get fixed378 // when we get to them.379 // Uses in PHIs may have already been proceeded though.380 // If the constraints come for #1, then, those are weak constraints and381 // no actual uses may rely on them. However, the problem remains mainly382 // the same as for #2. If the value stays in one register, we could383 // just switch the register bank of the definition, but we would need to384 // account for a repairing cost for each phi we silently change.385 //386 // In any case, if the value needs to be broken down into several387 // registers, the repairing is not local anymore as we need to patch388 // every uses to rebuild the value in just one register.389 //390 // To summarize:391 // - If the value is in a physical register, we can do the split and392 // fix locally.393 // Otherwise if the value is in a virtual register:394 // - If the value remains in one register, we do not have to split395 // just switching the register bank would do, but we need to account396 // in the repairing cost all the phi we changed.397 // - If the value spans several registers, then we cannot do a local398 // repairing.399 400 // Check if this is a physical or virtual register.401 Register Reg = MO.getReg();402 if (Reg.isPhysical()) {403 // We are going to split every outgoing edges.404 // Check that this is possible.405 // FIXME: The machine representation is currently broken406 // since it also several terminators in one basic block.407 // Because of that we would technically need a way to get408 // the targets of just one terminator to know which edges409 // we have to split.410 // Assert that we do not hit the ill-formed representation.411 412 // If there are other terminators before that one, some of413 // the outgoing edges may not be dominated by this definition.414 assert(&MI == &(*MI.getParent()->getFirstTerminator()) &&415 "Do not know which outgoing edges are relevant");416 const MachineInstr *Next = MI.getNextNode();417 assert((!Next || Next->isUnconditionalBranch()) &&418 "Do not know where each terminator ends up");419 if (Next)420 // If the next terminator uses Reg, this means we have421 // to split right after MI and thus we need a way to ask422 // which outgoing edges are affected.423 assert(!Next->readsRegister(Reg, /*TRI=*/nullptr) &&424 "Need to split between terminators");425 // We will split all the edges and repair there.426 } else {427 // This is a virtual register defined by a terminator.428 if (ValMapping.NumBreakDowns == 1) {429 // There is nothing to repair, but we may actually lie on430 // the repairing cost because of the PHIs already proceeded431 // as already stated.432 // Though the code will be correct.433 assert(false && "Repairing cost may not be accurate");434 } else {435 // We need to do non-local repairing. Basically, patch all436 // the uses (i.e., phis) that we already proceeded.437 // For now, just say this mapping is not possible.438 RepairPt.switchTo(RepairingPlacement::RepairingKind::Impossible);439 }440 }441}442 443RegBankSelect::MappingCost RegBankSelect::computeMapping(444 MachineInstr &MI, const RegisterBankInfo::InstructionMapping &InstrMapping,445 SmallVectorImpl<RepairingPlacement> &RepairPts,446 const RegBankSelect::MappingCost *BestCost) {447 assert((MBFI || !BestCost) && "Costs comparison require MBFI");448 449 if (!InstrMapping.isValid())450 return MappingCost::ImpossibleCost();451 452 // If mapped with InstrMapping, MI will have the recorded cost.453 MappingCost Cost(MBFI ? MBFI->getBlockFreq(MI.getParent())454 : BlockFrequency(1));455 bool Saturated = Cost.addLocalCost(InstrMapping.getCost());456 assert(!Saturated && "Possible mapping saturated the cost");457 LLVM_DEBUG(dbgs() << "Evaluating mapping cost for: " << MI);458 LLVM_DEBUG(dbgs() << "With: " << InstrMapping << '\n');459 RepairPts.clear();460 if (BestCost && Cost > *BestCost) {461 LLVM_DEBUG(dbgs() << "Mapping is too expensive from the start\n");462 return Cost;463 }464 const MachineRegisterInfo &MRI = MI.getMF()->getRegInfo();465 466 // Moreover, to realize this mapping, the register bank of each operand must467 // match this mapping. In other words, we may need to locally reassign the468 // register banks. Account for that repairing cost as well.469 // In this context, local means in the surrounding of MI.470 for (unsigned OpIdx = 0, EndOpIdx = InstrMapping.getNumOperands();471 OpIdx != EndOpIdx; ++OpIdx) {472 const MachineOperand &MO = MI.getOperand(OpIdx);473 if (!MO.isReg())474 continue;475 Register Reg = MO.getReg();476 if (!Reg)477 continue;478 LLT Ty = MRI.getType(Reg);479 if (!Ty.isValid())480 continue;481 482 LLVM_DEBUG(dbgs() << "Opd" << OpIdx << '\n');483 const RegisterBankInfo::ValueMapping &ValMapping =484 InstrMapping.getOperandMapping(OpIdx);485 // If Reg is already properly mapped, this is free.486 bool Assign;487 if (assignmentMatch(Reg, ValMapping, Assign)) {488 LLVM_DEBUG(dbgs() << "=> is free (match).\n");489 continue;490 }491 if (Assign) {492 LLVM_DEBUG(dbgs() << "=> is free (simple assignment).\n");493 RepairPts.emplace_back(RepairingPlacement(MI, OpIdx, *TRI, *this,494 RepairingPlacement::Reassign));495 continue;496 }497 498 // Find the insertion point for the repairing code.499 RepairPts.emplace_back(500 RepairingPlacement(MI, OpIdx, *TRI, *this, RepairingPlacement::Insert));501 RepairingPlacement &RepairPt = RepairPts.back();502 503 // If we need to split a basic block to materialize this insertion point,504 // we may give a higher cost to this mapping.505 // Nevertheless, we may get away with the split, so try that first.506 if (RepairPt.hasSplit())507 tryAvoidingSplit(RepairPt, MO, ValMapping);508 509 // Check that the materialization of the repairing is possible.510 if (!RepairPt.canMaterialize()) {511 LLVM_DEBUG(dbgs() << "Mapping involves impossible repairing\n");512 return MappingCost::ImpossibleCost();513 }514 515 // Account for the split cost and repair cost.516 // Unless the cost is already saturated or we do not care about the cost.517 if (!BestCost || Saturated)518 continue;519 520 // To get accurate information we need MBFI and MBPI.521 // Thus, if we end up here this information should be here.522 assert(MBFI && MBPI && "Cost computation requires MBFI and MBPI");523 524 // FIXME: We will have to rework the repairing cost model.525 // The repairing cost depends on the register bank that MO has.526 // However, when we break down the value into different values,527 // MO may not have a register bank while still needing repairing.528 // For the fast mode, we don't compute the cost so that is fine,529 // but still for the repairing code, we will have to make a choice.530 // For the greedy mode, we should choose greedily what is the best531 // choice based on the next use of MO.532 533 // Sums up the repairing cost of MO at each insertion point.534 uint64_t RepairCost = getRepairCost(MO, ValMapping);535 536 // This is an impossible to repair cost.537 if (RepairCost == std::numeric_limits<unsigned>::max())538 return MappingCost::ImpossibleCost();539 540 // Bias used for splitting: 5%.541 const uint64_t PercentageForBias = 5;542 uint64_t Bias = (RepairCost * PercentageForBias + 99) / 100;543 // We should not need more than a couple of instructions to repair544 // an assignment. In other words, the computation should not545 // overflow because the repairing cost is free of basic block546 // frequency.547 assert(((RepairCost < RepairCost * PercentageForBias) &&548 (RepairCost * PercentageForBias <549 RepairCost * PercentageForBias + 99)) &&550 "Repairing involves more than a billion of instructions?!");551 for (const std::unique_ptr<InsertPoint> &InsertPt : RepairPt) {552 assert(InsertPt->canMaterialize() && "We should not have made it here");553 // We will applied some basic block frequency and those uses uint64_t.554 if (!InsertPt->isSplit())555 Saturated = Cost.addLocalCost(RepairCost);556 else {557 uint64_t CostForInsertPt = RepairCost;558 // Again we shouldn't overflow here givent that559 // CostForInsertPt is frequency free at this point.560 assert(CostForInsertPt + Bias > CostForInsertPt &&561 "Repairing + split bias overflows");562 CostForInsertPt += Bias;563 uint64_t PtCost = InsertPt->frequency(*this) * CostForInsertPt;564 // Check if we just overflowed.565 if ((Saturated = PtCost < CostForInsertPt))566 Cost.saturate();567 else568 Saturated = Cost.addNonLocalCost(PtCost);569 }570 571 // Stop looking into what it takes to repair, this is already572 // too expensive.573 if (BestCost && Cost > *BestCost) {574 LLVM_DEBUG(dbgs() << "Mapping is too expensive, stop processing\n");575 return Cost;576 }577 578 // No need to accumulate more cost information.579 // We need to still gather the repairing information though.580 if (Saturated)581 break;582 }583 }584 LLVM_DEBUG(dbgs() << "Total cost is: " << Cost << "\n");585 return Cost;586}587 588bool RegBankSelect::applyMapping(589 MachineInstr &MI, const RegisterBankInfo::InstructionMapping &InstrMapping,590 SmallVectorImpl<RegBankSelect::RepairingPlacement> &RepairPts) {591 // OpdMapper will hold all the information needed for the rewriting.592 RegisterBankInfo::OperandsMapper OpdMapper(MI, InstrMapping, *MRI);593 594 // First, place the repairing code.595 for (RepairingPlacement &RepairPt : RepairPts) {596 if (!RepairPt.canMaterialize() ||597 RepairPt.getKind() == RepairingPlacement::Impossible)598 return false;599 assert(RepairPt.getKind() != RepairingPlacement::None &&600 "This should not make its way in the list");601 unsigned OpIdx = RepairPt.getOpIdx();602 MachineOperand &MO = MI.getOperand(OpIdx);603 const RegisterBankInfo::ValueMapping &ValMapping =604 InstrMapping.getOperandMapping(OpIdx);605 Register Reg = MO.getReg();606 607 switch (RepairPt.getKind()) {608 case RepairingPlacement::Reassign:609 assert(ValMapping.NumBreakDowns == 1 &&610 "Reassignment should only be for simple mapping");611 MRI->setRegBank(Reg, *ValMapping.BreakDown[0].RegBank);612 break;613 case RepairingPlacement::Insert:614 // Don't insert additional instruction for debug instruction.615 if (MI.isDebugInstr())616 break;617 OpdMapper.createVRegs(OpIdx);618 if (!repairReg(MO, ValMapping, RepairPt, OpdMapper.getVRegs(OpIdx)))619 return false;620 break;621 default:622 llvm_unreachable("Other kind should not happen");623 }624 }625 626 // Second, rewrite the instruction.627 LLVM_DEBUG(dbgs() << "Actual mapping of the operands: " << OpdMapper << '\n');628 RBI->applyMapping(MIRBuilder, OpdMapper);629 630 return true;631}632 633bool RegBankSelect::assignInstr(MachineInstr &MI) {634 LLVM_DEBUG(dbgs() << "Assign: " << MI);635 636 unsigned Opc = MI.getOpcode();637 if (isPreISelGenericOptimizationHint(Opc)) {638 assert((Opc == TargetOpcode::G_ASSERT_ZEXT ||639 Opc == TargetOpcode::G_ASSERT_SEXT ||640 Opc == TargetOpcode::G_ASSERT_ALIGN) &&641 "Unexpected hint opcode!");642 // The only correct mapping for these is to always use the source register643 // bank.644 const RegisterBank *RB =645 RBI->getRegBank(MI.getOperand(1).getReg(), *MRI, *TRI);646 // We can assume every instruction above this one has a selected register647 // bank.648 assert(RB && "Expected source register to have a register bank?");649 LLVM_DEBUG(dbgs() << "... Hint always uses source's register bank.\n");650 MRI->setRegBank(MI.getOperand(0).getReg(), *RB);651 return true;652 }653 654 // Remember the repairing placement for all the operands.655 SmallVector<RepairingPlacement, 4> RepairPts;656 657 const RegisterBankInfo::InstructionMapping *BestMapping;658 if (OptMode == RegBankSelect::Mode::Fast) {659 BestMapping = &RBI->getInstrMapping(MI);660 MappingCost DefaultCost = computeMapping(MI, *BestMapping, RepairPts);661 (void)DefaultCost;662 if (DefaultCost == MappingCost::ImpossibleCost())663 return false;664 } else {665 RegisterBankInfo::InstructionMappings PossibleMappings =666 RBI->getInstrPossibleMappings(MI);667 if (PossibleMappings.empty())668 return false;669 BestMapping = &findBestMapping(MI, PossibleMappings, RepairPts);670 }671 // Make sure the mapping is valid for MI.672 assert(BestMapping->verify(MI) && "Invalid instruction mapping");673 674 LLVM_DEBUG(dbgs() << "Best Mapping: " << *BestMapping << '\n');675 676 // After this call, MI may not be valid anymore.677 // Do not use it.678 return applyMapping(MI, *BestMapping, RepairPts);679}680 681bool RegBankSelect::assignRegisterBanks(MachineFunction &MF) {682 // Walk the function and assign register banks to all operands.683 // Use a RPOT to make sure all registers are assigned before we choose684 // the best mapping of the current instruction.685 ReversePostOrderTraversal<MachineFunction*> RPOT(&MF);686 for (MachineBasicBlock *MBB : RPOT) {687 // Set a sensible insertion point so that subsequent calls to688 // MIRBuilder.689 MIRBuilder.setMBB(*MBB);690 SmallVector<MachineInstr *> WorkList(691 make_pointer_range(reverse(MBB->instrs())));692 693 while (!WorkList.empty()) {694 MachineInstr &MI = *WorkList.pop_back_val();695 696 // Ignore target-specific post-isel instructions: they should use proper697 // regclasses.698 if (isTargetSpecificOpcode(MI.getOpcode()) && !MI.isPreISelOpcode())699 continue;700 701 // Ignore inline asm instructions: they should use physical702 // registers/regclasses703 if (MI.isInlineAsm())704 continue;705 706 // Ignore IMPLICIT_DEF which must have a regclass.707 if (MI.isImplicitDef())708 continue;709 710 if (!assignInstr(MI)) {711 reportGISelFailure(MF, *TPC, *MORE, "gisel-regbankselect",712 "unable to map instruction", MI);713 return false;714 }715 }716 }717 718 return true;719}720 721bool RegBankSelect::checkFunctionIsLegal(MachineFunction &MF) const {722#ifndef NDEBUG723 if (!DisableGISelLegalityCheck) {724 if (const MachineInstr *MI = machineFunctionIsIllegal(MF)) {725 reportGISelFailure(MF, *TPC, *MORE, "gisel-regbankselect",726 "instruction is not legal", *MI);727 return false;728 }729 }730#endif731 return true;732}733 734bool RegBankSelect::runOnMachineFunction(MachineFunction &MF) {735 // If the ISel pipeline failed, do not bother running that pass.736 if (MF.getProperties().hasFailedISel())737 return false;738 739 LLVM_DEBUG(dbgs() << "Assign register banks for: " << MF.getName() << '\n');740 const Function &F = MF.getFunction();741 Mode SaveOptMode = OptMode;742 if (F.hasOptNone())743 OptMode = Mode::Fast;744 init(MF);745 746#ifndef NDEBUG747 if (!checkFunctionIsLegal(MF))748 return false;749#endif750 751 assignRegisterBanks(MF);752 753 OptMode = SaveOptMode;754 return false;755}756 757//------------------------------------------------------------------------------758// Helper Classes Implementation759//------------------------------------------------------------------------------760RegBankSelect::RepairingPlacement::RepairingPlacement(761 MachineInstr &MI, unsigned OpIdx, const TargetRegisterInfo &TRI, Pass &P,762 RepairingPlacement::RepairingKind Kind)763 // Default is, we are going to insert code to repair OpIdx.764 : Kind(Kind), OpIdx(OpIdx),765 CanMaterialize(Kind != RepairingKind::Impossible), P(P) {766 const MachineOperand &MO = MI.getOperand(OpIdx);767 assert(MO.isReg() && "Trying to repair a non-reg operand");768 769 if (Kind != RepairingKind::Insert)770 return;771 772 // Repairings for definitions happen after MI, uses happen before.773 bool Before = !MO.isDef();774 775 // Check if we are done with MI.776 if (!MI.isPHI() && !MI.isTerminator()) {777 addInsertPoint(MI, Before);778 // We are done with the initialization.779 return;780 }781 782 // Now, look for the special cases.783 if (MI.isPHI()) {784 // - PHI must be the first instructions:785 // * Before, we have to split the related incoming edge.786 // * After, move the insertion point past the last phi.787 if (!Before) {788 MachineBasicBlock::iterator It = MI.getParent()->getFirstNonPHI();789 if (It != MI.getParent()->end())790 addInsertPoint(*It, /*Before*/ true);791 else792 addInsertPoint(*(--It), /*Before*/ false);793 return;794 }795 // We repair a use of a phi, we may need to split the related edge.796 MachineBasicBlock &Pred = *MI.getOperand(OpIdx + 1).getMBB();797 // Check if we can move the insertion point prior to the798 // terminators of the predecessor.799 Register Reg = MO.getReg();800 MachineBasicBlock::iterator It = Pred.getLastNonDebugInstr();801 for (auto Begin = Pred.begin(); It != Begin && It->isTerminator(); --It)802 if (It->modifiesRegister(Reg, &TRI)) {803 // We cannot hoist the repairing code in the predecessor.804 // Split the edge.805 addInsertPoint(Pred, *MI.getParent());806 return;807 }808 // At this point, we can insert in Pred.809 810 // - If It is invalid, Pred is empty and we can insert in Pred811 // wherever we want.812 // - If It is valid, It is the first non-terminator, insert after It.813 if (It == Pred.end())814 addInsertPoint(Pred, /*Beginning*/ false);815 else816 addInsertPoint(*It, /*Before*/ false);817 } else {818 // - Terminators must be the last instructions:819 // * Before, move the insert point before the first terminator.820 // * After, we have to split the outcoming edges.821 if (Before) {822 // Check whether Reg is defined by any terminator.823 MachineBasicBlock::reverse_iterator It = MI;824 auto REnd = MI.getParent()->rend();825 826 for (; It != REnd && It->isTerminator(); ++It) {827 assert(!It->modifiesRegister(MO.getReg(), &TRI) &&828 "copy insertion in middle of terminators not handled");829 }830 831 if (It == REnd) {832 addInsertPoint(*MI.getParent()->begin(), true);833 return;834 }835 836 // We are sure to be right before the first terminator.837 addInsertPoint(*It, /*Before*/ false);838 return;839 }840 // Make sure Reg is not redefined by other terminators, otherwise841 // we do not know how to split.842 for (MachineBasicBlock::iterator It = MI, End = MI.getParent()->end();843 ++It != End;)844 // The machine verifier should reject this kind of code.845 assert(It->modifiesRegister(MO.getReg(), &TRI) &&846 "Do not know where to split");847 // Split each outcoming edges.848 MachineBasicBlock &Src = *MI.getParent();849 for (auto &Succ : Src.successors())850 addInsertPoint(Src, Succ);851 }852}853 854void RegBankSelect::RepairingPlacement::addInsertPoint(MachineInstr &MI,855 bool Before) {856 addInsertPoint(*new InstrInsertPoint(MI, Before));857}858 859void RegBankSelect::RepairingPlacement::addInsertPoint(MachineBasicBlock &MBB,860 bool Beginning) {861 addInsertPoint(*new MBBInsertPoint(MBB, Beginning));862}863 864void RegBankSelect::RepairingPlacement::addInsertPoint(MachineBasicBlock &Src,865 MachineBasicBlock &Dst) {866 addInsertPoint(*new EdgeInsertPoint(Src, Dst, P));867}868 869void RegBankSelect::RepairingPlacement::addInsertPoint(870 RegBankSelect::InsertPoint &Point) {871 CanMaterialize &= Point.canMaterialize();872 HasSplit |= Point.isSplit();873 InsertPoints.emplace_back(&Point);874}875 876RegBankSelect::InstrInsertPoint::InstrInsertPoint(MachineInstr &Instr,877 bool Before)878 : Instr(Instr), Before(Before) {879 // Since we do not support splitting, we do not need to update880 // liveness and such, so do not do anything with P.881 assert((!Before || !Instr.isPHI()) &&882 "Splitting before phis requires more points");883 assert((!Before || !Instr.getNextNode() || !Instr.getNextNode()->isPHI()) &&884 "Splitting between phis does not make sense");885}886 887void RegBankSelect::InstrInsertPoint::materialize() {888 if (isSplit()) {889 // Slice and return the beginning of the new block.890 // If we need to split between the terminators, we theoritically891 // need to know where the first and second set of terminators end892 // to update the successors properly.893 // Now, in pratice, we should have a maximum of 2 branch894 // instructions; one conditional and one unconditional. Therefore895 // we know how to update the successor by looking at the target of896 // the unconditional branch.897 // If we end up splitting at some point, then, we should update898 // the liveness information and such. I.e., we would need to899 // access P here.900 // The machine verifier should actually make sure such cases901 // cannot happen.902 llvm_unreachable("Not yet implemented");903 }904 // Otherwise the insertion point is just the current or next905 // instruction depending on Before. I.e., there is nothing to do906 // here.907}908 909bool RegBankSelect::InstrInsertPoint::isSplit() const {910 // If the insertion point is after a terminator, we need to split.911 if (!Before)912 return Instr.isTerminator();913 // If we insert before an instruction that is after a terminator,914 // we are still after a terminator.915 return Instr.getPrevNode() && Instr.getPrevNode()->isTerminator();916}917 918uint64_t RegBankSelect::InstrInsertPoint::frequency(const Pass &P) const {919 // Even if we need to split, because we insert between terminators,920 // this split has actually the same frequency as the instruction.921 const auto *MBFIWrapper =922 P.getAnalysisIfAvailable<MachineBlockFrequencyInfoWrapperPass>();923 if (!MBFIWrapper)924 return 1;925 return MBFIWrapper->getMBFI().getBlockFreq(Instr.getParent()).getFrequency();926}927 928uint64_t RegBankSelect::MBBInsertPoint::frequency(const Pass &P) const {929 const auto *MBFIWrapper =930 P.getAnalysisIfAvailable<MachineBlockFrequencyInfoWrapperPass>();931 if (!MBFIWrapper)932 return 1;933 return MBFIWrapper->getMBFI().getBlockFreq(&MBB).getFrequency();934}935 936void RegBankSelect::EdgeInsertPoint::materialize() {937 // If we end up repairing twice at the same place before materializing the938 // insertion point, we may think we have to split an edge twice.939 // We should have a factory for the insert point such that identical points940 // are the same instance.941 assert(Src.isSuccessor(DstOrSplit) && DstOrSplit->isPredecessor(&Src) &&942 "This point has already been split");943 MachineBasicBlock *NewBB = Src.SplitCriticalEdge(DstOrSplit, P);944 assert(NewBB && "Invalid call to materialize");945 // We reuse the destination block to hold the information of the new block.946 DstOrSplit = NewBB;947}948 949uint64_t RegBankSelect::EdgeInsertPoint::frequency(const Pass &P) const {950 const auto *MBFIWrapper =951 P.getAnalysisIfAvailable<MachineBlockFrequencyInfoWrapperPass>();952 if (!MBFIWrapper)953 return 1;954 const auto *MBFI = &MBFIWrapper->getMBFI();955 if (WasMaterialized)956 return MBFI->getBlockFreq(DstOrSplit).getFrequency();957 958 auto *MBPIWrapper =959 P.getAnalysisIfAvailable<MachineBranchProbabilityInfoWrapperPass>();960 const MachineBranchProbabilityInfo *MBPI =961 MBPIWrapper ? &MBPIWrapper->getMBPI() : nullptr;962 if (!MBPI)963 return 1;964 // The basic block will be on the edge.965 return (MBFI->getBlockFreq(&Src) * MBPI->getEdgeProbability(&Src, DstOrSplit))966 .getFrequency();967}968 969bool RegBankSelect::EdgeInsertPoint::canMaterialize() const {970 // If this is not a critical edge, we should not have used this insert971 // point. Indeed, either the successor or the predecessor should972 // have do.973 assert(Src.succ_size() > 1 && DstOrSplit->pred_size() > 1 &&974 "Edge is not critical");975 return Src.canSplitCriticalEdge(DstOrSplit);976}977 978RegBankSelect::MappingCost::MappingCost(BlockFrequency LocalFreq)979 : LocalFreq(LocalFreq.getFrequency()) {}980 981bool RegBankSelect::MappingCost::addLocalCost(uint64_t Cost) {982 // Check if this overflows.983 if (LocalCost + Cost < LocalCost) {984 saturate();985 return true;986 }987 LocalCost += Cost;988 return isSaturated();989}990 991bool RegBankSelect::MappingCost::addNonLocalCost(uint64_t Cost) {992 // Check if this overflows.993 if (NonLocalCost + Cost < NonLocalCost) {994 saturate();995 return true;996 }997 NonLocalCost += Cost;998 return isSaturated();999}1000 1001bool RegBankSelect::MappingCost::isSaturated() const {1002 return LocalCost == UINT64_MAX - 1 && NonLocalCost == UINT64_MAX &&1003 LocalFreq == UINT64_MAX;1004}1005 1006void RegBankSelect::MappingCost::saturate() {1007 *this = ImpossibleCost();1008 --LocalCost;1009}1010 1011RegBankSelect::MappingCost RegBankSelect::MappingCost::ImpossibleCost() {1012 return MappingCost(UINT64_MAX, UINT64_MAX, UINT64_MAX);1013}1014 1015bool RegBankSelect::MappingCost::operator<(const MappingCost &Cost) const {1016 // Sort out the easy cases.1017 if (*this == Cost)1018 return false;1019 // If one is impossible to realize the other is cheaper unless it is1020 // impossible as well.1021 if ((*this == ImpossibleCost()) || (Cost == ImpossibleCost()))1022 return (*this == ImpossibleCost()) < (Cost == ImpossibleCost());1023 // If one is saturated the other is cheaper, unless it is saturated1024 // as well.1025 if (isSaturated() || Cost.isSaturated())1026 return isSaturated() < Cost.isSaturated();1027 // At this point we know both costs hold sensible values.1028 1029 // If both values have a different base frequency, there is no much1030 // we can do but to scale everything.1031 // However, if they have the same base frequency we can avoid making1032 // complicated computation.1033 uint64_t ThisLocalAdjust;1034 uint64_t OtherLocalAdjust;1035 if (LLVM_LIKELY(LocalFreq == Cost.LocalFreq)) {1036 1037 // At this point, we know the local costs are comparable.1038 // Do the case that do not involve potential overflow first.1039 if (NonLocalCost == Cost.NonLocalCost)1040 // Since the non-local costs do not discriminate on the result,1041 // just compare the local costs.1042 return LocalCost < Cost.LocalCost;1043 1044 // The base costs are comparable so we may only keep the relative1045 // value to increase our chances of avoiding overflows.1046 ThisLocalAdjust = 0;1047 OtherLocalAdjust = 0;1048 if (LocalCost < Cost.LocalCost)1049 OtherLocalAdjust = Cost.LocalCost - LocalCost;1050 else1051 ThisLocalAdjust = LocalCost - Cost.LocalCost;1052 } else {1053 ThisLocalAdjust = LocalCost;1054 OtherLocalAdjust = Cost.LocalCost;1055 }1056 1057 // The non-local costs are comparable, just keep the relative value.1058 uint64_t ThisNonLocalAdjust = 0;1059 uint64_t OtherNonLocalAdjust = 0;1060 if (NonLocalCost < Cost.NonLocalCost)1061 OtherNonLocalAdjust = Cost.NonLocalCost - NonLocalCost;1062 else1063 ThisNonLocalAdjust = NonLocalCost - Cost.NonLocalCost;1064 // Scale everything to make them comparable.1065 uint64_t ThisScaledCost = ThisLocalAdjust * LocalFreq;1066 // Check for overflow on that operation.1067 bool ThisOverflows = ThisLocalAdjust && (ThisScaledCost < ThisLocalAdjust ||1068 ThisScaledCost < LocalFreq);1069 uint64_t OtherScaledCost = OtherLocalAdjust * Cost.LocalFreq;1070 // Check for overflow on the last operation.1071 bool OtherOverflows =1072 OtherLocalAdjust &&1073 (OtherScaledCost < OtherLocalAdjust || OtherScaledCost < Cost.LocalFreq);1074 // Add the non-local costs.1075 ThisOverflows |= ThisNonLocalAdjust &&1076 ThisScaledCost + ThisNonLocalAdjust < ThisNonLocalAdjust;1077 ThisScaledCost += ThisNonLocalAdjust;1078 OtherOverflows |= OtherNonLocalAdjust &&1079 OtherScaledCost + OtherNonLocalAdjust < OtherNonLocalAdjust;1080 OtherScaledCost += OtherNonLocalAdjust;1081 // If both overflows, we cannot compare without additional1082 // precision, e.g., APInt. Just give up on that case.1083 if (ThisOverflows && OtherOverflows)1084 return false;1085 // If one overflows but not the other, we can still compare.1086 if (ThisOverflows || OtherOverflows)1087 return ThisOverflows < OtherOverflows;1088 // Otherwise, just compare the values.1089 return ThisScaledCost < OtherScaledCost;1090}1091 1092bool RegBankSelect::MappingCost::operator==(const MappingCost &Cost) const {1093 return LocalCost == Cost.LocalCost && NonLocalCost == Cost.NonLocalCost &&1094 LocalFreq == Cost.LocalFreq;1095}1096 1097#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)1098LLVM_DUMP_METHOD void RegBankSelect::MappingCost::dump() const {1099 print(dbgs());1100 dbgs() << '\n';1101}1102#endif1103 1104void RegBankSelect::MappingCost::print(raw_ostream &OS) const {1105 if (*this == ImpossibleCost()) {1106 OS << "impossible";1107 return;1108 }1109 if (isSaturated()) {1110 OS << "saturated";1111 return;1112 }1113 OS << LocalFreq << " * " << LocalCost << " + " << NonLocalCost;1114}1115