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