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