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