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/ADT/STLExtras.h"
16 #include "llvm/ADT/SmallVector.h"
17 #include "llvm/CodeGen/GlobalISel/LegalizerInfo.h"
18 #include "llvm/CodeGen/GlobalISel/RegisterBank.h"
19 #include "llvm/CodeGen/GlobalISel/RegisterBankInfo.h"
20 #include "llvm/CodeGen/GlobalISel/Utils.h"
21 #include "llvm/CodeGen/MachineBasicBlock.h"
22 #include "llvm/CodeGen/MachineBlockFrequencyInfo.h"
23 #include "llvm/CodeGen/MachineBranchProbabilityInfo.h"
24 #include "llvm/CodeGen/MachineFunction.h"
25 #include "llvm/CodeGen/MachineInstr.h"
26 #include "llvm/CodeGen/MachineOperand.h"
27 #include "llvm/CodeGen/MachineOptimizationRemarkEmitter.h"
28 #include "llvm/CodeGen/MachineRegisterInfo.h"
29 #include "llvm/CodeGen/TargetOpcodes.h"
30 #include "llvm/CodeGen/TargetPassConfig.h"
31 #include "llvm/CodeGen/TargetRegisterInfo.h"
32 #include "llvm/CodeGen/TargetSubtargetInfo.h"
33 #include "llvm/IR/Attributes.h"
34 #include "llvm/IR/Function.h"
35 #include "llvm/Pass.h"
36 #include "llvm/Support/BlockFrequency.h"
37 #include "llvm/Support/CommandLine.h"
38 #include "llvm/Support/Compiler.h"
39 #include "llvm/Support/Debug.h"
40 #include "llvm/Support/ErrorHandling.h"
41 #include "llvm/Support/raw_ostream.h"
49 #define DEBUG_TYPE "regbankselect"
53 static cl::opt<RegBankSelect::Mode> RegBankSelectMode(
54 cl::desc("Mode of the RegBankSelect pass"), cl::Hidden, cl::Optional,
55 cl::values(clEnumValN(RegBankSelect::Mode::Fast, "regbankselect-fast",
56 "Run the Fast mode (default mapping)"),
57 clEnumValN(RegBankSelect::Mode::Greedy, "regbankselect-greedy",
58 "Use the Greedy mode (best local mapping)")));
60 char RegBankSelect::ID = 0;
62 INITIALIZE_PASS_BEGIN(RegBankSelect, DEBUG_TYPE,
63 "Assign register bank of generic virtual registers",
65 INITIALIZE_PASS_DEPENDENCY(MachineBlockFrequencyInfo)
66 INITIALIZE_PASS_DEPENDENCY(MachineBranchProbabilityInfo)
67 INITIALIZE_PASS_DEPENDENCY(TargetPassConfig)
68 INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE,
69 "Assign register bank of generic virtual registers", false,
72 RegBankSelect::RegBankSelect(Mode RunningMode)
73 : MachineFunctionPass(ID), OptMode(RunningMode) {
74 initializeRegBankSelectPass(*PassRegistry::getPassRegistry());
75 if (RegBankSelectMode.getNumOccurrences() != 0) {
76 OptMode = RegBankSelectMode;
77 if (RegBankSelectMode != RunningMode)
78 DEBUG(dbgs() << "RegBankSelect mode overrided by command line\n");
82 void RegBankSelect::init(MachineFunction &MF) {
83 RBI = MF.getSubtarget().getRegBankInfo();
84 assert(RBI && "Cannot work without RegisterBankInfo");
85 MRI = &MF.getRegInfo();
86 TRI = MF.getSubtarget().getRegisterInfo();
87 TPC = &getAnalysis<TargetPassConfig>();
88 if (OptMode != Mode::Fast) {
89 MBFI = &getAnalysis<MachineBlockFrequencyInfo>();
90 MBPI = &getAnalysis<MachineBranchProbabilityInfo>();
96 MORE = llvm::make_unique<MachineOptimizationRemarkEmitter>(MF, MBFI);
99 void RegBankSelect::getAnalysisUsage(AnalysisUsage &AU) const {
100 if (OptMode != Mode::Fast) {
101 // We could preserve the information from these two analysis but
102 // the APIs do not allow to do so yet.
103 AU.addRequired<MachineBlockFrequencyInfo>();
104 AU.addRequired<MachineBranchProbabilityInfo>();
106 AU.addRequired<TargetPassConfig>();
107 MachineFunctionPass::getAnalysisUsage(AU);
110 bool RegBankSelect::assignmentMatch(
111 unsigned Reg, const RegisterBankInfo::ValueMapping &ValMapping,
112 bool &OnlyAssign) const {
113 // By default we assume we will have to repair something.
115 // Each part of a break down needs to end up in a different register.
116 // In other word, Reg assignement does not match.
117 if (ValMapping.NumBreakDowns > 1)
120 const RegisterBank *CurRegBank = RBI->getRegBank(Reg, *MRI, *TRI);
121 const RegisterBank *DesiredRegBrank = ValMapping.BreakDown[0].RegBank;
122 // Reg is free of assignment, a simple assignment will make the
123 // register bank to match.
124 OnlyAssign = CurRegBank == nullptr;
125 DEBUG(dbgs() << "Does assignment already match: ";
126 if (CurRegBank) dbgs() << *CurRegBank; else dbgs() << "none";
127 dbgs() << " against ";
128 assert(DesiredRegBrank && "The mapping must be valid");
129 dbgs() << *DesiredRegBrank << '\n';);
130 return CurRegBank == DesiredRegBrank;
133 bool RegBankSelect::repairReg(
134 MachineOperand &MO, const RegisterBankInfo::ValueMapping &ValMapping,
135 RegBankSelect::RepairingPlacement &RepairPt,
136 const iterator_range<SmallVectorImpl<unsigned>::const_iterator> &NewVRegs) {
137 if (ValMapping.NumBreakDowns != 1 && !TPC->isGlobalISelAbortEnabled())
139 assert(ValMapping.NumBreakDowns == 1 && "Not yet implemented");
140 // An empty range of new register means no repairing.
141 assert(NewVRegs.begin() != NewVRegs.end() && "We should not have to repair");
143 // Assume we are repairing a use and thus, the original reg will be
144 // the source of the repairing.
145 unsigned Src = MO.getReg();
146 unsigned Dst = *NewVRegs.begin();
148 // If we repair a definition, swap the source and destination for
153 assert((RepairPt.getNumInsertPoints() == 1 ||
154 TargetRegisterInfo::isPhysicalRegister(Dst)) &&
155 "We are about to create several defs for Dst");
157 // Build the instruction used to repair, then clone it at the right
158 // places. Avoiding buildCopy bypasses the check that Src and Dst have the
159 // same types because the type is a placeholder when this function is called.
161 MIRBuilder.buildInstrNoInsert(TargetOpcode::COPY).addDef(Dst).addUse(Src);
162 DEBUG(dbgs() << "Copy: " << printReg(Src) << " to: " << printReg(Dst)
165 // Check if MI is legal. if not, we need to legalize all the
166 // instructions we are going to insert.
167 std::unique_ptr<MachineInstr *[]> NewInstrs(
168 new MachineInstr *[RepairPt.getNumInsertPoints()]);
171 for (const std::unique_ptr<InsertPoint> &InsertPt : RepairPt) {
176 CurMI = MIRBuilder.getMF().CloneMachineInstr(MI);
177 InsertPt->insert(*CurMI);
178 NewInstrs[Idx++] = CurMI;
182 // Legalize NewInstrs if need be.
186 uint64_t RegBankSelect::getRepairCost(
187 const MachineOperand &MO,
188 const RegisterBankInfo::ValueMapping &ValMapping) const {
189 assert(MO.isReg() && "We should only repair register operand");
190 assert(ValMapping.NumBreakDowns && "Nothing to map??");
192 bool IsSameNumOfValues = ValMapping.NumBreakDowns == 1;
193 const RegisterBank *CurRegBank = RBI->getRegBank(MO.getReg(), *MRI, *TRI);
194 // If MO does not have a register bank, we should have just been
195 // able to set one unless we have to break the value down.
196 assert((!IsSameNumOfValues || CurRegBank) && "We should not have to repair");
197 // Def: Val <- NewDefs
198 // Same number of values: copy
199 // Different number: Val = build_sequence Defs1, Defs2, ...
200 // Use: NewSources <- Val.
201 // Same number of values: copy.
202 // Different number: Src1, Src2, ... =
203 // extract_value Val, Src1Begin, Src1Len, Src2Begin, Src2Len, ...
204 // We should remember that this value is available somewhere else to
205 // coalesce the value.
207 if (IsSameNumOfValues) {
208 const RegisterBank *DesiredRegBrank = ValMapping.BreakDown[0].RegBank;
209 // If we repair a definition, swap the source and destination for
212 std::swap(CurRegBank, DesiredRegBrank);
213 // TODO: It may be possible to actually avoid the copy.
214 // If we repair something where the source is defined by a copy
215 // and the source of that copy is on the right bank, we can reuse
218 // RegToRepair<BankA> = copy AlternativeSrc<BankB>
219 // = op RegToRepair<BankA>
220 // We can simply propagate AlternativeSrc instead of copying RegToRepair
221 // into a new virtual register.
222 // We would also need to propagate this information in the
223 // repairing placement.
224 unsigned Cost = RBI->copyCost(*DesiredRegBrank, *CurRegBank,
225 RBI->getSizeInBits(MO.getReg(), *MRI, *TRI));
226 // TODO: use a dedicated constant for ImpossibleCost.
227 if (Cost != std::numeric_limits<unsigned>::max())
229 // Return the legalization cost of that repairing.
231 return std::numeric_limits<unsigned>::max();
234 const RegisterBankInfo::InstructionMapping &RegBankSelect::findBestMapping(
235 MachineInstr &MI, RegisterBankInfo::InstructionMappings &PossibleMappings,
236 SmallVectorImpl<RepairingPlacement> &RepairPts) {
237 assert(!PossibleMappings.empty() &&
238 "Do not know how to map this instruction");
240 const RegisterBankInfo::InstructionMapping *BestMapping = nullptr;
241 MappingCost Cost = MappingCost::ImpossibleCost();
242 SmallVector<RepairingPlacement, 4> LocalRepairPts;
243 for (const RegisterBankInfo::InstructionMapping *CurMapping :
245 MappingCost CurCost =
246 computeMapping(MI, *CurMapping, LocalRepairPts, &Cost);
247 if (CurCost < Cost) {
248 DEBUG(dbgs() << "New best: " << CurCost << '\n');
250 BestMapping = CurMapping;
252 for (RepairingPlacement &RepairPt : LocalRepairPts)
253 RepairPts.emplace_back(std::move(RepairPt));
256 if (!BestMapping && !TPC->isGlobalISelAbortEnabled()) {
257 // If none of the mapping worked that means they are all impossible.
258 // Thus, pick the first one and set an impossible repairing point.
259 // It will trigger the failed isel mode.
260 BestMapping = *PossibleMappings.begin();
261 RepairPts.emplace_back(
262 RepairingPlacement(MI, 0, *TRI, *this, RepairingPlacement::Impossible));
264 assert(BestMapping && "No suitable mapping for instruction");
268 void RegBankSelect::tryAvoidingSplit(
269 RegBankSelect::RepairingPlacement &RepairPt, const MachineOperand &MO,
270 const RegisterBankInfo::ValueMapping &ValMapping) const {
271 const MachineInstr &MI = *MO.getParent();
272 assert(RepairPt.hasSplit() && "We should not have to adjust for split");
273 // Splitting should only occur for PHIs or between terminators,
274 // because we only do local repairing.
275 assert((MI.isPHI() || MI.isTerminator()) && "Why do we split?");
277 assert(&MI.getOperand(RepairPt.getOpIdx()) == &MO &&
278 "Repairing placement does not match operand");
280 // If we need splitting for phis, that means it is because we
281 // could not find an insertion point before the terminators of
282 // the predecessor block for this argument. In other words,
283 // the input value is defined by one of the terminators.
284 assert((!MI.isPHI() || !MO.isDef()) && "Need split for phi def?");
286 // We split to repair the use of a phi or a terminator.
288 if (MI.isTerminator()) {
289 assert(&MI != &(*MI.getParent()->getFirstTerminator()) &&
290 "Need to split for the first terminator?!");
292 // For the PHI case, the split may not be actually required.
293 // In the copy case, a phi is already a copy on the incoming edge,
294 // therefore there is no need to split.
295 if (ValMapping.NumBreakDowns == 1)
296 // This is a already a copy, there is nothing to do.
297 RepairPt.switchTo(RepairingPlacement::RepairingKind::Reassign);
302 // At this point, we need to repair a defintion of a terminator.
304 // Technically we need to fix the def of MI on all outgoing
305 // edges of MI to keep the repairing local. In other words, we
306 // will create several definitions of the same register. This
307 // does not work for SSA unless that definition is a physical
309 // However, there are other cases where we can get away with
310 // that while still keeping the repairing local.
311 assert(MI.isTerminator() && MO.isDef() &&
312 "This code is for the def of a terminator");
314 // Since we use RPO traversal, if we need to repair a definition
315 // this means this definition could be:
316 // 1. Used by PHIs (i.e., this VReg has been visited as part of the
317 // uses of a phi.), or
318 // 2. Part of a target specific instruction (i.e., the target applied
319 // some register class constraints when creating the instruction.)
320 // If the constraints come for #2, the target said that another mapping
321 // is supported so we may just drop them. Indeed, if we do not change
322 // the number of registers holding that value, the uses will get fixed
323 // when we get to them.
324 // Uses in PHIs may have already been proceeded though.
325 // If the constraints come for #1, then, those are weak constraints and
326 // no actual uses may rely on them. However, the problem remains mainly
327 // the same as for #2. If the value stays in one register, we could
328 // just switch the register bank of the definition, but we would need to
329 // account for a repairing cost for each phi we silently change.
331 // In any case, if the value needs to be broken down into several
332 // registers, the repairing is not local anymore as we need to patch
333 // every uses to rebuild the value in just one register.
336 // - If the value is in a physical register, we can do the split and
338 // Otherwise if the value is in a virtual register:
339 // - If the value remains in one register, we do not have to split
340 // just switching the register bank would do, but we need to account
341 // in the repairing cost all the phi we changed.
342 // - If the value spans several registers, then we cannot do a local
345 // Check if this is a physical or virtual register.
346 unsigned Reg = MO.getReg();
347 if (TargetRegisterInfo::isPhysicalRegister(Reg)) {
348 // We are going to split every outgoing edges.
349 // Check that this is possible.
350 // FIXME: The machine representation is currently broken
351 // since it also several terminators in one basic block.
352 // Because of that we would technically need a way to get
353 // the targets of just one terminator to know which edges
355 // Assert that we do not hit the ill-formed representation.
357 // If there are other terminators before that one, some of
358 // the outgoing edges may not be dominated by this definition.
359 assert(&MI == &(*MI.getParent()->getFirstTerminator()) &&
360 "Do not know which outgoing edges are relevant");
361 const MachineInstr *Next = MI.getNextNode();
362 assert((!Next || Next->isUnconditionalBranch()) &&
363 "Do not know where each terminator ends up");
365 // If the next terminator uses Reg, this means we have
366 // to split right after MI and thus we need a way to ask
367 // which outgoing edges are affected.
368 assert(!Next->readsRegister(Reg) && "Need to split between terminators");
369 // We will split all the edges and repair there.
371 // This is a virtual register defined by a terminator.
372 if (ValMapping.NumBreakDowns == 1) {
373 // There is nothing to repair, but we may actually lie on
374 // the repairing cost because of the PHIs already proceeded
375 // as already stated.
376 // Though the code will be correct.
377 assert(false && "Repairing cost may not be accurate");
379 // We need to do non-local repairing. Basically, patch all
380 // the uses (i.e., phis) that we already proceeded.
381 // For now, just say this mapping is not possible.
382 RepairPt.switchTo(RepairingPlacement::RepairingKind::Impossible);
387 RegBankSelect::MappingCost RegBankSelect::computeMapping(
388 MachineInstr &MI, const RegisterBankInfo::InstructionMapping &InstrMapping,
389 SmallVectorImpl<RepairingPlacement> &RepairPts,
390 const RegBankSelect::MappingCost *BestCost) {
391 assert((MBFI || !BestCost) && "Costs comparison require MBFI");
393 if (!InstrMapping.isValid())
394 return MappingCost::ImpossibleCost();
396 // If mapped with InstrMapping, MI will have the recorded cost.
397 MappingCost Cost(MBFI ? MBFI->getBlockFreq(MI.getParent()) : 1);
398 bool Saturated = Cost.addLocalCost(InstrMapping.getCost());
399 assert(!Saturated && "Possible mapping saturated the cost");
400 DEBUG(dbgs() << "Evaluating mapping cost for: " << MI);
401 DEBUG(dbgs() << "With: " << InstrMapping << '\n');
403 if (BestCost && Cost > *BestCost) {
404 DEBUG(dbgs() << "Mapping is too expensive from the start\n");
408 // Moreover, to realize this mapping, the register bank of each operand must
409 // match this mapping. In other words, we may need to locally reassign the
410 // register banks. Account for that repairing cost as well.
411 // In this context, local means in the surrounding of MI.
412 for (unsigned OpIdx = 0, EndOpIdx = InstrMapping.getNumOperands();
413 OpIdx != EndOpIdx; ++OpIdx) {
414 const MachineOperand &MO = MI.getOperand(OpIdx);
417 unsigned Reg = MO.getReg();
420 DEBUG(dbgs() << "Opd" << OpIdx << '\n');
421 const RegisterBankInfo::ValueMapping &ValMapping =
422 InstrMapping.getOperandMapping(OpIdx);
423 // If Reg is already properly mapped, this is free.
425 if (assignmentMatch(Reg, ValMapping, Assign)) {
426 DEBUG(dbgs() << "=> is free (match).\n");
430 DEBUG(dbgs() << "=> is free (simple assignment).\n");
431 RepairPts.emplace_back(RepairingPlacement(MI, OpIdx, *TRI, *this,
432 RepairingPlacement::Reassign));
436 // Find the insertion point for the repairing code.
437 RepairPts.emplace_back(
438 RepairingPlacement(MI, OpIdx, *TRI, *this, RepairingPlacement::Insert));
439 RepairingPlacement &RepairPt = RepairPts.back();
441 // If we need to split a basic block to materialize this insertion point,
442 // we may give a higher cost to this mapping.
443 // Nevertheless, we may get away with the split, so try that first.
444 if (RepairPt.hasSplit())
445 tryAvoidingSplit(RepairPt, MO, ValMapping);
447 // Check that the materialization of the repairing is possible.
448 if (!RepairPt.canMaterialize()) {
449 DEBUG(dbgs() << "Mapping involves impossible repairing\n");
450 return MappingCost::ImpossibleCost();
453 // Account for the split cost and repair cost.
454 // Unless the cost is already saturated or we do not care about the cost.
455 if (!BestCost || Saturated)
458 // To get accurate information we need MBFI and MBPI.
459 // Thus, if we end up here this information should be here.
460 assert(MBFI && MBPI && "Cost computation requires MBFI and MBPI");
462 // FIXME: We will have to rework the repairing cost model.
463 // The repairing cost depends on the register bank that MO has.
464 // However, when we break down the value into different values,
465 // MO may not have a register bank while still needing repairing.
466 // For the fast mode, we don't compute the cost so that is fine,
467 // but still for the repairing code, we will have to make a choice.
468 // For the greedy mode, we should choose greedily what is the best
469 // choice based on the next use of MO.
471 // Sums up the repairing cost of MO at each insertion point.
472 uint64_t RepairCost = getRepairCost(MO, ValMapping);
474 // This is an impossible to repair cost.
475 if (RepairCost == std::numeric_limits<unsigned>::max())
478 // Bias used for splitting: 5%.
479 const uint64_t PercentageForBias = 5;
480 uint64_t Bias = (RepairCost * PercentageForBias + 99) / 100;
481 // We should not need more than a couple of instructions to repair
482 // an assignment. In other words, the computation should not
483 // overflow because the repairing cost is free of basic block
485 assert(((RepairCost < RepairCost * PercentageForBias) &&
486 (RepairCost * PercentageForBias <
487 RepairCost * PercentageForBias + 99)) &&
488 "Repairing involves more than a billion of instructions?!");
489 for (const std::unique_ptr<InsertPoint> &InsertPt : RepairPt) {
490 assert(InsertPt->canMaterialize() && "We should not have made it here");
491 // We will applied some basic block frequency and those uses uint64_t.
492 if (!InsertPt->isSplit())
493 Saturated = Cost.addLocalCost(RepairCost);
495 uint64_t CostForInsertPt = RepairCost;
496 // Again we shouldn't overflow here givent that
497 // CostForInsertPt is frequency free at this point.
498 assert(CostForInsertPt + Bias > CostForInsertPt &&
499 "Repairing + split bias overflows");
500 CostForInsertPt += Bias;
501 uint64_t PtCost = InsertPt->frequency(*this) * CostForInsertPt;
502 // Check if we just overflowed.
503 if ((Saturated = PtCost < CostForInsertPt))
506 Saturated = Cost.addNonLocalCost(PtCost);
509 // Stop looking into what it takes to repair, this is already
511 if (BestCost && Cost > *BestCost) {
512 DEBUG(dbgs() << "Mapping is too expensive, stop processing\n");
516 // No need to accumulate more cost information.
517 // We need to still gather the repairing information though.
522 DEBUG(dbgs() << "Total cost is: " << Cost << "\n");
526 bool RegBankSelect::applyMapping(
527 MachineInstr &MI, const RegisterBankInfo::InstructionMapping &InstrMapping,
528 SmallVectorImpl<RegBankSelect::RepairingPlacement> &RepairPts) {
529 // OpdMapper will hold all the information needed for the rewritting.
530 RegisterBankInfo::OperandsMapper OpdMapper(MI, InstrMapping, *MRI);
532 // First, place the repairing code.
533 for (RepairingPlacement &RepairPt : RepairPts) {
534 if (!RepairPt.canMaterialize() ||
535 RepairPt.getKind() == RepairingPlacement::Impossible)
537 assert(RepairPt.getKind() != RepairingPlacement::None &&
538 "This should not make its way in the list");
539 unsigned OpIdx = RepairPt.getOpIdx();
540 MachineOperand &MO = MI.getOperand(OpIdx);
541 const RegisterBankInfo::ValueMapping &ValMapping =
542 InstrMapping.getOperandMapping(OpIdx);
543 unsigned Reg = MO.getReg();
545 switch (RepairPt.getKind()) {
546 case RepairingPlacement::Reassign:
547 assert(ValMapping.NumBreakDowns == 1 &&
548 "Reassignment should only be for simple mapping");
549 MRI->setRegBank(Reg, *ValMapping.BreakDown[0].RegBank);
551 case RepairingPlacement::Insert:
552 OpdMapper.createVRegs(OpIdx);
553 if (!repairReg(MO, ValMapping, RepairPt, OpdMapper.getVRegs(OpIdx)))
557 llvm_unreachable("Other kind should not happen");
561 // Second, rewrite the instruction.
562 DEBUG(dbgs() << "Actual mapping of the operands: " << OpdMapper << '\n');
563 RBI->applyMapping(OpdMapper);
568 bool RegBankSelect::assignInstr(MachineInstr &MI) {
569 DEBUG(dbgs() << "Assign: " << MI);
570 // Remember the repairing placement for all the operands.
571 SmallVector<RepairingPlacement, 4> RepairPts;
573 const RegisterBankInfo::InstructionMapping *BestMapping;
574 if (OptMode == RegBankSelect::Mode::Fast) {
575 BestMapping = &RBI->getInstrMapping(MI);
576 MappingCost DefaultCost = computeMapping(MI, *BestMapping, RepairPts);
578 if (DefaultCost == MappingCost::ImpossibleCost())
581 RegisterBankInfo::InstructionMappings PossibleMappings =
582 RBI->getInstrPossibleMappings(MI);
583 if (PossibleMappings.empty())
585 BestMapping = &findBestMapping(MI, PossibleMappings, RepairPts);
587 // Make sure the mapping is valid for MI.
588 assert(BestMapping->verify(MI) && "Invalid instruction mapping");
590 DEBUG(dbgs() << "Best Mapping: " << *BestMapping << '\n');
592 // After this call, MI may not be valid anymore.
594 return applyMapping(MI, *BestMapping, RepairPts);
597 bool RegBankSelect::runOnMachineFunction(MachineFunction &MF) {
598 // If the ISel pipeline failed, do not bother running that pass.
599 if (MF.getProperties().hasProperty(
600 MachineFunctionProperties::Property::FailedISel))
603 DEBUG(dbgs() << "Assign register banks for: " << MF.getName() << '\n');
604 const Function &F = MF.getFunction();
605 Mode SaveOptMode = OptMode;
606 if (F.hasFnAttribute(Attribute::OptimizeNone))
607 OptMode = Mode::Fast;
611 // Check that our input is fully legal: we require the function to have the
612 // Legalized property, so it should be.
613 // FIXME: This should be in the MachineVerifier, but it can't use the
614 // LegalizerInfo as it's currently in the separate GlobalISel library.
615 const MachineRegisterInfo &MRI = MF.getRegInfo();
616 if (const LegalizerInfo *MLI = MF.getSubtarget().getLegalizerInfo()) {
617 for (MachineBasicBlock &MBB : MF) {
618 for (MachineInstr &MI : MBB) {
619 if (isPreISelGenericOpcode(MI.getOpcode()) && !MLI->isLegal(MI, MRI)) {
620 reportGISelFailure(MF, *TPC, *MORE, "gisel-regbankselect",
621 "instruction is not legal", MI);
629 // Walk the function and assign register banks to all operands.
630 // Use a RPOT to make sure all registers are assigned before we choose
631 // the best mapping of the current instruction.
632 ReversePostOrderTraversal<MachineFunction*> RPOT(&MF);
633 for (MachineBasicBlock *MBB : RPOT) {
634 // Set a sensible insertion point so that subsequent calls to
636 MIRBuilder.setMBB(*MBB);
637 for (MachineBasicBlock::iterator MII = MBB->begin(), End = MBB->end();
639 // MI might be invalidated by the assignment, so move the
640 // iterator before hand.
641 MachineInstr &MI = *MII++;
643 // Ignore target-specific instructions: they should use proper regclasses.
644 if (isTargetSpecificOpcode(MI.getOpcode()))
647 if (!assignInstr(MI)) {
648 reportGISelFailure(MF, *TPC, *MORE, "gisel-regbankselect",
649 "unable to map instruction", MI);
654 OptMode = SaveOptMode;
658 //------------------------------------------------------------------------------
659 // Helper Classes Implementation
660 //------------------------------------------------------------------------------
661 RegBankSelect::RepairingPlacement::RepairingPlacement(
662 MachineInstr &MI, unsigned OpIdx, const TargetRegisterInfo &TRI, Pass &P,
663 RepairingPlacement::RepairingKind Kind)
664 // Default is, we are going to insert code to repair OpIdx.
665 : Kind(Kind), OpIdx(OpIdx),
666 CanMaterialize(Kind != RepairingKind::Impossible), P(P) {
667 const MachineOperand &MO = MI.getOperand(OpIdx);
668 assert(MO.isReg() && "Trying to repair a non-reg operand");
670 if (Kind != RepairingKind::Insert)
673 // Repairings for definitions happen after MI, uses happen before.
674 bool Before = !MO.isDef();
676 // Check if we are done with MI.
677 if (!MI.isPHI() && !MI.isTerminator()) {
678 addInsertPoint(MI, Before);
679 // We are done with the initialization.
683 // Now, look for the special cases.
685 // - PHI must be the first instructions:
686 // * Before, we have to split the related incoming edge.
687 // * After, move the insertion point past the last phi.
689 MachineBasicBlock::iterator It = MI.getParent()->getFirstNonPHI();
690 if (It != MI.getParent()->end())
691 addInsertPoint(*It, /*Before*/ true);
693 addInsertPoint(*(--It), /*Before*/ false);
696 // We repair a use of a phi, we may need to split the related edge.
697 MachineBasicBlock &Pred = *MI.getOperand(OpIdx + 1).getMBB();
698 // Check if we can move the insertion point prior to the
699 // terminators of the predecessor.
700 unsigned Reg = MO.getReg();
701 MachineBasicBlock::iterator It = Pred.getLastNonDebugInstr();
702 for (auto Begin = Pred.begin(); It != Begin && It->isTerminator(); --It)
703 if (It->modifiesRegister(Reg, &TRI)) {
704 // We cannot hoist the repairing code in the predecessor.
706 addInsertPoint(Pred, *MI.getParent());
709 // At this point, we can insert in Pred.
711 // - If It is invalid, Pred is empty and we can insert in Pred
713 // - If It is valid, It is the first non-terminator, insert after It.
714 if (It == Pred.end())
715 addInsertPoint(Pred, /*Beginning*/ false);
717 addInsertPoint(*It, /*Before*/ false);
719 // - Terminators must be the last instructions:
720 // * Before, move the insert point before the first terminator.
721 // * After, we have to split the outcoming edges.
722 unsigned Reg = MO.getReg();
724 // Check whether Reg is defined by any terminator.
725 MachineBasicBlock::iterator It = MI;
726 for (auto Begin = MI.getParent()->begin();
727 --It != Begin && It->isTerminator();)
728 if (It->modifiesRegister(Reg, &TRI)) {
729 // Insert the repairing code right after the definition.
730 addInsertPoint(*It, /*Before*/ false);
733 addInsertPoint(*It, /*Before*/ true);
736 // Make sure Reg is not redefined by other terminators, otherwise
737 // we do not know how to split.
738 for (MachineBasicBlock::iterator It = MI, End = MI.getParent()->end();
740 // The machine verifier should reject this kind of code.
741 assert(It->modifiesRegister(Reg, &TRI) && "Do not know where to split");
742 // Split each outcoming edges.
743 MachineBasicBlock &Src = *MI.getParent();
744 for (auto &Succ : Src.successors())
745 addInsertPoint(Src, Succ);
749 void RegBankSelect::RepairingPlacement::addInsertPoint(MachineInstr &MI,
751 addInsertPoint(*new InstrInsertPoint(MI, Before));
754 void RegBankSelect::RepairingPlacement::addInsertPoint(MachineBasicBlock &MBB,
756 addInsertPoint(*new MBBInsertPoint(MBB, Beginning));
759 void RegBankSelect::RepairingPlacement::addInsertPoint(MachineBasicBlock &Src,
760 MachineBasicBlock &Dst) {
761 addInsertPoint(*new EdgeInsertPoint(Src, Dst, P));
764 void RegBankSelect::RepairingPlacement::addInsertPoint(
765 RegBankSelect::InsertPoint &Point) {
766 CanMaterialize &= Point.canMaterialize();
767 HasSplit |= Point.isSplit();
768 InsertPoints.emplace_back(&Point);
771 RegBankSelect::InstrInsertPoint::InstrInsertPoint(MachineInstr &Instr,
773 : InsertPoint(), Instr(Instr), Before(Before) {
774 // Since we do not support splitting, we do not need to update
775 // liveness and such, so do not do anything with P.
776 assert((!Before || !Instr.isPHI()) &&
777 "Splitting before phis requires more points");
778 assert((!Before || !Instr.getNextNode() || !Instr.getNextNode()->isPHI()) &&
779 "Splitting between phis does not make sense");
782 void RegBankSelect::InstrInsertPoint::materialize() {
784 // Slice and return the beginning of the new block.
785 // If we need to split between the terminators, we theoritically
786 // need to know where the first and second set of terminators end
787 // to update the successors properly.
788 // Now, in pratice, we should have a maximum of 2 branch
789 // instructions; one conditional and one unconditional. Therefore
790 // we know how to update the successor by looking at the target of
791 // the unconditional branch.
792 // If we end up splitting at some point, then, we should update
793 // the liveness information and such. I.e., we would need to
795 // The machine verifier should actually make sure such cases
797 llvm_unreachable("Not yet implemented");
799 // Otherwise the insertion point is just the current or next
800 // instruction depending on Before. I.e., there is nothing to do
804 bool RegBankSelect::InstrInsertPoint::isSplit() const {
805 // If the insertion point is after a terminator, we need to split.
807 return Instr.isTerminator();
808 // If we insert before an instruction that is after a terminator,
809 // we are still after a terminator.
810 return Instr.getPrevNode() && Instr.getPrevNode()->isTerminator();
813 uint64_t RegBankSelect::InstrInsertPoint::frequency(const Pass &P) const {
814 // Even if we need to split, because we insert between terminators,
815 // this split has actually the same frequency as the instruction.
816 const MachineBlockFrequencyInfo *MBFI =
817 P.getAnalysisIfAvailable<MachineBlockFrequencyInfo>();
820 return MBFI->getBlockFreq(Instr.getParent()).getFrequency();
823 uint64_t RegBankSelect::MBBInsertPoint::frequency(const Pass &P) const {
824 const MachineBlockFrequencyInfo *MBFI =
825 P.getAnalysisIfAvailable<MachineBlockFrequencyInfo>();
828 return MBFI->getBlockFreq(&MBB).getFrequency();
831 void RegBankSelect::EdgeInsertPoint::materialize() {
832 // If we end up repairing twice at the same place before materializing the
833 // insertion point, we may think we have to split an edge twice.
834 // We should have a factory for the insert point such that identical points
835 // are the same instance.
836 assert(Src.isSuccessor(DstOrSplit) && DstOrSplit->isPredecessor(&Src) &&
837 "This point has already been split");
838 MachineBasicBlock *NewBB = Src.SplitCriticalEdge(DstOrSplit, P);
839 assert(NewBB && "Invalid call to materialize");
840 // We reuse the destination block to hold the information of the new block.
844 uint64_t RegBankSelect::EdgeInsertPoint::frequency(const Pass &P) const {
845 const MachineBlockFrequencyInfo *MBFI =
846 P.getAnalysisIfAvailable<MachineBlockFrequencyInfo>();
850 return MBFI->getBlockFreq(DstOrSplit).getFrequency();
852 const MachineBranchProbabilityInfo *MBPI =
853 P.getAnalysisIfAvailable<MachineBranchProbabilityInfo>();
856 // The basic block will be on the edge.
857 return (MBFI->getBlockFreq(&Src) * MBPI->getEdgeProbability(&Src, DstOrSplit))
861 bool RegBankSelect::EdgeInsertPoint::canMaterialize() const {
862 // If this is not a critical edge, we should not have used this insert
863 // point. Indeed, either the successor or the predecessor should
865 assert(Src.succ_size() > 1 && DstOrSplit->pred_size() > 1 &&
866 "Edge is not critical");
867 return Src.canSplitCriticalEdge(DstOrSplit);
870 RegBankSelect::MappingCost::MappingCost(const BlockFrequency &LocalFreq)
871 : LocalFreq(LocalFreq.getFrequency()) {}
873 bool RegBankSelect::MappingCost::addLocalCost(uint64_t Cost) {
874 // Check if this overflows.
875 if (LocalCost + Cost < LocalCost) {
880 return isSaturated();
883 bool RegBankSelect::MappingCost::addNonLocalCost(uint64_t Cost) {
884 // Check if this overflows.
885 if (NonLocalCost + Cost < NonLocalCost) {
889 NonLocalCost += Cost;
890 return isSaturated();
893 bool RegBankSelect::MappingCost::isSaturated() const {
894 return LocalCost == UINT64_MAX - 1 && NonLocalCost == UINT64_MAX &&
895 LocalFreq == UINT64_MAX;
898 void RegBankSelect::MappingCost::saturate() {
899 *this = ImpossibleCost();
903 RegBankSelect::MappingCost RegBankSelect::MappingCost::ImpossibleCost() {
904 return MappingCost(UINT64_MAX, UINT64_MAX, UINT64_MAX);
907 bool RegBankSelect::MappingCost::operator<(const MappingCost &Cost) const {
908 // Sort out the easy cases.
911 // If one is impossible to realize the other is cheaper unless it is
912 // impossible as well.
913 if ((*this == ImpossibleCost()) || (Cost == ImpossibleCost()))
914 return (*this == ImpossibleCost()) < (Cost == ImpossibleCost());
915 // If one is saturated the other is cheaper, unless it is saturated
917 if (isSaturated() || Cost.isSaturated())
918 return isSaturated() < Cost.isSaturated();
919 // At this point we know both costs hold sensible values.
921 // If both values have a different base frequency, there is no much
922 // we can do but to scale everything.
923 // However, if they have the same base frequency we can avoid making
924 // complicated computation.
925 uint64_t ThisLocalAdjust;
926 uint64_t OtherLocalAdjust;
927 if (LLVM_LIKELY(LocalFreq == Cost.LocalFreq)) {
929 // At this point, we know the local costs are comparable.
930 // Do the case that do not involve potential overflow first.
931 if (NonLocalCost == Cost.NonLocalCost)
932 // Since the non-local costs do not discriminate on the result,
933 // just compare the local costs.
934 return LocalCost < Cost.LocalCost;
936 // The base costs are comparable so we may only keep the relative
937 // value to increase our chances of avoiding overflows.
939 OtherLocalAdjust = 0;
940 if (LocalCost < Cost.LocalCost)
941 OtherLocalAdjust = Cost.LocalCost - LocalCost;
943 ThisLocalAdjust = LocalCost - Cost.LocalCost;
945 ThisLocalAdjust = LocalCost;
946 OtherLocalAdjust = Cost.LocalCost;
949 // The non-local costs are comparable, just keep the relative value.
950 uint64_t ThisNonLocalAdjust = 0;
951 uint64_t OtherNonLocalAdjust = 0;
952 if (NonLocalCost < Cost.NonLocalCost)
953 OtherNonLocalAdjust = Cost.NonLocalCost - NonLocalCost;
955 ThisNonLocalAdjust = NonLocalCost - Cost.NonLocalCost;
956 // Scale everything to make them comparable.
957 uint64_t ThisScaledCost = ThisLocalAdjust * LocalFreq;
958 // Check for overflow on that operation.
959 bool ThisOverflows = ThisLocalAdjust && (ThisScaledCost < ThisLocalAdjust ||
960 ThisScaledCost < LocalFreq);
961 uint64_t OtherScaledCost = OtherLocalAdjust * Cost.LocalFreq;
962 // Check for overflow on the last operation.
963 bool OtherOverflows =
965 (OtherScaledCost < OtherLocalAdjust || OtherScaledCost < Cost.LocalFreq);
966 // Add the non-local costs.
967 ThisOverflows |= ThisNonLocalAdjust &&
968 ThisScaledCost + ThisNonLocalAdjust < ThisNonLocalAdjust;
969 ThisScaledCost += ThisNonLocalAdjust;
970 OtherOverflows |= OtherNonLocalAdjust &&
971 OtherScaledCost + OtherNonLocalAdjust < OtherNonLocalAdjust;
972 OtherScaledCost += OtherNonLocalAdjust;
973 // If both overflows, we cannot compare without additional
974 // precision, e.g., APInt. Just give up on that case.
975 if (ThisOverflows && OtherOverflows)
977 // If one overflows but not the other, we can still compare.
978 if (ThisOverflows || OtherOverflows)
979 return ThisOverflows < OtherOverflows;
980 // Otherwise, just compare the values.
981 return ThisScaledCost < OtherScaledCost;
984 bool RegBankSelect::MappingCost::operator==(const MappingCost &Cost) const {
985 return LocalCost == Cost.LocalCost && NonLocalCost == Cost.NonLocalCost &&
986 LocalFreq == Cost.LocalFreq;
989 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
990 LLVM_DUMP_METHOD void RegBankSelect::MappingCost::dump() const {
996 void RegBankSelect::MappingCost::print(raw_ostream &OS) const {
997 if (*this == ImpossibleCost()) {
1001 if (isSaturated()) {
1005 OS << LocalFreq << " * " << LocalCost << " + " << NonLocalCost;