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