1//===- SelectionDAGBuilder.cpp - Selection-DAG building -------------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// This implements routines for translating from LLVM IR into SelectionDAG IR.
10//
11//===----------------------------------------------------------------------===//
12
13#include "SelectionDAGBuilder.h"
14#include "SDNodeDbgValue.h"
15#include "llvm/ADT/APFloat.h"
16#include "llvm/ADT/APInt.h"
17#include "llvm/ADT/BitVector.h"
18#include "llvm/ADT/None.h"
19#include "llvm/ADT/Optional.h"
20#include "llvm/ADT/STLExtras.h"
21#include "llvm/ADT/SmallPtrSet.h"
22#include "llvm/ADT/SmallSet.h"
23#include "llvm/ADT/StringRef.h"
24#include "llvm/ADT/Triple.h"
25#include "llvm/ADT/Twine.h"
26#include "llvm/Analysis/AliasAnalysis.h"
27#include "llvm/Analysis/BlockFrequencyInfo.h"
28#include "llvm/Analysis/BranchProbabilityInfo.h"
29#include "llvm/Analysis/ConstantFolding.h"
30#include "llvm/Analysis/EHPersonalities.h"
31#include "llvm/Analysis/Loads.h"
32#include "llvm/Analysis/MemoryLocation.h"
33#include "llvm/Analysis/ProfileSummaryInfo.h"
34#include "llvm/Analysis/TargetLibraryInfo.h"
35#include "llvm/Analysis/ValueTracking.h"
36#include "llvm/Analysis/VectorUtils.h"
37#include "llvm/CodeGen/Analysis.h"
38#include "llvm/CodeGen/FunctionLoweringInfo.h"
39#include "llvm/CodeGen/GCMetadata.h"
40#include "llvm/CodeGen/MachineBasicBlock.h"
41#include "llvm/CodeGen/MachineFrameInfo.h"
42#include "llvm/CodeGen/MachineFunction.h"
43#include "llvm/CodeGen/MachineInstr.h"
44#include "llvm/CodeGen/MachineInstrBuilder.h"
45#include "llvm/CodeGen/MachineJumpTableInfo.h"
46#include "llvm/CodeGen/MachineMemOperand.h"
47#include "llvm/CodeGen/MachineModuleInfo.h"
48#include "llvm/CodeGen/MachineOperand.h"
49#include "llvm/CodeGen/MachineRegisterInfo.h"
50#include "llvm/CodeGen/RuntimeLibcalls.h"
51#include "llvm/CodeGen/SelectionDAG.h"
52#include "llvm/CodeGen/SelectionDAGTargetInfo.h"
53#include "llvm/CodeGen/StackMaps.h"
54#include "llvm/CodeGen/SwiftErrorValueTracking.h"
55#include "llvm/CodeGen/TargetFrameLowering.h"
56#include "llvm/CodeGen/TargetInstrInfo.h"
57#include "llvm/CodeGen/TargetOpcodes.h"
58#include "llvm/CodeGen/TargetRegisterInfo.h"
59#include "llvm/CodeGen/TargetSubtargetInfo.h"
60#include "llvm/CodeGen/WinEHFuncInfo.h"
61#include "llvm/IR/Argument.h"
62#include "llvm/IR/Attributes.h"
63#include "llvm/IR/BasicBlock.h"
64#include "llvm/IR/CFG.h"
65#include "llvm/IR/CallingConv.h"
66#include "llvm/IR/Constant.h"
67#include "llvm/IR/ConstantRange.h"
68#include "llvm/IR/Constants.h"
69#include "llvm/IR/DataLayout.h"
70#include "llvm/IR/DebugInfoMetadata.h"
71#include "llvm/IR/DerivedTypes.h"
72#include "llvm/IR/Function.h"
73#include "llvm/IR/GetElementPtrTypeIterator.h"
74#include "llvm/IR/InlineAsm.h"
75#include "llvm/IR/InstrTypes.h"
76#include "llvm/IR/Instructions.h"
77#include "llvm/IR/IntrinsicInst.h"
78#include "llvm/IR/Intrinsics.h"
79#include "llvm/IR/IntrinsicsAArch64.h"
80#include "llvm/IR/IntrinsicsWebAssembly.h"
81#include "llvm/IR/LLVMContext.h"
82#include "llvm/IR/Metadata.h"
83#include "llvm/IR/Module.h"
84#include "llvm/IR/Operator.h"
85#include "llvm/IR/PatternMatch.h"
86#include "llvm/IR/Statepoint.h"
87#include "llvm/IR/Type.h"
88#include "llvm/IR/User.h"
89#include "llvm/IR/Value.h"
90#include "llvm/MC/MCContext.h"
91#include "llvm/MC/MCSymbol.h"
92#include "llvm/Support/AtomicOrdering.h"
93#include "llvm/Support/Casting.h"
94#include "llvm/Support/CommandLine.h"
95#include "llvm/Support/Compiler.h"
96#include "llvm/Support/Debug.h"
97#include "llvm/Support/MathExtras.h"
98#include "llvm/Support/raw_ostream.h"
99#include "llvm/Target/TargetIntrinsicInfo.h"
100#include "llvm/Target/TargetMachine.h"
101#include "llvm/Target/TargetOptions.h"
102#include "llvm/Transforms/Utils/Local.h"
103#include <cstddef>
104#include <cstring>
105#include <iterator>
106#include <limits>
107#include <numeric>
108#include <tuple>
109
110using namespace llvm;
111using namespace PatternMatch;
112using namespace SwitchCG;
113
114#define DEBUG_TYPE "isel"
115
116/// LimitFloatPrecision - Generate low-precision inline sequences for
117/// some float libcalls (6, 8 or 12 bits).
118static unsigned LimitFloatPrecision;
119
120static cl::opt<bool>
121 InsertAssertAlign("insert-assert-align", cl::init(true),
122 cl::desc("Insert the experimental `assertalign` node."),
123 cl::ReallyHidden);
124
125static cl::opt<unsigned, true>
126 LimitFPPrecision("limit-float-precision",
127 cl::desc("Generate low-precision inline sequences "
128 "for some float libcalls"),
129 cl::location(LimitFloatPrecision), cl::Hidden,
130 cl::init(0));
131
132static cl::opt<unsigned> SwitchPeelThreshold(
133 "switch-peel-threshold", cl::Hidden, cl::init(66),
134 cl::desc("Set the case probability threshold for peeling the case from a "
135 "switch statement. A value greater than 100 will void this "
136 "optimization"));
137
138// Limit the width of DAG chains. This is important in general to prevent
139// DAG-based analysis from blowing up. For example, alias analysis and
140// load clustering may not complete in reasonable time. It is difficult to
141// recognize and avoid this situation within each individual analysis, and
142// future analyses are likely to have the same behavior. Limiting DAG width is
143// the safe approach and will be especially important with global DAGs.
144//
145// MaxParallelChains default is arbitrarily high to avoid affecting
146// optimization, but could be lowered to improve compile time. Any ld-ld-st-st
147// sequence over this should have been converted to llvm.memcpy by the
148// frontend. It is easy to induce this behavior with .ll code such as:
149// %buffer = alloca [4096 x i8]
150// %data = load [4096 x i8]* %argPtr
151// store [4096 x i8] %data, [4096 x i8]* %buffer
152static const unsigned MaxParallelChains = 64;
153
154static SDValue getCopyFromPartsVector(SelectionDAG &DAG, const SDLoc &DL,
155 const SDValue *Parts, unsigned NumParts,
156 MVT PartVT, EVT ValueVT, const Value *V,
157 Optional<CallingConv::ID> CC);
158
159/// getCopyFromParts - Create a value that contains the specified legal parts
160/// combined into the value they represent. If the parts combine to a type
161/// larger than ValueVT then AssertOp can be used to specify whether the extra
162/// bits are known to be zero (ISD::AssertZext) or sign extended from ValueVT
163/// (ISD::AssertSext).
164static SDValue getCopyFromParts(SelectionDAG &DAG, const SDLoc &DL,
165 const SDValue *Parts, unsigned NumParts,
166 MVT PartVT, EVT ValueVT, const Value *V,
167 Optional<CallingConv::ID> CC = None,
168 Optional<ISD::NodeType> AssertOp = None) {
169 // Let the target assemble the parts if it wants to
170 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
171 if (SDValue Val = TLI.joinRegisterPartsIntoValue(DAG, DL, Parts, NumParts,
172 PartVT, ValueVT, CC))
173 return Val;
174
175 if (ValueVT.isVector())
176 return getCopyFromPartsVector(DAG, DL, Parts, NumParts, PartVT, ValueVT, V,
177 CC);
178
179 assert(NumParts > 0 && "No parts to assemble!");
180 SDValue Val = Parts[0];
181
182 if (NumParts > 1) {
183 // Assemble the value from multiple parts.
184 if (ValueVT.isInteger()) {
185 unsigned PartBits = PartVT.getSizeInBits();
186 unsigned ValueBits = ValueVT.getSizeInBits();
187
188 // Assemble the power of 2 part.
189 unsigned RoundParts =
190 (NumParts & (NumParts - 1)) ? 1 << Log2_32(NumParts) : NumParts;
191 unsigned RoundBits = PartBits * RoundParts;
192 EVT RoundVT = RoundBits == ValueBits ?
193 ValueVT : EVT::getIntegerVT(*DAG.getContext(), RoundBits);
194 SDValue Lo, Hi;
195
196 EVT HalfVT = EVT::getIntegerVT(*DAG.getContext(), RoundBits/2);
197
198 if (RoundParts > 2) {
199 Lo = getCopyFromParts(DAG, DL, Parts, RoundParts / 2,
200 PartVT, HalfVT, V);
201 Hi = getCopyFromParts(DAG, DL, Parts + RoundParts / 2,
202 RoundParts / 2, PartVT, HalfVT, V);
203 } else {
204 Lo = DAG.getNode(ISD::BITCAST, DL, HalfVT, Parts[0]);
205 Hi = DAG.getNode(ISD::BITCAST, DL, HalfVT, Parts[1]);
206 }
207
208 if (DAG.getDataLayout().isBigEndian())
209 std::swap(Lo, Hi);
210
211 Val = DAG.getNode(ISD::BUILD_PAIR, DL, RoundVT, Lo, Hi);
212
213 if (RoundParts < NumParts) {
214 // Assemble the trailing non-power-of-2 part.
215 unsigned OddParts = NumParts - RoundParts;
216 EVT OddVT = EVT::getIntegerVT(*DAG.getContext(), OddParts * PartBits);
217 Hi = getCopyFromParts(DAG, DL, Parts + RoundParts, OddParts, PartVT,
218 OddVT, V, CC);
219
220 // Combine the round and odd parts.
221 Lo = Val;
222 if (DAG.getDataLayout().isBigEndian())
223 std::swap(Lo, Hi);
224 EVT TotalVT = EVT::getIntegerVT(*DAG.getContext(), NumParts * PartBits);
225 Hi = DAG.getNode(ISD::ANY_EXTEND, DL, TotalVT, Hi);
226 Hi =
227 DAG.getNode(ISD::SHL, DL, TotalVT, Hi,
228 DAG.getConstant(Lo.getValueSizeInBits(), DL,
229 TLI.getPointerTy(DAG.getDataLayout())));
230 Lo = DAG.getNode(ISD::ZERO_EXTEND, DL, TotalVT, Lo);
231 Val = DAG.getNode(ISD::OR, DL, TotalVT, Lo, Hi);
232 }
233 } else if (PartVT.isFloatingPoint()) {
234 // FP split into multiple FP parts (for ppcf128)
235 assert(ValueVT == EVT(MVT::ppcf128) && PartVT == MVT::f64 &&
236 "Unexpected split");
237 SDValue Lo, Hi;
238 Lo = DAG.getNode(ISD::BITCAST, DL, EVT(MVT::f64), Parts[0]);
239 Hi = DAG.getNode(ISD::BITCAST, DL, EVT(MVT::f64), Parts[1]);
240 if (TLI.hasBigEndianPartOrdering(ValueVT, DAG.getDataLayout()))
241 std::swap(Lo, Hi);
242 Val = DAG.getNode(ISD::BUILD_PAIR, DL, ValueVT, Lo, Hi);
243 } else {
244 // FP split into integer parts (soft fp)
245 assert(ValueVT.isFloatingPoint() && PartVT.isInteger() &&
246 !PartVT.isVector() && "Unexpected split");
247 EVT IntVT = EVT::getIntegerVT(*DAG.getContext(), ValueVT.getSizeInBits());
248 Val = getCopyFromParts(DAG, DL, Parts, NumParts, PartVT, IntVT, V, CC);
249 }
250 }
251
252 // There is now one part, held in Val. Correct it to match ValueVT.
253 // PartEVT is the type of the register class that holds the value.
254 // ValueVT is the type of the inline asm operation.
255 EVT PartEVT = Val.getValueType();
256
257 if (PartEVT == ValueVT)
258 return Val;
259
260 if (PartEVT.isInteger() && ValueVT.isFloatingPoint() &&
261 ValueVT.bitsLT(PartEVT)) {
262 // For an FP value in an integer part, we need to truncate to the right
263 // width first.
264 PartEVT = EVT::getIntegerVT(*DAG.getContext(), ValueVT.getSizeInBits());
265 Val = DAG.getNode(ISD::TRUNCATE, DL, PartEVT, Val);
266 }
267
268 // Handle types that have the same size.
269 if (PartEVT.getSizeInBits() == ValueVT.getSizeInBits())
270 return DAG.getNode(ISD::BITCAST, DL, ValueVT, Val);
271
272 // Handle types with different sizes.
273 if (PartEVT.isInteger() && ValueVT.isInteger()) {
274 if (ValueVT.bitsLT(PartEVT)) {
275 // For a truncate, see if we have any information to
276 // indicate whether the truncated bits will always be
277 // zero or sign-extension.
278 if (AssertOp.hasValue())
279 Val = DAG.getNode(*AssertOp, DL, PartEVT, Val,
280 DAG.getValueType(ValueVT));
281 return DAG.getNode(ISD::TRUNCATE, DL, ValueVT, Val);
282 }
283 return DAG.getNode(ISD::ANY_EXTEND, DL, ValueVT, Val);
284 }
285
286 if (PartEVT.isFloatingPoint() && ValueVT.isFloatingPoint()) {
287 // FP_ROUND's are always exact here.
288 if (ValueVT.bitsLT(Val.getValueType()))
289 return DAG.getNode(
290 ISD::FP_ROUND, DL, ValueVT, Val,
291 DAG.getTargetConstant(1, DL, TLI.getPointerTy(DAG.getDataLayout())));
292
293 return DAG.getNode(ISD::FP_EXTEND, DL, ValueVT, Val);
294 }
295
296 // Handle MMX to a narrower integer type by bitcasting MMX to integer and
297 // then truncating.
298 if (PartEVT == MVT::x86mmx && ValueVT.isInteger() &&
299 ValueVT.bitsLT(PartEVT)) {
300 Val = DAG.getNode(ISD::BITCAST, DL, MVT::i64, Val);
301 return DAG.getNode(ISD::TRUNCATE, DL, ValueVT, Val);
302 }
303
304 report_fatal_error("Unknown mismatch in getCopyFromParts!");
305}
306
307static void diagnosePossiblyInvalidConstraint(LLVMContext &Ctx, const Value *V,
308 const Twine &ErrMsg) {
309 const Instruction *I = dyn_cast_or_null<Instruction>(V);
310 if (!V)
311 return Ctx.emitError(ErrMsg);
312
313 const char *AsmError = ", possible invalid constraint for vector type";
314 if (const CallInst *CI = dyn_cast<CallInst>(I))
315 if (CI->isInlineAsm())
316 return Ctx.emitError(I, ErrMsg + AsmError);
317
318 return Ctx.emitError(I, ErrMsg);
319}
320
321/// getCopyFromPartsVector - Create a value that contains the specified legal
322/// parts combined into the value they represent. If the parts combine to a
323/// type larger than ValueVT then AssertOp can be used to specify whether the
324/// extra bits are known to be zero (ISD::AssertZext) or sign extended from
325/// ValueVT (ISD::AssertSext).
326static SDValue getCopyFromPartsVector(SelectionDAG &DAG, const SDLoc &DL,
327 const SDValue *Parts, unsigned NumParts,
328 MVT PartVT, EVT ValueVT, const Value *V,
329 Optional<CallingConv::ID> CallConv) {
330 assert(ValueVT.isVector() && "Not a vector value");
331 assert(NumParts > 0 && "No parts to assemble!");
332 const bool IsABIRegCopy = CallConv.hasValue();
333
334 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
335 SDValue Val = Parts[0];
336
337 // Handle a multi-element vector.
338 if (NumParts > 1) {
339 EVT IntermediateVT;
340 MVT RegisterVT;
341 unsigned NumIntermediates;
342 unsigned NumRegs;
343
344 if (IsABIRegCopy) {
345 NumRegs = TLI.getVectorTypeBreakdownForCallingConv(
346 *DAG.getContext(), CallConv.getValue(), ValueVT, IntermediateVT,
347 NumIntermediates, RegisterVT);
348 } else {
349 NumRegs =
350 TLI.getVectorTypeBreakdown(*DAG.getContext(), ValueVT, IntermediateVT,
351 NumIntermediates, RegisterVT);
352 }
353
354 assert(NumRegs == NumParts && "Part count doesn't match vector breakdown!");
355 NumParts = NumRegs; // Silence a compiler warning.
356 assert(RegisterVT == PartVT && "Part type doesn't match vector breakdown!");
357 assert(RegisterVT.getSizeInBits() ==
358 Parts[0].getSimpleValueType().getSizeInBits() &&
359 "Part type sizes don't match!");
360
361 // Assemble the parts into intermediate operands.
362 SmallVector<SDValue, 8> Ops(NumIntermediates);
363 if (NumIntermediates == NumParts) {
364 // If the register was not expanded, truncate or copy the value,
365 // as appropriate.
366 for (unsigned i = 0; i != NumParts; ++i)
367 Ops[i] = getCopyFromParts(DAG, DL, &Parts[i], 1,
368 PartVT, IntermediateVT, V, CallConv);
369 } else if (NumParts > 0) {
370 // If the intermediate type was expanded, build the intermediate
371 // operands from the parts.
372 assert(NumParts % NumIntermediates == 0 &&
373 "Must expand into a divisible number of parts!");
374 unsigned Factor = NumParts / NumIntermediates;
375 for (unsigned i = 0; i != NumIntermediates; ++i)
376 Ops[i] = getCopyFromParts(DAG, DL, &Parts[i * Factor], Factor,
377 PartVT, IntermediateVT, V, CallConv);
378 }
379
380 // Build a vector with BUILD_VECTOR or CONCAT_VECTORS from the
381 // intermediate operands.
382 EVT BuiltVectorTy =
383 IntermediateVT.isVector()
384 ? EVT::getVectorVT(
385 *DAG.getContext(), IntermediateVT.getScalarType(),
386 IntermediateVT.getVectorElementCount() * NumParts)
387 : EVT::getVectorVT(*DAG.getContext(),
388 IntermediateVT.getScalarType(),
389 NumIntermediates);
390 Val = DAG.getNode(IntermediateVT.isVector() ? ISD::CONCAT_VECTORS
391 : ISD::BUILD_VECTOR,
392 DL, BuiltVectorTy, Ops);
393 }
394
395 // There is now one part, held in Val. Correct it to match ValueVT.
396 EVT PartEVT = Val.getValueType();
397
398 if (PartEVT == ValueVT)
399 return Val;
400
401 if (PartEVT.isVector()) {
402 // If the element type of the source/dest vectors are the same, but the
403 // parts vector has more elements than the value vector, then we have a
404 // vector widening case (e.g. <2 x float> -> <4 x float>). Extract the
405 // elements we want.
406 if (PartEVT.getVectorElementType() == ValueVT.getVectorElementType()) {
407 assert((PartEVT.getVectorElementCount().getKnownMinValue() >
408 ValueVT.getVectorElementCount().getKnownMinValue()) &&
409 (PartEVT.getVectorElementCount().isScalable() ==
410 ValueVT.getVectorElementCount().isScalable()) &&
411 "Cannot narrow, it would be a lossy transformation");
412 return DAG.getNode(ISD::EXTRACT_SUBVECTOR, DL, ValueVT, Val,
413 DAG.getVectorIdxConstant(0, DL));
414 }
415
416 // Vector/Vector bitcast.
417 if (ValueVT.getSizeInBits() == PartEVT.getSizeInBits())
418 return DAG.getNode(ISD::BITCAST, DL, ValueVT, Val);
419
420 assert(PartEVT.getVectorElementCount() == ValueVT.getVectorElementCount() &&
421 "Cannot handle this kind of promotion");
422 // Promoted vector extract
423 return DAG.getAnyExtOrTrunc(Val, DL, ValueVT);
424
425 }
426
427 // Trivial bitcast if the types are the same size and the destination
428 // vector type is legal.
429 if (PartEVT.getSizeInBits() == ValueVT.getSizeInBits() &&
430 TLI.isTypeLegal(ValueVT))
431 return DAG.getNode(ISD::BITCAST, DL, ValueVT, Val);
432
433 if (ValueVT.getVectorNumElements() != 1) {
434 // Certain ABIs require that vectors are passed as integers. For vectors
435 // are the same size, this is an obvious bitcast.
436 if (ValueVT.getSizeInBits() == PartEVT.getSizeInBits()) {
437 return DAG.getNode(ISD::BITCAST, DL, ValueVT, Val);
438 } else if (ValueVT.bitsLT(PartEVT)) {
439 const uint64_t ValueSize = ValueVT.getFixedSizeInBits();
440 EVT IntermediateType = EVT::getIntegerVT(*DAG.getContext(), ValueSize);
441 // Drop the extra bits.
442 Val = DAG.getNode(ISD::TRUNCATE, DL, IntermediateType, Val);
443 return DAG.getBitcast(ValueVT, Val);
444 }
445
446 diagnosePossiblyInvalidConstraint(
447 *DAG.getContext(), V, "non-trivial scalar-to-vector conversion");
448 return DAG.getUNDEF(ValueVT);
449 }
450
451 // Handle cases such as i8 -> <1 x i1>
452 EVT ValueSVT = ValueVT.getVectorElementType();
453 if (ValueVT.getVectorNumElements() == 1 && ValueSVT != PartEVT) {
454 if (ValueSVT.getSizeInBits() == PartEVT.getSizeInBits())
455 Val = DAG.getNode(ISD::BITCAST, DL, ValueSVT, Val);
456 else
457 Val = ValueVT.isFloatingPoint()
458 ? DAG.getFPExtendOrRound(Val, DL, ValueSVT)
459 : DAG.getAnyExtOrTrunc(Val, DL, ValueSVT);
460 }
461
462 return DAG.getBuildVector(ValueVT, DL, Val);
463}
464
465static void getCopyToPartsVector(SelectionDAG &DAG, const SDLoc &dl,
466 SDValue Val, SDValue *Parts, unsigned NumParts,
467 MVT PartVT, const Value *V,
468 Optional<CallingConv::ID> CallConv);
469
470/// getCopyToParts - Create a series of nodes that contain the specified value
471/// split into legal parts. If the parts contain more bits than Val, then, for
472/// integers, ExtendKind can be used to specify how to generate the extra bits.
473static void getCopyToParts(SelectionDAG &DAG, const SDLoc &DL, SDValue Val,
474 SDValue *Parts, unsigned NumParts, MVT PartVT,
475 const Value *V,
476 Optional<CallingConv::ID> CallConv = None,
477 ISD::NodeType ExtendKind = ISD::ANY_EXTEND) {
478 // Let the target split the parts if it wants to
479 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
480 if (TLI.splitValueIntoRegisterParts(DAG, DL, Val, Parts, NumParts, PartVT,
481 CallConv))
482 return;
483 EVT ValueVT = Val.getValueType();
484
485 // Handle the vector case separately.
486 if (ValueVT.isVector())
487 return getCopyToPartsVector(DAG, DL, Val, Parts, NumParts, PartVT, V,
488 CallConv);
489
490 unsigned PartBits = PartVT.getSizeInBits();
491 unsigned OrigNumParts = NumParts;
492 assert(DAG.getTargetLoweringInfo().isTypeLegal(PartVT) &&
493 "Copying to an illegal type!");
494
495 if (NumParts == 0)
496 return;
497
498 assert(!ValueVT.isVector() && "Vector case handled elsewhere");
499 EVT PartEVT = PartVT;
500 if (PartEVT == ValueVT) {
501 assert(NumParts == 1 && "No-op copy with multiple parts!");
502 Parts[0] = Val;
503 return;
504 }
505
506 if (NumParts * PartBits > ValueVT.getSizeInBits()) {
507 // If the parts cover more bits than the value has, promote the value.
508 if (PartVT.isFloatingPoint() && ValueVT.isFloatingPoint()) {
509 assert(NumParts == 1 && "Do not know what to promote to!");
510 Val = DAG.getNode(ISD::FP_EXTEND, DL, PartVT, Val);
511 } else {
512 if (ValueVT.isFloatingPoint()) {
513 // FP values need to be bitcast, then extended if they are being put
514 // into a larger container.
515 ValueVT = EVT::getIntegerVT(*DAG.getContext(), ValueVT.getSizeInBits());
516 Val = DAG.getNode(ISD::BITCAST, DL, ValueVT, Val);
517 }
518 assert((PartVT.isInteger() || PartVT == MVT::x86mmx) &&
519 ValueVT.isInteger() &&
520 "Unknown mismatch!");
521 ValueVT = EVT::getIntegerVT(*DAG.getContext(), NumParts * PartBits);
522 Val = DAG.getNode(ExtendKind, DL, ValueVT, Val);
523 if (PartVT == MVT::x86mmx)
524 Val = DAG.getNode(ISD::BITCAST, DL, PartVT, Val);
525 }
526 } else if (PartBits == ValueVT.getSizeInBits()) {
527 // Different types of the same size.
528 assert(NumParts == 1 && PartEVT != ValueVT);
529 Val = DAG.getNode(ISD::BITCAST, DL, PartVT, Val);
530 } else if (NumParts * PartBits < ValueVT.getSizeInBits()) {
531 // If the parts cover less bits than value has, truncate the value.
532 assert((PartVT.isInteger() || PartVT == MVT::x86mmx) &&
533 ValueVT.isInteger() &&
534 "Unknown mismatch!");
535 ValueVT = EVT::getIntegerVT(*DAG.getContext(), NumParts * PartBits);
536 Val = DAG.getNode(ISD::TRUNCATE, DL, ValueVT, Val);
537 if (PartVT == MVT::x86mmx)
538 Val = DAG.getNode(ISD::BITCAST, DL, PartVT, Val);
539 }
540
541 // The value may have changed - recompute ValueVT.
542 ValueVT = Val.getValueType();
543 assert(NumParts * PartBits == ValueVT.getSizeInBits() &&
544 "Failed to tile the value with PartVT!");
545
546 if (NumParts == 1) {
547 if (PartEVT != ValueVT) {
548 diagnosePossiblyInvalidConstraint(*DAG.getContext(), V,
549 "scalar-to-vector conversion failed");
550 Val = DAG.getNode(ISD::BITCAST, DL, PartVT, Val);
551 }
552
553 Parts[0] = Val;
554 return;
555 }
556
557 // Expand the value into multiple parts.
558 if (NumParts & (NumParts - 1)) {
559 // The number of parts is not a power of 2. Split off and copy the tail.
560 assert(PartVT.isInteger() && ValueVT.isInteger() &&
561 "Do not know what to expand to!");
562 unsigned RoundParts = 1 << Log2_32(NumParts);
563 unsigned RoundBits = RoundParts * PartBits;
564 unsigned OddParts = NumParts - RoundParts;
565 SDValue OddVal = DAG.getNode(ISD::SRL, DL, ValueVT, Val,
566 DAG.getShiftAmountConstant(RoundBits, ValueVT, DL, /*LegalTypes*/false));
567
568 getCopyToParts(DAG, DL, OddVal, Parts + RoundParts, OddParts, PartVT, V,
569 CallConv);
570
571 if (DAG.getDataLayout().isBigEndian())
572 // The odd parts were reversed by getCopyToParts - unreverse them.
573 std::reverse(Parts + RoundParts, Parts + NumParts);
574
575 NumParts = RoundParts;
576 ValueVT = EVT::getIntegerVT(*DAG.getContext(), NumParts * PartBits);
577 Val = DAG.getNode(ISD::TRUNCATE, DL, ValueVT, Val);
578 }
579
580 // The number of parts is a power of 2. Repeatedly bisect the value using
581 // EXTRACT_ELEMENT.
582 Parts[0] = DAG.getNode(ISD::BITCAST, DL,
583 EVT::getIntegerVT(*DAG.getContext(),
584 ValueVT.getSizeInBits()),
585 Val);
586
587 for (unsigned StepSize = NumParts; StepSize > 1; StepSize /= 2) {
588 for (unsigned i = 0; i < NumParts; i += StepSize) {
589 unsigned ThisBits = StepSize * PartBits / 2;
590 EVT ThisVT = EVT::getIntegerVT(*DAG.getContext(), ThisBits);
591 SDValue &Part0 = Parts[i];
592 SDValue &Part1 = Parts[i+StepSize/2];
593
594 Part1 = DAG.getNode(ISD::EXTRACT_ELEMENT, DL,
595 ThisVT, Part0, DAG.getIntPtrConstant(1, DL));
596 Part0 = DAG.getNode(ISD::EXTRACT_ELEMENT, DL,
597 ThisVT, Part0, DAG.getIntPtrConstant(0, DL));
598
599 if (ThisBits == PartBits && ThisVT != PartVT) {
600 Part0 = DAG.getNode(ISD::BITCAST, DL, PartVT, Part0);
601 Part1 = DAG.getNode(ISD::BITCAST, DL, PartVT, Part1);
602 }
603 }
604 }
605
606 if (DAG.getDataLayout().isBigEndian())
607 std::reverse(Parts, Parts + OrigNumParts);
608}
609
610static SDValue widenVectorToPartType(SelectionDAG &DAG,
611 SDValue Val, const SDLoc &DL, EVT PartVT) {
612 if (!PartVT.isFixedLengthVector())
613 return SDValue();
614
615 EVT ValueVT = Val.getValueType();
616 unsigned PartNumElts = PartVT.getVectorNumElements();
617 unsigned ValueNumElts = ValueVT.getVectorNumElements();
618 if (PartNumElts > ValueNumElts &&
619 PartVT.getVectorElementType() == ValueVT.getVectorElementType()) {
620 EVT ElementVT = PartVT.getVectorElementType();
621 // Vector widening case, e.g. <2 x float> -> <4 x float>. Shuffle in
622 // undef elements.
623 SmallVector<SDValue, 16> Ops;
624 DAG.ExtractVectorElements(Val, Ops);
625 SDValue EltUndef = DAG.getUNDEF(ElementVT);
626 for (unsigned i = ValueNumElts, e = PartNumElts; i != e; ++i)
627 Ops.push_back(EltUndef);
628
629 // FIXME: Use CONCAT for 2x -> 4x.
630 return DAG.getBuildVector(PartVT, DL, Ops);
631 }
632
633 return SDValue();
634}
635
636/// getCopyToPartsVector - Create a series of nodes that contain the specified
637/// value split into legal parts.
638static void getCopyToPartsVector(SelectionDAG &DAG, const SDLoc &DL,
639 SDValue Val, SDValue *Parts, unsigned NumParts,
640 MVT PartVT, const Value *V,
641 Optional<CallingConv::ID> CallConv) {
642 EVT ValueVT = Val.getValueType();
643 assert(ValueVT.isVector() && "Not a vector");
644 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
645 const bool IsABIRegCopy = CallConv.hasValue();
646
647 if (NumParts == 1) {
648 EVT PartEVT = PartVT;
649 if (PartEVT == ValueVT) {
650 // Nothing to do.
651 } else if (PartVT.getSizeInBits() == ValueVT.getSizeInBits()) {
652 // Bitconvert vector->vector case.
653 Val = DAG.getNode(ISD::BITCAST, DL, PartVT, Val);
654 } else if (SDValue Widened = widenVectorToPartType(DAG, Val, DL, PartVT)) {
655 Val = Widened;
656 } else if (PartVT.isVector() &&
657 PartEVT.getVectorElementType().bitsGE(
658 ValueVT.getVectorElementType()) &&
659 PartEVT.getVectorElementCount() ==
660 ValueVT.getVectorElementCount()) {
661
662 // Promoted vector extract
663 Val = DAG.getAnyExtOrTrunc(Val, DL, PartVT);
664 } else {
665 if (ValueVT.getVectorElementCount().isScalar()) {
666 Val = DAG.getNode(ISD::EXTRACT_VECTOR_ELT, DL, PartVT, Val,
667 DAG.getVectorIdxConstant(0, DL));
668 } else {
669 uint64_t ValueSize = ValueVT.getFixedSizeInBits();
670 assert(PartVT.getFixedSizeInBits() > ValueSize &&
671 "lossy conversion of vector to scalar type");
672 EVT IntermediateType = EVT::getIntegerVT(*DAG.getContext(), ValueSize);
673 Val = DAG.getBitcast(IntermediateType, Val);
674 Val = DAG.getAnyExtOrTrunc(Val, DL, PartVT);
675 }
676 }
677
678 assert(Val.getValueType() == PartVT && "Unexpected vector part value type");
679 Parts[0] = Val;
680 return;
681 }
682
683 // Handle a multi-element vector.
684 EVT IntermediateVT;
685 MVT RegisterVT;
686 unsigned NumIntermediates;
687 unsigned NumRegs;
688 if (IsABIRegCopy) {
689 NumRegs = TLI.getVectorTypeBreakdownForCallingConv(
690 *DAG.getContext(), CallConv.getValue(), ValueVT, IntermediateVT,
691 NumIntermediates, RegisterVT);
692 } else {
693 NumRegs =
694 TLI.getVectorTypeBreakdown(*DAG.getContext(), ValueVT, IntermediateVT,
695 NumIntermediates, RegisterVT);
696 }
697
698 assert(NumRegs == NumParts && "Part count doesn't match vector breakdown!");
699 NumParts = NumRegs; // Silence a compiler warning.
700 assert(RegisterVT == PartVT && "Part type doesn't match vector breakdown!");
701
702 assert(IntermediateVT.isScalableVector() == ValueVT.isScalableVector() &&
703 "Mixing scalable and fixed vectors when copying in parts");
704
705 Optional<ElementCount> DestEltCnt;
706
707 if (IntermediateVT.isVector())
708 DestEltCnt = IntermediateVT.getVectorElementCount() * NumIntermediates;
709 else
710 DestEltCnt = ElementCount::getFixed(NumIntermediates);
711
712 EVT BuiltVectorTy = EVT::getVectorVT(
713 *DAG.getContext(), IntermediateVT.getScalarType(), DestEltCnt.getValue());
714
715 if (ValueVT == BuiltVectorTy) {
716 // Nothing to do.
717 } else if (ValueVT.getSizeInBits() == BuiltVectorTy.getSizeInBits()) {
718 // Bitconvert vector->vector case.
719 Val = DAG.getNode(ISD::BITCAST, DL, BuiltVectorTy, Val);
720 } else if (SDValue Widened =
721 widenVectorToPartType(DAG, Val, DL, BuiltVectorTy)) {
722 Val = Widened;
723 } else if (BuiltVectorTy.getVectorElementType().bitsGE(
724 ValueVT.getVectorElementType()) &&
725 BuiltVectorTy.getVectorElementCount() ==
726 ValueVT.getVectorElementCount()) {
727 // Promoted vector extract
728 Val = DAG.getAnyExtOrTrunc(Val, DL, BuiltVectorTy);
729 }
730
731 assert(Val.getValueType() == BuiltVectorTy && "Unexpected vector value type");
732
733 // Split the vector into intermediate operands.
734 SmallVector<SDValue, 8> Ops(NumIntermediates);
735 for (unsigned i = 0; i != NumIntermediates; ++i) {
736 if (IntermediateVT.isVector()) {
737 // This does something sensible for scalable vectors - see the
738 // definition of EXTRACT_SUBVECTOR for further details.
739 unsigned IntermediateNumElts = IntermediateVT.getVectorMinNumElements();
740 Ops[i] =
741 DAG.getNode(ISD::EXTRACT_SUBVECTOR, DL, IntermediateVT, Val,
742 DAG.getVectorIdxConstant(i * IntermediateNumElts, DL));
743 } else {
744 Ops[i] = DAG.getNode(ISD::EXTRACT_VECTOR_ELT, DL, IntermediateVT, Val,
745 DAG.getVectorIdxConstant(i, DL));
746 }
747 }
748
749 // Split the intermediate operands into legal parts.
750 if (NumParts == NumIntermediates) {
751 // If the register was not expanded, promote or copy the value,
752 // as appropriate.
753 for (unsigned i = 0; i != NumParts; ++i)
754 getCopyToParts(DAG, DL, Ops[i], &Parts[i], 1, PartVT, V, CallConv);
755 } else if (NumParts > 0) {
756 // If the intermediate type was expanded, split each the value into
757 // legal parts.
758 assert(NumIntermediates != 0 && "division by zero");
759 assert(NumParts % NumIntermediates == 0 &&
760 "Must expand into a divisible number of parts!");
761 unsigned Factor = NumParts / NumIntermediates;
762 for (unsigned i = 0; i != NumIntermediates; ++i)
763 getCopyToParts(DAG, DL, Ops[i], &Parts[i * Factor], Factor, PartVT, V,
764 CallConv);
765 }
766}
767
768RegsForValue::RegsForValue(const SmallVector<unsigned, 4> &regs, MVT regvt,
769 EVT valuevt, Optional<CallingConv::ID> CC)
770 : ValueVTs(1, valuevt), RegVTs(1, regvt), Regs(regs),
771 RegCount(1, regs.size()), CallConv(CC) {}
772
773RegsForValue::RegsForValue(LLVMContext &Context, const TargetLowering &TLI,
774 const DataLayout &DL, unsigned Reg, Type *Ty,
775 Optional<CallingConv::ID> CC) {
776 ComputeValueVTs(TLI, DL, Ty, ValueVTs);
777
778 CallConv = CC;
779
780 for (EVT ValueVT : ValueVTs) {
781 unsigned NumRegs =
782 isABIMangled()
783 ? TLI.getNumRegistersForCallingConv(Context, CC.getValue(), ValueVT)
784 : TLI.getNumRegisters(Context, ValueVT);
785 MVT RegisterVT =
786 isABIMangled()
787 ? TLI.getRegisterTypeForCallingConv(Context, CC.getValue(), ValueVT)
788 : TLI.getRegisterType(Context, ValueVT);
789 for (unsigned i = 0; i != NumRegs; ++i)
790 Regs.push_back(Reg + i);
791 RegVTs.push_back(RegisterVT);
792 RegCount.push_back(NumRegs);
793 Reg += NumRegs;
794 }
795}
796
797SDValue RegsForValue::getCopyFromRegs(SelectionDAG &DAG,
798 FunctionLoweringInfo &FuncInfo,
799 const SDLoc &dl, SDValue &Chain,
800 SDValue *Flag, const Value *V) const {
801 // A Value with type {} or [0 x %t] needs no registers.
802 if (ValueVTs.empty())
803 return SDValue();
804
805 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
806
807 // Assemble the legal parts into the final values.
808 SmallVector<SDValue, 4> Values(ValueVTs.size());
809 SmallVector<SDValue, 8> Parts;
810 for (unsigned Value = 0, Part = 0, e = ValueVTs.size(); Value != e; ++Value) {
811 // Copy the legal parts from the registers.
812 EVT ValueVT = ValueVTs[Value];
813 unsigned NumRegs = RegCount[Value];
814 MVT RegisterVT = isABIMangled() ? TLI.getRegisterTypeForCallingConv(
815 *DAG.getContext(),
816 CallConv.getValue(), RegVTs[Value])
817 : RegVTs[Value];
818
819 Parts.resize(NumRegs);
820 for (unsigned i = 0; i != NumRegs; ++i) {
821 SDValue P;
822 if (!Flag) {
823 P = DAG.getCopyFromReg(Chain, dl, Regs[Part+i], RegisterVT);
824 } else {
825 P = DAG.getCopyFromReg(Chain, dl, Regs[Part+i], RegisterVT, *Flag);
826 *Flag = P.getValue(2);
827 }
828
829 Chain = P.getValue(1);
830 Parts[i] = P;
831
832 // If the source register was virtual and if we know something about it,
833 // add an assert node.
834 if (!Register::isVirtualRegister(Regs[Part + i]) ||
835 !RegisterVT.isInteger())
836 continue;
837
838 const FunctionLoweringInfo::LiveOutInfo *LOI =
839 FuncInfo.GetLiveOutRegInfo(Regs[Part+i]);
840 if (!LOI)
841 continue;
842
843 unsigned RegSize = RegisterVT.getScalarSizeInBits();
844 unsigned NumSignBits = LOI->NumSignBits;
845 unsigned NumZeroBits = LOI->Known.countMinLeadingZeros();
846
847 if (NumZeroBits == RegSize) {
848 // The current value is a zero.
849 // Explicitly express that as it would be easier for
850 // optimizations to kick in.
851 Parts[i] = DAG.getConstant(0, dl, RegisterVT);
852 continue;
853 }
854
855 // FIXME: We capture more information than the dag can represent. For
856 // now, just use the tightest assertzext/assertsext possible.
857 bool isSExt;
858 EVT FromVT(MVT::Other);
859 if (NumZeroBits) {
860 FromVT = EVT::getIntegerVT(*DAG.getContext(), RegSize - NumZeroBits);
861 isSExt = false;
862 } else if (NumSignBits > 1) {
863 FromVT =
864 EVT::getIntegerVT(*DAG.getContext(), RegSize - NumSignBits + 1);
865 isSExt = true;
866 } else {
867 continue;
868 }
869 // Add an assertion node.
870 assert(FromVT != MVT::Other);
871 Parts[i] = DAG.getNode(isSExt ? ISD::AssertSext : ISD::AssertZext, dl,
872 RegisterVT, P, DAG.getValueType(FromVT));
873 }
874
875 Values[Value] = getCopyFromParts(DAG, dl, Parts.begin(), NumRegs,
876 RegisterVT, ValueVT, V, CallConv);
877 Part += NumRegs;
878 Parts.clear();
879 }
880
881 return DAG.getNode(ISD::MERGE_VALUES, dl, DAG.getVTList(ValueVTs), Values);
882}
883
884void RegsForValue::getCopyToRegs(SDValue Val, SelectionDAG &DAG,
885 const SDLoc &dl, SDValue &Chain, SDValue *Flag,
886 const Value *V,
887 ISD::NodeType PreferredExtendType) const {
888 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
889 ISD::NodeType ExtendKind = PreferredExtendType;
890
891 // Get the list of the values's legal parts.
892 unsigned NumRegs = Regs.size();
893 SmallVector<SDValue, 8> Parts(NumRegs);
894 for (unsigned Value = 0, Part = 0, e = ValueVTs.size(); Value != e; ++Value) {
895 unsigned NumParts = RegCount[Value];
896
897 MVT RegisterVT = isABIMangled() ? TLI.getRegisterTypeForCallingConv(
898 *DAG.getContext(),
899 CallConv.getValue(), RegVTs[Value])
900 : RegVTs[Value];
901
902 if (ExtendKind == ISD::ANY_EXTEND && TLI.isZExtFree(Val, RegisterVT))
903 ExtendKind = ISD::ZERO_EXTEND;
904
905 getCopyToParts(DAG, dl, Val.getValue(Val.getResNo() + Value), &Parts[Part],
906 NumParts, RegisterVT, V, CallConv, ExtendKind);
907 Part += NumParts;
908 }
909
910 // Copy the parts into the registers.
911 SmallVector<SDValue, 8> Chains(NumRegs);
912 for (unsigned i = 0; i != NumRegs; ++i) {
913 SDValue Part;
914 if (!Flag) {
915 Part = DAG.getCopyToReg(Chain, dl, Regs[i], Parts[i]);
916 } else {
917 Part = DAG.getCopyToReg(Chain, dl, Regs[i], Parts[i], *Flag);
918 *Flag = Part.getValue(1);
919 }
920
921 Chains[i] = Part.getValue(0);
922 }
923
924 if (NumRegs == 1 || Flag)
925 // If NumRegs > 1 && Flag is used then the use of the last CopyToReg is
926 // flagged to it. That is the CopyToReg nodes and the user are considered
927 // a single scheduling unit. If we create a TokenFactor and return it as
928 // chain, then the TokenFactor is both a predecessor (operand) of the
929 // user as well as a successor (the TF operands are flagged to the user).
930 // c1, f1 = CopyToReg
931 // c2, f2 = CopyToReg
932 // c3 = TokenFactor c1, c2
933 // ...
934 // = op c3, ..., f2
935 Chain = Chains[NumRegs-1];
936 else
937 Chain = DAG.getNode(ISD::TokenFactor, dl, MVT::Other, Chains);
938}
939
940void RegsForValue::AddInlineAsmOperands(unsigned Code, bool HasMatching,
941 unsigned MatchingIdx, const SDLoc &dl,
942 SelectionDAG &DAG,
943 std::vector<SDValue> &Ops) const {
944 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
945
946 unsigned Flag = InlineAsm::getFlagWord(Code, Regs.size());
947 if (HasMatching)
948 Flag = InlineAsm::getFlagWordForMatchingOp(Flag, MatchingIdx);
949 else if (!Regs.empty() && Register::isVirtualRegister(Regs.front())) {
950 // Put the register class of the virtual registers in the flag word. That
951 // way, later passes can recompute register class constraints for inline
952 // assembly as well as normal instructions.
953 // Don't do this for tied operands that can use the regclass information
954 // from the def.
955 const MachineRegisterInfo &MRI = DAG.getMachineFunction().getRegInfo();
956 const TargetRegisterClass *RC = MRI.getRegClass(Regs.front());
957 Flag = InlineAsm::getFlagWordForRegClass(Flag, RC->getID());
958 }
959
960 SDValue Res = DAG.getTargetConstant(Flag, dl, MVT::i32);
961 Ops.push_back(Res);
962
963 if (Code == InlineAsm::Kind_Clobber) {
964 // Clobbers should always have a 1:1 mapping with registers, and may
965 // reference registers that have illegal (e.g. vector) types. Hence, we
966 // shouldn't try to apply any sort of splitting logic to them.
967 assert(Regs.size() == RegVTs.size() && Regs.size() == ValueVTs.size() &&
968 "No 1:1 mapping from clobbers to regs?");
969 Register SP = TLI.getStackPointerRegisterToSaveRestore();
970 (void)SP;
971 for (unsigned I = 0, E = ValueVTs.size(); I != E; ++I) {
972 Ops.push_back(DAG.getRegister(Regs[I], RegVTs[I]));
973 assert(
974 (Regs[I] != SP ||
975 DAG.getMachineFunction().getFrameInfo().hasOpaqueSPAdjustment()) &&
976 "If we clobbered the stack pointer, MFI should know about it.");
977 }
978 return;
979 }
980
981 for (unsigned Value = 0, Reg = 0, e = ValueVTs.size(); Value != e; ++Value) {
982 unsigned NumRegs = TLI.getNumRegisters(*DAG.getContext(), ValueVTs[Value]);
983 MVT RegisterVT = RegVTs[Value];
984 for (unsigned i = 0; i != NumRegs; ++i) {
985 assert(Reg < Regs.size() && "Mismatch in # registers expected");
986 unsigned TheReg = Regs[Reg++];
987 Ops.push_back(DAG.getRegister(TheReg, RegisterVT));
988 }
989 }
990}
991
992SmallVector<std::pair<unsigned, TypeSize>, 4>
993RegsForValue::getRegsAndSizes() const {
994 SmallVector<std::pair<unsigned, TypeSize>, 4> OutVec;
995 unsigned I = 0;
996 for (auto CountAndVT : zip_first(RegCount, RegVTs)) {
997 unsigned RegCount = std::get<0>(CountAndVT);
998 MVT RegisterVT = std::get<1>(CountAndVT);
999 TypeSize RegisterSize = RegisterVT.getSizeInBits();
1000 for (unsigned E = I + RegCount; I != E; ++I)
1001 OutVec.push_back(std::make_pair(Regs[I], RegisterSize));
1002 }
1003 return OutVec;
1004}
1005
1006void SelectionDAGBuilder::init(GCFunctionInfo *gfi, AliasAnalysis *aa,
1007 const TargetLibraryInfo *li) {
1008 AA = aa;
1009 GFI = gfi;
1010 LibInfo = li;
1011 DL = &DAG.getDataLayout();
1012 Context = DAG.getContext();
1013 LPadToCallSiteMap.clear();
1014 SL->init(DAG.getTargetLoweringInfo(), TM, DAG.getDataLayout());
1015}
1016
1017void SelectionDAGBuilder::clear() {
1018 NodeMap.clear();
1019 UnusedArgNodeMap.clear();
1020 PendingLoads.clear();
1021 PendingExports.clear();
1022 PendingConstrainedFP.clear();
1023 PendingConstrainedFPStrict.clear();
1024 CurInst = nullptr;
1025 HasTailCall = false;
1026 SDNodeOrder = LowestSDNodeOrder;
1027 StatepointLowering.clear();
1028}
1029
1030void SelectionDAGBuilder::clearDanglingDebugInfo() {
1031 DanglingDebugInfoMap.clear();
1032}
1033
1034// Update DAG root to include dependencies on Pending chains.
1035SDValue SelectionDAGBuilder::updateRoot(SmallVectorImpl<SDValue> &Pending) {
1036 SDValue Root = DAG.getRoot();
1037
1038 if (Pending.empty())
1039 return Root;
1040
1041 // Add current root to PendingChains, unless we already indirectly
1042 // depend on it.
1043 if (Root.getOpcode() != ISD::EntryToken) {
1044 unsigned i = 0, e = Pending.size();
1045 for (; i != e; ++i) {
1046 assert(Pending[i].getNode()->getNumOperands() > 1);
1047 if (Pending[i].getNode()->getOperand(0) == Root)
1048 break; // Don't add the root if we already indirectly depend on it.
1049 }
1050
1051 if (i == e)
1052 Pending.push_back(Root);
1053 }
1054
1055 if (Pending.size() == 1)
1056 Root = Pending[0];
1057 else
1058 Root = DAG.getTokenFactor(getCurSDLoc(), Pending);
1059
1060 DAG.setRoot(Root);
1061 Pending.clear();
1062 return Root;
1063}
1064
1065SDValue SelectionDAGBuilder::getMemoryRoot() {
1066 return updateRoot(PendingLoads);
1067}
1068
1069SDValue SelectionDAGBuilder::getRoot() {
1070 // Chain up all pending constrained intrinsics together with all
1071 // pending loads, by simply appending them to PendingLoads and
1072 // then calling getMemoryRoot().
1073 PendingLoads.reserve(PendingLoads.size() +
1074 PendingConstrainedFP.size() +
1075 PendingConstrainedFPStrict.size());
1076 PendingLoads.append(PendingConstrainedFP.begin(),
1077 PendingConstrainedFP.end());
1078 PendingLoads.append(PendingConstrainedFPStrict.begin(),
1079 PendingConstrainedFPStrict.end());
1080 PendingConstrainedFP.clear();
1081 PendingConstrainedFPStrict.clear();
1082 return getMemoryRoot();
1083}
1084
1085SDValue SelectionDAGBuilder::getControlRoot() {
1086 // We need to emit pending fpexcept.strict constrained intrinsics,
1087 // so append them to the PendingExports list.
1088 PendingExports.append(PendingConstrainedFPStrict.begin(),
1089 PendingConstrainedFPStrict.end());
1090 PendingConstrainedFPStrict.clear();
1091 return updateRoot(PendingExports);
1092}
1093
1094void SelectionDAGBuilder::visit(const Instruction &I) {
1095 // Set up outgoing PHI node register values before emitting the terminator.
1096 if (I.isTerminator()) {
1097 HandlePHINodesInSuccessorBlocks(I.getParent());
1098 }
1099
1100 // Increase the SDNodeOrder if dealing with a non-debug instruction.
1101 if (!isa<DbgInfoIntrinsic>(I))
1102 ++SDNodeOrder;
1103
1104 CurInst = &I;
1105
1106 visit(I.getOpcode(), I);
1107
1108 if (!I.isTerminator() && !HasTailCall &&
1109 !isa<GCStatepointInst>(I)) // statepoints handle their exports internally
1110 CopyToExportRegsIfNeeded(&I);
1111
1112 CurInst = nullptr;
1113}
1114
1115void SelectionDAGBuilder::visitPHI(const PHINode &) {
1116 llvm_unreachable("SelectionDAGBuilder shouldn't visit PHI nodes!");
1117}
1118
1119void SelectionDAGBuilder::visit(unsigned Opcode, const User &I) {
1120 // Note: this doesn't use InstVisitor, because it has to work with
1121 // ConstantExpr's in addition to instructions.
1122 switch (Opcode) {
1123 default: llvm_unreachable("Unknown instruction type encountered!");
1124 // Build the switch statement using the Instruction.def file.
1125#define HANDLE_INST(NUM, OPCODE, CLASS) \
1126 case Instruction::OPCODE: visit##OPCODE((const CLASS&)I); break;
1127#include "llvm/IR/Instruction.def"
1128 }
1129}
1130
1131void SelectionDAGBuilder::addDanglingDebugInfo(const DbgValueInst *DI,
1132 DebugLoc DL, unsigned Order) {
1133 // We treat variadic dbg_values differently at this stage.
1134 if (DI->hasArgList()) {
1135 // For variadic dbg_values we will now insert an undef.
1136 // FIXME: We can potentially recover these!
1137 SmallVector<SDDbgOperand, 2> Locs;
1138 for (const Value *V : DI->getValues()) {
1139 auto Undef = UndefValue::get(V->getType());
1140 Locs.push_back(SDDbgOperand::fromConst(Undef));
1141 }
1142 SDDbgValue *SDV = DAG.getDbgValueList(
1143 DI->getVariable(), DI->getExpression(), Locs, {},
1144 /*IsIndirect=*/false, DL, Order, /*IsVariadic=*/true);
1145 DAG.AddDbgValue(SDV, /*isParameter=*/false);
1146 } else {
1147 // TODO: Dangling debug info will eventually either be resolved or produce
1148 // an Undef DBG_VALUE. However in the resolution case, a gap may appear
1149 // between the original dbg.value location and its resolved DBG_VALUE,
1150 // which we should ideally fill with an extra Undef DBG_VALUE.
1151 assert(DI->getNumVariableLocationOps() == 1 &&
1152 "DbgValueInst without an ArgList should have a single location "
1153 "operand.");
1154 DanglingDebugInfoMap[DI->getValue(0)].emplace_back(DI, DL, Order);
1155 }
1156}
1157
1158void SelectionDAGBuilder::dropDanglingDebugInfo(const DILocalVariable *Variable,
1159 const DIExpression *Expr) {
1160 auto isMatchingDbgValue = [&](DanglingDebugInfo &DDI) {
1161 const DbgValueInst *DI = DDI.getDI();
1162 DIVariable *DanglingVariable = DI->getVariable();
1163 DIExpression *DanglingExpr = DI->getExpression();
1164 if (DanglingVariable == Variable && Expr->fragmentsOverlap(DanglingExpr)) {
1165 LLVM_DEBUG(dbgs() << "Dropping dangling debug info for " << *DI << "\n");
1166 return true;
1167 }
1168 return false;
1169 };
1170
1171 for (auto &DDIMI : DanglingDebugInfoMap) {
1172 DanglingDebugInfoVector &DDIV = DDIMI.second;
1173
1174 // If debug info is to be dropped, run it through final checks to see
1175 // whether it can be salvaged.
1176 for (auto &DDI : DDIV)
1177 if (isMatchingDbgValue(DDI))
1178 salvageUnresolvedDbgValue(DDI);
1179
1180 erase_if(DDIV, isMatchingDbgValue);
1181 }
1182}
1183
1184// resolveDanglingDebugInfo - if we saw an earlier dbg_value referring to V,
1185// generate the debug data structures now that we've seen its definition.
1186void SelectionDAGBuilder::resolveDanglingDebugInfo(const Value *V,
1187 SDValue Val) {
1188 auto DanglingDbgInfoIt = DanglingDebugInfoMap.find(V);
1189 if (DanglingDbgInfoIt == DanglingDebugInfoMap.end())
1190 return;
1191
1192 DanglingDebugInfoVector &DDIV = DanglingDbgInfoIt->second;
1193 for (auto &DDI : DDIV) {
1194 const DbgValueInst *DI = DDI.getDI();
1195 assert(!DI->hasArgList() && "Not implemented for variadic dbg_values");
1196 assert(DI && "Ill-formed DanglingDebugInfo");
1197 DebugLoc dl = DDI.getdl();
1198 unsigned ValSDNodeOrder = Val.getNode()->getIROrder();
1199 unsigned DbgSDNodeOrder = DDI.getSDNodeOrder();
1200 DILocalVariable *Variable = DI->getVariable();
1201 DIExpression *Expr = DI->getExpression();
1202 assert(Variable->isValidLocationForIntrinsic(dl) &&
1203 "Expected inlined-at fields to agree");
1204 SDDbgValue *SDV;
1205 if (Val.getNode()) {
1206 // FIXME: I doubt that it is correct to resolve a dangling DbgValue as a
1207 // FuncArgumentDbgValue (it would be hoisted to the function entry, and if
1208 // we couldn't resolve it directly when examining the DbgValue intrinsic
1209 // in the first place we should not be more successful here). Unless we
1210 // have some test case that prove this to be correct we should avoid
1211 // calling EmitFuncArgumentDbgValue here.
1212 if (!EmitFuncArgumentDbgValue(V, Variable, Expr, dl, false, Val)) {
1213 LLVM_DEBUG(dbgs() << "Resolve dangling debug info [order="
1214 << DbgSDNodeOrder << "] for:\n " << *DI << "\n");
1215 LLVM_DEBUG(dbgs() << " By mapping to:\n "; Val.dump());
1216 // Increase the SDNodeOrder for the DbgValue here to make sure it is
1217 // inserted after the definition of Val when emitting the instructions
1218 // after ISel. An alternative could be to teach
1219 // ScheduleDAGSDNodes::EmitSchedule to delay the insertion properly.
1220 LLVM_DEBUG(if (ValSDNodeOrder > DbgSDNodeOrder) dbgs()
1221 << "changing SDNodeOrder from " << DbgSDNodeOrder << " to "
1222 << ValSDNodeOrder << "\n");
1223 SDV = getDbgValue(Val, Variable, Expr, dl,
1224 std::max(DbgSDNodeOrder, ValSDNodeOrder));
1225 DAG.AddDbgValue(SDV, false);
1226 } else
1227 LLVM_DEBUG(dbgs() << "Resolved dangling debug info for " << *DI
1228 << "in EmitFuncArgumentDbgValue\n");
1229 } else {
1230 LLVM_DEBUG(dbgs() << "Dropping debug info for " << *DI << "\n");
1231 auto Undef = UndefValue::get(DDI.getDI()->getValue(0)->getType());
1232 auto SDV =
1233 DAG.getConstantDbgValue(Variable, Expr, Undef, dl, DbgSDNodeOrder);
1234 DAG.AddDbgValue(SDV, false);
1235 }
1236 }
1237 DDIV.clear();
1238}
1239
1240void SelectionDAGBuilder::salvageUnresolvedDbgValue(DanglingDebugInfo &DDI) {
1241 assert(!DDI.getDI()->hasArgList() &&
1242 "Not implemented for variadic dbg_values");
1243 Value *V = DDI.getDI()->getValue(0);
1244 DILocalVariable *Var = DDI.getDI()->getVariable();
1245 DIExpression *Expr = DDI.getDI()->getExpression();
1246 DebugLoc DL = DDI.getdl();
1247 DebugLoc InstDL = DDI.getDI()->getDebugLoc();
1248 unsigned SDOrder = DDI.getSDNodeOrder();
1249 // Currently we consider only dbg.value intrinsics -- we tell the salvager
1250 // that DW_OP_stack_value is desired.
1251 assert(isa<DbgValueInst>(DDI.getDI()));
1252 bool StackValue = true;
1253
1254 // Can this Value can be encoded without any further work?
1255 if (handleDebugValue(V, Var, Expr, DL, InstDL, SDOrder, /*IsVariadic=*/false))
1256 return;
1257
1258 // Attempt to salvage back through as many instructions as possible. Bail if
1259 // a non-instruction is seen, such as a constant expression or global
1260 // variable. FIXME: Further work could recover those too.
1261 while (isa<Instruction>(V)) {
1262 Instruction &VAsInst = *cast<Instruction>(V);
1263 // Temporary "0", awaiting real implementation.
1264 DIExpression *NewExpr = salvageDebugInfoImpl(VAsInst, Expr, StackValue, 0);
1265
1266 // If we cannot salvage any further, and haven't yet found a suitable debug
1267 // expression, bail out.
1268 if (!NewExpr)
1269 break;
1270
1271 // New value and expr now represent this debuginfo.
1272 V = VAsInst.getOperand(0);
1273 Expr = NewExpr;
1274
1275 // Some kind of simplification occurred: check whether the operand of the
1276 // salvaged debug expression can be encoded in this DAG.
1277 if (handleDebugValue(V, Var, Expr, DL, InstDL, SDOrder,
1278 /*IsVariadic=*/false)) {
1279 LLVM_DEBUG(dbgs() << "Salvaged debug location info for:\n "
1280 << DDI.getDI() << "\nBy stripping back to:\n " << V);
1281 return;
1282 }
1283 }
1284
1285 // This was the final opportunity to salvage this debug information, and it
1286 // couldn't be done. Place an undef DBG_VALUE at this location to terminate
1287 // any earlier variable location.
1288 auto Undef = UndefValue::get(DDI.getDI()->getValue(0)->getType());
1289 auto SDV = DAG.getConstantDbgValue(Var, Expr, Undef, DL, SDNodeOrder);
1290 DAG.AddDbgValue(SDV, false);
1291
1292 LLVM_DEBUG(dbgs() << "Dropping debug value info for:\n " << DDI.getDI()
1293 << "\n");
1294 LLVM_DEBUG(dbgs() << " Last seen at:\n " << *DDI.getDI()->getOperand(0)
1295 << "\n");
1296}
1297
1298bool SelectionDAGBuilder::handleDebugValue(ArrayRef<const Value *> Values,
1299 DILocalVariable *Var,
1300 DIExpression *Expr, DebugLoc dl,
1301 DebugLoc InstDL, unsigned Order,
1302 bool IsVariadic) {
1303 if (Values.empty())
1304 return true;
1305 SmallVector<SDDbgOperand> LocationOps;
1306 SmallVector<SDNode *> Dependencies;
1307 for (const Value *V : Values) {
1308 // Constant value.
1309 if (isa<ConstantInt>(V) || isa<ConstantFP>(V) || isa<UndefValue>(V) ||
1310 isa<ConstantPointerNull>(V)) {
1311 LocationOps.emplace_back(SDDbgOperand::fromConst(V));
1312 continue;
1313 }
1314
1315 // If the Value is a frame index, we can create a FrameIndex debug value
1316 // without relying on the DAG at all.
1317 if (const AllocaInst *AI = dyn_cast<AllocaInst>(V)) {
1318 auto SI = FuncInfo.StaticAllocaMap.find(AI);
1319 if (SI != FuncInfo.StaticAllocaMap.end()) {
1320 LocationOps.emplace_back(SDDbgOperand::fromFrameIdx(SI->second));
1321 continue;
1322 }
1323 }
1324
1325 // Do not use getValue() in here; we don't want to generate code at
1326 // this point if it hasn't been done yet.
1327 SDValue N = NodeMap[V];
1328 if (!N.getNode() && isa<Argument>(V)) // Check unused arguments map.
1329 N = UnusedArgNodeMap[V];
1330 if (N.getNode()) {
1331 // Only emit func arg dbg value for non-variadic dbg.values for now.
1332 if (!IsVariadic && EmitFuncArgumentDbgValue(V, Var, Expr, dl, false, N))
1333 return true;
1334 if (auto *FISDN = dyn_cast<FrameIndexSDNode>(N.getNode())) {
1335 // Construct a FrameIndexDbgValue for FrameIndexSDNodes so we can
1336 // describe stack slot locations.
1337 //
1338 // Consider "int x = 0; int *px = &x;". There are two kinds of
1339 // interesting debug values here after optimization:
1340 //
1341 // dbg.value(i32* %px, !"int *px", !DIExpression()), and
1342 // dbg.value(i32* %px, !"int x", !DIExpression(DW_OP_deref))
1343 //
1344 // Both describe the direct values of their associated variables.
1345 Dependencies.push_back(N.getNode());
1346 LocationOps.emplace_back(SDDbgOperand::fromFrameIdx(FISDN->getIndex()));
1347 continue;
1348 }
1349 LocationOps.emplace_back(
1350 SDDbgOperand::fromNode(N.getNode(), N.getResNo()));
1351 continue;
1352 }
1353
1354 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
1355 // Special rules apply for the first dbg.values of parameter variables in a
1356 // function. Identify them by the fact they reference Argument Values, that
1357 // they're parameters, and they are parameters of the current function. We
1358 // need to let them dangle until they get an SDNode.
1359 bool IsParamOfFunc =
1360 isa<Argument>(V) && Var->isParameter() && !InstDL.getInlinedAt();
1361 if (IsParamOfFunc)
1362 return false;
1363
1364 // The value is not used in this block yet (or it would have an SDNode).
1365 // We still want the value to appear for the user if possible -- if it has
1366 // an associated VReg, we can refer to that instead.
1367 auto VMI = FuncInfo.ValueMap.find(V);
1368 if (VMI != FuncInfo.ValueMap.end()) {
1369 unsigned Reg = VMI->second;
1370 // If this is a PHI node, it may be split up into several MI PHI nodes
1371 // (in FunctionLoweringInfo::set).
1372 RegsForValue RFV(V->getContext(), TLI, DAG.getDataLayout(), Reg,
1373 V->getType(), None);
1374 if (RFV.occupiesMultipleRegs()) {
1375 // FIXME: We could potentially support variadic dbg_values here.
1376 if (IsVariadic)
1377 return false;
1378 unsigned Offset = 0;
1379 unsigned BitsToDescribe = 0;
1380 if (auto VarSize = Var->getSizeInBits())
1381 BitsToDescribe = *VarSize;
1382 if (auto Fragment = Expr->getFragmentInfo())
1383 BitsToDescribe = Fragment->SizeInBits;
1384 for (auto RegAndSize : RFV.getRegsAndSizes()) {
1385 // Bail out if all bits are described already.
1386 if (Offset >= BitsToDescribe)
1387 break;
1388 // TODO: handle scalable vectors.
1389 unsigned RegisterSize = RegAndSize.second;
1390 unsigned FragmentSize = (Offset + RegisterSize > BitsToDescribe)
1391 ? BitsToDescribe - Offset
1392 : RegisterSize;
1393 auto FragmentExpr = DIExpression::createFragmentExpression(
1394 Expr, Offset, FragmentSize);
1395 if (!FragmentExpr)
1396 continue;
1397 SDDbgValue *SDV = DAG.getVRegDbgValue(
1398 Var, *FragmentExpr, RegAndSize.first, false, dl, SDNodeOrder);
1399 DAG.AddDbgValue(SDV, false);
1400 Offset += RegisterSize;
1401 }
1402 return true;
1403 }
1404 // We can use simple vreg locations for variadic dbg_values as well.
1405 LocationOps.emplace_back(SDDbgOperand::fromVReg(Reg));
1406 continue;
1407 }
1408 // We failed to create a SDDbgOperand for V.
1409 return false;
1410 }
1411
1412 // We have created a SDDbgOperand for each Value in Values.
1413 // Should use Order instead of SDNodeOrder?
1414 assert(!LocationOps.empty());
1415 SDDbgValue *SDV =
1416 DAG.getDbgValueList(Var, Expr, LocationOps, Dependencies,
1417 /*IsIndirect=*/false, dl, SDNodeOrder, IsVariadic);
1418 DAG.AddDbgValue(SDV, /*isParameter=*/false);
1419 return true;
1420}
1421
1422void SelectionDAGBuilder::resolveOrClearDbgInfo() {
1423 // Try to fixup any remaining dangling debug info -- and drop it if we can't.
1424 for (auto &Pair : DanglingDebugInfoMap)
1425 for (auto &DDI : Pair.second)
1426 salvageUnresolvedDbgValue(DDI);
1427 clearDanglingDebugInfo();
1428}
1429
1430/// getCopyFromRegs - If there was virtual register allocated for the value V
1431/// emit CopyFromReg of the specified type Ty. Return empty SDValue() otherwise.
1432SDValue SelectionDAGBuilder::getCopyFromRegs(const Value *V, Type *Ty) {
1433 DenseMap<const Value *, Register>::iterator It = FuncInfo.ValueMap.find(V);
1434 SDValue Result;
1435
1436 if (It != FuncInfo.ValueMap.end()) {
1437 Register InReg = It->second;
1438
1439 RegsForValue RFV(*DAG.getContext(), DAG.getTargetLoweringInfo(),
1440 DAG.getDataLayout(), InReg, Ty,
1441 None); // This is not an ABI copy.
1442 SDValue Chain = DAG.getEntryNode();
1443 Result = RFV.getCopyFromRegs(DAG, FuncInfo, getCurSDLoc(), Chain, nullptr,
1444 V);
1445 resolveDanglingDebugInfo(V, Result);
1446 }
1447
1448 return Result;
1449}
1450
1451/// getValue - Return an SDValue for the given Value.
1452SDValue SelectionDAGBuilder::getValue(const Value *V) {
1453 // If we already have an SDValue for this value, use it. It's important
1454 // to do this first, so that we don't create a CopyFromReg if we already
1455 // have a regular SDValue.
1456 SDValue &N = NodeMap[V];
1457 if (N.getNode()) return N;
1458
1459 // If there's a virtual register allocated and initialized for this
1460 // value, use it.
1461 if (SDValue copyFromReg = getCopyFromRegs(V, V->getType()))
1462 return copyFromReg;
1463
1464 // Otherwise create a new SDValue and remember it.
1465 SDValue Val = getValueImpl(V);
1466 NodeMap[V] = Val;
1467 resolveDanglingDebugInfo(V, Val);
1468 return Val;
1469}
1470
1471/// getNonRegisterValue - Return an SDValue for the given Value, but
1472/// don't look in FuncInfo.ValueMap for a virtual register.
1473SDValue SelectionDAGBuilder::getNonRegisterValue(const Value *V) {
1474 // If we already have an SDValue for this value, use it.
1475 SDValue &N = NodeMap[V];
1476 if (N.getNode()) {
1477 if (isa<ConstantSDNode>(N) || isa<ConstantFPSDNode>(N)) {
1478 // Remove the debug location from the node as the node is about to be used
1479 // in a location which may differ from the original debug location. This
1480 // is relevant to Constant and ConstantFP nodes because they can appear
1481 // as constant expressions inside PHI nodes.
1482 N->setDebugLoc(DebugLoc());
1483 }
1484 return N;
1485 }
1486
1487 // Otherwise create a new SDValue and remember it.
1488 SDValue Val = getValueImpl(V);
1489 NodeMap[V] = Val;
1490 resolveDanglingDebugInfo(V, Val);
1491 return Val;
1492}
1493
1494/// getValueImpl - Helper function for getValue and getNonRegisterValue.
1495/// Create an SDValue for the given value.
1496SDValue SelectionDAGBuilder::getValueImpl(const Value *V) {
1497 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
1498
1499 if (const Constant *C = dyn_cast<Constant>(V)) {
1500 EVT VT = TLI.getValueType(DAG.getDataLayout(), V->getType(), true);
1501
1502 if (const ConstantInt *CI = dyn_cast<ConstantInt>(C))
1503 return DAG.getConstant(*CI, getCurSDLoc(), VT);
1504
1505 if (const GlobalValue *GV = dyn_cast<GlobalValue>(C))
1506 return DAG.getGlobalAddress(GV, getCurSDLoc(), VT);
1507
1508 if (isa<ConstantPointerNull>(C)) {
1509 unsigned AS = V->getType()->getPointerAddressSpace();
1510 return DAG.getConstant(0, getCurSDLoc(),
1511 TLI.getPointerTy(DAG.getDataLayout(), AS));
1512 }
1513
1514 if (match(C, m_VScale(DAG.getDataLayout())))
1515 return DAG.getVScale(getCurSDLoc(), VT, APInt(VT.getSizeInBits(), 1));
1516
1517 if (const ConstantFP *CFP = dyn_cast<ConstantFP>(C))
1518 return DAG.getConstantFP(*CFP, getCurSDLoc(), VT);
1519
1520 if (isa<UndefValue>(C) && !V->getType()->isAggregateType())
1521 return DAG.getUNDEF(VT);
1522
1523 if (const ConstantExpr *CE = dyn_cast<ConstantExpr>(C)) {
1524 visit(CE->getOpcode(), *CE);
1525 SDValue N1 = NodeMap[V];
1526 assert(N1.getNode() && "visit didn't populate the NodeMap!");
1527 return N1;
1528 }
1529
1530 if (isa<ConstantStruct>(C) || isa<ConstantArray>(C)) {
1531 SmallVector<SDValue, 4> Constants;
1532 for (const Use &U : C->operands()) {
1533 SDNode *Val = getValue(U).getNode();
1534 // If the operand is an empty aggregate, there are no values.
1535 if (!Val) continue;
1536 // Add each leaf value from the operand to the Constants list
1537 // to form a flattened list of all the values.
1538 for (unsigned i = 0, e = Val->getNumValues(); i != e; ++i)
1539 Constants.push_back(SDValue(Val, i));
1540 }
1541
1542 return DAG.getMergeValues(Constants, getCurSDLoc());
1543 }
1544
1545 if (const ConstantDataSequential *CDS =
1546 dyn_cast<ConstantDataSequential>(C)) {
1547 SmallVector<SDValue, 4> Ops;
1548 for (unsigned i = 0, e = CDS->getNumElements(); i != e; ++i) {
1549 SDNode *Val = getValue(CDS->getElementAsConstant(i)).getNode();
1550 // Add each leaf value from the operand to the Constants list
1551 // to form a flattened list of all the values.
1552 for (unsigned i = 0, e = Val->getNumValues(); i != e; ++i)
1553 Ops.push_back(SDValue(Val, i));
1554 }
1555
1556 if (isa<ArrayType>(CDS->getType()))
1557 return DAG.getMergeValues(Ops, getCurSDLoc());
1558 return NodeMap[V] = DAG.getBuildVector(VT, getCurSDLoc(), Ops);
1559 }
1560
1561 if (C->getType()->isStructTy() || C->getType()->isArrayTy()) {
1562 assert((isa<ConstantAggregateZero>(C) || isa<UndefValue>(C)) &&
1563 "Unknown struct or array constant!");
1564
1565 SmallVector<EVT, 4> ValueVTs;
1566 ComputeValueVTs(TLI, DAG.getDataLayout(), C->getType(), ValueVTs);
1567 unsigned NumElts = ValueVTs.size();
1568 if (NumElts == 0)
1569 return SDValue(); // empty struct
1570 SmallVector<SDValue, 4> Constants(NumElts);
1571 for (unsigned i = 0; i != NumElts; ++i) {
1572 EVT EltVT = ValueVTs[i];
1573 if (isa<UndefValue>(C))
1574 Constants[i] = DAG.getUNDEF(EltVT);
1575 else if (EltVT.isFloatingPoint())
1576 Constants[i] = DAG.getConstantFP(0, getCurSDLoc(), EltVT);
1577 else
1578 Constants[i] = DAG.getConstant(0, getCurSDLoc(), EltVT);
1579 }
1580
1581 return DAG.getMergeValues(Constants, getCurSDLoc());
1582 }
1583
1584 if (const BlockAddress *BA = dyn_cast<BlockAddress>(C))
1585 return DAG.getBlockAddress(BA, VT);
1586
1587 if (const auto *Equiv = dyn_cast<DSOLocalEquivalent>(C))
1588 return getValue(Equiv->getGlobalValue());
1589
1590 VectorType *VecTy = cast<VectorType>(V->getType());
1591
1592 // Now that we know the number and type of the elements, get that number of
1593 // elements into the Ops array based on what kind of constant it is.
1594 if (const ConstantVector *CV = dyn_cast<ConstantVector>(C)) {
1595 SmallVector<SDValue, 16> Ops;
1596 unsigned NumElements = cast<FixedVectorType>(VecTy)->getNumElements();
1597 for (unsigned i = 0; i != NumElements; ++i)
1598 Ops.push_back(getValue(CV->getOperand(i)));
1599
1600 return NodeMap[V] = DAG.getBuildVector(VT, getCurSDLoc(), Ops);
1601 } else if (isa<ConstantAggregateZero>(C)) {
1602 EVT EltVT =
1603 TLI.getValueType(DAG.getDataLayout(), VecTy->getElementType());
1604
1605 SDValue Op;
1606 if (EltVT.isFloatingPoint())
1607 Op = DAG.getConstantFP(0, getCurSDLoc(), EltVT);
1608 else
1609 Op = DAG.getConstant(0, getCurSDLoc(), EltVT);
1610
1611 if (isa<ScalableVectorType>(VecTy))
1612 return NodeMap[V] = DAG.getSplatVector(VT, getCurSDLoc(), Op);
1613 else {
1614 SmallVector<SDValue, 16> Ops;
1615 Ops.assign(cast<FixedVectorType>(VecTy)->getNumElements(), Op);
1616 return NodeMap[V] = DAG.getBuildVector(VT, getCurSDLoc(), Ops);
1617 }
1618 }
1619 llvm_unreachable("Unknown vector constant");
1620 }
1621
1622 // If this is a static alloca, generate it as the frameindex instead of
1623 // computation.
1624 if (const AllocaInst *AI = dyn_cast<AllocaInst>(V)) {
1625 DenseMap<const AllocaInst*, int>::iterator SI =
1626 FuncInfo.StaticAllocaMap.find(AI);
1627 if (SI != FuncInfo.StaticAllocaMap.end())
1628 return DAG.getFrameIndex(SI->second,
1629 TLI.getFrameIndexTy(DAG.getDataLayout()));
1630 }
1631
1632 // If this is an instruction which fast-isel has deferred, select it now.
1633 if (const Instruction *Inst = dyn_cast<Instruction>(V)) {
1634 unsigned InReg = FuncInfo.InitializeRegForValue(Inst);
1635
1636 RegsForValue RFV(*DAG.getContext(), TLI, DAG.getDataLayout(), InReg,
1637 Inst->getType(), None);
1638 SDValue Chain = DAG.getEntryNode();
1639 return RFV.getCopyFromRegs(DAG, FuncInfo, getCurSDLoc(), Chain, nullptr, V);
1640 }
1641
1642 if (const MetadataAsValue *MD = dyn_cast<MetadataAsValue>(V)) {
1643 return DAG.getMDNode(cast<MDNode>(MD->getMetadata()));
1644 }
1645 llvm_unreachable("Can't get register for value!");
1646}
1647
1648void SelectionDAGBuilder::visitCatchPad(const CatchPadInst &I) {
1649 auto Pers = classifyEHPersonality(FuncInfo.Fn->getPersonalityFn());
1650 bool IsMSVCCXX = Pers == EHPersonality::MSVC_CXX;
1651 bool IsCoreCLR = Pers == EHPersonality::CoreCLR;
1652 bool IsSEH = isAsynchronousEHPersonality(Pers);
1653 MachineBasicBlock *CatchPadMBB = FuncInfo.MBB;
1654 if (!IsSEH)
1655 CatchPadMBB->setIsEHScopeEntry();
1656 // In MSVC C++ and CoreCLR, catchblocks are funclets and need prologues.
1657 if (IsMSVCCXX || IsCoreCLR)
1658 CatchPadMBB->setIsEHFuncletEntry();
1659}
1660
1661void SelectionDAGBuilder::visitCatchRet(const CatchReturnInst &I) {
1662 // Update machine-CFG edge.
1663 MachineBasicBlock *TargetMBB = FuncInfo.MBBMap[I.getSuccessor()];
1664 FuncInfo.MBB->addSuccessor(TargetMBB);
1665 TargetMBB->setIsEHCatchretTarget(true);
1666 DAG.getMachineFunction().setHasEHCatchret(true);
1667
1668 auto Pers = classifyEHPersonality(FuncInfo.Fn->getPersonalityFn());
1669 bool IsSEH = isAsynchronousEHPersonality(Pers);
1670 if (IsSEH) {
1671 // If this is not a fall-through branch or optimizations are switched off,
1672 // emit the branch.
1673 if (TargetMBB != NextBlock(FuncInfo.MBB) ||
1674 TM.getOptLevel() == CodeGenOpt::None)
1675 DAG.setRoot(DAG.getNode(ISD::BR, getCurSDLoc(), MVT::Other,
1676 getControlRoot(), DAG.getBasicBlock(TargetMBB)));
1677 return;
1678 }
1679
1680 // Figure out the funclet membership for the catchret's successor.
1681 // This will be used by the FuncletLayout pass to determine how to order the
1682 // BB's.
1683 // A 'catchret' returns to the outer scope's color.
1684 Value *ParentPad = I.getCatchSwitchParentPad();
1685 const BasicBlock *SuccessorColor;
1686 if (isa<ConstantTokenNone>(ParentPad))
1687 SuccessorColor = &FuncInfo.Fn->getEntryBlock();
1688 else
1689 SuccessorColor = cast<Instruction>(ParentPad)->getParent();
1690 assert(SuccessorColor && "No parent funclet for catchret!");
1691 MachineBasicBlock *SuccessorColorMBB = FuncInfo.MBBMap[SuccessorColor];
1692 assert(SuccessorColorMBB && "No MBB for SuccessorColor!");
1693
1694 // Create the terminator node.
1695 SDValue Ret = DAG.getNode(ISD::CATCHRET, getCurSDLoc(), MVT::Other,
1696 getControlRoot(), DAG.getBasicBlock(TargetMBB),
1697 DAG.getBasicBlock(SuccessorColorMBB));
1698 DAG.setRoot(Ret);
1699}
1700
1701void SelectionDAGBuilder::visitCleanupPad(const CleanupPadInst &CPI) {
1702 // Don't emit any special code for the cleanuppad instruction. It just marks
1703 // the start of an EH scope/funclet.
1704 FuncInfo.MBB->setIsEHScopeEntry();
1705 auto Pers = classifyEHPersonality(FuncInfo.Fn->getPersonalityFn());
1706 if (Pers != EHPersonality::Wasm_CXX) {
1707 FuncInfo.MBB->setIsEHFuncletEntry();
1708 FuncInfo.MBB->setIsCleanupFuncletEntry();
1709 }
1710}
1711
1712// In wasm EH, even though a catchpad may not catch an exception if a tag does
1713// not match, it is OK to add only the first unwind destination catchpad to the
1714// successors, because there will be at least one invoke instruction within the
1715// catch scope that points to the next unwind destination, if one exists, so
1716// CFGSort cannot mess up with BB sorting order.
1717// (All catchpads with 'catch (type)' clauses have a 'llvm.rethrow' intrinsic
1718// call within them, and catchpads only consisting of 'catch (...)' have a
1719// '__cxa_end_catch' call within them, both of which generate invokes in case
1720// the next unwind destination exists, i.e., the next unwind destination is not
1721// the caller.)
1722//
1723// Having at most one EH pad successor is also simpler and helps later
1724// transformations.
1725//
1726// For example,
1727// current:
1728// invoke void @foo to ... unwind label %catch.dispatch
1729// catch.dispatch:
1730// %0 = catchswitch within ... [label %catch.start] unwind label %next
1731// catch.start:
1732// ...
1733// ... in this BB or some other child BB dominated by this BB there will be an
1734// invoke that points to 'next' BB as an unwind destination
1735//
1736// next: ; We don't need to add this to 'current' BB's successor
1737// ...
1738static void findWasmUnwindDestinations(
1739 FunctionLoweringInfo &FuncInfo, const BasicBlock *EHPadBB,
1740 BranchProbability Prob,
1741 SmallVectorImpl<std::pair<MachineBasicBlock *, BranchProbability>>
1742 &UnwindDests) {
1743 while (EHPadBB) {
1744 const Instruction *Pad = EHPadBB->getFirstNonPHI();
1745 if (isa<CleanupPadInst>(Pad)) {
1746 // Stop on cleanup pads.
1747 UnwindDests.emplace_back(FuncInfo.MBBMap[EHPadBB], Prob);
1748 UnwindDests.back().first->setIsEHScopeEntry();
1749 break;
1750 } else if (auto *CatchSwitch = dyn_cast<CatchSwitchInst>(Pad)) {
1751 // Add the catchpad handlers to the possible destinations. We don't
1752 // continue to the unwind destination of the catchswitch for wasm.
1753 for (const BasicBlock *CatchPadBB : CatchSwitch->handlers()) {
1754 UnwindDests.emplace_back(FuncInfo.MBBMap[CatchPadBB], Prob);
1755 UnwindDests.back().first->setIsEHScopeEntry();
1756 }
1757 break;
1758 } else {
1759 continue;
1760 }
1761 }
1762}
1763
1764/// When an invoke or a cleanupret unwinds to the next EH pad, there are
1765/// many places it could ultimately go. In the IR, we have a single unwind
1766/// destination, but in the machine CFG, we enumerate all the possible blocks.
1767/// This function skips over imaginary basic blocks that hold catchswitch
1768/// instructions, and finds all the "real" machine
1769/// basic block destinations. As those destinations may not be successors of
1770/// EHPadBB, here we also calculate the edge probability to those destinations.
1771/// The passed-in Prob is the edge probability to EHPadBB.
1772static void findUnwindDestinations(
1773 FunctionLoweringInfo &FuncInfo, const BasicBlock *EHPadBB,
1774 BranchProbability Prob,
1775 SmallVectorImpl<std::pair<MachineBasicBlock *, BranchProbability>>
1776 &UnwindDests) {
1777 EHPersonality Personality =
1778 classifyEHPersonality(FuncInfo.Fn->getPersonalityFn());
1779 bool IsMSVCCXX = Personality == EHPersonality::MSVC_CXX;
1780 bool IsCoreCLR = Personality == EHPersonality::CoreCLR;
1781 bool IsWasmCXX = Personality == EHPersonality::Wasm_CXX;
1782 bool IsSEH = isAsynchronousEHPersonality(Personality);
1783
1784 if (IsWasmCXX) {
1785 findWasmUnwindDestinations(FuncInfo, EHPadBB, Prob, UnwindDests);
1786 assert(UnwindDests.size() <= 1 &&
1787 "There should be at most one unwind destination for wasm");
1788 return;
1789 }
1790
1791 while (EHPadBB) {
1792 const Instruction *Pad = EHPadBB->getFirstNonPHI();
1793 BasicBlock *NewEHPadBB = nullptr;
1794 if (isa<LandingPadInst>(Pad)) {
1795 // Stop on landingpads. They are not funclets.
1796 UnwindDests.emplace_back(FuncInfo.MBBMap[EHPadBB], Prob);
1797 break;
1798 } else if (isa<CleanupPadInst>(Pad)) {
1799 // Stop on cleanup pads. Cleanups are always funclet entries for all known
1800 // personalities.
1801 UnwindDests.emplace_back(FuncInfo.MBBMap[EHPadBB], Prob);
1802 UnwindDests.back().first->setIsEHScopeEntry();
1803 UnwindDests.back().first->setIsEHFuncletEntry();
1804 break;
1805 } else if (auto *CatchSwitch = dyn_cast<CatchSwitchInst>(Pad)) {
1806 // Add the catchpad handlers to the possible destinations.
1807 for (const BasicBlock *CatchPadBB : CatchSwitch->handlers()) {
1808 UnwindDests.emplace_back(FuncInfo.MBBMap[CatchPadBB], Prob);
1809 // For MSVC++ and the CLR, catchblocks are funclets and need prologues.
1810 if (IsMSVCCXX || IsCoreCLR)
1811 UnwindDests.back().first->setIsEHFuncletEntry();
1812 if (!IsSEH)
1813 UnwindDests.back().first->setIsEHScopeEntry();
1814 }
1815 NewEHPadBB = CatchSwitch->getUnwindDest();
1816 } else {
1817 continue;
1818 }
1819
1820 BranchProbabilityInfo *BPI = FuncInfo.BPI;
1821 if (BPI && NewEHPadBB)
1822 Prob *= BPI->getEdgeProbability(EHPadBB, NewEHPadBB);
1823 EHPadBB = NewEHPadBB;
1824 }
1825}
1826
1827void SelectionDAGBuilder::visitCleanupRet(const CleanupReturnInst &I) {
1828 // Update successor info.
1829 SmallVector<std::pair<MachineBasicBlock *, BranchProbability>, 1> UnwindDests;
1830 auto UnwindDest = I.getUnwindDest();
1831 BranchProbabilityInfo *BPI = FuncInfo.BPI;
1832 BranchProbability UnwindDestProb =
1833 (BPI && UnwindDest)
1834 ? BPI->getEdgeProbability(FuncInfo.MBB->getBasicBlock(), UnwindDest)
1835 : BranchProbability::getZero();
1836 findUnwindDestinations(FuncInfo, UnwindDest, UnwindDestProb, UnwindDests);
1837 for (auto &UnwindDest : UnwindDests) {
1838 UnwindDest.first->setIsEHPad();
1839 addSuccessorWithProb(FuncInfo.MBB, UnwindDest.first, UnwindDest.second);
1840 }
1841 FuncInfo.MBB->normalizeSuccProbs();
1842
1843 // Create the terminator node.
1844 SDValue Ret =
1845 DAG.getNode(ISD::CLEANUPRET, getCurSDLoc(), MVT::Other, getControlRoot());
1846 DAG.setRoot(Ret);
1847}
1848
1849void SelectionDAGBuilder::visitCatchSwitch(const CatchSwitchInst &CSI) {
1850 report_fatal_error("visitCatchSwitch not yet implemented!");
1851}
1852
1853void SelectionDAGBuilder::visitRet(const ReturnInst &I) {
1854 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
1855 auto &DL = DAG.getDataLayout();
1856 SDValue Chain = getControlRoot();
1857 SmallVector<ISD::OutputArg, 8> Outs;
1858 SmallVector<SDValue, 8> OutVals;
1859
1860 // Calls to @llvm.experimental.deoptimize don't generate a return value, so
1861 // lower
1862 //
1863 // %val = call <ty> @llvm.experimental.deoptimize()
1864 // ret <ty> %val
1865 //
1866 // differently.
1867 if (I.getParent()->getTerminatingDeoptimizeCall()) {
1868 LowerDeoptimizingReturn();
1869 return;
1870 }
1871
1872 if (!FuncInfo.CanLowerReturn) {
1873 unsigned DemoteReg = FuncInfo.DemoteRegister;
1874 const Function *F = I.getParent()->getParent();
1875
1876 // Emit a store of the return value through the virtual register.
1877 // Leave Outs empty so that LowerReturn won't try to load return
1878 // registers the usual way.
1879 SmallVector<EVT, 1> PtrValueVTs;
1880 ComputeValueVTs(TLI, DL,
1881 F->getReturnType()->getPointerTo(
1882 DAG.getDataLayout().getAllocaAddrSpace()),
1883 PtrValueVTs);
1884
1885 SDValue RetPtr = DAG.getCopyFromReg(DAG.getEntryNode(), getCurSDLoc(),
1886 DemoteReg, PtrValueVTs[0]);
1887 SDValue RetOp = getValue(I.getOperand(0));
1888
1889 SmallVector<EVT, 4> ValueVTs, MemVTs;
1890 SmallVector<uint64_t, 4> Offsets;
1891 ComputeValueVTs(TLI, DL, I.getOperand(0)->getType(), ValueVTs, &MemVTs,
1892 &Offsets);
1893 unsigned NumValues = ValueVTs.size();
1894
1895 SmallVector<SDValue, 4> Chains(NumValues);
1896 Align BaseAlign = DL.getPrefTypeAlign(I.getOperand(0)->getType());
1897 for (unsigned i = 0; i != NumValues; ++i) {
1898 // An aggregate return value cannot wrap around the address space, so
1899 // offsets to its parts don't wrap either.
1900 SDValue Ptr = DAG.getObjectPtrOffset(getCurSDLoc(), RetPtr,
1901 TypeSize::Fixed(Offsets[i]));
1902
1903 SDValue Val = RetOp.getValue(RetOp.getResNo() + i);
1904 if (MemVTs[i] != ValueVTs[i])
1905 Val = DAG.