LLVM  6.0.0svn
TargetLowering.cpp
Go to the documentation of this file.
1 //===-- TargetLowering.cpp - Implement the TargetLowering class -----------===//
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 the TargetLowering class.
11 //
12 //===----------------------------------------------------------------------===//
13 
15 #include "llvm/ADT/BitVector.h"
16 #include "llvm/ADT/STLExtras.h"
23 #include "llvm/IR/DataLayout.h"
24 #include "llvm/IR/DerivedTypes.h"
25 #include "llvm/IR/GlobalVariable.h"
26 #include "llvm/IR/LLVMContext.h"
27 #include "llvm/MC/MCAsmInfo.h"
28 #include "llvm/MC/MCExpr.h"
30 #include "llvm/Support/KnownBits.h"
36 #include <cctype>
37 using namespace llvm;
38 
39 /// NOTE: The TargetMachine owns TLOF.
41  : TargetLoweringBase(tm) {}
42 
43 const char *TargetLowering::getTargetNodeName(unsigned Opcode) const {
44  return nullptr;
45 }
46 
49 }
50 
51 /// Check whether a given call node is in tail position within its function. If
52 /// so, it sets Chain to the input chain of the tail call.
54  SDValue &Chain) const {
55  const Function *F = DAG.getMachineFunction().getFunction();
56 
57  // Conservatively require the attributes of the call to match those of
58  // the return. Ignore noalias because it doesn't affect the call sequence.
59  AttributeList CallerAttrs = F->getAttributes();
60  if (AttrBuilder(CallerAttrs, AttributeList::ReturnIndex)
61  .removeAttribute(Attribute::NoAlias)
62  .hasAttributes())
63  return false;
64 
65  // It's not safe to eliminate the sign / zero extension of the return value.
66  if (CallerAttrs.hasAttribute(AttributeList::ReturnIndex, Attribute::ZExt) ||
67  CallerAttrs.hasAttribute(AttributeList::ReturnIndex, Attribute::SExt))
68  return false;
69 
70  // Check if the only use is a function return node.
71  return isUsedByReturnOnly(Node, Chain);
72 }
73 
75  const uint32_t *CallerPreservedMask,
76  const SmallVectorImpl<CCValAssign> &ArgLocs,
77  const SmallVectorImpl<SDValue> &OutVals) const {
78  for (unsigned I = 0, E = ArgLocs.size(); I != E; ++I) {
79  const CCValAssign &ArgLoc = ArgLocs[I];
80  if (!ArgLoc.isRegLoc())
81  continue;
82  unsigned Reg = ArgLoc.getLocReg();
83  // Only look at callee saved registers.
84  if (MachineOperand::clobbersPhysReg(CallerPreservedMask, Reg))
85  continue;
86  // Check that we pass the value used for the caller.
87  // (We look for a CopyFromReg reading a virtual register that is used
88  // for the function live-in value of register Reg)
89  SDValue Value = OutVals[I];
90  if (Value->getOpcode() != ISD::CopyFromReg)
91  return false;
92  unsigned ArgReg = cast<RegisterSDNode>(Value->getOperand(1))->getReg();
93  if (MRI.getLiveInPhysReg(ArgReg) != Reg)
94  return false;
95  }
96  return true;
97 }
98 
99 /// \brief Set CallLoweringInfo attribute flags based on a call instruction
100 /// and called function attributes.
102  unsigned ArgIdx) {
103  IsSExt = CS->paramHasAttr(ArgIdx, Attribute::SExt);
104  IsZExt = CS->paramHasAttr(ArgIdx, Attribute::ZExt);
105  IsInReg = CS->paramHasAttr(ArgIdx, Attribute::InReg);
106  IsSRet = CS->paramHasAttr(ArgIdx, Attribute::StructRet);
107  IsNest = CS->paramHasAttr(ArgIdx, Attribute::Nest);
108  IsByVal = CS->paramHasAttr(ArgIdx, Attribute::ByVal);
109  IsInAlloca = CS->paramHasAttr(ArgIdx, Attribute::InAlloca);
110  IsReturned = CS->paramHasAttr(ArgIdx, Attribute::Returned);
111  IsSwiftSelf = CS->paramHasAttr(ArgIdx, Attribute::SwiftSelf);
112  IsSwiftError = CS->paramHasAttr(ArgIdx, Attribute::SwiftError);
113  Alignment = CS->getParamAlignment(ArgIdx);
114 }
115 
116 /// Generate a libcall taking the given operands as arguments and returning a
117 /// result of type RetVT.
118 std::pair<SDValue, SDValue>
120  ArrayRef<SDValue> Ops, bool isSigned,
121  const SDLoc &dl, bool doesNotReturn,
122  bool isReturnValueUsed) const {
124  Args.reserve(Ops.size());
125 
127  for (SDValue Op : Ops) {
128  Entry.Node = Op;
129  Entry.Ty = Entry.Node.getValueType().getTypeForEVT(*DAG.getContext());
130  Entry.IsSExt = shouldSignExtendTypeInLibCall(Op.getValueType(), isSigned);
131  Entry.IsZExt = !shouldSignExtendTypeInLibCall(Op.getValueType(), isSigned);
132  Args.push_back(Entry);
133  }
134 
135  if (LC == RTLIB::UNKNOWN_LIBCALL)
136  report_fatal_error("Unsupported library call operation!");
137  SDValue Callee = DAG.getExternalSymbol(getLibcallName(LC),
138  getPointerTy(DAG.getDataLayout()));
139 
140  Type *RetTy = RetVT.getTypeForEVT(*DAG.getContext());
142  bool signExtend = shouldSignExtendTypeInLibCall(RetVT, isSigned);
143  CLI.setDebugLoc(dl)
144  .setChain(DAG.getEntryNode())
145  .setLibCallee(getLibcallCallingConv(LC), RetTy, Callee, std::move(Args))
146  .setNoReturn(doesNotReturn)
147  .setDiscardResult(!isReturnValueUsed)
148  .setSExtResult(signExtend)
149  .setZExtResult(!signExtend);
150  return LowerCallTo(CLI);
151 }
152 
153 /// Soften the operands of a comparison. This code is shared among BR_CC,
154 /// SELECT_CC, and SETCC handlers.
156  SDValue &NewLHS, SDValue &NewRHS,
157  ISD::CondCode &CCCode,
158  const SDLoc &dl) const {
159  assert((VT == MVT::f32 || VT == MVT::f64 || VT == MVT::f128 || VT == MVT::ppcf128)
160  && "Unsupported setcc type!");
161 
162  // Expand into one or more soft-fp libcall(s).
163  RTLIB::Libcall LC1 = RTLIB::UNKNOWN_LIBCALL, LC2 = RTLIB::UNKNOWN_LIBCALL;
164  bool ShouldInvertCC = false;
165  switch (CCCode) {
166  case ISD::SETEQ:
167  case ISD::SETOEQ:
168  LC1 = (VT == MVT::f32) ? RTLIB::OEQ_F32 :
169  (VT == MVT::f64) ? RTLIB::OEQ_F64 :
170  (VT == MVT::f128) ? RTLIB::OEQ_F128 : RTLIB::OEQ_PPCF128;
171  break;
172  case ISD::SETNE:
173  case ISD::SETUNE:
174  LC1 = (VT == MVT::f32) ? RTLIB::UNE_F32 :
175  (VT == MVT::f64) ? RTLIB::UNE_F64 :
176  (VT == MVT::f128) ? RTLIB::UNE_F128 : RTLIB::UNE_PPCF128;
177  break;
178  case ISD::SETGE:
179  case ISD::SETOGE:
180  LC1 = (VT == MVT::f32) ? RTLIB::OGE_F32 :
181  (VT == MVT::f64) ? RTLIB::OGE_F64 :
182  (VT == MVT::f128) ? RTLIB::OGE_F128 : RTLIB::OGE_PPCF128;
183  break;
184  case ISD::SETLT:
185  case ISD::SETOLT:
186  LC1 = (VT == MVT::f32) ? RTLIB::OLT_F32 :
187  (VT == MVT::f64) ? RTLIB::OLT_F64 :
188  (VT == MVT::f128) ? RTLIB::OLT_F128 : RTLIB::OLT_PPCF128;
189  break;
190  case ISD::SETLE:
191  case ISD::SETOLE:
192  LC1 = (VT == MVT::f32) ? RTLIB::OLE_F32 :
193  (VT == MVT::f64) ? RTLIB::OLE_F64 :
194  (VT == MVT::f128) ? RTLIB::OLE_F128 : RTLIB::OLE_PPCF128;
195  break;
196  case ISD::SETGT:
197  case ISD::SETOGT:
198  LC1 = (VT == MVT::f32) ? RTLIB::OGT_F32 :
199  (VT == MVT::f64) ? RTLIB::OGT_F64 :
200  (VT == MVT::f128) ? RTLIB::OGT_F128 : RTLIB::OGT_PPCF128;
201  break;
202  case ISD::SETUO:
203  LC1 = (VT == MVT::f32) ? RTLIB::UO_F32 :
204  (VT == MVT::f64) ? RTLIB::UO_F64 :
205  (VT == MVT::f128) ? RTLIB::UO_F128 : RTLIB::UO_PPCF128;
206  break;
207  case ISD::SETO:
208  LC1 = (VT == MVT::f32) ? RTLIB::O_F32 :
209  (VT == MVT::f64) ? RTLIB::O_F64 :
210  (VT == MVT::f128) ? RTLIB::O_F128 : RTLIB::O_PPCF128;
211  break;
212  case ISD::SETONE:
213  // SETONE = SETOLT | SETOGT
214  LC1 = (VT == MVT::f32) ? RTLIB::OLT_F32 :
215  (VT == MVT::f64) ? RTLIB::OLT_F64 :
216  (VT == MVT::f128) ? RTLIB::OLT_F128 : RTLIB::OLT_PPCF128;
217  LC2 = (VT == MVT::f32) ? RTLIB::OGT_F32 :
218  (VT == MVT::f64) ? RTLIB::OGT_F64 :
219  (VT == MVT::f128) ? RTLIB::OGT_F128 : RTLIB::OGT_PPCF128;
220  break;
221  case ISD::SETUEQ:
222  LC1 = (VT == MVT::f32) ? RTLIB::UO_F32 :
223  (VT == MVT::f64) ? RTLIB::UO_F64 :
224  (VT == MVT::f128) ? RTLIB::UO_F128 : RTLIB::UO_PPCF128;
225  LC2 = (VT == MVT::f32) ? RTLIB::OEQ_F32 :
226  (VT == MVT::f64) ? RTLIB::OEQ_F64 :
227  (VT == MVT::f128) ? RTLIB::OEQ_F128 : RTLIB::OEQ_PPCF128;
228  break;
229  default:
230  // Invert CC for unordered comparisons
231  ShouldInvertCC = true;
232  switch (CCCode) {
233  case ISD::SETULT:
234  LC1 = (VT == MVT::f32) ? RTLIB::OGE_F32 :
235  (VT == MVT::f64) ? RTLIB::OGE_F64 :
236  (VT == MVT::f128) ? RTLIB::OGE_F128 : RTLIB::OGE_PPCF128;
237  break;
238  case ISD::SETULE:
239  LC1 = (VT == MVT::f32) ? RTLIB::OGT_F32 :
240  (VT == MVT::f64) ? RTLIB::OGT_F64 :
241  (VT == MVT::f128) ? RTLIB::OGT_F128 : RTLIB::OGT_PPCF128;
242  break;
243  case ISD::SETUGT:
244  LC1 = (VT == MVT::f32) ? RTLIB::OLE_F32 :
245  (VT == MVT::f64) ? RTLIB::OLE_F64 :
246  (VT == MVT::f128) ? RTLIB::OLE_F128 : RTLIB::OLE_PPCF128;
247  break;
248  case ISD::SETUGE:
249  LC1 = (VT == MVT::f32) ? RTLIB::OLT_F32 :
250  (VT == MVT::f64) ? RTLIB::OLT_F64 :
251  (VT == MVT::f128) ? RTLIB::OLT_F128 : RTLIB::OLT_PPCF128;
252  break;
253  default: llvm_unreachable("Do not know how to soften this setcc!");
254  }
255  }
256 
257  // Use the target specific return value for comparions lib calls.
258  EVT RetVT = getCmpLibcallReturnType();
259  SDValue Ops[2] = {NewLHS, NewRHS};
260  NewLHS = makeLibCall(DAG, LC1, RetVT, Ops, false /*sign irrelevant*/,
261  dl).first;
262  NewRHS = DAG.getConstant(0, dl, RetVT);
263 
264  CCCode = getCmpLibcallCC(LC1);
265  if (ShouldInvertCC)
266  CCCode = getSetCCInverse(CCCode, /*isInteger=*/true);
267 
268  if (LC2 != RTLIB::UNKNOWN_LIBCALL) {
269  SDValue Tmp = DAG.getNode(
270  ISD::SETCC, dl,
271  getSetCCResultType(DAG.getDataLayout(), *DAG.getContext(), RetVT),
272  NewLHS, NewRHS, DAG.getCondCode(CCCode));
273  NewLHS = makeLibCall(DAG, LC2, RetVT, Ops, false/*sign irrelevant*/,
274  dl).first;
275  NewLHS = DAG.getNode(
276  ISD::SETCC, dl,
277  getSetCCResultType(DAG.getDataLayout(), *DAG.getContext(), RetVT),
278  NewLHS, NewRHS, DAG.getCondCode(getCmpLibcallCC(LC2)));
279  NewLHS = DAG.getNode(ISD::OR, dl, Tmp.getValueType(), Tmp, NewLHS);
280  NewRHS = SDValue();
281  }
282 }
283 
284 /// Return the entry encoding for a jump table in the current function. The
285 /// returned value is a member of the MachineJumpTableInfo::JTEntryKind enum.
287  // In non-pic modes, just use the address of a block.
288  if (!isPositionIndependent())
290 
291  // In PIC mode, if the target supports a GPRel32 directive, use it.
292  if (getTargetMachine().getMCAsmInfo()->getGPRel32Directive() != nullptr)
294 
295  // Otherwise, use a label difference.
297 }
298 
300  SelectionDAG &DAG) const {
301  // If our PIC model is GP relative, use the global offset table as the base.
302  unsigned JTEncoding = getJumpTableEncoding();
303 
304  if ((JTEncoding == MachineJumpTableInfo::EK_GPRel64BlockAddress) ||
307 
308  return Table;
309 }
310 
311 /// This returns the relocation base for the given PIC jumptable, the same as
312 /// getPICJumpTableRelocBase, but as an MCExpr.
313 const MCExpr *
315  unsigned JTI,MCContext &Ctx) const{
316  // The normal PIC reloc base is the label at the start of the jump table.
317  return MCSymbolRefExpr::create(MF->getJTISymbol(JTI, Ctx), Ctx);
318 }
319 
320 bool
322  const TargetMachine &TM = getTargetMachine();
323  const GlobalValue *GV = GA->getGlobal();
324 
325  // If the address is not even local to this DSO we will have to load it from
326  // a got and then add the offset.
327  if (!TM.shouldAssumeDSOLocal(*GV->getParent(), GV))
328  return false;
329 
330  // If the code is position independent we will have to add a base register.
331  if (isPositionIndependent())
332  return false;
333 
334  // Otherwise we can do it.
335  return true;
336 }
337 
338 //===----------------------------------------------------------------------===//
339 // Optimization Methods
340 //===----------------------------------------------------------------------===//
341 
342 /// If the specified instruction has a constant integer operand and there are
343 /// bits set in that constant that are not demanded, then clear those bits and
344 /// return true.
346  TargetLoweringOpt &TLO) const {
347  SelectionDAG &DAG = TLO.DAG;
348  SDLoc DL(Op);
349  unsigned Opcode = Op.getOpcode();
350 
351  // Do target-specific constant optimization.
352  if (targetShrinkDemandedConstant(Op, Demanded, TLO))
353  return TLO.New.getNode();
354 
355  // FIXME: ISD::SELECT, ISD::SELECT_CC
356  switch (Opcode) {
357  default:
358  break;
359  case ISD::XOR:
360  case ISD::AND:
361  case ISD::OR: {
362  auto *Op1C = dyn_cast<ConstantSDNode>(Op.getOperand(1));
363  if (!Op1C)
364  return false;
365 
366  // If this is a 'not' op, don't touch it because that's a canonical form.
367  const APInt &C = Op1C->getAPIntValue();
368  if (Opcode == ISD::XOR && Demanded.isSubsetOf(C))
369  return false;
370 
371  if (!C.isSubsetOf(Demanded)) {
372  EVT VT = Op.getValueType();
373  SDValue NewC = DAG.getConstant(Demanded & C, DL, VT);
374  SDValue NewOp = DAG.getNode(Opcode, DL, VT, Op.getOperand(0), NewC);
375  return TLO.CombineTo(Op, NewOp);
376  }
377 
378  break;
379  }
380  }
381 
382  return false;
383 }
384 
385 /// Convert x+y to (VT)((SmallVT)x+(SmallVT)y) if the casts are free.
386 /// This uses isZExtFree and ZERO_EXTEND for the widening cast, but it could be
387 /// generalized for targets with other types of implicit widening casts.
389  const APInt &Demanded,
390  TargetLoweringOpt &TLO) const {
391  assert(Op.getNumOperands() == 2 &&
392  "ShrinkDemandedOp only supports binary operators!");
393  assert(Op.getNode()->getNumValues() == 1 &&
394  "ShrinkDemandedOp only supports nodes with one result!");
395 
396  SelectionDAG &DAG = TLO.DAG;
397  SDLoc dl(Op);
398 
399  // Early return, as this function cannot handle vector types.
400  if (Op.getValueType().isVector())
401  return false;
402 
403  // Don't do this if the node has another user, which may require the
404  // full value.
405  if (!Op.getNode()->hasOneUse())
406  return false;
407 
408  // Search for the smallest integer type with free casts to and from
409  // Op's type. For expedience, just check power-of-2 integer types.
410  const TargetLowering &TLI = DAG.getTargetLoweringInfo();
411  unsigned DemandedSize = BitWidth - Demanded.countLeadingZeros();
412  unsigned SmallVTBits = DemandedSize;
413  if (!isPowerOf2_32(SmallVTBits))
414  SmallVTBits = NextPowerOf2(SmallVTBits);
415  for (; SmallVTBits < BitWidth; SmallVTBits = NextPowerOf2(SmallVTBits)) {
416  EVT SmallVT = EVT::getIntegerVT(*DAG.getContext(), SmallVTBits);
417  if (TLI.isTruncateFree(Op.getValueType(), SmallVT) &&
418  TLI.isZExtFree(SmallVT, Op.getValueType())) {
419  // We found a type with free casts.
420  SDValue X = DAG.getNode(
421  Op.getOpcode(), dl, SmallVT,
422  DAG.getNode(ISD::TRUNCATE, dl, SmallVT, Op.getOperand(0)),
423  DAG.getNode(ISD::TRUNCATE, dl, SmallVT, Op.getOperand(1)));
424  bool NeedZext = DemandedSize > SmallVTBits;
425  SDValue Z = DAG.getNode(NeedZext ? ISD::ZERO_EXTEND : ISD::ANY_EXTEND,
426  dl, Op.getValueType(), X);
427  return TLO.CombineTo(Op, Z);
428  }
429  }
430  return false;
431 }
432 
433 bool
435  const APInt &Demanded,
436  DAGCombinerInfo &DCI,
437  TargetLoweringOpt &TLO) const {
438  SDValue Op = User->getOperand(OpIdx);
439  KnownBits Known;
440 
441  if (!SimplifyDemandedBits(Op, Demanded, Known, TLO, 0, true))
442  return false;
443 
444 
445  // Old will not always be the same as Op. For example:
446  //
447  // Demanded = 0xffffff
448  // Op = i64 truncate (i32 and x, 0xffffff)
449  // In this case simplify demand bits will want to replace the 'and' node
450  // with the value 'x', which will give us:
451  // Old = i32 and x, 0xffffff
452  // New = x
453  if (TLO.Old.hasOneUse()) {
454  // For the one use case, we just commit the change.
455  DCI.CommitTargetLoweringOpt(TLO);
456  return true;
457  }
458 
459  // If Old has more than one use then it must be Op, because the
460  // AssumeSingleUse flag is not propogated to recursive calls of
461  // SimplifyDemanded bits, so the only node with multiple use that
462  // it will attempt to combine will be opt.
463  assert(TLO.Old == Op);
464 
466  for (unsigned i = 0, e = User->getNumOperands(); i != e; ++i) {
467  if (i == OpIdx) {
468  NewOps.push_back(TLO.New);
469  continue;
470  }
471  NewOps.push_back(User->getOperand(i));
472  }
473  TLO.DAG.UpdateNodeOperands(User, NewOps);
474  // Op has less users now, so we may be able to perform additional combines
475  // with it.
476  DCI.AddToWorklist(Op.getNode());
477  // User's operands have been updated, so we may be able to do new combines
478  // with it.
479  DCI.AddToWorklist(User);
480  return true;
481 }
482 
484  DAGCombinerInfo &DCI) const {
485 
486  SelectionDAG &DAG = DCI.DAG;
487  TargetLoweringOpt TLO(DAG, !DCI.isBeforeLegalize(),
488  !DCI.isBeforeLegalizeOps());
489  KnownBits Known;
490 
491  bool Simplified = SimplifyDemandedBits(Op, DemandedMask, Known, TLO);
492  if (Simplified)
493  DCI.CommitTargetLoweringOpt(TLO);
494  return Simplified;
495 }
496 
497 /// Look at Op. At this point, we know that only the DemandedMask bits of the
498 /// result of Op are ever used downstream. If we can use this information to
499 /// simplify Op, create a new simplified DAG node and return true, returning the
500 /// original and new nodes in Old and New. Otherwise, analyze the expression and
501 /// return a mask of Known bits for the expression (used to simplify the
502 /// caller). The Known bits may only be accurate for those bits in the
503 /// DemandedMask.
505  const APInt &DemandedMask,
506  KnownBits &Known,
507  TargetLoweringOpt &TLO,
508  unsigned Depth,
509  bool AssumeSingleUse) const {
510  unsigned BitWidth = DemandedMask.getBitWidth();
511  assert(Op.getScalarValueSizeInBits() == BitWidth &&
512  "Mask size mismatches value type size!");
513  APInt NewMask = DemandedMask;
514  SDLoc dl(Op);
515  auto &DL = TLO.DAG.getDataLayout();
516 
517  // Don't know anything.
518  Known = KnownBits(BitWidth);
519 
520  // Other users may use these bits.
521  if (!Op.getNode()->hasOneUse() && !AssumeSingleUse) {
522  if (Depth != 0) {
523  // If not at the root, Just compute the Known bits to
524  // simplify things downstream.
525  TLO.DAG.computeKnownBits(Op, Known, Depth);
526  return false;
527  }
528  // If this is the root being simplified, allow it to have multiple uses,
529  // just set the NewMask to all bits.
530  NewMask = APInt::getAllOnesValue(BitWidth);
531  } else if (DemandedMask == 0) {
532  // Not demanding any bits from Op.
533  if (!Op.isUndef())
534  return TLO.CombineTo(Op, TLO.DAG.getUNDEF(Op.getValueType()));
535  return false;
536  } else if (Depth == 6) { // Limit search depth.
537  return false;
538  }
539 
540  KnownBits Known2, KnownOut;
541  switch (Op.getOpcode()) {
542  case ISD::Constant:
543  // We know all of the bits for a constant!
544  Known.One = cast<ConstantSDNode>(Op)->getAPIntValue();
545  Known.Zero = ~Known.One;
546  return false; // Don't fall through, will infinitely loop.
547  case ISD::BUILD_VECTOR:
548  // Collect the known bits that are shared by every constant vector element.
549  Known.Zero.setAllBits(); Known.One.setAllBits();
550  for (SDValue SrcOp : Op->ops()) {
551  if (!isa<ConstantSDNode>(SrcOp)) {
552  // We can only handle all constant values - bail out with no known bits.
553  Known = KnownBits(BitWidth);
554  return false;
555  }
556  Known2.One = cast<ConstantSDNode>(SrcOp)->getAPIntValue();
557  Known2.Zero = ~Known2.One;
558 
559  // BUILD_VECTOR can implicitly truncate sources, we must handle this.
560  if (Known2.One.getBitWidth() != BitWidth) {
561  assert(Known2.getBitWidth() > BitWidth &&
562  "Expected BUILD_VECTOR implicit truncation");
563  Known2 = Known2.trunc(BitWidth);
564  }
565 
566  // Known bits are the values that are shared by every element.
567  // TODO: support per-element known bits.
568  Known.One &= Known2.One;
569  Known.Zero &= Known2.Zero;
570  }
571  return false; // Don't fall through, will infinitely loop.
572  case ISD::AND:
573  // If the RHS is a constant, check to see if the LHS would be zero without
574  // using the bits from the RHS. Below, we use knowledge about the RHS to
575  // simplify the LHS, here we're using information from the LHS to simplify
576  // the RHS.
577  if (ConstantSDNode *RHSC = isConstOrConstSplat(Op.getOperand(1))) {
578  SDValue Op0 = Op.getOperand(0);
579  KnownBits LHSKnown;
580  // Do not increment Depth here; that can cause an infinite loop.
581  TLO.DAG.computeKnownBits(Op0, LHSKnown, Depth);
582  // If the LHS already has zeros where RHSC does, this and is dead.
583  if ((LHSKnown.Zero & NewMask) == (~RHSC->getAPIntValue() & NewMask))
584  return TLO.CombineTo(Op, Op0);
585 
586  // If any of the set bits in the RHS are known zero on the LHS, shrink
587  // the constant.
588  if (ShrinkDemandedConstant(Op, ~LHSKnown.Zero & NewMask, TLO))
589  return true;
590 
591  // Bitwise-not (xor X, -1) is a special case: we don't usually shrink its
592  // constant, but if this 'and' is only clearing bits that were just set by
593  // the xor, then this 'and' can be eliminated by shrinking the mask of
594  // the xor. For example, for a 32-bit X:
595  // and (xor (srl X, 31), -1), 1 --> xor (srl X, 31), 1
596  if (isBitwiseNot(Op0) && Op0.hasOneUse() &&
597  LHSKnown.One == ~RHSC->getAPIntValue()) {
598  SDValue Xor = TLO.DAG.getNode(ISD::XOR, dl, Op.getValueType(),
599  Op0.getOperand(0), Op.getOperand(1));
600  return TLO.CombineTo(Op, Xor);
601  }
602  }
603 
604  if (SimplifyDemandedBits(Op.getOperand(1), NewMask, Known, TLO, Depth+1))
605  return true;
606  assert(!Known.hasConflict() && "Bits known to be one AND zero?");
607  if (SimplifyDemandedBits(Op.getOperand(0), ~Known.Zero & NewMask,
608  Known2, TLO, Depth+1))
609  return true;
610  assert(!Known2.hasConflict() && "Bits known to be one AND zero?");
611 
612  // If all of the demanded bits are known one on one side, return the other.
613  // These bits cannot contribute to the result of the 'and'.
614  if (NewMask.isSubsetOf(Known2.Zero | Known.One))
615  return TLO.CombineTo(Op, Op.getOperand(0));
616  if (NewMask.isSubsetOf(Known.Zero | Known2.One))
617  return TLO.CombineTo(Op, Op.getOperand(1));
618  // If all of the demanded bits in the inputs are known zeros, return zero.
619  if (NewMask.isSubsetOf(Known.Zero | Known2.Zero))
620  return TLO.CombineTo(Op, TLO.DAG.getConstant(0, dl, Op.getValueType()));
621  // If the RHS is a constant, see if we can simplify it.
622  if (ShrinkDemandedConstant(Op, ~Known2.Zero & NewMask, TLO))
623  return true;
624  // If the operation can be done in a smaller type, do so.
625  if (ShrinkDemandedOp(Op, BitWidth, NewMask, TLO))
626  return true;
627 
628  // Output known-1 bits are only known if set in both the LHS & RHS.
629  Known.One &= Known2.One;
630  // Output known-0 are known to be clear if zero in either the LHS | RHS.
631  Known.Zero |= Known2.Zero;
632  break;
633  case ISD::OR:
634  if (SimplifyDemandedBits(Op.getOperand(1), NewMask, Known, TLO, Depth+1))
635  return true;
636  assert(!Known.hasConflict() && "Bits known to be one AND zero?");
637  if (SimplifyDemandedBits(Op.getOperand(0), ~Known.One & NewMask,
638  Known2, TLO, Depth+1))
639  return true;
640  assert(!Known2.hasConflict() && "Bits known to be one AND zero?");
641 
642  // If all of the demanded bits are known zero on one side, return the other.
643  // These bits cannot contribute to the result of the 'or'.
644  if (NewMask.isSubsetOf(Known2.One | Known.Zero))
645  return TLO.CombineTo(Op, Op.getOperand(0));
646  if (NewMask.isSubsetOf(Known.One | Known2.Zero))
647  return TLO.CombineTo(Op, Op.getOperand(1));
648  // If the RHS is a constant, see if we can simplify it.
649  if (ShrinkDemandedConstant(Op, NewMask, TLO))
650  return true;
651  // If the operation can be done in a smaller type, do so.
652  if (ShrinkDemandedOp(Op, BitWidth, NewMask, TLO))
653  return true;
654 
655  // Output known-0 bits are only known if clear in both the LHS & RHS.
656  Known.Zero &= Known2.Zero;
657  // Output known-1 are known to be set if set in either the LHS | RHS.
658  Known.One |= Known2.One;
659  break;
660  case ISD::XOR: {
661  if (SimplifyDemandedBits(Op.getOperand(1), NewMask, Known, TLO, Depth+1))
662  return true;
663  assert(!Known.hasConflict() && "Bits known to be one AND zero?");
664  if (SimplifyDemandedBits(Op.getOperand(0), NewMask, Known2, TLO, Depth+1))
665  return true;
666  assert(!Known2.hasConflict() && "Bits known to be one AND zero?");
667 
668  // If all of the demanded bits are known zero on one side, return the other.
669  // These bits cannot contribute to the result of the 'xor'.
670  if (NewMask.isSubsetOf(Known.Zero))
671  return TLO.CombineTo(Op, Op.getOperand(0));
672  if (NewMask.isSubsetOf(Known2.Zero))
673  return TLO.CombineTo(Op, Op.getOperand(1));
674  // If the operation can be done in a smaller type, do so.
675  if (ShrinkDemandedOp(Op, BitWidth, NewMask, TLO))
676  return true;
677 
678  // If all of the unknown bits are known to be zero on one side or the other
679  // (but not both) turn this into an *inclusive* or.
680  // e.g. (A & C1)^(B & C2) -> (A & C1)|(B & C2) iff C1&C2 == 0
681  if ((NewMask & ~Known.Zero & ~Known2.Zero) == 0)
682  return TLO.CombineTo(Op, TLO.DAG.getNode(ISD::OR, dl, Op.getValueType(),
683  Op.getOperand(0),
684  Op.getOperand(1)));
685 
686  // Output known-0 bits are known if clear or set in both the LHS & RHS.
687  KnownOut.Zero = (Known.Zero & Known2.Zero) | (Known.One & Known2.One);
688  // Output known-1 are known to be set if set in only one of the LHS, RHS.
689  KnownOut.One = (Known.Zero & Known2.One) | (Known.One & Known2.Zero);
690 
691  // If all of the demanded bits on one side are known, and all of the set
692  // bits on that side are also known to be set on the other side, turn this
693  // into an AND, as we know the bits will be cleared.
694  // e.g. (X | C1) ^ C2 --> (X | C1) & ~C2 iff (C1&C2) == C2
695  // NB: it is okay if more bits are known than are requested
696  if (NewMask.isSubsetOf(Known.Zero|Known.One)) { // all known on one side
697  if (Known.One == Known2.One) { // set bits are the same on both sides
698  EVT VT = Op.getValueType();
699  SDValue ANDC = TLO.DAG.getConstant(~Known.One & NewMask, dl, VT);
700  return TLO.CombineTo(Op, TLO.DAG.getNode(ISD::AND, dl, VT,
701  Op.getOperand(0), ANDC));
702  }
703  }
704 
705  // If the RHS is a constant, see if we can change it. Don't alter a -1
706  // constant because that's a 'not' op, and that is better for combining and
707  // codegen.
709  if (C && !C->isAllOnesValue()) {
710  if (NewMask.isSubsetOf(C->getAPIntValue())) {
711  // We're flipping all demanded bits. Flip the undemanded bits too.
712  SDValue New = TLO.DAG.getNOT(dl, Op.getOperand(0), Op.getValueType());
713  return TLO.CombineTo(Op, New);
714  }
715  // If we can't turn this into a 'not', try to shrink the constant.
716  if (ShrinkDemandedConstant(Op, NewMask, TLO))
717  return true;
718  }
719 
720  Known = std::move(KnownOut);
721  break;
722  }
723  case ISD::SELECT:
724  if (SimplifyDemandedBits(Op.getOperand(2), NewMask, Known, TLO, Depth+1))
725  return true;
726  if (SimplifyDemandedBits(Op.getOperand(1), NewMask, Known2, TLO, Depth+1))
727  return true;
728  assert(!Known.hasConflict() && "Bits known to be one AND zero?");
729  assert(!Known2.hasConflict() && "Bits known to be one AND zero?");
730 
731  // If the operands are constants, see if we can simplify them.
732  if (ShrinkDemandedConstant(Op, NewMask, TLO))
733  return true;
734 
735  // Only known if known in both the LHS and RHS.
736  Known.One &= Known2.One;
737  Known.Zero &= Known2.Zero;
738  break;
739  case ISD::SELECT_CC:
740  if (SimplifyDemandedBits(Op.getOperand(3), NewMask, Known, TLO, Depth+1))
741  return true;
742  if (SimplifyDemandedBits(Op.getOperand(2), NewMask, Known2, TLO, Depth+1))
743  return true;
744  assert(!Known.hasConflict() && "Bits known to be one AND zero?");
745  assert(!Known2.hasConflict() && "Bits known to be one AND zero?");
746 
747  // If the operands are constants, see if we can simplify them.
748  if (ShrinkDemandedConstant(Op, NewMask, TLO))
749  return true;
750 
751  // Only known if known in both the LHS and RHS.
752  Known.One &= Known2.One;
753  Known.Zero &= Known2.Zero;
754  break;
755  case ISD::SETCC: {
756  SDValue Op0 = Op.getOperand(0);
757  SDValue Op1 = Op.getOperand(1);
758  ISD::CondCode CC = cast<CondCodeSDNode>(Op.getOperand(2))->get();
759  // If (1) we only need the sign-bit, (2) the setcc operands are the same
760  // width as the setcc result, and (3) the result of a setcc conforms to 0 or
761  // -1, we may be able to bypass the setcc.
762  if (NewMask.isSignMask() && Op0.getScalarValueSizeInBits() == BitWidth &&
764  BooleanContent::ZeroOrNegativeOneBooleanContent) {
765  // If we're testing X < 0, then this compare isn't needed - just use X!
766  // FIXME: We're limiting to integer types here, but this should also work
767  // if we don't care about FP signed-zero. The use of SETLT with FP means
768  // that we don't care about NaNs.
769  if (CC == ISD::SETLT && Op1.getValueType().isInteger() &&
771  return TLO.CombineTo(Op, Op0);
772 
773  // TODO: Should we check for other forms of sign-bit comparisons?
774  // Examples: X <= -1, X >= 0
775  }
776  if (getBooleanContents(Op0.getValueType()) ==
778  BitWidth > 1)
779  Known.Zero.setBitsFrom(1);
780  break;
781  }
782  case ISD::SHL:
783  if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
784  unsigned ShAmt = SA->getZExtValue();
785  SDValue InOp = Op.getOperand(0);
786 
787  // If the shift count is an invalid immediate, don't do anything.
788  if (ShAmt >= BitWidth)
789  break;
790 
791  // If this is ((X >>u C1) << ShAmt), see if we can simplify this into a
792  // single shift. We can do this if the bottom bits (which are shifted
793  // out) are never demanded.
794  if (InOp.getOpcode() == ISD::SRL &&
795  isa<ConstantSDNode>(InOp.getOperand(1))) {
796  if (ShAmt && (NewMask & APInt::getLowBitsSet(BitWidth, ShAmt)) == 0) {
797  unsigned C1= cast<ConstantSDNode>(InOp.getOperand(1))->getZExtValue();
798  unsigned Opc = ISD::SHL;
799  int Diff = ShAmt-C1;
800  if (Diff < 0) {
801  Diff = -Diff;
802  Opc = ISD::SRL;
803  }
804 
805  SDValue NewSA =
806  TLO.DAG.getConstant(Diff, dl, Op.getOperand(1).getValueType());
807  EVT VT = Op.getValueType();
808  return TLO.CombineTo(Op, TLO.DAG.getNode(Opc, dl, VT,
809  InOp.getOperand(0), NewSA));
810  }
811  }
812 
813  if (SimplifyDemandedBits(InOp, NewMask.lshr(ShAmt), Known, TLO, Depth+1))
814  return true;
815 
816  // Convert (shl (anyext x, c)) to (anyext (shl x, c)) if the high bits
817  // are not demanded. This will likely allow the anyext to be folded away.
818  if (InOp.getNode()->getOpcode() == ISD::ANY_EXTEND) {
819  SDValue InnerOp = InOp.getOperand(0);
820  EVT InnerVT = InnerOp.getValueType();
821  unsigned InnerBits = InnerVT.getSizeInBits();
822  if (ShAmt < InnerBits && NewMask.getActiveBits() <= InnerBits &&
823  isTypeDesirableForOp(ISD::SHL, InnerVT)) {
824  EVT ShTy = getShiftAmountTy(InnerVT, DL);
825  if (!APInt(BitWidth, ShAmt).isIntN(ShTy.getSizeInBits()))
826  ShTy = InnerVT;
827  SDValue NarrowShl =
828  TLO.DAG.getNode(ISD::SHL, dl, InnerVT, InnerOp,
829  TLO.DAG.getConstant(ShAmt, dl, ShTy));
830  return
831  TLO.CombineTo(Op,
832  TLO.DAG.getNode(ISD::ANY_EXTEND, dl, Op.getValueType(),
833  NarrowShl));
834  }
835  // Repeat the SHL optimization above in cases where an extension
836  // intervenes: (shl (anyext (shr x, c1)), c2) to
837  // (shl (anyext x), c2-c1). This requires that the bottom c1 bits
838  // aren't demanded (as above) and that the shifted upper c1 bits of
839  // x aren't demanded.
840  if (InOp.hasOneUse() &&
841  InnerOp.getOpcode() == ISD::SRL &&
842  InnerOp.hasOneUse() &&
843  isa<ConstantSDNode>(InnerOp.getOperand(1))) {
844  unsigned InnerShAmt = cast<ConstantSDNode>(InnerOp.getOperand(1))
845  ->getZExtValue();
846  if (InnerShAmt < ShAmt &&
847  InnerShAmt < InnerBits &&
848  NewMask.getActiveBits() <= (InnerBits - InnerShAmt + ShAmt) &&
849  NewMask.countTrailingZeros() >= ShAmt) {
850  SDValue NewSA =
851  TLO.DAG.getConstant(ShAmt - InnerShAmt, dl,
852  Op.getOperand(1).getValueType());
853  EVT VT = Op.getValueType();
854  SDValue NewExt = TLO.DAG.getNode(ISD::ANY_EXTEND, dl, VT,
855  InnerOp.getOperand(0));
856  return TLO.CombineTo(Op, TLO.DAG.getNode(ISD::SHL, dl, VT,
857  NewExt, NewSA));
858  }
859  }
860  }
861 
862  Known.Zero <<= SA->getZExtValue();
863  Known.One <<= SA->getZExtValue();
864  // low bits known zero.
865  Known.Zero.setLowBits(SA->getZExtValue());
866  }
867  break;
868  case ISD::SRL:
869  if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
870  EVT VT = Op.getValueType();
871  unsigned ShAmt = SA->getZExtValue();
872  unsigned VTSize = VT.getSizeInBits();
873  SDValue InOp = Op.getOperand(0);
874 
875  // If the shift count is an invalid immediate, don't do anything.
876  if (ShAmt >= BitWidth)
877  break;
878 
879  APInt InDemandedMask = (NewMask << ShAmt);
880 
881  // If the shift is exact, then it does demand the low bits (and knows that
882  // they are zero).
883  if (Op->getFlags().hasExact())
884  InDemandedMask.setLowBits(ShAmt);
885 
886  // If this is ((X << C1) >>u ShAmt), see if we can simplify this into a
887  // single shift. We can do this if the top bits (which are shifted out)
888  // are never demanded.
889  if (InOp.getOpcode() == ISD::SHL &&
890  isa<ConstantSDNode>(InOp.getOperand(1))) {
891  if (ShAmt && (NewMask & APInt::getHighBitsSet(VTSize, ShAmt)) == 0) {
892  unsigned C1= cast<ConstantSDNode>(InOp.getOperand(1))->getZExtValue();
893  unsigned Opc = ISD::SRL;
894  int Diff = ShAmt-C1;
895  if (Diff < 0) {
896  Diff = -Diff;
897  Opc = ISD::SHL;
898  }
899 
900  SDValue NewSA =
901  TLO.DAG.getConstant(Diff, dl, Op.getOperand(1).getValueType());
902  return TLO.CombineTo(Op, TLO.DAG.getNode(Opc, dl, VT,
903  InOp.getOperand(0), NewSA));
904  }
905  }
906 
907  // Compute the new bits that are at the top now.
908  if (SimplifyDemandedBits(InOp, InDemandedMask, Known, TLO, Depth+1))
909  return true;
910  assert(!Known.hasConflict() && "Bits known to be one AND zero?");
911  Known.Zero.lshrInPlace(ShAmt);
912  Known.One.lshrInPlace(ShAmt);
913 
914  Known.Zero.setHighBits(ShAmt); // High bits known zero.
915  }
916  break;
917  case ISD::SRA:
918  // If this is an arithmetic shift right and only the low-bit is set, we can
919  // always convert this into a logical shr, even if the shift amount is
920  // variable. The low bit of the shift cannot be an input sign bit unless
921  // the shift amount is >= the size of the datatype, which is undefined.
922  if (NewMask.isOneValue())
923  return TLO.CombineTo(Op,
924  TLO.DAG.getNode(ISD::SRL, dl, Op.getValueType(),
925  Op.getOperand(0), Op.getOperand(1)));
926 
927  if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
928  EVT VT = Op.getValueType();
929  unsigned ShAmt = SA->getZExtValue();
930 
931  // If the shift count is an invalid immediate, don't do anything.
932  if (ShAmt >= BitWidth)
933  break;
934 
935  APInt InDemandedMask = (NewMask << ShAmt);
936 
937  // If the shift is exact, then it does demand the low bits (and knows that
938  // they are zero).
939  if (Op->getFlags().hasExact())
940  InDemandedMask.setLowBits(ShAmt);
941 
942  // If any of the demanded bits are produced by the sign extension, we also
943  // demand the input sign bit.
944  if (NewMask.countLeadingZeros() < ShAmt)
945  InDemandedMask.setSignBit();
946 
947  if (SimplifyDemandedBits(Op.getOperand(0), InDemandedMask, Known, TLO,
948  Depth+1))
949  return true;
950  assert(!Known.hasConflict() && "Bits known to be one AND zero?");
951  Known.Zero.lshrInPlace(ShAmt);
952  Known.One.lshrInPlace(ShAmt);
953 
954  // If the input sign bit is known to be zero, or if none of the top bits
955  // are demanded, turn this into an unsigned shift right.
956  if (Known.Zero[BitWidth - ShAmt - 1] ||
957  NewMask.countLeadingZeros() >= ShAmt) {
959  Flags.setExact(Op->getFlags().hasExact());
960  return TLO.CombineTo(Op,
961  TLO.DAG.getNode(ISD::SRL, dl, VT, Op.getOperand(0),
962  Op.getOperand(1), Flags));
963  }
964 
965  int Log2 = NewMask.exactLogBase2();
966  if (Log2 >= 0) {
967  // The bit must come from the sign.
968  SDValue NewSA =
969  TLO.DAG.getConstant(BitWidth - 1 - Log2, dl,
970  Op.getOperand(1).getValueType());
971  return TLO.CombineTo(Op, TLO.DAG.getNode(ISD::SRL, dl, VT,
972  Op.getOperand(0), NewSA));
973  }
974 
975  if (Known.One[BitWidth - ShAmt - 1])
976  // New bits are known one.
977  Known.One.setHighBits(ShAmt);
978  }
979  break;
980  case ISD::SIGN_EXTEND_INREG: {
981  EVT ExVT = cast<VTSDNode>(Op.getOperand(1))->getVT();
982 
983  APInt MsbMask = APInt::getHighBitsSet(BitWidth, 1);
984  // If we only care about the highest bit, don't bother shifting right.
985  if (MsbMask == NewMask) {
986  unsigned ShAmt = ExVT.getScalarSizeInBits();
987  SDValue InOp = Op.getOperand(0);
988  unsigned VTBits = Op->getValueType(0).getScalarSizeInBits();
989  bool AlreadySignExtended =
990  TLO.DAG.ComputeNumSignBits(InOp) >= VTBits-ShAmt+1;
991  // However if the input is already sign extended we expect the sign
992  // extension to be dropped altogether later and do not simplify.
993  if (!AlreadySignExtended) {
994  // Compute the correct shift amount type, which must be getShiftAmountTy
995  // for scalar types after legalization.
996  EVT ShiftAmtTy = Op.getValueType();
997  if (TLO.LegalTypes() && !ShiftAmtTy.isVector())
998  ShiftAmtTy = getShiftAmountTy(ShiftAmtTy, DL);
999 
1000  SDValue ShiftAmt = TLO.DAG.getConstant(BitWidth - ShAmt, dl,
1001  ShiftAmtTy);
1002  return TLO.CombineTo(Op, TLO.DAG.getNode(ISD::SHL, dl,
1003  Op.getValueType(), InOp,
1004  ShiftAmt));
1005  }
1006  }
1007 
1008  // Sign extension. Compute the demanded bits in the result that are not
1009  // present in the input.
1010  APInt NewBits =
1011  APInt::getHighBitsSet(BitWidth,
1012  BitWidth - ExVT.getScalarSizeInBits());
1013 
1014  // If none of the extended bits are demanded, eliminate the sextinreg.
1015  if ((NewBits & NewMask) == 0)
1016  return TLO.CombineTo(Op, Op.getOperand(0));
1017 
1018  APInt InSignBit =
1019  APInt::getSignMask(ExVT.getScalarSizeInBits()).zext(BitWidth);
1020  APInt InputDemandedBits =
1021  APInt::getLowBitsSet(BitWidth,
1022  ExVT.getScalarSizeInBits()) &
1023  NewMask;
1024 
1025  // Since the sign extended bits are demanded, we know that the sign
1026  // bit is demanded.
1027  InputDemandedBits |= InSignBit;
1028 
1029  if (SimplifyDemandedBits(Op.getOperand(0), InputDemandedBits,
1030  Known, TLO, Depth+1))
1031  return true;
1032  assert(!Known.hasConflict() && "Bits known to be one AND zero?");
1033 
1034  // If the sign bit of the input is known set or clear, then we know the
1035  // top bits of the result.
1036 
1037  // If the input sign bit is known zero, convert this into a zero extension.
1038  if (Known.Zero.intersects(InSignBit))
1039  return TLO.CombineTo(Op, TLO.DAG.getZeroExtendInReg(
1040  Op.getOperand(0), dl, ExVT.getScalarType()));
1041 
1042  if (Known.One.intersects(InSignBit)) { // Input sign bit known set
1043  Known.One |= NewBits;
1044  Known.Zero &= ~NewBits;
1045  } else { // Input sign bit unknown
1046  Known.Zero &= ~NewBits;
1047  Known.One &= ~NewBits;
1048  }
1049  break;
1050  }
1051  case ISD::BUILD_PAIR: {
1052  EVT HalfVT = Op.getOperand(0).getValueType();
1053  unsigned HalfBitWidth = HalfVT.getScalarSizeInBits();
1054 
1055  APInt MaskLo = NewMask.getLoBits(HalfBitWidth).trunc(HalfBitWidth);
1056  APInt MaskHi = NewMask.getHiBits(HalfBitWidth).trunc(HalfBitWidth);
1057 
1058  KnownBits KnownLo, KnownHi;
1059 
1060  if (SimplifyDemandedBits(Op.getOperand(0), MaskLo, KnownLo, TLO, Depth + 1))
1061  return true;
1062 
1063  if (SimplifyDemandedBits(Op.getOperand(1), MaskHi, KnownHi, TLO, Depth + 1))
1064  return true;
1065 
1066  Known.Zero = KnownLo.Zero.zext(BitWidth) |
1067  KnownHi.Zero.zext(BitWidth).shl(HalfBitWidth);
1068 
1069  Known.One = KnownLo.One.zext(BitWidth) |
1070  KnownHi.One.zext(BitWidth).shl(HalfBitWidth);
1071  break;
1072  }
1073  case ISD::ZERO_EXTEND: {
1074  unsigned OperandBitWidth = Op.getOperand(0).getScalarValueSizeInBits();
1075  APInt InMask = NewMask.trunc(OperandBitWidth);
1076 
1077  // If none of the top bits are demanded, convert this into an any_extend.
1078  APInt NewBits =
1079  APInt::getHighBitsSet(BitWidth, BitWidth - OperandBitWidth) & NewMask;
1080  if (!NewBits.intersects(NewMask))
1081  return TLO.CombineTo(Op, TLO.DAG.getNode(ISD::ANY_EXTEND, dl,
1082  Op.getValueType(),
1083  Op.getOperand(0)));
1084 
1085  if (SimplifyDemandedBits(Op.getOperand(0), InMask, Known, TLO, Depth+1))
1086  return true;
1087  assert(!Known.hasConflict() && "Bits known to be one AND zero?");
1088  Known = Known.zext(BitWidth);
1089  Known.Zero |= NewBits;
1090  break;
1091  }
1092  case ISD::SIGN_EXTEND: {
1093  EVT InVT = Op.getOperand(0).getValueType();
1094  unsigned InBits = InVT.getScalarSizeInBits();
1095  APInt InMask = APInt::getLowBitsSet(BitWidth, InBits);
1096  APInt InSignBit = APInt::getOneBitSet(BitWidth, InBits - 1);
1097  APInt NewBits = ~InMask & NewMask;
1098 
1099  // If none of the top bits are demanded, convert this into an any_extend.
1100  if (NewBits == 0)
1101  return TLO.CombineTo(Op,TLO.DAG.getNode(ISD::ANY_EXTEND, dl,
1102  Op.getValueType(),
1103  Op.getOperand(0)));
1104 
1105  // Since some of the sign extended bits are demanded, we know that the sign
1106  // bit is demanded.
1107  APInt InDemandedBits = InMask & NewMask;
1108  InDemandedBits |= InSignBit;
1109  InDemandedBits = InDemandedBits.trunc(InBits);
1110 
1111  if (SimplifyDemandedBits(Op.getOperand(0), InDemandedBits, Known, TLO,
1112  Depth+1))
1113  return true;
1114  Known = Known.zext(BitWidth);
1115 
1116  // If the sign bit is known zero, convert this to a zero extend.
1117  if (Known.Zero.intersects(InSignBit))
1118  return TLO.CombineTo(Op, TLO.DAG.getNode(ISD::ZERO_EXTEND, dl,
1119  Op.getValueType(),
1120  Op.getOperand(0)));
1121 
1122  // If the sign bit is known one, the top bits match.
1123  if (Known.One.intersects(InSignBit)) {
1124  Known.One |= NewBits;
1125  assert((Known.Zero & NewBits) == 0);
1126  } else { // Otherwise, top bits aren't known.
1127  assert((Known.One & NewBits) == 0);
1128  assert((Known.Zero & NewBits) == 0);
1129  }
1130  break;
1131  }
1132  case ISD::ANY_EXTEND: {
1133  unsigned OperandBitWidth = Op.getOperand(0).getScalarValueSizeInBits();
1134  APInt InMask = NewMask.trunc(OperandBitWidth);
1135  if (SimplifyDemandedBits(Op.getOperand(0), InMask, Known, TLO, Depth+1))
1136  return true;
1137  assert(!Known.hasConflict() && "Bits known to be one AND zero?");
1138  Known = Known.zext(BitWidth);
1139  break;
1140  }
1141  case ISD::TRUNCATE: {
1142  // Simplify the input, using demanded bit information, and compute the known
1143  // zero/one bits live out.
1144  unsigned OperandBitWidth = Op.getOperand(0).getScalarValueSizeInBits();
1145  APInt TruncMask = NewMask.zext(OperandBitWidth);
1146  if (SimplifyDemandedBits(Op.getOperand(0), TruncMask, Known, TLO, Depth+1))
1147  return true;
1148  Known = Known.trunc(BitWidth);
1149 
1150  // If the input is only used by this truncate, see if we can shrink it based
1151  // on the known demanded bits.
1152  if (Op.getOperand(0).getNode()->hasOneUse()) {
1153  SDValue In = Op.getOperand(0);
1154  switch (In.getOpcode()) {
1155  default: break;
1156  case ISD::SRL:
1157  // Shrink SRL by a constant if none of the high bits shifted in are
1158  // demanded.
1159  if (TLO.LegalTypes() &&
1161  // Do not turn (vt1 truncate (vt2 srl)) into (vt1 srl) if vt1 is
1162  // undesirable.
1163  break;
1165  if (!ShAmt)
1166  break;
1167  SDValue Shift = In.getOperand(1);
1168  if (TLO.LegalTypes()) {
1169  uint64_t ShVal = ShAmt->getZExtValue();
1170  Shift = TLO.DAG.getConstant(ShVal, dl,
1171  getShiftAmountTy(Op.getValueType(), DL));
1172  }
1173 
1174  if (ShAmt->getZExtValue() < BitWidth) {
1175  APInt HighBits = APInt::getHighBitsSet(OperandBitWidth,
1176  OperandBitWidth - BitWidth);
1177  HighBits.lshrInPlace(ShAmt->getZExtValue());
1178  HighBits = HighBits.trunc(BitWidth);
1179 
1180  if (!(HighBits & NewMask)) {
1181  // None of the shifted in bits are needed. Add a truncate of the
1182  // shift input, then shift it.
1183  SDValue NewTrunc = TLO.DAG.getNode(ISD::TRUNCATE, dl,
1184  Op.getValueType(),
1185  In.getOperand(0));
1186  return TLO.CombineTo(Op, TLO.DAG.getNode(ISD::SRL, dl,
1187  Op.getValueType(),
1188  NewTrunc,
1189  Shift));
1190  }
1191  }
1192  break;
1193  }
1194  }
1195 
1196  assert(!Known.hasConflict() && "Bits known to be one AND zero?");
1197  break;
1198  }
1199  case ISD::AssertZext: {
1200  // AssertZext demands all of the high bits, plus any of the low bits
1201  // demanded by its users.
1202  EVT VT = cast<VTSDNode>(Op.getOperand(1))->getVT();
1203  APInt InMask = APInt::getLowBitsSet(BitWidth,
1204  VT.getSizeInBits());
1205  if (SimplifyDemandedBits(Op.getOperand(0), ~InMask | NewMask,
1206  Known, TLO, Depth+1))
1207  return true;
1208  assert(!Known.hasConflict() && "Bits known to be one AND zero?");
1209 
1210  Known.Zero |= ~InMask;
1211  break;
1212  }
1213  case ISD::BITCAST:
1214  // If this is an FP->Int bitcast and if the sign bit is the only
1215  // thing demanded, turn this into a FGETSIGN.
1216  if (!TLO.LegalOperations() &&
1217  !Op.getValueType().isVector() &&
1218  !Op.getOperand(0).getValueType().isVector() &&
1219  NewMask == APInt::getSignMask(Op.getValueSizeInBits()) &&
1221  bool OpVTLegal = isOperationLegalOrCustom(ISD::FGETSIGN, Op.getValueType());
1223  if ((OpVTLegal || i32Legal) && Op.getValueType().isSimple() &&
1224  Op.getOperand(0).getValueType() != MVT::f128) {
1225  // Cannot eliminate/lower SHL for f128 yet.
1226  EVT Ty = OpVTLegal ? Op.getValueType() : MVT::i32;
1227  // Make a FGETSIGN + SHL to move the sign bit into the appropriate
1228  // place. We expect the SHL to be eliminated by other optimizations.
1229  SDValue Sign = TLO.DAG.getNode(ISD::FGETSIGN, dl, Ty, Op.getOperand(0));
1230  unsigned OpVTSizeInBits = Op.getValueSizeInBits();
1231  if (!OpVTLegal && OpVTSizeInBits > 32)
1232  Sign = TLO.DAG.getNode(ISD::ZERO_EXTEND, dl, Op.getValueType(), Sign);
1233  unsigned ShVal = Op.getValueSizeInBits() - 1;
1234  SDValue ShAmt = TLO.DAG.getConstant(ShVal, dl, Op.getValueType());
1235  return TLO.CombineTo(Op, TLO.DAG.getNode(ISD::SHL, dl,
1236  Op.getValueType(),
1237  Sign, ShAmt));
1238  }
1239  }
1240  break;
1241  case ISD::ADD:
1242  case ISD::MUL:
1243  case ISD::SUB: {
1244  // Add, Sub, and Mul don't demand any bits in positions beyond that
1245  // of the highest bit demanded of them.
1246  APInt LoMask = APInt::getLowBitsSet(BitWidth,
1247  BitWidth - NewMask.countLeadingZeros());
1248  if (SimplifyDemandedBits(Op.getOperand(0), LoMask, Known2, TLO, Depth+1) ||
1249  SimplifyDemandedBits(Op.getOperand(1), LoMask, Known2, TLO, Depth+1) ||
1250  // See if the operation should be performed at a smaller bit width.
1251  ShrinkDemandedOp(Op, BitWidth, NewMask, TLO)) {
1252  SDNodeFlags Flags = Op.getNode()->getFlags();
1253  if (Flags.hasNoSignedWrap() || Flags.hasNoUnsignedWrap()) {
1254  // Disable the nsw and nuw flags. We can no longer guarantee that we
1255  // won't wrap after simplification.
1256  Flags.setNoSignedWrap(false);
1257  Flags.setNoUnsignedWrap(false);
1258  SDValue NewOp = TLO.DAG.getNode(Op.getOpcode(), dl, Op.getValueType(),
1259  Op.getOperand(0), Op.getOperand(1),
1260  Flags);
1261  return TLO.CombineTo(Op, NewOp);
1262  }
1263  return true;
1264  }
1266  }
1267  default:
1268  // Just use computeKnownBits to compute output bits.
1269  TLO.DAG.computeKnownBits(Op, Known, Depth);
1270  break;
1271  }
1272 
1273  // If we know the value of all of the demanded bits, return this as a
1274  // constant.
1275  if (NewMask.isSubsetOf(Known.Zero|Known.One)) {
1276  // Avoid folding to a constant if any OpaqueConstant is involved.
1277  const SDNode *N = Op.getNode();
1279  E = SDNodeIterator::end(N); I != E; ++I) {
1280  SDNode *Op = *I;
1281  if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op))
1282  if (C->isOpaque())
1283  return false;
1284  }
1285  return TLO.CombineTo(Op,
1286  TLO.DAG.getConstant(Known.One, dl, Op.getValueType()));
1287  }
1288 
1289  return false;
1290 }
1291 
1292 /// Determine which of the bits specified in Mask are known to be either zero or
1293 /// one and return them in the Known.
1295  KnownBits &Known,
1296  const APInt &DemandedElts,
1297  const SelectionDAG &DAG,
1298  unsigned Depth) const {
1302  Op.getOpcode() == ISD::INTRINSIC_VOID) &&
1303  "Should use MaskedValueIsZero if you don't know whether Op"
1304  " is a target node!");
1305  Known.resetAll();
1306 }
1307 
1308 /// This method can be implemented by targets that want to expose additional
1309 /// information about sign bits to the DAG Combiner.
1311  const APInt &,
1312  const SelectionDAG &,
1313  unsigned Depth) const {
1317  Op.getOpcode() == ISD::INTRINSIC_VOID) &&
1318  "Should use ComputeNumSignBits if you don't know whether Op"
1319  " is a target node!");
1320  return 1;
1321 }
1322 
1323 // FIXME: Ideally, this would use ISD::isConstantSplatVector(), but that must
1324 // work with truncating build vectors and vectors with elements of less than
1325 // 8 bits.
1327  if (!N)
1328  return false;
1329 
1330  APInt CVal;
1331  if (auto *CN = dyn_cast<ConstantSDNode>(N)) {
1332  CVal = CN->getAPIntValue();
1333  } else if (auto *BV = dyn_cast<BuildVectorSDNode>(N)) {
1334  auto *CN = BV->getConstantSplatNode();
1335  if (!CN)
1336  return false;
1337 
1338  // If this is a truncating build vector, truncate the splat value.
1339  // Otherwise, we may fail to match the expected values below.
1340  unsigned BVEltWidth = BV->getValueType(0).getScalarSizeInBits();
1341  CVal = CN->getAPIntValue();
1342  if (BVEltWidth < CVal.getBitWidth())
1343  CVal = CVal.trunc(BVEltWidth);
1344  } else {
1345  return false;
1346  }
1347 
1348  switch (getBooleanContents(N->getValueType(0))) {
1350  return CVal[0];
1352  return CVal.isOneValue();
1354  return CVal.isAllOnesValue();
1355  }
1356 
1357  llvm_unreachable("Invalid boolean contents");
1358 }
1359 
1361  const SDLoc &DL) const {
1362  unsigned ElementWidth = VT.getScalarSizeInBits();
1363  APInt TrueInt =
1365  ? APInt(ElementWidth, 1)
1366  : APInt::getAllOnesValue(ElementWidth);
1367  return DAG.getConstant(TrueInt, DL, VT);
1368 }
1369 
1371  if (!N)
1372  return false;
1373 
1374  const ConstantSDNode *CN = dyn_cast<ConstantSDNode>(N);
1375  if (!CN) {
1377  if (!BV)
1378  return false;
1379 
1380  // Only interested in constant splats, we don't care about undef
1381  // elements in identifying boolean constants and getConstantSplatNode
1382  // returns NULL if all ops are undef;
1383  CN = BV->getConstantSplatNode();
1384  if (!CN)
1385  return false;
1386  }
1387 
1389  return !CN->getAPIntValue()[0];
1390 
1391  return CN->isNullValue();
1392 }
1393 
1395  bool SExt) const {
1396  if (VT == MVT::i1)
1397  return N->isOne();
1398 
1400  switch (Cnt) {
1402  // An extended value of 1 is always true, unless its original type is i1,
1403  // in which case it will be sign extended to -1.
1404  return (N->isOne() && !SExt) || (SExt && (N->getValueType(0) != MVT::i1));
1407  return N->isAllOnesValue() && SExt;
1408  }
1409  llvm_unreachable("Unexpected enumeration.");
1410 }
1411 
1412 /// This helper function of SimplifySetCC tries to optimize the comparison when
1413 /// either operand of the SetCC node is a bitwise-and instruction.
1414 SDValue TargetLowering::simplifySetCCWithAnd(EVT VT, SDValue N0, SDValue N1,
1415  ISD::CondCode Cond,
1416  DAGCombinerInfo &DCI,
1417  const SDLoc &DL) const {
1418  // Match these patterns in any of their permutations:
1419  // (X & Y) == Y
1420  // (X & Y) != Y
1421  if (N1.getOpcode() == ISD::AND && N0.getOpcode() != ISD::AND)
1422  std::swap(N0, N1);
1423 
1424  EVT OpVT = N0.getValueType();
1425  if (N0.getOpcode() != ISD::AND || !OpVT.isInteger() ||
1426  (Cond != ISD::SETEQ && Cond != ISD::SETNE))
1427  return SDValue();
1428 
1429  SDValue X, Y;
1430  if (N0.getOperand(0) == N1) {
1431  X = N0.getOperand(1);
1432  Y = N0.getOperand(0);
1433  } else if (N0.getOperand(1) == N1) {
1434  X = N0.getOperand(0);
1435  Y = N0.getOperand(1);
1436  } else {
1437  return SDValue();
1438  }
1439 
1440  SelectionDAG &DAG = DCI.DAG;
1441  SDValue Zero = DAG.getConstant(0, DL, OpVT);
1442  if (DAG.isKnownToBeAPowerOfTwo(Y)) {
1443  // Simplify X & Y == Y to X & Y != 0 if Y has exactly one bit set.
1444  // Note that where Y is variable and is known to have at most one bit set
1445  // (for example, if it is Z & 1) we cannot do this; the expressions are not
1446  // equivalent when Y == 0.
1447  Cond = ISD::getSetCCInverse(Cond, /*isInteger=*/true);
1448  if (DCI.isBeforeLegalizeOps() ||
1449  isCondCodeLegal(Cond, N0.getSimpleValueType()))
1450  return DAG.getSetCC(DL, VT, N0, Zero, Cond);
1451  } else if (N0.hasOneUse() && hasAndNotCompare(Y)) {
1452  // If the target supports an 'and-not' or 'and-complement' logic operation,
1453  // try to use that to make a comparison operation more efficient.
1454  // But don't do this transform if the mask is a single bit because there are
1455  // more efficient ways to deal with that case (for example, 'bt' on x86 or
1456  // 'rlwinm' on PPC).
1457 
1458  // Bail out if the compare operand that we want to turn into a zero is
1459  // already a zero (otherwise, infinite loop).
1460  auto *YConst = dyn_cast<ConstantSDNode>(Y);
1461  if (YConst && YConst->isNullValue())
1462  return SDValue();
1463 
1464  // Transform this into: ~X & Y == 0.
1465  SDValue NotX = DAG.getNOT(SDLoc(X), X, OpVT);
1466  SDValue NewAnd = DAG.getNode(ISD::AND, SDLoc(N0), OpVT, NotX, Y);
1467  return DAG.getSetCC(DL, VT, NewAnd, Zero, Cond);
1468  }
1469 
1470  return SDValue();
1471 }
1472 
1473 /// Try to simplify a setcc built with the specified operands and cc. If it is
1474 /// unable to simplify it, return a null SDValue.
1476  ISD::CondCode Cond, bool foldBooleans,
1477  DAGCombinerInfo &DCI,
1478  const SDLoc &dl) const {
1479  SelectionDAG &DAG = DCI.DAG;
1480 
1481  // These setcc operations always fold.
1482  switch (Cond) {
1483  default: break;
1484  case ISD::SETFALSE:
1485  case ISD::SETFALSE2: return DAG.getConstant(0, dl, VT);
1486  case ISD::SETTRUE:
1487  case ISD::SETTRUE2: {
1490  return DAG.getConstant(
1491  Cnt == TargetLowering::ZeroOrNegativeOneBooleanContent ? -1ULL : 1, dl,
1492  VT);
1493  }
1494  }
1495 
1496  // Ensure that the constant occurs on the RHS and fold constant comparisons.
1497  ISD::CondCode SwappedCC = ISD::getSetCCSwappedOperands(Cond);
1498  if (isa<ConstantSDNode>(N0.getNode()) &&
1499  (DCI.isBeforeLegalizeOps() ||
1500  isCondCodeLegal(SwappedCC, N0.getSimpleValueType())))
1501  return DAG.getSetCC(dl, VT, N1, N0, SwappedCC);
1502 
1503  if (auto *N1C = dyn_cast<ConstantSDNode>(N1.getNode())) {
1504  const APInt &C1 = N1C->getAPIntValue();
1505 
1506  // If the LHS is '(srl (ctlz x), 5)', the RHS is 0/1, and this is an
1507  // equality comparison, then we're just comparing whether X itself is
1508  // zero.
1509  if (N0.getOpcode() == ISD::SRL && (C1.isNullValue() || C1.isOneValue()) &&
1510  N0.getOperand(0).getOpcode() == ISD::CTLZ &&
1511  N0.getOperand(1).getOpcode() == ISD::Constant) {
1512  const APInt &ShAmt
1513  = cast<ConstantSDNode>(N0.getOperand(1))->getAPIntValue();
1514  if ((Cond == ISD::SETEQ || Cond == ISD::SETNE) &&
1515  ShAmt == Log2_32(N0.getValueSizeInBits())) {
1516  if ((C1 == 0) == (Cond == ISD::SETEQ)) {
1517  // (srl (ctlz x), 5) == 0 -> X != 0
1518  // (srl (ctlz x), 5) != 1 -> X != 0
1519  Cond = ISD::SETNE;
1520  } else {
1521  // (srl (ctlz x), 5) != 0 -> X == 0
1522  // (srl (ctlz x), 5) == 1 -> X == 0
1523  Cond = ISD::SETEQ;
1524  }
1525  SDValue Zero = DAG.getConstant(0, dl, N0.getValueType());
1526  return DAG.getSetCC(dl, VT, N0.getOperand(0).getOperand(0),
1527  Zero, Cond);
1528  }
1529  }
1530 
1531  SDValue CTPOP = N0;
1532  // Look through truncs that don't change the value of a ctpop.
1533  if (N0.hasOneUse() && N0.getOpcode() == ISD::TRUNCATE)
1534  CTPOP = N0.getOperand(0);
1535 
1536  if (CTPOP.hasOneUse() && CTPOP.getOpcode() == ISD::CTPOP &&
1537  (N0 == CTPOP ||
1539  EVT CTVT = CTPOP.getValueType();
1540  SDValue CTOp = CTPOP.getOperand(0);
1541 
1542  // (ctpop x) u< 2 -> (x & x-1) == 0
1543  // (ctpop x) u> 1 -> (x & x-1) != 0
1544  if ((Cond == ISD::SETULT && C1 == 2) || (Cond == ISD::SETUGT && C1 == 1)){
1545  SDValue Sub = DAG.getNode(ISD::SUB, dl, CTVT, CTOp,
1546  DAG.getConstant(1, dl, CTVT));
1547  SDValue And = DAG.getNode(ISD::AND, dl, CTVT, CTOp, Sub);
1549  return DAG.getSetCC(dl, VT, And, DAG.getConstant(0, dl, CTVT), CC);
1550  }
1551 
1552  // TODO: (ctpop x) == 1 -> x && (x & x-1) == 0 iff ctpop is illegal.
1553  }
1554 
1555  // (zext x) == C --> x == (trunc C)
1556  // (sext x) == C --> x == (trunc C)
1557  if ((Cond == ISD::SETEQ || Cond == ISD::SETNE) &&
1558  DCI.isBeforeLegalize() && N0->hasOneUse()) {
1559  unsigned MinBits = N0.getValueSizeInBits();
1560  SDValue PreExt;
1561  bool Signed = false;
1562  if (N0->getOpcode() == ISD::ZERO_EXTEND) {
1563  // ZExt
1564  MinBits = N0->getOperand(0).getValueSizeInBits();
1565  PreExt = N0->getOperand(0);
1566  } else if (N0->getOpcode() == ISD::AND) {
1567  // DAGCombine turns costly ZExts into ANDs
1568  if (auto *C = dyn_cast<ConstantSDNode>(N0->getOperand(1)))
1569  if ((C->getAPIntValue()+1).isPowerOf2()) {
1570  MinBits = C->getAPIntValue().countTrailingOnes();
1571  PreExt = N0->getOperand(0);
1572  }
1573  } else if (N0->getOpcode() == ISD::SIGN_EXTEND) {
1574  // SExt
1575  MinBits = N0->getOperand(0).getValueSizeInBits();
1576  PreExt = N0->getOperand(0);
1577  Signed = true;
1578  } else if (auto *LN0 = dyn_cast<LoadSDNode>(N0)) {
1579  // ZEXTLOAD / SEXTLOAD
1580  if (LN0->getExtensionType() == ISD::ZEXTLOAD) {
1581  MinBits = LN0->getMemoryVT().getSizeInBits();
1582  PreExt = N0;
1583  } else if (LN0->getExtensionType() == ISD::SEXTLOAD) {
1584  Signed = true;
1585  MinBits = LN0->getMemoryVT().getSizeInBits();
1586  PreExt = N0;
1587  }
1588  }
1589 
1590  // Figure out how many bits we need to preserve this constant.
1591  unsigned ReqdBits = Signed ?
1592  C1.getBitWidth() - C1.getNumSignBits() + 1 :
1593  C1.getActiveBits();
1594 
1595  // Make sure we're not losing bits from the constant.
1596  if (MinBits > 0 &&
1597  MinBits < C1.getBitWidth() &&
1598  MinBits >= ReqdBits) {
1599  EVT MinVT = EVT::getIntegerVT(*DAG.getContext(), MinBits);
1600  if (isTypeDesirableForOp(ISD::SETCC, MinVT)) {
1601  // Will get folded away.
1602  SDValue Trunc = DAG.getNode(ISD::TRUNCATE, dl, MinVT, PreExt);
1603  if (MinBits == 1 && C1 == 1)
1604  // Invert the condition.
1605  return DAG.getSetCC(dl, VT, Trunc, DAG.getConstant(0, dl, MVT::i1),
1606  Cond == ISD::SETEQ ? ISD::SETNE : ISD::SETEQ);
1607  SDValue C = DAG.getConstant(C1.trunc(MinBits), dl, MinVT);
1608  return DAG.getSetCC(dl, VT, Trunc, C, Cond);
1609  }
1610 
1611  // If truncating the setcc operands is not desirable, we can still
1612  // simplify the expression in some cases:
1613  // setcc ([sz]ext (setcc x, y, cc)), 0, setne) -> setcc (x, y, cc)
1614  // setcc ([sz]ext (setcc x, y, cc)), 0, seteq) -> setcc (x, y, inv(cc))
1615  // setcc (zext (setcc x, y, cc)), 1, setne) -> setcc (x, y, inv(cc))
1616  // setcc (zext (setcc x, y, cc)), 1, seteq) -> setcc (x, y, cc)
1617  // setcc (sext (setcc x, y, cc)), -1, setne) -> setcc (x, y, inv(cc))
1618  // setcc (sext (setcc x, y, cc)), -1, seteq) -> setcc (x, y, cc)
1619  SDValue TopSetCC = N0->getOperand(0);
1620  unsigned N0Opc = N0->getOpcode();
1621  bool SExt = (N0Opc == ISD::SIGN_EXTEND);
1622  if (TopSetCC.getValueType() == MVT::i1 && VT == MVT::i1 &&
1623  TopSetCC.getOpcode() == ISD::SETCC &&
1624  (N0Opc == ISD::ZERO_EXTEND || N0Opc == ISD::SIGN_EXTEND) &&
1625  (isConstFalseVal(N1C) ||
1626  isExtendedTrueVal(N1C, N0->getValueType(0), SExt))) {
1627 
1628  bool Inverse = (N1C->isNullValue() && Cond == ISD::SETEQ) ||
1629  (!N1C->isNullValue() && Cond == ISD::SETNE);
1630 
1631  if (!Inverse)
1632  return TopSetCC;
1633 
1635  cast<CondCodeSDNode>(TopSetCC.getOperand(2))->get(),
1636  TopSetCC.getOperand(0).getValueType().isInteger());
1637  return DAG.getSetCC(dl, VT, TopSetCC.getOperand(0),
1638  TopSetCC.getOperand(1),
1639  InvCond);
1640  }
1641  }
1642  }
1643 
1644  // If the LHS is '(and load, const)', the RHS is 0, the test is for
1645  // equality or unsigned, and all 1 bits of the const are in the same
1646  // partial word, see if we can shorten the load.
1647  if (DCI.isBeforeLegalize() &&
1648  !ISD::isSignedIntSetCC(Cond) &&
1649  N0.getOpcode() == ISD::AND && C1 == 0 &&
1650  N0.getNode()->hasOneUse() &&
1651  isa<LoadSDNode>(N0.getOperand(0)) &&
1652  N0.getOperand(0).getNode()->hasOneUse() &&
1653  isa<ConstantSDNode>(N0.getOperand(1))) {
1654  LoadSDNode *Lod = cast<LoadSDNode>(N0.getOperand(0));
1655  APInt bestMask;
1656  unsigned bestWidth = 0, bestOffset = 0;
1657  if (!Lod->isVolatile() && Lod->isUnindexed()) {
1658  unsigned origWidth = N0.getValueSizeInBits();
1659  unsigned maskWidth = origWidth;
1660  // We can narrow (e.g.) 16-bit extending loads on 32-bit target to
1661  // 8 bits, but have to be careful...
1662  if (Lod->getExtensionType() != ISD::NON_EXTLOAD)
1663  origWidth = Lod->getMemoryVT().getSizeInBits();
1664  const APInt &Mask =
1665  cast<ConstantSDNode>(N0.getOperand(1))->getAPIntValue();
1666  for (unsigned width = origWidth / 2; width>=8; width /= 2) {
1667  APInt newMask = APInt::getLowBitsSet(maskWidth, width);
1668  for (unsigned offset=0; offset<origWidth/width; offset++) {
1669  if (Mask.isSubsetOf(newMask)) {
1670  if (DAG.getDataLayout().isLittleEndian())
1671  bestOffset = (uint64_t)offset * (width/8);
1672  else
1673  bestOffset = (origWidth/width - offset - 1) * (width/8);
1674  bestMask = Mask.lshr(offset * (width/8) * 8);
1675  bestWidth = width;
1676  break;
1677  }
1678  newMask <<= width;
1679  }
1680  }
1681  }
1682  if (bestWidth) {
1683  EVT newVT = EVT::getIntegerVT(*DAG.getContext(), bestWidth);
1684  if (newVT.isRound()) {
1685  EVT PtrType = Lod->getOperand(1).getValueType();
1686  SDValue Ptr = Lod->getBasePtr();
1687  if (bestOffset != 0)
1688  Ptr = DAG.getNode(ISD::ADD, dl, PtrType, Lod->getBasePtr(),
1689  DAG.getConstant(bestOffset, dl, PtrType));
1690  unsigned NewAlign = MinAlign(Lod->getAlignment(), bestOffset);
1691  SDValue NewLoad = DAG.getLoad(
1692  newVT, dl, Lod->getChain(), Ptr,
1693  Lod->getPointerInfo().getWithOffset(bestOffset), NewAlign);
1694  return DAG.getSetCC(dl, VT,
1695  DAG.getNode(ISD::AND, dl, newVT, NewLoad,
1696  DAG.getConstant(bestMask.trunc(bestWidth),
1697  dl, newVT)),
1698  DAG.getConstant(0LL, dl, newVT), Cond);
1699  }
1700  }
1701  }
1702 
1703  // If the LHS is a ZERO_EXTEND, perform the comparison on the input.
1704  if (N0.getOpcode() == ISD::ZERO_EXTEND) {
1705  unsigned InSize = N0.getOperand(0).getValueSizeInBits();
1706 
1707  // If the comparison constant has bits in the upper part, the
1708  // zero-extended value could never match.
1709  if (C1.intersects(APInt::getHighBitsSet(C1.getBitWidth(),
1710  C1.getBitWidth() - InSize))) {
1711  switch (Cond) {
1712  case ISD::SETUGT:
1713  case ISD::SETUGE:
1714  case ISD::SETEQ:
1715  return DAG.getConstant(0, dl, VT);
1716  case ISD::SETULT:
1717  case ISD::SETULE:
1718  case ISD::SETNE:
1719  return DAG.getConstant(1, dl, VT);
1720  case ISD::SETGT:
1721  case ISD::SETGE:
1722  // True if the sign bit of C1 is set.
1723  return DAG.getConstant(C1.isNegative(), dl, VT);
1724  case ISD::SETLT:
1725  case ISD::SETLE:
1726  // True if the sign bit of C1 isn't set.
1727  return DAG.getConstant(C1.isNonNegative(), dl, VT);
1728  default:
1729  break;
1730  }
1731  }
1732 
1733  // Otherwise, we can perform the comparison with the low bits.
1734  switch (Cond) {
1735  case ISD::SETEQ:
1736  case ISD::SETNE:
1737  case ISD::SETUGT:
1738  case ISD::SETUGE:
1739  case ISD::SETULT:
1740  case ISD::SETULE: {
1741  EVT newVT = N0.getOperand(0).getValueType();
1742  if (DCI.isBeforeLegalizeOps() ||
1743  (isOperationLegal(ISD::SETCC, newVT) &&
1744  getCondCodeAction(Cond, newVT.getSimpleVT()) == Legal)) {
1745  EVT NewSetCCVT =
1746  getSetCCResultType(DAG.getDataLayout(), *DAG.getContext(), newVT);
1747  SDValue NewConst = DAG.getConstant(C1.trunc(InSize), dl, newVT);
1748 
1749  SDValue NewSetCC = DAG.getSetCC(dl, NewSetCCVT, N0.getOperand(0),
1750  NewConst, Cond);
1751  return DAG.getBoolExtOrTrunc(NewSetCC, dl, VT, N0.getValueType());
1752  }
1753  break;
1754  }
1755  default:
1756  break; // todo, be more careful with signed comparisons
1757  }
1758  } else if (N0.getOpcode() == ISD::SIGN_EXTEND_INREG &&
1759  (Cond == ISD::SETEQ || Cond == ISD::SETNE)) {
1760  EVT ExtSrcTy = cast<VTSDNode>(N0.getOperand(1))->getVT();
1761  unsigned ExtSrcTyBits = ExtSrcTy.getSizeInBits();
1762  EVT ExtDstTy = N0.getValueType();
1763  unsigned ExtDstTyBits = ExtDstTy.getSizeInBits();
1764 
1765  // If the constant doesn't fit into the number of bits for the source of
1766  // the sign extension, it is impossible for both sides to be equal.
1767  if (C1.getMinSignedBits() > ExtSrcTyBits)
1768  return DAG.getConstant(Cond == ISD::SETNE, dl, VT);
1769 
1770  SDValue ZextOp;
1771  EVT Op0Ty = N0.getOperand(0).getValueType();
1772  if (Op0Ty == ExtSrcTy) {
1773  ZextOp = N0.getOperand(0);
1774  } else {
1775  APInt Imm = APInt::getLowBitsSet(ExtDstTyBits, ExtSrcTyBits);
1776  ZextOp = DAG.getNode(ISD::AND, dl, Op0Ty, N0.getOperand(0),
1777  DAG.getConstant(Imm, dl, Op0Ty));
1778  }
1779  if (!DCI.isCalledByLegalizer())
1780  DCI.AddToWorklist(ZextOp.getNode());
1781  // Otherwise, make this a use of a zext.
1782  return DAG.getSetCC(dl, VT, ZextOp,
1784  ExtDstTyBits,
1785  ExtSrcTyBits),
1786  dl, ExtDstTy),
1787  Cond);
1788  } else if ((N1C->isNullValue() || N1C->isOne()) &&
1789  (Cond == ISD::SETEQ || Cond == ISD::SETNE)) {
1790  // SETCC (SETCC), [0|1], [EQ|NE] -> SETCC
1791  if (N0.getOpcode() == ISD::SETCC &&
1792  isTypeLegal(VT) && VT.bitsLE(N0.getValueType())) {
1793  bool TrueWhenTrue = (Cond == ISD::SETEQ) ^ (!N1C->isOne());
1794  if (TrueWhenTrue)
1795  return DAG.getNode(ISD::TRUNCATE, dl, VT, N0);
1796  // Invert the condition.
1797  ISD::CondCode CC = cast<CondCodeSDNode>(N0.getOperand(2))->get();
1798  CC = ISD::getSetCCInverse(CC,
1799  N0.getOperand(0).getValueType().isInteger());
1800  if (DCI.isBeforeLegalizeOps() ||
1801  isCondCodeLegal(CC, N0.getOperand(0).getSimpleValueType()))
1802  return DAG.getSetCC(dl, VT, N0.getOperand(0), N0.getOperand(1), CC);
1803  }
1804 
1805  if ((N0.getOpcode() == ISD::XOR ||
1806  (N0.getOpcode() == ISD::AND &&
1807  N0.getOperand(0).getOpcode() == ISD::XOR &&
1808  N0.getOperand(1) == N0.getOperand(0).getOperand(1))) &&
1809  isa<ConstantSDNode>(N0.getOperand(1)) &&
1810  cast<ConstantSDNode>(N0.getOperand(1))->isOne()) {
1811  // If this is (X^1) == 0/1, swap the RHS and eliminate the xor. We
1812  // can only do this if the top bits are known zero.
1813  unsigned BitWidth = N0.getValueSizeInBits();
1814  if (DAG.MaskedValueIsZero(N0,
1815  APInt::getHighBitsSet(BitWidth,
1816  BitWidth-1))) {
1817  // Okay, get the un-inverted input value.
1818  SDValue Val;
1819  if (N0.getOpcode() == ISD::XOR) {
1820  Val = N0.getOperand(0);
1821  } else {
1822  assert(N0.getOpcode() == ISD::AND &&
1823  N0.getOperand(0).getOpcode() == ISD::XOR);
1824  // ((X^1)&1)^1 -> X & 1
1825  Val = DAG.getNode(ISD::AND, dl, N0.getValueType(),
1826  N0.getOperand(0).getOperand(0),
1827  N0.getOperand(1));
1828  }
1829 
1830  return DAG.getSetCC(dl, VT, Val, N1,
1831  Cond == ISD::SETEQ ? ISD::SETNE : ISD::SETEQ);
1832  }
1833  } else if (N1C->isOne() &&
1834  (VT == MVT::i1 ||
1835  getBooleanContents(N0->getValueType(0)) ==
1837  SDValue Op0 = N0;
1838  if (Op0.getOpcode() == ISD::TRUNCATE)
1839  Op0 = Op0.getOperand(0);
1840 
1841  if ((Op0.getOpcode() == ISD::XOR) &&
1842  Op0.getOperand(0).getOpcode() == ISD::SETCC &&
1843  Op0.getOperand(1).getOpcode() == ISD::SETCC) {
1844  // (xor (setcc), (setcc)) == / != 1 -> (setcc) != / == (setcc)
1845  Cond = (Cond == ISD::SETEQ) ? ISD::SETNE : ISD::SETEQ;
1846  return DAG.getSetCC(dl, VT, Op0.getOperand(0), Op0.getOperand(1),
1847  Cond);
1848  }
1849  if (Op0.getOpcode() == ISD::AND &&
1850  isa<ConstantSDNode>(Op0.getOperand(1)) &&
1851  cast<ConstantSDNode>(Op0.getOperand(1))->isOne()) {
1852  // If this is (X&1) == / != 1, normalize it to (X&1) != / == 0.
1853  if (Op0.getValueType().bitsGT(VT))
1854  Op0 = DAG.getNode(ISD::AND, dl, VT,
1855  DAG.getNode(ISD::TRUNCATE, dl, VT, Op0.getOperand(0)),
1856  DAG.getConstant(1, dl, VT));
1857  else if (Op0.getValueType().bitsLT(VT))
1858  Op0 = DAG.getNode(ISD::AND, dl, VT,
1859  DAG.getNode(ISD::ANY_EXTEND, dl, VT, Op0.getOperand(0)),
1860  DAG.getConstant(1, dl, VT));
1861 
1862  return DAG.getSetCC(dl, VT, Op0,
1863  DAG.getConstant(0, dl, Op0.getValueType()),
1864  Cond == ISD::SETEQ ? ISD::SETNE : ISD::SETEQ);
1865  }
1866  if (Op0.getOpcode() == ISD::AssertZext &&
1867  cast<VTSDNode>(Op0.getOperand(1))->getVT() == MVT::i1)
1868  return DAG.getSetCC(dl, VT, Op0,
1869  DAG.getConstant(0, dl, Op0.getValueType()),
1870  Cond == ISD::SETEQ ? ISD::SETNE : ISD::SETEQ);
1871  }
1872  }
1873 
1874  APInt MinVal, MaxVal;
1875  unsigned OperandBitSize = N1C->getValueType(0).getSizeInBits();
1876  if (ISD::isSignedIntSetCC(Cond)) {
1877  MinVal = APInt::getSignedMinValue(OperandBitSize);
1878  MaxVal = APInt::getSignedMaxValue(OperandBitSize);
1879  } else {
1880  MinVal = APInt::getMinValue(OperandBitSize);
1881  MaxVal = APInt::getMaxValue(OperandBitSize);
1882  }
1883 
1884  // Canonicalize GE/LE comparisons to use GT/LT comparisons.
1885  if (Cond == ISD::SETGE || Cond == ISD::SETUGE) {
1886  // X >= MIN --> true
1887  if (C1 == MinVal)
1888  return DAG.getConstant(1, dl, VT);
1889 
1890  // X >= C0 --> X > (C0 - 1)
1891  APInt C = C1 - 1;
1892  ISD::CondCode NewCC = (Cond == ISD::SETGE) ? ISD::SETGT : ISD::SETUGT;
1893  if ((DCI.isBeforeLegalizeOps() ||
1894  isCondCodeLegal(NewCC, VT.getSimpleVT())) &&
1895  (!N1C->isOpaque() || (N1C->isOpaque() && C.getBitWidth() <= 64 &&
1897  return DAG.getSetCC(dl, VT, N0,
1898  DAG.getConstant(C, dl, N1.getValueType()),
1899  NewCC);
1900  }
1901  }
1902 
1903  if (Cond == ISD::SETLE || Cond == ISD::SETULE) {
1904  // X <= MAX --> true
1905  if (C1 == MaxVal)
1906  return DAG.getConstant(1, dl, VT);
1907 
1908  // X <= C0 --> X < (C0 + 1)
1909  APInt C = C1 + 1;
1910  ISD::CondCode NewCC = (Cond == ISD::SETLE) ? ISD::SETLT : ISD::SETULT;
1911  if ((DCI.isBeforeLegalizeOps() ||
1912  isCondCodeLegal(NewCC, VT.getSimpleVT())) &&
1913  (!N1C->isOpaque() || (N1C->isOpaque() && C.getBitWidth() <= 64 &&
1915  return DAG.getSetCC(dl, VT, N0,
1916  DAG.getConstant(C, dl, N1.getValueType()),
1917  NewCC);
1918  }
1919  }
1920 
1921  if ((Cond == ISD::SETLT || Cond == ISD::SETULT) && C1 == MinVal)
1922  return DAG.getConstant(0, dl, VT); // X < MIN --> false
1923  if ((Cond == ISD::SETGE || Cond == ISD::SETUGE) && C1 == MinVal)
1924  return DAG.getConstant(1, dl, VT); // X >= MIN --> true
1925  if ((Cond == ISD::SETGT || Cond == ISD::SETUGT) && C1 == MaxVal)
1926  return DAG.getConstant(0, dl, VT); // X > MAX --> false
1927  if ((Cond == ISD::SETLE || Cond == ISD::SETULE) && C1 == MaxVal)
1928  return DAG.getConstant(1, dl, VT); // X <= MAX --> true
1929 
1930  // Canonicalize setgt X, Min --> setne X, Min
1931  if ((Cond == ISD::SETGT || Cond == ISD::SETUGT) && C1 == MinVal)
1932  return DAG.getSetCC(dl, VT, N0, N1, ISD::SETNE);
1933  // Canonicalize setlt X, Max --> setne X, Max
1934  if ((Cond == ISD::SETLT || Cond == ISD::SETULT) && C1 == MaxVal)
1935  return DAG.getSetCC(dl, VT, N0, N1, ISD::SETNE);
1936 
1937  // If we have setult X, 1, turn it into seteq X, 0
1938  if ((Cond == ISD::SETLT || Cond == ISD::SETULT) && C1 == MinVal+1)
1939  return DAG.getSetCC(dl, VT, N0,
1940  DAG.getConstant(MinVal, dl, N0.getValueType()),
1941  ISD::SETEQ);
1942  // If we have setugt X, Max-1, turn it into seteq X, Max
1943  if ((Cond == ISD::SETGT || Cond == ISD::SETUGT) && C1 == MaxVal-1)
1944  return DAG.getSetCC(dl, VT, N0,
1945  DAG.getConstant(MaxVal, dl, N0.getValueType()),
1946  ISD::SETEQ);
1947 
1948  // If we have "setcc X, C0", check to see if we can shrink the immediate
1949  // by changing cc.
1950 
1951  // SETUGT X, SINTMAX -> SETLT X, 0
1952  if (Cond == ISD::SETUGT &&
1953  C1 == APInt::getSignedMaxValue(OperandBitSize))
1954  return DAG.getSetCC(dl, VT, N0,
1955  DAG.getConstant(0, dl, N1.getValueType()),
1956  ISD::SETLT);
1957 
1958  // SETULT X, SINTMIN -> SETGT X, -1
1959  if (Cond == ISD::SETULT &&
1960  C1 == APInt::getSignedMinValue(OperandBitSize)) {
1961  SDValue ConstMinusOne =
1962  DAG.getConstant(APInt::getAllOnesValue(OperandBitSize), dl,
1963  N1.getValueType());
1964  return DAG.getSetCC(dl, VT, N0, ConstMinusOne, ISD::SETGT);
1965  }
1966 
1967  // Fold bit comparisons when we can.
1968  if ((Cond == ISD::SETEQ || Cond == ISD::SETNE) &&
1969  (VT == N0.getValueType() ||
1970  (isTypeLegal(VT) && VT.bitsLE(N0.getValueType()))) &&
1971  N0.getOpcode() == ISD::AND) {
1972  auto &DL = DAG.getDataLayout();
1973  if (auto *AndRHS = dyn_cast<ConstantSDNode>(N0.getOperand(1))) {
1974  EVT ShiftTy = DCI.isBeforeLegalize()
1975  ? getPointerTy(DL)
1976  : getShiftAmountTy(N0.getValueType(), DL);
1977  if (Cond == ISD::SETNE && C1 == 0) {// (X & 8) != 0 --> (X & 8) >> 3
1978  // Perform the xform if the AND RHS is a single bit.
1979  if (AndRHS->getAPIntValue().isPowerOf2()) {
1980  return DAG.getNode(ISD::TRUNCATE, dl, VT,
1981  DAG.getNode(ISD::SRL, dl, N0.getValueType(), N0,
1982  DAG.getConstant(AndRHS->getAPIntValue().logBase2(), dl,
1983  ShiftTy)));
1984  }
1985  } else if (Cond == ISD::SETEQ && C1 == AndRHS->getAPIntValue()) {
1986  // (X & 8) == 8 --> (X & 8) >> 3
1987  // Perform the xform if C1 is a single bit.
1988  if (C1.isPowerOf2()) {
1989  return DAG.getNode(ISD::TRUNCATE, dl, VT,
1990  DAG.getNode(ISD::SRL, dl, N0.getValueType(), N0,
1991  DAG.getConstant(C1.logBase2(), dl,
1992  ShiftTy)));
1993  }
1994  }
1995  }
1996  }
1997 
1998  if (C1.getMinSignedBits() <= 64 &&
1999  !isLegalICmpImmediate(C1.getSExtValue())) {
2000  // (X & -256) == 256 -> (X >> 8) == 1
2001  if ((Cond == ISD::SETEQ || Cond == ISD::SETNE) &&
2002  N0.getOpcode() == ISD::AND && N0.hasOneUse()) {
2003  if (auto *AndRHS = dyn_cast<ConstantSDNode>(N0.getOperand(1))) {
2004  const APInt &AndRHSC = AndRHS->getAPIntValue();
2005  if ((-AndRHSC).isPowerOf2() && (AndRHSC & C1) == C1) {
2006  unsigned ShiftBits = AndRHSC.countTrailingZeros();
2007  auto &DL = DAG.getDataLayout();
2008  EVT ShiftTy = DCI.isBeforeLegalize()
2009  ? getPointerTy(DL)
2010  : getShiftAmountTy(N0.getValueType(), DL);
2011  EVT CmpTy = N0.getValueType();
2012  SDValue Shift = DAG.getNode(ISD::SRL, dl, CmpTy, N0.getOperand(0),
2013  DAG.getConstant(ShiftBits, dl,
2014  ShiftTy));
2015  SDValue CmpRHS = DAG.getConstant(C1.lshr(ShiftBits), dl, CmpTy);
2016  return DAG.getSetCC(dl, VT, Shift, CmpRHS, Cond);
2017  }
2018  }
2019  } else if (Cond == ISD::SETULT || Cond == ISD::SETUGE ||
2020  Cond == ISD::SETULE || Cond == ISD::SETUGT) {
2021  bool AdjOne = (Cond == ISD::SETULE || Cond == ISD::SETUGT);
2022  // X < 0x100000000 -> (X >> 32) < 1
2023  // X >= 0x100000000 -> (X >> 32) >= 1
2024  // X <= 0x0ffffffff -> (X >> 32) < 1
2025  // X > 0x0ffffffff -> (X >> 32) >= 1
2026  unsigned ShiftBits;
2027  APInt NewC = C1;
2028  ISD::CondCode NewCond = Cond;
2029  if (AdjOne) {
2030  ShiftBits = C1.countTrailingOnes();
2031  NewC = NewC + 1;
2032  NewCond = (Cond == ISD::SETULE) ? ISD::SETULT : ISD::SETUGE;
2033  } else {
2034  ShiftBits = C1.countTrailingZeros();
2035  }
2036  NewC.lshrInPlace(ShiftBits);
2037  if (ShiftBits && NewC.getMinSignedBits() <= 64 &&
2039  auto &DL = DAG.getDataLayout();
2040  EVT ShiftTy = DCI.isBeforeLegalize()
2041  ? getPointerTy(DL)
2042  : getShiftAmountTy(N0.getValueType(), DL);
2043  EVT CmpTy = N0.getValueType();
2044  SDValue Shift = DAG.getNode(ISD::SRL, dl, CmpTy, N0,
2045  DAG.getConstant(ShiftBits, dl, ShiftTy));
2046  SDValue CmpRHS = DAG.getConstant(NewC, dl, CmpTy);
2047  return DAG.getSetCC(dl, VT, Shift, CmpRHS, NewCond);
2048  }
2049  }
2050  }
2051  }
2052 
2053  if (isa<ConstantFPSDNode>(N0.getNode())) {
2054  // Constant fold or commute setcc.
2055  SDValue O = DAG.FoldSetCC(VT, N0, N1, Cond, dl);
2056  if (O.getNode()) return O;
2057  } else if (auto *CFP = dyn_cast<ConstantFPSDNode>(N1.getNode())) {
2058  // If the RHS of an FP comparison is a constant, simplify it away in
2059  // some cases.
2060  if (CFP->getValueAPF().isNaN()) {
2061  // If an operand is known to be a nan, we can fold it.
2062  switch (ISD::getUnorderedFlavor(Cond)) {
2063  default: llvm_unreachable("Unknown flavor!");
2064  case 0: // Known false.
2065  return DAG.getConstant(0, dl, VT);
2066  case 1: // Known true.
2067  return DAG.getConstant(1, dl, VT);
2068  case 2: // Undefined.
2069  return DAG.getUNDEF(VT);
2070  }
2071  }
2072 
2073  // Otherwise, we know the RHS is not a NaN. Simplify the node to drop the
2074  // constant if knowing that the operand is non-nan is enough. We prefer to
2075  // have SETO(x,x) instead of SETO(x, 0.0) because this avoids having to
2076  // materialize 0.0.
2077  if (Cond == ISD::SETO || Cond == ISD::SETUO)
2078  return DAG.getSetCC(dl, VT, N0, N0, Cond);
2079 
2080  // setcc (fneg x), C -> setcc swap(pred) x, -C
2081  if (N0.getOpcode() == ISD::FNEG) {
2083  if (DCI.isBeforeLegalizeOps() ||
2084  isCondCodeLegal(SwapCond, N0.getSimpleValueType())) {
2085  SDValue NegN1 = DAG.getNode(ISD::FNEG, dl, N0.getValueType(), N1);
2086  return DAG.getSetCC(dl, VT, N0.getOperand(0), NegN1, SwapCond);
2087  }
2088  }
2089 
2090  // If the condition is not legal, see if we can find an equivalent one
2091  // which is legal.
2092  if (!isCondCodeLegal(Cond, N0.getSimpleValueType())) {
2093  // If the comparison was an awkward floating-point == or != and one of
2094  // the comparison operands is infinity or negative infinity, convert the
2095  // condition to a less-awkward <= or >=.
2096  if (CFP->getValueAPF().isInfinity()) {
2097  if (CFP->getValueAPF().isNegative()) {
2098  if (Cond == ISD::SETOEQ &&
2100  return DAG.getSetCC(dl, VT, N0, N1, ISD::SETOLE);
2101  if (Cond == ISD::SETUEQ &&
2103  return DAG.getSetCC(dl, VT, N0, N1, ISD::SETULE);
2104  if (Cond == ISD::SETUNE &&
2106  return DAG.getSetCC(dl, VT, N0, N1, ISD::SETUGT);
2107  if (Cond == ISD::SETONE &&
2109  return DAG.getSetCC(dl, VT, N0, N1, ISD::SETOGT);
2110  } else {
2111  if (Cond == ISD::SETOEQ &&
2113  return DAG.getSetCC(dl, VT, N0, N1, ISD::SETOGE);
2114  if (Cond == ISD::SETUEQ &&
2116  return DAG.getSetCC(dl, VT, N0, N1, ISD::SETUGE);
2117  if (Cond == ISD::SETUNE &&
2119  return DAG.getSetCC(dl, VT, N0, N1, ISD::SETULT);
2120  if (Cond == ISD::SETONE &&
2122  return DAG.getSetCC(dl, VT, N0, N1, ISD::SETOLT);
2123  }
2124  }
2125  }
2126  }
2127 
2128  if (N0 == N1) {
2129  // The sext(setcc()) => setcc() optimization relies on the appropriate
2130  // constant being emitted.
2131  uint64_t EqVal = 0;
2132  switch (getBooleanContents(N0.getValueType())) {
2135  EqVal = ISD::isTrueWhenEqual(Cond);
2136  break;
2138  EqVal = ISD::isTrueWhenEqual(Cond) ? -1 : 0;
2139  break;
2140  }
2141 
2142  // We can always fold X == X for integer setcc's.
2143  if (N0.getValueType().isInteger()) {
2144  return DAG.getConstant(EqVal, dl, VT);
2145  }
2146  unsigned UOF = ISD::getUnorderedFlavor(Cond);
2147  if (UOF == 2) // FP operators that are undefined on NaNs.
2148  return DAG.getConstant(EqVal, dl, VT);
2149  if (UOF == unsigned(ISD::isTrueWhenEqual(Cond)))
2150  return DAG.getConstant(EqVal, dl, VT);
2151  // Otherwise, we can't fold it. However, we can simplify it to SETUO/SETO
2152  // if it is not already.
2153  ISD::CondCode NewCond = UOF == 0 ? ISD::SETO : ISD::SETUO;
2154  if (NewCond != Cond && (DCI.isBeforeLegalizeOps() ||
2155  getCondCodeAction(NewCond, N0.getSimpleValueType()) == Legal))
2156  return DAG.getSetCC(dl, VT, N0, N1, NewCond);
2157  }
2158 
2159  if ((Cond == ISD::SETEQ || Cond == ISD::SETNE) &&
2160  N0.getValueType().isInteger()) {
2161  if (N0.getOpcode() == ISD::ADD || N0.getOpcode() == ISD::SUB ||
2162  N0.getOpcode() == ISD::XOR) {
2163  // Simplify (X+Y) == (X+Z) --> Y == Z
2164  if (N0.getOpcode() == N1.getOpcode()) {
2165  if (N0.getOperand(0) == N1.getOperand(0))
2166  return DAG.getSetCC(dl, VT, N0.getOperand(1), N1.getOperand(1), Cond);
2167  if (N0.getOperand(1) == N1.getOperand(1))
2168  return DAG.getSetCC(dl, VT, N0.getOperand(0), N1.getOperand(0), Cond);
2169  if (isCommutativeBinOp(N0.getOpcode())) {
2170  // If X op Y == Y op X, try other combinations.
2171  if (N0.getOperand(0) == N1.getOperand(1))
2172  return DAG.getSetCC(dl, VT, N0.getOperand(1), N1.getOperand(0),
2173  Cond);
2174  if (N0.getOperand(1) == N1.getOperand(0))
2175  return DAG.getSetCC(dl, VT, N0.getOperand(0), N1.getOperand(1),
2176  Cond);
2177  }
2178  }
2179 
2180  // If RHS is a legal immediate value for a compare instruction, we need
2181  // to be careful about increasing register pressure needlessly.
2182  bool LegalRHSImm = false;
2183 
2184  if (auto *RHSC = dyn_cast<ConstantSDNode>(N1)) {
2185  if (auto *LHSR = dyn_cast<ConstantSDNode>(N0.getOperand(1))) {
2186  // Turn (X+C1) == C2 --> X == C2-C1
2187  if (N0.getOpcode() == ISD::ADD && N0.getNode()->hasOneUse()) {
2188  return DAG.getSetCC(dl, VT, N0.getOperand(0),
2189  DAG.getConstant(RHSC->getAPIntValue()-
2190  LHSR->getAPIntValue(),
2191  dl, N0.getValueType()), Cond);
2192  }
2193 
2194  // Turn (X^C1) == C2 into X == C1^C2 iff X&~C1 = 0.
2195  if (N0.getOpcode() == ISD::XOR)
2196  // If we know that all of the inverted bits are zero, don't bother
2197  // performing the inversion.
2198  if (DAG.MaskedValueIsZero(N0.getOperand(0), ~LHSR->getAPIntValue()))
2199  return
2200  DAG.getSetCC(dl, VT, N0.getOperand(0),
2201  DAG.getConstant(LHSR->getAPIntValue() ^
2202  RHSC->getAPIntValue(),
2203  dl, N0.getValueType()),
2204  Cond);
2205  }
2206 
2207  // Turn (C1-X) == C2 --> X == C1-C2
2208  if (auto *SUBC = dyn_cast<ConstantSDNode>(N0.getOperand(0))) {
2209  if (N0.getOpcode() == ISD::SUB && N0.getNode()->hasOneUse()) {
2210  return
2211  DAG.getSetCC(dl, VT, N0.getOperand(1),
2212  DAG.getConstant(SUBC->getAPIntValue() -
2213  RHSC->getAPIntValue(),
2214  dl, N0.getValueType()),
2215  Cond);
2216  }
2217  }
2218 
2219  // Could RHSC fold directly into a compare?
2220  if (RHSC->getValueType(0).getSizeInBits() <= 64)
2221  LegalRHSImm = isLegalICmpImmediate(RHSC->getSExtValue());
2222  }
2223 
2224  // Simplify (X+Z) == X --> Z == 0
2225  // Don't do this if X is an immediate that can fold into a cmp
2226  // instruction and X+Z has other uses. It could be an induction variable
2227  // chain, and the transform would increase register pressure.
2228  if (!LegalRHSImm || N0.getNode()->hasOneUse()) {
2229  if (N0.getOperand(0) == N1)
2230  return DAG.getSetCC(dl, VT, N0.getOperand(1),
2231  DAG.getConstant(0, dl, N0.getValueType()), Cond);
2232  if (N0.getOperand(1) == N1) {
2233  if (isCommutativeBinOp(N0.getOpcode()))
2234  return DAG.getSetCC(dl, VT, N0.getOperand(0),
2235  DAG.getConstant(0, dl, N0.getValueType()),
2236  Cond);
2237  if (N0.getNode()->hasOneUse()) {
2238  assert(N0.getOpcode() == ISD::SUB && "Unexpected operation!");
2239  auto &DL = DAG.getDataLayout();
2240  // (Z-X) == X --> Z == X<<1
2241  SDValue SH = DAG.getNode(
2242  ISD::SHL, dl, N1.getValueType(), N1,
2243  DAG.getConstant(1, dl,
2244  getShiftAmountTy(N1.getValueType(), DL)));
2245  if (!DCI.isCalledByLegalizer())
2246  DCI.AddToWorklist(SH.getNode());
2247  return DAG.getSetCC(dl, VT, N0.getOperand(0), SH, Cond);
2248  }
2249  }
2250  }
2251  }
2252 
2253  if (N1.getOpcode() == ISD::ADD || N1.getOpcode() == ISD::SUB ||
2254  N1.getOpcode() == ISD::XOR) {
2255  // Simplify X == (X+Z) --> Z == 0
2256  if (N1.getOperand(0) == N0)
2257  return DAG.getSetCC(dl, VT, N1.getOperand(1),
2258  DAG.getConstant(0, dl, N1.getValueType()), Cond);
2259  if (N1.getOperand(1) == N0) {
2260  if (isCommutativeBinOp(N1.getOpcode()))
2261  return DAG.getSetCC(dl, VT, N1.getOperand(0),
2262  DAG.getConstant(0, dl, N1.getValueType()), Cond);
2263  if (N1.getNode()->hasOneUse()) {
2264  assert(N1.getOpcode() == ISD::SUB && "Unexpected operation!");
2265  auto &DL = DAG.getDataLayout();
2266  // X == (Z-X) --> X<<1 == Z
2267  SDValue SH = DAG.getNode(
2268  ISD::SHL, dl, N1.getValueType(), N0,
2269  DAG.getConstant(1, dl, getShiftAmountTy(N0.getValueType(), DL)));
2270  if (!DCI.isCalledByLegalizer())
2271  DCI.AddToWorklist(SH.getNode());
2272  return DAG.getSetCC(dl, VT, SH, N1.getOperand(0), Cond);
2273  }
2274  }
2275  }
2276 
2277  if (SDValue V = simplifySetCCWithAnd(VT, N0, N1, Cond, DCI, dl))
2278  return V;
2279  }
2280 
2281  // Fold away ALL boolean setcc's.
2282  SDValue Temp;
2283  if (N0.getValueType() == MVT::i1 && foldBooleans) {
2284  switch (Cond) {
2285  default: llvm_unreachable("Unknown integer setcc!");
2286  case ISD::SETEQ: // X == Y -> ~(X^Y)
2287  Temp = DAG.getNode(ISD::XOR, dl, MVT::i1, N0, N1);
2288  N0 = DAG.getNOT(dl, Temp, MVT::i1);
2289  if (!DCI.isCalledByLegalizer())
2290  DCI.AddToWorklist(Temp.getNode());
2291  break;
2292  case ISD::SETNE: // X != Y --> (X^Y)
2293  N0 = DAG.getNode(ISD::XOR, dl, MVT::i1, N0, N1);
2294  break;
2295  case ISD::SETGT: // X >s Y --> X == 0 & Y == 1 --> ~X & Y
2296  case ISD::SETULT: // X <u Y --> X == 0 & Y == 1 --> ~X & Y
2297  Temp = DAG.getNOT(dl, N0, MVT::i1);
2298  N0 = DAG.getNode(ISD::AND, dl, MVT::i1, N1, Temp);
2299  if (!DCI.isCalledByLegalizer())
2300  DCI.AddToWorklist(Temp.getNode());
2301  break;
2302  case ISD::SETLT: // X <s Y --> X == 1 & Y == 0 --> ~Y & X
2303  case ISD::SETUGT: // X >u Y --> X == 1 & Y == 0 --> ~Y & X
2304  Temp = DAG.getNOT(dl, N1, MVT::i1);
2305  N0 = DAG.getNode(ISD::AND, dl, MVT::i1, N0, Temp);
2306  if (!DCI.isCalledByLegalizer())
2307  DCI.AddToWorklist(Temp.getNode());
2308  break;
2309  case ISD::SETULE: // X <=u Y --> X == 0 | Y == 1 --> ~X | Y
2310  case ISD::SETGE: // X >=s Y --> X == 0 | Y == 1 --> ~X | Y
2311  Temp = DAG.getNOT(dl, N0, MVT::i1);
2312  N0 = DAG.getNode(ISD::OR, dl, MVT::i1, N1, Temp);
2313  if (!DCI.isCalledByLegalizer())
2314  DCI.AddToWorklist(Temp.getNode());
2315  break;
2316  case ISD::SETUGE: // X >=u Y --> X == 1 | Y == 0 --> ~Y | X
2317  case ISD::SETLE: // X <=s Y --> X == 1 | Y == 0 --> ~Y | X
2318  Temp = DAG.getNOT(dl, N1, MVT::i1);
2319  N0 = DAG.getNode(ISD::OR, dl, MVT::i1, N0, Temp);
2320  break;
2321  }
2322  if (VT != MVT::i1) {
2323  if (!DCI.isCalledByLegalizer())
2324  DCI.AddToWorklist(N0.getNode());
2325  // FIXME: If running after legalize, we probably can't do this.
2326  N0 = DAG.getNode(ISD::ZERO_EXTEND, dl, VT, N0);
2327  }
2328  return N0;
2329  }
2330 
2331  // Could not fold it.
2332  return SDValue();
2333 }
2334 
2335 /// Returns true (and the GlobalValue and the offset) if the node is a
2336 /// GlobalAddress + offset.
2338  int64_t &Offset) const {
2339  if (auto *GASD = dyn_cast<GlobalAddressSDNode>(N)) {
2340  GA = GASD->getGlobal();
2341  Offset += GASD->getOffset();
2342  return true;
2343  }
2344 
2345  if (N->getOpcode() == ISD::ADD) {
2346  SDValue N1 = N->getOperand(0);
2347  SDValue N2 = N->getOperand(1);
2348  if (isGAPlusOffset(N1.getNode(), GA, Offset)) {
2349  if (auto *V = dyn_cast<ConstantSDNode>(N2)) {
2350  Offset += V->getSExtValue();
2351  return true;
2352  }
2353  } else if (isGAPlusOffset(N2.getNode(), GA, Offset)) {
2354  if (auto *V = dyn_cast<ConstantSDNode>(N1)) {
2355  Offset += V->getSExtValue();
2356  return true;
2357  }
2358  }
2359  }
2360 
2361  return false;
2362 }
2363 
2365  DAGCombinerInfo &DCI) const {
2366  // Default implementation: no optimization.
2367  return SDValue();
2368 }
2369 
2370 //===----------------------------------------------------------------------===//
2371 // Inline Assembler Implementation Methods
2372 //===----------------------------------------------------------------------===//
2373 
2376  unsigned S = Constraint.size();
2377 
2378  if (S == 1) {
2379  switch (Constraint[0]) {
2380  default: break;
2381  case 'r': return C_RegisterClass;
2382  case 'm': // memory
2383  case 'o': // offsetable
2384  case 'V': // not offsetable
2385  return C_Memory;
2386  case 'i': // Simple Integer or Relocatable Constant
2387  case 'n': // Simple Integer
2388  case 'E': // Floating Point Constant
2389  case 'F': // Floating Point Constant
2390  case 's': // Relocatable Constant
2391  case 'p': // Address.
2392  case 'X': // Allow ANY value.
2393  case 'I': // Target registers.
2394  case 'J':
2395  case 'K':
2396  case 'L':
2397  case 'M':
2398  case 'N':
2399  case 'O':
2400  case 'P':
2401  case '<':
2402  case '>':
2403  return C_Other;
2404  }
2405  }
2406 
2407  if (S > 1 && Constraint[0] == '{' && Constraint[S-1] == '}') {
2408  if (S == 8 && Constraint.substr(1, 6) == "memory") // "{memory}"
2409  return C_Memory;
2410  return C_Register;
2411  }
2412  return C_Unknown;
2413 }
2414 
2415 /// Try to replace an X constraint, which matches anything, with another that
2416 /// has more specific requirements based on the type of the corresponding
2417 /// operand.
2418 const char *TargetLowering::LowerXConstraint(EVT ConstraintVT) const{
2419  if (ConstraintVT.isInteger())
2420  return "r";
2421  if (ConstraintVT.isFloatingPoint())
2422  return "f"; // works for many targets
2423  return nullptr;
2424 }
2425 
2426 /// Lower the specified operand into the Ops vector.
2427 /// If it is invalid, don't add anything to Ops.
2429  std::string &Constraint,
2430  std::vector<SDValue> &Ops,
2431  SelectionDAG &DAG) const {
2432 
2433  if (Constraint.length() > 1) return;
2434 
2435  char ConstraintLetter = Constraint[0];
2436  switch (ConstraintLetter) {
2437  default: break;
2438  case 'X': // Allows any operand; labels (basic block) use this.
2439  if (Op.getOpcode() == ISD::BasicBlock) {
2440  Ops.push_back(Op);
2441  return;
2442  }
2444  case 'i': // Simple Integer or Relocatable Constant
2445  case 'n': // Simple Integer
2446  case 's': { // Relocatable Constant
2447  // These operands are interested in values of the form (GV+C), where C may
2448  // be folded in as an offset of GV, or it may be explicitly added. Also, it
2449  // is possible and fine if either GV or C are missing.
2452 
2453  // If we have "(add GV, C)", pull out GV/C
2454  if (Op.getOpcode() == ISD::ADD) {
2455  C = dyn_cast<ConstantSDNode>(Op.getOperand(1));
2457  if (!C || !GA) {
2458  C = dyn_cast<ConstantSDNode>(Op.getOperand(0));
2460  }
2461  if (!C || !GA) {
2462  C = nullptr;
2463  GA = nullptr;
2464  }
2465  }
2466 
2467  // If we find a valid operand, map to the TargetXXX version so that the
2468  // value itself doesn't get selected.
2469  if (GA) { // Either &GV or &GV+C
2470  if (ConstraintLetter != 'n') {
2471  int64_t Offs = GA->getOffset();
2472  if (C) Offs += C->getZExtValue();
2473  Ops.push_back(DAG.getTargetGlobalAddress(GA->getGlobal(),
2474  C ? SDLoc(C) : SDLoc(),
2475  Op.getValueType(), Offs));
2476  }
2477  return;
2478  }
2479  if (C) { // just C, no GV.
2480  // Simple constants are not allowed for 's'.
2481  if (ConstraintLetter != 's') {
2482  // gcc prints these as sign extended. Sign extend value to 64 bits
2483  // now; without this it would get ZExt'd later in
2484  // ScheduleDAGSDNodes::EmitNode, which is very generic.
2485  Ops.push_back(DAG.getTargetConstant(C->getSExtValue(),
2486  SDLoc(C), MVT::i64));
2487  }
2488  return;
2489  }
2490  break;
2491  }
2492  }
2493 }
2494 
2495 std::pair<unsigned, const TargetRegisterClass *>
2497  StringRef Constraint,
2498  MVT VT) const {
2499  if (Constraint.empty() || Constraint[0] != '{')
2500  return std::make_pair(0u, static_cast<TargetRegisterClass*>(nullptr));
2501  assert(*(Constraint.end()-1) == '}' && "Not a brace enclosed constraint?");
2502 
2503  // Remove the braces from around the name.
2504  StringRef RegName(Constraint.data()+1, Constraint.size()-2);
2505 
2506  std::pair<unsigned, const TargetRegisterClass*> R =
2507  std::make_pair(0u, static_cast<const TargetRegisterClass*>(nullptr));
2508 
2509  // Figure out which register class contains this reg.
2510  for (const TargetRegisterClass *RC : RI->regclasses()) {
2511  // If none of the value types for this register class are valid, we
2512  // can't use it. For example, 64-bit reg classes on 32-bit targets.
2513  if (!isLegalRC(*RI, *RC))
2514  continue;
2515 
2516  for (TargetRegisterClass::iterator I = RC->begin(), E = RC->end();
2517  I != E; ++I) {
2518  if (RegName.equals_lower(RI->getRegAsmName(*I))) {
2519  std::pair<unsigned, const TargetRegisterClass*> S =
2520  std::make_pair(*I, RC);
2521 
2522  // If this register class has the requested value type, return it,
2523  // otherwise keep searching and return the first class found
2524  // if no other is found which explicitly has the requested type.
2525  if (RI->isTypeLegalForClass(*RC, VT))
2526  return S;
2527  if (!R.second)
2528  R = S;
2529  }
2530  }
2531  }
2532 
2533  return R;
2534 }
2535 
2536 //===----------------------------------------------------------------------===//
2537 // Constraint Selection.
2538 
2539 /// Return true of this is an input operand that is a matching constraint like
2540 /// "4".
2542  assert(!ConstraintCode.empty() && "No known constraint!");
2543  return isdigit(static_cast<unsigned char>(ConstraintCode[0]));
2544 }
2545 
2546 /// If this is an input matching constraint, this method returns the output
2547 /// operand it matches.
2549  assert(!ConstraintCode.empty() && "No known constraint!");
2550  return atoi(ConstraintCode.c_str());
2551 }
2552 
2553 /// Split up the constraint string from the inline assembly value into the
2554 /// specific constraints and their prefixes, and also tie in the associated
2555 /// operand values.
2556 /// If this returns an empty vector, and if the constraint string itself
2557 /// isn't empty, there was an error parsing.
2560  const TargetRegisterInfo *TRI,
2561  ImmutableCallSite CS) const {
2562  /// Information about all of the constraints.
2563  AsmOperandInfoVector ConstraintOperands;
2564  const InlineAsm *IA = cast<InlineAsm>(CS.getCalledValue());
2565  unsigned maCount = 0; // Largest number of multiple alternative constraints.
2566 
2567  // Do a prepass over the constraints, canonicalizing them, and building up the
2568  // ConstraintOperands list.
2569  unsigned ArgNo = 0; // ArgNo - The argument of the CallInst.
2570  unsigned ResNo = 0; // ResNo - The result number of the next output.
2571 
2572  for (InlineAsm::ConstraintInfo &CI : IA->ParseConstraints()) {
2573  ConstraintOperands.emplace_back(std::move(CI));
2574  AsmOperandInfo &OpInfo = ConstraintOperands.back();
2575 
2576  // Update multiple alternative constraint count.
2577  if (OpInfo.multipleAlternatives.size() > maCount)
2578  maCount = OpInfo.multipleAlternatives.size();
2579 
2580  OpInfo.ConstraintVT = MVT::Other;
2581 
2582  // Compute the value type for each operand.
2583  switch (OpInfo.Type) {
2584  case InlineAsm::isOutput:
2585  // Indirect outputs just consume an argument.
2586  if (OpInfo.isIndirect) {
2587  OpInfo.CallOperandVal = const_cast<Value *>(CS.getArgument(ArgNo++));
2588  break;
2589  }
2590 
2591  // The return value of the call is this value. As such, there is no
2592  // corresponding argument.
2593  assert(!CS.getType()->isVoidTy() &&
2594  "Bad inline asm!");
2595  if (StructType *STy = dyn_cast<StructType>(CS.getType())) {
2596  OpInfo.ConstraintVT =
2597  getSimpleValueType(DL, STy->getElementType(ResNo));
2598  } else {
2599  assert(ResNo == 0 && "Asm only has one result!");
2600  OpInfo.ConstraintVT = getSimpleValueType(DL, CS.getType());
2601  }
2602  ++ResNo;
2603  break;
2604  case InlineAsm::isInput:
2605  OpInfo.CallOperandVal = const_cast<Value *>(CS.getArgument(ArgNo++));
2606  break;
2607  case InlineAsm::isClobber:
2608  // Nothing to do.
2609  break;
2610  }
2611 
2612  if (OpInfo.CallOperandVal) {
2613  llvm::Type *OpTy = OpInfo.CallOperandVal->getType();
2614  if (OpInfo.isIndirect) {
2615  llvm::PointerType *PtrTy = dyn_cast<PointerType>(OpTy);
2616  if (!PtrTy)
2617  report_fatal_error("Indirect operand for inline asm not a pointer!");
2618  OpTy = PtrTy->getElementType();
2619  }
2620 
2621  // Look for vector wrapped in a struct. e.g. { <16 x i8> }.
2622  if (StructType *STy = dyn_cast<StructType>(OpTy))
2623  if (STy->getNumElements() == 1)
2624  OpTy = STy->getElementType(0);
2625 
2626  // If OpTy is not a single value, it may be a struct/union that we
2627  // can tile with integers.
2628  if (!OpTy->isSingleValueType() && OpTy->isSized()) {
2629  unsigned BitSize = DL.getTypeSizeInBits(OpTy);
2630  switch (BitSize) {
2631  default: break;
2632  case 1:
2633  case 8:
2634  case 16:
2635  case 32:
2636  case 64:
2637  case 128:
2638  OpInfo.ConstraintVT =
2639  MVT::getVT(IntegerType::get(OpTy->getContext(), BitSize), true);
2640  break;
2641  }
2642  } else if (PointerType *PT = dyn_cast<PointerType>(OpTy)) {
2643  unsigned PtrSize = DL.getPointerSizeInBits(PT->getAddressSpace());
2644  OpInfo.ConstraintVT = MVT::getIntegerVT(PtrSize);
2645  } else {
2646  OpInfo.ConstraintVT = MVT::getVT(OpTy, true);
2647  }
2648  }
2649  }
2650 
2651  // If we have multiple alternative constraints, select the best alternative.
2652  if (!ConstraintOperands.empty()) {
2653  if (maCount) {
2654  unsigned bestMAIndex = 0;
2655  int bestWeight = -1;
2656  // weight: -1 = invalid match, and 0 = so-so match to 5 = good match.
2657  int weight = -1;
2658  unsigned maIndex;
2659  // Compute the sums of the weights for each alternative, keeping track
2660  // of the best (highest weight) one so far.
2661  for (maIndex = 0; maIndex < maCount; ++maIndex) {
2662  int weightSum = 0;
2663  for (unsigned cIndex = 0, eIndex = ConstraintOperands.size();
2664  cIndex != eIndex; ++cIndex) {
2665  AsmOperandInfo& OpInfo = ConstraintOperands[cIndex];
2666  if (OpInfo.Type == InlineAsm::isClobber)
2667  continue;
2668 
2669  // If this is an output operand with a matching input operand,
2670  // look up the matching input. If their types mismatch, e.g. one
2671  // is an integer, the other is floating point, or their sizes are
2672  // different, flag it as an maCantMatch.
2673  if (OpInfo.hasMatchingInput()) {
2674  AsmOperandInfo &Input = ConstraintOperands[OpInfo.MatchingInput];
2675  if (OpInfo.ConstraintVT != Input.ConstraintVT) {
2676  if ((OpInfo.ConstraintVT.isInteger() !=
2677  Input.ConstraintVT.isInteger()) ||
2678  (OpInfo.ConstraintVT.getSizeInBits() !=
2679  Input.ConstraintVT.getSizeInBits())) {
2680  weightSum = -1; // Can't match.
2681  break;
2682  }
2683  }
2684  }
2685  weight = getMultipleConstraintMatchWeight(OpInfo, maIndex);
2686  if (weight == -1) {
2687  weightSum = -1;
2688  break;
2689  }
2690  weightSum += weight;
2691  }
2692  // Update best.
2693  if (weightSum > bestWeight) {
2694  bestWeight = weightSum;
2695  bestMAIndex = maIndex;
2696  }
2697  }
2698 
2699  // Now select chosen alternative in each constraint.
2700  for (unsigned cIndex = 0, eIndex = ConstraintOperands.size();
2701  cIndex != eIndex; ++cIndex) {
2702  AsmOperandInfo& cInfo = ConstraintOperands[cIndex];
2703  if (cInfo.Type == InlineAsm::isClobber)
2704  continue;
2705  cInfo.selectAlternative(bestMAIndex);
2706  }
2707  }
2708  }
2709 
2710  // Check and hook up tied operands, choose constraint code to use.
2711  for (unsigned cIndex = 0, eIndex = ConstraintOperands.size();
2712  cIndex != eIndex; ++cIndex) {
2713  AsmOperandInfo& OpInfo = ConstraintOperands[cIndex];
2714 
2715  // If this is an output operand with a matching input operand, look up the
2716  // matching input. If their types mismatch, e.g. one is an integer, the
2717  // other is floating point, or their sizes are different, flag it as an
2718  // error.
2719  if (OpInfo.hasMatchingInput()) {
2720  AsmOperandInfo &Input = ConstraintOperands[OpInfo.MatchingInput];
2721 
2722  if (OpInfo.ConstraintVT != Input.ConstraintVT) {
2723  std::pair<unsigned, const TargetRegisterClass *> MatchRC =
2725  OpInfo.ConstraintVT);
2726  std::pair<unsigned, const TargetRegisterClass *> InputRC =
2728  Input.ConstraintVT);
2729  if ((OpInfo.ConstraintVT.isInteger() !=
2730  Input.ConstraintVT.isInteger()) ||
2731  (MatchRC.second != InputRC.second)) {
2732  report_fatal_error("Unsupported asm: input constraint"
2733  " with a matching output constraint of"
2734  " incompatible type!");
2735  }
2736  }
2737  }
2738  }
2739 
2740  return ConstraintOperands;
2741 }
2742 
2743 /// Return an integer indicating how general CT is.
2745  switch (CT) {
2748  return 0;
2750  return 1;
2752  return 2;
2754  return 3;
2755  }
2756  llvm_unreachable("Invalid constraint type");
2757 }
2758 
2759 /// Examine constraint type and operand type and determine a weight value.
2760 /// This object must already have been set up with the operand type
2761 /// and the current alternative constraint selected.
2764  AsmOperandInfo &info, int maIndex) const {
2766  if (maIndex >= (int)info.multipleAlternatives.size())
2767  rCodes = &info.Codes;
2768  else
2769  rCodes = &info.multipleAlternatives[maIndex].Codes;
2770  ConstraintWeight BestWeight = CW_Invalid;
2771 
2772  // Loop over the options, keeping track of the most general one.
2773  for (unsigned i = 0, e = rCodes->size(); i != e; ++i) {
2774  ConstraintWeight weight =
2775  getSingleConstraintMatchWeight(info, (*rCodes)[i].c_str());
2776  if (weight > BestWeight)
2777  BestWeight = weight;
2778  }
2779 
2780  return BestWeight;
2781 }
2782 
2783 /// Examine constraint type and operand type and determine a weight value.
2784 /// This object must already have been set up with the operand type
2785 /// and the current alternative constraint selected.
2788  AsmOperandInfo &info, const char *constraint) const {
2789  ConstraintWeight weight = CW_Invalid;
2790  Value *CallOperandVal = info.CallOperandVal;
2791  // If we don't have a value, we can't do a match,
2792  // but allow it at the lowest weight.
2793  if (!CallOperandVal)
2794  return CW_Default;
2795  // Look at the constraint type.
2796  switch (*constraint) {
2797  case 'i': // immediate integer.
2798  case 'n': // immediate integer with a known value.
2799  if (isa<ConstantInt>(CallOperandVal))
2800  weight = CW_Constant;
2801  break;
2802  case 's': // non-explicit intregal immediate.
2803  if (isa<GlobalValue>(CallOperandVal))
2804  weight = CW_Constant;
2805  break;
2806  case 'E': // immediate float if host format.
2807  case 'F': // immediate float.
2808  if (isa<ConstantFP>(CallOperandVal))
2809  weight = CW_Constant;
2810  break;
2811  case '<': // memory operand with autodecrement.
2812  case '>': // memory operand with autoincrement.
2813  case 'm': // memory operand.
2814  case 'o': // offsettable memory operand
2815  case 'V': // non-offsettable memory operand
2816  weight = CW_Memory;
2817  break;
2818  case 'r': // general register.
2819  case 'g': // general register, memory operand or immediate integer.
2820  // note: Clang converts "g" to "imr".
2821  if (CallOperandVal->getType()->isIntegerTy())
2822  weight = CW_Register;
2823  break;
2824  case 'X': // any operand.
2825  default:
2826  weight = CW_Default;
2827  break;
2828  }
2829  return weight;
2830 }
2831 
2832 /// If there are multiple different constraints that we could pick for this
2833 /// operand (e.g. "imr") try to pick the 'best' one.
2834 /// This is somewhat tricky: constraints fall into four classes:
2835 /// Other -> immediates and magic values
2836 /// Register -> one specific register
2837 /// RegisterClass -> a group of regs
2838 /// Memory -> memory
2839 /// Ideally, we would pick the most specific constraint possible: if we have
2840 /// something that fits into a register, we would pick it. The problem here
2841 /// is that if we have something that could either be in a register or in
2842 /// memory that use of the register could cause selection of *other*
2843 /// operands to fail: they might only succeed if we pick memory. Because of
2844 /// this the heuristic we use is:
2845 ///
2846 /// 1) If there is an 'other' constraint, and if the operand is valid for
2847 /// that constraint, use it. This makes us take advantage of 'i'
2848 /// constraints when available.
2849 /// 2) Otherwise, pick the most general constraint present. This prefers
2850 /// 'm' over 'r', for example.
2851 ///
2853  const TargetLowering &TLI,
2854  SDValue Op, SelectionDAG *DAG) {
2855  assert(OpInfo.Codes.size() > 1 && "Doesn't have multiple constraint options");
2856  unsigned BestIdx = 0;
2858  int BestGenerality = -1;
2859 
2860  // Loop over the options, keeping track of the most general one.
2861  for (unsigned i = 0, e = OpInfo.Codes.size(); i != e; ++i) {
2863  TLI.getConstraintType(OpInfo.Codes[i]);
2864 
2865  // If this is an 'other' constraint, see if the operand is valid for it.
2866  // For example, on X86 we might have an 'rI' constraint. If the operand
2867  // is an integer in the range [0..31] we want to use I (saving a load
2868  // of a register), otherwise we must use 'r'.
2869  if (CType == TargetLowering::C_Other && Op.getNode()) {
2870  assert(OpInfo.Codes[i].size() == 1 &&
2871  "Unhandled multi-letter 'other' constraint");
2872  std::vector<SDValue> ResultOps;
2873  TLI.LowerAsmOperandForConstraint(Op, OpInfo.Codes[i],
2874  ResultOps, *DAG);
2875  if (!ResultOps.empty()) {
2876  BestType = CType;
2877  BestIdx = i;
2878  break;
2879  }
2880  }
2881 
2882  // Things with matching constraints can only be registers, per gcc
2883  // documentation. This mainly affects "g" constraints.
2884  if (CType == TargetLowering::C_Memory && OpInfo.hasMatchingInput())
2885  continue;
2886 
2887  // This constraint letter is more general than the previous one, use it.
2888  int Generality = getConstraintGenerality(CType);
2889  if (Generality > BestGenerality) {
2890  BestType = CType;
2891  BestIdx = i;
2892  BestGenerality = Generality;
2893  }
2894  }
2895 
2896  OpInfo.ConstraintCode = OpInfo.Codes[BestIdx];
2897  OpInfo.ConstraintType = BestType;
2898 }
2899 
2900 /// Determines the constraint code and constraint type to use for the specific
2901 /// AsmOperandInfo, setting OpInfo.ConstraintCode and OpInfo.ConstraintType.
2903  SDValue Op,
2904  SelectionDAG *DAG) const {
2905  assert(!OpInfo.Codes.empty() && "Must have at least one constraint");
2906 
2907  // Single-letter constraints ('r') are very common.
2908  if (OpInfo.Codes.size() == 1) {
2909  OpInfo.ConstraintCode = OpInfo.Codes[0];
2911  } else {
2912  ChooseConstraint(OpInfo, *this, Op, DAG);
2913  }
2914 
2915  // 'X' matches anything.
2916  if (OpInfo.ConstraintCode == "X" && OpInfo.CallOperandVal) {
2917  // Labels and constants are handled elsewhere ('X' is the only thing
2918  // that matches labels). For Functions, the type here is the type of
2919  // the result, which is not what we want to look at; leave them alone.
2920  Value *v = OpInfo.CallOperandVal;
2921  if (isa<BasicBlock>(v) || isa<ConstantInt>(v) || isa<Function>(v)) {
2922  OpInfo.CallOperandVal = v;
2923  return;
2924  }
2925 
2926  // Otherwise, try to resolve it to something we know about by looking at
2927  // the actual operand type.
2928  if (const char *Repl = LowerXConstraint(OpInfo.ConstraintVT)) {
2929  OpInfo.ConstraintCode = Repl;
2931  }
2932  }
2933 }
2934 
2935 /// \brief Given an exact SDIV by a constant, create a multiplication
2936 /// with the multiplicative inverse of the constant.
2938  const SDLoc &dl, SelectionDAG &DAG,
2939  std::vector<SDNode *> &Created) {
2940  assert(d != 0 && "Division by zero!");
2941 
2942  // Shift the value upfront if it is even, so the LSB is one.
2943  unsigned ShAmt = d.countTrailingZeros();
2944  if (ShAmt) {
2945  // TODO: For UDIV use SRL instead of SRA.
2946  SDValue Amt =
2947  DAG.getConstant(ShAmt, dl, TLI.getShiftAmountTy(Op1.getValueType(),
2948  DAG.getDataLayout()));
2950  Flags.setExact(true);
2951  Op1 = DAG.getNode(ISD::SRA, dl, Op1.getValueType(), Op1, Amt, Flags);
2952  Created.push_back(Op1.getNode());
2953  d.ashrInPlace(ShAmt);
2954  }
2955 
2956  // Calculate the multiplicative inverse, using Newton's method.
2957  APInt t, xn = d;
2958  while ((t = d*xn) != 1)
2959  xn *= APInt(d.getBitWidth(), 2) - t;
2960 
2961  SDValue Op2 = DAG.getConstant(xn, dl, Op1.getValueType());
2962  SDValue Mul = DAG.getNode(ISD::MUL, dl, Op1.getValueType(), Op1, Op2);
2963  Created.push_back(Mul.getNode());
2964  return Mul;
2965 }
2966 
2968  SelectionDAG &DAG,
2969  std::vector<SDNode *> *Created) const {
2971  const TargetLowering &TLI = DAG.getTargetLoweringInfo();
2972  if (TLI.isIntDivCheap(N->getValueType(0), Attr))
2973  return SDValue(N,0); // Lower SDIV as SDIV
2974  return SDValue();
2975 }
2976 
2977 /// \brief Given an ISD::SDIV node expressing a divide by constant,
2978 /// return a DAG expression to select that will generate the same value by
2979 /// multiplying by a magic number.
2980 /// Ref: "Hacker's Delight" or "The PowerPC Compiler Writer's Guide".
2982  SelectionDAG &DAG, bool IsAfterLegalization,
2983  std::vector<SDNode *> *Created) const {
2984  assert(Created && "No vector to hold sdiv ops.");
2985 
2986  EVT VT = N->getValueType(0);
2987  SDLoc dl(N);
2988 
2989  // Check to see if we can do this.
2990  // FIXME: We should be more aggressive here.
2991  if (!isTypeLegal(VT))
2992  return SDValue();
2993 
2994  // If the sdiv has an 'exact' bit we can use a simpler lowering.
2995  if (N->getFlags().hasExact())
2996  return BuildExactSDIV(*this, N->getOperand(0), Divisor, dl, DAG, *Created);
2997 
2998  APInt::ms magics = Divisor.magic();
2999 
3000  // Multiply the numerator (operand 0) by the magic value
3001  // FIXME: We should support doing a MUL in a wider type
3002  SDValue Q;
3003  if (IsAfterLegalization ? isOperationLegal(ISD::MULHS, VT) :
3005  Q = DAG.getNode(ISD::MULHS, dl, VT, N->getOperand(0),
3006  DAG.getConstant(magics.m, dl, VT));
3007  else if (IsAfterLegalization ? isOperationLegal(ISD::SMUL_LOHI, VT) :
3009  Q = SDValue(DAG.getNode(ISD::SMUL_LOHI, dl, DAG.getVTList(VT, VT),
3010  N->getOperand(0),
3011  DAG.getConstant(magics.m, dl, VT)).getNode(), 1);
3012  else
3013  return SDValue(); // No mulhs or equvialent
3014  // If d > 0 and m < 0, add the numerator
3015  if (Divisor.isStrictlyPositive() && magics.m.isNegative()) {
3016  Q = DAG.getNode(ISD::ADD, dl, VT, Q, N->getOperand(0));
3017  Created->push_back(Q.getNode());
3018  }
3019  // If d < 0 and m > 0, subtract the numerator.
3020  if (Divisor.isNegative() && magics.m.isStrictlyPositive()) {
3021  Q = DAG.getNode(ISD::SUB, dl, VT, Q, N->getOperand(0));
3022  Created->push_back(Q.getNode());
3023  }
3024  auto &DL = DAG.getDataLayout();
3025  // Shift right algebraic if shift value is nonzero
3026  if (magics.s > 0) {
3027  Q = DAG.getNode(
3028  ISD::SRA, dl, VT, Q,
3029  DAG.getConstant(magics.s, dl, getShiftAmountTy(Q.getValueType(), DL)));
3030  Created->push_back(Q.getNode());
3031  }
3032  // Extract the sign bit and add it to the quotient
3033  SDValue T =
3034  DAG.getNode(ISD::SRL, dl, VT, Q,
3035  DAG.getConstant(VT.getScalarSizeInBits() - 1, dl,
3036  getShiftAmountTy(Q.getValueType(), DL)));
3037  Created->push_back(T.getNode());
3038  return DAG.getNode(ISD::ADD, dl, VT, Q, T);
3039 }
3040 
3041 /// \brief Given an ISD::UDIV node expressing a divide by constant,
3042 /// return a DAG expression to select that will generate the same value by
3043 /// multiplying by a magic number.
3044 /// Ref: "Hacker's Delight" or "The PowerPC Compiler Writer's Guide".
3046  SelectionDAG &DAG, bool IsAfterLegalization,
3047  std::vector<SDNode *> *Created) const {
3048  assert(Created && "No vector to hold udiv ops.");
3049 
3050  EVT VT = N->getValueType(0);
3051  SDLoc dl(N);
3052  auto &DL = DAG.getDataLayout();
3053 
3054  // Check to see if we can do this.
3055  // FIXME: We should be more aggressive here.
3056  if (!isTypeLegal(VT))
3057  return SDValue();
3058 
3059  // FIXME: We should use a narrower constant when the upper
3060  // bits are known to be zero.
3061  APInt::mu magics = Divisor.magicu();
3062 
3063  SDValue Q = N->getOperand(0);
3064 
3065  // If the divisor is even, we can avoid using the expensive fixup by shifting
3066  // the divided value upfront.
3067  if (magics.a != 0 && !Divisor[0]) {
3068  unsigned Shift = Divisor.countTrailingZeros();
3069  Q = DAG.getNode(
3070  ISD::SRL, dl, VT, Q,
3071  DAG.getConstant(Shift, dl, getShiftAmountTy(Q.getValueType(), DL)));
3072  Created->push_back(Q.getNode());
3073 
3074  // Get magic number for the shifted divisor.
3075  magics = Divisor.lshr(Shift).magicu(Shift);
3076  assert(magics.a == 0 && "Should use cheap fixup now");
3077  }
3078 
3079  // Multiply the numerator (operand 0) by the magic value
3080  // FIXME: We should support doing a MUL in a wider type
3081  if (IsAfterLegalization ? isOperationLegal(ISD::MULHU, VT) :
3083  Q = DAG.getNode(ISD::MULHU, dl, VT, Q, DAG.getConstant(magics.m, dl, VT));
3084  else if (IsAfterLegalization ? isOperationLegal(ISD::UMUL_LOHI, VT) :
3086  Q = SDValue(DAG.getNode(ISD::UMUL_LOHI, dl, DAG.getVTList(VT, VT), Q,
3087  DAG.getConstant(magics.m, dl, VT)).getNode(), 1);
3088  else
3089  return SDValue(); // No mulhu or equivalent
3090 
3091  Created->push_back(Q.getNode());
3092 
3093  if (magics.a == 0) {
3094  assert(magics.s < Divisor.getBitWidth() &&
3095  "We shouldn't generate an undefined shift!");
3096  return DAG.getNode(
3097  ISD::SRL, dl, VT, Q,
3098  DAG.getConstant(magics.s, dl, getShiftAmountTy(Q.getValueType(), DL)));
3099  } else {
3100  SDValue NPQ = DAG.getNode(ISD::SUB, dl, VT, N->getOperand(0), Q);
3101  Created->push_back(NPQ.getNode());
3102  NPQ = DAG.getNode(
3103  ISD::SRL, dl, VT, NPQ,
3104  DAG.getConstant(1, dl, getShiftAmountTy(NPQ.getValueType(), DL)));
3105  Created->push_back(NPQ.getNode());
3106  NPQ = DAG.getNode(ISD::ADD, dl, VT, NPQ, Q);
3107  Created->push_back(NPQ.getNode());
3108  return DAG.getNode(
3109  ISD::SRL, dl, VT, NPQ,
3110  DAG.getConstant(magics.s - 1, dl,
3111  getShiftAmountTy(NPQ.getValueType(), DL)));
3112  }
3113 }
3114 
3115 bool TargetLowering::
3117  if (!isa<ConstantSDNode>(Op.getOperand(0))) {
3118  DAG.getContext()->emitError("argument to '__builtin_return_address' must "
3119  "be a constant integer");
3120  return true;
3121  }
3122 
3123  return false;
3124 }
3125 
3126 //===----------------------------------------------------------------------===//
3127 // Legalization Utilities
3128 //===----------------------------------------------------------------------===//
3129 
3130 bool TargetLowering::expandMUL_LOHI(unsigned Opcode, EVT VT, SDLoc dl,
3131  SDValue LHS, SDValue RHS,
3132  SmallVectorImpl<SDValue> &Result,
3133  EVT HiLoVT, SelectionDAG &DAG,
3135  SDValue LH, SDValue RL, SDValue RH) const {
3136  assert(Opcode == ISD::MUL || Opcode == ISD::UMUL_LOHI ||
3137  Opcode == ISD::SMUL_LOHI);
3138 
3139  bool HasMULHS = (Kind == MulExpansionKind::Always) ||
3141  bool HasMULHU = (Kind == MulExpansionKind::Always) ||
3143  bool HasSMUL_LOHI = (Kind == MulExpansionKind::Always) ||
3145  bool HasUMUL_LOHI = (Kind == MulExpansionKind::Always) ||
3147 
3148  if (!HasMULHU && !HasMULHS && !HasUMUL_LOHI && !HasSMUL_LOHI)
3149  return false;
3150 
3151  unsigned OuterBitSize = VT.getScalarSizeInBits();
3152  unsigned InnerBitSize = HiLoVT.getScalarSizeInBits();
3153  unsigned LHSSB = DAG.ComputeNumSignBits(LHS);
3154  unsigned RHSSB = DAG.ComputeNumSignBits(RHS);
3155 
3156  // LL, LH, RL, and RH must be either all NULL or all set to a value.
3157  assert((LL.getNode() && LH.getNode() && RL.getNode() && RH.getNode()) ||
3158  (!LL.getNode() && !LH.getNode() && !RL.getNode() && !RH.getNode()));
3159 
3160  SDVTList VTs = DAG.getVTList(HiLoVT, HiLoVT);
3161  auto MakeMUL_LOHI = [&](SDValue L, SDValue R, SDValue &Lo, SDValue &Hi,
3162  bool Signed) -> bool {
3163  if ((Signed && HasSMUL_LOHI) || (!Signed && HasUMUL_LOHI)) {
3164  Lo = DAG.getNode(Signed ? ISD::SMUL_LOHI : ISD::UMUL_LOHI, dl, VTs, L, R);
3165  Hi = SDValue(Lo.getNode(), 1);
3166  return true;
3167  }
3168  if ((Signed && HasMULHS) || (!Signed && HasMULHU)) {
3169  Lo = DAG.getNode(ISD::MUL, dl, HiLoVT, L, R);
3170  Hi = DAG.getNode(Signed ? ISD::MULHS : ISD::MULHU, dl, HiLoVT, L, R);
3171  return true;
3172  }
3173  return false;
3174  };
3175 
3176  SDValue Lo, Hi;
3177 
3178  if (!LL.getNode() && !RL.getNode() &&
3180  LL = DAG.getNode(ISD::TRUNCATE, dl, HiLoVT, LHS);
3181  RL = DAG.getNode(ISD::TRUNCATE, dl, HiLoVT, RHS);
3182  }
3183 
3184  if (!LL.getNode())
3185  return false;
3186 
3187  APInt HighMask = APInt::getHighBitsSet(OuterBitSize, InnerBitSize);
3188  if (DAG.MaskedValueIsZero(LHS, HighMask) &&
3189  DAG.MaskedValueIsZero(RHS, HighMask)) {
3190  // The inputs are both zero-extended.
3191  if (MakeMUL_LOHI(LL, RL, Lo, Hi, false)) {
3192  Result.push_back(Lo);
3193  Result.push_back(Hi);
3194  if (Opcode != ISD::MUL) {
3195  SDValue Zero = DAG.getConstant(0, dl, HiLoVT);
3196  Result.push_back(Zero);
3197  Result.push_back(Zero);
3198  }
3199  return true;
3200  }
3201  }
3202 
3203  if (!VT.isVector() && Opcode == ISD::MUL && LHSSB > InnerBitSize &&
3204  RHSSB > InnerBitSize) {
3205  // The input values are both sign-extended.
3206  // TODO non-MUL case?
3207  if (MakeMUL_LOHI(LL, RL, Lo, Hi, true)) {
3208  Result.push_back(Lo);
3209  Result.push_back(Hi);
3210  return true;
3211  }
3212  }
3213 
3214  unsigned ShiftAmount = OuterBitSize - InnerBitSize;
3215  EVT ShiftAmountTy = getShiftAmountTy(VT, DAG.getDataLayout());
3216  if (APInt::getMaxValue(ShiftAmountTy.getSizeInBits()).ult(ShiftAmount)) {
3217  // FIXME getShiftAmountTy does not always return a sensible result when VT
3218  // is an illegal type, and so the type may be too small to fit the shift
3219  // amount. Override it with i32. The shift will have to be legalized.
3220  ShiftAmountTy = MVT::i32;
3221  }
3222  SDValue Shift = DAG.getConstant(ShiftAmount, dl, ShiftAmountTy);
3223 
3224  if (!LH.getNode() && !RH.getNode() &&
3227  LH = DAG.getNode(ISD::SRL, dl, VT, LHS, Shift);
3228  LH = DAG.getNode(ISD::TRUNCATE, dl, HiLoVT, LH);
3229  RH = DAG.getNode(ISD::SRL, dl, VT, RHS, Shift);
3230  RH = DAG.getNode(ISD::TRUNCATE, dl, HiLoVT, RH);
3231  }
3232 
3233  if (!LH.getNode())
3234  return false;
3235 
3236  if (!MakeMUL_LOHI(LL, RL, Lo, Hi, false))
3237  return false;
3238 
3239  Result.push_back(Lo);
3240 
3241  if (Opcode == ISD::MUL) {
3242  RH = DAG.getNode(ISD::MUL, dl, HiLoVT, LL, RH);
3243  LH = DAG.getNode(ISD::MUL, dl, HiLoVT, LH, RL);
3244  Hi = DAG.getNode(ISD::ADD, dl, HiLoVT, Hi, RH);
3245  Hi = DAG.getNode(ISD::ADD, dl, HiLoVT, Hi, LH);
3246  Result.push_back(Hi);
3247  return true;
3248  }
3249 
3250  // Compute the full width result.
3251  auto Merge = [&](SDValue Lo, SDValue Hi) -> SDValue {
3252  Lo = DAG.getNode(ISD::ZERO_EXTEND, dl, VT, Lo);
3253  Hi = DAG.getNode(ISD::ZERO_EXTEND, dl, VT, Hi);
3254  Hi = DAG.getNode(ISD::SHL, dl, VT, Hi, Shift);
3255  return DAG.getNode(ISD::OR, dl, VT, Lo, Hi);
3256  };
3257 
3258  SDValue Next = DAG.getNode(ISD::ZERO_EXTEND, dl, VT, Hi);
3259  if (!MakeMUL_LOHI(LL, RH, Lo, Hi, false))
3260  return false;
3261 
3262  // This is effectively the add part of a multiply-add of half-sized operands,
3263  // so it cannot overflow.
3264  Next = DAG.getNode(ISD::ADD, dl, VT, Next, Merge(Lo, Hi));
3265 
3266  if (!MakeMUL_LOHI(LH, RL, Lo, Hi, false))
3267  return false;
3268 
3269  Next = DAG.getNode(ISD::ADDC, dl, DAG.getVTList(VT, MVT::Glue), Next,
3270  Merge(Lo, Hi));
3271 
3272  SDValue Carry = Next.getValue(1);
3273  Result.push_back(DAG.getNode(ISD::TRUNCATE, dl, HiLoVT, Next));
3274  Next = DAG.getNode(ISD::SRL, dl, VT, Next, Shift);
3275 
3276  if (!MakeMUL_LOHI(LH, RH, Lo, Hi, Opcode == ISD::SMUL_LOHI))
3277  return false;
3278 
3279  SDValue Zero = DAG.getConstant(0, dl, HiLoVT);
3280  Hi = DAG.getNode(ISD::ADDE, dl, DAG.getVTList(HiLoVT, MVT::Glue), Hi, Zero,
3281  Carry);
3282  Next = DAG.getNode(ISD::ADD, dl, VT, Next, Merge(Lo, Hi));
3283 
3284  if (Opcode == ISD::SMUL_LOHI) {
3285  SDValue NextSub = DAG.getNode(ISD::SUB, dl, VT, Next,
3286  DAG.getNode(ISD::ZERO_EXTEND, dl, VT, RL));
3287  Next = DAG.getSelectCC(dl, LH, Zero, NextSub, Next, ISD::SETLT);
3288 
3289  NextSub = DAG.getNode(ISD::SUB, dl, VT, Next,
3290  DAG.getNode(ISD::ZERO_EXTEND, dl, VT, LL));
3291  Next = DAG.getSelectCC(dl, RH, Zero, NextSub, Next, ISD::SETLT);
3292  }
3293 
3294  Result.push_back(DAG.getNode(ISD::TRUNCATE, dl, HiLoVT, Next));
3295  Next = DAG.getNode(ISD::SRL, dl, VT, Next, Shift);
3296  Result.push_back(DAG.getNode(ISD::TRUNCATE, dl, HiLoVT, Next));
3297  return true;
3298 }
3299 
3302  SDValue LL, SDValue LH, SDValue RL,
3303  SDValue RH) const {
3304  SmallVector<SDValue, 2> Result;
3305  bool Ok = expandMUL_LOHI(N->getOpcode(), N->getValueType(0), N,
3306  N->getOperand(0), N->getOperand(1), Result, HiLoVT,
3307  DAG, Kind, LL, LH, RL, RH);
3308  if (Ok) {
3309  assert(Result.size() == 2);
3310  Lo = Result[0];
3311  Hi = Result[1];
3312  }
3313  return Ok;
3314 }
3315 
3317  SelectionDAG &DAG) const {
3318  EVT VT = Node->getOperand(0).getValueType();
3319  EVT NVT = Node->getValueType(0);
3320  SDLoc dl(SDValue(Node, 0));
3321 
3322  // FIXME: Only f32 to i64 conversions are supported.
3323  if (VT != MVT::f32 || NVT != MVT::i64)
3324  return false;
3325 
3326  // Expand f32 -> i64 conversion
3327  // This algorithm comes from compiler-rt's implementation of fixsfdi:
3328  // https://github.com/llvm-mirror/compiler-rt/blob/master/lib/builtins/fixsfdi.c
3329  EVT IntVT = EVT::getIntegerVT(*DAG.getContext(),
3330  VT.getSizeInBits());
3331  SDValue ExponentMask = DAG.getConstant(0x7F800000, dl, IntVT);
3332  SDValue ExponentLoBit = DAG.getConstant(23, dl, IntVT);
3333  SDValue Bias = DAG.getConstant(127, dl, IntVT);
3334  SDValue SignMask = DAG.getConstant(APInt::getSignMask(VT.getSizeInBits()), dl,
3335  IntVT);
3336  SDValue SignLowBit = DAG.getConstant(VT.getSizeInBits() - 1, dl, IntVT);
3337  SDValue MantissaMask = DAG.getConstant(0x007FFFFF, dl, IntVT);
3338 
3339  SDValue Bits = DAG.getNode(ISD::BITCAST, dl, IntVT, Node->getOperand(0));
3340 
3341  auto &DL = DAG.getDataLayout();
3342  SDValue ExponentBits = DAG.getNode(
3343  ISD::SRL, dl, IntVT, DAG.getNode(ISD::AND, dl, IntVT, Bits, ExponentMask),
3344  DAG.getZExtOrTrunc(ExponentLoBit, dl, getShiftAmountTy(IntVT, DL)));
3345  SDValue Exponent = DAG.getNode(ISD::SUB, dl, IntVT, ExponentBits, Bias);
3346 
3347  SDValue Sign = DAG.getNode(
3348  ISD::SRA, dl, IntVT, DAG.getNode(ISD::AND, dl, IntVT, Bits, SignMask),
3349  DAG.getZExtOrTrunc(SignLowBit, dl, getShiftAmountTy(IntVT, DL)));
3350  Sign = DAG.getSExtOrTrunc(Sign, dl, NVT);
3351 
3352  SDValue R = DAG.getNode(ISD::OR, dl, IntVT,
3353  DAG.getNode(ISD::AND, dl, IntVT, Bits, MantissaMask),
3354  DAG.getConstant(0x00800000, dl, IntVT));
3355 
3356  R = DAG.getZExtOrTrunc(R, dl, NVT);
3357 
3358  R = DAG.getSelectCC(
3359  dl, Exponent, ExponentLoBit,
3360  DAG.getNode(ISD::SHL, dl, NVT, R,
3361  DAG.getZExtOrTrunc(
3362  DAG.getNode(ISD::SUB, dl, IntVT, Exponent, ExponentLoBit),
3363  dl, getShiftAmountTy(IntVT, DL))),
3364  DAG.getNode(ISD::SRL, dl, NVT, R,
3365  DAG.getZExtOrTrunc(
3366  DAG.getNode(ISD::SUB, dl, IntVT, ExponentLoBit, Exponent),
3367  dl, getShiftAmountTy(IntVT, DL))),
3368  ISD::SETGT);
3369 
3370  SDValue Ret = DAG.getNode(ISD::SUB, dl, NVT,
3371  DAG.getNode(ISD::XOR, dl, NVT, R, Sign),
3372  Sign);
3373 
3374  Result = DAG.getSelectCC(dl, Exponent, DAG.getConstant(0, dl, IntVT),
3375  DAG.getConstant(0, dl, NVT), Ret, ISD::SETLT);
3376  return true;
3377 }
3378 
3380  SelectionDAG &DAG) const {
3381  SDLoc SL(LD);
3382  SDValue Chain = LD->getChain();
3383  SDValue BasePTR = LD->getBasePtr();
3384  EVT SrcVT = LD->getMemoryVT();
3385  ISD::LoadExtType ExtType = LD->getExtensionType();
3386 
3387  unsigned NumElem = SrcVT.getVectorNumElements();
3388 
3389  EVT SrcEltVT = SrcVT.getScalarType();
3390  EVT DstEltVT = LD->getValueType(0).getScalarType();
3391 
3392  unsigned Stride = SrcEltVT.getSizeInBits() / 8;
3393  assert(SrcEltVT.isByteSized());
3394 
3395  EVT PtrVT = BasePTR.getValueType();
3396 
3398  SmallVector<SDValue, 8> LoadChains;
3399 
3400  for (unsigned Idx = 0; Idx < NumElem; ++Idx) {
3401  SDValue ScalarLoad =
3402  DAG.getExtLoad(ExtType, SL, DstEltVT, Chain, BasePTR,
3403  LD->getPointerInfo().getWithOffset(Idx * Stride),
3404  SrcEltVT, MinAlign(LD->getAlignment(), Idx * Stride),
3405  LD->getMemOperand()->getFlags(), LD->getAAInfo());
3406 
3407  BasePTR = DAG.getNode(ISD::ADD, SL, PtrVT, BasePTR,
3408  DAG.getConstant(Stride, SL, PtrVT));
3409 
3410  Vals.push_back(ScalarLoad.getValue(0));
3411  LoadChains.push_back(ScalarLoad.getValue(1));
3412  }
3413 
3414  SDValue NewChain = DAG.getNode(ISD::TokenFactor, SL, MVT::Other, LoadChains);
3415  SDValue Value = DAG.getBuildVector(LD->getValueType(0), SL, Vals);
3416 
3417  return DAG.getMergeValues({ Value, NewChain }, SL);
3418 }
3419 
3420 // FIXME: This relies on each element having a byte size, otherwise the stride
3421 // is 0 and just overwrites the same location. ExpandStore currently expects
3422 // this broken behavior.
3424  SelectionDAG &DAG) const {
3425  SDLoc SL(ST);
3426 
3427  SDValue Chain = ST->getChain();
3428  SDValue BasePtr = ST->getBasePtr();
3429  SDValue Value = ST->getValue();
3430  EVT StVT = ST->getMemoryVT();
3431 
3432  // The type of the data we want to save
3433  EVT RegVT = Value.getValueType();
3434  EVT RegSclVT = RegVT.getScalarType();
3435 
3436  // The type of data as saved in memory.
3437  EVT MemSclVT = StVT.getScalarType();
3438 
3439  EVT PtrVT = BasePtr.getValueType();
3440 
3441  // Store Stride in bytes
3442  unsigned Stride = MemSclVT.getSizeInBits() / 8;
3443  EVT IdxVT = getVectorIdxTy(DAG.getDataLayout());
3444  unsigned NumElem = StVT.getVectorNumElements();
3445 
3446  // Extract each of the elements from the original vector and save them into
3447  // memory individually.
3448  SmallVector<SDValue, 8> Stores;
3449  for (unsigned Idx = 0; Idx < NumElem; ++Idx) {
3450  SDValue Elt = DAG.getNode(ISD::EXTRACT_VECTOR_ELT, SL, RegSclVT, Value,
3451  DAG.getConstant(Idx, SL, IdxVT));
3452 
3453  SDValue Ptr = DAG.getNode(ISD::ADD, SL, PtrVT, BasePtr,
3454  DAG.getConstant(Idx * Stride, SL, PtrVT));
3455 
3456  // This scalar TruncStore may be illegal, but we legalize it later.
3457  SDValue Store = DAG.getTruncStore(
3458  Chain, SL, Elt, Ptr, ST->getPointerInfo().getWithOffset(Idx * Stride),
3459  MemSclVT, MinAlign(ST->getAlignment(), Idx * Stride),
3460  ST->getMemOperand()->getFlags(), ST->getAAInfo());
3461 
3462  Stores.push_back(Store);
3463  }
3464 
3465  return DAG.getNode(ISD::TokenFactor, SL, MVT::Other, Stores);
3466 }
3467 
3468 std::pair<SDValue, SDValue>
3471  "unaligned indexed loads not implemented!");
3472  SDValue Chain = LD->getChain();
3473  SDValue Ptr = LD->getBasePtr();
3474  EVT VT = LD->getValueType(0);
3475  EVT LoadedVT = LD->getMemoryVT();
3476  SDLoc dl(LD);
3477  if (VT.isFloatingPoint() || VT.isVector()) {
3478  EVT intVT = EVT::getIntegerVT(*DAG.getContext(), LoadedVT.getSizeInBits());
3479  if (isTypeLegal(intVT) && isTypeLegal(LoadedVT)) {
3480  if (!isOperationLegalOrCustom(ISD::LOAD, intVT)) {
3481  // Scalarize the load and let the individual components be handled.
3482  SDValue Scalarized = scalarizeVectorLoad(LD, DAG);
3483  return std::make_pair(Scalarized.getValue(0), Scalarized.getValue(1));
3484  }
3485 
3486  // Expand to a (misaligned) integer load of the same size,
3487  // then bitconvert to floating point or vector.
3488  SDValue newLoad = DAG.getLoad(intVT, dl, Chain, Ptr,
3489  LD->getMemOperand());
3490  SDValue Result = DAG.getNode(ISD::BITCAST, dl, LoadedVT, newLoad);
3491  if (LoadedVT != VT)
3492  Result = DAG.getNode(VT.isFloatingPoint() ? ISD::FP_EXTEND :
3493  ISD::ANY_EXTEND, dl, VT, Result);
3494 
3495  return std::make_pair(Result, newLoad.getValue(1));
3496  }
3497 
3498  // Copy the value to a (aligned) stack slot using (unaligned) integer
3499  // loads and stores, then do a (aligned) load from the stack slot.
3500  MVT RegVT = getRegisterType(*DAG.getContext(), intVT);
3501  unsigned LoadedBytes = LoadedVT.getSizeInBits() / 8;
3502  unsigned RegBytes = RegVT.getSizeInBits() / 8;
3503  unsigned NumRegs = (LoadedBytes + RegBytes - 1) / RegBytes;
3504 
3505  // Make sure the stack slot is also aligned for the register type.
3506  SDValue StackBase = DAG.CreateStackTemporary(LoadedVT, RegVT);
3507 
3508  SmallVector<SDValue, 8> Stores;
3509  SDValue StackPtr = StackBase;
3510  unsigned Offset = 0;
3511 
3512  EVT PtrVT = Ptr.getValueType();
3513  EVT StackPtrVT = StackPtr.getValueType();
3514 
3515  SDValue PtrIncrement = DAG.getConstant(RegBytes, dl, PtrVT);
3516  SDValue StackPtrIncrement = DAG.getConstant(RegBytes, dl, StackPtrVT);
3517 
3518  // Do all but one copies using the full register width.
3519  for (unsigned i = 1; i < NumRegs; i++) {
3520  // Load one integer register's worth from the original location.
3521  SDValue Load = DAG.getLoad(
3522  RegVT, dl, Chain, Ptr, LD->getPointerInfo().getWithOffset(Offset),
3524  LD->getAAInfo());
3525  // Follow the load with a store to the stack slot. Remember the store.
3526  Stores.push_back(DAG.getStore(Load.getValue(1), dl, Load, StackPtr,
3527  MachinePointerInfo()));
3528  // Increment the pointers.
3529  Offset += RegBytes;
3530  Ptr = DAG.getNode(ISD::ADD, dl, PtrVT, Ptr, PtrIncrement);
3531  StackPtr = DAG.getNode(ISD::ADD, dl, StackPtrVT, StackPtr,
3532  StackPtrIncrement);
3533  }
3534 
3535  // The last copy may be partial. Do an extending load.
3536  EVT MemVT = EVT::getIntegerVT(*DAG.getContext(),
3537  8 * (LoadedBytes - Offset));
3538  SDValue Load =
3539  DAG.getExtLoad(ISD::EXTLOAD, dl, RegVT, Chain, Ptr,
3540  LD->getPointerInfo().getWithOffset(Offset), MemVT,
3541  MinAlign(LD->getAlignment(), Offset),
3542  LD->getMemOperand()->getFlags(), LD->getAAInfo());
3543  // Follow the load with a store to the stack slot. Remember the store.
3544  // On big-endian machines this requires a truncating store to ensure
3545  // that the bits end up in the right place.
3546  Stores.push_back(DAG.getTruncStore(Load.getValue(1), dl, Load, StackPtr,
3547  MachinePointerInfo(), MemVT));
3548 
3549  // The order of the stores doesn't matter - say it with a TokenFactor.
3550  SDValue TF = DAG.getNode(ISD::TokenFactor, dl, MVT::Other, Stores);
3551 
3552  // Finally, perform the original load only redirected to the stack slot.
3553  Load = DAG.getExtLoad(LD->getExtensionType(), dl, VT, TF, StackBase,
3554  MachinePointerInfo(), LoadedVT);
3555 
3556  // Callers expect a MERGE_VALUES node.
3557  return std::make_pair(Load, TF);
3558  }
3559 
3560  assert(LoadedVT.isInteger() && !LoadedVT.isVector() &&
3561  "Unaligned load of unsupported type.");
3562 
3563  // Compute the new VT that is half the size of the old one. This is an
3564  // integer MVT.
3565  unsigned NumBits = LoadedVT.getSizeInBits();
3566  EVT NewLoadedVT;
3567  NewLoadedVT = EVT::getIntegerVT(*DAG.getContext(), NumBits/2);
3568  NumBits >>= 1;
3569 
3570  unsigned Alignment = LD->getAlignment();
3571  unsigned IncrementSize = NumBits / 8;
3572  ISD::LoadExtType HiExtType = LD->getExtensionType();
3573 
3574  // If the original load is NON_EXTLOAD, the hi part load must be ZEXTLOAD.
3575  if (HiExtType == ISD::NON_EXTLOAD)
3576  HiExtType = ISD::ZEXTLOAD;
3577 
3578  // Load the value in two parts
3579  SDValue Lo, Hi;
3580  if (DAG.getDataLayout().isLittleEndian()) {
3581  Lo = DAG.getExtLoad(ISD::ZEXTLOAD, dl, VT, Chain, Ptr, LD->getPointerInfo(),
3582  NewLoadedVT, Alignment, LD->getMemOperand()->getFlags(),
3583  LD->getAAInfo());
3584  Ptr = DAG.getNode(ISD::ADD, dl, Ptr.getValueType(), Ptr,
3585  DAG.getConstant(IncrementSize, dl, Ptr.getValueType()));
3586  Hi = DAG.getExtLoad(HiExtType, dl, VT, Chain, Ptr,
3587  LD->getPointerInfo().getWithOffset(IncrementSize),
3588  NewLoadedVT, MinAlign(Alignment, IncrementSize),
3589  LD->getMemOperand()->getFlags(), LD->getAAInfo());
3590  } else {
3591  Hi = DAG.getExtLoad(HiExtType, dl, VT, Chain, Ptr, LD->getPointerInfo(),
3592  NewLoadedVT, Alignment, LD->getMemOperand()->getFlags(),
3593  LD->getAAInfo());
3594  Ptr = DAG.getNode(ISD::ADD, dl, Ptr.getValueType(), Ptr,
3595  DAG.getConstant(IncrementSize, dl, Ptr.getValueType()));
3596  Lo = DAG.getExtLoad(ISD::ZEXTLOAD, dl, VT, Chain, Ptr,
3597  LD->getPointerInfo().getWithOffset(IncrementSize),
3598  NewLoadedVT, MinAlign(Alignment, IncrementSize),
3599  LD->getMemOperand()->getFlags(), LD->getAAInfo());
3600  }
3601 
3602  // aggregate the two parts
3603  SDValue ShiftAmount =
3604  DAG.getConstant(NumBits, dl, getShiftAmountTy(Hi.getValueType(),
3605  DAG.getDataLayout()));
3606  SDValue Result = DAG.getNode(ISD::SHL, dl, VT, Hi, ShiftAmount);
3607  Result = DAG.getNode(ISD::OR, dl, VT, Result, Lo);
3608 
3609  SDValue TF = DAG.getNode(ISD::TokenFactor, dl, MVT::Other, Lo.getValue(1),
3610  Hi.getValue(1));
3611 
3612  return std::make_pair(Result, TF);
3613 }
3614 
3616  SelectionDAG &DAG) const {
3618  "unaligned indexed stores not implemented!");
3619  SDValue Chain = ST->getChain();
3620  SDValue Ptr = ST->getBasePtr();
3621  SDValue Val = ST->getValue();
3622  EVT VT = Val.getValueType();
3623  int Alignment = ST->getAlignment();
3624 
3625  SDLoc dl(ST);
3626  if (ST->getMemoryVT().isFloatingPoint() ||
3627  ST->getMemoryVT().isVector()) {
3628  EVT intVT = EVT::getIntegerVT(*DAG.getContext(), VT.getSizeInBits());
3629  if (isTypeLegal(intVT)) {
3630  if (!isOperationLegalOrCustom(ISD::STORE, intVT)) {
3631  // Scalarize the store and let the individual components be handled.
3632  SDValue Result = scalarizeVectorStore(ST, DAG);
3633 
3634  return Result;
3635  }
3636  // Expand to a bitconvert of the value to the integer type of the
3637  // same size, then a (misaligned) int store.
3638  // FIXME: Does not handle truncating floating point stores!
3639  SDValue Result = DAG.getNode(ISD::BITCAST, dl, intVT, Val);
3640  Result = DAG.getStore(Chain, dl, Result, Ptr, ST->getPointerInfo(),
3641  Alignment, ST->getMemOperand()->getFlags());
3642  return Result;
3643  }
3644  // Do a (aligned) store to a stack slot, then copy from the stack slot
3645  // to the final destination using (unaligned) integer loads and stores.
3646  EVT StoredVT = ST->getMemoryVT();
3647  MVT RegVT =
3648  getRegisterType(*DAG.getContext(),
3650  StoredVT.getSizeInBits()));
3651  EVT PtrVT = Ptr.getValueType();
3652  unsigned StoredBytes = StoredVT.getSizeInBits() / 8;
3653  unsigned RegBytes = RegVT.getSizeInBits() / 8;
3654  unsigned NumRegs = (StoredBytes + RegBytes - 1) / RegBytes;
3655 
3656  // Make sure the stack slot is also aligned for the register type.
3657  SDValue StackPtr = DAG.CreateStackTemporary(StoredVT, RegVT);
3658 
3659  // Perform the original store, only redirected to the stack slot.
3660  SDValue Store = DAG.getTruncStore(Chain, dl, Val, StackPtr,
3661  MachinePointerInfo(), StoredVT);
3662 
3663  EVT StackPtrVT = StackPtr.getValueType();
3664 
3665  SDValue PtrIncrement = DAG.getConstant(RegBytes, dl, PtrVT);
3666  SDValue StackPtrIncrement = DAG.getConstant(RegBytes, dl, StackPtrVT);
3667  SmallVector<SDValue, 8> Stores;
3668  unsigned Offset = 0;
3669 
3670  // Do all but one copies using the full register width.
3671  for (unsigned i = 1; i < NumRegs; i++) {
3672  // Load one integer register's worth from the stack slot.
3673  SDValue Load =
3674  DAG.getLoad(RegVT, dl, Store, StackPtr, MachinePointerInfo());
3675  // Store it to the final location. Remember the store.
3676  Stores.push_back(DAG.getStore(Load.getValue(1), dl, Load, Ptr,
3677  ST->getPointerInfo().getWithOffset(Offset),
3678  MinAlign(ST->getAlignment(), Offset),
3679  ST->getMemOperand()->getFlags()));
3680  // Increment the pointers.
3681  Offset += RegBytes;
3682  StackPtr = DAG.getNode(ISD::ADD, dl, StackPtrVT,
3683  StackPtr, StackPtrIncrement);
3684  Ptr = DAG.getNode(ISD::ADD, dl, PtrVT, Ptr, PtrIncrement);
3685  }
3686 
3687  // The last store may be partial. Do a truncating store. On big-endian
3688  // machines this requires an extending load from the stack slot to ensure
3689  // that the bits are in the right place.
3690  EVT MemVT = EVT::getIntegerVT(*DAG.getContext(),
3691  8 * (StoredBytes - Offset));
3692 
3693  // Load from the stack slot.
3694  SDValue Load = DAG.getExtLoad(ISD::EXTLOAD, dl, RegVT, Store, StackPtr,
3695  MachinePointerInfo(), MemVT);
3696 
3697  Stores.push_back(
3698  DAG.getTruncStore(Load.getValue(1), dl, Load, Ptr,
3699  ST->getPointerInfo().getWithOffset(Offset), MemVT,
3700  MinAlign(ST->getAlignment(), Offset),
3701  ST->getMemOperand()->getFlags(), ST->getAAInfo()));
3702  // The order of the stores doesn't matter - say it with a TokenFactor.
3703  SDValue Result = DAG.getNode(ISD::TokenFactor, dl, MVT::Other, Stores);
3704  return Result;
3705  }
3706 
3707  assert(ST->getMemoryVT().isInteger() &&
3708  !ST->getMemoryVT().isVector() &&
3709  "Unaligned store of unknown type.");
3710  // Get the half-size VT
3711  EVT NewStoredVT = ST->getMemoryVT().getHalfSizedIntegerVT(*DAG.getContext());
3712  int NumBits = NewStoredVT.getSizeInBits();
3713  int IncrementSize = NumBits / 8;
3714 
3715  // Divide the stored value in two parts.
3716  SDValue ShiftAmount =
3717  DAG.getConstant(NumBits, dl, getShiftAmountTy(Val.getValueType(),
3718  DAG.getDataLayout()));
3719  SDValue Lo = Val;
3720  SDValue Hi = DAG.getNode(ISD::SRL, dl, VT, Val, ShiftAmount);
3721 
3722  // Store the two parts
3723  SDValue Store1, Store2;
3724  Store1 = DAG.getTruncStore(Chain, dl,
3725  DAG.getDataLayout().isLittleEndian() ? Lo : Hi,
3726  Ptr, ST->getPointerInfo(), NewStoredVT, Alignment,
3727  ST->getMemOperand()->getFlags());
3728 
3729  EVT PtrVT = Ptr.getValueType();
3730  Ptr = DAG.getNode(ISD::ADD, dl, PtrVT, Ptr,
3731  DAG.getConstant(IncrementSize, dl, PtrVT));
3732  Alignment = MinAlign(Alignment, IncrementSize);
3733  Store2 = DAG.getTruncStore(
3734  Chain, dl, DAG.getDataLayout().isLittleEndian() ? Hi : Lo, Ptr,
3735  ST->getPointerInfo().getWithOffset(IncrementSize), NewStoredVT, Alignment,
3736  ST->getMemOperand()->getFlags(), ST->getAAInfo());
3737 
3738  SDValue Result =
3739  DAG.getNode(ISD::TokenFactor, dl, MVT::Other, Store1, Store2);
3740  return Result;
3741 }
3742 
3743 SDValue
3745  const SDLoc &DL, EVT DataVT,
3746  SelectionDAG &DAG,
3747  bool IsCompressedMemory) const {
3748  SDValue Increment;
3749  EVT AddrVT = Addr.getValueType();
3750  EVT MaskVT = Mask.getValueType();
3751  assert(DataVT.getVectorNumElements() == MaskVT.getVectorNumElements() &&
3752  "Incompatible types of Data and Mask");
3753  if (IsCompressedMemory) {
3754  // Incrementing the pointer according to number of '1's in the mask.
3755  EVT MaskIntVT = EVT::getIntegerVT(*DAG.getContext(), MaskVT.getSizeInBits());
3756  SDValue MaskInIntReg = DAG.getBitcast(MaskIntVT, Mask);
3757  if (MaskIntVT.getSizeInBits() < 32) {
3758  MaskInIntReg = DAG.getNode(ISD::ZERO_EXTEND, DL, MVT::i32, MaskInIntReg);
3759  MaskIntVT = MVT::i32;
3760  }
3761 
3762  // Count '1's with POPCNT.
3763  Increment = DAG.getNode(ISD::CTPOP, DL, MaskIntVT, MaskInIntReg);
3764  Increment = DAG.getZExtOrTrunc(Increment, DL, AddrVT);
3765  // Scale is an element size in bytes.
3766  SDValue Scale = DAG.getConstant(DataVT.getScalarSizeInBits() / 8, DL,
3767  AddrVT);
3768  Increment = DAG.getNode(ISD::MUL, DL, AddrVT, Increment, Scale);
3769  } else
3770  Increment = DAG.getConstant(DataVT.getSizeInBits() / 8, DL, AddrVT);
3771 
3772  return DAG.getNode(ISD::ADD, DL, AddrVT, Addr, Increment);
3773 }
3774 
3776  SDValue Idx,
3777  EVT VecVT,
3778  const SDLoc &dl) {
3779  if (isa<ConstantSDNode>(Idx))
3780  return Idx;
3781 
3782  EVT IdxVT = Idx.getValueType();
3783  unsigned NElts = VecVT.getVectorNumElements();
3784  if (isPowerOf2_32(NElts)) {
3786  Log2_32(NElts));
3787  return DAG.getNode(ISD::AND, dl, IdxVT, Idx,
3788  DAG.getConstant(Imm, dl, IdxVT));
3789  }
3790 
3791  return DAG.getNode(ISD::UMIN, dl, IdxVT, Idx,
3792  DAG.getConstant(NElts - 1, dl, IdxVT));
3793 }
3794 
3796  SDValue VecPtr, EVT VecVT,
3797  SDValue Index) const {
3798  SDLoc dl(Index);
3799  // Make sure the index type is big enough to compute in.
3800  Index = DAG.getZExtOrTrunc(Index, dl, getPointerTy(DAG.getDataLayout()));
3801 
3802  EVT EltVT = VecVT.getVectorElementType();
3803 
3804  // Calculate the element offset and add it to the pointer.
3805  unsigned EltSize = EltVT.getSizeInBits() / 8; // FIXME: should be ABI size.
3806  assert(EltSize * 8 == EltVT.getSizeInBits() &&
3807  "Converting bits to bytes lost precision");
3808 
3809  Index = clampDynamicVectorIndex(DAG, Index, VecVT, dl);
3810 
3811  EVT IdxVT = Index.getValueType();
3812 
3813  Index = DAG.getNode(ISD::MUL, dl, IdxVT, Index,
3814  DAG.getConstant(EltSize, dl, IdxVT));
3815  return DAG.getNode(ISD::ADD, dl, IdxVT, Index, VecPtr);
3816 }
3817 
3818 //===----------------------------------------------------------------------===//
3819 // Implementation of Emulated TLS Model
3820 //===----------------------------------------------------------------------===//
3821 
3823  SelectionDAG &DAG) const {
3824  // Access to address of TLS varialbe xyz is lowered to a function call:
3825  // __emutls_get_address( address of global variable named "__emutls_v.xyz" )
3826  EVT PtrVT = getPointerTy(DAG.getDataLayout());
3827  PointerType *VoidPtrType = Type::getInt8PtrTy(*DAG.getContext());
3828  SDLoc dl(GA);
3829 
3830  ArgListTy Args;
3831  ArgListEntry Entry;
3832  std::string NameString = ("__emutls_v." + GA->getGlobal()->getName()).str();
3833  Module *VariableModule = const_cast<Module*>(GA->getGlobal()->getParent());
3834  StringRef EmuTlsVarName(NameString);
3835  GlobalVariable *EmuTlsVar = VariableModule->getNamedGlobal(EmuTlsVarName);
3836  assert(EmuTlsVar && "Cannot find EmuTlsVar ");
3837  Entry.Node = DAG.getGlobalAddress(EmuTlsVar, dl, PtrVT);
3838  Entry.Ty = VoidPtrType;
3839  Args.push_back(Entry);
3840 
3841  SDValue EmuTlsGetAddr = DAG.getExternalSymbol("__emutls_get_address", PtrVT);
3842 
3844  CLI.setDebugLoc(dl).setChain(DAG.getEntryNode());
3845  CLI.setLibCallee(CallingConv::C, VoidPtrType, EmuTlsGetAddr, std::move(Args));
3846  std::pair<SDValue, SDValue> CallResult = LowerCallTo(CLI);
3847 
3848  // TLSADDR will be codegen'ed as call. Inform MFI that function has calls.
3849  // At last for X86 targets, maybe good for other targets too?
3851  MFI.setAdjustsStack(true); // Is this only for X86 target?
3852  MFI.setHasCalls(true);
3853 
3854  assert((GA->getOffset() == 0) &&
3855  "Emulated TLS must have zero offset in GlobalAddressSDNode");
3856  return CallResult.first;
3857 }
3858 
3860  SelectionDAG &DAG) const {
3861  assert((Op->getOpcode() == ISD::SETCC) && "Input has to be a SETCC node.");
3862  if (!isCtlzFast())
3863  return SDValue();
3864  ISD::CondCode CC = cast<CondCodeSDNode>(Op.getOperand(2))->get();
3865  SDLoc dl(Op);
3866  if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
3867  if (C->isNullValue() && CC == ISD::SETEQ) {
3868  EVT VT = Op.getOperand(0).getValueType();
3869  SDValue Zext = Op.getOperand(0);
3870  if (VT.bitsLT(MVT::i32)) {
3871  VT = MVT::i32;
3872  Zext = DAG.getNode(ISD::ZERO_EXTEND, dl, VT, Op.getOperand(0));
3873  }
3874  unsigned Log2b = Log2_32(VT.getSizeInBits());
3875  SDValue Clz = DAG.getNode(ISD::CTLZ, dl, VT, Zext);
3876  SDValue Scc = DAG.getNode(ISD::SRL, dl, VT, Clz,
3877  DAG.getConstant(Log2b, dl, MVT::i32));
3878  return DAG.getNode(ISD::TRUNCATE, dl, MVT::i32, Scc);
3879  }
3880  }
3881  return SDValue();
3882 }
SDValue getStore(SDValue Chain, const SDLoc &dl, SDValue Val, SDValue Ptr, MachinePointerInfo PtrInfo, unsigned Alignment=0, MachineMemOperand::Flags MMOFlags=MachineMemOperand::MONone, const AAMDNodes &AAInfo=AAMDNodes())
Helper function to build ISD::STORE nodes.
uint64_t CallInst * C
BITCAST - This operator converts between integer, vector and FP values, as if the value was stored to...
Definition: ISDOpcodes.h:544
SDValue getGlobalAddress(const GlobalValue *GV, const SDLoc &DL, EVT VT, int64_t offset=0, bool isTargetGA=false, unsigned char TargetFlags=0)
static MVT getIntegerVT(unsigned BitWidth)
unsigned Log2_32_Ceil(uint32_t Value)
Return the ceil log base 2 of the specified value, 32 if the value is zero.
Definition: MathExtras.h:544
BUILTIN_OP_END - This must be the last enum value in this list.
Definition: ISDOpcodes.h:827
A parsed version of the target data layout string in and methods for querying it. ...
Definition: DataLayout.h:109
virtual MVT getVectorIdxTy(const DataLayout &DL) const
Returns the type to be used for the index operand of: ISD::INSERT_VECTOR_ELT, ISD::EXTRACT_VECTOR_ELT...
EVT getValueType() const
Return the ValueType of the referenced return value.
bool isInteger() const
Return true if this is an integer or a vector integer type.
void setSignBit()
Set the sign bit to 1.
Definition: APInt.h:1392
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
bool isUndef() const
SDValue getBoolExtOrTrunc(SDValue Op, const SDLoc &SL, EVT VT, EVT OpVT)
Convert Op, which must be of integer type, to the integer type VT, by using an extension appropriate ...
const GlobalValue * getGlobal() const
static APInt getAllOnesValue(unsigned numBits)
Get the all-ones value.
Definition: APInt.h:555
unsigned getOpcode() const
Return the SelectionDAG opcode value for this node.
SDValue getSetCC(const SDLoc &DL, EVT VT, SDValue LHS, SDValue RHS, ISD::CondCode Cond)
Helper function to make it easier to build SetCC&#39;s if you just have an ISD::CondCode instead of an SD...
Definition: SelectionDAG.h:884
SDValue getConstTrueVal(SelectionDAG &DAG, EVT VT, const SDLoc &DL) const
Return a constant of type VT that contains a true value that respects getBooleanContents() ...
static const MCSymbolRefExpr * create(const MCSymbol *Symbol, MCContext &Ctx)
Definition: MCExpr.h:305
LLVM_ATTRIBUTE_NORETURN void report_fatal_error(Error Err, bool gen_crash_diag=true)
Report a serious error, calling any installed error handler.
Definition: Error.cpp:103
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
unsigned getParamAlignment(unsigned ArgNo) const
Extract the alignment for a call or parameter (0=unknown).
Definition: CallSite.h:403
Various leaf nodes.
Definition: ISDOpcodes.h:60
EVT getScalarType() const
If this is a vector type, return the element type, otherwise return this.
Definition: ValueTypes.h:260
virtual MVT::SimpleValueType getCmpLibcallReturnType() const
Return the ValueType for comparison libcalls.
A Module instance is used to store all the information related to an LLVM module. ...
Definition: Module.h:63
bool isSized(SmallPtrSetImpl< Type *> *Visited=nullptr) const
Return true if it makes sense to take the size of this type.
Definition: Type.h:262
LLVM_ATTRIBUTE_ALWAYS_INLINE size_type size() const
Definition: SmallVector.h:136
SDValue scalarizeVectorStore(StoreSDNode *ST, SelectionDAG &DAG) const
const SDValue & getBasePtr() const
Carry-setting nodes for multiple precision addition and subtraction.
Definition: ISDOpcodes.h:222
virtual unsigned getJumpTableEncoding() const
Return the entry encoding for a jump table in the current function.
EVT getValueType(unsigned ResNo) const
Return the type of a specified result.
virtual void LowerAsmOperandForConstraint(SDValue Op, std::string &Constraint, std::vector< SDValue > &Ops, SelectionDAG &DAG) const
Lower the specified operand into the Ops vector.
unsigned s
shift amount
Definition: APInt.h:1936
LLVM_NODISCARD LLVM_ATTRIBUTE_ALWAYS_INLINE size_t size() const
size - Get the string size.
Definition: StringRef.h:138
APInt zext(unsigned width) const
Zero extend to a new width.
Definition: APInt.cpp:865
const SDValue & getValue() const
static APInt getLowBitsSet(unsigned numBits, unsigned loBitsSet)
Get a value with low bits set.
Definition: APInt.h:641
MVT getSimpleVT() const
Return the SimpleValueType held in the specified simple EVT.
Definition: ValueTypes.h:253
Libcall
RTLIB::Libcall enum - This enum defines all of the runtime library calls the backend can emit...
virtual SDValue PerformDAGCombine(SDNode *N, DAGCombinerInfo &DCI) const
This method will be invoked for all target nodes and for any target-independent nodes that the target...
AAMDNodes getAAInfo() const
Returns the AA info that describes the dereference.
bool isSubsetOf(const APInt &RHS) const
This operation checks that all bits set in this APInt are also set in RHS.
Definition: APInt.h:1308
const GlobalVariable * getNamedGlobal(StringRef Name) const
Return the global variable in the module with the specified name, of arbitrary type.
Definition: Module.h:383
const SDValue & getChain() const
ISD::MemIndexedMode getAddressingMode() const
Return the addressing mode for this load or store: unindexed, pre-inc, pre-dec, post-inc, or post-dec.
virtual bool isCommutativeBinOp(unsigned Opcode) const
Returns true if the opcode is a commutative binary operation.
unsigned getAlignment() const
bool isBitwiseNot(SDValue V)
Returns true if V is a bitwise not operation.
virtual std::pair< unsigned, const TargetRegisterClass * > getRegForInlineAsmConstraint(const TargetRegisterInfo *TRI, StringRef Constraint, MVT VT) const
Given a physical register constraint (e.g.
APInt trunc(unsigned width) const
Truncate to new width.
Definition: APInt.cpp:818
virtual const char * getTargetNodeName(unsigned Opcode) const
This method returns the name of a target specific DAG node.
void setAllBits()
Set every bit to 1.
Definition: APInt.h:1369
unsigned getPointerSizeInBits(unsigned AS=0) const
Layout pointer size, in bits FIXME: The defaults need to be removed once all of the backends/clients ...
Definition: DataLayout.h:346
The two locations do not alias at all.
Definition: AliasAnalysis.h:79
virtual AsmOperandInfoVector ParseConstraints(const DataLayout &DL, const TargetRegisterInfo *TRI, ImmutableCallSite CS) const
Split up the constraint string from the inline assembly value into the specific constraints and their...
bool isInteger() const
Return true if this is an integer or a vector integer type.
Definition: ValueTypes.h:141
CallLoweringInfo & setDebugLoc(const SDLoc &dl)
void softenSetCCOperands(SelectionDAG &DAG, EVT VT, SDValue &NewLHS, SDValue &NewRHS, ISD::CondCode &CCCode, const SDLoc &DL) const
Soften the operands of a comparison.
SDValue getTruncStore(SDValue Chain, const SDLoc &dl, SDValue Val, SDValue Ptr, MachinePointerInfo PtrInfo, EVT TVT, unsigned Alignment=0, MachineMemOperand::Flags MMOFlags=MachineMemOperand::MONone, const AAMDNodes &AAInfo=AAMDNodes())
virtual bool isTypeDesirableForOp(unsigned, EVT VT) const
Return true if the target has native support for the specified value type and it is &#39;desirable&#39; to us...
const SDNodeFlags getFlags() const
BooleanContent getBooleanContents(bool isVec, bool isFloat) const
For targets without i1 registers, this gives the nature of the high-bits of boolean values held in ty...
SDNode * getNode() const
get the SDNode which holds the desired result
SDValue getNode(unsigned Opcode, const SDLoc &DL, EVT VT, ArrayRef< SDUse > Ops)
Gets or creates the specified node.
virtual bool isZExtFree(Type *FromTy, Type *ToTy) const
Return true if any actual instruction that defines a value of type FromTy implicitly zero-extends the...
Value * CallOperandVal
If this is the result output operand or a clobber, this is null, otherwise it is the incoming operand...
bool isOperationLegalOrCustom(unsigned Op, EVT VT) const
Return true if the specified operation is legal on this target or can be made legal with custom lower...
bool isByteSized() const
Return true if the bit size is a multiple of 8.
Definition: ValueTypes.h:212
MachineMemOperand * getMemOperand() const
Return a MachineMemOperand object describing the memory reference performed by operation.
bool isTrueWhenEqual(CondCode Cond)
Return true if the specified condition returns true if the two operands to the condition are equal...
Definition: ISDOpcodes.h:955
bool isConstTrueVal(const SDNode *N) const
Return if the N is a constant or constant vector equal to the true value from getBooleanContents().
CallLoweringInfo & setDiscardResult(bool Value=true)
unsigned getBitWidth() const
Get the bit width of this value.
Definition: KnownBits.h:40
virtual SDValue LowerToTLSEmulatedModel(const GlobalAddressSDNode *GA, SelectionDAG &DAG) const
Lower TLS global address SDNode for target independent emulated TLS model.
unsigned getValueSizeInBits() const
Returns the size of the value in bits.
Magic data for optimising unsigned division by a constant.
Definition: APInt.h:1940
Select with condition operator - This selects between a true value and a false value (ops #2 and #3) ...
Definition: ISDOpcodes.h:403
LLVM_NODISCARD LLVM_ATTRIBUTE_ALWAYS_INLINE const char * data() const
data - Get a pointer to the start of the string (which may not be null terminated).
Definition: StringRef.h:128
bool hasOneUse() const
Return true if there is exactly one node using value ResNo of Node.
static APInt getSignedMaxValue(unsigned numBits)
Gets maximum signed value of APInt for a specific bit width.
Definition: APInt.h:528
bool hasAttribute(unsigned Index, Attribute::AttrKind Kind) const
Return true if the attribute exists at the given index.
INT = FGETSIGN(FP) - Return the sign bit of the specified floating point value as an integer 0/1 valu...
Definition: ISDOpcodes.h:290
unsigned getBitWidth() const
Return the number of bits in the APInt.
Definition: APInt.h:1488
SDValue getExternalSymbol(const char *Sym, EVT VT)
bool hasMatchingInput() const
hasMatchingInput - Return true if this is an output constraint that has a matching input constraint...
Definition: InlineAsm.h:135
bool isCondCodeLegal(ISD::CondCode CC, MVT VT) const
Return true if the specified condition code is legal on this target.
ConstraintCodeVector Codes
Code - The constraint code, either the register name (in braces) or the constraint letter/number...
Definition: InlineAsm.h:149
LLVMContext & getContext() const
Return the LLVMContext in which this type was uniqued.
Definition: Type.h:130
RESULT,OUTCHAIN = INTRINSIC_W_CHAIN(INCHAIN, INTRINSICID, arg1, ...) This node represents a target in...
Definition: ISDOpcodes.h:159
virtual bool isCtlzFast() const
Return true if ctlz instruction is fast.
A convenience struct that encapsulates a DAG, and two SDValues for returning information from TargetL...
MVT getRegisterType(MVT VT) const
Return the type of registers that this ValueType will eventually require.
bool isFloatingPoint() const
Return true if this is a FP or a vector FP type.
Definition: ValueTypes.h:136
unsigned countTrailingZeros() const
Count the number of trailing zero bits.
Definition: APInt.h:1611
static GCMetadataPrinterRegistry::Add< OcamlGCMetadataPrinter > Y("ocaml", "ocaml 3.10-compatible collector")
virtual unsigned ComputeNumSignBitsForTargetNode(SDValue Op, const APInt &DemandedElts, const SelectionDAG &DAG, unsigned Depth=0) const
This method can be implemented by targets that want to expose additional information about sign bits ...
void setNoSignedWrap(bool b)
ms magic() const
Calculate the magic numbers required to implement a signed integer division by a constant as a sequen...
Definition: APInt.cpp:1152
std::vector< std::string > ConstraintCodeVector
Definition: InlineAsm.h:97
bool hasOneUse() const
Return true if there is exactly one use of this node.
APInt getLoBits(unsigned numBits) const
Compute an APInt containing numBits lowbits from this APInt.
Definition: APInt.cpp:515
virtual bool isGAPlusOffset(SDNode *N, const GlobalValue *&GA, int64_t &Offset) const
Returns true (and the GlobalValue and the offset) if the node is a GlobalAddress + offset...
static SDValue clampDynamicVectorIndex(SelectionDAG &DAG, SDValue Idx, EVT VecVT, const SDLoc &dl)
SDValue SimplifySetCC(EVT VT, SDValue N0, SDValue N1, ISD::CondCode Cond, bool foldBooleans, DAGCombinerInfo &DCI, const SDLoc &dl) const
Try to simplify a setcc built with the specified operands and cc.
APInt shl(unsigned shiftAmt) const
Left-shift function.
Definition: APInt.h:981
Shift and rotation operations.
Definition: ISDOpcodes.h:378
static F t[256]
Type * getTypeForEVT(LLVMContext &Context) const
This method returns an LLVM type corresponding to the specified EVT.
Definition: ValueTypes.cpp:205
Class to represent struct types.
Definition: DerivedTypes.h:201
bool isBuildVectorAllZeros(const SDNode *N)
Return true if the specified node is a BUILD_VECTOR where all of the elements are 0 or undef...
TargetLowering::ConstraintType ConstraintType
Information about the constraint code, e.g.
CallLoweringInfo & setChain(SDValue InChain)
BUILD_PAIR - This is the opposite of EXTRACT_ELEMENT in some ways.
Definition: ISDOpcodes.h:190
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:42
Base class for the full range of assembler expressions which are needed for parsing.
Definition: MCExpr.h:36
static SDValue BuildExactSDIV(const TargetLowering &TLI, SDValue Op1, APInt d, const SDLoc &dl, SelectionDAG &DAG, std::vector< SDNode *> &Created)
Given an exact SDIV by a constant, create a multiplication with the multiplicative inverse of the con...
bool isIntegerTy() const
True if this is an instance of IntegerType.
Definition: Type.h:197
unsigned getScalarValueSizeInBits() const
ISD::LoadExtType getExtensionType() const
Return whether this is a plain node, or one of the varieties of value-extending loads.
Reg
All possible values of the reg field in the ModR/M byte.
iterator_range< regclass_iterator > regclasses() const
The MachineFrameInfo class represents an abstract stack frame until prolog/epilog code is inserted...
SDValue getEntryNode() const
Return the token chain corresponding to the entry of the function.
Definition: SelectionDAG.h:434
const DataLayout & getDataLayout() const
Definition: SelectionDAG.h:376
SDVTList getVTList(EVT VT)
Return an SDVTList that represents the list of values specified.
APInt getHiBits(unsigned numBits) const
Compute an APInt containing numBits highbits from this APInt.
Definition: APInt.cpp:510
bool expandMUL(SDNode *N, SDValue &Lo, SDValue &Hi, EVT HiLoVT, SelectionDAG &DAG, MulExpansionKind Kind, SDValue LL=SDValue(), SDValue LH=SDValue(), SDValue RL=SDValue(), SDValue RH=SDValue()) const
Expand a MUL into two nodes.
void lshrInPlace(unsigned ShiftAmt)
Logical right-shift this APInt by ShiftAmt in place.
Definition: APInt.h:966
SDValue FoldSetCC(EVT VT, SDValue N1, SDValue N2, ISD::CondCode Cond, const SDLoc &dl)
Constant fold a setcc to true or false.
This class defines information used to lower LLVM code to legal SelectionDAG operators that the targe...
zlib-gnu style compression
bool ShrinkDemandedOp(SDValue Op, unsigned BitWidth, const APInt &Demanded, TargetLoweringOpt &TLO) const
Convert x+y to (VT)((SmallVT)x+(SmallVT)y) if the casts are free.
This represents a list of ValueType&#39;s that has been intern&#39;d by a SelectionDAG.
SDValue getExtLoad(ISD::LoadExtType ExtType, const SDLoc &dl, EVT VT, SDValue Chain, SDValue Ptr, MachinePointerInfo PtrInfo, EVT MemVT, unsigned Alignment=0, MachineMemOperand::Flags MMOFlags=MachineMemOperand::MONone, const AAMDNodes &AAInfo=AAMDNodes())
unsigned getLiveInPhysReg(unsigned VReg) const
getLiveInPhysReg - If VReg is a live-in virtual register, return the corresponding live-in physical r...
virtual bool isTruncateFree(Type *FromTy, Type *ToTy) const
Return true if it&#39;s free to truncate a value of type FromTy to type ToTy.
SDValue getMergeValues(ArrayRef< SDValue > Ops, const SDLoc &dl)
Create a MERGE_VALUES node from the given operands.
unsigned getSizeInBits() const
Context object for machine code objects.
Definition: MCContext.h:59
void emitError(unsigned LocCookie, const Twine &ErrorStr)
emitError - Emit an error message to the currently installed error handler with optional location inf...
ValTy * getCalledValue() const
Return the pointer to function that is being called.
Definition: CallSite.h:97
unsigned getActiveBits() const
Compute the number of active bits in the value.
Definition: APInt.h:1512
int64_t getSExtValue() const
SDValue getSExtOrTrunc(SDValue Op, const SDLoc &DL, EVT VT)
Convert Op, which must be of integer type, to the integer type VT, by either sign-extending or trunca...
void ashrInPlace(unsigned ShiftAmt)
Arithmetic right-shift this APInt by ShiftAmt in place.
Definition: APInt.h:942
unsigned getScalarSizeInBits() const
Definition: ValueTypes.h:298
unsigned getSizeInBits() const
Return the size of the specified value type in bits.
Definition: ValueTypes.h:292
int64_t getSExtValue() const
Get sign extended value.
Definition: APInt.h:1554
#define F(x, y, z)
Definition: MD5.cpp:55
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:245
MachineFunction & getMachineFunction() const
Definition: SelectionDAG.h:375
static SDNodeIterator begin(const SDNode *N)
EK_LabelDifference32 - Each entry is the address of the block minus the address of the jump table...
CallingConv::ID getLibcallCallingConv(RTLIB::Libcall Call) const
Get the CallingConv that should be used for the specified libcall.
This contains information for each constraint that we are lowering.
Simple integer binary arithmetic operators.
Definition: ISDOpcodes.h:200
LLVM_NODISCARD LLVM_ATTRIBUTE_ALWAYS_INLINE bool empty() const
empty - Check if the string is empty.
Definition: StringRef.h:133
bool isExtendedTrueVal(const ConstantSDNode *N, EVT VT, bool Signed) const
Return if N is a True value when extended to VT.
bool paramHasAttr(unsigned ArgNo, Attribute::AttrKind Kind) const
Return true if the call or the callee has the given attribute.
Definition: CallSite.h:374
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory)...
Definition: APInt.h:33
EK_BlockAddress - Each entry is a plain address of block, e.g.
bool isLittleEndian() const
Layout endianness...
Definition: DataLayout.h:216
CallLoweringInfo & setZExtResult(bool Value=true)
signed char MatchingInput
MatchingInput - If this is not -1, this is an output constraint where an input constraint is required...
Definition: InlineAsm.h:131
SDValue getUNDEF(EVT VT)
Return an UNDEF node. UNDEF does not have a useful SDLoc.
Definition: SelectionDAG.h:816
AttributeList getAttributes() const
Return the attribute list for this Function.
Definition: Function.h:197
CondCode
ISD::CondCode enum - These are ordered carefully to make the bitfields below work out...
Definition: ISDOpcodes.h:909
std::pair< SDValue, SDValue > expandUnalignedLoad(LoadSDNode *LD, SelectionDAG &DAG) const
Expands an unaligned load to 2 half-size loads for an integer, and possibly more for vectors...
LLVM_NODISCARD LLVM_ATTRIBUTE_ALWAYS_INLINE StringRef substr(size_t Start, size_t N=npos) const
Return a reference to the substring from [Start, Start + N).
Definition: StringRef.h:598
SDValue getTargetConstant(uint64_t Val, const SDLoc &DL, EVT VT, bool isOpaque=false)
Definition: SelectionDAG.h:546
ConstraintPrefix Type
Type - The basic type of the constraint: input/output/clobber.
Definition: InlineAsm.h:121
ArrayRef< SDUse > ops() const
bool parametersInCSRMatch(const MachineRegisterInfo &MRI, const uint32_t *CallerPreservedMask, const SmallVectorImpl< CCValAssign > &ArgLocs, const SmallVectorImpl< SDValue > &OutVals) const
Check whether parameters to a call that are passed in callee saved registers are the same as from the...
bool isSignedIntSetCC(CondCode Code)
Return true if this is a setcc instruction that performs a signed comparison when used with integer o...
Definition: ISDOpcodes.h:942
bool isTypeLegalForClass(const TargetRegisterClass &RC, MVT T) const
Return true if the given TargetRegisterClass has the ValueType T.
RESULT = INTRINSIC_WO_CHAIN(INTRINSICID, arg1, arg2, ...) This node represents a target intrinsic fun...
Definition: ISDOpcodes.h:151
Class to represent pointers.
Definition: DerivedTypes.h:467
virtual StringRef getRegAsmName(unsigned Reg) const
Return the assembly name for Reg.
This class is used to represent ISD::STORE nodes.
BUILD_VECTOR(ELT0, ELT1, ELT2, ELT3,...) - Return a vector with the specified, possibly variable...
Definition: ISDOpcodes.h:301
MVT getSimpleValueType() const
Return the simple ValueType of the referenced return value.
static APInt getHighBitsSet(unsigned numBits, unsigned hiBitsSet)
Get a value with high bits set.
Definition: APInt.h:629
bool bitsGT(EVT VT) const
Return true if this has more bits than VT.
Definition: ValueTypes.h:229
unsigned ComputeNumSignBits(SDValue Op, unsigned Depth=0) const
Return the number of times the sign bit of the register is replicated into the other bits...
void setAttributes(ImmutableCallSite *CS, unsigned ArgIdx)
Set CallLoweringInfo attribute flags based on a call instruction and called function attributes...
bool isVoidTy() const
Return true if this is &#39;void&#39;.
Definition: Type.h:141
constexpr uint64_t MinAlign(uint64_t A, uint64_t B)
A and B are either alignments or offsets.
Definition: MathExtras.h:602
unsigned getNumValues() const
Return the number of values defined/returned by this operator.
bool ShrinkDemandedConstant(SDValue Op, const APInt &Demanded, TargetLoweringOpt &TLO) const
Check to see if the specified operand of the specified instruction is a constant integer.
bool isNegative() const
Determine sign of this APInt.
Definition: APInt.h:357
const SDValue & getBasePtr() const
EK_GPRel64BlockAddress - Each entry is an address of block, encoded with a relocation as gp-relative...
std::vector< AsmOperandInfo > AsmOperandInfoVector
OUTCHAIN = INTRINSIC_VOID(INCHAIN, INTRINSICID, arg1, arg2, ...) This node represents a target intrin...
Definition: ISDOpcodes.h:166
MVT getSimpleValueType(const DataLayout &DL, Type *Ty, bool AllowUnknown=false) const
Return the MVT corresponding to this LLVM type. See getValueType.
bool isAllOnesValue() const
Determine if all bits are set.
Definition: APInt.h:389
virtual const char * LowerXConstraint(EVT ConstraintVT) const
Try to replace an X constraint, which matches anything, with another that has more specific requireme...
bool isStrictlyPositive() const
Determine if this APInt Value is positive.
Definition: APInt.h:384
unsigned const MachineRegisterInfo * MRI
MVT getPointerTy(const DataLayout &DL, uint32_t AS=0) const
Return the pointer type for the given address space, defaults to the pointer type from the data layou...
bool shouldAssumeDSOLocal(const Module &M, const GlobalValue *GV) const
constexpr bool isPowerOf2_32(uint32_t Value)
Return true if the argument is a power of two > 0.
Definition: MathExtras.h:421
Machine Value Type.
The instances of the Type class are immutable: once they are created, they are never changed...
Definition: Type.h:46
virtual ConstraintType getConstraintType(StringRef Constraint) const
Given a constraint, return the type of constraint it is for this target.
bool isIndirect
isIndirect - True if this operand is an indirect operand.
Definition: InlineAsm.h:145
MachineFrameInfo & getFrameInfo()
getFrameInfo - Return the frame info object for the current function.
unsigned getVectorNumElements() const
Given a vector type, return the number of elements it contains.
Definition: ValueTypes.h:273
size_t size() const
size - Get the array size.
Definition: ArrayRef.h:149
void resetAll()
Resets the known state of all bits.
Definition: KnownBits.h:66
bool isRound() const
Return true if the size is a power-of-two number of bytes.
Definition: ValueTypes.h:217
const SDValue & getOperand(unsigned Num) const
LoadExtType
LoadExtType enum - This enum defines the three variants of LOADEXT (load with extension).
Definition: ISDOpcodes.h:884
constexpr char Args[]
Key for Kernel::Metadata::mArgs.
bool bitsLE(EVT VT) const
Return true if this has no more bits than VT.
Definition: ValueTypes.h:247
Carry-using nodes for multiple precision addition and subtraction.
Definition: ISDOpcodes.h:231
bool isOneValue() const
Determine if this is a value of 1.
Definition: APInt.h:404
static void ChooseConstraint(TargetLowering::AsmOperandInfo &OpInfo, const TargetLowering &TLI, SDValue Op, SelectionDAG *DAG)
If there are multiple different constraints that we could pick for this operand (e.g.
static APInt getOneBitSet(unsigned numBits, unsigned BitNo)
Return an APInt with exactly one bit set in the result.
Definition: APInt.h:581
SubConstraintInfoVector multipleAlternatives
multipleAlternatives - If there are multiple alternative constraints, this array will contain them...
Definition: InlineAsm.h:156
LegalizeAction getCondCodeAction(ISD::CondCode CC, MVT VT) const
Return how the condition code should be treated: either it is legal, needs to be expanded to some oth...
SDValue getVectorElementPointer(SelectionDAG &DAG, SDValue VecPtr, EVT VecVT, SDValue Idx) const
Get a pointer to vector element Idx located in memory for a vector of type VecVT starting at a base a...
mu magicu(unsigned LeadingZeros=0) const
Calculate the magic numbers required to implement an unsigned integer division by a constant as a seq...
Definition: APInt.cpp:1196
KnownBits trunc(unsigned BitWidth)
Truncate the underlying known Zero and One bits.
Definition: KnownBits.h:115
virtual ConstraintWeight getSingleConstraintMatchWeight(AsmOperandInfo &info, const char *constraint) const
Examine constraint string and operand type and determine a weight value.
bool CombineTo(SDValue O, SDValue N)
MCSymbol * getJTISymbol(unsigned JTI, MCContext &Ctx, bool isLinkerPrivate=false) const
getJTISymbol - Return the MCSymbol for the specified non-empty jump table.
const APInt & getAPIntValue() const
virtual bool targetShrinkDemandedConstant(SDValue Op, const APInt &Demanded, TargetLoweringOpt &TLO) const
unsigned getUnorderedFlavor(CondCode Cond)
This function returns 0 if the condition is always false if an operand is a NaN, 1 if the condition i...
Definition: ISDOpcodes.h:962
CondCode getSetCCSwappedOperands(CondCode Operation)
Return the operation corresponding to (Y op X) when given the operation for (X op Y)...
static MVT getVT(Type *Ty, bool HandleUnknown=false)
Return the value type corresponding to the specified type.
Definition: ValueTypes.cpp:283
bool isOperationLegal(unsigned Op, EVT VT) const
Return true if the specified operation is legal on this target.
ConstantSDNode * isConstOrConstSplat(SDValue V)
Returns the SDNode if it is a constant splat BuildVector or constant int.
lazy value info
X = FP_EXTEND(Y) - Extend a smaller FP type into a larger FP type.
Definition: ISDOpcodes.h:529
std::vector< ArgListEntry > ArgListTy
Extended Value Type.
Definition: ValueTypes.h:34
bool isIntN(unsigned N, int64_t x)
Checks if an signed integer fits into the given (dynamic) bit width.
Definition: MathExtras.h:390
uint64_t NextPowerOf2(uint64_t A)
Returns the next power of two (in 64-bits) that is strictly greater than A.
Definition: MathExtras.h:632
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
This structure contains all information that is necessary for lowering calls.
bool isPositionIndependent() const
virtual bool isUsedByReturnOnly(SDNode *, SDValue &) const
Return true if result of the specified node is used by a return node only.
static PointerType * getInt8PtrTy(LLVMContext &C, unsigned AS=0)
Definition: Type.cpp:220
bool isVolatile() const
const TargetMachine & getTargetMachine() const
This class contains a discriminated union of information about pointers in memory operands...
unsigned getNumOperands() const
Return the number of values used by this operation.
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
std::string ConstraintCode
This contains the actual string for the code, like "m".
APInt lshr(unsigned shiftAmt) const
Logical right-shift function.
Definition: APInt.h:959
SDValue getLoad(EVT VT, const SDLoc &dl, SDValue Chain, SDValue Ptr, MachinePointerInfo PtrInfo, unsigned Alignment=0, MachineMemOperand::Flags MMOFlags=MachineMemOperand::MONone, const AAMDNodes &AAInfo=AAMDNodes(), const MDNode *Ranges=nullptr)
Loads are not normal binary operators: their result type is not determined by their operands...
SDValue CreateStackTemporary(EVT VT, unsigned minAlign=1)
Create a stack temporary, suitable for holding the specified value type.
bool isUnindexed() const
Return true if this is NOT a pre/post inc/dec load/store.
This base class for TargetLowering contains the SelectionDAG-independent parts that can be used from ...
SDValue getBitcast(EVT VT, SDValue V)
Return a bitcast using the SDLoc of the value operand, and casting to the provided type...
static APInt getSignMask(unsigned BitWidth)
Get the SignMask for a specific bit width.
Definition: APInt.h:548
TokenFactor - This node takes multiple tokens as input and produces a single token result...
Definition: ISDOpcodes.h:50
bool isLegalRC(const TargetRegisterInfo &TRI, const TargetRegisterClass &RC) const
Return true if the value types that can be represented by the specified register class are all legal...
static IntegerType * get(LLVMContext &C, unsigned NumBits)
This static method is the primary way of constructing an IntegerType.
Definition: Type.cpp:240
virtual SDValue BuildSDIVPow2(SDNode *N, const APInt &Divisor, SelectionDAG &DAG, std::vector< SDNode *> *Created) const
Targets may override this function to provide custom SDIV lowering for power-of-2 denominators...
const TargetLowering & getTargetLoweringInfo() const
Definition: SelectionDAG.h:379
static void Merge(const std::string &Input, const std::vector< std::string > Result, size_t NumNewFeatures)
void setNoUnsignedWrap(bool b)
SmallVectorImpl< T >::const_pointer c_str(SmallVectorImpl< T > &str)
SDValue scalarizeVectorLoad(LoadSDNode *LD, SelectionDAG &DAG) const
Turn load of vector type into a load of the individual elements.
#define E
Definition: LargeTest.cpp:27
virtual ConstraintWeight getMultipleConstraintMatchWeight(AsmOperandInfo &info, int maIndex) const
Examine constraint type and operand type and determine a weight value.
ValTy * getArgument(unsigned ArgNo) const
Definition: CallSite.h:183
SDValue lowerCmpEqZeroToCtlzSrl(SDValue Op, SelectionDAG &DAG) const
EXTRACT_VECTOR_ELT(VECTOR, IDX) - Returns a single element from VECTOR identified by the (potentially...
Definition: ISDOpcodes.h:313
EVT getVectorElementType() const
Given a vector type, return the type of each element.
Definition: ValueTypes.h:265
SDNode * UpdateNodeOperands(SDNode *N, SDValue Op)
Mutate the specified node in-place to have the specified operands.
double Log2(double Value)
Return the log base 2 of the specified value.
Definition: MathExtras.h:520
This is used to represent a portion of an LLVM function in a low-level Data Dependence DAG representa...
Definition: SelectionDAG.h:209
APInt m
magic number
Definition: APInt.h:1941
SDValue getZExtOrTrunc(SDValue Op, const SDLoc &DL, EVT VT)
Convert Op, which must be of integer type, to the integer type VT, by either zero-extending or trunca...
virtual SDValue getPICJumpTableRelocBase(SDValue Table, SelectionDAG &DAG) const
Returns relocation base for the given PIC jumptable.
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:864
SDValue BuildSDIV(SDNode *N, const APInt &Divisor, SelectionDAG &DAG, bool IsAfterLegalization, std::vector< SDNode *> *Created) const
Given an ISD::SDIV node expressing a divide by constant, return a DAG expression to select that will ...
SDValue getBuildVector(EVT VT, const SDLoc &DL, ArrayRef< SDValue > Ops)
Return an ISD::BUILD_VECTOR node.
Definition: SelectionDAG.h:698
CCValAssign - Represent assignment of one arg/retval to a location.
const size_t N
Wrapper class for IR location info (IR ordering and DebugLoc) to be passed into SDNode creation funct...
static APInt getMinValue(unsigned numBits)
Gets minimum unsigned value of APInt for a specific bit width.
Definition: APInt.h:535
CallLoweringInfo & setSExtResult(bool Value=true)
SDValue IncrementMemoryAddress(SDValue Addr, SDValue Mask, const SDLoc &DL, EVT DataVT, SelectionDAG &DAG, bool IsCompressedMemory) const
Increments memory address Addr according to the type of the value DataVT that should be stored...
SDValue BuildUDIV(SDNode *N, const APInt &Divisor, SelectionDAG &DAG, bool IsAfterLegalization, std::vector< SDNode *> *Created) const
Given an ISD::UDIV node expressing a divide by constant, return a DAG expression to select that will ...
Represents one node in the SelectionDAG.
virtual void computeKnownBitsForTargetNode(const SDValue Op, KnownBits &Known, const APInt &DemandedElts, const SelectionDAG &DAG, unsigned Depth=0) const
Determine which of the bits specified in Mask are known to be either zero or one and return them in t...
CondCode getSetCCInverse(CondCode Operation, bool isInteger)
Return the operation corresponding to !(X op Y), where &#39;op&#39; is a valid SetCC operation.
SDValue getNOT(const SDLoc &DL, SDValue Val, EVT VT)
Create a bitwise NOT operation as (XOR Val, -1).
bool isConstFalseVal(const SDNode *N) const
Return if the N is a constant or constant vector equal to the false value from getBooleanContents().
MachinePointerInfo getWithOffset(int64_t O) const
C - The default llvm calling convention, compatible with C.
Definition: CallingConv.h:35
unsigned Log2_32(uint32_t Value)
Return the floor log base 2 of the specified value, -1 if the value is zero.
Definition: MathExtras.h:531
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:923