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