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