Bug Summary

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

Annotated Source Code

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