Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp
Line
Count
Source (jump to first uncovered line)
1
//===- SelectionDAGISel.cpp - Implement the SelectionDAGISel class --------===//
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
//
9
// This implements the SelectionDAGISel class.
10
//
11
//===----------------------------------------------------------------------===//
12
13
#include "llvm/CodeGen/SelectionDAGISel.h"
14
#include "ScheduleDAGSDNodes.h"
15
#include "SelectionDAGBuilder.h"
16
#include "llvm/ADT/APInt.h"
17
#include "llvm/ADT/DenseMap.h"
18
#include "llvm/ADT/None.h"
19
#include "llvm/ADT/PostOrderIterator.h"
20
#include "llvm/ADT/STLExtras.h"
21
#include "llvm/ADT/SmallPtrSet.h"
22
#include "llvm/ADT/SmallSet.h"
23
#include "llvm/ADT/SmallVector.h"
24
#include "llvm/ADT/Statistic.h"
25
#include "llvm/ADT/StringRef.h"
26
#include "llvm/Analysis/AliasAnalysis.h"
27
#include "llvm/Analysis/BranchProbabilityInfo.h"
28
#include "llvm/Analysis/CFG.h"
29
#include "llvm/Analysis/EHPersonalities.h"
30
#include "llvm/Analysis/OptimizationRemarkEmitter.h"
31
#include "llvm/Analysis/TargetLibraryInfo.h"
32
#include "llvm/Analysis/TargetTransformInfo.h"
33
#include "llvm/CodeGen/FastISel.h"
34
#include "llvm/CodeGen/FunctionLoweringInfo.h"
35
#include "llvm/CodeGen/GCMetadata.h"
36
#include "llvm/CodeGen/ISDOpcodes.h"
37
#include "llvm/CodeGen/MachineBasicBlock.h"
38
#include "llvm/CodeGen/MachineFrameInfo.h"
39
#include "llvm/CodeGen/MachineFunction.h"
40
#include "llvm/CodeGen/MachineFunctionPass.h"
41
#include "llvm/CodeGen/MachineInstr.h"
42
#include "llvm/CodeGen/MachineInstrBuilder.h"
43
#include "llvm/CodeGen/MachineMemOperand.h"
44
#include "llvm/CodeGen/MachineModuleInfo.h"
45
#include "llvm/CodeGen/MachineOperand.h"
46
#include "llvm/CodeGen/MachinePassRegistry.h"
47
#include "llvm/CodeGen/MachineRegisterInfo.h"
48
#include "llvm/CodeGen/SchedulerRegistry.h"
49
#include "llvm/CodeGen/SelectionDAG.h"
50
#include "llvm/CodeGen/SelectionDAGNodes.h"
51
#include "llvm/CodeGen/StackProtector.h"
52
#include "llvm/CodeGen/SwiftErrorValueTracking.h"
53
#include "llvm/CodeGen/TargetInstrInfo.h"
54
#include "llvm/CodeGen/TargetLowering.h"
55
#include "llvm/CodeGen/TargetRegisterInfo.h"
56
#include "llvm/CodeGen/TargetSubtargetInfo.h"
57
#include "llvm/CodeGen/ValueTypes.h"
58
#include "llvm/IR/BasicBlock.h"
59
#include "llvm/IR/Constants.h"
60
#include "llvm/IR/DataLayout.h"
61
#include "llvm/IR/DebugInfoMetadata.h"
62
#include "llvm/IR/DebugLoc.h"
63
#include "llvm/IR/DiagnosticInfo.h"
64
#include "llvm/IR/Dominators.h"
65
#include "llvm/IR/Function.h"
66
#include "llvm/IR/InlineAsm.h"
67
#include "llvm/IR/InstIterator.h"
68
#include "llvm/IR/InstrTypes.h"
69
#include "llvm/IR/Instruction.h"
70
#include "llvm/IR/Instructions.h"
71
#include "llvm/IR/IntrinsicInst.h"
72
#include "llvm/IR/Intrinsics.h"
73
#include "llvm/IR/Metadata.h"
74
#include "llvm/IR/Type.h"
75
#include "llvm/IR/User.h"
76
#include "llvm/IR/Value.h"
77
#include "llvm/MC/MCInstrDesc.h"
78
#include "llvm/MC/MCRegisterInfo.h"
79
#include "llvm/Pass.h"
80
#include "llvm/Support/BranchProbability.h"
81
#include "llvm/Support/Casting.h"
82
#include "llvm/Support/CodeGen.h"
83
#include "llvm/Support/CommandLine.h"
84
#include "llvm/Support/Compiler.h"
85
#include "llvm/Support/Debug.h"
86
#include "llvm/Support/ErrorHandling.h"
87
#include "llvm/Support/KnownBits.h"
88
#include "llvm/Support/MachineValueType.h"
89
#include "llvm/Support/Timer.h"
90
#include "llvm/Support/raw_ostream.h"
91
#include "llvm/Target/TargetIntrinsicInfo.h"
92
#include "llvm/Target/TargetMachine.h"
93
#include "llvm/Target/TargetOptions.h"
94
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
95
#include <algorithm>
96
#include <cassert>
97
#include <cstdint>
98
#include <iterator>
99
#include <limits>
100
#include <memory>
101
#include <string>
102
#include <utility>
103
#include <vector>
104
105
using namespace llvm;
106
107
#define DEBUG_TYPE "isel"
108
109
STATISTIC(NumFastIselFailures, "Number of instructions fast isel failed on");
110
STATISTIC(NumFastIselSuccess, "Number of instructions fast isel selected");
111
STATISTIC(NumFastIselBlocks, "Number of blocks selected entirely by fast isel");
112
STATISTIC(NumDAGBlocks, "Number of blocks selected using DAG");
113
STATISTIC(NumDAGIselRetries,"Number of times dag isel has to try another path");
114
STATISTIC(NumEntryBlocks, "Number of entry blocks encountered");
115
STATISTIC(NumFastIselFailLowerArguments,
116
          "Number of entry blocks where fast isel failed to lower arguments");
117
118
static cl::opt<int> EnableFastISelAbort(
119
    "fast-isel-abort", cl::Hidden,
120
    cl::desc("Enable abort calls when \"fast\" instruction selection "
121
             "fails to lower an instruction: 0 disable the abort, 1 will "
122
             "abort but for args, calls and terminators, 2 will also "
123
             "abort for argument lowering, and 3 will never fallback "
124
             "to SelectionDAG."));
125
126
static cl::opt<bool> EnableFastISelFallbackReport(
127
    "fast-isel-report-on-fallback", cl::Hidden,
128
    cl::desc("Emit a diagnostic when \"fast\" instruction selection "
129
             "falls back to SelectionDAG."));
130
131
static cl::opt<bool>
132
UseMBPI("use-mbpi",
133
        cl::desc("use Machine Branch Probability Info"),
134
        cl::init(true), cl::Hidden);
135
136
#ifndef NDEBUG
137
static cl::opt<std::string>
138
FilterDAGBasicBlockName("filter-view-dags", cl::Hidden,
139
                        cl::desc("Only display the basic block whose name "
140
                                 "matches this for all view-*-dags options"));
141
static cl::opt<bool>
142
ViewDAGCombine1("view-dag-combine1-dags", cl::Hidden,
143
          cl::desc("Pop up a window to show dags before the first "
144
                   "dag combine pass"));
145
static cl::opt<bool>
146
ViewLegalizeTypesDAGs("view-legalize-types-dags", cl::Hidden,
147
          cl::desc("Pop up a window to show dags before legalize types"));
148
static cl::opt<bool>
149
ViewLegalizeDAGs("view-legalize-dags", cl::Hidden,
150
          cl::desc("Pop up a window to show dags before legalize"));
151
static cl::opt<bool>
152
ViewDAGCombine2("view-dag-combine2-dags", cl::Hidden,
153
          cl::desc("Pop up a window to show dags before the second "
154
                   "dag combine pass"));
155
static cl::opt<bool>
156
ViewDAGCombineLT("view-dag-combine-lt-dags", cl::Hidden,
157
          cl::desc("Pop up a window to show dags before the post legalize types"
158
                   " dag combine pass"));
159
static cl::opt<bool>
160
ViewISelDAGs("view-isel-dags", cl::Hidden,
161
          cl::desc("Pop up a window to show isel dags as they are selected"));
162
static cl::opt<bool>
163
ViewSchedDAGs("view-sched-dags", cl::Hidden,
164
          cl::desc("Pop up a window to show sched dags as they are processed"));
165
static cl::opt<bool>
166
ViewSUnitDAGs("view-sunit-dags", cl::Hidden,
167
      cl::desc("Pop up a window to show SUnit dags after they are processed"));
168
#else
169
static const bool ViewDAGCombine1 = false,
170
                  ViewLegalizeTypesDAGs = false, ViewLegalizeDAGs = false,
171
                  ViewDAGCombine2 = false,
172
                  ViewDAGCombineLT = false,
173
                  ViewISelDAGs = false, ViewSchedDAGs = false,
174
                  ViewSUnitDAGs = false;
175
#endif
176
177
//===---------------------------------------------------------------------===//
178
///
179
/// RegisterScheduler class - Track the registration of instruction schedulers.
180
///
181
//===---------------------------------------------------------------------===//
182
MachinePassRegistry<RegisterScheduler::FunctionPassCtor>
183
    RegisterScheduler::Registry;
184
185
//===---------------------------------------------------------------------===//
186
///
187
/// ISHeuristic command line option for instruction schedulers.
188
///
189
//===---------------------------------------------------------------------===//
190
static cl::opt<RegisterScheduler::FunctionPassCtor, false,
191
               RegisterPassParser<RegisterScheduler>>
192
ISHeuristic("pre-RA-sched",
193
            cl::init(&createDefaultScheduler), cl::Hidden,
194
            cl::desc("Instruction schedulers available (before register"
195
                     " allocation):"));
196
197
static RegisterScheduler
198
defaultListDAGScheduler("default", "Best scheduler for the target",
199
                        createDefaultScheduler);
200
201
namespace llvm {
202
203
  //===--------------------------------------------------------------------===//
204
  /// This class is used by SelectionDAGISel to temporarily override
205
  /// the optimization level on a per-function basis.
206
  class OptLevelChanger {
207
    SelectionDAGISel &IS;
208
    CodeGenOpt::Level SavedOptLevel;
209
    bool SavedFastISel;
210
211
  public:
212
    OptLevelChanger(SelectionDAGISel &ISel,
213
278k
                    CodeGenOpt::Level NewOptLevel) : IS(ISel) {
214
278k
      SavedOptLevel = IS.OptLevel;
215
278k
      if (NewOptLevel == SavedOptLevel)
216
277k
        return;
217
270
      IS.OptLevel = NewOptLevel;
218
270
      IS.TM.setOptLevel(NewOptLevel);
219
270
      LLVM_DEBUG(dbgs() << "\nChanging optimization level for Function "
220
270
                        << IS.MF->getFunction().getName() << "\n");
221
270
      LLVM_DEBUG(dbgs() << "\tBefore: -O" << SavedOptLevel << " ; After: -O"
222
270
                        << NewOptLevel << "\n");
223
270
      SavedFastISel = IS.TM.Options.EnableFastISel;
224
270
      if (NewOptLevel == CodeGenOpt::None) {
225
270
        IS.TM.setFastISel(IS.TM.getO0WantsFastISel());
226
270
        LLVM_DEBUG(
227
270
            dbgs() << "\tFastISel is "
228
270
                   << (IS.TM.Options.EnableFastISel ? "enabled" : "disabled")
229
270
                   << "\n");
230
270
      }
231
270
    }
232
233
277k
    ~OptLevelChanger() {
234
277k
      if (IS.OptLevel == SavedOptLevel)
235
277k
        return;
236
269
      LLVM_DEBUG(dbgs() << "\nRestoring optimization level for Function "
237
269
                        << IS.MF->getFunction().getName() << "\n");
238
269
      LLVM_DEBUG(dbgs() << "\tBefore: -O" << IS.OptLevel << " ; After: -O"
239
269
                        << SavedOptLevel << "\n");
240
269
      IS.OptLevel = SavedOptLevel;
241
269
      IS.TM.setOptLevel(SavedOptLevel);
242
269
      IS.TM.setFastISel(SavedFastISel);
243
269
    }
244
  };
245
246
  //===--------------------------------------------------------------------===//
247
  /// createDefaultScheduler - This creates an instruction scheduler appropriate
248
  /// for the target.
249
  ScheduleDAGSDNodes* createDefaultScheduler(SelectionDAGISel *IS,
250
1.24M
                                             CodeGenOpt::Level OptLevel) {
251
1.24M
    const TargetLowering *TLI = IS->TLI;
252
1.24M
    const TargetSubtargetInfo &ST = IS->MF->getSubtarget();
253
1.24M
254
1.24M
    // Try first to see if the Target has its own way of selecting a scheduler
255
1.24M
    if (auto *SchedulerCtor = ST.getDAGScheduler(OptLevel)) {
256
0
      return SchedulerCtor(IS, OptLevel);
257
0
    }
258
1.24M
259
1.24M
    if (OptLevel == CodeGenOpt::None ||
260
1.24M
        
(1.23M
ST.enableMachineScheduler()1.23M
&&
ST.enableMachineSchedDefaultSched()1.12M
) ||
261
1.24M
        
TLI->getSchedulingPreference() == Sched::Source109k
)
262
1.14M
      return createSourceListDAGScheduler(IS, OptLevel);
263
102k
    if (TLI->getSchedulingPreference() == Sched::RegPressure)
264
19.7k
      return createBURRListDAGScheduler(IS, OptLevel);
265
83.1k
    if (TLI->getSchedulingPreference() == Sched::Hybrid)
266
64.5k
      return createHybridListDAGScheduler(IS, OptLevel);
267
18.6k
    if (TLI->getSchedulingPreference() == Sched::VLIW)
268
0
      return createVLIWDAGScheduler(IS, OptLevel);
269
18.6k
    assert(TLI->getSchedulingPreference() == Sched::ILP &&
270
18.6k
           "Unknown sched type!");
271
18.6k
    return createILPListDAGScheduler(IS, OptLevel);
272
18.6k
  }
273
274
} // end namespace llvm
275
276
// EmitInstrWithCustomInserter - This method should be implemented by targets
277
// that mark instructions with the 'usesCustomInserter' flag.  These
278
// instructions are special in various ways, which require special support to
279
// insert.  The specified MachineInstr is created but not inserted into any
280
// basic blocks, and this method is called to expand it into a sequence of
281
// instructions, potentially also creating new basic blocks and control flow.
282
// When new basic blocks are inserted and the edges from MBB to its successors
283
// are modified, the method should insert pairs of <OldSucc, NewSucc> into the
284
// DenseMap.
285
MachineBasicBlock *
286
TargetLowering::EmitInstrWithCustomInserter(MachineInstr &MI,
287
0
                                            MachineBasicBlock *MBB) const {
288
#ifndef NDEBUG
289
  dbgs() << "If a target marks an instruction with "
290
          "'usesCustomInserter', it must implement "
291
          "TargetLowering::EmitInstrWithCustomInserter!";
292
#endif
293
0
  llvm_unreachable(nullptr);
294
0
}
295
296
void TargetLowering::AdjustInstrPostInstrSelection(MachineInstr &MI,
297
0
                                                   SDNode *Node) const {
298
0
  assert(!MI.hasPostISelHook() &&
299
0
         "If a target marks an instruction with 'hasPostISelHook', "
300
0
         "it must implement TargetLowering::AdjustInstrPostInstrSelection!");
301
0
}
302
303
//===----------------------------------------------------------------------===//
304
// SelectionDAGISel code
305
//===----------------------------------------------------------------------===//
306
307
SelectionDAGISel::SelectionDAGISel(TargetMachine &tm,
308
                                   CodeGenOpt::Level OL) :
309
  MachineFunctionPass(ID), TM(tm),
310
  FuncInfo(new FunctionLoweringInfo()),
311
  SwiftError(new SwiftErrorValueTracking()),
312
  CurDAG(new SelectionDAG(tm, OL)),
313
  SDB(new SelectionDAGBuilder(*CurDAG, *FuncInfo, *SwiftError, OL)),
314
  AA(), GFI(),
315
  OptLevel(OL),
316
38.1k
  DAGSize(0) {
317
38.1k
    initializeGCModuleInfoPass(*PassRegistry::getPassRegistry());
318
38.1k
    initializeBranchProbabilityInfoWrapperPassPass(
319
38.1k
        *PassRegistry::getPassRegistry());
320
38.1k
    initializeAAResultsWrapperPassPass(*PassRegistry::getPassRegistry());
321
38.1k
    initializeTargetLibraryInfoWrapperPassPass(
322
38.1k
        *PassRegistry::getPassRegistry());
323
38.1k
  }
324
325
37.9k
SelectionDAGISel::~SelectionDAGISel() {
326
37.9k
  delete SDB;
327
37.9k
  delete CurDAG;
328
37.9k
  delete FuncInfo;
329
37.9k
  delete SwiftError;
330
37.9k
}
331
332
37.8k
void SelectionDAGISel::getAnalysisUsage(AnalysisUsage &AU) const {
333
37.8k
  if (OptLevel != CodeGenOpt::None)
334
36.0k
    AU.addRequired<AAResultsWrapperPass>();
335
37.8k
  AU.addRequired<GCModuleInfo>();
336
37.8k
  AU.addRequired<StackProtector>();
337
37.8k
  AU.addPreserved<GCModuleInfo>();
338
37.8k
  AU.addRequired<TargetLibraryInfoWrapperPass>();
339
37.8k
  AU.addRequired<TargetTransformInfoWrapperPass>();
340
37.8k
  if (UseMBPI && OptLevel != CodeGenOpt::None)
341
36.0k
    AU.addRequired<BranchProbabilityInfoWrapperPass>();
342
37.8k
  MachineFunctionPass::getAnalysisUsage(AU);
343
37.8k
}
344
345
/// SplitCriticalSideEffectEdges - Look for critical edges with a PHI value that
346
/// may trap on it.  In this case we have to split the edge so that the path
347
/// through the predecessor block that doesn't go to the phi block doesn't
348
/// execute the possibly trapping instruction. If available, we pass domtree
349
/// and loop info to be updated when we split critical edges. This is because
350
/// SelectionDAGISel preserves these analyses.
351
/// This is required for correctness, so it must be done at -O0.
352
///
353
static void SplitCriticalSideEffectEdges(Function &Fn, DominatorTree *DT,
354
278k
                                         LoopInfo *LI) {
355
278k
  // Loop for blocks with phi nodes.
356
1.20M
  for (BasicBlock &BB : Fn) {
357
1.20M
    PHINode *PN = dyn_cast<PHINode>(BB.begin());
358
1.20M
    if (!PN) 
continue1.05M
;
359
153k
360
153k
  ReprocessBlock:
361
153k
    // For each block with a PHI node, check to see if any of the input values
362
153k
    // are potentially trapping constant expressions.  Constant expressions are
363
153k
    // the only potentially trapping value that can occur as the argument to a
364
153k
    // PHI.
365
394k
    for (BasicBlock::iterator I = BB.begin(); (PN = dyn_cast<PHINode>(I)); 
++I241k
)
366
851k
      
for (unsigned i = 0, e = PN->getNumIncomingValues(); 241k
i != e;
++i610k
) {
367
610k
        ConstantExpr *CE = dyn_cast<ConstantExpr>(PN->getIncomingValue(i));
368
610k
        if (!CE || 
!CE->canTrap()12.6k
)
continue610k
;
369
2
370
2
        // The only case we have to worry about is when the edge is critical.
371
2
        // Since this block has a PHI Node, we assume it has multiple input
372
2
        // edges: check to see if the pred has multiple successors.
373
2
        BasicBlock *Pred = PN->getIncomingBlock(i);
374
2
        if (Pred->getTerminator()->getNumSuccessors() == 1)
375
2
          continue;
376
0
377
0
        // Okay, we have to split this edge.
378
0
        SplitCriticalEdge(
379
0
            Pred->getTerminator(), GetSuccessorNumber(Pred, &BB),
380
0
            CriticalEdgeSplittingOptions(DT, LI).setMergeIdenticalEdges());
381
0
        goto ReprocessBlock;
382
0
      }
383
153k
  }
384
278k
}
385
386
static void computeUsesMSVCFloatingPoint(const Triple &TT, const Function &F,
387
277k
                                         MachineModuleInfo &MMI) {
388
277k
  // Only needed for MSVC
389
277k
  if (!TT.isWindowsMSVCEnvironment())
390
275k
    return;
391
2.59k
392
2.59k
  // If it's already set, nothing to do.
393
2.59k
  if (MMI.usesMSVCFloatingPoint())
394
774
    return;
395
1.81k
396
10.5k
  
for (const Instruction &I : instructions(F))1.81k
{
397
10.5k
    if (I.getType()->isFPOrFPVectorTy()) {
398
55
      MMI.setUsesMSVCFloatingPoint(true);
399
55
      return;
400
55
    }
401
18.1k
    
for (const auto &Op : I.operands())10.5k
{
402
18.1k
      if (Op->getType()->isFPOrFPVectorTy()) {
403
47
        MMI.setUsesMSVCFloatingPoint(true);
404
47
        return;
405
47
      }
406
18.1k
    }
407
10.5k
  }
408
1.81k
}
409
410
497k
bool SelectionDAGISel::runOnMachineFunction(MachineFunction &mf) {
411
497k
  // If we already selected that function, we do not need to run SDISel.
412
497k
  if (mf.getProperties().hasProperty(
413
497k
          MachineFunctionProperties::Property::Selected))
414
219k
    return false;
415
278k
  // Do some sanity-checking on the command-line options.
416
278k
  assert((!EnableFastISelAbort || TM.Options.EnableFastISel) &&
417
278k
         "-fast-isel-abort > 0 requires -fast-isel");
418
278k
419
278k
  const Function &Fn = mf.getFunction();
420
278k
  MF = &mf;
421
278k
422
278k
  // Reset the target options before resetting the optimization
423
278k
  // level below.
424
278k
  // FIXME: This is a horrible hack and should be processed via
425
278k
  // codegen looking at the optimization level explicitly when
426
278k
  // it wants to look at it.
427
278k
  TM.resetTargetOptions(Fn);
428
278k
  // Reset OptLevel to None for optnone functions.
429
278k
  CodeGenOpt::Level NewOptLevel = OptLevel;
430
278k
  if (OptLevel != CodeGenOpt::None && 
skipFunction(Fn)269k
)
431
270
    NewOptLevel = CodeGenOpt::None;
432
278k
  OptLevelChanger OLC(*this, NewOptLevel);
433
278k
434
278k
  TII = MF->getSubtarget().getInstrInfo();
435
278k
  TLI = MF->getSubtarget().getTargetLowering();
436
278k
  RegInfo = &MF->getRegInfo();
437
278k
  LibInfo = &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
438
278k
  GFI = Fn.hasGC() ? 
&getAnalysis<GCModuleInfo>().getFunctionInfo(Fn)81
:
nullptr278k
;
439
278k
  ORE = make_unique<OptimizationRemarkEmitter>(&Fn);
440
278k
  auto *DTWP = getAnalysisIfAvailable<DominatorTreeWrapperPass>();
441
278k
  DominatorTree *DT = DTWP ? 
&DTWP->getDomTree()270k
:
nullptr7.53k
;
442
278k
  auto *LIWP = getAnalysisIfAvailable<LoopInfoWrapperPass>();
443
278k
  LoopInfo *LI = LIWP ? 
&LIWP->getLoopInfo()269k
:
nullptr8.24k
;
444
278k
445
278k
  LLVM_DEBUG(dbgs() << "\n\n\n=== " << Fn.getName() << "\n");
446
278k
447
278k
  SplitCriticalSideEffectEdges(const_cast<Function &>(Fn), DT, LI);
448
278k
449
278k
  CurDAG->init(*MF, *ORE, this, LibInfo,
450
278k
   getAnalysisIfAvailable<LegacyDivergenceAnalysis>());
451
278k
  FuncInfo->set(Fn, *MF, CurDAG);
452
278k
  SwiftError->setFunction(*MF);
453
278k
454
278k
  // Now get the optional analyzes if we want to.
455
278k
  // This is based on the possibly changed OptLevel (after optnone is taken
456
278k
  // into account).  That's unfortunate but OK because it just means we won't
457
278k
  // ask for passes that have been required anyway.
458
278k
459
278k
  if (UseMBPI && 
OptLevel != CodeGenOpt::None278k
)
460
269k
    FuncInfo->BPI = &getAnalysis<BranchProbabilityInfoWrapperPass>().getBPI();
461
8.52k
  else
462
8.52k
    FuncInfo->BPI = nullptr;
463
278k
464
278k
  if (OptLevel != CodeGenOpt::None)
465
269k
    AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
466
8.51k
  else
467
8.51k
    AA = nullptr;
468
278k
469
278k
  SDB->init(GFI, AA, LibInfo);
470
278k
471
278k
  MF->setHasInlineAsm(false);
472
278k
473
278k
  FuncInfo->SplitCSR = false;
474
278k
475
278k
  // We split CSR if the target supports it for the given function
476
278k
  // and the function has only return exits.
477
278k
  if (OptLevel != CodeGenOpt::None && 
TLI->supportSplitCSR(MF)269k
) {
478
2.28k
    FuncInfo->SplitCSR = true;
479
2.28k
480
2.28k
    // Collect all the return blocks.
481
2.49k
    for (const BasicBlock &BB : Fn) {
482
2.49k
      if (!succ_empty(&BB))
483
212
        continue;
484
2.28k
485
2.28k
      const Instruction *Term = BB.getTerminator();
486
2.28k
      if (isa<UnreachableInst>(Term) || 
isa<ReturnInst>(Term)2.28k
)
487
2.28k
        continue;
488
0
489
0
      // Bail out if the exit block is not Return nor Unreachable.
490
0
      FuncInfo->SplitCSR = false;
491
0
      break;
492
0
    }
493
2.28k
  }
494
278k
495
278k
  MachineBasicBlock *EntryMBB = &MF->front();
496
278k
  if (FuncInfo->SplitCSR)
497
2.28k
    // This performs initialization so lowering for SplitCSR will be correct.
498
2.28k
    TLI->initializeSplitCSR(EntryMBB);
499
278k
500
278k
  SelectAllBasicBlocks(Fn);
501
278k
  if (FastISelFailed && 
EnableFastISelFallbackReport9.81k
) {
502
2
    DiagnosticInfoISelFallback DiagFallback(Fn);
503
2
    Fn.getContext().diagnose(DiagFallback);
504
2
  }
505
278k
506
278k
  // Replace forward-declared registers with the registers containing
507
278k
  // the desired value.
508
278k
  // Note: it is important that this happens **before** the call to
509
278k
  // EmitLiveInCopies, since implementations can skip copies of unused
510
278k
  // registers. If we don't apply the reg fixups before, some registers may
511
278k
  // appear as unused and will be skipped, resulting in bad MI.
512
278k
  MachineRegisterInfo &MRI = MF->getRegInfo();
513
278k
  for (DenseMap<unsigned, unsigned>::iterator I = FuncInfo->RegFixups.begin(),
514
278k
                                              E = FuncInfo->RegFixups.end();
515
290k
       I != E; 
++I12.0k
) {
516
12.0k
    unsigned From = I->first;
517
12.0k
    unsigned To = I->second;
518
12.0k
    // If To is also scheduled to be replaced, find what its ultimate
519
12.0k
    // replacement is.
520
12.6k
    while (true) {
521
12.6k
      DenseMap<unsigned, unsigned>::iterator J = FuncInfo->RegFixups.find(To);
522
12.6k
      if (J == E)
523
12.0k
        break;
524
622
      To = J->second;
525
622
    }
526
12.0k
    // Make sure the new register has a sufficiently constrained register class.
527
12.0k
    if (TargetRegisterInfo::isVirtualRegister(From) &&
528
12.0k
        TargetRegisterInfo::isVirtualRegister(To))
529
12.0k
      MRI.constrainRegClass(To, MRI.getRegClass(From));
530
12.0k
    // Replace it.
531
12.0k
532
12.0k
    // Replacing one register with another won't touch the kill flags.
533
12.0k
    // We need to conservatively clear the kill flags as a kill on the old
534
12.0k
    // register might dominate existing uses of the new register.
535
12.0k
    if (!MRI.use_empty(To))
536
556
      MRI.clearKillFlags(From);
537
12.0k
    MRI.replaceRegWith(From, To);
538
12.0k
  }
539
278k
540
278k
  // If the first basic block in the function has live ins that need to be
541
278k
  // copied into vregs, emit the copies into the top of the block before
542
278k
  // emitting the code for the block.
543
278k
  const TargetRegisterInfo &TRI = *MF->getSubtarget().getRegisterInfo();
544
278k
  RegInfo->EmitLiveInCopies(EntryMBB, TRI, *TII);
545
278k
546
278k
  // Insert copies in the entry block and the return blocks.
547
278k
  if (FuncInfo->SplitCSR) {
548
2.28k
    SmallVector<MachineBasicBlock*, 4> Returns;
549
2.28k
    // Collect all the return blocks.
550
2.49k
    for (MachineBasicBlock &MBB : mf) {
551
2.49k
      if (!MBB.succ_empty())
552
214
        continue;
553
2.28k
554
2.28k
      MachineBasicBlock::iterator Term = MBB.getFirstTerminator();
555
2.28k
      if (Term != MBB.end() && 
Term->isReturn()2.27k
) {
556
2.27k
        Returns.push_back(&MBB);
557
2.27k
        continue;
558
2.27k
      }
559
2.28k
    }
560
2.28k
    TLI->insertCopiesSplitCSR(EntryMBB, Returns);
561
2.28k
  }
562
278k
563
278k
  DenseMap<unsigned, unsigned> LiveInMap;
564
278k
  if (!FuncInfo->ArgDbgValues.empty())
565
191
    for (std::pair<unsigned, unsigned> LI : RegInfo->liveins())
566
275
      if (LI.second)
567
274
        LiveInMap.insert(LI);
568
278k
569
278k
  // Insert DBG_VALUE instructions for function arguments to the entry block.
570
278k
  for (unsigned i = 0, e = FuncInfo->ArgDbgValues.size(); i != e; 
++i326
) {
571
326
    MachineInstr *MI = FuncInfo->ArgDbgValues[e-i-1];
572
326
    bool hasFI = MI->getOperand(0).isFI();
573
326
    Register Reg =
574
326
        hasFI ? 
TRI.getFrameRegister(*MF)26
:
MI->getOperand(0).getReg()300
;
575
326
    if (TargetRegisterInfo::isPhysicalRegister(Reg))
576
274
      EntryMBB->insert(EntryMBB->begin(), MI);
577
52
    else {
578
52
      MachineInstr *Def = RegInfo->getVRegDef(Reg);
579
52
      if (Def) {
580
52
        MachineBasicBlock::iterator InsertPos = Def;
581
52
        // FIXME: VR def may not be in entry block.
582
52
        Def->getParent()->insert(std::next(InsertPos), MI);
583
52
      } else
584
52
        LLVM_DEBUG(dbgs() << "Dropping debug info for dead vreg"
585
52
                          << TargetRegisterInfo::virtReg2Index(Reg) << "\n");
586
52
    }
587
326
588
326
    // If Reg is live-in then update debug info to track its copy in a vreg.
589
326
    DenseMap<unsigned, unsigned>::iterator LDI = LiveInMap.find(Reg);
590
326
    if (LDI != LiveInMap.end()) {
591
199
      assert(!hasFI && "There's no handling of frame pointer updating here yet "
592
199
                       "- add if needed");
593
199
      MachineInstr *Def = RegInfo->getVRegDef(LDI->second);
594
199
      MachineBasicBlock::iterator InsertPos = Def;
595
199
      const MDNode *Variable = MI->getDebugVariable();
596
199
      const MDNode *Expr = MI->getDebugExpression();
597
199
      DebugLoc DL = MI->getDebugLoc();
598
199
      bool IsIndirect = MI->isIndirectDebugValue();
599
199
      if (IsIndirect)
600
199
        assert(MI->getOperand(1).getImm() == 0 &&
601
199
               "DBG_VALUE with nonzero offset");
602
199
      assert(cast<DILocalVariable>(Variable)->isValidLocationForIntrinsic(DL) &&
603
199
             "Expected inlined-at fields to agree");
604
199
      // Def is never a terminator here, so it is ok to increment InsertPos.
605
199
      BuildMI(*EntryMBB, ++InsertPos, DL, TII->get(TargetOpcode::DBG_VALUE),
606
199
              IsIndirect, LDI->second, Variable, Expr);
607
199
608
199
      // If this vreg is directly copied into an exported register then
609
199
      // that COPY instructions also need DBG_VALUE, if it is the only
610
199
      // user of LDI->second.
611
199
      MachineInstr *CopyUseMI = nullptr;
612
199
      for (MachineRegisterInfo::use_instr_iterator
613
199
           UI = RegInfo->use_instr_begin(LDI->second),
614
288
           E = RegInfo->use_instr_end(); UI != E; ) {
615
254
        MachineInstr *UseMI = &*(UI++);
616
254
        if (UseMI->isDebugValue()) 
continue39
;
617
215
        if (UseMI->isCopy() && 
!CopyUseMI61
&&
UseMI->getParent() == EntryMBB51
) {
618
50
          CopyUseMI = UseMI; continue;
619
50
        }
620
165
        // Otherwise this is another use or second copy use.
621
165
        CopyUseMI = nullptr; break;
622
165
      }
623
199
      if (CopyUseMI) {
624
34
        // Use MI's debug location, which describes where Variable was
625
34
        // declared, rather than whatever is attached to CopyUseMI.
626
34
        MachineInstr *NewMI =
627
34
            BuildMI(*MF, DL, TII->get(TargetOpcode::DBG_VALUE), IsIndirect,
628
34
                    CopyUseMI->getOperand(0).getReg(), Variable, Expr);
629
34
        MachineBasicBlock::iterator Pos = CopyUseMI;
630
34
        EntryMBB->insertAfter(Pos, NewMI);
631
34
      }
632
199
    }
633
326
  }
634
278k
635
278k
  // Determine if there are any calls in this machine function.
636
278k
  MachineFrameInfo &MFI = MF->getFrameInfo();
637
1.22M
  for (const auto &MBB : *MF) {
638
1.22M
    if (MFI.hasCalls() && 
MF->hasInlineAsm()686k
)
639
1.92k
      break;
640
1.22M
641
11.1M
    
for (const auto &MI : MBB)1.22M
{
642
11.1M
      const MCInstrDesc &MCID = TII->get(MI.getOpcode());
643
11.1M
      if ((MCID.isCall() && 
!MCID.isReturn()454k
) ||
644
11.1M
          
MI.isStackAligningInlineAsm()10.7M
) {
645
390k
        MFI.setHasCalls(true);
646
390k
      }
647
11.1M
      if (MI.isInlineAsm()) {
648
18.2k
        MF->setHasInlineAsm(true);
649
18.2k
      }
650
11.1M
    }
651
1.22M
  }
652
278k
653
278k
  // Determine if there is a call to setjmp in the machine function.
654
278k
  MF->setExposesReturnsTwice(Fn.callsFunctionThatReturnsTwice());
655
278k
656
278k
  // Determine if floating point is used for msvc
657
278k
  computeUsesMSVCFloatingPoint(TM.getTargetTriple(), Fn, MF->getMMI());
658
278k
659
278k
  // Replace forward-declared registers with the registers containing
660
278k
  // the desired value.
661
278k
  for (DenseMap<unsigned, unsigned>::iterator
662
278k
       I = FuncInfo->RegFixups.begin(), E = FuncInfo->RegFixups.end();
663
290k
       I != E; 
++I12.0k
) {
664
12.0k
    unsigned From = I->first;
665
12.0k
    unsigned To = I->second;
666
12.0k
    // If To is also scheduled to be replaced, find what its ultimate
667
12.0k
    // replacement is.
668
12.6k
    while (true) {
669
12.6k
      DenseMap<unsigned, unsigned>::iterator J = FuncInfo->RegFixups.find(To);
670
12.6k
      if (J == E) 
break12.0k
;
671
622
      To = J->second;
672
622
    }
673
12.0k
    // Make sure the new register has a sufficiently constrained register class.
674
12.0k
    if (TargetRegisterInfo::isVirtualRegister(From) &&
675
12.0k
        TargetRegisterInfo::isVirtualRegister(To))
676
12.0k
      MRI.constrainRegClass(To, MRI.getRegClass(From));
677
12.0k
    // Replace it.
678
12.0k
679
12.0k
680
12.0k
    // Replacing one register with another won't touch the kill flags.
681
12.0k
    // We need to conservatively clear the kill flags as a kill on the old
682
12.0k
    // register might dominate existing uses of the new register.
683
12.0k
    if (!MRI.use_empty(To))
684
11.8k
      MRI.clearKillFlags(From);
685
12.0k
    MRI.replaceRegWith(From, To);
686
12.0k
  }
687
278k
688
278k
  TLI->finalizeLowering(*MF);
689
278k
690
278k
  // Release function-specific state. SDB and CurDAG are already cleared
691
278k
  // at this point.
692
278k
  FuncInfo->clear();
693
278k
694
278k
  LLVM_DEBUG(dbgs() << "*** MachineFunction at end of ISel ***\n");
695
278k
  LLVM_DEBUG(MF->print(dbgs()));
696
278k
697
278k
  return true;
698
278k
}
699
700
static void reportFastISelFailure(MachineFunction &MF,
701
                                  OptimizationRemarkEmitter &ORE,
702
                                  OptimizationRemarkMissed &R,
703
17.4k
                                  bool ShouldAbort) {
704
17.4k
  // Print the function name explicitly if we don't have a debug location (which
705
17.4k
  // makes the diagnostic less useful) or if we're going to emit a raw error.
706
17.4k
  if (!R.getLocation().isValid() || 
ShouldAbort331
)
707
17.1k
    R << (" (in function: " + MF.getName() + ")").str();
708
17.4k
709
17.4k
  if (ShouldAbort)
710
3
    report_fatal_error(R.getMsg());
711
17.4k
712
17.4k
  ORE.emit(R);
713
17.4k
}
714
715
void SelectionDAGISel::SelectBasicBlock(BasicBlock::const_iterator Begin,
716
                                        BasicBlock::const_iterator End,
717
1.19M
                                        bool &HadTailCall) {
718
1.19M
  // Allow creating illegal types during DAG building for the basic block.
719
1.19M
  CurDAG->NewNodesMustHaveLegalTypes = false;
720
1.19M
721
1.19M
  // Lower the instructions. If a call is emitted as a tail call, cease emitting
722
1.19M
  // nodes for this block.
723
7.97M
  for (BasicBlock::const_iterator I = Begin; I != End && 
!SDB->HasTailCall6.84M
;
++I6.77M
) {
724
6.77M
    if (!ElidedArgCopyInstrs.count(&*I))
725
6.77M
      SDB->visit(*I);
726
6.77M
  }
727
1.19M
728
1.19M
  // Make sure the root of the DAG is up-to-date.
729
1.19M
  CurDAG->setRoot(SDB->getControlRoot());
730
1.19M
  HadTailCall = SDB->HasTailCall;
731
1.19M
  SDB->resolveOrClearDbgInfo();
732
1.19M
  SDB->clear();
733
1.19M
734
1.19M
  // Final step, emit the lowered DAG as machine code.
735
1.19M
  CodeGenAndEmitDAG();
736
1.19M
}
737
738
1.23M
void SelectionDAGISel::ComputeLiveOutVRegInfo() {
739
1.23M
  SmallPtrSet<SDNode*, 16> VisitedNodes;
740
1.23M
  SmallVector<SDNode*, 128> Worklist;
741
1.23M
742
1.23M
  Worklist.push_back(CurDAG->getRoot().getNode());
743
1.23M
744
1.23M
  KnownBits Known;
745
1.23M
746
10.2M
  do {
747
10.2M
    SDNode *N = Worklist.pop_back_val();
748
10.2M
749
10.2M
    // If we've already seen this node, ignore it.
750
10.2M
    if (!VisitedNodes.insert(N).second)
751
1.11M
      continue;
752
9.12M
753
9.12M
    // Otherwise, add all chain operands to the worklist.
754
9.12M
    for (const SDValue &Op : N->op_values())
755
22.9M
      if (Op.getValueType() == MVT::Other)
756
9.00M
        Worklist.push_back(Op.getNode());
757
9.12M
758
9.12M
    // If this is a CopyToReg with a vreg dest, process it.
759
9.12M
    if (N->getOpcode() != ISD::CopyToReg)
760
7.14M
      continue;
761
1.97M
762
1.97M
    unsigned DestReg = cast<RegisterSDNode>(N->getOperand(1))->getReg();
763
1.97M
    if (!TargetRegisterInfo::isVirtualRegister(DestReg))
764
1.13M
      continue;
765
843k
766
843k
    // Ignore non-integer values.
767
843k
    SDValue Src = N->getOperand(2);
768
843k
    EVT SrcVT = Src.getValueType();
769
843k
    if (!SrcVT.isInteger())
770
31.6k
      continue;
771
811k
772
811k
    unsigned NumSignBits = CurDAG->ComputeNumSignBits(Src);
773
811k
    Known = CurDAG->computeKnownBits(Src);
774
811k
    FuncInfo->AddLiveOutRegInfo(DestReg, NumSignBits, Known);
775
10.2M
  } while (!Worklist.empty());
776
1.23M
}
777
778
1.24M
void SelectionDAGISel::CodeGenAndEmitDAG() {
779
1.24M
  StringRef GroupName = "sdag";
780
1.24M
  StringRef GroupDescription = "Instruction Selection and Scheduling";
781
1.24M
  std::string BlockName;
782
1.24M
  bool MatchFilterBB = false; (void)MatchFilterBB;
783
#ifndef NDEBUG
784
  TargetTransformInfo &TTI =
785
      getAnalysis<TargetTransformInfoWrapperPass>().getTTI(*FuncInfo->Fn);
786
#endif
787
788
1.24M
  // Pre-type legalization allow creation of any node types.
789
1.24M
  CurDAG->NewNodesMustHaveLegalTypes = false;
790
1.24M
791
#ifndef NDEBUG
792
  MatchFilterBB = (FilterDAGBasicBlockName.empty() ||
793
                   FilterDAGBasicBlockName ==
794
                       FuncInfo->MBB->getBasicBlock()->getName());
795
#endif
796
#ifdef NDEBUG
797
1.24M
  if (ViewDAGCombine1 || 
ViewLegalizeTypesDAGs0
||
ViewLegalizeDAGs0
||
798
1.24M
      
ViewDAGCombine20
||
ViewDAGCombineLT0
||
ViewISelDAGs0
||
ViewSchedDAGs0
||
799
1.24M
      
ViewSUnitDAGs0
)
800
0
#endif
801
0
  {
802
0
    BlockName =
803
0
        (MF->getName() + ":" + FuncInfo->MBB->getBasicBlock()->getName()).str();
804
0
  }
805
1.24M
  LLVM_DEBUG(dbgs() << "Initial selection DAG: "
806
1.24M
                    << printMBBReference(*FuncInfo->MBB) << " '" << BlockName
807
1.24M
                    << "'\n";
808
1.24M
             CurDAG->dump());
809
1.24M
810
1.24M
  if (ViewDAGCombine1 && 
MatchFilterBB0
)
811
0
    CurDAG->viewGraph("dag-combine1 input for " + BlockName);
812
1.24M
813
1.24M
  // Run the DAG combiner in pre-legalize mode.
814
1.24M
  {
815
1.24M
    NamedRegionTimer T("combine1", "DAG Combining 1", GroupName,
816
1.24M
                       GroupDescription, TimePassesIsEnabled);
817
1.24M
    CurDAG->Combine(BeforeLegalizeTypes, AA, OptLevel);
818
1.24M
  }
819
1.24M
820
#ifndef NDEBUG
821
  if (TTI.hasBranchDivergence())
822
    CurDAG->VerifyDAGDiverence();
823
#endif
824
825
1.24M
  LLVM_DEBUG(dbgs() << "Optimized lowered selection DAG: "
826
1.24M
                    << printMBBReference(*FuncInfo->MBB) << " '" << BlockName
827
1.24M
                    << "'\n";
828
1.24M
             CurDAG->dump());
829
1.24M
830
1.24M
  // Second step, hack on the DAG until it only uses operations and types that
831
1.24M
  // the target supports.
832
1.24M
  if (ViewLegalizeTypesDAGs && 
MatchFilterBB0
)
833
0
    CurDAG->viewGraph("legalize-types input for " + BlockName);
834
1.24M
835
1.24M
  bool Changed;
836
1.24M
  {
837
1.24M
    NamedRegionTimer T("legalize_types", "Type Legalization", GroupName,
838
1.24M
                       GroupDescription, TimePassesIsEnabled);
839
1.24M
    Changed = CurDAG->LegalizeTypes();
840
1.24M
  }
841
1.24M
842
#ifndef NDEBUG
843
  if (TTI.hasBranchDivergence())
844
    CurDAG->VerifyDAGDiverence();
845
#endif
846
847
1.24M
  LLVM_DEBUG(dbgs() << "Type-legalized selection DAG: "
848
1.24M
                    << printMBBReference(*FuncInfo->MBB) << " '" << BlockName
849
1.24M
                    << "'\n";
850
1.24M
             CurDAG->dump());
851
1.24M
852
1.24M
  // Only allow creation of legal node types.
853
1.24M
  CurDAG->NewNodesMustHaveLegalTypes = true;
854
1.24M
855
1.24M
  if (Changed) {
856
350k
    if (ViewDAGCombineLT && 
MatchFilterBB0
)
857
0
      CurDAG->viewGraph("dag-combine-lt input for " + BlockName);
858
350k
859
350k
    // Run the DAG combiner in post-type-legalize mode.
860
350k
    {
861
350k
      NamedRegionTimer T("combine_lt", "DAG Combining after legalize types",
862
350k
                         GroupName, GroupDescription, TimePassesIsEnabled);
863
350k
      CurDAG->Combine(AfterLegalizeTypes, AA, OptLevel);
864
350k
    }
865
350k
866
#ifndef NDEBUG
867
    if (TTI.hasBranchDivergence())
868
      CurDAG->VerifyDAGDiverence();
869
#endif
870
871
350k
    LLVM_DEBUG(dbgs() << "Optimized type-legalized selection DAG: "
872
350k
                      << printMBBReference(*FuncInfo->MBB) << " '" << BlockName
873
350k
                      << "'\n";
874
350k
               CurDAG->dump());
875
350k
  }
876
1.24M
877
1.24M
  {
878
1.24M
    NamedRegionTimer T("legalize_vec", "Vector Legalization", GroupName,
879
1.24M
                       GroupDescription, TimePassesIsEnabled);
880
1.24M
    Changed = CurDAG->LegalizeVectors();
881
1.24M
  }
882
1.24M
883
1.24M
  if (Changed) {
884
41.0k
    LLVM_DEBUG(dbgs() << "Vector-legalized selection DAG: "
885
41.0k
                      << printMBBReference(*FuncInfo->MBB) << " '" << BlockName
886
41.0k
                      << "'\n";
887
41.0k
               CurDAG->dump());
888
41.0k
889
41.0k
    {
890
41.0k
      NamedRegionTimer T("legalize_types2", "Type Legalization 2", GroupName,
891
41.0k
                         GroupDescription, TimePassesIsEnabled);
892
41.0k
      CurDAG->LegalizeTypes();
893
41.0k
    }
894
41.0k
895
41.0k
    LLVM_DEBUG(dbgs() << "Vector/type-legalized selection DAG: "
896
41.0k
                      << printMBBReference(*FuncInfo->MBB) << " '" << BlockName
897
41.0k
                      << "'\n";
898
41.0k
               CurDAG->dump());
899
41.0k
900
41.0k
    if (ViewDAGCombineLT && 
MatchFilterBB0
)
901
0
      CurDAG->viewGraph("dag-combine-lv input for " + BlockName);
902
41.0k
903
41.0k
    // Run the DAG combiner in post-type-legalize mode.
904
41.0k
    {
905
41.0k
      NamedRegionTimer T("combine_lv", "DAG Combining after legalize vectors",
906
41.0k
                         GroupName, GroupDescription, TimePassesIsEnabled);
907
41.0k
      CurDAG->Combine(AfterLegalizeVectorOps, AA, OptLevel);
908
41.0k
    }
909
41.0k
910
41.0k
    LLVM_DEBUG(dbgs() << "Optimized vector-legalized selection DAG: "
911
41.0k
                      << printMBBReference(*FuncInfo->MBB) << " '" << BlockName
912
41.0k
                      << "'\n";
913
41.0k
               CurDAG->dump());
914
41.0k
915
#ifndef NDEBUG
916
    if (TTI.hasBranchDivergence())
917
      CurDAG->VerifyDAGDiverence();
918
#endif
919
  }
920
1.24M
921
1.24M
  if (ViewLegalizeDAGs && 
MatchFilterBB0
)
922
0
    CurDAG->viewGraph("legalize input for " + BlockName);
923
1.24M
924
1.24M
  {
925
1.24M
    NamedRegionTimer T("legalize", "DAG Legalization", GroupName,
926
1.24M
                       GroupDescription, TimePassesIsEnabled);
927
1.24M
    CurDAG->Legalize();
928
1.24M
  }
929
1.24M
930
#ifndef NDEBUG
931
  if (TTI.hasBranchDivergence())
932
    CurDAG->VerifyDAGDiverence();
933
#endif
934
935
1.24M
  LLVM_DEBUG(dbgs() << "Legalized selection DAG: "
936
1.24M
                    << printMBBReference(*FuncInfo->MBB) << " '" << BlockName
937
1.24M
                    << "'\n";
938
1.24M
             CurDAG->dump());
939
1.24M
940
1.24M
  if (ViewDAGCombine2 && 
MatchFilterBB0
)
941
0
    CurDAG->viewGraph("dag-combine2 input for " + BlockName);
942
1.24M
943
1.24M
  // Run the DAG combiner in post-legalize mode.
944
1.24M
  {
945
1.24M
    NamedRegionTimer T("combine2", "DAG Combining 2", GroupName,
946
1.24M
                       GroupDescription, TimePassesIsEnabled);
947
1.24M
    CurDAG->Combine(AfterLegalizeDAG, AA, OptLevel);
948
1.24M
  }
949
1.24M
950
#ifndef NDEBUG
951
  if (TTI.hasBranchDivergence())
952
    CurDAG->VerifyDAGDiverence();
953
#endif
954
955
1.24M
  LLVM_DEBUG(dbgs() << "Optimized legalized selection DAG: "
956
1.24M
                    << printMBBReference(*FuncInfo->MBB) << " '" << BlockName
957
1.24M
                    << "'\n";
958
1.24M
             CurDAG->dump());
959
1.24M
960
1.24M
  if (OptLevel != CodeGenOpt::None)
961
1.23M
    ComputeLiveOutVRegInfo();
962
1.24M
963
1.24M
  if (ViewISelDAGs && 
MatchFilterBB0
)
964
0
    CurDAG->viewGraph("isel input for " + BlockName);
965
1.24M
966
1.24M
  // Third, instruction select all of the operations to machine code, adding the
967
1.24M
  // code to the MachineBasicBlock.
968
1.24M
  {
969
1.24M
    NamedRegionTimer T("isel", "Instruction Selection", GroupName,
970
1.24M
                       GroupDescription, TimePassesIsEnabled);
971
1.24M
    DoInstructionSelection();
972
1.24M
  }
973
1.24M
974
1.24M
  LLVM_DEBUG(dbgs() << "Selected selection DAG: "
975
1.24M
                    << printMBBReference(*FuncInfo->MBB) << " '" << BlockName
976
1.24M
                    << "'\n";
977
1.24M
             CurDAG->dump());
978
1.24M
979
1.24M
  if (ViewSchedDAGs && 
MatchFilterBB0
)
980
0
    CurDAG->viewGraph("scheduler input for " + BlockName);
981
1.24M
982
1.24M
  // Schedule machine code.
983
1.24M
  ScheduleDAGSDNodes *Scheduler = CreateScheduler();
984
1.24M
  {
985
1.24M
    NamedRegionTimer T("sched", "Instruction Scheduling", GroupName,
986
1.24M
                       GroupDescription, TimePassesIsEnabled);
987
1.24M
    Scheduler->Run(CurDAG, FuncInfo->MBB);
988
1.24M
  }
989
1.24M
990
1.24M
  if (ViewSUnitDAGs && 
MatchFilterBB0
)
991
0
    Scheduler->viewGraph();
992
1.24M
993
1.24M
  // Emit machine code to BB.  This can change 'BB' to the last block being
994
1.24M
  // inserted into.
995
1.24M
  MachineBasicBlock *FirstMBB = FuncInfo->MBB, *LastMBB;
996
1.24M
  {
997
1.24M
    NamedRegionTimer T("emit", "Instruction Creation", GroupName,
998
1.24M
                       GroupDescription, TimePassesIsEnabled);
999
1.24M
1000
1.24M
    // FuncInfo->InsertPt is passed by reference and set to the end of the
1001
1.24M
    // scheduled instructions.
1002
1.24M
    LastMBB = FuncInfo->MBB = Scheduler->EmitSchedule(FuncInfo->InsertPt);
1003
1.24M
  }
1004
1.24M
1005
1.24M
  // If the block was split, make sure we update any references that are used to
1006
1.24M
  // update PHI nodes later on.
1007
1.24M
  if (FirstMBB != LastMBB)
1008
0
    SDB->UpdateSplitBlock(FirstMBB, LastMBB);
1009
1.24M
1010
1.24M
  // Free the scheduler state.
1011
1.24M
  {
1012
1.24M
    NamedRegionTimer T("cleanup", "Instruction Scheduling Cleanup", GroupName,
1013
1.24M
                       GroupDescription, TimePassesIsEnabled);
1014
1.24M
    delete Scheduler;
1015
1.24M
  }
1016
1.24M
1017
1.24M
  // Free the SelectionDAG state, now that we're finished with it.
1018
1.24M
  CurDAG->clear();
1019
1.24M
}
1020
1021
namespace {
1022
1023
/// ISelUpdater - helper class to handle updates of the instruction selection
1024
/// graph.
1025
class ISelUpdater : public SelectionDAG::DAGUpdateListener {
1026
  SelectionDAG::allnodes_iterator &ISelPosition;
1027
1028
public:
1029
  ISelUpdater(SelectionDAG &DAG, SelectionDAG::allnodes_iterator &isp)
1030
1.24M
    : SelectionDAG::DAGUpdateListener(DAG), ISelPosition(isp) {}
1031
1032
  /// NodeDeleted - Handle nodes deleted from the graph. If the node being
1033
  /// deleted is the current ISelPosition node, update ISelPosition.
1034
  ///
1035
5.49M
  void NodeDeleted(SDNode *N, SDNode *E) override {
1036
5.49M
    if (ISelPosition == SelectionDAG::allnodes_iterator(N))
1037
750k
      ++ISelPosition;
1038
5.49M
  }
1039
};
1040
1041
} // end anonymous namespace
1042
1043
// This function is used to enforce the topological node id property
1044
// property leveraged during Instruction selection. Before selection all
1045
// nodes are given a non-negative id such that all nodes have a larger id than
1046
// their operands. As this holds transitively we can prune checks that a node N
1047
// is a predecessor of M another by not recursively checking through M's
1048
// operands if N's ID is larger than M's ID. This is significantly improves
1049
// performance of for various legality checks (e.g. IsLegalToFold /
1050
// UpdateChains).
1051
1052
// However, when we fuse multiple nodes into a single node
1053
// during selection we may induce a predecessor relationship between inputs and
1054
// outputs of distinct nodes being merged violating the topological property.
1055
// Should a fused node have a successor which has yet to be selected, our
1056
// legality checks would be incorrect. To avoid this we mark all unselected
1057
// sucessor nodes, i.e. id != -1 as invalid for pruning by bit-negating (x =>
1058
// (-(x+1))) the ids and modify our pruning check to ignore negative Ids of M.
1059
// We use bit-negation to more clearly enforce that node id -1 can only be
1060
// achieved by selected nodes). As the conversion is reversable the original Id,
1061
// topological pruning can still be leveraged when looking for unselected nodes.
1062
// This method is call internally in all ISel replacement calls.
1063
10.3M
void SelectionDAGISel::EnforceNodeIdInvariant(SDNode *Node) {
1064
10.3M
  SmallVector<SDNode *, 4> Nodes;
1065
10.3M
  Nodes.push_back(Node);
1066
10.3M
1067
21.2M
  while (!Nodes.empty()) {
1068
10.8M
    SDNode *N = Nodes.pop_back_val();
1069
14.8M
    for (auto *U : N->uses()) {
1070
14.8M
      auto UId = U->getNodeId();
1071
14.8M
      if (UId > 0) {
1072
477k
        InvalidateNodeId(U);
1073
477k
        Nodes.push_back(U);
1074
477k
      }
1075
14.8M
    }
1076
10.8M
  }
1077
10.3M
}
1078
1079
// InvalidateNodeId - As discusses in EnforceNodeIdInvariant, mark a
1080
// NodeId with the equivalent node id which is invalid for topological
1081
// pruning.
1082
490k
void SelectionDAGISel::InvalidateNodeId(SDNode *N) {
1083
490k
  int InvalidId = -(N->getNodeId() + 1);
1084
490k
  N->setNodeId(InvalidId);
1085
490k
}
1086
1087
// getUninvalidatedNodeId - get original uninvalidated node id.
1088
1.96k
int SelectionDAGISel::getUninvalidatedNodeId(SDNode *N) {
1089
1.96k
  int Id = N->getNodeId();
1090
1.96k
  if (Id < -1)
1091
260
    return -(Id + 1);
1092
1.70k
  return Id;
1093
1.70k
}
1094
1095
1.24M
void SelectionDAGISel::DoInstructionSelection() {
1096
1.24M
  LLVM_DEBUG(dbgs() << "===== Instruction selection begins: "
1097
1.24M
                    << printMBBReference(*FuncInfo->MBB) << " '"
1098
1.24M
                    << FuncInfo->MBB->getName() << "'\n");
1099
1.24M
1100
1.24M
  PreprocessISelDAG();
1101
1.24M
1102
1.24M
  // Select target instructions for the DAG.
1103
1.24M
  {
1104
1.24M
    // Number all nodes with a topological order and set DAGSize.
1105
1.24M
    DAGSize = CurDAG->AssignTopologicalOrder();
1106
1.24M
1107
1.24M
    // Create a dummy node (which is not added to allnodes), that adds
1108
1.24M
    // a reference to the root node, preventing it from being deleted,
1109
1.24M
    // and tracking any changes of the root.
1110
1.24M
    HandleSDNode Dummy(CurDAG->getRoot());
1111
1.24M
    SelectionDAG::allnodes_iterator ISelPosition (CurDAG->getRoot().getNode());
1112
1.24M
    ++ISelPosition;
1113
1.24M
1114
1.24M
    // Make sure that ISelPosition gets properly updated when nodes are deleted
1115
1.24M
    // in calls made from this function.
1116
1.24M
    ISelUpdater ISU(*CurDAG, ISelPosition);
1117
1.24M
1118
1.24M
    // The AllNodes list is now topological-sorted. Visit the
1119
1.24M
    // nodes by starting at the end of the list (the root of the
1120
1.24M
    // graph) and preceding back toward the beginning (the entry
1121
1.24M
    // node).
1122
22.5M
    while (ISelPosition != CurDAG->allnodes_begin()) {
1123
21.2M
      SDNode *Node = &*--ISelPosition;
1124
21.2M
      // Skip dead nodes. DAGCombiner is expected to eliminate all dead nodes,
1125
21.2M
      // but there are currently some corner cases that it misses. Also, this
1126
21.2M
      // makes it theoretically possible to disable the DAGCombiner.
1127
21.2M
      if (Node->use_empty())
1128
2.55k
        continue;
1129
21.2M
1130
#ifndef NDEBUG
1131
      SmallVector<SDNode *, 4> Nodes;
1132
      Nodes.push_back(Node);
1133
1134
      while (!Nodes.empty()) {
1135
        auto N = Nodes.pop_back_val();
1136
        if (N->getOpcode() == ISD::TokenFactor || N->getNodeId() < 0)
1137
          continue;
1138
        for (const SDValue &Op : N->op_values()) {
1139
          if (Op->getOpcode() == ISD::TokenFactor)
1140
            Nodes.push_back(Op.getNode());
1141
          else {
1142
            // We rely on topological ordering of node ids for checking for
1143
            // cycles when fusing nodes during selection. All unselected nodes
1144
            // successors of an already selected node should have a negative id.
1145
            // This assertion will catch such cases. If this assertion triggers
1146
            // it is likely you using DAG-level Value/Node replacement functions
1147
            // (versus equivalent ISEL replacement) in backend-specific
1148
            // selections. See comment in EnforceNodeIdInvariant for more
1149
            // details.
1150
            assert(Op->getNodeId() != -1 &&
1151
                   "Node has already selected predecessor node");
1152
          }
1153
        }
1154
      }
1155
#endif
1156
1157
21.2M
      // When we are using non-default rounding modes or FP exception behavior
1158
21.2M
      // FP operations are represented by StrictFP pseudo-operations.  For
1159
21.2M
      // targets that do not (yet) understand strict FP operations directly,
1160
21.2M
      // we convert them to normal FP opcodes instead at this point.  This
1161
21.2M
      // will allow them to be handled by existing target-specific instruction
1162
21.2M
      // selectors.
1163
21.2M
      if (Node->isStrictFPOpcode() &&
1164
21.2M
          (TLI->getOperationAction(Node->getOpcode(), Node->getValueType(0))
1165
1.19k
           != TargetLowering::Legal))
1166
398
        Node = CurDAG->mutateStrictFPToFP(Node);
1167
21.2M
1168
21.2M
      LLVM_DEBUG(dbgs() << "\nISEL: Starting selection on root node: ";
1169
21.2M
                 Node->dump(CurDAG));
1170
21.2M
1171
21.2M
      Select(Node);
1172
21.2M
    }
1173
1.24M
1174
1.24M
    CurDAG->setRoot(Dummy.getValue());
1175
1.24M
  }
1176
1.24M
1177
1.24M
  LLVM_DEBUG(dbgs() << "\n===== Instruction selection ends:\n");
1178
1.24M
1179
1.24M
  PostprocessISelDAG();
1180
1.24M
}
1181
1182
118
static bool hasExceptionPointerOrCodeUser(const CatchPadInst *CPI) {
1183
172
  for (const User *U : CPI->users()) {
1184
172
    if (const IntrinsicInst *EHPtrCall = dyn_cast<IntrinsicInst>(U)) {
1185
7
      Intrinsic::ID IID = EHPtrCall->getIntrinsicID();
1186
7
      if (IID == Intrinsic::eh_exceptionpointer ||
1187
7
          
IID == Intrinsic::eh_exceptioncode4
)
1188
7
        return true;
1189
7
    }
1190
172
  }
1191
118
  
return false111
;
1192
118
}
1193
1194
// wasm.landingpad.index intrinsic is for associating a landing pad index number
1195
// with a catchpad instruction. Retrieve the landing pad index in the intrinsic
1196
// and store the mapping in the function.
1197
static void mapWasmLandingPadIndex(MachineBasicBlock *MBB,
1198
50
                                   const CatchPadInst *CPI) {
1199
50
  MachineFunction *MF = MBB->getParent();
1200
50
  // In case of single catch (...), we don't emit LSDA, so we don't need
1201
50
  // this information.
1202
50
  bool IsSingleCatchAllClause =
1203
50
      CPI->getNumArgOperands() == 1 &&
1204
50
      
cast<Constant>(CPI->getArgOperand(0))->isNullValue()44
;
1205
50
  if (!IsSingleCatchAllClause) {
1206
16
    // Create a mapping from landing pad label to landing pad index.
1207
16
    bool IntrFound = false;
1208
32
    for (const User *U : CPI->users()) {
1209
32
      if (const auto *Call = dyn_cast<IntrinsicInst>(U)) {
1210
16
        Intrinsic::ID IID = Call->getIntrinsicID();
1211
16
        if (IID == Intrinsic::wasm_landingpad_index) {
1212
16
          Value *IndexArg = Call->getArgOperand(1);
1213
16
          int Index = cast<ConstantInt>(IndexArg)->getZExtValue();
1214
16
          MF->setWasmLandingPadIndex(MBB, Index);
1215
16
          IntrFound = true;
1216
16
          break;
1217
16
        }
1218
16
      }
1219
32
    }
1220
16
    assert(IntrFound && "wasm.landingpad.index intrinsic not found!");
1221
16
    (void)IntrFound;
1222
16
  }
1223
50
}
1224
1225
/// PrepareEHLandingPad - Emit an EH_LABEL, set up live-in registers, and
1226
/// do other setup for EH landing-pad blocks.
1227
3.78k
bool SelectionDAGISel::PrepareEHLandingPad() {
1228
3.78k
  MachineBasicBlock *MBB = FuncInfo->MBB;
1229
3.78k
  const Constant *PersonalityFn = FuncInfo->Fn->getPersonalityFn();
1230
3.78k
  const BasicBlock *LLVMBB = MBB->getBasicBlock();
1231
3.78k
  const TargetRegisterClass *PtrRC =
1232
3.78k
      TLI->getRegClassFor(TLI->getPointerTy(CurDAG->getDataLayout()));
1233
3.78k
1234
3.78k
  auto Pers = classifyEHPersonality(PersonalityFn);
1235
3.78k
1236
3.78k
  // Catchpads have one live-in register, which typically holds the exception
1237
3.78k
  // pointer or code.
1238
3.78k
  if (isFuncletEHPersonality(Pers)) {
1239
164
    if (const auto *CPI = dyn_cast<CatchPadInst>(LLVMBB->getFirstNonPHI())) {
1240
118
      if (hasExceptionPointerOrCodeUser(CPI)) {
1241
7
        // Get or create the virtual register to hold the pointer or code.  Mark
1242
7
        // the live in physreg and copy into the vreg.
1243
7
        MCPhysReg EHPhysReg = TLI->getExceptionPointerRegister(PersonalityFn);
1244
7
        assert(EHPhysReg && "target lacks exception pointer register");
1245
7
        MBB->addLiveIn(EHPhysReg);
1246
7
        unsigned VReg = FuncInfo->getCatchPadExceptionPointerVReg(CPI, PtrRC);
1247
7
        BuildMI(*MBB, FuncInfo->InsertPt, SDB->getCurDebugLoc(),
1248
7
                TII->get(TargetOpcode::COPY), VReg)
1249
7
            .addReg(EHPhysReg, RegState::Kill);
1250
7
      }
1251
118
    }
1252
164
    return true;
1253
164
  }
1254
3.62k
1255
3.62k
  // Add a label to mark the beginning of the landing pad.  Deletion of the
1256
3.62k
  // landing pad can thus be detected via the MachineModuleInfo.
1257
3.62k
  MCSymbol *Label = MF->addLandingPad(MBB);
1258
3.62k
1259
3.62k
  const MCInstrDesc &II = TII->get(TargetOpcode::EH_LABEL);
1260
3.62k
  BuildMI(*MBB, FuncInfo->InsertPt, SDB->getCurDebugLoc(), II)
1261
3.62k
    .addSym(Label);
1262
3.62k
1263
3.62k
  if (Pers == EHPersonality::Wasm_CXX) {
1264
70
    if (const auto *CPI = dyn_cast<CatchPadInst>(LLVMBB->getFirstNonPHI()))
1265
50
      mapWasmLandingPadIndex(MBB, CPI);
1266
3.55k
  } else {
1267
3.55k
    // Assign the call site to the landing pad's begin label.
1268
3.55k
    MF->setCallSiteLandingPad(Label, SDB->LPadToCallSiteMap[MBB]);
1269
3.55k
    // Mark exception register as live in.
1270
3.55k
    if (unsigned Reg = TLI->getExceptionPointerRegister(PersonalityFn))
1271
3.43k
      FuncInfo->ExceptionPointerVirtReg = MBB->addLiveIn(Reg, PtrRC);
1272
3.55k
    // Mark exception selector register as live in.
1273
3.55k
    if (unsigned Reg = TLI->getExceptionSelectorRegister(PersonalityFn))
1274
3.43k
      FuncInfo->ExceptionSelectorVirtReg = MBB->addLiveIn(Reg, PtrRC);
1275
3.55k
  }
1276
3.62k
1277
3.62k
  return true;
1278
3.62k
}
1279
1280
/// isFoldedOrDeadInstruction - Return true if the specified instruction is
1281
/// side-effect free and is either dead or folded into a generated instruction.
1282
/// Return false if it needs to be emitted.
1283
static bool isFoldedOrDeadInstruction(const Instruction *I,
1284
74.7k
                                      FunctionLoweringInfo *FuncInfo) {
1285
74.7k
  return !I->mayWriteToMemory() && // Side-effecting instructions aren't folded.
1286
74.7k
         
!I->isTerminator()61.0k
&& // Terminators aren't folded.
1287
74.7k
         
!isa<DbgInfoIntrinsic>(I)45.3k
&& // Debug instructions aren't folded.
1288
74.7k
         
!I->isEHPad()44.1k
&& // EH pad instructions aren't folded.
1289
74.7k
         
!FuncInfo->isExportedInst(I)44.1k
; // Exported instrs must be computed.
1290
74.7k
}
1291
1292
/// Collect llvm.dbg.declare information. This is done after argument lowering
1293
/// in case the declarations refer to arguments.
1294
278k
static void processDbgDeclares(FunctionLoweringInfo *FuncInfo) {
1295
278k
  MachineFunction *MF = FuncInfo->MF;
1296
278k
  const DataLayout &DL = MF->getDataLayout();
1297
1.20M
  for (const BasicBlock &BB : *FuncInfo->Fn) {
1298
7.12M
    for (const Instruction &I : BB) {
1299
7.12M
      const DbgDeclareInst *DI = dyn_cast<DbgDeclareInst>(&I);
1300
7.12M
      if (!DI)
1301
7.12M
        continue;
1302
1.01k
1303
1.01k
      assert(DI->getVariable() && "Missing variable");
1304
1.01k
      assert(DI->getDebugLoc() && "Missing location");
1305
1.01k
      const Value *Address = DI->getAddress();
1306
1.01k
      if (!Address)
1307
7
        continue;
1308
1.01k
1309
1.01k
      // Look through casts and constant offset GEPs. These mostly come from
1310
1.01k
      // inalloca.
1311
1.01k
      APInt Offset(DL.getTypeSizeInBits(Address->getType()), 0);
1312
1.01k
      Address = Address->stripAndAccumulateInBoundsConstantOffsets(DL, Offset);
1313
1.01k
1314
1.01k
      // Check if the variable is a static alloca or a byval or inalloca
1315
1.01k
      // argument passed in memory. If it is not, then we will ignore this
1316
1.01k
      // intrinsic and handle this during isel like dbg.value.
1317
1.01k
      int FI = std::numeric_limits<int>::max();
1318
1.01k
      if (const auto *AI = dyn_cast<AllocaInst>(Address)) {
1319
929
        auto SI = FuncInfo->StaticAllocaMap.find(AI);
1320
929
        if (SI != FuncInfo->StaticAllocaMap.end())
1321
916
          FI = SI->second;
1322
929
      } else 
if (const auto *82
Arg82
= dyn_cast<Argument>(Address))
1323
53
        FI = FuncInfo->getArgumentFrameIndex(Arg);
1324
1.01k
1325
1.01k
      if (FI == std::numeric_limits<int>::max())
1326
72
        continue;
1327
939
1328
939
      DIExpression *Expr = DI->getExpression();
1329
939
      if (Offset.getBoolValue())
1330
6
        Expr = DIExpression::prepend(Expr, DIExpression::ApplyOffset,
1331
6
                                     Offset.getZExtValue());
1332
939
      MF->setVariableDbgInfo(DI->getVariable(), Expr, FI, DI->getDebugLoc());
1333
939
    }
1334
1.20M
  }
1335
278k
}
1336
1337
278k
void SelectionDAGISel::SelectAllBasicBlocks(const Function &Fn) {
1338
278k
  FastISelFailed = false;
1339
278k
  // Initialize the Fast-ISel state, if needed.
1340
278k
  FastISel *FastIS = nullptr;
1341
278k
  if (TM.Options.EnableFastISel) {
1342
16.7k
    LLVM_DEBUG(dbgs() << "Enabling fast-isel\n");
1343
16.7k
    FastIS = TLI->createFastISel(*FuncInfo, LibInfo);
1344
16.7k
  }
1345
278k
1346
278k
  ReversePostOrderTraversal<const Function*> RPOT(&Fn);
1347
278k
1348
278k
  // Lower arguments up front. An RPO iteration always visits the entry block
1349
278k
  // first.
1350
278k
  assert(*RPOT.begin() == &Fn.getEntryBlock());
1351
278k
  ++NumEntryBlocks;
1352
278k
1353
278k
  // Set up FuncInfo for ISel. Entry blocks never have PHIs.
1354
278k
  FuncInfo->MBB = FuncInfo->MBBMap[&Fn.getEntryBlock()];
1355
278k
  FuncInfo->InsertPt = FuncInfo->MBB->begin();
1356
278k
1357
278k
  CurDAG->setFunctionLoweringInfo(FuncInfo);
1358
278k
1359
278k
  if (!FastIS) {
1360
264k
    LowerArguments(Fn);
1361
264k
  } else {
1362
13.4k
    // See if fast isel can lower the arguments.
1363
13.4k
    FastIS->startNewBlock();
1364
13.4k
    if (!FastIS->lowerArguments()) {
1365
8.24k
      FastISelFailed = true;
1366
8.24k
      // Fast isel failed to lower these arguments
1367
8.24k
      ++NumFastIselFailLowerArguments;
1368
8.24k
1369
8.24k
      OptimizationRemarkMissed R("sdagisel", "FastISelFailure",
1370
8.24k
                                 Fn.getSubprogram(),
1371
8.24k
                                 &Fn.getEntryBlock());
1372
8.24k
      R << "FastISel didn't lower all arguments: "
1373
8.24k
        << ore::NV("Prototype", Fn.getType());
1374
8.24k
      reportFastISelFailure(*MF, *ORE, R, EnableFastISelAbort > 1);
1375
8.24k
1376
8.24k
      // Use SelectionDAG argument lowering
1377
8.24k
      LowerArguments(Fn);
1378
8.24k
      CurDAG->setRoot(SDB->getControlRoot());
1379
8.24k
      SDB->clear();
1380
8.24k
      CodeGenAndEmitDAG();
1381
8.24k
    }
1382
13.4k
1383
13.4k
    // If we inserted any instructions at the beginning, make a note of
1384
13.4k
    // where they are, so we can be sure to emit subsequent instructions
1385
13.4k
    // after them.
1386
13.4k
    if (FuncInfo->InsertPt != FuncInfo->MBB->begin())
1387
7.03k
      FastIS->setLastLocalValue(&*std::prev(FuncInfo->InsertPt));
1388
6.39k
    else
1389
6.39k
      FastIS->setLastLocalValue(nullptr);
1390
13.4k
  }
1391
278k
1392
278k
  bool Inserted = SwiftError->createEntriesInEntryBlock(SDB->getCurDebugLoc());
1393
278k
1394
278k
  if (FastIS && 
Inserted13.4k
)
1395
23
    FastIS->setLastLocalValue(&*std::prev(FuncInfo->InsertPt));
1396
278k
1397
278k
  processDbgDeclares(FuncInfo);
1398
278k
1399
278k
  // Iterate over all basic blocks in the function.
1400
278k
  StackProtector &SP = getAnalysis<StackProtector>();
1401
1.20M
  for (const BasicBlock *LLVMBB : RPOT) {
1402
1.20M
    if (OptLevel != CodeGenOpt::None) {
1403
1.19M
      bool AllPredsVisited = true;
1404
1.19M
      for (const_pred_iterator PI = pred_begin(LLVMBB), PE = pred_end(LLVMBB);
1405
2.44M
           PI != PE; 
++PI1.25M
) {
1406
1.34M
        if (!FuncInfo->VisitedBBs.count(*PI)) {
1407
89.0k
          AllPredsVisited = false;
1408
89.0k
          break;
1409
89.0k
        }
1410
1.34M
      }
1411
1.19M
1412
1.19M
      if (AllPredsVisited) {
1413
1.10M
        for (const PHINode &PN : LLVMBB->phis())
1414
117k
          FuncInfo->ComputePHILiveOutRegInfo(&PN);
1415
1.10M
      } else {
1416
89.0k
        for (const PHINode &PN : LLVMBB->phis())
1417
122k
          FuncInfo->InvalidatePHILiveOutRegInfo(&PN);
1418
89.0k
      }
1419
1.19M
1420
1.19M
      FuncInfo->VisitedBBs.insert(LLVMBB);
1421
1.19M
    }
1422
1.20M
1423
1.20M
    BasicBlock::const_iterator const Begin =
1424
1.20M
        LLVMBB->getFirstNonPHI()->getIterator();
1425
1.20M
    BasicBlock::const_iterator const End = LLVMBB->end();
1426
1.20M
    BasicBlock::const_iterator BI = End;
1427
1.20M
1428
1.20M
    FuncInfo->MBB = FuncInfo->MBBMap[LLVMBB];
1429
1.20M
    if (!FuncInfo->MBB)
1430
160
      continue; // Some blocks like catchpads have no code or MBB.
1431
1.20M
1432
1.20M
    // Insert new instructions after any phi or argument setup code.
1433
1.20M
    FuncInfo->InsertPt = FuncInfo->MBB->end();
1434
1.20M
1435
1.20M
    // Setup an EH landing-pad block.
1436
1.20M
    FuncInfo->ExceptionPointerVirtReg = 0;
1437
1.20M
    FuncInfo->ExceptionSelectorVirtReg = 0;
1438
1.20M
    if (LLVMBB->isEHPad())
1439
3.78k
      if (!PrepareEHLandingPad())
1440
0
        continue;
1441
1.20M
1442
1.20M
    // Before doing SelectionDAG ISel, see if FastISel has been requested.
1443
1.20M
    if (FastIS) {
1444
15.8k
      if (LLVMBB != &Fn.getEntryBlock())
1445
2.44k
        FastIS->startNewBlock();
1446
15.8k
1447
15.8k
      unsigned NumFastIselRemaining = std::distance(Begin, End);
1448
15.8k
1449
15.8k
      // Pre-assign swifterror vregs.
1450
15.8k
      SwiftError->preassignVRegs(FuncInfo->MBB, Begin, End);
1451
15.8k
1452
15.8k
      // Do FastISel on as many instructions as possible.
1453
55.8k
      for (; BI != Begin; 
--BI39.9k
) {
1454
46.2k
        const Instruction *Inst = &*std::prev(BI);
1455
46.2k
1456
46.2k
        // If we no longer require this instruction, skip it.
1457
46.2k
        if (isFoldedOrDeadInstruction(Inst, FuncInfo) ||
1458
46.2k
            
ElidedArgCopyInstrs.count(Inst)41.4k
) {
1459
4.99k
          --NumFastIselRemaining;
1460
4.99k
          continue;
1461
4.99k
        }
1462
41.2k
1463
41.2k
        // Bottom-up: reset the insert pos at the top, after any local-value
1464
41.2k
        // instructions.
1465
41.2k
        FastIS->recomputeInsertPt();
1466
41.2k
1467
41.2k
        // Try to select the instruction with FastISel.
1468
41.2k
        if (FastIS->selectInstruction(Inst)) {
1469
32.0k
          --NumFastIselRemaining;
1470
32.0k
          ++NumFastIselSuccess;
1471
32.0k
          // If fast isel succeeded, skip over all the folded instructions, and
1472
32.0k
          // then see if there is a load right before the selected instructions.
1473
32.0k
          // Try to fold the load if so.
1474
32.0k
          const Instruction *BeforeInst = Inst;
1475
36.5k
          while (BeforeInst != &*Begin) {
1476
28.5k
            BeforeInst = &*std::prev(BasicBlock::const_iterator(BeforeInst));
1477
28.5k
            if (!isFoldedOrDeadInstruction(BeforeInst, FuncInfo))
1478
24.0k
              break;
1479
28.5k
          }
1480
32.0k
          if (BeforeInst != Inst && 
isa<LoadInst>(BeforeInst)25.8k
&&
1481
32.0k
              
BeforeInst->hasOneUse()2.81k
&&
1482
32.0k
              
FastIS->tryToFoldLoad(cast<LoadInst>(BeforeInst), Inst)2.61k
) {
1483
402
            // If we succeeded, don't re-select the load.
1484
402
            BI = std::next(BasicBlock::const_iterator(BeforeInst));
1485
402
            --NumFastIselRemaining;
1486
402
            ++NumFastIselSuccess;
1487
402
          }
1488
32.0k
          continue;
1489
32.0k
        }
1490
9.23k
1491
9.23k
        FastISelFailed = true;
1492
9.23k
1493
9.23k
        // Then handle certain instructions as single-LLVM-Instruction blocks.
1494
9.23k
        // We cannot separate out GCrelocates to their own blocks since we need
1495
9.23k
        // to keep track of gc-relocates for a particular gc-statepoint. This is
1496
9.23k
        // done by SelectionDAGBuilder::LowerAsSTATEPOINT, called before
1497
9.23k
        // visitGCRelocate.
1498
9.23k
        if (isa<CallInst>(Inst) && 
!isStatepoint(Inst)3.04k
&&
!isGCRelocate(Inst)3.04k
&&
1499
9.23k
            
!isGCResult(Inst)3.03k
) {
1500
3.03k
          OptimizationRemarkMissed R("sdagisel", "FastISelFailure",
1501
3.03k
                                     Inst->getDebugLoc(), LLVMBB);
1502
3.03k
1503
3.03k
          R << "FastISel missed call";
1504
3.03k
1505
3.03k
          if (R.isEnabled() || 
EnableFastISelAbort3.03k
) {
1506
68
            std::string InstStrStorage;
1507
68
            raw_string_ostream InstStr(InstStrStorage);
1508
68
            InstStr << *Inst;
1509
68
1510
68
            R << ": " << InstStr.str();
1511
68
          }
1512
3.03k
1513
3.03k
          reportFastISelFailure(*MF, *ORE, R, EnableFastISelAbort > 2);
1514
3.03k
1515
3.03k
          if (!Inst->getType()->isVoidTy() && 
!Inst->getType()->isTokenTy()2.48k
&&
1516
3.03k
              
!Inst->use_empty()2.48k
) {
1517
2.42k
            unsigned &R = FuncInfo->ValueMap[Inst];
1518
2.42k
            if (!R)
1519
3
              R = FuncInfo->CreateRegs(Inst);
1520
2.42k
          }
1521
3.03k
1522
3.03k
          bool HadTailCall = false;
1523
3.03k
          MachineBasicBlock::iterator SavedInsertPt = FuncInfo->InsertPt;
1524
3.03k
          SelectBasicBlock(Inst->getIterator(), BI, HadTailCall);
1525
3.03k
1526
3.03k
          // If the call was emitted as a tail call, we're done with the block.
1527
3.03k
          // We also need to delete any previously emitted instructions.
1528
3.03k
          if (HadTailCall) {
1529
97
            FastIS->removeDeadCode(SavedInsertPt, FuncInfo->MBB->end());
1530
97
            --BI;
1531
97
            break;
1532
97
          }
1533
2.94k
1534
2.94k
          // Recompute NumFastIselRemaining as Selection DAG instruction
1535
2.94k
          // selection may have handled the call, input args, etc.
1536
2.94k
          unsigned RemainingNow = std::distance(Begin, BI);
1537
2.94k
          NumFastIselFailures += NumFastIselRemaining - RemainingNow;
1538
2.94k
          NumFastIselRemaining = RemainingNow;
1539
2.94k
          continue;
1540
2.94k
        }
1541
6.19k
1542
6.19k
        OptimizationRemarkMissed R("sdagisel", "FastISelFailure",
1543
6.19k
                                   Inst->getDebugLoc(), LLVMBB);
1544
6.19k
1545
6.19k
        bool ShouldAbort = EnableFastISelAbort;
1546
6.19k
        if (Inst->isTerminator()) {
1547
1.14k
          // Use a different message for terminator misses.
1548
1.14k
          R << "FastISel missed terminator";
1549
1.14k
          // Don't abort for terminator unless the level is really high
1550
1.14k
          ShouldAbort = (EnableFastISelAbort > 2);
1551
5.05k
        } else {
1552
5.05k
          R << "FastISel missed";
1553
5.05k
        }
1554
6.19k
1555
6.19k
        if (R.isEnabled() || 
EnableFastISelAbort6.19k
) {
1556
138
          std::string InstStrStorage;
1557
138
          raw_string_ostream InstStr(InstStrStorage);
1558
138
          InstStr << *Inst;
1559
138
          R << ": " << InstStr.str();
1560
138
        }
1561
6.19k
1562
6.19k
        reportFastISelFailure(*MF, *ORE, R, ShouldAbort);
1563
6.19k
1564
6.19k
        NumFastIselFailures += NumFastIselRemaining;
1565
6.19k
        break;
1566
6.19k
      }
1567
15.8k
1568
15.8k
      FastIS->recomputeInsertPt();
1569
15.8k
    }
1570
1.20M
1571
1.20M
    if (SP.shouldEmitSDCheck(*LLVMBB)) {
1572
486
      bool FunctionBasedInstrumentation =
1573
486
          TLI->getSSPStackGuardCheck(*Fn.getParent());
1574
486
      SDB->SPDescriptor.initialize(LLVMBB, FuncInfo->MBBMap[LLVMBB],
1575
486
                                   FunctionBasedInstrumentation);
1576
486
    }
1577
1.20M
1578
1.20M
    if (Begin != BI)
1579
1.19M
      ++NumDAGBlocks;
1580
9.63k
    else
1581
9.63k
      ++NumFastIselBlocks;
1582
1.20M
1583
1.20M
    if (Begin != BI) {
1584
1.19M
      // Run SelectionDAG instruction selection on the remainder of the block
1585
1.19M
      // not handled by FastISel. If FastISel is not run, this is the entire
1586
1.19M
      // block.
1587
1.19M
      bool HadTailCall;
1588
1.19M
      SelectBasicBlock(Begin, BI, HadTailCall);
1589
1.19M
1590
1.19M
      // But if FastISel was run, we already selected some of the block.
1591
1.19M
      // If we emitted a tail-call, we need to delete any previously emitted
1592
1.19M
      // instruction that follows it.
1593
1.19M
      if (HadTailCall && 
FuncInfo->InsertPt != FuncInfo->MBB->end()63.8k
)
1594
1
        FastIS->removeDeadCode(FuncInfo->InsertPt, FuncInfo->MBB->end());
1595
1.19M
    }
1596
1.20M
1597
1.20M
    if (FastIS)
1598
15.8k
      FastIS->finishBasicBlock();
1599
1.20M
    FinishBasicBlock();
1600
1.20M
    FuncInfo->PHINodesToUpdate.clear();
1601
1.20M
    ElidedArgCopyInstrs.clear();
1602
1.20M
  }
1603
278k
1604
278k
  SP.copyToMachineFrameInfo(MF->getFrameInfo());
1605
278k
1606
278k
  SwiftError->propagateVRegs();
1607
278k
1608
278k
  delete FastIS;
1609
278k
  SDB->clearDanglingDebugInfo();
1610
278k
  SDB->SPDescriptor.resetPerFunctionState();
1611
278k
}
1612
1613
/// Given that the input MI is before a partial terminator sequence TSeq, return
1614
/// true if M + TSeq also a partial terminator sequence.
1615
///
1616
/// A Terminator sequence is a sequence of MachineInstrs which at this point in
1617
/// lowering copy vregs into physical registers, which are then passed into
1618
/// terminator instructors so we can satisfy ABI constraints. A partial
1619
/// terminator sequence is an improper subset of a terminator sequence (i.e. it
1620
/// may be the whole terminator sequence).
1621
683
static bool MIIsInTerminatorSequence(const MachineInstr &MI) {
1622
683
  // If we do not have a copy or an implicit def, we return true if and only if
1623
683
  // MI is a debug value.
1624
683
  if (!MI.isCopy() && 
!MI.isImplicitDef()334
)
1625
331
    // Sometimes DBG_VALUE MI sneak in between the copies from the vregs to the
1626
331
    // physical registers if there is debug info associated with the terminator
1627
331
    // of our mbb. We want to include said debug info in our terminator
1628
331
    // sequence, so we return true in that case.
1629
331
    return MI.isDebugValue();
1630
352
1631
352
  // We have left the terminator sequence if we are not doing one of the
1632
352
  // following:
1633
352
  //
1634
352
  // 1. Copying a vreg into a physical register.
1635
352
  // 2. Copying a vreg into a vreg.
1636
352
  // 3. Defining a register via an implicit def.
1637
352
1638
352
  // OPI should always be a register definition...
1639
352
  MachineInstr::const_mop_iterator OPI = MI.operands_begin();
1640
352
  if (!OPI->isReg() || !OPI->isDef())
1641
0
    return false;
1642
352
1643
352
  // Defining any register via an implicit def is always ok.
1644
352
  if (MI.isImplicitDef())
1645
3
    return true;
1646
349
1647
349
  // Grab the copy source...
1648
349
  MachineInstr::const_mop_iterator OPI2 = OPI;
1649
349
  ++OPI2;
1650
349
  assert(OPI2 != MI.operands_end()
1651
349
         && "Should have a copy implying we should have 2 arguments.");
1652
349
1653
349
  // Make sure that the copy dest is not a vreg when the copy source is a
1654
349
  // physical register.
1655
349
  if (!OPI2->isReg() ||
1656
349
      (!TargetRegisterInfo::isPhysicalRegister(OPI->getReg()) &&
1657
349
       
TargetRegisterInfo::isPhysicalRegister(OPI2->getReg())111
))
1658
111
    return false;
1659
238
1660
238
  return true;
1661
238
}
1662
1663
/// Find the split point at which to splice the end of BB into its success stack
1664
/// protector check machine basic block.
1665
///
1666
/// On many platforms, due to ABI constraints, terminators, even before register
1667
/// allocation, use physical registers. This creates an issue for us since
1668
/// physical registers at this point can not travel across basic
1669
/// blocks. Luckily, selectiondag always moves physical registers into vregs
1670
/// when they enter functions and moves them through a sequence of copies back
1671
/// into the physical registers right before the terminator creating a
1672
/// ``Terminator Sequence''. This function is searching for the beginning of the
1673
/// terminator sequence so that we can ensure that we splice off not just the
1674
/// terminator, but additionally the copies that move the vregs into the
1675
/// physical registers.
1676
static MachineBasicBlock::iterator
1677
486
FindSplitPointForStackProtector(MachineBasicBlock *BB) {
1678
486
  MachineBasicBlock::iterator SplitPoint = BB->getFirstTerminator();
1679
486
  //
1680
486
  if (SplitPoint == BB->begin())
1681
44
    return SplitPoint;
1682
442
1683
442
  MachineBasicBlock::iterator Start = BB->begin();
1684
442
  MachineBasicBlock::iterator Previous = SplitPoint;
1685
442
  --Previous;
1686
442
1687
683
  while (MIIsInTerminatorSequence(*Previous)) {
1688
241
    SplitPoint = Previous;
1689
241
    if (Previous == Start)
1690
0
      break;
1691
241
    --Previous;
1692
241
  }
1693
442
1694
442
  return SplitPoint;
1695
442
}
1696
1697
void
1698
1.20M
SelectionDAGISel::FinishBasicBlock() {
1699
1.20M
  LLVM_DEBUG(dbgs() << "Total amount of phi nodes to update: "
1700
1.20M
                    << FuncInfo->PHINodesToUpdate.size() << "\n";
1701
1.20M
             for (unsigned i = 0, e = FuncInfo->PHINodesToUpdate.size(); i != e;
1702
1.20M
                  ++i) dbgs()
1703
1.20M
             << "Node " << i << " : (" << FuncInfo->PHINodesToUpdate[i].first
1704
1.20M
             << ", " << FuncInfo->PHINodesToUpdate[i].second << ")\n");
1705
1.20M
1706
1.20M
  // Next, now that we know what the last MBB the LLVM BB expanded is, update
1707
1.20M
  // PHI nodes in successors.
1708
1.82M
  for (unsigned i = 0, e = FuncInfo->PHINodesToUpdate.size(); i != e; 
++i616k
) {
1709
616k
    MachineInstrBuilder PHI(*MF, FuncInfo->PHINodesToUpdate[i].first);
1710
616k
    assert(PHI->isPHI() &&
1711
616k
           "This is not a machine PHI node that we are updating!");
1712
616k
    if (!FuncInfo->MBB->isSuccessor(PHI->getParent()))
1713
8.30k
      continue;
1714
608k
    PHI.addReg(FuncInfo->PHINodesToUpdate[i].second).addMBB(FuncInfo->MBB);
1715
608k
  }
1716
1.20M
1717
1.20M
  // Handle stack protector.
1718
1.20M
  if (SDB->SPDescriptor.shouldEmitFunctionBasedCheckStackProtector()) {
1719
84
    // The target provides a guard check function. There is no need to
1720
84
    // generate error handling code or to split current basic block.
1721
84
    MachineBasicBlock *ParentMBB = SDB->SPDescriptor.getParentMBB();
1722
84
1723
84
    // Add load and check to the basicblock.
1724
84
    FuncInfo->MBB = ParentMBB;
1725
84
    FuncInfo->InsertPt =
1726
84
        FindSplitPointForStackProtector(ParentMBB);
1727
84
    SDB->visitSPDescriptorParent(SDB->SPDescriptor, ParentMBB);
1728
84
    CurDAG->setRoot(SDB->getRoot());
1729
84
    SDB->clear();
1730
84
    CodeGenAndEmitDAG();
1731
84
1732
84
    // Clear the Per-BB State.
1733
84
    SDB->SPDescriptor.resetPerBBState();
1734
1.20M
  } else if (SDB->SPDescriptor.shouldEmitStackProtector()) {
1735
402
    MachineBasicBlock *ParentMBB = SDB->SPDescriptor.getParentMBB();
1736
402
    MachineBasicBlock *SuccessMBB = SDB->SPDescriptor.getSuccessMBB();
1737
402
1738
402
    // Find the split point to split the parent mbb. At the same time copy all
1739
402
    // physical registers used in the tail of parent mbb into virtual registers
1740
402
    // before the split point and back into physical registers after the split
1741
402
    // point. This prevents us needing to deal with Live-ins and many other
1742
402
    // register allocation issues caused by us splitting the parent mbb. The
1743
402
    // register allocator will clean up said virtual copies later on.
1744
402
    MachineBasicBlock::iterator SplitPoint =
1745
402
        FindSplitPointForStackProtector(ParentMBB);
1746
402
1747
402
    // Splice the terminator of ParentMBB into SuccessMBB.
1748
402
    SuccessMBB->splice(SuccessMBB->end(), ParentMBB,
1749
402
                       SplitPoint,
1750
402
                       ParentMBB->end());
1751
402
1752
402
    // Add compare/jump on neq/jump to the parent BB.
1753
402
    FuncInfo->MBB = ParentMBB;
1754
402
    FuncInfo->InsertPt = ParentMBB->end();
1755
402
    SDB->visitSPDescriptorParent(SDB->SPDescriptor, ParentMBB);
1756
402
    CurDAG->setRoot(SDB->getRoot());
1757
402
    SDB->clear();
1758
402
    CodeGenAndEmitDAG();
1759
402
1760
402
    // CodeGen Failure MBB if we have not codegened it yet.
1761
402
    MachineBasicBlock *FailureMBB = SDB->SPDescriptor.getFailureMBB();
1762
402
    if (FailureMBB->empty()) {
1763
392
      FuncInfo->MBB = FailureMBB;
1764
392
      FuncInfo->InsertPt = FailureMBB->end();
1765
392
      SDB->visitSPDescriptorFailure(SDB->SPDescriptor);
1766
392
      CurDAG->setRoot(SDB->getRoot());
1767
392
      SDB->clear();
1768
392
      CodeGenAndEmitDAG();
1769
392
    }
1770
402
1771
402
    // Clear the Per-BB State.
1772
402
    SDB->SPDescriptor.resetPerBBState();
1773
402
  }
1774
1.20M
1775
1.20M
  // Lower each BitTestBlock.
1776
1.20M
  for (auto &BTB : SDB->SL->BitTestCases) {
1777
286
    // Lower header first, if it wasn't already lowered
1778
286
    if (!BTB.Emitted) {
1779
2
      // Set the current basic block to the mbb we wish to insert the code into
1780
2
      FuncInfo->MBB = BTB.Parent;
1781
2
      FuncInfo->InsertPt = FuncInfo->MBB->end();
1782
2
      // Emit the code
1783
2
      SDB->visitBitTestHeader(BTB, FuncInfo->MBB);
1784
2
      CurDAG->setRoot(SDB->getRoot());
1785
2
      SDB->clear();
1786
2
      CodeGenAndEmitDAG();
1787
2
    }
1788
286
1789
286
    BranchProbability UnhandledProb = BTB.Prob;
1790
659
    for (unsigned j = 0, ej = BTB.Cases.size(); j != ej; 
++j373
) {
1791
410
      UnhandledProb -= BTB.Cases[j].ExtraProb;
1792
410
      // Set the current basic block to the mbb we wish to insert the code into
1793
410
      FuncInfo->MBB = BTB.Cases[j].ThisBB;
1794
410
      FuncInfo->InsertPt = FuncInfo->MBB->end();
1795
410
      // Emit the code
1796
410
1797
410
      // If all cases cover a contiguous range, it is not necessary to jump to
1798
410
      // the default block after the last bit test fails. This is because the
1799
410
      // range check during bit test header creation has guaranteed that every
1800
410
      // case here doesn't go outside the range. In this case, there is no need
1801
410
      // to perform the last bit test, as it will always be true. Instead, make
1802
410
      // the second-to-last bit-test fall through to the target of the last bit
1803
410
      // test, and delete the last bit test.
1804
410
1805
410
      MachineBasicBlock *NextMBB;
1806
410
      if (BTB.ContiguousRange && 
j + 2 == ej71
) {
1807
37
        // Second-to-last bit-test with contiguous range: fall through to the
1808
37
        // target of the final bit test.
1809
37
        NextMBB = BTB.Cases[j + 1].TargetBB;
1810
373
      } else if (j + 1 == ej) {
1811
249
        // For the last bit test, fall through to Default.
1812
249
        NextMBB = BTB.Default;
1813
249
      } else {
1814
124
        // Otherwise, fall through to the next bit test.
1815
124
        NextMBB = BTB.Cases[j + 1].ThisBB;
1816
124
      }
1817
410
1818
410
      SDB->visitBitTestCase(BTB, NextMBB, UnhandledProb, BTB.Reg, BTB.Cases[j],
1819
410
                            FuncInfo->MBB);
1820
410
1821
410
      CurDAG->setRoot(SDB->getRoot());
1822
410
      SDB->clear();
1823
410
      CodeGenAndEmitDAG();
1824
410
1825
410
      if (BTB.ContiguousRange && 
j + 2 == ej71
) {
1826
37
        // Since we're not going to use the final bit test, remove it.
1827
37
        BTB.Cases.pop_back();
1828
37
        break;
1829
37
      }
1830
410
    }
1831
286
1832
286
    // Update PHI Nodes
1833
286
    for (unsigned pi = 0, pe = FuncInfo->PHINodesToUpdate.size();
1834
401
         pi != pe; 
++pi115
) {
1835
115
      MachineInstrBuilder PHI(*MF, FuncInfo->PHINodesToUpdate[pi].first);
1836
115
      MachineBasicBlock *PHIBB = PHI->getParent();
1837
115
      assert(PHI->isPHI() &&
1838
115
             "This is not a machine PHI node that we are updating!");
1839
115
      // This is "default" BB. We have two jumps to it. From "header" BB and
1840
115
      // from last "case" BB, unless the latter was skipped.
1841
115
      if (PHIBB == BTB.Default) {
1842
33
        PHI.addReg(FuncInfo->PHINodesToUpdate[pi].second).addMBB(BTB.Parent);
1843
33
        if (!BTB.ContiguousRange) {
1844
31
          PHI.addReg(FuncInfo->PHINodesToUpdate[pi].second)
1845
31
              .addMBB(BTB.Cases.back().ThisBB);
1846
31
         }
1847
33
      }
1848
115
      // One of "cases" BB.
1849
115
      for (unsigned j = 0, ej = BTB.Cases.size();
1850
250
           j != ej; 
++j135
) {
1851
135
        MachineBasicBlock* cBB = BTB.Cases[j].ThisBB;
1852
135
        if (cBB->isSuccessor(PHIBB))
1853
98
          PHI.addReg(FuncInfo->PHINodesToUpdate[pi].second).addMBB(cBB);
1854
135
      }
1855
115
    }
1856
286
  }
1857
1.20M
  SDB->SL->BitTestCases.clear();
1858
1.20M
1859
1.20M
  // If the JumpTable record is filled in, then we need to emit a jump table.
1860
1.20M
  // Updating the PHI nodes is tricky in this case, since we need to determine
1861
1.20M
  // whether the PHI is a successor of the range check MBB or the jump table MBB
1862
1.20M
  for (unsigned i = 0, e = SDB->SL->JTCases.size(); i != e; 
++i2.26k
) {
1863
2.26k
    // Lower header first, if it wasn't already lowered
1864
2.26k
    if (!SDB->SL->JTCases[i].first.Emitted) {
1865
35
      // Set the current basic block to the mbb we wish to insert the code into
1866
35
      FuncInfo->MBB = SDB->SL->JTCases[i].first.HeaderBB;
1867
35
      FuncInfo->InsertPt = FuncInfo->MBB->end();
1868
35
      // Emit the code
1869
35
      SDB->visitJumpTableHeader(SDB->SL->JTCases[i].second,
1870
35
                                SDB->SL->JTCases[i].first, FuncInfo->MBB);
1871
35
      CurDAG->setRoot(SDB->getRoot());
1872
35
      SDB->clear();
1873
35
      CodeGenAndEmitDAG();
1874
35
    }
1875
2.26k
1876
2.26k
    // Set the current basic block to the mbb we wish to insert the code into
1877
2.26k
    FuncInfo->MBB = SDB->SL->JTCases[i].second.MBB;
1878
2.26k
    FuncInfo->InsertPt = FuncInfo->MBB->end();
1879
2.26k
    // Emit the code
1880
2.26k
    SDB->visitJumpTable(SDB->SL->JTCases[i].second);
1881
2.26k
    CurDAG->setRoot(SDB->getRoot());
1882
2.26k
    SDB->clear();
1883
2.26k
    CodeGenAndEmitDAG();
1884
2.26k
1885
2.26k
    // Update PHI Nodes
1886
2.26k
    for (unsigned pi = 0, pe = FuncInfo->PHINodesToUpdate.size();
1887
4.88k
         pi != pe; 
++pi2.61k
) {
1888
2.61k
      MachineInstrBuilder PHI(*MF, FuncInfo->PHINodesToUpdate[pi].first);
1889
2.61k
      MachineBasicBlock *PHIBB = PHI->getParent();
1890
2.61k
      assert(PHI->isPHI() &&
1891
2.61k
             "This is not a machine PHI node that we are updating!");
1892
2.61k
      // "default" BB. We can go there only from header BB.
1893
2.61k
      if (PHIBB == SDB->SL->JTCases[i].second.Default)
1894
1.61k
        PHI.addReg(FuncInfo->PHINodesToUpdate[pi].second)
1895
1.61k
           .addMBB(SDB->SL->JTCases[i].first.HeaderBB);
1896
2.61k
      // JT BB. Just iterate over successors here
1897
2.61k
      if (FuncInfo->MBB->isSuccessor(PHIBB))
1898
1.08k
        PHI.addReg(FuncInfo->PHINodesToUpdate[pi].second).addMBB(FuncInfo->MBB);
1899
2.61k
    }
1900
2.26k
  }
1901
1.20M
  SDB->SL->JTCases.clear();
1902
1.20M
1903
1.20M
  // If we generated any switch lowering information, build and codegen any
1904
1.20M
  // additional DAGs necessary.
1905
1.23M
  for (unsigned i = 0, e = SDB->SL->SwitchCases.size(); i != e; 
++i35.4k
) {
1906
35.4k
    // Set the current basic block to the mbb we wish to insert the code into
1907
35.4k
    FuncInfo->MBB = SDB->SL->SwitchCases[i].ThisBB;
1908
35.4k
    FuncInfo->InsertPt = FuncInfo->MBB->end();
1909
35.4k
1910
35.4k
    // Determine the unique successors.
1911
35.4k
    SmallVector<MachineBasicBlock *, 2> Succs;
1912
35.4k
    Succs.push_back(SDB->SL->SwitchCases[i].TrueBB);
1913
35.4k
    if (SDB->SL->SwitchCases[i].TrueBB != SDB->SL->SwitchCases[i].FalseBB)
1914
35.4k
      Succs.push_back(SDB->SL->SwitchCases[i].FalseBB);
1915
35.4k
1916
35.4k
    // Emit the code. Note that this could result in FuncInfo->MBB being split.
1917
35.4k
    SDB->visitSwitchCase(SDB->SL->SwitchCases[i], FuncInfo->MBB);
1918
35.4k
    CurDAG->setRoot(SDB->getRoot());
1919
35.4k
    SDB->clear();
1920
35.4k
    CodeGenAndEmitDAG();
1921
35.4k
1922
35.4k
    // Remember the last block, now that any splitting is done, for use in
1923
35.4k
    // populating PHI nodes in successors.
1924
35.4k
    MachineBasicBlock *ThisBB = FuncInfo->MBB;
1925
35.4k
1926
35.4k
    // Handle any PHI nodes in successors of this chunk, as if we were coming
1927
35.4k
    // from the original BB before switch expansion.  Note that PHI nodes can
1928
35.4k
    // occur multiple times in PHINodesToUpdate.  We have to be very careful to
1929
35.4k
    // handle them the right number of times.
1930
106k
    for (unsigned i = 0, e = Succs.size(); i != e; 
++i70.9k
) {
1931
70.9k
      FuncInfo->MBB = Succs[i];
1932
70.9k
      FuncInfo->InsertPt = FuncInfo->MBB->end();
1933
70.9k
      // FuncInfo->MBB may have been removed from the CFG if a branch was
1934
70.9k
      // constant folded.
1935
70.9k
      if (ThisBB->isSuccessor(FuncInfo->MBB)) {
1936
70.9k
        for (MachineBasicBlock::iterator
1937
70.9k
             MBBI = FuncInfo->MBB->begin(), MBBE = FuncInfo->MBB->end();
1938
83.6k
             MBBI != MBBE && 
MBBI->isPHI()13.3k
;
++MBBI12.7k
) {
1939
12.7k
          MachineInstrBuilder PHI(*MF, MBBI);
1940
12.7k
          // This value for this PHI node is recorded in PHINodesToUpdate.
1941
25.9k
          for (unsigned pn = 0; ; 
++pn13.2k
) {
1942
25.9k
            assert(pn != FuncInfo->PHINodesToUpdate.size() &&
1943
25.9k
                   "Didn't find PHI entry!");
1944
25.9k
            if (FuncInfo->PHINodesToUpdate[pn].first == PHI) {
1945
12.7k
              PHI.addReg(FuncInfo->PHINodesToUpdate[pn].second).addMBB(ThisBB);
1946
12.7k
              break;
1947
12.7k
            }
1948
25.9k
          }
1949
12.7k
        }
1950
70.9k
      }
1951
70.9k
    }
1952
35.4k
  }
1953
1.20M
  SDB->SL->SwitchCases.clear();
1954
1.20M
}
1955
1956
/// Create the scheduler. If a specific scheduler was specified
1957
/// via the SchedulerRegistry, use it, otherwise select the
1958
/// one preferred by the target.
1959
///
1960
1.24M
ScheduleDAGSDNodes *SelectionDAGISel::CreateScheduler() {
1961
1.24M
  return ISHeuristic(this, OptLevel);
1962
1.24M
}
1963
1964
//===----------------------------------------------------------------------===//
1965
// Helper functions used by the generated instruction selector.
1966
//===----------------------------------------------------------------------===//
1967
// Calls to these methods are generated by tblgen.
1968
1969
/// CheckAndMask - The isel is trying to match something like (and X, 255).  If
1970
/// the dag combiner simplified the 255, we still want to match.  RHS is the
1971
/// actual value in the DAG on the RHS of an AND, and DesiredMaskS is the value
1972
/// specified in the .td file (e.g. 255).
1973
bool SelectionDAGISel::CheckAndMask(SDValue LHS, ConstantSDNode *RHS,
1974
931k
                                    int64_t DesiredMaskS) const {
1975
931k
  const APInt &ActualMask = RHS->getAPIntValue();
1976
931k
  const APInt &DesiredMask = APInt(LHS.getValueSizeInBits(), DesiredMaskS);
1977
931k
1978
931k
  // If the actual mask exactly matches, success!
1979
931k
  if (ActualMask == DesiredMask)
1980
167k
    return true;
1981
764k
1982
764k
  // If the actual AND mask is allowing unallowed bits, this doesn't match.
1983
764k
  if (!ActualMask.isSubsetOf(DesiredMask))
1984
283k
    return false;
1985
480k
1986
480k
  // Otherwise, the DAG Combiner may have proven that the value coming in is
1987
480k
  // either already zero or is not demanded.  Check for known zero input bits.
1988
480k
  APInt NeededMask = DesiredMask & ~ActualMask;
1989
480k
  if (CurDAG->MaskedValueIsZero(LHS, NeededMask))
1990
87.7k
    return true;
1991
392k
1992
392k
  // TODO: check to see if missing bits are just not demanded.
1993
392k
1994
392k
  // Otherwise, this pattern doesn't match.
1995
392k
  return false;
1996
392k
}
1997
1998
/// CheckOrMask - The isel is trying to match something like (or X, 255).  If
1999
/// the dag combiner simplified the 255, we still want to match.  RHS is the
2000
/// actual value in the DAG on the RHS of an OR, and DesiredMaskS is the value
2001
/// specified in the .td file (e.g. 255).
2002
bool SelectionDAGISel::CheckOrMask(SDValue LHS, ConstantSDNode *RHS,
2003
776
                                   int64_t DesiredMaskS) const {
2004
776
  const APInt &ActualMask = RHS->getAPIntValue();
2005
776
  const APInt &DesiredMask = APInt(LHS.getValueSizeInBits(), DesiredMaskS);
2006
776
2007
776
  // If the actual mask exactly matches, success!
2008
776
  if (ActualMask == DesiredMask)
2009
5
    return true;
2010
771
2011
771
  // If the actual AND mask is allowing unallowed bits, this doesn't match.
2012
771
  if (!ActualMask.isSubsetOf(DesiredMask))
2013
226
    return false;
2014
545
2015
545
  // Otherwise, the DAG Combiner may have proven that the value coming in is
2016
545
  // either already zero or is not demanded.  Check for known zero input bits.
2017
545
  APInt NeededMask = DesiredMask & ~ActualMask;
2018
545
  KnownBits Known = CurDAG->computeKnownBits(LHS);
2019
545
2020
545
  // If all the missing bits in the or are already known to be set, match!
2021
545
  if (NeededMask.isSubsetOf(Known.One))
2022
0
    return true;
2023
545
2024
545
  // TODO: check to see if missing bits are just not demanded.
2025
545
2026
545
  // Otherwise, this pattern doesn't match.
2027
545
  return false;
2028
545
}
2029
2030
/// SelectInlineAsmMemoryOperands - Calls to this are automatically generated
2031
/// by tblgen.  Others should not call it.
2032
void SelectionDAGISel::SelectInlineAsmMemoryOperands(std::vector<SDValue> &Ops,
2033
20.3k
                                                     const SDLoc &DL) {
2034
20.3k
  std::vector<SDValue> InOps;
2035
20.3k
  std::swap(InOps, Ops);
2036
20.3k
2037
20.3k
  Ops.push_back(InOps[InlineAsm::Op_InputChain]); // 0
2038
20.3k
  Ops.push_back(InOps[InlineAsm::Op_AsmString]);  // 1
2039
20.3k
  Ops.push_back(InOps[InlineAsm::Op_MDNode]);     // 2, !srcloc
2040
20.3k
  Ops.push_back(InOps[InlineAsm::Op_ExtraInfo]);  // 3 (SideEffect, AlignStack)
2041
20.3k
2042
20.3k
  unsigned i = InlineAsm::Op_FirstOperand, e = InOps.size();
2043
20.3k
  if (InOps[e-1].getValueType() == MVT::Glue)
2044
3.30k
    --e;  // Don't process a glue operand if it is here.
2045
20.3k
2046
113k
  while (i != e) {
2047
93.4k
    unsigned Flags = cast<ConstantSDNode>(InOps[i])->getZExtValue();
2048
93.4k
    if (!InlineAsm::isMemKind(Flags)) {
2049
92.9k
      // Just skip over this operand, copying the operands verbatim.
2050
92.9k
      Ops.insert(Ops.end(), InOps.begin()+i,
2051
92.9k
                 InOps.begin()+i+InlineAsm::getNumOperandRegisters(Flags) + 1);
2052
92.9k
      i += InlineAsm::getNumOperandRegisters(Flags) + 1;
2053
92.9k
    } else {
2054
517
      assert(InlineAsm::getNumOperandRegisters(Flags) == 1 &&
2055
517
             "Memory operand with multiple values?");
2056
517
2057
517
      unsigned TiedToOperand;
2058
517
      if (InlineAsm::isUseOperandTiedToDef(Flags, TiedToOperand)) {
2059
0
        // We need the constraint ID from the operand this is tied to.
2060
0
        unsigned CurOp = InlineAsm::Op_FirstOperand;
2061
0
        Flags = cast<ConstantSDNode>(InOps[CurOp])->getZExtValue();
2062
0
        for (; TiedToOperand; --TiedToOperand) {
2063
0
          CurOp += InlineAsm::getNumOperandRegisters(Flags)+1;
2064
0
          Flags = cast<ConstantSDNode>(InOps[CurOp])->getZExtValue();
2065
0
        }
2066
0
      }
2067
517
2068
517
      // Otherwise, this is a memory operand.  Ask the target to select it.
2069
517
      std::vector<SDValue> SelOps;
2070
517
      unsigned ConstraintID = InlineAsm::getMemoryConstraintID(Flags);
2071
517
      if (SelectInlineAsmMemoryOperand(InOps[i+1], ConstraintID, SelOps))
2072
0
        report_fatal_error("Could not match memory address.  Inline asm"
2073
0
                           " failure!");
2074
517
2075
517
      // Add this to the output node.
2076
517
      unsigned NewFlags =
2077
517
        InlineAsm::getFlagWord(InlineAsm::Kind_Mem, SelOps.size());
2078
517
      NewFlags = InlineAsm::getFlagWordForMem(NewFlags, ConstraintID);
2079
517
      Ops.push_back(CurDAG->getTargetConstant(NewFlags, DL, MVT::i32));
2080
517
      Ops.insert(Ops.end(), SelOps.begin(), SelOps.end());
2081
517
      i += 2;
2082
517
    }
2083
93.4k
  }
2084
20.3k
2085
20.3k
  // Add the glue input back if present.
2086
20.3k
  if (e != InOps.size())
2087
3.30k
    Ops.push_back(InOps.back());
2088
20.3k
}
2089
2090
/// findGlueUse - Return use of MVT::Glue value produced by the specified
2091
/// SDNode.
2092
///
2093
3.88k
static SDNode *findGlueUse(SDNode *N) {
2094
3.88k
  unsigned FlagResNo = N->getNumValues()-1;
2095
7.88k
  for (SDNode::use_iterator I = N->use_begin(), E = N->use_end(); I != E; 
++I4.00k
) {
2096
6.18k
    SDUse &Use = I.getUse();
2097
6.18k
    if (Use.getResNo() == FlagResNo)
2098
2.17k
      return Use.getUser();
2099
6.18k
  }
2100
3.88k
  
return nullptr1.70k
;
2101
3.88k
}
2102
2103
/// findNonImmUse - Return true if "Def" is a predecessor of "Root" via a path
2104
/// beyond "ImmedUse".  We may ignore chains as they are checked separately.
2105
static bool findNonImmUse(SDNode *Root, SDNode *Def, SDNode *ImmedUse,
2106
129k
                          bool IgnoreChains) {
2107
129k
  SmallPtrSet<const SDNode *, 16> Visited;
2108
129k
  SmallVector<const SDNode *, 16> WorkList;
2109
129k
  // Only check if we have non-immediate uses of Def.
2110
129k
  if (ImmedUse->isOnlyUserOf(Def))
2111
94.9k
    return false;
2112
34.2k
2113
34.2k
  // We don't care about paths to Def that go through ImmedUse so mark it
2114
34.2k
  // visited and mark non-def operands as used.
2115
34.2k
  Visited.insert(ImmedUse);
2116
78.6k
  for (const SDValue &Op : ImmedUse->op_values()) {
2117
78.6k
    SDNode *N = Op.getNode();
2118
78.6k
    // Ignore chain deps (they are validated by
2119
78.6k
    // HandleMergeInputChains) and immediate uses
2120
78.6k
    if ((Op.getValueType() == MVT::Other && 
IgnoreChains1.50k
) ||
N == Def77.1k
)
2121
35.9k
      continue;
2122
42.6k
    if (!Visited.insert(N).second)
2123
239
      continue;
2124
42.4k
    WorkList.push_back(N);
2125
42.4k
  }
2126
34.2k
2127
34.2k
  // Initialize worklist to operands of Root.
2128
34.2k
  if (Root != ImmedUse) {
2129
57.1k
    for (const SDValue &Op : Root->op_values()) {
2130
57.1k
      SDNode *N = Op.getNode();
2131
57.1k
      // Ignore chains (they are validated by HandleMergeInputChains)
2132
57.1k
      if ((Op.getValueType() == MVT::Other && 
IgnoreChains13.9k
) ||
N == Def43.2k
)
2133
13.9k
        continue;
2134
43.2k
      if (!Visited.insert(N).second)
2135
14.5k
        continue;
2136
28.7k
      WorkList.push_back(N);
2137
28.7k
    }
2138
14.7k
  }
2139
34.2k
2140
34.2k
  return SDNode::hasPredecessorHelper(Def, Visited, WorkList, 0, true);
2141
34.2k
}
2142
2143
/// IsProfitableToFold - Returns true if it's profitable to fold the specific
2144
/// operand node N of U during instruction selection that starts at Root.
2145
bool SelectionDAGISel::IsProfitableToFold(SDValue N, SDNode *U,
2146
3.93k
                                          SDNode *Root) const {
2147
3.93k
  if (OptLevel == CodeGenOpt::None) 
return false174
;
2148
3.75k
  return N.hasOneUse();
2149
3.75k
}
2150
2151
/// IsLegalToFold - Returns true if the specific operand node N of
2152
/// U can be folded during instruction selection that starts at Root.
2153
bool SelectionDAGISel::IsLegalToFold(SDValue N, SDNode *U, SDNode *Root,
2154
                                     CodeGenOpt::Level OptLevel,
2155
129k
                                     bool IgnoreChains) {
2156
129k
  if (OptLevel == CodeGenOpt::None) 
return false23
;
2157
129k
2158
129k
  // If Root use can somehow reach N through a path that that doesn't contain
2159
129k
  // U then folding N would create a cycle. e.g. In the following
2160
129k
  // diagram, Root can reach N through X. If N is folded into Root, then
2161
129k
  // X is both a predecessor and a successor of U.
2162
129k
  //
2163
129k
  //          [N*]           //
2164
129k
  //         ^   ^           //
2165
129k
  //        /     \          //
2166
129k
  //      [U*]    [X]?       //
2167
129k
  //        ^     ^          //
2168
129k
  //         \   /           //
2169
129k
  //          \ /            //
2170
129k
  //         [Root*]         //
2171
129k
  //
2172
129k
  // * indicates nodes to be folded together.
2173
129k
  //
2174
129k
  // If Root produces glue, then it gets (even more) interesting. Since it
2175
129k
  // will be "glued" together with its glue use in the scheduler, we need to
2176
129k
  // check if it might reach N.
2177
129k
  //
2178
129k
  //          [N*]           //
2179
129k
  //         ^   ^           //
2180
129k
  //        /     \          //
2181
129k
  //      [U*]    [X]?       //
2182
129k
  //        ^       ^        //
2183
129k
  //         \       \       //
2184
129k
  //          \      |       //
2185
129k
  //         [Root*] |       //
2186
129k
  //          ^      |       //
2187
129k
  //          f      |       //
2188
129k
  //          |      /       //
2189
129k
  //         [Y]    /        //
2190
129k
  //           ^   /         //
2191
129k
  //           f  /          //
2192
129k
  //           | /           //
2193
129k
  //          [GU]           //
2194
129k
  //
2195
129k
  // If GU (glue use) indirectly reaches N (the load), and Root folds N
2196
129k
  // (call it Fold), then X is a predecessor of GU and a successor of
2197
129k
  // Fold. But since Fold and GU are glued together, this will create
2198
129k
  // a cycle in the scheduling graph.
2199
129k
2200
129k
  // If the node has glue, walk down the graph to the "lowest" node in the
2201
129k
  // glueged set.
2202
129k
  EVT VT = Root->getValueType(Root->getNumValues()-1);
2203
131k
  while (VT == MVT::Glue) {
2204
3.88k
    SDNode *GU = findGlueUse(Root);
2205
3.88k
    if (!GU)
2206
1.70k
      break;
2207
2.17k
    Root = GU;
2208
2.17k
    VT = Root->getValueType(Root->getNumValues()-1);
2209
2.17k
2210
2.17k
    // If our query node has a glue result with a use, we've walked up it.  If
2211
2.17k
    // the user (which has already been selected) has a chain or indirectly uses
2212
2.17k
    // the chain, HandleMergeInputChains will not consider it.  Because of
2213
2.17k
    // this, we cannot ignore chains in this predicate.
2214
2.17k
    IgnoreChains = false;
2215
2.17k
  }
2216
129k
2217
129k
  return !findNonImmUse(Root, N.getNode(), U, IgnoreChains);
2218
129k
}
2219
2220
20.3k
void SelectionDAGISel::Select_INLINEASM(SDNode *N, bool Branch) {
2221
20.3k
  SDLoc DL(N);
2222
20.3k
2223
20.3k
  std::vector<SDValue> Ops(N->op_begin(), N->op_end());
2224
20.3k
  SelectInlineAsmMemoryOperands(Ops, DL);
2225
20.3k
2226
20.3k
  const EVT VTs[] = {MVT::Other, MVT::Glue};
2227
20.3k
  SDValue New = CurDAG->getNode(Branch ? 
ISD::INLINEASM_BR5
:
ISD::INLINEASM20.3k
, DL, VTs, Ops);
2228
20.3k
  New->setNodeId(-1);
2229
20.3k
  ReplaceUses(N, New.getNode());
2230
20.3k
  CurDAG->RemoveDeadNode(N);
2231
20.3k
}
2232
2233
51
void SelectionDAGISel::Select_READ_REGISTER(SDNode *Op) {
2234
51
  SDLoc dl(Op);
2235
51
  MDNodeSDNode *MD = dyn_cast<MDNodeSDNode>(Op->getOperand(1));
2236
51
  const MDString *RegStr = dyn_cast<MDString>(MD->getMD()->getOperand(0));
2237
51
  unsigned Reg =
2238
51
      TLI->getRegisterByName(RegStr->getString().data(), Op->getValueType(0),
2239
51
                             *CurDAG);
2240
51
  SDValue New = CurDAG->getCopyFromReg(
2241
51
                        Op->getOperand(0), dl, Reg, Op->getValueType(0));
2242
51
  New->setNodeId(-1);
2243
51
  ReplaceUses(Op, New.getNode());
2244
51
  CurDAG->RemoveDeadNode(Op);
2245
51
}
2246
2247
29
void SelectionDAGISel::Select_WRITE_REGISTER(SDNode *Op) {
2248
29
  SDLoc dl(Op);
2249
29
  MDNodeSDNode *MD = dyn_cast<MDNodeSDNode>(Op->getOperand(1));
2250
29
  const MDString *RegStr = dyn_cast<MDString>(MD->getMD()->getOperand(0));
2251
29
  unsigned Reg = TLI->getRegisterByName(RegStr->getString().data(),
2252
29
                                        Op->getOperand(2).getValueType(),
2253
29
                                        *CurDAG);
2254
29
  SDValue New = CurDAG->getCopyToReg(
2255
29
                        Op->getOperand(0), dl, Reg, Op->getOperand(2));
2256
29
  New->setNodeId(-1);
2257
29
  ReplaceUses(Op, New.getNode());
2258
29
  CurDAG->RemoveDeadNode(Op);
2259
29
}
2260
2261
12.1k
void SelectionDAGISel::Select_UNDEF(SDNode *N) {
2262
12.1k
  CurDAG->SelectNodeTo(N, TargetOpcode::IMPLICIT_DEF, N->getValueType(0));
2263
12.1k
}
2264
2265
/// GetVBR - decode a vbr encoding whose top bit is set.
2266
LLVM_ATTRIBUTE_ALWAYS_INLINE static inline uint64_t
2267
31.9M
GetVBR(uint64_t Val, const unsigned char *MatcherTable, unsigned &Idx) {
2268
31.9M
  assert(Val >= 128 && "Not a VBR");
2269
31.9M
  Val &= 127;  // Remove first vbr bit.
2270
31.9M
2271
31.9M
  unsigned Shift = 7;
2272
31.9M
  uint64_t NextBits;
2273
38.8M
  do {
2274
38.8M
    NextBits = MatcherTable[Idx++];
2275
38.8M
    Val |= (NextBits&127) << Shift;
2276
38.8M
    Shift += 7;
2277
38.8M
  } while (NextBits & 128);
2278
31.9M
2279
31.9M
  return Val;
2280
31.9M
}
2281
2282
/// When a match is complete, this method updates uses of interior chain results
2283
/// to use the new results.
2284
void SelectionDAGISel::UpdateChains(
2285
    SDNode *NodeToMatch, SDValue InputChain,
2286
7.54M
    SmallVectorImpl<SDNode *> &ChainNodesMatched, bool isMorphNodeTo) {
2287
7.54M
  SmallVector<SDNode*, 4> NowDeadNodes;
2288
7.54M
2289
7.54M
  // Now that all the normal results are replaced, we replace the chain and
2290
7.54M
  // glue results if present.
2291
7.54M
  if (!ChainNodesMatched.empty()) {
2292
4.25M
    assert(InputChain.getNode() &&
2293
4.25M
           "Matched input chains but didn't produce a chain");
2294
4.25M
    // Loop over all of the nodes we matched that produced a chain result.
2295
4.25M
    // Replace all the chain results with the final chain we ended up with.
2296
8.51M
    for (unsigned i = 0, e = ChainNodesMatched.size(); i != e; 
++i4.25M
) {
2297
4.25M
      SDNode *ChainNode = ChainNodesMatched[i];
2298
4.25M
      // If ChainNode is null, it's because we replaced it on a previous
2299
4.25M
      // iteration and we cleared it out of the map. Just skip it.
2300
4.25M
      if (!ChainNode)
2301
0
        continue;
2302
4.25M
2303
4.25M
      assert(ChainNode->getOpcode() != ISD::DELETED_NODE &&
2304
4.25M
             "Deleted node left in chain");
2305
4.25M
2306
4.25M
      // Don't replace the results of the root node if we're doing a
2307
4.25M
      // MorphNodeTo.
2308
4.25M
      if (ChainNode == NodeToMatch && 
isMorphNodeTo4.24M
)
2309
4.24M
        continue;
2310
13.1k
2311
13.1k
      SDValue ChainVal = SDValue(ChainNode, ChainNode->getNumValues()-1);
2312
13.1k
      if (ChainVal.getValueType() == MVT::Glue)
2313
0
        ChainVal = ChainVal.getValue(ChainVal->getNumValues()-2);
2314
13.1k
      assert(ChainVal.getValueType() == MVT::Other && "Not a chain?");
2315
13.1k
      SelectionDAG::DAGNodeDeletedListener NDL(
2316
13.1k
          *CurDAG, [&](SDNode *N, SDNode *E) {
2317
0
            std::replace(ChainNodesMatched.begin(), ChainNodesMatched.end(), N,
2318
0
                         static_cast<SDNode *>(nullptr));
2319
0
          });
2320
13.1k
      if (ChainNode->getOpcode() != ISD::TokenFactor)
2321
13.1k
        ReplaceUses(ChainVal, InputChain);
2322
13.1k
2323
13.1k
      // If the node became dead and we haven't already seen it, delete it.
2324
13.1k
      if (ChainNode != NodeToMatch && 
ChainNode->use_empty()12.1k
&&
2325
13.1k
          
!std::count(NowDeadNodes.begin(), NowDeadNodes.end(), ChainNode)12.1k
)
2326
12.1k
        NowDeadNodes.push_back(ChainNode);
2327
13.1k
    }
2328
4.25M
  }
2329
7.54M
2330
7.54M
  if (!NowDeadNodes.empty())
2331
12.1k
    CurDAG->RemoveDeadNodes(NowDeadNodes);
2332
7.54M
2333
7.54M
  LLVM_DEBUG(dbgs() << "ISEL: Match complete!\n");
2334
7.54M
}
2335
2336
/// HandleMergeInputChains - This implements the OPC_EmitMergeInputChains
2337
/// operation for when the pattern matched at least one node with a chains.  The
2338
/// input vector contains a list of all of the chained nodes that we match.  We
2339
/// must determine if this is a valid thing to cover (i.e. matching it won't
2340
/// induce cycles in the DAG) and if so, creating a TokenFactor node. that will
2341
/// be used as the input node chain for the generated nodes.
2342
static SDValue
2343
HandleMergeInputChains(SmallVectorImpl<SDNode*> &ChainNodesMatched,
2344
4.32M
                       SelectionDAG *CurDAG) {
2345
4.32M
2346
4.32M
  SmallPtrSet<const SDNode *, 16> Visited;
2347
4.32M
  SmallVector<const SDNode *, 8> Worklist;
2348
4.32M
  SmallVector<SDValue, 3> InputChains;
2349
4.32M
  unsigned int Max = 8192;
2350
4.32M
2351
4.32M
  // Quick exit on trivial merge.
2352
4.32M
  if (ChainNodesMatched.size() == 1)
2353
4.32M
    return ChainNodesMatched[0]->getOperand(0);
2354
6.85k
2355
6.85k
  // Add chains that aren't already added (internal). Peek through
2356
6.85k
  // token factors.
2357
15.3k
  
std::function<void(const SDValue)> AddChains = [&](const SDValue V) 6.85k
{
2358
15.3k
    if (V.getValueType() != MVT::Other)
2359
0
      return;
2360
15.3k
    if (V->getOpcode() == ISD::EntryToken)
2361
4.12k
      return;
2362
11.1k
    if (!Visited.insert(V.getNode()).second)
2363
6.65k
      return;
2364
4.51k
    if (V->getOpcode() == ISD::TokenFactor) {
2365
620
      for (const SDValue &Op : V->op_values())
2366
1.54k
        AddChains(Op);
2367
620
    } else
2368
3.89k
      InputChains.push_back(V);
2369
4.51k
  };
2370
6.85k
2371
13.7k
  for (auto *N : ChainNodesMatched) {
2372
13.7k
    Worklist.push_back(N);
2373
13.7k
    Visited.insert(N);
2374
13.7k
  }
2375
6.85k
2376
20.6k
  while (!Worklist.empty())
2377
13.7k
    AddChains(Worklist.pop_back_val()->getOperand(0));
2378
6.85k
2379
6.85k
  // Skip the search if there are no chain dependencies.
2380
6.85k
  if (InputChains.size() == 0)
2381
3.58k
    return CurDAG->getEntryNode();
2382
3.27k
2383
3.27k
  // If one of these chains is a successor of input, we must have a
2384
3.27k
  // node that is both the predecessor and successor of the
2385
3.27k
  // to-be-merged nodes. Fail.
2386
3.27k
  Visited.clear();
2387
3.27k
  for (SDValue V : InputChains)
2388
3.89k
    Worklist.push_back(V.getNode());
2389
3.27k
2390
3.27k
  for (auto *N : ChainNodesMatched)
2391
6.55k
    if (SDNode::hasPredecessorHelper(N, Visited, Worklist, Max, true))
2392
50
      return SDValue();
2393
3.27k
2394
3.27k
  // Return merged chain.
2395
3.27k
  
if (3.22k
InputChains.size() == 13.22k
)
2396
2.91k
    return InputChains[0];
2397
315
  return CurDAG->getNode(ISD::TokenFactor, SDLoc(ChainNodesMatched[0]),
2398
315
                         MVT::Other, InputChains);
2399
315
}
2400
2401
/// MorphNode - Handle morphing a node in place for the selector.
2402
SDNode *SelectionDAGISel::
2403
MorphNode(SDNode *Node, unsigned TargetOpc, SDVTList VTList,
2404
7.41M
          ArrayRef<SDValue> Ops, unsigned EmitNodeInfo) {
2405
7.41M
  // It is possible we're using MorphNodeTo to replace a node with no
2406
7.41M
  // normal results with one that has a normal result (or we could be
2407
7.41M
  // adding a chain) and the input could have glue and chains as well.
2408
7.41M
  // In this case we need to shift the operands down.
2409
7.41M
  // FIXME: This is a horrible hack and broken in obscure cases, no worse
2410
7.41M
  // than the old isel though.
2411
7.41M
  int OldGlueResultNo = -1, OldChainResultNo = -1;
2412
7.41M
2413
7.41M
  unsigned NTMNumResults = Node->getNumValues();
2414
7.41M
  if (Node->getValueType(NTMNumResults-1) == MVT::Glue) {
2415
1.31M
    OldGlueResultNo = NTMNumResults-1;
2416
1.31M
    if (NTMNumResults != 1 &&
2417
1.31M
        
Node->getValueType(NTMNumResults-2) == MVT::Other1.25M
)
2418
1.25M
      OldChainResultNo = NTMNumResults-2;
2419
6.10M
  } else if (Node->getValueType(NTMNumResults-1) == MVT::Other)
2420
2.98M
    OldChainResultNo = NTMNumResults-1;
2421
7.41M
2422
7.41M
  // Call the underlying SelectionDAG routine to do the transmogrification. Note
2423
7.41M
  // that this deletes operands of the old node that become dead.
2424
7.41M
  SDNode *Res = CurDAG->MorphNodeTo(Node, ~TargetOpc, VTList, Ops);
2425
7.41M
2426
7.41M
  // MorphNodeTo can operate in two ways: if an existing node with the
2427
7.41M
  // specified operands exists, it can just return it.  Otherwise, it
2428
7.41M
  // updates the node in place to have the requested operands.
2429
7.41M
  if (Res == Node) {
2430
7.40M
    // If we updated the node in place, reset the node ID.  To the isel,
2431
7.40M
    // this should be just like a newly allocated machine node.
2432
7.40M
    Res->setNodeId(-1);
2433
7.40M
  }
2434
7.41M
2435
7.41M
  unsigned ResNumResults = Res->getNumValues();
2436
7.41M
  // Move the glue if needed.
2437
7.41M
  if ((EmitNodeInfo & OPFL_GlueOutput) && 
OldGlueResultNo != -11.24M
&&
2438
7.41M
      
(unsigned)OldGlueResultNo != ResNumResults-11.24M
)
2439
1.08M
    ReplaceUses(SDValue(Node, OldGlueResultNo),
2440
1.08M
                SDValue(Res, ResNumResults - 1));
2441
7.41M
2442
7.41M
  if ((EmitNodeInfo & OPFL_GlueOutput) != 0)
2443
1.24M
    --ResNumResults;
2444
7.41M
2445
7.41M
  // Move the chain reference if needed.
2446
7.41M
  if ((EmitNodeInfo & OPFL_Chain) && 
OldChainResultNo != -14.32M
&&
2447
7.41M
      
(unsigned)OldChainResultNo != ResNumResults-14.24M
)
2448
1.05M
    ReplaceUses(SDValue(Node, OldChainResultNo),
2449
1.05M
                SDValue(Res, ResNumResults - 1));
2450
7.41M
2451
7.41M
  // Otherwise, no replacement happened because the node already exists. Replace
2452
7.41M
  // Uses of the old node with the new one.
2453
7.41M
  if (Res != Node) {
2454
3.21k
    ReplaceNode(Node, Res);
2455
7.40M
  } else {
2456
7.40M
    EnforceNodeIdInvariant(Res);
2457
7.40M
  }
2458
7.41M
2459
7.41M
  return Res;
2460
7.41M
}
2461
2462
/// CheckSame - Implements OP_CheckSame.
2463
LLVM_ATTRIBUTE_ALWAYS_INLINE static inline bool
2464
CheckSame(const unsigned char *MatcherTable, unsigned &MatcherIndex,
2465
          SDValue N,
2466
63.9k
          const SmallVectorImpl<std::pair<SDValue, SDNode*>> &RecordedNodes) {
2467
63.9k
  // Accept if it is exactly the same as a previously recorded node.
2468
63.9k
  unsigned RecNo = MatcherTable[MatcherIndex++];
2469
63.9k
  assert(RecNo < RecordedNodes.size() && "Invalid CheckSame");
2470
63.9k
  return N == RecordedNodes[RecNo].first;
2471
63.9k
}
2472
2473
/// CheckChildSame - Implements OP_CheckChildXSame.
2474
LLVM_ATTRIBUTE_ALWAYS_INLINE static inline bool
2475
CheckChildSame(const unsigned char *MatcherTable, unsigned &MatcherIndex,
2476
              SDValue N,
2477
              const SmallVectorImpl<std::pair<SDValue, SDNode*>> &RecordedNodes,
2478
60.8k
              unsigned ChildNo) {
2479
60.8k
  if (ChildNo >= N.getNumOperands())
2480
0
    return false;  // Match fails if out of range child #.
2481
60.8k
  return ::CheckSame(MatcherTable, MatcherIndex, N.getOperand(ChildNo),
2482
60.8k
                     RecordedNodes);
2483
60.8k
}
2484
2485
/// CheckPatternPredicate - Implements OP_CheckPatternPredicate.
2486
LLVM_ATTRIBUTE_ALWAYS_INLINE static inline bool
2487
CheckPatternPredicate(const unsigned char *MatcherTable, unsigned &MatcherIndex,
2488
5.08M
                      const SelectionDAGISel &SDISel) {
2489
5.08M
  return SDISel.CheckPatternPredicate(MatcherTable[MatcherIndex++]);
2490
5.08M
}
2491
2492
/// CheckNodePredicate - Implements OP_CheckNodePredicate.
2493
LLVM_ATTRIBUTE_ALWAYS_INLINE static inline bool
2494
CheckNodePredicate(const unsigned char *MatcherTable, unsigned &MatcherIndex,
2495
21.0M
                   const SelectionDAGISel &SDISel, SDNode *N) {
2496
21.0M
  return SDISel.CheckNodePredicate(N, MatcherTable[MatcherIndex++]);
2497
21.0M
}
2498
2499
LLVM_ATTRIBUTE_ALWAYS_INLINE static inline bool
2500
CheckOpcode(const unsigned char *MatcherTable, unsigned &MatcherIndex,
2501
14.4M
            SDNode *N) {
2502
14.4M
  uint16_t Opc = MatcherTable[MatcherIndex++];
2503
14.4M
  Opc |= (unsigned short)MatcherTable[MatcherIndex++] << 8;
2504
14.4M
  return N->getOpcode() == Opc;
2505
14.4M
}
2506
2507
LLVM_ATTRIBUTE_ALWAYS_INLINE static inline bool
2508
CheckType(const unsigned char *MatcherTable, unsigned &MatcherIndex, SDValue N,
2509
19.2M
          const TargetLowering *TLI, const DataLayout &DL) {
2510
19.2M
  MVT::SimpleValueType VT = (MVT::SimpleValueType)MatcherTable[MatcherIndex++];
2511
19.2M
  if (N.getValueType() == VT) 
return true5.59M
;
2512
13.7M
2513
13.7M
  // Handle the case when VT is iPTR.
2514
13.7M
  return VT == MVT::iPTR && 
N.getValueType() == TLI->getPointerTy(DL)92.1k
;
2515
13.7M
}
2516
2517
LLVM_ATTRIBUTE_ALWAYS_INLINE static inline bool
2518
CheckChildType(const unsigned char *MatcherTable, unsigned &MatcherIndex,
2519
               SDValue N, const TargetLowering *TLI, const DataLayout &DL,
2520
14.7M
               unsigned ChildNo) {
2521
14.7M
  if (ChildNo >= N.getNumOperands())
2522
0
    return false;  // Match fails if out of range child #.
2523
14.7M
  return ::CheckType(MatcherTable, MatcherIndex, N.getOperand(ChildNo), TLI,
2524
14.7M
                     DL);
2525
14.7M
}
2526
2527
LLVM_ATTRIBUTE_ALWAYS_INLINE static inline bool
2528
CheckCondCode(const unsigned char *MatcherTable, unsigned &MatcherIndex,
2529
177k
              SDValue N) {
2530
177k
  return cast<CondCodeSDNode>(N)->get() ==
2531
177k
      (ISD::CondCode)MatcherTable[MatcherIndex++];
2532
177k
}
2533
2534
LLVM_ATTRIBUTE_ALWAYS_INLINE static inline bool
2535
CheckChild2CondCode(const unsigned char *MatcherTable, unsigned &MatcherIndex,
2536
158k
                    SDValue N) {
2537
158k
  if (2 >= N.getNumOperands())
2538
0
    return false;
2539
158k
  return ::CheckCondCode(MatcherTable, MatcherIndex, N.getOperand(2));
2540
158k
}
2541
2542
LLVM_ATTRIBUTE_ALWAYS_INLINE static inline bool
2543
CheckValueType(const unsigned char *MatcherTable, unsigned &MatcherIndex,
2544
26.7k
               SDValue N, const TargetLowering *TLI, const DataLayout &DL) {
2545
26.7k
  MVT::SimpleValueType VT = (MVT::SimpleValueType)MatcherTable[MatcherIndex++];
2546
26.7k
  if (cast<VTSDNode>(N)->getVT() == VT)
2547
13.7k
    return true;
2548
12.9k
2549
12.9k
  // Handle the case when VT is iPTR.
2550
12.9k
  return VT == MVT::iPTR && 
cast<VTSDNode>(N)->getVT() == TLI->getPointerTy(DL)0
;
2551
12.9k
}
2552
2553
LLVM_ATTRIBUTE_ALWAYS_INLINE static inline bool
2554
CheckInteger(const unsigned char *MatcherTable, unsigned &MatcherIndex,
2555
5.94M
             SDValue N) {
2556
5.94M
  int64_t Val = MatcherTable[MatcherIndex++];
2557
5.94M
  if (Val & 128)
2558
4.55M
    Val = GetVBR(Val, MatcherTable, MatcherIndex);
2559
5.94M
2560
5.94M
  ConstantSDNode *C = dyn_cast<ConstantSDNode>(N);
2561
5.94M
  return C && 
C->getSExtValue() == Val5.20M
;
2562
5.94M
}
2563
2564
LLVM_ATTRIBUTE_ALWAYS_INLINE static inline bool
2565
CheckChildInteger(const unsigned char *MatcherTable, unsigned &MatcherIndex,
2566
5.72M
                  SDValue N, unsigned ChildNo) {
2567
5.72M
  if (ChildNo >= N.getNumOperands())
2568
0
    return false;  // Match fails if out of range child #.
2569
5.72M
  return ::CheckInteger(MatcherTable, MatcherIndex, N.getOperand(ChildNo));
2570
5.72M
}
2571
2572
LLVM_ATTRIBUTE_ALWAYS_INLINE static inline bool
2573
CheckAndImm(const unsigned char *MatcherTable, unsigned &MatcherIndex,
2574
2.37M
            SDValue N, const SelectionDAGISel &SDISel) {
2575
2.37M
  int64_t Val = MatcherTable[MatcherIndex++];
2576
2.37M
  if (Val & 128)
2577
2.37M
    Val = GetVBR(Val, MatcherTable, MatcherIndex);
2578
2.37M
2579
2.37M
  if (N->getOpcode() != ISD::AND) 
return false1.01M
;
2580
1.36M
2581
1.36M
  ConstantSDNode *C = dyn_cast<ConstantSDNode>(N->getOperand(1));
2582
1.36M
  return C && 
SDISel.CheckAndMask(N.getOperand(0), C, Val)931k
;
2583
1.36M
}
2584
2585
LLVM_ATTRIBUTE_ALWAYS_INLINE static inline bool
2586
CheckOrImm(const unsigned char *MatcherTable, unsigned &MatcherIndex,
2587
3.94k
           SDValue N, const SelectionDAGISel &SDISel) {
2588
3.94k
  int64_t Val = MatcherTable[MatcherIndex++];
2589
3.94k
  if (Val & 128)
2590
3.94k
    Val = GetVBR(Val, MatcherTable, MatcherIndex);
2591
3.94k
2592
3.94k
  if (N->getOpcode() != ISD::OR) 
return false0
;
2593
3.94k
2594
3.94k
  ConstantSDNode *C = dyn_cast<ConstantSDNode>(N->getOperand(1));
2595
3.94k
  return C && 
SDISel.CheckOrMask(N.getOperand(0), C, Val)776
;
2596
3.94k
}
2597
2598
/// IsPredicateKnownToFail - If we know how and can do so without pushing a
2599
/// scope, evaluate the current node.  If the current predicate is known to
2600
/// fail, set Result=true and return anything.  If the current predicate is
2601
/// known to pass, set Result=false and return the MatcherIndex to continue
2602
/// with.  If the current predicate is unknown, set Result=false and return the
2603
/// MatcherIndex to continue with.
2604
static unsigned IsPredicateKnownToFail(const unsigned char *Table,
2605
                                       unsigned Index, SDValue N,
2606
                                       bool &Result,
2607
                                       const SelectionDAGISel &SDISel,
2608
31.5M
                  SmallVectorImpl<std::pair<SDValue, SDNode*>> &RecordedNodes) {
2609
31.5M
  switch (Table[Index++]) {
2610
31.5M
  default:
2611
7.73M
    Result = false;
2612
7.73M
    return Index-1;  // Could not evaluate this predicate.
2613
31.5M
  case SelectionDAGISel::OPC_CheckSame:
2614
0
    Result = !::CheckSame(Table, Index, N, RecordedNodes);
2615
0
    return Index;
2616
31.5M
  case SelectionDAGISel::OPC_CheckChild0Same:
2617
24.8k
  case SelectionDAGISel::OPC_CheckChild1Same:
2618
24.8k
  case SelectionDAGISel::OPC_CheckChild2Same:
2619
24.8k
  case SelectionDAGISel::OPC_CheckChild3Same:
2620
24.8k
    Result = !::CheckChildSame(Table, Index, N, RecordedNodes,
2621
24.8k
                        Table[Index-1] - SelectionDAGISel::OPC_CheckChild0Same);
2622
24.8k
    return Index;
2623
2.35M
  case SelectionDAGISel::OPC_CheckPatternPredicate:
2624
2.35M
    Result = !::CheckPatternPredicate(Table, Index, SDISel);
2625
2.35M
    return Index;
2626
5.07M
  case SelectionDAGISel::OPC_CheckPredicate:
2627
5.07M
    Result = !::CheckNodePredicate(Table, Index, SDISel, N.getNode());
2628
5.07M
    return Index;
2629
338k
  case SelectionDAGISel::OPC_CheckOpcode:
2630
338k
    Result = !::CheckOpcode(Table, Index, N.getNode());
2631
338k
    return Index;
2632
24.8k
  case SelectionDAGISel::OPC_CheckType:
2633
14.0k
    Result = !::CheckType(Table, Index, N, SDISel.TLI,
2634
14.0k
                          SDISel.CurDAG->getDataLayout());
2635
14.0k
    return Index;
2636
24.8k
  case SelectionDAGISel::OPC_CheckTypeRes: {
2637
0
    unsigned Res = Table[Index++];
2638
0
    Result = !::CheckType(Table, Index, N.getValue(Res), SDISel.TLI,
2639
0
                          SDISel.CurDAG->getDataLayout());
2640
0
    return Index;
2641
24.8k
  }
2642
9.99M
  case SelectionDAGISel::OPC_CheckChild0Type:
2643
9.99M
  case SelectionDAGISel::OPC_CheckChild1Type:
2644
9.99M
  case SelectionDAGISel::OPC_CheckChild2Type:
2645
9.99M
  case SelectionDAGISel::OPC_CheckChild3Type:
2646
9.99M
  case SelectionDAGISel::OPC_CheckChild4Type:
2647
9.99M
  case SelectionDAGISel::OPC_CheckChild5Type:
2648
9.99M
  case SelectionDAGISel::OPC_CheckChild6Type:
2649
9.99M
  case SelectionDAGISel::OPC_CheckChild7Type:
2650
9.99M
    Result = !::CheckChildType(
2651
9.99M
                 Table, Index, N, SDISel.TLI, SDISel.CurDAG->getDataLayout(),
2652
9.99M
                 Table[Index - 1] - SelectionDAGISel::OPC_CheckChild0Type);
2653
9.99M
    return Index;
2654
9.99M
  case SelectionDAGISel::OPC_CheckCondCode:
2655
14.1k
    Result = !::CheckCondCode(Table, Index, N);
2656
14.1k
    return Index;
2657
9.99M
  case SelectionDAGISel::OPC_CheckChild2CondCode:
2658
51.6k
    Result = !::CheckChild2CondCode(Table, Index, N);
2659
51.6k
    return Index;
2660
9.99M
  case SelectionDAGISel::OPC_CheckValueType:
2661
24.6k
    Result = !::CheckValueType(Table, Index, N, SDISel.TLI,
2662
24.6k
                               SDISel.CurDAG->getDataLayout());
2663
24.6k
    return Index;
2664
9.99M
  case SelectionDAGISel::OPC_CheckInteger:
2665
196k
    Result = !::CheckInteger(Table, Index, N);
2666
196k
    return Index;
2667
9.99M
  case SelectionDAGISel::OPC_CheckChild0Integer:
2668
4.48M
  case SelectionDAGISel::OPC_CheckChild1Integer:
2669
4.48M
  case SelectionDAGISel::OPC_CheckChild2Integer:
2670
4.48M
  case SelectionDAGISel::OPC_CheckChild3Integer:
2671
4.48M
  case SelectionDAGISel::OPC_CheckChild4Integer:
2672
4.48M
    Result = !::CheckChildInteger(Table, Index, N,
2673
4.48M
                     Table[Index-1] - SelectionDAGISel::OPC_CheckChild0Integer);
2674
4.48M
    return Index;
2675
4.48M
  case SelectionDAGISel::OPC_CheckAndImm:
2676
1.22M
    Result = !::CheckAndImm(Table, Index, N, SDISel);
2677
1.22M
    return Index;
2678
4.48M
  case SelectionDAGISel::OPC_CheckOrImm:
2679
0
    Result = !::CheckOrImm(Table, Index, N, SDISel);
2680
0
    return Index;
2681
31.5M
  }
2682
31.5M
}
2683
2684
namespace {
2685
2686
struct MatchScope {
2687
  /// FailIndex - If this match fails, this is the index to continue with.
2688
  unsigned FailIndex;
2689
2690
  /// NodeStack - The node stack when the scope was formed.
2691
  SmallVector<SDValue, 4> NodeStack;
2692
2693
  /// NumRecordedNodes - The number of recorded nodes when the scope was formed.
2694
  unsigned NumRecordedNodes;
2695
2696
  /// NumMatchedMemRefs - The number of matched memref entries.
2697
  unsigned NumMatchedMemRefs;
2698
2699
  /// InputChain/InputGlue - The current chain/glue
2700
  SDValue InputChain, InputGlue;
2701
2702
  /// HasChainNodesMatched - True if the ChainNodesMatched list is non-empty.
2703
  bool HasChainNodesMatched;
2704
};
2705
2706
/// \A DAG update listener to keep the matching state
2707
/// (i.e. RecordedNodes and MatchScope) uptodate if the target is allowed to
2708
/// change the DAG while matching.  X86 addressing mode matcher is an example
2709
/// for this.
2710
class MatchStateUpdater : public SelectionDAG::DAGUpdateListener
2711
{
2712
  SDNode **NodeToMatch;
2713
  SmallVectorImpl<std::pair<SDValue, SDNode *>> &RecordedNodes;
2714
  SmallVectorImpl<MatchScope> &MatchScopes;
2715
2716
public:
2717
  MatchStateUpdater(SelectionDAG &DAG, SDNode **NodeToMatch,
2718
                    SmallVectorImpl<std::pair<SDValue, SDNode *>> &RN,
2719
                    SmallVectorImpl<MatchScope> &MS)
2720
      : SelectionDAG::DAGUpdateListener(DAG), NodeToMatch(NodeToMatch),
2721
922k
        RecordedNodes(RN), MatchScopes(MS) {}
2722
2723
8.97k
  void NodeDeleted(SDNode *N, SDNode *E) override {
2724
8.97k
    // Some early-returns here to avoid the search if we deleted the node or
2725
8.97k
    // if the update comes from MorphNodeTo (MorphNodeTo is the last thing we
2726
8.97k
    // do, so it's unnecessary to update matching state at that point).
2727
8.97k
    // Neither of these can occur currently because we only install this
2728
8.97k
    // update listener during matching a complex patterns.
2729
8.97k
    if (!E || 
E->isMachineOpcode()10
)
2730
8.96k
      return;
2731
8
    // Check if NodeToMatch was updated.
2732
8
    if (N == *NodeToMatch)
2733
4
      *NodeToMatch = E;
2734
8
    // Performing linear search here does not matter because we almost never
2735
8
    // run this code.  You'd have to have a CSE during complex pattern
2736
8
    // matching.
2737
8
    for (auto &I : RecordedNodes)
2738
50
      if (I.first.getNode() == N)
2739
5
        I.first.setNode(E);
2740
8
2741
8
    for (auto &I : MatchScopes)
2742
16
      for (auto &J : I.NodeStack)
2743
17
        if (J.getNode() == N)
2744
9
          J.setNode(E);
2745
8
  }
2746
};
2747
2748
} // end anonymous namespace
2749
2750
void SelectionDAGISel::SelectCodeCommon(SDNode *NodeToMatch,
2751
                                        const unsigned char *MatcherTable,
2752
20.7M
                                        unsigned TableSize) {
2753
20.7M
  // FIXME: Should these even be selected?  Handle these cases in the caller?
2754
20.7M
  switch (NodeToMatch->getOpcode()) {
2755
20.7M
  default:
2756
7.54M
    break;
2757
20.7M
  case ISD::EntryToken:       // These nodes remain the same.
2758
12.9M
  case ISD::BasicBlock:
2759
12.9M
  case ISD::Register:
2760
12.9M
  case ISD::RegisterMask:
2761
12.9M
  case ISD::HANDLENODE:
2762
12.9M
  case ISD::MDNODE_SDNODE:
2763
12.9M
  case ISD::TargetConstant:
2764
12.9M
  case ISD::TargetConstantFP:
2765
12.9M
  case ISD::TargetConstantPool:
2766
12.9M
  case ISD::TargetFrameIndex:
2767
12.9M
  case ISD::TargetExternalSymbol:
2768
12.9M
  case ISD::MCSymbol:
2769
12.9M
  case ISD::TargetBlockAddress:
2770
12.9M
  case ISD::TargetJumpTable:
2771
12.9M
  case ISD::TargetGlobalTLSAddress:
2772
12.9M
  case ISD::TargetGlobalAddress:
2773
12.9M
  case ISD::TokenFactor:
2774
12.9M
  case ISD::CopyFromReg:
2775
12.9M
  case ISD::CopyToReg:
2776
12.9M
  case ISD::EH_LABEL:
2777
12.9M
  case ISD::ANNOTATION_LABEL:
2778
12.9M
  case ISD::LIFETIME_START:
2779
12.9M
  case ISD::LIFETIME_END:
2780
12.9M
    NodeToMatch->setNodeId(-1); // Mark selected.
2781
12.9M
    return;
2782
12.9M
  case ISD::AssertSext:
2783
222k
  case ISD::AssertZext:
2784
222k
    ReplaceUses(SDValue(NodeToMatch, 0), NodeToMatch->getOperand(0));
2785
222k
    CurDAG->RemoveDeadNode(NodeToMatch);
2786
222k
    return;
2787
222k
  case ISD::INLINEASM:
2788
20.3k
  case ISD::INLINEASM_BR:
2789
20.3k
    Select_INLINEASM(NodeToMatch,
2790
20.3k
                     NodeToMatch->getOpcode() == ISD::INLINEASM_BR);
2791
20.3k
    return;
2792
20.3k
  case ISD::READ_REGISTER:
2793
51
    Select_READ_REGISTER(NodeToMatch);
2794
51
    return;
2795
20.3k
  case ISD::WRITE_REGISTER:
2796
29
    Select_WRITE_REGISTER(NodeToMatch);
2797
29
    return;
2798
20.3k
  case ISD::UNDEF:
2799
12.1k
    Select_UNDEF(NodeToMatch);
2800
12.1k
    return;
2801
7.54M
  }
2802
7.54M
2803
7.54M
  assert(!NodeToMatch->isMachineOpcode() && "Node already selected!");
2804
7.54M
2805
7.54M
  // Set up the node stack with NodeToMatch as the only node on the stack.
2806
7.54M
  SmallVector<SDValue, 8> NodeStack;
2807
7.54M
  SDValue N = SDValue(NodeToMatch, 0);
2808
7.54M
  NodeStack.push_back(N);
2809
7.54M
2810
7.54M
  // MatchScopes - Scopes used when matching, if a match failure happens, this
2811
7.54M
  // indicates where to continue checking.
2812
7.54M
  SmallVector<MatchScope, 8> MatchScopes;
2813
7.54M
2814
7.54M
  // RecordedNodes - This is the set of nodes that have been recorded by the
2815
7.54M
  // state machine.  The second value is the parent of the node, or null if the
2816
7.54M
  // root is recorded.
2817
7.54M
  SmallVector<std::pair<SDValue, SDNode*>, 8> RecordedNodes;
2818
7.54M
2819
7.54M
  // MatchedMemRefs - This is the set of MemRef's we've seen in the input
2820
7.54M
  // pattern.
2821
7.54M
  SmallVector<MachineMemOperand*, 2> MatchedMemRefs;
2822
7.54M
2823
7.54M
  // These are the current input chain and glue for use when generating nodes.
2824
7.54M
  // Various Emit operations change these.  For example, emitting a copytoreg
2825
7.54M
  // uses and updates these.
2826
7.54M
  SDValue InputChain, InputGlue;
2827
7.54M
2828
7.54M
  // ChainNodesMatched - If a pattern matches nodes that have input/output
2829
7.54M
  // chains, the OPC_EmitMergeInputChains operation is emitted which indicates
2830
7.54M
  // which ones they are.  The result is captured into this list so that we can
2831
7.54M
  // update the chain results when the pattern is complete.
2832
7.54M
  SmallVector<SDNode*, 3> ChainNodesMatched;
2833
7.54M
2834
7.54M
  LLVM_DEBUG(dbgs() << "ISEL: Starting pattern match\n");
2835
7.54M
2836
7.54M
  // Determine where to start the interpreter.  Normally we start at opcode #0,
2837
7.54M
  // but if the state machine starts with an OPC_SwitchOpcode, then we
2838
7.54M
  // accelerate the first lookup (which is guaranteed to be hot) with the
2839
7.54M
  // OpcodeOffset table.
2840
7.54M
  unsigned MatcherIndex = 0;
2841
7.54M
2842
7.54M
  if (!OpcodeOffset.empty()) {
2843
7.51M
    // Already computed the OpcodeOffset table, just index into it.
2844
7.51M
    if (N.getOpcode() < OpcodeOffset.size())
2845
7.51M
      MatcherIndex = OpcodeOffset[N.getOpcode()];
2846
7.51M
    LLVM_DEBUG(dbgs() << "  Initial Opcode index to " << MatcherIndex << "\n");
2847
7.51M
2848
7.51M
  } else 
if (30.3k
MatcherTable[0] == OPC_SwitchOpcode30.3k
) {
2849
30.3k
    // Otherwise, the table isn't computed, but the state machine does start
2850
30.3k
    // with an OPC_SwitchOpcode instruction.  Populate the table now, since this
2851
30.3k
    // is the first time we're selecting an instruction.
2852
30.3k
    unsigned Idx = 1;
2853
8.04M
    while (true) {
2854
8.04M
      // Get the size of this case.
2855
8.04M
      unsigned CaseSize = MatcherTable[Idx++];
2856
8.04M
      if (CaseSize & 128)
2857
4.26M
        CaseSize = GetVBR(CaseSize, MatcherTable, Idx);
2858
8.04M
      if (CaseSize == 0) 
break30.3k
;
2859
8.01M
2860
8.01M
      // Get the opcode, add the index to the table.
2861
8.01M
      uint16_t Opc = MatcherTable[Idx++];
2862
8.01M
      Opc |= (unsigned short)MatcherTable[Idx++] << 8;
2863
8.01M
      if (Opc >= OpcodeOffset.size())
2864
61.8k
        OpcodeOffset.resize((Opc+1)*2);
2865
8.01M
      OpcodeOffset[Opc] = Idx;
2866
8.01M
      Idx += CaseSize;
2867
8.01M
    }
2868
30.3k
2869
30.3k
    // Okay, do the lookup for the first opcode.
2870
30.3k
    if (N.getOpcode() < OpcodeOffset.size())
2871
30.3k
      MatcherIndex = OpcodeOffset[N.getOpcode()];
2872
30.3k
  }
2873
7.54M
2874
146M
  while (
true146M
) {
2875
146M
    assert(MatcherIndex < TableSize && "Invalid index");
2876
#ifndef NDEBUG
2877
    unsigned CurrentOpcodeIndex = MatcherIndex;
2878
#endif
2879
    BuiltinOpcodes Opcode = (BuiltinOpcodes)MatcherTable[MatcherIndex++];
2880
146M
    switch (Opcode) {
2881
146M
    case OPC_Scope: {
2882
14.9M
      // Okay, the semantics of this operation are that we should push a scope
2883
14.9M
      // then evaluate the first child.  However, pushing a scope only to have
2884
14.9M
      // the first check fail (which then pops it) is inefficient.  If we can
2885
14.9M
      // determine immediately that the first check (or first several) will
2886
14.9M
      // immediately fail, don't even bother pushing a scope for them.
2887
14.9M
      unsigned FailIndex;
2888
14.9M
2889
31.9M
      while (true) {
2890
31.9M
        unsigned NumToSkip = MatcherTable[MatcherIndex++];
2891
31.9M
        if (NumToSkip & 128)
2892
5.28M
          NumToSkip = GetVBR(NumToSkip, MatcherTable, MatcherIndex);
2893
31.9M
        // Found the end of the scope with no match.
2894
31.9M
        if (NumToSkip == 0) {
2895
406k
          FailIndex = 0;
2896
406k
          break;
2897
406k
        }
2898
31.5M
2899
31.5M
        FailIndex = MatcherIndex+NumToSkip;
2900
31.5M
2901
31.5M
        unsigned MatcherIndexOfPredicate = MatcherIndex;
2902
31.5M
        (void)MatcherIndexOfPredicate; // silence warning.
2903
31.5M
2904
31.5M
        // If we can't evaluate this predicate without pushing a scope (e.g. if
2905
31.5M
        // it is a 'MoveParent') or if the predicate succeeds on this node, we
2906
31.5M
        // push the scope and evaluate the full predicate chain.
2907
31.5M
        bool Result;
2908
31.5M
        MatcherIndex = IsPredicateKnownToFail(MatcherTable, MatcherIndex, N,
2909
31.5M
                                              Result, *this, RecordedNodes);
2910
31.5M
        if (!Result)
2911
14.5M
          break;
2912
16.9M
2913
16.9M
        LLVM_DEBUG(
2914
16.9M
            dbgs() << "  Skipped scope entry (due to false predicate) at "
2915
16.9M
                   << "index " << MatcherIndexOfPredicate << ", continuing at "
2916
16.9M
                   << FailIndex << "\n");
2917
16.9M
        ++NumDAGIselRetries;
2918
16.9M
2919
16.9M
        // Otherwise, we know that this case of the Scope is guaranteed to fail,
2920
16.9M
        // move to the next case.
2921
16.9M
        MatcherIndex = FailIndex;
2922
16.9M
      }
2923
14.9M
2924
14.9M
      // If the whole scope failed to match, bail.
2925
14.9M
      if (FailIndex == 0) 
break406k
;
2926
14.5M
2927
14.5M
      // Push a MatchScope which indicates where to go if the first child fails
2928
14.5M
      // to match.
2929
14.5M
      MatchScope NewEntry;
2930
14.5M
      NewEntry.FailIndex = FailIndex;
2931
14.5M
      NewEntry.NodeStack.append(NodeStack.begin(), NodeStack.end());
2932
14.5M
      NewEntry.NumRecordedNodes = RecordedNodes.size();
2933
14.5M
      NewEntry.NumMatchedMemRefs = MatchedMemRefs.size();
2934
14.5M
      NewEntry.InputChain = InputChain;
2935
14.5M
      NewEntry.InputGlue = InputGlue;
2936
14.5M
      NewEntry.HasChainNodesMatched = !ChainNodesMatched.empty();
2937
14.5M
      MatchScopes.push_back(NewEntry);
2938
14.5M
      continue;
2939
14.5M
    }
2940
14.5M
    case OPC_RecordNode: {
2941
5.19M
      // Remember this node, it may end up being an operand in the pattern.
2942
5.19M
      SDNode *Parent = nullptr;
2943
5.19M
      if (NodeStack.size() > 1)
2944
266k
        Parent = NodeStack[NodeStack.size()-2].getNode();
2945
5.19M
      RecordedNodes.push_back(std::make_pair(N, Parent));
2946
5.19M
      continue;
2947
14.5M
    }
2948
14.5M
2949
20.8M
    case OPC_RecordChild0: case OPC_RecordChild1:
2950
20.8M
    case OPC_RecordChild2: case OPC_RecordChild3:
2951
20.8M
    case OPC_RecordChild4: case OPC_RecordChild5:
2952
20.8M
    case OPC_RecordChild6: case OPC_RecordChild7: {
2953
20.8M
      unsigned ChildNo = Opcode-OPC_RecordChild0;
2954
20.8M
      if (ChildNo >= N.getNumOperands())
2955
1.50k
        break;  // Match fails if out of range child #.
2956
20.8M
2957
20.8M
      RecordedNodes.push_back(std::make_pair(N->getOperand(ChildNo),
2958
20.8M
                                             N.getNode()));
2959
20.8M
      continue;
2960
20.8M
    }
2961
20.8M
    case OPC_RecordMemRef:
2962
1.74M
      if (auto *MN = dyn_cast<MemSDNode>(N))
2963
1.74M
        MatchedMemRefs.push_back(MN->getMemOperand());
2964
112
      else {
2965
112
        LLVM_DEBUG(dbgs() << "Expected MemSDNode "; N->dump(CurDAG);
2966
112
                   dbgs() << '\n');
2967
112
      }
2968
1.74M
2969
1.74M
      continue;
2970
20.8M
2971
20.8M
    case OPC_CaptureGlueInput:
2972
1.73M
      // If the current node has an input glue, capture it in InputGlue.
2973
1.73M
      if (N->getNumOperands() != 0 &&
2974
1.73M
          N->getOperand(N->getNumOperands()-1).getValueType() == MVT::Glue)
2975
1.00M
        InputGlue = N->getOperand(N->getNumOperands()-1);
2976
1.73M
      continue;
2977
20.8M
2978
20.8M
    case OPC_MoveChild: {
2979
8.17k
      unsigned ChildNo = MatcherTable[MatcherIndex++];
2980
8.17k
      if (ChildNo >= N.getNumOperands())
2981
148
        break;  // Match fails if out of range child #.
2982
8.02k
      N = N.getOperand(ChildNo);
2983
8.02k
      NodeStack.push_back(N);
2984
8.02k
      continue;
2985
8.02k
    }
2986
8.02k
2987
18.7M
    case OPC_MoveChild0: case OPC_MoveChild1:
2988
18.7M
    case OPC_MoveChild2: case OPC_MoveChild3:
2989
18.7M
    case OPC_MoveChild4: case OPC_MoveChild5:
2990
18.7M
    case OPC_MoveChild6: case OPC_MoveChild7: {
2991
18.7M
      unsigned ChildNo = Opcode-OPC_MoveChild0;
2992
18.7M
      if (ChildNo >= N.getNumOperands())
2993
408
        break;  // Match fails if out of range child #.
2994
18.7M
      N = N.getOperand(ChildNo);
2995
18.7M
      NodeStack.push_back(N);
2996
18.7M
      continue;
2997
18.7M
    }
2998
18.7M
2999
18.7M
    case OPC_MoveParent:
3000
6.52M
      // Pop the current node off the NodeStack.
3001
6.52M
      NodeStack.pop_back();
3002
6.52M
      assert(!NodeStack.empty() && "Node stack imbalance!");
3003
6.52M
      N = NodeStack.back();
3004
6.52M
      continue;
3005
18.7M
3006
18.7M
    case OPC_CheckSame:
3007
3.16k
      if (!::CheckSame(MatcherTable, MatcherIndex, N, RecordedNodes)) 
break0
;
3008
3.16k
      continue;
3009
3.16k
3010
35.9k
    case OPC_CheckChild0Same: case OPC_CheckChild1Same:
3011
35.9k
    case OPC_CheckChild2Same: case OPC_CheckChild3Same:
3012
35.9k
      if (!::CheckChildSame(MatcherTable, MatcherIndex, N, RecordedNodes,
3013
35.9k
                            Opcode-OPC_CheckChild0Same))
3014
14.6k
        break;
3015
21.3k
      continue;
3016
21.3k
3017
2.72M
    case OPC_CheckPatternPredicate:
3018
2.72M
      if (!::CheckPatternPredicate(MatcherTable, MatcherIndex, *this)) 
break1.04M
;
3019
1.68M
      continue;
3020
15.9M
    case OPC_CheckPredicate:
3021
15.9M
      if (!::CheckNodePredicate(MatcherTable, MatcherIndex, *this,
3022
15.9M
                                N.getNode()))
3023
8.76M
        break;
3024
7.20M
      continue;
3025
7.20M
    case OPC_CheckPredicateWithOperands: {
3026
7.00k
      unsigned OpNum = MatcherTable[MatcherIndex++];
3027
7.00k
      SmallVector<SDValue, 8> Operands;
3028
7.00k
3029
28.0k
      for (unsigned i = 0; i < OpNum; 
++i21.0k
)
3030
21.0k
        Operands.push_back(RecordedNodes[MatcherTable[MatcherIndex++]].first);
3031
7.00k
3032
7.00k
      unsigned PredNo = MatcherTable[MatcherIndex++];
3033
7.00k
      if (!CheckNodePredicateWithOperands(N.getNode(), PredNo, Operands))
3034
5.28k
        break;
3035
1.71k
      continue;
3036
1.71k
    }
3037
5.68M
    case OPC_CheckComplexPat: {
3038
5.68M
      unsigned CPNum = MatcherTable[MatcherIndex++];
3039
5.68M
      unsigned RecNo = MatcherTable[MatcherIndex++];
3040
5.68M
      assert(RecNo < RecordedNodes.size() && "Invalid CheckComplexPat");
3041
5.68M
3042
5.68M
      // If target can modify DAG during matching, keep the matching state
3043
5.68M
      // consistent.
3044
5.68M
      std::unique_ptr<MatchStateUpdater> MSU;
3045
5.68M
      if (ComplexPatternFuncMutatesDAG())
3046
922k
        MSU.reset(new MatchStateUpdater(*CurDAG, &NodeToMatch, RecordedNodes,
3047
922k
                                        MatchScopes));
3048
5.68M
3049
5.68M
      if (!CheckComplexPattern(NodeToMatch, RecordedNodes[RecNo].second,
3050
5.68M
                               RecordedNodes[RecNo].first, CPNum,
3051
5.68M
                               RecordedNodes))
3052
3.60M
        break;
3053
2.08M
      continue;
3054
2.08M
    }
3055
14.0M
    case OPC_CheckOpcode:
3056
14.0M
      if (!::CheckOpcode(MatcherTable, MatcherIndex, N.getNode())) 
break9.38M
;
3057
4.68M
      continue;
3058
4.68M
3059
4.68M
    case OPC_CheckType:
3060
4.53M
      if (!::CheckType(MatcherTable, MatcherIndex, N, TLI,
3061
4.53M
                       CurDAG->getDataLayout()))
3062
2.09M
        break;
3063
2.43M
      continue;
3064
2.43M
3065
2.43M
    case OPC_CheckTypeRes: {
3066
796
      unsigned Res = MatcherTable[MatcherIndex++];
3067
796
      if (!::CheckType(MatcherTable, MatcherIndex, N.getValue(Res), TLI,
3068
796
                       CurDAG->getDataLayout()))
3069
154
        break;
3070
642
      continue;
3071
642
    }
3072
642
3073
3.93M
    case OPC_SwitchOpcode: {
3074
3.93M
      unsigned CurNodeOpcode = N.getOpcode();
3075
3.93M
      unsigned SwitchStart = MatcherIndex-1; (void)SwitchStart;
3076
3.93M
      unsigned CaseSize;
3077
16.1M
      while (true) {
3078
16.1M
        // Get the size of this case.
3079
16.1M
        CaseSize = MatcherTable[MatcherIndex++];
3080
16.1M
        if (CaseSize & 128)
3081
6.09M
          CaseSize = GetVBR(CaseSize, MatcherTable, MatcherIndex);
3082
16.1M
        if (CaseSize == 0) 
break2.66M
;
3083
13.4M
3084
13.4M
        uint16_t Opc = MatcherTable[MatcherIndex++];
3085
13.4M
        Opc |= (unsigned short)MatcherTable[MatcherIndex++] << 8;
3086
13.4M
3087
13.4M
        // If the opcode matches, then we will execute this case.
3088
13.4M
        if (CurNodeOpcode == Opc)
3089
1.26M
          break;
3090
12.1M
3091
12.1M
        // Otherwise, skip over this case.
3092
12.1M
        MatcherIndex += CaseSize;
3093
12.1M
      }
3094
3.93M
3095
3.93M
      // If no cases matched, bail out.
3096
3.93M
      if (CaseSize == 0) 
break2.66M
;
3097
1.26M
3098
1.26M
      // Otherwise, execute the case we found.
3099
1.26M
      LLVM_DEBUG(dbgs() << "  OpcodeSwitch from " << SwitchStart << " to "
3100
1.26M
                        << MatcherIndex << "\n");
3101
1.26M
      continue;
3102
1.26M
    }
3103
1.26M
3104
4.10M
    case OPC_SwitchType: {
3105
4.10M
      MVT CurNodeVT = N.getSimpleValueType();
3106
4.10M
      unsigned SwitchStart = MatcherIndex-1; (void)SwitchStart;
3107
4.10M
      unsigned CaseSize;
3108
10.2M
      while (
true10.2M
) {
3109
10.2M
        // Get the size of this case.
3110
10.2M
        CaseSize = MatcherTable[MatcherIndex++];
3111
10.2M
        if (CaseSize & 128)
3112
208k
          CaseSize = GetVBR(CaseSize, MatcherTable, MatcherIndex);
3113
10.2M
        if (CaseSize == 0) 
break645k
;
3114
9.58M
3115
9.58M
        MVT CaseVT = (MVT::SimpleValueType)MatcherTable[MatcherIndex++];
3116
9.58M
        if (CaseVT == MVT::iPTR)
3117
0
          CaseVT = TLI->getPointerTy(CurDAG->getDataLayout());
3118
9.58M
3119
9.58M
        // If the VT matches, then we will execute this case.
3120
9.58M
        if (CurNodeVT == CaseVT)
3121
3.45M
          break;
3122
6.12M
3123
6.12M
        // Otherwise, skip over this case.
3124
6.12M
        MatcherIndex += CaseSize;
3125
6.12M
      }
3126
4.10M
3127
4.10M
      // If no cases matched, bail out.
3128
4.10M
      if (CaseSize == 0) 
break645k
;
3129
3.45M
3130
3.45M
      // Otherwise, execute the case we found.
3131
3.45M
      LLVM_DEBUG(dbgs() << "  TypeSwitch[" << EVT(CurNodeVT).getEVTString()
3132
3.45M
                        << "] from " << SwitchStart << " to " << MatcherIndex
3133
3.45M
                        << '\n');
3134
3.45M
      continue;
3135
3.45M
    }
3136
4.75M
    case OPC_CheckChild0Type: case OPC_CheckChild1Type:
3137
4.75M
    case OPC_CheckChild2Type: case OPC_CheckChild3Type:
3138
4.75M
    case OPC_CheckChild4Type: case OPC_CheckChild5Type:
3139
4.75M
    case OPC_CheckChild6Type: case OPC_CheckChild7Type:
3140
4.75M
      if (!::CheckChildType(MatcherTable, MatcherIndex, N, TLI,
3141
4.75M
                            CurDAG->getDataLayout(),
3142
4.75M
                            Opcode - OPC_CheckChild0Type))
3143
3.64M
        break;
3144
1.11M
      continue;
3145
1.11M
    case OPC_CheckCondCode:
3146
4.29k
      if (!::CheckCondCode(MatcherTable, MatcherIndex, N)) 
break3.84k
;
3147
453
      continue;
3148
107k
    case OPC_CheckChild2CondCode:
3149
107k
      if (!::CheckChild2CondCode(MatcherTable, MatcherIndex, N)) 
break93.1k
;
3150
14.0k
      continue;
3151
14.0k
    case OPC_CheckValueType:
3152
2.05k
      if (!::CheckValueType(MatcherTable, MatcherIndex, N, TLI,
3153
2.05k
                            CurDAG->getDataLayout()))
3154
111
        break;
3155
1.94k
      continue;
3156
15.3k
    case OPC_CheckInteger:
3157
15.3k
      if (!::CheckInteger(MatcherTable, MatcherIndex, N)) 
break12.8k
;
3158
2.47k
      continue;
3159
1.24M
    case OPC_CheckChild0Integer: case OPC_CheckChild1Integer:
3160
1.24M
    case OPC_CheckChild2Integer: case OPC_CheckChild3Integer:
3161
1.24M
    case OPC_CheckChild4Integer:
3162
1.24M
      if (!::CheckChildInteger(MatcherTable, MatcherIndex, N,
3163
1.24M
                               Opcode-OPC_CheckChild0Integer)) 
break988k
;
3164
252k
      continue;
3165
1.15M
    case OPC_CheckAndImm:
3166
1.15M
      if (!::CheckAndImm(MatcherTable, MatcherIndex, N, *this)) 
break900k
;
3167
249k
      continue;
3168
249k
    case OPC_CheckOrImm:
3169
3.94k
      if (!::CheckOrImm(MatcherTable, MatcherIndex, N, *this)) 
break3.94k
;
3170
5
      continue;
3171
179k
    case OPC_CheckImmAllOnesV:
3172
179k
      if (!ISD::isBuildVectorAllOnes(N.getNode())) 
break158k
;
3173
20.5k
      continue;
3174
99.3k
    case OPC_CheckImmAllZerosV:
3175
99.3k
      if (!ISD::isBuildVectorAllZeros(N.getNode())) 
break70.5k
;
3176
28.8k
      continue;
3177
28.8k
3178
241k
    case OPC_CheckFoldableChainNode: {
3179
241k
      assert(NodeStack.size() != 1 && "No parent node");
3180
241k
      // Verify that all intermediate nodes between the root and this one have
3181
241k
      // a single use.
3182
241k
      bool HasMultipleUses = false;
3183
279k
      for (unsigned i = 1, e = NodeStack.size()-1; i != e; 
++i37.7k
)
3184
46.6k
        if (!NodeStack[i].getNode()->hasOneUse()) {
3185
8.95k
          HasMultipleUses = true;
3186
8.95k
          break;
3187
8.95k
        }
3188
241k
      if (HasMultipleUses) 
break8.95k
;
3189
232k
3190
232k
      // Check to see that the target thinks this is profitable to fold and that
3191
232k
      // we can fold it without inducing cycles in the graph.
3192
232k
      if (!IsProfitableToFold(N, NodeStack[NodeStack.size()-2].getNode(),
3193
232k
                              NodeToMatch) ||
3194
232k
          !IsLegalToFold(N, NodeStack[NodeStack.size()-2].getNode(),
3195
127k
                         NodeToMatch, OptLevel,
3196
127k
                         true/*We validate our own chains*/))
3197
107k
        break;
3198
125k
3199
125k
      continue;
3200
125k
    }
3201
2.48M
    case OPC_EmitInteger: {
3202
2.48M
      MVT::SimpleValueType VT =
3203
2.48M
        (MVT::SimpleValueType)MatcherTable[MatcherIndex++];
3204
2.48M
      int64_t Val = MatcherTable[MatcherIndex++];
3205
2.48M
      if (Val & 128)
3206
97.6k
        Val = GetVBR(Val, MatcherTable, MatcherIndex);
3207
2.48M
      RecordedNodes.push_back(std::pair<SDValue, SDNode*>(
3208
2.48M
                              CurDAG->getTargetConstant(Val, SDLoc(NodeToMatch),
3209
2.48M
                                                        VT), nullptr));
3210
2.48M
      continue;
3211
125k
    }
3212
809k
    case OPC_EmitRegister: {
3213
809k
      MVT::SimpleValueType VT =
3214
809k
        (MVT::SimpleValueType)MatcherTable[MatcherIndex++];
3215
809k
      unsigned RegNo = MatcherTable[MatcherIndex++];
3216
809k
      RecordedNodes.push_back(std::pair<SDValue, SDNode*>(
3217
809k
                              CurDAG->getRegister(RegNo, VT), nullptr));
3218
809k
      continue;
3219
125k
    }
3220
125k
    case OPC_EmitRegister2: {
3221
421
      // For targets w/ more than 256 register names, the register enum
3222
421
      // values are stored in two bytes in the matcher table (just like
3223
421
      // opcodes).
3224
421
      MVT::SimpleValueType VT =
3225
421
        (MVT::SimpleValueType)MatcherTable[MatcherIndex++];
3226
421
      unsigned RegNo = MatcherTable[MatcherIndex++];
3227
421
      RegNo |= MatcherTable[MatcherIndex++] << 8;
3228
421
      RecordedNodes.push_back(std::pair<SDValue, SDNode*>(
3229
421
                              CurDAG->getRegister(RegNo, VT), nullptr));
3230
421
      continue;
3231
125k
    }
3232
125k
3233
1.28M
    case OPC_EmitConvertToTarget:  {
3234
1.28M
      // Convert from IMM/FPIMM to target version.
3235
1.28M
      unsigned RecNo = MatcherTable[MatcherIndex++];
3236
1.28M
      assert(RecNo < RecordedNodes.size() && "Invalid EmitConvertToTarget");
3237
1.28M
      SDValue Imm = RecordedNodes[RecNo].first;
3238
1.28M
3239
1.28M
      if (Imm->getOpcode() == ISD::Constant) {
3240
1.22M
        const ConstantInt *Val=cast<ConstantSDNode>(Imm)->getConstantIntValue();
3241
1.22M
        Imm = CurDAG->getTargetConstant(*Val, SDLoc(NodeToMatch),
3242
1.22M
                                        Imm.getValueType());
3243
1.22M
      } else 
if (59.9k
Imm->getOpcode() == ISD::ConstantFP59.9k
) {
3244
3.40k
        const ConstantFP *Val=cast<ConstantFPSDNode>(Imm)->getConstantFPValue();
3245
3.40k
        Imm = CurDAG->getTargetConstantFP(*Val, SDLoc(NodeToMatch),
3246
3.40k
                                          Imm.getValueType());
3247
3.40k
      }
3248
1.28M
3249
1.28M
      RecordedNodes.push_back(std::make_pair(Imm, RecordedNodes[RecNo].second));
3250
1.28M
      continue;
3251
125k
    }
3252
125k
3253
4.32M
    case OPC_EmitMergeInputChains1_0:    // OPC_EmitMergeInputChains, 1, 0
3254
4.32M
    case OPC_EmitMergeInputChains1_1:    // OPC_EmitMergeInputChains, 1, 1
3255
4.32M
    case OPC_EmitMergeInputChains1_2: {  // OPC_EmitMergeInputChains, 1, 2
3256
4.32M
      // These are space-optimized forms of OPC_EmitMergeInputChains.
3257
4.32M
      assert(!InputChain.getNode() &&
3258
4.32M
             "EmitMergeInputChains should be the first chain producing node");
3259
4.32M
      assert(ChainNodesMatched.empty() &&
3260
4.32M
             "Should only have one EmitMergeInputChains per match");
3261
4.32M
3262
4.32M
      // Read all of the chained nodes.
3263
4.32M
      unsigned RecNo = Opcode - OPC_EmitMergeInputChains1_0;
3264
4.32M
      assert(RecNo < RecordedNodes.size() && "Invalid EmitMergeInputChains");
3265
4.32M
      ChainNodesMatched.push_back(RecordedNodes[RecNo].first.getNode());
3266
4.32M
3267
4.32M
      // FIXME: What if other value results of the node have uses not matched
3268
4.32M
      // by this pattern?
3269
4.32M
      if (ChainNodesMatched.back() != NodeToMatch &&
3270
4.32M
          
!RecordedNodes[RecNo].first.hasOneUse()83.3k
) {
3271
752
        ChainNodesMatched.clear();
3272
752
        break;
3273
752
      }
3274
4.32M
3275
4.32M
      // Merge the input chains if they are not intra-pattern references.
3276
4.32M
      InputChain = HandleMergeInputChains(ChainNodesMatched, CurDAG);
3277
4.32M
3278
4.32M
      if (!InputChain.getNode())
3279
0
        break;  // Failed to merge.
3280
4.32M
      continue;
3281
4.32M
    }
3282
4.32M
3283
4.32M
    case OPC_EmitMergeInputChains: {
3284
7.30k
      assert(!InputChain.getNode() &&
3285
7.30k
             "EmitMergeInputChains should be the first chain producing node");
3286
7.30k
      // This node gets a list of nodes we matched in the input that have
3287
7.30k
      // chains.  We want to token factor all of the input chains to these nodes
3288
7.30k
      // together.  However, if any of the input chains is actually one of the
3289
7.30k
      // nodes matched in this pattern, then we have an intra-match reference.
3290
7.30k
      // Ignore these because the newly token factored chain should not refer to
3291
7.30k
      // the old nodes.
3292
7.30k
      unsigned NumChains = MatcherTable[MatcherIndex++];
3293
7.30k
      assert(NumChains != 0 && "Can't TF zero chains");
3294
7.30k
3295
7.30k
      assert(ChainNodesMatched.empty() &&
3296
7.30k
             "Should only have one EmitMergeInputChains per match");
3297
7.30k
3298
7.30k
      // Read all of the chained nodes.
3299
21.5k
      for (unsigned i = 0; i != NumChains; 
++i14.2k
) {
3300
14.2k
        unsigned RecNo = MatcherTable[MatcherIndex++];
3301
14.2k
        assert(RecNo < RecordedNodes.size() && "Invalid EmitMergeInputChains");
3302
14.2k
        ChainNodesMatched.push_back(RecordedNodes[RecNo].first.getNode());
3303
14.2k
3304
14.2k
        // FIXME: What if other value results of the node have uses not matched
3305
14.2k
        // by this pattern?
3306
14.2k
        if (ChainNodesMatched.back() != NodeToMatch &&
3307
14.2k
            
!RecordedNodes[RecNo].first.hasOneUse()7.34k
) {
3308
23
          ChainNodesMatched.clear();
3309
23
          break;
3310
23
        }
3311
14.2k
      }
3312
7.30k
3313
7.30k
      // If the inner loop broke out, the match fails.
3314
7.30k
      if (ChainNodesMatched.empty())
3315
23
        break;
3316
7.28k
3317
7.28k
      // Merge the input chains if they are not intra-pattern references.
3318
7.28k
      InputChain = HandleMergeInputChains(ChainNodesMatched, CurDAG);
3319
7.28k
3320
7.28k
      if (!InputChain.getNode())
3321
50
        break;  // Failed to merge.
3322
7.23k
3323
7.23k
      continue;
3324
7.23k
    }
3325
7.23k
3326
364k
    case OPC_EmitCopyToReg:
3327
364k
    case OPC_EmitCopyToReg2: {
3328
364k
      unsigned RecNo = MatcherTable[MatcherIndex++];
3329
364k
      assert(RecNo < RecordedNodes.size() && "Invalid EmitCopyToReg");
3330
364k
      unsigned DestPhysReg = MatcherTable[MatcherIndex++];
3331
364k
      if (Opcode == OPC_EmitCopyToReg2)
3332
0
        DestPhysReg |= MatcherTable[MatcherIndex++] << 8;
3333
364k
3334
364k
      if (!InputChain.getNode())
3335
65.5k
        InputChain = CurDAG->getEntryNode();
3336
364k
3337
364k
      InputChain = CurDAG->getCopyToReg(InputChain, SDLoc(NodeToMatch),
3338
364k
                                        DestPhysReg, RecordedNodes[RecNo].first,
3339
364k
                                        InputGlue);
3340
364k
3341
364k
      InputGlue = InputChain.getValue(1);
3342
364k
      continue;
3343
364k
    }
3344
364k
3345
364k
    case OPC_EmitNodeXForm: {
3346
267k
      unsigned XFormNo = MatcherTable[MatcherIndex++];
3347
267k
      unsigned RecNo = MatcherTable[MatcherIndex++];
3348
267k
      assert(RecNo < RecordedNodes.size() && "Invalid EmitNodeXForm");
3349
267k
      SDValue Res = RunSDNodeXForm(RecordedNodes[RecNo].first, XFormNo);
3350
267k
      RecordedNodes.push_back(std::pair<SDValue,SDNode*>(Res, nullptr));
3351
267k
      continue;
3352
364k
    }
3353
364k
    case OPC_Coverage: {
3354
0
      // This is emitted right before MorphNode/EmitNode.
3355
0
      // So it should be safe to assume that this node has been selected
3356
0
      unsigned index = MatcherTable[MatcherIndex++];
3357
0
      index |= (MatcherTable[MatcherIndex++] << 8);
3358
0
      dbgs() << "COVERED: " << getPatternForIndex(index) << "\n";
3359
0
      dbgs() << "INCLUDED: " << getIncludePathForIndex(index) << "\n";
3360
0
      continue;
3361
364k
    }
3362
364k
3363
7.83M
    case OPC_EmitNode:     case OPC_MorphNodeTo:
3364
7.83M
    case OPC_EmitNode0:    case OPC_EmitNode1:    case OPC_EmitNode2:
3365
7.83M
    case OPC_MorphNodeTo0: case OPC_MorphNodeTo1: case OPC_MorphNodeTo2: {
3366
7.83M
      uint16_t TargetOpc = MatcherTable[MatcherIndex++];
3367
7.83M
      TargetOpc |= (unsigned short)MatcherTable[MatcherIndex++] << 8;
3368
7.83M
      unsigned EmitNodeInfo = MatcherTable[MatcherIndex++];
3369
7.83M
      // Get the result VT list.
3370
7.83M
      unsigned NumVTs;
3371
7.83M
      // If this is one of the compressed forms, get the number of VTs based
3372
7.83M
      // on the Opcode. Otherwise read the next byte from the table.
3373
7.83M
      if (Opcode >= OPC_MorphNodeTo0 && 
Opcode <= OPC_MorphNodeTo27.41M
)
3374
7.41M
        NumVTs = Opcode - OPC_MorphNodeTo0;
3375
418k
      else if (Opcode >= OPC_EmitNode0 && 
Opcode <= OPC_EmitNode2418k
)
3376
418k
        NumVTs = Opcode - OPC_EmitNode0;
3377
83
      else
3378
83
        NumVTs = MatcherTable[MatcherIndex++];
3379
7.83M
      SmallVector<EVT, 4> VTs;
3380
13.8M
      for (unsigned i = 0; i != NumVTs; 
++i6.03M
) {
3381
6.03M
        MVT::SimpleValueType VT =
3382
6.03M
          (MVT::SimpleValueType)MatcherTable[MatcherIndex++];
3383
6.03M
        if (VT == MVT::iPTR)
3384
759
          VT = TLI->getPointerTy(CurDAG->getDataLayout()).SimpleTy;
3385
6.03M
        VTs.push_back(VT);
3386
6.03M
      }
3387
7.83M
3388
7.83M
      if (EmitNodeInfo & OPFL_Chain)
3389
4.36M
        VTs.push_back(MVT::Other);
3390
7.83M
      if (EmitNodeInfo & OPFL_GlueOutput)
3391
1.24M
        VTs.push_back(MVT::Glue);
3392
7.83M
3393
7.83M
      // This is hot code, so optimize the two most common cases of 1 and 2
3394
7.83M
      // results.
3395
7.83M
      SDVTList VTList;
3396
7.83M
      if (VTs.size() == 1)
3397
5.06M
        VTList = CurDAG->getVTList(VTs[0]);
3398
2.76M
      else if (VTs.size() == 2)
3399
1.71M
        VTList = CurDAG->getVTList(VTs[0], VTs[1]);
3400
1.05M
      else
3401
1.05M
        VTList = CurDAG->getVTList(VTs);
3402
7.83M
3403
7.83M
      // Get the operand list.
3404
7.83M
      unsigned NumOps = MatcherTable[MatcherIndex++];
3405
7.83M
      SmallVector<SDValue, 8> Ops;
3406
26.9M
      for (unsigned i = 0; i != NumOps; 
++i19.0M
) {
3407
19.0M
        unsigned RecNo = MatcherTable[MatcherIndex++];
3408
19.0M
        if (RecNo & 128)
3409
7.06k
          RecNo = GetVBR(RecNo, MatcherTable, MatcherIndex);
3410
19.0M
3411
19.0M
        assert(RecNo < RecordedNodes.size() && "Invalid EmitNode");
3412
19.0M
        Ops.push_back(RecordedNodes[RecNo].first);
3413
19.0M
      }
3414
7.83M
3415
7.83M
      // If there are variadic operands to add, handle them now.
3416
7.83M
      if (EmitNodeInfo & OPFL_VariadicInfo) {
3417
696k
        // Determine the start index to copy from.
3418
696k
        unsigned FirstOpToCopy = getNumFixedFromVariadicInfo(EmitNodeInfo);
3419
696k
        FirstOpToCopy += (EmitNodeInfo & OPFL_Chain) ? 
1690k
:
06.52k
;
3420
696k
        assert(NodeToMatch->getNumOperands() >= FirstOpToCopy &&
3421
696k
               "Invalid variadic node");
3422
696k
        // Copy all of the variadic operands, not including a potential glue
3423
696k
        // input.
3424
696k
        for (unsigned i = FirstOpToCopy, e = NodeToMatch->getNumOperands();
3425
2.32M
             i != e; 
++i1.62M
) {
3426
2.16M
          SDValue V = NodeToMatch->getOperand(i);
3427
2.16M
          if (V.getValueType() == MVT::Glue) 
break545k
;
3428
1.62M
          Ops.push_back(V);
3429
1.62M
        }
3430
696k
      }
3431
7.83M
3432
7.83M
      // If this has chain/glue inputs, add them.
3433
7.83M
      if (EmitNodeInfo & OPFL_Chain)
3434
4.36M
        Ops.push_back(InputChain);
3435
7.83M
      if ((EmitNodeInfo & OPFL_GlueInput) && 
InputGlue.getNode() != nullptr1.49M
)
3436
1.32M
        Ops.push_back(InputGlue);
3437
7.83M
3438
7.83M
      // Create the node.
3439
7.83M
      MachineSDNode *Res = nullptr;
3440
7.83M
      bool IsMorphNodeTo = Opcode == OPC_MorphNodeTo ||
3441
7.83M
                     
(7.83M
Opcode >= OPC_MorphNodeTo07.83M
&&
Opcode <= OPC_MorphNodeTo27.41M
);
3442
7.83M
      if (!IsMorphNodeTo) {
3443
418k
        // If this is a normal EmitNode command, just create the new node and
3444
418k
        // add the results to the RecordedNodes list.
3445
418k
        Res = CurDAG->getMachineNode(TargetOpc, SDLoc(NodeToMatch),
3446
418k
                                     VTList, Ops);
3447
418k
3448
418k
        // Add all the non-glue/non-chain results to the RecordedNodes list.
3449
873k
        for (unsigned i = 0, e = VTs.size(); i != e; 
++i455k
) {
3450
489k
          if (VTs[i] == MVT::Other || 
VTs[i] == MVT::Glue455k
)
break34.0k
;
3451
455k
          RecordedNodes.push_back(std::pair<SDValue,SDNode*>(SDValue(Res, i),
3452
455k
                                                             nullptr));
3453
455k
        }
3454
7.41M
      } else {
3455
7.41M
        assert(NodeToMatch->getOpcode() != ISD::DELETED_NODE &&
3456
7.41M
               "NodeToMatch was removed partway through selection");
3457
7.41M
        SelectionDAG::DAGNodeDeletedListener NDL(*CurDAG, [&](SDNode *N,
3458
7.41M
                                                              SDNode *E) {
3459
4.40M
          CurDAG->salvageDebugInfo(*N);
3460
4.40M
          auto &Chain = ChainNodesMatched;
3461
4.40M
          assert((!E || !is_contained(Chain, N)) &&
3462
4.40M
                 "Chain node replaced during MorphNode");
3463
4.40M
          Chain.erase(std::remove(Chain.begin(), Chain.end(), N), Chain.end());
3464
4.40M
        });
3465
7.41M
        Res = cast<MachineSDNode>(MorphNode(NodeToMatch, TargetOpc, VTList,
3466
7.41M
                                            Ops, EmitNodeInfo));
3467
7.41M
      }
3468
7.83M
3469
7.83M
      // If the node had chain/glue results, update our notion of the current
3470
7.83M
      // chain and glue.
3471
7.83M
      if (EmitNodeInfo & OPFL_GlueOutput) {
3472
1.24M
        InputGlue = SDValue(Res, VTs.size()-1);
3473
1.24M
        if (EmitNodeInfo & OPFL_Chain)
3474
1.19M
          InputChain = SDValue(Res, VTs.size()-2);
3475
6.58M
      } else if (EmitNodeInfo & OPFL_Chain)
3476
3.17M
        InputChain = SDValue(Res, VTs.size()-1);
3477
7.83M
3478
7.83M
      // If the OPFL_MemRefs glue is set on this node, slap all of the
3479
7.83M
      // accumulated memrefs onto it.
3480
7.83M
      //
3481
7.83M
      // FIXME: This is vastly incorrect for patterns with multiple outputs
3482
7.83M
      // instructions that access memory and for ComplexPatterns that match
3483
7.83M
      // loads.
3484
7.83M
      if (EmitNodeInfo & OPFL_MemRefs) {
3485
1.56M
        // Only attach load or store memory operands if the generated
3486
1.56M
        // instruction may load or store.
3487
1.56M
        const MCInstrDesc &MCID = TII->get(TargetOpc);
3488
1.56M
        bool mayLoad = MCID.mayLoad();
3489
1.56M
        bool mayStore = MCID.mayStore();
3490
1.56M
3491
1.56M
        // We expect to have relatively few of these so just filter them into a
3492
1.56M
        // temporary buffer so that we can easily add them to the instruction.
3493
1.56M
        SmallVector<MachineMemOperand *, 4> FilteredMemRefs;
3494
1.56M
        for (MachineMemOperand *MMO : MatchedMemRefs) {
3495
1.56M
          if (MMO->isLoad()) {
3496
835k
            if (mayLoad)
3497
835k
              FilteredMemRefs.push_back(MMO);
3498
835k
          } else 
if (732k
MMO->isStore()732k
) {
3499
732k
            if (mayStore)
3500
732k
              FilteredMemRefs.push_back(MMO);
3501
732k
          } else {
3502
0
            FilteredMemRefs.push_back(MMO);
3503
0
          }
3504
1.56M
        }
3505
1.56M
3506
1.56M
        CurDAG->setNodeMemRefs(Res, FilteredMemRefs);
3507
1.56M
      }
3508
7.83M
3509
7.83M
      LLVM_DEBUG(if (!MatchedMemRefs.empty() && Res->memoperands_empty()) dbgs()
3510
7.83M
                     << "  Dropping mem operands\n";
3511
7.83M
                 dbgs() << "  " << (IsMorphNodeTo ? "Morphed" : "Created")
3512
7.83M
                        << " node: ";
3513
7.83M
                 Res->dump(CurDAG););
3514
7.83M
3515
7.83M
      // If this was a MorphNodeTo then we're completely done!
3516
7.83M
      if (IsMorphNodeTo) {
3517
7.41M
        // Update chain uses.
3518
7.41M
        UpdateChains(Res, InputChain, ChainNodesMatched, true);
3519
7.41M
        return;
3520
7.41M
      }
3521
418k
      continue;
3522
418k
    }
3523
418k
3524
418k
    case OPC_CompleteMatch: {
3525
129k
      // The match has been completed, and any new nodes (if any) have been
3526
129k
      // created.  Patch up references to the matched dag to use the newly
3527
129k
      // created nodes.
3528
129k
      unsigned NumResults = MatcherTable[MatcherIndex++];
3529
129k
3530
258k
      for (unsigned i = 0; i != NumResults; 
++i129k
) {
3531
129k
        unsigned ResSlot = MatcherTable[MatcherIndex++];
3532
129k
        if (ResSlot & 128)
3533
0
          ResSlot = GetVBR(ResSlot, MatcherTable, MatcherIndex);
3534
129k
3535
129k
        assert(ResSlot < RecordedNodes.size() && "Invalid CompleteMatch");
3536
129k
        SDValue Res = RecordedNodes[ResSlot].first;
3537
129k
3538
129k
        assert(i < NodeToMatch->getNumValues() &&
3539
129k
               NodeToMatch->getValueType(i) != MVT::Other &&
3540
129k
               NodeToMatch->getValueType(i) != MVT::Glue &&
3541
129k
               "Invalid number of results to complete!");
3542
129k
        assert((NodeToMatch->getValueType(i) == Res.getValueType() ||
3543
129k
                NodeToMatch->getValueType(i) == MVT::iPTR ||
3544
129k
                Res.getValueType() == MVT::iPTR ||
3545
129k
                NodeToMatch->getValueType(i).getSizeInBits() ==
3546
129k
                    Res.getValueSizeInBits()) &&
3547
129k
               "invalid replacement");
3548
129k
        ReplaceUses(SDValue(NodeToMatch, i), Res);
3549
129k
      }
3550
129k
3551
129k
      // Update chain uses.
3552
129k
      UpdateChains(NodeToMatch, InputChain, ChainNodesMatched, false);
3553
129k
3554
129k
      // If the root node defines glue, we need to update it to the glue result.
3555
129k
      // TODO: This never happens in our tests and I think it can be removed /
3556
129k
      // replaced with an assert, but if we do it this the way the change is
3557
129k
      // NFC.
3558
129k
      if (NodeToMatch->getValueType(NodeToMatch->getNumValues() - 1) ==
3559
129k
              MVT::Glue &&
3560
129k
          
InputGlue.getNode()0
)
3561
0
        ReplaceUses(SDValue(NodeToMatch, NodeToMatch->getNumValues() - 1),
3562
0
                    InputGlue);
3563
129k
3564
129k
      assert(NodeToMatch->use_empty() &&
3565
129k
             "Didn't replace all uses of the node?");
3566
129k
      CurDAG->RemoveDeadNode(NodeToMatch);
3567
129k
3568
129k
      return;
3569
34.6M
    }
3570
34.6M
    }
3571
34.6M
3572
34.6M
    // If the code reached this point, then the match failed.  See if there is
3573
34.6M
    // another child to try in the current 'Scope', otherwise pop it until we
3574
34.6M
    // find a case to check.
3575
34.6M
    LLVM_DEBUG(dbgs() << "  Match failed at index " << CurrentOpcodeIndex
3576
34.6M
                      << "\n");
3577
34.6M
    ++NumDAGIselRetries;
3578
38.2M
    while (true) {
3579
38.2M
      if (MatchScopes.empty()) {
3580
26
        CannotYetSelect(NodeToMatch);
3581
26
        return;
3582
26
      }
3583
38.2M
3584
38.2M
      // Restore the interpreter state back to the point where the scope was
3585
38.2M
      // formed.
3586
38.2M
      MatchScope &LastScope = MatchScopes.back();
3587
38.2M
      RecordedNodes.resize(LastScope.NumRecordedNodes);
3588
38.2M
      NodeStack.clear();
3589
38.2M
      NodeStack.append(LastScope.NodeStack.begin(), LastScope.NodeStack.end());
3590
38.2M
      N = NodeStack.back();
3591
38.2M
3592
38.2M
      if (LastScope.NumMatchedMemRefs != MatchedMemRefs.size())
3593
172k
        MatchedMemRefs.resize(LastScope.NumMatchedMemRefs);
3594
38.2M
      MatcherIndex = LastScope.FailIndex;
3595
38.2M
3596
38.2M
      LLVM_DEBUG(dbgs() << "  Continuing at " << MatcherIndex << "\n");
3597
38.2M
3598
38.2M
      InputChain = LastScope.InputChain;
3599
38.2M
      InputGlue = LastScope.InputGlue;
3600
38.2M
      if (!LastScope.HasChainNodesMatched)
3601
38.2M
        ChainNodesMatched.clear();
3602
38.2M
3603
38.2M
      // Check to see what the offset is at the new MatcherIndex.  If it is zero
3604
38.2M
      // we have reached the end of this scope, otherwise we have another child
3605
38.2M
      // in the current scope to try.
3606
38.2M
      unsigned NumToSkip = MatcherTable[MatcherIndex++];
3607
38.2M
      if (NumToSkip & 128)
3608
9.04M
        NumToSkip = GetVBR(NumToSkip, MatcherTable, MatcherIndex);
3609
38.2M
3610
38.2M
      // If we have another child in this scope to match, update FailIndex and
3611
38.2M
      // try it.
3612
38.2M
      if (NumToSkip != 0) {
3613
34.6M
        LastScope.FailIndex = MatcherIndex+NumToSkip;
3614
34.6M
        break;
3615
34.6M
      }
3616
3.58M
3617
3.58M
      // End of this scope, pop it and try the next child in the containing
3618
3.58M
      // scope.
3619
3.58M
      MatchScopes.pop_back();
3620
3.58M
    }
3621
34.6M
  }
3622
7.54M
}
3623
3624
335
bool SelectionDAGISel::isOrEquivalentToAdd(const SDNode *N) const {
3625
335
  assert(N->getOpcode() == ISD::OR && "Unexpected opcode");
3626
335
  auto *C = dyn_cast<ConstantSDNode>(N->getOperand(1));
3627
335
  if (!C)
3628
0
    return false;
3629
335
3630
335
  // Detect when "or" is used to add an offset to a stack object.
3631
335
  if (auto *FN = dyn_cast<FrameIndexSDNode>(N->getOperand(0))) {
3632
285
    MachineFrameInfo &MFI = MF->getFrameInfo();
3633
285
    unsigned A = MFI.getObjectAlignment(FN->getIndex());
3634
285
    assert(isPowerOf2_32(A) && "Unexpected alignment");
3635
285
    int32_t Off = C->getSExtValue();
3636
285
    // If the alleged offset fits in the zero bits guaranteed by
3637
285
    // the alignment, then this or is really an add.
3638
285
    return (Off >= 0) && (((A - 1) & Off) == unsigned(Off));
3639
285
  }
3640
50
  return false;
3641
50
}
3642
3643
26
void SelectionDAGISel::CannotYetSelect(SDNode *N) {
3644
26
  std::string msg;
3645
26
  raw_string_ostream Msg(msg);
3646
26
  Msg << "Cannot select: ";
3647
26
3648
26
  if (N->getOpcode() != ISD::INTRINSIC_W_CHAIN &&
3649
26
      
N->getOpcode() != ISD::INTRINSIC_WO_CHAIN25
&&
3650
26
      
N->getOpcode() != ISD::INTRINSIC_VOID14
) {
3651
8
    N->printrFull(Msg, CurDAG);
3652
8
    Msg << "\nIn function: " << MF->getName();
3653
18
  } else {
3654
18
    bool HasInputChain = N->getOperand(0).getValueType() == MVT::Other;
3655
18
    unsigned iid =
3656
18
      cast<ConstantSDNode>(N->getOperand(HasInputChain))->getZExtValue();
3657
18
    if (iid < Intrinsic::num_intrinsics)
3658
18
      Msg << "intrinsic %" << Intrinsic::getName((Intrinsic::ID)iid, None);
3659
0
    else if (const TargetIntrinsicInfo *TII = TM.getIntrinsicInfo())
3660
0
      Msg << "target intrinsic %" << TII->getName(iid);
3661
0
    else
3662
0
      Msg << "unknown intrinsic #" << iid;
3663
18
  }
3664
26
  report_fatal_error(Msg.str());
3665
26
}
3666
3667
char SelectionDAGISel::ID = 0;