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!");
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 = Demanded.getActiveBits();
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  assert(DemandedSize <= SmallVTBits && "Narrowed below demanded bits?");
425  SDValue Z = DAG.getNode(ISD::ANY_EXTEND, dl, Op.getValueType(), X);
426  return TLO.CombineTo(Op, Z);
427  }
428  }
429  return false;
430 }
431 
432 bool
434  const APInt &Demanded,
435  DAGCombinerInfo &DCI,
436  TargetLoweringOpt &TLO) const {
437  SDValue Op = User->getOperand(OpIdx);
438  KnownBits Known;
439 
440  if (!SimplifyDemandedBits(Op, Demanded, Known, TLO, 0, true))
441  return false;
442 
443 
444  // Old will not always be the same as Op. For example:
445  //
446  // Demanded = 0xffffff
447  // Op = i64 truncate (i32 and x, 0xffffff)
448  // In this case simplify demand bits will want to replace the 'and' node
449  // with the value 'x', which will give us:
450  // Old = i32 and x, 0xffffff
451  // New = x
452  if (TLO.Old.hasOneUse()) {
453  // For the one use case, we just commit the change.
454  DCI.CommitTargetLoweringOpt(TLO);
455  return true;
456  }
457 
458  // If Old has more than one use then it must be Op, because the
459  // AssumeSingleUse flag is not propogated to recursive calls of
460  // SimplifyDemanded bits, so the only node with multiple use that
461  // it will attempt to combine will be opt.
462  assert(TLO.Old == Op);
463 
465  for (unsigned i = 0, e = User->getNumOperands(); i != e; ++i) {
466  if (i == OpIdx) {
467  NewOps.push_back(TLO.New);
468  continue;
469  }
470  NewOps.push_back(User->getOperand(i));
471  }
472  TLO.DAG.UpdateNodeOperands(User, NewOps);
473  // Op has less users now, so we may be able to perform additional combines
474  // with it.
475  DCI.AddToWorklist(Op.getNode());
476  // User's operands have been updated, so we may be able to do new combines
477  // with it.
478  DCI.AddToWorklist(User);
479  return true;
480 }
481 
483  DAGCombinerInfo &DCI) const {
484 
485  SelectionDAG &DAG = DCI.DAG;
486  TargetLoweringOpt TLO(DAG, !DCI.isBeforeLegalize(),
487  !DCI.isBeforeLegalizeOps());
488  KnownBits Known;
489 
490  bool Simplified = SimplifyDemandedBits(Op, DemandedMask, Known, TLO);
491  if (Simplified)
492  DCI.CommitTargetLoweringOpt(TLO);
493  return Simplified;
494 }
495 
496 /// Look at Op. At this point, we know that only the DemandedMask bits of the
497 /// result of Op are ever used downstream. If we can use this information to
498 /// simplify Op, create a new simplified DAG node and return true, returning the
499 /// original and new nodes in Old and New. Otherwise, analyze the expression and
500 /// return a mask of Known bits for the expression (used to simplify the
501 /// caller). The Known bits may only be accurate for those bits in the
502 /// DemandedMask.
504  const APInt &DemandedMask,
505  KnownBits &Known,
506  TargetLoweringOpt &TLO,
507  unsigned Depth,
508  bool AssumeSingleUse) const {
509  unsigned BitWidth = DemandedMask.getBitWidth();
510  assert(Op.getScalarValueSizeInBits() == BitWidth &&
511  "Mask size mismatches value type size!");
512  APInt NewMask = DemandedMask;
513  SDLoc dl(Op);
514  auto &DL = TLO.DAG.getDataLayout();
515 
516  // Don't know anything.
517  Known = KnownBits(BitWidth);
518 
519  // Other users may use these bits.
520  if (!Op.getNode()->hasOneUse() && !AssumeSingleUse) {
521  if (Depth != 0) {
522  // If not at the root, Just compute the Known bits to
523  // simplify things downstream.
524  TLO.DAG.computeKnownBits(Op, Known, Depth);
525  return false;
526  }
527  // If this is the root being simplified, allow it to have multiple uses,
528  // just set the NewMask to all bits.
529  NewMask = APInt::getAllOnesValue(BitWidth);
530  } else if (DemandedMask == 0) {
531  // Not demanding any bits from Op.
532  if (!Op.isUndef())
533  return TLO.CombineTo(Op, TLO.DAG.getUNDEF(Op.getValueType()));
534  return false;
535  } else if (Depth == 6) { // Limit search depth.
536  return false;
537  }
538 
539  KnownBits Known2, KnownOut;
540  switch (Op.getOpcode()) {
541  case ISD::Constant:
542  // We know all of the bits for a constant!
543  Known.One = cast<ConstantSDNode>(Op)->getAPIntValue();
544  Known.Zero = ~Known.One;
545  return false; // Don't fall through, will infinitely loop.
546  case ISD::BUILD_VECTOR:
547  // Collect the known bits that are shared by every constant vector element.
548  Known.Zero.setAllBits(); Known.One.setAllBits();
549  for (SDValue SrcOp : Op->ops()) {
550  if (!isa<ConstantSDNode>(SrcOp)) {
551  // We can only handle all constant values - bail out with no known bits.
552  Known = KnownBits(BitWidth);
553  return false;
554  }
555  Known2.One = cast<ConstantSDNode>(SrcOp)->getAPIntValue();
556  Known2.Zero = ~Known2.One;
557 
558  // BUILD_VECTOR can implicitly truncate sources, we must handle this.
559  if (Known2.One.getBitWidth() != BitWidth) {
560  assert(Known2.getBitWidth() > BitWidth &&
561  "Expected BUILD_VECTOR implicit truncation");
562  Known2 = Known2.trunc(BitWidth);
563  }
564 
565  // Known bits are the values that are shared by every element.
566  // TODO: support per-element known bits.
567  Known.One &= Known2.One;
568  Known.Zero &= Known2.Zero;
569  }
570  return false; // Don't fall through, will infinitely loop.
571  case ISD::AND:
572  // If the RHS is a constant, check to see if the LHS would be zero without
573  // using the bits from the RHS. Below, we use knowledge about the RHS to
574  // simplify the LHS, here we're using information from the LHS to simplify
575  // the RHS.
576  if (ConstantSDNode *RHSC = isConstOrConstSplat(Op.getOperand(1))) {
577  SDValue Op0 = Op.getOperand(0);
578  KnownBits LHSKnown;
579  // Do not increment Depth here; that can cause an infinite loop.
580  TLO.DAG.computeKnownBits(Op0, LHSKnown, Depth);
581  // If the LHS already has zeros where RHSC does, this and is dead.
582  if ((LHSKnown.Zero & NewMask) == (~RHSC->getAPIntValue() & NewMask))
583  return TLO.CombineTo(Op, Op0);
584 
585  // If any of the set bits in the RHS are known zero on the LHS, shrink
586  // the constant.
587  if (ShrinkDemandedConstant(Op, ~LHSKnown.Zero & NewMask, TLO))
588  return true;
589 
590  // Bitwise-not (xor X, -1) is a special case: we don't usually shrink its
591  // constant, but if this 'and' is only clearing bits that were just set by
592  // the xor, then this 'and' can be eliminated by shrinking the mask of
593  // the xor. For example, for a 32-bit X:
594  // and (xor (srl X, 31), -1), 1 --> xor (srl X, 31), 1
595  if (isBitwiseNot(Op0) && Op0.hasOneUse() &&
596  LHSKnown.One == ~RHSC->getAPIntValue()) {
597  SDValue Xor = TLO.DAG.getNode(ISD::XOR, dl, Op.getValueType(),
598  Op0.getOperand(0), Op.getOperand(1));
599  return TLO.CombineTo(Op, Xor);
600  }
601  }
602 
603  if (SimplifyDemandedBits(Op.getOperand(1), NewMask, Known, TLO, Depth+1))
604  return true;
605  assert(!Known.hasConflict() && "Bits known to be one AND zero?");
606  if (SimplifyDemandedBits(Op.getOperand(0), ~Known.Zero & NewMask,
607  Known2, TLO, Depth+1))
608  return true;
609  assert(!Known2.hasConflict() && "Bits known to be one AND zero?");
610 
611  // If all of the demanded bits are known one on one side, return the other.
612  // These bits cannot contribute to the result of the 'and'.
613  if (NewMask.isSubsetOf(Known2.Zero | Known.One))
614  return TLO.CombineTo(Op, Op.getOperand(0));
615  if (NewMask.isSubsetOf(Known.Zero | Known2.One))
616  return TLO.CombineTo(Op, Op.getOperand(1));
617  // If all of the demanded bits in the inputs are known zeros, return zero.
618  if (NewMask.isSubsetOf(Known.Zero | Known2.Zero))
619  return TLO.CombineTo(Op, TLO.DAG.getConstant(0, dl, Op.getValueType()));
620  // If the RHS is a constant, see if we can simplify it.
621  if (ShrinkDemandedConstant(Op, ~Known2.Zero & NewMask, TLO))
622  return true;
623  // If the operation can be done in a smaller type, do so.
624  if (ShrinkDemandedOp(Op, BitWidth, NewMask, TLO))
625  return true;
626 
627  // Output known-1 bits are only known if set in both the LHS & RHS.
628  Known.One &= Known2.One;
629  // Output known-0 are known to be clear if zero in either the LHS | RHS.
630  Known.Zero |= Known2.Zero;
631  break;
632  case ISD::OR:
633  if (SimplifyDemandedBits(Op.getOperand(1), NewMask, Known, TLO, Depth+1))
634  return true;
635  assert(!Known.hasConflict() && "Bits known to be one AND zero?");
636  if (SimplifyDemandedBits(Op.getOperand(0), ~Known.One & NewMask,
637  Known2, TLO, Depth+1))
638  return true;
639  assert(!Known2.hasConflict() && "Bits known to be one AND zero?");
640 
641  // If all of the demanded bits are known zero on one side, return the other.
642  // These bits cannot contribute to the result of the 'or'.
643  if (NewMask.isSubsetOf(Known2.One | Known.Zero))
644  return TLO.CombineTo(Op, Op.getOperand(0));
645  if (NewMask.isSubsetOf(Known.One | Known2.Zero))
646  return TLO.CombineTo(Op, Op.getOperand(1));
647  // If the RHS is a constant, see if we can simplify it.
648  if (ShrinkDemandedConstant(Op, NewMask, TLO))
649  return true;
650  // If the operation can be done in a smaller type, do so.
651  if (ShrinkDemandedOp(Op, BitWidth, NewMask, TLO))
652  return true;
653 
654  // Output known-0 bits are only known if clear in both the LHS & RHS.
655  Known.Zero &= Known2.Zero;
656  // Output known-1 are known to be set if set in either the LHS | RHS.
657  Known.One |= Known2.One;
658  break;
659  case ISD::XOR: {
660  if (SimplifyDemandedBits(Op.getOperand(1), NewMask, Known, TLO, Depth+1))
661  return true;
662  assert(!Known.hasConflict() && "Bits known to be one AND zero?");
663  if (SimplifyDemandedBits(Op.getOperand(0), NewMask, Known2, TLO, Depth+1))
664  return true;
665  assert(!Known2.hasConflict() && "Bits known to be one AND zero?");
666 
667  // If all of the demanded bits are known zero on one side, return the other.
668  // These bits cannot contribute to the result of the 'xor'.
669  if (NewMask.isSubsetOf(Known.Zero))
670  return TLO.CombineTo(Op, Op.getOperand(0));
671  if (NewMask.isSubsetOf(Known2.Zero))
672  return TLO.CombineTo(Op, Op.getOperand(1));
673  // If the operation can be done in a smaller type, do so.
674  if (ShrinkDemandedOp(Op, BitWidth, NewMask, TLO))
675  return true;
676 
677  // If all of the unknown bits are known to be zero on one side or the other
678  // (but not both) turn this into an *inclusive* or.
679  // e.g. (A & C1)^(B & C2) -> (A & C1)|(B & C2) iff C1&C2 == 0
680  if ((NewMask & ~Known.Zero & ~Known2.Zero) == 0)
681  return TLO.CombineTo(Op, TLO.DAG.getNode(ISD::OR, dl, Op.getValueType(),
682  Op.getOperand(0),
683  Op.getOperand(1)));
684 
685  // Output known-0 bits are known if clear or set in both the LHS & RHS.
686  KnownOut.Zero = (Known.Zero & Known2.Zero) | (Known.One & Known2.One);
687  // Output known-1 are known to be set if set in only one of the LHS, RHS.
688  KnownOut.One = (Known.Zero & Known2.One) | (Known.One & Known2.Zero);
689 
690  // If all of the demanded bits on one side are known, and all of the set
691  // bits on that side are also known to be set on the other side, turn this
692  // into an AND, as we know the bits will be cleared.
693  // e.g. (X | C1) ^ C2 --> (X | C1) & ~C2 iff (C1&C2) == C2
694  // NB: it is okay if more bits are known than are requested
695  if (NewMask.isSubsetOf(Known.Zero|Known.One)) { // all known on one side
696  if (Known.One == Known2.One) { // set bits are the same on both sides
697  EVT VT = Op.getValueType();
698  SDValue ANDC = TLO.DAG.getConstant(~Known.One & NewMask, dl, VT);
699  return TLO.CombineTo(Op, TLO.DAG.getNode(ISD::AND, dl, VT,
700  Op.getOperand(0), ANDC));
701  }
702  }
703 
704  // If the RHS is a constant, see if we can change it. Don't alter a -1
705  // constant because that's a 'not' op, and that is better for combining and
706  // codegen.
708  if (C && !C->isAllOnesValue()) {
709  if (NewMask.isSubsetOf(C->getAPIntValue())) {
710  // We're flipping all demanded bits. Flip the undemanded bits too.
711  SDValue New = TLO.DAG.getNOT(dl, Op.getOperand(0), Op.getValueType());
712  return TLO.CombineTo(Op, New);
713  }
714  // If we can't turn this into a 'not', try to shrink the constant.
715  if (ShrinkDemandedConstant(Op, NewMask, TLO))
716  return true;
717  }
718 
719  Known = std::move(KnownOut);
720  break;
721  }
722  case ISD::SELECT:
723  if (SimplifyDemandedBits(Op.getOperand(2), NewMask, Known, TLO, Depth+1))
724  return true;
725  if (SimplifyDemandedBits(Op.getOperand(1), NewMask, Known2, TLO, Depth+1))
726  return true;
727  assert(!Known.hasConflict() && "Bits known to be one AND zero?");
728  assert(!Known2.hasConflict() && "Bits known to be one AND zero?");
729 
730  // If the operands are constants, see if we can simplify them.
731  if (ShrinkDemandedConstant(Op, NewMask, TLO))
732  return true;
733 
734  // Only known if known in both the LHS and RHS.
735  Known.One &= Known2.One;
736  Known.Zero &= Known2.Zero;
737  break;
738  case ISD::SELECT_CC:
739  if (SimplifyDemandedBits(Op.getOperand(3), NewMask, Known, TLO, Depth+1))
740  return true;
741  if (SimplifyDemandedBits(Op.getOperand(2), NewMask, Known2, TLO, Depth+1))
742  return true;
743  assert(!Known.hasConflict() && "Bits known to be one AND zero?");
744  assert(!Known2.hasConflict() && "Bits known to be one AND zero?");
745 
746  // If the operands are constants, see if we can simplify them.
747  if (ShrinkDemandedConstant(Op, NewMask, TLO))
748  return true;
749 
750  // Only known if known in both the LHS and RHS.
751  Known.One &= Known2.One;
752  Known.Zero &= Known2.Zero;
753  break;
754  case ISD::SETCC: {
755  SDValue Op0 = Op.getOperand(0);
756  SDValue Op1 = Op.getOperand(1);
757  ISD::CondCode CC = cast<CondCodeSDNode>(Op.getOperand(2))->get();
758  // If (1) we only need the sign-bit, (2) the setcc operands are the same
759  // width as the setcc result, and (3) the result of a setcc conforms to 0 or
760  // -1, we may be able to bypass the setcc.
761  if (NewMask.isSignMask() && Op0.getScalarValueSizeInBits() == BitWidth &&
763  BooleanContent::ZeroOrNegativeOneBooleanContent) {
764  // If we're testing X < 0, then this compare isn't needed - just use X!
765  // FIXME: We're limiting to integer types here, but this should also work
766  // if we don't care about FP signed-zero. The use of SETLT with FP means
767  // that we don't care about NaNs.
768  if (CC == ISD::SETLT && Op1.getValueType().isInteger() &&
770  return TLO.CombineTo(Op, Op0);
771 
772  // TODO: Should we check for other forms of sign-bit comparisons?
773  // Examples: X <= -1, X >= 0
774  }
775  if (getBooleanContents(Op0.getValueType()) ==
777  BitWidth > 1)
778  Known.Zero.setBitsFrom(1);
779  break;
780  }
781  case ISD::SHL:
782  if (ConstantSDNode *SA = isConstOrConstSplat(Op.getOperand(1))) {
783  SDValue InOp = Op.getOperand(0);
784 
785  // If the shift count is an invalid immediate, don't do anything.
786  if (SA->getAPIntValue().uge(BitWidth))
787  break;
788 
789  unsigned ShAmt = SA->getZExtValue();
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  if (ConstantSDNode *SA2 = isConstOrConstSplat(InOp.getOperand(1))) {
796  if (ShAmt && (NewMask & APInt::getLowBitsSet(BitWidth, ShAmt)) == 0) {
797  if (SA2->getAPIntValue().ult(BitWidth)) {
798  unsigned C1 = SA2->getZExtValue();
799  unsigned Opc = ISD::SHL;
800  int Diff = ShAmt-C1;
801  if (Diff < 0) {
802  Diff = -Diff;
803  Opc = ISD::SRL;
804  }
805 
806  SDValue NewSA =
807  TLO.DAG.getConstant(Diff, dl, Op.getOperand(1).getValueType());
808  EVT VT = Op.getValueType();
809  return TLO.CombineTo(Op, TLO.DAG.getNode(Opc, dl, VT,
810  InOp.getOperand(0),
811  NewSA));
812  }
813  }
814  }
815  }
816 
817  if (SimplifyDemandedBits(InOp, NewMask.lshr(ShAmt), Known, TLO, Depth+1))
818  return true;
819 
820  // Convert (shl (anyext x, c)) to (anyext (shl x, c)) if the high bits
821  // are not demanded. This will likely allow the anyext to be folded away.
822  if (InOp.getNode()->getOpcode() == ISD::ANY_EXTEND) {
823  SDValue InnerOp = InOp.getOperand(0);
824  EVT InnerVT = InnerOp.getValueType();
825  unsigned InnerBits = InnerVT.getScalarSizeInBits();
826  if (ShAmt < InnerBits && NewMask.getActiveBits() <= InnerBits &&
827  isTypeDesirableForOp(ISD::SHL, InnerVT)) {
828  EVT ShTy = getShiftAmountTy(InnerVT, DL);
829  if (!APInt(BitWidth, ShAmt).isIntN(ShTy.getSizeInBits()))
830  ShTy = InnerVT;
831  SDValue NarrowShl =
832  TLO.DAG.getNode(ISD::SHL, dl, InnerVT, InnerOp,
833  TLO.DAG.getConstant(ShAmt, dl, ShTy));
834  return
835  TLO.CombineTo(Op,
836  TLO.DAG.getNode(ISD::ANY_EXTEND, dl, Op.getValueType(),
837  NarrowShl));
838  }
839  // Repeat the SHL optimization above in cases where an extension
840  // intervenes: (shl (anyext (shr x, c1)), c2) to
841  // (shl (anyext x), c2-c1). This requires that the bottom c1 bits
842  // aren't demanded (as above) and that the shifted upper c1 bits of
843  // x aren't demanded.
844  if (InOp.hasOneUse() && InnerOp.getOpcode() == ISD::SRL &&
845  InnerOp.hasOneUse()) {
846  if (ConstantSDNode *SA2 = isConstOrConstSplat(InnerOp.getOperand(1))) {
847  unsigned InnerShAmt = SA2->getLimitedValue(InnerBits);
848  if (InnerShAmt < ShAmt &&
849  InnerShAmt < InnerBits &&
850  NewMask.getActiveBits() <= (InnerBits - InnerShAmt + ShAmt) &&
851  NewMask.countTrailingZeros() >= ShAmt) {
852  SDValue NewSA =
853  TLO.DAG.getConstant(ShAmt - InnerShAmt, dl,
854  Op.getOperand(1).getValueType());
855  EVT VT = Op.getValueType();
856  SDValue NewExt = TLO.DAG.getNode(ISD::ANY_EXTEND, dl, VT,
857  InnerOp.getOperand(0));
858  return TLO.CombineTo(Op, TLO.DAG.getNode(ISD::SHL, dl, VT,
859  NewExt, NewSA));
860  }
861  }
862  }
863  }
864 
865  Known.Zero <<= ShAmt;
866  Known.One <<= ShAmt;
867  // low bits known zero.
868  Known.Zero.setLowBits(ShAmt);
869  }
870  break;
871  case ISD::SRL:
872  if (ConstantSDNode *SA = isConstOrConstSplat(Op.getOperand(1))) {
873  SDValue InOp = Op.getOperand(0);
874 
875  // If the shift count is an invalid immediate, don't do anything.
876  if (SA->getAPIntValue().uge(BitWidth))
877  break;
878 
879  unsigned ShAmt = SA->getZExtValue();
880  APInt InDemandedMask = (NewMask << ShAmt);
881 
882  // If the shift is exact, then it does demand the low bits (and knows that
883  // they are zero).
884  if (Op->getFlags().hasExact())
885  InDemandedMask.setLowBits(ShAmt);
886 
887  // If this is ((X << C1) >>u ShAmt), see if we can simplify this into a
888  // single shift. We can do this if the top bits (which are shifted out)
889  // are never demanded.
890  if (InOp.getOpcode() == ISD::SHL) {
891  if (ConstantSDNode *SA2 = isConstOrConstSplat(InOp.getOperand(1))) {
892  if (ShAmt &&
893  (NewMask & APInt::getHighBitsSet(BitWidth, ShAmt)) == 0) {
894  if (SA2->getAPIntValue().ult(BitWidth)) {
895  unsigned C1 = SA2->getZExtValue();
896  unsigned Opc = ISD::SRL;
897  int Diff = ShAmt-C1;
898  if (Diff < 0) {
899  Diff = -Diff;
900  Opc = ISD::SHL;
901  }
902 
903  SDValue NewSA =
904  TLO.DAG.getConstant(Diff, dl, Op.getOperand(1).getValueType());
905  EVT VT = Op.getValueType();
906  return TLO.CombineTo(Op, TLO.DAG.getNode(Opc, dl, VT,
907  InOp.getOperand(0),
908  NewSA));
909  }
910  }
911  }
912  }
913 
914  // Compute the new bits that are at the top now.
915  if (SimplifyDemandedBits(InOp, InDemandedMask, Known, TLO, Depth+1))
916  return true;
917  assert(!Known.hasConflict() && "Bits known to be one AND zero?");
918  Known.Zero.lshrInPlace(ShAmt);
919  Known.One.lshrInPlace(ShAmt);
920 
921  Known.Zero.setHighBits(ShAmt); // High bits known zero.
922  }
923  break;
924  case ISD::SRA:
925  // If this is an arithmetic shift right and only the low-bit is set, we can
926  // always convert this into a logical shr, even if the shift amount is
927  // variable. The low bit of the shift cannot be an input sign bit unless
928  // the shift amount is >= the size of the datatype, which is undefined.
929  if (NewMask.isOneValue())
930  return TLO.CombineTo(Op,
931  TLO.DAG.getNode(ISD::SRL, dl, Op.getValueType(),
932  Op.getOperand(0), Op.getOperand(1)));
933 
934  if (ConstantSDNode *SA = isConstOrConstSplat(Op.getOperand(1))) {
935  EVT VT = Op.getValueType();
936 
937  // If the shift count is an invalid immediate, don't do anything.
938  if (SA->getAPIntValue().uge(BitWidth))
939  break;
940 
941  unsigned ShAmt = SA->getZExtValue();
942  APInt InDemandedMask = (NewMask << ShAmt);
943 
944  // If the shift is exact, then it does demand the low bits (and knows that
945  // they are zero).
946  if (Op->getFlags().hasExact())
947  InDemandedMask.setLowBits(ShAmt);
948 
949  // If any of the demanded bits are produced by the sign extension, we also
950  // demand the input sign bit.
951  if (NewMask.countLeadingZeros() < ShAmt)
952  InDemandedMask.setSignBit();
953 
954  if (SimplifyDemandedBits(Op.getOperand(0), InDemandedMask, Known, TLO,
955  Depth+1))
956  return true;
957  assert(!Known.hasConflict() && "Bits known to be one AND zero?");
958  Known.Zero.lshrInPlace(ShAmt);
959  Known.One.lshrInPlace(ShAmt);
960 
961  // If the input sign bit is known to be zero, or if none of the top bits
962  // are demanded, turn this into an unsigned shift right.
963  if (Known.Zero[BitWidth - ShAmt - 1] ||
964  NewMask.countLeadingZeros() >= ShAmt) {
966  Flags.setExact(Op->getFlags().hasExact());
967  return TLO.CombineTo(Op,
968  TLO.DAG.getNode(ISD::SRL, dl, VT, Op.getOperand(0),
969  Op.getOperand(1), Flags));
970  }
971 
972  int Log2 = NewMask.exactLogBase2();
973  if (Log2 >= 0) {
974  // The bit must come from the sign.
975  SDValue NewSA =
976  TLO.DAG.getConstant(BitWidth - 1 - Log2, dl,
977  Op.getOperand(1).getValueType());
978  return TLO.CombineTo(Op, TLO.DAG.getNode(ISD::SRL, dl, VT,
979  Op.getOperand(0), NewSA));
980  }
981 
982  if (Known.One[BitWidth - ShAmt - 1])
983  // New bits are known one.
984  Known.One.setHighBits(ShAmt);
985  }
986  break;
987  case ISD::SIGN_EXTEND_INREG: {
988  EVT ExVT = cast<VTSDNode>(Op.getOperand(1))->getVT();
989 
990  APInt MsbMask = APInt::getHighBitsSet(BitWidth, 1);
991  // If we only care about the highest bit, don't bother shifting right.
992  if (MsbMask == NewMask) {
993  unsigned ShAmt = ExVT.getScalarSizeInBits();
994  SDValue InOp = Op.getOperand(0);
995  unsigned VTBits = Op->getValueType(0).getScalarSizeInBits();
996  bool AlreadySignExtended =
997  TLO.DAG.ComputeNumSignBits(InOp) >= VTBits-ShAmt+1;
998  // However if the input is already sign extended we expect the sign
999  // extension to be dropped altogether later and do not simplify.
1000  if (!AlreadySignExtended) {
1001  // Compute the correct shift amount type, which must be getShiftAmountTy
1002  // for scalar types after legalization.
1003  EVT ShiftAmtTy = Op.getValueType();
1004  if (TLO.LegalTypes() && !ShiftAmtTy.isVector())
1005  ShiftAmtTy = getShiftAmountTy(ShiftAmtTy, DL);
1006 
1007  SDValue ShiftAmt = TLO.DAG.getConstant(BitWidth - ShAmt, dl,
1008  ShiftAmtTy);
1009  return TLO.CombineTo(Op, TLO.DAG.getNode(ISD::SHL, dl,
1010  Op.getValueType(), InOp,
1011  ShiftAmt));
1012  }
1013  }
1014 
1015  // Sign extension. Compute the demanded bits in the result that are not
1016  // present in the input.
1017  APInt NewBits =
1018  APInt::getHighBitsSet(BitWidth,
1019  BitWidth - ExVT.getScalarSizeInBits());
1020 
1021  // If none of the extended bits are demanded, eliminate the sextinreg.
1022  if ((NewBits & NewMask) == 0)
1023  return TLO.CombineTo(Op, Op.getOperand(0));
1024 
1025  APInt InSignBit =
1026  APInt::getSignMask(ExVT.getScalarSizeInBits()).zext(BitWidth);
1027  APInt InputDemandedBits =
1028  APInt::getLowBitsSet(BitWidth,
1029  ExVT.getScalarSizeInBits()) &
1030  NewMask;
1031 
1032  // Since the sign extended bits are demanded, we know that the sign
1033  // bit is demanded.
1034  InputDemandedBits |= InSignBit;
1035 
1036  if (SimplifyDemandedBits(Op.getOperand(0), InputDemandedBits,
1037  Known, TLO, Depth+1))
1038  return true;
1039  assert(!Known.hasConflict() && "Bits known to be one AND zero?");
1040 
1041  // If the sign bit of the input is known set or clear, then we know the
1042  // top bits of the result.
1043 
1044  // If the input sign bit is known zero, convert this into a zero extension.
1045  if (Known.Zero.intersects(InSignBit))
1046  return TLO.CombineTo(Op, TLO.DAG.getZeroExtendInReg(
1047  Op.getOperand(0), dl, ExVT.getScalarType()));
1048 
1049  if (Known.One.intersects(InSignBit)) { // Input sign bit known set
1050  Known.One |= NewBits;
1051  Known.Zero &= ~NewBits;
1052  } else { // Input sign bit unknown
1053  Known.Zero &= ~NewBits;
1054  Known.One &= ~NewBits;
1055  }
1056  break;
1057  }
1058  case ISD::BUILD_PAIR: {
1059  EVT HalfVT = Op.getOperand(0).getValueType();
1060  unsigned HalfBitWidth = HalfVT.getScalarSizeInBits();
1061 
1062  APInt MaskLo = NewMask.getLoBits(HalfBitWidth).trunc(HalfBitWidth);
1063  APInt MaskHi = NewMask.getHiBits(HalfBitWidth).trunc(HalfBitWidth);
1064 
1065  KnownBits KnownLo, KnownHi;
1066 
1067  if (SimplifyDemandedBits(Op.getOperand(0), MaskLo, KnownLo, TLO, Depth + 1))
1068  return true;
1069 
1070  if (SimplifyDemandedBits(Op.getOperand(1), MaskHi, KnownHi, TLO, Depth + 1))
1071  return true;
1072 
1073  Known.Zero = KnownLo.Zero.zext(BitWidth) |
1074  KnownHi.Zero.zext(BitWidth).shl(HalfBitWidth);
1075 
1076  Known.One = KnownLo.One.zext(BitWidth) |
1077  KnownHi.One.zext(BitWidth).shl(HalfBitWidth);
1078  break;
1079  }
1080  case ISD::ZERO_EXTEND: {
1081  unsigned OperandBitWidth = Op.getOperand(0).getScalarValueSizeInBits();
1082  APInt InMask = NewMask.trunc(OperandBitWidth);
1083 
1084  // If none of the top bits are demanded, convert this into an any_extend.
1085  APInt NewBits =
1086  APInt::getHighBitsSet(BitWidth, BitWidth - OperandBitWidth) & NewMask;
1087  if (!NewBits.intersects(NewMask))
1088  return TLO.CombineTo(Op, TLO.DAG.getNode(ISD::ANY_EXTEND, dl,
1089  Op.getValueType(),
1090  Op.getOperand(0)));
1091 
1092  if (SimplifyDemandedBits(Op.getOperand(0), InMask, Known, TLO, Depth+1))
1093  return true;
1094  assert(!Known.hasConflict() && "Bits known to be one AND zero?");
1095  Known = Known.zext(BitWidth);
1096  Known.Zero |= NewBits;
1097  break;
1098  }
1099  case ISD::SIGN_EXTEND: {
1100  EVT InVT = Op.getOperand(0).getValueType();
1101  unsigned InBits = InVT.getScalarSizeInBits();
1102  APInt InMask = APInt::getLowBitsSet(BitWidth, InBits);
1103  APInt InSignBit = APInt::getOneBitSet(BitWidth, InBits - 1);
1104  APInt NewBits = ~InMask & NewMask;
1105 
1106  // If none of the top bits are demanded, convert this into an any_extend.
1107  if (NewBits == 0)
1108  return TLO.CombineTo(Op,TLO.DAG.getNode(ISD::ANY_EXTEND, dl,
1109  Op.getValueType(),
1110  Op.getOperand(0)));
1111 
1112  // Since some of the sign extended bits are demanded, we know that the sign
1113  // bit is demanded.
1114  APInt InDemandedBits = InMask & NewMask;
1115  InDemandedBits |= InSignBit;
1116  InDemandedBits = InDemandedBits.trunc(InBits);
1117 
1118  if (SimplifyDemandedBits(Op.getOperand(0), InDemandedBits, Known, TLO,
1119  Depth+1))
1120  return true;
1121  Known = Known.zext(BitWidth);
1122 
1123  // If the sign bit is known zero, convert this to a zero extend.
1124  if (Known.Zero.intersects(InSignBit))
1125  return TLO.CombineTo(Op, TLO.DAG.getNode(ISD::ZERO_EXTEND, dl,
1126  Op.getValueType(),
1127  Op.getOperand(0)));
1128 
1129  // If the sign bit is known one, the top bits match.
1130  if (Known.One.intersects(InSignBit)) {
1131  Known.One |= NewBits;
1132  assert((Known.Zero & NewBits) == 0);
1133  } else { // Otherwise, top bits aren't known.
1134  assert((Known.One & NewBits) == 0);
1135  assert((Known.Zero & NewBits) == 0);
1136  }
1137  break;
1138  }
1139  case ISD::ANY_EXTEND: {
1140  unsigned OperandBitWidth = Op.getOperand(0).getScalarValueSizeInBits();
1141  APInt InMask = NewMask.trunc(OperandBitWidth);
1142  if (SimplifyDemandedBits(Op.getOperand(0), InMask, Known, TLO, Depth+1))
1143  return true;
1144  assert(!Known.hasConflict() && "Bits known to be one AND zero?");
1145  Known = Known.zext(BitWidth);
1146  break;
1147  }
1148  case ISD::TRUNCATE: {
1149  // Simplify the input, using demanded bit information, and compute the known
1150  // zero/one bits live out.
1151  unsigned OperandBitWidth = Op.getOperand(0).getScalarValueSizeInBits();
1152  APInt TruncMask = NewMask.zext(OperandBitWidth);
1153  if (SimplifyDemandedBits(Op.getOperand(0), TruncMask, Known, TLO, Depth+1))
1154  return true;
1155  Known = Known.trunc(BitWidth);
1156 
1157  // If the input is only used by this truncate, see if we can shrink it based
1158  // on the known demanded bits.
1159  if (Op.getOperand(0).getNode()->hasOneUse()) {
1160  SDValue In = Op.getOperand(0);
1161  switch (In.getOpcode()) {
1162  default: break;
1163  case ISD::SRL:
1164  // Shrink SRL by a constant if none of the high bits shifted in are
1165  // demanded.
1166  if (TLO.LegalTypes() &&
1168  // Do not turn (vt1 truncate (vt2 srl)) into (vt1 srl) if vt1 is
1169  // undesirable.
1170  break;
1172  if (!ShAmt)
1173  break;
1174  SDValue Shift = In.getOperand(1);
1175  if (TLO.LegalTypes()) {
1176  uint64_t ShVal = ShAmt->getZExtValue();
1177  Shift = TLO.DAG.getConstant(ShVal, dl,
1178  getShiftAmountTy(Op.getValueType(), DL));
1179  }
1180 
1181  if (ShAmt->getZExtValue() < BitWidth) {
1182  APInt HighBits = APInt::getHighBitsSet(OperandBitWidth,
1183  OperandBitWidth - BitWidth);
1184  HighBits.lshrInPlace(ShAmt->getZExtValue());
1185  HighBits = HighBits.trunc(BitWidth);
1186 
1187  if (!(HighBits & NewMask)) {
1188  // None of the shifted in bits are needed. Add a truncate of the
1189  // shift input, then shift it.
1190  SDValue NewTrunc = TLO.DAG.getNode(ISD::TRUNCATE, dl,
1191  Op.getValueType(),
1192  In.getOperand(0));
1193  return TLO.CombineTo(Op, TLO.DAG.getNode(ISD::SRL, dl,
1194  Op.getValueType(),
1195  NewTrunc,
1196  Shift));
1197  }
1198  }
1199  break;
1200  }
1201  }
1202 
1203  assert(!Known.hasConflict() && "Bits known to be one AND zero?");
1204  break;
1205  }
1206  case ISD::AssertZext: {
1207  // AssertZext demands all of the high bits, plus any of the low bits
1208  // demanded by its users.
1209  EVT VT = cast<VTSDNode>(Op.getOperand(1))->getVT();
1210  APInt InMask = APInt::getLowBitsSet(BitWidth,
1211  VT.getSizeInBits());
1212  if (SimplifyDemandedBits(Op.getOperand(0), ~InMask | NewMask,
1213  Known, TLO, Depth+1))
1214  return true;
1215  assert(!Known.hasConflict() && "Bits known to be one AND zero?");
1216 
1217  Known.Zero |= ~InMask;
1218  break;
1219  }
1220  case ISD::BITCAST:
1221  // If this is an FP->Int bitcast and if the sign bit is the only
1222  // thing demanded, turn this into a FGETSIGN.
1223  if (!TLO.LegalOperations() &&
1224  !Op.getValueType().isVector() &&
1225  !Op.getOperand(0).getValueType().isVector() &&
1226  NewMask == APInt::getSignMask(Op.getValueSizeInBits()) &&
1228  bool OpVTLegal = isOperationLegalOrCustom(ISD::FGETSIGN, Op.getValueType());
1230  if ((OpVTLegal || i32Legal) && Op.getValueType().isSimple() &&
1231  Op.getOperand(0).getValueType() != MVT::f128) {
1232  // Cannot eliminate/lower SHL for f128 yet.
1233  EVT Ty = OpVTLegal ? Op.getValueType() : MVT::i32;
1234  // Make a FGETSIGN + SHL to move the sign bit into the appropriate
1235  // place. We expect the SHL to be eliminated by other optimizations.
1236  SDValue Sign = TLO.DAG.getNode(ISD::FGETSIGN, dl, Ty, Op.getOperand(0));
1237  unsigned OpVTSizeInBits = Op.getValueSizeInBits();
1238  if (!OpVTLegal && OpVTSizeInBits > 32)
1239  Sign = TLO.DAG.getNode(ISD::ZERO_EXTEND, dl, Op.getValueType(), Sign);
1240  unsigned ShVal = Op.getValueSizeInBits() - 1;
1241  SDValue ShAmt = TLO.DAG.getConstant(ShVal, dl, Op.getValueType());
1242  return TLO.CombineTo(Op, TLO.DAG.getNode(ISD::SHL, dl,
1243  Op.getValueType(),
1244  Sign, ShAmt));
1245  }
1246  }
1247  break;
1248  case ISD::ADD:
1249  case ISD::MUL:
1250  case ISD::SUB: {
1251  // Add, Sub, and Mul don't demand any bits in positions beyond that
1252  // of the highest bit demanded of them.
1253  APInt LoMask = APInt::getLowBitsSet(BitWidth,
1254  BitWidth - NewMask.countLeadingZeros());
1255  if (SimplifyDemandedBits(Op.getOperand(0), LoMask, Known2, TLO, Depth+1) ||
1256  SimplifyDemandedBits(Op.getOperand(1), LoMask, Known2, TLO, Depth+1) ||
1257  // See if the operation should be performed at a smaller bit width.
1258  ShrinkDemandedOp(Op, BitWidth, NewMask, TLO)) {
1259  SDNodeFlags Flags = Op.getNode()->getFlags();
1260  if (Flags.hasNoSignedWrap() || Flags.hasNoUnsignedWrap()) {
1261  // Disable the nsw and nuw flags. We can no longer guarantee that we
1262  // won't wrap after simplification.
1263  Flags.setNoSignedWrap(false);
1264  Flags.setNoUnsignedWrap(false);
1265  SDValue NewOp = TLO.DAG.getNode(Op.getOpcode(), dl, Op.getValueType(),
1266  Op.getOperand(0), Op.getOperand(1),
1267  Flags);
1268  return TLO.CombineTo(Op, NewOp);
1269  }
1270  return true;
1271  }
1273  }
1274  default:
1275  // Just use computeKnownBits to compute output bits.
1276  TLO.DAG.computeKnownBits(Op, Known, Depth);
1277  break;
1278  }
1279 
1280  // If we know the value of all of the demanded bits, return this as a
1281  // constant.
1282  if (NewMask.isSubsetOf(Known.Zero|Known.One)) {
1283  // Avoid folding to a constant if any OpaqueConstant is involved.
1284  const SDNode *N = Op.getNode();
1286  E = SDNodeIterator::end(N); I != E; ++I) {
1287  SDNode *Op = *I;
1288  if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op))
1289  if (C->isOpaque())
1290  return false;
1291  }
1292  return TLO.CombineTo(Op,
1293  TLO.DAG.getConstant(Known.One, dl, Op.getValueType()));
1294  }
1295 
1296  return false;
1297 }
1298 
1299 /// Determine which of the bits specified in Mask are known to be either zero or
1300 /// one and return them in the Known.
1302  KnownBits &Known,
1303  const APInt &DemandedElts,
1304  const SelectionDAG &DAG,
1305  unsigned Depth) const {
1309  Op.getOpcode() == ISD::INTRINSIC_VOID) &&
1310  "Should use MaskedValueIsZero if you don't know whether Op"
1311  " is a target node!");
1312  Known.resetAll();
1313 }
1314 
1315 /// This method can be implemented by targets that want to expose additional
1316 /// information about sign bits to the DAG Combiner.
1318  const APInt &,
1319  const SelectionDAG &,
1320  unsigned Depth) const {
1324  Op.getOpcode() == ISD::INTRINSIC_VOID) &&
1325  "Should use ComputeNumSignBits if you don't know whether Op"
1326  " is a target node!");
1327  return 1;
1328 }
1329 
1330 // FIXME: Ideally, this would use ISD::isConstantSplatVector(), but that must
1331 // work with truncating build vectors and vectors with elements of less than
1332 // 8 bits.
1334  if (!N)
1335  return false;
1336 
1337  APInt CVal;
1338  if (auto *CN = dyn_cast<ConstantSDNode>(N)) {
1339  CVal = CN->getAPIntValue();
1340  } else if (auto *BV = dyn_cast<BuildVectorSDNode>(N)) {
1341  auto *CN = BV->getConstantSplatNode();
1342  if (!CN)
1343  return false;
1344 
1345  // If this is a truncating build vector, truncate the splat value.
1346  // Otherwise, we may fail to match the expected values below.
1347  unsigned BVEltWidth = BV->getValueType(0).getScalarSizeInBits();
1348  CVal = CN->getAPIntValue();
1349  if (BVEltWidth < CVal.getBitWidth())
1350  CVal = CVal.trunc(BVEltWidth);
1351  } else {
1352  return false;
1353  }
1354 
1355  switch (getBooleanContents(N->getValueType(0))) {
1357  return CVal[0];
1359  return CVal.isOneValue();
1361  return CVal.isAllOnesValue();
1362  }
1363 
1364  llvm_unreachable("Invalid boolean contents");
1365 }
1366 
1368  const SDLoc &DL) const {
1369  unsigned ElementWidth = VT.getScalarSizeInBits();
1370  APInt TrueInt =
1372  ? APInt(ElementWidth, 1)
1373  : APInt::getAllOnesValue(ElementWidth);
1374  return DAG.getConstant(TrueInt, DL, VT);
1375 }
1376 
1378  if (!N)
1379  return false;
1380 
1381  const ConstantSDNode *CN = dyn_cast<ConstantSDNode>(N);
1382  if (!CN) {
1384  if (!BV)
1385  return false;
1386 
1387  // Only interested in constant splats, we don't care about undef
1388  // elements in identifying boolean constants and getConstantSplatNode
1389  // returns NULL if all ops are undef;
1390  CN = BV->getConstantSplatNode();
1391  if (!CN)
1392  return false;
1393  }
1394 
1396  return !CN->getAPIntValue()[0];
1397 
1398  return CN->isNullValue();
1399 }
1400 
1402  bool SExt) const {
1403  if (VT == MVT::i1)
1404  return N->isOne();
1405 
1407  switch (Cnt) {
1409  // An extended value of 1 is always true, unless its original type is i1,
1410  // in which case it will be sign extended to -1.
1411  return (N->isOne() && !SExt) || (SExt && (N->getValueType(0) != MVT::i1));
1414  return N->isAllOnesValue() && SExt;
1415  }
1416  llvm_unreachable("Unexpected enumeration.");
1417 }
1418 
1419 /// This helper function of SimplifySetCC tries to optimize the comparison when
1420 /// either operand of the SetCC node is a bitwise-and instruction.
1421 SDValue TargetLowering::simplifySetCCWithAnd(EVT VT, SDValue N0, SDValue N1,
1422  ISD::CondCode Cond,
1423  DAGCombinerInfo &DCI,
1424  const SDLoc &DL) const {
1425  // Match these patterns in any of their permutations:
1426  // (X & Y) == Y
1427  // (X & Y) != Y
1428  if (N1.getOpcode() == ISD::AND && N0.getOpcode() != ISD::AND)
1429  std::swap(N0, N1);
1430 
1431  EVT OpVT = N0.getValueType();
1432  if (N0.getOpcode() != ISD::AND || !OpVT.isInteger() ||
1433  (Cond != ISD::SETEQ && Cond != ISD::SETNE))
1434  return SDValue();
1435 
1436  SDValue X, Y;
1437  if (N0.getOperand(0) == N1) {
1438  X = N0.getOperand(1);
1439  Y = N0.getOperand(0);
1440  } else if (N0.getOperand(1) == N1) {
1441  X = N0.getOperand(0);
1442  Y = N0.getOperand(1);
1443  } else {
1444  return SDValue();
1445  }
1446 
1447  SelectionDAG &DAG = DCI.DAG;
1448  SDValue Zero = DAG.getConstant(0, DL, OpVT);
1449  if (DAG.isKnownToBeAPowerOfTwo(Y)) {
1450  // Simplify X & Y == Y to X & Y != 0 if Y has exactly one bit set.
1451  // Note that where Y is variable and is known to have at most one bit set
1452  // (for example, if it is Z & 1) we cannot do this; the expressions are not
1453  // equivalent when Y == 0.
1454  Cond = ISD::getSetCCInverse(Cond, /*isInteger=*/true);
1455  if (DCI.isBeforeLegalizeOps() ||
1456  isCondCodeLegal(Cond, N0.getSimpleValueType()))
1457  return DAG.getSetCC(DL, VT, N0, Zero, Cond);
1458  } else if (N0.hasOneUse() && hasAndNotCompare(Y)) {
1459  // If the target supports an 'and-not' or 'and-complement' logic operation,
1460  // try to use that to make a comparison operation more efficient.
1461  // But don't do this transform if the mask is a single bit because there are
1462  // more efficient ways to deal with that case (for example, 'bt' on x86 or
1463  // 'rlwinm' on PPC).
1464 
1465  // Bail out if the compare operand that we want to turn into a zero is
1466  // already a zero (otherwise, infinite loop).
1467  auto *YConst = dyn_cast<ConstantSDNode>(Y);
1468  if (YConst && YConst->isNullValue())
1469  return SDValue();
1470 
1471  // Transform this into: ~X & Y == 0.
1472  SDValue NotX = DAG.getNOT(SDLoc(X), X, OpVT);
1473  SDValue NewAnd = DAG.getNode(ISD::AND, SDLoc(N0), OpVT, NotX, Y);
1474  return DAG.getSetCC(DL, VT, NewAnd, Zero, Cond);
1475  }
1476 
1477  return SDValue();
1478 }
1479 
1480 /// Try to simplify a setcc built with the specified operands and cc. If it is
1481 /// unable to simplify it, return a null SDValue.
1483  ISD::CondCode Cond, bool foldBooleans,
1484  DAGCombinerInfo &DCI,
1485  const SDLoc &dl) const {
1486  SelectionDAG &DAG = DCI.DAG;
1487 
1488  // These setcc operations always fold.
1489  switch (Cond) {
1490  default: break;
1491  case ISD::SETFALSE:
1492  case ISD::SETFALSE2: return DAG.getConstant(0, dl, VT);
1493  case ISD::SETTRUE:
1494  case ISD::SETTRUE2: {
1497  return DAG.getConstant(
1498  Cnt == TargetLowering::ZeroOrNegativeOneBooleanContent ? -1ULL : 1, dl,
1499  VT);
1500  }
1501  }
1502 
1503  // Ensure that the constant occurs on the RHS and fold constant comparisons.
1504  ISD::CondCode SwappedCC = ISD::getSetCCSwappedOperands(Cond);
1505  if (isa<ConstantSDNode>(N0.getNode()) &&
1506  (DCI.isBeforeLegalizeOps() ||
1507  isCondCodeLegal(SwappedCC, N0.getSimpleValueType())))
1508  return DAG.getSetCC(dl, VT, N1, N0, SwappedCC);
1509 
1510  if (auto *N1C = dyn_cast<ConstantSDNode>(N1.getNode())) {
1511  const APInt &C1 = N1C->getAPIntValue();
1512 
1513  // If the LHS is '(srl (ctlz x), 5)', the RHS is 0/1, and this is an
1514  // equality comparison, then we're just comparing whether X itself is
1515  // zero.
1516  if (N0.getOpcode() == ISD::SRL && (C1.isNullValue() || C1.isOneValue()) &&
1517  N0.getOperand(0).getOpcode() == ISD::CTLZ &&
1518  N0.getOperand(1).getOpcode() == ISD::Constant) {
1519  const APInt &ShAmt
1520  = cast<ConstantSDNode>(N0.getOperand(1))->getAPIntValue();
1521  if ((Cond == ISD::SETEQ || Cond == ISD::SETNE) &&
1522  ShAmt == Log2_32(N0.getValueSizeInBits())) {
1523  if ((C1 == 0) == (Cond == ISD::SETEQ)) {
1524  // (srl (ctlz x), 5) == 0 -> X != 0
1525  // (srl (ctlz x), 5) != 1 -> X != 0
1526  Cond = ISD::SETNE;
1527  } else {
1528  // (srl (ctlz x), 5) != 0 -> X == 0
1529  // (srl (ctlz x), 5) == 1 -> X == 0
1530  Cond = ISD::SETEQ;
1531  }
1532  SDValue Zero = DAG.getConstant(0, dl, N0.getValueType());
1533  return DAG.getSetCC(dl, VT, N0.getOperand(0).getOperand(0),
1534  Zero, Cond);
1535  }
1536  }
1537 
1538  SDValue CTPOP = N0;
1539  // Look through truncs that don't change the value of a ctpop.
1540  if (N0.hasOneUse() && N0.getOpcode() == ISD::TRUNCATE)
1541  CTPOP = N0.getOperand(0);
1542 
1543  if (CTPOP.hasOneUse() && CTPOP.getOpcode() == ISD::CTPOP &&
1544  (N0 == CTPOP ||
1546  EVT CTVT = CTPOP.getValueType();
1547  SDValue CTOp = CTPOP.getOperand(0);
1548 
1549  // (ctpop x) u< 2 -> (x & x-1) == 0
1550  // (ctpop x) u> 1 -> (x & x-1) != 0
1551  if ((Cond == ISD::SETULT && C1 == 2) || (Cond == ISD::SETUGT && C1 == 1)){
1552  SDValue Sub = DAG.getNode(ISD::SUB, dl, CTVT, CTOp,
1553  DAG.getConstant(1, dl, CTVT));
1554  SDValue And = DAG.getNode(ISD::AND, dl, CTVT, CTOp, Sub);
1556  return DAG.getSetCC(dl, VT, And, DAG.getConstant(0, dl, CTVT), CC);
1557  }
1558 
1559  // TODO: (ctpop x) == 1 -> x && (x & x-1) == 0 iff ctpop is illegal.
1560  }
1561 
1562  // (zext x) == C --> x == (trunc C)
1563  // (sext x) == C --> x == (trunc C)
1564  if ((Cond == ISD::SETEQ || Cond == ISD::SETNE) &&
1565  DCI.isBeforeLegalize() && N0->hasOneUse()) {
1566  unsigned MinBits = N0.getValueSizeInBits();
1567  SDValue PreExt;
1568  bool Signed = false;
1569  if (N0->getOpcode() == ISD::ZERO_EXTEND) {
1570  // ZExt
1571  MinBits = N0->getOperand(0).getValueSizeInBits();
1572  PreExt = N0->getOperand(0);
1573  } else if (N0->getOpcode() == ISD::AND) {
1574  // DAGCombine turns costly ZExts into ANDs
1575  if (auto *C = dyn_cast<ConstantSDNode>(N0->getOperand(1)))
1576  if ((C->getAPIntValue()+1).isPowerOf2()) {
1577  MinBits = C->getAPIntValue().countTrailingOnes();
1578  PreExt = N0->getOperand(0);
1579  }
1580  } else if (N0->getOpcode() == ISD::SIGN_EXTEND) {
1581  // SExt
1582  MinBits = N0->getOperand(0).getValueSizeInBits();
1583  PreExt = N0->getOperand(0);
1584  Signed = true;
1585  } else if (auto *LN0 = dyn_cast<LoadSDNode>(N0)) {
1586  // ZEXTLOAD / SEXTLOAD
1587  if (LN0->getExtensionType() == ISD::ZEXTLOAD) {
1588  MinBits = LN0->getMemoryVT().getSizeInBits();
1589  PreExt = N0;
1590  } else if (LN0->getExtensionType() == ISD::SEXTLOAD) {
1591  Signed = true;
1592  MinBits = LN0->getMemoryVT().getSizeInBits();
1593  PreExt = N0;
1594  }
1595  }
1596 
1597  // Figure out how many bits we need to preserve this constant.
1598  unsigned ReqdBits = Signed ?
1599  C1.getBitWidth() - C1.getNumSignBits() + 1 :
1600  C1.getActiveBits();
1601 
1602  // Make sure we're not losing bits from the constant.
1603  if (MinBits > 0 &&
1604  MinBits < C1.getBitWidth() &&
1605  MinBits >= ReqdBits) {
1606  EVT MinVT = EVT::getIntegerVT(*DAG.getContext(), MinBits);
1607  if (isTypeDesirableForOp(ISD::SETCC, MinVT)) {
1608  // Will get folded away.
1609  SDValue Trunc = DAG.getNode(ISD::TRUNCATE, dl, MinVT, PreExt);
1610  if (MinBits == 1 && C1 == 1)
1611  // Invert the condition.
1612  return DAG.getSetCC(dl, VT, Trunc, DAG.getConstant(0, dl, MVT::i1),
1613  Cond == ISD::SETEQ ? ISD::SETNE : ISD::SETEQ);
1614  SDValue C = DAG.getConstant(C1.trunc(MinBits), dl, MinVT);
1615  return DAG.getSetCC(dl, VT, Trunc, C, Cond);
1616  }
1617 
1618  // If truncating the setcc operands is not desirable, we can still
1619  // simplify the expression in some cases:
1620  // setcc ([sz]ext (setcc x, y, cc)), 0, setne) -> setcc (x, y, cc)
1621  // setcc ([sz]ext (setcc x, y, cc)), 0, seteq) -> setcc (x, y, inv(cc))
1622  // setcc (zext (setcc x, y, cc)), 1, setne) -> setcc (x, y, inv(cc))
1623  // setcc (zext (setcc x, y, cc)), 1, seteq) -> setcc (x, y, cc)
1624  // setcc (sext (setcc x, y, cc)), -1, setne) -> setcc (x, y, inv(cc))
1625  // setcc (sext (setcc x, y, cc)), -1, seteq) -> setcc (x, y, cc)
1626  SDValue TopSetCC = N0->getOperand(0);
1627  unsigned N0Opc = N0->getOpcode();
1628  bool SExt = (N0Opc == ISD::SIGN_EXTEND);
1629  if (TopSetCC.getValueType() == MVT::i1 && VT == MVT::i1 &&
1630  TopSetCC.getOpcode() == ISD::SETCC &&
1631  (N0Opc == ISD::ZERO_EXTEND || N0Opc == ISD::SIGN_EXTEND) &&
1632  (isConstFalseVal(N1C) ||
1633  isExtendedTrueVal(N1C, N0->getValueType(0), SExt))) {
1634 
1635  bool Inverse = (N1C->isNullValue() && Cond == ISD::SETEQ) ||
1636  (!N1C->isNullValue() && Cond == ISD::SETNE);
1637 
1638  if (!Inverse)
1639  return TopSetCC;
1640 
1642  cast<CondCodeSDNode>(TopSetCC.getOperand(2))->get(),
1643  TopSetCC.getOperand(0).getValueType().isInteger());
1644  return DAG.getSetCC(dl, VT, TopSetCC.getOperand(0),
1645  TopSetCC.getOperand(1),
1646  InvCond);
1647  }
1648  }
1649  }
1650 
1651  // If the LHS is '(and load, const)', the RHS is 0, the test is for
1652  // equality or unsigned, and all 1 bits of the const are in the same
1653  // partial word, see if we can shorten the load.
1654  if (DCI.isBeforeLegalize() &&
1655  !ISD::isSignedIntSetCC(Cond) &&
1656  N0.getOpcode() == ISD::AND && C1 == 0 &&
1657  N0.getNode()->hasOneUse() &&
1658  isa<LoadSDNode>(N0.getOperand(0)) &&
1659  N0.getOperand(0).getNode()->hasOneUse() &&
1660  isa<ConstantSDNode>(N0.getOperand(1))) {
1661  LoadSDNode *Lod = cast<LoadSDNode>(N0.getOperand(0));
1662  APInt bestMask;
1663  unsigned bestWidth = 0, bestOffset = 0;
1664  if (!Lod->isVolatile() && Lod->isUnindexed()) {
1665  unsigned origWidth = N0.getValueSizeInBits();
1666  unsigned maskWidth = origWidth;
1667  // We can narrow (e.g.) 16-bit extending loads on 32-bit target to
1668  // 8 bits, but have to be careful...
1669  if (Lod->getExtensionType() != ISD::NON_EXTLOAD)
1670  origWidth = Lod->getMemoryVT().getSizeInBits();
1671  const APInt &Mask =
1672  cast<ConstantSDNode>(N0.getOperand(1))->getAPIntValue();
1673  for (unsigned width = origWidth / 2; width>=8; width /= 2) {
1674  APInt newMask = APInt::getLowBitsSet(maskWidth, width);
1675  for (unsigned offset=0; offset<origWidth/width; offset++) {
1676  if (Mask.isSubsetOf(newMask)) {
1677  if (DAG.getDataLayout().isLittleEndian())
1678  bestOffset = (uint64_t)offset * (width/8);
1679  else
1680  bestOffset = (origWidth/width - offset - 1) * (width/8);
1681  bestMask = Mask.lshr(offset * (width/8) * 8);
1682  bestWidth = width;
1683  break;
1684  }
1685  newMask <<= width;
1686  }
1687  }
1688  }
1689  if (bestWidth) {
1690  EVT newVT = EVT::getIntegerVT(*DAG.getContext(), bestWidth);
1691  if (newVT.isRound()) {
1692  EVT PtrType = Lod->getOperand(1).getValueType();
1693  SDValue Ptr = Lod->getBasePtr();
1694  if (bestOffset != 0)
1695  Ptr = DAG.getNode(ISD::ADD, dl, PtrType, Lod->getBasePtr(),
1696  DAG.getConstant(bestOffset, dl, PtrType));
1697  unsigned NewAlign = MinAlign(Lod->getAlignment(), bestOffset);
1698  SDValue NewLoad = DAG.getLoad(
1699  newVT, dl, Lod->getChain(), Ptr,
1700  Lod->getPointerInfo().getWithOffset(bestOffset), NewAlign);
1701  return DAG.getSetCC(dl, VT,
1702  DAG.getNode(ISD::AND, dl, newVT, NewLoad,
1703  DAG.getConstant(bestMask.trunc(bestWidth),
1704  dl, newVT)),
1705  DAG.getConstant(0LL, dl, newVT), Cond);
1706  }
1707  }
1708  }
1709 
1710  // If the LHS is a ZERO_EXTEND, perform the comparison on the input.
1711  if (N0.getOpcode() == ISD::ZERO_EXTEND) {
1712  unsigned InSize = N0.getOperand(0).getValueSizeInBits();
1713 
1714  // If the comparison constant has bits in the upper part, the
1715  // zero-extended value could never match.
1716  if (C1.intersects(APInt::getHighBitsSet(C1.getBitWidth(),
1717  C1.getBitWidth() - InSize))) {
1718  switch (Cond) {
1719  case ISD::SETUGT:
1720  case ISD::SETUGE:
1721  case ISD::SETEQ:
1722  return DAG.getConstant(0, dl, VT);
1723  case ISD::SETULT:
1724  case ISD::SETULE:
1725  case ISD::SETNE:
1726  return DAG.getConstant(1, dl, VT);
1727  case ISD::SETGT:
1728  case ISD::SETGE:
1729  // True if the sign bit of C1 is set.
1730  return DAG.getConstant(C1.isNegative(), dl, VT);
1731  case ISD::SETLT:
1732  case ISD::SETLE:
1733  // True if the sign bit of C1 isn't set.
1734  return DAG.getConstant(C1.isNonNegative(), dl, VT);
1735  default:
1736  break;
1737  }
1738  }
1739 
1740  // Otherwise, we can perform the comparison with the low bits.
1741  switch (Cond) {
1742  case ISD::SETEQ:
1743  case ISD::SETNE:
1744  case ISD::SETUGT:
1745  case ISD::SETUGE:
1746  case ISD::SETULT:
1747  case ISD::SETULE: {
1748  EVT newVT = N0.getOperand(0).getValueType();
1749  if (DCI.isBeforeLegalizeOps() ||
1750  (isOperationLegal(ISD::SETCC, newVT) &&
1751  getCondCodeAction(Cond, newVT.getSimpleVT()) == Legal)) {
1752  EVT NewSetCCVT =
1753  getSetCCResultType(DAG.getDataLayout(), *DAG.getContext(), newVT);
1754  SDValue NewConst = DAG.getConstant(C1.trunc(InSize), dl, newVT);
1755 
1756  SDValue NewSetCC = DAG.getSetCC(dl, NewSetCCVT, N0.getOperand(0),
1757  NewConst, Cond);
1758  return DAG.getBoolExtOrTrunc(NewSetCC, dl, VT, N0.getValueType());
1759  }
1760  break;
1761  }
1762  default:
1763  break; // todo, be more careful with signed comparisons
1764  }
1765  } else if (N0.getOpcode() == ISD::SIGN_EXTEND_INREG &&
1766  (Cond == ISD::SETEQ || Cond == ISD::SETNE)) {
1767  EVT ExtSrcTy = cast<VTSDNode>(N0.getOperand(1))->getVT();
1768  unsigned ExtSrcTyBits = ExtSrcTy.getSizeInBits();
1769  EVT ExtDstTy = N0.getValueType();
1770  unsigned ExtDstTyBits = ExtDstTy.getSizeInBits();
1771 
1772  // If the constant doesn't fit into the number of bits for the source of
1773  // the sign extension, it is impossible for both sides to be equal.
1774  if (C1.getMinSignedBits() > ExtSrcTyBits)
1775  return DAG.getConstant(Cond == ISD::SETNE, dl, VT);
1776 
1777  SDValue ZextOp;
1778  EVT Op0Ty = N0.getOperand(0).getValueType();
1779  if (Op0Ty == ExtSrcTy) {
1780  ZextOp = N0.getOperand(0);
1781  } else {
1782  APInt Imm = APInt::getLowBitsSet(ExtDstTyBits, ExtSrcTyBits);
1783  ZextOp = DAG.getNode(ISD::AND, dl, Op0Ty, N0.getOperand(0),
1784  DAG.getConstant(Imm, dl, Op0Ty));
1785  }
1786  if (!DCI.isCalledByLegalizer())
1787  DCI.AddToWorklist(ZextOp.getNode());
1788  // Otherwise, make this a use of a zext.
1789  return DAG.getSetCC(dl, VT, ZextOp,
1791  ExtDstTyBits,
1792  ExtSrcTyBits),
1793  dl, ExtDstTy),
1794  Cond);
1795  } else if ((N1C->isNullValue() || N1C->isOne()) &&
1796  (Cond == ISD::SETEQ || Cond == ISD::SETNE)) {
1797  // SETCC (SETCC), [0|1], [EQ|NE] -> SETCC
1798  if (N0.getOpcode() == ISD::SETCC &&
1799  isTypeLegal(VT) && VT.bitsLE(N0.getValueType())) {
1800  bool TrueWhenTrue = (Cond == ISD::SETEQ) ^ (!N1C->isOne());
1801  if (TrueWhenTrue)
1802  return DAG.getNode(ISD::TRUNCATE, dl, VT, N0);
1803  // Invert the condition.
1804  ISD::CondCode CC = cast<CondCodeSDNode>(N0.getOperand(2))->get();
1805  CC = ISD::getSetCCInverse(CC,
1806  N0.getOperand(0).getValueType().isInteger());
1807  if (DCI.isBeforeLegalizeOps() ||
1808  isCondCodeLegal(CC, N0.getOperand(0).getSimpleValueType()))
1809  return DAG.getSetCC(dl, VT, N0.getOperand(0), N0.getOperand(1), CC);
1810  }
1811 
1812  if ((N0.getOpcode() == ISD::XOR ||
1813  (N0.getOpcode() == ISD::AND &&
1814  N0.getOperand(0).getOpcode() == ISD::XOR &&
1815  N0.getOperand(1) == N0.getOperand(0).getOperand(1))) &&
1816  isa<ConstantSDNode>(N0.getOperand(1)) &&
1817  cast<ConstantSDNode>(N0.getOperand(1))->isOne()) {
1818  // If this is (X^1) == 0/1, swap the RHS and eliminate the xor. We
1819  // can only do this if the top bits are known zero.
1820  unsigned BitWidth = N0.getValueSizeInBits();
1821  if (DAG.MaskedValueIsZero(N0,
1822  APInt::getHighBitsSet(BitWidth,
1823  BitWidth-1))) {
1824  // Okay, get the un-inverted input value.
1825  SDValue Val;
1826  if (N0.getOpcode() == ISD::XOR) {
1827  Val = N0.getOperand(0);
1828  } else {
1829  assert(N0.getOpcode() == ISD::AND &&
1830  N0.getOperand(0).getOpcode() == ISD::XOR);
1831  // ((X^1)&1)^1 -> X & 1
1832  Val = DAG.getNode(ISD::AND, dl, N0.getValueType(),
1833  N0.getOperand(0).getOperand(0),
1834  N0.getOperand(1));
1835  }
1836 
1837  return DAG.getSetCC(dl, VT, Val, N1,
1838  Cond == ISD::SETEQ ? ISD::SETNE : ISD::SETEQ);
1839  }
1840  } else if (N1C->isOne() &&
1841  (VT == MVT::i1 ||
1842  getBooleanContents(N0->getValueType(0)) ==
1844  SDValue Op0 = N0;
1845  if (Op0.getOpcode() == ISD::TRUNCATE)
1846  Op0 = Op0.getOperand(0);
1847 
1848  if ((Op0.getOpcode() == ISD::XOR) &&
1849  Op0.getOperand(0).getOpcode() == ISD::SETCC &&
1850  Op0.getOperand(1).getOpcode() == ISD::SETCC) {
1851  // (xor (setcc), (setcc)) == / != 1 -> (setcc) != / == (setcc)
1852  Cond = (Cond == ISD::SETEQ) ? ISD::SETNE : ISD::SETEQ;
1853  return DAG.getSetCC(dl, VT, Op0.getOperand(0), Op0.getOperand(1),
1854  Cond);
1855  }
1856  if (Op0.getOpcode() == ISD::AND &&
1857  isa<ConstantSDNode>(Op0.getOperand(1)) &&
1858  cast<ConstantSDNode>(Op0.getOperand(1))->isOne()) {
1859  // If this is (X&1) == / != 1, normalize it to (X&1) != / == 0.
1860  if (Op0.getValueType().bitsGT(VT))
1861  Op0 = DAG.getNode(ISD::AND, dl, VT,
1862  DAG.getNode(ISD::TRUNCATE, dl, VT, Op0.getOperand(0)),
1863  DAG.getConstant(1, dl, VT));
1864  else if (Op0.getValueType().bitsLT(VT))
1865  Op0 = DAG.getNode(ISD::AND, dl, VT,
1866  DAG.getNode(ISD::ANY_EXTEND, dl, VT, Op0.getOperand(0)),
1867  DAG.getConstant(1, dl, VT));
1868 
1869  return DAG.getSetCC(dl, VT, Op0,
1870  DAG.getConstant(0, dl, Op0.getValueType()),
1871  Cond == ISD::SETEQ ? ISD::SETNE : ISD::SETEQ);
1872  }
1873  if (Op0.getOpcode() == ISD::AssertZext &&
1874  cast<VTSDNode>(Op0.getOperand(1))->getVT() == MVT::i1)
1875  return DAG.getSetCC(dl, VT, Op0,
1876  DAG.getConstant(0, dl, Op0.getValueType()),
1877  Cond == ISD::SETEQ ? ISD::SETNE : ISD::SETEQ);
1878  }
1879  }
1880 
1881  APInt MinVal, MaxVal;
1882  unsigned OperandBitSize = N1C->getValueType(0).getSizeInBits();
1883  if (ISD::isSignedIntSetCC(Cond)) {
1884  MinVal = APInt::getSignedMinValue(OperandBitSize);
1885  MaxVal = APInt::getSignedMaxValue(OperandBitSize);
1886  } else {
1887  MinVal = APInt::getMinValue(OperandBitSize);
1888  MaxVal = APInt::getMaxValue(OperandBitSize);
1889  }
1890 
1891  // Canonicalize GE/LE comparisons to use GT/LT comparisons.
1892  if (Cond == ISD::SETGE || Cond == ISD::SETUGE) {
1893  // X >= MIN --> true
1894  if (C1 == MinVal)
1895  return DAG.getConstant(1, dl, VT);
1896 
1897  // X >= C0 --> X > (C0 - 1)
1898  APInt C = C1 - 1;
1899  ISD::CondCode NewCC = (Cond == ISD::SETGE) ? ISD::SETGT : ISD::SETUGT;
1900  if ((DCI.isBeforeLegalizeOps() ||
1901  isCondCodeLegal(NewCC, VT.getSimpleVT())) &&
1902  (!N1C->isOpaque() || (N1C->isOpaque() && C.getBitWidth() <= 64 &&
1904  return DAG.getSetCC(dl, VT, N0,
1905  DAG.getConstant(C, dl, N1.getValueType()),
1906  NewCC);
1907  }
1908  }
1909 
1910  if (Cond == ISD::SETLE || Cond == ISD::SETULE) {
1911  // X <= MAX --> true
1912  if (C1 == MaxVal)
1913  return DAG.getConstant(1, dl, VT);
1914 
1915  // X <= C0 --> X < (C0 + 1)
1916  APInt C = C1 + 1;
1917  ISD::CondCode NewCC = (Cond == ISD::SETLE) ? ISD::SETLT : ISD::SETULT;
1918  if ((DCI.isBeforeLegalizeOps() ||
1919  isCondCodeLegal(NewCC, VT.getSimpleVT())) &&
1920  (!N1C->isOpaque() || (N1C->isOpaque() && C.getBitWidth() <= 64 &&
1922  return DAG.getSetCC(dl, VT, N0,
1923  DAG.getConstant(C, dl, N1.getValueType()),
1924  NewCC);
1925  }
1926  }
1927 
1928  if ((Cond == ISD::SETLT || Cond == ISD::SETULT) && C1 == MinVal)
1929  return DAG.getConstant(0, dl, VT); // X < MIN --> false
1930  if ((Cond == ISD::SETGE || Cond == ISD::SETUGE) && C1 == MinVal)
1931  return DAG.getConstant(1, dl, VT); // X >= MIN --> true
1932  if ((Cond == ISD::SETGT || Cond == ISD::SETUGT) && C1 == MaxVal)
1933  return DAG.getConstant(0, dl, VT); // X > MAX --> false
1934  if ((Cond == ISD::SETLE || Cond == ISD::SETULE) && C1 == MaxVal)
1935  return DAG.getConstant(1, dl, VT); // X <= MAX --> true
1936 
1937  // Canonicalize setgt X, Min --> setne X, Min
1938  if ((Cond == ISD::SETGT || Cond == ISD::SETUGT) && C1 == MinVal)
1939  return DAG.getSetCC(dl, VT, N0, N1, ISD::SETNE);
1940  // Canonicalize setlt X, Max --> setne X, Max
1941  if ((Cond == ISD::SETLT || Cond == ISD::SETULT) && C1 == MaxVal)
1942  return DAG.getSetCC(dl, VT, N0, N1, ISD::SETNE);
1943 
1944  // If we have setult X, 1, turn it into seteq X, 0
1945  if ((Cond == ISD::SETLT || Cond == ISD::SETULT) && C1 == MinVal+1)
1946  return DAG.getSetCC(dl, VT, N0,
1947  DAG.getConstant(MinVal, dl, N0.getValueType()),
1948  ISD::SETEQ);
1949  // If we have setugt X, Max-1, turn it into seteq X, Max
1950  if ((Cond == ISD::SETGT || Cond == ISD::SETUGT) && C1 == MaxVal-1)
1951  return DAG.getSetCC(dl, VT, N0,
1952  DAG.getConstant(MaxVal, dl, N0.getValueType()),
1953  ISD::SETEQ);
1954 
1955  // If we have "setcc X, C0", check to see if we can shrink the immediate
1956  // by changing cc.
1957 
1958  // SETUGT X, SINTMAX -> SETLT X, 0
1959  if (Cond == ISD::SETUGT &&
1960  C1 == APInt::getSignedMaxValue(OperandBitSize))
1961  return DAG.getSetCC(dl, VT, N0,
1962  DAG.getConstant(0, dl, N1.getValueType()),
1963  ISD::SETLT);
1964 
1965  // SETULT X, SINTMIN -> SETGT X, -1
1966  if (Cond == ISD::SETULT &&
1967  C1 == APInt::getSignedMinValue(OperandBitSize)) {
1968  SDValue ConstMinusOne =
1969  DAG.getConstant(APInt::getAllOnesValue(OperandBitSize), dl,
1970  N1.getValueType());
1971  return DAG.getSetCC(dl, VT, N0, ConstMinusOne, ISD::SETGT);
1972  }
1973 
1974  // Fold bit comparisons when we can.
1975  if ((Cond == ISD::SETEQ || Cond == ISD::SETNE) &&
1976  (VT == N0.getValueType() ||
1977  (isTypeLegal(VT) && VT.bitsLE(N0.getValueType()))) &&
1978  N0.getOpcode() == ISD::AND) {
1979  auto &DL = DAG.getDataLayout();
1980  if (auto *AndRHS = dyn_cast<ConstantSDNode>(N0.getOperand(1))) {
1981  EVT ShiftTy = DCI.isBeforeLegalize()
1982  ? getPointerTy(DL)
1983  : getShiftAmountTy(N0.getValueType(), DL);
1984  if (Cond == ISD::SETNE && C1 == 0) {// (X & 8) != 0 --> (X & 8) >> 3
1985  // Perform the xform if the AND RHS is a single bit.
1986  if (AndRHS->getAPIntValue().isPowerOf2()) {
1987  return DAG.getNode(ISD::TRUNCATE, dl, VT,
1988  DAG.getNode(ISD::SRL, dl, N0.getValueType(), N0,
1989  DAG.getConstant(AndRHS->getAPIntValue().logBase2(), dl,
1990  ShiftTy)));
1991  }
1992  } else if (Cond == ISD::SETEQ && C1 == AndRHS->getAPIntValue()) {
1993  // (X & 8) == 8 --> (X & 8) >> 3
1994  // Perform the xform if C1 is a single bit.
1995  if (C1.isPowerOf2()) {
1996  return DAG.getNode(ISD::TRUNCATE, dl, VT,
1997  DAG.getNode(ISD::SRL, dl, N0.getValueType(), N0,
1998  DAG.getConstant(C1.logBase2(), dl,
1999  ShiftTy)));
2000  }
2001  }
2002  }
2003  }
2004 
2005  if (C1.getMinSignedBits() <= 64 &&
2006  !isLegalICmpImmediate(C1.getSExtValue())) {
2007  // (X & -256) == 256 -> (X >> 8) == 1
2008  if ((Cond == ISD::SETEQ || Cond == ISD::SETNE) &&
2009  N0.getOpcode() == ISD::AND && N0.hasOneUse()) {
2010  if (auto *AndRHS = dyn_cast<ConstantSDNode>(N0.getOperand(1))) {
2011  const APInt &AndRHSC = AndRHS->getAPIntValue();
2012  if ((-AndRHSC).isPowerOf2() && (AndRHSC & C1) == C1) {
2013  unsigned ShiftBits = AndRHSC.countTrailingZeros();
2014  auto &DL = DAG.getDataLayout();
2015  EVT ShiftTy = DCI.isBeforeLegalize()
2016  ? getPointerTy(DL)
2017  : getShiftAmountTy(N0.getValueType(), DL);
2018  EVT CmpTy = N0.getValueType();
2019  SDValue Shift = DAG.getNode(ISD::SRL, dl, CmpTy, N0.getOperand(0),
2020  DAG.getConstant(ShiftBits, dl,
2021  ShiftTy));
2022  SDValue CmpRHS = DAG.getConstant(C1.lshr(ShiftBits), dl, CmpTy);
2023  return DAG.getSetCC(dl, VT, Shift, CmpRHS, Cond);
2024  }
2025  }
2026  } else if (Cond == ISD::SETULT || Cond == ISD::SETUGE ||
2027  Cond == ISD::SETULE || Cond == ISD::SETUGT) {
2028  bool AdjOne = (Cond == ISD::SETULE || Cond == ISD::SETUGT);
2029  // X < 0x100000000 -> (X >> 32) < 1
2030  // X >= 0x100000000 -> (X >> 32) >= 1
2031  // X <= 0x0ffffffff -> (X >> 32) < 1
2032  // X > 0x0ffffffff -> (X >> 32) >= 1
2033  unsigned ShiftBits;
2034  APInt NewC = C1;
2035  ISD::CondCode NewCond = Cond;
2036  if (AdjOne) {
2037  ShiftBits = C1.countTrailingOnes();
2038  NewC = NewC + 1;
2039  NewCond = (Cond == ISD::SETULE) ? ISD::SETULT : ISD::SETUGE;
2040  } else {
2041  ShiftBits = C1.countTrailingZeros();
2042  }
2043  NewC.lshrInPlace(ShiftBits);
2044  if (ShiftBits && NewC.getMinSignedBits() <= 64 &&
2046  auto &DL = DAG.getDataLayout();
2047  EVT ShiftTy = DCI.isBeforeLegalize()
2048  ? getPointerTy(DL)
2049  : getShiftAmountTy(N0.getValueType(), DL);
2050  EVT CmpTy = N0.getValueType();
2051  SDValue Shift = DAG.getNode(ISD::SRL, dl, CmpTy, N0,
2052  DAG.getConstant(ShiftBits, dl, ShiftTy));
2053  SDValue CmpRHS = DAG.getConstant(NewC, dl, CmpTy);
2054  return DAG.getSetCC(dl, VT, Shift, CmpRHS, NewCond);
2055  }
2056  }
2057  }
2058  }
2059 
2060  if (isa<ConstantFPSDNode>(N0.getNode())) {
2061  // Constant fold or commute setcc.
2062  SDValue O = DAG.FoldSetCC(VT, N0, N1, Cond, dl);
2063  if (O.getNode()) return O;
2064  } else if (auto *CFP = dyn_cast<ConstantFPSDNode>(N1.getNode())) {
2065  // If the RHS of an FP comparison is a constant, simplify it away in
2066  // some cases.
2067  if (CFP->getValueAPF().isNaN()) {
2068  // If an operand is known to be a nan, we can fold it.
2069  switch (ISD::getUnorderedFlavor(Cond)) {
2070  default: llvm_unreachable("Unknown flavor!");
2071  case 0: // Known false.
2072  return DAG.getConstant(0, dl, VT);
2073  case 1: // Known true.
2074  return DAG.getConstant(1, dl, VT);
2075  case 2: // Undefined.
2076  return DAG.getUNDEF(VT);
2077  }
2078  }
2079 
2080  // Otherwise, we know the RHS is not a NaN. Simplify the node to drop the
2081  // constant if knowing that the operand is non-nan is enough. We prefer to
2082  // have SETO(x,x) instead of SETO(x, 0.0) because this avoids having to
2083  // materialize 0.0.
2084  if (Cond == ISD::SETO || Cond == ISD::SETUO)
2085  return DAG.getSetCC(dl, VT, N0, N0, Cond);
2086 
2087  // setcc (fneg x), C -> setcc swap(pred) x, -C
2088  if (N0.getOpcode() == ISD::FNEG) {
2090  if (DCI.isBeforeLegalizeOps() ||
2091  isCondCodeLegal(SwapCond, N0.getSimpleValueType())) {
2092  SDValue NegN1 = DAG.getNode(ISD::FNEG, dl, N0.getValueType(), N1);
2093  return DAG.getSetCC(dl, VT, N0.getOperand(0), NegN1, SwapCond);
2094  }
2095  }
2096 
2097  // If the condition is not legal, see if we can find an equivalent one
2098  // which is legal.
2099  if (!isCondCodeLegal(Cond, N0.getSimpleValueType())) {
2100  // If the comparison was an awkward floating-point == or != and one of
2101  // the comparison operands is infinity or negative infinity, convert the
2102  // condition to a less-awkward <= or >=.
2103  if (CFP->getValueAPF().isInfinity()) {
2104  if (CFP->getValueAPF().isNegative()) {
2105  if (Cond == ISD::SETOEQ &&
2107  return DAG.getSetCC(dl, VT, N0, N1, ISD::SETOLE);
2108  if (Cond == ISD::SETUEQ &&
2110  return DAG.getSetCC(dl, VT, N0, N1, ISD::SETULE);
2111  if (Cond == ISD::SETUNE &&
2113  return DAG.getSetCC(dl, VT, N0, N1, ISD::SETUGT);
2114  if (Cond == ISD::SETONE &&
2116  return DAG.getSetCC(dl, VT, N0, N1, ISD::SETOGT);
2117  } else {
2118  if (Cond == ISD::SETOEQ &&
2120  return DAG.getSetCC(dl, VT, N0, N1, ISD::SETOGE);
2121  if (Cond == ISD::SETUEQ &&
2123  return DAG.getSetCC(dl, VT, N0, N1, ISD::SETUGE);
2124  if (Cond == ISD::SETUNE &&
2126  return DAG.getSetCC(dl, VT, N0, N1, ISD::SETULT);
2127  if (Cond == ISD::SETONE &&
2129  return DAG.getSetCC(dl, VT, N0, N1, ISD::SETOLT);
2130  }
2131  }
2132  }
2133  }
2134 
2135  if (N0 == N1) {
2136  // The sext(setcc()) => setcc() optimization relies on the appropriate
2137  // constant being emitted.
2138  uint64_t EqVal = 0;
2139  switch (getBooleanContents(N0.getValueType())) {
2142  EqVal = ISD::isTrueWhenEqual(Cond);
2143  break;
2145  EqVal = ISD::isTrueWhenEqual(Cond) ? -1 : 0;
2146  break;
2147  }
2148 
2149  // We can always fold X == X for integer setcc's.
2150  if (N0.getValueType().isInteger()) {
2151  return DAG.getConstant(EqVal, dl, VT);
2152  }
2153  unsigned UOF = ISD::getUnorderedFlavor(Cond);
2154  if (UOF == 2) // FP operators that are undefined on NaNs.
2155  return DAG.getConstant(EqVal, dl, VT);
2156  if (UOF == unsigned(ISD::isTrueWhenEqual(Cond)))
2157  return DAG.getConstant(EqVal, dl, VT);
2158  // Otherwise, we can't fold it. However, we can simplify it to SETUO/SETO
2159  // if it is not already.
2160  ISD::CondCode NewCond = UOF == 0 ? ISD::SETO : ISD::SETUO;
2161  if (NewCond != Cond && (DCI.isBeforeLegalizeOps() ||
2162  getCondCodeAction(NewCond, N0.getSimpleValueType()) == Legal))
2163  return DAG.getSetCC(dl, VT, N0, N1, NewCond);
2164  }
2165 
2166  if ((Cond == ISD::SETEQ || Cond == ISD::SETNE) &&
2167  N0.getValueType().isInteger()) {
2168  if (N0.getOpcode() == ISD::ADD || N0.getOpcode() == ISD::SUB ||
2169  N0.getOpcode() == ISD::XOR) {
2170  // Simplify (X+Y) == (X+Z) --> Y == Z
2171  if (N0.getOpcode() == N1.getOpcode()) {
2172  if (N0.getOperand(0) == N1.getOperand(0))
2173  return DAG.getSetCC(dl, VT, N0.getOperand(1), N1.getOperand(1), Cond);
2174  if (N0.getOperand(1) == N1.getOperand(1))
2175  return DAG.getSetCC(dl, VT, N0.getOperand(0), N1.getOperand(0), Cond);
2176  if (isCommutativeBinOp(N0.getOpcode())) {
2177  // If X op Y == Y op X, try other combinations.
2178  if (N0.getOperand(0) == N1.getOperand(1))
2179  return DAG.getSetCC(dl, VT, N0.getOperand(1), N1.getOperand(0),
2180  Cond);
2181  if (N0.getOperand(1) == N1.getOperand(0))
2182  return DAG.getSetCC(dl, VT, N0.getOperand(0), N1.getOperand(1),
2183  Cond);
2184  }
2185  }
2186 
2187  // If RHS is a legal immediate value for a compare instruction, we need
2188  // to be careful about increasing register pressure needlessly.
2189  bool LegalRHSImm = false;
2190 
2191  if (auto *RHSC = dyn_cast<ConstantSDNode>(N1)) {
2192  if (auto *LHSR = dyn_cast<ConstantSDNode>(N0.getOperand(1))) {
2193  // Turn (X+C1) == C2 --> X == C2-C1
2194  if (N0.getOpcode() == ISD::ADD && N0.getNode()->hasOneUse()) {
2195  return DAG.getSetCC(dl, VT, N0.getOperand(0),
2196  DAG.getConstant(RHSC->getAPIntValue()-
2197  LHSR->getAPIntValue(),
2198  dl, N0.getValueType()), Cond);
2199  }
2200 
2201  // Turn (X^C1) == C2 into X == C1^C2 iff X&~C1 = 0.
2202  if (N0.getOpcode() == ISD::XOR)
2203  // If we know that all of the inverted bits are zero, don't bother
2204  // performing the inversion.
2205  if (DAG.MaskedValueIsZero(N0.getOperand(0), ~LHSR->getAPIntValue()))
2206  return
2207  DAG.getSetCC(dl, VT, N0.getOperand(0),
2208  DAG.getConstant(LHSR->getAPIntValue() ^
2209  RHSC->getAPIntValue(),
2210  dl, N0.getValueType()),
2211  Cond);
2212  }
2213 
2214  // Turn (C1-X) == C2 --> X == C1-C2
2215  if (auto *SUBC = dyn_cast<ConstantSDNode>(N0.getOperand(0))) {
2216  if (N0.getOpcode() == ISD::SUB && N0.getNode()->hasOneUse()) {
2217  return
2218  DAG.getSetCC(dl, VT, N0.getOperand(1),
2219  DAG.getConstant(SUBC->getAPIntValue() -
2220  RHSC->getAPIntValue(),
2221  dl, N0.getValueType()),
2222  Cond);
2223  }
2224  }
2225 
2226  // Could RHSC fold directly into a compare?
2227  if (RHSC->getValueType(0).getSizeInBits() <= 64)
2228  LegalRHSImm = isLegalICmpImmediate(RHSC->getSExtValue());
2229  }
2230 
2231  // Simplify (X+Z) == X --> Z == 0
2232  // Don't do this if X is an immediate that can fold into a cmp
2233  // instruction and X+Z has other uses. It could be an induction variable
2234  // chain, and the transform would increase register pressure.
2235  if (!LegalRHSImm || N0.getNode()->hasOneUse()) {
2236  if (N0.getOperand(0) == N1)
2237  return DAG.getSetCC(dl, VT, N0.getOperand(1),
2238  DAG.getConstant(0, dl, N0.getValueType()), Cond);
2239  if (N0.getOperand(1) == N1) {
2240  if (isCommutativeBinOp(N0.getOpcode()))
2241  return DAG.getSetCC(dl, VT, N0.getOperand(0),
2242  DAG.getConstant(0, dl, N0.getValueType()),
2243  Cond);
2244  if (N0.getNode()->hasOneUse()) {
2245  assert(N0.getOpcode() == ISD::SUB && "Unexpected operation!");
2246  auto &DL = DAG.getDataLayout();
2247  // (Z-X) == X --> Z == X<<1
2248  SDValue SH = DAG.getNode(
2249  ISD::SHL, dl, N1.getValueType(), N1,
2250  DAG.getConstant(1, dl,
2251  getShiftAmountTy(N1.getValueType(), DL)));
2252  if (!DCI.isCalledByLegalizer())
2253  DCI.AddToWorklist(SH.getNode());
2254  return DAG.getSetCC(dl, VT, N0.getOperand(0), SH, Cond);
2255  }
2256  }
2257  }
2258  }
2259 
2260  if (N1.getOpcode() == ISD::ADD || N1.getOpcode() == ISD::SUB ||
2261  N1.getOpcode() == ISD::XOR) {
2262  // Simplify X == (X+Z) --> Z == 0
2263  if (N1.getOperand(0) == N0)
2264  return DAG.getSetCC(dl, VT, N1.getOperand(1),
2265  DAG.getConstant(0, dl, N1.getValueType()), Cond);
2266  if (N1.getOperand(1) == N0) {
2267  if (isCommutativeBinOp(N1.getOpcode()))
2268  return DAG.getSetCC(dl, VT, N1.getOperand(0),
2269  DAG.getConstant(0, dl, N1.getValueType()), Cond);
2270  if (N1.getNode()->hasOneUse()) {
2271  assert(N1.getOpcode() == ISD::SUB && "Unexpected operation!");
2272  auto &DL = DAG.getDataLayout();
2273  // X == (Z-X) --> X<<1 == Z
2274  SDValue SH = DAG.getNode(
2275  ISD::SHL, dl, N1.getValueType(), N0,
2276  DAG.getConstant(1, dl, getShiftAmountTy(N0.getValueType(), DL)));
2277  if (!DCI.isCalledByLegalizer())
2278  DCI.AddToWorklist(SH.getNode());
2279  return DAG.getSetCC(dl, VT, SH, N1.getOperand(0), Cond);
2280  }
2281  }
2282  }
2283 
2284  if (SDValue V = simplifySetCCWithAnd(VT, N0, N1, Cond, DCI, dl))
2285  return V;
2286  }
2287 
2288  // Fold away ALL boolean setcc's.
2289  SDValue Temp;
2290  if (N0.getValueType() == MVT::i1 && foldBooleans) {
2291  switch (Cond) {
2292  default: llvm_unreachable("Unknown integer setcc!");
2293  case ISD::SETEQ: // X == Y -> ~(X^Y)
2294  Temp = DAG.getNode(ISD::XOR, dl, MVT::i1, N0, N1);
2295  N0 = DAG.getNOT(dl, Temp, MVT::i1);
2296  if (!DCI.isCalledByLegalizer())
2297  DCI.AddToWorklist(Temp.getNode());
2298  break;
2299  case ISD::SETNE: // X != Y --> (X^Y)
2300  N0 = DAG.getNode(ISD::XOR, dl, MVT::i1, N0, N1);
2301  break;
2302  case ISD::SETGT: // X >s Y --> X == 0 & Y == 1 --> ~X & Y
2303  case ISD::SETULT: // X <u Y --> X == 0 & Y == 1 --> ~X & Y
2304  Temp = DAG.getNOT(dl, N0, MVT::i1);
2305  N0 = DAG.getNode(ISD::AND, dl, MVT::i1, N1, Temp);
2306  if (!DCI.isCalledByLegalizer())
2307  DCI.AddToWorklist(Temp.getNode());
2308  break;
2309  case ISD::SETLT: // X <s Y --> X == 1 & Y == 0 --> ~Y & X
2310  case ISD::SETUGT: // X >u Y --> X == 1 & Y == 0 --> ~Y & X
2311  Temp = DAG.getNOT(dl, N1, MVT::i1);
2312  N0 = DAG.getNode(ISD::AND, dl, MVT::i1, N0, Temp);
2313  if (!DCI.isCalledByLegalizer())
2314  DCI.AddToWorklist(Temp.getNode());
2315  break;
2316  case ISD::SETULE: // X <=u Y --> X == 0 | Y == 1 --> ~X | Y
2317  case ISD::SETGE: // X >=s Y --> X == 0 | Y == 1 --> ~X | Y
2318  Temp = DAG.getNOT(dl, N0, MVT::i1);
2319  N0 = DAG.getNode(ISD::OR, dl, MVT::i1, N1, Temp);
2320  if (!DCI.isCalledByLegalizer())
2321  DCI.AddToWorklist(Temp.getNode());
2322  break;
2323  case ISD::SETUGE: // X >=u Y --> X == 1 | Y == 0 --> ~Y | X
2324  case ISD::SETLE: // X <=s Y --> X == 1 | Y == 0 --> ~Y | X
2325  Temp = DAG.getNOT(dl, N1, MVT::i1);
2326  N0 = DAG.getNode(ISD::OR, dl, MVT::i1, N0, Temp);
2327  break;
2328  }
2329  if (VT != MVT::i1) {
2330  if (!DCI.isCalledByLegalizer())
2331  DCI.AddToWorklist(N0.getNode());
2332  // FIXME: If running after legalize, we probably can't do this.
2333  N0 = DAG.getNode(ISD::ZERO_EXTEND, dl, VT, N0);
2334  }
2335  return N0;
2336  }
2337 
2338  // Could not fold it.
2339  return SDValue();
2340 }
2341 
2342 /// Returns true (and the GlobalValue and the offset) if the node is a
2343 /// GlobalAddress + offset.
2345  int64_t &Offset) const {
2346  if (auto *GASD = dyn_cast<GlobalAddressSDNode>(N)) {
2347  GA = GASD->getGlobal();
2348  Offset += GASD->getOffset();
2349  return true;
2350  }
2351 
2352  if (N->getOpcode() == ISD::ADD) {
2353  SDValue N1 = N->getOperand(0);
2354  SDValue N2 = N->getOperand(1);
2355  if (isGAPlusOffset(N1.getNode(), GA, Offset)) {
2356  if (auto *V = dyn_cast<ConstantSDNode>(N2)) {
2357  Offset += V->getSExtValue();
2358  return true;
2359  }
2360  } else if (isGAPlusOffset(N2.getNode(), GA, Offset)) {
2361  if (auto *V = dyn_cast<ConstantSDNode>(N1)) {
2362  Offset += V->getSExtValue();
2363  return true;
2364  }
2365  }
2366  }
2367 
2368  return false;
2369 }
2370 
2372  DAGCombinerInfo &DCI) const {
2373  // Default implementation: no optimization.
2374  return SDValue();
2375 }
2376 
2377 //===----------------------------------------------------------------------===//
2378 // Inline Assembler Implementation Methods
2379 //===----------------------------------------------------------------------===//
2380 
2383  unsigned S = Constraint.size();
2384 
2385  if (S == 1) {
2386  switch (Constraint[0]) {
2387  default: break;
2388  case 'r': return C_RegisterClass;
2389  case 'm': // memory
2390  case 'o': // offsetable
2391  case 'V': // not offsetable
2392  return C_Memory;
2393  case 'i': // Simple Integer or Relocatable Constant
2394  case 'n': // Simple Integer
2395  case 'E': // Floating Point Constant
2396  case 'F': // Floating Point Constant
2397  case 's': // Relocatable Constant
2398  case 'p': // Address.
2399  case 'X': // Allow ANY value.
2400  case 'I': // Target registers.
2401  case 'J':
2402  case 'K':
2403  case 'L':
2404  case 'M':
2405  case 'N':
2406  case 'O':
2407  case 'P':
2408  case '<':
2409  case '>':
2410  return C_Other;
2411  }
2412  }
2413 
2414  if (S > 1 && Constraint[0] == '{' && Constraint[S-1] == '}') {
2415  if (S == 8 && Constraint.substr(1, 6) == "memory") // "{memory}"
2416  return C_Memory;
2417  return C_Register;
2418  }
2419  return C_Unknown;
2420 }
2421 
2422 /// Try to replace an X constraint, which matches anything, with another that
2423 /// has more specific requirements based on the type of the corresponding
2424 /// operand.
2425 const char *TargetLowering::LowerXConstraint(EVT ConstraintVT) const{
2426  if (ConstraintVT.isInteger())
2427  return "r";
2428  if (ConstraintVT.isFloatingPoint())
2429  return "f"; // works for many targets
2430  return nullptr;
2431 }
2432 
2433 /// Lower the specified operand into the Ops vector.
2434 /// If it is invalid, don't add anything to Ops.
2436  std::string &Constraint,
2437  std::vector<SDValue> &Ops,
2438  SelectionDAG &DAG) const {
2439 
2440  if (Constraint.length() > 1) return;
2441 
2442  char ConstraintLetter = Constraint[0];
2443  switch (ConstraintLetter) {
2444  default: break;
2445  case 'X': // Allows any operand; labels (basic block) use this.
2446  if (Op.getOpcode() == ISD::BasicBlock) {
2447  Ops.push_back(Op);
2448  return;
2449  }
2451  case 'i': // Simple Integer or Relocatable Constant
2452  case 'n': // Simple Integer
2453  case 's': { // Relocatable Constant
2454  // These operands are interested in values of the form (GV+C), where C may
2455  // be folded in as an offset of GV, or it may be explicitly added. Also, it
2456  // is possible and fine if either GV or C are missing.
2459 
2460  // If we have "(add GV, C)", pull out GV/C
2461  if (Op.getOpcode() == ISD::ADD) {
2462  C = dyn_cast<ConstantSDNode>(Op.getOperand(1));
2464  if (!C || !GA) {
2465  C = dyn_cast<ConstantSDNode>(Op.getOperand(0));
2467  }
2468  if (!C || !GA) {
2469  C = nullptr;
2470  GA = nullptr;
2471  }
2472  }
2473 
2474  // If we find a valid operand, map to the TargetXXX version so that the
2475  // value itself doesn't get selected.
2476  if (GA) { // Either &GV or &GV+C
2477  if (ConstraintLetter != 'n') {
2478  int64_t Offs = GA->getOffset();
2479  if (C) Offs += C->getZExtValue();
2480  Ops.push_back(DAG.getTargetGlobalAddress(GA->getGlobal(),
2481  C ? SDLoc(C) : SDLoc(),
2482  Op.getValueType(), Offs));
2483  }
2484  return;
2485  }
2486  if (C) { // just C, no GV.
2487  // Simple constants are not allowed for 's'.
2488  if (ConstraintLetter != 's') {
2489  // gcc prints these as sign extended. Sign extend value to 64 bits
2490  // now; without this it would get ZExt'd later in
2491  // ScheduleDAGSDNodes::EmitNode, which is very generic.
2492  Ops.push_back(DAG.getTargetConstant(C->getSExtValue(),
2493  SDLoc(C), MVT::i64));
2494  }
2495  return;
2496  }
2497  break;
2498  }
2499  }
2500 }
2501 
2502 std::pair<unsigned, const TargetRegisterClass *>
2504  StringRef Constraint,
2505  MVT VT) const {
2506  if (Constraint.empty() || Constraint[0] != '{')
2507  return std::make_pair(0u, static_cast<TargetRegisterClass*>(nullptr));
2508  assert(*(Constraint.end()-1) == '}' && "Not a brace enclosed constraint?");
2509 
2510  // Remove the braces from around the name.
2511  StringRef RegName(Constraint.data()+1, Constraint.size()-2);
2512 
2513  std::pair<unsigned, const TargetRegisterClass*> R =
2514  std::make_pair(0u, static_cast<const TargetRegisterClass*>(nullptr));
2515 
2516  // Figure out which register class contains this reg.
2517  for (const TargetRegisterClass *RC : RI->regclasses()) {
2518  // If none of the value types for this register class are valid, we
2519  // can't use it. For example, 64-bit reg classes on 32-bit targets.
2520  if (!isLegalRC(*RI, *RC))
2521  continue;
2522 
2523  for (TargetRegisterClass::iterator I = RC->begin(), E = RC->end();
2524  I != E; ++I) {
2525  if (RegName.equals_lower(RI->getRegAsmName(*I))) {
2526  std::pair<unsigned, const TargetRegisterClass*> S =
2527  std::make_pair(*I, RC);
2528 
2529  // If this register class has the requested value type, return it,
2530  // otherwise keep searching and return the first class found
2531  // if no other is found which explicitly has the requested type.
2532  if (RI->isTypeLegalForClass(*RC, VT))
2533  return S;
2534  if (!R.second)
2535  R = S;
2536  }
2537  }
2538  }
2539 
2540  return R;
2541 }
2542 
2543 //===----------------------------------------------------------------------===//
2544 // Constraint Selection.
2545 
2546 /// Return true of this is an input operand that is a matching constraint like
2547 /// "4".
2549  assert(!ConstraintCode.empty() && "No known constraint!");
2550  return isdigit(static_cast<unsigned char>(ConstraintCode[0]));
2551 }
2552 
2553 /// If this is an input matching constraint, this method returns the output
2554 /// operand it matches.
2556  assert(!ConstraintCode.empty() && "No known constraint!");
2557  return atoi(ConstraintCode.c_str());
2558 }
2559 
2560 /// Split up the constraint string from the inline assembly value into the
2561 /// specific constraints and their prefixes, and also tie in the associated
2562 /// operand values.
2563 /// If this returns an empty vector, and if the constraint string itself
2564 /// isn't empty, there was an error parsing.
2567  const TargetRegisterInfo *TRI,
2568  ImmutableCallSite CS) const {
2569  /// Information about all of the constraints.
2570  AsmOperandInfoVector ConstraintOperands;
2571  const InlineAsm *IA = cast<InlineAsm>(CS.getCalledValue());
2572  unsigned maCount = 0; // Largest number of multiple alternative constraints.
2573 
2574  // Do a prepass over the constraints, canonicalizing them, and building up the
2575  // ConstraintOperands list.
2576  unsigned ArgNo = 0; // ArgNo - The argument of the CallInst.
2577  unsigned ResNo = 0; // ResNo - The result number of the next output.
2578 
2579  for (InlineAsm::ConstraintInfo &CI : IA->ParseConstraints()) {
2580  ConstraintOperands.emplace_back(std::move(CI));
2581  AsmOperandInfo &OpInfo = ConstraintOperands.back();
2582 
2583  // Update multiple alternative constraint count.
2584  if (OpInfo.multipleAlternatives.size() > maCount)
2585  maCount = OpInfo.multipleAlternatives.size();
2586 
2587  OpInfo.ConstraintVT = MVT::Other;
2588 
2589  // Compute the value type for each operand.
2590  switch (OpInfo.Type) {
2591  case InlineAsm::isOutput:
2592  // Indirect outputs just consume an argument.
2593  if (OpInfo.isIndirect) {
2594  OpInfo.CallOperandVal = const_cast<Value *>(CS.getArgument(ArgNo++));
2595  break;
2596  }
2597 
2598  // The return value of the call is this value. As such, there is no
2599  // corresponding argument.
2600  assert(!CS.getType()->isVoidTy() &&
2601  "Bad inline asm!");
2602  if (StructType *STy = dyn_cast<StructType>(CS.getType())) {
2603  OpInfo.ConstraintVT =
2604  getSimpleValueType(DL, STy->getElementType(ResNo));
2605  } else {
2606  assert(ResNo == 0 && "Asm only has one result!");
2607  OpInfo.ConstraintVT = getSimpleValueType(DL, CS.getType());
2608  }
2609  ++ResNo;
2610  break;
2611  case InlineAsm::isInput:
2612  OpInfo.CallOperandVal = const_cast<Value *>(CS.getArgument(ArgNo++));
2613  break;
2614  case InlineAsm::isClobber:
2615  // Nothing to do.
2616  break;
2617  }
2618 
2619  if (OpInfo.CallOperandVal) {
2620  llvm::Type *OpTy = OpInfo.CallOperandVal->getType();
2621  if (OpInfo.isIndirect) {
2622  llvm::PointerType *PtrTy = dyn_cast<PointerType>(OpTy);
2623  if (!PtrTy)
2624  report_fatal_error("Indirect operand for inline asm not a pointer!");
2625  OpTy = PtrTy->getElementType();
2626  }
2627 
2628  // Look for vector wrapped in a struct. e.g. { <16 x i8> }.
2629  if (StructType *STy = dyn_cast<StructType>(OpTy))
2630  if (STy->getNumElements() == 1)
2631  OpTy = STy->getElementType(0);
2632 
2633  // If OpTy is not a single value, it may be a struct/union that we
2634  // can tile with integers.
2635  if (!OpTy->isSingleValueType() && OpTy->isSized()) {
2636  unsigned BitSize = DL.getTypeSizeInBits(OpTy);
2637  switch (BitSize) {
2638  default: break;
2639  case 1:
2640  case 8:
2641  case 16:
2642  case 32:
2643  case 64:
2644  case 128:
2645  OpInfo.ConstraintVT =
2646  MVT::getVT(IntegerType::get(OpTy->getContext(), BitSize), true);
2647  break;
2648  }
2649  } else if (PointerType *PT = dyn_cast<PointerType>(OpTy)) {
2650  unsigned PtrSize = DL.getPointerSizeInBits(PT->getAddressSpace());
2651  OpInfo.ConstraintVT = MVT::getIntegerVT(PtrSize);
2652  } else {
2653  OpInfo.ConstraintVT = MVT::getVT(OpTy, true);
2654  }
2655  }
2656  }
2657 
2658  // If we have multiple alternative constraints, select the best alternative.
2659  if (!ConstraintOperands.empty()) {
2660  if (maCount) {
2661  unsigned bestMAIndex = 0;
2662  int bestWeight = -1;
2663  // weight: -1 = invalid match, and 0 = so-so match to 5 = good match.
2664  int weight = -1;
2665  unsigned maIndex;
2666  // Compute the sums of the weights for each alternative, keeping track
2667  // of the best (highest weight) one so far.
2668  for (maIndex = 0; maIndex < maCount; ++maIndex) {
2669  int weightSum = 0;
2670  for (unsigned cIndex = 0, eIndex = ConstraintOperands.size();
2671  cIndex != eIndex; ++cIndex) {
2672  AsmOperandInfo& OpInfo = ConstraintOperands[cIndex];
2673  if (OpInfo.Type == InlineAsm::isClobber)
2674  continue;
2675 
2676  // If this is an output operand with a matching input operand,
2677  // look up the matching input. If their types mismatch, e.g. one
2678  // is an integer, the other is floating point, or their sizes are
2679  // different, flag it as an maCantMatch.
2680  if (OpInfo.hasMatchingInput()) {
2681  AsmOperandInfo &Input = ConstraintOperands[OpInfo.MatchingInput];
2682  if (OpInfo.ConstraintVT != Input.ConstraintVT) {
2683  if ((OpInfo.ConstraintVT.isInteger() !=
2684  Input.ConstraintVT.isInteger()) ||
2685  (OpInfo.ConstraintVT.getSizeInBits() !=
2686  Input.ConstraintVT.getSizeInBits())) {
2687  weightSum = -1; // Can't match.
2688  break;
2689  }
2690  }
2691  }
2692  weight = getMultipleConstraintMatchWeight(OpInfo, maIndex);
2693  if (weight == -1) {
2694  weightSum = -1;
2695  break;
2696  }
2697  weightSum += weight;
2698  }
2699  // Update best.
2700  if (weightSum > bestWeight) {
2701  bestWeight = weightSum;
2702  bestMAIndex = maIndex;
2703  }
2704  }
2705 
2706  // Now select chosen alternative in each constraint.
2707  for (unsigned cIndex = 0, eIndex = ConstraintOperands.size();
2708  cIndex != eIndex; ++cIndex) {
2709  AsmOperandInfo& cInfo = ConstraintOperands[cIndex];
2710  if (cInfo.Type == InlineAsm::isClobber)
2711  continue;
2712  cInfo.selectAlternative(bestMAIndex);
2713  }
2714  }
2715  }
2716 
2717  // Check and hook up tied operands, choose constraint code to use.
2718  for (unsigned cIndex = 0, eIndex = ConstraintOperands.size();
2719  cIndex != eIndex; ++cIndex) {
2720  AsmOperandInfo& OpInfo = ConstraintOperands[cIndex];
2721 
2722  // If this is an output operand with a matching input operand, look up the
2723  // matching input. If their types mismatch, e.g. one is an integer, the
2724  // other is floating point, or their sizes are different, flag it as an
2725  // error.
2726  if (OpInfo.hasMatchingInput()) {
2727  AsmOperandInfo &Input = ConstraintOperands[OpInfo.MatchingInput];
2728 
2729  if (OpInfo.ConstraintVT != Input.ConstraintVT) {
2730  std::pair<unsigned, const TargetRegisterClass *> MatchRC =
2732  OpInfo.ConstraintVT);
2733  std::pair<unsigned, const TargetRegisterClass *> InputRC =
2735  Input.ConstraintVT);
2736  if ((OpInfo.ConstraintVT.isInteger() !=
2737  Input.ConstraintVT.isInteger()) ||
2738  (MatchRC.second != InputRC.second)) {
2739  report_fatal_error("Unsupported asm: input constraint"
2740  " with a matching output constraint of"
2741  " incompatible type!");
2742  }
2743  }
2744  }
2745  }
2746 
2747  return ConstraintOperands;
2748 }
2749 
2750 /// Return an integer indicating how general CT is.
2752  switch (CT) {
2755  return 0;
2757  return 1;
2759  return 2;
2761  return 3;
2762  }
2763  llvm_unreachable("Invalid constraint type");
2764 }
2765 
2766 /// Examine constraint type and operand type and determine a weight value.
2767 /// This object must already have been set up with the operand type
2768 /// and the current alternative constraint selected.
2771  AsmOperandInfo &info, int maIndex) const {
2773  if (maIndex >= (int)info.multipleAlternatives.size())
2774  rCodes = &info.Codes;
2775  else
2776  rCodes = &info.multipleAlternatives[maIndex].Codes;
2777  ConstraintWeight BestWeight = CW_Invalid;
2778 
2779  // Loop over the options, keeping track of the most general one.
2780  for (unsigned i = 0, e = rCodes->size(); i != e; ++i) {
2781  ConstraintWeight weight =
2782  getSingleConstraintMatchWeight(info, (*rCodes)[i].c_str());
2783  if (weight > BestWeight)
2784  BestWeight = weight;
2785  }
2786 
2787  return BestWeight;
2788 }
2789 
2790 /// Examine constraint type and operand type and determine a weight value.
2791 /// This object must already have been set up with the operand type
2792 /// and the current alternative constraint selected.
2795  AsmOperandInfo &info, const char *constraint) const {
2796  ConstraintWeight weight = CW_Invalid;
2797  Value *CallOperandVal = info.CallOperandVal;
2798  // If we don't have a value, we can't do a match,
2799  // but allow it at the lowest weight.
2800  if (!CallOperandVal)
2801  return CW_Default;
2802  // Look at the constraint type.
2803  switch (*constraint) {
2804  case 'i': // immediate integer.
2805  case 'n': // immediate integer with a known value.
2806  if (isa<ConstantInt>(CallOperandVal))
2807  weight = CW_Constant;
2808  break;
2809  case 's': // non-explicit intregal immediate.
2810  if (isa<GlobalValue>(CallOperandVal))
2811  weight = CW_Constant;
2812  break;
2813  case 'E': // immediate float if host format.
2814  case 'F': // immediate float.
2815  if (isa<ConstantFP>(CallOperandVal))
2816  weight = CW_Constant;
2817  break;
2818  case '<': // memory operand with autodecrement.
2819  case '>': // memory operand with autoincrement.
2820  case 'm': // memory operand.
2821  case 'o': // offsettable memory operand
2822  case 'V': // non-offsettable memory operand
2823  weight = CW_Memory;
2824  break;
2825  case 'r': // general register.
2826  case 'g': // general register, memory operand or immediate integer.
2827  // note: Clang converts "g" to "imr".
2828  if (CallOperandVal->getType()->isIntegerTy())
2829  weight = CW_Register;
2830  break;
2831  case 'X': // any operand.
2832  default:
2833  weight = CW_Default;
2834  break;
2835  }
2836  return weight;
2837 }
2838 
2839 /// If there are multiple different constraints that we could pick for this
2840 /// operand (e.g. "imr") try to pick the 'best' one.
2841 /// This is somewhat tricky: constraints fall into four classes:
2842 /// Other -> immediates and magic values
2843 /// Register -> one specific register
2844 /// RegisterClass -> a group of regs
2845 /// Memory -> memory
2846 /// Ideally, we would pick the most specific constraint possible: if we have
2847 /// something that fits into a register, we would pick it. The problem here
2848 /// is that if we have something that could either be in a register or in
2849 /// memory that use of the register could cause selection of *other*
2850 /// operands to fail: they might only succeed if we pick memory. Because of
2851 /// this the heuristic we use is:
2852 ///
2853 /// 1) If there is an 'other' constraint, and if the operand is valid for
2854 /// that constraint, use it. This makes us take advantage of 'i'
2855 /// constraints when available.
2856 /// 2) Otherwise, pick the most general constraint present. This prefers
2857 /// 'm' over 'r', for example.
2858 ///
2860  const TargetLowering &TLI,
2861  SDValue Op, SelectionDAG *DAG) {
2862  assert(OpInfo.Codes.size() > 1 && "Doesn't have multiple constraint options");
2863  unsigned BestIdx = 0;
2865  int BestGenerality = -1;
2866 
2867  // Loop over the options, keeping track of the most general one.
2868  for (unsigned i = 0, e = OpInfo.Codes.size(); i != e; ++i) {
2870  TLI.getConstraintType(OpInfo.Codes[i]);
2871 
2872  // If this is an 'other' constraint, see if the operand is valid for it.
2873  // For example, on X86 we might have an 'rI' constraint. If the operand
2874  // is an integer in the range [0..31] we want to use I (saving a load
2875  // of a register), otherwise we must use 'r'.
2876  if (CType == TargetLowering::C_Other && Op.getNode()) {
2877  assert(OpInfo.Codes[i].size() == 1 &&
2878  "Unhandled multi-letter 'other' constraint");
2879  std::vector<SDValue> ResultOps;
2880  TLI.LowerAsmOperandForConstraint(Op, OpInfo.Codes[i],
2881  ResultOps, *DAG);
2882  if (!ResultOps.empty()) {
2883  BestType = CType;
2884  BestIdx = i;
2885  break;
2886  }
2887  }
2888 
2889  // Things with matching constraints can only be registers, per gcc
2890  // documentation. This mainly affects "g" constraints.
2891  if (CType == TargetLowering::C_Memory && OpInfo.hasMatchingInput())
2892  continue;
2893 
2894  // This constraint letter is more general than the previous one, use it.
2895  int Generality = getConstraintGenerality(CType);
2896  if (Generality > BestGenerality) {
2897  BestType = CType;
2898  BestIdx = i;
2899  BestGenerality = Generality;
2900  }
2901  }
2902 
2903  OpInfo.ConstraintCode = OpInfo.Codes[BestIdx];
2904  OpInfo.ConstraintType = BestType;
2905 }
2906 
2907 /// Determines the constraint code and constraint type to use for the specific
2908 /// AsmOperandInfo, setting OpInfo.ConstraintCode and OpInfo.ConstraintType.
2910  SDValue Op,
2911  SelectionDAG *DAG) const {
2912  assert(!OpInfo.Codes.empty() && "Must have at least one constraint");
2913 
2914  // Single-letter constraints ('r') are very common.
2915  if (OpInfo.Codes.size() == 1) {
2916  OpInfo.ConstraintCode = OpInfo.Codes[0];
2918  } else {
2919  ChooseConstraint(OpInfo, *this, Op, DAG);
2920  }
2921 
2922  // 'X' matches anything.
2923  if (OpInfo.ConstraintCode == "X" && OpInfo.CallOperandVal) {
2924  // Labels and constants are handled elsewhere ('X' is the only thing
2925  // that matches labels). For Functions, the type here is the type of
2926  // the result, which is not what we want to look at; leave them alone.
2927  Value *v = OpInfo.CallOperandVal;
2928  if (isa<BasicBlock>(v) || isa<ConstantInt>(v) || isa<Function>(v)) {
2929  OpInfo.CallOperandVal = v;
2930  return;
2931  }
2932 
2933  // Otherwise, try to resolve it to something we know about by looking at
2934  // the actual operand type.
2935  if (const char *Repl = LowerXConstraint(OpInfo.ConstraintVT)) {
2936  OpInfo.ConstraintCode = Repl;
2938  }
2939  }
2940 }
2941 
2942 /// \brief Given an exact SDIV by a constant, create a multiplication
2943 /// with the multiplicative inverse of the constant.
2945  const SDLoc &dl, SelectionDAG &DAG,
2946  std::vector<SDNode *> &Created) {
2947  assert(d != 0 && "Division by zero!");
2948 
2949  // Shift the value upfront if it is even, so the LSB is one.
2950  unsigned ShAmt = d.countTrailingZeros();
2951  if (ShAmt) {
2952  // TODO: For UDIV use SRL instead of SRA.
2953  SDValue Amt =
2954  DAG.getConstant(ShAmt, dl, TLI.getShiftAmountTy(Op1.getValueType(),
2955  DAG.getDataLayout()));
2957  Flags.setExact(true);
2958  Op1 = DAG.getNode(ISD::SRA, dl, Op1.getValueType(), Op1, Amt, Flags);
2959  Created.push_back(Op1.getNode());
2960  d.ashrInPlace(ShAmt);
2961  }
2962 
2963  // Calculate the multiplicative inverse, using Newton's method.
2964  APInt t, xn = d;
2965  while ((t = d*xn) != 1)
2966  xn *= APInt(d.getBitWidth(), 2) - t;
2967 
2968  SDValue Op2 = DAG.getConstant(xn, dl, Op1.getValueType());
2969  SDValue Mul = DAG.getNode(ISD::MUL, dl, Op1.getValueType(), Op1, Op2);
2970  Created.push_back(Mul.getNode());
2971  return Mul;
2972 }
2973 
2975  SelectionDAG &DAG,
2976  std::vector<SDNode *> *Created) const {
2978  const TargetLowering &TLI = DAG.getTargetLoweringInfo();
2979  if (TLI.isIntDivCheap(N->getValueType(0), Attr))
2980  return SDValue(N,0); // Lower SDIV as SDIV
2981  return SDValue();
2982 }
2983 
2984 /// \brief Given an ISD::SDIV node expressing a divide by constant,
2985 /// return a DAG expression to select that will generate the same value by
2986 /// multiplying by a magic number.
2987 /// Ref: "Hacker's Delight" or "The PowerPC Compiler Writer's Guide".
2989  SelectionDAG &DAG, bool IsAfterLegalization,
2990  std::vector<SDNode *> *Created) const {
2991  assert(Created && "No vector to hold sdiv ops.");
2992 
2993  EVT VT = N->getValueType(0);
2994  SDLoc dl(N);
2995 
2996  // Check to see if we can do this.
2997  // FIXME: We should be more aggressive here.
2998  if (!isTypeLegal(VT))
2999  return SDValue();
3000 
3001  // If the sdiv has an 'exact' bit we can use a simpler lowering.
3002  if (N->getFlags().hasExact())
3003  return BuildExactSDIV(*this, N->getOperand(0), Divisor, dl, DAG, *Created);
3004 
3005  APInt::ms magics = Divisor.magic();
3006 
3007  // Multiply the numerator (operand 0) by the magic value
3008  // FIXME: We should support doing a MUL in a wider type
3009  SDValue Q;
3010  if (IsAfterLegalization ? isOperationLegal(ISD::MULHS, VT) :
3012  Q = DAG.getNode(ISD::MULHS, dl, VT, N->getOperand(0),
3013  DAG.getConstant(magics.m, dl, VT));
3014  else if (IsAfterLegalization ? isOperationLegal(ISD::SMUL_LOHI, VT) :
3016  Q = SDValue(DAG.getNode(ISD::SMUL_LOHI, dl, DAG.getVTList(VT, VT),
3017  N->getOperand(0),
3018  DAG.getConstant(magics.m, dl, VT)).getNode(), 1);
3019  else
3020  return SDValue(); // No mulhs or equvialent
3021  // If d > 0 and m < 0, add the numerator
3022  if (Divisor.isStrictlyPositive() && magics.m.isNegative()) {
3023  Q = DAG.getNode(ISD::ADD, dl, VT, Q, N->getOperand(0));
3024  Created->push_back(Q.getNode());
3025  }
3026  // If d < 0 and m > 0, subtract the numerator.
3027  if (Divisor.isNegative() && magics.m.isStrictlyPositive()) {
3028  Q = DAG.getNode(ISD::SUB, dl, VT, Q, N->getOperand(0));
3029  Created->push_back(Q.getNode());
3030  }
3031  auto &DL = DAG.getDataLayout();
3032  // Shift right algebraic if shift value is nonzero
3033  if (magics.s > 0) {
3034  Q = DAG.getNode(
3035  ISD::SRA, dl, VT, Q,
3036  DAG.getConstant(magics.s, dl, getShiftAmountTy(Q.getValueType(), DL)));
3037  Created->push_back(Q.getNode());
3038  }
3039  // Extract the sign bit and add it to the quotient
3040  SDValue T =
3041  DAG.getNode(ISD::SRL, dl, VT, Q,
3042  DAG.getConstant(VT.getScalarSizeInBits() - 1, dl,
3043  getShiftAmountTy(Q.getValueType(), DL)));
3044  Created->push_back(T.getNode());
3045  return DAG.getNode(ISD::ADD, dl, VT, Q, T);
3046 }
3047 
3048 /// \brief Given an ISD::UDIV node expressing a divide by constant,
3049 /// return a DAG expression to select that will generate the same value by
3050 /// multiplying by a magic number.
3051 /// Ref: "Hacker's Delight" or "The PowerPC Compiler Writer's Guide".
3053  SelectionDAG &DAG, bool IsAfterLegalization,
3054  std::vector<SDNode *> *Created) const {
3055  assert(Created && "No vector to hold udiv ops.");
3056 
3057  EVT VT = N->getValueType(0);
3058  SDLoc dl(N);
3059  auto &DL = DAG.getDataLayout();
3060 
3061  // Check to see if we can do this.
3062  // FIXME: We should be more aggressive here.
3063  if (!isTypeLegal(VT))
3064  return SDValue();
3065 
3066  // FIXME: We should use a narrower constant when the upper
3067  // bits are known to be zero.
3068  APInt::mu magics = Divisor.magicu();
3069 
3070  SDValue Q = N->getOperand(0);
3071 
3072  // If the divisor is even, we can avoid using the expensive fixup by shifting
3073  // the divided value upfront.
3074  if (magics.a != 0 && !Divisor[0]) {
3075  unsigned Shift = Divisor.countTrailingZeros();
3076  Q = DAG.getNode(
3077  ISD::SRL, dl, VT, Q,
3078  DAG.getConstant(Shift, dl, getShiftAmountTy(Q.getValueType(), DL)));
3079  Created->push_back(Q.getNode());
3080 
3081  // Get magic number for the shifted divisor.
3082  magics = Divisor.lshr(Shift).magicu(Shift);
3083  assert(magics.a == 0 && "Should use cheap fixup now");
3084  }
3085 
3086  // Multiply the numerator (operand 0) by the magic value
3087  // FIXME: We should support doing a MUL in a wider type
3088  if (IsAfterLegalization ? isOperationLegal(ISD::MULHU, VT) :
3090  Q = DAG.getNode(ISD::MULHU, dl, VT, Q, DAG.getConstant(magics.m, dl, VT));
3091  else if (IsAfterLegalization ? isOperationLegal(ISD::UMUL_LOHI, VT) :
3093  Q = SDValue(DAG.getNode(ISD::UMUL_LOHI, dl, DAG.getVTList(VT, VT), Q,
3094  DAG.getConstant(magics.m, dl, VT)).getNode(), 1);
3095  else
3096  return SDValue(); // No mulhu or equivalent
3097 
3098  Created->push_back(Q.getNode());
3099 
3100  if (magics.a == 0) {
3101  assert(magics.s < Divisor.getBitWidth() &&
3102  "We shouldn't generate an undefined shift!");
3103  return DAG.getNode(
3104  ISD::SRL, dl, VT, Q,
3105  DAG.getConstant(magics.s, dl, getShiftAmountTy(Q.getValueType(), DL)));
3106  } else {
3107  SDValue NPQ = DAG.getNode(ISD::SUB, dl, VT, N->getOperand(0), Q);
3108  Created->push_back(NPQ.getNode());
3109  NPQ = DAG.getNode(
3110  ISD::SRL, dl, VT, NPQ,
3111  DAG.getConstant(1, dl, getShiftAmountTy(NPQ.getValueType(), DL)));
3112  Created->push_back(NPQ.getNode());
3113  NPQ = DAG.getNode(ISD::ADD, dl, VT, NPQ, Q);
3114  Created->push_back(NPQ.getNode());
3115  return DAG.getNode(
3116  ISD::SRL, dl, VT, NPQ,
3117  DAG.getConstant(magics.s - 1, dl,
3118  getShiftAmountTy(NPQ.getValueType(), DL)));
3119  }
3120 }
3121 
3122 bool TargetLowering::
3124  if (!isa<ConstantSDNode>(Op.getOperand(0))) {
3125  DAG.getContext()->emitError("argument to '__builtin_return_address' must "
3126  "be a constant integer");
3127  return true;
3128  }
3129 
3130  return false;
3131 }
3132 
3133 //===----------------------------------------------------------------------===//
3134 // Legalization Utilities
3135 //===----------------------------------------------------------------------===//
3136 
3137 bool TargetLowering::expandMUL_LOHI(unsigned Opcode, EVT VT, SDLoc dl,
3138  SDValue LHS, SDValue RHS,
3139  SmallVectorImpl<SDValue> &Result,
3140  EVT HiLoVT, SelectionDAG &DAG,
3142  SDValue LH, SDValue RL, SDValue RH) const {
3143  assert(Opcode == ISD::MUL || Opcode == ISD::UMUL_LOHI ||
3144  Opcode == ISD::SMUL_LOHI);
3145 
3146  bool HasMULHS = (Kind == MulExpansionKind::Always) ||
3148  bool HasMULHU = (Kind == MulExpansionKind::Always) ||
3150  bool HasSMUL_LOHI = (Kind == MulExpansionKind::Always) ||
3152  bool HasUMUL_LOHI = (Kind == MulExpansionKind::Always) ||
3154 
3155  if (!HasMULHU && !HasMULHS && !HasUMUL_LOHI && !HasSMUL_LOHI)
3156  return false;
3157 
3158  unsigned OuterBitSize = VT.getScalarSizeInBits();
3159  unsigned InnerBitSize = HiLoVT.getScalarSizeInBits();
3160  unsigned LHSSB = DAG.ComputeNumSignBits(LHS);
3161  unsigned RHSSB = DAG.ComputeNumSignBits(RHS);
3162 
3163  // LL, LH, RL, and RH must be either all NULL or all set to a value.
3164  assert((LL.getNode() && LH.getNode() && RL.getNode() && RH.getNode()) ||
3165  (!LL.getNode() && !LH.getNode() && !RL.getNode() && !RH.getNode()));
3166 
3167  SDVTList VTs = DAG.getVTList(HiLoVT, HiLoVT);
3168  auto MakeMUL_LOHI = [&](SDValue L, SDValue R, SDValue &Lo, SDValue &Hi,
3169  bool Signed) -> bool {
3170  if ((Signed && HasSMUL_LOHI) || (!Signed && HasUMUL_LOHI)) {
3171  Lo = DAG.getNode(Signed ? ISD::SMUL_LOHI : ISD::UMUL_LOHI, dl, VTs, L, R);
3172  Hi = SDValue(Lo.getNode(), 1);
3173  return true;
3174  }
3175  if ((Signed && HasMULHS) || (!Signed && HasMULHU)) {
3176  Lo = DAG.getNode(ISD::MUL, dl, HiLoVT, L, R);
3177  Hi = DAG.getNode(Signed ? ISD::MULHS : ISD::MULHU, dl, HiLoVT, L, R);
3178  return true;
3179  }
3180  return false;
3181  };
3182 
3183  SDValue Lo, Hi;
3184 
3185  if (!LL.getNode() && !RL.getNode() &&
3187  LL = DAG.getNode(ISD::TRUNCATE, dl, HiLoVT, LHS);
3188  RL = DAG.getNode(ISD::TRUNCATE, dl, HiLoVT, RHS);
3189  }
3190 
3191  if (!LL.getNode())
3192  return false;
3193 
3194  APInt HighMask = APInt::getHighBitsSet(OuterBitSize, InnerBitSize);
3195  if (DAG.MaskedValueIsZero(LHS, HighMask) &&
3196  DAG.MaskedValueIsZero(RHS, HighMask)) {
3197  // The inputs are both zero-extended.
3198  if (MakeMUL_LOHI(LL, RL, Lo, Hi, false)) {
3199  Result.push_back(Lo);
3200  Result.push_back(Hi);
3201  if (Opcode != ISD::MUL) {
3202  SDValue Zero = DAG.getConstant(0, dl, HiLoVT);
3203  Result.push_back(Zero);
3204  Result.push_back(Zero);
3205  }
3206  return true;
3207  }
3208  }
3209 
3210  if (!VT.isVector() && Opcode == ISD::MUL && LHSSB > InnerBitSize &&
3211  RHSSB > InnerBitSize) {
3212  // The input values are both sign-extended.
3213  // TODO non-MUL case?
3214  if (MakeMUL_LOHI(LL, RL, Lo, Hi, true)) {
3215  Result.push_back(Lo);
3216  Result.push_back(Hi);
3217  return true;
3218  }
3219  }
3220 
3221  unsigned ShiftAmount = OuterBitSize - InnerBitSize;
3222  EVT ShiftAmountTy = getShiftAmountTy(VT, DAG.getDataLayout());
3223  if (APInt::getMaxValue(ShiftAmountTy.getSizeInBits()).ult(ShiftAmount)) {
3224  // FIXME getShiftAmountTy does not always return a sensible result when VT
3225  // is an illegal type, and so the type may be too small to fit the shift
3226  // amount. Override it with i32. The shift will have to be legalized.
3227  ShiftAmountTy = MVT::i32;
3228  }
3229  SDValue Shift = DAG.getConstant(ShiftAmount, dl, ShiftAmountTy);
3230 
3231  if (!LH.getNode() && !RH.getNode() &&
3234  LH = DAG.getNode(ISD::SRL, dl, VT, LHS, Shift);
3235  LH = DAG.getNode(ISD::TRUNCATE, dl, HiLoVT, LH);
3236  RH = DAG.getNode(ISD::SRL, dl, VT, RHS, Shift);
3237  RH = DAG.getNode(ISD::TRUNCATE, dl, HiLoVT, RH);
3238  }
3239 
3240  if (!LH.getNode())
3241  return false;
3242 
3243  if (!MakeMUL_LOHI(LL, RL, Lo, Hi, false))
3244  return false;
3245 
3246  Result.push_back(Lo);
3247 
3248  if (Opcode == ISD::MUL) {
3249  RH = DAG.getNode(ISD::MUL, dl, HiLoVT, LL, RH);
3250  LH = DAG.getNode(ISD::MUL, dl, HiLoVT, LH, RL);
3251  Hi = DAG.getNode(ISD::ADD, dl, HiLoVT, Hi, RH);
3252  Hi = DAG.getNode(ISD::ADD, dl, HiLoVT, Hi, LH);
3253  Result.push_back(Hi);
3254  return true;
3255  }
3256 
3257  // Compute the full width result.
3258  auto Merge = [&](SDValue Lo, SDValue Hi) -> SDValue {
3259  Lo = DAG.getNode(ISD::ZERO_EXTEND, dl, VT, Lo);
3260  Hi = DAG.getNode(ISD::ZERO_EXTEND, dl, VT, Hi);
3261  Hi = DAG.getNode(ISD::SHL, dl, VT, Hi, Shift);
3262  return DAG.getNode(ISD::OR, dl, VT, Lo, Hi);
3263  };
3264 
3265  SDValue Next = DAG.getNode(ISD::ZERO_EXTEND, dl, VT, Hi);
3266  if (!MakeMUL_LOHI(LL, RH, Lo, Hi, false))
3267  return false;
3268 
3269  // This is effectively the add part of a multiply-add of half-sized operands,
3270  // so it cannot overflow.
3271  Next = DAG.getNode(ISD::ADD, dl, VT, Next, Merge(Lo, Hi));
3272 
3273  if (!MakeMUL_LOHI(LH, RL, Lo, Hi, false))
3274  return false;
3275 
3276  Next = DAG.getNode(ISD::ADDC, dl, DAG.getVTList(VT, MVT::Glue), Next,
3277  Merge(Lo, Hi));
3278 
3279  SDValue Carry = Next.getValue(1);
3280  Result.push_back(DAG.getNode(ISD::TRUNCATE, dl, HiLoVT, Next));
3281  Next = DAG.getNode(ISD::SRL, dl, VT, Next, Shift);
3282 
3283  if (!MakeMUL_LOHI(LH, RH, Lo, Hi, Opcode == ISD::SMUL_LOHI))
3284  return false;
3285 
3286  SDValue Zero = DAG.getConstant(0, dl, HiLoVT);
3287  Hi = DAG.getNode(ISD::ADDE, dl, DAG.getVTList(HiLoVT, MVT::Glue), Hi, Zero,
3288  Carry);
3289  Next = DAG.getNode(ISD::ADD, dl, VT, Next, Merge(Lo, Hi));
3290 
3291  if (Opcode == ISD::SMUL_LOHI) {
3292  SDValue NextSub = DAG.getNode(ISD::SUB, dl, VT, Next,
3293  DAG.getNode(ISD::ZERO_EXTEND, dl, VT, RL));
3294  Next = DAG.getSelectCC(dl, LH, Zero, NextSub, Next, ISD::SETLT);
3295 
3296  NextSub = DAG.getNode(ISD::SUB, dl, VT, Next,
3297  DAG.getNode(ISD::ZERO_EXTEND, dl, VT, LL));
3298  Next = DAG.getSelectCC(dl, RH, Zero, NextSub, Next, ISD::SETLT);
3299  }
3300 
3301  Result.push_back(DAG.getNode(ISD::TRUNCATE, dl, HiLoVT, Next));
3302  Next = DAG.getNode(ISD::SRL, dl, VT, Next, Shift);
3303  Result.push_back(DAG.getNode(ISD::TRUNCATE, dl, HiLoVT, Next));
3304  return true;
3305 }
3306 
3309  SDValue LL, SDValue LH, SDValue RL,
3310  SDValue RH) const {
3311  SmallVector<SDValue, 2> Result;
3312  bool Ok = expandMUL_LOHI(N->getOpcode(), N->getValueType(0), N,
3313  N->getOperand(0), N->getOperand(1), Result, HiLoVT,
3314  DAG, Kind, LL, LH, RL, RH);
3315  if (Ok) {
3316  assert(Result.size() == 2);
3317  Lo = Result[0];
3318  Hi = Result[1];
3319  }
3320  return Ok;
3321 }
3322 
3324  SelectionDAG &DAG) const {
3325  EVT VT = Node->getOperand(0).getValueType();
3326  EVT NVT = Node->getValueType(0);
3327  SDLoc dl(SDValue(Node, 0));
3328 
3329  // FIXME: Only f32 to i64 conversions are supported.
3330  if (VT != MVT::f32 || NVT != MVT::i64)
3331  return false;
3332 
3333  // Expand f32 -> i64 conversion
3334  // This algorithm comes from compiler-rt's implementation of fixsfdi:
3335  // https://github.com/llvm-mirror/compiler-rt/blob/master/lib/builtins/fixsfdi.c
3336  EVT IntVT = EVT::getIntegerVT(*DAG.getContext(),
3337  VT.getSizeInBits());
3338  SDValue ExponentMask = DAG.getConstant(0x7F800000, dl, IntVT);
3339  SDValue ExponentLoBit = DAG.getConstant(23, dl, IntVT);
3340  SDValue Bias = DAG.getConstant(127, dl, IntVT);
3341  SDValue SignMask = DAG.getConstant(APInt::getSignMask(VT.getSizeInBits()), dl,
3342  IntVT);
3343  SDValue SignLowBit = DAG.getConstant(VT.getSizeInBits() - 1, dl, IntVT);
3344  SDValue MantissaMask = DAG.getConstant(0x007FFFFF, dl, IntVT);
3345 
3346  SDValue Bits = DAG.getNode(ISD::BITCAST, dl, IntVT, Node->getOperand(0));
3347 
3348  auto &DL = DAG.getDataLayout();
3349  SDValue ExponentBits = DAG.getNode(
3350  ISD::SRL, dl, IntVT, DAG.getNode(ISD::AND, dl, IntVT, Bits, ExponentMask),
3351  DAG.getZExtOrTrunc(ExponentLoBit, dl, getShiftAmountTy(IntVT, DL)));
3352  SDValue Exponent = DAG.getNode(ISD::SUB, dl, IntVT, ExponentBits, Bias);
3353 
3354  SDValue Sign = DAG.getNode(
3355  ISD::SRA, dl, IntVT, DAG.getNode(ISD::AND, dl, IntVT, Bits, SignMask),
3356  DAG.getZExtOrTrunc(SignLowBit, dl, getShiftAmountTy(IntVT, DL)));
3357  Sign = DAG.getSExtOrTrunc(Sign, dl, NVT);
3358 
3359  SDValue R = DAG.getNode(ISD::OR, dl, IntVT,
3360  DAG.getNode(ISD::AND, dl, IntVT, Bits, MantissaMask),
3361  DAG.getConstant(0x00800000, dl, IntVT));
3362 
3363  R = DAG.getZExtOrTrunc(R, dl, NVT);
3364 
3365  R = DAG.getSelectCC(
3366  dl, Exponent, ExponentLoBit,
3367  DAG.getNode(ISD::SHL, dl, NVT, R,
3368  DAG.getZExtOrTrunc(
3369  DAG.getNode(ISD::SUB, dl, IntVT, Exponent, ExponentLoBit),
3370  dl, getShiftAmountTy(IntVT, DL))),
3371  DAG.getNode(ISD::SRL, dl, NVT, R,
3372  DAG.getZExtOrTrunc(
3373  DAG.getNode(ISD::SUB, dl, IntVT, ExponentLoBit, Exponent),
3374  dl, getShiftAmountTy(IntVT, DL))),
3375  ISD::SETGT);
3376 
3377  SDValue Ret = DAG.getNode(ISD::SUB, dl, NVT,
3378  DAG.getNode(ISD::XOR, dl, NVT, R, Sign),
3379  Sign);
3380 
3381  Result = DAG.getSelectCC(dl, Exponent, DAG.getConstant(0, dl, IntVT),
3382  DAG.getConstant(0, dl, NVT), Ret, ISD::SETLT);
3383  return true;
3384 }
3385 
3387  SelectionDAG &DAG) const {
3388  SDLoc SL(LD);
3389  SDValue Chain = LD->getChain();
3390  SDValue BasePTR = LD->getBasePtr();
3391  EVT SrcVT = LD->getMemoryVT();
3392  ISD::LoadExtType ExtType = LD->getExtensionType();
3393 
3394  unsigned NumElem = SrcVT.getVectorNumElements();
3395 
3396  EVT SrcEltVT = SrcVT.getScalarType();
3397  EVT DstEltVT = LD->getValueType(0).getScalarType();
3398 
3399  unsigned Stride = SrcEltVT.getSizeInBits() / 8;
3400  assert(SrcEltVT.isByteSized());
3401 
3402  EVT PtrVT = BasePTR.getValueType();
3403 
3405  SmallVector<SDValue, 8> LoadChains;
3406 
3407  for (unsigned Idx = 0; Idx < NumElem; ++Idx) {
3408  SDValue ScalarLoad =
3409  DAG.getExtLoad(ExtType, SL, DstEltVT, Chain, BasePTR,
3410  LD->getPointerInfo().getWithOffset(Idx * Stride),
3411  SrcEltVT, MinAlign(LD->getAlignment(), Idx * Stride),
3412  LD->getMemOperand()->getFlags(), LD->getAAInfo());
3413 
3414  BasePTR = DAG.getNode(ISD::ADD, SL, PtrVT, BasePTR,
3415  DAG.getConstant(Stride, SL, PtrVT));
3416 
3417  Vals.push_back(ScalarLoad.getValue(0));
3418  LoadChains.push_back(ScalarLoad.getValue(1));
3419  }
3420 
3421  SDValue NewChain = DAG.getNode(ISD::TokenFactor, SL, MVT::Other, LoadChains);
3422  SDValue Value = DAG.getBuildVector(LD->getValueType(0), SL, Vals);
3423 
3424  return DAG.getMergeValues({ Value, NewChain }, SL);
3425 }
3426 
3427 // FIXME: This relies on each element having a byte size, otherwise the stride
3428 // is 0 and just overwrites the same location. ExpandStore currently expects
3429 // this broken behavior.
3431  SelectionDAG &DAG) const {
3432  SDLoc SL(ST);
3433 
3434  SDValue Chain = ST->getChain();
3435  SDValue BasePtr = ST->getBasePtr();
3436  SDValue Value = ST->getValue();
3437  EVT StVT = ST->getMemoryVT();
3438 
3439  // The type of the data we want to save
3440  EVT RegVT = Value.getValueType();
3441  EVT RegSclVT = RegVT.getScalarType();
3442 
3443  // The type of data as saved in memory.
3444  EVT MemSclVT = StVT.getScalarType();
3445 
3446  EVT PtrVT = BasePtr.getValueType();
3447 
3448  // Store Stride in bytes
3449  unsigned Stride = MemSclVT.getSizeInBits() / 8;
3450  EVT IdxVT = getVectorIdxTy(DAG.getDataLayout());
3451  unsigned NumElem = StVT.getVectorNumElements();
3452 
3453  // Extract each of the elements from the original vector and save them into
3454  // memory individually.
3455  SmallVector<SDValue, 8> Stores;
3456  for (unsigned Idx = 0; Idx < NumElem; ++Idx) {
3457  SDValue Elt = DAG.getNode(ISD::EXTRACT_VECTOR_ELT, SL, RegSclVT, Value,
3458  DAG.getConstant(Idx, SL, IdxVT));
3459 
3460  SDValue Ptr = DAG.getNode(ISD::ADD, SL, PtrVT, BasePtr,
3461  DAG.getConstant(Idx * Stride, SL, PtrVT));
3462 
3463  // This scalar TruncStore may be illegal, but we legalize it later.
3464  SDValue Store = DAG.getTruncStore(
3465  Chain, SL, Elt, Ptr, ST->getPointerInfo().getWithOffset(Idx * Stride),
3466  MemSclVT, MinAlign(ST->getAlignment(), Idx * Stride),
3467  ST->getMemOperand()->getFlags(), ST->getAAInfo());
3468 
3469  Stores.push_back(Store);
3470  }
3471 
3472  return DAG.getNode(ISD::TokenFactor, SL, MVT::Other, Stores);
3473 }
3474 
3475 std::pair<SDValue, SDValue>
3478  "unaligned indexed loads not implemented!");
3479  SDValue Chain = LD->getChain();
3480  SDValue Ptr = LD->getBasePtr();
3481  EVT VT = LD->getValueType(0);
3482  EVT LoadedVT = LD->getMemoryVT();
3483  SDLoc dl(LD);
3484  if (VT.isFloatingPoint() || VT.isVector()) {
3485  EVT intVT = EVT::getIntegerVT(*DAG.getContext(), LoadedVT.getSizeInBits());
3486  if (isTypeLegal(intVT) && isTypeLegal(LoadedVT)) {
3487  if (!isOperationLegalOrCustom(ISD::LOAD, intVT)) {
3488  // Scalarize the load and let the individual components be handled.
3489  SDValue Scalarized = scalarizeVectorLoad(LD, DAG);
3490  return std::make_pair(Scalarized.getValue(0), Scalarized.getValue(1));
3491  }
3492 
3493  // Expand to a (misaligned) integer load of the same size,
3494  // then bitconvert to floating point or vector.
3495  SDValue newLoad = DAG.getLoad(intVT, dl, Chain, Ptr,
3496  LD->getMemOperand());
3497  SDValue Result = DAG.getNode(ISD::BITCAST, dl, LoadedVT, newLoad);
3498  if (LoadedVT != VT)
3499  Result = DAG.getNode(VT.isFloatingPoint() ? ISD::FP_EXTEND :
3500  ISD::ANY_EXTEND, dl, VT, Result);
3501 
3502  return std::make_pair(Result, newLoad.getValue(1));
3503  }
3504 
3505  // Copy the value to a (aligned) stack slot using (unaligned) integer
3506  // loads and stores, then do a (aligned) load from the stack slot.
3507  MVT RegVT = getRegisterType(*DAG.getContext(), intVT);
3508  unsigned LoadedBytes = LoadedVT.getSizeInBits() / 8;
3509  unsigned RegBytes = RegVT.getSizeInBits() / 8;
3510  unsigned NumRegs = (LoadedBytes + RegBytes - 1) / RegBytes;
3511 
3512  // Make sure the stack slot is also aligned for the register type.
3513  SDValue StackBase = DAG.CreateStackTemporary(LoadedVT, RegVT);
3514 
3515  SmallVector<SDValue, 8> Stores;
3516  SDValue StackPtr = StackBase;
3517  unsigned Offset = 0;
3518 
3519  EVT PtrVT = Ptr.getValueType();
3520  EVT StackPtrVT = StackPtr.getValueType();
3521 
3522  SDValue PtrIncrement = DAG.getConstant(RegBytes, dl, PtrVT);
3523  SDValue StackPtrIncrement = DAG.getConstant(RegBytes, dl, StackPtrVT);
3524 
3525  // Do all but one copies using the full register width.
3526  for (unsigned i = 1; i < NumRegs; i++) {
3527  // Load one integer register's worth from the original location.
3528  SDValue Load = DAG.getLoad(
3529  RegVT, dl, Chain, Ptr, LD->getPointerInfo().getWithOffset(Offset),
3531  LD->getAAInfo());
3532  // Follow the load with a store to the stack slot. Remember the store.
3533  Stores.push_back(DAG.getStore(Load.getValue(1), dl, Load, StackPtr,
3534  MachinePointerInfo()));
3535  // Increment the pointers.
3536  Offset += RegBytes;
3537  Ptr = DAG.getNode(ISD::ADD, dl, PtrVT, Ptr, PtrIncrement);
3538  StackPtr = DAG.getNode(ISD::ADD, dl, StackPtrVT, StackPtr,
3539  StackPtrIncrement);
3540  }
3541 
3542  // The last copy may be partial. Do an extending load.
3543  EVT MemVT = EVT::getIntegerVT(*DAG.getContext(),
3544  8 * (LoadedBytes - Offset));
3545  SDValue Load =
3546  DAG.getExtLoad(ISD::EXTLOAD, dl, RegVT, Chain, Ptr,
3547  LD->getPointerInfo().getWithOffset(Offset), MemVT,
3548  MinAlign(LD->getAlignment(), Offset),
3549  LD->getMemOperand()->getFlags(), LD->getAAInfo());
3550  // Follow the load with a store to the stack slot. Remember the store.
3551  // On big-endian machines this requires a truncating store to ensure
3552  // that the bits end up in the right place.
3553  Stores.push_back(DAG.getTruncStore(Load.getValue(1), dl, Load, StackPtr,
3554  MachinePointerInfo(), MemVT));
3555 
3556  // The order of the stores doesn't matter - say it with a TokenFactor.
3557  SDValue TF = DAG.getNode(ISD::TokenFactor, dl, MVT::Other, Stores);
3558 
3559  // Finally, perform the original load only redirected to the stack slot.
3560  Load = DAG.getExtLoad(LD->getExtensionType(), dl, VT, TF, StackBase,
3561  MachinePointerInfo(), LoadedVT);
3562 
3563  // Callers expect a MERGE_VALUES node.
3564  return std::make_pair(Load, TF);
3565  }
3566 
3567  assert(LoadedVT.isInteger() && !LoadedVT.isVector() &&
3568  "Unaligned load of unsupported type.");
3569 
3570  // Compute the new VT that is half the size of the old one. This is an
3571  // integer MVT.
3572  unsigned NumBits = LoadedVT.getSizeInBits();
3573  EVT NewLoadedVT;
3574  NewLoadedVT = EVT::getIntegerVT(*DAG.getContext(), NumBits/2);
3575  NumBits >>= 1;
3576 
3577  unsigned Alignment = LD->getAlignment();
3578  unsigned IncrementSize = NumBits / 8;
3579  ISD::LoadExtType HiExtType = LD->getExtensionType();
3580 
3581  // If the original load is NON_EXTLOAD, the hi part load must be ZEXTLOAD.
3582  if (HiExtType == ISD::NON_EXTLOAD)
3583  HiExtType = ISD::ZEXTLOAD;
3584 
3585  // Load the value in two parts
3586  SDValue Lo, Hi;
3587  if (DAG.getDataLayout().isLittleEndian()) {
3588  Lo = DAG.getExtLoad(ISD::ZEXTLOAD, dl, VT, Chain, Ptr, LD->getPointerInfo(),
3589  NewLoadedVT, Alignment, LD->getMemOperand()->getFlags(),
3590  LD->getAAInfo());
3591  Ptr = DAG.getNode(ISD::ADD, dl, Ptr.getValueType(), Ptr,
3592  DAG.getConstant(IncrementSize, dl, Ptr.getValueType()));
3593  Hi = DAG.getExtLoad(HiExtType, dl, VT, Chain, Ptr,
3594  LD->getPointerInfo().getWithOffset(IncrementSize),
3595  NewLoadedVT, MinAlign(Alignment, IncrementSize),
3596  LD->getMemOperand()->getFlags(), LD->getAAInfo());
3597  } else {
3598  Hi = DAG.getExtLoad(HiExtType, dl, VT, Chain, Ptr, LD->getPointerInfo(),
3599  NewLoadedVT, Alignment, LD->getMemOperand()->getFlags(),
3600  LD->getAAInfo());
3601  Ptr = DAG.getNode(ISD::ADD, dl, Ptr.getValueType(), Ptr,
3602  DAG.getConstant(IncrementSize, dl, Ptr.getValueType()));
3603  Lo = DAG.getExtLoad(ISD::ZEXTLOAD, dl, VT, Chain, Ptr,
3604  LD->getPointerInfo().getWithOffset(IncrementSize),
3605  NewLoadedVT, MinAlign(Alignment, IncrementSize),
3606  LD->getMemOperand()->getFlags(), LD->getAAInfo());
3607  }
3608 
3609  // aggregate the two parts
3610  SDValue ShiftAmount =
3611  DAG.getConstant(NumBits, dl, getShiftAmountTy(Hi.getValueType(),
3612  DAG.getDataLayout()));
3613  SDValue Result = DAG.getNode(ISD::SHL, dl, VT, Hi, ShiftAmount);
3614  Result = DAG.getNode(ISD::OR, dl, VT, Result, Lo);
3615 
3616  SDValue TF = DAG.getNode(ISD::TokenFactor, dl, MVT::Other, Lo.getValue(1),
3617  Hi.getValue(1));
3618 
3619  return std::make_pair(Result, TF);
3620 }
3621 
3623  SelectionDAG &DAG) const {
3625  "unaligned indexed stores not implemented!");
3626  SDValue Chain = ST->getChain();
3627  SDValue Ptr = ST->getBasePtr();
3628  SDValue Val = ST->getValue();
3629  EVT VT = Val.getValueType();
3630  int Alignment = ST->getAlignment();
3631 
3632  SDLoc dl(ST);
3633  if (ST->getMemoryVT().isFloatingPoint() ||
3634  ST->getMemoryVT().isVector()) {
3635  EVT intVT = EVT::getIntegerVT(*DAG.getContext(), VT.getSizeInBits());
3636  if (isTypeLegal(intVT)) {
3637  if (!isOperationLegalOrCustom(ISD::STORE, intVT)) {
3638  // Scalarize the store and let the individual components be handled.
3639  SDValue Result = scalarizeVectorStore(ST, DAG);
3640 
3641  return Result;
3642  }
3643  // Expand to a bitconvert of the value to the integer type of the
3644  // same size, then a (misaligned) int store.
3645  // FIXME: Does not handle truncating floating point stores!
3646  SDValue Result = DAG.getNode(ISD::BITCAST, dl, intVT, Val);
3647  Result = DAG.getStore(Chain, dl, Result, Ptr, ST->getPointerInfo(),
3648  Alignment, ST->getMemOperand()->getFlags());
3649  return Result;
3650  }
3651  // Do a (aligned) store to a stack slot, then copy from the stack slot
3652  // to the final destination using (unaligned) integer loads and stores.
3653  EVT StoredVT = ST->getMemoryVT();
3654  MVT RegVT =
3655  getRegisterType(*DAG.getContext(),
3657  StoredVT.getSizeInBits()));
3658  EVT PtrVT = Ptr.getValueType();
3659  unsigned StoredBytes = StoredVT.getSizeInBits() / 8;
3660  unsigned RegBytes = RegVT.getSizeInBits() / 8;
3661  unsigned NumRegs = (StoredBytes + RegBytes - 1) / RegBytes;
3662 
3663  // Make sure the stack slot is also aligned for the register type.
3664  SDValue StackPtr = DAG.CreateStackTemporary(StoredVT, RegVT);
3665 
3666  // Perform the original store, only redirected to the stack slot.
3667  SDValue Store = DAG.getTruncStore(Chain, dl, Val, StackPtr,
3668  MachinePointerInfo(), StoredVT);
3669 
3670  EVT StackPtrVT = StackPtr.getValueType();
3671 
3672  SDValue PtrIncrement = DAG.getConstant(RegBytes, dl, PtrVT);
3673  SDValue StackPtrIncrement = DAG.getConstant(RegBytes, dl, StackPtrVT);
3674  SmallVector<SDValue, 8> Stores;
3675  unsigned Offset = 0;
3676 
3677  // Do all but one copies using the full register width.
3678  for (unsigned i = 1; i < NumRegs; i++) {
3679  // Load one integer register's worth from the stack slot.
3680  SDValue Load =
3681  DAG.getLoad(RegVT, dl, Store, StackPtr, MachinePointerInfo());
3682  // Store it to the final location. Remember the store.
3683  Stores.push_back(DAG.getStore(Load.getValue(1), dl, Load, Ptr,
3684  ST->getPointerInfo().getWithOffset(Offset),
3685  MinAlign(ST->getAlignment(), Offset),
3686  ST->getMemOperand()->getFlags()));
3687  // Increment the pointers.
3688  Offset += RegBytes;
3689  StackPtr = DAG.getNode(ISD::ADD, dl, StackPtrVT,
3690  StackPtr, StackPtrIncrement);
3691  Ptr = DAG.getNode(ISD::ADD, dl, PtrVT, Ptr, PtrIncrement);
3692  }
3693 
3694  // The last store may be partial. Do a truncating store. On big-endian
3695  // machines this requires an extending load from the stack slot to ensure
3696  // that the bits are in the right place.
3697  EVT MemVT = EVT::getIntegerVT(*DAG.getContext(),
3698  8 * (StoredBytes - Offset));
3699 
3700  // Load from the stack slot.
3701  SDValue Load = DAG.getExtLoad(ISD::EXTLOAD, dl, RegVT, Store, StackPtr,
3702  MachinePointerInfo(), MemVT);
3703 
3704  Stores.push_back(
3705  DAG.getTruncStore(Load.getValue(1), dl, Load, Ptr,
3706  ST->getPointerInfo().getWithOffset(Offset), MemVT,
3707  MinAlign(ST->getAlignment(), Offset),
3708  ST->getMemOperand()->getFlags(), ST->getAAInfo()));
3709  // The order of the stores doesn't matter - say it with a TokenFactor.
3710  SDValue Result = DAG.getNode(ISD::TokenFactor, dl, MVT::Other, Stores);
3711  return Result;
3712  }
3713 
3714  assert(ST->getMemoryVT().isInteger() &&
3715  !ST->getMemoryVT().isVector() &&
3716  "Unaligned store of unknown type.");
3717  // Get the half-size VT
3718  EVT NewStoredVT = ST->getMemoryVT().getHalfSizedIntegerVT(*DAG.getContext());
3719  int NumBits = NewStoredVT.getSizeInBits();
3720  int IncrementSize = NumBits / 8;
3721 
3722  // Divide the stored value in two parts.
3723  SDValue ShiftAmount =
3724  DAG.getConstant(NumBits, dl, getShiftAmountTy(Val.getValueType(),
3725  DAG.getDataLayout()));
3726  SDValue Lo = Val;
3727  SDValue Hi = DAG.getNode(ISD::SRL, dl, VT, Val, ShiftAmount);
3728 
3729  // Store the two parts
3730  SDValue Store1, Store2;
3731  Store1 = DAG.getTruncStore(Chain, dl,
3732  DAG.getDataLayout().isLittleEndian() ? Lo : Hi,
3733  Ptr, ST->getPointerInfo(), NewStoredVT, Alignment,
3734  ST->getMemOperand()->getFlags());
3735 
3736  EVT PtrVT = Ptr.getValueType();
3737  Ptr = DAG.getNode(ISD::ADD, dl, PtrVT, Ptr,
3738  DAG.getConstant(IncrementSize, dl, PtrVT));
3739  Alignment = MinAlign(Alignment, IncrementSize);
3740  Store2 = DAG.getTruncStore(
3741  Chain, dl, DAG.getDataLayout().isLittleEndian() ? Hi : Lo, Ptr,
3742  ST->getPointerInfo().getWithOffset(IncrementSize), NewStoredVT, Alignment,
3743  ST->getMemOperand()->getFlags(), ST->getAAInfo());
3744 
3745  SDValue Result =
3746  DAG.getNode(ISD::TokenFactor, dl, MVT::Other, Store1, Store2);
3747  return Result;
3748 }
3749 
3750 SDValue
3752  const SDLoc &DL, EVT DataVT,
3753  SelectionDAG &DAG,
3754  bool IsCompressedMemory) const {
3755  SDValue Increment;
3756  EVT AddrVT = Addr.getValueType();
3757  EVT MaskVT = Mask.getValueType();
3758  assert(DataVT.getVectorNumElements() == MaskVT.getVectorNumElements() &&
3759  "Incompatible types of Data and Mask");
3760  if (IsCompressedMemory) {
3761  // Incrementing the pointer according to number of '1's in the mask.
3762  EVT MaskIntVT = EVT::getIntegerVT(*DAG.getContext(), MaskVT.getSizeInBits());
3763  SDValue MaskInIntReg = DAG.getBitcast(MaskIntVT, Mask);
3764  if (MaskIntVT.getSizeInBits() < 32) {
3765  MaskInIntReg = DAG.getNode(ISD::ZERO_EXTEND, DL, MVT::i32, MaskInIntReg);
3766  MaskIntVT = MVT::i32;
3767  }
3768 
3769  // Count '1's with POPCNT.
3770  Increment = DAG.getNode(ISD::CTPOP, DL, MaskIntVT, MaskInIntReg);
3771  Increment = DAG.getZExtOrTrunc(Increment, DL, AddrVT);
3772  // Scale is an element size in bytes.
3773  SDValue Scale = DAG.getConstant(DataVT.getScalarSizeInBits() / 8, DL,
3774  AddrVT);
3775  Increment = DAG.getNode(ISD::MUL, DL, AddrVT, Increment, Scale);
3776  } else
3777  Increment = DAG.getConstant(DataVT.getSizeInBits() / 8, DL, AddrVT);
3778 
3779  return DAG.getNode(ISD::ADD, DL, AddrVT, Addr, Increment);
3780 }
3781 
3783  SDValue Idx,
3784  EVT VecVT,
3785  const SDLoc &dl) {
3786  if (isa<ConstantSDNode>(Idx))
3787  return Idx;
3788 
3789  EVT IdxVT = Idx.getValueType();
3790  unsigned NElts = VecVT.getVectorNumElements();
3791  if (isPowerOf2_32(NElts)) {
3793  Log2_32(NElts));
3794  return DAG.getNode(ISD::AND, dl, IdxVT, Idx,
3795  DAG.getConstant(Imm, dl, IdxVT));
3796  }
3797 
3798  return DAG.getNode(ISD::UMIN, dl, IdxVT, Idx,
3799  DAG.getConstant(NElts - 1, dl, IdxVT));
3800 }
3801 
3803  SDValue VecPtr, EVT VecVT,
3804  SDValue Index) const {
3805  SDLoc dl(Index);
3806  // Make sure the index type is big enough to compute in.
3807  Index = DAG.getZExtOrTrunc(Index, dl, getPointerTy(DAG.getDataLayout()));
3808 
3809  EVT EltVT = VecVT.getVectorElementType();
3810 
3811  // Calculate the element offset and add it to the pointer.
3812  unsigned EltSize = EltVT.getSizeInBits() / 8; // FIXME: should be ABI size.
3813  assert(EltSize * 8 == EltVT.getSizeInBits() &&
3814  "Converting bits to bytes lost precision");
3815 
3816  Index = clampDynamicVectorIndex(DAG, Index, VecVT, dl);
3817 
3818  EVT IdxVT = Index.getValueType();
3819 
3820  Index = DAG.getNode(ISD::MUL, dl, IdxVT, Index,
3821  DAG.getConstant(EltSize, dl, IdxVT));
3822  return DAG.getNode(ISD::ADD, dl, IdxVT, Index, VecPtr);
3823 }
3824 
3825 //===----------------------------------------------------------------------===//
3826 // Implementation of Emulated TLS Model
3827 //===----------------------------------------------------------------------===//
3828 
3830  SelectionDAG &DAG) const {
3831  // Access to address of TLS varialbe xyz is lowered to a function call:
3832  // __emutls_get_address( address of global variable named "__emutls_v.xyz" )
3833  EVT PtrVT = getPointerTy(DAG.getDataLayout());
3834  PointerType *VoidPtrType = Type::getInt8PtrTy(*DAG.getContext());
3835  SDLoc dl(GA);
3836 
3837  ArgListTy Args;
3838  ArgListEntry Entry;
3839  std::string NameString = ("__emutls_v." + GA->getGlobal()->getName()).str();
3840  Module *VariableModule = const_cast<Module*>(GA->getGlobal()->getParent());
3841  StringRef EmuTlsVarName(NameString);
3842  GlobalVariable *EmuTlsVar = VariableModule->getNamedGlobal(EmuTlsVarName);
3843  assert(EmuTlsVar && "Cannot find EmuTlsVar ");
3844  Entry.Node = DAG.getGlobalAddress(EmuTlsVar, dl, PtrVT);
3845  Entry.Ty = VoidPtrType;
3846  Args.push_back(Entry);
3847 
3848  SDValue EmuTlsGetAddr = DAG.getExternalSymbol("__emutls_get_address", PtrVT);
3849 
3851  CLI.setDebugLoc(dl).setChain(DAG.getEntryNode());
3852  CLI.setLibCallee(CallingConv::C, VoidPtrType, EmuTlsGetAddr, std::move(Args));
3853  std::pair<SDValue, SDValue> CallResult = LowerCallTo(CLI);
3854 
3855  // TLSADDR will be codegen'ed as call. Inform MFI that function has calls.
3856  // At last for X86 targets, maybe good for other targets too?
3858  MFI.setAdjustsStack(true); // Is this only for X86 target?
3859  MFI.setHasCalls(true);
3860 
3861  assert((GA->getOffset() == 0) &&
3862  "Emulated TLS must have zero offset in GlobalAddressSDNode");
3863  return CallResult.first;
3864 }
3865 
3867  SelectionDAG &DAG) const {
3868  assert((Op->getOpcode() == ISD::SETCC) && "Input has to be a SETCC node.");
3869  if (!isCtlzFast())
3870  return SDValue();
3871  ISD::CondCode CC = cast<CondCodeSDNode>(Op.getOperand(2))->get();
3872  SDLoc dl(Op);
3873  if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
3874  if (C->isNullValue() && CC == ISD::SETEQ) {
3875  EVT VT = Op.getOperand(0).getValueType();
3876  SDValue Zext = Op.getOperand(0);
3877  if (VT.bitsLT(MVT::i32)) {
3878  VT = MVT::i32;
3879  Zext = DAG.getNode(ISD::ZERO_EXTEND, dl, VT, Op.getOperand(0));
3880  }
3881  unsigned Log2b = Log2_32(VT.getSizeInBits());
3882  SDValue Clz = DAG.getNode(ISD::CTLZ, dl, VT, Zext);
3883  SDValue Scc = DAG.getNode(ISD::SRL, dl, VT, Clz,
3884  DAG.getConstant(Log2b, dl, MVT::i32));
3885  return DAG.getNode(ISD::TRUNCATE, dl, MVT::i32, Scc);
3886  }
3887  }
3888  return SDValue();
3889 }
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:545
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:834
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:890
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
struct fuzzer::@309 Flags
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:406
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:85
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
F(f)
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:962
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:404
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:291
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.
C - The default llvm calling convention, compatible with C.
Definition: CallingConv.h:35
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:379
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:438
const DataLayout & getDataLayout() const
Definition: SelectionDAG.h:380
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:100
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
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:245
MachineFunction & getMachineFunction() const
Definition: SelectionDAG.h:377
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:377
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:822
AttributeList getAttributes() const
Return the attribute list for this Function.
Definition: Function.h:205
CondCode
ISD::CondCode enum - These are ordered carefully to make the bitfields below work out...
Definition: ISDOpcodes.h:916
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:550
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:949
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
amdgpu Simplify well known AMD library false Value * Callee
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:302
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
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
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:891
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:969
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:530
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
R600 Clause Merge
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:383
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.
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:186
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:314
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:704
CCValAssign - Represent assignment of one arg/retval to a location.
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
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 BitVe