Coverage Report

Created: 2019-07-24 05:18

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