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