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