diff options
Diffstat (limited to 'lib/CodeGen/GlobalISel')
| -rw-r--r-- | lib/CodeGen/GlobalISel/CMakeLists.txt | 27 | ||||
| -rw-r--r-- | lib/CodeGen/GlobalISel/GlobalISel.cpp | 30 | ||||
| -rw-r--r-- | lib/CodeGen/GlobalISel/IRTranslator.cpp | 164 | ||||
| -rw-r--r-- | lib/CodeGen/GlobalISel/LLVMBuild.txt | 22 | ||||
| -rw-r--r-- | lib/CodeGen/GlobalISel/MachineIRBuilder.cpp | 104 | ||||
| -rw-r--r-- | lib/CodeGen/GlobalISel/RegBankSelect.cpp | 897 | ||||
| -rw-r--r-- | lib/CodeGen/GlobalISel/RegisterBank.cpp | 107 | ||||
| -rw-r--r-- | lib/CodeGen/GlobalISel/RegisterBankInfo.cpp | 663 |
8 files changed, 2014 insertions, 0 deletions
diff --git a/lib/CodeGen/GlobalISel/CMakeLists.txt b/lib/CodeGen/GlobalISel/CMakeLists.txt new file mode 100644 index 0000000000000..e3e81ae5c4b15 --- /dev/null +++ b/lib/CodeGen/GlobalISel/CMakeLists.txt @@ -0,0 +1,27 @@ +# List of all GlobalISel files. +set(GLOBAL_ISEL_FILES + IRTranslator.cpp + MachineIRBuilder.cpp + RegBankSelect.cpp + RegisterBank.cpp + RegisterBankInfo.cpp + ) + +# Add GlobalISel files to the dependencies if the user wants to build it. +if(LLVM_BUILD_GLOBAL_ISEL) + set(GLOBAL_ISEL_BUILD_FILES ${GLOBAL_ISEL_FILES}) +else() + set(GLOBAL_ISEL_BUILD_FILES"") + set(LLVM_OPTIONAL_SOURCES LLVMGlobalISel ${GLOBAL_ISEL_FILES}) +endif() + + +# In LLVMBuild.txt files, it is not possible to mark a dependency to a +# library as optional. So instead, generate an empty library if we did +# not ask for it. +add_llvm_library(LLVMGlobalISel + ${GLOBAL_ISEL_BUILD_FILES} + GlobalISel.cpp + ) + +add_dependencies(LLVMGlobalISel intrinsics_gen) diff --git a/lib/CodeGen/GlobalISel/GlobalISel.cpp b/lib/CodeGen/GlobalISel/GlobalISel.cpp new file mode 100644 index 0000000000000..231e5ac82becd --- /dev/null +++ b/lib/CodeGen/GlobalISel/GlobalISel.cpp @@ -0,0 +1,30 @@ +//===-- llvm/CodeGen/GlobalISel/GlobalIsel.cpp --- GlobalISel ----*- C++ -*-==// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +/// \file +// This file implements the common initialization routines for the +// GlobalISel library. +//===----------------------------------------------------------------------===// + +#include "llvm/InitializePasses.h" +#include "llvm/PassRegistry.h" + +using namespace llvm; + +#ifndef LLVM_BUILD_GLOBAL_ISEL + +void llvm::initializeGlobalISel(PassRegistry &Registry) { +} + +#else + +void llvm::initializeGlobalISel(PassRegistry &Registry) { + initializeIRTranslatorPass(Registry); + initializeRegBankSelectPass(Registry); +} +#endif // LLVM_BUILD_GLOBAL_ISEL diff --git a/lib/CodeGen/GlobalISel/IRTranslator.cpp b/lib/CodeGen/GlobalISel/IRTranslator.cpp new file mode 100644 index 0000000000000..b8a960cfac760 --- /dev/null +++ b/lib/CodeGen/GlobalISel/IRTranslator.cpp @@ -0,0 +1,164 @@ +//===-- llvm/CodeGen/GlobalISel/IRTranslator.cpp - IRTranslator --*- C++ -*-==// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +/// \file +/// This file implements the IRTranslator class. +//===----------------------------------------------------------------------===// + +#include "llvm/CodeGen/GlobalISel/IRTranslator.h" + +#include "llvm/ADT/SmallVector.h" +#include "llvm/CodeGen/GlobalISel/CallLowering.h" +#include "llvm/CodeGen/MachineFunction.h" +#include "llvm/CodeGen/MachineRegisterInfo.h" +#include "llvm/IR/Constant.h" +#include "llvm/IR/Function.h" +#include "llvm/IR/Type.h" +#include "llvm/IR/Value.h" +#include "llvm/Target/TargetLowering.h" + +#define DEBUG_TYPE "irtranslator" + +using namespace llvm; + +char IRTranslator::ID = 0; +INITIALIZE_PASS(IRTranslator, "irtranslator", "IRTranslator LLVM IR -> MI", + false, false); + +IRTranslator::IRTranslator() : MachineFunctionPass(ID), MRI(nullptr) { + initializeIRTranslatorPass(*PassRegistry::getPassRegistry()); +} + +unsigned IRTranslator::getOrCreateVReg(const Value &Val) { + unsigned &ValReg = ValToVReg[&Val]; + // Check if this is the first time we see Val. + if (!ValReg) { + // Fill ValRegsSequence with the sequence of registers + // we need to concat together to produce the value. + assert(Val.getType()->isSized() && + "Don't know how to create an empty vreg"); + assert(!Val.getType()->isAggregateType() && "Not yet implemented"); + unsigned Size = Val.getType()->getPrimitiveSizeInBits(); + unsigned VReg = MRI->createGenericVirtualRegister(Size); + ValReg = VReg; + assert(!isa<Constant>(Val) && "Not yet implemented"); + } + return ValReg; +} + +MachineBasicBlock &IRTranslator::getOrCreateBB(const BasicBlock &BB) { + MachineBasicBlock *&MBB = BBToMBB[&BB]; + if (!MBB) { + MachineFunction &MF = MIRBuilder.getMF(); + MBB = MF.CreateMachineBasicBlock(); + MF.push_back(MBB); + } + return *MBB; +} + +bool IRTranslator::translateBinaryOp(unsigned Opcode, const Instruction &Inst) { + // Get or create a virtual register for each value. + // Unless the value is a Constant => loadimm cst? + // or inline constant each time? + // Creation of a virtual register needs to have a size. + unsigned Op0 = getOrCreateVReg(*Inst.getOperand(0)); + unsigned Op1 = getOrCreateVReg(*Inst.getOperand(1)); + unsigned Res = getOrCreateVReg(Inst); + MIRBuilder.buildInstr(Opcode, Inst.getType(), Res, Op0, Op1); + return true; +} + +bool IRTranslator::translateReturn(const Instruction &Inst) { + assert(isa<ReturnInst>(Inst) && "Return expected"); + const Value *Ret = cast<ReturnInst>(Inst).getReturnValue(); + // The target may mess up with the insertion point, but + // this is not important as a return is the last instruction + // of the block anyway. + return CLI->lowerReturn(MIRBuilder, Ret, !Ret ? 0 : getOrCreateVReg(*Ret)); +} + +bool IRTranslator::translateBr(const Instruction &Inst) { + assert(isa<BranchInst>(Inst) && "Branch expected"); + const BranchInst &BrInst = *cast<BranchInst>(&Inst); + if (BrInst.isUnconditional()) { + const BasicBlock &BrTgt = *cast<BasicBlock>(BrInst.getOperand(0)); + MachineBasicBlock &TgtBB = getOrCreateBB(BrTgt); + MIRBuilder.buildInstr(TargetOpcode::G_BR, BrTgt.getType(), TgtBB); + } else { + assert(0 && "Not yet implemented"); + } + // Link successors. + MachineBasicBlock &CurBB = MIRBuilder.getMBB(); + for (const BasicBlock *Succ : BrInst.successors()) + CurBB.addSuccessor(&getOrCreateBB(*Succ)); + return true; +} + +bool IRTranslator::translate(const Instruction &Inst) { + MIRBuilder.setDebugLoc(Inst.getDebugLoc()); + switch(Inst.getOpcode()) { + case Instruction::Add: + return translateBinaryOp(TargetOpcode::G_ADD, Inst); + case Instruction::Or: + return translateBinaryOp(TargetOpcode::G_OR, Inst); + case Instruction::Br: + return translateBr(Inst); + case Instruction::Ret: + return translateReturn(Inst); + + default: + llvm_unreachable("Opcode not supported"); + } +} + + +void IRTranslator::finalize() { + // Release the memory used by the different maps we + // needed during the translation. + ValToVReg.clear(); + Constants.clear(); +} + +bool IRTranslator::runOnMachineFunction(MachineFunction &MF) { + const Function &F = *MF.getFunction(); + if (F.empty()) + return false; + CLI = MF.getSubtarget().getCallLowering(); + MIRBuilder.setMF(MF); + MRI = &MF.getRegInfo(); + // Setup the arguments. + MachineBasicBlock &MBB = getOrCreateBB(F.front()); + MIRBuilder.setMBB(MBB); + SmallVector<unsigned, 8> VRegArgs; + for (const Argument &Arg: F.args()) + VRegArgs.push_back(getOrCreateVReg(Arg)); + bool Succeeded = + CLI->lowerFormalArguments(MIRBuilder, F.getArgumentList(), VRegArgs); + if (!Succeeded) + report_fatal_error("Unable to lower arguments"); + + for (const BasicBlock &BB: F) { + MachineBasicBlock &MBB = getOrCreateBB(BB); + // Set the insertion point of all the following translations to + // the end of this basic block. + MIRBuilder.setMBB(MBB); + for (const Instruction &Inst: BB) { + bool Succeeded = translate(Inst); + if (!Succeeded) { + DEBUG(dbgs() << "Cannot translate: " << Inst << '\n'); + report_fatal_error("Unable to translate instruction"); + } + } + } + + // Now that the MachineFrameInfo has been configured, no further changes to + // the reserved registers are possible. + MRI->freezeReservedRegs(MF); + + return false; +} diff --git a/lib/CodeGen/GlobalISel/LLVMBuild.txt b/lib/CodeGen/GlobalISel/LLVMBuild.txt new file mode 100644 index 0000000000000..a2daa3b222a6d --- /dev/null +++ b/lib/CodeGen/GlobalISel/LLVMBuild.txt @@ -0,0 +1,22 @@ +;===- ./lib/CodeGen/GlobalISel/LLVMBuild.txt -----------------*- Conf -*--===; +; +; The LLVM Compiler Infrastructure +; +; This file is distributed under the University of Illinois Open Source +; License. See LICENSE.TXT for details. +; +;===------------------------------------------------------------------------===; +; +; This is an LLVMBuild description file for the components in this subdirectory. +; +; For more information on the LLVMBuild system, please see: +; +; http://llvm.org/docs/LLVMBuild.html +; +;===------------------------------------------------------------------------===; + +[component_0] +type = Library +name = GlobalISel +parent = CodeGen +required_libraries = Analysis CodeGen Core MC Support Target TransformUtils diff --git a/lib/CodeGen/GlobalISel/MachineIRBuilder.cpp b/lib/CodeGen/GlobalISel/MachineIRBuilder.cpp new file mode 100644 index 0000000000000..2f19bcf1e68b9 --- /dev/null +++ b/lib/CodeGen/GlobalISel/MachineIRBuilder.cpp @@ -0,0 +1,104 @@ +//===-- llvm/CodeGen/GlobalISel/MachineIRBuilder.cpp - MIBuilder--*- C++ -*-==// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +/// \file +/// This file implements the MachineIRBuidler class. +//===----------------------------------------------------------------------===// +#include "llvm/CodeGen/GlobalISel/MachineIRBuilder.h" + +#include "llvm/CodeGen/MachineFunction.h" +#include "llvm/CodeGen/MachineInstr.h" +#include "llvm/CodeGen/MachineInstrBuilder.h" +#include "llvm/Target/TargetInstrInfo.h" +#include "llvm/Target/TargetOpcodes.h" +#include "llvm/Target/TargetSubtargetInfo.h" + +using namespace llvm; + +void MachineIRBuilder::setMF(MachineFunction &MF) { + this->MF = &MF; + this->MBB = nullptr; + this->TII = MF.getSubtarget().getInstrInfo(); + this->DL = DebugLoc(); + this->MI = nullptr; +} + +void MachineIRBuilder::setMBB(MachineBasicBlock &MBB, bool Beginning) { + this->MBB = &MBB; + Before = Beginning; + assert(&getMF() == MBB.getParent() && + "Basic block is in a different function"); +} + +void MachineIRBuilder::setInstr(MachineInstr &MI, bool Before) { + assert(MI.getParent() && "Instruction is not part of a basic block"); + setMBB(*MI.getParent()); + this->MI = &MI; + this->Before = Before; +} + +MachineBasicBlock::iterator MachineIRBuilder::getInsertPt() { + if (MI) { + if (Before) + return MI; + if (!MI->getNextNode()) + return getMBB().end(); + return MI->getNextNode(); + } + return Before ? getMBB().begin() : getMBB().end(); +} + +//------------------------------------------------------------------------------ +// Build instruction variants. +//------------------------------------------------------------------------------ +MachineInstr *MachineIRBuilder::buildInstr(unsigned Opcode, Type *Ty) { + MachineInstr *NewMI = BuildMI(getMF(), DL, getTII().get(Opcode)); + if (Ty) { + assert(isPreISelGenericOpcode(Opcode) && + "Only generic instruction can have a type"); + NewMI->setType(Ty); + } else + assert(!isPreISelGenericOpcode(Opcode) && + "Generic instruction must have a type"); + getMBB().insert(getInsertPt(), NewMI); + return NewMI; +} + +MachineInstr *MachineIRBuilder::buildInstr(unsigned Opcode, unsigned Res, + unsigned Op0, unsigned Op1) { + return buildInstr(Opcode, nullptr, Res, Op0, Op1); +} + +MachineInstr *MachineIRBuilder::buildInstr(unsigned Opcode, Type *Ty, + unsigned Res, unsigned Op0, + unsigned Op1) { + MachineInstr *NewMI = buildInstr(Opcode, Ty); + MachineInstrBuilder(getMF(), NewMI) + .addReg(Res, RegState::Define) + .addReg(Op0) + .addReg(Op1); + return NewMI; +} + +MachineInstr *MachineIRBuilder::buildInstr(unsigned Opcode, unsigned Res, + unsigned Op0) { + MachineInstr *NewMI = buildInstr(Opcode, nullptr); + MachineInstrBuilder(getMF(), NewMI).addReg(Res, RegState::Define).addReg(Op0); + return NewMI; +} + +MachineInstr *MachineIRBuilder::buildInstr(unsigned Opcode) { + return buildInstr(Opcode, nullptr); +} + +MachineInstr *MachineIRBuilder::buildInstr(unsigned Opcode, Type *Ty, + MachineBasicBlock &BB) { + MachineInstr *NewMI = buildInstr(Opcode, Ty); + MachineInstrBuilder(getMF(), NewMI).addMBB(&BB); + return NewMI; +} diff --git a/lib/CodeGen/GlobalISel/RegBankSelect.cpp b/lib/CodeGen/GlobalISel/RegBankSelect.cpp new file mode 100644 index 0000000000000..419e270c91275 --- /dev/null +++ b/lib/CodeGen/GlobalISel/RegBankSelect.cpp @@ -0,0 +1,897 @@ +//===- llvm/CodeGen/GlobalISel/RegBankSelect.cpp - RegBankSelect -*- C++ -*-==// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +/// \file +/// This file implements the RegBankSelect class. +//===----------------------------------------------------------------------===// + +#include "llvm/CodeGen/GlobalISel/RegBankSelect.h" +#include "llvm/ADT/PostOrderIterator.h" +#include "llvm/CodeGen/GlobalISel/RegisterBank.h" +#include "llvm/CodeGen/MachineBlockFrequencyInfo.h" +#include "llvm/CodeGen/MachineBranchProbabilityInfo.h" +#include "llvm/CodeGen/MachineRegisterInfo.h" +#include "llvm/IR/Function.h" +#include "llvm/Support/BlockFrequency.h" +#include "llvm/Support/CommandLine.h" +#include "llvm/Support/Debug.h" +#include "llvm/Target/TargetSubtargetInfo.h" + +#define DEBUG_TYPE "regbankselect" + +using namespace llvm; + +static cl::opt<RegBankSelect::Mode> RegBankSelectMode( + cl::desc("Mode of the RegBankSelect pass"), cl::Hidden, cl::Optional, + cl::values(clEnumValN(RegBankSelect::Mode::Fast, "regbankselect-fast", + "Run the Fast mode (default mapping)"), + clEnumValN(RegBankSelect::Mode::Greedy, "regbankselect-greedy", + "Use the Greedy mode (best local mapping)"), + clEnumValEnd)); + +char RegBankSelect::ID = 0; +INITIALIZE_PASS_BEGIN(RegBankSelect, "regbankselect", + "Assign register bank of generic virtual registers", + false, false); +INITIALIZE_PASS_DEPENDENCY(MachineBlockFrequencyInfo) +INITIALIZE_PASS_DEPENDENCY(MachineBranchProbabilityInfo) +INITIALIZE_PASS_END(RegBankSelect, "regbankselect", + "Assign register bank of generic virtual registers", false, + false); + +RegBankSelect::RegBankSelect(Mode RunningMode) + : MachineFunctionPass(ID), RBI(nullptr), MRI(nullptr), TRI(nullptr), + MBFI(nullptr), MBPI(nullptr), OptMode(RunningMode) { + initializeRegBankSelectPass(*PassRegistry::getPassRegistry()); + if (RegBankSelectMode.getNumOccurrences() != 0) { + OptMode = RegBankSelectMode; + if (RegBankSelectMode != RunningMode) + DEBUG(dbgs() << "RegBankSelect mode overrided by command line\n"); + } +} + +void RegBankSelect::init(MachineFunction &MF) { + RBI = MF.getSubtarget().getRegBankInfo(); + assert(RBI && "Cannot work without RegisterBankInfo"); + MRI = &MF.getRegInfo(); + TRI = MF.getSubtarget().getRegisterInfo(); + if (OptMode != Mode::Fast) { + MBFI = &getAnalysis<MachineBlockFrequencyInfo>(); + MBPI = &getAnalysis<MachineBranchProbabilityInfo>(); + } else { + MBFI = nullptr; + MBPI = nullptr; + } + MIRBuilder.setMF(MF); +} + +void RegBankSelect::getAnalysisUsage(AnalysisUsage &AU) const { + if (OptMode != Mode::Fast) { + // We could preserve the information from these two analysis but + // the APIs do not allow to do so yet. + AU.addRequired<MachineBlockFrequencyInfo>(); + AU.addRequired<MachineBranchProbabilityInfo>(); + } + MachineFunctionPass::getAnalysisUsage(AU); +} + +bool RegBankSelect::assignmentMatch( + unsigned Reg, const RegisterBankInfo::ValueMapping &ValMapping, + bool &OnlyAssign) const { + // By default we assume we will have to repair something. + OnlyAssign = false; + // Each part of a break down needs to end up in a different register. + // In other word, Reg assignement does not match. + if (ValMapping.BreakDown.size() > 1) + return false; + + const RegisterBank *CurRegBank = RBI->getRegBank(Reg, *MRI, *TRI); + const RegisterBank *DesiredRegBrank = ValMapping.BreakDown[0].RegBank; + // Reg is free of assignment, a simple assignment will make the + // register bank to match. + OnlyAssign = CurRegBank == nullptr; + DEBUG(dbgs() << "Does assignment already match: "; + if (CurRegBank) dbgs() << *CurRegBank; else dbgs() << "none"; + dbgs() << " against "; + assert(DesiredRegBrank && "The mapping must be valid"); + dbgs() << *DesiredRegBrank << '\n';); + return CurRegBank == DesiredRegBrank; +} + +void RegBankSelect::repairReg( + MachineOperand &MO, const RegisterBankInfo::ValueMapping &ValMapping, + RegBankSelect::RepairingPlacement &RepairPt, + const iterator_range<SmallVectorImpl<unsigned>::const_iterator> &NewVRegs) { + assert(ValMapping.BreakDown.size() == 1 && "Not yet implemented"); + // An empty range of new register means no repairing. + assert(NewVRegs.begin() != NewVRegs.end() && "We should not have to repair"); + + // Assume we are repairing a use and thus, the original reg will be + // the source of the repairing. + unsigned Src = MO.getReg(); + unsigned Dst = *NewVRegs.begin(); + + // If we repair a definition, swap the source and destination for + // the repairing. + if (MO.isDef()) + std::swap(Src, Dst); + + assert((RepairPt.getNumInsertPoints() == 1 || + TargetRegisterInfo::isPhysicalRegister(Dst)) && + "We are about to create several defs for Dst"); + + // Build the instruction used to repair, then clone it at the right places. + MachineInstr *MI = MIRBuilder.buildInstr(TargetOpcode::COPY, Dst, Src); + MI->removeFromParent(); + DEBUG(dbgs() << "Copy: " << PrintReg(Src) << " to: " << PrintReg(Dst) + << '\n'); + // TODO: + // Check if MI is legal. if not, we need to legalize all the + // instructions we are going to insert. + std::unique_ptr<MachineInstr *[]> NewInstrs( + new MachineInstr *[RepairPt.getNumInsertPoints()]); + bool IsFirst = true; + unsigned Idx = 0; + for (const std::unique_ptr<InsertPoint> &InsertPt : RepairPt) { + MachineInstr *CurMI; + if (IsFirst) + CurMI = MI; + else + CurMI = MIRBuilder.getMF().CloneMachineInstr(MI); + InsertPt->insert(*CurMI); + NewInstrs[Idx++] = CurMI; + IsFirst = false; + } + // TODO: + // Legalize NewInstrs if need be. +} + +uint64_t RegBankSelect::getRepairCost( + const MachineOperand &MO, + const RegisterBankInfo::ValueMapping &ValMapping) const { + assert(MO.isReg() && "We should only repair register operand"); + assert(!ValMapping.BreakDown.empty() && "Nothing to map??"); + + bool IsSameNumOfValues = ValMapping.BreakDown.size() == 1; + const RegisterBank *CurRegBank = RBI->getRegBank(MO.getReg(), *MRI, *TRI); + // If MO does not have a register bank, we should have just been + // able to set one unless we have to break the value down. + assert((!IsSameNumOfValues || CurRegBank) && "We should not have to repair"); + // Def: Val <- NewDefs + // Same number of values: copy + // Different number: Val = build_sequence Defs1, Defs2, ... + // Use: NewSources <- Val. + // Same number of values: copy. + // Different number: Src1, Src2, ... = + // extract_value Val, Src1Begin, Src1Len, Src2Begin, Src2Len, ... + // We should remember that this value is available somewhere else to + // coalesce the value. + + if (IsSameNumOfValues) { + const RegisterBank *DesiredRegBrank = ValMapping.BreakDown[0].RegBank; + // If we repair a definition, swap the source and destination for + // the repairing. + if (MO.isDef()) + std::swap(CurRegBank, DesiredRegBrank); + // TODO: It may be possible to actually avoid the copy. + // If we repair something where the source is defined by a copy + // and the source of that copy is on the right bank, we can reuse + // it for free. + // E.g., + // RegToRepair<BankA> = copy AlternativeSrc<BankB> + // = op RegToRepair<BankA> + // We can simply propagate AlternativeSrc instead of copying RegToRepair + // into a new virtual register. + // We would also need to propagate this information in the + // repairing placement. + unsigned Cost = + RBI->copyCost(*DesiredRegBrank, *CurRegBank, + RegisterBankInfo::getSizeInBits(MO.getReg(), *MRI, *TRI)); + // TODO: use a dedicated constant for ImpossibleCost. + if (Cost != UINT_MAX) + return Cost; + assert(false && "Legalization not available yet"); + // Return the legalization cost of that repairing. + } + assert(false && "Complex repairing not implemented yet"); + return 1; +} + +RegisterBankInfo::InstructionMapping &RegBankSelect::findBestMapping( + MachineInstr &MI, RegisterBankInfo::InstructionMappings &PossibleMappings, + SmallVectorImpl<RepairingPlacement> &RepairPts) { + + RegisterBankInfo::InstructionMapping *BestMapping = nullptr; + MappingCost Cost = MappingCost::ImpossibleCost(); + SmallVector<RepairingPlacement, 4> LocalRepairPts; + for (RegisterBankInfo::InstructionMapping &CurMapping : PossibleMappings) { + MappingCost CurCost = computeMapping(MI, CurMapping, LocalRepairPts, &Cost); + if (CurCost < Cost) { + Cost = CurCost; + BestMapping = &CurMapping; + RepairPts.clear(); + for (RepairingPlacement &RepairPt : LocalRepairPts) + RepairPts.emplace_back(std::move(RepairPt)); + } + } + assert(BestMapping && "No suitable mapping for instruction"); + return *BestMapping; +} + +void RegBankSelect::tryAvoidingSplit( + RegBankSelect::RepairingPlacement &RepairPt, const MachineOperand &MO, + const RegisterBankInfo::ValueMapping &ValMapping) const { + const MachineInstr &MI = *MO.getParent(); + assert(RepairPt.hasSplit() && "We should not have to adjust for split"); + // Splitting should only occur for PHIs or between terminators, + // because we only do local repairing. + assert((MI.isPHI() || MI.isTerminator()) && "Why do we split?"); + + assert(&MI.getOperand(RepairPt.getOpIdx()) == &MO && + "Repairing placement does not match operand"); + + // If we need splitting for phis, that means it is because we + // could not find an insertion point before the terminators of + // the predecessor block for this argument. In other words, + // the input value is defined by one of the terminators. + assert((!MI.isPHI() || !MO.isDef()) && "Need split for phi def?"); + + // We split to repair the use of a phi or a terminator. + if (!MO.isDef()) { + if (MI.isTerminator()) { + assert(&MI != &(*MI.getParent()->getFirstTerminator()) && + "Need to split for the first terminator?!"); + } else { + // For the PHI case, the split may not be actually required. + // In the copy case, a phi is already a copy on the incoming edge, + // therefore there is no need to split. + if (ValMapping.BreakDown.size() == 1) + // This is a already a copy, there is nothing to do. + RepairPt.switchTo(RepairingPlacement::RepairingKind::Reassign); + } + return; + } + + // At this point, we need to repair a defintion of a terminator. + + // Technically we need to fix the def of MI on all outgoing + // edges of MI to keep the repairing local. In other words, we + // will create several definitions of the same register. This + // does not work for SSA unless that definition is a physical + // register. + // However, there are other cases where we can get away with + // that while still keeping the repairing local. + assert(MI.isTerminator() && MO.isDef() && + "This code is for the def of a terminator"); + + // Since we use RPO traversal, if we need to repair a definition + // this means this definition could be: + // 1. Used by PHIs (i.e., this VReg has been visited as part of the + // uses of a phi.), or + // 2. Part of a target specific instruction (i.e., the target applied + // some register class constraints when creating the instruction.) + // If the constraints come for #2, the target said that another mapping + // is supported so we may just drop them. Indeed, if we do not change + // the number of registers holding that value, the uses will get fixed + // when we get to them. + // Uses in PHIs may have already been proceeded though. + // If the constraints come for #1, then, those are weak constraints and + // no actual uses may rely on them. However, the problem remains mainly + // the same as for #2. If the value stays in one register, we could + // just switch the register bank of the definition, but we would need to + // account for a repairing cost for each phi we silently change. + // + // In any case, if the value needs to be broken down into several + // registers, the repairing is not local anymore as we need to patch + // every uses to rebuild the value in just one register. + // + // To summarize: + // - If the value is in a physical register, we can do the split and + // fix locally. + // Otherwise if the value is in a virtual register: + // - If the value remains in one register, we do not have to split + // just switching the register bank would do, but we need to account + // in the repairing cost all the phi we changed. + // - If the value spans several registers, then we cannot do a local + // repairing. + + // Check if this is a physical or virtual register. + unsigned Reg = MO.getReg(); + if (TargetRegisterInfo::isPhysicalRegister(Reg)) { + // We are going to split every outgoing edges. + // Check that this is possible. + // FIXME: The machine representation is currently broken + // since it also several terminators in one basic block. + // Because of that we would technically need a way to get + // the targets of just one terminator to know which edges + // we have to split. + // Assert that we do not hit the ill-formed representation. + + // If there are other terminators before that one, some of + // the outgoing edges may not be dominated by this definition. + assert(&MI == &(*MI.getParent()->getFirstTerminator()) && + "Do not know which outgoing edges are relevant"); + const MachineInstr *Next = MI.getNextNode(); + assert((!Next || Next->isUnconditionalBranch()) && + "Do not know where each terminator ends up"); + if (Next) + // If the next terminator uses Reg, this means we have + // to split right after MI and thus we need a way to ask + // which outgoing edges are affected. + assert(!Next->readsRegister(Reg) && "Need to split between terminators"); + // We will split all the edges and repair there. + } else { + // This is a virtual register defined by a terminator. + if (ValMapping.BreakDown.size() == 1) { + // There is nothing to repair, but we may actually lie on + // the repairing cost because of the PHIs already proceeded + // as already stated. + // Though the code will be correct. + assert(0 && "Repairing cost may not be accurate"); + } else { + // We need to do non-local repairing. Basically, patch all + // the uses (i.e., phis) that we already proceeded. + // For now, just say this mapping is not possible. + RepairPt.switchTo(RepairingPlacement::RepairingKind::Impossible); + } + } +} + +RegBankSelect::MappingCost RegBankSelect::computeMapping( + MachineInstr &MI, const RegisterBankInfo::InstructionMapping &InstrMapping, + SmallVectorImpl<RepairingPlacement> &RepairPts, + const RegBankSelect::MappingCost *BestCost) { + assert((MBFI || !BestCost) && "Costs comparison require MBFI"); + + // If mapped with InstrMapping, MI will have the recorded cost. + MappingCost Cost(MBFI ? MBFI->getBlockFreq(MI.getParent()) : 1); + bool Saturated = Cost.addLocalCost(InstrMapping.getCost()); + assert(!Saturated && "Possible mapping saturated the cost"); + DEBUG(dbgs() << "Evaluating mapping cost for: " << MI); + DEBUG(dbgs() << "With: " << InstrMapping << '\n'); + RepairPts.clear(); + if (BestCost && Cost > *BestCost) + return Cost; + + // Moreover, to realize this mapping, the register bank of each operand must + // match this mapping. In other words, we may need to locally reassign the + // register banks. Account for that repairing cost as well. + // In this context, local means in the surrounding of MI. + for (unsigned OpIdx = 0, EndOpIdx = MI.getNumOperands(); OpIdx != EndOpIdx; + ++OpIdx) { + const MachineOperand &MO = MI.getOperand(OpIdx); + if (!MO.isReg()) + continue; + unsigned Reg = MO.getReg(); + if (!Reg) + continue; + DEBUG(dbgs() << "Opd" << OpIdx); + const RegisterBankInfo::ValueMapping &ValMapping = + InstrMapping.getOperandMapping(OpIdx); + // If Reg is already properly mapped, this is free. + bool Assign; + if (assignmentMatch(Reg, ValMapping, Assign)) { + DEBUG(dbgs() << " is free (match).\n"); + continue; + } + if (Assign) { + DEBUG(dbgs() << " is free (simple assignment).\n"); + RepairPts.emplace_back(RepairingPlacement(MI, OpIdx, *TRI, *this, + RepairingPlacement::Reassign)); + continue; + } + + // Find the insertion point for the repairing code. + RepairPts.emplace_back( + RepairingPlacement(MI, OpIdx, *TRI, *this, RepairingPlacement::Insert)); + RepairingPlacement &RepairPt = RepairPts.back(); + + // If we need to split a basic block to materialize this insertion point, + // we may give a higher cost to this mapping. + // Nevertheless, we may get away with the split, so try that first. + if (RepairPt.hasSplit()) + tryAvoidingSplit(RepairPt, MO, ValMapping); + + // Check that the materialization of the repairing is possible. + if (!RepairPt.canMaterialize()) + return MappingCost::ImpossibleCost(); + + // Account for the split cost and repair cost. + // Unless the cost is already saturated or we do not care about the cost. + if (!BestCost || Saturated) + continue; + + // To get accurate information we need MBFI and MBPI. + // Thus, if we end up here this information should be here. + assert(MBFI && MBPI && "Cost computation requires MBFI and MBPI"); + + // FIXME: We will have to rework the repairing cost model. + // The repairing cost depends on the register bank that MO has. + // However, when we break down the value into different values, + // MO may not have a register bank while still needing repairing. + // For the fast mode, we don't compute the cost so that is fine, + // but still for the repairing code, we will have to make a choice. + // For the greedy mode, we should choose greedily what is the best + // choice based on the next use of MO. + + // Sums up the repairing cost of MO at each insertion point. + uint64_t RepairCost = getRepairCost(MO, ValMapping); + // Bias used for splitting: 5%. + const uint64_t PercentageForBias = 5; + uint64_t Bias = (RepairCost * PercentageForBias + 99) / 100; + // We should not need more than a couple of instructions to repair + // an assignment. In other words, the computation should not + // overflow because the repairing cost is free of basic block + // frequency. + assert(((RepairCost < RepairCost * PercentageForBias) && + (RepairCost * PercentageForBias < + RepairCost * PercentageForBias + 99)) && + "Repairing involves more than a billion of instructions?!"); + for (const std::unique_ptr<InsertPoint> &InsertPt : RepairPt) { + assert(InsertPt->canMaterialize() && "We should not have made it here"); + // We will applied some basic block frequency and those uses uint64_t. + if (!InsertPt->isSplit()) + Saturated = Cost.addLocalCost(RepairCost); + else { + uint64_t CostForInsertPt = RepairCost; + // Again we shouldn't overflow here givent that + // CostForInsertPt is frequency free at this point. + assert(CostForInsertPt + Bias > CostForInsertPt && + "Repairing + split bias overflows"); + CostForInsertPt += Bias; + uint64_t PtCost = InsertPt->frequency(*this) * CostForInsertPt; + // Check if we just overflowed. + if ((Saturated = PtCost < CostForInsertPt)) + Cost.saturate(); + else + Saturated = Cost.addNonLocalCost(PtCost); + } + + // Stop looking into what it takes to repair, this is already + // too expensive. + if (BestCost && Cost > *BestCost) + return Cost; + + // No need to accumulate more cost information. + // We need to still gather the repairing information though. + if (Saturated) + break; + } + } + return Cost; +} + +void RegBankSelect::applyMapping( + MachineInstr &MI, const RegisterBankInfo::InstructionMapping &InstrMapping, + SmallVectorImpl<RegBankSelect::RepairingPlacement> &RepairPts) { + // OpdMapper will hold all the information needed for the rewritting. + RegisterBankInfo::OperandsMapper OpdMapper(MI, InstrMapping, *MRI); + + // First, place the repairing code. + for (RepairingPlacement &RepairPt : RepairPts) { + assert(RepairPt.canMaterialize() && + RepairPt.getKind() != RepairingPlacement::Impossible && + "This mapping is impossible"); + assert(RepairPt.getKind() != RepairingPlacement::None && + "This should not make its way in the list"); + unsigned OpIdx = RepairPt.getOpIdx(); + MachineOperand &MO = MI.getOperand(OpIdx); + const RegisterBankInfo::ValueMapping &ValMapping = + InstrMapping.getOperandMapping(OpIdx); + unsigned BreakDownSize = ValMapping.BreakDown.size(); + (void)BreakDownSize; + unsigned Reg = MO.getReg(); + + switch (RepairPt.getKind()) { + case RepairingPlacement::Reassign: + assert(BreakDownSize == 1 && + "Reassignment should only be for simple mapping"); + MRI->setRegBank(Reg, *ValMapping.BreakDown[0].RegBank); + break; + case RepairingPlacement::Insert: + OpdMapper.createVRegs(OpIdx); + repairReg(MO, ValMapping, RepairPt, OpdMapper.getVRegs(OpIdx)); + break; + default: + llvm_unreachable("Other kind should not happen"); + } + } + // Second, rewrite the instruction. + DEBUG(dbgs() << "Actual mapping of the operands: " << OpdMapper << '\n'); + RBI->applyMapping(OpdMapper); +} + +void RegBankSelect::assignInstr(MachineInstr &MI) { + DEBUG(dbgs() << "Assign: " << MI); + // Remember the repairing placement for all the operands. + SmallVector<RepairingPlacement, 4> RepairPts; + + RegisterBankInfo::InstructionMapping BestMapping; + if (OptMode == RegBankSelect::Mode::Fast) { + BestMapping = RBI->getInstrMapping(MI); + MappingCost DefaultCost = computeMapping(MI, BestMapping, RepairPts); + (void)DefaultCost; + assert(DefaultCost != MappingCost::ImpossibleCost() && + "Default mapping is not suited"); + } else { + RegisterBankInfo::InstructionMappings PossibleMappings = + RBI->getInstrPossibleMappings(MI); + assert(!PossibleMappings.empty() && + "Do not know how to map this instruction"); + BestMapping = std::move(findBestMapping(MI, PossibleMappings, RepairPts)); + } + // Make sure the mapping is valid for MI. + assert(BestMapping.verify(MI) && "Invalid instruction mapping"); + + DEBUG(dbgs() << "Mapping: " << BestMapping << '\n'); + + // After this call, MI may not be valid anymore. + // Do not use it. + applyMapping(MI, BestMapping, RepairPts); +} + +bool RegBankSelect::runOnMachineFunction(MachineFunction &MF) { + DEBUG(dbgs() << "Assign register banks for: " << MF.getName() << '\n'); + const Function *F = MF.getFunction(); + Mode SaveOptMode = OptMode; + if (F->hasFnAttribute(Attribute::OptimizeNone)) + OptMode = Mode::Fast; + init(MF); + // Walk the function and assign register banks to all operands. + // Use a RPOT to make sure all registers are assigned before we choose + // the best mapping of the current instruction. + ReversePostOrderTraversal<MachineFunction*> RPOT(&MF); + for (MachineBasicBlock *MBB : RPOT) { + // Set a sensible insertion point so that subsequent calls to + // MIRBuilder. + MIRBuilder.setMBB(*MBB); + for (MachineBasicBlock::iterator MII = MBB->begin(), End = MBB->end(); + MII != End;) { + // MI might be invalidated by the assignment, so move the + // iterator before hand. + assignInstr(*MII++); + } + } + OptMode = SaveOptMode; + return false; +} + +//------------------------------------------------------------------------------ +// Helper Classes Implementation +//------------------------------------------------------------------------------ +RegBankSelect::RepairingPlacement::RepairingPlacement( + MachineInstr &MI, unsigned OpIdx, const TargetRegisterInfo &TRI, Pass &P, + RepairingPlacement::RepairingKind Kind) + // Default is, we are going to insert code to repair OpIdx. + : Kind(Kind), + OpIdx(OpIdx), + CanMaterialize(Kind != RepairingKind::Impossible), + HasSplit(false), + P(P) { + const MachineOperand &MO = MI.getOperand(OpIdx); + assert(MO.isReg() && "Trying to repair a non-reg operand"); + + if (Kind != RepairingKind::Insert) + return; + + // Repairings for definitions happen after MI, uses happen before. + bool Before = !MO.isDef(); + + // Check if we are done with MI. + if (!MI.isPHI() && !MI.isTerminator()) { + addInsertPoint(MI, Before); + // We are done with the initialization. + return; + } + + // Now, look for the special cases. + if (MI.isPHI()) { + // - PHI must be the first instructions: + // * Before, we have to split the related incoming edge. + // * After, move the insertion point past the last phi. + if (!Before) { + MachineBasicBlock::iterator It = MI.getParent()->getFirstNonPHI(); + if (It != MI.getParent()->end()) + addInsertPoint(*It, /*Before*/ true); + else + addInsertPoint(*(--It), /*Before*/ false); + return; + } + // We repair a use of a phi, we may need to split the related edge. + MachineBasicBlock &Pred = *MI.getOperand(OpIdx + 1).getMBB(); + // Check if we can move the insertion point prior to the + // terminators of the predecessor. + unsigned Reg = MO.getReg(); + MachineBasicBlock::iterator It = Pred.getLastNonDebugInstr(); + for (auto Begin = Pred.begin(); It != Begin && It->isTerminator(); --It) + if (It->modifiesRegister(Reg, &TRI)) { + // We cannot hoist the repairing code in the predecessor. + // Split the edge. + addInsertPoint(Pred, *MI.getParent()); + return; + } + // At this point, we can insert in Pred. + + // - If It is invalid, Pred is empty and we can insert in Pred + // wherever we want. + // - If It is valid, It is the first non-terminator, insert after It. + if (It == Pred.end()) + addInsertPoint(Pred, /*Beginning*/ false); + else + addInsertPoint(*It, /*Before*/ false); + } else { + // - Terminators must be the last instructions: + // * Before, move the insert point before the first terminator. + // * After, we have to split the outcoming edges. + unsigned Reg = MO.getReg(); + if (Before) { + // Check whether Reg is defined by any terminator. + MachineBasicBlock::iterator It = MI; + for (auto Begin = MI.getParent()->begin(); + --It != Begin && It->isTerminator();) + if (It->modifiesRegister(Reg, &TRI)) { + // Insert the repairing code right after the definition. + addInsertPoint(*It, /*Before*/ false); + return; + } + addInsertPoint(*It, /*Before*/ true); + return; + } + // Make sure Reg is not redefined by other terminators, otherwise + // we do not know how to split. + for (MachineBasicBlock::iterator It = MI, End = MI.getParent()->end(); + ++It != End;) + // The machine verifier should reject this kind of code. + assert(It->modifiesRegister(Reg, &TRI) && "Do not know where to split"); + // Split each outcoming edges. + MachineBasicBlock &Src = *MI.getParent(); + for (auto &Succ : Src.successors()) + addInsertPoint(Src, Succ); + } +} + +void RegBankSelect::RepairingPlacement::addInsertPoint(MachineInstr &MI, + bool Before) { + addInsertPoint(*new InstrInsertPoint(MI, Before)); +} + +void RegBankSelect::RepairingPlacement::addInsertPoint(MachineBasicBlock &MBB, + bool Beginning) { + addInsertPoint(*new MBBInsertPoint(MBB, Beginning)); +} + +void RegBankSelect::RepairingPlacement::addInsertPoint(MachineBasicBlock &Src, + MachineBasicBlock &Dst) { + addInsertPoint(*new EdgeInsertPoint(Src, Dst, P)); +} + +void RegBankSelect::RepairingPlacement::addInsertPoint( + RegBankSelect::InsertPoint &Point) { + CanMaterialize &= Point.canMaterialize(); + HasSplit |= Point.isSplit(); + InsertPoints.emplace_back(&Point); +} + +RegBankSelect::InstrInsertPoint::InstrInsertPoint(MachineInstr &Instr, + bool Before) + : InsertPoint(), Instr(Instr), Before(Before) { + // Since we do not support splitting, we do not need to update + // liveness and such, so do not do anything with P. + assert((!Before || !Instr.isPHI()) && + "Splitting before phis requires more points"); + assert((!Before || !Instr.getNextNode() || !Instr.getNextNode()->isPHI()) && + "Splitting between phis does not make sense"); +} + +void RegBankSelect::InstrInsertPoint::materialize() { + if (isSplit()) { + // Slice and return the beginning of the new block. + // If we need to split between the terminators, we theoritically + // need to know where the first and second set of terminators end + // to update the successors properly. + // Now, in pratice, we should have a maximum of 2 branch + // instructions; one conditional and one unconditional. Therefore + // we know how to update the successor by looking at the target of + // the unconditional branch. + // If we end up splitting at some point, then, we should update + // the liveness information and such. I.e., we would need to + // access P here. + // The machine verifier should actually make sure such cases + // cannot happen. + llvm_unreachable("Not yet implemented"); + } + // Otherwise the insertion point is just the current or next + // instruction depending on Before. I.e., there is nothing to do + // here. +} + +bool RegBankSelect::InstrInsertPoint::isSplit() const { + // If the insertion point is after a terminator, we need to split. + if (!Before) + return Instr.isTerminator(); + // If we insert before an instruction that is after a terminator, + // we are still after a terminator. + return Instr.getPrevNode() && Instr.getPrevNode()->isTerminator(); +} + +uint64_t RegBankSelect::InstrInsertPoint::frequency(const Pass &P) const { + // Even if we need to split, because we insert between terminators, + // this split has actually the same frequency as the instruction. + const MachineBlockFrequencyInfo *MBFI = + P.getAnalysisIfAvailable<MachineBlockFrequencyInfo>(); + if (!MBFI) + return 1; + return MBFI->getBlockFreq(Instr.getParent()).getFrequency(); +} + +uint64_t RegBankSelect::MBBInsertPoint::frequency(const Pass &P) const { + const MachineBlockFrequencyInfo *MBFI = + P.getAnalysisIfAvailable<MachineBlockFrequencyInfo>(); + if (!MBFI) + return 1; + return MBFI->getBlockFreq(&MBB).getFrequency(); +} + +void RegBankSelect::EdgeInsertPoint::materialize() { + // If we end up repairing twice at the same place before materializing the + // insertion point, we may think we have to split an edge twice. + // We should have a factory for the insert point such that identical points + // are the same instance. + assert(Src.isSuccessor(DstOrSplit) && DstOrSplit->isPredecessor(&Src) && + "This point has already been split"); + MachineBasicBlock *NewBB = Src.SplitCriticalEdge(DstOrSplit, P); + assert(NewBB && "Invalid call to materialize"); + // We reuse the destination block to hold the information of the new block. + DstOrSplit = NewBB; +} + +uint64_t RegBankSelect::EdgeInsertPoint::frequency(const Pass &P) const { + const MachineBlockFrequencyInfo *MBFI = + P.getAnalysisIfAvailable<MachineBlockFrequencyInfo>(); + if (!MBFI) + return 1; + if (WasMaterialized) + return MBFI->getBlockFreq(DstOrSplit).getFrequency(); + + const MachineBranchProbabilityInfo *MBPI = + P.getAnalysisIfAvailable<MachineBranchProbabilityInfo>(); + if (!MBPI) + return 1; + // The basic block will be on the edge. + return (MBFI->getBlockFreq(&Src) * MBPI->getEdgeProbability(&Src, DstOrSplit)) + .getFrequency(); +} + +bool RegBankSelect::EdgeInsertPoint::canMaterialize() const { + // If this is not a critical edge, we should not have used this insert + // point. Indeed, either the successor or the predecessor should + // have do. + assert(Src.succ_size() > 1 && DstOrSplit->pred_size() > 1 && + "Edge is not critical"); + return Src.canSplitCriticalEdge(DstOrSplit); +} + +RegBankSelect::MappingCost::MappingCost(const BlockFrequency &LocalFreq) + : LocalCost(0), NonLocalCost(0), LocalFreq(LocalFreq.getFrequency()) {} + +bool RegBankSelect::MappingCost::addLocalCost(uint64_t Cost) { + // Check if this overflows. + if (LocalCost + Cost < LocalCost) { + saturate(); + return true; + } + LocalCost += Cost; + return isSaturated(); +} + +bool RegBankSelect::MappingCost::addNonLocalCost(uint64_t Cost) { + // Check if this overflows. + if (NonLocalCost + Cost < NonLocalCost) { + saturate(); + return true; + } + NonLocalCost += Cost; + return isSaturated(); +} + +bool RegBankSelect::MappingCost::isSaturated() const { + return LocalCost == UINT64_MAX - 1 && NonLocalCost == UINT64_MAX && + LocalFreq == UINT64_MAX; +} + +void RegBankSelect::MappingCost::saturate() { + *this = ImpossibleCost(); + --LocalCost; +} + +RegBankSelect::MappingCost RegBankSelect::MappingCost::ImpossibleCost() { + return MappingCost(UINT64_MAX, UINT64_MAX, UINT64_MAX); +} + +bool RegBankSelect::MappingCost::operator<(const MappingCost &Cost) const { + // Sort out the easy cases. + if (*this == Cost) + return false; + // If one is impossible to realize the other is cheaper unless it is + // impossible as well. + if ((*this == ImpossibleCost()) || (Cost == ImpossibleCost())) + return (*this == ImpossibleCost()) < (Cost == ImpossibleCost()); + // If one is saturated the other is cheaper, unless it is saturated + // as well. + if (isSaturated() || Cost.isSaturated()) + return isSaturated() < Cost.isSaturated(); + // At this point we know both costs hold sensible values. + + // If both values have a different base frequency, there is no much + // we can do but to scale everything. + // However, if they have the same base frequency we can avoid making + // complicated computation. + uint64_t ThisLocalAdjust; + uint64_t OtherLocalAdjust; + if (LLVM_LIKELY(LocalFreq == Cost.LocalFreq)) { + + // At this point, we know the local costs are comparable. + // Do the case that do not involve potential overflow first. + if (NonLocalCost == Cost.NonLocalCost) + // Since the non-local costs do not discriminate on the result, + // just compare the local costs. + return LocalCost < Cost.LocalCost; + + // The base costs are comparable so we may only keep the relative + // value to increase our chances of avoiding overflows. + ThisLocalAdjust = 0; + OtherLocalAdjust = 0; + if (LocalCost < Cost.LocalCost) + OtherLocalAdjust = Cost.LocalCost - LocalCost; + else + ThisLocalAdjust = LocalCost - Cost.LocalCost; + + } else { + ThisLocalAdjust = LocalCost; + OtherLocalAdjust = Cost.LocalCost; + } + + // The non-local costs are comparable, just keep the relative value. + uint64_t ThisNonLocalAdjust = 0; + uint64_t OtherNonLocalAdjust = 0; + if (NonLocalCost < Cost.NonLocalCost) + OtherNonLocalAdjust = Cost.NonLocalCost - NonLocalCost; + else + ThisNonLocalAdjust = NonLocalCost - Cost.NonLocalCost; + // Scale everything to make them comparable. + uint64_t ThisScaledCost = ThisLocalAdjust * LocalFreq; + // Check for overflow on that operation. + bool ThisOverflows = ThisLocalAdjust && (ThisScaledCost < ThisLocalAdjust || + ThisScaledCost < LocalFreq); + uint64_t OtherScaledCost = OtherLocalAdjust * Cost.LocalFreq; + // Check for overflow on the last operation. + bool OtherOverflows = + OtherLocalAdjust && + (OtherScaledCost < OtherLocalAdjust || OtherScaledCost < Cost.LocalFreq); + // Add the non-local costs. + ThisOverflows |= ThisNonLocalAdjust && + ThisScaledCost + ThisNonLocalAdjust < ThisNonLocalAdjust; + ThisScaledCost += ThisNonLocalAdjust; + OtherOverflows |= OtherNonLocalAdjust && + OtherScaledCost + OtherNonLocalAdjust < OtherNonLocalAdjust; + OtherScaledCost += OtherNonLocalAdjust; + // If both overflows, we cannot compare without additional + // precision, e.g., APInt. Just give up on that case. + if (ThisOverflows && OtherOverflows) + return false; + // If one overflows but not the other, we can still compare. + if (ThisOverflows || OtherOverflows) + return ThisOverflows < OtherOverflows; + // Otherwise, just compare the values. + return ThisScaledCost < OtherScaledCost; +} + +bool RegBankSelect::MappingCost::operator==(const MappingCost &Cost) const { + return LocalCost == Cost.LocalCost && NonLocalCost == Cost.NonLocalCost && + LocalFreq == Cost.LocalFreq; +} diff --git a/lib/CodeGen/GlobalISel/RegisterBank.cpp b/lib/CodeGen/GlobalISel/RegisterBank.cpp new file mode 100644 index 0000000000000..a911225b5af5c --- /dev/null +++ b/lib/CodeGen/GlobalISel/RegisterBank.cpp @@ -0,0 +1,107 @@ +//===- llvm/CodeGen/GlobalISel/RegisterBank.cpp - Register Bank --*- C++ -*-==// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +/// \file +/// This file implements the RegisterBank class. +//===----------------------------------------------------------------------===// + +#include "llvm/CodeGen/GlobalISel/RegisterBank.h" +#include "llvm/Target/TargetRegisterInfo.h" + +#define DEBUG_TYPE "registerbank" + +using namespace llvm; + +const unsigned RegisterBank::InvalidID = UINT_MAX; + +RegisterBank::RegisterBank() : ID(InvalidID), Name(nullptr), Size(0) {} + +bool RegisterBank::verify(const TargetRegisterInfo &TRI) const { + assert(isValid() && "Invalid register bank"); + assert(ContainedRegClasses.size() == TRI.getNumRegClasses() && + "TRI does not match the initialization process?"); + for (unsigned RCId = 0, End = TRI.getNumRegClasses(); RCId != End; ++RCId) { + const TargetRegisterClass &RC = *TRI.getRegClass(RCId); + + if (!covers(RC)) + continue; + // Verify that the register bank covers all the sub classes of the + // classes it covers. + + // Use a different (slow in that case) method than + // RegisterBankInfo to find the subclasses of RC, to make sure + // both agree on the covers. + for (unsigned SubRCId = 0; SubRCId != End; ++SubRCId) { + const TargetRegisterClass &SubRC = *TRI.getRegClass(RCId); + + if (!RC.hasSubClassEq(&SubRC)) + continue; + + // Verify that the Size of the register bank is big enough to cover + // all the register classes it covers. + assert((getSize() >= SubRC.getSize() * 8) && + "Size is not big enough for all the subclasses!"); + assert(covers(SubRC) && "Not all subclasses are covered"); + } + } + return true; +} + +bool RegisterBank::covers(const TargetRegisterClass &RC) const { + assert(isValid() && "RB hasn't been initialized yet"); + return ContainedRegClasses.test(RC.getID()); +} + +bool RegisterBank::isValid() const { + return ID != InvalidID && Name != nullptr && Size != 0 && + // A register bank that does not cover anything is useless. + !ContainedRegClasses.empty(); +} + +bool RegisterBank::operator==(const RegisterBank &OtherRB) const { + // There must be only one instance of a given register bank alive + // for the whole compilation. + // The RegisterBankInfo is supposed to enforce that. + assert((OtherRB.getID() != getID() || &OtherRB == this) && + "ID does not uniquely identify a RegisterBank"); + return &OtherRB == this; +} + +void RegisterBank::dump(const TargetRegisterInfo *TRI) const { + print(dbgs(), /* IsForDebug */ true, TRI); +} + +void RegisterBank::print(raw_ostream &OS, bool IsForDebug, + const TargetRegisterInfo *TRI) const { + OS << getName(); + if (!IsForDebug) + return; + OS << "(ID:" << getID() << ", Size:" << getSize() << ")\n" + << "isValid:" << isValid() << '\n' + << "Number of Covered register classes: " << ContainedRegClasses.count() + << '\n'; + // Print all the subclasses if we can. + // This register classes may not be properly initialized yet. + if (!TRI || ContainedRegClasses.empty()) + return; + assert(ContainedRegClasses.size() == TRI->getNumRegClasses() && + "TRI does not match the initialization process?"); + bool IsFirst = true; + OS << "Covered register classes:\n"; + for (unsigned RCId = 0, End = TRI->getNumRegClasses(); RCId != End; ++RCId) { + const TargetRegisterClass &RC = *TRI->getRegClass(RCId); + + if (!covers(RC)) + continue; + + if (!IsFirst) + OS << ", "; + OS << TRI->getRegClassName(&RC); + IsFirst = false; + } +} diff --git a/lib/CodeGen/GlobalISel/RegisterBankInfo.cpp b/lib/CodeGen/GlobalISel/RegisterBankInfo.cpp new file mode 100644 index 0000000000000..ef8e4f6d68518 --- /dev/null +++ b/lib/CodeGen/GlobalISel/RegisterBankInfo.cpp @@ -0,0 +1,663 @@ +//===- llvm/CodeGen/GlobalISel/RegisterBankInfo.cpp --------------*- C++ -*-==// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +/// \file +/// This file implements the RegisterBankInfo class. +//===----------------------------------------------------------------------===// + +#include "llvm/CodeGen/GlobalISel/RegisterBankInfo.h" +#include "llvm/ADT/SmallString.h" +#include "llvm/ADT/SmallVector.h" +#include "llvm/ADT/iterator_range.h" +#include "llvm/CodeGen/GlobalISel/RegisterBank.h" +#include "llvm/CodeGen/MachineBasicBlock.h" +#include "llvm/CodeGen/MachineFunction.h" +#include "llvm/CodeGen/MachineRegisterInfo.h" +#include "llvm/IR/Type.h" +#include "llvm/Support/Debug.h" +#include "llvm/Support/raw_ostream.h" +#include "llvm/Target/TargetInstrInfo.h" +#include "llvm/Target/TargetOpcodes.h" +#include "llvm/Target/TargetRegisterInfo.h" +#include "llvm/Target/TargetSubtargetInfo.h" + +#include <algorithm> // For std::max. + +#define DEBUG_TYPE "registerbankinfo" + +using namespace llvm; + +const unsigned RegisterBankInfo::DefaultMappingID = UINT_MAX; +const unsigned RegisterBankInfo::InvalidMappingID = UINT_MAX - 1; + +//------------------------------------------------------------------------------ +// RegisterBankInfo implementation. +//------------------------------------------------------------------------------ +RegisterBankInfo::RegisterBankInfo(unsigned NumRegBanks) + : NumRegBanks(NumRegBanks) { + RegBanks.reset(new RegisterBank[NumRegBanks]); +} + +bool RegisterBankInfo::verify(const TargetRegisterInfo &TRI) const { + DEBUG(for (unsigned Idx = 0, End = getNumRegBanks(); Idx != End; ++Idx) { + const RegisterBank &RegBank = getRegBank(Idx); + assert(Idx == RegBank.getID() && + "ID does not match the index in the array"); + dbgs() << "Verify " << RegBank << '\n'; + assert(RegBank.verify(TRI) && "RegBank is invalid"); + }); + return true; +} + +void RegisterBankInfo::createRegisterBank(unsigned ID, const char *Name) { + DEBUG(dbgs() << "Create register bank: " << ID << " with name \"" << Name + << "\"\n"); + RegisterBank &RegBank = getRegBank(ID); + assert(RegBank.getID() == RegisterBank::InvalidID && + "A register bank should be created only once"); + RegBank.ID = ID; + RegBank.Name = Name; +} + +void RegisterBankInfo::addRegBankCoverage(unsigned ID, unsigned RCId, + const TargetRegisterInfo &TRI, + bool AddTypeMapping) { + RegisterBank &RB = getRegBank(ID); + unsigned NbOfRegClasses = TRI.getNumRegClasses(); + + DEBUG(dbgs() << "Add coverage for: " << RB << '\n'); + + // Check if RB is underconstruction. + if (!RB.isValid()) + RB.ContainedRegClasses.resize(NbOfRegClasses); + else if (RB.covers(*TRI.getRegClass(RCId))) + // If RB already covers this register class, there is nothing + // to do. + return; + + BitVector &Covered = RB.ContainedRegClasses; + SmallVector<unsigned, 8> WorkList; + + WorkList.push_back(RCId); + Covered.set(RCId); + + unsigned &MaxSize = RB.Size; + do { + unsigned RCId = WorkList.pop_back_val(); + + const TargetRegisterClass &CurRC = *TRI.getRegClass(RCId); + + DEBUG(dbgs() << "Examine: " << TRI.getRegClassName(&CurRC) + << "(Size*8: " << (CurRC.getSize() * 8) << ")\n"); + + // Remember the biggest size in bits. + MaxSize = std::max(MaxSize, CurRC.getSize() * 8); + + // If we have been asked to record the type supported by this + // register bank, do it now. + if (AddTypeMapping) + for (MVT::SimpleValueType SVT : + make_range(CurRC.vt_begin(), CurRC.vt_end())) + recordRegBankForType(getRegBank(ID), SVT); + + // Walk through all sub register classes and push them into the worklist. + bool First = true; + for (BitMaskClassIterator It(CurRC.getSubClassMask(), TRI); It.isValid(); + ++It) { + unsigned SubRCId = It.getID(); + if (!Covered.test(SubRCId)) { + if (First) + DEBUG(dbgs() << " Enqueue sub-class: "); + DEBUG(dbgs() << TRI.getRegClassName(TRI.getRegClass(SubRCId)) << ", "); + WorkList.push_back(SubRCId); + // Remember that we saw the sub class. + Covered.set(SubRCId); + First = false; + } + } + if (!First) + DEBUG(dbgs() << '\n'); + + // Push also all the register classes that can be accessed via a + // subreg index, i.e., its subreg-class (which is different than + // its subclass). + // + // Note: It would probably be faster to go the other way around + // and have this method add only super classes, since this + // information is available in a more efficient way. However, it + // feels less natural for the client of this APIs plus we will + // TableGen the whole bitset at some point, so compile time for + // the initialization is not very important. + First = true; + for (unsigned SubRCId = 0; SubRCId < NbOfRegClasses; ++SubRCId) { + if (Covered.test(SubRCId)) + continue; + bool Pushed = false; + const TargetRegisterClass *SubRC = TRI.getRegClass(SubRCId); + for (SuperRegClassIterator SuperRCIt(SubRC, &TRI); SuperRCIt.isValid(); + ++SuperRCIt) { + if (Pushed) + break; + for (BitMaskClassIterator It(SuperRCIt.getMask(), TRI); It.isValid(); + ++It) { + unsigned SuperRCId = It.getID(); + if (SuperRCId == RCId) { + if (First) + DEBUG(dbgs() << " Enqueue subreg-class: "); + DEBUG(dbgs() << TRI.getRegClassName(SubRC) << ", "); + WorkList.push_back(SubRCId); + // Remember that we saw the sub class. + Covered.set(SubRCId); + Pushed = true; + First = false; + break; + } + } + } + } + if (!First) + DEBUG(dbgs() << '\n'); + } while (!WorkList.empty()); +} + +const RegisterBank * +RegisterBankInfo::getRegBank(unsigned Reg, const MachineRegisterInfo &MRI, + const TargetRegisterInfo &TRI) const { + if (TargetRegisterInfo::isPhysicalRegister(Reg)) + return &getRegBankFromRegClass(*TRI.getMinimalPhysRegClass(Reg)); + + assert(Reg && "NoRegister does not have a register bank"); + const RegClassOrRegBank &RegClassOrBank = MRI.getRegClassOrRegBank(Reg); + if (RegClassOrBank.is<const RegisterBank *>()) + return RegClassOrBank.get<const RegisterBank *>(); + const TargetRegisterClass *RC = + RegClassOrBank.get<const TargetRegisterClass *>(); + if (RC) + return &getRegBankFromRegClass(*RC); + return nullptr; +} + +const RegisterBank *RegisterBankInfo::getRegBankFromConstraints( + const MachineInstr &MI, unsigned OpIdx, const TargetInstrInfo &TII, + const TargetRegisterInfo &TRI) const { + // The mapping of the registers may be available via the + // register class constraints. + const TargetRegisterClass *RC = MI.getRegClassConstraint(OpIdx, &TII, &TRI); + + if (!RC) + return nullptr; + + const RegisterBank &RegBank = getRegBankFromRegClass(*RC); + // Sanity check that the target properly implemented getRegBankFromRegClass. + assert(RegBank.covers(*RC) && + "The mapping of the register bank does not make sense"); + return &RegBank; +} + +RegisterBankInfo::InstructionMapping +RegisterBankInfo::getInstrMappingImpl(const MachineInstr &MI) const { + RegisterBankInfo::InstructionMapping Mapping(DefaultMappingID, /*Cost*/ 1, + MI.getNumOperands()); + const MachineFunction &MF = *MI.getParent()->getParent(); + const TargetSubtargetInfo &STI = MF.getSubtarget(); + const TargetRegisterInfo &TRI = *STI.getRegisterInfo(); + const MachineRegisterInfo &MRI = MF.getRegInfo(); + // We may need to query the instruction encoding to guess the mapping. + const TargetInstrInfo &TII = *STI.getInstrInfo(); + + // Before doing anything complicated check if the mapping is not + // directly available. + bool CompleteMapping = true; + // For copies we want to walk over the operands and try to find one + // that has a register bank. + bool isCopyLike = MI.isCopy() || MI.isPHI(); + // Remember the register bank for reuse for copy-like instructions. + const RegisterBank *RegBank = nullptr; + // Remember the size of the register for reuse for copy-like instructions. + unsigned RegSize = 0; + for (unsigned OpIdx = 0, End = MI.getNumOperands(); OpIdx != End; ++OpIdx) { + const MachineOperand &MO = MI.getOperand(OpIdx); + if (!MO.isReg()) + continue; + unsigned Reg = MO.getReg(); + if (!Reg) + continue; + // The register bank of Reg is just a side effect of the current + // excution and in particular, there is no reason to believe this + // is the best default mapping for the current instruction. Keep + // it as an alternative register bank if we cannot figure out + // something. + const RegisterBank *AltRegBank = getRegBank(Reg, MRI, TRI); + // For copy-like instruction, we want to reuse the register bank + // that is already set on Reg, if any, since those instructions do + // not have any constraints. + const RegisterBank *CurRegBank = isCopyLike ? AltRegBank : nullptr; + if (!CurRegBank) { + // If this is a target specific instruction, we can deduce + // the register bank from the encoding constraints. + CurRegBank = getRegBankFromConstraints(MI, OpIdx, TII, TRI); + if (!CurRegBank) { + // Check if we can deduce the register bank from the type of + // the instruction. + Type *MITy = MI.getType(); + if (MITy) + CurRegBank = getRegBankForType( + MVT::getVT(MITy, /*HandleUnknown*/ true).SimpleTy); + if (!CurRegBank) + // Use the current assigned register bank. + // That may not make much sense though. + CurRegBank = AltRegBank; + if (!CurRegBank) { + // All our attempts failed, give up. + CompleteMapping = false; + + if (!isCopyLike) + // MI does not carry enough information to guess the mapping. + return InstructionMapping(); + + // For copies, we want to keep interating to find a register + // bank for the other operands if we did not find one yet. + if (RegBank) + break; + continue; + } + } + } + RegBank = CurRegBank; + RegSize = getSizeInBits(Reg, MRI, TRI); + Mapping.setOperandMapping(OpIdx, RegSize, *CurRegBank); + } + + if (CompleteMapping) + return Mapping; + + assert(isCopyLike && "We should have bailed on non-copies at this point"); + // For copy like instruction, if none of the operand has a register + // bank avialable, there is nothing we can propagate. + if (!RegBank) + return InstructionMapping(); + + // This is a copy-like instruction. + // Propagate RegBank to all operands that do not have a + // mapping yet. + for (unsigned OpIdx = 0, End = MI.getNumOperands(); OpIdx != End; ++OpIdx) { + const MachineOperand &MO = MI.getOperand(OpIdx); + // Don't assign a mapping for non-reg operands. + if (!MO.isReg()) + continue; + + // If a mapping already exists, do not touch it. + if (!static_cast<const InstructionMapping *>(&Mapping) + ->getOperandMapping(OpIdx) + .BreakDown.empty()) + continue; + + Mapping.setOperandMapping(OpIdx, RegSize, *RegBank); + } + return Mapping; +} + +RegisterBankInfo::InstructionMapping +RegisterBankInfo::getInstrMapping(const MachineInstr &MI) const { + RegisterBankInfo::InstructionMapping Mapping = getInstrMappingImpl(MI); + if (Mapping.isValid()) + return Mapping; + llvm_unreachable("The target must implement this"); +} + +RegisterBankInfo::InstructionMappings +RegisterBankInfo::getInstrPossibleMappings(const MachineInstr &MI) const { + InstructionMappings PossibleMappings; + // Put the default mapping first. + PossibleMappings.push_back(getInstrMapping(MI)); + // Then the alternative mapping, if any. + InstructionMappings AltMappings = getInstrAlternativeMappings(MI); + for (InstructionMapping &AltMapping : AltMappings) + PossibleMappings.emplace_back(std::move(AltMapping)); +#ifndef NDEBUG + for (const InstructionMapping &Mapping : PossibleMappings) + assert(Mapping.verify(MI) && "Mapping is invalid"); +#endif + return PossibleMappings; +} + +RegisterBankInfo::InstructionMappings +RegisterBankInfo::getInstrAlternativeMappings(const MachineInstr &MI) const { + // No alternative for MI. + return InstructionMappings(); +} + +void RegisterBankInfo::applyDefaultMapping(const OperandsMapper &OpdMapper) { + MachineInstr &MI = OpdMapper.getMI(); + DEBUG(dbgs() << "Applying default-like mapping\n"); + for (unsigned OpIdx = 0, EndIdx = MI.getNumOperands(); OpIdx != EndIdx; + ++OpIdx) { + DEBUG(dbgs() << "OpIdx " << OpIdx); + MachineOperand &MO = MI.getOperand(OpIdx); + if (!MO.isReg()) { + DEBUG(dbgs() << " is not a register, nothing to be done\n"); + continue; + } + assert( + OpdMapper.getInstrMapping().getOperandMapping(OpIdx).BreakDown.size() == + 1 && + "This mapping is too complex for this function"); + iterator_range<SmallVectorImpl<unsigned>::const_iterator> NewRegs = + OpdMapper.getVRegs(OpIdx); + if (NewRegs.begin() == NewRegs.end()) { + DEBUG(dbgs() << " has not been repaired, nothing to be done\n"); + continue; + } + DEBUG(dbgs() << " changed, replace " << MO.getReg()); + MO.setReg(*NewRegs.begin()); + DEBUG(dbgs() << " with " << MO.getReg()); + } +} + +unsigned RegisterBankInfo::getSizeInBits(unsigned Reg, + const MachineRegisterInfo &MRI, + const TargetRegisterInfo &TRI) { + const TargetRegisterClass *RC = nullptr; + if (TargetRegisterInfo::isPhysicalRegister(Reg)) { + // The size is not directly available for physical registers. + // Instead, we need to access a register class that contains Reg and + // get the size of that register class. + RC = TRI.getMinimalPhysRegClass(Reg); + } else { + unsigned RegSize = MRI.getSize(Reg); + // If Reg is not a generic register, query the register class to + // get its size. + if (RegSize) + return RegSize; + // Since Reg is not a generic register, it must have a register class. + RC = MRI.getRegClass(Reg); + } + assert(RC && "Unable to deduce the register class"); + return RC->getSize() * 8; +} + +//------------------------------------------------------------------------------ +// Helper classes implementation. +//------------------------------------------------------------------------------ +void RegisterBankInfo::PartialMapping::dump() const { + print(dbgs()); + dbgs() << '\n'; +} + +bool RegisterBankInfo::PartialMapping::verify() const { + assert(RegBank && "Register bank not set"); + assert(Length && "Empty mapping"); + assert((StartIdx < getHighBitIdx()) && "Overflow, switch to APInt?"); + // Check if the minimum width fits into RegBank. + assert(RegBank->getSize() >= Length && "Register bank too small for Mask"); + return true; +} + +void RegisterBankInfo::PartialMapping::print(raw_ostream &OS) const { + OS << "[" << StartIdx << ", " << getHighBitIdx() << "], RegBank = "; + if (RegBank) + OS << *RegBank; + else + OS << "nullptr"; +} + +bool RegisterBankInfo::ValueMapping::verify(unsigned ExpectedBitWidth) const { + assert(!BreakDown.empty() && "Value mapped nowhere?!"); + unsigned OrigValueBitWidth = 0; + for (const RegisterBankInfo::PartialMapping &PartMap : BreakDown) { + // Check that each register bank is big enough to hold the partial value: + // this check is done by PartialMapping::verify + assert(PartMap.verify() && "Partial mapping is invalid"); + // The original value should completely be mapped. + // Thus the maximum accessed index + 1 is the size of the original value. + OrigValueBitWidth = + std::max(OrigValueBitWidth, PartMap.getHighBitIdx() + 1); + } + assert(OrigValueBitWidth == ExpectedBitWidth && "BitWidth does not match"); + APInt ValueMask(OrigValueBitWidth, 0); + for (const RegisterBankInfo::PartialMapping &PartMap : BreakDown) { + // Check that the union of the partial mappings covers the whole value, + // without overlaps. + // The high bit is exclusive in the APInt API, thus getHighBitIdx + 1. + APInt PartMapMask = APInt::getBitsSet(OrigValueBitWidth, PartMap.StartIdx, + PartMap.getHighBitIdx() + 1); + ValueMask ^= PartMapMask; + assert((ValueMask & PartMapMask) == PartMapMask && + "Some partial mappings overlap"); + } + assert(ValueMask.isAllOnesValue() && "Value is not fully mapped"); + return true; +} + +void RegisterBankInfo::ValueMapping::dump() const { + print(dbgs()); + dbgs() << '\n'; +} + +void RegisterBankInfo::ValueMapping::print(raw_ostream &OS) const { + OS << "#BreakDown: " << BreakDown.size() << " "; + bool IsFirst = true; + for (const PartialMapping &PartMap : BreakDown) { + if (!IsFirst) + OS << ", "; + OS << '[' << PartMap << ']'; + IsFirst = false; + } +} + +void RegisterBankInfo::InstructionMapping::setOperandMapping( + unsigned OpIdx, unsigned MaskSize, const RegisterBank &RegBank) { + // Build the value mapping. + assert(MaskSize <= RegBank.getSize() && "Register bank is too small"); + + // Create the mapping object. + getOperandMapping(OpIdx).BreakDown.push_back( + PartialMapping(0, MaskSize, RegBank)); +} + +bool RegisterBankInfo::InstructionMapping::verify( + const MachineInstr &MI) const { + // Check that all the register operands are properly mapped. + // Check the constructor invariant. + assert(NumOperands == MI.getNumOperands() && + "NumOperands must match, see constructor"); + assert(MI.getParent() && MI.getParent()->getParent() && + "MI must be connected to a MachineFunction"); + const MachineFunction &MF = *MI.getParent()->getParent(); + (void)MF; + + for (unsigned Idx = 0; Idx < NumOperands; ++Idx) { + const MachineOperand &MO = MI.getOperand(Idx); + const RegisterBankInfo::ValueMapping &MOMapping = getOperandMapping(Idx); + (void)MOMapping; + if (!MO.isReg()) { + assert(MOMapping.BreakDown.empty() && + "We should not care about non-reg mapping"); + continue; + } + unsigned Reg = MO.getReg(); + if (!Reg) + continue; + // Register size in bits. + // This size must match what the mapping expects. + assert(MOMapping.verify(getSizeInBits( + Reg, MF.getRegInfo(), *MF.getSubtarget().getRegisterInfo())) && + "Value mapping is invalid"); + } + return true; +} + +void RegisterBankInfo::InstructionMapping::dump() const { + print(dbgs()); + dbgs() << '\n'; +} + +void RegisterBankInfo::InstructionMapping::print(raw_ostream &OS) const { + OS << "ID: " << getID() << " Cost: " << getCost() << " Mapping: "; + + for (unsigned OpIdx = 0; OpIdx != NumOperands; ++OpIdx) { + const ValueMapping &ValMapping = getOperandMapping(OpIdx); + if (OpIdx) + OS << ", "; + OS << "{ Idx: " << OpIdx << " Map: " << ValMapping << '}'; + } +} + +const int RegisterBankInfo::OperandsMapper::DontKnowIdx = -1; + +RegisterBankInfo::OperandsMapper::OperandsMapper( + MachineInstr &MI, const InstructionMapping &InstrMapping, + MachineRegisterInfo &MRI) + : MRI(MRI), MI(MI), InstrMapping(InstrMapping) { + unsigned NumOpds = MI.getNumOperands(); + OpToNewVRegIdx.reset(new int[NumOpds]); + std::fill(&OpToNewVRegIdx[0], &OpToNewVRegIdx[NumOpds], + OperandsMapper::DontKnowIdx); + assert(InstrMapping.verify(MI) && "Invalid mapping for MI"); +} + +iterator_range<SmallVectorImpl<unsigned>::iterator> +RegisterBankInfo::OperandsMapper::getVRegsMem(unsigned OpIdx) { + assert(OpIdx < getMI().getNumOperands() && "Out-of-bound access"); + unsigned NumPartialVal = + getInstrMapping().getOperandMapping(OpIdx).BreakDown.size(); + int StartIdx = OpToNewVRegIdx[OpIdx]; + + if (StartIdx == OperandsMapper::DontKnowIdx) { + // This is the first time we try to access OpIdx. + // Create the cells that will hold all the partial values at the + // end of the list of NewVReg. + StartIdx = NewVRegs.size(); + OpToNewVRegIdx[OpIdx] = StartIdx; + for (unsigned i = 0; i < NumPartialVal; ++i) + NewVRegs.push_back(0); + } + SmallVectorImpl<unsigned>::iterator End = + getNewVRegsEnd(StartIdx, NumPartialVal); + + return make_range(&NewVRegs[StartIdx], End); +} + +SmallVectorImpl<unsigned>::const_iterator +RegisterBankInfo::OperandsMapper::getNewVRegsEnd(unsigned StartIdx, + unsigned NumVal) const { + return const_cast<OperandsMapper *>(this)->getNewVRegsEnd(StartIdx, NumVal); +} +SmallVectorImpl<unsigned>::iterator +RegisterBankInfo::OperandsMapper::getNewVRegsEnd(unsigned StartIdx, + unsigned NumVal) { + assert((NewVRegs.size() == StartIdx + NumVal || + NewVRegs.size() > StartIdx + NumVal) && + "NewVRegs too small to contain all the partial mapping"); + return NewVRegs.size() <= StartIdx + NumVal ? NewVRegs.end() + : &NewVRegs[StartIdx + NumVal]; +} + +void RegisterBankInfo::OperandsMapper::createVRegs(unsigned OpIdx) { + assert(OpIdx < getMI().getNumOperands() && "Out-of-bound access"); + iterator_range<SmallVectorImpl<unsigned>::iterator> NewVRegsForOpIdx = + getVRegsMem(OpIdx); + const SmallVectorImpl<PartialMapping> &PartMapList = + getInstrMapping().getOperandMapping(OpIdx).BreakDown; + SmallVectorImpl<PartialMapping>::const_iterator PartMap = PartMapList.begin(); + for (unsigned &NewVReg : NewVRegsForOpIdx) { + assert(PartMap != PartMapList.end() && "Out-of-bound access"); + assert(NewVReg == 0 && "Register has already been created"); + NewVReg = MRI.createGenericVirtualRegister(PartMap->Length); + MRI.setRegBank(NewVReg, *PartMap->RegBank); + ++PartMap; + } +} + +void RegisterBankInfo::OperandsMapper::setVRegs(unsigned OpIdx, + unsigned PartialMapIdx, + unsigned NewVReg) { + assert(OpIdx < getMI().getNumOperands() && "Out-of-bound access"); + assert(getInstrMapping().getOperandMapping(OpIdx).BreakDown.size() > + PartialMapIdx && + "Out-of-bound access for partial mapping"); + // Make sure the memory is initialized for that operand. + (void)getVRegsMem(OpIdx); + assert(NewVRegs[OpToNewVRegIdx[OpIdx] + PartialMapIdx] == 0 && + "This value is already set"); + NewVRegs[OpToNewVRegIdx[OpIdx] + PartialMapIdx] = NewVReg; +} + +iterator_range<SmallVectorImpl<unsigned>::const_iterator> +RegisterBankInfo::OperandsMapper::getVRegs(unsigned OpIdx, + bool ForDebug) const { + (void)ForDebug; + assert(OpIdx < getMI().getNumOperands() && "Out-of-bound access"); + int StartIdx = OpToNewVRegIdx[OpIdx]; + + if (StartIdx == OperandsMapper::DontKnowIdx) + return make_range(NewVRegs.end(), NewVRegs.end()); + + unsigned PartMapSize = + getInstrMapping().getOperandMapping(OpIdx).BreakDown.size(); + SmallVectorImpl<unsigned>::const_iterator End = + getNewVRegsEnd(StartIdx, PartMapSize); + iterator_range<SmallVectorImpl<unsigned>::const_iterator> Res = + make_range(&NewVRegs[StartIdx], End); +#ifndef NDEBUG + for (unsigned VReg : Res) + assert((VReg || ForDebug) && "Some registers are uninitialized"); +#endif + return Res; +} + +void RegisterBankInfo::OperandsMapper::dump() const { + print(dbgs(), true); + dbgs() << '\n'; +} + +void RegisterBankInfo::OperandsMapper::print(raw_ostream &OS, + bool ForDebug) const { + unsigned NumOpds = getMI().getNumOperands(); + if (ForDebug) { + OS << "Mapping for " << getMI() << "\nwith " << getInstrMapping() << '\n'; + // Print out the internal state of the index table. + OS << "Populated indices (CellNumber, IndexInNewVRegs): "; + bool IsFirst = true; + for (unsigned Idx = 0; Idx != NumOpds; ++Idx) { + if (OpToNewVRegIdx[Idx] != DontKnowIdx) { + if (!IsFirst) + OS << ", "; + OS << '(' << Idx << ", " << OpToNewVRegIdx[Idx] << ')'; + IsFirst = false; + } + } + OS << '\n'; + } else + OS << "Mapping ID: " << getInstrMapping().getID() << ' '; + + OS << "Operand Mapping: "; + // If we have a function, we can pretty print the name of the registers. + // Otherwise we will print the raw numbers. + const TargetRegisterInfo *TRI = + getMI().getParent() && getMI().getParent()->getParent() + ? getMI().getParent()->getParent()->getSubtarget().getRegisterInfo() + : nullptr; + bool IsFirst = true; + for (unsigned Idx = 0; Idx != NumOpds; ++Idx) { + if (OpToNewVRegIdx[Idx] == DontKnowIdx) + continue; + if (!IsFirst) + OS << ", "; + IsFirst = false; + OS << '(' << PrintReg(getMI().getOperand(Idx).getReg(), TRI) << ", ["; + bool IsFirstNewVReg = true; + for (unsigned VReg : getVRegs(Idx)) { + if (!IsFirstNewVReg) + OS << ", "; + IsFirstNewVReg = false; + OS << PrintReg(VReg, TRI); + } + OS << "])"; + } +} |