LLVM 19.0.0git
SelectionDAGBuilder.cpp
Go to the documentation of this file.
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/STLExtras.h"
20#include "llvm/ADT/SmallSet.h"
21#include "llvm/ADT/StringRef.h"
22#include "llvm/ADT/Twine.h"
26#include "llvm/Analysis/Loads.h"
58#include "llvm/IR/Argument.h"
59#include "llvm/IR/Attributes.h"
60#include "llvm/IR/BasicBlock.h"
61#include "llvm/IR/CFG.h"
62#include "llvm/IR/CallingConv.h"
63#include "llvm/IR/Constant.h"
65#include "llvm/IR/Constants.h"
66#include "llvm/IR/DataLayout.h"
67#include "llvm/IR/DebugInfo.h"
72#include "llvm/IR/Function.h"
74#include "llvm/IR/InlineAsm.h"
75#include "llvm/IR/InstrTypes.h"
78#include "llvm/IR/Intrinsics.h"
79#include "llvm/IR/IntrinsicsAArch64.h"
80#include "llvm/IR/IntrinsicsAMDGPU.h"
81#include "llvm/IR/IntrinsicsWebAssembly.h"
82#include "llvm/IR/LLVMContext.h"
84#include "llvm/IR/Metadata.h"
85#include "llvm/IR/Module.h"
86#include "llvm/IR/Operator.h"
88#include "llvm/IR/Statepoint.h"
89#include "llvm/IR/Type.h"
90#include "llvm/IR/User.h"
91#include "llvm/IR/Value.h"
92#include "llvm/MC/MCContext.h"
97#include "llvm/Support/Debug.h"
106#include <cstddef>
107#include <iterator>
108#include <limits>
109#include <optional>
110#include <tuple>
111
112using namespace llvm;
113using namespace PatternMatch;
114using namespace SwitchCG;
115
116#define DEBUG_TYPE "isel"
117
118/// LimitFloatPrecision - Generate low-precision inline sequences for
119/// some float libcalls (6, 8 or 12 bits).
120static unsigned LimitFloatPrecision;
121
122static cl::opt<bool>
123 InsertAssertAlign("insert-assert-align", cl::init(true),
124 cl::desc("Insert the experimental `assertalign` node."),
126
128 LimitFPPrecision("limit-float-precision",
129 cl::desc("Generate low-precision inline sequences "
130 "for some float libcalls"),
132 cl::init(0));
133
135 "switch-peel-threshold", cl::Hidden, cl::init(66),
136 cl::desc("Set the case probability threshold for peeling the case from a "
137 "switch statement. A value greater than 100 will void this "
138 "optimization"));
139
140// Limit the width of DAG chains. This is important in general to prevent
141// DAG-based analysis from blowing up. For example, alias analysis and
142// load clustering may not complete in reasonable time. It is difficult to
143// recognize and avoid this situation within each individual analysis, and
144// future analyses are likely to have the same behavior. Limiting DAG width is
145// the safe approach and will be especially important with global DAGs.
146//
147// MaxParallelChains default is arbitrarily high to avoid affecting
148// optimization, but could be lowered to improve compile time. Any ld-ld-st-st
149// sequence over this should have been converted to llvm.memcpy by the
150// frontend. It is easy to induce this behavior with .ll code such as:
151// %buffer = alloca [4096 x i8]
152// %data = load [4096 x i8]* %argPtr
153// store [4096 x i8] %data, [4096 x i8]* %buffer
154static const unsigned MaxParallelChains = 64;
155
157 const SDValue *Parts, unsigned NumParts,
158 MVT PartVT, EVT ValueVT, const Value *V,
159 SDValue InChain,
160 std::optional<CallingConv::ID> CC);
161
162/// getCopyFromParts - Create a value that contains the specified legal parts
163/// combined into the value they represent. If the parts combine to a type
164/// larger than ValueVT then AssertOp can be used to specify whether the extra
165/// bits are known to be zero (ISD::AssertZext) or sign extended from ValueVT
166/// (ISD::AssertSext).
167static SDValue
168getCopyFromParts(SelectionDAG &DAG, const SDLoc &DL, const SDValue *Parts,
169 unsigned NumParts, MVT PartVT, EVT ValueVT, const Value *V,
170 SDValue InChain,
171 std::optional<CallingConv::ID> CC = std::nullopt,
172 std::optional<ISD::NodeType> AssertOp = std::nullopt) {
173 // Let the target assemble the parts if it wants to
174 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
175 if (SDValue Val = TLI.joinRegisterPartsIntoValue(DAG, DL, Parts, NumParts,
176 PartVT, ValueVT, CC))
177 return Val;
178
179 if (ValueVT.isVector())
180 return getCopyFromPartsVector(DAG, DL, Parts, NumParts, PartVT, ValueVT, V,
181 InChain, CC);
182
183 assert(NumParts > 0 && "No parts to assemble!");
184 SDValue Val = Parts[0];
185
186 if (NumParts > 1) {
187 // Assemble the value from multiple parts.
188 if (ValueVT.isInteger()) {
189 unsigned PartBits = PartVT.getSizeInBits();
190 unsigned ValueBits = ValueVT.getSizeInBits();
191
192 // Assemble the power of 2 part.
193 unsigned RoundParts = llvm::bit_floor(NumParts);
194 unsigned RoundBits = PartBits * RoundParts;
195 EVT RoundVT = RoundBits == ValueBits ?
196 ValueVT : EVT::getIntegerVT(*DAG.getContext(), RoundBits);
197 SDValue Lo, Hi;
198
199 EVT HalfVT = EVT::getIntegerVT(*DAG.getContext(), RoundBits/2);
200
201 if (RoundParts > 2) {
202 Lo = getCopyFromParts(DAG, DL, Parts, RoundParts / 2, PartVT, HalfVT, V,
203 InChain);
204 Hi = getCopyFromParts(DAG, DL, Parts + RoundParts / 2, RoundParts / 2,
205 PartVT, HalfVT, V, InChain);
206 } else {
207 Lo = DAG.getNode(ISD::BITCAST, DL, HalfVT, Parts[0]);
208 Hi = DAG.getNode(ISD::BITCAST, DL, HalfVT, Parts[1]);
209 }
210
211 if (DAG.getDataLayout().isBigEndian())
212 std::swap(Lo, Hi);
213
214 Val = DAG.getNode(ISD::BUILD_PAIR, DL, RoundVT, Lo, Hi);
215
216 if (RoundParts < NumParts) {
217 // Assemble the trailing non-power-of-2 part.
218 unsigned OddParts = NumParts - RoundParts;
219 EVT OddVT = EVT::getIntegerVT(*DAG.getContext(), OddParts * PartBits);
220 Hi = getCopyFromParts(DAG, DL, Parts + RoundParts, OddParts, PartVT,
221 OddVT, V, InChain, CC);
222
223 // Combine the round and odd parts.
224 Lo = Val;
225 if (DAG.getDataLayout().isBigEndian())
226 std::swap(Lo, Hi);
227 EVT TotalVT = EVT::getIntegerVT(*DAG.getContext(), NumParts * PartBits);
228 Hi = DAG.getNode(ISD::ANY_EXTEND, DL, TotalVT, Hi);
229 Hi = DAG.getNode(ISD::SHL, DL, TotalVT, Hi,
230 DAG.getConstant(Lo.getValueSizeInBits(), DL,
232 TotalVT, DAG.getDataLayout())));
233 Lo = DAG.getNode(ISD::ZERO_EXTEND, DL, TotalVT, Lo);
234 Val = DAG.getNode(ISD::OR, DL, TotalVT, Lo, Hi);
235 }
236 } else if (PartVT.isFloatingPoint()) {
237 // FP split into multiple FP parts (for ppcf128)
238 assert(ValueVT == EVT(MVT::ppcf128) && PartVT == MVT::f64 &&
239 "Unexpected split");
240 SDValue Lo, Hi;
241 Lo = DAG.getNode(ISD::BITCAST, DL, EVT(MVT::f64), Parts[0]);
242 Hi = DAG.getNode(ISD::BITCAST, DL, EVT(MVT::f64), Parts[1]);
243 if (TLI.hasBigEndianPartOrdering(ValueVT, DAG.getDataLayout()))
244 std::swap(Lo, Hi);
245 Val = DAG.getNode(ISD::BUILD_PAIR, DL, ValueVT, Lo, Hi);
246 } else {
247 // FP split into integer parts (soft fp)
248 assert(ValueVT.isFloatingPoint() && PartVT.isInteger() &&
249 !PartVT.isVector() && "Unexpected split");
250 EVT IntVT = EVT::getIntegerVT(*DAG.getContext(), ValueVT.getSizeInBits());
251 Val = getCopyFromParts(DAG, DL, Parts, NumParts, PartVT, IntVT, V,
252 InChain, CC);
253 }
254 }
255
256 // There is now one part, held in Val. Correct it to match ValueVT.
257 // PartEVT is the type of the register class that holds the value.
258 // ValueVT is the type of the inline asm operation.
259 EVT PartEVT = Val.getValueType();
260
261 if (PartEVT == ValueVT)
262 return Val;
263
264 if (PartEVT.isInteger() && ValueVT.isFloatingPoint() &&
265 ValueVT.bitsLT(PartEVT)) {
266 // For an FP value in an integer part, we need to truncate to the right
267 // width first.
268 PartEVT = EVT::getIntegerVT(*DAG.getContext(), ValueVT.getSizeInBits());
269 Val = DAG.getNode(ISD::TRUNCATE, DL, PartEVT, Val);
270 }
271
272 // Handle types that have the same size.
273 if (PartEVT.getSizeInBits() == ValueVT.getSizeInBits())
274 return DAG.getNode(ISD::BITCAST, DL, ValueVT, Val);
275
276 // Handle types with different sizes.
277 if (PartEVT.isInteger() && ValueVT.isInteger()) {
278 if (ValueVT.bitsLT(PartEVT)) {
279 // For a truncate, see if we have any information to
280 // indicate whether the truncated bits will always be
281 // zero or sign-extension.
282 if (AssertOp)
283 Val = DAG.getNode(*AssertOp, DL, PartEVT, Val,
284 DAG.getValueType(ValueVT));
285 return DAG.getNode(ISD::TRUNCATE, DL, ValueVT, Val);
286 }
287 return DAG.getNode(ISD::ANY_EXTEND, DL, ValueVT, Val);
288 }
289
290 if (PartEVT.isFloatingPoint() && ValueVT.isFloatingPoint()) {
291 // FP_ROUND's are always exact here.
292 if (ValueVT.bitsLT(Val.getValueType())) {
293
294 SDValue NoChange =
296
298 llvm::Attribute::StrictFP)) {
299 return DAG.getNode(ISD::STRICT_FP_ROUND, DL,
300 DAG.getVTList(ValueVT, MVT::Other), InChain, Val,
301 NoChange);
302 }
303
304 return DAG.getNode(ISD::FP_ROUND, DL, ValueVT, Val, NoChange);
305 }
306
307 return DAG.getNode(ISD::FP_EXTEND, DL, ValueVT, Val);
308 }
309
310 // Handle MMX to a narrower integer type by bitcasting MMX to integer and
311 // then truncating.
312 if (PartEVT == MVT::x86mmx && ValueVT.isInteger() &&
313 ValueVT.bitsLT(PartEVT)) {
314 Val = DAG.getNode(ISD::BITCAST, DL, MVT::i64, Val);
315 return DAG.getNode(ISD::TRUNCATE, DL, ValueVT, Val);
316 }
317
318 report_fatal_error("Unknown mismatch in getCopyFromParts!");
319}
320
322 const Twine &ErrMsg) {
323 const Instruction *I = dyn_cast_or_null<Instruction>(V);
324 if (!V)
325 return Ctx.emitError(ErrMsg);
326
327 const char *AsmError = ", possible invalid constraint for vector type";
328 if (const CallInst *CI = dyn_cast<CallInst>(I))
329 if (CI->isInlineAsm())
330 return Ctx.emitError(I, ErrMsg + AsmError);
331
332 return Ctx.emitError(I, ErrMsg);
333}
334
335/// getCopyFromPartsVector - Create a value that contains the specified legal
336/// parts combined into the value they represent. If the parts combine to a
337/// type larger than ValueVT then AssertOp can be used to specify whether the
338/// extra bits are known to be zero (ISD::AssertZext) or sign extended from
339/// ValueVT (ISD::AssertSext).
341 const SDValue *Parts, unsigned NumParts,
342 MVT PartVT, EVT ValueVT, const Value *V,
343 SDValue InChain,
344 std::optional<CallingConv::ID> CallConv) {
345 assert(ValueVT.isVector() && "Not a vector value");
346 assert(NumParts > 0 && "No parts to assemble!");
347 const bool IsABIRegCopy = CallConv.has_value();
348
349 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
350 SDValue Val = Parts[0];
351
352 // Handle a multi-element vector.
353 if (NumParts > 1) {
354 EVT IntermediateVT;
355 MVT RegisterVT;
356 unsigned NumIntermediates;
357 unsigned NumRegs;
358
359 if (IsABIRegCopy) {
361 *DAG.getContext(), *CallConv, ValueVT, IntermediateVT,
362 NumIntermediates, RegisterVT);
363 } else {
364 NumRegs =
365 TLI.getVectorTypeBreakdown(*DAG.getContext(), ValueVT, IntermediateVT,
366 NumIntermediates, RegisterVT);
367 }
368
369 assert(NumRegs == NumParts && "Part count doesn't match vector breakdown!");
370 NumParts = NumRegs; // Silence a compiler warning.
371 assert(RegisterVT == PartVT && "Part type doesn't match vector breakdown!");
372 assert(RegisterVT.getSizeInBits() ==
373 Parts[0].getSimpleValueType().getSizeInBits() &&
374 "Part type sizes don't match!");
375
376 // Assemble the parts into intermediate operands.
377 SmallVector<SDValue, 8> Ops(NumIntermediates);
378 if (NumIntermediates == NumParts) {
379 // If the register was not expanded, truncate or copy the value,
380 // as appropriate.
381 for (unsigned i = 0; i != NumParts; ++i)
382 Ops[i] = getCopyFromParts(DAG, DL, &Parts[i], 1, PartVT, IntermediateVT,
383 V, InChain, CallConv);
384 } else if (NumParts > 0) {
385 // If the intermediate type was expanded, build the intermediate
386 // operands from the parts.
387 assert(NumParts % NumIntermediates == 0 &&
388 "Must expand into a divisible number of parts!");
389 unsigned Factor = NumParts / NumIntermediates;
390 for (unsigned i = 0; i != NumIntermediates; ++i)
391 Ops[i] = getCopyFromParts(DAG, DL, &Parts[i * Factor], Factor, PartVT,
392 IntermediateVT, V, InChain, CallConv);
393 }
394
395 // Build a vector with BUILD_VECTOR or CONCAT_VECTORS from the
396 // intermediate operands.
397 EVT BuiltVectorTy =
398 IntermediateVT.isVector()
400 *DAG.getContext(), IntermediateVT.getScalarType(),
401 IntermediateVT.getVectorElementCount() * NumParts)
403 IntermediateVT.getScalarType(),
404 NumIntermediates);
405 Val = DAG.getNode(IntermediateVT.isVector() ? ISD::CONCAT_VECTORS
407 DL, BuiltVectorTy, Ops);
408 }
409
410 // There is now one part, held in Val. Correct it to match ValueVT.
411 EVT PartEVT = Val.getValueType();
412
413 if (PartEVT == ValueVT)
414 return Val;
415
416 if (PartEVT.isVector()) {
417 // Vector/Vector bitcast.
418 if (ValueVT.getSizeInBits() == PartEVT.getSizeInBits())
419 return DAG.getNode(ISD::BITCAST, DL, ValueVT, Val);
420
421 // If the parts vector has more elements than the value vector, then we
422 // have a vector widening case (e.g. <2 x float> -> <4 x float>).
423 // Extract the elements we want.
424 if (PartEVT.getVectorElementCount() != ValueVT.getVectorElementCount()) {
427 (PartEVT.getVectorElementCount().isScalable() ==
428 ValueVT.getVectorElementCount().isScalable()) &&
429 "Cannot narrow, it would be a lossy transformation");
430 PartEVT =
432 ValueVT.getVectorElementCount());
433 Val = DAG.getNode(ISD::EXTRACT_SUBVECTOR, DL, PartEVT, Val,
434 DAG.getVectorIdxConstant(0, DL));
435 if (PartEVT == ValueVT)
436 return Val;
437 if (PartEVT.isInteger() && ValueVT.isFloatingPoint())
438 return DAG.getNode(ISD::BITCAST, DL, ValueVT, Val);
439
440 // Vector/Vector bitcast (e.g. <2 x bfloat> -> <2 x half>).
441 if (ValueVT.getSizeInBits() == PartEVT.getSizeInBits())
442 return DAG.getNode(ISD::BITCAST, DL, ValueVT, Val);
443 }
444
445 // Promoted vector extract
446 return DAG.getAnyExtOrTrunc(Val, DL, ValueVT);
447 }
448
449 // Trivial bitcast if the types are the same size and the destination
450 // vector type is legal.
451 if (PartEVT.getSizeInBits() == ValueVT.getSizeInBits() &&
452 TLI.isTypeLegal(ValueVT))
453 return DAG.getNode(ISD::BITCAST, DL, ValueVT, Val);
454
455 if (ValueVT.getVectorNumElements() != 1) {
456 // Certain ABIs require that vectors are passed as integers. For vectors
457 // are the same size, this is an obvious bitcast.
458 if (ValueVT.getSizeInBits() == PartEVT.getSizeInBits()) {
459 return DAG.getNode(ISD::BITCAST, DL, ValueVT, Val);
460 } else if (ValueVT.bitsLT(PartEVT)) {
461 const uint64_t ValueSize = ValueVT.getFixedSizeInBits();
462 EVT IntermediateType = EVT::getIntegerVT(*DAG.getContext(), ValueSize);
463 // Drop the extra bits.
464 Val = DAG.getNode(ISD::TRUNCATE, DL, IntermediateType, Val);
465 return DAG.getBitcast(ValueVT, Val);
466 }
467
469 *DAG.getContext(), V, "non-trivial scalar-to-vector conversion");
470 return DAG.getUNDEF(ValueVT);
471 }
472
473 // Handle cases such as i8 -> <1 x i1>
474 EVT ValueSVT = ValueVT.getVectorElementType();
475 if (ValueVT.getVectorNumElements() == 1 && ValueSVT != PartEVT) {
476 unsigned ValueSize = ValueSVT.getSizeInBits();
477 if (ValueSize == PartEVT.getSizeInBits()) {
478 Val = DAG.getNode(ISD::BITCAST, DL, ValueSVT, Val);
479 } else if (ValueSVT.isFloatingPoint() && PartEVT.isInteger()) {
480 // It's possible a scalar floating point type gets softened to integer and
481 // then promoted to a larger integer. If PartEVT is the larger integer
482 // we need to truncate it and then bitcast to the FP type.
483 assert(ValueSVT.bitsLT(PartEVT) && "Unexpected types");
484 EVT IntermediateType = EVT::getIntegerVT(*DAG.getContext(), ValueSize);
485 Val = DAG.getNode(ISD::TRUNCATE, DL, IntermediateType, Val);
486 Val = DAG.getBitcast(ValueSVT, Val);
487 } else {
488 Val = ValueVT.isFloatingPoint()
489 ? DAG.getFPExtendOrRound(Val, DL, ValueSVT)
490 : DAG.getAnyExtOrTrunc(Val, DL, ValueSVT);
491 }
492 }
493
494 return DAG.getBuildVector(ValueVT, DL, Val);
495}
496
497static void getCopyToPartsVector(SelectionDAG &DAG, const SDLoc &dl,
498 SDValue Val, SDValue *Parts, unsigned NumParts,
499 MVT PartVT, const Value *V,
500 std::optional<CallingConv::ID> CallConv);
501
502/// getCopyToParts - Create a series of nodes that contain the specified value
503/// split into legal parts. If the parts contain more bits than Val, then, for
504/// integers, ExtendKind can be used to specify how to generate the extra bits.
505static void
507 unsigned NumParts, MVT PartVT, const Value *V,
508 std::optional<CallingConv::ID> CallConv = std::nullopt,
509 ISD::NodeType ExtendKind = ISD::ANY_EXTEND) {
510 // Let the target split the parts if it wants to
511 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
512 if (TLI.splitValueIntoRegisterParts(DAG, DL, Val, Parts, NumParts, PartVT,
513 CallConv))
514 return;
515 EVT ValueVT = Val.getValueType();
516
517 // Handle the vector case separately.
518 if (ValueVT.isVector())
519 return getCopyToPartsVector(DAG, DL, Val, Parts, NumParts, PartVT, V,
520 CallConv);
521
522 unsigned OrigNumParts = NumParts;
524 "Copying to an illegal type!");
525
526 if (NumParts == 0)
527 return;
528
529 assert(!ValueVT.isVector() && "Vector case handled elsewhere");
530 EVT PartEVT = PartVT;
531 if (PartEVT == ValueVT) {
532 assert(NumParts == 1 && "No-op copy with multiple parts!");
533 Parts[0] = Val;
534 return;
535 }
536
537 unsigned PartBits = PartVT.getSizeInBits();
538 if (NumParts * PartBits > ValueVT.getSizeInBits()) {
539 // If the parts cover more bits than the value has, promote the value.
540 if (PartVT.isFloatingPoint() && ValueVT.isFloatingPoint()) {
541 assert(NumParts == 1 && "Do not know what to promote to!");
542 Val = DAG.getNode(ISD::FP_EXTEND, DL, PartVT, Val);
543 } else {
544 if (ValueVT.isFloatingPoint()) {
545 // FP values need to be bitcast, then extended if they are being put
546 // into a larger container.
547 ValueVT = EVT::getIntegerVT(*DAG.getContext(), ValueVT.getSizeInBits());
548 Val = DAG.getNode(ISD::BITCAST, DL, ValueVT, Val);
549 }
550 assert((PartVT.isInteger() || PartVT == MVT::x86mmx) &&
551 ValueVT.isInteger() &&
552 "Unknown mismatch!");
553 ValueVT = EVT::getIntegerVT(*DAG.getContext(), NumParts * PartBits);
554 Val = DAG.getNode(ExtendKind, DL, ValueVT, Val);
555 if (PartVT == MVT::x86mmx)
556 Val = DAG.getNode(ISD::BITCAST, DL, PartVT, Val);
557 }
558 } else if (PartBits == ValueVT.getSizeInBits()) {
559 // Different types of the same size.
560 assert(NumParts == 1 && PartEVT != ValueVT);
561 Val = DAG.getNode(ISD::BITCAST, DL, PartVT, Val);
562 } else if (NumParts * PartBits < ValueVT.getSizeInBits()) {
563 // If the parts cover less bits than value has, truncate the value.
564 assert((PartVT.isInteger() || PartVT == MVT::x86mmx) &&
565 ValueVT.isInteger() &&
566 "Unknown mismatch!");
567 ValueVT = EVT::getIntegerVT(*DAG.getContext(), NumParts * PartBits);
568 Val = DAG.getNode(ISD::TRUNCATE, DL, ValueVT, Val);
569 if (PartVT == MVT::x86mmx)
570 Val = DAG.getNode(ISD::BITCAST, DL, PartVT, Val);
571 }
572
573 // The value may have changed - recompute ValueVT.
574 ValueVT = Val.getValueType();
575 assert(NumParts * PartBits == ValueVT.getSizeInBits() &&
576 "Failed to tile the value with PartVT!");
577
578 if (NumParts == 1) {
579 if (PartEVT != ValueVT) {
581 "scalar-to-vector conversion failed");
582 Val = DAG.getNode(ISD::BITCAST, DL, PartVT, Val);
583 }
584
585 Parts[0] = Val;
586 return;
587 }
588
589 // Expand the value into multiple parts.
590 if (NumParts & (NumParts - 1)) {
591 // The number of parts is not a power of 2. Split off and copy the tail.
592 assert(PartVT.isInteger() && ValueVT.isInteger() &&
593 "Do not know what to expand to!");
594 unsigned RoundParts = llvm::bit_floor(NumParts);
595 unsigned RoundBits = RoundParts * PartBits;
596 unsigned OddParts = NumParts - RoundParts;
597 SDValue OddVal = DAG.getNode(ISD::SRL, DL, ValueVT, Val,
598 DAG.getShiftAmountConstant(RoundBits, ValueVT, DL));
599
600 getCopyToParts(DAG, DL, OddVal, Parts + RoundParts, OddParts, PartVT, V,
601 CallConv);
602
603 if (DAG.getDataLayout().isBigEndian())
604 // The odd parts were reversed by getCopyToParts - unreverse them.
605 std::reverse(Parts + RoundParts, Parts + NumParts);
606
607 NumParts = RoundParts;
608 ValueVT = EVT::getIntegerVT(*DAG.getContext(), NumParts * PartBits);
609 Val = DAG.getNode(ISD::TRUNCATE, DL, ValueVT, Val);
610 }
611
612 // The number of parts is a power of 2. Repeatedly bisect the value using
613 // EXTRACT_ELEMENT.
614 Parts[0] = DAG.getNode(ISD::BITCAST, DL,
616 ValueVT.getSizeInBits()),
617 Val);
618
619 for (unsigned StepSize = NumParts; StepSize > 1; StepSize /= 2) {
620 for (unsigned i = 0; i < NumParts; i += StepSize) {
621 unsigned ThisBits = StepSize * PartBits / 2;
622 EVT ThisVT = EVT::getIntegerVT(*DAG.getContext(), ThisBits);
623 SDValue &Part0 = Parts[i];
624 SDValue &Part1 = Parts[i+StepSize/2];
625
626 Part1 = DAG.getNode(ISD::EXTRACT_ELEMENT, DL,
627 ThisVT, Part0, DAG.getIntPtrConstant(1, DL));
628 Part0 = DAG.getNode(ISD::EXTRACT_ELEMENT, DL,
629 ThisVT, Part0, DAG.getIntPtrConstant(0, DL));
630
631 if (ThisBits == PartBits && ThisVT != PartVT) {
632 Part0 = DAG.getNode(ISD::BITCAST, DL, PartVT, Part0);
633 Part1 = DAG.getNode(ISD::BITCAST, DL, PartVT, Part1);
634 }
635 }
636 }
637
638 if (DAG.getDataLayout().isBigEndian())
639 std::reverse(Parts, Parts + OrigNumParts);
640}
641
643 const SDLoc &DL, EVT PartVT) {
644 if (!PartVT.isVector())
645 return SDValue();
646
647 EVT ValueVT = Val.getValueType();
648 EVT PartEVT = PartVT.getVectorElementType();
649 EVT ValueEVT = ValueVT.getVectorElementType();
650 ElementCount PartNumElts = PartVT.getVectorElementCount();
651 ElementCount ValueNumElts = ValueVT.getVectorElementCount();
652
653 // We only support widening vectors with equivalent element types and
654 // fixed/scalable properties. If a target needs to widen a fixed-length type
655 // to a scalable one, it should be possible to use INSERT_SUBVECTOR below.
656 if (ElementCount::isKnownLE(PartNumElts, ValueNumElts) ||
657 PartNumElts.isScalable() != ValueNumElts.isScalable())
658 return SDValue();
659
660 // Have a try for bf16 because some targets share its ABI with fp16.
661 if (ValueEVT == MVT::bf16 && PartEVT == MVT::f16) {
663 "Cannot widen to illegal type");
664 Val = DAG.getNode(ISD::BITCAST, DL,
665 ValueVT.changeVectorElementType(MVT::f16), Val);
666 } else if (PartEVT != ValueEVT) {
667 return SDValue();
668 }
669
670 // Widening a scalable vector to another scalable vector is done by inserting
671 // the vector into a larger undef one.
672 if (PartNumElts.isScalable())
673 return DAG.getNode(ISD::INSERT_SUBVECTOR, DL, PartVT, DAG.getUNDEF(PartVT),
674 Val, DAG.getVectorIdxConstant(0, DL));
675
676 // Vector widening case, e.g. <2 x float> -> <4 x float>. Shuffle in
677 // undef elements.
679 DAG.ExtractVectorElements(Val, Ops);
680 SDValue EltUndef = DAG.getUNDEF(PartEVT);
681 Ops.append((PartNumElts - ValueNumElts).getFixedValue(), EltUndef);
682
683 // FIXME: Use CONCAT for 2x -> 4x.
684 return DAG.getBuildVector(PartVT, DL, Ops);
685}
686
687/// getCopyToPartsVector - Create a series of nodes that contain the specified
688/// value split into legal parts.
689static void getCopyToPartsVector(SelectionDAG &DAG, const SDLoc &DL,
690 SDValue Val, SDValue *Parts, unsigned NumParts,
691 MVT PartVT, const Value *V,
692 std::optional<CallingConv::ID> CallConv) {
693 EVT ValueVT = Val.getValueType();
694 assert(ValueVT.isVector() && "Not a vector");
695 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
696 const bool IsABIRegCopy = CallConv.has_value();
697
698 if (NumParts == 1) {
699 EVT PartEVT = PartVT;
700 if (PartEVT == ValueVT) {
701 // Nothing to do.
702 } else if (PartVT.getSizeInBits() == ValueVT.getSizeInBits()) {
703 // Bitconvert vector->vector case.
704 Val = DAG.getNode(ISD::BITCAST, DL, PartVT, Val);
705 } else if (SDValue Widened = widenVectorToPartType(DAG, Val, DL, PartVT)) {
706 Val = Widened;
707 } else if (PartVT.isVector() &&
709 ValueVT.getVectorElementType()) &&
710 PartEVT.getVectorElementCount() ==
711 ValueVT.getVectorElementCount()) {
712
713 // Promoted vector extract
714 Val = DAG.getAnyExtOrTrunc(Val, DL, PartVT);
715 } else if (PartEVT.isVector() &&
716 PartEVT.getVectorElementType() !=
717 ValueVT.getVectorElementType() &&
718 TLI.getTypeAction(*DAG.getContext(), ValueVT) ==
719 TargetLowering::TypeWidenVector) {
720 // Combination of widening and promotion.
721 EVT WidenVT =
723 PartVT.getVectorElementCount());
724 SDValue Widened = widenVectorToPartType(DAG, Val, DL, WidenVT);
725 Val = DAG.getAnyExtOrTrunc(Widened, DL, PartVT);
726 } else {
727 // Don't extract an integer from a float vector. This can happen if the
728 // FP type gets softened to integer and then promoted. The promotion
729 // prevents it from being picked up by the earlier bitcast case.
730 if (ValueVT.getVectorElementCount().isScalar() &&
731 (!ValueVT.isFloatingPoint() || !PartVT.isInteger())) {
732 // If we reach this condition and PartVT is FP, this means that
733 // ValueVT is also FP and both have a different size, otherwise we
734 // would have bitcasted them. Producing an EXTRACT_VECTOR_ELT here
735 // would be invalid since that would mean the smaller FP type has to
736 // be extended to the larger one.
737 if (PartVT.isFloatingPoint()) {
738 Val = DAG.getBitcast(ValueVT.getScalarType(), Val);
739 Val = DAG.getNode(ISD::FP_EXTEND, DL, PartVT, Val);
740 } else
741 Val = DAG.getNode(ISD::EXTRACT_VECTOR_ELT, DL, PartVT, Val,
742 DAG.getVectorIdxConstant(0, DL));
743 } else {
744 uint64_t ValueSize = ValueVT.getFixedSizeInBits();
745 assert(PartVT.getFixedSizeInBits() > ValueSize &&
746 "lossy conversion of vector to scalar type");
747 EVT IntermediateType = EVT::getIntegerVT(*DAG.getContext(), ValueSize);
748 Val = DAG.getBitcast(IntermediateType, Val);
749 Val = DAG.getAnyExtOrTrunc(Val, DL, PartVT);
750 }
751 }
752
753 assert(Val.getValueType() == PartVT && "Unexpected vector part value type");
754 Parts[0] = Val;
755 return;
756 }
757
758 // Handle a multi-element vector.
759 EVT IntermediateVT;
760 MVT RegisterVT;
761 unsigned NumIntermediates;
762 unsigned NumRegs;
763 if (IsABIRegCopy) {
765 *DAG.getContext(), *CallConv, ValueVT, IntermediateVT, NumIntermediates,
766 RegisterVT);
767 } else {
768 NumRegs =
769 TLI.getVectorTypeBreakdown(*DAG.getContext(), ValueVT, IntermediateVT,
770 NumIntermediates, RegisterVT);
771 }
772
773 assert(NumRegs == NumParts && "Part count doesn't match vector breakdown!");
774 NumParts = NumRegs; // Silence a compiler warning.
775 assert(RegisterVT == PartVT && "Part type doesn't match vector breakdown!");
776
777 assert(IntermediateVT.isScalableVector() == ValueVT.isScalableVector() &&
778 "Mixing scalable and fixed vectors when copying in parts");
779
780 std::optional<ElementCount> DestEltCnt;
781
782 if (IntermediateVT.isVector())
783 DestEltCnt = IntermediateVT.getVectorElementCount() * NumIntermediates;
784 else
785 DestEltCnt = ElementCount::getFixed(NumIntermediates);
786
787 EVT BuiltVectorTy = EVT::getVectorVT(
788 *DAG.getContext(), IntermediateVT.getScalarType(), *DestEltCnt);
789
790 if (ValueVT == BuiltVectorTy) {
791 // Nothing to do.
792 } else if (ValueVT.getSizeInBits() == BuiltVectorTy.getSizeInBits()) {
793 // Bitconvert vector->vector case.
794 Val = DAG.getNode(ISD::BITCAST, DL, BuiltVectorTy, Val);
795 } else {
796 if (BuiltVectorTy.getVectorElementType().bitsGT(
797 ValueVT.getVectorElementType())) {
798 // Integer promotion.
799 ValueVT = EVT::getVectorVT(*DAG.getContext(),
800 BuiltVectorTy.getVectorElementType(),
801 ValueVT.getVectorElementCount());
802 Val = DAG.getNode(ISD::ANY_EXTEND, DL, ValueVT, Val);
803 }
804
805 if (SDValue Widened = widenVectorToPartType(DAG, Val, DL, BuiltVectorTy)) {
806 Val = Widened;
807 }
808 }
809
810 assert(Val.getValueType() == BuiltVectorTy && "Unexpected vector value type");
811
812 // Split the vector into intermediate operands.
813 SmallVector<SDValue, 8> Ops(NumIntermediates);
814 for (unsigned i = 0; i != NumIntermediates; ++i) {
815 if (IntermediateVT.isVector()) {
816 // This does something sensible for scalable vectors - see the
817 // definition of EXTRACT_SUBVECTOR for further details.
818 unsigned IntermediateNumElts = IntermediateVT.getVectorMinNumElements();
819 Ops[i] =
820 DAG.getNode(ISD::EXTRACT_SUBVECTOR, DL, IntermediateVT, Val,
821 DAG.getVectorIdxConstant(i * IntermediateNumElts, DL));
822 } else {
823 Ops[i] = DAG.getNode(ISD::EXTRACT_VECTOR_ELT, DL, IntermediateVT, Val,
824 DAG.getVectorIdxConstant(i, DL));
825 }
826 }
827
828 // Split the intermediate operands into legal parts.
829 if (NumParts == NumIntermediates) {
830 // If the register was not expanded, promote or copy the value,
831 // as appropriate.
832 for (unsigned i = 0; i != NumParts; ++i)
833 getCopyToParts(DAG, DL, Ops[i], &Parts[i], 1, PartVT, V, CallConv);
834 } else if (NumParts > 0) {
835 // If the intermediate type was expanded, split each the value into
836 // legal parts.
837 assert(NumIntermediates != 0 && "division by zero");
838 assert(NumParts % NumIntermediates == 0 &&
839 "Must expand into a divisible number of parts!");
840 unsigned Factor = NumParts / NumIntermediates;
841 for (unsigned i = 0; i != NumIntermediates; ++i)
842 getCopyToParts(DAG, DL, Ops[i], &Parts[i * Factor], Factor, PartVT, V,
843 CallConv);
844 }
845}
846
848 EVT valuevt, std::optional<CallingConv::ID> CC)
849 : ValueVTs(1, valuevt), RegVTs(1, regvt), Regs(regs),
850 RegCount(1, regs.size()), CallConv(CC) {}
851
853 const DataLayout &DL, unsigned Reg, Type *Ty,
854 std::optional<CallingConv::ID> CC) {
855 ComputeValueVTs(TLI, DL, Ty, ValueVTs);
856
857 CallConv = CC;
858
859 for (EVT ValueVT : ValueVTs) {
860 unsigned NumRegs =
862 ? TLI.getNumRegistersForCallingConv(Context, *CC, ValueVT)
863 : TLI.getNumRegisters(Context, ValueVT);
864 MVT RegisterVT =
866 ? TLI.getRegisterTypeForCallingConv(Context, *CC, ValueVT)
867 : TLI.getRegisterType(Context, ValueVT);
868 for (unsigned i = 0; i != NumRegs; ++i)
869 Regs.push_back(Reg + i);
870 RegVTs.push_back(RegisterVT);
871 RegCount.push_back(NumRegs);
872 Reg += NumRegs;
873 }
874}
875
877 FunctionLoweringInfo &FuncInfo,
878 const SDLoc &dl, SDValue &Chain,
879 SDValue *Glue, const Value *V) const {
880 // A Value with type {} or [0 x %t] needs no registers.
881 if (ValueVTs.empty())
882 return SDValue();
883
884 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
885
886 // Assemble the legal parts into the final values.
887 SmallVector<SDValue, 4> Values(ValueVTs.size());
889 for (unsigned Value = 0, Part = 0, e = ValueVTs.size(); Value != e; ++Value) {
890 // Copy the legal parts from the registers.
891 EVT ValueVT = ValueVTs[Value];
892 unsigned NumRegs = RegCount[Value];
893 MVT RegisterVT = isABIMangled()
895 *DAG.getContext(), *CallConv, RegVTs[Value])
896 : RegVTs[Value];
897
898 Parts.resize(NumRegs);
899 for (unsigned i = 0; i != NumRegs; ++i) {
900 SDValue P;
901 if (!Glue) {
902 P = DAG.getCopyFromReg(Chain, dl, Regs[Part+i], RegisterVT);
903 } else {
904 P = DAG.getCopyFromReg(Chain, dl, Regs[Part+i], RegisterVT, *Glue);
905 *Glue = P.getValue(2);
906 }
907
908 Chain = P.getValue(1);
909 Parts[i] = P;
910
911 // If the source register was virtual and if we know something about it,
912 // add an assert node.
913 if (!Register::isVirtualRegister(Regs[Part + i]) ||
914 !RegisterVT.isInteger())
915 continue;
916
918 FuncInfo.GetLiveOutRegInfo(Regs[Part+i]);
919 if (!LOI)
920 continue;
921
922 unsigned RegSize = RegisterVT.getScalarSizeInBits();
923 unsigned NumSignBits = LOI->NumSignBits;
924 unsigned NumZeroBits = LOI->Known.countMinLeadingZeros();
925
926 if (NumZeroBits == RegSize) {
927 // The current value is a zero.
928 // Explicitly express that as it would be easier for
929 // optimizations to kick in.
930 Parts[i] = DAG.getConstant(0, dl, RegisterVT);
931 continue;
932 }
933
934 // FIXME: We capture more information than the dag can represent. For
935 // now, just use the tightest assertzext/assertsext possible.
936 bool isSExt;
937 EVT FromVT(MVT::Other);
938 if (NumZeroBits) {
939 FromVT = EVT::getIntegerVT(*DAG.getContext(), RegSize - NumZeroBits);
940 isSExt = false;
941 } else if (NumSignBits > 1) {
942 FromVT =
943 EVT::getIntegerVT(*DAG.getContext(), RegSize - NumSignBits + 1);
944 isSExt = true;
945 } else {
946 continue;
947 }
948 // Add an assertion node.
949 assert(FromVT != MVT::Other);
950 Parts[i] = DAG.getNode(isSExt ? ISD::AssertSext : ISD::AssertZext, dl,
951 RegisterVT, P, DAG.getValueType(FromVT));
952 }
953
954 Values[Value] = getCopyFromParts(DAG, dl, Parts.begin(), NumRegs,
955 RegisterVT, ValueVT, V, Chain, CallConv);
956 Part += NumRegs;
957 Parts.clear();
958 }
959
960 return DAG.getNode(ISD::MERGE_VALUES, dl, DAG.getVTList(ValueVTs), Values);
961}
962
964 const SDLoc &dl, SDValue &Chain, SDValue *Glue,
965 const Value *V,
966 ISD::NodeType PreferredExtendType) const {
967 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
968 ISD::NodeType ExtendKind = PreferredExtendType;
969
970 // Get the list of the values's legal parts.
971 unsigned NumRegs = Regs.size();
972 SmallVector<SDValue, 8> Parts(NumRegs);
973 for (unsigned Value = 0, Part = 0, e = ValueVTs.size(); Value != e; ++Value) {
974 unsigned NumParts = RegCount[Value];
975
976 MVT RegisterVT = isABIMangled()
978 *DAG.getContext(), *CallConv, RegVTs[Value])
979 : RegVTs[Value];
980
981 if (ExtendKind == ISD::ANY_EXTEND && TLI.isZExtFree(Val, RegisterVT))
982 ExtendKind = ISD::ZERO_EXTEND;
983
984 getCopyToParts(DAG, dl, Val.getValue(Val.getResNo() + Value), &Parts[Part],
985 NumParts, RegisterVT, V, CallConv, ExtendKind);
986 Part += NumParts;
987 }
988
989 // Copy the parts into the registers.
990 SmallVector<SDValue, 8> Chains(NumRegs);
991 for (unsigned i = 0; i != NumRegs; ++i) {
992 SDValue Part;
993 if (!Glue) {
994 Part = DAG.getCopyToReg(Chain, dl, Regs[i], Parts[i]);
995 } else {
996 Part = DAG.getCopyToReg(Chain, dl, Regs[i], Parts[i], *Glue);
997 *Glue = Part.getValue(1);
998 }
999
1000 Chains[i] = Part.getValue(0);
1001 }
1002
1003 if (NumRegs == 1 || Glue)
1004 // If NumRegs > 1 && Glue is used then the use of the last CopyToReg is
1005 // flagged to it. That is the CopyToReg nodes and the user are considered
1006 // a single scheduling unit. If we create a TokenFactor and return it as
1007 // chain, then the TokenFactor is both a predecessor (operand) of the
1008 // user as well as a successor (the TF operands are flagged to the user).
1009 // c1, f1 = CopyToReg
1010 // c2, f2 = CopyToReg
1011 // c3 = TokenFactor c1, c2
1012 // ...
1013 // = op c3, ..., f2
1014 Chain = Chains[NumRegs-1];
1015 else
1016 Chain = DAG.getNode(ISD::TokenFactor, dl, MVT::Other, Chains);
1017}
1018
1020 unsigned MatchingIdx, const SDLoc &dl,
1021 SelectionDAG &DAG,
1022 std::vector<SDValue> &Ops) const {
1023 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
1024
1025 InlineAsm::Flag Flag(Code, Regs.size());
1026 if (HasMatching)
1027 Flag.setMatchingOp(MatchingIdx);
1028 else if (!Regs.empty() && Register::isVirtualRegister(Regs.front())) {
1029 // Put the register class of the virtual registers in the flag word. That
1030 // way, later passes can recompute register class constraints for inline
1031 // assembly as well as normal instructions.
1032 // Don't do this for tied operands that can use the regclass information
1033 // from the def.
1035 const TargetRegisterClass *RC = MRI.getRegClass(Regs.front());
1036 Flag.setRegClass(RC->getID());
1037 }
1038
1039 SDValue Res = DAG.getTargetConstant(Flag, dl, MVT::i32);
1040 Ops.push_back(Res);
1041
1042 if (Code == InlineAsm::Kind::Clobber) {
1043 // Clobbers should always have a 1:1 mapping with registers, and may
1044 // reference registers that have illegal (e.g. vector) types. Hence, we
1045 // shouldn't try to apply any sort of splitting logic to them.
1046 assert(Regs.size() == RegVTs.size() && Regs.size() == ValueVTs.size() &&
1047 "No 1:1 mapping from clobbers to regs?");
1049 (void)SP;
1050 for (unsigned I = 0, E = ValueVTs.size(); I != E; ++I) {
1051 Ops.push_back(DAG.getRegister(Regs[I], RegVTs[I]));
1052 assert(
1053 (Regs[I] != SP ||
1055 "If we clobbered the stack pointer, MFI should know about it.");
1056 }
1057 return;
1058 }
1059
1060 for (unsigned Value = 0, Reg = 0, e = ValueVTs.size(); Value != e; ++Value) {
1061 MVT RegisterVT = RegVTs[Value];
1062 unsigned NumRegs = TLI.getNumRegisters(*DAG.getContext(), ValueVTs[Value],
1063 RegisterVT);
1064 for (unsigned i = 0; i != NumRegs; ++i) {
1065 assert(Reg < Regs.size() && "Mismatch in # registers expected");
1066 unsigned TheReg = Regs[Reg++];
1067 Ops.push_back(DAG.getRegister(TheReg, RegisterVT));
1068 }
1069 }
1070}
1071
1075 unsigned I = 0;
1076 for (auto CountAndVT : zip_first(RegCount, RegVTs)) {
1077 unsigned RegCount = std::get<0>(CountAndVT);
1078 MVT RegisterVT = std::get<1>(CountAndVT);
1079 TypeSize RegisterSize = RegisterVT.getSizeInBits();
1080 for (unsigned E = I + RegCount; I != E; ++I)
1081 OutVec.push_back(std::make_pair(Regs[I], RegisterSize));
1082 }
1083 return OutVec;
1084}
1085
1087 AssumptionCache *ac,
1088 const TargetLibraryInfo *li) {
1089 AA = aa;
1090 AC = ac;
1091 GFI = gfi;
1092 LibInfo = li;
1094 LPadToCallSiteMap.clear();
1096 AssignmentTrackingEnabled = isAssignmentTrackingEnabled(
1098}
1099
1101 NodeMap.clear();
1102 UnusedArgNodeMap.clear();
1103 PendingLoads.clear();
1104 PendingExports.clear();
1105 PendingConstrainedFP.clear();
1106 PendingConstrainedFPStrict.clear();
1107 CurInst = nullptr;
1108 HasTailCall = false;
1109 SDNodeOrder = LowestSDNodeOrder;
1111}
1112
1114 DanglingDebugInfoMap.clear();
1115}
1116
1117// Update DAG root to include dependencies on Pending chains.
1118SDValue SelectionDAGBuilder::updateRoot(SmallVectorImpl<SDValue> &Pending) {
1119 SDValue Root = DAG.getRoot();
1120
1121 if (Pending.empty())
1122 return Root;
1123
1124 // Add current root to PendingChains, unless we already indirectly
1125 // depend on it.
1126 if (Root.getOpcode() != ISD::EntryToken) {
1127 unsigned i = 0, e = Pending.size();
1128 for (; i != e; ++i) {
1129 assert(Pending[i].getNode()->getNumOperands() > 1);
1130 if (Pending[i].getNode()->getOperand(0) == Root)
1131 break; // Don't add the root if we already indirectly depend on it.
1132 }
1133
1134 if (i == e)
1135 Pending.push_back(Root);
1136 }
1137
1138 if (Pending.size() == 1)
1139 Root = Pending[0];
1140 else
1141 Root = DAG.getTokenFactor(getCurSDLoc(), Pending);
1142
1143 DAG.setRoot(Root);
1144 Pending.clear();
1145 return Root;
1146}
1147
1149 return updateRoot(PendingLoads);
1150}
1151
1153 // Chain up all pending constrained intrinsics together with all
1154 // pending loads, by simply appending them to PendingLoads and
1155 // then calling getMemoryRoot().
1156 PendingLoads.reserve(PendingLoads.size() +
1157 PendingConstrainedFP.size() +
1158 PendingConstrainedFPStrict.size());
1159 PendingLoads.append(PendingConstrainedFP.begin(),
1160 PendingConstrainedFP.end());
1161 PendingLoads.append(PendingConstrainedFPStrict.begin(),
1162 PendingConstrainedFPStrict.end());
1163 PendingConstrainedFP.clear();
1164 PendingConstrainedFPStrict.clear();
1165 return getMemoryRoot();
1166}
1167
1169 // We need to emit pending fpexcept.strict constrained intrinsics,
1170 // so append them to the PendingExports list.
1171 PendingExports.append(PendingConstrainedFPStrict.begin(),
1172 PendingConstrainedFPStrict.end());
1173 PendingConstrainedFPStrict.clear();
1174 return updateRoot(PendingExports);
1175}
1176
1178 DILocalVariable *Variable,
1180 DebugLoc DL) {
1181 assert(Variable && "Missing variable");
1182
1183 // Check if address has undef value.
1184 if (!Address || isa<UndefValue>(Address) ||
1185 (Address->use_empty() && !isa<Argument>(Address))) {
1186 LLVM_DEBUG(
1187 dbgs()
1188 << "dbg_declare: Dropping debug info (bad/undef/unused-arg address)\n");
1189 return;
1190 }
1191
1192 bool IsParameter = Variable->isParameter() || isa<Argument>(Address);
1193
1194 SDValue &N = NodeMap[Address];
1195 if (!N.getNode() && isa<Argument>(Address))
1196 // Check unused arguments map.
1197 N = UnusedArgNodeMap[Address];
1198 SDDbgValue *SDV;
1199 if (N.getNode()) {
1200 if (const BitCastInst *BCI = dyn_cast<BitCastInst>(Address))
1201 Address = BCI->getOperand(0);
1202 // Parameters are handled specially.
1203 auto *FINode = dyn_cast<FrameIndexSDNode>(N.getNode());
1204 if (IsParameter && FINode) {
1205 // Byval parameter. We have a frame index at this point.
1206 SDV = DAG.getFrameIndexDbgValue(Variable, Expression, FINode->getIndex(),
1207 /*IsIndirect*/ true, DL, SDNodeOrder);
1208 } else if (isa<Argument>(Address)) {
1209 // Address is an argument, so try to emit its dbg value using
1210 // virtual register info from the FuncInfo.ValueMap.
1211 EmitFuncArgumentDbgValue(Address, Variable, Expression, DL,
1212 FuncArgumentDbgValueKind::Declare, N);
1213 return;
1214 } else {
1215 SDV = DAG.getDbgValue(Variable, Expression, N.getNode(), N.getResNo(),
1216 true, DL, SDNodeOrder);
1217 }
1218 DAG.AddDbgValue(SDV, IsParameter);
1219 } else {
1220 // If Address is an argument then try to emit its dbg value using
1221 // virtual register info from the FuncInfo.ValueMap.
1222 if (!EmitFuncArgumentDbgValue(Address, Variable, Expression, DL,
1223 FuncArgumentDbgValueKind::Declare, N)) {
1224 LLVM_DEBUG(dbgs() << "dbg_declare: Dropping debug info"
1225 << " (could not emit func-arg dbg_value)\n");
1226 }
1227 }
1228 return;
1229}
1230
1232 // Add SDDbgValue nodes for any var locs here. Do so before updating
1233 // SDNodeOrder, as this mapping is {Inst -> Locs BEFORE Inst}.
1234 if (FunctionVarLocs const *FnVarLocs = DAG.getFunctionVarLocs()) {
1235 // Add SDDbgValue nodes for any var locs here. Do so before updating
1236 // SDNodeOrder, as this mapping is {Inst -> Locs BEFORE Inst}.
1237 for (auto It = FnVarLocs->locs_begin(&I), End = FnVarLocs->locs_end(&I);
1238 It != End; ++It) {
1239 auto *Var = FnVarLocs->getDILocalVariable(It->VariableID);
1240 dropDanglingDebugInfo(Var, It->Expr);
1241 if (It->Values.isKillLocation(It->Expr)) {
1242 handleKillDebugValue(Var, It->Expr, It->DL, SDNodeOrder);
1243 continue;
1244 }
1245 SmallVector<Value *> Values(It->Values.location_ops());
1246 if (!handleDebugValue(Values, Var, It->Expr, It->DL, SDNodeOrder,
1247 It->Values.hasArgList())) {
1249 for (Value *V : It->Values.location_ops())
1250 Vals.push_back(V);
1252 FnVarLocs->getDILocalVariable(It->VariableID),
1253 It->Expr, Vals.size() > 1, It->DL, SDNodeOrder);
1254 }
1255 }
1256 }
1257
1258 // We must skip DbgVariableRecords if they've already been processed above as
1259 // we have just emitted the debug values resulting from assignment tracking
1260 // analysis, making any existing DbgVariableRecords redundant (and probably
1261 // less correct). We still need to process DbgLabelRecords. This does sink
1262 // DbgLabelRecords to the bottom of the group of debug records. That sholdn't
1263 // be important as it does so deterministcally and ordering between
1264 // DbgLabelRecords and DbgVariableRecords is immaterial (other than for MIR/IR
1265 // printing).
1266 bool SkipDbgVariableRecords = DAG.getFunctionVarLocs();
1267 // Is there is any debug-info attached to this instruction, in the form of
1268 // DbgRecord non-instruction debug-info records.
1269 for (DbgRecord &DR : I.getDbgRecordRange()) {
1270 if (DbgLabelRecord *DLR = dyn_cast<DbgLabelRecord>(&DR)) {
1271 assert(DLR->getLabel() && "Missing label");
1272 SDDbgLabel *SDV =
1273 DAG.getDbgLabel(DLR->getLabel(), DLR->getDebugLoc(), SDNodeOrder);
1274 DAG.AddDbgLabel(SDV);
1275 continue;
1276 }
1277
1278 if (SkipDbgVariableRecords)
1279 continue;
1280 DbgVariableRecord &DVR = cast<DbgVariableRecord>(DR);
1281 DILocalVariable *Variable = DVR.getVariable();
1284
1286 if (FuncInfo.PreprocessedDVRDeclares.contains(&DVR))
1287 continue;
1288 LLVM_DEBUG(dbgs() << "SelectionDAG visiting dbg_declare: " << DVR
1289 << "\n");
1291 DVR.getDebugLoc());
1292 continue;
1293 }
1294
1295 // A DbgVariableRecord with no locations is a kill location.
1297 if (Values.empty()) {
1299 SDNodeOrder);
1300 continue;
1301 }
1302
1303 // A DbgVariableRecord with an undef or absent location is also a kill
1304 // location.
1305 if (llvm::any_of(Values,
1306 [](Value *V) { return !V || isa<UndefValue>(V); })) {
1308 SDNodeOrder);
1309 continue;
1310 }
1311
1312 bool IsVariadic = DVR.hasArgList();
1313 if (!handleDebugValue(Values, Variable, Expression, DVR.getDebugLoc(),
1314 SDNodeOrder, IsVariadic)) {
1315 addDanglingDebugInfo(Values, Variable, Expression, IsVariadic,
1316 DVR.getDebugLoc(), SDNodeOrder);
1317 }
1318 }
1319}
1320
1322 visitDbgInfo(I);
1323
1324 // Set up outgoing PHI node register values before emitting the terminator.
1325 if (I.isTerminator()) {
1326 HandlePHINodesInSuccessorBlocks(I.getParent());
1327 }
1328
1329 // Increase the SDNodeOrder if dealing with a non-debug instruction.
1330 if (!isa<DbgInfoIntrinsic>(I))
1331 ++SDNodeOrder;
1332
1333 CurInst = &I;
1334
1335 // Set inserted listener only if required.
1336 bool NodeInserted = false;
1337 std::unique_ptr<SelectionDAG::DAGNodeInsertedListener> InsertedListener;
1338 MDNode *PCSectionsMD = I.getMetadata(LLVMContext::MD_pcsections);
1339 MDNode *MMRA = I.getMetadata(LLVMContext::MD_mmra);
1340 if (PCSectionsMD || MMRA) {
1341 InsertedListener = std::make_unique<SelectionDAG::DAGNodeInsertedListener>(
1342 DAG, [&](SDNode *) { NodeInserted = true; });
1343 }
1344
1345 visit(I.getOpcode(), I);
1346
1347 if (!I.isTerminator() && !HasTailCall &&
1348 !isa<GCStatepointInst>(I)) // statepoints handle their exports internally
1350
1351 // Handle metadata.
1352 if (PCSectionsMD || MMRA) {
1353 auto It = NodeMap.find(&I);
1354 if (It != NodeMap.end()) {
1355 if (PCSectionsMD)
1356 DAG.addPCSections(It->second.getNode(), PCSectionsMD);
1357 if (MMRA)
1358 DAG.addMMRAMetadata(It->second.getNode(), MMRA);
1359 } else if (NodeInserted) {
1360 // This should not happen; if it does, don't let it go unnoticed so we can
1361 // fix it. Relevant visit*() function is probably missing a setValue().
1362 errs() << "warning: loosing !pcsections and/or !mmra metadata ["
1363 << I.getModule()->getName() << "]\n";
1364 LLVM_DEBUG(I.dump());
1365 assert(false);
1366 }
1367 }
1368
1369 CurInst = nullptr;
1370}
1371
1372void SelectionDAGBuilder::visitPHI(const PHINode &) {
1373 llvm_unreachable("SelectionDAGBuilder shouldn't visit PHI nodes!");
1374}
1375
1376void SelectionDAGBuilder::visit(unsigned Opcode, const User &I) {
1377 // Note: this doesn't use InstVisitor, because it has to work with
1378 // ConstantExpr's in addition to instructions.
1379 switch (Opcode) {
1380 default: llvm_unreachable("Unknown instruction type encountered!");
1381 // Build the switch statement using the Instruction.def file.
1382#define HANDLE_INST(NUM, OPCODE, CLASS) \
1383 case Instruction::OPCODE: visit##OPCODE((const CLASS&)I); break;
1384#include "llvm/IR/Instruction.def"
1385 }
1386}
1387
1389 DILocalVariable *Variable,
1390 DebugLoc DL, unsigned Order,
1393 // For variadic dbg_values we will now insert an undef.
1394 // FIXME: We can potentially recover these!
1396 for (const Value *V : Values) {
1397 auto *Undef = UndefValue::get(V->getType());
1399 }
1400 SDDbgValue *SDV = DAG.getDbgValueList(Variable, Expression, Locs, {},
1401 /*IsIndirect=*/false, DL, Order,
1402 /*IsVariadic=*/true);
1403 DAG.AddDbgValue(SDV, /*isParameter=*/false);
1404 return true;
1405}
1406
1408 DILocalVariable *Var,
1409 DIExpression *Expr,
1410 bool IsVariadic, DebugLoc DL,
1411 unsigned Order) {
1412 if (IsVariadic) {
1413 handleDanglingVariadicDebugInfo(DAG, Var, DL, Order, Values, Expr);
1414 return;
1415 }
1416 // TODO: Dangling debug info will eventually either be resolved or produce
1417 // an Undef DBG_VALUE. However in the resolution case, a gap may appear
1418 // between the original dbg.value location and its resolved DBG_VALUE,
1419 // which we should ideally fill with an extra Undef DBG_VALUE.
1420 assert(Values.size() == 1);
1421 DanglingDebugInfoMap[Values[0]].emplace_back(Var, Expr, DL, Order);
1422}
1423
1425 const DIExpression *Expr) {
1426 auto isMatchingDbgValue = [&](DanglingDebugInfo &DDI) {
1427 DIVariable *DanglingVariable = DDI.getVariable();
1428 DIExpression *DanglingExpr = DDI.getExpression();
1429 if (DanglingVariable == Variable && Expr->fragmentsOverlap(DanglingExpr)) {
1430 LLVM_DEBUG(dbgs() << "Dropping dangling debug info for "
1431 << printDDI(nullptr, DDI) << "\n");
1432 return true;
1433 }
1434 return false;
1435 };
1436
1437 for (auto &DDIMI : DanglingDebugInfoMap) {
1438 DanglingDebugInfoVector &DDIV = DDIMI.second;
1439
1440 // If debug info is to be dropped, run it through final checks to see
1441 // whether it can be salvaged.
1442 for (auto &DDI : DDIV)
1443 if (isMatchingDbgValue(DDI))
1444 salvageUnresolvedDbgValue(DDIMI.first, DDI);
1445
1446 erase_if(DDIV, isMatchingDbgValue);
1447 }
1448}
1449
1450// resolveDanglingDebugInfo - if we saw an earlier dbg_value referring to V,
1451// generate the debug data structures now that we've seen its definition.
1453 SDValue Val) {
1454 auto DanglingDbgInfoIt = DanglingDebugInfoMap.find(V);
1455 if (DanglingDbgInfoIt == DanglingDebugInfoMap.end())
1456 return;
1457
1458 DanglingDebugInfoVector &DDIV = DanglingDbgInfoIt->second;
1459 for (auto &DDI : DDIV) {
1460 DebugLoc DL = DDI.getDebugLoc();
1461 unsigned ValSDNodeOrder = Val.getNode()->getIROrder();
1462 unsigned DbgSDNodeOrder = DDI.getSDNodeOrder();
1463 DILocalVariable *Variable = DDI.getVariable();
1464 DIExpression *Expr = DDI.getExpression();
1466 "Expected inlined-at fields to agree");
1467 SDDbgValue *SDV;
1468 if (Val.getNode()) {
1469 // FIXME: I doubt that it is correct to resolve a dangling DbgValue as a
1470 // FuncArgumentDbgValue (it would be hoisted to the function entry, and if
1471 // we couldn't resolve it directly when examining the DbgValue intrinsic
1472 // in the first place we should not be more successful here). Unless we
1473 // have some test case that prove this to be correct we should avoid
1474 // calling EmitFuncArgumentDbgValue here.
1475 if (!EmitFuncArgumentDbgValue(V, Variable, Expr, DL,
1476 FuncArgumentDbgValueKind::Value, Val)) {
1477 LLVM_DEBUG(dbgs() << "Resolve dangling debug info for "
1478 << printDDI(V, DDI) << "\n");
1479 LLVM_DEBUG(dbgs() << " By mapping to:\n "; Val.dump());
1480 // Increase the SDNodeOrder for the DbgValue here to make sure it is
1481 // inserted after the definition of Val when emitting the instructions
1482 // after ISel. An alternative could be to teach
1483 // ScheduleDAGSDNodes::EmitSchedule to delay the insertion properly.
1484 LLVM_DEBUG(if (ValSDNodeOrder > DbgSDNodeOrder) dbgs()
1485 << "changing SDNodeOrder from " << DbgSDNodeOrder << " to "
1486 << ValSDNodeOrder << "\n");
1487 SDV = getDbgValue(Val, Variable, Expr, DL,
1488 std::max(DbgSDNodeOrder, ValSDNodeOrder));
1489 DAG.AddDbgValue(SDV, false);
1490 } else
1491 LLVM_DEBUG(dbgs() << "Resolved dangling debug info for "
1492 << printDDI(V, DDI)
1493 << " in EmitFuncArgumentDbgValue\n");
1494 } else {
1495 LLVM_DEBUG(dbgs() << "Dropping debug info for " << printDDI(V, DDI)
1496 << "\n");
1497 auto Undef = UndefValue::get(V->getType());
1498 auto SDV =
1499 DAG.getConstantDbgValue(Variable, Expr, Undef, DL, DbgSDNodeOrder);
1500 DAG.AddDbgValue(SDV, false);
1501 }
1502 }
1503 DDIV.clear();
1504}
1505
1507 DanglingDebugInfo &DDI) {
1508 // TODO: For the variadic implementation, instead of only checking the fail
1509 // state of `handleDebugValue`, we need know specifically which values were
1510 // invalid, so that we attempt to salvage only those values when processing
1511 // a DIArgList.
1512 const Value *OrigV = V;
1513 DILocalVariable *Var = DDI.getVariable();
1514 DIExpression *Expr = DDI.getExpression();
1515 DebugLoc DL = DDI.getDebugLoc();
1516 unsigned SDOrder = DDI.getSDNodeOrder();
1517
1518 // Currently we consider only dbg.value intrinsics -- we tell the salvager
1519 // that DW_OP_stack_value is desired.
1520 bool StackValue = true;
1521
1522 // Can this Value can be encoded without any further work?
1523 if (handleDebugValue(V, Var, Expr, DL, SDOrder, /*IsVariadic=*/false))
1524 return;
1525
1526 // Attempt to salvage back through as many instructions as possible. Bail if
1527 // a non-instruction is seen, such as a constant expression or global
1528 // variable. FIXME: Further work could recover those too.
1529 while (isa<Instruction>(V)) {
1530 const Instruction &VAsInst = *cast<const Instruction>(V);
1531 // Temporary "0", awaiting real implementation.
1533 SmallVector<Value *, 4> AdditionalValues;
1534 V = salvageDebugInfoImpl(const_cast<Instruction &>(VAsInst),
1535 Expr->getNumLocationOperands(), Ops,
1536 AdditionalValues);
1537 // If we cannot salvage any further, and haven't yet found a suitable debug
1538 // expression, bail out.
1539 if (!V)
1540 break;
1541
1542 // TODO: If AdditionalValues isn't empty, then the salvage can only be
1543 // represented with a DBG_VALUE_LIST, so we give up. When we have support
1544 // here for variadic dbg_values, remove that condition.
1545 if (!AdditionalValues.empty())
1546 break;
1547
1548 // New value and expr now represent this debuginfo.
1549 Expr = DIExpression::appendOpsToArg(Expr, Ops, 0, StackValue);
1550
1551 // Some kind of simplification occurred: check whether the operand of the
1552 // salvaged debug expression can be encoded in this DAG.
1553 if (handleDebugValue(V, Var, Expr, DL, SDOrder, /*IsVariadic=*/false)) {
1554 LLVM_DEBUG(
1555 dbgs() << "Salvaged debug location info for:\n " << *Var << "\n"
1556 << *OrigV << "\nBy stripping back to:\n " << *V << "\n");
1557 return;
1558 }
1559 }
1560
1561 // This was the final opportunity to salvage this debug information, and it
1562 // couldn't be done. Place an undef DBG_VALUE at this location to terminate
1563 // any earlier variable location.
1564 assert(OrigV && "V shouldn't be null");
1565 auto *Undef = UndefValue::get(OrigV->getType());
1566 auto *SDV = DAG.getConstantDbgValue(Var, Expr, Undef, DL, SDNodeOrder);
1567 DAG.AddDbgValue(SDV, false);
1568 LLVM_DEBUG(dbgs() << "Dropping debug value info for:\n "
1569 << printDDI(OrigV, DDI) << "\n");
1570}
1571
1573 DIExpression *Expr,
1574 DebugLoc DbgLoc,
1575 unsigned Order) {
1579 handleDebugValue(Poison, Var, NewExpr, DbgLoc, Order,
1580 /*IsVariadic*/ false);
1581}
1582
1584 DILocalVariable *Var,
1585 DIExpression *Expr, DebugLoc DbgLoc,
1586 unsigned Order, bool IsVariadic) {
1587 if (Values.empty())
1588 return true;
1589
1590 // Filter EntryValue locations out early.
1591 if (visitEntryValueDbgValue(Values, Var, Expr, DbgLoc))
1592 return true;
1593
1594 SmallVector<SDDbgOperand> LocationOps;
1595 SmallVector<SDNode *> Dependencies;
1596 for (const Value *V : Values) {
1597 // Constant value.
1598 if (isa<ConstantInt>(V) || isa<ConstantFP>(V) || isa<UndefValue>(V) ||
1599 isa<ConstantPointerNull>(V)) {
1600 LocationOps.emplace_back(SDDbgOperand::fromConst(V));
1601 continue;
1602 }
1603
1604 // Look through IntToPtr constants.
1605 if (auto *CE = dyn_cast<ConstantExpr>(V))
1606 if (CE->getOpcode() == Instruction::IntToPtr) {
1607 LocationOps.emplace_back(SDDbgOperand::fromConst(CE->getOperand(0)));
1608 continue;
1609 }
1610
1611 // If the Value is a frame index, we can create a FrameIndex debug value
1612 // without relying on the DAG at all.
1613 if (const AllocaInst *AI = dyn_cast<AllocaInst>(V)) {
1614 auto SI = FuncInfo.StaticAllocaMap.find(AI);
1615 if (SI != FuncInfo.StaticAllocaMap.end()) {
1616 LocationOps.emplace_back(SDDbgOperand::fromFrameIdx(SI->second));
1617 continue;
1618 }
1619 }
1620
1621 // Do not use getValue() in here; we don't want to generate code at
1622 // this point if it hasn't been done yet.
1623 SDValue N = NodeMap[V];
1624 if (!N.getNode() && isa<Argument>(V)) // Check unused arguments map.
1625 N = UnusedArgNodeMap[V];
1626 if (N.getNode()) {
1627 // Only emit func arg dbg value for non-variadic dbg.values for now.
1628 if (!IsVariadic &&
1629 EmitFuncArgumentDbgValue(V, Var, Expr, DbgLoc,
1630 FuncArgumentDbgValueKind::Value, N))
1631 return true;
1632 if (auto *FISDN = dyn_cast<FrameIndexSDNode>(N.getNode())) {
1633 // Construct a FrameIndexDbgValue for FrameIndexSDNodes so we can
1634 // describe stack slot locations.
1635 //
1636 // Consider "int x = 0; int *px = &x;". There are two kinds of
1637 // interesting debug values here after optimization:
1638 //
1639 // dbg.value(i32* %px, !"int *px", !DIExpression()), and
1640 // dbg.value(i32* %px, !"int x", !DIExpression(DW_OP_deref))
1641 //
1642 // Both describe the direct values of their associated variables.
1643 Dependencies.push_back(N.getNode());
1644 LocationOps.emplace_back(SDDbgOperand::fromFrameIdx(FISDN->getIndex()));
1645 continue;
1646 }
1647 LocationOps.emplace_back(
1648 SDDbgOperand::fromNode(N.getNode(), N.getResNo()));
1649 continue;
1650 }
1651
1653 // Special rules apply for the first dbg.values of parameter variables in a
1654 // function. Identify them by the fact they reference Argument Values, that
1655 // they're parameters, and they are parameters of the current function. We
1656 // need to let them dangle until they get an SDNode.
1657 bool IsParamOfFunc =
1658 isa<Argument>(V) && Var->isParameter() && !DbgLoc.getInlinedAt();
1659 if (IsParamOfFunc)
1660 return false;
1661
1662 // The value is not used in this block yet (or it would have an SDNode).
1663 // We still want the value to appear for the user if possible -- if it has
1664 // an associated VReg, we can refer to that instead.
1665 auto VMI = FuncInfo.ValueMap.find(V);
1666 if (VMI != FuncInfo.ValueMap.end()) {
1667 unsigned Reg = VMI->second;
1668 // If this is a PHI node, it may be split up into several MI PHI nodes
1669 // (in FunctionLoweringInfo::set).
1670 RegsForValue RFV(V->getContext(), TLI, DAG.getDataLayout(), Reg,
1671 V->getType(), std::nullopt);
1672 if (RFV.occupiesMultipleRegs()) {
1673 // FIXME: We could potentially support variadic dbg_values here.
1674 if (IsVariadic)
1675 return false;
1676 unsigned Offset = 0;
1677 unsigned BitsToDescribe = 0;
1678 if (auto VarSize = Var->getSizeInBits())
1679 BitsToDescribe = *VarSize;
1680 if (auto Fragment = Expr->getFragmentInfo())
1681 BitsToDescribe = Fragment->SizeInBits;
1682 for (const auto &RegAndSize : RFV.getRegsAndSizes()) {
1683 // Bail out if all bits are described already.
1684 if (Offset >= BitsToDescribe)
1685 break;
1686 // TODO: handle scalable vectors.
1687 unsigned RegisterSize = RegAndSize.second;
1688 unsigned FragmentSize = (Offset + RegisterSize > BitsToDescribe)
1689 ? BitsToDescribe - Offset
1690 : RegisterSize;
1691 auto FragmentExpr = DIExpression::createFragmentExpression(
1692 Expr, Offset, FragmentSize);
1693 if (!FragmentExpr)
1694 continue;
1696 Var, *FragmentExpr, RegAndSize.first, false, DbgLoc, Order);
1697 DAG.AddDbgValue(SDV, false);
1698 Offset += RegisterSize;
1699 }
1700 return true;
1701 }
1702 // We can use simple vreg locations for variadic dbg_values as well.
1703 LocationOps.emplace_back(SDDbgOperand::fromVReg(Reg));
1704 continue;
1705 }
1706 // We failed to create a SDDbgOperand for V.
1707 return false;
1708 }
1709
1710 // We have created a SDDbgOperand for each Value in Values.
1711 assert(!LocationOps.empty());
1712 SDDbgValue *SDV =
1713 DAG.getDbgValueList(Var, Expr, LocationOps, Dependencies,
1714 /*IsIndirect=*/false, DbgLoc, Order, IsVariadic);
1715 DAG.AddDbgValue(SDV, /*isParameter=*/false);
1716 return true;
1717}
1718
1720 // Try to fixup any remaining dangling debug info -- and drop it if we can't.
1721 for (auto &Pair : DanglingDebugInfoMap)
1722 for (auto &DDI : Pair.second)
1723 salvageUnresolvedDbgValue(const_cast<Value *>(Pair.first), DDI);
1725}
1726
1727/// getCopyFromRegs - If there was virtual register allocated for the value V
1728/// emit CopyFromReg of the specified type Ty. Return empty SDValue() otherwise.
1731 SDValue Result;
1732
1733 if (It != FuncInfo.ValueMap.end()) {
1734 Register InReg = It->second;
1735
1737 DAG.getDataLayout(), InReg, Ty,
1738 std::nullopt); // This is not an ABI copy.
1739 SDValue Chain = DAG.getEntryNode();
1740 Result = RFV.getCopyFromRegs(DAG, FuncInfo, getCurSDLoc(), Chain, nullptr,
1741 V);
1742 resolveDanglingDebugInfo(V, Result);
1743 }
1744
1745 return Result;
1746}
1747
1748/// getValue - Return an SDValue for the given Value.
1750 // If we already have an SDValue for this value, use it. It's important
1751 // to do this first, so that we don't create a CopyFromReg if we already
1752 // have a regular SDValue.
1753 SDValue &N = NodeMap[V];
1754 if (N.getNode()) return N;
1755
1756 // If there's a virtual register allocated and initialized for this
1757 // value, use it.
1758 if (SDValue copyFromReg = getCopyFromRegs(V, V->getType()))
1759 return copyFromReg;
1760
1761 // Otherwise create a new SDValue and remember it.
1762 SDValue Val = getValueImpl(V);
1763 NodeMap[V] = Val;
1765 return Val;
1766}
1767
1768/// getNonRegisterValue - Return an SDValue for the given Value, but
1769/// don't look in FuncInfo.ValueMap for a virtual register.
1771 // If we already have an SDValue for this value, use it.
1772 SDValue &N = NodeMap[V];
1773 if (N.getNode()) {
1774 if (isIntOrFPConstant(N)) {
1775 // Remove the debug location from the node as the node is about to be used
1776 // in a location which may differ from the original debug location. This
1777 // is relevant to Constant and ConstantFP nodes because they can appear
1778 // as constant expressions inside PHI nodes.
1779 N->setDebugLoc(DebugLoc());
1780 }
1781 return N;
1782 }
1783
1784 // Otherwise create a new SDValue and remember it.
1785 SDValue Val = getValueImpl(V);
1786 NodeMap[V] = Val;
1788 return Val;
1789}
1790
1791/// getValueImpl - Helper function for getValue and getNonRegisterValue.
1792/// Create an SDValue for the given value.
1795
1796 if (const Constant *C = dyn_cast<Constant>(V)) {
1797 EVT VT = TLI.getValueType(DAG.getDataLayout(), V->getType(), true);
1798
1799 if (const ConstantInt *CI = dyn_cast<ConstantInt>(C))
1800 return DAG.getConstant(*CI, getCurSDLoc(), VT);
1801
1802 if (const GlobalValue *GV = dyn_cast<GlobalValue>(C))
1803 return DAG.getGlobalAddress(GV, getCurSDLoc(), VT);
1804
1805 if (isa<ConstantPointerNull>(C)) {
1806 unsigned AS = V->getType()->getPointerAddressSpace();
1807 return DAG.getConstant(0, getCurSDLoc(),
1808 TLI.getPointerTy(DAG.getDataLayout(), AS));
1809 }
1810
1811 if (match(C, m_VScale()))
1812 return DAG.getVScale(getCurSDLoc(), VT, APInt(VT.getSizeInBits(), 1));
1813
1814 if (const ConstantFP *CFP = dyn_cast<ConstantFP>(C))
1815 return DAG.getConstantFP(*CFP, getCurSDLoc(), VT);
1816
1817 if (isa<UndefValue>(C) && !V->getType()->isAggregateType())
1818 return DAG.getUNDEF(VT);
1819
1820 if (const ConstantExpr *CE = dyn_cast<ConstantExpr>(C)) {
1821 visit(CE->getOpcode(), *CE);
1822 SDValue N1 = NodeMap[V];
1823 assert(N1.getNode() && "visit didn't populate the NodeMap!");
1824 return N1;
1825 }
1826
1827 if (isa<ConstantStruct>(C) || isa<ConstantArray>(C)) {
1829 for (const Use &U : C->operands()) {
1830 SDNode *Val = getValue(U).getNode();
1831 // If the operand is an empty aggregate, there are no values.
1832 if (!Val) continue;
1833 // Add each leaf value from the operand to the Constants list
1834 // to form a flattened list of all the values.
1835 for (unsigned i = 0, e = Val->getNumValues(); i != e; ++i)
1836 Constants.push_back(SDValue(Val, i));
1837 }
1838
1840 }
1841
1842 if (const ConstantDataSequential *CDS =
1843 dyn_cast<ConstantDataSequential>(C)) {
1845 for (unsigned i = 0, e = CDS->getNumElements(); i != e; ++i) {
1846 SDNode *Val = getValue(CDS->getElementAsConstant(i)).getNode();
1847 // Add each leaf value from the operand to the Constants list
1848 // to form a flattened list of all the values.
1849 for (unsigned i = 0, e = Val->getNumValues(); i != e; ++i)
1850 Ops.push_back(SDValue(Val, i));
1851 }
1852
1853 if (isa<ArrayType>(CDS->getType()))
1854 return DAG.getMergeValues(Ops, getCurSDLoc());
1855 return NodeMap[V] = DAG.getBuildVector(VT, getCurSDLoc(), Ops);
1856 }
1857
1858 if (C->getType()->isStructTy() || C->getType()->isArrayTy()) {
1859 assert((isa<ConstantAggregateZero>(C) || isa<UndefValue>(C)) &&
1860 "Unknown struct or array constant!");
1861
1862 SmallVector<EVT, 4> ValueVTs;
1863 ComputeValueVTs(TLI, DAG.getDataLayout(), C->getType(), ValueVTs);
1864 unsigned NumElts = ValueVTs.size();
1865 if (NumElts == 0)
1866 return SDValue(); // empty struct
1868 for (unsigned i = 0; i != NumElts; ++i) {
1869 EVT EltVT = ValueVTs[i];
1870 if (isa<UndefValue>(C))
1871 Constants[i] = DAG.getUNDEF(EltVT);
1872 else if (EltVT.isFloatingPoint())
1873 Constants[i] = DAG.getConstantFP(0, getCurSDLoc(), EltVT);
1874 else
1875 Constants[i] = DAG.getConstant(0, getCurSDLoc(), EltVT);
1876 }
1877
1879 }
1880
1881 if (const BlockAddress *BA = dyn_cast<BlockAddress>(C))
1882 return DAG.getBlockAddress(BA, VT);
1883
1884 if (const auto *Equiv = dyn_cast<DSOLocalEquivalent>(C))
1885 return getValue(Equiv->getGlobalValue());
1886
1887 if (const auto *NC = dyn_cast<NoCFIValue>(C))
1888 return getValue(NC->getGlobalValue());
1889
1890 if (VT == MVT::aarch64svcount) {
1891 assert(C->isNullValue() && "Can only zero this target type!");
1892 return DAG.getNode(ISD::BITCAST, getCurSDLoc(), VT,
1893 DAG.getConstant(0, getCurSDLoc(), MVT::nxv16i1));
1894 }
1895
1896 VectorType *VecTy = cast<VectorType>(V->getType());
1897
1898 // Now that we know the number and type of the elements, get that number of
1899 // elements into the Ops array based on what kind of constant it is.
1900 if (const ConstantVector *CV = dyn_cast<ConstantVector>(C)) {
1902 unsigned NumElements = cast<FixedVectorType>(VecTy)->getNumElements();
1903 for (unsigned i = 0; i != NumElements; ++i)
1904 Ops.push_back(getValue(CV->getOperand(i)));
1905
1906 return NodeMap[V] = DAG.getBuildVector(VT, getCurSDLoc(), Ops);
1907 }
1908
1909 if (isa<ConstantAggregateZero>(C)) {
1910 EVT EltVT =
1912
1913 SDValue Op;
1914 if (EltVT.isFloatingPoint())
1915 Op = DAG.getConstantFP(0, getCurSDLoc(), EltVT);
1916 else
1917 Op = DAG.getConstant(0, getCurSDLoc(), EltVT);
1918
1919 return NodeMap[V] = DAG.getSplat(VT, getCurSDLoc(), Op);
1920 }
1921
1922 llvm_unreachable("Unknown vector constant");
1923 }
1924
1925 // If this is a static alloca, generate it as the frameindex instead of
1926 // computation.
1927 if (const AllocaInst *AI = dyn_cast<AllocaInst>(V)) {
1929 FuncInfo.StaticAllocaMap.find(AI);
1930 if (SI != FuncInfo.StaticAllocaMap.end())
1931 return DAG.getFrameIndex(
1932 SI->second, TLI.getValueType(DAG.getDataLayout(), AI->getType()));
1933 }
1934
1935 // If this is an instruction which fast-isel has deferred, select it now.
1936 if (const Instruction *Inst = dyn_cast<Instruction>(V)) {
1938
1939 RegsForValue RFV(*DAG.getContext(), TLI, DAG.getDataLayout(), InReg,
1940 Inst->getType(), std::nullopt);
1941 SDValue Chain = DAG.getEntryNode();
1942 return RFV.getCopyFromRegs(DAG, FuncInfo, getCurSDLoc(), Chain, nullptr, V);
1943 }
1944
1945 if (const MetadataAsValue *MD = dyn_cast<MetadataAsValue>(V))
1946 return DAG.getMDNode(cast<MDNode>(MD->getMetadata()));
1947
1948 if (const auto *BB = dyn_cast<BasicBlock>(V))
1949 return DAG.getBasicBlock(FuncInfo.MBBMap[BB]);
1950
1951 llvm_unreachable("Can't get register for value!");
1952}
1953
1954void SelectionDAGBuilder::visitCatchPad(const CatchPadInst &I) {
1956 bool IsMSVCCXX = Pers == EHPersonality::MSVC_CXX;
1957 bool IsCoreCLR = Pers == EHPersonality::CoreCLR;
1958 bool IsSEH = isAsynchronousEHPersonality(Pers);
1959 MachineBasicBlock *CatchPadMBB = FuncInfo.MBB;
1960 if (!IsSEH)
1961 CatchPadMBB->setIsEHScopeEntry();
1962 // In MSVC C++ and CoreCLR, catchblocks are funclets and need prologues.
1963 if (IsMSVCCXX || IsCoreCLR)
1964 CatchPadMBB->setIsEHFuncletEntry();
1965}
1966
1967void SelectionDAGBuilder::visitCatchRet(const CatchReturnInst &I) {
1968 // Update machine-CFG edge.
1969 MachineBasicBlock *TargetMBB = FuncInfo.MBBMap[I.getSuccessor()];
1970 FuncInfo.MBB->addSuccessor(TargetMBB);
1971 TargetMBB->setIsEHCatchretTarget(true);
1973
1975 bool IsSEH = isAsynchronousEHPersonality(Pers);
1976 if (IsSEH) {
1977 // If this is not a fall-through branch or optimizations are switched off,
1978 // emit the branch.
1979 if (TargetMBB != NextBlock(FuncInfo.MBB) ||
1981 DAG.setRoot(DAG.getNode(ISD::BR, getCurSDLoc(), MVT::Other,
1982 getControlRoot(), DAG.getBasicBlock(TargetMBB)));
1983 return;
1984 }
1985
1986 // Figure out the funclet membership for the catchret's successor.
1987 // This will be used by the FuncletLayout pass to determine how to order the
1988 // BB's.
1989 // A 'catchret' returns to the outer scope's color.
1990 Value *ParentPad = I.getCatchSwitchParentPad();
1991 const BasicBlock *SuccessorColor;
1992 if (isa<ConstantTokenNone>(ParentPad))
1993 SuccessorColor = &FuncInfo.Fn->getEntryBlock();
1994 else
1995 SuccessorColor = cast<Instruction>(ParentPad)->getParent();
1996 assert(SuccessorColor && "No parent funclet for catchret!");
1997 MachineBasicBlock *SuccessorColorMBB = FuncInfo.MBBMap[SuccessorColor];
1998 assert(SuccessorColorMBB && "No MBB for SuccessorColor!");
1999
2000 // Create the terminator node.
2002 getControlRoot(), DAG.getBasicBlock(TargetMBB),
2003 DAG.getBasicBlock(SuccessorColorMBB));
2004 DAG.setRoot(Ret);
2005}
2006
2007void SelectionDAGBuilder::visitCleanupPad(const CleanupPadInst &CPI) {
2008 // Don't emit any special code for the cleanuppad instruction. It just marks
2009 // the start of an EH scope/funclet.
2012 if (Pers != EHPersonality::Wasm_CXX) {
2015 }
2016}
2017
2018// In wasm EH, even though a catchpad may not catch an exception if a tag does
2019// not match, it is OK to add only the first unwind destination catchpad to the
2020// successors, because there will be at least one invoke instruction within the
2021// catch scope that points to the next unwind destination, if one exists, so
2022// CFGSort cannot mess up with BB sorting order.
2023// (All catchpads with 'catch (type)' clauses have a 'llvm.rethrow' intrinsic
2024// call within them, and catchpads only consisting of 'catch (...)' have a
2025// '__cxa_end_catch' call within them, both of which generate invokes in case
2026// the next unwind destination exists, i.e., the next unwind destination is not
2027// the caller.)
2028//
2029// Having at most one EH pad successor is also simpler and helps later
2030// transformations.
2031//
2032// For example,
2033// current:
2034// invoke void @foo to ... unwind label %catch.dispatch
2035// catch.dispatch:
2036// %0 = catchswitch within ... [label %catch.start] unwind label %next
2037// catch.start:
2038// ...
2039// ... in this BB or some other child BB dominated by this BB there will be an
2040// invoke that points to 'next' BB as an unwind destination
2041//
2042// next: ; We don't need to add this to 'current' BB's successor
2043// ...
2045 FunctionLoweringInfo &FuncInfo, const BasicBlock *EHPadBB,
2046 BranchProbability Prob,
2047 SmallVectorImpl<std::pair<MachineBasicBlock *, BranchProbability>>
2048 &UnwindDests) {
2049 while (EHPadBB) {
2050 const Instruction *Pad = EHPadBB->getFirstNonPHI();
2051 if (isa<CleanupPadInst>(Pad)) {
2052 // Stop on cleanup pads.
2053 UnwindDests.emplace_back(FuncInfo.MBBMap[EHPadBB], Prob);
2054 UnwindDests.back().first->setIsEHScopeEntry();
2055 break;
2056 } else if (const auto *CatchSwitch = dyn_cast<CatchSwitchInst>(Pad)) {
2057 // Add the catchpad handlers to the possible destinations. We don't
2058 // continue to the unwind destination of the catchswitch for wasm.
2059 for (const BasicBlock *CatchPadBB : CatchSwitch->handlers()) {
2060 UnwindDests.emplace_back(FuncInfo.MBBMap[CatchPadBB], Prob);
2061 UnwindDests.back().first->setIsEHScopeEntry();
2062 }
2063 break;
2064 } else {
2065 continue;
2066 }
2067 }
2068}
2069
2070/// When an invoke or a cleanupret unwinds to the next EH pad, there are
2071/// many places it could ultimately go. In the IR, we have a single unwind
2072/// destination, but in the machine CFG, we enumerate all the possible blocks.
2073/// This function skips over imaginary basic blocks that hold catchswitch
2074/// instructions, and finds all the "real" machine
2075/// basic block destinations. As those destinations may not be successors of
2076/// EHPadBB, here we also calculate the edge probability to those destinations.
2077/// The passed-in Prob is the edge probability to EHPadBB.
2079 FunctionLoweringInfo &FuncInfo, const BasicBlock *EHPadBB,
2080 BranchProbability Prob,
2081 SmallVectorImpl<std::pair<MachineBasicBlock *, BranchProbability>>
2082 &UnwindDests) {
2083 EHPersonality Personality =
2085 bool IsMSVCCXX = Personality == EHPersonality::MSVC_CXX;
2086 bool IsCoreCLR = Personality == EHPersonality::CoreCLR;
2087 bool IsWasmCXX = Personality == EHPersonality::Wasm_CXX;
2088 bool IsSEH = isAsynchronousEHPersonality(Personality);
2089
2090 if (IsWasmCXX) {
2091 findWasmUnwindDestinations(FuncInfo, EHPadBB, Prob, UnwindDests);
2092 assert(UnwindDests.size() <= 1 &&
2093 "There should be at most one unwind destination for wasm");
2094 return;
2095 }
2096
2097 while (EHPadBB) {
2098 const Instruction *Pad = EHPadBB->getFirstNonPHI();
2099 BasicBlock *NewEHPadBB = nullptr;
2100 if (isa<LandingPadInst>(Pad)) {
2101 // Stop on landingpads. They are not funclets.
2102 UnwindDests.emplace_back(FuncInfo.MBBMap[EHPadBB], Prob);
2103 break;
2104 } else if (isa<CleanupPadInst>(Pad)) {
2105 // Stop on cleanup pads. Cleanups are always funclet entries for all known
2106 // personalities.
2107 UnwindDests.emplace_back(FuncInfo.MBBMap[EHPadBB], Prob);
2108 UnwindDests.back().first->setIsEHScopeEntry();
2109 UnwindDests.back().first->setIsEHFuncletEntry();
2110 break;
2111 } else if (const auto *CatchSwitch = dyn_cast<CatchSwitchInst>(Pad)) {
2112 // Add the catchpad handlers to the possible destinations.
2113 for (const BasicBlock *CatchPadBB : CatchSwitch->handlers()) {
2114 UnwindDests.emplace_back(FuncInfo.MBBMap[CatchPadBB], Prob);
2115 // For MSVC++ and the CLR, catchblocks are funclets and need prologues.
2116 if (IsMSVCCXX || IsCoreCLR)
2117 UnwindDests.back().first->setIsEHFuncletEntry();
2118 if (!IsSEH)
2119 UnwindDests.back().first->setIsEHScopeEntry();
2120 }
2121 NewEHPadBB = CatchSwitch->getUnwindDest();
2122 } else {
2123 continue;
2124 }
2125
2126 BranchProbabilityInfo *BPI = FuncInfo.BPI;
2127 if (BPI && NewEHPadBB)
2128 Prob *= BPI->getEdgeProbability(EHPadBB, NewEHPadBB);
2129 EHPadBB = NewEHPadBB;
2130 }
2131}
2132
2133void SelectionDAGBuilder::visitCleanupRet(const CleanupReturnInst &I) {
2134 // Update successor info.
2136 auto UnwindDest = I.getUnwindDest();
2138 BranchProbability UnwindDestProb =
2139 (BPI && UnwindDest)
2140 ? BPI->getEdgeProbability(FuncInfo.MBB->getBasicBlock(), UnwindDest)
2142 findUnwindDestinations(FuncInfo, UnwindDest, UnwindDestProb, UnwindDests);
2143 for (auto &UnwindDest : UnwindDests) {
2144 UnwindDest.first->setIsEHPad();
2145 addSuccessorWithProb(FuncInfo.MBB, UnwindDest.first, UnwindDest.second);
2146 }
2148
2149 // Create the terminator node.
2150 SDValue Ret =
2152 DAG.setRoot(Ret);
2153}
2154
2155void SelectionDAGBuilder::visitCatchSwitch(const CatchSwitchInst &CSI) {
2156 report_fatal_error("visitCatchSwitch not yet implemented!");
2157}
2158
2159void SelectionDAGBuilder::visitRet(const ReturnInst &I) {
2161 auto &DL = DAG.getDataLayout();
2162 SDValue Chain = getControlRoot();
2165
2166 // Calls to @llvm.experimental.deoptimize don't generate a return value, so
2167 // lower
2168 //
2169 // %val = call <ty> @llvm.experimental.deoptimize()
2170 // ret <ty> %val
2171 //
2172 // differently.
2173 if (I.getParent()->getTerminatingDeoptimizeCall()) {
2175 return;
2176 }
2177
2178 if (!FuncInfo.CanLowerReturn) {
2179 unsigned DemoteReg = FuncInfo.DemoteRegister;
2180 const Function *F = I.getParent()->getParent();
2181
2182 // Emit a store of the return value through the virtual register.
2183 // Leave Outs empty so that LowerReturn won't try to load return
2184 // registers the usual way.
2185 SmallVector<EVT, 1> PtrValueVTs;
2186 ComputeValueVTs(TLI, DL,
2187 PointerType::get(F->getContext(),
2189 PtrValueVTs);
2190
2191 SDValue RetPtr =
2192 DAG.getCopyFromReg(Chain, getCurSDLoc(), DemoteReg, PtrValueVTs[0]);
2193 SDValue RetOp = getValue(I.getOperand(0));
2194
2195 SmallVector<EVT, 4> ValueVTs, MemVTs;
2197 ComputeValueVTs(TLI, DL, I.getOperand(0)->getType(), ValueVTs, &MemVTs,
2198 &Offsets, 0);
2199 unsigned NumValues = ValueVTs.size();
2200
2201 SmallVector<SDValue, 4> Chains(NumValues);
2202 Align BaseAlign = DL.getPrefTypeAlign(I.getOperand(0)->getType());
2203 for (unsigned i = 0; i != NumValues; ++i) {
2204 // An aggregate return value cannot wrap around the address space, so
2205 // offsets to its parts don't wrap either.
2207 TypeSize::getFixed(Offsets[i]));
2208
2209 SDValue Val = RetOp.getValue(RetOp.getResNo() + i);
2210 if (MemVTs[i] != ValueVTs[i])
2211 Val = DAG.getPtrExtOrTrunc(Val, getCurSDLoc(), MemVTs[i]);
2212 Chains[i] = DAG.getStore(
2213 Chain, getCurSDLoc(), Val,
2214 // FIXME: better loc info would be nice.
2216 commonAlignment(BaseAlign, Offsets[i]));
2217 }
2218
2220 MVT::Other, Chains);
2221 } else if (I.getNumOperands() != 0) {
2222 SmallVector<EVT, 4> ValueVTs;
2223 ComputeValueVTs(TLI, DL, I.getOperand(0)->getType(), ValueVTs);
2224 unsigned NumValues = ValueVTs.size();
2225 if (NumValues) {
2226 SDValue RetOp = getValue(I.getOperand(0));
2227
2228 const Function *F = I.getParent()->getParent();
2229
2230 bool NeedsRegBlock = TLI.functionArgumentNeedsConsecutiveRegisters(
2231 I.getOperand(0)->getType(), F->getCallingConv(),
2232 /*IsVarArg*/ false, DL);
2233
2234 ISD::NodeType ExtendKind = ISD::ANY_EXTEND;
2235 if (F->getAttributes().hasRetAttr(Attribute::SExt))
2236 ExtendKind = ISD::SIGN_EXTEND;
2237 else if (F->getAttributes().hasRetAttr(Attribute::ZExt))
2238 ExtendKind = ISD::ZERO_EXTEND;
2239
2240 LLVMContext &Context = F->getContext();
2241 bool RetInReg = F->getAttributes().hasRetAttr(Attribute::InReg);
2242
2243 for (unsigned j = 0; j != NumValues; ++j) {
2244 EVT VT = ValueVTs[j];
2245
2246 if (ExtendKind != ISD::ANY_EXTEND && VT.isInteger())
2247 VT = TLI.getTypeForExtReturn(Context, VT, ExtendKind);
2248
2249 CallingConv::ID CC = F->getCallingConv();
2250
2251 unsigned NumParts = TLI.getNumRegistersForCallingConv(Context, CC, VT);
2252 MVT PartVT = TLI.getRegisterTypeForCallingConv(Context, CC, VT);
2253 SmallVector<SDValue, 4> Parts(NumParts);
2255 SDValue(RetOp.getNode(), RetOp.getResNo() + j),
2256 &Parts[0], NumParts, PartVT, &I, CC, ExtendKind);
2257
2258 // 'inreg' on function refers to return value
2260 if (RetInReg)
2261 Flags.setInReg();
2262
2263 if (I.getOperand(0)->getType()->isPointerTy()) {
2264 Flags.setPointer();
2265 Flags.setPointerAddrSpace(
2266 cast<PointerType>(I.getOperand(0)->getType())->getAddressSpace());
2267 }
2268
2269 if (NeedsRegBlock) {
2270 Flags.setInConsecutiveRegs();
2271 if (j == NumValues - 1)
2272 Flags.setInConsecutiveRegsLast();
2273 }
2274
2275 // Propagate extension type if any
2276 if (ExtendKind == ISD::SIGN_EXTEND)
2277 Flags.setSExt();
2278 else if (ExtendKind == ISD::ZERO_EXTEND)
2279 Flags.setZExt();
2280
2281 for (unsigned i = 0; i < NumParts; ++i) {
2282 Outs.push_back(ISD::OutputArg(Flags,
2283 Parts[i].getValueType().getSimpleVT(),
2284 VT, /*isfixed=*/true, 0, 0));
2285 OutVals.push_back(Parts[i]);
2286 }
2287 }
2288 }
2289 }
2290
2291 // Push in swifterror virtual register as the last element of Outs. This makes
2292 // sure swifterror virtual register will be returned in the swifterror
2293 // physical register.
2294 const Function *F = I.getParent()->getParent();
2295 if (TLI.supportSwiftError() &&
2296 F->getAttributes().hasAttrSomewhere(Attribute::SwiftError)) {
2297 assert(SwiftError.getFunctionArg() && "Need a swift error argument");
2299 Flags.setSwiftError();
2301 Flags, /*vt=*/TLI.getPointerTy(DL), /*argvt=*/EVT(TLI.getPointerTy(DL)),
2302 /*isfixed=*/true, /*origidx=*/1, /*partOffs=*/0));
2303 // Create SDNode for the swifterror virtual register.
2304 OutVals.push_back(
2307 EVT(TLI.getPointerTy(DL))));
2308 }
2309
2310 bool isVarArg = DAG.getMachineFunction().getFunction().isVarArg();
2311 CallingConv::ID CallConv =
2314 Chain, CallConv, isVarArg, Outs, OutVals, getCurSDLoc(), DAG);
2315
2316 // Verify that the target's LowerReturn behaved as expected.
2317 assert(Chain.getNode() && Chain.getValueType() == MVT::Other &&
2318 "LowerReturn didn't return a valid chain!");
2319
2320 // Update the DAG with the new chain value resulting from return lowering.
2321 DAG.setRoot(Chain);
2322}
2323
2324/// CopyToExportRegsIfNeeded - If the given value has virtual registers
2325/// created for it, emit nodes to copy the value into the virtual
2326/// registers.
2328 // Skip empty types
2329 if (V->getType()->isEmptyTy())
2330 return;
2331
2333 if (VMI != FuncInfo.ValueMap.end()) {
2334 assert((!V->use_empty() || isa<CallBrInst>(V)) &&
2335 "Unused value assigned virtual registers!");
2336 CopyValueToVirtualRegister(V, VMI->second);
2337 }
2338}
2339
2340/// ExportFromCurrentBlock - If this condition isn't known to be exported from
2341/// the current basic block, add it to ValueMap now so that we'll get a
2342/// CopyTo/FromReg.
2344 // No need to export constants.
2345 if (!isa<Instruction>(V) && !isa<Argument>(V)) return;
2346
2347 // Already exported?
2348 if (FuncInfo.isExportedInst(V)) return;
2349
2352}
2353
2355 const BasicBlock *FromBB) {
2356 // The operands of the setcc have to be in this block. We don't know
2357 // how to export them from some other block.
2358 if (const Instruction *VI = dyn_cast<Instruction>(V)) {
2359 // Can export from current BB.
2360 if (VI->getParent() == FromBB)
2361 return true;
2362
2363 // Is already exported, noop.
2364 return FuncInfo.isExportedInst(V);
2365 }
2366
2367 // If this is an argument, we can export it if the BB is the entry block or
2368 // if it is already exported.
2369 if (isa<Argument>(V)) {
2370 if (FromBB->isEntryBlock())
2371 return true;
2372
2373 // Otherwise, can only export this if it is already exported.
2374 return FuncInfo.isExportedInst(V);
2375 }
2376
2377 // Otherwise, constants can always be exported.
2378 return true;
2379}
2380
2381/// Return branch probability calculated by BranchProbabilityInfo for IR blocks.
2383SelectionDAGBuilder::getEdgeProbability(const MachineBasicBlock *Src,
2384 const MachineBasicBlock *Dst) const {
2386 const BasicBlock *SrcBB = Src->getBasicBlock();
2387 const BasicBlock *DstBB = Dst->getBasicBlock();
2388 if (!BPI) {
2389 // If BPI is not available, set the default probability as 1 / N, where N is
2390 // the number of successors.
2391 auto SuccSize = std::max<uint32_t>(succ_size(SrcBB), 1);
2392 return BranchProbability(1, SuccSize);
2393 }
2394 return BPI->getEdgeProbability(SrcBB, DstBB);
2395}
2396
2397void SelectionDAGBuilder::addSuccessorWithProb(MachineBasicBlock *Src,
2398 MachineBasicBlock *Dst,
2399 BranchProbability Prob) {
2400 if (!FuncInfo.BPI)
2401 Src->addSuccessorWithoutProb(Dst);
2402 else {
2403 if (Prob.isUnknown())
2404 Prob = getEdgeProbability(Src, Dst);
2405 Src->addSuccessor(Dst, Prob);
2406 }
2407}
2408
2409static bool InBlock(const Value *V, const BasicBlock *BB) {
2410 if (const Instruction *I = dyn_cast<Instruction>(V))
2411 return I->getParent() == BB;
2412 return true;
2413}
2414
2415/// EmitBranchForMergedCondition - Helper method for FindMergedConditions.
2416/// This function emits a branch and is used at the leaves of an OR or an
2417/// AND operator tree.
2418void
2421 MachineBasicBlock *FBB,
2422 MachineBasicBlock *CurBB,
2423 MachineBasicBlock *SwitchBB,
2424 BranchProbability TProb,
2425 BranchProbability FProb,
2426 bool InvertCond) {
2427 const BasicBlock *BB = CurBB->getBasicBlock();
2428
2429 // If the leaf of the tree is a comparison, merge the condition into
2430 // the caseblock.
2431 if (const CmpInst *BOp = dyn_cast<CmpInst>(Cond)) {
2432 // The operands of the cmp have to be in this block. We don't know
2433 // how to export them from some other block. If this is the first block
2434 // of the sequence, no exporting is needed.
2435 if (CurBB == SwitchBB ||
2436 (isExportableFromCurrentBlock(BOp->getOperand(0), BB) &&
2437 isExportableFromCurrentBlock(BOp->getOperand(1), BB))) {
2438 ISD::CondCode Condition;
2439 if (const ICmpInst *IC = dyn_cast<ICmpInst>(Cond)) {
2440 ICmpInst::Predicate Pred =
2441 InvertCond ? IC->getInversePredicate() : IC->getPredicate();
2442 Condition = getICmpCondCode(Pred);
2443 } else {
2444 const FCmpInst *FC = cast<FCmpInst>(Cond);
2445 FCmpInst::Predicate Pred =
2446 InvertCond ? FC->getInversePredicate() : FC->getPredicate();
2447 Condition = getFCmpCondCode(Pred);
2448 if (TM.Options.NoNaNsFPMath)
2449 Condition = getFCmpCodeWithoutNaN(Condition);
2450 }
2451
2452 CaseBlock CB(Condition, BOp->getOperand(0), BOp->getOperand(1), nullptr,
2453 TBB, FBB, CurBB, getCurSDLoc(), TProb, FProb);
2454 SL->SwitchCases.push_back(CB);
2455 return;
2456 }
2457 }
2458
2459 // Create a CaseBlock record representing this branch.
2460 ISD::CondCode Opc = InvertCond ? ISD::SETNE : ISD::SETEQ;
2462 nullptr, TBB, FBB, CurBB, getCurSDLoc(), TProb, FProb);
2463 SL->SwitchCases.push_back(CB);
2464}
2465
2466// Collect dependencies on V recursively. This is used for the cost analysis in
2467// `shouldKeepJumpConditionsTogether`.
2471 unsigned Depth = 0) {
2472 // Return false if we have an incomplete count.
2474 return false;
2475
2476 auto *I = dyn_cast<Instruction>(V);
2477 if (I == nullptr)
2478 return true;
2479
2480 if (Necessary != nullptr) {
2481 // This instruction is necessary for the other side of the condition so
2482 // don't count it.
2483 if (Necessary->contains(I))
2484 return true;
2485 }
2486
2487 // Already added this dep.
2488 if (!Deps->try_emplace(I, false).second)
2489 return true;
2490
2491 for (unsigned OpIdx = 0, E = I->getNumOperands(); OpIdx < E; ++OpIdx)
2492 if (!collectInstructionDeps(Deps, I->getOperand(OpIdx), Necessary,
2493 Depth + 1))
2494 return false;
2495 return true;
2496}
2497
2499 const FunctionLoweringInfo &FuncInfo, const BranchInst &I,
2500 Instruction::BinaryOps Opc, const Value *Lhs, const Value *Rhs,
2502 if (I.getNumSuccessors() != 2)
2503 return false;
2504
2505 if (!I.isConditional())
2506 return false;
2507
2508 if (Params.BaseCost < 0)
2509 return false;
2510
2511 // Baseline cost.
2512 InstructionCost CostThresh = Params.BaseCost;
2513
2514 BranchProbabilityInfo *BPI = nullptr;
2515 if (Params.LikelyBias || Params.UnlikelyBias)
2516 BPI = FuncInfo.BPI;
2517 if (BPI != nullptr) {
2518 // See if we are either likely to get an early out or compute both lhs/rhs
2519 // of the condition.
2520 BasicBlock *IfFalse = I.getSuccessor(0);
2521 BasicBlock *IfTrue = I.getSuccessor(1);
2522
2523 std::optional<bool> Likely;
2524 if (BPI->isEdgeHot(I.getParent(), IfTrue))
2525 Likely = true;
2526 else if (BPI->isEdgeHot(I.getParent(), IfFalse))
2527 Likely = false;
2528
2529 if (Likely) {
2530 if (Opc == (*Likely ? Instruction::And : Instruction::Or))
2531 // Its likely we will have to compute both lhs and rhs of condition
2532 CostThresh += Params.LikelyBias;
2533 else {
2534 if (Params.UnlikelyBias < 0)
2535 return false;
2536 // Its likely we will get an early out.
2537 CostThresh -= Params.UnlikelyBias;
2538 }
2539 }
2540 }
2541
2542 if (CostThresh <= 0)
2543 return false;
2544
2545 // Collect "all" instructions that lhs condition is dependent on.
2546 // Use map for stable iteration (to avoid non-determanism of iteration of
2547 // SmallPtrSet). The `bool` value is just a dummy.
2549 collectInstructionDeps(&LhsDeps, Lhs);
2550 // Collect "all" instructions that rhs condition is dependent on AND are
2551 // dependencies of lhs. This gives us an estimate on which instructions we
2552 // stand to save by splitting the condition.
2553 if (!collectInstructionDeps(&RhsDeps, Rhs, &LhsDeps))
2554 return false;
2555 // Add the compare instruction itself unless its a dependency on the LHS.
2556 if (const auto *RhsI = dyn_cast<Instruction>(Rhs))
2557 if (!LhsDeps.contains(RhsI))
2558 RhsDeps.try_emplace(RhsI, false);
2559
2560 const auto &TLI = DAG.getTargetLoweringInfo();
2561 const auto &TTI =
2562 TLI.getTargetMachine().getTargetTransformInfo(*I.getFunction());
2563
2564 InstructionCost CostOfIncluding = 0;
2565 // See if this instruction will need to computed independently of whether RHS
2566 // is.
2567 Value *BrCond = I.getCondition();
2568 auto ShouldCountInsn = [&RhsDeps, &BrCond](const Instruction *Ins) {
2569 for (const auto *U : Ins->users()) {
2570 // If user is independent of RHS calculation we don't need to count it.
2571 if (auto *UIns = dyn_cast<Instruction>(U))
2572 if (UIns != BrCond && !RhsDeps.contains(UIns))
2573 return false;
2574 }
2575 return true;
2576 };
2577
2578 // Prune instructions from RHS Deps that are dependencies of unrelated
2579 // instructions. The value (SelectionDAG::MaxRecursionDepth) is fairly
2580 // arbitrary and just meant to cap the how much time we spend in the pruning
2581 // loop. Its highly unlikely to come into affect.
2582 const unsigned MaxPruneIters = SelectionDAG::MaxRecursionDepth;
2583 // Stop after a certain point. No incorrectness from including too many
2584 // instructions.
2585 for (unsigned PruneIters = 0; PruneIters < MaxPruneIters; ++PruneIters) {
2586 const Instruction *ToDrop = nullptr;
2587 for (const auto &InsPair : RhsDeps) {
2588 if (!ShouldCountInsn(InsPair.first)) {
2589 ToDrop = InsPair.first;
2590 break;
2591 }
2592 }
2593 if (ToDrop == nullptr)
2594 break;
2595 RhsDeps.erase(ToDrop);
2596 }
2597
2598 for (const auto &InsPair : RhsDeps) {
2599 // Finally accumulate latency that we can only attribute to computing the
2600 // RHS condition. Use latency because we are essentially trying to calculate
2601 // the cost of the dependency chain.
2602 // Possible TODO: We could try to estimate ILP and make this more precise.
2603 CostOfIncluding +=
2605
2606 if (CostOfIncluding > CostThresh)
2607 return false;
2608 }
2609 return true;
2610}
2611
2614 MachineBasicBlock *FBB,
2615 MachineBasicBlock *CurBB,
2616 MachineBasicBlock *SwitchBB,
2618 BranchProbability TProb,
2619 BranchProbability FProb,
2620 bool InvertCond) {
2621 // Skip over not part of the tree and remember to invert op and operands at
2622 // next level.
2623 Value *NotCond;
2624 if (match(Cond, m_OneUse(m_Not(m_Value(NotCond)))) &&
2625 InBlock(NotCond, CurBB->getBasicBlock())) {
2626 FindMergedConditions(NotCond, TBB, FBB, CurBB, SwitchBB, Opc, TProb, FProb,
2627 !InvertCond);
2628 return;
2629 }
2630
2631 const Instruction *BOp = dyn_cast<Instruction>(Cond);
2632 const Value *BOpOp0, *BOpOp1;
2633 // Compute the effective opcode for Cond, taking into account whether it needs
2634 // to be inverted, e.g.
2635 // and (not (or A, B)), C
2636 // gets lowered as
2637 // and (and (not A, not B), C)
2639 if (BOp) {
2640 BOpc = match(BOp, m_LogicalAnd(m_Value(BOpOp0), m_Value(BOpOp1)))
2641 ? Instruction::And
2642 : (match(BOp, m_LogicalOr(m_Value(BOpOp0), m_Value(BOpOp1)))
2643 ? Instruction::Or
2645 if (InvertCond) {
2646 if (BOpc == Instruction::And)
2647 BOpc = Instruction::Or;
2648 else if (BOpc == Instruction::Or)
2649 BOpc = Instruction::And;
2650 }
2651 }
2652
2653 // If this node is not part of the or/and tree, emit it as a branch.
2654 // Note that all nodes in the tree should have same opcode.
2655 bool BOpIsInOrAndTree = BOpc && BOpc == Opc && BOp->hasOneUse();
2656 if (!BOpIsInOrAndTree || BOp->getParent() != CurBB->getBasicBlock() ||
2657 !InBlock(BOpOp0, CurBB->getBasicBlock()) ||
2658 !InBlock(BOpOp1, CurBB->getBasicBlock())) {
2659 EmitBranchForMergedCondition(Cond, TBB, FBB, CurBB, SwitchBB,
2660 TProb, FProb, InvertCond);
2661 return;
2662 }
2663
2664 // Create TmpBB after CurBB.
2665 MachineFunction::iterator BBI(CurBB);
2668 CurBB->getParent()->insert(++BBI, TmpBB);
2669
2670 if (Opc == Instruction::Or) {
2671 // Codegen X | Y as:
2672 // BB1:
2673 // jmp_if_X TBB
2674 // jmp TmpBB
2675 // TmpBB:
2676 // jmp_if_Y TBB
2677 // jmp FBB
2678 //
2679
2680 // We have flexibility in setting Prob for BB1 and Prob for TmpBB.
2681 // The requirement is that
2682 // TrueProb for BB1 + (FalseProb for BB1 * TrueProb for TmpBB)
2683 // = TrueProb for original BB.
2684 // Assuming the original probabilities are A and B, one choice is to set
2685 // BB1's probabilities to A/2 and A/2+B, and set TmpBB's probabilities to
2686 // A/(1+B) and 2B/(1+B). This choice assumes that
2687 // TrueProb for BB1 == FalseProb for BB1 * TrueProb for TmpBB.
2688 // Another choice is to assume TrueProb for BB1 equals to TrueProb for
2689 // TmpBB, but the math is more complicated.
2690
2691 auto NewTrueProb = TProb / 2;
2692 auto NewFalseProb = TProb / 2 + FProb;
2693 // Emit the LHS condition.
2694 FindMergedConditions(BOpOp0, TBB, TmpBB, CurBB, SwitchBB, Opc, NewTrueProb,
2695 NewFalseProb, InvertCond);
2696
2697 // Normalize A/2 and B to get A/(1+B) and 2B/(1+B).
2698 SmallVector<BranchProbability, 2> Probs{TProb / 2, FProb};
2699 BranchProbability::normalizeProbabilities(Probs.begin(), Probs.end());
2700 // Emit the RHS condition into TmpBB.
2701 FindMergedConditions(BOpOp1, TBB, FBB, TmpBB, SwitchBB, Opc, Probs[0],
2702 Probs[1], InvertCond);
2703 } else {
2704 assert(Opc == Instruction::And && "Unknown merge op!");
2705 // Codegen X & Y as:
2706 // BB1:
2707 // jmp_if_X TmpBB
2708 // jmp FBB
2709 // TmpBB:
2710 // jmp_if_Y TBB
2711 // jmp FBB
2712 //
2713 // This requires creation of TmpBB after CurBB.
2714
2715 // We have flexibility in setting Prob for BB1 and Prob for TmpBB.
2716 // The requirement is that
2717 // FalseProb for BB1 + (TrueProb for BB1 * FalseProb for TmpBB)
2718 // = FalseProb for original BB.
2719 // Assuming the original probabilities are A and B, one choice is to set
2720 // BB1's probabilities to A+B/2 and B/2, and set TmpBB's probabilities to
2721 // 2A/(1+A) and B/(1+A). This choice assumes that FalseProb for BB1 ==
2722 // TrueProb for BB1 * FalseProb for TmpBB.
2723
2724 auto NewTrueProb = TProb + FProb / 2;
2725 auto NewFalseProb = FProb / 2;
2726 // Emit the LHS condition.
2727 FindMergedConditions(BOpOp0, TmpBB, FBB, CurBB, SwitchBB, Opc, NewTrueProb,
2728 NewFalseProb, InvertCond);
2729
2730 // Normalize A and B/2 to get 2A/(1+A) and B/(1+A).
2731 SmallVector<BranchProbability, 2> Probs{TProb, FProb / 2};
2732 BranchProbability::normalizeProbabilities(Probs.begin(), Probs.end());
2733 // Emit the RHS condition into TmpBB.
2734 FindMergedConditions(BOpOp1, TBB, FBB, TmpBB, SwitchBB, Opc, Probs[0],
2735 Probs[1], InvertCond);
2736 }
2737}
2738
2739/// If the set of cases should be emitted as a series of branches, return true.
2740/// If we should emit this as a bunch of and/or'd together conditions, return
2741/// false.
2742bool
2743SelectionDAGBuilder::ShouldEmitAsBranches(const std::vector<CaseBlock> &Cases) {
2744 if (Cases.size() != 2) return true;
2745
2746 // If this is two comparisons of the same values or'd or and'd together, they
2747 // will get folded into a single comparison, so don't emit two blocks.
2748 if ((Cases[0].CmpLHS == Cases[1].CmpLHS &&
2749 Cases[0].CmpRHS == Cases[1].CmpRHS) ||
2750 (Cases[0].CmpRHS == Cases[1].CmpLHS &&
2751 Cases[0].CmpLHS == Cases[1].CmpRHS)) {
2752 return false;
2753 }
2754
2755 // Handle: (X != null) | (Y != null) --> (X|Y) != 0
2756 // Handle: (X == null) & (Y == null) --> (X|Y) == 0
2757 if (Cases[0].CmpRHS == Cases[1].CmpRHS &&
2758 Cases[0].CC == Cases[1].CC &&
2759 isa<Constant>(Cases[0].CmpRHS) &&
2760 cast<Constant>(Cases[0].CmpRHS)->isNullValue()) {
2761 if (Cases[0].CC == ISD::SETEQ && Cases[0].TrueBB == Cases[1].ThisBB)
2762 return false;
2763 if (Cases[0].CC == ISD::SETNE && Cases[0].FalseBB == Cases[1].ThisBB)
2764 return false;
2765 }
2766
2767 return true;
2768}
2769
2770void SelectionDAGBuilder::visitBr(const BranchInst &I) {
2772
2773 // Update machine-CFG edges.
2774 MachineBasicBlock *Succ0MBB = FuncInfo.MBBMap[I.getSuccessor(0)];
2775
2776 if (I.isUnconditional()) {
2777 // Update machine-CFG edges.
2778 BrMBB->addSuccessor(Succ0MBB);
2779
2780 // If this is not a fall-through branch or optimizations are switched off,
2781 // emit the branch.
2782 if (Succ0MBB != NextBlock(BrMBB) ||
2784 auto Br = DAG.getNode(ISD::BR, getCurSDLoc(), MVT::Other,
2785 getControlRoot(), DAG.getBasicBlock(Succ0MBB));
2786 setValue(&I, Br);
2787 DAG.setRoot(Br);
2788 }
2789
2790 return;
2791 }
2792
2793 // If this condition is one of the special cases we handle, do special stuff
2794 // now.
2795 const Value *CondVal = I.getCondition();
2796 MachineBasicBlock *Succ1MBB = FuncInfo.MBBMap[I.getSuccessor(1)];
2797
2798 // If this is a series of conditions that are or'd or and'd together, emit
2799 // this as a sequence of branches instead of setcc's with and/or operations.
2800 // As long as jumps are not expensive (exceptions for multi-use logic ops,
2801 // unpredictable branches, and vector extracts because those jumps are likely
2802 // expensive for any target), this should improve performance.
2803 // For example, instead of something like:
2804 // cmp A, B
2805 // C = seteq
2806 // cmp D, E
2807 // F = setle
2808 // or C, F
2809 // jnz foo
2810 // Emit:
2811 // cmp A, B
2812 // je foo
2813 // cmp D, E
2814 // jle foo
2815 const Instruction *BOp = dyn_cast<Instruction>(CondVal);
2816 if (!DAG.getTargetLoweringInfo().isJumpExpensive() && BOp &&
2817 BOp->hasOneUse() && !I.hasMetadata(LLVMContext::MD_unpredictable)) {
2818 Value *Vec;
2819 const Value *BOp0, *BOp1;
2821 if (match(BOp, m_LogicalAnd(m_Value(BOp0), m_Value(BOp1))))
2822 Opcode = Instruction::And;
2823 else if (match(BOp, m_LogicalOr(m_Value(BOp0), m_Value(BOp1))))
2824 Opcode = Instruction::Or;
2825
2826 if (Opcode &&
2827 !(match(BOp0, m_ExtractElt(m_Value(Vec), m_Value())) &&
2828 match(BOp1, m_ExtractElt(m_Specific(Vec), m_Value()))) &&
2830 FuncInfo, I, Opcode, BOp0, BOp1,
2832 Opcode, BOp0, BOp1))) {
2833 FindMergedConditions(BOp, Succ0MBB, Succ1MBB, BrMBB, BrMBB, Opcode,
2834 getEdgeProbability(BrMBB, Succ0MBB),
2835 getEdgeProbability(BrMBB, Succ1MBB),
2836 /*InvertCond=*/false);
2837 // If the compares in later blocks need to use values not currently
2838 // exported from this block, export them now. This block should always
2839 // be the first entry.
2840 assert(SL->SwitchCases[0].ThisBB == BrMBB && "Unexpected lowering!");
2841
2842 // Allow some cases to be rejected.
2843 if (ShouldEmitAsBranches(SL->SwitchCases)) {
2844 for (unsigned i = 1, e = SL->SwitchCases.size(); i != e; ++i) {
2845 ExportFromCurrentBlock(SL->SwitchCases[i].CmpLHS);
2846 ExportFromCurrentBlock(SL->SwitchCases[i].CmpRHS);
2847 }
2848
2849 // Emit the branch for this block.
2850 visitSwitchCase(SL->SwitchCases[0], BrMBB);
2851 SL->SwitchCases.erase(SL->SwitchCases.begin());
2852 return;
2853 }
2854
2855 // Okay, we decided not to do this, remove any inserted MBB's and clear
2856 // SwitchCases.
2857 for (unsigned i = 1, e = SL->SwitchCases.size(); i != e; ++i)
2858 FuncInfo.MF->erase(SL->SwitchCases[i].ThisBB);
2859
2860 SL->SwitchCases.clear();
2861 }
2862 }
2863
2864 // Create a CaseBlock record representing this branch.
2866 nullptr, Succ0MBB, Succ1MBB, BrMBB, getCurSDLoc());
2867
2868 // Use visitSwitchCase to actually insert the fast branch sequence for this
2869 // cond branch.
2870 visitSwitchCase(CB, BrMBB);
2871}
2872
2873/// visitSwitchCase - Emits the necessary code to represent a single node in
2874/// the binary search tree resulting from lowering a switch instruction.
2876 MachineBasicBlock *SwitchBB) {
2877 SDValue Cond;
2878 SDValue CondLHS = getValue(CB.CmpLHS);
2879 SDLoc dl = CB.DL;
2880
2881 if (CB.CC == ISD::SETTRUE) {
2882 // Branch or fall through to TrueBB.
2883 addSuccessorWithProb(SwitchBB, CB.TrueBB, CB.TrueProb);
2884 SwitchBB->normalizeSuccProbs();
2885 if (CB.TrueBB != NextBlock(SwitchBB)) {
2886 DAG.setRoot(DAG.getNode(ISD::BR, dl, MVT::Other, getControlRoot(),
2887 DAG.getBasicBlock(CB.TrueBB)));
2888 }
2889 return;
2890 }
2891
2892 auto &TLI = DAG.getTargetLoweringInfo();
2893 EVT MemVT = TLI.getMemValueType(DAG.getDataLayout(), CB.CmpLHS->getType());
2894
2895 // Build the setcc now.
2896 if (!CB.CmpMHS) {
2897 // Fold "(X == true)" to X and "(X == false)" to !X to
2898 // handle common cases produced by branch lowering.
2899 if (CB.CmpRHS == ConstantInt::getTrue(*DAG.getContext()) &&
2900 CB.CC == ISD::SETEQ)
2901 Cond = CondLHS;
2902 else if (CB.CmpRHS == ConstantInt::getFalse(*DAG.getContext()) &&
2903 CB.CC == ISD::SETEQ) {
2904 SDValue True = DAG.getConstant(1, dl, CondLHS.getValueType());
2905 Cond = DAG.getNode(ISD::XOR, dl, CondLHS.getValueType(), CondLHS, True);
2906 } else {
2907 SDValue CondRHS = getValue(CB.CmpRHS);
2908
2909 // If a pointer's DAG type is larger than its memory type then the DAG
2910 // values are zero-extended. This breaks signed comparisons so truncate
2911 // back to the underlying type before doing the compare.
2912 if (CondLHS.getValueType() != MemVT) {
2913 CondLHS = DAG.getPtrExtOrTrunc(CondLHS, getCurSDLoc(), MemVT);
2914 CondRHS = DAG.getPtrExtOrTrunc(CondRHS, getCurSDLoc(), MemVT);
2915 }
2916 Cond = DAG.getSetCC(dl, MVT::i1, CondLHS, CondRHS, CB.CC);
2917 }
2918 } else {
2919 assert(CB.CC == ISD::SETLE && "Can handle only LE ranges now");
2920
2921 const APInt& Low = cast<ConstantInt>(CB.CmpLHS)->getValue();
2922 const APInt& High = cast<ConstantInt>(CB.CmpRHS)->getValue();
2923
2924 SDValue CmpOp = getValue(CB.CmpMHS);
2925 EVT VT = CmpOp.getValueType();
2926
2927 if (cast<ConstantInt>(CB.CmpLHS)->isMinValue(true)) {
2928 Cond = DAG.getSetCC(dl, MVT::i1, CmpOp, DAG.getConstant(High, dl, VT),
2929 ISD::SETLE);
2930 } else {
2931 SDValue SUB = DAG.getNode(ISD::SUB, dl,
2932 VT, CmpOp, DAG.getConstant(Low, dl, VT));
2933 Cond = DAG.getSetCC(dl, MVT::i1, SUB,
2934 DAG.getConstant(High-Low, dl, VT), ISD::SETULE);
2935 }
2936 }
2937
2938 // Update successor info
2939 addSuccessorWithProb(SwitchBB, CB.TrueBB, CB.TrueProb);
2940 // TrueBB and FalseBB are always different unless the incoming IR is
2941 // degenerate. This only happens when running llc on weird IR.
2942 if (CB.TrueBB != CB.FalseBB)
2943 addSuccessorWithProb(SwitchBB, CB.FalseBB, CB.FalseProb);
2944 SwitchBB->normalizeSuccProbs();
2945
2946 // If the lhs block is the next block, invert the condition so that we can
2947 // fall through to the lhs instead of the rhs block.
2948 if (CB.TrueBB == NextBlock(SwitchBB)) {
2949 std::swap(CB.TrueBB, CB.FalseBB);
2950 SDValue True = DAG.getConstant(1, dl, Cond.getValueType());
2951 Cond = DAG.getNode(ISD::XOR, dl, Cond.getValueType(), Cond, True);
2952 }
2953
2954 SDValue BrCond = DAG.getNode(ISD::BRCOND, dl,
2955 MVT::Other, getControlRoot(), Cond,
2957
2958 setValue(CurInst, BrCond);
2959
2960 // Insert the false branch. Do this even if it's a fall through branch,
2961 // this makes it easier to do DAG optimizations which require inverting
2962 // the branch condition.
2963 BrCond = DAG.getNode(ISD::BR, dl, MVT::Other, BrCond,
2965
2966 DAG.setRoot(BrCond);
2967}
2968
2969/// visitJumpTable - Emit JumpTable node in the current MBB
2971 // Emit the code for the jump table
2972 assert(JT.SL && "Should set SDLoc for SelectionDAG!");
2973 assert(JT.Reg != -1U && "Should lower JT Header first!");
2975 SDValue Index = DAG.getCopyFromReg(getControlRoot(), *JT.SL, JT.Reg, PTy);
2976 SDValue Table = DAG.getJumpTable(JT.JTI, PTy);
2977 SDValue BrJumpTable = DAG.getNode(ISD::BR_JT, *JT.SL, MVT::Other,
2978 Index.getValue(1), Table, Index);
2979 DAG.setRoot(BrJumpTable);
2980}
2981
2982/// visitJumpTableHeader - This function emits necessary code to produce index
2983/// in the JumpTable from switch case.
2985 JumpTableHeader &JTH,
2986 MachineBasicBlock *SwitchBB) {
2987 assert(JT.SL && "Should set SDLoc for SelectionDAG!");
2988 const SDLoc &dl = *JT.SL;
2989
2990 // Subtract the lowest switch case value from the value being switched on.
2991 SDValue SwitchOp = getValue(JTH.SValue);
2992 EVT VT = SwitchOp.getValueType();
2993 SDValue Sub = DAG.getNode(ISD::SUB, dl, VT, SwitchOp,
2994 DAG.getConstant(JTH.First, dl, VT));
2995
2996 // The SDNode we just created, which holds the value being switched on minus
2997 // the smallest case value, needs to be copied to a virtual register so it
2998 // can be used as an index into the jump table in a subsequent basic block.
2999 // This value may be smaller or larger than the target's pointer type, and
3000 // therefore require extension or truncating.
3002 SwitchOp = DAG.getZExtOrTrunc(Sub, dl, TLI.getPointerTy(DAG.getDataLayout()));
3003
3004 unsigned JumpTableReg =
3006 SDValue CopyTo = DAG.getCopyToReg(getControlRoot(), dl,
3007 JumpTableReg, SwitchOp);
3008 JT.Reg = JumpTableReg;
3009
3010 if (!JTH.FallthroughUnreachable) {
3011 // Emit the range check for the jump table, and branch to the default block
3012 // for the switch statement if the value being switched on exceeds the
3013 // largest case in the switch.
3014 SDValue CMP = DAG.getSetCC(
3016 Sub.getValueType()),
3017 Sub, DAG.getConstant(JTH.Last - JTH.First, dl, VT), ISD::SETUGT);
3018
3019 SDValue BrCond = DAG.getNode(ISD::BRCOND, dl,
3020 MVT::Other, CopyTo, CMP,
3021 DAG.getBasicBlock(JT.Default));
3022
3023 // Avoid emitting unnecessary branches to the next block.
3024 if (JT.MBB != NextBlock(SwitchBB))
3025 BrCond = DAG.getNode(ISD::BR, dl, MVT::Other, BrCond,
3026 DAG.getBasicBlock(JT.MBB));
3027
3028 DAG.setRoot(BrCond);
3029 } else {
3030 // Avoid emitting unnecessary branches to the next block.
3031 if (JT.MBB != NextBlock(SwitchBB))
3032 DAG.setRoot(DAG.getNode(ISD::BR, dl, MVT::Other, CopyTo,
3033 DAG.getBasicBlock(JT.MBB)));
3034 else
3035 DAG.setRoot(CopyTo);
3036 }
3037}
3038
3039/// Create a LOAD_STACK_GUARD node, and let it carry the target specific global
3040/// variable if there exists one.
3042 SDValue &Chain) {
3043 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
3044 EVT PtrTy = TLI.getPointerTy(DAG.getDataLayout());
3045 EVT PtrMemTy = TLI.getPointerMemTy(DAG.getDataLayout());
3049 DAG.getMachineNode(TargetOpcode::LOAD_STACK_GUARD, DL, PtrTy, Chain);
3050 if (Global) {
3051 MachinePointerInfo MPInfo(Global);
3055 MPInfo, Flags, LocationSize::precise(PtrTy.getSizeInBits() / 8),
3056 DAG.getEVTAlign(PtrTy));
3057 DAG.setNodeMemRefs(Node, {MemRef});
3058 }
3059 if (PtrTy != PtrMemTy)
3060 return DAG.getPtrExtOrTrunc(SDValue(Node, 0), DL, PtrMemTy);
3061 return SDValue(Node, 0);
3062}
3063
3064/// Codegen a new tail for a stack protector check ParentMBB which has had its
3065/// tail spliced into a stack protector check success bb.
3066///
3067/// For a high level explanation of how this fits into the stack protector
3068/// generation see the comment on the declaration of class
3069/// StackProtectorDescriptor.
3071 MachineBasicBlock *ParentBB) {
3072
3073 // First create the loads to the guard/stack slot for the comparison.
3075 EVT PtrTy = TLI.getPointerTy(DAG.getDataLayout());
3076 EVT PtrMemTy = TLI.getPointerMemTy(DAG.getDataLayout());
3077
3078 MachineFrameInfo &MFI = ParentBB->getParent()->getFrameInfo();
3079 int FI = MFI.getStackProtectorIndex();
3080
3081 SDValue Guard;
3082 SDLoc dl = getCurSDLoc();
3083 SDValue StackSlotPtr = DAG.getFrameIndex(FI, PtrTy);
3084 const Module &M = *ParentBB->getParent()->getFunction().getParent();
3085 Align Align =
3086 DAG.getDataLayout().getPrefTypeAlign(PointerType::get(M.getContext(), 0));
3087
3088 // Generate code to load the content of the guard slot.
3089 SDValue GuardVal = DAG.getLoad(
3090 PtrMemTy, dl, DAG.getEntryNode(), StackSlotPtr,
3093
3094 if (TLI.useStackGuardXorFP())
3095 GuardVal = TLI.emitStackGuardXorFP(DAG, GuardVal, dl);
3096
3097 // Retrieve guard check function, nullptr if instrumentation is inlined.
3098 if (const Function *GuardCheckFn = TLI.getSSPStackGuardCheck(M)) {
3099 // The target provides a guard check function to validate the guard value.
3100 // Generate a call to that function with the content of the guard slot as
3101 // argument.
3102 FunctionType *FnTy = GuardCheckFn->getFunctionType();
3103 assert(FnTy->getNumParams() == 1 && "Invalid function signature");
3104
3107 Entry.Node = GuardVal;
3108 Entry.Ty = FnTy->getParamType(0);
3109 if (GuardCheckFn->hasParamAttribute(0, Attribute::AttrKind::InReg))
3110 Entry.IsInReg = true;
3111 Args.push_back(Entry);
3112
3116 .setCallee(GuardCheckFn->getCallingConv(), FnTy->getReturnType(),
3117 getValue(GuardCheckFn), std::move(Args));
3118
3119 std::pair<SDValue, SDValue> Result = TLI.LowerCallTo(CLI);
3120 DAG.setRoot(Result.second);
3121 return;
3122 }
3123
3124 // If useLoadStackGuardNode returns true, generate LOAD_STACK_GUARD.
3125 // Otherwise, emit a volatile load to retrieve the stack guard value.
3126 SDValue Chain = DAG.getEntryNode();
3127 if (TLI.useLoadStackGuardNode()) {
3128 Guard = getLoadStackGuard(DAG, dl, Chain);
3129 } else {
3130 const Value *IRGuard = TLI.getSDagStackGuard(M);
3131 SDValue GuardPtr = getValue(IRGuard);
3132
3133 Guard = DAG.getLoad(PtrMemTy, dl, Chain, GuardPtr,
3134 MachinePointerInfo(IRGuard, 0), Align,
3136 }
3137
3138 // Perform the comparison via a getsetcc.
3140 *DAG.getContext(),
3141 Guard.getValueType()),
3142 Guard, GuardVal, ISD::SETNE);
3143
3144 // If the guard/stackslot do not equal, branch to failure MBB.
3145 SDValue BrCond = DAG.getNode(ISD::BRCOND, dl,
3146 MVT::Other, GuardVal.getOperand(0),
3147 Cmp, DAG.getBasicBlock(SPD.getFailureMBB()));
3148 // Otherwise branch to success MBB.
3149 SDValue Br = DAG.getNode(ISD::BR, dl,
3150 MVT::Other, BrCond,
3152
3153 DAG.setRoot(Br);
3154}
3155
3156/// Codegen the failure basic block for a stack protector check.
3157///
3158/// A failure stack protector machine basic block consists simply of a call to
3159/// __stack_chk_fail().
3160///
3161/// For a high level explanation of how this fits into the stack protector
3162/// generation see the comment on the declaration of class
3163/// StackProtectorDescriptor.
3164void
3168 CallOptions.setDiscardResult(true);
3169 SDValue Chain =
3170 TLI.makeLibCall(DAG, RTLIB::STACKPROTECTOR_CHECK_FAIL, MVT::isVoid,
3171 std::nullopt, CallOptions, getCurSDLoc())
3172 .second;
3173 // On PS4/PS5, the "return address" must still be within the calling
3174 // function, even if it's at the very end, so emit an explicit TRAP here.
3175 // Passing 'true' for doesNotReturn above won't generate the trap for us.
3176 if (TM.getTargetTriple().isPS())
3177 Chain = DAG.getNode(ISD::TRAP, getCurSDLoc(), MVT::Other, Chain);
3178 // WebAssembly needs an unreachable instruction after a non-returning call,
3179 // because the function return type can be different from __stack_chk_fail's
3180 // return type (void).
3181 if (TM.getTargetTriple().isWasm())
3182 Chain = DAG.getNode(ISD::TRAP, getCurSDLoc(), MVT::Other, Chain);
3183
3184 DAG.setRoot(Chain);
3185}
3186
3187/// visitBitTestHeader - This function emits necessary code to produce value
3188/// suitable for "bit tests"
3190 MachineBasicBlock *SwitchBB) {
3191 SDLoc dl = getCurSDLoc();
3192
3193 // Subtract the minimum value.
3194 SDValue SwitchOp = getValue(B.SValue);
3195 EVT VT = SwitchOp.getValueType();
3196 SDValue RangeSub =
3197 DAG.getNode(ISD::SUB, dl, VT, SwitchOp, DAG.getConstant(B.First, dl, VT));
3198
3199 // Determine the type of the test operands.
3201 bool UsePtrType = false;
3202 if (!TLI.isTypeLegal(VT)) {
3203 UsePtrType = true;
3204 } else {
3205 for (unsigned i = 0, e = B.Cases.size(); i != e; ++i)
3206 if (!isUIntN(VT.getSizeInBits(), B.Cases[i].Mask)) {
3207 // Switch table case range are encoded into series of masks.
3208 // Just use pointer type, it's guaranteed to fit.
3209 UsePtrType = true;
3210 break;
3211 }
3212 }
3213 SDValue Sub = RangeSub;
3214 if (UsePtrType) {
3215 VT = TLI.getPointerTy(DAG.getDataLayout());
3216 Sub = DAG.getZExtOrTrunc(Sub, dl, VT);
3217 }
3218
3219 B.RegVT = VT.getSimpleVT();
3220 B.Reg = FuncInfo.CreateReg(B.RegVT);
3221 SDValue CopyTo = DAG.getCopyToReg(getControlRoot(), dl, B.Reg, Sub);
3222
3223 MachineBasicBlock* MBB = B.Cases[0].ThisBB;
3224
3225 if (!B.FallthroughUnreachable)
3226 addSuccessorWithProb(SwitchBB, B.Default, B.DefaultProb);
3227 addSuccessorWithProb(SwitchBB, MBB, B.Prob);
3228 SwitchBB->normalizeSuccProbs();
3229
3230 SDValue Root = CopyTo;
3231 if (!B.FallthroughUnreachable) {
3232 // Conditional branch to the default block.
3233 SDValue RangeCmp = DAG.getSetCC(dl,
3235 RangeSub.getValueType()),
3236 RangeSub, DAG.getConstant(B.Range, dl, RangeSub.getValueType()),
3237 ISD::SETUGT);
3238
3239 Root = DAG.getNode(ISD::BRCOND, dl, MVT::Other, Root, RangeCmp,
3240 DAG.getBasicBlock(B.Default));
3241 }
3242
3243 // Avoid emitting unnecessary branches to the next block.
3244 if (MBB != NextBlock(SwitchBB))
3245 Root = DAG.getNode(ISD::BR, dl, MVT::Other, Root, DAG.getBasicBlock(MBB));
3246
3247 DAG.setRoot(Root);
3248}
3249
3250/// visitBitTestCase - this function produces one "bit test"
3252 MachineBasicBlock* NextMBB,
3253 BranchProbability BranchProbToNext,
3254 unsigned Reg,
3255 BitTestCase &B,
3256 MachineBasicBlock *SwitchBB) {
3257 SDLoc dl = getCurSDLoc();
3258 MVT VT = BB.RegVT;
3259 SDValue ShiftOp = DAG.getCopyFromReg(getControlRoot(), dl, Reg, VT);
3260 SDValue Cmp;
3261 unsigned PopCount = llvm::popcount(B.Mask);
3263 if (PopCount == 1) {
3264 // Testing for a single bit; just compare the shift count with what it
3265 // would need to be to shift a 1 bit in that position.
3266 Cmp = DAG.getSetCC(
3268 ShiftOp, DAG.getConstant(llvm::countr_zero(B.Mask), dl, VT),
3269 ISD::SETEQ);
3270 } else if (PopCount == BB.Range) {
3271 // There is only one zero bit in the range, test for it directly.
3272 Cmp = DAG.getSetCC(
3274 ShiftOp, DAG.getConstant(llvm::countr_one(B.Mask), dl, VT), ISD::SETNE);
3275 } else {
3276 // Make desired shift
3277 SDValue SwitchVal = DAG.getNode(ISD::SHL, dl, VT,
3278 DAG.getConstant(1, dl, VT), ShiftOp);
3279
3280 // Emit bit tests and jumps
3281 SDValue AndOp = DAG.getNode(ISD::AND, dl,
3282 VT, SwitchVal, DAG.getConstant(B.Mask, dl, VT));
3283 Cmp = DAG.getSetCC(
3285 AndOp, DAG.getConstant(0, dl, VT), ISD::SETNE);
3286 }
3287
3288 // The branch probability from SwitchBB to B.TargetBB is B.ExtraProb.
3289 addSuccessorWithProb(SwitchBB, B.TargetBB, B.ExtraProb);
3290 // The branch probability from SwitchBB to NextMBB is BranchProbToNext.
3291 addSuccessorWithProb(SwitchBB, NextMBB, BranchProbToNext);
3292 // It is not guaranteed that the sum of B.ExtraProb and BranchProbToNext is
3293 // one as they are relative probabilities (and thus work more like weights),
3294 // and hence we need to normalize them to let the sum of them become one.
3295 SwitchBB->normalizeSuccProbs();
3296
3297 SDValue BrAnd = DAG.getNode(ISD::BRCOND, dl,
3298 MVT::Other, getControlRoot(),
3299 Cmp, DAG.getBasicBlock(B.TargetBB));
3300
3301 // Avoid emitting unnecessary branches to the next block.
3302 if (NextMBB != NextBlock(SwitchBB))
3303 BrAnd = DAG.getNode(ISD::BR, dl, MVT::Other, BrAnd,
3304 DAG.getBasicBlock(NextMBB));
3305
3306 DAG.setRoot(BrAnd);
3307}
3308
3309void SelectionDAGBuilder::visitInvoke(const InvokeInst &I) {
3310 MachineBasicBlock *InvokeMBB = FuncInfo.MBB;
3311
3312 // Retrieve successors. Look through artificial IR level blocks like
3313 // catchswitch for successors.
3314 MachineBasicBlock *Return = FuncInfo.MBBMap[I.getSuccessor(0)];
3315 const BasicBlock *EHPadBB = I.getSuccessor(1);
3316 MachineBasicBlock *EHPadMBB = FuncInfo.MBBMap[EHPadBB];
3317
3318 // Deopt and ptrauth bundles are lowered in helper functions, and we don't
3319 // have to do anything here to lower funclet bundles.
3320 assert(!I.hasOperandBundlesOtherThan(
3321 {LLVMContext::OB_deopt, LLVMContext::OB_gc_transition,
3322 LLVMContext::OB_gc_live, LLVMContext::OB_funclet,
3323 LLVMContext::OB_cfguardtarget, LLVMContext::OB_ptrauth,
3324 LLVMContext::OB_clang_arc_attachedcall}) &&
3325 "Cannot lower invokes with arbitrary operand bundles yet!");
3326
3327 const Value *Callee(I.getCalledOperand());
3328 const Function *Fn = dyn_cast<Function>(Callee);
3329 if (isa<InlineAsm>(Callee))
3330 visitInlineAsm(I, EHPadBB);
3331 else if (Fn && Fn->isIntrinsic()) {
3332 switch (Fn->getIntrinsicID()) {
3333 default:
3334 llvm_unreachable("Cannot invoke this intrinsic");
3335 case Intrinsic::donothing:
3336 // Ignore invokes to @llvm.donothing: jump directly to the next BB.
3337 case Intrinsic::seh_try_begin:
3338 case Intrinsic::seh_scope_begin:
3339 case Intrinsic::seh_try_end:
3340 case Intrinsic::seh_scope_end:
3341 if (EHPadMBB)
3342 // a block referenced by EH table
3343 // so dtor-funclet not removed by opts
3344 EHPadMBB->setMachineBlockAddressTaken();
3345 break;
3346 case Intrinsic::experimental_patchpoint_void:
3347 case Intrinsic::experimental_patchpoint:
3348 visitPatchpoint(I, EHPadBB);
3349 break;
3350 case Intrinsic::experimental_gc_statepoint:
3351 LowerStatepoint(cast<GCStatepointInst>(I), EHPadBB);
3352 break;
3353 case Intrinsic::wasm_rethrow: {
3354 // This is usually done in visitTargetIntrinsic, but this intrinsic is
3355 // special because it can be invoked, so we manually lower it to a DAG
3356 // node here.
3358 Ops.push_back(getControlRoot()); // inchain for the terminator node
3360 Ops.push_back(
3361 DAG.getTargetConstant(Intrinsic::wasm_rethrow, getCurSDLoc(),
3363 SDVTList VTs = DAG.getVTList(ArrayRef<EVT>({MVT::Other})); // outchain
3365 break;
3366 }
3367 }
3368 } else if (I.hasDeoptState()) {
3369 // Currently we do not lower any intrinsic calls with deopt operand bundles.
3370 // Eventually we will support lowering the @llvm.experimental.deoptimize
3371 // intrinsic, and right now there are no plans to support other intrinsics
3372 // with deopt state.
3373 LowerCallSiteWithDeoptBundle(&I, getValue(Callee), EHPadBB);
3374 } else if (I.countOperandBundlesOfType(LLVMContext::OB_ptrauth)) {
3375 LowerCallSiteWithPtrAuthBundle(cast<CallBase>(I), EHPadBB);
3376 } else {
3377 LowerCallTo(I, getValue(Callee), false, false, EHPadBB);
3378 }
3379
3380 // If the value of the invoke is used outside of its defining block, make it
3381 // available as a virtual register.
3382 // We already took care of the exported value for the statepoint instruction
3383 // during call to the LowerStatepoint.
3384 if (!isa<GCStatepointInst>(I)) {
3386 }
3387
3390 BranchProbability EHPadBBProb =
3391 BPI ? BPI->getEdgeProbability(InvokeMBB->getBasicBlock(), EHPadBB)
3393 findUnwindDestinations(FuncInfo, EHPadBB, EHPadBBProb, UnwindDests);
3394
3395 // Update successor info.
3396 addSuccessorWithProb(InvokeMBB, Return);
3397 for (auto &UnwindDest : UnwindDests) {
3398 UnwindDest.first->setIsEHPad();
3399 addSuccessorWithProb(InvokeMBB, UnwindDest.first, UnwindDest.second);
3400 }
3401 InvokeMBB->normalizeSuccProbs();
3402
3403 // Drop into normal successor.
3405 DAG.getBasicBlock(Return)));
3406}
3407
3408void SelectionDAGBuilder::visitCallBr(const CallBrInst &I) {
3409 MachineBasicBlock *CallBrMBB = FuncInfo.MBB;
3410
3411 // Deopt bundles are lowered in LowerCallSiteWithDeoptBundle, and we don't
3412 // have to do anything here to lower funclet bundles.
3413 assert(!I.hasOperandBundlesOtherThan(
3414 {LLVMContext::OB_deopt, LLVMContext::OB_funclet}) &&
3415 "Cannot lower callbrs with arbitrary operand bundles yet!");
3416
3417 assert(I.isInlineAsm() && "Only know how to handle inlineasm callbr");
3418 visitInlineAsm(I);
3420
3421 // Retrieve successors.
3423 Dests.insert(I.getDefaultDest());
3424 MachineBasicBlock *Return = FuncInfo.MBBMap[I.getDefaultDest()];
3425
3426 // Update successor info.
3427 addSuccessorWithProb(CallBrMBB, Return, BranchProbability::getOne());
3428 for (unsigned i = 0, e = I.getNumIndirectDests(); i < e; ++i) {
3429 BasicBlock *Dest = I.getIndirectDest(i);
3431 Target->setIsInlineAsmBrIndirectTarget();
3432 Target->setMachineBlockAddressTaken();
3433 Target->setLabelMustBeEmitted();
3434 // Don't add duplicate machine successors.
3435 if (Dests.insert(Dest).second)
3436 addSuccessorWithProb(CallBrMBB, Target, BranchProbability::getZero());
3437 }
3438 CallBrMBB->normalizeSuccProbs();
3439
3440 // Drop into default successor.
3442 MVT::Other, getControlRoot(),
3443 DAG.getBasicBlock(Return)));
3444}
3445
3446void SelectionDAGBuilder::visitResume(const ResumeInst &RI) {
3447 llvm_unreachable("SelectionDAGBuilder shouldn't visit resume instructions!");
3448}
3449
3450void SelectionDAGBuilder::visitLandingPad(const LandingPadInst &LP) {
3452 "Call to landingpad not in landing pad!");
3453
3454 // If there aren't registers to copy the values into (e.g., during SjLj
3455 // exceptions), then don't bother to create these DAG nodes.
3457 const Constant *PersonalityFn = FuncInfo.Fn->getPersonalityFn();
3458 if (TLI.getExceptionPointerRegister(PersonalityFn) == 0 &&
3459 TLI.getExceptionSelectorRegister(PersonalityFn) == 0)
3460 return;
3461
3462 // If landingpad's return type is token type, we don't create DAG nodes
3463 // for its exception pointer and selector value. The extraction of exception
3464 // pointer or selector value from token type landingpads is not currently
3465 // supported.
3466 if (LP.getType()->isTokenTy())
3467 return;
3468
3469 SmallVector<EVT, 2> ValueVTs;
3470 SDLoc dl = getCurSDLoc();
3471 ComputeValueVTs(TLI, DAG.getDataLayout(), LP.getType(), ValueVTs);
3472 assert(ValueVTs.size() == 2 && "Only two-valued landingpads are supported");
3473
3474 // Get the two live-in registers as SDValues. The physregs have already been
3475 // copied into virtual registers.
3476 SDValue Ops[2];
3478 Ops[0] = DAG.getZExtOrTrunc(
3482 dl, ValueVTs[0]);
3483 } else {
3484 Ops[0] = DAG.getConstant(0, dl, TLI.getPointerTy(DAG.getDataLayout()));
3485 }
3486 Ops[1] = DAG.getZExtOrTrunc(
3490 dl, ValueVTs[1]);
3491
3492 // Merge into one.
3494 DAG.getVTList(ValueVTs), Ops);
3495 setValue(&LP, Res);
3496}
3497
3500 // Update JTCases.
3501 for (JumpTableBlock &JTB : SL->JTCases)
3502 if (JTB.first.HeaderBB == First)
3503 JTB.first.HeaderBB = Last;
3504
3505 // Update BitTestCases.
3506 for (BitTestBlock &BTB : SL->BitTestCases)
3507 if (BTB.Parent == First)
3508 BTB.Parent = Last;
3509}
3510
3511void SelectionDAGBuilder::visitIndirectBr(const IndirectBrInst &I) {
3512 MachineBasicBlock *IndirectBrMBB = FuncInfo.MBB;
3513
3514 // Update machine-CFG edges with unique successors.
3516 for (unsigned i = 0, e = I.getNumSuccessors(); i != e; ++i) {
3517 BasicBlock *BB = I.getSuccessor(i);
3518 bool Inserted = Done.insert(BB).second;
3519 if (!Inserted)
3520 continue;
3521
3522 MachineBasicBlock *Succ = FuncInfo.MBBMap[BB];
3523 addSuccessorWithProb(IndirectBrMBB, Succ);
3524 }
3525 IndirectBrMBB->normalizeSuccProbs();
3526
3528 MVT::Other, getControlRoot(),
3529 getValue(I.getAddress())));
3530}
3531
3532void SelectionDAGBuilder::visitUnreachable(const UnreachableInst &I) {
3534 return;
3535
3536 // We may be able to ignore unreachable behind a noreturn call.
3538 if (const CallInst *Call = dyn_cast_or_null<CallInst>(I.getPrevNode())) {
3539 if (Call->doesNotReturn())
3540 return;
3541 }
3542 }
3543
3544 DAG.setRoot(DAG.getNode(ISD::TRAP, getCurSDLoc(), MVT::Other, DAG.getRoot()));
3545}
3546
3547void SelectionDAGBuilder::visitUnary(const User &I, unsigned Opcode) {
3549 if (auto *FPOp = dyn_cast<FPMathOperator>(&I))
3550 Flags.copyFMF(*FPOp);
3551
3552 SDValue Op = getValue(I.getOperand(0));
3553 SDValue UnNodeValue = DAG.getNode(Opcode, getCurSDLoc(), Op.getValueType(),
3554 Op, Flags);
3555 setValue(&I, UnNodeValue);
3556}
3557
3558void SelectionDAGBuilder::visitBinary(const User &I, unsigned Opcode) {
3560 if (auto *OFBinOp = dyn_cast<OverflowingBinaryOperator>(&I)) {
3561 Flags.setNoSignedWrap(OFBinOp->hasNoSignedWrap());
3562 Flags.setNoUnsignedWrap(OFBinOp->hasNoUnsignedWrap());
3563 }
3564 if (auto *ExactOp = dyn_cast<PossiblyExactOperator>(&I))
3565 Flags.setExact(ExactOp->isExact());
3566 if (auto *DisjointOp = dyn_cast<PossiblyDisjointInst>(&I))
3567 Flags.setDisjoint(DisjointOp->isDisjoint());
3568 if (auto *FPOp = dyn_cast<FPMathOperator>(&I))
3569 Flags.copyFMF(*FPOp);
3570
3571 SDValue Op1 = getValue(I.getOperand(0));
3572 SDValue Op2 = getValue(I.getOperand(1));
3573 SDValue BinNodeValue = DAG.getNode(Opcode, getCurSDLoc(), Op1.getValueType(),
3574 Op1, Op2, Flags);
3575 setValue(&I, BinNodeValue);
3576}
3577
3578void SelectionDAGBuilder::visitShift(const User &I, unsigned Opcode) {
3579 SDValue Op1 = getValue(I.getOperand(0));
3580 SDValue Op2 = getValue(I.getOperand(1));
3581
3583 Op1.getValueType(), DAG.getDataLayout());
3584
3585 // Coerce the shift amount to the right type if we can. This exposes the
3586 // truncate or zext to optimization early.
3587 if (!I.getType()->isVectorTy() && Op2.getValueType() != ShiftTy) {
3589 "Unexpected shift type");
3590 Op2 = DAG.getZExtOrTrunc(Op2, getCurSDLoc(), ShiftTy);
3591 }
3592
3593 bool nuw = false;
3594 bool nsw = false;
3595 bool exact = false;
3596
3597 if (Opcode == ISD::SRL || Opcode == ISD::SRA || Opcode == ISD::SHL) {
3598
3599 if (const OverflowingBinaryOperator *OFBinOp =
3600 dyn_cast<const OverflowingBinaryOperator>(&I)) {
3601 nuw = OFBinOp->hasNoUnsignedWrap();
3602 nsw = OFBinOp->hasNoSignedWrap();
3603 }
3604 if (const PossiblyExactOperator *ExactOp =
3605 dyn_cast<const PossiblyExactOperator>(&I))
3606 exact = ExactOp->isExact();
3607 }
3609 Flags.setExact(exact);
3610 Flags.setNoSignedWrap(nsw);
3611 Flags.setNoUnsignedWrap(nuw);
3612 SDValue Res = DAG.getNode(Opcode, getCurSDLoc(), Op1.getValueType(), Op1, Op2,
3613 Flags);
3614 setValue(&I, Res);
3615}
3616
3617void SelectionDAGBuilder::visitSDiv(const User &I) {
3618 SDValue Op1 = getValue(I.getOperand(0));
3619 SDValue Op2 = getValue(I.getOperand(1));
3620
3622 Flags.setExact(isa<PossiblyExactOperator>(&I) &&
3623 cast<PossiblyExactOperator>(&I)->isExact());
3625 Op2, Flags));
3626}
3627
3628void SelectionDAGBuilder::visitICmp(const ICmpInst &I) {
3629 ICmpInst::Predicate predicate = I.getPredicate();
3630 SDValue Op1 = getValue(I.getOperand(0));
3631 SDValue Op2 = getValue(I.getOperand(1));
3632 ISD::CondCode Opcode = getICmpCondCode(predicate);
3633
3634 auto &TLI = DAG.getTargetLoweringInfo();
3635 EVT MemVT =
3636 TLI.getMemValueType(DAG.getDataLayout(), I.getOperand(0)->getType());
3637
3638 // If a pointer's DAG type is larger than its memory type then the DAG values
3639 // are zero-extended. This breaks signed comparisons so truncate back to the
3640 // underlying type before doing the compare.
3641 if (Op1.getValueType() != MemVT) {
3642 Op1 = DAG.getPtrExtOrTrunc(Op1, getCurSDLoc(), MemVT);
3643 Op2 = DAG.getPtrExtOrTrunc(Op2, getCurSDLoc(), MemVT);
3644 }
3645
3647 I.getType());
3648 setValue(&I, DAG.getSetCC(getCurSDLoc(), DestVT, Op1, Op2, Opcode));
3649}
3650
3651void SelectionDAGBuilder::visitFCmp(const FCmpInst &I) {
3652 FCmpInst::Predicate predicate = I.getPredicate();
3653 SDValue Op1 = getValue(I.getOperand(0));
3654 SDValue Op2 = getValue(I.getOperand(1));
3655
3656 ISD::CondCode Condition = getFCmpCondCode(predicate);
3657 auto *FPMO = cast<FPMathOperator>(&I);
3658 if (FPMO->hasNoNaNs() || TM.Options.NoNaNsFPMath)
3659 Condition = getFCmpCodeWithoutNaN(Condition);
3660
3662 Flags.copyFMF(*FPMO);
3663 SelectionDAG::FlagInserter FlagsInserter(DAG, Flags);
3664
3666 I.getType());
3667 setValue(&I, DAG.getSetCC(getCurSDLoc(), DestVT, Op1, Op2, Condition));
3668}
3669
3670// Check if the condition of the select has one use or two users that are both
3671// selects with the same condition.
3672static bool hasOnlySelectUsers(const Value *Cond) {
3673 return llvm::all_of(Cond->users(), [](const Value *V) {
3674 return isa<SelectInst>(V);
3675 });
3676}
3677
3678void SelectionDAGBuilder::visitSelect(const User &I) {
3679 SmallVector<EVT, 4> ValueVTs;
3681 ValueVTs);
3682 unsigned NumValues = ValueVTs.size();
3683 if (NumValues == 0) return;
3684
3685 SmallVector<SDValue, 4> Values(NumValues);
3686 SDValue Cond = getValue(I.getOperand(0));
3687 SDValue LHSVal = getValue(I.getOperand(1));
3688 SDValue RHSVal = getValue(I.getOperand(2));
3689 SmallVector<SDValue, 1> BaseOps(1, Cond);
3690 ISD::NodeType OpCode =
3691 Cond.getValueType().isVector() ? ISD::VSELECT : ISD::SELECT;
3692
3693 bool IsUnaryAbs = false;
3694 bool Negate = false;
3695
3697 if (auto *FPOp = dyn_cast<FPMathOperator>(&I))
3698 Flags.copyFMF(*FPOp);
3699
3700 Flags.setUnpredictable(
3701 cast<SelectInst>(I).getMetadata(LLVMContext::MD_unpredictable));
3702
3703 // Min/max matching is only viable if all output VTs are the same.
3704 if (all_equal(ValueVTs)) {
3705 EVT VT = ValueVTs[0];
3706 LLVMContext &Ctx = *DAG.getContext();
3707 auto &TLI = DAG.getTargetLoweringInfo();
3708
3709 // We care about the legality of the operation after it has been type
3710 // legalized.
3711 while (TLI.getTypeAction(Ctx, VT) != TargetLoweringBase::TypeLegal)
3712 VT = TLI.getTypeToTransformTo(Ctx, VT);
3713
3714 // If the vselect is legal, assume we want to leave this as a vector setcc +
3715 // vselect. Otherwise, if this is going to be scalarized, we want to see if
3716 // min/max is legal on the scalar type.
3717 bool UseScalarMinMax = VT.isVector() &&
3719
3720 // ValueTracking's select pattern matching does not account for -0.0,
3721 // so we can't lower to FMINIMUM/FMAXIMUM because those nodes specify that
3722 // -0.0 is less than +0.0.
3723 Value *LHS, *RHS;
3724 auto SPR = matchSelectPattern(const_cast<User*>(&I), LHS, RHS);
3726 switch (SPR.Flavor) {
3727 case SPF_UMAX: Opc = ISD::UMAX; break;
3728 case SPF_UMIN: Opc = ISD::UMIN; break;
3729 case SPF_SMAX: Opc = ISD::SMAX; break;
3730 case SPF_SMIN: Opc = ISD::SMIN; break;
3731 case SPF_FMINNUM:
3732 switch (SPR.NaNBehavior) {
3733 case SPNB_NA: llvm_unreachable("No NaN behavior for FP op?");
3734 case SPNB_RETURNS_NAN: break;
3735 case SPNB_RETURNS_OTHER: Opc = ISD::FMINNUM; break;
3736 case SPNB_RETURNS_ANY:
3738 (UseScalarMinMax &&
3740 Opc = ISD::FMINNUM;
3741 break;
3742 }
3743 break;
3744 case SPF_FMAXNUM:
3745 switch (SPR.NaNBehavior) {
3746 case SPNB_NA: llvm_unreachable("No NaN behavior for FP op?");
3747 case SPNB_RETURNS_NAN: break;
3748 case SPNB_RETURNS_OTHER: Opc = ISD::FMAXNUM; break;
3749 case SPNB_RETURNS_ANY:
3751 (UseScalarMinMax &&
3753 Opc = ISD::FMAXNUM;
3754 break;
3755 }
3756 break;
3757 case SPF_NABS:
3758 Negate = true;
3759 [[fallthrough]];
3760 case SPF_ABS:
3761 IsUnaryAbs = true;
3762 Opc = ISD::ABS;
3763 break;
3764 default: break;
3765 }
3766
3767 if (!IsUnaryAbs && Opc != ISD::DELETED_NODE &&
3768 (TLI.isOperationLegalOrCustomOrPromote(Opc, VT) ||
3769 (UseScalarMinMax &&
3770 TLI.isOperationLegalOrCustom(Opc, VT.getScalarType()))) &&
3771 // If the underlying comparison instruction is used by any other
3772 // instruction, the consumed instructions won't be destroyed, so it is
3773 // not profitable to convert to a min/max.
3774 hasOnlySelectUsers(cast<SelectInst>(I).getCondition())) {
3775 OpCode = Opc;
3776 LHSVal = getValue(LHS);
3777 RHSVal = getValue(RHS);
3778 BaseOps.clear();
3779 }
3780
3781 if (IsUnaryAbs) {
3782 OpCode = Opc;
3783 LHSVal = getValue(LHS);
3784 BaseOps.clear();
3785 }
3786 }
3787
3788 if (IsUnaryAbs) {
3789 for (unsigned i = 0; i != NumValues; ++i) {
3790 SDLoc dl = getCurSDLoc();
3791 EVT VT = LHSVal.getNode()->getValueType(LHSVal.getResNo() + i);
3792 Values[i] =
3793 DAG.getNode(OpCode, dl, VT, LHSVal.getValue(LHSVal.getResNo() + i));
3794 if (Negate)
3795 Values[i] = DAG.getNegative(Values[i], dl, VT);
3796 }
3797 } else {
3798 for (unsigned i = 0; i != NumValues; ++i) {
3799 SmallVector<SDValue, 3> Ops(BaseOps.begin(), BaseOps.end());
3800 Ops.push_back(SDValue(LHSVal.getNode(), LHSVal.getResNo() + i));
3801 Ops.push_back(SDValue(RHSVal.getNode(), RHSVal.getResNo() + i));
3802 Values[i] = DAG.getNode(
3803 OpCode, getCurSDLoc(),
3804 LHSVal.getNode()->getValueType(LHSVal.getResNo() + i), Ops, Flags);
3805 }
3806 }
3807
3809 DAG.getVTList(ValueVTs), Values));
3810}
3811
3812void SelectionDAGBuilder::visitTrunc(const User &I) {
3813 // TruncInst cannot be a no-op cast because sizeof(src) > sizeof(dest).
3814 SDValue N = getValue(I.getOperand(0));
3816 I.getType());
3818}
3819
3820void SelectionDAGBuilder::visitZExt(const User &I) {
3821 // ZExt cannot be a no-op cast because sizeof(src) < sizeof(dest).
3822 // ZExt also can't be a cast to bool for same reason. So, nothing much to do
3823 SDValue N = getValue(I.getOperand(0));
3824 auto &TLI = DAG.getTargetLoweringInfo();
3825 EVT DestVT = TLI.getValueType(DAG.getDataLayout(), I.getType());
3826
3828 if (auto *PNI = dyn_cast<PossiblyNonNegInst>(&I))
3829 Flags.setNonNeg(PNI->hasNonNeg());
3830
3831 // Eagerly use nonneg information to canonicalize towards sign_extend if
3832 // that is the target's preference.
3833 // TODO: Let the target do this later.
3834 if (Flags.hasNonNeg() &&
3835 TLI.isSExtCheaperThanZExt(N.getValueType(), DestVT)) {
3837 return;
3838 }
3839
3840 setValue(&I, DAG.getNode(ISD::ZERO_EXTEND, getCurSDLoc(), DestVT, N, Flags));
3841}
3842
3843void SelectionDAGBuilder::visitSExt(const User &I) {
3844 // SExt cannot be a no-op cast because sizeof(src) < sizeof(dest).
3845 // SExt also can't be a cast to bool for same reason. So, nothing much to do
3846 SDValue N = getValue(I.getOperand(0));
3848 I.getType());
3850}
3851
3852void SelectionDAGBuilder::visitFPTrunc(const User &I) {
3853 // FPTrunc is never a no-op cast, no need to check
3854 SDValue N = getValue(I.getOperand(0));
3855 SDLoc dl = getCurSDLoc();
3857 EVT DestVT = TLI.getValueType(DAG.getDataLayout(), I.getType());
3858 setValue(&I, DAG.getNode(ISD::FP_ROUND, dl, DestVT, N,
3860 0, dl, TLI.getPointerTy(DAG.getDataLayout()))));
3861}
3862
3863void SelectionDAGBuilder::visitFPExt(const User &I) {
3864 // FPExt is never a no-op cast, no need to check
3865 SDValue N = getValue(I.getOperand(0));
3867 I.getType());
3869}
3870
3871void SelectionDAGBuilder::visitFPToUI(const User &I) {
3872 // FPToUI is never a no-op cast, no need to check
3873 SDValue N = getValue(I.getOperand(0));
3875 I.getType());
3877}
3878
3879void SelectionDAGBuilder::visitFPToSI(const User &I) {
3880 // FPToSI is never a no-op cast, no need to check
3881 SDValue N = getValue(I.getOperand(0));
3883 I.getType());
3885}
3886
3887void SelectionDAGBuilder::visitUIToFP(const User &I) {
3888 // UIToFP is never a no-op cast, no need to check
3889 SDValue N = getValue(I.getOperand(0));
3891 I.getType());
3893 if (auto *PNI = dyn_cast<PossiblyNonNegInst>(&I))
3894 Flags.setNonNeg(PNI->hasNonNeg());
3895
3896 setValue(&I, DAG.getNode(ISD::UINT_TO_FP, getCurSDLoc(), DestVT, N, Flags));
3897}
3898
3899void SelectionDAGBuilder::visitSIToFP(const User &I) {
3900 // SIToFP is never a no-op cast, no need to check
3901 SDValue N = getValue(I.getOperand(0));
3903 I.getType());
3905}
3906
3907void SelectionDAGBuilder::visitPtrToInt(const User &I) {
3908 // What to do depends on the size of the integer and the size of the pointer.
3909 // We can either truncate, zero extend, or no-op, accordingly.
3910 SDValue N = getValue(I.getOperand(0));
3911 auto &TLI = DAG.getTargetLoweringInfo();
3913 I.getType());
3914 EVT PtrMemVT =
3915 TLI.getMemValueType(DAG.getDataLayout(), I.getOperand(0)->getType());
3916 N = DAG.getPtrExtOrTrunc(N, getCurSDLoc(), PtrMemVT);
3917 N = DAG.getZExtOrTrunc(N, getCurSDLoc(), DestVT);
3918 setValue(&I, N);
3919}
3920
3921void SelectionDAGBuilder::visitIntToPtr(const User &I) {
3922 // What to do depends on the size of the integer and the size of the pointer.
3923 // We can either truncate, zero extend, or no-op, accordingly.
3924 SDValue N = getValue(I.getOperand(0));
3925 auto &TLI = DAG.getTargetLoweringInfo();
3926 EVT DestVT = TLI.getValueType(DAG.getDataLayout(), I.getType());
3927 EVT PtrMemVT = TLI.getMemValueType(DAG.getDataLayout(), I.getType());
3928 N = DAG.getZExtOrTrunc(N, getCurSDLoc(), PtrMemVT);
3929 N = DAG.getPtrExtOrTrunc(N, getCurSDLoc(), DestVT);
3930 setValue(&I, N);
3931}
3932
3933void SelectionDAGBuilder::visitBitCast(const User &I) {
3934 SDValue N = getValue(I.getOperand(0));
3935 SDLoc dl = getCurSDLoc();
3937 I.getType());
3938
3939 // BitCast assures us that source and destination are the same size so this is
3940 // either a BITCAST or a no-op.
3941 if (DestVT != N.getValueType())
3943 DestVT, N)); // convert types.
3944 // Check if the original LLVM IR Operand was a ConstantInt, because getValue()
3945 // might fold any kind of constant expression to an integer constant and that
3946 // is not what we are looking for. Only recognize a bitcast of a genuine
3947 // constant integer as an opaque constant.
3948 else if(ConstantInt *C = dyn_cast<ConstantInt>(I.getOperand(0)))
3949 setValue(&I, DAG.getConstant(C->getValue(), dl, DestVT, /*isTarget=*/false,
3950 /*isOpaque*/true));
3951 else
3952 setValue(&I, N); // noop cast.
3953}
3954
3955void SelectionDAGBuilder::visitAddrSpaceCast(const User &I) {
3957 const Value *SV = I.getOperand(0);
3958 SDValue N = getValue(SV);
3959 EVT DestVT = TLI.getValueType(DAG.getDataLayout(), I.getType());
3960
3961 unsigned SrcAS = SV->getType()->getPointerAddressSpace();
3962 unsigned DestAS = I.getType()->getPointerAddressSpace();
3963
3964 if (!TM.isNoopAddrSpaceCast(SrcAS, DestAS))
3965 N = DAG.getAddrSpaceCast(getCurSDLoc(), DestVT, N, SrcAS, DestAS);
3966
3967 setValue(&I, N);
3968}
3969
3970void SelectionDAGBuilder::visitInsertElement(const User &I) {
3972 SDValue InVec = getValue(I.getOperand(0));
3973 SDValue InVal = getValue(I.getOperand(1));
3974 SDValue InIdx = DAG.getZExtOrTrunc(getValue(I.getOperand(2)), getCurSDLoc(),
3977 TLI.getValueType(DAG.getDataLayout(), I.getType()),
3978 InVec, InVal, InIdx));
3979}
3980
3981void SelectionDAGBuilder::visitExtractElement(const User &I) {
3983 SDValue InVec = getValue(I.getOperand(0));
3984 SDValue InIdx = DAG.getZExtOrTrunc(getValue(I.getOperand(1)), getCurSDLoc(),
3987 TLI.getValueType(DAG.getDataLayout(), I.getType()),
3988 InVec, InIdx));
3989}
3990
3991void SelectionDAGBuilder::visitShuffleVector(const User &I) {
3992 SDValue Src1 = getValue(I.getOperand(0));
3993 SDValue Src2 = getValue(I.getOperand(1));
3995 if (auto *SVI = dyn_cast<ShuffleVectorInst>(&I))
3996 Mask = SVI->getShuffleMask();
3997 else
3998 Mask = cast<ConstantExpr>(I).getShuffleMask();
3999 SDLoc DL = getCurSDLoc();
4001 EVT VT = TLI.getValueType(DAG.getDataLayout(), I.getType());
4002 EVT SrcVT = Src1.getValueType();
4003
4004 if (all_of(Mask, [](int Elem) { return Elem == 0; }) &&
4005 VT.isScalableVector()) {
4006 // Canonical splat form of first element of first input vector.
4007 SDValue FirstElt =
4010 setValue(&I, DAG.getNode(ISD::SPLAT_VECTOR, DL, VT, FirstElt));
4011 return;
4012 }
4013
4014 // For now, we only handle splats for scalable vectors.
4015 // The DAGCombiner will perform a BUILD_VECTOR -> SPLAT_VECTOR transformation
4016 // for targets that support a SPLAT_VECTOR for non-scalable vector types.
4017 assert(!VT.isScalableVector() && "Unsupported scalable vector shuffle");
4018
4019 unsigned SrcNumElts = SrcVT.getVectorNumElements();
4020 unsigned MaskNumElts = Mask.size();
4021
4022 if (SrcNumElts == MaskNumElts) {
4023 setValue(&I, DAG.getVectorShuffle(VT, DL, Src1, Src2, Mask));
4024 return;
4025 }
4026
4027 // Normalize the shuffle vector since mask and vector length don't match.
4028 if (SrcNumElts < MaskNumElts) {
4029 // Mask is longer than the source vectors. We can use concatenate vector to
4030 // make the mask and vectors lengths match.
4031
4032 if (MaskNumElts % SrcNumElts == 0) {
4033 // Mask length is a multiple of the source vector length.
4034 // Check if the shuffle is some kind of concatenation of the input
4035 // vectors.
4036 unsigned NumConcat = MaskNumElts / SrcNumElts;
4037 bool IsConcat = true;
4038 SmallVector<int, 8> ConcatSrcs(NumConcat, -1);
4039 for (unsigned i = 0; i != MaskNumElts; ++i) {
4040 int Idx = Mask[i];
4041 if (Idx < 0)
4042 continue;
4043 // Ensure the indices in each SrcVT sized piece are sequential and that
4044 // the same source is used for the whole piece.
4045 if ((Idx % SrcNumElts != (i % SrcNumElts)) ||
4046 (ConcatSrcs[i / SrcNumElts] >= 0 &&
4047 ConcatSrcs[i / SrcNumElts] != (int)(Idx / SrcNumElts))) {
4048 IsConcat = false;
4049 break;
4050 }
4051 // Remember which source this index came from.
4052 ConcatSrcs[i / SrcNumElts] = Idx / SrcNumElts;
4053 }
4054
4055 // The shuffle is concatenating multiple vectors together. Just emit
4056 // a CONCAT_VECTORS operation.
4057 if (IsConcat) {
4058 SmallVector<SDValue, 8> ConcatOps;
4059 for (auto Src : ConcatSrcs) {
4060 if (Src < 0)
4061 ConcatOps.push_back(DAG.getUNDEF(SrcVT));
4062 else if (Src == 0)
4063 ConcatOps.push_back(Src1);
4064 else
4065 ConcatOps.push_back(Src2);
4066 }
4067 setValue(&I, DAG.getNode(ISD::CONCAT_VECTORS, DL, VT, ConcatOps));
4068 return;
4069 }
4070 }
4071
4072 unsigned PaddedMaskNumElts = alignTo(MaskNumElts, SrcNumElts);
4073 unsigned NumConcat = PaddedMaskNumElts / SrcNumElts;
4074 EVT PaddedVT = EVT::getVectorVT(*DAG.getContext(), VT.getScalarType(),
4075 PaddedMaskNumElts);
4076
4077 // Pad both vectors with undefs to make them the same length as the mask.
4078 SDValue UndefVal = DAG.getUNDEF(SrcVT);
4079
4080 SmallVector<SDValue, 8> MOps1(NumConcat, UndefVal);
4081 SmallVector<SDValue, 8> MOps2(NumConcat, UndefVal);
4082 MOps1[0] = Src1;
4083 MOps2[0] = Src2;
4084
4085 Src1 = DAG.getNode(ISD::CONCAT_VECTORS, DL, PaddedVT, MOps1);
4086 Src2 = DAG.getNode(ISD::CONCAT_VECTORS, DL, PaddedVT, MOps2);
4087
4088 // Readjust mask for new input vector length.
4089 SmallVector<int, 8> MappedOps(PaddedMaskNumElts, -1);
4090 for (unsigned i = 0; i != MaskNumElts; ++i) {
4091 int Idx = Mask[i];
4092 if (Idx >= (int)SrcNumElts)
4093 Idx -= SrcNumElts - PaddedMaskNumElts;
4094 MappedOps[i] = Idx;
4095 }
4096
4097 SDValue Result = DAG.getVectorShuffle(PaddedVT, DL, Src1, Src2, MappedOps);
4098
4099 // If the concatenated vector was padded, extract a subvector with the
4100 // correct number of elements.
4101 if (MaskNumElts != PaddedMaskNumElts)
4104
4105 setValue(&I, Result);
4106 return;
4107 }
4108
4109 if (SrcNumElts > MaskNumElts) {
4110 // Analyze the access pattern of the vector to see if we can extract
4111 // two subvectors and do the shuffle.
4112 int StartIdx[2] = { -1, -1 }; // StartIdx to extract from
4113 bool CanExtract = true;
4114 for (int Idx : Mask) {
4115 unsigned Input = 0;
4116 if (Idx < 0)
4117 continue;
4118
4119 if (Idx >= (int)SrcNumElts) {
4120 Input = 1;
4121 Idx -= SrcNumElts;
4122 }
4123
4124 // If all the indices come from the same MaskNumElts sized portion of
4125 // the sources we can use extract. Also make sure the extract wouldn't
4126 // extract past the end of the source.
4127 int NewStartIdx = alignDown(Idx, MaskNumElts);
4128 if (NewStartIdx + MaskNumElts > SrcNumElts ||
4129 (StartIdx[Input] >= 0 && StartIdx[Input] != NewStartIdx))
4130 CanExtract = false;
4131 // Make sure we always update StartIdx as we use it to track if all
4132 // elements are undef.
4133 StartIdx[Input] = NewStartIdx;
4134 }
4135
4136 if (StartIdx[0] < 0 && StartIdx[1] < 0) {
4137 setValue(&I, DAG.getUNDEF(VT)); // Vectors are not used.
4138 return;
4139 }
4140 if (CanExtract) {
4141 // Extract appropriate subvector and generate a vector shuffle
4142 for (unsigned Input = 0; Input < 2; ++Input) {
4143 SDValue &Src = Input == 0 ? Src1 : Src2;
4144 if (StartIdx[Input] < 0)
4145 Src = DAG.getUNDEF(VT);
4146 else {
4147 Src = DAG.getNode(ISD::EXTRACT_SUBVECTOR, DL, VT, Src,
4148 DAG.getVectorIdxConstant(StartIdx[Input], DL));
4149 }
4150 }
4151
4152 // Calculate new mask.
4153 SmallVector<int, 8> MappedOps(Mask);
4154 for (int &Idx : MappedOps) {
4155 if (Idx >= (int)SrcNumElts)
4156 Idx -= SrcNumElts + StartIdx[1] - MaskNumElts;
4157 else if (Idx >= 0)
4158 Idx -= StartIdx[0];
4159 }
4160
4161 setValue(&I, DAG.getVectorShuffle(VT, DL, Src1, Src2, MappedOps));
4162 return;
4163 }
4164 }
4165
4166 // We can't use either concat vectors or extract subvectors so fall back to
4167 // replacing the shuffle with extract and build vector.
4168 // to insert and build vector.
4169 EVT EltVT = VT.getVectorElementType();
4171 for (int Idx : Mask) {
4172 SDValue Res;
4173
4174 if (Idx < 0) {
4175 Res = DAG.getUNDEF(EltVT);
4176 } else {
4177 SDValue &Src = Idx < (int)SrcNumElts ? Src1 : Src2;
4178 if (Idx >= (int)SrcNumElts) Idx -= SrcNumElts;
4179
4180 Res = DAG.getNode(ISD::EXTRACT_VECTOR_ELT, DL, EltVT, Src,
4182 }
4183
4184 Ops.push_back(Res);
4185 }
4186
4187 setValue(&I, DAG.getBuildVector(VT, DL, Ops));
4188}
4189
4190void SelectionDAGBuilder::visitInsertValue(const InsertValueInst &I) {
4191 ArrayRef<unsigned> Indices = I.getIndices();
4192 const Value *Op0 = I.getOperand(0);
4193 const Value *Op1 = I.getOperand(1);
4194 Type *AggTy = I.getType();
4195 Type *ValTy = Op1->getType();
4196 bool IntoUndef = isa<UndefValue>(Op0);
4197 bool FromUndef = isa<UndefValue>(Op1);
4198
4199 unsigned LinearIndex = ComputeLinearIndex(AggTy, Indices);
4200
4202 SmallVector<EVT, 4> AggValueVTs;
4203 ComputeValueVTs(TLI, DAG.getDataLayout(), AggTy, AggValueVTs);
4204 SmallVector<EVT, 4> ValValueVTs;
4205 ComputeValueVTs(TLI, DAG.getDataLayout(), ValTy, ValValueVTs);
4206
4207 unsigned NumAggValues = AggValueVTs.size();
4208 unsigned NumValValues = ValValueVTs.size();
4209 SmallVector<SDValue, 4> Values(NumAggValues);
4210
4211 // Ignore an insertvalue that produces an empty object
4212 if (!NumAggValues) {
4213 setValue(&I, DAG.getUNDEF(MVT(MVT::Other)));
4214 return;
4215 }
4216
4217 SDValue Agg = getValue(Op0);
4218 unsigned i = 0;
4219 // Copy the beginning value(s) from the original aggregate.
4220 for (; i != LinearIndex; ++i)
4221 Values[i] = IntoUndef ? DAG.getUNDEF(AggValueVTs[i]) :
4222 SDValue(Agg.getNode(), Agg.getResNo() + i);
4223 // Copy values from the inserted value(s).
4224 if (NumValValues) {
4225 SDValue Val = getValue(Op1);
4226 for (; i != LinearIndex + NumValValues; ++i)
4227 Values[i] = FromUndef ? DAG.getUNDEF(AggValueVTs[i]) :
4228 SDValue(Val.getNode(), Val.getResNo() + i - LinearIndex);
4229 }
4230 // Copy remaining value(s) from the original aggregate.
4231 for (; i != NumAggValues; ++i)
4232 Values[i] = IntoUndef ? DAG.getUNDEF(AggValueVTs[i]) :
4233 SDValue(Agg.getNode(), Agg.getResNo() + i);
4234
4236 DAG.getVTList(AggValueVTs), Values));
4237}
4238
4239void SelectionDAGBuilder::visitExtractValue(const ExtractValueInst &I) {
4240 ArrayRef<unsigned> Indices = I.getIndices();
4241 const Value *Op0 = I.getOperand(0);
4242 Type *AggTy = Op0->getType();
4243 Type *ValTy = I.getType();
4244 bool OutOfUndef = isa<UndefValue>(Op0);
4245
4246 unsigned LinearIndex = ComputeLinearIndex(AggTy, Indices);
4247
4248 const TargetLowering &TLI = DAG.getTa