LLVM  16.0.0git
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/Function.h"
34 #include "llvm/InitializePasses.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 *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 
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 *DesiredRegBank = 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, DesiredRegBank);
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(*DesiredRegBank, *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(
316  RepairingPlacement(MI, 0, *TRI, *this, RepairingPlacement::Impossible));
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();
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(
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  const MachineRegisterInfo &MRI = MI.getMF()->getRegInfo();
462 
463  // Moreover, to realize this mapping, the register bank of each operand must
464  // match this mapping. In other words, we may need to locally reassign the
465  // register banks. Account for that repairing cost as well.
466  // In this context, local means in the surrounding of MI.
467  for (unsigned OpIdx = 0, EndOpIdx = InstrMapping.getNumOperands();
468  OpIdx != EndOpIdx; ++OpIdx) {
469  const MachineOperand &MO = MI.getOperand(OpIdx);
470  if (!MO.isReg())
471  continue;
472  Register Reg = MO.getReg();
473  if (!Reg)
474  continue;
475  LLT Ty = MRI.getType(Reg);
476  if (!Ty.isValid())
477  continue;
478 
479  LLVM_DEBUG(dbgs() << "Opd" << OpIdx << '\n');
480  const RegisterBankInfo::ValueMapping &ValMapping =
481  InstrMapping.getOperandMapping(OpIdx);
482  // If Reg is already properly mapped, this is free.
483  bool Assign;
484  if (assignmentMatch(Reg, ValMapping, Assign)) {
485  LLVM_DEBUG(dbgs() << "=> is free (match).\n");
486  continue;
487  }
488  if (Assign) {
489  LLVM_DEBUG(dbgs() << "=> is free (simple assignment).\n");
490  RepairPts.emplace_back(RepairingPlacement(MI, OpIdx, *TRI, *this,
492  continue;
493  }
494 
495  // Find the insertion point for the repairing code.
496  RepairPts.emplace_back(
497  RepairingPlacement(MI, OpIdx, *TRI, *this, RepairingPlacement::Insert));
498  RepairingPlacement &RepairPt = RepairPts.back();
499 
500  // If we need to split a basic block to materialize this insertion point,
501  // we may give a higher cost to this mapping.
502  // Nevertheless, we may get away with the split, so try that first.
503  if (RepairPt.hasSplit())
504  tryAvoidingSplit(RepairPt, MO, ValMapping);
505 
506  // Check that the materialization of the repairing is possible.
507  if (!RepairPt.canMaterialize()) {
508  LLVM_DEBUG(dbgs() << "Mapping involves impossible repairing\n");
509  return MappingCost::ImpossibleCost();
510  }
511 
512  // Account for the split cost and repair cost.
513  // Unless the cost is already saturated or we do not care about the cost.
514  if (!BestCost || Saturated)
515  continue;
516 
517  // To get accurate information we need MBFI and MBPI.
518  // Thus, if we end up here this information should be here.
519  assert(MBFI && MBPI && "Cost computation requires MBFI and MBPI");
520 
521  // FIXME: We will have to rework the repairing cost model.
522  // The repairing cost depends on the register bank that MO has.
523  // However, when we break down the value into different values,
524  // MO may not have a register bank while still needing repairing.
525  // For the fast mode, we don't compute the cost so that is fine,
526  // but still for the repairing code, we will have to make a choice.
527  // For the greedy mode, we should choose greedily what is the best
528  // choice based on the next use of MO.
529 
530  // Sums up the repairing cost of MO at each insertion point.
531  uint64_t RepairCost = getRepairCost(MO, ValMapping);
532 
533  // This is an impossible to repair cost.
534  if (RepairCost == std::numeric_limits<unsigned>::max())
535  return MappingCost::ImpossibleCost();
536 
537  // Bias used for splitting: 5%.
538  const uint64_t PercentageForBias = 5;
539  uint64_t Bias = (RepairCost * PercentageForBias + 99) / 100;
540  // We should not need more than a couple of instructions to repair
541  // an assignment. In other words, the computation should not
542  // overflow because the repairing cost is free of basic block
543  // frequency.
544  assert(((RepairCost < RepairCost * PercentageForBias) &&
545  (RepairCost * PercentageForBias <
546  RepairCost * PercentageForBias + 99)) &&
547  "Repairing involves more than a billion of instructions?!");
548  for (const std::unique_ptr<InsertPoint> &InsertPt : RepairPt) {
549  assert(InsertPt->canMaterialize() && "We should not have made it here");
550  // We will applied some basic block frequency and those uses uint64_t.
551  if (!InsertPt->isSplit())
552  Saturated = Cost.addLocalCost(RepairCost);
553  else {
554  uint64_t CostForInsertPt = RepairCost;
555  // Again we shouldn't overflow here givent that
556  // CostForInsertPt is frequency free at this point.
557  assert(CostForInsertPt + Bias > CostForInsertPt &&
558  "Repairing + split bias overflows");
559  CostForInsertPt += Bias;
560  uint64_t PtCost = InsertPt->frequency(*this) * CostForInsertPt;
561  // Check if we just overflowed.
562  if ((Saturated = PtCost < CostForInsertPt))
563  Cost.saturate();
564  else
565  Saturated = Cost.addNonLocalCost(PtCost);
566  }
567 
568  // Stop looking into what it takes to repair, this is already
569  // too expensive.
570  if (BestCost && Cost > *BestCost) {
571  LLVM_DEBUG(dbgs() << "Mapping is too expensive, stop processing\n");
572  return Cost;
573  }
574 
575  // No need to accumulate more cost information.
576  // We need to still gather the repairing information though.
577  if (Saturated)
578  break;
579  }
580  }
581  LLVM_DEBUG(dbgs() << "Total cost is: " << Cost << "\n");
582  return Cost;
583 }
584 
585 bool RegBankSelect::applyMapping(
588  // OpdMapper will hold all the information needed for the rewriting.
589  RegisterBankInfo::OperandsMapper OpdMapper(MI, InstrMapping, *MRI);
590 
591  // First, place the repairing code.
592  for (RepairingPlacement &RepairPt : RepairPts) {
593  if (!RepairPt.canMaterialize() ||
594  RepairPt.getKind() == RepairingPlacement::Impossible)
595  return false;
596  assert(RepairPt.getKind() != RepairingPlacement::None &&
597  "This should not make its way in the list");
598  unsigned OpIdx = RepairPt.getOpIdx();
599  MachineOperand &MO = MI.getOperand(OpIdx);
600  const RegisterBankInfo::ValueMapping &ValMapping =
601  InstrMapping.getOperandMapping(OpIdx);
602  Register Reg = MO.getReg();
603 
604  switch (RepairPt.getKind()) {
606  assert(ValMapping.NumBreakDowns == 1 &&
607  "Reassignment should only be for simple mapping");
608  MRI->setRegBank(Reg, *ValMapping.BreakDown[0].RegBank);
609  break;
611  // Don't insert additional instruction for debug instruction.
612  if (MI.isDebugInstr())
613  break;
614  OpdMapper.createVRegs(OpIdx);
615  if (!repairReg(MO, ValMapping, RepairPt, OpdMapper.getVRegs(OpIdx)))
616  return false;
617  break;
618  default:
619  llvm_unreachable("Other kind should not happen");
620  }
621  }
622 
623  // Second, rewrite the instruction.
624  LLVM_DEBUG(dbgs() << "Actual mapping of the operands: " << OpdMapper << '\n');
625  RBI->applyMapping(OpdMapper);
626 
627  return true;
628 }
629 
630 bool RegBankSelect::assignInstr(MachineInstr &MI) {
631  LLVM_DEBUG(dbgs() << "Assign: " << MI);
632 
633  unsigned Opc = MI.getOpcode();
635  assert((Opc == TargetOpcode::G_ASSERT_ZEXT ||
636  Opc == TargetOpcode::G_ASSERT_SEXT ||
637  Opc == TargetOpcode::G_ASSERT_ALIGN) &&
638  "Unexpected hint opcode!");
639  // The only correct mapping for these is to always use the source register
640  // bank.
641  const RegisterBank *RB =
642  RBI->getRegBank(MI.getOperand(1).getReg(), *MRI, *TRI);
643  // We can assume every instruction above this one has a selected register
644  // bank.
645  assert(RB && "Expected source register to have a register bank?");
646  LLVM_DEBUG(dbgs() << "... Hint always uses source's register bank.\n");
647  MRI->setRegBank(MI.getOperand(0).getReg(), *RB);
648  return true;
649  }
650 
651  // Remember the repairing placement for all the operands.
653 
654  const RegisterBankInfo::InstructionMapping *BestMapping;
655  if (OptMode == RegBankSelect::Mode::Fast) {
656  BestMapping = &RBI->getInstrMapping(MI);
657  MappingCost DefaultCost = computeMapping(MI, *BestMapping, RepairPts);
658  (void)DefaultCost;
659  if (DefaultCost == MappingCost::ImpossibleCost())
660  return false;
661  } else {
662  RegisterBankInfo::InstructionMappings PossibleMappings =
664  if (PossibleMappings.empty())
665  return false;
666  BestMapping = &findBestMapping(MI, PossibleMappings, RepairPts);
667  }
668  // Make sure the mapping is valid for MI.
669  assert(BestMapping->verify(MI) && "Invalid instruction mapping");
670 
671  LLVM_DEBUG(dbgs() << "Best Mapping: " << *BestMapping << '\n');
672 
673  // After this call, MI may not be valid anymore.
674  // Do not use it.
675  return applyMapping(MI, *BestMapping, RepairPts);
676 }
677 
679  // If the ISel pipeline failed, do not bother running that pass.
680  if (MF.getProperties().hasProperty(
682  return false;
683 
684  LLVM_DEBUG(dbgs() << "Assign register banks for: " << MF.getName() << '\n');
685  const Function &F = MF.getFunction();
686  Mode SaveOptMode = OptMode;
687  if (F.hasOptNone())
688  OptMode = Mode::Fast;
689  init(MF);
690 
691 #ifndef NDEBUG
692  // Check that our input is fully legal: we require the function to have the
693  // Legalized property, so it should be.
694  // FIXME: This should be in the MachineVerifier.
696  if (const MachineInstr *MI = machineFunctionIsIllegal(MF)) {
697  reportGISelFailure(MF, *TPC, *MORE, "gisel-regbankselect",
698  "instruction is not legal", *MI);
699  return false;
700  }
701 #endif
702 
703  // Walk the function and assign register banks to all operands.
704  // Use a RPOT to make sure all registers are assigned before we choose
705  // the best mapping of the current instruction.
707  for (MachineBasicBlock *MBB : RPOT) {
708  // Set a sensible insertion point so that subsequent calls to
709  // MIRBuilder.
710  MIRBuilder.setMBB(*MBB);
713 
714  while (!WorkList.empty()) {
715  MachineInstr &MI = *WorkList.pop_back_val();
716 
717  // Ignore target-specific post-isel instructions: they should use proper
718  // regclasses.
719  if (isTargetSpecificOpcode(MI.getOpcode()) && !MI.isPreISelOpcode())
720  continue;
721 
722  // Ignore inline asm instructions: they should use physical
723  // registers/regclasses
724  if (MI.isInlineAsm())
725  continue;
726 
727  // Ignore IMPLICIT_DEF which must have a regclass.
728  if (MI.isImplicitDef())
729  continue;
730 
731  if (!assignInstr(MI)) {
732  reportGISelFailure(MF, *TPC, *MORE, "gisel-regbankselect",
733  "unable to map instruction", MI);
734  return false;
735  }
736  }
737  }
738 
739  OptMode = SaveOptMode;
740  return false;
741 }
742 
743 //------------------------------------------------------------------------------
744 // Helper Classes Implementation
745 //------------------------------------------------------------------------------
747  MachineInstr &MI, unsigned OpIdx, const TargetRegisterInfo &TRI, Pass &P,
749  // Default is, we are going to insert code to repair OpIdx.
750  : Kind(Kind), OpIdx(OpIdx),
751  CanMaterialize(Kind != RepairingKind::Impossible), P(P) {
752  const MachineOperand &MO = MI.getOperand(OpIdx);
753  assert(MO.isReg() && "Trying to repair a non-reg operand");
754 
755  if (Kind != RepairingKind::Insert)
756  return;
757 
758  // Repairings for definitions happen after MI, uses happen before.
759  bool Before = !MO.isDef();
760 
761  // Check if we are done with MI.
762  if (!MI.isPHI() && !MI.isTerminator()) {
763  addInsertPoint(MI, Before);
764  // We are done with the initialization.
765  return;
766  }
767 
768  // Now, look for the special cases.
769  if (MI.isPHI()) {
770  // - PHI must be the first instructions:
771  // * Before, we have to split the related incoming edge.
772  // * After, move the insertion point past the last phi.
773  if (!Before) {
774  MachineBasicBlock::iterator It = MI.getParent()->getFirstNonPHI();
775  if (It != MI.getParent()->end())
776  addInsertPoint(*It, /*Before*/ true);
777  else
778  addInsertPoint(*(--It), /*Before*/ false);
779  return;
780  }
781  // We repair a use of a phi, we may need to split the related edge.
782  MachineBasicBlock &Pred = *MI.getOperand(OpIdx + 1).getMBB();
783  // Check if we can move the insertion point prior to the
784  // terminators of the predecessor.
785  Register Reg = MO.getReg();
787  for (auto Begin = Pred.begin(); It != Begin && It->isTerminator(); --It)
788  if (It->modifiesRegister(Reg, &TRI)) {
789  // We cannot hoist the repairing code in the predecessor.
790  // Split the edge.
791  addInsertPoint(Pred, *MI.getParent());
792  return;
793  }
794  // At this point, we can insert in Pred.
795 
796  // - If It is invalid, Pred is empty and we can insert in Pred
797  // wherever we want.
798  // - If It is valid, It is the first non-terminator, insert after It.
799  if (It == Pred.end())
800  addInsertPoint(Pred, /*Beginning*/ false);
801  else
802  addInsertPoint(*It, /*Before*/ false);
803  } else {
804  // - Terminators must be the last instructions:
805  // * Before, move the insert point before the first terminator.
806  // * After, we have to split the outcoming edges.
807  if (Before) {
808  // Check whether Reg is defined by any terminator.
810  auto REnd = MI.getParent()->rend();
811 
812  for (; It != REnd && It->isTerminator(); ++It) {
813  assert(!It->modifiesRegister(MO.getReg(), &TRI) &&
814  "copy insertion in middle of terminators not handled");
815  }
816 
817  if (It == REnd) {
818  addInsertPoint(*MI.getParent()->begin(), true);
819  return;
820  }
821 
822  // We are sure to be right before the first terminator.
823  addInsertPoint(*It, /*Before*/ false);
824  return;
825  }
826  // Make sure Reg is not redefined by other terminators, otherwise
827  // we do not know how to split.
828  for (MachineBasicBlock::iterator It = MI, End = MI.getParent()->end();
829  ++It != End;)
830  // The machine verifier should reject this kind of code.
831  assert(It->modifiesRegister(MO.getReg(), &TRI) &&
832  "Do not know where to split");
833  // Split each outcoming edges.
834  MachineBasicBlock &Src = *MI.getParent();
835  for (auto &Succ : Src.successors())
836  addInsertPoint(Src, Succ);
837  }
838 }
839 
841  bool Before) {
842  addInsertPoint(*new InstrInsertPoint(MI, Before));
843 }
844 
846  bool Beginning) {
847  addInsertPoint(*new MBBInsertPoint(MBB, Beginning));
848 }
849 
851  MachineBasicBlock &Dst) {
852  addInsertPoint(*new EdgeInsertPoint(Src, Dst, P));
853 }
854 
857  CanMaterialize &= Point.canMaterialize();
858  HasSplit |= Point.isSplit();
859  InsertPoints.emplace_back(&Point);
860 }
861 
863  bool Before)
864  : Instr(Instr), Before(Before) {
865  // Since we do not support splitting, we do not need to update
866  // liveness and such, so do not do anything with P.
867  assert((!Before || !Instr.isPHI()) &&
868  "Splitting before phis requires more points");
869  assert((!Before || !Instr.getNextNode() || !Instr.getNextNode()->isPHI()) &&
870  "Splitting between phis does not make sense");
871 }
872 
873 void RegBankSelect::InstrInsertPoint::materialize() {
874  if (isSplit()) {
875  // Slice and return the beginning of the new block.
876  // If we need to split between the terminators, we theoritically
877  // need to know where the first and second set of terminators end
878  // to update the successors properly.
879  // Now, in pratice, we should have a maximum of 2 branch
880  // instructions; one conditional and one unconditional. Therefore
881  // we know how to update the successor by looking at the target of
882  // the unconditional branch.
883  // If we end up splitting at some point, then, we should update
884  // the liveness information and such. I.e., we would need to
885  // access P here.
886  // The machine verifier should actually make sure such cases
887  // cannot happen.
888  llvm_unreachable("Not yet implemented");
889  }
890  // Otherwise the insertion point is just the current or next
891  // instruction depending on Before. I.e., there is nothing to do
892  // here.
893 }
894 
896  // If the insertion point is after a terminator, we need to split.
897  if (!Before)
898  return Instr.isTerminator();
899  // If we insert before an instruction that is after a terminator,
900  // we are still after a terminator.
901  return Instr.getPrevNode() && Instr.getPrevNode()->isTerminator();
902 }
903 
905  // Even if we need to split, because we insert between terminators,
906  // this split has actually the same frequency as the instruction.
907  const MachineBlockFrequencyInfo *MBFI =
908  P.getAnalysisIfAvailable<MachineBlockFrequencyInfo>();
909  if (!MBFI)
910  return 1;
911  return MBFI->getBlockFreq(Instr.getParent()).getFrequency();
912 }
913 
915  const MachineBlockFrequencyInfo *MBFI =
916  P.getAnalysisIfAvailable<MachineBlockFrequencyInfo>();
917  if (!MBFI)
918  return 1;
919  return MBFI->getBlockFreq(&MBB).getFrequency();
920 }
921 
922 void RegBankSelect::EdgeInsertPoint::materialize() {
923  // If we end up repairing twice at the same place before materializing the
924  // insertion point, we may think we have to split an edge twice.
925  // We should have a factory for the insert point such that identical points
926  // are the same instance.
927  assert(Src.isSuccessor(DstOrSplit) && DstOrSplit->isPredecessor(&Src) &&
928  "This point has already been split");
929  MachineBasicBlock *NewBB = Src.SplitCriticalEdge(DstOrSplit, P);
930  assert(NewBB && "Invalid call to materialize");
931  // We reuse the destination block to hold the information of the new block.
932  DstOrSplit = NewBB;
933 }
934 
936  const MachineBlockFrequencyInfo *MBFI =
937  P.getAnalysisIfAvailable<MachineBlockFrequencyInfo>();
938  if (!MBFI)
939  return 1;
940  if (WasMaterialized)
941  return MBFI->getBlockFreq(DstOrSplit).getFrequency();
942 
943  const MachineBranchProbabilityInfo *MBPI =
944  P.getAnalysisIfAvailable<MachineBranchProbabilityInfo>();
945  if (!MBPI)
946  return 1;
947  // The basic block will be on the edge.
948  return (MBFI->getBlockFreq(&Src) * MBPI->getEdgeProbability(&Src, DstOrSplit))
949  .getFrequency();
950 }
951 
953  // If this is not a critical edge, we should not have used this insert
954  // point. Indeed, either the successor or the predecessor should
955  // have do.
956  assert(Src.succ_size() > 1 && DstOrSplit->pred_size() > 1 &&
957  "Edge is not critical");
958  return Src.canSplitCriticalEdge(DstOrSplit);
959 }
960 
961 RegBankSelect::MappingCost::MappingCost(const BlockFrequency &LocalFreq)
962  : LocalFreq(LocalFreq.getFrequency()) {}
963 
964 bool RegBankSelect::MappingCost::addLocalCost(uint64_t Cost) {
965  // Check if this overflows.
966  if (LocalCost + Cost < LocalCost) {
967  saturate();
968  return true;
969  }
970  LocalCost += Cost;
971  return isSaturated();
972 }
973 
974 bool RegBankSelect::MappingCost::addNonLocalCost(uint64_t Cost) {
975  // Check if this overflows.
976  if (NonLocalCost + Cost < NonLocalCost) {
977  saturate();
978  return true;
979  }
980  NonLocalCost += Cost;
981  return isSaturated();
982 }
983 
984 bool RegBankSelect::MappingCost::isSaturated() const {
985  return LocalCost == UINT64_MAX - 1 && NonLocalCost == UINT64_MAX &&
986  LocalFreq == UINT64_MAX;
987 }
988 
989 void RegBankSelect::MappingCost::saturate() {
990  *this = ImpossibleCost();
991  --LocalCost;
992 }
993 
994 RegBankSelect::MappingCost RegBankSelect::MappingCost::ImpossibleCost() {
995  return MappingCost(UINT64_MAX, UINT64_MAX, UINT64_MAX);
996 }
997 
998 bool RegBankSelect::MappingCost::operator<(const MappingCost &Cost) const {
999  // Sort out the easy cases.
1000  if (*this == Cost)
1001  return false;
1002  // If one is impossible to realize the other is cheaper unless it is
1003  // impossible as well.
1004  if ((*this == ImpossibleCost()) || (Cost == ImpossibleCost()))
1005  return (*this == ImpossibleCost()) < (Cost == ImpossibleCost());
1006  // If one is saturated the other is cheaper, unless it is saturated
1007  // as well.
1008  if (isSaturated() || Cost.isSaturated())
1009  return isSaturated() < Cost.isSaturated();
1010  // At this point we know both costs hold sensible values.
1011 
1012  // If both values have a different base frequency, there is no much
1013  // we can do but to scale everything.
1014  // However, if they have the same base frequency we can avoid making
1015  // complicated computation.
1016  uint64_t ThisLocalAdjust;
1017  uint64_t OtherLocalAdjust;
1018  if (LLVM_LIKELY(LocalFreq == Cost.LocalFreq)) {
1019 
1020  // At this point, we know the local costs are comparable.
1021  // Do the case that do not involve potential overflow first.
1022  if (NonLocalCost == Cost.NonLocalCost)
1023  // Since the non-local costs do not discriminate on the result,
1024  // just compare the local costs.
1025  return LocalCost < Cost.LocalCost;
1026 
1027  // The base costs are comparable so we may only keep the relative
1028  // value to increase our chances of avoiding overflows.
1029  ThisLocalAdjust = 0;
1030  OtherLocalAdjust = 0;
1031  if (LocalCost < Cost.LocalCost)
1032  OtherLocalAdjust = Cost.LocalCost - LocalCost;
1033  else
1034  ThisLocalAdjust = LocalCost - Cost.LocalCost;
1035  } else {
1036  ThisLocalAdjust = LocalCost;
1037  OtherLocalAdjust = Cost.LocalCost;
1038  }
1039 
1040  // The non-local costs are comparable, just keep the relative value.
1041  uint64_t ThisNonLocalAdjust = 0;
1042  uint64_t OtherNonLocalAdjust = 0;
1043  if (NonLocalCost < Cost.NonLocalCost)
1044  OtherNonLocalAdjust = Cost.NonLocalCost - NonLocalCost;
1045  else
1046  ThisNonLocalAdjust = NonLocalCost - Cost.NonLocalCost;
1047  // Scale everything to make them comparable.
1048  uint64_t ThisScaledCost = ThisLocalAdjust * LocalFreq;
1049  // Check for overflow on that operation.
1050  bool ThisOverflows = ThisLocalAdjust && (ThisScaledCost < ThisLocalAdjust ||
1051  ThisScaledCost < LocalFreq);
1052  uint64_t OtherScaledCost = OtherLocalAdjust * Cost.LocalFreq;
1053  // Check for overflow on the last operation.
1054  bool OtherOverflows =
1055  OtherLocalAdjust &&
1056  (OtherScaledCost < OtherLocalAdjust || OtherScaledCost < Cost.LocalFreq);
1057  // Add the non-local costs.
1058  ThisOverflows |= ThisNonLocalAdjust &&
1059  ThisScaledCost + ThisNonLocalAdjust < ThisNonLocalAdjust;
1060  ThisScaledCost += ThisNonLocalAdjust;
1061  OtherOverflows |= OtherNonLocalAdjust &&
1062  OtherScaledCost + OtherNonLocalAdjust < OtherNonLocalAdjust;
1063  OtherScaledCost += OtherNonLocalAdjust;
1064  // If both overflows, we cannot compare without additional
1065  // precision, e.g., APInt. Just give up on that case.
1066  if (ThisOverflows && OtherOverflows)
1067  return false;
1068  // If one overflows but not the other, we can still compare.
1069  if (ThisOverflows || OtherOverflows)
1070  return ThisOverflows < OtherOverflows;
1071  // Otherwise, just compare the values.
1072  return ThisScaledCost < OtherScaledCost;
1073 }
1074 
1075 bool RegBankSelect::MappingCost::operator==(const MappingCost &Cost) const {
1076  return LocalCost == Cost.LocalCost && NonLocalCost == Cost.NonLocalCost &&
1077  LocalFreq == Cost.LocalFreq;
1078 }
1079 
1080 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1082  print(dbgs());
1083  dbgs() << '\n';
1084 }
1085 #endif
1086 
1088  if (*this == ImpossibleCost()) {
1089  OS << "impossible";
1090  return;
1091  }
1092  if (isSaturated()) {
1093  OS << "saturated";
1094  return;
1095  }
1096  OS << LocalFreq << " * " << LocalCost << " + " << NonLocalCost;
1097 }
llvm::RegBankSelect::RepairingPlacement::RepairingPlacement
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.
Definition: RegBankSelect.cpp:746
llvm::MachineIRBuilder::setMF
void setMF(MachineFunction &MF)
Definition: MachineIRBuilder.cpp:24
llvm::RegBankSelect::RepairingPlacement::addInsertPoint
void addInsertPoint(MachineBasicBlock &MBB, bool Beginning)
Definition: RegBankSelect.cpp:845
llvm::RegBankSelect::InsertPoint
Abstract class used to represent an insertion point in a CFG.
Definition: RegBankSelect.h:111
llvm::MachineFunctionProperties::hasProperty
bool hasProperty(Property P) const
Definition: MachineFunction.h:192
MI
IRTranslator LLVM IR MI
Definition: IRTranslator.cpp:109
MachineInstr.h
LLVM_DUMP_METHOD
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds.
Definition: Compiler.h:492
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
llvm::LLT::getScalarSizeInBits
unsigned getScalarSizeInBits() const
Definition: LowLevelTypeImpl.h:224
print
static void print(raw_ostream &Out, object::Archive::Kind Kind, T Val)
Definition: ArchiveWriter.cpp:189
Insert
Vector Rotate Left Mask Mask Insert
Definition: README_P9.txt:112
llvm::MachineRegisterInfo
MachineRegisterInfo - Keep track of information for virtual and physical registers,...
Definition: MachineRegisterInfo.h:50
llvm::isPreISelGenericOptimizationHint
bool isPreISelGenericOptimizationHint(unsigned Opcode)
Definition: TargetOpcodes.h:42
llvm::Function
Definition: Function.h:60
P
This currently compiles esp xmm0 movsd esp eax eax esp ret We should use not the dag combiner This is because dagcombine2 needs to be able to see through the X86ISD::Wrapper which DAGCombine can t really do The code for turning x load into a single vector load is target independent and should be moved to the dag combiner The code for turning x load into a vector load can only handle a direct load from a global or a direct load from the stack It should be generalized to handle any load from P
Definition: README-SSE.txt:411
Pass.h
llvm::RegBankSelect::InstrInsertPoint::InstrInsertPoint
InstrInsertPoint(MachineInstr &Instr, bool Before=true)
Create an insertion point before (Before=true) or after Instr.
Definition: RegBankSelect.cpp:862
llvm::MachineBasicBlock::instrs
instr_range instrs()
Definition: MachineBasicBlock.h:300
llvm::ilist_node_with_parent::getNextNode
NodeTy * getNextNode()
Get the next node, or nullptr for the list tail.
Definition: ilist_node.h:289
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1199
llvm::RegisterBankInfo::InstructionMapping::verify
bool verify(const MachineInstr &MI) const
Verifiy that this mapping makes sense for MI.
Definition: RegisterBankInfo.cpp:595
llvm::RegisterBankInfo::getRegBank
RegisterBank & getRegBank(unsigned ID)
Get the register bank identified by ID.
Definition: RegisterBankInfo.h:431
ErrorHandling.h
llvm::X86Disassembler::Reg
Reg
All possible values of the reg field in the ModR/M byte.
Definition: X86DisassemblerDecoder.h:462
RegisterBankInfo.h
llvm::MachineFunctionPass
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
Definition: MachineFunctionPass.h:30
MachineBasicBlock.h
llvm::DisableGISelLegalityCheck
cl::opt< bool > DisableGISelLegalityCheck
llvm::TargetSubtargetInfo::getRegisterInfo
virtual const TargetRegisterInfo * getRegisterInfo() const
getRegisterInfo - If register information is available, return it.
Definition: TargetSubtargetInfo.h:127
llvm::cl::Hidden
@ Hidden
Definition: CommandLine.h:139
llvm::TargetRegisterInfo
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
Definition: TargetRegisterInfo.h:236
BlockFrequency.h
llvm::LLT::isValid
bool isValid() const
Definition: LowLevelTypeImpl.h:116
llvm::getSelectionDAGFallbackAnalysisUsage
void getSelectionDAGFallbackAnalysisUsage(AnalysisUsage &AU)
Modify analysis usage so it preserves passes required for the SelectionDAG fallback.
Definition: Utils.cpp:895
llvm::max
Expected< ExpressionValue > max(const ExpressionValue &Lhs, const ExpressionValue &Rhs)
Definition: FileCheck.cpp:337
llvm::MachineIRBuilder::buildInstrNoInsert
MachineInstrBuilder buildInstrNoInsert(unsigned Opcode)
Build but don't insert <empty> = Opcode <empty>.
Definition: MachineIRBuilder.cpp:39
llvm::dump
void dump(const SparseBitVector< ElementSize > &LHS, raw_ostream &out)
Definition: SparseBitVector.h:877
STLExtras.h
llvm::RegisterBankInfo::InstructionMapping::isValid
bool isValid() const
Check whether this object is valid.
Definition: RegisterBankInfo.h:253
llvm::Sched::Fast
@ Fast
Definition: TargetLowering.h:104
LegalizerInfo.h
TRI
unsigned const TargetRegisterInfo * TRI
Definition: MachineSink.cpp:1628
INITIALIZE_PASS_END
INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false) RegBankSelect
Definition: RegBankSelect.cpp:68
llvm::RegBankSelect::RepairingPlacement::Insert
@ Insert
Reparing code needs to happen before InsertPoints.
Definition: RegBankSelect.h:321
llvm::RegBankSelect::MBBInsertPoint::frequency
uint64_t frequency(const Pass &P) const override
Frequency of the insertion point.
Definition: RegBankSelect.cpp:914
llvm::MachineBlockFrequencyInfo::getBlockFreq
BlockFrequency getBlockFreq(const MachineBasicBlock *MBB) const
getblockFreq - Return block frequency.
Definition: MachineBlockFrequencyInfo.cpp:230
llvm::MachineFunctionPass::getAnalysisUsage
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
Definition: MachineFunctionPass.cpp:167
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:101
llvm::RegisterBankInfo::ValueMapping::BreakDown
const PartialMapping * BreakDown
How the value is broken down between the different register banks.
Definition: RegisterBankInfo.h:147
llvm::RegisterBankInfo::ValueMapping::partsAllUniform
bool partsAllUniform() const
Definition: RegisterBankInfo.cpp:535
llvm::RegBankSelect::RepairingPlacement::hasSplit
bool hasSplit()
Definition: RegBankSelect.h:365
F
#define F(x, y, z)
Definition: MD5.cpp:55
MachineRegisterInfo.h
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
llvm::RegBankSelect::InstrInsertPoint::frequency
uint64_t frequency(const Pass &P) const override
Frequency of the insertion point.
Definition: RegBankSelect.cpp:904
llvm::RegisterBankInfo::getBreakDownCost
virtual unsigned getBreakDownCost(const ValueMapping &ValMapping, const RegisterBank *CurBank=nullptr) const
Get the cost of using ValMapping to decompose a register.
Definition: RegisterBankInfo.h:633
llvm::MachineInstr::isUnconditionalBranch
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:926
CommandLine.h
llvm::MachineInstrBuilder::addDef
const MachineInstrBuilder & addDef(Register RegNo, unsigned Flags=0, unsigned SubReg=0) const
Add a virtual register definition operand.
Definition: MachineInstrBuilder.h:116
llvm::RegBankSelect::RepairingPlacement::RepairingKind
RepairingKind
Define the kind of action this repairing needs.
Definition: RegBankSelect.h:317
llvm::RegBankSelect::EdgeInsertPoint::frequency
uint64_t frequency(const Pass &P) const override
Frequency of the insertion point.
Definition: RegBankSelect.cpp:935
llvm::MachineFunction::getRegInfo
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
Definition: MachineFunction.h:667
llvm::ms_demangle::IntrinsicFunctionKind::Assign
@ Assign
llvm::RegisterBank
This class implements the register bank concept.
Definition: RegisterBank.h:28
llvm::MachineBlockFrequencyInfo
MachineBlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate machine basic b...
Definition: MachineBlockFrequencyInfo.h:33
llvm::MachineBranchProbabilityInfo
Definition: MachineBranchProbabilityInfo.h:22
llvm::MachineIRBuilder::setMBB
void setMBB(MachineBasicBlock &MBB)
Set the insertion point to the end of MBB.
Definition: MachineIRBuilder.h:333
InlinePriorityMode::Cost
@ Cost
llvm::RegBankSelect::runOnMachineFunction
bool runOnMachineFunction(MachineFunction &MF) override
Walk through MF and assign a register bank to every virtual register that are still mapped to nothing...
Definition: RegBankSelect.cpp:678
llvm::LLT::getSizeInBits
TypeSize getSizeInBits() const
Returns the total size of the type. Must only be called on sized types.
Definition: LowLevelTypeImpl.h:152
llvm::RegisterBankInfo::applyMapping
void applyMapping(const OperandsMapper &OpdMapper) const
Apply OpdMapper.getInstrMapping() to OpdMapper.getMI().
Definition: RegisterBankInfo.h:715
llvm::Register::isPhysicalRegister
static bool isPhysicalRegister(unsigned Reg)
Return true if the specified register number is in the physical register namespace.
Definition: Register.h:65
llvm::AnalysisUsage
Represent the analysis usage information of a pass.
Definition: PassAnalysisSupport.h:47
Utils.h
llvm::MachineFunction::getProperties
const MachineFunctionProperties & getProperties() const
Get the function properties.
Definition: MachineFunction.h:748
UINT64_MAX
#define UINT64_MAX
Definition: DataTypes.h:77
llvm::RegisterBankInfo::getInstrPossibleMappings
InstructionMappings getInstrPossibleMappings(const MachineInstr &MI) const
Get the possible mapping for MI.
Definition: RegisterBankInfo.cpp:411
false
Definition: StackSlotColoring.cpp:141
TargetOpcodes.h
llvm::RegBankSelect::EdgeInsertPoint
Insertion point on an edge.
Definition: RegBankSelect.h:273
llvm::MachineOperand
MachineOperand class - Representation of each machine instruction operand.
Definition: MachineOperand.h:48
llvm::TargetPassConfig::isGlobalISelAbortEnabled
bool isGlobalISelAbortEnabled() const
Check whether or not GlobalISel should abort on error.
Definition: TargetPassConfig.cpp:1570
INITIALIZE_PASS_BEGIN
INITIALIZE_PASS_BEGIN(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false)
llvm::machineFunctionIsIllegal
const MachineInstr * machineFunctionIsIllegal(const MachineFunction &MF)
Checks that MIR is fully legal, returns an illegal instruction if it's not, nullptr otherwise.
Definition: LegalizerInfo.cpp:424
llvm::MachineIRBuilder::getMF
MachineFunction & getMF()
Getter for the function we currently build.
Definition: MachineIRBuilder.h:271
llvm::report_fatal_error
void report_fatal_error(Error Err, bool gen_crash_diag=true)
Report a serious error, calling any installed error handler.
Definition: Error.cpp:145
llvm::RegBankSelect::InstrInsertPoint
Insertion point before or after an instruction.
Definition: RegBankSelect.h:204
llvm::raw_ostream
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:52
llvm::RegBankSelect::InsertPoint::canMaterialize
virtual bool canMaterialize() const
Check whether this insertion point can be materialized.
Definition: RegBankSelect.h:200
llvm::MachineOperand::getParent
MachineInstr * getParent()
getParent - Return the instruction that this operand belongs to.
Definition: MachineOperand.h:237
llvm::RegBankSelect::RepairingPlacement::Reassign
@ Reassign
(Re)assign the register bank of the operand.
Definition: RegBankSelect.h:323
llvm::RegisterBankInfo::getSizeInBits
unsigned getSizeInBits(Register Reg, const MachineRegisterInfo &MRI, const TargetRegisterInfo &TRI) const
Get the size in bits of Reg.
Definition: RegisterBankInfo.cpp:493
llvm::CallingConv::ID
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
llvm::MachineBasicBlock
Definition: MachineBasicBlock.h:94
llvm::Pass::print
virtual void print(raw_ostream &OS, const Module *M) const
print - Print out the internal state of the pass.
Definition: Pass.cpp:130
llvm::RegisterBankInfo::OperandsMapper
Helper class used to get/create the virtual registers that will be used to replace the MachineOperand...
Definition: RegisterBankInfo.h:279
MachineOptimizationRemarkEmitter.h
===- MachineOptimizationRemarkEmitter.h - Opt Diagnostics -*- C++ -*-—===//
llvm::TargetPassConfig
Target-Independent Code Generator Pass Configuration Options.
Definition: TargetPassConfig.h:84
llvm::MachineFunction::getSubtarget
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
Definition: MachineFunction.h:657
llvm::cl::opt
Definition: CommandLine.h:1411
llvm::BlockFrequency
Definition: BlockFrequency.h:23
llvm::cl::values
ValuesClass values(OptsTy... Options)
Helper to build a ValuesClass by forwarding a variable number of arguments as an initializer list to ...
Definition: CommandLine.h:704
llvm::MachineOperand::isReg
bool isReg() const
isReg - Tests if this is a MO_Register operand.
Definition: MachineOperand.h:320
llvm::MachineInstr
Representation of each machine instruction.
Definition: MachineInstr.h:66
llvm::MachineInstrBuilder
Definition: MachineInstrBuilder.h:69
uint64_t
llvm::MachineRegisterInfo::setRegBank
void setRegBank(Register Reg, const RegisterBank &RegBank)
Set the register bank to RegBank for Reg.
Definition: MachineRegisterInfo.cpp:61
llvm::RegisterBankInfo::InstructionMapping
Helper class that represents how the value of an instruction may be mapped and what is the related co...
Definition: RegisterBankInfo.h:189
llvm::MachineFunction::CloneMachineInstr
MachineInstr * CloneMachineInstr(const MachineInstr *Orig)
Create a new MachineInstr which is a copy of Orig, identical in all ways except the instruction has n...
Definition: MachineFunction.cpp:383
INITIALIZE_PASS_DEPENDENCY
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
llvm::RegisterBankInfo::InstructionMapping::getNumOperands
unsigned getNumOperands() const
Get the number of operands.
Definition: RegisterBankInfo.h:233
move
compiles ldr LCPI1_0 ldr ldr mov lsr tst moveq r1 ldr LCPI1_1 and r0 bx lr It would be better to do something like to fold the shift into the conditional move
Definition: README.txt:546
llvm::RegBankSelect::InstrInsertPoint::isSplit
bool isSplit() const override
Does this point involve splitting an edge or block? As soon as ::getPoint is called and thus,...
Definition: RegBankSelect.cpp:895
llvm::BlockFrequency::getFrequency
uint64_t getFrequency() const
Returns the frequency as a fixpoint number scaled by the entry frequency.
Definition: BlockFrequency.h:34
llvm::LLT::isVector
bool isVector() const
Definition: LowLevelTypeImpl.h:122
llvm::LLT::getNumElements
uint16_t getNumElements() const
Returns the number of elements in a vector LLT.
Definition: LowLevelTypeImpl.h:126
llvm::MachineBasicBlock::getLastNonDebugInstr
iterator getLastNonDebugInstr(bool SkipPseudoOp=true)
Returns an iterator to the last non-debug instruction in the basic block, or end().
Definition: MachineBasicBlock.cpp:264
TargetPassConfig.h
llvm::MachineFunction::getName
StringRef getName() const
getName - Return the name of the corresponding LLVM function.
Definition: MachineFunction.cpp:567
llvm::SmallVectorImpl::const_iterator
typename SuperClass::const_iterator const_iterator
Definition: SmallVector.h:582
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
MachineBranchProbabilityInfo.h
std::swap
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:853
llvm::RegisterBankInfo::InstructionMapping::getCost
unsigned getCost() const
Get the cost.
Definition: RegisterBankInfo.h:227
llvm::operator==
bool operator==(uint64_t V1, const APInt &V2)
Definition: APInt.h:2010
Mode
SI Whole Quad Mode
Definition: SIWholeQuadMode.cpp:264
llvm::MachineInstr::isPHI
bool isPHI() const
Definition: MachineInstr.h:1300
llvm::MachineInstrBuilder::addUse
const MachineInstrBuilder & addUse(Register RegNo, unsigned Flags=0, unsigned SubReg=0) const
Add a virtual register use operand.
Definition: MachineInstrBuilder.h:123
llvm::MachineOperand::getReg
Register getReg() const
getReg - Returns the register number.
Definition: MachineOperand.h:359
llvm::RegisterBankInfo::PartialMapping::RegBank
const RegisterBank * RegBank
Register bank where the partial value lives.
Definition: RegisterBankInfo.h:60
llvm::MachineBranchProbabilityInfo::getEdgeProbability
BranchProbability getEdgeProbability(const MachineBasicBlock *Src, const MachineBasicBlock *Dst) const
Definition: MachineBranchProbabilityInfo.cpp:56
register
should just be implemented with a CLZ instruction Since there are other e that share this it would be best to implement this in a target independent as zero is the default value for the binary encoder e add r0 add r5 Register operands should be distinct That when the encoding does not require two syntactical operands to refer to the same register
Definition: README.txt:726
llvm::MachineInstr::readsRegister
bool readsRegister(Register Reg, const TargetRegisterInfo *TRI=nullptr) const
Return true if the MachineInstr reads the specified register.
Definition: MachineInstr.h:1390
llvm::TargetSubtargetInfo::getRegBankInfo
virtual const RegisterBankInfo * getRegBankInfo() const
If the information for the register banks is available, return it.
Definition: TargetSubtargetInfo.h:131
llvm::MachineFunction
Definition: MachineFunction.h:257
llvm::size
auto size(R &&Range, std::enable_if_t< std::is_base_of< std::random_access_iterator_tag, typename std::iterator_traits< decltype(Range.begin())>::iterator_category >::value, void > *=nullptr)
Get the size of a range.
Definition: STLExtras.h:1715
llvm::make_pointer_range
iterator_range< pointer_iterator< WrappedIteratorT > > make_pointer_range(RangeT &&Range)
Definition: iterator.h:363
llvm::RegisterBankInfo::ValueMapping
Helper struct that represents how a value is mapped through different register banks.
Definition: RegisterBankInfo.h:145
llvm::RegBankSelect::RepairingPlacement::None
@ None
Nothing to repair, just drop this action.
Definition: RegBankSelect.h:319
llvm::RegBankSelect::RepairingPlacement::getNumInsertPoints
unsigned getNumInsertPoints() const
Definition: RegBankSelect.h:389
llvm_unreachable
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
Definition: ErrorHandling.h:143
llvm::RegBankSelect::RepairingPlacement
Struct used to represent the placement of a repairing point for a given operand.
Definition: RegBankSelect.h:314
Compiler.h
TargetSubtargetInfo.h
clEnumValN
#define clEnumValN(ENUMVAL, FLAGNAME, DESC)
Definition: CommandLine.h:679
llvm::MachineOperand::isDef
bool isDef() const
Definition: MachineOperand.h:374
llvm::RegisterBankInfo::PartialMapping::Length
unsigned Length
Length of this mapping in bits.
Definition: RegisterBankInfo.h:57
MRI
unsigned const MachineRegisterInfo * MRI
Definition: AArch64AdvSIMDScalarPass.cpp:105
llvm::Register
Wrapper class representing virtual and physical registers.
Definition: Register.h:19
llvm::cl::Optional
@ Optional
Definition: CommandLine.h:115
llvm::RegBankSelect::EdgeInsertPoint::canMaterialize
bool canMaterialize() const override
Check whether this insertion point can be materialized.
Definition: RegBankSelect.cpp:952
MBB
MachineBasicBlock & MBB
Definition: AArch64SLSHardening.cpp:74
llvm::MachineFunctionProperties::Property::FailedISel
@ FailedISel
Reassign
GCN NSA Reassign
Definition: GCNNSAReassign.cpp:100
llvm::MachineFunction::getFunction
Function & getFunction()
Return the LLVM function that this machine code represents.
Definition: MachineFunction.h:623
operator<
bool operator<(const DeltaInfo &LHS, int64_t Delta)
Definition: LineTable.cpp:30
llvm::isTargetSpecificOpcode
bool isTargetSpecificOpcode(unsigned Opcode)
Check whether the given Opcode is a target-specific opcode.
Definition: TargetOpcodes.h:36
llvm::RegBankSelect::InsertPoint::isSplit
virtual bool isSplit() const
Does this point involve splitting an edge or block? As soon as ::getPoint is called and thus,...
Definition: RegBankSelect.h:188
RegBankSelect.h
Function.h
llvm::RegisterBankInfo::copyCost
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.
Definition: RegisterBankInfo.h:613
llvm::SmallVectorImpl::clear
void clear()
Definition: SmallVector.h:614
llvm::RegisterBankInfo::getInstrMapping
virtual const InstructionMapping & getInstrMapping(const MachineInstr &MI) const
Get the mapping of the different operands of MI on the register bank.
Definition: RegisterBankInfo.cpp:403
llvm::ReversePostOrderTraversal
Definition: PostOrderIterator.h:291
llvm::reportGISelFailure
void reportGISelFailure(MachineFunction &MF, const TargetPassConfig &TPC, MachineOptimizationRemarkEmitter &MORE, MachineOptimizationRemarkMissed &R)
Report an ISel error as a missed optimization remark to the LLVMContext's diagnostic stream.
Definition: Utils.cpp:269
llvm::RegisterBankInfo::ValueMapping::NumBreakDowns
unsigned NumBreakDowns
Number of partial mapping to break down this value.
Definition: RegisterBankInfo.h:150
llvm::RegBankSelect::Mode
Mode
List of the modes supported by the RegBankSelect pass.
Definition: RegBankSelect.h:96
llvm::Pass
Pass interface - Implemented by all 'passes'.
Definition: Pass.h:91
PostOrderIterator.h
llvm::RegBankSelect::RepairingPlacement::switchTo
void switchTo(RepairingKind NewKind)
Change the type of this repairing placement to NewKind.
Definition: RegBankSelect.h:399
SmallVector.h
llvm::MachineBasicBlock::begin
iterator begin()
Definition: MachineBasicBlock.h:305
llvm::MachineRegisterInfo::getType
LLT getType(Register Reg) const
Get the low-level type of Reg or LLT{} if Reg is not a generic (target independent) virtual register.
Definition: MachineRegisterInfo.h:745
RegisterBank.h
llvm::SmallVectorImpl::pop_back_val
T pop_back_val()
Definition: SmallVector.h:677
llvm::iterator_range
A range adaptor for a pair of iterators.
Definition: iterator_range.h:30
LLVM_LIKELY
#define LLVM_LIKELY(EXPR)
Definition: Compiler.h:209
llvm::SmallVectorImpl
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:42
llvm::RegBankSelect::RepairingPlacement::getOpIdx
unsigned getOpIdx() const
Definition: RegBankSelect.h:363
llvm::reverse
auto reverse(ContainerTy &&C)
Definition: STLExtras.h:485
MachineOperand.h
llvm::RegBankSelect::ID
static char ID
Definition: RegBankSelect.h:93
llvm::RegBankSelect
This pass implements the reg bank selector pass used in the GlobalISel pipeline.
Definition: RegBankSelect.h:91
llvm::AnalysisUsage::addRequired
AnalysisUsage & addRequired()
Definition: PassAnalysisSupport.h:75
llvm::RegBankSelect::MBBInsertPoint
Insertion point at the beginning or end of a basic block.
Definition: RegBankSelect.h:237
llvm::cl::desc
Definition: CommandLine.h:412
DEBUG_TYPE
#define DEBUG_TYPE
Definition: RegBankSelect.cpp:49
raw_ostream.h
MachineFunction.h
llvm::printReg
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.
Definition: TargetRegisterInfo.cpp:111
registers
Implement PPCInstrInfo::isLoadFromStackSlot isStoreToStackSlot for vector registers
Definition: README_ALTIVEC.txt:4
llvm::MachineInstrBundleIterator< MachineInstr >
InitializePasses.h
MachineBlockFrequencyInfo.h
llvm::RegBankSelect::RepairingPlacement::Impossible
@ Impossible
Mark this repairing placement as impossible.
Definition: RegBankSelect.h:325
TargetRegisterInfo.h
Debug.h
llvm::MachineBasicBlock::end
iterator end()
Definition: MachineBasicBlock.h:307
llvm::RegBankSelect::getAnalysisUsage
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
Definition: RegBankSelect.cpp:98
of
Add support for conditional and other related patterns Instead of
Definition: README.txt:134
RegBankSelectMode
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)")))
llvm::SmallVectorImpl::emplace_back
reference emplace_back(ArgTypes &&... Args)
Definition: SmallVector.h:941
llvm::LLT
Definition: LowLevelTypeImpl.h:39