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