Bug Summary

File:lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp
Warning:line 1563, column 9
Called C++ object pointer is null

Annotated Source Code

Press '?' to see keyboard shortcuts

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