LLVM  10.0.0svn
RegBankSelect.cpp
Go to the documentation of this file.
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 
14 #include "llvm/ADT/STLExtras.h"
15 #include "llvm/ADT/SmallVector.h"
32 #include "llvm/Config/llvm-config.h"
33 #include "llvm/IR/Attributes.h"
34 #include "llvm/IR/Function.h"
35 #include "llvm/Pass.h"
38 #include "llvm/Support/Compiler.h"
39 #include "llvm/Support/Debug.h"
42 #include <algorithm>
43 #include <cassert>
44 #include <cstdint>
45 #include <limits>
46 #include <memory>
47 #include <utility>
48 
49 #define DEBUG_TYPE "regbankselect"
50 
51 using namespace llvm;
52 
54  cl::desc("Mode of the RegBankSelect pass"), cl::Hidden, cl::Optional,
55  cl::values(clEnumValN(RegBankSelect::Mode::Fast, "regbankselect-fast",
56  "Run the Fast mode (default mapping)"),
57  clEnumValN(RegBankSelect::Mode::Greedy, "regbankselect-greedy",
58  "Use the Greedy mode (best local mapping)")));
59 
60 char RegBankSelect::ID = 0;
61 
63  "Assign register bank of generic virtual registers",
64  false, false);
69  "Assign register bank of generic virtual registers", false,
70  false)
71 
72 RegBankSelect::RegBankSelect(Mode RunningMode)
73  : MachineFunctionPass(ID), OptMode(RunningMode) {
74  if (RegBankSelectMode.getNumOccurrences() != 0) {
75  OptMode = RegBankSelectMode;
76  if (RegBankSelectMode != RunningMode)
77  LLVM_DEBUG(dbgs() << "RegBankSelect mode overrided by command line\n");
78  }
79 }
80 
81 void RegBankSelect::init(MachineFunction &MF) {
82  RBI = MF.getSubtarget().getRegBankInfo();
83  assert(RBI && "Cannot work without RegisterBankInfo");
84  MRI = &MF.getRegInfo();
85  TRI = MF.getSubtarget().getRegisterInfo();
86  TPC = &getAnalysis<TargetPassConfig>();
87  if (OptMode != Mode::Fast) {
88  MBFI = &getAnalysis<MachineBlockFrequencyInfo>();
89  MBPI = &getAnalysis<MachineBranchProbabilityInfo>();
90  } else {
91  MBFI = nullptr;
92  MBPI = nullptr;
93  }
94  MIRBuilder.setMF(MF);
95  MORE = std::make_unique<MachineOptimizationRemarkEmitter>(MF, MBFI);
96 }
97 
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.
104  }
108 }
109 
110 bool 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, *TRI);
121  const RegisterBank *DesiredRegBrank = ValMapping.BreakDown[0].RegBank;
122  // Reg is free of assignment, a simple assignment will make the
123  // register bank to match.
124  OnlyAssign = CurRegBank == nullptr;
125  LLVM_DEBUG(dbgs() << "Does assignment already match: ";
126  if (CurRegBank) dbgs() << *CurRegBank; else dbgs() << "none";
127  dbgs() << " against ";
128  assert(DesiredRegBrank && "The mapping must be valid");
129  dbgs() << *DesiredRegBrank << '\n';);
130  return CurRegBank == DesiredRegBrank;
131 }
132 
133 bool RegBankSelect::repairReg(
134  MachineOperand &MO, const RegisterBankInfo::ValueMapping &ValMapping,
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(Src, Dst);
155 
156  assert((RepairPt.getNumInsertPoints() == 1 ||
158  "We are about to create several defs for Dst");
159 
160  // Build the instruction used to repair, then clone it at the right
161  // places. Avoiding buildCopy bypasses the check that Src and Dst have the
162  // same types because the type is a placeholder when this function is called.
163  MI = MIRBuilder.buildInstrNoInsert(TargetOpcode::COPY)
164  .addDef(Dst)
165  .addUse(Src);
166  LLVM_DEBUG(dbgs() << "Copy: " << printReg(Src) << " to: " << printReg(Dst)
167  << '\n');
168  } else {
169  // TODO: Support with G_IMPLICIT_DEF + G_INSERT sequence or G_EXTRACT
170  // sequence.
171  assert(ValMapping.partsAllUniform() && "irregular breakdowns not supported");
172 
173  LLT RegTy = MRI->getType(MO.getReg());
174  if (MO.isDef()) {
175  unsigned MergeOp;
176  if (RegTy.isVector()) {
177  if (ValMapping.NumBreakDowns == RegTy.getNumElements())
178  MergeOp = TargetOpcode::G_BUILD_VECTOR;
179  else {
180  assert(
181  (ValMapping.BreakDown[0].Length * ValMapping.NumBreakDowns ==
182  RegTy.getSizeInBits()) &&
183  (ValMapping.BreakDown[0].Length % RegTy.getScalarSizeInBits() ==
184  0) &&
185  "don't understand this value breakdown");
186 
187  MergeOp = TargetOpcode::G_CONCAT_VECTORS;
188  }
189  } else
190  MergeOp = TargetOpcode::G_MERGE_VALUES;
191 
192  auto MergeBuilder =
193  MIRBuilder.buildInstrNoInsert(MergeOp)
194  .addDef(MO.getReg());
195 
196  for (Register SrcReg : NewVRegs)
197  MergeBuilder.addUse(SrcReg);
198 
199  MI = MergeBuilder;
200  } else {
201  MachineInstrBuilder UnMergeBuilder =
202  MIRBuilder.buildInstrNoInsert(TargetOpcode::G_UNMERGE_VALUES);
203  for (Register DefReg : NewVRegs)
204  UnMergeBuilder.addDef(DefReg);
205 
206  UnMergeBuilder.addUse(MO.getReg());
207  MI = UnMergeBuilder;
208  }
209  }
210 
211  if (RepairPt.getNumInsertPoints() != 1)
212  report_fatal_error("need testcase to support multiple insertion points");
213 
214  // TODO:
215  // Check if MI is legal. if not, we need to legalize all the
216  // instructions we are going to insert.
217  std::unique_ptr<MachineInstr *[]> NewInstrs(
218  new MachineInstr *[RepairPt.getNumInsertPoints()]);
219  bool IsFirst = true;
220  unsigned Idx = 0;
221  for (const std::unique_ptr<InsertPoint> &InsertPt : RepairPt) {
222  MachineInstr *CurMI;
223  if (IsFirst)
224  CurMI = MI;
225  else
226  CurMI = MIRBuilder.getMF().CloneMachineInstr(MI);
227  InsertPt->insert(*CurMI);
228  NewInstrs[Idx++] = CurMI;
229  IsFirst = false;
230  }
231  // TODO:
232  // Legalize NewInstrs if need be.
233  return true;
234 }
235 
236 uint64_t RegBankSelect::getRepairCost(
237  const MachineOperand &MO,
238  const RegisterBankInfo::ValueMapping &ValMapping) const {
239  assert(MO.isReg() && "We should only repair register operand");
240  assert(ValMapping.NumBreakDowns && "Nothing to map??");
241 
242  bool IsSameNumOfValues = ValMapping.NumBreakDowns == 1;
243  const RegisterBank *CurRegBank = RBI->getRegBank(MO.getReg(), *MRI, *TRI);
244  // If MO does not have a register bank, we should have just been
245  // able to set one unless we have to break the value down.
246  assert(CurRegBank || MO.isDef());
247 
248  // Def: Val <- NewDefs
249  // Same number of values: copy
250  // Different number: Val = build_sequence Defs1, Defs2, ...
251  // Use: NewSources <- Val.
252  // Same number of values: copy.
253  // Different number: Src1, Src2, ... =
254  // extract_value Val, Src1Begin, Src1Len, Src2Begin, Src2Len, ...
255  // We should remember that this value is available somewhere else to
256  // coalesce the value.
257 
258  if (ValMapping.NumBreakDowns != 1)
259  return RBI->getBreakDownCost(ValMapping, CurRegBank);
260 
261  if (IsSameNumOfValues) {
262  const RegisterBank *DesiredRegBrank = ValMapping.BreakDown[0].RegBank;
263  // If we repair a definition, swap the source and destination for
264  // the repairing.
265  if (MO.isDef())
266  std::swap(CurRegBank, DesiredRegBrank);
267  // TODO: It may be possible to actually avoid the copy.
268  // If we repair something where the source is defined by a copy
269  // and the source of that copy is on the right bank, we can reuse
270  // it for free.
271  // E.g.,
272  // RegToRepair<BankA> = copy AlternativeSrc<BankB>
273  // = op RegToRepair<BankA>
274  // We can simply propagate AlternativeSrc instead of copying RegToRepair
275  // into a new virtual register.
276  // We would also need to propagate this information in the
277  // repairing placement.
278  unsigned Cost = RBI->copyCost(*DesiredRegBrank, *CurRegBank,
279  RBI->getSizeInBits(MO.getReg(), *MRI, *TRI));
280  // TODO: use a dedicated constant for ImpossibleCost.
282  return Cost;
283  // Return the legalization cost of that repairing.
284  }
286 }
287 
288 const RegisterBankInfo::InstructionMapping &RegBankSelect::findBestMapping(
291  assert(!PossibleMappings.empty() &&
292  "Do not know how to map this instruction");
293 
294  const RegisterBankInfo::InstructionMapping *BestMapping = nullptr;
295  MappingCost Cost = MappingCost::ImpossibleCost();
296  SmallVector<RepairingPlacement, 4> LocalRepairPts;
297  for (const RegisterBankInfo::InstructionMapping *CurMapping :
298  PossibleMappings) {
299  MappingCost CurCost =
300  computeMapping(MI, *CurMapping, LocalRepairPts, &Cost);
301  if (CurCost < Cost) {
302  LLVM_DEBUG(dbgs() << "New best: " << CurCost << '\n');
303  Cost = CurCost;
304  BestMapping = CurMapping;
305  RepairPts.clear();
306  for (RepairingPlacement &RepairPt : LocalRepairPts)
307  RepairPts.emplace_back(std::move(RepairPt));
308  }
309  }
310  if (!BestMapping && !TPC->isGlobalISelAbortEnabled()) {
311  // If none of the mapping worked that means they are all impossible.
312  // Thus, pick the first one and set an impossible repairing point.
313  // It will trigger the failed isel mode.
314  BestMapping = *PossibleMappings.begin();
315  RepairPts.emplace_back(
317  } else
318  assert(BestMapping && "No suitable mapping for instruction");
319  return *BestMapping;
320 }
321 
322 void RegBankSelect::tryAvoidingSplit(
324  const RegisterBankInfo::ValueMapping &ValMapping) const {
325  const MachineInstr &MI = *MO.getParent();
326  assert(RepairPt.hasSplit() && "We should not have to adjust for split");
327  // Splitting should only occur for PHIs or between terminators,
328  // because we only do local repairing.
329  assert((MI.isPHI() || MI.isTerminator()) && "Why do we split?");
330 
331  assert(&MI.getOperand(RepairPt.getOpIdx()) == &MO &&
332  "Repairing placement does not match operand");
333 
334  // If we need splitting for phis, that means it is because we
335  // could not find an insertion point before the terminators of
336  // the predecessor block for this argument. In other words,
337  // the input value is defined by one of the terminators.
338  assert((!MI.isPHI() || !MO.isDef()) && "Need split for phi def?");
339 
340  // We split to repair the use of a phi or a terminator.
341  if (!MO.isDef()) {
342  if (MI.isTerminator()) {
343  assert(&MI != &(*MI.getParent()->getFirstTerminator()) &&
344  "Need to split for the first terminator?!");
345  } else {
346  // For the PHI case, the split may not be actually required.
347  // In the copy case, a phi is already a copy on the incoming edge,
348  // therefore there is no need to split.
349  if (ValMapping.NumBreakDowns == 1)
350  // This is a already a copy, there is nothing to do.
352  }
353  return;
354  }
355 
356  // At this point, we need to repair a defintion of a terminator.
357 
358  // Technically we need to fix the def of MI on all outgoing
359  // edges of MI to keep the repairing local. In other words, we
360  // will create several definitions of the same register. This
361  // does not work for SSA unless that definition is a physical
362  // register.
363  // However, there are other cases where we can get away with
364  // that while still keeping the repairing local.
365  assert(MI.isTerminator() && MO.isDef() &&
366  "This code is for the def of a terminator");
367 
368  // Since we use RPO traversal, if we need to repair a definition
369  // this means this definition could be:
370  // 1. Used by PHIs (i.e., this VReg has been visited as part of the
371  // uses of a phi.), or
372  // 2. Part of a target specific instruction (i.e., the target applied
373  // some register class constraints when creating the instruction.)
374  // If the constraints come for #2, the target said that another mapping
375  // is supported so we may just drop them. Indeed, if we do not change
376  // the number of registers holding that value, the uses will get fixed
377  // when we get to them.
378  // Uses in PHIs may have already been proceeded though.
379  // If the constraints come for #1, then, those are weak constraints and
380  // no actual uses may rely on them. However, the problem remains mainly
381  // the same as for #2. If the value stays in one register, we could
382  // just switch the register bank of the definition, but we would need to
383  // account for a repairing cost for each phi we silently change.
384  //
385  // In any case, if the value needs to be broken down into several
386  // registers, the repairing is not local anymore as we need to patch
387  // every uses to rebuild the value in just one register.
388  //
389  // To summarize:
390  // - If the value is in a physical register, we can do the split and
391  // fix locally.
392  // Otherwise if the value is in a virtual register:
393  // - If the value remains in one register, we do not have to split
394  // just switching the register bank would do, but we need to account
395  // in the repairing cost all the phi we changed.
396  // - If the value spans several registers, then we cannot do a local
397  // repairing.
398 
399  // Check if this is a physical or virtual register.
400  Register Reg = MO.getReg();
401  if (Register::isPhysicalRegister(Reg)) {
402  // We are going to split every outgoing edges.
403  // Check that this is possible.
404  // FIXME: The machine representation is currently broken
405  // since it also several terminators in one basic block.
406  // Because of that we would technically need a way to get
407  // the targets of just one terminator to know which edges
408  // we have to split.
409  // Assert that we do not hit the ill-formed representation.
410 
411  // If there are other terminators before that one, some of
412  // the outgoing edges may not be dominated by this definition.
413  assert(&MI == &(*MI.getParent()->getFirstTerminator()) &&
414  "Do not know which outgoing edges are relevant");
415  const MachineInstr *Next = MI.getNextNode();
416  assert((!Next || Next->isUnconditionalBranch()) &&
417  "Do not know where each terminator ends up");
418  if (Next)
419  // If the next terminator uses Reg, this means we have
420  // to split right after MI and thus we need a way to ask
421  // which outgoing edges are affected.
422  assert(!Next->readsRegister(Reg) && "Need to split between terminators");
423  // We will split all the edges and repair there.
424  } else {
425  // This is a virtual register defined by a terminator.
426  if (ValMapping.NumBreakDowns == 1) {
427  // There is nothing to repair, but we may actually lie on
428  // the repairing cost because of the PHIs already proceeded
429  // as already stated.
430  // Though the code will be correct.
431  assert(false && "Repairing cost may not be accurate");
432  } else {
433  // We need to do non-local repairing. Basically, patch all
434  // the uses (i.e., phis) that we already proceeded.
435  // For now, just say this mapping is not possible.
436  RepairPt.switchTo(RepairingPlacement::RepairingKind::Impossible);
437  }
438  }
439 }
440 
441 RegBankSelect::MappingCost RegBankSelect::computeMapping(
442  MachineInstr &MI, const RegisterBankInfo::InstructionMapping &InstrMapping,
444  const RegBankSelect::MappingCost *BestCost) {
445  assert((MBFI || !BestCost) && "Costs comparison require MBFI");
446 
447  if (!InstrMapping.isValid())
448  return MappingCost::ImpossibleCost();
449 
450  // If mapped with InstrMapping, MI will have the recorded cost.
451  MappingCost Cost(MBFI ? MBFI->getBlockFreq(MI.getParent()) : 1);
452  bool Saturated = Cost.addLocalCost(InstrMapping.getCost());
453  assert(!Saturated && "Possible mapping saturated the cost");
454  LLVM_DEBUG(dbgs() << "Evaluating mapping cost for: " << MI);
455  LLVM_DEBUG(dbgs() << "With: " << InstrMapping << '\n');
456  RepairPts.clear();
457  if (BestCost && Cost > *BestCost) {
458  LLVM_DEBUG(dbgs() << "Mapping is too expensive from the start\n");
459  return Cost;
460  }
461 
462  // Moreover, to realize this mapping, the register bank of each operand must
463  // match this mapping. In other words, we may need to locally reassign the
464  // register banks. Account for that repairing cost as well.
465  // In this context, local means in the surrounding of MI.
466  for (unsigned OpIdx = 0, EndOpIdx = InstrMapping.getNumOperands();
467  OpIdx != EndOpIdx; ++OpIdx) {
468  const MachineOperand &MO = MI.getOperand(OpIdx);
469  if (!MO.isReg())
470  continue;
471  Register Reg = MO.getReg();
472  if (!Reg)
473  continue;
474  LLVM_DEBUG(dbgs() << "Opd" << OpIdx << '\n');
475  const RegisterBankInfo::ValueMapping &ValMapping =
476  InstrMapping.getOperandMapping(OpIdx);
477  // If Reg is already properly mapped, this is free.
478  bool Assign;
479  if (assignmentMatch(Reg, ValMapping, Assign)) {
480  LLVM_DEBUG(dbgs() << "=> is free (match).\n");
481  continue;
482  }
483  if (Assign) {
484  LLVM_DEBUG(dbgs() << "=> is free (simple assignment).\n");
485  RepairPts.emplace_back(RepairingPlacement(MI, OpIdx, *TRI, *this,
487  continue;
488  }
489 
490  // Find the insertion point for the repairing code.
491  RepairPts.emplace_back(
492  RepairingPlacement(MI, OpIdx, *TRI, *this, RepairingPlacement::Insert));
493  RepairingPlacement &RepairPt = RepairPts.back();
494 
495  // If we need to split a basic block to materialize this insertion point,
496  // we may give a higher cost to this mapping.
497  // Nevertheless, we may get away with the split, so try that first.
498  if (RepairPt.hasSplit())
499  tryAvoidingSplit(RepairPt, MO, ValMapping);
500 
501  // Check that the materialization of the repairing is possible.
502  if (!RepairPt.canMaterialize()) {
503  LLVM_DEBUG(dbgs() << "Mapping involves impossible repairing\n");
504  return MappingCost::ImpossibleCost();
505  }
506 
507  // Account for the split cost and repair cost.
508  // Unless the cost is already saturated or we do not care about the cost.
509  if (!BestCost || Saturated)
510  continue;
511 
512  // To get accurate information we need MBFI and MBPI.
513  // Thus, if we end up here this information should be here.
514  assert(MBFI && MBPI && "Cost computation requires MBFI and MBPI");
515 
516  // FIXME: We will have to rework the repairing cost model.
517  // The repairing cost depends on the register bank that MO has.
518  // However, when we break down the value into different values,
519  // MO may not have a register bank while still needing repairing.
520  // For the fast mode, we don't compute the cost so that is fine,
521  // but still for the repairing code, we will have to make a choice.
522  // For the greedy mode, we should choose greedily what is the best
523  // choice based on the next use of MO.
524 
525  // Sums up the repairing cost of MO at each insertion point.
526  uint64_t RepairCost = getRepairCost(MO, ValMapping);
527 
528  // This is an impossible to repair cost.
529  if (RepairCost == std::numeric_limits<unsigned>::max())
530  return MappingCost::ImpossibleCost();
531 
532  // Bias used for splitting: 5%.
533  const uint64_t PercentageForBias = 5;
534  uint64_t Bias = (RepairCost * PercentageForBias + 99) / 100;
535  // We should not need more than a couple of instructions to repair
536  // an assignment. In other words, the computation should not
537  // overflow because the repairing cost is free of basic block
538  // frequency.
539  assert(((RepairCost < RepairCost * PercentageForBias) &&
540  (RepairCost * PercentageForBias <
541  RepairCost * PercentageForBias + 99)) &&
542  "Repairing involves more than a billion of instructions?!");
543  for (const std::unique_ptr<InsertPoint> &InsertPt : RepairPt) {
544  assert(InsertPt->canMaterialize() && "We should not have made it here");
545  // We will applied some basic block frequency and those uses uint64_t.
546  if (!InsertPt->isSplit())
547  Saturated = Cost.addLocalCost(RepairCost);
548  else {
549  uint64_t CostForInsertPt = RepairCost;
550  // Again we shouldn't overflow here givent that
551  // CostForInsertPt is frequency free at this point.
552  assert(CostForInsertPt + Bias > CostForInsertPt &&
553  "Repairing + split bias overflows");
554  CostForInsertPt += Bias;
555  uint64_t PtCost = InsertPt->frequency(*this) * CostForInsertPt;
556  // Check if we just overflowed.
557  if ((Saturated = PtCost < CostForInsertPt))
558  Cost.saturate();
559  else
560  Saturated = Cost.addNonLocalCost(PtCost);
561  }
562 
563  // Stop looking into what it takes to repair, this is already
564  // too expensive.
565  if (BestCost && Cost > *BestCost) {
566  LLVM_DEBUG(dbgs() << "Mapping is too expensive, stop processing\n");
567  return Cost;
568  }
569 
570  // No need to accumulate more cost information.
571  // We need to still gather the repairing information though.
572  if (Saturated)
573  break;
574  }
575  }
576  LLVM_DEBUG(dbgs() << "Total cost is: " << Cost << "\n");
577  return Cost;
578 }
579 
580 bool RegBankSelect::applyMapping(
581  MachineInstr &MI, const RegisterBankInfo::InstructionMapping &InstrMapping,
583  // OpdMapper will hold all the information needed for the rewriting.
584  RegisterBankInfo::OperandsMapper OpdMapper(MI, InstrMapping, *MRI);
585 
586  // First, place the repairing code.
587  for (RepairingPlacement &RepairPt : RepairPts) {
588  if (!RepairPt.canMaterialize() ||
590  return false;
591  assert(RepairPt.getKind() != RepairingPlacement::None &&
592  "This should not make its way in the list");
593  unsigned OpIdx = RepairPt.getOpIdx();
594  MachineOperand &MO = MI.getOperand(OpIdx);
595  const RegisterBankInfo::ValueMapping &ValMapping =
596  InstrMapping.getOperandMapping(OpIdx);
597  Register Reg = MO.getReg();
598 
599  switch (RepairPt.getKind()) {
601  assert(ValMapping.NumBreakDowns == 1 &&
602  "Reassignment should only be for simple mapping");
603  MRI->setRegBank(Reg, *ValMapping.BreakDown[0].RegBank);
604  break;
606  OpdMapper.createVRegs(OpIdx);
607  if (!repairReg(MO, ValMapping, RepairPt, OpdMapper.getVRegs(OpIdx)))
608  return false;
609  break;
610  default:
611  llvm_unreachable("Other kind should not happen");
612  }
613  }
614 
615  // Second, rewrite the instruction.
616  LLVM_DEBUG(dbgs() << "Actual mapping of the operands: " << OpdMapper << '\n');
617  RBI->applyMapping(OpdMapper);
618 
619  return true;
620 }
621 
622 bool RegBankSelect::assignInstr(MachineInstr &MI) {
623  LLVM_DEBUG(dbgs() << "Assign: " << MI);
624  // Remember the repairing placement for all the operands.
626 
627  const RegisterBankInfo::InstructionMapping *BestMapping;
628  if (OptMode == RegBankSelect::Mode::Fast) {
629  BestMapping = &RBI->getInstrMapping(MI);
630  MappingCost DefaultCost = computeMapping(MI, *BestMapping, RepairPts);
631  (void)DefaultCost;
632  if (DefaultCost == MappingCost::ImpossibleCost())
633  return false;
634  } else {
635  RegisterBankInfo::InstructionMappings PossibleMappings =
636  RBI->getInstrPossibleMappings(MI);
637  if (PossibleMappings.empty())
638  return false;
639  BestMapping = &findBestMapping(MI, PossibleMappings, RepairPts);
640  }
641  // Make sure the mapping is valid for MI.
642  assert(BestMapping->verify(MI) && "Invalid instruction mapping");
643 
644  LLVM_DEBUG(dbgs() << "Best Mapping: " << *BestMapping << '\n');
645 
646  // After this call, MI may not be valid anymore.
647  // Do not use it.
648  return applyMapping(MI, *BestMapping, RepairPts);
649 }
650 
652  // If the ISel pipeline failed, do not bother running that pass.
653  if (MF.getProperties().hasProperty(
655  return false;
656 
657  LLVM_DEBUG(dbgs() << "Assign register banks for: " << MF.getName() << '\n');
658  const Function &F = MF.getFunction();
659  Mode SaveOptMode = OptMode;
660  if (F.hasOptNone())
661  OptMode = Mode::Fast;
662  init(MF);
663 
664 #ifndef NDEBUG
665  // Check that our input is fully legal: we require the function to have the
666  // Legalized property, so it should be.
667  // FIXME: This should be in the MachineVerifier.
669  if (const MachineInstr *MI = machineFunctionIsIllegal(MF)) {
670  reportGISelFailure(MF, *TPC, *MORE, "gisel-regbankselect",
671  "instruction is not legal", *MI);
672  return false;
673  }
674 #endif
675 
676  // Walk the function and assign register banks to all operands.
677  // Use a RPOT to make sure all registers are assigned before we choose
678  // the best mapping of the current instruction.
680  for (MachineBasicBlock *MBB : RPOT) {
681  // Set a sensible insertion point so that subsequent calls to
682  // MIRBuilder.
683  MIRBuilder.setMBB(*MBB);
684  for (MachineBasicBlock::iterator MII = MBB->begin(), End = MBB->end();
685  MII != End;) {
686  // MI might be invalidated by the assignment, so move the
687  // iterator before hand.
688  MachineInstr &MI = *MII++;
689 
690  // Ignore target-specific post-isel instructions: they should use proper
691  // regclasses.
693  continue;
694 
695  if (!assignInstr(MI)) {
696  reportGISelFailure(MF, *TPC, *MORE, "gisel-regbankselect",
697  "unable to map instruction", MI);
698  return false;
699  }
700 
701  // It's possible the mapping changed control flow, and moved the following
702  // instruction to a new block, so figure out the new parent.
703  if (MII != End) {
704  MachineBasicBlock *NextInstBB = MII->getParent();
705  if (NextInstBB != MBB) {
706  LLVM_DEBUG(dbgs() << "Instruction mapping changed control flow\n");
707  MBB = NextInstBB;
708  MIRBuilder.setMBB(*MBB);
709  End = MBB->end();
710  }
711  }
712  }
713  }
714 
715  OptMode = SaveOptMode;
716  return false;
717 }
718 
719 //------------------------------------------------------------------------------
720 // Helper Classes Implementation
721 //------------------------------------------------------------------------------
723  MachineInstr &MI, unsigned OpIdx, const TargetRegisterInfo &TRI, Pass &P,
725  // Default is, we are going to insert code to repair OpIdx.
726  : Kind(Kind), OpIdx(OpIdx),
727  CanMaterialize(Kind != RepairingKind::Impossible), P(P) {
728  const MachineOperand &MO = MI.getOperand(OpIdx);
729  assert(MO.isReg() && "Trying to repair a non-reg operand");
730 
731  if (Kind != RepairingKind::Insert)
732  return;
733 
734  // Repairings for definitions happen after MI, uses happen before.
735  bool Before = !MO.isDef();
736 
737  // Check if we are done with MI.
738  if (!MI.isPHI() && !MI.isTerminator()) {
739  addInsertPoint(MI, Before);
740  // We are done with the initialization.
741  return;
742  }
743 
744  // Now, look for the special cases.
745  if (MI.isPHI()) {
746  // - PHI must be the first instructions:
747  // * Before, we have to split the related incoming edge.
748  // * After, move the insertion point past the last phi.
749  if (!Before) {
751  if (It != MI.getParent()->end())
752  addInsertPoint(*It, /*Before*/ true);
753  else
754  addInsertPoint(*(--It), /*Before*/ false);
755  return;
756  }
757  // We repair a use of a phi, we may need to split the related edge.
758  MachineBasicBlock &Pred = *MI.getOperand(OpIdx + 1).getMBB();
759  // Check if we can move the insertion point prior to the
760  // terminators of the predecessor.
761  Register Reg = MO.getReg();
763  for (auto Begin = Pred.begin(); It != Begin && It->isTerminator(); --It)
764  if (It->modifiesRegister(Reg, &TRI)) {
765  // We cannot hoist the repairing code in the predecessor.
766  // Split the edge.
767  addInsertPoint(Pred, *MI.getParent());
768  return;
769  }
770  // At this point, we can insert in Pred.
771 
772  // - If It is invalid, Pred is empty and we can insert in Pred
773  // wherever we want.
774  // - If It is valid, It is the first non-terminator, insert after It.
775  if (It == Pred.end())
776  addInsertPoint(Pred, /*Beginning*/ false);
777  else
778  addInsertPoint(*It, /*Before*/ false);
779  } else {
780  // - Terminators must be the last instructions:
781  // * Before, move the insert point before the first terminator.
782  // * After, we have to split the outcoming edges.
783  if (Before) {
784  // Check whether Reg is defined by any terminator.
786  auto REnd = MI.getParent()->rend();
787 
788  for (; It != REnd && It->isTerminator(); ++It) {
789  assert(!It->modifiesRegister(MO.getReg(), &TRI) &&
790  "copy insertion in middle of terminators not handled");
791  }
792 
793  if (It == REnd) {
794  addInsertPoint(*MI.getParent()->begin(), true);
795  return;
796  }
797 
798  // We are sure to be right before the first terminator.
799  addInsertPoint(*It, /*Before*/ false);
800  return;
801  }
802  // Make sure Reg is not redefined by other terminators, otherwise
803  // we do not know how to split.
804  for (MachineBasicBlock::iterator It = MI, End = MI.getParent()->end();
805  ++It != End;)
806  // The machine verifier should reject this kind of code.
807  assert(It->modifiesRegister(MO.getReg(), &TRI) &&
808  "Do not know where to split");
809  // Split each outcoming edges.
810  MachineBasicBlock &Src = *MI.getParent();
811  for (auto &Succ : Src.successors())
812  addInsertPoint(Src, Succ);
813  }
814 }
815 
817  bool Before) {
818  addInsertPoint(*new InstrInsertPoint(MI, Before));
819 }
820 
822  bool Beginning) {
823  addInsertPoint(*new MBBInsertPoint(MBB, Beginning));
824 }
825 
827  MachineBasicBlock &Dst) {
828  addInsertPoint(*new EdgeInsertPoint(Src, Dst, P));
829 }
830 
833  CanMaterialize &= Point.canMaterialize();
834  HasSplit |= Point.isSplit();
835  InsertPoints.emplace_back(&Point);
836 }
837 
839  bool Before)
840  : InsertPoint(), Instr(Instr), Before(Before) {
841  // Since we do not support splitting, we do not need to update
842  // liveness and such, so do not do anything with P.
843  assert((!Before || !Instr.isPHI()) &&
844  "Splitting before phis requires more points");
845  assert((!Before || !Instr.getNextNode() || !Instr.getNextNode()->isPHI()) &&
846  "Splitting between phis does not make sense");
847 }
848 
849 void RegBankSelect::InstrInsertPoint::materialize() {
850  if (isSplit()) {
851  // Slice and return the beginning of the new block.
852  // If we need to split between the terminators, we theoritically
853  // need to know where the first and second set of terminators end
854  // to update the successors properly.
855  // Now, in pratice, we should have a maximum of 2 branch
856  // instructions; one conditional and one unconditional. Therefore
857  // we know how to update the successor by looking at the target of
858  // the unconditional branch.
859  // If we end up splitting at some point, then, we should update
860  // the liveness information and such. I.e., we would need to
861  // access P here.
862  // The machine verifier should actually make sure such cases
863  // cannot happen.
864  llvm_unreachable("Not yet implemented");
865  }
866  // Otherwise the insertion point is just the current or next
867  // instruction depending on Before. I.e., there is nothing to do
868  // here.
869 }
870 
872  // If the insertion point is after a terminator, we need to split.
873  if (!Before)
874  return Instr.isTerminator();
875  // If we insert before an instruction that is after a terminator,
876  // we are still after a terminator.
877  return Instr.getPrevNode() && Instr.getPrevNode()->isTerminator();
878 }
879 
881  // Even if we need to split, because we insert between terminators,
882  // this split has actually the same frequency as the instruction.
883  const MachineBlockFrequencyInfo *MBFI =
885  if (!MBFI)
886  return 1;
887  return MBFI->getBlockFreq(Instr.getParent()).getFrequency();
888 }
889 
891  const MachineBlockFrequencyInfo *MBFI =
893  if (!MBFI)
894  return 1;
895  return MBFI->getBlockFreq(&MBB).getFrequency();
896 }
897 
898 void RegBankSelect::EdgeInsertPoint::materialize() {
899  // If we end up repairing twice at the same place before materializing the
900  // insertion point, we may think we have to split an edge twice.
901  // We should have a factory for the insert point such that identical points
902  // are the same instance.
903  assert(Src.isSuccessor(DstOrSplit) && DstOrSplit->isPredecessor(&Src) &&
904  "This point has already been split");
905  MachineBasicBlock *NewBB = Src.SplitCriticalEdge(DstOrSplit, P);
906  assert(NewBB && "Invalid call to materialize");
907  // We reuse the destination block to hold the information of the new block.
908  DstOrSplit = NewBB;
909 }
910 
912  const MachineBlockFrequencyInfo *MBFI =
914  if (!MBFI)
915  return 1;
916  if (WasMaterialized)
917  return MBFI->getBlockFreq(DstOrSplit).getFrequency();
918 
919  const MachineBranchProbabilityInfo *MBPI =
921  if (!MBPI)
922  return 1;
923  // The basic block will be on the edge.
924  return (MBFI->getBlockFreq(&Src) * MBPI->getEdgeProbability(&Src, DstOrSplit))
925  .getFrequency();
926 }
927 
929  // If this is not a critical edge, we should not have used this insert
930  // point. Indeed, either the successor or the predecessor should
931  // have do.
932  assert(Src.succ_size() > 1 && DstOrSplit->pred_size() > 1 &&
933  "Edge is not critical");
934  return Src.canSplitCriticalEdge(DstOrSplit);
935 }
936 
937 RegBankSelect::MappingCost::MappingCost(const BlockFrequency &LocalFreq)
938  : LocalFreq(LocalFreq.getFrequency()) {}
939 
940 bool RegBankSelect::MappingCost::addLocalCost(uint64_t Cost) {
941  // Check if this overflows.
942  if (LocalCost + Cost < LocalCost) {
943  saturate();
944  return true;
945  }
946  LocalCost += Cost;
947  return isSaturated();
948 }
949 
950 bool RegBankSelect::MappingCost::addNonLocalCost(uint64_t Cost) {
951  // Check if this overflows.
952  if (NonLocalCost + Cost < NonLocalCost) {
953  saturate();
954  return true;
955  }
956  NonLocalCost += Cost;
957  return isSaturated();
958 }
959 
960 bool RegBankSelect::MappingCost::isSaturated() const {
961  return LocalCost == UINT64_MAX - 1 && NonLocalCost == UINT64_MAX &&
962  LocalFreq == UINT64_MAX;
963 }
964 
965 void RegBankSelect::MappingCost::saturate() {
966  *this = ImpossibleCost();
967  --LocalCost;
968 }
969 
970 RegBankSelect::MappingCost RegBankSelect::MappingCost::ImpossibleCost() {
971  return MappingCost(UINT64_MAX, UINT64_MAX, UINT64_MAX);
972 }
973 
974 bool RegBankSelect::MappingCost::operator<(const MappingCost &Cost) const {
975  // Sort out the easy cases.
976  if (*this == Cost)
977  return false;
978  // If one is impossible to realize the other is cheaper unless it is
979  // impossible as well.
980  if ((*this == ImpossibleCost()) || (Cost == ImpossibleCost()))
981  return (*this == ImpossibleCost()) < (Cost == ImpossibleCost());
982  // If one is saturated the other is cheaper, unless it is saturated
983  // as well.
984  if (isSaturated() || Cost.isSaturated())
985  return isSaturated() < Cost.isSaturated();
986  // At this point we know both costs hold sensible values.
987 
988  // If both values have a different base frequency, there is no much
989  // we can do but to scale everything.
990  // However, if they have the same base frequency we can avoid making
991  // complicated computation.
992  uint64_t ThisLocalAdjust;
993  uint64_t OtherLocalAdjust;
994  if (LLVM_LIKELY(LocalFreq == Cost.LocalFreq)) {
995 
996  // At this point, we know the local costs are comparable.
997  // Do the case that do not involve potential overflow first.
998  if (NonLocalCost == Cost.NonLocalCost)
999  // Since the non-local costs do not discriminate on the result,
1000  // just compare the local costs.
1001  return LocalCost < Cost.LocalCost;
1002 
1003  // The base costs are comparable so we may only keep the relative
1004  // value to increase our chances of avoiding overflows.
1005  ThisLocalAdjust = 0;
1006  OtherLocalAdjust = 0;
1007  if (LocalCost < Cost.LocalCost)
1008  OtherLocalAdjust = Cost.LocalCost - LocalCost;
1009  else
1010  ThisLocalAdjust = LocalCost - Cost.LocalCost;
1011  } else {
1012  ThisLocalAdjust = LocalCost;
1013  OtherLocalAdjust = Cost.LocalCost;
1014  }
1015 
1016  // The non-local costs are comparable, just keep the relative value.
1017  uint64_t ThisNonLocalAdjust = 0;
1018  uint64_t OtherNonLocalAdjust = 0;
1019  if (NonLocalCost < Cost.NonLocalCost)
1020  OtherNonLocalAdjust = Cost.NonLocalCost - NonLocalCost;
1021  else
1022  ThisNonLocalAdjust = NonLocalCost - Cost.NonLocalCost;
1023  // Scale everything to make them comparable.
1024  uint64_t ThisScaledCost = ThisLocalAdjust * LocalFreq;
1025  // Check for overflow on that operation.
1026  bool ThisOverflows = ThisLocalAdjust && (ThisScaledCost < ThisLocalAdjust ||
1027  ThisScaledCost < LocalFreq);
1028  uint64_t OtherScaledCost = OtherLocalAdjust * Cost.LocalFreq;
1029  // Check for overflow on the last operation.
1030  bool OtherOverflows =
1031  OtherLocalAdjust &&
1032  (OtherScaledCost < OtherLocalAdjust || OtherScaledCost < Cost.LocalFreq);
1033  // Add the non-local costs.
1034  ThisOverflows |= ThisNonLocalAdjust &&
1035  ThisScaledCost + ThisNonLocalAdjust < ThisNonLocalAdjust;
1036  ThisScaledCost += ThisNonLocalAdjust;
1037  OtherOverflows |= OtherNonLocalAdjust &&
1038  OtherScaledCost + OtherNonLocalAdjust < OtherNonLocalAdjust;
1039  OtherScaledCost += OtherNonLocalAdjust;
1040  // If both overflows, we cannot compare without additional
1041  // precision, e.g., APInt. Just give up on that case.
1042  if (ThisOverflows && OtherOverflows)
1043  return false;
1044  // If one overflows but not the other, we can still compare.
1045  if (ThisOverflows || OtherOverflows)
1046  return ThisOverflows < OtherOverflows;
1047  // Otherwise, just compare the values.
1048  return ThisScaledCost < OtherScaledCost;
1049 }
1050 
1051 bool RegBankSelect::MappingCost::operator==(const MappingCost &Cost) const {
1052  return LocalCost == Cost.LocalCost && NonLocalCost == Cost.NonLocalCost &&
1053  LocalFreq == Cost.LocalFreq;
1054 }
1055 
1056 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1058  print(dbgs());
1059  dbgs() << '\n';
1060 }
1061 #endif
1062 
1064  if (*this == ImpossibleCost()) {
1065  OS << "impossible";
1066  return;
1067  }
1068  if (isSaturated()) {
1069  OS << "saturated";
1070  return;
1071  }
1072  OS << LocalFreq << " * " << LocalCost << " + " << NonLocalCost;
1073 }
Pass interface - Implemented by all &#39;passes&#39;.
Definition: Pass.h:80
reference emplace_back(ArgTypes &&... Args)
Definition: SmallVector.h:641
bool canMaterialize() const override
Check whether this insertion point can be materialized.
MachineInstr * getParent()
getParent - Return the instruction that this operand belongs to.
typename SuperClass::const_iterator const_iterator
Definition: SmallVector.h:320
MachineBasicBlock * getMBB() const
SI Whole Quad Mode
NodeTy * getNextNode()
Get the next node, or nullptr for the list tail.
Definition: ilist_node.h:288
LLVM_ATTRIBUTE_NORETURN void report_fatal_error(Error Err, bool gen_crash_diag=true)
Report a serious error, calling any installed error handler.
Definition: Error.cpp:139
This class represents lattice values for constants.
Definition: AllocatorList.h:23
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds...
Definition: Compiler.h:484
void getSelectionDAGFallbackAnalysisUsage(AnalysisUsage &AU)
Modify analysis usage so it preserves passes required for the SelectionDAG fallback.
Definition: Utils.cpp:431
#define LLVM_LIKELY(EXPR)
Definition: Compiler.h:211
virtual const TargetRegisterInfo * getRegisterInfo() const
getRegisterInfo - If register information is available, return it.
INITIALIZE_PASS_BEGIN(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false)
const MachineFunctionProperties & getProperties() const
Get the function properties.
Helper class that represents how the value of an instruction may be mapped and what is the related co...
unsigned getCost() const
Get the cost.
static bool isPhysicalRegister(unsigned Reg)
Return true if the specified register number is in the physical register namespace.
Definition: Register.h:63
iterator getFirstTerminator()
Returns an iterator to the first terminator instruction of this basic block.
Reparing code needs to happen before InsertPoints.
unsigned Reg
uint64_t getFrequency() const
Returns the frequency as a fixpoint number scaled by the entry frequency.
MachineBlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate machine basic b...
LLT getType(unsigned Reg) const
Get the low-level type of Reg or LLT{} if Reg is not a generic (target independent) virtual register...
static void dump(StringRef Title, SpillInfo const &Spills)
Definition: CoroFrame.cpp:322
Helper class used to get/create the virtual registers that will be used to replace the MachineOperand...
virtual const RegisterBankInfo * getRegBankInfo() const
If the information for the register banks is available, return it.
F(f)
Printable printReg(Register Reg, const TargetRegisterInfo *TRI=nullptr, unsigned SubIdx=0, const MachineRegisterInfo *MRI=nullptr)
Prints virtual and physical registers with or without a TRI instance.
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
void setRegBank(unsigned Reg, const RegisterBank &RegBank)
Set the register bank to RegBank for Reg.
bool isPHI() const
Mode
List of the modes supported by the RegBankSelect pass.
Definition: RegBankSelect.h:95
void switchTo(RepairingKind NewKind)
Change the type of this repairing placement to NewKind.
iterator_range< succ_iterator > successors()
const PartialMapping * BreakDown
How the value is broken down between the different register banks.
void setMF(MachineFunction &MF)
AnalysisUsage & addRequired()
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:50
Mark this repairing placement as impossible.
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
Abstract class used to represent an insertion point in a CFG.
virtual unsigned getBreakDownCost(const ValueMapping &ValMapping, const RegisterBank *CurBank=nullptr) const
Get the cost of using ValMapping to decompose a register.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:41
bool isTerminator(QueryType Type=AnyInBundle) const
Returns true if this instruction part of the terminator for a basic block.
Definition: MachineInstr.h:672
RepairingKind
Define the kind of action this repairing needs.
This file contains the simple types necessary to represent the attributes associated with functions a...
unsigned getOpcode() const
Returns the opcode of this MachineInstr.
Definition: MachineInstr.h:410
const MachineInstrBuilder & addDef(Register RegNo, unsigned Flags=0, unsigned SubReg=0) const
Add a virtual register definition operand.
Target-Independent Code Generator Pass Configuration Options.
#define UINT64_MAX
Definition: DataTypes.h:83
iterator_range< SmallVectorImpl< Register >::const_iterator > getVRegs(unsigned OpIdx, bool ForDebug=false) const
Get all the virtual registers required to map the OpIdx-th operand of the instruction.
MachineInstrBuilder buildInstrNoInsert(unsigned Opcode)
Build but don&#39;t insert <empty> = Opcode <empty>.
MachineFunction & getMF()
Getter for the function we currently build.
iterator getLastNonDebugInstr()
Returns an iterator to the last non-debug instruction in the basic block, or end().
#define DEBUG_TYPE
reverse_iterator rend()
RepairingPlacement(MachineInstr &MI, unsigned OpIdx, const TargetRegisterInfo &TRI, Pass &P, RepairingKind Kind=RepairingKind::Insert)
Create a repairing placement for the OpIdx-th operand of MI.
StringRef getName() const
getName - Return the name of the corresponding LLVM function.
const RegisterBank * RegBank
Register bank where the partial value lives.
uint64_t frequency(const Pass &P) const override
Frequency of the insertion point.
===- MachineOptimizationRemarkEmitter.h - Opt Diagnostics -*- C++ -*-—===//
#define P(N)
const MachineInstrBuilder & addUse(Register RegNo, unsigned Flags=0, unsigned SubReg=0) const
Add a virtual register use operand.
bool isPreISelOpcode(QueryType Type=IgnoreBundle) const
Return true if this is an instruction that should go through the usual legalization steps...
Definition: MachineInstr.h:622
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
This pass implements the reg bank selector pass used in the GlobalISel pipeline.
Definition: RegBankSelect.h:90
Insertion point on an edge.
virtual const InstructionMapping & getInstrMapping(const MachineInstr &MI) const
Get the mapping of the different operands of MI on the register bank.
ValuesClass values(OptsTy... Options)
Helper to build a ValuesClass by forwarding a variable number of arguments as an initializer list to ...
Definition: CommandLine.h:652
BlockFrequency getBlockFreq(const MachineBasicBlock *MBB) const
getblockFreq - Return block frequency.
unsigned Length
Length of this mapping in bits.
Represent the analysis usage information of a pass.
Fast - This calling convention attempts to make calls as fast as possible (e.g.
Definition: CallingConv.h:42
bool isTargetSpecificOpcode(unsigned Opcode)
Check whether the given Opcode is a target-specific opcode.
Definition: TargetOpcodes.h:36
static void print(raw_ostream &Out, object::Archive::Kind Kind, T Val)
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
cl::opt< bool > DisableGISelLegalityCheck
INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false) RegBankSelect
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
bool isValid() const
Check whether this object is valid.
bool verify(const MachineInstr &MI) const
Verifiy that this mapping makes sense for MI.
const MachineInstr * machineFunctionIsIllegal(const MachineFunction &MF)
Checks that MIR is fully legal, returns an illegal instruction if it&#39;s not, nullptr otherwise...
bool readsRegister(Register Reg, const TargetRegisterInfo *TRI=nullptr) const
Return true if the MachineInstr reads the specified register.
auto size(R &&Range, typename std::enable_if< std::is_same< typename std::iterator_traits< decltype(Range.begin())>::iterator_category, std::random_access_iterator_tag >::value, void >::type *=nullptr) -> decltype(std::distance(Range.begin(), Range.end()))
Get the size of a range.
Definition: STLExtras.h:1146
bool isGlobalISelAbortEnabled() const
Check whether or not GlobalISel should abort on error.
Align max(MaybeAlign Lhs, Align Rhs)
Definition: Alignment.h:390
Struct used to represent the placement of a repairing point for a given operand.
MachineInstr * CloneMachineInstr(const MachineInstr *Orig)
Create a new MachineInstr which is a copy of Orig, identical in all ways except the instruction has n...
RegisterBank & getRegBank(unsigned ID)
Get the register bank identified by ID.
MachineOperand class - Representation of each machine instruction operand.
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:837
This class implements the register bank concept.
Definition: RegisterBank.h:28
Helper struct that represents how a value is mapped through different register banks.
const Function & getFunction() const
Return the LLVM function that this machine code represents.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:940
A range adaptor for a pair of iterators.
virtual bool canMaterialize() const
Check whether this insertion point can be materialized.
bool isUnconditionalBranch(QueryType Type=AnyInBundle) const
Return true if this is a branch which always transfers control flow to some other block...
Definition: MachineInstr.h:702
void createVRegs(unsigned OpIdx)
Create as many new virtual registers as needed for the mapping of the OpIdx-th operand.
#define clEnumValN(ENUMVAL, FLAGNAME, DESC)
Definition: CommandLine.h:627
const MachineBasicBlock * getParent() const
Definition: MachineInstr.h:255
bool operator==(const StringView &LHS, const StringView &RHS)
Definition: StringView.h:119
BranchProbability getEdgeProbability(const MachineBasicBlock *Src, const MachineBasicBlock *Dst) const
Representation of each machine instruction.
Definition: MachineInstr.h:63
const MachineFunction * getParent() const
Return the MachineFunction containing this basic block.
Insertion point before or after an instruction.
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:55
virtual unsigned copyCost(const RegisterBank &A, const RegisterBank &B, unsigned Size) const
Get the cost of a copy from B to A, or put differently, get the cost of A = COPY B.
void setMBB(MachineBasicBlock &MBB)
Set the insertion point to the end of MBB.
GCN NSA Reassign
InstrInsertPoint(MachineInstr &Instr, bool Before=true)
Create an insertion point before (Before=true) or after Instr.
uint64_t frequency(const Pass &P) const override
Frequency of the insertion point.
bool WasMaterialized
Tell if the insert point has already been materialized.
virtual void print(raw_ostream &OS, const Module *M) const
print - Print out the internal state of the pass.
Definition: Pass.cpp:128
void addInsertPoint(MachineBasicBlock &MBB, bool Beginning)
iterator getFirstNonPHI()
Returns a pointer to the first instruction in this block that is not a PHINode instruction.
static cl::opt< RegBankSelect::Mode > RegBankSelectMode(cl::desc("Mode of the RegBankSelect pass"), cl::Hidden, cl::Optional, cl::values(clEnumValN(RegBankSelect::Mode::Fast, "regbankselect-fast", "Run the Fast mode (default mapping)"), clEnumValN(RegBankSelect::Mode::Greedy, "regbankselect-greedy", "Use the Greedy mode (best local mapping)")))
bool runOnMachineFunction(MachineFunction &MF) override
Walk through MF and assign a register bank to every virtual register that are still mapped to nothing...
bool isReg() const
isReg - Tests if this is a MO_Register operand.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
bool hasProperty(Property P) const
MachineBasicBlock * SplitCriticalEdge(MachineBasicBlock *Succ, Pass &P)
Split the critical edge from this block to the given successor block, and return the newly created bl...
unsigned NumBreakDowns
Number of partial mapping to break down this value.
AnalysisType * getAnalysisIfAvailable() const
getAnalysisIfAvailable<AnalysisType>() - Subclasses use this function to get analysis information tha...
(Re)assign the register bank of the operand.
virtual bool isSplit() const
Does this point involve splitting an edge or block? As soon as ::getPoint is called and thus...
This class implements an extremely fast bulk output stream that can only output to a stream...
Definition: raw_ostream.h:45
IRTranslator LLVM IR MI
bool operator<(const DeltaInfo &LHS, int64_t Delta)
Definition: LineTable.cpp:30
Register getReg() const
getReg - Returns the register number.
uint64_t frequency(const Pass &P) const override
Frequency of the insertion point.
unsigned getNumOperands() const
Get the number of operands.
#define LLVM_DEBUG(X)
Definition: Debug.h:122
const MachineOperand & getOperand(unsigned i) const
Definition: MachineInstr.h:415
void reportGISelFailure(MachineFunction &MF, const TargetPassConfig &TPC, MachineOptimizationRemarkEmitter &MORE, MachineOptimizationRemarkMissed &R)
Report an ISel error as a missed optimization remark to the LLVMContext&#39;s diagnostic stream...
Definition: Utils.cpp:178
Insertion point at the beginning or end of a basic block.
Nothing to repair, just drop this action.
Wrapper class representing virtual and physical registers.
Definition: Register.h:19
bool isSplit() const override
Does this point involve splitting an edge or block? As soon as ::getPoint is called and thus...