6e9125d0c7cc524ab678e5c339dd6a1b84f46f69
[oota-llvm.git] / lib / CodeGen / SelectionDAG / SelectionDAGBuilder.cpp
1 //===-- SelectionDAGBuilder.cpp - Selection-DAG building ------------------===//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This implements routines for translating from LLVM IR into SelectionDAG IR.
11 //
12 //===----------------------------------------------------------------------===//
13
14 #include "SelectionDAGBuilder.h"
15 #include "SDNodeDbgValue.h"
16 #include "llvm/ADT/BitVector.h"
17 #include "llvm/ADT/Optional.h"
18 #include "llvm/ADT/SmallSet.h"
19 #include "llvm/ADT/Statistic.h"
20 #include "llvm/Analysis/AliasAnalysis.h"
21 #include "llvm/Analysis/BranchProbabilityInfo.h"
22 #include "llvm/Analysis/ConstantFolding.h"
23 #include "llvm/Analysis/TargetLibraryInfo.h"
24 #include "llvm/Analysis/ValueTracking.h"
25 #include "llvm/CodeGen/FastISel.h"
26 #include "llvm/CodeGen/FunctionLoweringInfo.h"
27 #include "llvm/CodeGen/GCMetadata.h"
28 #include "llvm/CodeGen/GCStrategy.h"
29 #include "llvm/CodeGen/MachineFrameInfo.h"
30 #include "llvm/CodeGen/MachineFunction.h"
31 #include "llvm/CodeGen/MachineInstrBuilder.h"
32 #include "llvm/CodeGen/MachineJumpTableInfo.h"
33 #include "llvm/CodeGen/MachineModuleInfo.h"
34 #include "llvm/CodeGen/MachineRegisterInfo.h"
35 #include "llvm/CodeGen/SelectionDAG.h"
36 #include "llvm/CodeGen/StackMaps.h"
37 #include "llvm/CodeGen/WinEHFuncInfo.h"
38 #include "llvm/IR/CallingConv.h"
39 #include "llvm/IR/Constants.h"
40 #include "llvm/IR/DataLayout.h"
41 #include "llvm/IR/DebugInfo.h"
42 #include "llvm/IR/DerivedTypes.h"
43 #include "llvm/IR/Function.h"
44 #include "llvm/IR/GlobalVariable.h"
45 #include "llvm/IR/InlineAsm.h"
46 #include "llvm/IR/Instructions.h"
47 #include "llvm/IR/IntrinsicInst.h"
48 #include "llvm/IR/Intrinsics.h"
49 #include "llvm/IR/LLVMContext.h"
50 #include "llvm/IR/Module.h"
51 #include "llvm/IR/Statepoint.h"
52 #include "llvm/MC/MCSymbol.h"
53 #include "llvm/Support/CommandLine.h"
54 #include "llvm/Support/Debug.h"
55 #include "llvm/Support/ErrorHandling.h"
56 #include "llvm/Support/MathExtras.h"
57 #include "llvm/Support/raw_ostream.h"
58 #include "llvm/Target/TargetFrameLowering.h"
59 #include "llvm/Target/TargetInstrInfo.h"
60 #include "llvm/Target/TargetIntrinsicInfo.h"
61 #include "llvm/Target/TargetLowering.h"
62 #include "llvm/Target/TargetOptions.h"
63 #include "llvm/Target/TargetSelectionDAGInfo.h"
64 #include "llvm/Target/TargetSubtargetInfo.h"
65 #include <algorithm>
66 using namespace llvm;
67
68 #define DEBUG_TYPE "isel"
69
70 /// LimitFloatPrecision - Generate low-precision inline sequences for
71 /// some float libcalls (6, 8 or 12 bits).
72 static unsigned LimitFloatPrecision;
73
74 static cl::opt<unsigned, true>
75 LimitFPPrecision("limit-float-precision",
76                  cl::desc("Generate low-precision inline sequences "
77                           "for some float libcalls"),
78                  cl::location(LimitFloatPrecision),
79                  cl::init(0));
80
81 static cl::opt<bool>
82 EnableFMFInDAG("enable-fmf-dag", cl::init(false), cl::Hidden,
83                 cl::desc("Enable fast-math-flags for DAG nodes"));
84
85 // Limit the width of DAG chains. This is important in general to prevent
86 // DAG-based analysis from blowing up. For example, alias analysis and
87 // load clustering may not complete in reasonable time. It is difficult to
88 // recognize and avoid this situation within each individual analysis, and
89 // future analyses are likely to have the same behavior. Limiting DAG width is
90 // the safe approach and will be especially important with global DAGs.
91 //
92 // MaxParallelChains default is arbitrarily high to avoid affecting
93 // optimization, but could be lowered to improve compile time. Any ld-ld-st-st
94 // sequence over this should have been converted to llvm.memcpy by the
95 // frontend. It easy to induce this behavior with .ll code such as:
96 // %buffer = alloca [4096 x i8]
97 // %data = load [4096 x i8]* %argPtr
98 // store [4096 x i8] %data, [4096 x i8]* %buffer
99 static const unsigned MaxParallelChains = 64;
100
101 static SDValue getCopyFromPartsVector(SelectionDAG &DAG, SDLoc DL,
102                                       const SDValue *Parts, unsigned NumParts,
103                                       MVT PartVT, EVT ValueVT, const Value *V);
104
105 /// getCopyFromParts - Create a value that contains the specified legal parts
106 /// combined into the value they represent.  If the parts combine to a type
107 /// larger then ValueVT then AssertOp can be used to specify whether the extra
108 /// bits are known to be zero (ISD::AssertZext) or sign extended from ValueVT
109 /// (ISD::AssertSext).
110 static SDValue getCopyFromParts(SelectionDAG &DAG, SDLoc DL,
111                                 const SDValue *Parts,
112                                 unsigned NumParts, MVT PartVT, EVT ValueVT,
113                                 const Value *V,
114                                 ISD::NodeType AssertOp = ISD::DELETED_NODE) {
115   if (ValueVT.isVector())
116     return getCopyFromPartsVector(DAG, DL, Parts, NumParts,
117                                   PartVT, ValueVT, V);
118
119   assert(NumParts > 0 && "No parts to assemble!");
120   const TargetLowering &TLI = DAG.getTargetLoweringInfo();
121   SDValue Val = Parts[0];
122
123   if (NumParts > 1) {
124     // Assemble the value from multiple parts.
125     if (ValueVT.isInteger()) {
126       unsigned PartBits = PartVT.getSizeInBits();
127       unsigned ValueBits = ValueVT.getSizeInBits();
128
129       // Assemble the power of 2 part.
130       unsigned RoundParts = NumParts & (NumParts - 1) ?
131         1 << Log2_32(NumParts) : NumParts;
132       unsigned RoundBits = PartBits * RoundParts;
133       EVT RoundVT = RoundBits == ValueBits ?
134         ValueVT : EVT::getIntegerVT(*DAG.getContext(), RoundBits);
135       SDValue Lo, Hi;
136
137       EVT HalfVT = EVT::getIntegerVT(*DAG.getContext(), RoundBits/2);
138
139       if (RoundParts > 2) {
140         Lo = getCopyFromParts(DAG, DL, Parts, RoundParts / 2,
141                               PartVT, HalfVT, V);
142         Hi = getCopyFromParts(DAG, DL, Parts + RoundParts / 2,
143                               RoundParts / 2, PartVT, HalfVT, V);
144       } else {
145         Lo = DAG.getNode(ISD::BITCAST, DL, HalfVT, Parts[0]);
146         Hi = DAG.getNode(ISD::BITCAST, DL, HalfVT, Parts[1]);
147       }
148
149       if (DAG.getDataLayout().isBigEndian())
150         std::swap(Lo, Hi);
151
152       Val = DAG.getNode(ISD::BUILD_PAIR, DL, RoundVT, Lo, Hi);
153
154       if (RoundParts < NumParts) {
155         // Assemble the trailing non-power-of-2 part.
156         unsigned OddParts = NumParts - RoundParts;
157         EVT OddVT = EVT::getIntegerVT(*DAG.getContext(), OddParts * PartBits);
158         Hi = getCopyFromParts(DAG, DL,
159                               Parts + RoundParts, OddParts, PartVT, OddVT, V);
160
161         // Combine the round and odd parts.
162         Lo = Val;
163         if (DAG.getDataLayout().isBigEndian())
164           std::swap(Lo, Hi);
165         EVT TotalVT = EVT::getIntegerVT(*DAG.getContext(), NumParts * PartBits);
166         Hi = DAG.getNode(ISD::ANY_EXTEND, DL, TotalVT, Hi);
167         Hi = DAG.getNode(ISD::SHL, DL, TotalVT, Hi,
168                          DAG.getConstant(Lo.getValueType().getSizeInBits(), DL,
169                                          TLI.getPointerTy()));
170         Lo = DAG.getNode(ISD::ZERO_EXTEND, DL, TotalVT, Lo);
171         Val = DAG.getNode(ISD::OR, DL, TotalVT, Lo, Hi);
172       }
173     } else if (PartVT.isFloatingPoint()) {
174       // FP split into multiple FP parts (for ppcf128)
175       assert(ValueVT == EVT(MVT::ppcf128) && PartVT == MVT::f64 &&
176              "Unexpected split");
177       SDValue Lo, Hi;
178       Lo = DAG.getNode(ISD::BITCAST, DL, EVT(MVT::f64), Parts[0]);
179       Hi = DAG.getNode(ISD::BITCAST, DL, EVT(MVT::f64), Parts[1]);
180       if (TLI.hasBigEndianPartOrdering(ValueVT, DAG.getDataLayout()))
181         std::swap(Lo, Hi);
182       Val = DAG.getNode(ISD::BUILD_PAIR, DL, ValueVT, Lo, Hi);
183     } else {
184       // FP split into integer parts (soft fp)
185       assert(ValueVT.isFloatingPoint() && PartVT.isInteger() &&
186              !PartVT.isVector() && "Unexpected split");
187       EVT IntVT = EVT::getIntegerVT(*DAG.getContext(), ValueVT.getSizeInBits());
188       Val = getCopyFromParts(DAG, DL, Parts, NumParts, PartVT, IntVT, V);
189     }
190   }
191
192   // There is now one part, held in Val.  Correct it to match ValueVT.
193   EVT PartEVT = Val.getValueType();
194
195   if (PartEVT == ValueVT)
196     return Val;
197
198   if (PartEVT.isInteger() && ValueVT.isInteger()) {
199     if (ValueVT.bitsLT(PartEVT)) {
200       // For a truncate, see if we have any information to
201       // indicate whether the truncated bits will always be
202       // zero or sign-extension.
203       if (AssertOp != ISD::DELETED_NODE)
204         Val = DAG.getNode(AssertOp, DL, PartEVT, Val,
205                           DAG.getValueType(ValueVT));
206       return DAG.getNode(ISD::TRUNCATE, DL, ValueVT, Val);
207     }
208     return DAG.getNode(ISD::ANY_EXTEND, DL, ValueVT, Val);
209   }
210
211   if (PartEVT.isFloatingPoint() && ValueVT.isFloatingPoint()) {
212     // FP_ROUND's are always exact here.
213     if (ValueVT.bitsLT(Val.getValueType()))
214       return DAG.getNode(ISD::FP_ROUND, DL, ValueVT, Val,
215                          DAG.getTargetConstant(1, DL, TLI.getPointerTy()));
216
217     return DAG.getNode(ISD::FP_EXTEND, DL, ValueVT, Val);
218   }
219
220   if (PartEVT.getSizeInBits() == ValueVT.getSizeInBits())
221     return DAG.getNode(ISD::BITCAST, DL, ValueVT, Val);
222
223   llvm_unreachable("Unknown mismatch!");
224 }
225
226 static void diagnosePossiblyInvalidConstraint(LLVMContext &Ctx, const Value *V,
227                                               const Twine &ErrMsg) {
228   const Instruction *I = dyn_cast_or_null<Instruction>(V);
229   if (!V)
230     return Ctx.emitError(ErrMsg);
231
232   const char *AsmError = ", possible invalid constraint for vector type";
233   if (const CallInst *CI = dyn_cast<CallInst>(I))
234     if (isa<InlineAsm>(CI->getCalledValue()))
235       return Ctx.emitError(I, ErrMsg + AsmError);
236
237   return Ctx.emitError(I, ErrMsg);
238 }
239
240 /// getCopyFromPartsVector - Create a value that contains the specified legal
241 /// parts combined into the value they represent.  If the parts combine to a
242 /// type larger then ValueVT then AssertOp can be used to specify whether the
243 /// extra bits are known to be zero (ISD::AssertZext) or sign extended from
244 /// ValueVT (ISD::AssertSext).
245 static SDValue getCopyFromPartsVector(SelectionDAG &DAG, SDLoc DL,
246                                       const SDValue *Parts, unsigned NumParts,
247                                       MVT PartVT, EVT ValueVT, const Value *V) {
248   assert(ValueVT.isVector() && "Not a vector value");
249   assert(NumParts > 0 && "No parts to assemble!");
250   const TargetLowering &TLI = DAG.getTargetLoweringInfo();
251   SDValue Val = Parts[0];
252
253   // Handle a multi-element vector.
254   if (NumParts > 1) {
255     EVT IntermediateVT;
256     MVT RegisterVT;
257     unsigned NumIntermediates;
258     unsigned NumRegs =
259     TLI.getVectorTypeBreakdown(*DAG.getContext(), ValueVT, IntermediateVT,
260                                NumIntermediates, RegisterVT);
261     assert(NumRegs == NumParts && "Part count doesn't match vector breakdown!");
262     NumParts = NumRegs; // Silence a compiler warning.
263     assert(RegisterVT == PartVT && "Part type doesn't match vector breakdown!");
264     assert(RegisterVT.getSizeInBits() ==
265            Parts[0].getSimpleValueType().getSizeInBits() &&
266            "Part type sizes don't match!");
267
268     // Assemble the parts into intermediate operands.
269     SmallVector<SDValue, 8> Ops(NumIntermediates);
270     if (NumIntermediates == NumParts) {
271       // If the register was not expanded, truncate or copy the value,
272       // as appropriate.
273       for (unsigned i = 0; i != NumParts; ++i)
274         Ops[i] = getCopyFromParts(DAG, DL, &Parts[i], 1,
275                                   PartVT, IntermediateVT, V);
276     } else if (NumParts > 0) {
277       // If the intermediate type was expanded, build the intermediate
278       // operands from the parts.
279       assert(NumParts % NumIntermediates == 0 &&
280              "Must expand into a divisible number of parts!");
281       unsigned Factor = NumParts / NumIntermediates;
282       for (unsigned i = 0; i != NumIntermediates; ++i)
283         Ops[i] = getCopyFromParts(DAG, DL, &Parts[i * Factor], Factor,
284                                   PartVT, IntermediateVT, V);
285     }
286
287     // Build a vector with BUILD_VECTOR or CONCAT_VECTORS from the
288     // intermediate operands.
289     Val = DAG.getNode(IntermediateVT.isVector() ? ISD::CONCAT_VECTORS
290                                                 : ISD::BUILD_VECTOR,
291                       DL, ValueVT, Ops);
292   }
293
294   // There is now one part, held in Val.  Correct it to match ValueVT.
295   EVT PartEVT = Val.getValueType();
296
297   if (PartEVT == ValueVT)
298     return Val;
299
300   if (PartEVT.isVector()) {
301     // If the element type of the source/dest vectors are the same, but the
302     // parts vector has more elements than the value vector, then we have a
303     // vector widening case (e.g. <2 x float> -> <4 x float>).  Extract the
304     // elements we want.
305     if (PartEVT.getVectorElementType() == ValueVT.getVectorElementType()) {
306       assert(PartEVT.getVectorNumElements() > ValueVT.getVectorNumElements() &&
307              "Cannot narrow, it would be a lossy transformation");
308       return DAG.getNode(ISD::EXTRACT_SUBVECTOR, DL, ValueVT, Val,
309                          DAG.getConstant(0, DL, TLI.getVectorIdxTy()));
310     }
311
312     // Vector/Vector bitcast.
313     if (ValueVT.getSizeInBits() == PartEVT.getSizeInBits())
314       return DAG.getNode(ISD::BITCAST, DL, ValueVT, Val);
315
316     assert(PartEVT.getVectorNumElements() == ValueVT.getVectorNumElements() &&
317       "Cannot handle this kind of promotion");
318     // Promoted vector extract
319     bool Smaller = ValueVT.bitsLE(PartEVT);
320     return DAG.getNode((Smaller ? ISD::TRUNCATE : ISD::ANY_EXTEND),
321                        DL, ValueVT, Val);
322
323   }
324
325   // Trivial bitcast if the types are the same size and the destination
326   // vector type is legal.
327   if (PartEVT.getSizeInBits() == ValueVT.getSizeInBits() &&
328       TLI.isTypeLegal(ValueVT))
329     return DAG.getNode(ISD::BITCAST, DL, ValueVT, Val);
330
331   // Handle cases such as i8 -> <1 x i1>
332   if (ValueVT.getVectorNumElements() != 1) {
333     diagnosePossiblyInvalidConstraint(*DAG.getContext(), V,
334                                       "non-trivial scalar-to-vector conversion");
335     return DAG.getUNDEF(ValueVT);
336   }
337
338   if (ValueVT.getVectorNumElements() == 1 &&
339       ValueVT.getVectorElementType() != PartEVT) {
340     bool Smaller = ValueVT.bitsLE(PartEVT);
341     Val = DAG.getNode((Smaller ? ISD::TRUNCATE : ISD::ANY_EXTEND),
342                        DL, ValueVT.getScalarType(), Val);
343   }
344
345   return DAG.getNode(ISD::BUILD_VECTOR, DL, ValueVT, Val);
346 }
347
348 static void getCopyToPartsVector(SelectionDAG &DAG, SDLoc dl,
349                                  SDValue Val, SDValue *Parts, unsigned NumParts,
350                                  MVT PartVT, const Value *V);
351
352 /// getCopyToParts - Create a series of nodes that contain the specified value
353 /// split into legal parts.  If the parts contain more bits than Val, then, for
354 /// integers, ExtendKind can be used to specify how to generate the extra bits.
355 static void getCopyToParts(SelectionDAG &DAG, SDLoc DL,
356                            SDValue Val, SDValue *Parts, unsigned NumParts,
357                            MVT PartVT, const Value *V,
358                            ISD::NodeType ExtendKind = ISD::ANY_EXTEND) {
359   EVT ValueVT = Val.getValueType();
360
361   // Handle the vector case separately.
362   if (ValueVT.isVector())
363     return getCopyToPartsVector(DAG, DL, Val, Parts, NumParts, PartVT, V);
364
365   unsigned PartBits = PartVT.getSizeInBits();
366   unsigned OrigNumParts = NumParts;
367   assert(DAG.getTargetLoweringInfo().isTypeLegal(PartVT) &&
368          "Copying to an illegal type!");
369
370   if (NumParts == 0)
371     return;
372
373   assert(!ValueVT.isVector() && "Vector case handled elsewhere");
374   EVT PartEVT = PartVT;
375   if (PartEVT == ValueVT) {
376     assert(NumParts == 1 && "No-op copy with multiple parts!");
377     Parts[0] = Val;
378     return;
379   }
380
381   if (NumParts * PartBits > ValueVT.getSizeInBits()) {
382     // If the parts cover more bits than the value has, promote the value.
383     if (PartVT.isFloatingPoint() && ValueVT.isFloatingPoint()) {
384       assert(NumParts == 1 && "Do not know what to promote to!");
385       Val = DAG.getNode(ISD::FP_EXTEND, DL, PartVT, Val);
386     } else {
387       assert((PartVT.isInteger() || PartVT == MVT::x86mmx) &&
388              ValueVT.isInteger() &&
389              "Unknown mismatch!");
390       ValueVT = EVT::getIntegerVT(*DAG.getContext(), NumParts * PartBits);
391       Val = DAG.getNode(ExtendKind, DL, ValueVT, Val);
392       if (PartVT == MVT::x86mmx)
393         Val = DAG.getNode(ISD::BITCAST, DL, PartVT, Val);
394     }
395   } else if (PartBits == ValueVT.getSizeInBits()) {
396     // Different types of the same size.
397     assert(NumParts == 1 && PartEVT != ValueVT);
398     Val = DAG.getNode(ISD::BITCAST, DL, PartVT, Val);
399   } else if (NumParts * PartBits < ValueVT.getSizeInBits()) {
400     // If the parts cover less bits than value has, truncate the value.
401     assert((PartVT.isInteger() || PartVT == MVT::x86mmx) &&
402            ValueVT.isInteger() &&
403            "Unknown mismatch!");
404     ValueVT = EVT::getIntegerVT(*DAG.getContext(), NumParts * PartBits);
405     Val = DAG.getNode(ISD::TRUNCATE, DL, ValueVT, Val);
406     if (PartVT == MVT::x86mmx)
407       Val = DAG.getNode(ISD::BITCAST, DL, PartVT, Val);
408   }
409
410   // The value may have changed - recompute ValueVT.
411   ValueVT = Val.getValueType();
412   assert(NumParts * PartBits == ValueVT.getSizeInBits() &&
413          "Failed to tile the value with PartVT!");
414
415   if (NumParts == 1) {
416     if (PartEVT != ValueVT)
417       diagnosePossiblyInvalidConstraint(*DAG.getContext(), V,
418                                         "scalar-to-vector conversion failed");
419
420     Parts[0] = Val;
421     return;
422   }
423
424   // Expand the value into multiple parts.
425   if (NumParts & (NumParts - 1)) {
426     // The number of parts is not a power of 2.  Split off and copy the tail.
427     assert(PartVT.isInteger() && ValueVT.isInteger() &&
428            "Do not know what to expand to!");
429     unsigned RoundParts = 1 << Log2_32(NumParts);
430     unsigned RoundBits = RoundParts * PartBits;
431     unsigned OddParts = NumParts - RoundParts;
432     SDValue OddVal = DAG.getNode(ISD::SRL, DL, ValueVT, Val,
433                                  DAG.getIntPtrConstant(RoundBits, DL));
434     getCopyToParts(DAG, DL, OddVal, Parts + RoundParts, OddParts, PartVT, V);
435
436     if (DAG.getDataLayout().isBigEndian())
437       // The odd parts were reversed by getCopyToParts - unreverse them.
438       std::reverse(Parts + RoundParts, Parts + NumParts);
439
440     NumParts = RoundParts;
441     ValueVT = EVT::getIntegerVT(*DAG.getContext(), NumParts * PartBits);
442     Val = DAG.getNode(ISD::TRUNCATE, DL, ValueVT, Val);
443   }
444
445   // The number of parts is a power of 2.  Repeatedly bisect the value using
446   // EXTRACT_ELEMENT.
447   Parts[0] = DAG.getNode(ISD::BITCAST, DL,
448                          EVT::getIntegerVT(*DAG.getContext(),
449                                            ValueVT.getSizeInBits()),
450                          Val);
451
452   for (unsigned StepSize = NumParts; StepSize > 1; StepSize /= 2) {
453     for (unsigned i = 0; i < NumParts; i += StepSize) {
454       unsigned ThisBits = StepSize * PartBits / 2;
455       EVT ThisVT = EVT::getIntegerVT(*DAG.getContext(), ThisBits);
456       SDValue &Part0 = Parts[i];
457       SDValue &Part1 = Parts[i+StepSize/2];
458
459       Part1 = DAG.getNode(ISD::EXTRACT_ELEMENT, DL,
460                           ThisVT, Part0, DAG.getIntPtrConstant(1, DL));
461       Part0 = DAG.getNode(ISD::EXTRACT_ELEMENT, DL,
462                           ThisVT, Part0, DAG.getIntPtrConstant(0, DL));
463
464       if (ThisBits == PartBits && ThisVT != PartVT) {
465         Part0 = DAG.getNode(ISD::BITCAST, DL, PartVT, Part0);
466         Part1 = DAG.getNode(ISD::BITCAST, DL, PartVT, Part1);
467       }
468     }
469   }
470
471   if (DAG.getDataLayout().isBigEndian())
472     std::reverse(Parts, Parts + OrigNumParts);
473 }
474
475
476 /// getCopyToPartsVector - Create a series of nodes that contain the specified
477 /// value split into legal parts.
478 static void getCopyToPartsVector(SelectionDAG &DAG, SDLoc DL,
479                                  SDValue Val, SDValue *Parts, unsigned NumParts,
480                                  MVT PartVT, const Value *V) {
481   EVT ValueVT = Val.getValueType();
482   assert(ValueVT.isVector() && "Not a vector");
483   const TargetLowering &TLI = DAG.getTargetLoweringInfo();
484
485   if (NumParts == 1) {
486     EVT PartEVT = PartVT;
487     if (PartEVT == ValueVT) {
488       // Nothing to do.
489     } else if (PartVT.getSizeInBits() == ValueVT.getSizeInBits()) {
490       // Bitconvert vector->vector case.
491       Val = DAG.getNode(ISD::BITCAST, DL, PartVT, Val);
492     } else if (PartVT.isVector() &&
493                PartEVT.getVectorElementType() == ValueVT.getVectorElementType() &&
494                PartEVT.getVectorNumElements() > ValueVT.getVectorNumElements()) {
495       EVT ElementVT = PartVT.getVectorElementType();
496       // Vector widening case, e.g. <2 x float> -> <4 x float>.  Shuffle in
497       // undef elements.
498       SmallVector<SDValue, 16> Ops;
499       for (unsigned i = 0, e = ValueVT.getVectorNumElements(); i != e; ++i)
500         Ops.push_back(DAG.getNode(ISD::EXTRACT_VECTOR_ELT, DL,
501                                   ElementVT, Val, DAG.getConstant(i, DL,
502                                                   TLI.getVectorIdxTy())));
503
504       for (unsigned i = ValueVT.getVectorNumElements(),
505            e = PartVT.getVectorNumElements(); i != e; ++i)
506         Ops.push_back(DAG.getUNDEF(ElementVT));
507
508       Val = DAG.getNode(ISD::BUILD_VECTOR, DL, PartVT, Ops);
509
510       // FIXME: Use CONCAT for 2x -> 4x.
511
512       //SDValue UndefElts = DAG.getUNDEF(VectorTy);
513       //Val = DAG.getNode(ISD::CONCAT_VECTORS, DL, PartVT, Val, UndefElts);
514     } else if (PartVT.isVector() &&
515                PartEVT.getVectorElementType().bitsGE(
516                  ValueVT.getVectorElementType()) &&
517                PartEVT.getVectorNumElements() == ValueVT.getVectorNumElements()) {
518
519       // Promoted vector extract
520       bool Smaller = PartEVT.bitsLE(ValueVT);
521       Val = DAG.getNode((Smaller ? ISD::TRUNCATE : ISD::ANY_EXTEND),
522                         DL, PartVT, Val);
523     } else{
524       // Vector -> scalar conversion.
525       assert(ValueVT.getVectorNumElements() == 1 &&
526              "Only trivial vector-to-scalar conversions should get here!");
527       Val = DAG.getNode(ISD::EXTRACT_VECTOR_ELT, DL,
528                         PartVT, Val,
529                         DAG.getConstant(0, DL, TLI.getVectorIdxTy()));
530
531       bool Smaller = ValueVT.bitsLE(PartVT);
532       Val = DAG.getNode((Smaller ? ISD::TRUNCATE : ISD::ANY_EXTEND),
533                          DL, PartVT, Val);
534     }
535
536     Parts[0] = Val;
537     return;
538   }
539
540   // Handle a multi-element vector.
541   EVT IntermediateVT;
542   MVT RegisterVT;
543   unsigned NumIntermediates;
544   unsigned NumRegs = TLI.getVectorTypeBreakdown(*DAG.getContext(), ValueVT,
545                                                 IntermediateVT,
546                                                 NumIntermediates, RegisterVT);
547   unsigned NumElements = ValueVT.getVectorNumElements();
548
549   assert(NumRegs == NumParts && "Part count doesn't match vector breakdown!");
550   NumParts = NumRegs; // Silence a compiler warning.
551   assert(RegisterVT == PartVT && "Part type doesn't match vector breakdown!");
552
553   // Split the vector into intermediate operands.
554   SmallVector<SDValue, 8> Ops(NumIntermediates);
555   for (unsigned i = 0; i != NumIntermediates; ++i) {
556     if (IntermediateVT.isVector())
557       Ops[i] = DAG.getNode(ISD::EXTRACT_SUBVECTOR, DL,
558                            IntermediateVT, Val,
559                    DAG.getConstant(i * (NumElements / NumIntermediates), DL,
560                                    TLI.getVectorIdxTy()));
561     else
562       Ops[i] = DAG.getNode(ISD::EXTRACT_VECTOR_ELT, DL,
563                            IntermediateVT, Val,
564                            DAG.getConstant(i, DL, TLI.getVectorIdxTy()));
565   }
566
567   // Split the intermediate operands into legal parts.
568   if (NumParts == NumIntermediates) {
569     // If the register was not expanded, promote or copy the value,
570     // as appropriate.
571     for (unsigned i = 0; i != NumParts; ++i)
572       getCopyToParts(DAG, DL, Ops[i], &Parts[i], 1, PartVT, V);
573   } else if (NumParts > 0) {
574     // If the intermediate type was expanded, split each the value into
575     // legal parts.
576     assert(NumIntermediates != 0 && "division by zero");
577     assert(NumParts % NumIntermediates == 0 &&
578            "Must expand into a divisible number of parts!");
579     unsigned Factor = NumParts / NumIntermediates;
580     for (unsigned i = 0; i != NumIntermediates; ++i)
581       getCopyToParts(DAG, DL, Ops[i], &Parts[i*Factor], Factor, PartVT, V);
582   }
583 }
584
585 RegsForValue::RegsForValue() {}
586
587 RegsForValue::RegsForValue(const SmallVector<unsigned, 4> &regs, MVT regvt,
588                            EVT valuevt)
589     : ValueVTs(1, valuevt), RegVTs(1, regvt), Regs(regs) {}
590
591 RegsForValue::RegsForValue(LLVMContext &Context, const TargetLowering &tli,
592                            unsigned Reg, Type *Ty) {
593   ComputeValueVTs(tli, Ty, ValueVTs);
594
595   for (unsigned Value = 0, e = ValueVTs.size(); Value != e; ++Value) {
596     EVT ValueVT = ValueVTs[Value];
597     unsigned NumRegs = tli.getNumRegisters(Context, ValueVT);
598     MVT RegisterVT = tli.getRegisterType(Context, ValueVT);
599     for (unsigned i = 0; i != NumRegs; ++i)
600       Regs.push_back(Reg + i);
601     RegVTs.push_back(RegisterVT);
602     Reg += NumRegs;
603   }
604 }
605
606 /// getCopyFromRegs - Emit a series of CopyFromReg nodes that copies from
607 /// this value and returns the result as a ValueVT value.  This uses
608 /// Chain/Flag as the input and updates them for the output Chain/Flag.
609 /// If the Flag pointer is NULL, no flag is used.
610 SDValue RegsForValue::getCopyFromRegs(SelectionDAG &DAG,
611                                       FunctionLoweringInfo &FuncInfo,
612                                       SDLoc dl,
613                                       SDValue &Chain, SDValue *Flag,
614                                       const Value *V) const {
615   // A Value with type {} or [0 x %t] needs no registers.
616   if (ValueVTs.empty())
617     return SDValue();
618
619   const TargetLowering &TLI = DAG.getTargetLoweringInfo();
620
621   // Assemble the legal parts into the final values.
622   SmallVector<SDValue, 4> Values(ValueVTs.size());
623   SmallVector<SDValue, 8> Parts;
624   for (unsigned Value = 0, Part = 0, e = ValueVTs.size(); Value != e; ++Value) {
625     // Copy the legal parts from the registers.
626     EVT ValueVT = ValueVTs[Value];
627     unsigned NumRegs = TLI.getNumRegisters(*DAG.getContext(), ValueVT);
628     MVT RegisterVT = RegVTs[Value];
629
630     Parts.resize(NumRegs);
631     for (unsigned i = 0; i != NumRegs; ++i) {
632       SDValue P;
633       if (!Flag) {
634         P = DAG.getCopyFromReg(Chain, dl, Regs[Part+i], RegisterVT);
635       } else {
636         P = DAG.getCopyFromReg(Chain, dl, Regs[Part+i], RegisterVT, *Flag);
637         *Flag = P.getValue(2);
638       }
639
640       Chain = P.getValue(1);
641       Parts[i] = P;
642
643       // If the source register was virtual and if we know something about it,
644       // add an assert node.
645       if (!TargetRegisterInfo::isVirtualRegister(Regs[Part+i]) ||
646           !RegisterVT.isInteger() || RegisterVT.isVector())
647         continue;
648
649       const FunctionLoweringInfo::LiveOutInfo *LOI =
650         FuncInfo.GetLiveOutRegInfo(Regs[Part+i]);
651       if (!LOI)
652         continue;
653
654       unsigned RegSize = RegisterVT.getSizeInBits();
655       unsigned NumSignBits = LOI->NumSignBits;
656       unsigned NumZeroBits = LOI->KnownZero.countLeadingOnes();
657
658       if (NumZeroBits == RegSize) {
659         // The current value is a zero.
660         // Explicitly express that as it would be easier for
661         // optimizations to kick in.
662         Parts[i] = DAG.getConstant(0, dl, RegisterVT);
663         continue;
664       }
665
666       // FIXME: We capture more information than the dag can represent.  For
667       // now, just use the tightest assertzext/assertsext possible.
668       bool isSExt = true;
669       EVT FromVT(MVT::Other);
670       if (NumSignBits == RegSize)
671         isSExt = true, FromVT = MVT::i1;   // ASSERT SEXT 1
672       else if (NumZeroBits >= RegSize-1)
673         isSExt = false, FromVT = MVT::i1;  // ASSERT ZEXT 1
674       else if (NumSignBits > RegSize-8)
675         isSExt = true, FromVT = MVT::i8;   // ASSERT SEXT 8
676       else if (NumZeroBits >= RegSize-8)
677         isSExt = false, FromVT = MVT::i8;  // ASSERT ZEXT 8
678       else if (NumSignBits > RegSize-16)
679         isSExt = true, FromVT = MVT::i16;  // ASSERT SEXT 16
680       else if (NumZeroBits >= RegSize-16)
681         isSExt = false, FromVT = MVT::i16; // ASSERT ZEXT 16
682       else if (NumSignBits > RegSize-32)
683         isSExt = true, FromVT = MVT::i32;  // ASSERT SEXT 32
684       else if (NumZeroBits >= RegSize-32)
685         isSExt = false, FromVT = MVT::i32; // ASSERT ZEXT 32
686       else
687         continue;
688
689       // Add an assertion node.
690       assert(FromVT != MVT::Other);
691       Parts[i] = DAG.getNode(isSExt ? ISD::AssertSext : ISD::AssertZext, dl,
692                              RegisterVT, P, DAG.getValueType(FromVT));
693     }
694
695     Values[Value] = getCopyFromParts(DAG, dl, Parts.begin(),
696                                      NumRegs, RegisterVT, ValueVT, V);
697     Part += NumRegs;
698     Parts.clear();
699   }
700
701   return DAG.getNode(ISD::MERGE_VALUES, dl, DAG.getVTList(ValueVTs), Values);
702 }
703
704 /// getCopyToRegs - Emit a series of CopyToReg nodes that copies the
705 /// specified value into the registers specified by this object.  This uses
706 /// Chain/Flag as the input and updates them for the output Chain/Flag.
707 /// If the Flag pointer is NULL, no flag is used.
708 void RegsForValue::getCopyToRegs(SDValue Val, SelectionDAG &DAG, SDLoc dl,
709                                  SDValue &Chain, SDValue *Flag, const Value *V,
710                                  ISD::NodeType PreferredExtendType) const {
711   const TargetLowering &TLI = DAG.getTargetLoweringInfo();
712   ISD::NodeType ExtendKind = PreferredExtendType;
713
714   // Get the list of the values's legal parts.
715   unsigned NumRegs = Regs.size();
716   SmallVector<SDValue, 8> Parts(NumRegs);
717   for (unsigned Value = 0, Part = 0, e = ValueVTs.size(); Value != e; ++Value) {
718     EVT ValueVT = ValueVTs[Value];
719     unsigned NumParts = TLI.getNumRegisters(*DAG.getContext(), ValueVT);
720     MVT RegisterVT = RegVTs[Value];
721
722     if (ExtendKind == ISD::ANY_EXTEND && TLI.isZExtFree(Val, RegisterVT))
723       ExtendKind = ISD::ZERO_EXTEND;
724
725     getCopyToParts(DAG, dl, Val.getValue(Val.getResNo() + Value),
726                    &Parts[Part], NumParts, RegisterVT, V, ExtendKind);
727     Part += NumParts;
728   }
729
730   // Copy the parts into the registers.
731   SmallVector<SDValue, 8> Chains(NumRegs);
732   for (unsigned i = 0; i != NumRegs; ++i) {
733     SDValue Part;
734     if (!Flag) {
735       Part = DAG.getCopyToReg(Chain, dl, Regs[i], Parts[i]);
736     } else {
737       Part = DAG.getCopyToReg(Chain, dl, Regs[i], Parts[i], *Flag);
738       *Flag = Part.getValue(1);
739     }
740
741     Chains[i] = Part.getValue(0);
742   }
743
744   if (NumRegs == 1 || Flag)
745     // If NumRegs > 1 && Flag is used then the use of the last CopyToReg is
746     // flagged to it. That is the CopyToReg nodes and the user are considered
747     // a single scheduling unit. If we create a TokenFactor and return it as
748     // chain, then the TokenFactor is both a predecessor (operand) of the
749     // user as well as a successor (the TF operands are flagged to the user).
750     // c1, f1 = CopyToReg
751     // c2, f2 = CopyToReg
752     // c3     = TokenFactor c1, c2
753     // ...
754     //        = op c3, ..., f2
755     Chain = Chains[NumRegs-1];
756   else
757     Chain = DAG.getNode(ISD::TokenFactor, dl, MVT::Other, Chains);
758 }
759
760 /// AddInlineAsmOperands - Add this value to the specified inlineasm node
761 /// operand list.  This adds the code marker and includes the number of
762 /// values added into it.
763 void RegsForValue::AddInlineAsmOperands(unsigned Code, bool HasMatching,
764                                         unsigned MatchingIdx, SDLoc dl,
765                                         SelectionDAG &DAG,
766                                         std::vector<SDValue> &Ops) const {
767   const TargetLowering &TLI = DAG.getTargetLoweringInfo();
768
769   unsigned Flag = InlineAsm::getFlagWord(Code, Regs.size());
770   if (HasMatching)
771     Flag = InlineAsm::getFlagWordForMatchingOp(Flag, MatchingIdx);
772   else if (!Regs.empty() &&
773            TargetRegisterInfo::isVirtualRegister(Regs.front())) {
774     // Put the register class of the virtual registers in the flag word.  That
775     // way, later passes can recompute register class constraints for inline
776     // assembly as well as normal instructions.
777     // Don't do this for tied operands that can use the regclass information
778     // from the def.
779     const MachineRegisterInfo &MRI = DAG.getMachineFunction().getRegInfo();
780     const TargetRegisterClass *RC = MRI.getRegClass(Regs.front());
781     Flag = InlineAsm::getFlagWordForRegClass(Flag, RC->getID());
782   }
783
784   SDValue Res = DAG.getTargetConstant(Flag, dl, MVT::i32);
785   Ops.push_back(Res);
786
787   unsigned SP = TLI.getStackPointerRegisterToSaveRestore();
788   for (unsigned Value = 0, Reg = 0, e = ValueVTs.size(); Value != e; ++Value) {
789     unsigned NumRegs = TLI.getNumRegisters(*DAG.getContext(), ValueVTs[Value]);
790     MVT RegisterVT = RegVTs[Value];
791     for (unsigned i = 0; i != NumRegs; ++i) {
792       assert(Reg < Regs.size() && "Mismatch in # registers expected");
793       unsigned TheReg = Regs[Reg++];
794       Ops.push_back(DAG.getRegister(TheReg, RegisterVT));
795
796       if (TheReg == SP && Code == InlineAsm::Kind_Clobber) {
797         // If we clobbered the stack pointer, MFI should know about it.
798         assert(DAG.getMachineFunction().getFrameInfo()->
799             hasOpaqueSPAdjustment());
800       }
801     }
802   }
803 }
804
805 void SelectionDAGBuilder::init(GCFunctionInfo *gfi, AliasAnalysis &aa,
806                                const TargetLibraryInfo *li) {
807   AA = &aa;
808   GFI = gfi;
809   LibInfo = li;
810   DL = &DAG.getDataLayout();
811   Context = DAG.getContext();
812   LPadToCallSiteMap.clear();
813 }
814
815 /// clear - Clear out the current SelectionDAG and the associated
816 /// state and prepare this SelectionDAGBuilder object to be used
817 /// for a new block. This doesn't clear out information about
818 /// additional blocks that are needed to complete switch lowering
819 /// or PHI node updating; that information is cleared out as it is
820 /// consumed.
821 void SelectionDAGBuilder::clear() {
822   NodeMap.clear();
823   UnusedArgNodeMap.clear();
824   PendingLoads.clear();
825   PendingExports.clear();
826   CurInst = nullptr;
827   HasTailCall = false;
828   SDNodeOrder = LowestSDNodeOrder;
829   StatepointLowering.clear();
830 }
831
832 /// clearDanglingDebugInfo - Clear the dangling debug information
833 /// map. This function is separated from the clear so that debug
834 /// information that is dangling in a basic block can be properly
835 /// resolved in a different basic block. This allows the
836 /// SelectionDAG to resolve dangling debug information attached
837 /// to PHI nodes.
838 void SelectionDAGBuilder::clearDanglingDebugInfo() {
839   DanglingDebugInfoMap.clear();
840 }
841
842 /// getRoot - Return the current virtual root of the Selection DAG,
843 /// flushing any PendingLoad items. This must be done before emitting
844 /// a store or any other node that may need to be ordered after any
845 /// prior load instructions.
846 ///
847 SDValue SelectionDAGBuilder::getRoot() {
848   if (PendingLoads.empty())
849     return DAG.getRoot();
850
851   if (PendingLoads.size() == 1) {
852     SDValue Root = PendingLoads[0];
853     DAG.setRoot(Root);
854     PendingLoads.clear();
855     return Root;
856   }
857
858   // Otherwise, we have to make a token factor node.
859   SDValue Root = DAG.getNode(ISD::TokenFactor, getCurSDLoc(), MVT::Other,
860                              PendingLoads);
861   PendingLoads.clear();
862   DAG.setRoot(Root);
863   return Root;
864 }
865
866 /// getControlRoot - Similar to getRoot, but instead of flushing all the
867 /// PendingLoad items, flush all the PendingExports items. It is necessary
868 /// to do this before emitting a terminator instruction.
869 ///
870 SDValue SelectionDAGBuilder::getControlRoot() {
871   SDValue Root = DAG.getRoot();
872
873   if (PendingExports.empty())
874     return Root;
875
876   // Turn all of the CopyToReg chains into one factored node.
877   if (Root.getOpcode() != ISD::EntryToken) {
878     unsigned i = 0, e = PendingExports.size();
879     for (; i != e; ++i) {
880       assert(PendingExports[i].getNode()->getNumOperands() > 1);
881       if (PendingExports[i].getNode()->getOperand(0) == Root)
882         break;  // Don't add the root if we already indirectly depend on it.
883     }
884
885     if (i == e)
886       PendingExports.push_back(Root);
887   }
888
889   Root = DAG.getNode(ISD::TokenFactor, getCurSDLoc(), MVT::Other,
890                      PendingExports);
891   PendingExports.clear();
892   DAG.setRoot(Root);
893   return Root;
894 }
895
896 void SelectionDAGBuilder::visit(const Instruction &I) {
897   // Set up outgoing PHI node register values before emitting the terminator.
898   if (isa<TerminatorInst>(&I))
899     HandlePHINodesInSuccessorBlocks(I.getParent());
900
901   ++SDNodeOrder;
902
903   CurInst = &I;
904
905   visit(I.getOpcode(), I);
906
907   if (!isa<TerminatorInst>(&I) && !HasTailCall)
908     CopyToExportRegsIfNeeded(&I);
909
910   CurInst = nullptr;
911 }
912
913 void SelectionDAGBuilder::visitPHI(const PHINode &) {
914   llvm_unreachable("SelectionDAGBuilder shouldn't visit PHI nodes!");
915 }
916
917 void SelectionDAGBuilder::visit(unsigned Opcode, const User &I) {
918   // Note: this doesn't use InstVisitor, because it has to work with
919   // ConstantExpr's in addition to instructions.
920   switch (Opcode) {
921   default: llvm_unreachable("Unknown instruction type encountered!");
922     // Build the switch statement using the Instruction.def file.
923 #define HANDLE_INST(NUM, OPCODE, CLASS) \
924     case Instruction::OPCODE: visit##OPCODE((const CLASS&)I); break;
925 #include "llvm/IR/Instruction.def"
926   }
927 }
928
929 // resolveDanglingDebugInfo - if we saw an earlier dbg_value referring to V,
930 // generate the debug data structures now that we've seen its definition.
931 void SelectionDAGBuilder::resolveDanglingDebugInfo(const Value *V,
932                                                    SDValue Val) {
933   DanglingDebugInfo &DDI = DanglingDebugInfoMap[V];
934   if (DDI.getDI()) {
935     const DbgValueInst *DI = DDI.getDI();
936     DebugLoc dl = DDI.getdl();
937     unsigned DbgSDNodeOrder = DDI.getSDNodeOrder();
938     DILocalVariable *Variable = DI->getVariable();
939     DIExpression *Expr = DI->getExpression();
940     assert(Variable->isValidLocationForIntrinsic(dl) &&
941            "Expected inlined-at fields to agree");
942     uint64_t Offset = DI->getOffset();
943     // A dbg.value for an alloca is always indirect.
944     bool IsIndirect = isa<AllocaInst>(V) || Offset != 0;
945     SDDbgValue *SDV;
946     if (Val.getNode()) {
947       if (!EmitFuncArgumentDbgValue(V, Variable, Expr, dl, Offset, IsIndirect,
948                                     Val)) {
949         SDV = DAG.getDbgValue(Variable, Expr, Val.getNode(), Val.getResNo(),
950                               IsIndirect, Offset, dl, DbgSDNodeOrder);
951         DAG.AddDbgValue(SDV, Val.getNode(), false);
952       }
953     } else
954       DEBUG(dbgs() << "Dropping debug info for " << *DI << "\n");
955     DanglingDebugInfoMap[V] = DanglingDebugInfo();
956   }
957 }
958
959 /// getCopyFromRegs - If there was virtual register allocated for the value V
960 /// emit CopyFromReg of the specified type Ty. Return empty SDValue() otherwise.
961 SDValue SelectionDAGBuilder::getCopyFromRegs(const Value *V, Type *Ty) {
962   DenseMap<const Value *, unsigned>::iterator It = FuncInfo.ValueMap.find(V);
963   SDValue Result;
964
965   if (It != FuncInfo.ValueMap.end()) {
966     unsigned InReg = It->second;
967     RegsForValue RFV(*DAG.getContext(), DAG.getTargetLoweringInfo(), InReg,
968                      Ty);
969     SDValue Chain = DAG.getEntryNode();
970     Result = RFV.getCopyFromRegs(DAG, FuncInfo, getCurSDLoc(), Chain, nullptr, V);
971     resolveDanglingDebugInfo(V, Result);
972   }
973
974   return Result;
975 }
976
977 /// getValue - Return an SDValue for the given Value.
978 SDValue SelectionDAGBuilder::getValue(const Value *V) {
979   // If we already have an SDValue for this value, use it. It's important
980   // to do this first, so that we don't create a CopyFromReg if we already
981   // have a regular SDValue.
982   SDValue &N = NodeMap[V];
983   if (N.getNode()) return N;
984
985   // If there's a virtual register allocated and initialized for this
986   // value, use it.
987   SDValue copyFromReg = getCopyFromRegs(V, V->getType());
988   if (copyFromReg.getNode()) {
989     return copyFromReg;
990   }
991
992   // Otherwise create a new SDValue and remember it.
993   SDValue Val = getValueImpl(V);
994   NodeMap[V] = Val;
995   resolveDanglingDebugInfo(V, Val);
996   return Val;
997 }
998
999 // Return true if SDValue exists for the given Value
1000 bool SelectionDAGBuilder::findValue(const Value *V) const {
1001   return (NodeMap.find(V) != NodeMap.end()) ||
1002     (FuncInfo.ValueMap.find(V) != FuncInfo.ValueMap.end());
1003 }
1004
1005 /// getNonRegisterValue - Return an SDValue for the given Value, but
1006 /// don't look in FuncInfo.ValueMap for a virtual register.
1007 SDValue SelectionDAGBuilder::getNonRegisterValue(const Value *V) {
1008   // If we already have an SDValue for this value, use it.
1009   SDValue &N = NodeMap[V];
1010   if (N.getNode()) {
1011     if (isa<ConstantSDNode>(N) || isa<ConstantFPSDNode>(N)) {
1012       // Remove the debug location from the node as the node is about to be used
1013       // in a location which may differ from the original debug location.  This
1014       // is relevant to Constant and ConstantFP nodes because they can appear
1015       // as constant expressions inside PHI nodes.
1016       N->setDebugLoc(DebugLoc());
1017     }
1018     return N;
1019   }
1020
1021   // Otherwise create a new SDValue and remember it.
1022   SDValue Val = getValueImpl(V);
1023   NodeMap[V] = Val;
1024   resolveDanglingDebugInfo(V, Val);
1025   return Val;
1026 }
1027
1028 /// getValueImpl - Helper function for getValue and getNonRegisterValue.
1029 /// Create an SDValue for the given value.
1030 SDValue SelectionDAGBuilder::getValueImpl(const Value *V) {
1031   const TargetLowering &TLI = DAG.getTargetLoweringInfo();
1032
1033   if (const Constant *C = dyn_cast<Constant>(V)) {
1034     EVT VT = TLI.getValueType(V->getType(), true);
1035
1036     if (const ConstantInt *CI = dyn_cast<ConstantInt>(C))
1037       return DAG.getConstant(*CI, getCurSDLoc(), VT);
1038
1039     if (const GlobalValue *GV = dyn_cast<GlobalValue>(C))
1040       return DAG.getGlobalAddress(GV, getCurSDLoc(), VT);
1041
1042     if (isa<ConstantPointerNull>(C)) {
1043       unsigned AS = V->getType()->getPointerAddressSpace();
1044       return DAG.getConstant(0, getCurSDLoc(), TLI.getPointerTy(AS));
1045     }
1046
1047     if (const ConstantFP *CFP = dyn_cast<ConstantFP>(C))
1048       return DAG.getConstantFP(*CFP, getCurSDLoc(), VT);
1049
1050     if (isa<UndefValue>(C) && !V->getType()->isAggregateType())
1051       return DAG.getUNDEF(VT);
1052
1053     if (const ConstantExpr *CE = dyn_cast<ConstantExpr>(C)) {
1054       visit(CE->getOpcode(), *CE);
1055       SDValue N1 = NodeMap[V];
1056       assert(N1.getNode() && "visit didn't populate the NodeMap!");
1057       return N1;
1058     }
1059
1060     if (isa<ConstantStruct>(C) || isa<ConstantArray>(C)) {
1061       SmallVector<SDValue, 4> Constants;
1062       for (User::const_op_iterator OI = C->op_begin(), OE = C->op_end();
1063            OI != OE; ++OI) {
1064         SDNode *Val = getValue(*OI).getNode();
1065         // If the operand is an empty aggregate, there are no values.
1066         if (!Val) continue;
1067         // Add each leaf value from the operand to the Constants list
1068         // to form a flattened list of all the values.
1069         for (unsigned i = 0, e = Val->getNumValues(); i != e; ++i)
1070           Constants.push_back(SDValue(Val, i));
1071       }
1072
1073       return DAG.getMergeValues(Constants, getCurSDLoc());
1074     }
1075
1076     if (const ConstantDataSequential *CDS =
1077           dyn_cast<ConstantDataSequential>(C)) {
1078       SmallVector<SDValue, 4> Ops;
1079       for (unsigned i = 0, e = CDS->getNumElements(); i != e; ++i) {
1080         SDNode *Val = getValue(CDS->getElementAsConstant(i)).getNode();
1081         // Add each leaf value from the operand to the Constants list
1082         // to form a flattened list of all the values.
1083         for (unsigned i = 0, e = Val->getNumValues(); i != e; ++i)
1084           Ops.push_back(SDValue(Val, i));
1085       }
1086
1087       if (isa<ArrayType>(CDS->getType()))
1088         return DAG.getMergeValues(Ops, getCurSDLoc());
1089       return NodeMap[V] = DAG.getNode(ISD::BUILD_VECTOR, getCurSDLoc(),
1090                                       VT, Ops);
1091     }
1092
1093     if (C->getType()->isStructTy() || C->getType()->isArrayTy()) {
1094       assert((isa<ConstantAggregateZero>(C) || isa<UndefValue>(C)) &&
1095              "Unknown struct or array constant!");
1096
1097       SmallVector<EVT, 4> ValueVTs;
1098       ComputeValueVTs(TLI, C->getType(), ValueVTs);
1099       unsigned NumElts = ValueVTs.size();
1100       if (NumElts == 0)
1101         return SDValue(); // empty struct
1102       SmallVector<SDValue, 4> Constants(NumElts);
1103       for (unsigned i = 0; i != NumElts; ++i) {
1104         EVT EltVT = ValueVTs[i];
1105         if (isa<UndefValue>(C))
1106           Constants[i] = DAG.getUNDEF(EltVT);
1107         else if (EltVT.isFloatingPoint())
1108           Constants[i] = DAG.getConstantFP(0, getCurSDLoc(), EltVT);
1109         else
1110           Constants[i] = DAG.getConstant(0, getCurSDLoc(), EltVT);
1111       }
1112
1113       return DAG.getMergeValues(Constants, getCurSDLoc());
1114     }
1115
1116     if (const BlockAddress *BA = dyn_cast<BlockAddress>(C))
1117       return DAG.getBlockAddress(BA, VT);
1118
1119     VectorType *VecTy = cast<VectorType>(V->getType());
1120     unsigned NumElements = VecTy->getNumElements();
1121
1122     // Now that we know the number and type of the elements, get that number of
1123     // elements into the Ops array based on what kind of constant it is.
1124     SmallVector<SDValue, 16> Ops;
1125     if (const ConstantVector *CV = dyn_cast<ConstantVector>(C)) {
1126       for (unsigned i = 0; i != NumElements; ++i)
1127         Ops.push_back(getValue(CV->getOperand(i)));
1128     } else {
1129       assert(isa<ConstantAggregateZero>(C) && "Unknown vector constant!");
1130       EVT EltVT = TLI.getValueType(VecTy->getElementType());
1131
1132       SDValue Op;
1133       if (EltVT.isFloatingPoint())
1134         Op = DAG.getConstantFP(0, getCurSDLoc(), EltVT);
1135       else
1136         Op = DAG.getConstant(0, getCurSDLoc(), EltVT);
1137       Ops.assign(NumElements, Op);
1138     }
1139
1140     // Create a BUILD_VECTOR node.
1141     return NodeMap[V] = DAG.getNode(ISD::BUILD_VECTOR, getCurSDLoc(), VT, Ops);
1142   }
1143
1144   // If this is a static alloca, generate it as the frameindex instead of
1145   // computation.
1146   if (const AllocaInst *AI = dyn_cast<AllocaInst>(V)) {
1147     DenseMap<const AllocaInst*, int>::iterator SI =
1148       FuncInfo.StaticAllocaMap.find(AI);
1149     if (SI != FuncInfo.StaticAllocaMap.end())
1150       return DAG.getFrameIndex(SI->second, TLI.getPointerTy());
1151   }
1152
1153   // If this is an instruction which fast-isel has deferred, select it now.
1154   if (const Instruction *Inst = dyn_cast<Instruction>(V)) {
1155     unsigned InReg = FuncInfo.InitializeRegForValue(Inst);
1156     RegsForValue RFV(*DAG.getContext(), TLI, InReg, Inst->getType());
1157     SDValue Chain = DAG.getEntryNode();
1158     return RFV.getCopyFromRegs(DAG, FuncInfo, getCurSDLoc(), Chain, nullptr, V);
1159   }
1160
1161   llvm_unreachable("Can't get register for value!");
1162 }
1163
1164 void SelectionDAGBuilder::visitRet(const ReturnInst &I) {
1165   const TargetLowering &TLI = DAG.getTargetLoweringInfo();
1166   SDValue Chain = getControlRoot();
1167   SmallVector<ISD::OutputArg, 8> Outs;
1168   SmallVector<SDValue, 8> OutVals;
1169
1170   if (!FuncInfo.CanLowerReturn) {
1171     unsigned DemoteReg = FuncInfo.DemoteRegister;
1172     const Function *F = I.getParent()->getParent();
1173
1174     // Emit a store of the return value through the virtual register.
1175     // Leave Outs empty so that LowerReturn won't try to load return
1176     // registers the usual way.
1177     SmallVector<EVT, 1> PtrValueVTs;
1178     ComputeValueVTs(TLI, PointerType::getUnqual(F->getReturnType()),
1179                     PtrValueVTs);
1180
1181     SDValue RetPtr = DAG.getRegister(DemoteReg, PtrValueVTs[0]);
1182     SDValue RetOp = getValue(I.getOperand(0));
1183
1184     SmallVector<EVT, 4> ValueVTs;
1185     SmallVector<uint64_t, 4> Offsets;
1186     ComputeValueVTs(TLI, I.getOperand(0)->getType(), ValueVTs, &Offsets);
1187     unsigned NumValues = ValueVTs.size();
1188
1189     SmallVector<SDValue, 4> Chains(NumValues);
1190     for (unsigned i = 0; i != NumValues; ++i) {
1191       SDValue Add = DAG.getNode(ISD::ADD, getCurSDLoc(),
1192                                 RetPtr.getValueType(), RetPtr,
1193                                 DAG.getIntPtrConstant(Offsets[i],
1194                                                       getCurSDLoc()));
1195       Chains[i] =
1196         DAG.getStore(Chain, getCurSDLoc(),
1197                      SDValue(RetOp.getNode(), RetOp.getResNo() + i),
1198                      // FIXME: better loc info would be nice.
1199                      Add, MachinePointerInfo(), false, false, 0);
1200     }
1201
1202     Chain = DAG.getNode(ISD::TokenFactor, getCurSDLoc(),
1203                         MVT::Other, Chains);
1204   } else if (I.getNumOperands() != 0) {
1205     SmallVector<EVT, 4> ValueVTs;
1206     ComputeValueVTs(TLI, I.getOperand(0)->getType(), ValueVTs);
1207     unsigned NumValues = ValueVTs.size();
1208     if (NumValues) {
1209       SDValue RetOp = getValue(I.getOperand(0));
1210
1211       const Function *F = I.getParent()->getParent();
1212
1213       ISD::NodeType ExtendKind = ISD::ANY_EXTEND;
1214       if (F->getAttributes().hasAttribute(AttributeSet::ReturnIndex,
1215                                           Attribute::SExt))
1216         ExtendKind = ISD::SIGN_EXTEND;
1217       else if (F->getAttributes().hasAttribute(AttributeSet::ReturnIndex,
1218                                                Attribute::ZExt))
1219         ExtendKind = ISD::ZERO_EXTEND;
1220
1221       LLVMContext &Context = F->getContext();
1222       bool RetInReg = F->getAttributes().hasAttribute(AttributeSet::ReturnIndex,
1223                                                       Attribute::InReg);
1224
1225       for (unsigned j = 0; j != NumValues; ++j) {
1226         EVT VT = ValueVTs[j];
1227
1228         if (ExtendKind != ISD::ANY_EXTEND && VT.isInteger())
1229           VT = TLI.getTypeForExtArgOrReturn(Context, VT, ExtendKind);
1230
1231         unsigned NumParts = TLI.getNumRegisters(Context, VT);
1232         MVT PartVT = TLI.getRegisterType(Context, VT);
1233         SmallVector<SDValue, 4> Parts(NumParts);
1234         getCopyToParts(DAG, getCurSDLoc(),
1235                        SDValue(RetOp.getNode(), RetOp.getResNo() + j),
1236                        &Parts[0], NumParts, PartVT, &I, ExtendKind);
1237
1238         // 'inreg' on function refers to return value
1239         ISD::ArgFlagsTy Flags = ISD::ArgFlagsTy();
1240         if (RetInReg)
1241           Flags.setInReg();
1242
1243         // Propagate extension type if any
1244         if (ExtendKind == ISD::SIGN_EXTEND)
1245           Flags.setSExt();
1246         else if (ExtendKind == ISD::ZERO_EXTEND)
1247           Flags.setZExt();
1248
1249         for (unsigned i = 0; i < NumParts; ++i) {
1250           Outs.push_back(ISD::OutputArg(Flags, Parts[i].getValueType(),
1251                                         VT, /*isfixed=*/true, 0, 0));
1252           OutVals.push_back(Parts[i]);
1253         }
1254       }
1255     }
1256   }
1257
1258   bool isVarArg = DAG.getMachineFunction().getFunction()->isVarArg();
1259   CallingConv::ID CallConv =
1260     DAG.getMachineFunction().getFunction()->getCallingConv();
1261   Chain = DAG.getTargetLoweringInfo().LowerReturn(
1262       Chain, CallConv, isVarArg, Outs, OutVals, getCurSDLoc(), DAG);
1263
1264   // Verify that the target's LowerReturn behaved as expected.
1265   assert(Chain.getNode() && Chain.getValueType() == MVT::Other &&
1266          "LowerReturn didn't return a valid chain!");
1267
1268   // Update the DAG with the new chain value resulting from return lowering.
1269   DAG.setRoot(Chain);
1270 }
1271
1272 /// CopyToExportRegsIfNeeded - If the given value has virtual registers
1273 /// created for it, emit nodes to copy the value into the virtual
1274 /// registers.
1275 void SelectionDAGBuilder::CopyToExportRegsIfNeeded(const Value *V) {
1276   // Skip empty types
1277   if (V->getType()->isEmptyTy())
1278     return;
1279
1280   DenseMap<const Value *, unsigned>::iterator VMI = FuncInfo.ValueMap.find(V);
1281   if (VMI != FuncInfo.ValueMap.end()) {
1282     assert(!V->use_empty() && "Unused value assigned virtual registers!");
1283     CopyValueToVirtualRegister(V, VMI->second);
1284   }
1285 }
1286
1287 /// ExportFromCurrentBlock - If this condition isn't known to be exported from
1288 /// the current basic block, add it to ValueMap now so that we'll get a
1289 /// CopyTo/FromReg.
1290 void SelectionDAGBuilder::ExportFromCurrentBlock(const Value *V) {
1291   // No need to export constants.
1292   if (!isa<Instruction>(V) && !isa<Argument>(V)) return;
1293
1294   // Already exported?
1295   if (FuncInfo.isExportedInst(V)) return;
1296
1297   unsigned Reg = FuncInfo.InitializeRegForValue(V);
1298   CopyValueToVirtualRegister(V, Reg);
1299 }
1300
1301 bool SelectionDAGBuilder::isExportableFromCurrentBlock(const Value *V,
1302                                                      const BasicBlock *FromBB) {
1303   // The operands of the setcc have to be in this block.  We don't know
1304   // how to export them from some other block.
1305   if (const Instruction *VI = dyn_cast<Instruction>(V)) {
1306     // Can export from current BB.
1307     if (VI->getParent() == FromBB)
1308       return true;
1309
1310     // Is already exported, noop.
1311     return FuncInfo.isExportedInst(V);
1312   }
1313
1314   // If this is an argument, we can export it if the BB is the entry block or
1315   // if it is already exported.
1316   if (isa<Argument>(V)) {
1317     if (FromBB == &FromBB->getParent()->getEntryBlock())
1318       return true;
1319
1320     // Otherwise, can only export this if it is already exported.
1321     return FuncInfo.isExportedInst(V);
1322   }
1323
1324   // Otherwise, constants can always be exported.
1325   return true;
1326 }
1327
1328 /// Return branch probability calculated by BranchProbabilityInfo for IR blocks.
1329 uint32_t SelectionDAGBuilder::getEdgeWeight(const MachineBasicBlock *Src,
1330                                             const MachineBasicBlock *Dst) const {
1331   BranchProbabilityInfo *BPI = FuncInfo.BPI;
1332   if (!BPI)
1333     return 0;
1334   const BasicBlock *SrcBB = Src->getBasicBlock();
1335   const BasicBlock *DstBB = Dst->getBasicBlock();
1336   return BPI->getEdgeWeight(SrcBB, DstBB);
1337 }
1338
1339 void SelectionDAGBuilder::
1340 addSuccessorWithWeight(MachineBasicBlock *Src, MachineBasicBlock *Dst,
1341                        uint32_t Weight /* = 0 */) {
1342   if (!Weight)
1343     Weight = getEdgeWeight(Src, Dst);
1344   Src->addSuccessor(Dst, Weight);
1345 }
1346
1347
1348 static bool InBlock(const Value *V, const BasicBlock *BB) {
1349   if (const Instruction *I = dyn_cast<Instruction>(V))
1350     return I->getParent() == BB;
1351   return true;
1352 }
1353
1354 /// EmitBranchForMergedCondition - Helper method for FindMergedConditions.
1355 /// This function emits a branch and is used at the leaves of an OR or an
1356 /// AND operator tree.
1357 ///
1358 void
1359 SelectionDAGBuilder::EmitBranchForMergedCondition(const Value *Cond,
1360                                                   MachineBasicBlock *TBB,
1361                                                   MachineBasicBlock *FBB,
1362                                                   MachineBasicBlock *CurBB,
1363                                                   MachineBasicBlock *SwitchBB,
1364                                                   uint32_t TWeight,
1365                                                   uint32_t FWeight) {
1366   const BasicBlock *BB = CurBB->getBasicBlock();
1367
1368   // If the leaf of the tree is a comparison, merge the condition into
1369   // the caseblock.
1370   if (const CmpInst *BOp = dyn_cast<CmpInst>(Cond)) {
1371     // The operands of the cmp have to be in this block.  We don't know
1372     // how to export them from some other block.  If this is the first block
1373     // of the sequence, no exporting is needed.
1374     if (CurBB == SwitchBB ||
1375         (isExportableFromCurrentBlock(BOp->getOperand(0), BB) &&
1376          isExportableFromCurrentBlock(BOp->getOperand(1), BB))) {
1377       ISD::CondCode Condition;
1378       if (const ICmpInst *IC = dyn_cast<ICmpInst>(Cond)) {
1379         Condition = getICmpCondCode(IC->getPredicate());
1380       } else if (const FCmpInst *FC = dyn_cast<FCmpInst>(Cond)) {
1381         Condition = getFCmpCondCode(FC->getPredicate());
1382         if (TM.Options.NoNaNsFPMath)
1383           Condition = getFCmpCodeWithoutNaN(Condition);
1384       } else {
1385         (void)Condition; // silence warning.
1386         llvm_unreachable("Unknown compare instruction");
1387       }
1388
1389       CaseBlock CB(Condition, BOp->getOperand(0), BOp->getOperand(1), nullptr,
1390                    TBB, FBB, CurBB, TWeight, FWeight);
1391       SwitchCases.push_back(CB);
1392       return;
1393     }
1394   }
1395
1396   // Create a CaseBlock record representing this branch.
1397   CaseBlock CB(ISD::SETEQ, Cond, ConstantInt::getTrue(*DAG.getContext()),
1398                nullptr, TBB, FBB, CurBB, TWeight, FWeight);
1399   SwitchCases.push_back(CB);
1400 }
1401
1402 /// Scale down both weights to fit into uint32_t.
1403 static void ScaleWeights(uint64_t &NewTrue, uint64_t &NewFalse) {
1404   uint64_t NewMax = (NewTrue > NewFalse) ? NewTrue : NewFalse;
1405   uint32_t Scale = (NewMax / UINT32_MAX) + 1;
1406   NewTrue = NewTrue / Scale;
1407   NewFalse = NewFalse / Scale;
1408 }
1409
1410 /// FindMergedConditions - If Cond is an expression like
1411 void SelectionDAGBuilder::FindMergedConditions(const Value *Cond,
1412                                                MachineBasicBlock *TBB,
1413                                                MachineBasicBlock *FBB,
1414                                                MachineBasicBlock *CurBB,
1415                                                MachineBasicBlock *SwitchBB,
1416                                                unsigned Opc, uint32_t TWeight,
1417                                                uint32_t FWeight) {
1418   // If this node is not part of the or/and tree, emit it as a branch.
1419   const Instruction *BOp = dyn_cast<Instruction>(Cond);
1420   if (!BOp || !(isa<BinaryOperator>(BOp) || isa<CmpInst>(BOp)) ||
1421       (unsigned)BOp->getOpcode() != Opc || !BOp->hasOneUse() ||
1422       BOp->getParent() != CurBB->getBasicBlock() ||
1423       !InBlock(BOp->getOperand(0), CurBB->getBasicBlock()) ||
1424       !InBlock(BOp->getOperand(1), CurBB->getBasicBlock())) {
1425     EmitBranchForMergedCondition(Cond, TBB, FBB, CurBB, SwitchBB,
1426                                  TWeight, FWeight);
1427     return;
1428   }
1429
1430   //  Create TmpBB after CurBB.
1431   MachineFunction::iterator BBI = CurBB;
1432   MachineFunction &MF = DAG.getMachineFunction();
1433   MachineBasicBlock *TmpBB = MF.CreateMachineBasicBlock(CurBB->getBasicBlock());
1434   CurBB->getParent()->insert(++BBI, TmpBB);
1435
1436   if (Opc == Instruction::Or) {
1437     // Codegen X | Y as:
1438     // BB1:
1439     //   jmp_if_X TBB
1440     //   jmp TmpBB
1441     // TmpBB:
1442     //   jmp_if_Y TBB
1443     //   jmp FBB
1444     //
1445
1446     // We have flexibility in setting Prob for BB1 and Prob for TmpBB.
1447     // The requirement is that
1448     //   TrueProb for BB1 + (FalseProb for BB1 * TrueProb for TmpBB)
1449     //     = TrueProb for original BB.
1450     // Assuming the original weights are A and B, one choice is to set BB1's
1451     // weights to A and A+2B, and set TmpBB's weights to A and 2B. This choice
1452     // assumes that
1453     //   TrueProb for BB1 == FalseProb for BB1 * TrueProb for TmpBB.
1454     // Another choice is to assume TrueProb for BB1 equals to TrueProb for
1455     // TmpBB, but the math is more complicated.
1456
1457     uint64_t NewTrueWeight = TWeight;
1458     uint64_t NewFalseWeight = (uint64_t)TWeight + 2 * (uint64_t)FWeight;
1459     ScaleWeights(NewTrueWeight, NewFalseWeight);
1460     // Emit the LHS condition.
1461     FindMergedConditions(BOp->getOperand(0), TBB, TmpBB, CurBB, SwitchBB, Opc,
1462                          NewTrueWeight, NewFalseWeight);
1463
1464     NewTrueWeight = TWeight;
1465     NewFalseWeight = 2 * (uint64_t)FWeight;
1466     ScaleWeights(NewTrueWeight, NewFalseWeight);
1467     // Emit the RHS condition into TmpBB.
1468     FindMergedConditions(BOp->getOperand(1), TBB, FBB, TmpBB, SwitchBB, Opc,
1469                          NewTrueWeight, NewFalseWeight);
1470   } else {
1471     assert(Opc == Instruction::And && "Unknown merge op!");
1472     // Codegen X & Y as:
1473     // BB1:
1474     //   jmp_if_X TmpBB
1475     //   jmp FBB
1476     // TmpBB:
1477     //   jmp_if_Y TBB
1478     //   jmp FBB
1479     //
1480     //  This requires creation of TmpBB after CurBB.
1481
1482     // We have flexibility in setting Prob for BB1 and Prob for TmpBB.
1483     // The requirement is that
1484     //   FalseProb for BB1 + (TrueProb for BB1 * FalseProb for TmpBB)
1485     //     = FalseProb for original BB.
1486     // Assuming the original weights are A and B, one choice is to set BB1's
1487     // weights to 2A+B and B, and set TmpBB's weights to 2A and B. This choice
1488     // assumes that
1489     //   FalseProb for BB1 == TrueProb for BB1 * FalseProb for TmpBB.
1490
1491     uint64_t NewTrueWeight = 2 * (uint64_t)TWeight + (uint64_t)FWeight;
1492     uint64_t NewFalseWeight = FWeight;
1493     ScaleWeights(NewTrueWeight, NewFalseWeight);
1494     // Emit the LHS condition.
1495     FindMergedConditions(BOp->getOperand(0), TmpBB, FBB, CurBB, SwitchBB, Opc,
1496                          NewTrueWeight, NewFalseWeight);
1497
1498     NewTrueWeight = 2 * (uint64_t)TWeight;
1499     NewFalseWeight = FWeight;
1500     ScaleWeights(NewTrueWeight, NewFalseWeight);
1501     // Emit the RHS condition into TmpBB.
1502     FindMergedConditions(BOp->getOperand(1), TBB, FBB, TmpBB, SwitchBB, Opc,
1503                          NewTrueWeight, NewFalseWeight);
1504   }
1505 }
1506
1507 /// If the set of cases should be emitted as a series of branches, return true.
1508 /// If we should emit this as a bunch of and/or'd together conditions, return
1509 /// false.
1510 bool
1511 SelectionDAGBuilder::ShouldEmitAsBranches(const std::vector<CaseBlock> &Cases) {
1512   if (Cases.size() != 2) return true;
1513
1514   // If this is two comparisons of the same values or'd or and'd together, they
1515   // will get folded into a single comparison, so don't emit two blocks.
1516   if ((Cases[0].CmpLHS == Cases[1].CmpLHS &&
1517        Cases[0].CmpRHS == Cases[1].CmpRHS) ||
1518       (Cases[0].CmpRHS == Cases[1].CmpLHS &&
1519        Cases[0].CmpLHS == Cases[1].CmpRHS)) {
1520     return false;
1521   }
1522
1523   // Handle: (X != null) | (Y != null) --> (X|Y) != 0
1524   // Handle: (X == null) & (Y == null) --> (X|Y) == 0
1525   if (Cases[0].CmpRHS == Cases[1].CmpRHS &&
1526       Cases[0].CC == Cases[1].CC &&
1527       isa<Constant>(Cases[0].CmpRHS) &&
1528       cast<Constant>(Cases[0].CmpRHS)->isNullValue()) {
1529     if (Cases[0].CC == ISD::SETEQ && Cases[0].TrueBB == Cases[1].ThisBB)
1530       return false;
1531     if (Cases[0].CC == ISD::SETNE && Cases[0].FalseBB == Cases[1].ThisBB)
1532       return false;
1533   }
1534
1535   return true;
1536 }
1537
1538 void SelectionDAGBuilder::visitBr(const BranchInst &I) {
1539   MachineBasicBlock *BrMBB = FuncInfo.MBB;
1540
1541   // Update machine-CFG edges.
1542   MachineBasicBlock *Succ0MBB = FuncInfo.MBBMap[I.getSuccessor(0)];
1543
1544   if (I.isUnconditional()) {
1545     // Update machine-CFG edges.
1546     BrMBB->addSuccessor(Succ0MBB);
1547
1548     // If this is not a fall-through branch or optimizations are switched off,
1549     // emit the branch.
1550     if (Succ0MBB != NextBlock(BrMBB) || TM.getOptLevel() == CodeGenOpt::None)
1551       DAG.setRoot(DAG.getNode(ISD::BR, getCurSDLoc(),
1552                               MVT::Other, getControlRoot(),
1553                               DAG.getBasicBlock(Succ0MBB)));
1554
1555     return;
1556   }
1557
1558   // If this condition is one of the special cases we handle, do special stuff
1559   // now.
1560   const Value *CondVal = I.getCondition();
1561   MachineBasicBlock *Succ1MBB = FuncInfo.MBBMap[I.getSuccessor(1)];
1562
1563   // If this is a series of conditions that are or'd or and'd together, emit
1564   // this as a sequence of branches instead of setcc's with and/or operations.
1565   // As long as jumps are not expensive, this should improve performance.
1566   // For example, instead of something like:
1567   //     cmp A, B
1568   //     C = seteq
1569   //     cmp D, E
1570   //     F = setle
1571   //     or C, F
1572   //     jnz foo
1573   // Emit:
1574   //     cmp A, B
1575   //     je foo
1576   //     cmp D, E
1577   //     jle foo
1578   //
1579   if (const BinaryOperator *BOp = dyn_cast<BinaryOperator>(CondVal)) {
1580     if (!DAG.getTargetLoweringInfo().isJumpExpensive() &&
1581         BOp->hasOneUse() && (BOp->getOpcode() == Instruction::And ||
1582                              BOp->getOpcode() == Instruction::Or)) {
1583       FindMergedConditions(BOp, Succ0MBB, Succ1MBB, BrMBB, BrMBB,
1584                            BOp->getOpcode(), getEdgeWeight(BrMBB, Succ0MBB),
1585                            getEdgeWeight(BrMBB, Succ1MBB));
1586       // If the compares in later blocks need to use values not currently
1587       // exported from this block, export them now.  This block should always
1588       // be the first entry.
1589       assert(SwitchCases[0].ThisBB == BrMBB && "Unexpected lowering!");
1590
1591       // Allow some cases to be rejected.
1592       if (ShouldEmitAsBranches(SwitchCases)) {
1593         for (unsigned i = 1, e = SwitchCases.size(); i != e; ++i) {
1594           ExportFromCurrentBlock(SwitchCases[i].CmpLHS);
1595           ExportFromCurrentBlock(SwitchCases[i].CmpRHS);
1596         }
1597
1598         // Emit the branch for this block.
1599         visitSwitchCase(SwitchCases[0], BrMBB);
1600         SwitchCases.erase(SwitchCases.begin());
1601         return;
1602       }
1603
1604       // Okay, we decided not to do this, remove any inserted MBB's and clear
1605       // SwitchCases.
1606       for (unsigned i = 1, e = SwitchCases.size(); i != e; ++i)
1607         FuncInfo.MF->erase(SwitchCases[i].ThisBB);
1608
1609       SwitchCases.clear();
1610     }
1611   }
1612
1613   // Create a CaseBlock record representing this branch.
1614   CaseBlock CB(ISD::SETEQ, CondVal, ConstantInt::getTrue(*DAG.getContext()),
1615                nullptr, Succ0MBB, Succ1MBB, BrMBB);
1616
1617   // Use visitSwitchCase to actually insert the fast branch sequence for this
1618   // cond branch.
1619   visitSwitchCase(CB, BrMBB);
1620 }
1621
1622 /// visitSwitchCase - Emits the necessary code to represent a single node in
1623 /// the binary search tree resulting from lowering a switch instruction.
1624 void SelectionDAGBuilder::visitSwitchCase(CaseBlock &CB,
1625                                           MachineBasicBlock *SwitchBB) {
1626   SDValue Cond;
1627   SDValue CondLHS = getValue(CB.CmpLHS);
1628   SDLoc dl = getCurSDLoc();
1629
1630   // Build the setcc now.
1631   if (!CB.CmpMHS) {
1632     // Fold "(X == true)" to X and "(X == false)" to !X to
1633     // handle common cases produced by branch lowering.
1634     if (CB.CmpRHS == ConstantInt::getTrue(*DAG.getContext()) &&
1635         CB.CC == ISD::SETEQ)
1636       Cond = CondLHS;
1637     else if (CB.CmpRHS == ConstantInt::getFalse(*DAG.getContext()) &&
1638              CB.CC == ISD::SETEQ) {
1639       SDValue True = DAG.getConstant(1, dl, CondLHS.getValueType());
1640       Cond = DAG.getNode(ISD::XOR, dl, CondLHS.getValueType(), CondLHS, True);
1641     } else
1642       Cond = DAG.getSetCC(dl, MVT::i1, CondLHS, getValue(CB.CmpRHS), CB.CC);
1643   } else {
1644     assert(CB.CC == ISD::SETLE && "Can handle only LE ranges now");
1645
1646     const APInt& Low = cast<ConstantInt>(CB.CmpLHS)->getValue();
1647     const APInt& High = cast<ConstantInt>(CB.CmpRHS)->getValue();
1648
1649     SDValue CmpOp = getValue(CB.CmpMHS);
1650     EVT VT = CmpOp.getValueType();
1651
1652     if (cast<ConstantInt>(CB.CmpLHS)->isMinValue(true)) {
1653       Cond = DAG.getSetCC(dl, MVT::i1, CmpOp, DAG.getConstant(High, dl, VT),
1654                           ISD::SETLE);
1655     } else {
1656       SDValue SUB = DAG.getNode(ISD::SUB, dl,
1657                                 VT, CmpOp, DAG.getConstant(Low, dl, VT));
1658       Cond = DAG.getSetCC(dl, MVT::i1, SUB,
1659                           DAG.getConstant(High-Low, dl, VT), ISD::SETULE);
1660     }
1661   }
1662
1663   // Update successor info
1664   addSuccessorWithWeight(SwitchBB, CB.TrueBB, CB.TrueWeight);
1665   // TrueBB and FalseBB are always different unless the incoming IR is
1666   // degenerate. This only happens when running llc on weird IR.
1667   if (CB.TrueBB != CB.FalseBB)
1668     addSuccessorWithWeight(SwitchBB, CB.FalseBB, CB.FalseWeight);
1669
1670   // If the lhs block is the next block, invert the condition so that we can
1671   // fall through to the lhs instead of the rhs block.
1672   if (CB.TrueBB == NextBlock(SwitchBB)) {
1673     std::swap(CB.TrueBB, CB.FalseBB);
1674     SDValue True = DAG.getConstant(1, dl, Cond.getValueType());
1675     Cond = DAG.getNode(ISD::XOR, dl, Cond.getValueType(), Cond, True);
1676   }
1677
1678   SDValue BrCond = DAG.getNode(ISD::BRCOND, dl,
1679                                MVT::Other, getControlRoot(), Cond,
1680                                DAG.getBasicBlock(CB.TrueBB));
1681
1682   // Insert the false branch. Do this even if it's a fall through branch,
1683   // this makes it easier to do DAG optimizations which require inverting
1684   // the branch condition.
1685   BrCond = DAG.getNode(ISD::BR, dl, MVT::Other, BrCond,
1686                        DAG.getBasicBlock(CB.FalseBB));
1687
1688   DAG.setRoot(BrCond);
1689 }
1690
1691 /// visitJumpTable - Emit JumpTable node in the current MBB
1692 void SelectionDAGBuilder::visitJumpTable(JumpTable &JT) {
1693   // Emit the code for the jump table
1694   assert(JT.Reg != -1U && "Should lower JT Header first!");
1695   EVT PTy = DAG.getTargetLoweringInfo().getPointerTy();
1696   SDValue Index = DAG.getCopyFromReg(getControlRoot(), getCurSDLoc(),
1697                                      JT.Reg, PTy);
1698   SDValue Table = DAG.getJumpTable(JT.JTI, PTy);
1699   SDValue BrJumpTable = DAG.getNode(ISD::BR_JT, getCurSDLoc(),
1700                                     MVT::Other, Index.getValue(1),
1701                                     Table, Index);
1702   DAG.setRoot(BrJumpTable);
1703 }
1704
1705 /// visitJumpTableHeader - This function emits necessary code to produce index
1706 /// in the JumpTable from switch case.
1707 void SelectionDAGBuilder::visitJumpTableHeader(JumpTable &JT,
1708                                                JumpTableHeader &JTH,
1709                                                MachineBasicBlock *SwitchBB) {
1710   SDLoc dl = getCurSDLoc();
1711
1712   // Subtract the lowest switch case value from the value being switched on and
1713   // conditional branch to default mbb if the result is greater than the
1714   // difference between smallest and largest cases.
1715   SDValue SwitchOp = getValue(JTH.SValue);
1716   EVT VT = SwitchOp.getValueType();
1717   SDValue Sub = DAG.getNode(ISD::SUB, dl, VT, SwitchOp,
1718                             DAG.getConstant(JTH.First, dl, VT));
1719
1720   // The SDNode we just created, which holds the value being switched on minus
1721   // the smallest case value, needs to be copied to a virtual register so it
1722   // can be used as an index into the jump table in a subsequent basic block.
1723   // This value may be smaller or larger than the target's pointer type, and
1724   // therefore require extension or truncating.
1725   const TargetLowering &TLI = DAG.getTargetLoweringInfo();
1726   SwitchOp = DAG.getZExtOrTrunc(Sub, dl, TLI.getPointerTy());
1727
1728   unsigned JumpTableReg = FuncInfo.CreateReg(TLI.getPointerTy());
1729   SDValue CopyTo = DAG.getCopyToReg(getControlRoot(), dl,
1730                                     JumpTableReg, SwitchOp);
1731   JT.Reg = JumpTableReg;
1732
1733   // Emit the range check for the jump table, and branch to the default block
1734   // for the switch statement if the value being switched on exceeds the largest
1735   // case in the switch.
1736   SDValue CMP =
1737       DAG.getSetCC(dl, TLI.getSetCCResultType(*DAG.getContext(),
1738                                               Sub.getValueType()),
1739                    Sub, DAG.getConstant(JTH.Last - JTH.First, dl, VT),
1740                    ISD::SETUGT);
1741
1742   SDValue BrCond = DAG.getNode(ISD::BRCOND, dl,
1743                                MVT::Other, CopyTo, CMP,
1744                                DAG.getBasicBlock(JT.Default));
1745
1746   // Avoid emitting unnecessary branches to the next block.
1747   if (JT.MBB != NextBlock(SwitchBB))
1748     BrCond = DAG.getNode(ISD::BR, dl, MVT::Other, BrCond,
1749                          DAG.getBasicBlock(JT.MBB));
1750
1751   DAG.setRoot(BrCond);
1752 }
1753
1754 /// Codegen a new tail for a stack protector check ParentMBB which has had its
1755 /// tail spliced into a stack protector check success bb.
1756 ///
1757 /// For a high level explanation of how this fits into the stack protector
1758 /// generation see the comment on the declaration of class
1759 /// StackProtectorDescriptor.
1760 void SelectionDAGBuilder::visitSPDescriptorParent(StackProtectorDescriptor &SPD,
1761                                                   MachineBasicBlock *ParentBB) {
1762
1763   // First create the loads to the guard/stack slot for the comparison.
1764   const TargetLowering &TLI = DAG.getTargetLoweringInfo();
1765   EVT PtrTy = TLI.getPointerTy();
1766
1767   MachineFrameInfo *MFI = ParentBB->getParent()->getFrameInfo();
1768   int FI = MFI->getStackProtectorIndex();
1769
1770   const Value *IRGuard = SPD.getGuard();
1771   SDValue GuardPtr = getValue(IRGuard);
1772   SDValue StackSlotPtr = DAG.getFrameIndex(FI, PtrTy);
1773
1774   unsigned Align = DL->getPrefTypeAlignment(IRGuard->getType());
1775
1776   SDValue Guard;
1777   SDLoc dl = getCurSDLoc();
1778
1779   // If GuardReg is set and useLoadStackGuardNode returns true, retrieve the
1780   // guard value from the virtual register holding the value. Otherwise, emit a
1781   // volatile load to retrieve the stack guard value.
1782   unsigned GuardReg = SPD.getGuardReg();
1783
1784   if (GuardReg && TLI.useLoadStackGuardNode())
1785     Guard = DAG.getCopyFromReg(DAG.getEntryNode(), dl, GuardReg,
1786                                PtrTy);
1787   else
1788     Guard = DAG.getLoad(PtrTy, dl, DAG.getEntryNode(),
1789                         GuardPtr, MachinePointerInfo(IRGuard, 0),
1790                         true, false, false, Align);
1791
1792   SDValue StackSlot = DAG.getLoad(PtrTy, dl, DAG.getEntryNode(),
1793                                   StackSlotPtr,
1794                                   MachinePointerInfo::getFixedStack(FI),
1795                                   true, false, false, Align);
1796
1797   // Perform the comparison via a subtract/getsetcc.
1798   EVT VT = Guard.getValueType();
1799   SDValue Sub = DAG.getNode(ISD::SUB, dl, VT, Guard, StackSlot);
1800
1801   SDValue Cmp =
1802       DAG.getSetCC(dl, TLI.getSetCCResultType(*DAG.getContext(),
1803                                                          Sub.getValueType()),
1804                    Sub, DAG.getConstant(0, dl, VT), ISD::SETNE);
1805
1806   // If the sub is not 0, then we know the guard/stackslot do not equal, so
1807   // branch to failure MBB.
1808   SDValue BrCond = DAG.getNode(ISD::BRCOND, dl,
1809                                MVT::Other, StackSlot.getOperand(0),
1810                                Cmp, DAG.getBasicBlock(SPD.getFailureMBB()));
1811   // Otherwise branch to success MBB.
1812   SDValue Br = DAG.getNode(ISD::BR, dl,
1813                            MVT::Other, BrCond,
1814                            DAG.getBasicBlock(SPD.getSuccessMBB()));
1815
1816   DAG.setRoot(Br);
1817 }
1818
1819 /// Codegen the failure basic block for a stack protector check.
1820 ///
1821 /// A failure stack protector machine basic block consists simply of a call to
1822 /// __stack_chk_fail().
1823 ///
1824 /// For a high level explanation of how this fits into the stack protector
1825 /// generation see the comment on the declaration of class
1826 /// StackProtectorDescriptor.
1827 void
1828 SelectionDAGBuilder::visitSPDescriptorFailure(StackProtectorDescriptor &SPD) {
1829   const TargetLowering &TLI = DAG.getTargetLoweringInfo();
1830   SDValue Chain =
1831       TLI.makeLibCall(DAG, RTLIB::STACKPROTECTOR_CHECK_FAIL, MVT::isVoid,
1832                       nullptr, 0, false, getCurSDLoc(), false, false).second;
1833   DAG.setRoot(Chain);
1834 }
1835
1836 /// visitBitTestHeader - This function emits necessary code to produce value
1837 /// suitable for "bit tests"
1838 void SelectionDAGBuilder::visitBitTestHeader(BitTestBlock &B,
1839                                              MachineBasicBlock *SwitchBB) {
1840   SDLoc dl = getCurSDLoc();
1841
1842   // Subtract the minimum value
1843   SDValue SwitchOp = getValue(B.SValue);
1844   EVT VT = SwitchOp.getValueType();
1845   SDValue Sub = DAG.getNode(ISD::SUB, dl, VT, SwitchOp,
1846                             DAG.getConstant(B.First, dl, VT));
1847
1848   // Check range
1849   const TargetLowering &TLI = DAG.getTargetLoweringInfo();
1850   SDValue RangeCmp =
1851       DAG.getSetCC(dl, TLI.getSetCCResultType(*DAG.getContext(),
1852                                               Sub.getValueType()),
1853                    Sub, DAG.getConstant(B.Range, dl, VT), ISD::SETUGT);
1854
1855   // Determine the type of the test operands.
1856   bool UsePtrType = false;
1857   if (!TLI.isTypeLegal(VT))
1858     UsePtrType = true;
1859   else {
1860     for (unsigned i = 0, e = B.Cases.size(); i != e; ++i)
1861       if (!isUIntN(VT.getSizeInBits(), B.Cases[i].Mask)) {
1862         // Switch table case range are encoded into series of masks.
1863         // Just use pointer type, it's guaranteed to fit.
1864         UsePtrType = true;
1865         break;
1866       }
1867   }
1868   if (UsePtrType) {
1869     VT = TLI.getPointerTy();
1870     Sub = DAG.getZExtOrTrunc(Sub, dl, VT);
1871   }
1872
1873   B.RegVT = VT.getSimpleVT();
1874   B.Reg = FuncInfo.CreateReg(B.RegVT);
1875   SDValue CopyTo = DAG.getCopyToReg(getControlRoot(), dl, B.Reg, Sub);
1876
1877   MachineBasicBlock* MBB = B.Cases[0].ThisBB;
1878
1879   addSuccessorWithWeight(SwitchBB, B.Default);
1880   addSuccessorWithWeight(SwitchBB, MBB);
1881
1882   SDValue BrRange = DAG.getNode(ISD::BRCOND, dl,
1883                                 MVT::Other, CopyTo, RangeCmp,
1884                                 DAG.getBasicBlock(B.Default));
1885
1886   // Avoid emitting unnecessary branches to the next block.
1887   if (MBB != NextBlock(SwitchBB))
1888     BrRange = DAG.getNode(ISD::BR, dl, MVT::Other, BrRange,
1889                           DAG.getBasicBlock(MBB));
1890
1891   DAG.setRoot(BrRange);
1892 }
1893
1894 /// visitBitTestCase - this function produces one "bit test"
1895 void SelectionDAGBuilder::visitBitTestCase(BitTestBlock &BB,
1896                                            MachineBasicBlock* NextMBB,
1897                                            uint32_t BranchWeightToNext,
1898                                            unsigned Reg,
1899                                            BitTestCase &B,
1900                                            MachineBasicBlock *SwitchBB) {
1901   SDLoc dl = getCurSDLoc();
1902   MVT VT = BB.RegVT;
1903   SDValue ShiftOp = DAG.getCopyFromReg(getControlRoot(), dl, Reg, VT);
1904   SDValue Cmp;
1905   unsigned PopCount = countPopulation(B.Mask);
1906   const TargetLowering &TLI = DAG.getTargetLoweringInfo();
1907   if (PopCount == 1) {
1908     // Testing for a single bit; just compare the shift count with what it
1909     // would need to be to shift a 1 bit in that position.
1910     Cmp = DAG.getSetCC(
1911         dl, TLI.getSetCCResultType(*DAG.getContext(), VT), ShiftOp,
1912         DAG.getConstant(countTrailingZeros(B.Mask), dl, VT), ISD::SETEQ);
1913   } else if (PopCount == BB.Range) {
1914     // There is only one zero bit in the range, test for it directly.
1915     Cmp = DAG.getSetCC(
1916         dl, TLI.getSetCCResultType(*DAG.getContext(), VT), ShiftOp,
1917         DAG.getConstant(countTrailingOnes(B.Mask), dl, VT), ISD::SETNE);
1918   } else {
1919     // Make desired shift
1920     SDValue SwitchVal = DAG.getNode(ISD::SHL, dl, VT,
1921                                     DAG.getConstant(1, dl, VT), ShiftOp);
1922
1923     // Emit bit tests and jumps
1924     SDValue AndOp = DAG.getNode(ISD::AND, dl,
1925                                 VT, SwitchVal, DAG.getConstant(B.Mask, dl, VT));
1926     Cmp = DAG.getSetCC(dl, TLI.getSetCCResultType(*DAG.getContext(), VT), AndOp,
1927                        DAG.getConstant(0, dl, VT), ISD::SETNE);
1928   }
1929
1930   // The branch weight from SwitchBB to B.TargetBB is B.ExtraWeight.
1931   addSuccessorWithWeight(SwitchBB, B.TargetBB, B.ExtraWeight);
1932   // The branch weight from SwitchBB to NextMBB is BranchWeightToNext.
1933   addSuccessorWithWeight(SwitchBB, NextMBB, BranchWeightToNext);
1934
1935   SDValue BrAnd = DAG.getNode(ISD::BRCOND, dl,
1936                               MVT::Other, getControlRoot(),
1937                               Cmp, DAG.getBasicBlock(B.TargetBB));
1938
1939   // Avoid emitting unnecessary branches to the next block.
1940   if (NextMBB != NextBlock(SwitchBB))
1941     BrAnd = DAG.getNode(ISD::BR, dl, MVT::Other, BrAnd,
1942                         DAG.getBasicBlock(NextMBB));
1943
1944   DAG.setRoot(BrAnd);
1945 }
1946
1947 void SelectionDAGBuilder::visitInvoke(const InvokeInst &I) {
1948   MachineBasicBlock *InvokeMBB = FuncInfo.MBB;
1949
1950   // Retrieve successors.
1951   MachineBasicBlock *Return = FuncInfo.MBBMap[I.getSuccessor(0)];
1952   MachineBasicBlock *LandingPad = FuncInfo.MBBMap[I.getSuccessor(1)];
1953
1954   const Value *Callee(I.getCalledValue());
1955   const Function *Fn = dyn_cast<Function>(Callee);
1956   if (isa<InlineAsm>(Callee))
1957     visitInlineAsm(&I);
1958   else if (Fn && Fn->isIntrinsic()) {
1959     switch (Fn->getIntrinsicID()) {
1960     default:
1961       llvm_unreachable("Cannot invoke this intrinsic");
1962     case Intrinsic::donothing:
1963       // Ignore invokes to @llvm.donothing: jump directly to the next BB.
1964       break;
1965     case Intrinsic::experimental_patchpoint_void:
1966     case Intrinsic::experimental_patchpoint_i64:
1967       visitPatchpoint(&I, LandingPad);
1968       break;
1969     case Intrinsic::experimental_gc_statepoint:
1970       LowerStatepoint(ImmutableStatepoint(&I), LandingPad);
1971       break;
1972     }
1973   } else
1974     LowerCallTo(&I, getValue(Callee), false, LandingPad);
1975
1976   // If the value of the invoke is used outside of its defining block, make it
1977   // available as a virtual register.
1978   // We already took care of the exported value for the statepoint instruction
1979   // during call to the LowerStatepoint.
1980   if (!isStatepoint(I)) {
1981     CopyToExportRegsIfNeeded(&I);
1982   }
1983
1984   // Update successor info
1985   addSuccessorWithWeight(InvokeMBB, Return);
1986   addSuccessorWithWeight(InvokeMBB, LandingPad);
1987
1988   // Drop into normal successor.
1989   DAG.setRoot(DAG.getNode(ISD::BR, getCurSDLoc(),
1990                           MVT::Other, getControlRoot(),
1991                           DAG.getBasicBlock(Return)));
1992 }
1993
1994 void SelectionDAGBuilder::visitResume(const ResumeInst &RI) {
1995   llvm_unreachable("SelectionDAGBuilder shouldn't visit resume instructions!");
1996 }
1997
1998 void SelectionDAGBuilder::visitLandingPad(const LandingPadInst &LP) {
1999   assert(FuncInfo.MBB->isLandingPad() &&
2000          "Call to landingpad not in landing pad!");
2001
2002   MachineBasicBlock *MBB = FuncInfo.MBB;
2003   MachineModuleInfo &MMI = DAG.getMachineFunction().getMMI();
2004   AddLandingPadInfo(LP, MMI, MBB);
2005
2006   // If there aren't registers to copy the values into (e.g., during SjLj
2007   // exceptions), then don't bother to create these DAG nodes.
2008   const TargetLowering &TLI = DAG.getTargetLoweringInfo();
2009   if (TLI.getExceptionPointerRegister() == 0 &&
2010       TLI.getExceptionSelectorRegister() == 0)
2011     return;
2012
2013   SmallVector<EVT, 2> ValueVTs;
2014   SDLoc dl = getCurSDLoc();
2015   ComputeValueVTs(TLI, LP.getType(), ValueVTs);
2016   assert(ValueVTs.size() == 2 && "Only two-valued landingpads are supported");
2017
2018   // Get the two live-in registers as SDValues. The physregs have already been
2019   // copied into virtual registers.
2020   SDValue Ops[2];
2021   if (FuncInfo.ExceptionPointerVirtReg) {
2022     Ops[0] = DAG.getZExtOrTrunc(
2023         DAG.getCopyFromReg(DAG.getEntryNode(), dl,
2024                            FuncInfo.ExceptionPointerVirtReg, TLI.getPointerTy()),
2025         dl, ValueVTs[0]);
2026   } else {
2027     Ops[0] = DAG.getConstant(0, dl, TLI.getPointerTy());
2028   }
2029   Ops[1] = DAG.getZExtOrTrunc(
2030       DAG.getCopyFromReg(DAG.getEntryNode(), dl,
2031                          FuncInfo.ExceptionSelectorVirtReg, TLI.getPointerTy()),
2032       dl, ValueVTs[1]);
2033
2034   // Merge into one.
2035   SDValue Res = DAG.getNode(ISD::MERGE_VALUES, dl,
2036                             DAG.getVTList(ValueVTs), Ops);
2037   setValue(&LP, Res);
2038 }
2039
2040 unsigned
2041 SelectionDAGBuilder::visitLandingPadClauseBB(GlobalValue *ClauseGV,
2042                                              MachineBasicBlock *LPadBB) {
2043   SDValue Chain = getControlRoot();
2044   SDLoc dl = getCurSDLoc();
2045
2046   // Get the typeid that we will dispatch on later.
2047   const TargetLowering &TLI = DAG.getTargetLoweringInfo();
2048   const TargetRegisterClass *RC = TLI.getRegClassFor(TLI.getPointerTy());
2049   unsigned VReg = FuncInfo.MF->getRegInfo().createVirtualRegister(RC);
2050   unsigned TypeID = DAG.getMachineFunction().getMMI().getTypeIDFor(ClauseGV);
2051   SDValue Sel = DAG.getConstant(TypeID, dl, TLI.getPointerTy());
2052   Chain = DAG.getCopyToReg(Chain, dl, VReg, Sel);
2053
2054   // Branch to the main landing pad block.
2055   MachineBasicBlock *ClauseMBB = FuncInfo.MBB;
2056   ClauseMBB->addSuccessor(LPadBB);
2057   DAG.setRoot(DAG.getNode(ISD::BR, dl, MVT::Other, Chain,
2058                           DAG.getBasicBlock(LPadBB)));
2059   return VReg;
2060 }
2061
2062 void SelectionDAGBuilder::sortAndRangeify(CaseClusterVector &Clusters) {
2063 #ifndef NDEBUG
2064   for (const CaseCluster &CC : Clusters)
2065     assert(CC.Low == CC.High && "Input clusters must be single-case");
2066 #endif
2067
2068   std::sort(Clusters.begin(), Clusters.end(),
2069             [](const CaseCluster &a, const CaseCluster &b) {
2070     return a.Low->getValue().slt(b.Low->getValue());
2071   });
2072
2073   // Merge adjacent clusters with the same destination.
2074   const unsigned N = Clusters.size();
2075   unsigned DstIndex = 0;
2076   for (unsigned SrcIndex = 0; SrcIndex < N; ++SrcIndex) {
2077     CaseCluster &CC = Clusters[SrcIndex];
2078     const ConstantInt *CaseVal = CC.Low;
2079     MachineBasicBlock *Succ = CC.MBB;
2080
2081     if (DstIndex != 0 && Clusters[DstIndex - 1].MBB == Succ &&
2082         (CaseVal->getValue() - Clusters[DstIndex - 1].High->getValue()) == 1) {
2083       // If this case has the same successor and is a neighbour, merge it into
2084       // the previous cluster.
2085       Clusters[DstIndex - 1].High = CaseVal;
2086       Clusters[DstIndex - 1].Weight += CC.Weight;
2087       assert(Clusters[DstIndex - 1].Weight >= CC.Weight && "Weight overflow!");
2088     } else {
2089       std::memmove(&Clusters[DstIndex++], &Clusters[SrcIndex],
2090                    sizeof(Clusters[SrcIndex]));
2091     }
2092   }
2093   Clusters.resize(DstIndex);
2094 }
2095
2096 void SelectionDAGBuilder::UpdateSplitBlock(MachineBasicBlock *First,
2097                                            MachineBasicBlock *Last) {
2098   // Update JTCases.
2099   for (unsigned i = 0, e = JTCases.size(); i != e; ++i)
2100     if (JTCases[i].first.HeaderBB == First)
2101       JTCases[i].first.HeaderBB = Last;
2102
2103   // Update BitTestCases.
2104   for (unsigned i = 0, e = BitTestCases.size(); i != e; ++i)
2105     if (BitTestCases[i].Parent == First)
2106       BitTestCases[i].Parent = Last;
2107 }
2108
2109 void SelectionDAGBuilder::visitIndirectBr(const IndirectBrInst &I) {
2110   MachineBasicBlock *IndirectBrMBB = FuncInfo.MBB;
2111
2112   // Update machine-CFG edges with unique successors.
2113   SmallSet<BasicBlock*, 32> Done;
2114   for (unsigned i = 0, e = I.getNumSuccessors(); i != e; ++i) {
2115     BasicBlock *BB = I.getSuccessor(i);
2116     bool Inserted = Done.insert(BB).second;
2117     if (!Inserted)
2118         continue;
2119
2120     MachineBasicBlock *Succ = FuncInfo.MBBMap[BB];
2121     addSuccessorWithWeight(IndirectBrMBB, Succ);
2122   }
2123
2124   DAG.setRoot(DAG.getNode(ISD::BRIND, getCurSDLoc(),
2125                           MVT::Other, getControlRoot(),
2126                           getValue(I.getAddress())));
2127 }
2128
2129 void SelectionDAGBuilder::visitUnreachable(const UnreachableInst &I) {
2130   if (DAG.getTarget().Options.TrapUnreachable)
2131     DAG.setRoot(DAG.getNode(ISD::TRAP, getCurSDLoc(), MVT::Other, DAG.getRoot()));
2132 }
2133
2134 void SelectionDAGBuilder::visitFSub(const User &I) {
2135   // -0.0 - X --> fneg
2136   Type *Ty = I.getType();
2137   if (isa<Constant>(I.getOperand(0)) &&
2138       I.getOperand(0) == ConstantFP::getZeroValueForNegation(Ty)) {
2139     SDValue Op2 = getValue(I.getOperand(1));
2140     setValue(&I, DAG.getNode(ISD::FNEG, getCurSDLoc(),
2141                              Op2.getValueType(), Op2));
2142     return;
2143   }
2144
2145   visitBinary(I, ISD::FSUB);
2146 }
2147
2148 void SelectionDAGBuilder::visitBinary(const User &I, unsigned OpCode) {
2149   SDValue Op1 = getValue(I.getOperand(0));
2150   SDValue Op2 = getValue(I.getOperand(1));
2151
2152   bool nuw = false;
2153   bool nsw = false;
2154   bool exact = false;
2155   FastMathFlags FMF;
2156
2157   if (const OverflowingBinaryOperator *OFBinOp =
2158           dyn_cast<const OverflowingBinaryOperator>(&I)) {
2159     nuw = OFBinOp->hasNoUnsignedWrap();
2160     nsw = OFBinOp->hasNoSignedWrap();
2161   }
2162   if (const PossiblyExactOperator *ExactOp =
2163           dyn_cast<const PossiblyExactOperator>(&I))
2164     exact = ExactOp->isExact();
2165   if (const FPMathOperator *FPOp = dyn_cast<const FPMathOperator>(&I))
2166     FMF = FPOp->getFastMathFlags();
2167
2168   SDNodeFlags Flags;
2169   Flags.setExact(exact);
2170   Flags.setNoSignedWrap(nsw);
2171   Flags.setNoUnsignedWrap(nuw);
2172   if (EnableFMFInDAG) {
2173     Flags.setAllowReciprocal(FMF.allowReciprocal());
2174     Flags.setNoInfs(FMF.noInfs());
2175     Flags.setNoNaNs(FMF.noNaNs());
2176     Flags.setNoSignedZeros(FMF.noSignedZeros());
2177     Flags.setUnsafeAlgebra(FMF.unsafeAlgebra());
2178   }
2179   SDValue BinNodeValue = DAG.getNode(OpCode, getCurSDLoc(), Op1.getValueType(),
2180                                      Op1, Op2, &Flags);
2181   setValue(&I, BinNodeValue);
2182 }
2183
2184 void SelectionDAGBuilder::visitShift(const User &I, unsigned Opcode) {
2185   SDValue Op1 = getValue(I.getOperand(0));
2186   SDValue Op2 = getValue(I.getOperand(1));
2187
2188   EVT ShiftTy =
2189       DAG.getTargetLoweringInfo().getShiftAmountTy(Op2.getValueType());
2190
2191   // Coerce the shift amount to the right type if we can.
2192   if (!I.getType()->isVectorTy() && Op2.getValueType() != ShiftTy) {
2193     unsigned ShiftSize = ShiftTy.getSizeInBits();
2194     unsigned Op2Size = Op2.getValueType().getSizeInBits();
2195     SDLoc DL = getCurSDLoc();
2196
2197     // If the operand is smaller than the shift count type, promote it.
2198     if (ShiftSize > Op2Size)
2199       Op2 = DAG.getNode(ISD::ZERO_EXTEND, DL, ShiftTy, Op2);
2200
2201     // If the operand is larger than the shift count type but the shift
2202     // count type has enough bits to represent any shift value, truncate
2203     // it now. This is a common case and it exposes the truncate to
2204     // optimization early.
2205     else if (ShiftSize >= Log2_32_Ceil(Op2.getValueType().getSizeInBits()))
2206       Op2 = DAG.getNode(ISD::TRUNCATE, DL, ShiftTy, Op2);
2207     // Otherwise we'll need to temporarily settle for some other convenient
2208     // type.  Type legalization will make adjustments once the shiftee is split.
2209     else
2210       Op2 = DAG.getZExtOrTrunc(Op2, DL, MVT::i32);
2211   }
2212
2213   bool nuw = false;
2214   bool nsw = false;
2215   bool exact = false;
2216
2217   if (Opcode == ISD::SRL || Opcode == ISD::SRA || Opcode == ISD::SHL) {
2218
2219     if (const OverflowingBinaryOperator *OFBinOp =
2220             dyn_cast<const OverflowingBinaryOperator>(&I)) {
2221       nuw = OFBinOp->hasNoUnsignedWrap();
2222       nsw = OFBinOp->hasNoSignedWrap();
2223     }
2224     if (const PossiblyExactOperator *ExactOp =
2225             dyn_cast<const PossiblyExactOperator>(&I))
2226       exact = ExactOp->isExact();
2227   }
2228   SDNodeFlags Flags;
2229   Flags.setExact(exact);
2230   Flags.setNoSignedWrap(nsw);
2231   Flags.setNoUnsignedWrap(nuw);
2232   SDValue Res = DAG.getNode(Opcode, getCurSDLoc(), Op1.getValueType(), Op1, Op2,
2233                             &Flags);
2234   setValue(&I, Res);
2235 }
2236
2237 void SelectionDAGBuilder::visitSDiv(const User &I) {
2238   SDValue Op1 = getValue(I.getOperand(0));
2239   SDValue Op2 = getValue(I.getOperand(1));
2240
2241   SDNodeFlags Flags;
2242   Flags.setExact(isa<PossiblyExactOperator>(&I) &&
2243                  cast<PossiblyExactOperator>(&I)->isExact());
2244   setValue(&I, DAG.getNode(ISD::SDIV, getCurSDLoc(), Op1.getValueType(), Op1,
2245                            Op2, &Flags));
2246 }
2247
2248 void SelectionDAGBuilder::visitICmp(const User &I) {
2249   ICmpInst::Predicate predicate = ICmpInst::BAD_ICMP_PREDICATE;
2250   if (const ICmpInst *IC = dyn_cast<ICmpInst>(&I))
2251     predicate = IC->getPredicate();
2252   else if (const ConstantExpr *IC = dyn_cast<ConstantExpr>(&I))
2253     predicate = ICmpInst::Predicate(IC->getPredicate());
2254   SDValue Op1 = getValue(I.getOperand(0));
2255   SDValue Op2 = getValue(I.getOperand(1));
2256   ISD::CondCode Opcode = getICmpCondCode(predicate);
2257
2258   EVT DestVT = DAG.getTargetLoweringInfo().getValueType(I.getType());
2259   setValue(&I, DAG.getSetCC(getCurSDLoc(), DestVT, Op1, Op2, Opcode));
2260 }
2261
2262 void SelectionDAGBuilder::visitFCmp(const User &I) {
2263   FCmpInst::Predicate predicate = FCmpInst::BAD_FCMP_PREDICATE;
2264   if (const FCmpInst *FC = dyn_cast<FCmpInst>(&I))
2265     predicate = FC->getPredicate();
2266   else if (const ConstantExpr *FC = dyn_cast<ConstantExpr>(&I))
2267     predicate = FCmpInst::Predicate(FC->getPredicate());
2268   SDValue Op1 = getValue(I.getOperand(0));
2269   SDValue Op2 = getValue(I.getOperand(1));
2270   ISD::CondCode Condition = getFCmpCondCode(predicate);
2271   if (TM.Options.NoNaNsFPMath)
2272     Condition = getFCmpCodeWithoutNaN(Condition);
2273   EVT DestVT = DAG.getTargetLoweringInfo().getValueType(I.getType());
2274   setValue(&I, DAG.getSetCC(getCurSDLoc(), DestVT, Op1, Op2, Condition));
2275 }
2276
2277 void SelectionDAGBuilder::visitSelect(const User &I) {
2278   SmallVector<EVT, 4> ValueVTs;
2279   ComputeValueVTs(DAG.getTargetLoweringInfo(), I.getType(), ValueVTs);
2280   unsigned NumValues = ValueVTs.size();
2281   if (NumValues == 0) return;
2282
2283   SmallVector<SDValue, 4> Values(NumValues);
2284   SDValue Cond     = getValue(I.getOperand(0));
2285   SDValue LHSVal   = getValue(I.getOperand(1));
2286   SDValue RHSVal   = getValue(I.getOperand(2));
2287   auto BaseOps = {Cond};
2288   ISD::NodeType OpCode = Cond.getValueType().isVector() ?
2289     ISD::VSELECT : ISD::SELECT;
2290
2291   // Min/max matching is only viable if all output VTs are the same.
2292   if (std::equal(ValueVTs.begin(), ValueVTs.end(), ValueVTs.begin())) {
2293     Value *LHS, *RHS;
2294     SelectPatternFlavor SPF = matchSelectPattern(const_cast<User*>(&I), LHS, RHS);
2295     ISD::NodeType Opc = ISD::DELETED_NODE;
2296     switch (SPF) {
2297     case SPF_UMAX: Opc = ISD::UMAX; break;
2298     case SPF_UMIN: Opc = ISD::UMIN; break;
2299     case SPF_SMAX: Opc = ISD::SMAX; break;
2300     case SPF_SMIN: Opc = ISD::SMIN; break;
2301     default: break;
2302     }
2303
2304     EVT VT = ValueVTs[0];
2305     LLVMContext &Ctx = *DAG.getContext();
2306     auto &TLI = DAG.getTargetLoweringInfo();
2307     while (TLI.getTypeAction(Ctx, VT) == TargetLoweringBase::TypeSplitVector)
2308       VT = TLI.getTypeToTransformTo(Ctx, VT);
2309
2310     if (Opc != ISD::DELETED_NODE && TLI.isOperationLegalOrCustom(Opc, VT) &&
2311         // If the underlying comparison instruction is used by any other instruction,
2312         // the consumed instructions won't be destroyed, so it is not profitable
2313         // to convert to a min/max.
2314         cast<SelectInst>(&I)->getCondition()->hasOneUse()) {
2315       OpCode = Opc;
2316       LHSVal = getValue(LHS);
2317       RHSVal = getValue(RHS);
2318       BaseOps = {};
2319     }
2320   }
2321
2322   for (unsigned i = 0; i != NumValues; ++i) {
2323     SmallVector<SDValue, 3> Ops(BaseOps.begin(), BaseOps.end());
2324     Ops.push_back(SDValue(LHSVal.getNode(), LHSVal.getResNo() + i));
2325     Ops.push_back(SDValue(RHSVal.getNode(), RHSVal.getResNo() + i));
2326     Values[i] = DAG.getNode(OpCode, getCurSDLoc(),
2327                             LHSVal.getNode()->getValueType(LHSVal.getResNo()+i),
2328                             Ops);
2329   }
2330
2331   setValue(&I, DAG.getNode(ISD::MERGE_VALUES, getCurSDLoc(),
2332                            DAG.getVTList(ValueVTs), Values));
2333 }
2334
2335 void SelectionDAGBuilder::visitTrunc(const User &I) {
2336   // TruncInst cannot be a no-op cast because sizeof(src) > sizeof(dest).
2337   SDValue N = getValue(I.getOperand(0));
2338   EVT DestVT = DAG.getTargetLoweringInfo().getValueType(I.getType());
2339   setValue(&I, DAG.getNode(ISD::TRUNCATE, getCurSDLoc(), DestVT, N));
2340 }
2341
2342 void SelectionDAGBuilder::visitZExt(const User &I) {
2343   // ZExt cannot be a no-op cast because sizeof(src) < sizeof(dest).
2344   // ZExt also can't be a cast to bool for same reason. So, nothing much to do
2345   SDValue N = getValue(I.getOperand(0));
2346   EVT DestVT = DAG.getTargetLoweringInfo().getValueType(I.getType());
2347   setValue(&I, DAG.getNode(ISD::ZERO_EXTEND, getCurSDLoc(), DestVT, N));
2348 }
2349
2350 void SelectionDAGBuilder::visitSExt(const User &I) {
2351   // SExt cannot be a no-op cast because sizeof(src) < sizeof(dest).
2352   // SExt also can't be a cast to bool for same reason. So, nothing much to do
2353   SDValue N = getValue(I.getOperand(0));
2354   EVT DestVT = DAG.getTargetLoweringInfo().getValueType(I.getType());
2355   setValue(&I, DAG.getNode(ISD::SIGN_EXTEND, getCurSDLoc(), DestVT, N));
2356 }
2357
2358 void SelectionDAGBuilder::visitFPTrunc(const User &I) {
2359   // FPTrunc is never a no-op cast, no need to check
2360   SDValue N = getValue(I.getOperand(0));
2361   SDLoc dl = getCurSDLoc();
2362   const TargetLowering &TLI = DAG.getTargetLoweringInfo();
2363   EVT DestVT = TLI.getValueType(I.getType());
2364   setValue(&I, DAG.getNode(ISD::FP_ROUND, dl, DestVT, N,
2365                            DAG.getTargetConstant(0, dl, TLI.getPointerTy())));
2366 }
2367
2368 void SelectionDAGBuilder::visitFPExt(const User &I) {
2369   // FPExt is never a no-op cast, no need to check
2370   SDValue N = getValue(I.getOperand(0));
2371   EVT DestVT = DAG.getTargetLoweringInfo().getValueType(I.getType());
2372   setValue(&I, DAG.getNode(ISD::FP_EXTEND, getCurSDLoc(), DestVT, N));
2373 }
2374
2375 void SelectionDAGBuilder::visitFPToUI(const User &I) {
2376   // FPToUI is never a no-op cast, no need to check
2377   SDValue N = getValue(I.getOperand(0));
2378   EVT DestVT = DAG.getTargetLoweringInfo().getValueType(I.getType());
2379   setValue(&I, DAG.getNode(ISD::FP_TO_UINT, getCurSDLoc(), DestVT, N));
2380 }
2381
2382 void SelectionDAGBuilder::visitFPToSI(const User &I) {
2383   // FPToSI is never a no-op cast, no need to check
2384   SDValue N = getValue(I.getOperand(0));
2385   EVT DestVT = DAG.getTargetLoweringInfo().getValueType(I.getType());
2386   setValue(&I, DAG.getNode(ISD::FP_TO_SINT, getCurSDLoc(), DestVT, N));
2387 }
2388
2389 void SelectionDAGBuilder::visitUIToFP(const User &I) {
2390   // UIToFP is never a no-op cast, no need to check
2391   SDValue N = getValue(I.getOperand(0));
2392   EVT DestVT = DAG.getTargetLoweringInfo().getValueType(I.getType());
2393   setValue(&I, DAG.getNode(ISD::UINT_TO_FP, getCurSDLoc(), DestVT, N));
2394 }
2395
2396 void SelectionDAGBuilder::visitSIToFP(const User &I) {
2397   // SIToFP is never a no-op cast, no need to check
2398   SDValue N = getValue(I.getOperand(0));
2399   EVT DestVT = DAG.getTargetLoweringInfo().getValueType(I.getType());
2400   setValue(&I, DAG.getNode(ISD::SINT_TO_FP, getCurSDLoc(), DestVT, N));
2401 }
2402
2403 void SelectionDAGBuilder::visitPtrToInt(const User &I) {
2404   // What to do depends on the size of the integer and the size of the pointer.
2405   // We can either truncate, zero extend, or no-op, accordingly.
2406   SDValue N = getValue(I.getOperand(0));
2407   EVT DestVT = DAG.getTargetLoweringInfo().getValueType(I.getType());
2408   setValue(&I, DAG.getZExtOrTrunc(N, getCurSDLoc(), DestVT));
2409 }
2410
2411 void SelectionDAGBuilder::visitIntToPtr(const User &I) {
2412   // What to do depends on the size of the integer and the size of the pointer.
2413   // We can either truncate, zero extend, or no-op, accordingly.
2414   SDValue N = getValue(I.getOperand(0));
2415   EVT DestVT = DAG.getTargetLoweringInfo().getValueType(I.getType());
2416   setValue(&I, DAG.getZExtOrTrunc(N, getCurSDLoc(), DestVT));
2417 }
2418
2419 void SelectionDAGBuilder::visitBitCast(const User &I) {
2420   SDValue N = getValue(I.getOperand(0));
2421   SDLoc dl = getCurSDLoc();
2422   EVT DestVT = DAG.getTargetLoweringInfo().getValueType(I.getType());
2423
2424   // BitCast assures us that source and destination are the same size so this is
2425   // either a BITCAST or a no-op.
2426   if (DestVT != N.getValueType())
2427     setValue(&I, DAG.getNode(ISD::BITCAST, dl,
2428                              DestVT, N)); // convert types.
2429   // Check if the original LLVM IR Operand was a ConstantInt, because getValue()
2430   // might fold any kind of constant expression to an integer constant and that
2431   // is not what we are looking for. Only regcognize a bitcast of a genuine
2432   // constant integer as an opaque constant.
2433   else if(ConstantInt *C = dyn_cast<ConstantInt>(I.getOperand(0)))
2434     setValue(&I, DAG.getConstant(C->getValue(), dl, DestVT, /*isTarget=*/false,
2435                                  /*isOpaque*/true));
2436   else
2437     setValue(&I, N);            // noop cast.
2438 }
2439
2440 void SelectionDAGBuilder::visitAddrSpaceCast(const User &I) {
2441   const TargetLowering &TLI = DAG.getTargetLoweringInfo();
2442   const Value *SV = I.getOperand(0);
2443   SDValue N = getValue(SV);
2444   EVT DestVT = TLI.getValueType(I.getType());
2445
2446   unsigned SrcAS = SV->getType()->getPointerAddressSpace();
2447   unsigned DestAS = I.getType()->getPointerAddressSpace();
2448
2449   if (!TLI.isNoopAddrSpaceCast(SrcAS, DestAS))
2450     N = DAG.getAddrSpaceCast(getCurSDLoc(), DestVT, N, SrcAS, DestAS);
2451
2452   setValue(&I, N);
2453 }
2454
2455 void SelectionDAGBuilder::visitInsertElement(const User &I) {
2456   const TargetLowering &TLI = DAG.getTargetLoweringInfo();
2457   SDValue InVec = getValue(I.getOperand(0));
2458   SDValue InVal = getValue(I.getOperand(1));
2459   SDValue InIdx = DAG.getSExtOrTrunc(getValue(I.getOperand(2)),
2460                                      getCurSDLoc(), TLI.getVectorIdxTy());
2461   setValue(&I, DAG.getNode(ISD::INSERT_VECTOR_ELT, getCurSDLoc(),
2462                            TLI.getValueType(I.getType()), InVec, InVal, InIdx));
2463 }
2464
2465 void SelectionDAGBuilder::visitExtractElement(const User &I) {
2466   const TargetLowering &TLI = DAG.getTargetLoweringInfo();
2467   SDValue InVec = getValue(I.getOperand(0));
2468   SDValue InIdx = DAG.getSExtOrTrunc(getValue(I.getOperand(1)),
2469                                      getCurSDLoc(), TLI.getVectorIdxTy());
2470   setValue(&I, DAG.getNode(ISD::EXTRACT_VECTOR_ELT, getCurSDLoc(),
2471                            TLI.getValueType(I.getType()), InVec, InIdx));
2472 }
2473
2474 // Utility for visitShuffleVector - Return true if every element in Mask,
2475 // beginning from position Pos and ending in Pos+Size, falls within the
2476 // specified sequential range [L, L+Pos). or is undef.
2477 static bool isSequentialInRange(const SmallVectorImpl<int> &Mask,
2478                                 unsigned Pos, unsigned Size, int Low) {
2479   for (unsigned i = Pos, e = Pos+Size; i != e; ++i, ++Low)
2480     if (Mask[i] >= 0 && Mask[i] != Low)
2481       return false;
2482   return true;
2483 }
2484
2485 void SelectionDAGBuilder::visitShuffleVector(const User &I) {
2486   SDValue Src1 = getValue(I.getOperand(0));
2487   SDValue Src2 = getValue(I.getOperand(1));
2488
2489   SmallVector<int, 8> Mask;
2490   ShuffleVectorInst::getShuffleMask(cast<Constant>(I.getOperand(2)), Mask);
2491   unsigned MaskNumElts = Mask.size();
2492
2493   const TargetLowering &TLI = DAG.getTargetLoweringInfo();
2494   EVT VT = TLI.getValueType(I.getType());
2495   EVT SrcVT = Src1.getValueType();
2496   unsigned SrcNumElts = SrcVT.getVectorNumElements();
2497
2498   if (SrcNumElts == MaskNumElts) {
2499     setValue(&I, DAG.getVectorShuffle(VT, getCurSDLoc(), Src1, Src2,
2500                                       &Mask[0]));
2501     return;
2502   }
2503
2504   // Normalize the shuffle vector since mask and vector length don't match.
2505   if (SrcNumElts < MaskNumElts && MaskNumElts % SrcNumElts == 0) {
2506     // Mask is longer than the source vectors and is a multiple of the source
2507     // vectors.  We can use concatenate vector to make the mask and vectors
2508     // lengths match.
2509     if (SrcNumElts*2 == MaskNumElts) {
2510       // First check for Src1 in low and Src2 in high
2511       if (isSequentialInRange(Mask, 0, SrcNumElts, 0) &&
2512           isSequentialInRange(Mask, SrcNumElts, SrcNumElts, SrcNumElts)) {
2513         // The shuffle is concatenating two vectors together.
2514         setValue(&I, DAG.getNode(ISD::CONCAT_VECTORS, getCurSDLoc(),
2515                                  VT, Src1, Src2));
2516         return;
2517       }
2518       // Then check for Src2 in low and Src1 in high
2519       if (isSequentialInRange(Mask, 0, SrcNumElts, SrcNumElts) &&
2520           isSequentialInRange(Mask, SrcNumElts, SrcNumElts, 0)) {
2521         // The shuffle is concatenating two vectors together.
2522         setValue(&I, DAG.getNode(ISD::CONCAT_VECTORS, getCurSDLoc(),
2523                                  VT, Src2, Src1));
2524         return;
2525       }
2526     }
2527
2528     // Pad both vectors with undefs to make them the same length as the mask.
2529     unsigned NumConcat = MaskNumElts / SrcNumElts;
2530     bool Src1U = Src1.getOpcode() == ISD::UNDEF;
2531     bool Src2U = Src2.getOpcode() == ISD::UNDEF;
2532     SDValue UndefVal = DAG.getUNDEF(SrcVT);
2533
2534     SmallVector<SDValue, 8> MOps1(NumConcat, UndefVal);
2535     SmallVector<SDValue, 8> MOps2(NumConcat, UndefVal);
2536     MOps1[0] = Src1;
2537     MOps2[0] = Src2;
2538
2539     Src1 = Src1U ? DAG.getUNDEF(VT) : DAG.getNode(ISD::CONCAT_VECTORS,
2540                                                   getCurSDLoc(), VT, MOps1);
2541     Src2 = Src2U ? DAG.getUNDEF(VT) : DAG.getNode(ISD::CONCAT_VECTORS,
2542                                                   getCurSDLoc(), VT, MOps2);
2543
2544     // Readjust mask for new input vector length.
2545     SmallVector<int, 8> MappedOps;
2546     for (unsigned i = 0; i != MaskNumElts; ++i) {
2547       int Idx = Mask[i];
2548       if (Idx >= (int)SrcNumElts)
2549         Idx -= SrcNumElts - MaskNumElts;
2550       MappedOps.push_back(Idx);
2551     }
2552
2553     setValue(&I, DAG.getVectorShuffle(VT, getCurSDLoc(), Src1, Src2,
2554                                       &MappedOps[0]));
2555     return;
2556   }
2557
2558   if (SrcNumElts > MaskNumElts) {
2559     // Analyze the access pattern of the vector to see if we can extract
2560     // two subvectors and do the shuffle. The analysis is done by calculating
2561     // the range of elements the mask access on both vectors.
2562     int MinRange[2] = { static_cast<int>(SrcNumElts),
2563                         static_cast<int>(SrcNumElts)};
2564     int MaxRange[2] = {-1, -1};
2565
2566     for (unsigned i = 0; i != MaskNumElts; ++i) {
2567       int Idx = Mask[i];
2568       unsigned Input = 0;
2569       if (Idx < 0)
2570         continue;
2571
2572       if (Idx >= (int)SrcNumElts) {
2573         Input = 1;
2574         Idx -= SrcNumElts;
2575       }
2576       if (Idx > MaxRange[Input])
2577         MaxRange[Input] = Idx;
2578       if (Idx < MinRange[Input])
2579         MinRange[Input] = Idx;
2580     }
2581
2582     // Check if the access is smaller than the vector size and can we find
2583     // a reasonable extract index.
2584     int RangeUse[2] = { -1, -1 };  // 0 = Unused, 1 = Extract, -1 = Can not
2585                                    // Extract.
2586     int StartIdx[2];  // StartIdx to extract from
2587     for (unsigned Input = 0; Input < 2; ++Input) {
2588       if (MinRange[Input] >= (int)SrcNumElts && MaxRange[Input] < 0) {
2589         RangeUse[Input] = 0; // Unused
2590         StartIdx[Input] = 0;
2591         continue;
2592       }
2593
2594       // Find a good start index that is a multiple of the mask length. Then
2595       // see if the rest of the elements are in range.
2596       StartIdx[Input] = (MinRange[Input]/MaskNumElts)*MaskNumElts;
2597       if (MaxRange[Input] - StartIdx[Input] < (int)MaskNumElts &&
2598           StartIdx[Input] + MaskNumElts <= SrcNumElts)
2599         RangeUse[Input] = 1; // Extract from a multiple of the mask length.
2600     }
2601
2602     if (RangeUse[0] == 0 && RangeUse[1] == 0) {
2603       setValue(&I, DAG.getUNDEF(VT)); // Vectors are not used.
2604       return;
2605     }
2606     if (RangeUse[0] >= 0 && RangeUse[1] >= 0) {
2607       // Extract appropriate subvector and generate a vector shuffle
2608       for (unsigned Input = 0; Input < 2; ++Input) {
2609         SDValue &Src = Input == 0 ? Src1 : Src2;
2610         if (RangeUse[Input] == 0)
2611           Src = DAG.getUNDEF(VT);
2612         else {
2613           SDLoc dl = getCurSDLoc();
2614           Src = DAG.getNode(
2615               ISD::EXTRACT_SUBVECTOR, dl, VT, Src,
2616               DAG.getConstant(StartIdx[Input], dl, TLI.getVectorIdxTy()));
2617         }
2618       }
2619
2620       // Calculate new mask.
2621       SmallVector<int, 8> MappedOps;
2622       for (unsigned i = 0; i != MaskNumElts; ++i) {
2623         int Idx = Mask[i];
2624         if (Idx >= 0) {
2625           if (Idx < (int)SrcNumElts)
2626             Idx -= StartIdx[0];
2627           else
2628             Idx -= SrcNumElts + StartIdx[1] - MaskNumElts;
2629         }
2630         MappedOps.push_back(Idx);
2631       }
2632
2633       setValue(&I, DAG.getVectorShuffle(VT, getCurSDLoc(), Src1, Src2,
2634                                         &MappedOps[0]));
2635       return;
2636     }
2637   }
2638
2639   // We can't use either concat vectors or extract subvectors so fall back to
2640   // replacing the shuffle with extract and build vector.
2641   // to insert and build vector.
2642   EVT EltVT = VT.getVectorElementType();
2643   EVT IdxVT = TLI.getVectorIdxTy();
2644   SDLoc dl = getCurSDLoc();
2645   SmallVector<SDValue,8> Ops;
2646   for (unsigned i = 0; i != MaskNumElts; ++i) {
2647     int Idx = Mask[i];
2648     SDValue Res;
2649
2650     if (Idx < 0) {
2651       Res = DAG.getUNDEF(EltVT);
2652     } else {
2653       SDValue &Src = Idx < (int)SrcNumElts ? Src1 : Src2;
2654       if (Idx >= (int)SrcNumElts) Idx -= SrcNumElts;
2655
2656       Res = DAG.getNode(ISD::EXTRACT_VECTOR_ELT, dl,
2657                         EltVT, Src, DAG.getConstant(Idx, dl, IdxVT));
2658     }
2659
2660     Ops.push_back(Res);
2661   }
2662
2663   setValue(&I, DAG.getNode(ISD::BUILD_VECTOR, dl, VT, Ops));
2664 }
2665
2666 void SelectionDAGBuilder::visitInsertValue(const InsertValueInst &I) {
2667   const Value *Op0 = I.getOperand(0);
2668   const Value *Op1 = I.getOperand(1);
2669   Type *AggTy = I.getType();
2670   Type *ValTy = Op1->getType();
2671   bool IntoUndef = isa<UndefValue>(Op0);
2672   bool FromUndef = isa<UndefValue>(Op1);
2673
2674   unsigned LinearIndex = ComputeLinearIndex(AggTy, I.getIndices());
2675
2676   const TargetLowering &TLI = DAG.getTargetLoweringInfo();
2677   SmallVector<EVT, 4> AggValueVTs;
2678   ComputeValueVTs(TLI, AggTy, AggValueVTs);
2679   SmallVector<EVT, 4> ValValueVTs;
2680   ComputeValueVTs(TLI, ValTy, ValValueVTs);
2681
2682   unsigned NumAggValues = AggValueVTs.size();
2683   unsigned NumValValues = ValValueVTs.size();
2684   SmallVector<SDValue, 4> Values(NumAggValues);
2685
2686   // Ignore an insertvalue that produces an empty object
2687   if (!NumAggValues) {
2688     setValue(&I, DAG.getUNDEF(MVT(MVT::Other)));
2689     return;
2690   }
2691
2692   SDValue Agg = getValue(Op0);
2693   unsigned i = 0;
2694   // Copy the beginning value(s) from the original aggregate.
2695   for (; i != LinearIndex; ++i)
2696     Values[i] = IntoUndef ? DAG.getUNDEF(AggValueVTs[i]) :
2697                 SDValue(Agg.getNode(), Agg.getResNo() + i);
2698   // Copy values from the inserted value(s).
2699   if (NumValValues) {
2700     SDValue Val = getValue(Op1);
2701     for (; i != LinearIndex + NumValValues; ++i)
2702       Values[i] = FromUndef ? DAG.getUNDEF(AggValueVTs[i]) :
2703                   SDValue(Val.getNode(), Val.getResNo() + i - LinearIndex);
2704   }
2705   // Copy remaining value(s) from the original aggregate.
2706   for (; i != NumAggValues; ++i)
2707     Values[i] = IntoUndef ? DAG.getUNDEF(AggValueVTs[i]) :
2708                 SDValue(Agg.getNode(), Agg.getResNo() + i);
2709
2710   setValue(&I, DAG.getNode(ISD::MERGE_VALUES, getCurSDLoc(),
2711                            DAG.getVTList(AggValueVTs), Values));
2712 }
2713
2714 void SelectionDAGBuilder::visitExtractValue(const ExtractValueInst &I) {
2715   const Value *Op0 = I.getOperand(0);
2716   Type *AggTy = Op0->getType();
2717   Type *ValTy = I.getType();
2718   bool OutOfUndef = isa<UndefValue>(Op0);
2719
2720   unsigned LinearIndex = ComputeLinearIndex(AggTy, I.getIndices());
2721
2722   const TargetLowering &TLI = DAG.getTargetLoweringInfo();
2723   SmallVector<EVT, 4> ValValueVTs;
2724   ComputeValueVTs(TLI, ValTy, ValValueVTs);
2725
2726   unsigned NumValValues = ValValueVTs.size();
2727
2728   // Ignore a extractvalue that produces an empty object
2729   if (!NumValValues) {
2730     setValue(&I, DAG.getUNDEF(MVT(MVT::Other)));
2731     return;
2732   }
2733
2734   SmallVector<SDValue, 4> Values(NumValValues);
2735
2736   SDValue Agg = getValue(Op0);
2737   // Copy out the selected value(s).
2738   for (unsigned i = LinearIndex; i != LinearIndex + NumValValues; ++i)
2739     Values[i - LinearIndex] =
2740       OutOfUndef ?
2741         DAG.getUNDEF(Agg.getNode()->getValueType(Agg.getResNo() + i)) :
2742         SDValue(Agg.getNode(), Agg.getResNo() + i);
2743
2744   setValue(&I, DAG.getNode(ISD::MERGE_VALUES, getCurSDLoc(),
2745                            DAG.getVTList(ValValueVTs), Values));
2746 }
2747
2748 void SelectionDAGBuilder::visitGetElementPtr(const User &I) {
2749   Value *Op0 = I.getOperand(0);
2750   // Note that the pointer operand may be a vector of pointers. Take the scalar
2751   // element which holds a pointer.
2752   Type *Ty = Op0->getType()->getScalarType();
2753   unsigned AS = Ty->getPointerAddressSpace();
2754   SDValue N = getValue(Op0);
2755   SDLoc dl = getCurSDLoc();
2756
2757   for (GetElementPtrInst::const_op_iterator OI = I.op_begin()+1, E = I.op_end();
2758        OI != E; ++OI) {
2759     const Value *Idx = *OI;
2760     if (StructType *StTy = dyn_cast<StructType>(Ty)) {
2761       unsigned Field = cast<Constant>(Idx)->getUniqueInteger().getZExtValue();
2762       if (Field) {
2763         // N = N + Offset
2764         uint64_t Offset = DL->getStructLayout(StTy)->getElementOffset(Field);
2765         N = DAG.getNode(ISD::ADD, dl, N.getValueType(), N,
2766                         DAG.getConstant(Offset, dl, N.getValueType()));
2767       }
2768
2769       Ty = StTy->getElementType(Field);
2770     } else {
2771       Ty = cast<SequentialType>(Ty)->getElementType();
2772       MVT PtrTy = DAG.getTargetLoweringInfo().getPointerTy(AS);
2773       unsigned PtrSize = PtrTy.getSizeInBits();
2774       APInt ElementSize(PtrSize, DL->getTypeAllocSize(Ty));
2775
2776       // If this is a constant subscript, handle it quickly.
2777       if (const auto *CI = dyn_cast<ConstantInt>(Idx)) {
2778         if (CI->isZero())
2779           continue;
2780         APInt Offs = ElementSize * CI->getValue().sextOrTrunc(PtrSize);
2781         SDValue OffsVal = DAG.getConstant(Offs, dl, PtrTy);
2782         N = DAG.getNode(ISD::ADD, dl, N.getValueType(), N, OffsVal);
2783         continue;
2784       }
2785
2786       // N = N + Idx * ElementSize;
2787       SDValue IdxN = getValue(Idx);
2788
2789       // If the index is smaller or larger than intptr_t, truncate or extend
2790       // it.
2791       IdxN = DAG.getSExtOrTrunc(IdxN, dl, N.getValueType());
2792
2793       // If this is a multiply by a power of two, turn it into a shl
2794       // immediately.  This is a very common case.
2795       if (ElementSize != 1) {
2796         if (ElementSize.isPowerOf2()) {
2797           unsigned Amt = ElementSize.logBase2();
2798           IdxN = DAG.getNode(ISD::SHL, dl,
2799                              N.getValueType(), IdxN,
2800                              DAG.getConstant(Amt, dl, IdxN.getValueType()));
2801         } else {
2802           SDValue Scale = DAG.getConstant(ElementSize, dl, IdxN.getValueType());
2803           IdxN = DAG.getNode(ISD::MUL, dl,
2804                              N.getValueType(), IdxN, Scale);
2805         }
2806       }
2807
2808       N = DAG.getNode(ISD::ADD, dl,
2809                       N.getValueType(), N, IdxN);
2810     }
2811   }
2812
2813   setValue(&I, N);
2814 }
2815
2816 void SelectionDAGBuilder::visitAlloca(const AllocaInst &I) {
2817   // If this is a fixed sized alloca in the entry block of the function,
2818   // allocate it statically on the stack.
2819   if (FuncInfo.StaticAllocaMap.count(&I))
2820     return;   // getValue will auto-populate this.
2821
2822   SDLoc dl = getCurSDLoc();
2823   Type *Ty = I.getAllocatedType();
2824   const TargetLowering &TLI = DAG.getTargetLoweringInfo();
2825   auto &DL = DAG.getDataLayout();
2826   uint64_t TySize = DL.getTypeAllocSize(Ty);
2827   unsigned Align =
2828       std::max((unsigned)DL.getPrefTypeAlignment(Ty), I.getAlignment());
2829
2830   SDValue AllocSize = getValue(I.getArraySize());
2831
2832   EVT IntPtr = TLI.getPointerTy();
2833   if (AllocSize.getValueType() != IntPtr)
2834     AllocSize = DAG.getZExtOrTrunc(AllocSize, dl, IntPtr);
2835
2836   AllocSize = DAG.getNode(ISD::MUL, dl, IntPtr,
2837                           AllocSize,
2838                           DAG.getConstant(TySize, dl, IntPtr));
2839
2840   // Handle alignment.  If the requested alignment is less than or equal to
2841   // the stack alignment, ignore it.  If the size is greater than or equal to
2842   // the stack alignment, we note this in the DYNAMIC_STACKALLOC node.
2843   unsigned StackAlign =
2844       DAG.getSubtarget().getFrameLowering()->getStackAlignment();
2845   if (Align <= StackAlign)
2846     Align = 0;
2847
2848   // Round the size of the allocation up to the stack alignment size
2849   // by add SA-1 to the size.
2850   AllocSize = DAG.getNode(ISD::ADD, dl,
2851                           AllocSize.getValueType(), AllocSize,
2852                           DAG.getIntPtrConstant(StackAlign - 1, dl));
2853
2854   // Mask out the low bits for alignment purposes.
2855   AllocSize = DAG.getNode(ISD::AND, dl,
2856                           AllocSize.getValueType(), AllocSize,
2857                           DAG.getIntPtrConstant(~(uint64_t)(StackAlign - 1),
2858                                                 dl));
2859
2860   SDValue Ops[] = { getRoot(), AllocSize, DAG.getIntPtrConstant(Align, dl) };
2861   SDVTList VTs = DAG.getVTList(AllocSize.getValueType(), MVT::Other);
2862   SDValue DSA = DAG.getNode(ISD::DYNAMIC_STACKALLOC, dl, VTs, Ops);
2863   setValue(&I, DSA);
2864   DAG.setRoot(DSA.getValue(1));
2865
2866   assert(FuncInfo.MF->getFrameInfo()->hasVarSizedObjects());
2867 }
2868
2869 void SelectionDAGBuilder::visitLoad(const LoadInst &I) {
2870   if (I.isAtomic())
2871     return visitAtomicLoad(I);
2872
2873   const Value *SV = I.getOperand(0);
2874   SDValue Ptr = getValue(SV);
2875
2876   Type *Ty = I.getType();
2877
2878   bool isVolatile = I.isVolatile();
2879   bool isNonTemporal = I.getMetadata(LLVMContext::MD_nontemporal) != nullptr;
2880
2881   // The IR notion of invariant_load only guarantees that all *non-faulting*
2882   // invariant loads result in the same value.  The MI notion of invariant load
2883   // guarantees that the load can be legally moved to any location within its
2884   // containing function.  The MI notion of invariant_load is stronger than the
2885   // IR notion of invariant_load -- an MI invariant_load is an IR invariant_load
2886   // with a guarantee that the location being loaded from is dereferenceable
2887   // throughout the function's lifetime.
2888
2889   bool isInvariant = I.getMetadata(LLVMContext::MD_invariant_load) != nullptr &&
2890     isDereferenceablePointer(SV, *DAG.getTarget().getDataLayout());
2891   unsigned Alignment = I.getAlignment();
2892
2893   AAMDNodes AAInfo;
2894   I.getAAMetadata(AAInfo);
2895   const MDNode *Ranges = I.getMetadata(LLVMContext::MD_range);
2896
2897   const TargetLowering &TLI = DAG.getTargetLoweringInfo();
2898   SmallVector<EVT, 4> ValueVTs;
2899   SmallVector<uint64_t, 4> Offsets;
2900   ComputeValueVTs(TLI, Ty, ValueVTs, &Offsets);
2901   unsigned NumValues = ValueVTs.size();
2902   if (NumValues == 0)
2903     return;
2904
2905   SDValue Root;
2906   bool ConstantMemory = false;
2907   if (isVolatile || NumValues > MaxParallelChains)
2908     // Serialize volatile loads with other side effects.
2909     Root = getRoot();
2910   else if (AA->pointsToConstantMemory(
2911                MemoryLocation(SV, AA->getTypeStoreSize(Ty), AAInfo))) {
2912     // Do not serialize (non-volatile) loads of constant memory with anything.
2913     Root = DAG.getEntryNode();
2914     ConstantMemory = true;
2915   } else {
2916     // Do not serialize non-volatile loads against each other.
2917     Root = DAG.getRoot();
2918   }
2919
2920   SDLoc dl = getCurSDLoc();
2921
2922   if (isVolatile)
2923     Root = TLI.prepareVolatileOrAtomicLoad(Root, dl, DAG);
2924
2925   SmallVector<SDValue, 4> Values(NumValues);
2926   SmallVector<SDValue, 4> Chains(std::min(MaxParallelChains, NumValues));
2927   EVT PtrVT = Ptr.getValueType();
2928   unsigned ChainI = 0;
2929   for (unsigned i = 0; i != NumValues; ++i, ++ChainI) {
2930     // Serializing loads here may result in excessive register pressure, and
2931     // TokenFactor places arbitrary choke points on the scheduler. SD scheduling
2932     // could recover a bit by hoisting nodes upward in the chain by recognizing
2933     // they are side-effect free or do not alias. The optimizer should really
2934     // avoid this case by converting large object/array copies to llvm.memcpy
2935     // (MaxParallelChains should always remain as failsafe).
2936     if (ChainI == MaxParallelChains) {
2937       assert(PendingLoads.empty() && "PendingLoads must be serialized first");
2938       SDValue Chain = DAG.getNode(ISD::TokenFactor, dl, MVT::Other,
2939                                   makeArrayRef(Chains.data(), ChainI));
2940       Root = Chain;
2941       ChainI = 0;
2942     }
2943     SDValue A = DAG.getNode(ISD::ADD, dl,
2944                             PtrVT, Ptr,
2945                             DAG.getConstant(Offsets[i], dl, PtrVT));
2946     SDValue L = DAG.getLoad(ValueVTs[i], dl, Root,
2947                             A, MachinePointerInfo(SV, Offsets[i]), isVolatile,
2948                             isNonTemporal, isInvariant, Alignment, AAInfo,
2949                             Ranges);
2950
2951     Values[i] = L;
2952     Chains[ChainI] = L.getValue(1);
2953   }
2954
2955   if (!ConstantMemory) {
2956     SDValue Chain = DAG.getNode(ISD::TokenFactor, dl, MVT::Other,
2957                                 makeArrayRef(Chains.data(), ChainI));
2958     if (isVolatile)
2959       DAG.setRoot(Chain);
2960     else
2961       PendingLoads.push_back(Chain);
2962   }
2963
2964   setValue(&I, DAG.getNode(ISD::MERGE_VALUES, dl,
2965                            DAG.getVTList(ValueVTs), Values));
2966 }
2967
2968 void SelectionDAGBuilder::visitStore(const StoreInst &I) {
2969   if (I.isAtomic())
2970     return visitAtomicStore(I);
2971
2972   const Value *SrcV = I.getOperand(0);
2973   const Value *PtrV = I.getOperand(1);
2974
2975   SmallVector<EVT, 4> ValueVTs;
2976   SmallVector<uint64_t, 4> Offsets;
2977   ComputeValueVTs(DAG.getTargetLoweringInfo(), SrcV->getType(),
2978                   ValueVTs, &Offsets);
2979   unsigned NumValues = ValueVTs.size();
2980   if (NumValues == 0)
2981     return;
2982
2983   // Get the lowered operands. Note that we do this after
2984   // checking if NumResults is zero, because with zero results
2985   // the operands won't have values in the map.
2986   SDValue Src = getValue(SrcV);
2987   SDValue Ptr = getValue(PtrV);
2988
2989   SDValue Root = getRoot();
2990   SmallVector<SDValue, 4> Chains(std::min(MaxParallelChains, NumValues));
2991   EVT PtrVT = Ptr.getValueType();
2992   bool isVolatile = I.isVolatile();
2993   bool isNonTemporal = I.getMetadata(LLVMContext::MD_nontemporal) != nullptr;
2994   unsigned Alignment = I.getAlignment();
2995   SDLoc dl = getCurSDLoc();
2996
2997   AAMDNodes AAInfo;
2998   I.getAAMetadata(AAInfo);
2999
3000   unsigned ChainI = 0;
3001   for (unsigned i = 0; i != NumValues; ++i, ++ChainI) {
3002     // See visitLoad comments.
3003     if (ChainI == MaxParallelChains) {
3004       SDValue Chain = DAG.getNode(ISD::TokenFactor, dl, MVT::Other,
3005                                   makeArrayRef(Chains.data(), ChainI));
3006       Root = Chain;
3007       ChainI = 0;
3008     }
3009     SDValue Add = DAG.getNode(ISD::ADD, dl, PtrVT, Ptr,
3010                               DAG.getConstant(Offsets[i], dl, PtrVT));
3011     SDValue St = DAG.getStore(Root, dl,
3012                               SDValue(Src.getNode(), Src.getResNo() + i),
3013                               Add, MachinePointerInfo(PtrV, Offsets[i]),
3014                               isVolatile, isNonTemporal, Alignment, AAInfo);
3015     Chains[ChainI] = St;
3016   }
3017
3018   SDValue StoreNode = DAG.getNode(ISD::TokenFactor, dl, MVT::Other,
3019                                   makeArrayRef(Chains.data(), ChainI));
3020   DAG.setRoot(StoreNode);
3021 }
3022
3023 void SelectionDAGBuilder::visitMaskedStore(const CallInst &I) {
3024   SDLoc sdl = getCurSDLoc();
3025
3026   // llvm.masked.store.*(Src0, Ptr, alignemt, Mask)
3027   Value  *PtrOperand = I.getArgOperand(1);
3028   SDValue Ptr = getValue(PtrOperand);
3029   SDValue Src0 = getValue(I.getArgOperand(0));
3030   SDValue Mask = getValue(I.getArgOperand(3));
3031   EVT VT = Src0.getValueType();
3032   unsigned Alignment = (cast<ConstantInt>(I.getArgOperand(2)))->getZExtValue();
3033   if (!Alignment)
3034     Alignment = DAG.getEVTAlignment(VT);
3035
3036   AAMDNodes AAInfo;
3037   I.getAAMetadata(AAInfo);
3038
3039   MachineMemOperand *MMO =
3040     DAG.getMachineFunction().
3041     getMachineMemOperand(MachinePointerInfo(PtrOperand),
3042                           MachineMemOperand::MOStore,  VT.getStoreSize(),
3043                           Alignment, AAInfo);
3044   SDValue StoreNode = DAG.getMaskedStore(getRoot(), sdl, Src0, Ptr, Mask, VT,
3045                                          MMO, false);
3046   DAG.setRoot(StoreNode);
3047   setValue(&I, StoreNode);
3048 }
3049
3050 // Gather/scatter receive a vector of pointers.
3051 // This vector of pointers may be represented as a base pointer + vector of 
3052 // indices, it depends on GEP and instruction preceeding GEP
3053 // that calculates indices
3054 static bool getUniformBase(Value *& Ptr, SDValue& Base, SDValue& Index,
3055                            SelectionDAGBuilder* SDB) {
3056
3057   assert (Ptr->getType()->isVectorTy() && "Uexpected pointer type");
3058   GetElementPtrInst *Gep = dyn_cast<GetElementPtrInst>(Ptr);
3059   if (!Gep || Gep->getNumOperands() > 2)
3060     return false;
3061   ShuffleVectorInst *ShuffleInst = 
3062     dyn_cast<ShuffleVectorInst>(Gep->getPointerOperand());
3063   if (!ShuffleInst || !ShuffleInst->getMask()->isNullValue() ||
3064       cast<Instruction>(ShuffleInst->getOperand(0))->getOpcode() !=
3065       Instruction::InsertElement)
3066     return false;
3067
3068   Ptr = cast<InsertElementInst>(ShuffleInst->getOperand(0))->getOperand(1);
3069
3070   SelectionDAG& DAG = SDB->DAG;
3071   const TargetLowering &TLI = DAG.getTargetLoweringInfo();
3072   // Check is the Ptr is inside current basic block
3073   // If not, look for the shuffle instruction
3074   if (SDB->findValue(Ptr))
3075     Base = SDB->getValue(Ptr);
3076   else if (SDB->findValue(ShuffleInst)) {
3077     SDValue ShuffleNode = SDB->getValue(ShuffleInst);
3078     SDLoc sdl = ShuffleNode;
3079     Base = DAG.getNode(ISD::EXTRACT_VECTOR_ELT, sdl,
3080                        ShuffleNode.getValueType().getScalarType(), ShuffleNode,
3081                        DAG.getConstant(0, sdl, TLI.getVectorIdxTy()));
3082     SDB->setValue(Ptr, Base);
3083   }
3084   else
3085     return false;
3086
3087   Value *IndexVal = Gep->getOperand(1);
3088   if (SDB->findValue(IndexVal)) {
3089     Index = SDB->getValue(IndexVal);
3090
3091     if (SExtInst* Sext = dyn_cast<SExtInst>(IndexVal)) {
3092       IndexVal = Sext->getOperand(0);
3093       if (SDB->findValue(IndexVal))
3094         Index = SDB->getValue(IndexVal);
3095     }
3096     return true;
3097   }
3098   return false;
3099 }
3100
3101 void SelectionDAGBuilder::visitMaskedScatter(const CallInst &I) {
3102   SDLoc sdl = getCurSDLoc();
3103
3104   // llvm.masked.scatter.*(Src0, Ptrs, alignemt, Mask)
3105   Value  *Ptr = I.getArgOperand(1);
3106   SDValue Src0 = getValue(I.getArgOperand(0));
3107   SDValue Mask = getValue(I.getArgOperand(3));
3108   EVT VT = Src0.getValueType();
3109   unsigned Alignment = (cast<ConstantInt>(I.getArgOperand(2)))->getZExtValue();
3110   if (!Alignment)
3111     Alignment = DAG.getEVTAlignment(VT);
3112   const TargetLowering &TLI = DAG.getTargetLoweringInfo();
3113
3114   AAMDNodes AAInfo;
3115   I.getAAMetadata(AAInfo);
3116
3117   SDValue Base;
3118   SDValue Index;
3119   Value *BasePtr = Ptr;
3120   bool UniformBase = getUniformBase(BasePtr, Base, Index, this);
3121
3122   Value *MemOpBasePtr = UniformBase ? BasePtr : nullptr;
3123   MachineMemOperand *MMO = DAG.getMachineFunction().
3124     getMachineMemOperand(MachinePointerInfo(MemOpBasePtr),
3125                          MachineMemOperand::MOStore,  VT.getStoreSize(),
3126                          Alignment, AAInfo);
3127   if (!UniformBase) {
3128     Base = DAG.getTargetConstant(0, sdl, TLI.getPointerTy());
3129     Index = getValue(Ptr);
3130   }
3131   SDValue Ops[] = { getRoot(), Src0, Mask, Base, Index };
3132   SDValue Scatter = DAG.getMaskedScatter(DAG.getVTList(MVT::Other), VT, sdl,
3133                                          Ops, MMO);
3134   DAG.setRoot(Scatter);
3135   setValue(&I, Scatter);
3136 }
3137
3138 void SelectionDAGBuilder::visitMaskedLoad(const CallInst &I) {
3139   SDLoc sdl = getCurSDLoc();
3140
3141   // @llvm.masked.load.*(Ptr, alignment, Mask, Src0)
3142   Value  *PtrOperand = I.getArgOperand(0);
3143   SDValue Ptr = getValue(PtrOperand);
3144   SDValue Src0 = getValue(I.getArgOperand(3));
3145   SDValue Mask = getValue(I.getArgOperand(2));
3146
3147   const TargetLowering &TLI = DAG.getTargetLoweringInfo();
3148   EVT VT = TLI.getValueType(I.getType());
3149   unsigned Alignment = (cast<ConstantInt>(I.getArgOperand(1)))->getZExtValue();
3150   if (!Alignment)
3151     Alignment = DAG.getEVTAlignment(VT);
3152
3153   AAMDNodes AAInfo;
3154   I.getAAMetadata(AAInfo);
3155   const MDNode *Ranges = I.getMetadata(LLVMContext::MD_range);
3156
3157   SDValue InChain = DAG.getRoot();
3158   if (AA->pointsToConstantMemory(MemoryLocation(
3159           PtrOperand, AA->getTypeStoreSize(I.getType()), AAInfo))) {
3160     // Do not serialize (non-volatile) loads of constant memory with anything.
3161     InChain = DAG.getEntryNode();
3162   }
3163
3164   MachineMemOperand *MMO =
3165     DAG.getMachineFunction().
3166     getMachineMemOperand(MachinePointerInfo(PtrOperand),
3167                           MachineMemOperand::MOLoad,  VT.getStoreSize(),
3168                           Alignment, AAInfo, Ranges);
3169
3170   SDValue Load = DAG.getMaskedLoad(VT, sdl, InChain, Ptr, Mask, Src0, VT, MMO,
3171                                    ISD::NON_EXTLOAD);
3172   SDValue OutChain = Load.getValue(1);
3173   DAG.setRoot(OutChain);
3174   setValue(&I, Load);
3175 }
3176
3177 void SelectionDAGBuilder::visitMaskedGather(const CallInst &I) {
3178   SDLoc sdl = getCurSDLoc();
3179
3180   // @llvm.masked.gather.*(Ptrs, alignment, Mask, Src0)
3181   Value  *Ptr = I.getArgOperand(0);
3182   SDValue Src0 = getValue(I.getArgOperand(3));
3183   SDValue Mask = getValue(I.getArgOperand(2));
3184
3185   const TargetLowering &TLI = DAG.getTargetLoweringInfo();
3186   EVT VT = TLI.getValueType(I.getType());
3187   unsigned Alignment = (cast<ConstantInt>(I.getArgOperand(1)))->getZExtValue();
3188   if (!Alignment)
3189     Alignment = DAG.getEVTAlignment(VT);
3190
3191   AAMDNodes AAInfo;
3192   I.getAAMetadata(AAInfo);
3193   const MDNode *Ranges = I.getMetadata(LLVMContext::MD_range);
3194
3195   SDValue Root = DAG.getRoot();
3196   SDValue Base;
3197   SDValue Index;
3198   Value *BasePtr = Ptr;
3199   bool UniformBase = getUniformBase(BasePtr, Base, Index, this);
3200   bool ConstantMemory = false;
3201   if (UniformBase &&
3202       AA->pointsToConstantMemory(
3203           MemoryLocation(BasePtr, AA->getTypeStoreSize(I.getType()), AAInfo))) {
3204     // Do not serialize (non-volatile) loads of constant memory with anything.
3205     Root = DAG.getEntryNode();
3206     ConstantMemory = true;
3207   }
3208
3209   MachineMemOperand *MMO =
3210     DAG.getMachineFunction().
3211     getMachineMemOperand(MachinePointerInfo(UniformBase ? BasePtr : nullptr),
3212                          MachineMemOperand::MOLoad,  VT.getStoreSize(),
3213                          Alignment, AAInfo, Ranges);
3214
3215   if (!UniformBase) {
3216     Base = DAG.getTargetConstant(0, sdl, TLI.getPointerTy());
3217     Index = getValue(Ptr);
3218   }
3219   SDValue Ops[] = { Root, Src0, Mask, Base, Index };
3220   SDValue Gather = DAG.getMaskedGather(DAG.getVTList(VT, MVT::Other), VT, sdl,
3221                                        Ops, MMO);
3222
3223   SDValue OutChain = Gather.getValue(1);
3224   if (!ConstantMemory)
3225     PendingLoads.push_back(OutChain);
3226   setValue(&I, Gather);
3227 }
3228
3229 void SelectionDAGBuilder::visitAtomicCmpXchg(const AtomicCmpXchgInst &I) {
3230   SDLoc dl = getCurSDLoc();
3231   AtomicOrdering SuccessOrder = I.getSuccessOrdering();
3232   AtomicOrdering FailureOrder = I.getFailureOrdering();
3233   SynchronizationScope Scope = I.getSynchScope();
3234
3235   SDValue InChain = getRoot();
3236
3237   MVT MemVT = getValue(I.getCompareOperand()).getSimpleValueType();
3238   SDVTList VTs = DAG.getVTList(MemVT, MVT::i1, MVT::Other);
3239   SDValue L = DAG.getAtomicCmpSwap(
3240       ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS, dl, MemVT, VTs, InChain,
3241       getValue(I.getPointerOperand()), getValue(I.getCompareOperand()),
3242       getValue(I.getNewValOperand()), MachinePointerInfo(I.getPointerOperand()),
3243       /*Alignment=*/ 0, SuccessOrder, FailureOrder, Scope);
3244
3245   SDValue OutChain = L.getValue(2);
3246
3247   setValue(&I, L);
3248   DAG.setRoot(OutChain);
3249 }
3250
3251 void SelectionDAGBuilder::visitAtomicRMW(const AtomicRMWInst &I) {
3252   SDLoc dl = getCurSDLoc();
3253   ISD::NodeType NT;
3254   switch (I.getOperation()) {
3255   default: llvm_unreachable("Unknown atomicrmw operation");
3256   case AtomicRMWInst::Xchg: NT = ISD::ATOMIC_SWAP; break;
3257   case AtomicRMWInst::Add:  NT = ISD::ATOMIC_LOAD_ADD; break;
3258   case AtomicRMWInst::Sub:  NT = ISD::ATOMIC_LOAD_SUB; break;
3259   case AtomicRMWInst::And:  NT = ISD::ATOMIC_LOAD_AND; break;
3260   case AtomicRMWInst::Nand: NT = ISD::ATOMIC_LOAD_NAND; break;
3261   case AtomicRMWInst::Or:   NT = ISD::ATOMIC_LOAD_OR; break;
3262   case AtomicRMWInst::Xor:  NT = ISD::ATOMIC_LOAD_XOR; break;
3263   case AtomicRMWInst::Max:  NT = ISD::ATOMIC_LOAD_MAX; break;
3264   case AtomicRMWInst::Min:  NT = ISD::ATOMIC_LOAD_MIN; break;
3265   case AtomicRMWInst::UMax: NT = ISD::ATOMIC_LOAD_UMAX; break;
3266   case AtomicRMWInst::UMin: NT = ISD::ATOMIC_LOAD_UMIN; break;
3267   }
3268   AtomicOrdering Order = I.getOrdering();
3269   SynchronizationScope Scope = I.getSynchScope();
3270
3271   SDValue InChain = getRoot();
3272
3273   SDValue L =
3274     DAG.getAtomic(NT, dl,
3275                   getValue(I.getValOperand()).getSimpleValueType(),
3276                   InChain,
3277                   getValue(I.getPointerOperand()),
3278                   getValue(I.getValOperand()),
3279                   I.getPointerOperand(),
3280                   /* Alignment=*/ 0, Order, Scope);
3281
3282   SDValue OutChain = L.getValue(1);
3283
3284   setValue(&I, L);
3285   DAG.setRoot(OutChain);
3286 }
3287
3288 void SelectionDAGBuilder::visitFence(const FenceInst &I) {
3289   SDLoc dl = getCurSDLoc();
3290   const TargetLowering &TLI = DAG.getTargetLoweringInfo();
3291   SDValue Ops[3];
3292   Ops[0] = getRoot();
3293   Ops[1] = DAG.getConstant(I.getOrdering(), dl, TLI.getPointerTy());
3294   Ops[2] = DAG.getConstant(I.getSynchScope(), dl, TLI.getPointerTy());
3295   DAG.setRoot(DAG.getNode(ISD::ATOMIC_FENCE, dl, MVT::Other, Ops));
3296 }
3297
3298 void SelectionDAGBuilder::visitAtomicLoad(const LoadInst &I) {
3299   SDLoc dl = getCurSDLoc();
3300   AtomicOrdering Order = I.getOrdering();
3301   SynchronizationScope Scope = I.getSynchScope();
3302
3303   SDValue InChain = getRoot();
3304
3305   const TargetLowering &TLI = DAG.getTargetLoweringInfo();
3306   EVT VT = TLI.getValueType(I.getType());
3307
3308   if (I.getAlignment() < VT.getSizeInBits() / 8)
3309     report_fatal_error("Cannot generate unaligned atomic load");
3310
3311   MachineMemOperand *MMO =
3312       DAG.getMachineFunction().
3313       getMachineMemOperand(MachinePointerInfo(I.getPointerOperand()),
3314                            MachineMemOperand::MOVolatile |
3315                            MachineMemOperand::MOLoad,
3316                            VT.getStoreSize(),
3317                            I.getAlignment() ? I.getAlignment() :
3318                                               DAG.getEVTAlignment(VT));
3319
3320   InChain = TLI.prepareVolatileOrAtomicLoad(InChain, dl, DAG);
3321   SDValue L =
3322       DAG.getAtomic(ISD::ATOMIC_LOAD, dl, VT, VT, InChain,
3323                     getValue(I.getPointerOperand()), MMO,
3324                     Order, Scope);
3325
3326   SDValue OutChain = L.getValue(1);
3327
3328   setValue(&I, L);
3329   DAG.setRoot(OutChain);
3330 }
3331
3332 void SelectionDAGBuilder::visitAtomicStore(const StoreInst &I) {
3333   SDLoc dl = getCurSDLoc();
3334
3335   AtomicOrdering Order = I.getOrdering();
3336   SynchronizationScope Scope = I.getSynchScope();
3337
3338   SDValue InChain = getRoot();
3339
3340   const TargetLowering &TLI = DAG.getTargetLoweringInfo();
3341   EVT VT = TLI.getValueType(I.getValueOperand()->getType());
3342
3343   if (I.getAlignment() < VT.getSizeInBits() / 8)
3344     report_fatal_error("Cannot generate unaligned atomic store");
3345
3346   SDValue OutChain =
3347     DAG.getAtomic(ISD::ATOMIC_STORE, dl, VT,
3348                   InChain,
3349                   getValue(I.getPointerOperand()),
3350                   getValue(I.getValueOperand()),
3351                   I.getPointerOperand(), I.getAlignment(),
3352                   Order, Scope);
3353
3354   DAG.setRoot(OutChain);
3355 }
3356
3357 /// visitTargetIntrinsic - Lower a call of a target intrinsic to an INTRINSIC
3358 /// node.
3359 void SelectionDAGBuilder::visitTargetIntrinsic(const CallInst &I,
3360                                                unsigned Intrinsic) {
3361   bool HasChain = !I.doesNotAccessMemory();
3362   bool OnlyLoad = HasChain && I.onlyReadsMemory();
3363
3364   // Build the operand list.
3365   SmallVector<SDValue, 8> Ops;
3366   if (HasChain) {  // If this intrinsic has side-effects, chainify it.
3367     if (OnlyLoad) {
3368       // We don't need to serialize loads against other loads.
3369       Ops.push_back(DAG.getRoot());
3370     } else {
3371       Ops.push_back(getRoot());
3372     }
3373   }
3374
3375   // Info is set by getTgtMemInstrinsic
3376   TargetLowering::IntrinsicInfo Info;
3377   const TargetLowering &TLI = DAG.getTargetLoweringInfo();
3378   bool IsTgtIntrinsic = TLI.getTgtMemIntrinsic(Info, I, Intrinsic);
3379
3380   // Add the intrinsic ID as an integer operand if it's not a target intrinsic.
3381   if (!IsTgtIntrinsic || Info.opc == ISD::INTRINSIC_VOID ||
3382       Info.opc == ISD::INTRINSIC_W_CHAIN)
3383     Ops.push_back(DAG.getTargetConstant(Intrinsic, getCurSDLoc(),
3384                                         TLI.getPointerTy()));
3385
3386   // Add all operands of the call to the operand list.
3387   for (unsigned i = 0, e = I.getNumArgOperands(); i != e; ++i) {
3388     SDValue Op = getValue(I.getArgOperand(i));
3389     Ops.push_back(Op);
3390   }
3391
3392   SmallVector<EVT, 4> ValueVTs;
3393   ComputeValueVTs(TLI, I.getType(), ValueVTs);
3394
3395   if (HasChain)
3396     ValueVTs.push_back(MVT::Other);
3397
3398   SDVTList VTs = DAG.getVTList(ValueVTs);
3399
3400   // Create the node.
3401   SDValue Result;
3402   if (IsTgtIntrinsic) {
3403     // This is target intrinsic that touches memory
3404     Result = DAG.getMemIntrinsicNode(Info.opc, getCurSDLoc(),
3405                                      VTs, Ops, Info.memVT,
3406                                    MachinePointerInfo(Info.ptrVal, Info.offset),
3407                                      Info.align, Info.vol,
3408                                      Info.readMem, Info.writeMem, Info.size);
3409   } else if (!HasChain) {
3410     Result = DAG.getNode(ISD::INTRINSIC_WO_CHAIN, getCurSDLoc(), VTs, Ops);
3411   } else if (!I.getType()->isVoidTy()) {
3412     Result = DAG.getNode(ISD::INTRINSIC_W_CHAIN, getCurSDLoc(), VTs, Ops);
3413   } else {
3414     Result = DAG.getNode(ISD::INTRINSIC_VOID, getCurSDLoc(), VTs, Ops);
3415   }
3416
3417   if (HasChain) {
3418     SDValue Chain = Result.getValue(Result.getNode()->getNumValues()-1);
3419     if (OnlyLoad)
3420       PendingLoads.push_back(Chain);
3421     else
3422       DAG.setRoot(Chain);
3423   }
3424
3425   if (!I.getType()->isVoidTy()) {
3426     if (VectorType *PTy = dyn_cast<VectorType>(I.getType())) {
3427       EVT VT = TLI.getValueType(PTy);
3428       Result = DAG.getNode(ISD::BITCAST, getCurSDLoc(), VT, Result);
3429     }
3430
3431     setValue(&I, Result);
3432   }
3433 }
3434
3435 /// GetSignificand - Get the significand and build it into a floating-point
3436 /// number with exponent of 1:
3437 ///
3438 ///   Op = (Op & 0x007fffff) | 0x3f800000;
3439 ///
3440 /// where Op is the hexadecimal representation of floating point value.
3441 static SDValue
3442 GetSignificand(SelectionDAG &DAG, SDValue Op, SDLoc dl) {
3443   SDValue t1 = DAG.getNode(ISD::AND, dl, MVT::i32, Op,
3444                            DAG.getConstant(0x007fffff, dl, MVT::i32));
3445   SDValue t2 = DAG.getNode(ISD::OR, dl, MVT::i32, t1,
3446                            DAG.getConstant(0x3f800000, dl, MVT::i32));
3447   return DAG.getNode(ISD::BITCAST, dl, MVT::f32, t2);
3448 }
3449
3450 /// GetExponent - Get the exponent:
3451 ///
3452 ///   (float)(int)(((Op & 0x7f800000) >> 23) - 127);
3453 ///
3454 /// where Op is the hexadecimal representation of floating point value.
3455 static SDValue
3456 GetExponent(SelectionDAG &DAG, SDValue Op, const TargetLowering &TLI,
3457             SDLoc dl) {
3458   SDValue t0 = DAG.getNode(ISD::AND, dl, MVT::i32, Op,
3459                            DAG.getConstant(0x7f800000, dl, MVT::i32));
3460   SDValue t1 = DAG.getNode(ISD::SRL, dl, MVT::i32, t0,
3461                            DAG.getConstant(23, dl, TLI.getPointerTy()));
3462   SDValue t2 = DAG.getNode(ISD::SUB, dl, MVT::i32, t1,
3463                            DAG.getConstant(127, dl, MVT::i32));
3464   return DAG.getNode(ISD::SINT_TO_FP, dl, MVT::f32, t2);
3465 }
3466
3467 /// getF32Constant - Get 32-bit floating point constant.
3468 static SDValue
3469 getF32Constant(SelectionDAG &DAG, unsigned Flt, SDLoc dl) {
3470   return DAG.getConstantFP(APFloat(APFloat::IEEEsingle, APInt(32, Flt)), dl,
3471                            MVT::f32);
3472 }
3473
3474 static SDValue getLimitedPrecisionExp2(SDValue t0, SDLoc dl,
3475                                        SelectionDAG &DAG) {
3476   //   IntegerPartOfX = ((int32_t)(t0);
3477   SDValue IntegerPartOfX = DAG.getNode(ISD::FP_TO_SINT, dl, MVT::i32, t0);
3478
3479   //   FractionalPartOfX = t0 - (float)IntegerPartOfX;
3480   SDValue t1 = DAG.getNode(ISD::SINT_TO_FP, dl, MVT::f32, IntegerPartOfX);
3481   SDValue X = DAG.getNode(ISD::FSUB, dl, MVT::f32, t0, t1);
3482
3483   //   IntegerPartOfX <<= 23;
3484   IntegerPartOfX = DAG.getNode(
3485       ISD::SHL, dl, MVT::i32, IntegerPartOfX,
3486       DAG.getConstant(23, dl, DAG.getTargetLoweringInfo().getPointerTy()));
3487
3488   SDValue TwoToFractionalPartOfX;
3489   if (LimitFloatPrecision <= 6) {
3490     // For floating-point precision of 6:
3491     //
3492     //   TwoToFractionalPartOfX =
3493     //     0.997535578f +
3494     //       (0.735607626f + 0.252464424f * x) * x;
3495     //
3496     // error 0.0144103317, which is 6 bits
3497     SDValue t2 = DAG.getNode(ISD::FMUL, dl, MVT::f32, X,
3498                              getF32Constant(DAG, 0x3e814304, dl));
3499     SDValue t3 = DAG.getNode(ISD::FADD, dl, MVT::f32, t2,
3500                              getF32Constant(DAG, 0x3f3c50c8, dl));
3501     SDValue t4 = DAG.getNode(ISD::FMUL, dl, MVT::f32, t3, X);
3502     TwoToFractionalPartOfX = DAG.getNode(ISD::FADD, dl, MVT::f32, t4,
3503                                          getF32Constant(DAG, 0x3f7f5e7e, dl));
3504   } else if (LimitFloatPrecision <= 12) {
3505     // For floating-point precision of 12:
3506     //
3507     //   TwoToFractionalPartOfX =
3508     //     0.999892986f +
3509     //       (0.696457318f +
3510     //         (0.224338339f + 0.792043434e-1f * x) * x) * x;
3511     //
3512     // error 0.000107046256, which is 13 to 14 bits
3513     SDValue t2 = DAG.getNode(ISD::FMUL, dl, MVT::f32, X,
3514                              getF32Constant(DAG, 0x3da235e3, dl));
3515     SDValue t3 = DAG.getNode(ISD::FADD, dl, MVT::f32, t2,
3516                              getF32Constant(DAG, 0x3e65b8f3, dl));
3517     SDValue t4 = DAG.getNode(ISD::FMUL, dl, MVT::f32, t3, X);
3518     SDValue t5 = DAG.getNode(ISD::FADD, dl, MVT::f32, t4,
3519                              getF32Constant(DAG, 0x3f324b07, dl));
3520     SDValue t6 = DAG.getNode(ISD::FMUL, dl, MVT::f32, t5, X);
3521     TwoToFractionalPartOfX = DAG.getNode(ISD::FADD, dl, MVT::f32, t6,
3522                                          getF32Constant(DAG, 0x3f7ff8fd, dl));
3523   } else { // LimitFloatPrecision <= 18
3524     // For floating-point precision of 18:
3525     //
3526     //   TwoToFractionalPartOfX =
3527     //     0.999999982f +
3528     //       (0.693148872f +
3529     //         (0.240227044f +
3530     //           (0.554906021e-1f +
3531     //             (0.961591928e-2f +
3532     //               (0.136028312e-2f + 0.157059148e-3f *x)*x)*x)*x)*x)*x;
3533     // error 2.47208000*10^(-7), which is better than 18 bits
3534     SDValue t2 = DAG.getNode(ISD::FMUL, dl, MVT::f32, X,
3535                              getF32Constant(DAG, 0x3924b03e, dl));
3536     SDValue t3 = DAG.getNode(ISD::FADD, dl, MVT::f32, t2,
3537                              getF32Constant(DAG, 0x3ab24b87, dl));
3538     SDValue t4 = DAG.getNode(ISD::FMUL, dl, MVT::f32, t3, X);
3539     SDValue t5 = DAG.getNode(ISD::FADD, dl, MVT::f32, t4,
3540                              getF32Constant(DAG, 0x3c1d8c17, dl));
3541     SDValue t6 = DAG.getNode(ISD::FMUL, dl, MVT::f32, t5, X);
3542     SDValue t7 = DAG.getNode(ISD::FADD, dl, MVT::f32, t6,
3543                              getF32Constant(DAG, 0x3d634a1d, dl));
3544     SDValue t8 = DAG.getNode(ISD::FMUL, dl, MVT::f32, t7, X);
3545     SDValue t9 = DAG.getNode(ISD::FADD, dl, MVT::f32, t8,
3546                              getF32Constant(DAG, 0x3e75fe14, dl));
3547     SDValue t10 = DAG.getNode(ISD::FMUL, dl, MVT::f32, t9, X);
3548     SDValue t11 = DAG.getNode(ISD::FADD, dl, MVT::f32, t10,
3549                               getF32Constant(DAG, 0x3f317234, dl));
3550     SDValue t12 = DAG.getNode(ISD::FMUL, dl, MVT::f32, t11, X);
3551     TwoToFractionalPartOfX = DAG.getNode(ISD::FADD, dl, MVT::f32, t12,
3552                                          getF32Constant(DAG, 0x3f800000, dl));
3553   }
3554
3555   // Add the exponent into the result in integer domain.
3556   SDValue t13 = DAG.getNode(ISD::BITCAST, dl, MVT::i32, TwoToFractionalPartOfX);
3557   return DAG.getNode(ISD::BITCAST, dl, MVT::f32,
3558                      DAG.getNode(ISD::ADD, dl, MVT::i32, t13, IntegerPartOfX));
3559 }
3560
3561 /// expandExp - Lower an exp intrinsic. Handles the special sequences for
3562 /// limited-precision mode.
3563 static SDValue expandExp(SDLoc dl, SDValue Op, SelectionDAG &DAG,
3564                          const TargetLowering &TLI) {
3565   if (Op.getValueType() == MVT::f32 &&
3566       LimitFloatPrecision > 0 && LimitFloatPrecision <= 18) {
3567
3568     // Put the exponent in the right bit position for later addition to the
3569     // final result:
3570     //
3571     //   #define LOG2OFe 1.4426950f
3572     //   t0 = Op * LOG2OFe
3573     SDValue t0 = DAG.getNode(ISD::FMUL, dl, MVT::f32, Op,
3574                              getF32Constant(DAG, 0x3fb8aa3b, dl));
3575     return getLimitedPrecisionExp2(t0, dl, DAG);
3576   }
3577
3578   // No special expansion.
3579   return DAG.getNode(ISD::FEXP, dl, Op.getValueType(), Op);
3580 }
3581
3582 /// expandLog - Lower a log intrinsic. Handles the special sequences for
3583 /// limited-precision mode.
3584 static SDValue expandLog(SDLoc dl, SDValue Op, SelectionDAG &DAG,
3585                          const TargetLowering &TLI) {
3586   if (Op.getValueType() == MVT::f32 &&
3587       LimitFloatPrecision > 0 && LimitFloatPrecision <= 18) {
3588     SDValue Op1 = DAG.getNode(ISD::BITCAST, dl, MVT::i32, Op);
3589
3590     // Scale the exponent by log(2) [0.69314718f].
3591     SDValue Exp = GetExponent(DAG, Op1, TLI, dl);
3592     SDValue LogOfExponent = DAG.getNode(ISD::FMUL, dl, MVT::f32, Exp,
3593                                         getF32Constant(DAG, 0x3f317218, dl));
3594
3595     // Get the significand and build it into a floating-point number with
3596     // exponent of 1.
3597     SDValue X = GetSignificand(DAG, Op1, dl);
3598
3599     SDValue LogOfMantissa;
3600     if (LimitFloatPrecision <= 6) {
3601       // For floating-point precision of 6:
3602       //
3603       //   LogofMantissa =
3604       //     -1.1609546f +
3605       //       (1.4034025f - 0.23903021f * x) * x;
3606       //
3607       // error 0.0034276066, which is better than 8 bits
3608       SDValue t0 = DAG.getNode(ISD::FMUL, dl, MVT::f32, X,
3609                                getF32Constant(DAG, 0xbe74c456, dl));
3610       SDValue t1 = DAG.getNode(ISD::FADD, dl, MVT::f32, t0,
3611                                getF32Constant(DAG, 0x3fb3a2b1, dl));
3612       SDValue t2 = DAG.getNode(ISD::FMUL, dl, MVT::f32, t1, X);
3613       LogOfMantissa = DAG.getNode(ISD::FSUB, dl, MVT::f32, t2,
3614                                   getF32Constant(DAG, 0x3f949a29, dl));
3615     } else if (LimitFloatPrecision <= 12) {
3616       // For floating-point precision of 12:
3617       //
3618       //   LogOfMantissa =
3619       //     -1.7417939f +
3620       //       (2.8212026f +
3621       //         (-1.4699568f +
3622       //           (0.44717955f - 0.56570851e-1f * x) * x) * x) * x;
3623       //
3624       // error 0.000061011436, which is 14 bits
3625       SDValue t0 = DAG.getNode(ISD::FMUL, dl, MVT::f32, X,
3626                                getF32Constant(DAG, 0xbd67b6d6, dl));
3627       SDValue t1 = DAG.getNode(ISD::FADD, dl, MVT::f32, t0,
3628                                getF32Constant(DAG, 0x3ee4f4b8, dl));
3629       SDValue t2 = DAG.getNode(ISD::FMUL, dl, MVT::f32, t1, X);
3630       SDValue t3 = DAG.getNode(ISD::FSUB, dl, MVT::f32, t2,
3631                                getF32Constant(DAG, 0x3fbc278b, dl));
3632       SDValue t4 = DAG.getNode(ISD::FMUL, dl, MVT::f32, t3, X);
3633       SDValue t5 = DAG.getNode(ISD::FADD, dl, MVT::f32, t4,
3634                                getF32Constant(DAG, 0x40348e95, dl));
3635       SDValue t6 = DAG.getNode(ISD::FMUL, dl, MVT::f32, t5, X);
3636       LogOfMantissa = DAG.getNode(ISD::FSUB, dl, MVT::f32, t6,
3637                                   getF32Constant(DAG, 0x3fdef31a, dl));
3638     } else { // LimitFloatPrecision <= 18
3639       // For floating-point precision of 18:
3640       //
3641       //   LogOfMantissa =
3642       //     -2.1072184f +
3643       //       (4.2372794f +
3644       //         (-3.7029485f +
3645       //           (2.2781945f +
3646       //             (-0.87823314f +
3647       //               (0.19073739f - 0.17809712e-1f * x) * x) * x) * x) * x)*x;
3648       //
3649       // error 0.0000023660568, which is better than 18 bits
3650       SDValue t0 = DAG.getNode(ISD::FMUL, dl, MVT::f32, X,
3651                                getF32Constant(DAG, 0xbc91e5ac, dl));
3652       SDValue t1 = DAG.getNode(ISD::FADD, dl, MVT::f32, t0,
3653                                getF32Constant(DAG, 0x3e4350aa, dl));
3654       SDValue t2 = DAG.getNode(ISD::FMUL, dl, MVT::f32, t1, X);
3655       SDValue t3 = DAG.getNode(ISD::FSUB, dl, MVT::f32, t2,
3656                                getF32Constant(DAG, 0x3f60d3e3, dl));
3657       SDValue t4 = DAG.getNode(ISD::FMUL, dl, MVT::f32, t3, X);
3658       SDValue t5 = DAG.getNode(ISD::FADD, dl, MVT::f32, t4,
3659                                getF32Constant(DAG, 0x4011cdf0, dl));
3660       SDValue t6 = DAG.getNode(ISD::FMUL, dl, MVT::f32, t5, X);
3661       SDValue t7 = DAG.getNode(ISD::FSUB, dl, MVT::f32, t6,
3662                                getF32Constant(DAG, 0x406cfd1c, dl));
3663       SDValue t8 = DAG.getNode(ISD::FMUL, dl, MVT::f32, t7, X);
3664       SDValue t9 = DAG.getNode(ISD::FADD, dl, MVT::f32, t8,
3665                                getF32Constant(DAG, 0x408797cb, dl));
3666       SDValue t10 = DAG.getNode(ISD::FMUL, dl, MVT::f32, t9, X);
3667       LogOfMantissa = DAG.getNode(ISD::FSUB, dl, MVT::f32, t10,
3668                                   getF32Constant(DAG, 0x4006dcab, dl));
3669     }
3670
3671     return DAG.getNode(ISD::FADD, dl, MVT::f32, LogOfExponent, LogOfMantissa);
3672   }
3673
3674   // No special expansion.
3675   return DAG.getNode(ISD::FLOG, dl, Op.getValueType(), Op);
3676 }
3677
3678 /// expandLog2 - Lower a log2 intrinsic. Handles the special sequences for
3679 /// limited-precision mode.
3680 static SDValue expandLog2(SDLoc dl, SDValue Op, SelectionDAG &DAG,
3681                           const TargetLowering &TLI) {
3682   if (Op.getValueType() == MVT::f32 &&
3683       LimitFloatPrecision > 0 && LimitFloatPrecision <= 18) {
3684     SDValue Op1 = DAG.getNode(ISD::BITCAST, dl, MVT::i32, Op);
3685
3686     // Get the exponent.
3687     SDValue LogOfExponent = GetExponent(DAG, Op1, TLI, dl);
3688
3689     // Get the significand and build it into a floating-point number with
3690     // exponent of 1.
3691     SDValue X = GetSignificand(DAG, Op1, dl);
3692
3693     // Different possible minimax approximations of significand in
3694     // floating-point for various degrees of accuracy over [1,2].
3695     SDValue Log2ofMantissa;
3696     if (LimitFloatPrecision <= 6) {
3697       // For floating-point precision of 6:
3698       //
3699       //   Log2ofMantissa = -1.6749035f + (2.0246817f - .34484768f * x) * x;
3700       //
3701       // error 0.0049451742, which is more than 7 bits
3702       SDValue t0 = DAG.getNode(ISD::FMUL, dl, MVT::f32, X,
3703                                getF32Constant(DAG, 0xbeb08fe0, dl));
3704       SDValue t1 = DAG.getNode(ISD::FADD, dl, MVT::f32, t0,
3705                                getF32Constant(DAG, 0x40019463, dl));
3706       SDValue t2 = DAG.getNode(ISD::FMUL, dl, MVT::f32, t1, X);
3707       Log2ofMantissa = DAG.getNode(ISD::FSUB, dl, MVT::f32, t2,
3708                                    getF32Constant(DAG, 0x3fd6633d, dl));
3709     } else if (LimitFloatPrecision <= 12) {
3710       // For floating-point precision of 12:
3711       //
3712       //   Log2ofMantissa =
3713       //     -2.51285454f +
3714       //       (4.07009056f +
3715       //         (-2.12067489f +
3716       //           (.645142248f - 0.816157886e-1f * x) * x) * x) * x;
3717       //
3718       // error 0.0000876136000, which is better than 13 bits
3719       SDValue t0 = DAG.getNode(ISD::FMUL, dl, MVT::f32, X,
3720                                getF32Constant(DAG, 0xbda7262e, dl));
3721       SDValue t1 = DAG.getNode(ISD::FADD, dl, MVT::f32, t0,
3722                                getF32Constant(DAG, 0x3f25280b, dl));
3723       SDValue t2 = DAG.getNode(ISD::FMUL, dl, MVT::f32, t1, X);
3724       SDValue t3 = DAG.getNode(ISD::FSUB, dl, MVT::f32, t2,
3725                                getF32Constant(DAG, 0x4007b923, dl));
3726       SDValue t4 = DAG.getNode(ISD::FMUL, dl, MVT::