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