LLVM  mainline
TargetLowering.cpp
Go to the documentation of this file.
00001 //===-- TargetLowering.cpp - Implement the TargetLowering class -----------===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file is distributed under the University of Illinois Open Source
00006 // License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // This implements the TargetLowering class.
00011 //
00012 //===----------------------------------------------------------------------===//
00013 
00014 #include "llvm/Target/TargetLowering.h"
00015 #include "llvm/ADT/BitVector.h"
00016 #include "llvm/ADT/STLExtras.h"
00017 #include "llvm/CodeGen/Analysis.h"
00018 #include "llvm/CodeGen/MachineFrameInfo.h"
00019 #include "llvm/CodeGen/MachineFunction.h"
00020 #include "llvm/CodeGen/MachineJumpTableInfo.h"
00021 #include "llvm/CodeGen/SelectionDAG.h"
00022 #include "llvm/IR/DataLayout.h"
00023 #include "llvm/IR/DerivedTypes.h"
00024 #include "llvm/IR/GlobalVariable.h"
00025 #include "llvm/IR/LLVMContext.h"
00026 #include "llvm/MC/MCAsmInfo.h"
00027 #include "llvm/MC/MCExpr.h"
00028 #include "llvm/Support/CommandLine.h"
00029 #include "llvm/Support/ErrorHandling.h"
00030 #include "llvm/Support/MathExtras.h"
00031 #include "llvm/Target/TargetLoweringObjectFile.h"
00032 #include "llvm/Target/TargetMachine.h"
00033 #include "llvm/Target/TargetRegisterInfo.h"
00034 #include "llvm/Target/TargetSubtargetInfo.h"
00035 #include <cctype>
00036 using namespace llvm;
00037 
00038 /// NOTE: The TargetMachine owns TLOF.
00039 TargetLowering::TargetLowering(const TargetMachine &tm)
00040   : TargetLoweringBase(tm) {}
00041 
00042 const char *TargetLowering::getTargetNodeName(unsigned Opcode) const {
00043   return nullptr;
00044 }
00045 
00046 /// Check whether a given call node is in tail position within its function. If
00047 /// so, it sets Chain to the input chain of the tail call.
00048 bool TargetLowering::isInTailCallPosition(SelectionDAG &DAG, SDNode *Node,
00049                                           SDValue &Chain) const {
00050   const Function *F = DAG.getMachineFunction().getFunction();
00051 
00052   // Conservatively require the attributes of the call to match those of
00053   // the return. Ignore noalias because it doesn't affect the call sequence.
00054   AttributeSet CallerAttrs = F->getAttributes();
00055   if (AttrBuilder(CallerAttrs, AttributeSet::ReturnIndex)
00056       .removeAttribute(Attribute::NoAlias).hasAttributes())
00057     return false;
00058 
00059   // It's not safe to eliminate the sign / zero extension of the return value.
00060   if (CallerAttrs.hasAttribute(AttributeSet::ReturnIndex, Attribute::ZExt) ||
00061       CallerAttrs.hasAttribute(AttributeSet::ReturnIndex, Attribute::SExt))
00062     return false;
00063 
00064   // Check if the only use is a function return node.
00065   return isUsedByReturnOnly(Node, Chain);
00066 }
00067 
00068 /// \brief Set CallLoweringInfo attribute flags based on a call instruction
00069 /// and called function attributes.
00070 void TargetLowering::ArgListEntry::setAttributes(ImmutableCallSite *CS,
00071                                                  unsigned AttrIdx) {
00072   isSExt     = CS->paramHasAttr(AttrIdx, Attribute::SExt);
00073   isZExt     = CS->paramHasAttr(AttrIdx, Attribute::ZExt);
00074   isInReg    = CS->paramHasAttr(AttrIdx, Attribute::InReg);
00075   isSRet     = CS->paramHasAttr(AttrIdx, Attribute::StructRet);
00076   isNest     = CS->paramHasAttr(AttrIdx, Attribute::Nest);
00077   isByVal    = CS->paramHasAttr(AttrIdx, Attribute::ByVal);
00078   isInAlloca = CS->paramHasAttr(AttrIdx, Attribute::InAlloca);
00079   isReturned = CS->paramHasAttr(AttrIdx, Attribute::Returned);
00080   Alignment  = CS->getParamAlignment(AttrIdx);
00081 }
00082 
00083 /// Generate a libcall taking the given operands as arguments and returning a
00084 /// result of type RetVT.
00085 std::pair<SDValue, SDValue>
00086 TargetLowering::makeLibCall(SelectionDAG &DAG,
00087                             RTLIB::Libcall LC, EVT RetVT,
00088                             ArrayRef<SDValue> Ops,
00089                             bool isSigned, SDLoc dl,
00090                             bool doesNotReturn,
00091                             bool isReturnValueUsed) const {
00092   TargetLowering::ArgListTy Args;
00093   Args.reserve(Ops.size());
00094 
00095   TargetLowering::ArgListEntry Entry;
00096   for (SDValue Op : Ops) {
00097     Entry.Node = Op;
00098     Entry.Ty = Entry.Node.getValueType().getTypeForEVT(*DAG.getContext());
00099     Entry.isSExt = shouldSignExtendTypeInLibCall(Op.getValueType(), isSigned);
00100     Entry.isZExt = !shouldSignExtendTypeInLibCall(Op.getValueType(), isSigned);
00101     Args.push_back(Entry);
00102   }
00103 
00104   if (LC == RTLIB::UNKNOWN_LIBCALL)
00105     report_fatal_error("Unsupported library call operation!");
00106   SDValue Callee = DAG.getExternalSymbol(getLibcallName(LC),
00107                                          getPointerTy(DAG.getDataLayout()));
00108 
00109   Type *RetTy = RetVT.getTypeForEVT(*DAG.getContext());
00110   TargetLowering::CallLoweringInfo CLI(DAG);
00111   bool signExtend = shouldSignExtendTypeInLibCall(RetVT, isSigned);
00112   CLI.setDebugLoc(dl).setChain(DAG.getEntryNode())
00113     .setCallee(getLibcallCallingConv(LC), RetTy, Callee, std::move(Args), 0)
00114     .setNoReturn(doesNotReturn).setDiscardResult(!isReturnValueUsed)
00115     .setSExtResult(signExtend).setZExtResult(!signExtend);
00116   return LowerCallTo(CLI);
00117 }
00118 
00119 /// Soften the operands of a comparison. This code is shared among BR_CC,
00120 /// SELECT_CC, and SETCC handlers.
00121 void TargetLowering::softenSetCCOperands(SelectionDAG &DAG, EVT VT,
00122                                          SDValue &NewLHS, SDValue &NewRHS,
00123                                          ISD::CondCode &CCCode,
00124                                          SDLoc dl) const {
00125   assert((VT == MVT::f32 || VT == MVT::f64 || VT == MVT::f128)
00126          && "Unsupported setcc type!");
00127 
00128   // Expand into one or more soft-fp libcall(s).
00129   RTLIB::Libcall LC1 = RTLIB::UNKNOWN_LIBCALL, LC2 = RTLIB::UNKNOWN_LIBCALL;
00130   bool ShouldInvertCC = false;
00131   switch (CCCode) {
00132   case ISD::SETEQ:
00133   case ISD::SETOEQ:
00134     LC1 = (VT == MVT::f32) ? RTLIB::OEQ_F32 :
00135           (VT == MVT::f64) ? RTLIB::OEQ_F64 : RTLIB::OEQ_F128;
00136     break;
00137   case ISD::SETNE:
00138   case ISD::SETUNE:
00139     LC1 = (VT == MVT::f32) ? RTLIB::UNE_F32 :
00140           (VT == MVT::f64) ? RTLIB::UNE_F64 : RTLIB::UNE_F128;
00141     break;
00142   case ISD::SETGE:
00143   case ISD::SETOGE:
00144     LC1 = (VT == MVT::f32) ? RTLIB::OGE_F32 :
00145           (VT == MVT::f64) ? RTLIB::OGE_F64 : RTLIB::OGE_F128;
00146     break;
00147   case ISD::SETLT:
00148   case ISD::SETOLT:
00149     LC1 = (VT == MVT::f32) ? RTLIB::OLT_F32 :
00150           (VT == MVT::f64) ? RTLIB::OLT_F64 : RTLIB::OLT_F128;
00151     break;
00152   case ISD::SETLE:
00153   case ISD::SETOLE:
00154     LC1 = (VT == MVT::f32) ? RTLIB::OLE_F32 :
00155           (VT == MVT::f64) ? RTLIB::OLE_F64 : RTLIB::OLE_F128;
00156     break;
00157   case ISD::SETGT:
00158   case ISD::SETOGT:
00159     LC1 = (VT == MVT::f32) ? RTLIB::OGT_F32 :
00160           (VT == MVT::f64) ? RTLIB::OGT_F64 : RTLIB::OGT_F128;
00161     break;
00162   case ISD::SETUO:
00163     LC1 = (VT == MVT::f32) ? RTLIB::UO_F32 :
00164           (VT == MVT::f64) ? RTLIB::UO_F64 : RTLIB::UO_F128;
00165     break;
00166   case ISD::SETO:
00167     LC1 = (VT == MVT::f32) ? RTLIB::O_F32 :
00168           (VT == MVT::f64) ? RTLIB::O_F64 : RTLIB::O_F128;
00169     break;
00170   case ISD::SETONE:
00171     // SETONE = SETOLT | SETOGT
00172     LC1 = (VT == MVT::f32) ? RTLIB::OLT_F32 :
00173           (VT == MVT::f64) ? RTLIB::OLT_F64 : RTLIB::OLT_F128;
00174     LC2 = (VT == MVT::f32) ? RTLIB::OGT_F32 :
00175           (VT == MVT::f64) ? RTLIB::OGT_F64 : RTLIB::OGT_F128;
00176     break;
00177   case ISD::SETUEQ:
00178     LC1 = (VT == MVT::f32) ? RTLIB::UO_F32 :
00179           (VT == MVT::f64) ? RTLIB::UO_F64 : RTLIB::UO_F128;
00180     LC2 = (VT == MVT::f32) ? RTLIB::OEQ_F32 :
00181           (VT == MVT::f64) ? RTLIB::OEQ_F64 : RTLIB::OEQ_F128;
00182     break;
00183   default:
00184     // Invert CC for unordered comparisons
00185     ShouldInvertCC = true;
00186     switch (CCCode) {
00187     case ISD::SETULT:
00188       LC1 = (VT == MVT::f32) ? RTLIB::OGE_F32 :
00189             (VT == MVT::f64) ? RTLIB::OGE_F64 : RTLIB::OGE_F128;
00190       break;
00191     case ISD::SETULE:
00192       LC1 = (VT == MVT::f32) ? RTLIB::OGT_F32 :
00193             (VT == MVT::f64) ? RTLIB::OGT_F64 : RTLIB::OGT_F128;
00194       break;
00195     case ISD::SETUGT:
00196       LC1 = (VT == MVT::f32) ? RTLIB::OLE_F32 :
00197             (VT == MVT::f64) ? RTLIB::OLE_F64 : RTLIB::OLE_F128;
00198       break;
00199     case ISD::SETUGE:
00200       LC1 = (VT == MVT::f32) ? RTLIB::OLT_F32 :
00201             (VT == MVT::f64) ? RTLIB::OLT_F64 : RTLIB::OLT_F128;
00202       break;
00203     default: llvm_unreachable("Do not know how to soften this setcc!");
00204     }
00205   }
00206 
00207   // Use the target specific return value for comparions lib calls.
00208   EVT RetVT = getCmpLibcallReturnType();
00209   SDValue Ops[2] = {NewLHS, NewRHS};
00210   NewLHS = makeLibCall(DAG, LC1, RetVT, Ops, false /*sign irrelevant*/,
00211                        dl).first;
00212   NewRHS = DAG.getConstant(0, dl, RetVT);
00213 
00214   CCCode = getCmpLibcallCC(LC1);
00215   if (ShouldInvertCC)
00216     CCCode = getSetCCInverse(CCCode, /*isInteger=*/true);
00217 
00218   if (LC2 != RTLIB::UNKNOWN_LIBCALL) {
00219     SDValue Tmp = DAG.getNode(
00220         ISD::SETCC, dl,
00221         getSetCCResultType(DAG.getDataLayout(), *DAG.getContext(), RetVT),
00222         NewLHS, NewRHS, DAG.getCondCode(CCCode));
00223     NewLHS = makeLibCall(DAG, LC2, RetVT, Ops, false/*sign irrelevant*/,
00224                          dl).first;
00225     NewLHS = DAG.getNode(
00226         ISD::SETCC, dl,
00227         getSetCCResultType(DAG.getDataLayout(), *DAG.getContext(), RetVT),
00228         NewLHS, NewRHS, DAG.getCondCode(getCmpLibcallCC(LC2)));
00229     NewLHS = DAG.getNode(ISD::OR, dl, Tmp.getValueType(), Tmp, NewLHS);
00230     NewRHS = SDValue();
00231   }
00232 }
00233 
00234 /// Return the entry encoding for a jump table in the current function. The
00235 /// returned value is a member of the MachineJumpTableInfo::JTEntryKind enum.
00236 unsigned TargetLowering::getJumpTableEncoding() const {
00237   // In non-pic modes, just use the address of a block.
00238   if (getTargetMachine().getRelocationModel() != Reloc::PIC_)
00239     return MachineJumpTableInfo::EK_BlockAddress;
00240 
00241   // In PIC mode, if the target supports a GPRel32 directive, use it.
00242   if (getTargetMachine().getMCAsmInfo()->getGPRel32Directive() != nullptr)
00243     return MachineJumpTableInfo::EK_GPRel32BlockAddress;
00244 
00245   // Otherwise, use a label difference.
00246   return MachineJumpTableInfo::EK_LabelDifference32;
00247 }
00248 
00249 SDValue TargetLowering::getPICJumpTableRelocBase(SDValue Table,
00250                                                  SelectionDAG &DAG) const {
00251   // If our PIC model is GP relative, use the global offset table as the base.
00252   unsigned JTEncoding = getJumpTableEncoding();
00253 
00254   if ((JTEncoding == MachineJumpTableInfo::EK_GPRel64BlockAddress) ||
00255       (JTEncoding == MachineJumpTableInfo::EK_GPRel32BlockAddress))
00256     return DAG.getGLOBAL_OFFSET_TABLE(getPointerTy(DAG.getDataLayout()));
00257 
00258   return Table;
00259 }
00260 
00261 /// This returns the relocation base for the given PIC jumptable, the same as
00262 /// getPICJumpTableRelocBase, but as an MCExpr.
00263 const MCExpr *
00264 TargetLowering::getPICJumpTableRelocBaseExpr(const MachineFunction *MF,
00265                                              unsigned JTI,MCContext &Ctx) const{
00266   // The normal PIC reloc base is the label at the start of the jump table.
00267   return MCSymbolRefExpr::create(MF->getJTISymbol(JTI, Ctx), Ctx);
00268 }
00269 
00270 bool
00271 TargetLowering::isOffsetFoldingLegal(const GlobalAddressSDNode *GA) const {
00272   // Assume that everything is safe in static mode.
00273   if (getTargetMachine().getRelocationModel() == Reloc::Static)
00274     return true;
00275 
00276   // In dynamic-no-pic mode, assume that known defined values are safe.
00277   if (getTargetMachine().getRelocationModel() == Reloc::DynamicNoPIC &&
00278       GA && GA->getGlobal()->isStrongDefinitionForLinker())
00279     return true;
00280 
00281   // Otherwise assume nothing is safe.
00282   return false;
00283 }
00284 
00285 //===----------------------------------------------------------------------===//
00286 //  Optimization Methods
00287 //===----------------------------------------------------------------------===//
00288 
00289 /// Check to see if the specified operand of the specified instruction is a
00290 /// constant integer. If so, check to see if there are any bits set in the
00291 /// constant that are not demanded. If so, shrink the constant and return true.
00292 bool TargetLowering::TargetLoweringOpt::ShrinkDemandedConstant(SDValue Op,
00293                                                         const APInt &Demanded) {
00294   SDLoc dl(Op);
00295 
00296   // FIXME: ISD::SELECT, ISD::SELECT_CC
00297   switch (Op.getOpcode()) {
00298   default: break;
00299   case ISD::XOR:
00300   case ISD::AND:
00301   case ISD::OR: {
00302     ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1));
00303     if (!C) return false;
00304 
00305     if (Op.getOpcode() == ISD::XOR &&
00306         (C->getAPIntValue() | (~Demanded)).isAllOnesValue())
00307       return false;
00308 
00309     // if we can expand it to have all bits set, do it
00310     if (C->getAPIntValue().intersects(~Demanded)) {
00311       EVT VT = Op.getValueType();
00312       SDValue New = DAG.getNode(Op.getOpcode(), dl, VT, Op.getOperand(0),
00313                                 DAG.getConstant(Demanded &
00314                                                 C->getAPIntValue(),
00315                                                 dl, VT));
00316       return CombineTo(Op, New);
00317     }
00318 
00319     break;
00320   }
00321   }
00322 
00323   return false;
00324 }
00325 
00326 /// Convert x+y to (VT)((SmallVT)x+(SmallVT)y) if the casts are free.
00327 /// This uses isZExtFree and ZERO_EXTEND for the widening cast, but it could be
00328 /// generalized for targets with other types of implicit widening casts.
00329 bool
00330 TargetLowering::TargetLoweringOpt::ShrinkDemandedOp(SDValue Op,
00331                                                     unsigned BitWidth,
00332                                                     const APInt &Demanded,
00333                                                     SDLoc dl) {
00334   assert(Op.getNumOperands() == 2 &&
00335          "ShrinkDemandedOp only supports binary operators!");
00336   assert(Op.getNode()->getNumValues() == 1 &&
00337          "ShrinkDemandedOp only supports nodes with one result!");
00338 
00339   // Early return, as this function cannot handle vector types.
00340   if (Op.getValueType().isVector())
00341     return false;
00342 
00343   // Don't do this if the node has another user, which may require the
00344   // full value.
00345   if (!Op.getNode()->hasOneUse())
00346     return false;
00347 
00348   // Search for the smallest integer type with free casts to and from
00349   // Op's type. For expedience, just check power-of-2 integer types.
00350   const TargetLowering &TLI = DAG.getTargetLoweringInfo();
00351   unsigned DemandedSize = BitWidth - Demanded.countLeadingZeros();
00352   unsigned SmallVTBits = DemandedSize;
00353   if (!isPowerOf2_32(SmallVTBits))
00354     SmallVTBits = NextPowerOf2(SmallVTBits);
00355   for (; SmallVTBits < BitWidth; SmallVTBits = NextPowerOf2(SmallVTBits)) {
00356     EVT SmallVT = EVT::getIntegerVT(*DAG.getContext(), SmallVTBits);
00357     if (TLI.isTruncateFree(Op.getValueType(), SmallVT) &&
00358         TLI.isZExtFree(SmallVT, Op.getValueType())) {
00359       // We found a type with free casts.
00360       SDValue X = DAG.getNode(Op.getOpcode(), dl, SmallVT,
00361                               DAG.getNode(ISD::TRUNCATE, dl, SmallVT,
00362                                           Op.getNode()->getOperand(0)),
00363                               DAG.getNode(ISD::TRUNCATE, dl, SmallVT,
00364                                           Op.getNode()->getOperand(1)));
00365       bool NeedZext = DemandedSize > SmallVTBits;
00366       SDValue Z = DAG.getNode(NeedZext ? ISD::ZERO_EXTEND : ISD::ANY_EXTEND,
00367                               dl, Op.getValueType(), X);
00368       return CombineTo(Op, Z);
00369     }
00370   }
00371   return false;
00372 }
00373 
00374 /// Look at Op. At this point, we know that only the DemandedMask bits of the
00375 /// result of Op are ever used downstream. If we can use this information to
00376 /// simplify Op, create a new simplified DAG node and return true, returning the
00377 /// original and new nodes in Old and New. Otherwise, analyze the expression and
00378 /// return a mask of KnownOne and KnownZero bits for the expression (used to
00379 /// simplify the caller).  The KnownZero/One bits may only be accurate for those
00380 /// bits in the DemandedMask.
00381 bool TargetLowering::SimplifyDemandedBits(SDValue Op,
00382                                           const APInt &DemandedMask,
00383                                           APInt &KnownZero,
00384                                           APInt &KnownOne,
00385                                           TargetLoweringOpt &TLO,
00386                                           unsigned Depth) const {
00387   unsigned BitWidth = DemandedMask.getBitWidth();
00388   assert(Op.getValueType().getScalarType().getSizeInBits() == BitWidth &&
00389          "Mask size mismatches value type size!");
00390   APInt NewMask = DemandedMask;
00391   SDLoc dl(Op);
00392   auto &DL = TLO.DAG.getDataLayout();
00393 
00394   // Don't know anything.
00395   KnownZero = KnownOne = APInt(BitWidth, 0);
00396 
00397   // Other users may use these bits.
00398   if (!Op.getNode()->hasOneUse()) {
00399     if (Depth != 0) {
00400       // If not at the root, Just compute the KnownZero/KnownOne bits to
00401       // simplify things downstream.
00402       TLO.DAG.computeKnownBits(Op, KnownZero, KnownOne, Depth);
00403       return false;
00404     }
00405     // If this is the root being simplified, allow it to have multiple uses,
00406     // just set the NewMask to all bits.
00407     NewMask = APInt::getAllOnesValue(BitWidth);
00408   } else if (DemandedMask == 0) {
00409     // Not demanding any bits from Op.
00410     if (Op.getOpcode() != ISD::UNDEF)
00411       return TLO.CombineTo(Op, TLO.DAG.getUNDEF(Op.getValueType()));
00412     return false;
00413   } else if (Depth == 6) {        // Limit search depth.
00414     return false;
00415   }
00416 
00417   APInt KnownZero2, KnownOne2, KnownZeroOut, KnownOneOut;
00418   switch (Op.getOpcode()) {
00419   case ISD::Constant:
00420     // We know all of the bits for a constant!
00421     KnownOne = cast<ConstantSDNode>(Op)->getAPIntValue();
00422     KnownZero = ~KnownOne;
00423     return false;   // Don't fall through, will infinitely loop.
00424   case ISD::AND:
00425     // If the RHS is a constant, check to see if the LHS would be zero without
00426     // using the bits from the RHS.  Below, we use knowledge about the RHS to
00427     // simplify the LHS, here we're using information from the LHS to simplify
00428     // the RHS.
00429     if (ConstantSDNode *RHSC = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
00430       APInt LHSZero, LHSOne;
00431       // Do not increment Depth here; that can cause an infinite loop.
00432       TLO.DAG.computeKnownBits(Op.getOperand(0), LHSZero, LHSOne, Depth);
00433       // If the LHS already has zeros where RHSC does, this and is dead.
00434       if ((LHSZero & NewMask) == (~RHSC->getAPIntValue() & NewMask))
00435         return TLO.CombineTo(Op, Op.getOperand(0));
00436       // If any of the set bits in the RHS are known zero on the LHS, shrink
00437       // the constant.
00438       if (TLO.ShrinkDemandedConstant(Op, ~LHSZero & NewMask))
00439         return true;
00440     }
00441 
00442     if (SimplifyDemandedBits(Op.getOperand(1), NewMask, KnownZero,
00443                              KnownOne, TLO, Depth+1))
00444       return true;
00445     assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
00446     if (SimplifyDemandedBits(Op.getOperand(0), ~KnownZero & NewMask,
00447                              KnownZero2, KnownOne2, TLO, Depth+1))
00448       return true;
00449     assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
00450 
00451     // If all of the demanded bits are known one on one side, return the other.
00452     // These bits cannot contribute to the result of the 'and'.
00453     if ((NewMask & ~KnownZero2 & KnownOne) == (~KnownZero2 & NewMask))
00454       return TLO.CombineTo(Op, Op.getOperand(0));
00455     if ((NewMask & ~KnownZero & KnownOne2) == (~KnownZero & NewMask))
00456       return TLO.CombineTo(Op, Op.getOperand(1));
00457     // If all of the demanded bits in the inputs are known zeros, return zero.
00458     if ((NewMask & (KnownZero|KnownZero2)) == NewMask)
00459       return TLO.CombineTo(Op, TLO.DAG.getConstant(0, dl, Op.getValueType()));
00460     // If the RHS is a constant, see if we can simplify it.
00461     if (TLO.ShrinkDemandedConstant(Op, ~KnownZero2 & NewMask))
00462       return true;
00463     // If the operation can be done in a smaller type, do so.
00464     if (TLO.ShrinkDemandedOp(Op, BitWidth, NewMask, dl))
00465       return true;
00466 
00467     // Output known-1 bits are only known if set in both the LHS & RHS.
00468     KnownOne &= KnownOne2;
00469     // Output known-0 are known to be clear if zero in either the LHS | RHS.
00470     KnownZero |= KnownZero2;
00471     break;
00472   case ISD::OR:
00473     if (SimplifyDemandedBits(Op.getOperand(1), NewMask, KnownZero,
00474                              KnownOne, TLO, Depth+1))
00475       return true;
00476     assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
00477     if (SimplifyDemandedBits(Op.getOperand(0), ~KnownOne & NewMask,
00478                              KnownZero2, KnownOne2, TLO, Depth+1))
00479       return true;
00480     assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
00481 
00482     // If all of the demanded bits are known zero on one side, return the other.
00483     // These bits cannot contribute to the result of the 'or'.
00484     if ((NewMask & ~KnownOne2 & KnownZero) == (~KnownOne2 & NewMask))
00485       return TLO.CombineTo(Op, Op.getOperand(0));
00486     if ((NewMask & ~KnownOne & KnownZero2) == (~KnownOne & NewMask))
00487       return TLO.CombineTo(Op, Op.getOperand(1));
00488     // If all of the potentially set bits on one side are known to be set on
00489     // the other side, just use the 'other' side.
00490     if ((NewMask & ~KnownZero & KnownOne2) == (~KnownZero & NewMask))
00491       return TLO.CombineTo(Op, Op.getOperand(0));
00492     if ((NewMask & ~KnownZero2 & KnownOne) == (~KnownZero2 & NewMask))
00493       return TLO.CombineTo(Op, Op.getOperand(1));
00494     // If the RHS is a constant, see if we can simplify it.
00495     if (TLO.ShrinkDemandedConstant(Op, NewMask))
00496       return true;
00497     // If the operation can be done in a smaller type, do so.
00498     if (TLO.ShrinkDemandedOp(Op, BitWidth, NewMask, dl))
00499       return true;
00500 
00501     // Output known-0 bits are only known if clear in both the LHS & RHS.
00502     KnownZero &= KnownZero2;
00503     // Output known-1 are known to be set if set in either the LHS | RHS.
00504     KnownOne |= KnownOne2;
00505     break;
00506   case ISD::XOR:
00507     if (SimplifyDemandedBits(Op.getOperand(1), NewMask, KnownZero,
00508                              KnownOne, TLO, Depth+1))
00509       return true;
00510     assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
00511     if (SimplifyDemandedBits(Op.getOperand(0), NewMask, KnownZero2,
00512                              KnownOne2, TLO, Depth+1))
00513       return true;
00514     assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
00515 
00516     // If all of the demanded bits are known zero on one side, return the other.
00517     // These bits cannot contribute to the result of the 'xor'.
00518     if ((KnownZero & NewMask) == NewMask)
00519       return TLO.CombineTo(Op, Op.getOperand(0));
00520     if ((KnownZero2 & NewMask) == NewMask)
00521       return TLO.CombineTo(Op, Op.getOperand(1));
00522     // If the operation can be done in a smaller type, do so.
00523     if (TLO.ShrinkDemandedOp(Op, BitWidth, NewMask, dl))
00524       return true;
00525 
00526     // If all of the unknown bits are known to be zero on one side or the other
00527     // (but not both) turn this into an *inclusive* or.
00528     //    e.g. (A & C1)^(B & C2) -> (A & C1)|(B & C2) iff C1&C2 == 0
00529     if ((NewMask & ~KnownZero & ~KnownZero2) == 0)
00530       return TLO.CombineTo(Op, TLO.DAG.getNode(ISD::OR, dl, Op.getValueType(),
00531                                                Op.getOperand(0),
00532                                                Op.getOperand(1)));
00533 
00534     // Output known-0 bits are known if clear or set in both the LHS & RHS.
00535     KnownZeroOut = (KnownZero & KnownZero2) | (KnownOne & KnownOne2);
00536     // Output known-1 are known to be set if set in only one of the LHS, RHS.
00537     KnownOneOut = (KnownZero & KnownOne2) | (KnownOne & KnownZero2);
00538 
00539     // If all of the demanded bits on one side are known, and all of the set
00540     // bits on that side are also known to be set on the other side, turn this
00541     // into an AND, as we know the bits will be cleared.
00542     //    e.g. (X | C1) ^ C2 --> (X | C1) & ~C2 iff (C1&C2) == C2
00543     // NB: it is okay if more bits are known than are requested
00544     if ((NewMask & (KnownZero|KnownOne)) == NewMask) { // all known on one side
00545       if (KnownOne == KnownOne2) { // set bits are the same on both sides
00546         EVT VT = Op.getValueType();
00547         SDValue ANDC = TLO.DAG.getConstant(~KnownOne & NewMask, dl, VT);
00548         return TLO.CombineTo(Op, TLO.DAG.getNode(ISD::AND, dl, VT,
00549                                                  Op.getOperand(0), ANDC));
00550       }
00551     }
00552 
00553     // If the RHS is a constant, see if we can simplify it.
00554     // for XOR, we prefer to force bits to 1 if they will make a -1.
00555     // if we can't force bits, try to shrink constant
00556     if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
00557       APInt Expanded = C->getAPIntValue() | (~NewMask);
00558       // if we can expand it to have all bits set, do it
00559       if (Expanded.isAllOnesValue()) {
00560         if (Expanded != C->getAPIntValue()) {
00561           EVT VT = Op.getValueType();
00562           SDValue New = TLO.DAG.getNode(Op.getOpcode(), dl,VT, Op.getOperand(0),
00563                                         TLO.DAG.getConstant(Expanded, dl, VT));
00564           return TLO.CombineTo(Op, New);
00565         }
00566         // if it already has all the bits set, nothing to change
00567         // but don't shrink either!
00568       } else if (TLO.ShrinkDemandedConstant(Op, NewMask)) {
00569         return true;
00570       }
00571     }
00572 
00573     KnownZero = KnownZeroOut;
00574     KnownOne  = KnownOneOut;
00575     break;
00576   case ISD::SELECT:
00577     if (SimplifyDemandedBits(Op.getOperand(2), NewMask, KnownZero,
00578                              KnownOne, TLO, Depth+1))
00579       return true;
00580     if (SimplifyDemandedBits(Op.getOperand(1), NewMask, KnownZero2,
00581                              KnownOne2, TLO, Depth+1))
00582       return true;
00583     assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
00584     assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
00585 
00586     // If the operands are constants, see if we can simplify them.
00587     if (TLO.ShrinkDemandedConstant(Op, NewMask))
00588       return true;
00589 
00590     // Only known if known in both the LHS and RHS.
00591     KnownOne &= KnownOne2;
00592     KnownZero &= KnownZero2;
00593     break;
00594   case ISD::SELECT_CC:
00595     if (SimplifyDemandedBits(Op.getOperand(3), NewMask, KnownZero,
00596                              KnownOne, TLO, Depth+1))
00597       return true;
00598     if (SimplifyDemandedBits(Op.getOperand(2), NewMask, KnownZero2,
00599                              KnownOne2, TLO, Depth+1))
00600       return true;
00601     assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
00602     assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
00603 
00604     // If the operands are constants, see if we can simplify them.
00605     if (TLO.ShrinkDemandedConstant(Op, NewMask))
00606       return true;
00607 
00608     // Only known if known in both the LHS and RHS.
00609     KnownOne &= KnownOne2;
00610     KnownZero &= KnownZero2;
00611     break;
00612   case ISD::SHL:
00613     if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
00614       unsigned ShAmt = SA->getZExtValue();
00615       SDValue InOp = Op.getOperand(0);
00616 
00617       // If the shift count is an invalid immediate, don't do anything.
00618       if (ShAmt >= BitWidth)
00619         break;
00620 
00621       // If this is ((X >>u C1) << ShAmt), see if we can simplify this into a
00622       // single shift.  We can do this if the bottom bits (which are shifted
00623       // out) are never demanded.
00624       if (InOp.getOpcode() == ISD::SRL &&
00625           isa<ConstantSDNode>(InOp.getOperand(1))) {
00626         if (ShAmt && (NewMask & APInt::getLowBitsSet(BitWidth, ShAmt)) == 0) {
00627           unsigned C1= cast<ConstantSDNode>(InOp.getOperand(1))->getZExtValue();
00628           unsigned Opc = ISD::SHL;
00629           int Diff = ShAmt-C1;
00630           if (Diff < 0) {
00631             Diff = -Diff;
00632             Opc = ISD::SRL;
00633           }
00634 
00635           SDValue NewSA =
00636             TLO.DAG.getConstant(Diff, dl, Op.getOperand(1).getValueType());
00637           EVT VT = Op.getValueType();
00638           return TLO.CombineTo(Op, TLO.DAG.getNode(Opc, dl, VT,
00639                                                    InOp.getOperand(0), NewSA));
00640         }
00641       }
00642 
00643       if (SimplifyDemandedBits(InOp, NewMask.lshr(ShAmt),
00644                                KnownZero, KnownOne, TLO, Depth+1))
00645         return true;
00646 
00647       // Convert (shl (anyext x, c)) to (anyext (shl x, c)) if the high bits
00648       // are not demanded. This will likely allow the anyext to be folded away.
00649       if (InOp.getNode()->getOpcode() == ISD::ANY_EXTEND) {
00650         SDValue InnerOp = InOp.getNode()->getOperand(0);
00651         EVT InnerVT = InnerOp.getValueType();
00652         unsigned InnerBits = InnerVT.getSizeInBits();
00653         if (ShAmt < InnerBits && NewMask.lshr(InnerBits) == 0 &&
00654             isTypeDesirableForOp(ISD::SHL, InnerVT)) {
00655           EVT ShTy = getShiftAmountTy(InnerVT, DL);
00656           if (!APInt(BitWidth, ShAmt).isIntN(ShTy.getSizeInBits()))
00657             ShTy = InnerVT;
00658           SDValue NarrowShl =
00659             TLO.DAG.getNode(ISD::SHL, dl, InnerVT, InnerOp,
00660                             TLO.DAG.getConstant(ShAmt, dl, ShTy));
00661           return
00662             TLO.CombineTo(Op,
00663                           TLO.DAG.getNode(ISD::ANY_EXTEND, dl, Op.getValueType(),
00664                                           NarrowShl));
00665         }
00666         // Repeat the SHL optimization above in cases where an extension
00667         // intervenes: (shl (anyext (shr x, c1)), c2) to
00668         // (shl (anyext x), c2-c1).  This requires that the bottom c1 bits
00669         // aren't demanded (as above) and that the shifted upper c1 bits of
00670         // x aren't demanded.
00671         if (InOp.hasOneUse() &&
00672             InnerOp.getOpcode() == ISD::SRL &&
00673             InnerOp.hasOneUse() &&
00674             isa<ConstantSDNode>(InnerOp.getOperand(1))) {
00675           uint64_t InnerShAmt = cast<ConstantSDNode>(InnerOp.getOperand(1))
00676             ->getZExtValue();
00677           if (InnerShAmt < ShAmt &&
00678               InnerShAmt < InnerBits &&
00679               NewMask.lshr(InnerBits - InnerShAmt + ShAmt) == 0 &&
00680               NewMask.trunc(ShAmt) == 0) {
00681             SDValue NewSA =
00682               TLO.DAG.getConstant(ShAmt - InnerShAmt, dl,
00683                                   Op.getOperand(1).getValueType());
00684             EVT VT = Op.getValueType();
00685             SDValue NewExt = TLO.DAG.getNode(ISD::ANY_EXTEND, dl, VT,
00686                                              InnerOp.getOperand(0));
00687             return TLO.CombineTo(Op, TLO.DAG.getNode(ISD::SHL, dl, VT,
00688                                                      NewExt, NewSA));
00689           }
00690         }
00691       }
00692 
00693       KnownZero <<= SA->getZExtValue();
00694       KnownOne  <<= SA->getZExtValue();
00695       // low bits known zero.
00696       KnownZero |= APInt::getLowBitsSet(BitWidth, SA->getZExtValue());
00697     }
00698     break;
00699   case ISD::SRL:
00700     if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
00701       EVT VT = Op.getValueType();
00702       unsigned ShAmt = SA->getZExtValue();
00703       unsigned VTSize = VT.getSizeInBits();
00704       SDValue InOp = Op.getOperand(0);
00705 
00706       // If the shift count is an invalid immediate, don't do anything.
00707       if (ShAmt >= BitWidth)
00708         break;
00709 
00710       APInt InDemandedMask = (NewMask << ShAmt);
00711 
00712       // If the shift is exact, then it does demand the low bits (and knows that
00713       // they are zero).
00714       if (cast<BinaryWithFlagsSDNode>(Op)->Flags.hasExact())
00715         InDemandedMask |= APInt::getLowBitsSet(BitWidth, ShAmt);
00716 
00717       // If this is ((X << C1) >>u ShAmt), see if we can simplify this into a
00718       // single shift.  We can do this if the top bits (which are shifted out)
00719       // are never demanded.
00720       if (InOp.getOpcode() == ISD::SHL &&
00721           isa<ConstantSDNode>(InOp.getOperand(1))) {
00722         if (ShAmt && (NewMask & APInt::getHighBitsSet(VTSize, ShAmt)) == 0) {
00723           unsigned C1= cast<ConstantSDNode>(InOp.getOperand(1))->getZExtValue();
00724           unsigned Opc = ISD::SRL;
00725           int Diff = ShAmt-C1;
00726           if (Diff < 0) {
00727             Diff = -Diff;
00728             Opc = ISD::SHL;
00729           }
00730 
00731           SDValue NewSA =
00732             TLO.DAG.getConstant(Diff, dl, Op.getOperand(1).getValueType());
00733           return TLO.CombineTo(Op, TLO.DAG.getNode(Opc, dl, VT,
00734                                                    InOp.getOperand(0), NewSA));
00735         }
00736       }
00737 
00738       // Compute the new bits that are at the top now.
00739       if (SimplifyDemandedBits(InOp, InDemandedMask,
00740                                KnownZero, KnownOne, TLO, Depth+1))
00741         return true;
00742       assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
00743       KnownZero = KnownZero.lshr(ShAmt);
00744       KnownOne  = KnownOne.lshr(ShAmt);
00745 
00746       APInt HighBits = APInt::getHighBitsSet(BitWidth, ShAmt);
00747       KnownZero |= HighBits;  // High bits known zero.
00748     }
00749     break;
00750   case ISD::SRA:
00751     // If this is an arithmetic shift right and only the low-bit is set, we can
00752     // always convert this into a logical shr, even if the shift amount is
00753     // variable.  The low bit of the shift cannot be an input sign bit unless
00754     // the shift amount is >= the size of the datatype, which is undefined.
00755     if (NewMask == 1)
00756       return TLO.CombineTo(Op,
00757                            TLO.DAG.getNode(ISD::SRL, dl, Op.getValueType(),
00758                                            Op.getOperand(0), Op.getOperand(1)));
00759 
00760     if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
00761       EVT VT = Op.getValueType();
00762       unsigned ShAmt = SA->getZExtValue();
00763 
00764       // If the shift count is an invalid immediate, don't do anything.
00765       if (ShAmt >= BitWidth)
00766         break;
00767 
00768       APInt InDemandedMask = (NewMask << ShAmt);
00769 
00770       // If the shift is exact, then it does demand the low bits (and knows that
00771       // they are zero).
00772       if (cast<BinaryWithFlagsSDNode>(Op)->Flags.hasExact())
00773         InDemandedMask |= APInt::getLowBitsSet(BitWidth, ShAmt);
00774 
00775       // If any of the demanded bits are produced by the sign extension, we also
00776       // demand the input sign bit.
00777       APInt HighBits = APInt::getHighBitsSet(BitWidth, ShAmt);
00778       if (HighBits.intersects(NewMask))
00779         InDemandedMask |= APInt::getSignBit(VT.getScalarType().getSizeInBits());
00780 
00781       if (SimplifyDemandedBits(Op.getOperand(0), InDemandedMask,
00782                                KnownZero, KnownOne, TLO, Depth+1))
00783         return true;
00784       assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
00785       KnownZero = KnownZero.lshr(ShAmt);
00786       KnownOne  = KnownOne.lshr(ShAmt);
00787 
00788       // Handle the sign bit, adjusted to where it is now in the mask.
00789       APInt SignBit = APInt::getSignBit(BitWidth).lshr(ShAmt);
00790 
00791       // If the input sign bit is known to be zero, or if none of the top bits
00792       // are demanded, turn this into an unsigned shift right.
00793       if (KnownZero.intersects(SignBit) || (HighBits & ~NewMask) == HighBits) {
00794         SDNodeFlags Flags;
00795         Flags.setExact(cast<BinaryWithFlagsSDNode>(Op)->Flags.hasExact());
00796         return TLO.CombineTo(Op,
00797                              TLO.DAG.getNode(ISD::SRL, dl, VT, Op.getOperand(0),
00798                                              Op.getOperand(1), &Flags));
00799       }
00800 
00801       int Log2 = NewMask.exactLogBase2();
00802       if (Log2 >= 0) {
00803         // The bit must come from the sign.
00804         SDValue NewSA =
00805           TLO.DAG.getConstant(BitWidth - 1 - Log2, dl,
00806                               Op.getOperand(1).getValueType());
00807         return TLO.CombineTo(Op, TLO.DAG.getNode(ISD::SRL, dl, VT,
00808                                                  Op.getOperand(0), NewSA));
00809       }
00810 
00811       if (KnownOne.intersects(SignBit))
00812         // New bits are known one.
00813         KnownOne |= HighBits;
00814     }
00815     break;
00816   case ISD::SIGN_EXTEND_INREG: {
00817     EVT ExVT = cast<VTSDNode>(Op.getOperand(1))->getVT();
00818 
00819     APInt MsbMask = APInt::getHighBitsSet(BitWidth, 1);
00820     // If we only care about the highest bit, don't bother shifting right.
00821     if (MsbMask == NewMask) {
00822       unsigned ShAmt = ExVT.getScalarType().getSizeInBits();
00823       SDValue InOp = Op.getOperand(0);
00824       unsigned VTBits = Op->getValueType(0).getScalarType().getSizeInBits();
00825       bool AlreadySignExtended =
00826         TLO.DAG.ComputeNumSignBits(InOp) >= VTBits-ShAmt+1;
00827       // However if the input is already sign extended we expect the sign
00828       // extension to be dropped altogether later and do not simplify.
00829       if (!AlreadySignExtended) {
00830         // Compute the correct shift amount type, which must be getShiftAmountTy
00831         // for scalar types after legalization.
00832         EVT ShiftAmtTy = Op.getValueType();
00833         if (TLO.LegalTypes() && !ShiftAmtTy.isVector())
00834           ShiftAmtTy = getShiftAmountTy(ShiftAmtTy, DL);
00835 
00836         SDValue ShiftAmt = TLO.DAG.getConstant(BitWidth - ShAmt, dl,
00837                                                ShiftAmtTy);
00838         return TLO.CombineTo(Op, TLO.DAG.getNode(ISD::SHL, dl,
00839                                                  Op.getValueType(), InOp,
00840                                                  ShiftAmt));
00841       }
00842     }
00843 
00844     // Sign extension.  Compute the demanded bits in the result that are not
00845     // present in the input.
00846     APInt NewBits =
00847       APInt::getHighBitsSet(BitWidth,
00848                             BitWidth - ExVT.getScalarType().getSizeInBits());
00849 
00850     // If none of the extended bits are demanded, eliminate the sextinreg.
00851     if ((NewBits & NewMask) == 0)
00852       return TLO.CombineTo(Op, Op.getOperand(0));
00853 
00854     APInt InSignBit =
00855       APInt::getSignBit(ExVT.getScalarType().getSizeInBits()).zext(BitWidth);
00856     APInt InputDemandedBits =
00857       APInt::getLowBitsSet(BitWidth,
00858                            ExVT.getScalarType().getSizeInBits()) &
00859       NewMask;
00860 
00861     // Since the sign extended bits are demanded, we know that the sign
00862     // bit is demanded.
00863     InputDemandedBits |= InSignBit;
00864 
00865     if (SimplifyDemandedBits(Op.getOperand(0), InputDemandedBits,
00866                              KnownZero, KnownOne, TLO, Depth+1))
00867       return true;
00868     assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
00869 
00870     // If the sign bit of the input is known set or clear, then we know the
00871     // top bits of the result.
00872 
00873     // If the input sign bit is known zero, convert this into a zero extension.
00874     if (KnownZero.intersects(InSignBit))
00875       return TLO.CombineTo(Op,
00876                           TLO.DAG.getZeroExtendInReg(Op.getOperand(0),dl,ExVT));
00877 
00878     if (KnownOne.intersects(InSignBit)) {    // Input sign bit known set
00879       KnownOne |= NewBits;
00880       KnownZero &= ~NewBits;
00881     } else {                       // Input sign bit unknown
00882       KnownZero &= ~NewBits;
00883       KnownOne &= ~NewBits;
00884     }
00885     break;
00886   }
00887   case ISD::BUILD_PAIR: {
00888     EVT HalfVT = Op.getOperand(0).getValueType();
00889     unsigned HalfBitWidth = HalfVT.getScalarSizeInBits();
00890 
00891     APInt MaskLo = NewMask.getLoBits(HalfBitWidth).trunc(HalfBitWidth);
00892     APInt MaskHi = NewMask.getHiBits(HalfBitWidth).trunc(HalfBitWidth);
00893 
00894     APInt KnownZeroLo, KnownOneLo;
00895     APInt KnownZeroHi, KnownOneHi;
00896 
00897     if (SimplifyDemandedBits(Op.getOperand(0), MaskLo, KnownZeroLo,
00898                              KnownOneLo, TLO, Depth + 1))
00899       return true;
00900 
00901     if (SimplifyDemandedBits(Op.getOperand(1), MaskHi, KnownZeroHi,
00902                              KnownOneHi, TLO, Depth + 1))
00903       return true;
00904 
00905     KnownZero = KnownZeroLo.zext(BitWidth) |
00906                 KnownZeroHi.zext(BitWidth).shl(HalfBitWidth);
00907 
00908     KnownOne = KnownOneLo.zext(BitWidth) |
00909                KnownOneHi.zext(BitWidth).shl(HalfBitWidth);
00910     break;
00911   }
00912   case ISD::ZERO_EXTEND: {
00913     unsigned OperandBitWidth =
00914       Op.getOperand(0).getValueType().getScalarType().getSizeInBits();
00915     APInt InMask = NewMask.trunc(OperandBitWidth);
00916 
00917     // If none of the top bits are demanded, convert this into an any_extend.
00918     APInt NewBits =
00919       APInt::getHighBitsSet(BitWidth, BitWidth - OperandBitWidth) & NewMask;
00920     if (!NewBits.intersects(NewMask))
00921       return TLO.CombineTo(Op, TLO.DAG.getNode(ISD::ANY_EXTEND, dl,
00922                                                Op.getValueType(),
00923                                                Op.getOperand(0)));
00924 
00925     if (SimplifyDemandedBits(Op.getOperand(0), InMask,
00926                              KnownZero, KnownOne, TLO, Depth+1))
00927       return true;
00928     assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
00929     KnownZero = KnownZero.zext(BitWidth);
00930     KnownOne = KnownOne.zext(BitWidth);
00931     KnownZero |= NewBits;
00932     break;
00933   }
00934   case ISD::SIGN_EXTEND: {
00935     EVT InVT = Op.getOperand(0).getValueType();
00936     unsigned InBits = InVT.getScalarType().getSizeInBits();
00937     APInt InMask    = APInt::getLowBitsSet(BitWidth, InBits);
00938     APInt InSignBit = APInt::getBitsSet(BitWidth, InBits - 1, InBits);
00939     APInt NewBits   = ~InMask & NewMask;
00940 
00941     // If none of the top bits are demanded, convert this into an any_extend.
00942     if (NewBits == 0)
00943       return TLO.CombineTo(Op,TLO.DAG.getNode(ISD::ANY_EXTEND, dl,
00944                                               Op.getValueType(),
00945                                               Op.getOperand(0)));
00946 
00947     // Since some of the sign extended bits are demanded, we know that the sign
00948     // bit is demanded.
00949     APInt InDemandedBits = InMask & NewMask;
00950     InDemandedBits |= InSignBit;
00951     InDemandedBits = InDemandedBits.trunc(InBits);
00952 
00953     if (SimplifyDemandedBits(Op.getOperand(0), InDemandedBits, KnownZero,
00954                              KnownOne, TLO, Depth+1))
00955       return true;
00956     KnownZero = KnownZero.zext(BitWidth);
00957     KnownOne = KnownOne.zext(BitWidth);
00958 
00959     // If the sign bit is known zero, convert this to a zero extend.
00960     if (KnownZero.intersects(InSignBit))
00961       return TLO.CombineTo(Op, TLO.DAG.getNode(ISD::ZERO_EXTEND, dl,
00962                                                Op.getValueType(),
00963                                                Op.getOperand(0)));
00964 
00965     // If the sign bit is known one, the top bits match.
00966     if (KnownOne.intersects(InSignBit)) {
00967       KnownOne |= NewBits;
00968       assert((KnownZero & NewBits) == 0);
00969     } else {   // Otherwise, top bits aren't known.
00970       assert((KnownOne & NewBits) == 0);
00971       assert((KnownZero & NewBits) == 0);
00972     }
00973     break;
00974   }
00975   case ISD::ANY_EXTEND: {
00976     unsigned OperandBitWidth =
00977       Op.getOperand(0).getValueType().getScalarType().getSizeInBits();
00978     APInt InMask = NewMask.trunc(OperandBitWidth);
00979     if (SimplifyDemandedBits(Op.getOperand(0), InMask,
00980                              KnownZero, KnownOne, TLO, Depth+1))
00981       return true;
00982     assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
00983     KnownZero = KnownZero.zext(BitWidth);
00984     KnownOne = KnownOne.zext(BitWidth);
00985     break;
00986   }
00987   case ISD::TRUNCATE: {
00988     // Simplify the input, using demanded bit information, and compute the known
00989     // zero/one bits live out.
00990     unsigned OperandBitWidth =
00991       Op.getOperand(0).getValueType().getScalarType().getSizeInBits();
00992     APInt TruncMask = NewMask.zext(OperandBitWidth);
00993     if (SimplifyDemandedBits(Op.getOperand(0), TruncMask,
00994                              KnownZero, KnownOne, TLO, Depth+1))
00995       return true;
00996     KnownZero = KnownZero.trunc(BitWidth);
00997     KnownOne = KnownOne.trunc(BitWidth);
00998 
00999     // If the input is only used by this truncate, see if we can shrink it based
01000     // on the known demanded bits.
01001     if (Op.getOperand(0).getNode()->hasOneUse()) {
01002       SDValue In = Op.getOperand(0);
01003       switch (In.getOpcode()) {
01004       default: break;
01005       case ISD::SRL:
01006         // Shrink SRL by a constant if none of the high bits shifted in are
01007         // demanded.
01008         if (TLO.LegalTypes() &&
01009             !isTypeDesirableForOp(ISD::SRL, Op.getValueType()))
01010           // Do not turn (vt1 truncate (vt2 srl)) into (vt1 srl) if vt1 is
01011           // undesirable.
01012           break;
01013         ConstantSDNode *ShAmt = dyn_cast<ConstantSDNode>(In.getOperand(1));
01014         if (!ShAmt)
01015           break;
01016         SDValue Shift = In.getOperand(1);
01017         if (TLO.LegalTypes()) {
01018           uint64_t ShVal = ShAmt->getZExtValue();
01019           Shift = TLO.DAG.getConstant(ShVal, dl,
01020                                       getShiftAmountTy(Op.getValueType(), DL));
01021         }
01022 
01023         APInt HighBits = APInt::getHighBitsSet(OperandBitWidth,
01024                                                OperandBitWidth - BitWidth);
01025         HighBits = HighBits.lshr(ShAmt->getZExtValue()).trunc(BitWidth);
01026 
01027         if (ShAmt->getZExtValue() < BitWidth && !(HighBits & NewMask)) {
01028           // None of the shifted in bits are needed.  Add a truncate of the
01029           // shift input, then shift it.
01030           SDValue NewTrunc = TLO.DAG.getNode(ISD::TRUNCATE, dl,
01031                                              Op.getValueType(),
01032                                              In.getOperand(0));
01033           return TLO.CombineTo(Op, TLO.DAG.getNode(ISD::SRL, dl,
01034                                                    Op.getValueType(),
01035                                                    NewTrunc,
01036                                                    Shift));
01037         }
01038         break;
01039       }
01040     }
01041 
01042     assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
01043     break;
01044   }
01045   case ISD::AssertZext: {
01046     // AssertZext demands all of the high bits, plus any of the low bits
01047     // demanded by its users.
01048     EVT VT = cast<VTSDNode>(Op.getOperand(1))->getVT();
01049     APInt InMask = APInt::getLowBitsSet(BitWidth,
01050                                         VT.getSizeInBits());
01051     if (SimplifyDemandedBits(Op.getOperand(0), ~InMask | NewMask,
01052                              KnownZero, KnownOne, TLO, Depth+1))
01053       return true;
01054     assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
01055 
01056     KnownZero |= ~InMask & NewMask;
01057     break;
01058   }
01059   case ISD::BITCAST:
01060     // If this is an FP->Int bitcast and if the sign bit is the only
01061     // thing demanded, turn this into a FGETSIGN.
01062     if (!TLO.LegalOperations() &&
01063         !Op.getValueType().isVector() &&
01064         !Op.getOperand(0).getValueType().isVector() &&
01065         NewMask == APInt::getSignBit(Op.getValueType().getSizeInBits()) &&
01066         Op.getOperand(0).getValueType().isFloatingPoint()) {
01067       bool OpVTLegal = isOperationLegalOrCustom(ISD::FGETSIGN, Op.getValueType());
01068       bool i32Legal  = isOperationLegalOrCustom(ISD::FGETSIGN, MVT::i32);
01069       if ((OpVTLegal || i32Legal) && Op.getValueType().isSimple() &&
01070            Op.getOperand(0).getValueType() != MVT::f128) {
01071         // Cannot eliminate/lower SHL for f128 yet.
01072         EVT Ty = OpVTLegal ? Op.getValueType() : MVT::i32;
01073         // Make a FGETSIGN + SHL to move the sign bit into the appropriate
01074         // place.  We expect the SHL to be eliminated by other optimizations.
01075         SDValue Sign = TLO.DAG.getNode(ISD::FGETSIGN, dl, Ty, Op.getOperand(0));
01076         unsigned OpVTSizeInBits = Op.getValueType().getSizeInBits();
01077         if (!OpVTLegal && OpVTSizeInBits > 32)
01078           Sign = TLO.DAG.getNode(ISD::ZERO_EXTEND, dl, Op.getValueType(), Sign);
01079         unsigned ShVal = Op.getValueType().getSizeInBits()-1;
01080         SDValue ShAmt = TLO.DAG.getConstant(ShVal, dl, Op.getValueType());
01081         return TLO.CombineTo(Op, TLO.DAG.getNode(ISD::SHL, dl,
01082                                                  Op.getValueType(),
01083                                                  Sign, ShAmt));
01084       }
01085     }
01086     break;
01087   case ISD::ADD:
01088   case ISD::MUL:
01089   case ISD::SUB: {
01090     // Add, Sub, and Mul don't demand any bits in positions beyond that
01091     // of the highest bit demanded of them.
01092     APInt LoMask = APInt::getLowBitsSet(BitWidth,
01093                                         BitWidth - NewMask.countLeadingZeros());
01094     if (SimplifyDemandedBits(Op.getOperand(0), LoMask, KnownZero2,
01095                              KnownOne2, TLO, Depth+1))
01096       return true;
01097     if (SimplifyDemandedBits(Op.getOperand(1), LoMask, KnownZero2,
01098                              KnownOne2, TLO, Depth+1))
01099       return true;
01100     // See if the operation should be performed at a smaller bit width.
01101     if (TLO.ShrinkDemandedOp(Op, BitWidth, NewMask, dl))
01102       return true;
01103   }
01104   // FALL THROUGH
01105   default:
01106     // Just use computeKnownBits to compute output bits.
01107     TLO.DAG.computeKnownBits(Op, KnownZero, KnownOne, Depth);
01108     break;
01109   }
01110 
01111   // If we know the value of all of the demanded bits, return this as a
01112   // constant.
01113   if ((NewMask & (KnownZero|KnownOne)) == NewMask) {
01114     // Avoid folding to a constant if any OpaqueConstant is involved.
01115     const SDNode *N = Op.getNode();
01116     for (SDNodeIterator I = SDNodeIterator::begin(N),
01117          E = SDNodeIterator::end(N); I != E; ++I) {
01118       SDNode *Op = *I;
01119       if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op))
01120         if (C->isOpaque())
01121           return false;
01122     }
01123     return TLO.CombineTo(Op,
01124                          TLO.DAG.getConstant(KnownOne, dl, Op.getValueType()));
01125   }
01126 
01127   return false;
01128 }
01129 
01130 /// Determine which of the bits specified in Mask are known to be either zero or
01131 /// one and return them in the KnownZero/KnownOne bitsets.
01132 void TargetLowering::computeKnownBitsForTargetNode(const SDValue Op,
01133                                                    APInt &KnownZero,
01134                                                    APInt &KnownOne,
01135                                                    const SelectionDAG &DAG,
01136                                                    unsigned Depth) const {
01137   assert((Op.getOpcode() >= ISD::BUILTIN_OP_END ||
01138           Op.getOpcode() == ISD::INTRINSIC_WO_CHAIN ||
01139           Op.getOpcode() == ISD::INTRINSIC_W_CHAIN ||
01140           Op.getOpcode() == ISD::INTRINSIC_VOID) &&
01141          "Should use MaskedValueIsZero if you don't know whether Op"
01142          " is a target node!");
01143   KnownZero = KnownOne = APInt(KnownOne.getBitWidth(), 0);
01144 }
01145 
01146 /// This method can be implemented by targets that want to expose additional
01147 /// information about sign bits to the DAG Combiner.
01148 unsigned TargetLowering::ComputeNumSignBitsForTargetNode(SDValue Op,
01149                                                          const SelectionDAG &,
01150                                                          unsigned Depth) const {
01151   assert((Op.getOpcode() >= ISD::BUILTIN_OP_END ||
01152           Op.getOpcode() == ISD::INTRINSIC_WO_CHAIN ||
01153           Op.getOpcode() == ISD::INTRINSIC_W_CHAIN ||
01154           Op.getOpcode() == ISD::INTRINSIC_VOID) &&
01155          "Should use ComputeNumSignBits if you don't know whether Op"
01156          " is a target node!");
01157   return 1;
01158 }
01159 
01160 /// Test if the given value is known to have exactly one bit set. This differs
01161 /// from computeKnownBits in that it doesn't need to determine which bit is set.
01162 static bool ValueHasExactlyOneBitSet(SDValue Val, const SelectionDAG &DAG) {
01163   // A left-shift of a constant one will have exactly one bit set, because
01164   // shifting the bit off the end is undefined.
01165   if (Val.getOpcode() == ISD::SHL)
01166     if (ConstantSDNode *C =
01167          dyn_cast<ConstantSDNode>(Val.getNode()->getOperand(0)))
01168       if (C->getAPIntValue() == 1)
01169         return true;
01170 
01171   // Similarly, a right-shift of a constant sign-bit will have exactly
01172   // one bit set.
01173   if (Val.getOpcode() == ISD::SRL)
01174     if (ConstantSDNode *C =
01175          dyn_cast<ConstantSDNode>(Val.getNode()->getOperand(0)))
01176       if (C->getAPIntValue().isSignBit())
01177         return true;
01178 
01179   // More could be done here, though the above checks are enough
01180   // to handle some common cases.
01181 
01182   // Fall back to computeKnownBits to catch other known cases.
01183   EVT OpVT = Val.getValueType();
01184   unsigned BitWidth = OpVT.getScalarType().getSizeInBits();
01185   APInt KnownZero, KnownOne;
01186   DAG.computeKnownBits(Val, KnownZero, KnownOne);
01187   return (KnownZero.countPopulation() == BitWidth - 1) &&
01188          (KnownOne.countPopulation() == 1);
01189 }
01190 
01191 bool TargetLowering::isConstTrueVal(const SDNode *N) const {
01192   if (!N)
01193     return false;
01194 
01195   const ConstantSDNode *CN = dyn_cast<ConstantSDNode>(N);
01196   if (!CN) {
01197     const BuildVectorSDNode *BV = dyn_cast<BuildVectorSDNode>(N);
01198     if (!BV)
01199       return false;
01200 
01201     BitVector UndefElements;
01202     CN = BV->getConstantSplatNode(&UndefElements);
01203     // Only interested in constant splats, and we don't try to handle undef
01204     // elements in identifying boolean constants.
01205     if (!CN || UndefElements.none())
01206       return false;
01207   }
01208 
01209   switch (getBooleanContents(N->getValueType(0))) {
01210   case UndefinedBooleanContent:
01211     return CN->getAPIntValue()[0];
01212   case ZeroOrOneBooleanContent:
01213     return CN->isOne();
01214   case ZeroOrNegativeOneBooleanContent:
01215     return CN->isAllOnesValue();
01216   }
01217 
01218   llvm_unreachable("Invalid boolean contents");
01219 }
01220 
01221 bool TargetLowering::isConstFalseVal(const SDNode *N) const {
01222   if (!N)
01223     return false;
01224 
01225   const ConstantSDNode *CN = dyn_cast<ConstantSDNode>(N);
01226   if (!CN) {
01227     const BuildVectorSDNode *BV = dyn_cast<BuildVectorSDNode>(N);
01228     if (!BV)
01229       return false;
01230 
01231     BitVector UndefElements;
01232     CN = BV->getConstantSplatNode(&UndefElements);
01233     // Only interested in constant splats, and we don't try to handle undef
01234     // elements in identifying boolean constants.
01235     if (!CN || UndefElements.none())
01236       return false;
01237   }
01238 
01239   if (getBooleanContents(N->getValueType(0)) == UndefinedBooleanContent)
01240     return !CN->getAPIntValue()[0];
01241 
01242   return CN->isNullValue();
01243 }
01244 
01245 bool TargetLowering::isExtendedTrueVal(const ConstantSDNode *N, EVT VT,
01246                                        bool SExt) const {
01247   if (VT == MVT::i1)
01248     return N->isOne();
01249 
01250   TargetLowering::BooleanContent Cnt = getBooleanContents(VT);
01251   switch (Cnt) {
01252   case TargetLowering::ZeroOrOneBooleanContent:
01253     // An extended value of 1 is always true, unless its original type is i1,
01254     // in which case it will be sign extended to -1.
01255     return (N->isOne() && !SExt) || (SExt && (N->getValueType(0) != MVT::i1));
01256   case TargetLowering::UndefinedBooleanContent:
01257   case TargetLowering::ZeroOrNegativeOneBooleanContent:
01258     return N->isAllOnesValue() && SExt;
01259   }
01260   llvm_unreachable("Unexpected enumeration.");
01261 }
01262 
01263 /// Try to simplify a setcc built with the specified operands and cc. If it is
01264 /// unable to simplify it, return a null SDValue.
01265 SDValue
01266 TargetLowering::SimplifySetCC(EVT VT, SDValue N0, SDValue N1,
01267                               ISD::CondCode Cond, bool foldBooleans,
01268                               DAGCombinerInfo &DCI, SDLoc dl) const {
01269   SelectionDAG &DAG = DCI.DAG;
01270 
01271   // These setcc operations always fold.
01272   switch (Cond) {
01273   default: break;
01274   case ISD::SETFALSE:
01275   case ISD::SETFALSE2: return DAG.getConstant(0, dl, VT);
01276   case ISD::SETTRUE:
01277   case ISD::SETTRUE2: {
01278     TargetLowering::BooleanContent Cnt =
01279         getBooleanContents(N0->getValueType(0));
01280     return DAG.getConstant(
01281         Cnt == TargetLowering::ZeroOrNegativeOneBooleanContent ? -1ULL : 1, dl,
01282         VT);
01283   }
01284   }
01285 
01286   // Ensure that the constant occurs on the RHS, and fold constant
01287   // comparisons.
01288   ISD::CondCode SwappedCC = ISD::getSetCCSwappedOperands(Cond);
01289   if (isa<ConstantSDNode>(N0.getNode()) &&
01290       (DCI.isBeforeLegalizeOps() ||
01291        isCondCodeLegal(SwappedCC, N0.getSimpleValueType())))
01292     return DAG.getSetCC(dl, VT, N1, N0, SwappedCC);
01293 
01294   if (auto *N1C = dyn_cast<ConstantSDNode>(N1.getNode())) {
01295     const APInt &C1 = N1C->getAPIntValue();
01296 
01297     // If the LHS is '(srl (ctlz x), 5)', the RHS is 0/1, and this is an
01298     // equality comparison, then we're just comparing whether X itself is
01299     // zero.
01300     if (N0.getOpcode() == ISD::SRL && (C1 == 0 || C1 == 1) &&
01301         N0.getOperand(0).getOpcode() == ISD::CTLZ &&
01302         N0.getOperand(1).getOpcode() == ISD::Constant) {
01303       const APInt &ShAmt
01304         = cast<ConstantSDNode>(N0.getOperand(1))->getAPIntValue();
01305       if ((Cond == ISD::SETEQ || Cond == ISD::SETNE) &&
01306           ShAmt == Log2_32(N0.getValueType().getSizeInBits())) {
01307         if ((C1 == 0) == (Cond == ISD::SETEQ)) {
01308           // (srl (ctlz x), 5) == 0  -> X != 0
01309           // (srl (ctlz x), 5) != 1  -> X != 0
01310           Cond = ISD::SETNE;
01311         } else {
01312           // (srl (ctlz x), 5) != 0  -> X == 0
01313           // (srl (ctlz x), 5) == 1  -> X == 0
01314           Cond = ISD::SETEQ;
01315         }
01316         SDValue Zero = DAG.getConstant(0, dl, N0.getValueType());
01317         return DAG.getSetCC(dl, VT, N0.getOperand(0).getOperand(0),
01318                             Zero, Cond);
01319       }
01320     }
01321 
01322     SDValue CTPOP = N0;
01323     // Look through truncs that don't change the value of a ctpop.
01324     if (N0.hasOneUse() && N0.getOpcode() == ISD::TRUNCATE)
01325       CTPOP = N0.getOperand(0);
01326 
01327     if (CTPOP.hasOneUse() && CTPOP.getOpcode() == ISD::CTPOP &&
01328         (N0 == CTPOP || N0.getValueType().getSizeInBits() >
01329                         Log2_32_Ceil(CTPOP.getValueType().getSizeInBits()))) {
01330       EVT CTVT = CTPOP.getValueType();
01331       SDValue CTOp = CTPOP.getOperand(0);
01332 
01333       // (ctpop x) u< 2 -> (x & x-1) == 0
01334       // (ctpop x) u> 1 -> (x & x-1) != 0
01335       if ((Cond == ISD::SETULT && C1 == 2) || (Cond == ISD::SETUGT && C1 == 1)){
01336         SDValue Sub = DAG.getNode(ISD::SUB, dl, CTVT, CTOp,
01337                                   DAG.getConstant(1, dl, CTVT));
01338         SDValue And = DAG.getNode(ISD::AND, dl, CTVT, CTOp, Sub);
01339         ISD::CondCode CC = Cond == ISD::SETULT ? ISD::SETEQ : ISD::SETNE;
01340         return DAG.getSetCC(dl, VT, And, DAG.getConstant(0, dl, CTVT), CC);
01341       }
01342 
01343       // TODO: (ctpop x) == 1 -> x && (x & x-1) == 0 iff ctpop is illegal.
01344     }
01345 
01346     // (zext x) == C --> x == (trunc C)
01347     // (sext x) == C --> x == (trunc C)
01348     if ((Cond == ISD::SETEQ || Cond == ISD::SETNE) &&
01349         DCI.isBeforeLegalize() && N0->hasOneUse()) {
01350       unsigned MinBits = N0.getValueSizeInBits();
01351       SDValue PreExt;
01352       bool Signed = false;
01353       if (N0->getOpcode() == ISD::ZERO_EXTEND) {
01354         // ZExt
01355         MinBits = N0->getOperand(0).getValueSizeInBits();
01356         PreExt = N0->getOperand(0);
01357       } else if (N0->getOpcode() == ISD::AND) {
01358         // DAGCombine turns costly ZExts into ANDs
01359         if (auto *C = dyn_cast<ConstantSDNode>(N0->getOperand(1)))
01360           if ((C->getAPIntValue()+1).isPowerOf2()) {
01361             MinBits = C->getAPIntValue().countTrailingOnes();
01362             PreExt = N0->getOperand(0);
01363           }
01364       } else if (N0->getOpcode() == ISD::SIGN_EXTEND) {
01365         // SExt
01366         MinBits = N0->getOperand(0).getValueSizeInBits();
01367         PreExt = N0->getOperand(0);
01368         Signed = true;
01369       } else if (auto *LN0 = dyn_cast<LoadSDNode>(N0)) {
01370         // ZEXTLOAD / SEXTLOAD
01371         if (LN0->getExtensionType() == ISD::ZEXTLOAD) {
01372           MinBits = LN0->getMemoryVT().getSizeInBits();
01373           PreExt = N0;
01374         } else if (LN0->getExtensionType() == ISD::SEXTLOAD) {
01375           Signed = true;
01376           MinBits = LN0->getMemoryVT().getSizeInBits();
01377           PreExt = N0;
01378         }
01379       }
01380 
01381       // Figure out how many bits we need to preserve this constant.
01382       unsigned ReqdBits = Signed ?
01383         C1.getBitWidth() - C1.getNumSignBits() + 1 :
01384         C1.getActiveBits();
01385 
01386       // Make sure we're not losing bits from the constant.
01387       if (MinBits > 0 &&
01388           MinBits < C1.getBitWidth() &&
01389           MinBits >= ReqdBits) {
01390         EVT MinVT = EVT::getIntegerVT(*DAG.getContext(), MinBits);
01391         if (isTypeDesirableForOp(ISD::SETCC, MinVT)) {
01392           // Will get folded away.
01393           SDValue Trunc = DAG.getNode(ISD::TRUNCATE, dl, MinVT, PreExt);
01394           SDValue C = DAG.getConstant(C1.trunc(MinBits), dl, MinVT);
01395           return DAG.getSetCC(dl, VT, Trunc, C, Cond);
01396         }
01397 
01398         // If truncating the setcc operands is not desirable, we can still
01399         // simplify the expression in some cases:
01400         // setcc ([sz]ext (setcc x, y, cc)), 0, setne) -> setcc (x, y, cc)
01401         // setcc ([sz]ext (setcc x, y, cc)), 0, seteq) -> setcc (x, y, inv(cc))
01402         // setcc (zext (setcc x, y, cc)), 1, setne) -> setcc (x, y, inv(cc))
01403         // setcc (zext (setcc x, y, cc)), 1, seteq) -> setcc (x, y, cc)
01404         // setcc (sext (setcc x, y, cc)), -1, setne) -> setcc (x, y, inv(cc))
01405         // setcc (sext (setcc x, y, cc)), -1, seteq) -> setcc (x, y, cc)
01406         SDValue TopSetCC = N0->getOperand(0);
01407         unsigned N0Opc = N0->getOpcode();
01408         bool SExt = (N0Opc == ISD::SIGN_EXTEND);
01409         if (TopSetCC.getValueType() == MVT::i1 && VT == MVT::i1 &&
01410             TopSetCC.getOpcode() == ISD::SETCC &&
01411             (N0Opc == ISD::ZERO_EXTEND || N0Opc == ISD::SIGN_EXTEND) &&
01412             (isConstFalseVal(N1C) ||
01413              isExtendedTrueVal(N1C, N0->getValueType(0), SExt))) {
01414 
01415           bool Inverse = (N1C->isNullValue() && Cond == ISD::SETEQ) ||
01416                          (!N1C->isNullValue() && Cond == ISD::SETNE);
01417 
01418           if (!Inverse)
01419             return TopSetCC;
01420 
01421           ISD::CondCode InvCond = ISD::getSetCCInverse(
01422               cast<CondCodeSDNode>(TopSetCC.getOperand(2))->get(),
01423               TopSetCC.getOperand(0).getValueType().isInteger());
01424           return DAG.getSetCC(dl, VT, TopSetCC.getOperand(0),
01425                                       TopSetCC.getOperand(1),
01426                                       InvCond);
01427 
01428         }
01429       }
01430     }
01431 
01432     // If the LHS is '(and load, const)', the RHS is 0,
01433     // the test is for equality or unsigned, and all 1 bits of the const are
01434     // in the same partial word, see if we can shorten the load.
01435     if (DCI.isBeforeLegalize() &&
01436         !ISD::isSignedIntSetCC(Cond) &&
01437         N0.getOpcode() == ISD::AND && C1 == 0 &&
01438         N0.getNode()->hasOneUse() &&
01439         isa<LoadSDNode>(N0.getOperand(0)) &&
01440         N0.getOperand(0).getNode()->hasOneUse() &&
01441         isa<ConstantSDNode>(N0.getOperand(1))) {
01442       LoadSDNode *Lod = cast<LoadSDNode>(N0.getOperand(0));
01443       APInt bestMask;
01444       unsigned bestWidth = 0, bestOffset = 0;
01445       if (!Lod->isVolatile() && Lod->isUnindexed()) {
01446         unsigned origWidth = N0.getValueType().getSizeInBits();
01447         unsigned maskWidth = origWidth;
01448         // We can narrow (e.g.) 16-bit extending loads on 32-bit target to
01449         // 8 bits, but have to be careful...
01450         if (Lod->getExtensionType() != ISD::NON_EXTLOAD)
01451           origWidth = Lod->getMemoryVT().getSizeInBits();
01452         const APInt &Mask =
01453           cast<ConstantSDNode>(N0.getOperand(1))->getAPIntValue();
01454         for (unsigned width = origWidth / 2; width>=8; width /= 2) {
01455           APInt newMask = APInt::getLowBitsSet(maskWidth, width);
01456           for (unsigned offset=0; offset<origWidth/width; offset++) {
01457             if ((newMask & Mask) == Mask) {
01458               if (!DAG.getDataLayout().isLittleEndian())
01459                 bestOffset = (origWidth/width - offset - 1) * (width/8);
01460               else
01461                 bestOffset = (uint64_t)offset * (width/8);
01462               bestMask = Mask.lshr(offset * (width/8) * 8);
01463               bestWidth = width;
01464               break;
01465             }
01466             newMask = newMask << width;
01467           }
01468         }
01469       }
01470       if (bestWidth) {
01471         EVT newVT = EVT::getIntegerVT(*DAG.getContext(), bestWidth);
01472         if (newVT.isRound()) {
01473           EVT PtrType = Lod->getOperand(1).getValueType();
01474           SDValue Ptr = Lod->getBasePtr();
01475           if (bestOffset != 0)
01476             Ptr = DAG.getNode(ISD::ADD, dl, PtrType, Lod->getBasePtr(),
01477                               DAG.getConstant(bestOffset, dl, PtrType));
01478           unsigned NewAlign = MinAlign(Lod->getAlignment(), bestOffset);
01479           SDValue NewLoad = DAG.getLoad(newVT, dl, Lod->getChain(), Ptr,
01480                                 Lod->getPointerInfo().getWithOffset(bestOffset),
01481                                         false, false, false, NewAlign);
01482           return DAG.getSetCC(dl, VT,
01483                               DAG.getNode(ISD::AND, dl, newVT, NewLoad,
01484                                       DAG.getConstant(bestMask.trunc(bestWidth),
01485                                                       dl, newVT)),
01486                               DAG.getConstant(0LL, dl, newVT), Cond);
01487         }
01488       }
01489     }
01490 
01491     // If the LHS is a ZERO_EXTEND, perform the comparison on the input.
01492     if (N0.getOpcode() == ISD::ZERO_EXTEND) {
01493       unsigned InSize = N0.getOperand(0).getValueType().getSizeInBits();
01494 
01495       // If the comparison constant has bits in the upper part, the
01496       // zero-extended value could never match.
01497       if (C1.intersects(APInt::getHighBitsSet(C1.getBitWidth(),
01498                                               C1.getBitWidth() - InSize))) {
01499         switch (Cond) {
01500         case ISD::SETUGT:
01501         case ISD::SETUGE:
01502         case ISD::SETEQ: return DAG.getConstant(0, dl, VT);
01503         case ISD::SETULT:
01504         case ISD::SETULE:
01505         case ISD::SETNE: return DAG.getConstant(1, dl, VT);
01506         case ISD::SETGT:
01507         case ISD::SETGE:
01508           // True if the sign bit of C1 is set.
01509           return DAG.getConstant(C1.isNegative(), dl, VT);
01510         case ISD::SETLT:
01511         case ISD::SETLE:
01512           // True if the sign bit of C1 isn't set.
01513           return DAG.getConstant(C1.isNonNegative(), dl, VT);
01514         default:
01515           break;
01516         }
01517       }
01518 
01519       // Otherwise, we can perform the comparison with the low bits.
01520       switch (Cond) {
01521       case ISD::SETEQ:
01522       case ISD::SETNE:
01523       case ISD::SETUGT:
01524       case ISD::SETUGE:
01525       case ISD::SETULT:
01526       case ISD::SETULE: {
01527         EVT newVT = N0.getOperand(0).getValueType();
01528         if (DCI.isBeforeLegalizeOps() ||
01529             (isOperationLegal(ISD::SETCC, newVT) &&
01530              getCondCodeAction(Cond, newVT.getSimpleVT()) == Legal)) {
01531           EVT NewSetCCVT =
01532               getSetCCResultType(DAG.getDataLayout(), *DAG.getContext(), newVT);
01533           SDValue NewConst = DAG.getConstant(C1.trunc(InSize), dl, newVT);
01534 
01535           SDValue NewSetCC = DAG.getSetCC(dl, NewSetCCVT, N0.getOperand(0),
01536                                           NewConst, Cond);
01537           return DAG.getBoolExtOrTrunc(NewSetCC, dl, VT, N0.getValueType());
01538         }
01539         break;
01540       }
01541       default:
01542         break;   // todo, be more careful with signed comparisons
01543       }
01544     } else if (N0.getOpcode() == ISD::SIGN_EXTEND_INREG &&
01545                (Cond == ISD::SETEQ || Cond == ISD::SETNE)) {
01546       EVT ExtSrcTy = cast<VTSDNode>(N0.getOperand(1))->getVT();
01547       unsigned ExtSrcTyBits = ExtSrcTy.getSizeInBits();
01548       EVT ExtDstTy = N0.getValueType();
01549       unsigned ExtDstTyBits = ExtDstTy.getSizeInBits();
01550 
01551       // If the constant doesn't fit into the number of bits for the source of
01552       // the sign extension, it is impossible for both sides to be equal.
01553       if (C1.getMinSignedBits() > ExtSrcTyBits)
01554         return DAG.getConstant(Cond == ISD::SETNE, dl, VT);
01555 
01556       SDValue ZextOp;
01557       EVT Op0Ty = N0.getOperand(0).getValueType();
01558       if (Op0Ty == ExtSrcTy) {
01559         ZextOp = N0.getOperand(0);
01560       } else {
01561         APInt Imm = APInt::getLowBitsSet(ExtDstTyBits, ExtSrcTyBits);
01562         ZextOp = DAG.getNode(ISD::AND, dl, Op0Ty, N0.getOperand(0),
01563                               DAG.getConstant(Imm, dl, Op0Ty));
01564       }
01565       if (!DCI.isCalledByLegalizer())
01566         DCI.AddToWorklist(ZextOp.getNode());
01567       // Otherwise, make this a use of a zext.
01568       return DAG.getSetCC(dl, VT, ZextOp,
01569                           DAG.getConstant(C1 & APInt::getLowBitsSet(
01570                                                               ExtDstTyBits,
01571                                                               ExtSrcTyBits),
01572                                           dl, ExtDstTy),
01573                           Cond);
01574     } else if ((N1C->isNullValue() || N1C->getAPIntValue() == 1) &&
01575                 (Cond == ISD::SETEQ || Cond == ISD::SETNE)) {
01576       // SETCC (SETCC), [0|1], [EQ|NE]  -> SETCC
01577       if (N0.getOpcode() == ISD::SETCC &&
01578           isTypeLegal(VT) && VT.bitsLE(N0.getValueType())) {
01579         bool TrueWhenTrue = (Cond == ISD::SETEQ) ^ (N1C->getAPIntValue() != 1);
01580         if (TrueWhenTrue)
01581           return DAG.getNode(ISD::TRUNCATE, dl, VT, N0);
01582         // Invert the condition.
01583         ISD::CondCode CC = cast<CondCodeSDNode>(N0.getOperand(2))->get();
01584         CC = ISD::getSetCCInverse(CC,
01585                                   N0.getOperand(0).getValueType().isInteger());
01586         if (DCI.isBeforeLegalizeOps() ||
01587             isCondCodeLegal(CC, N0.getOperand(0).getSimpleValueType()))
01588           return DAG.getSetCC(dl, VT, N0.getOperand(0), N0.getOperand(1), CC);
01589       }
01590 
01591       if ((N0.getOpcode() == ISD::XOR ||
01592            (N0.getOpcode() == ISD::AND &&
01593             N0.getOperand(0).getOpcode() == ISD::XOR &&
01594             N0.getOperand(1) == N0.getOperand(0).getOperand(1))) &&
01595           isa<ConstantSDNode>(N0.getOperand(1)) &&
01596           cast<ConstantSDNode>(N0.getOperand(1))->getAPIntValue() == 1) {
01597         // If this is (X^1) == 0/1, swap the RHS and eliminate the xor.  We
01598         // can only do this if the top bits are known zero.
01599         unsigned BitWidth = N0.getValueSizeInBits();
01600         if (DAG.MaskedValueIsZero(N0,
01601                                   APInt::getHighBitsSet(BitWidth,
01602                                                         BitWidth-1))) {
01603           // Okay, get the un-inverted input value.
01604           SDValue Val;
01605           if (N0.getOpcode() == ISD::XOR)
01606             Val = N0.getOperand(0);
01607           else {
01608             assert(N0.getOpcode() == ISD::AND &&
01609                     N0.getOperand(0).getOpcode() == ISD::XOR);
01610             // ((X^1)&1)^1 -> X & 1
01611             Val = DAG.getNode(ISD::AND, dl, N0.getValueType(),
01612                               N0.getOperand(0).getOperand(0),
01613                               N0.getOperand(1));
01614           }
01615 
01616           return DAG.getSetCC(dl, VT, Val, N1,
01617                               Cond == ISD::SETEQ ? ISD::SETNE : ISD::SETEQ);
01618         }
01619       } else if (N1C->getAPIntValue() == 1 &&
01620                  (VT == MVT::i1 ||
01621                   getBooleanContents(N0->getValueType(0)) ==
01622                       ZeroOrOneBooleanContent)) {
01623         SDValue Op0 = N0;
01624         if (Op0.getOpcode() == ISD::TRUNCATE)
01625           Op0 = Op0.getOperand(0);
01626 
01627         if ((Op0.getOpcode() == ISD::XOR) &&
01628             Op0.getOperand(0).getOpcode() == ISD::SETCC &&
01629             Op0.getOperand(1).getOpcode() == ISD::SETCC) {
01630           // (xor (setcc), (setcc)) == / != 1 -> (setcc) != / == (setcc)
01631           Cond = (Cond == ISD::SETEQ) ? ISD::SETNE : ISD::SETEQ;
01632           return DAG.getSetCC(dl, VT, Op0.getOperand(0), Op0.getOperand(1),
01633                               Cond);
01634         }
01635         if (Op0.getOpcode() == ISD::AND &&
01636             isa<ConstantSDNode>(Op0.getOperand(1)) &&
01637             cast<ConstantSDNode>(Op0.getOperand(1))->getAPIntValue() == 1) {
01638           // If this is (X&1) == / != 1, normalize it to (X&1) != / == 0.
01639           if (Op0.getValueType().bitsGT(VT))
01640             Op0 = DAG.getNode(ISD::AND, dl, VT,
01641                           DAG.getNode(ISD::TRUNCATE, dl, VT, Op0.getOperand(0)),
01642                           DAG.getConstant(1, dl, VT));
01643           else if (Op0.getValueType().bitsLT(VT))
01644             Op0 = DAG.getNode(ISD::AND, dl, VT,
01645                         DAG.getNode(ISD::ANY_EXTEND, dl, VT, Op0.getOperand(0)),
01646                         DAG.getConstant(1, dl, VT));
01647 
01648           return DAG.getSetCC(dl, VT, Op0,
01649                               DAG.getConstant(0, dl, Op0.getValueType()),
01650                               Cond == ISD::SETEQ ? ISD::SETNE : ISD::SETEQ);
01651         }
01652         if (Op0.getOpcode() == ISD::AssertZext &&
01653             cast<VTSDNode>(Op0.getOperand(1))->getVT() == MVT::i1)
01654           return DAG.getSetCC(dl, VT, Op0,
01655                               DAG.getConstant(0, dl, Op0.getValueType()),
01656                               Cond == ISD::SETEQ ? ISD::SETNE : ISD::SETEQ);
01657       }
01658     }
01659 
01660     APInt MinVal, MaxVal;
01661     unsigned OperandBitSize = N1C->getValueType(0).getSizeInBits();
01662     if (ISD::isSignedIntSetCC(Cond)) {
01663       MinVal = APInt::getSignedMinValue(OperandBitSize);
01664       MaxVal = APInt::getSignedMaxValue(OperandBitSize);
01665     } else {
01666       MinVal = APInt::getMinValue(OperandBitSize);
01667       MaxVal = APInt::getMaxValue(OperandBitSize);
01668     }
01669 
01670     // Canonicalize GE/LE comparisons to use GT/LT comparisons.
01671     if (Cond == ISD::SETGE || Cond == ISD::SETUGE) {
01672       if (C1 == MinVal) return DAG.getConstant(1, dl, VT);  // X >= MIN --> true
01673       // X >= C0 --> X > (C0 - 1)
01674       APInt C = C1 - 1;
01675       ISD::CondCode NewCC = (Cond == ISD::SETGE) ? ISD::SETGT : ISD::SETUGT;
01676       if ((DCI.isBeforeLegalizeOps() ||
01677            isCondCodeLegal(NewCC, VT.getSimpleVT())) &&
01678           (!N1C->isOpaque() || (N1C->isOpaque() && C.getBitWidth() <= 64 &&
01679                                 isLegalICmpImmediate(C.getSExtValue())))) {
01680         return DAG.getSetCC(dl, VT, N0,
01681                             DAG.getConstant(C, dl, N1.getValueType()),
01682                             NewCC);
01683       }
01684     }
01685 
01686     if (Cond == ISD::SETLE || Cond == ISD::SETULE) {
01687       if (C1 == MaxVal) return DAG.getConstant(1, dl, VT);  // X <= MAX --> true
01688       // X <= C0 --> X < (C0 + 1)
01689       APInt C = C1 + 1;
01690       ISD::CondCode NewCC = (Cond == ISD::SETLE) ? ISD::SETLT : ISD::SETULT;
01691       if ((DCI.isBeforeLegalizeOps() ||
01692            isCondCodeLegal(NewCC, VT.getSimpleVT())) &&
01693           (!N1C->isOpaque() || (N1C->isOpaque() && C.getBitWidth() <= 64 &&
01694                                 isLegalICmpImmediate(C.getSExtValue())))) {
01695         return DAG.getSetCC(dl, VT, N0,
01696                             DAG.getConstant(C, dl, N1.getValueType()),
01697                             NewCC);
01698       }
01699     }
01700 
01701     if ((Cond == ISD::SETLT || Cond == ISD::SETULT) && C1 == MinVal)
01702       return DAG.getConstant(0, dl, VT);      // X < MIN --> false
01703     if ((Cond == ISD::SETGE || Cond == ISD::SETUGE) && C1 == MinVal)
01704       return DAG.getConstant(1, dl, VT);      // X >= MIN --> true
01705     if ((Cond == ISD::SETGT || Cond == ISD::SETUGT) && C1 == MaxVal)
01706       return DAG.getConstant(0, dl, VT);      // X > MAX --> false
01707     if ((Cond == ISD::SETLE || Cond == ISD::SETULE) && C1 == MaxVal)
01708       return DAG.getConstant(1, dl, VT);      // X <= MAX --> true
01709 
01710     // Canonicalize setgt X, Min --> setne X, Min
01711     if ((Cond == ISD::SETGT || Cond == ISD::SETUGT) && C1 == MinVal)
01712       return DAG.getSetCC(dl, VT, N0, N1, ISD::SETNE);
01713     // Canonicalize setlt X, Max --> setne X, Max
01714     if ((Cond == ISD::SETLT || Cond == ISD::SETULT) && C1 == MaxVal)
01715       return DAG.getSetCC(dl, VT, N0, N1, ISD::SETNE);
01716 
01717     // If we have setult X, 1, turn it into seteq X, 0
01718     if ((Cond == ISD::SETLT || Cond == ISD::SETULT) && C1 == MinVal+1)
01719       return DAG.getSetCC(dl, VT, N0,
01720                           DAG.getConstant(MinVal, dl, N0.getValueType()),
01721                           ISD::SETEQ);
01722     // If we have setugt X, Max-1, turn it into seteq X, Max
01723     if ((Cond == ISD::SETGT || Cond == ISD::SETUGT) && C1 == MaxVal-1)
01724       return DAG.getSetCC(dl, VT, N0,
01725                           DAG.getConstant(MaxVal, dl, N0.getValueType()),
01726                           ISD::SETEQ);
01727 
01728     // If we have "setcc X, C0", check to see if we can shrink the immediate
01729     // by changing cc.
01730 
01731     // SETUGT X, SINTMAX  -> SETLT X, 0
01732     if (Cond == ISD::SETUGT &&
01733         C1 == APInt::getSignedMaxValue(OperandBitSize))
01734       return DAG.getSetCC(dl, VT, N0,
01735                           DAG.getConstant(0, dl, N1.getValueType()),
01736                           ISD::SETLT);
01737 
01738     // SETULT X, SINTMIN  -> SETGT X, -1
01739     if (Cond == ISD::SETULT &&
01740         C1 == APInt::getSignedMinValue(OperandBitSize)) {
01741       SDValue ConstMinusOne =
01742           DAG.getConstant(APInt::getAllOnesValue(OperandBitSize), dl,
01743                           N1.getValueType());
01744       return DAG.getSetCC(dl, VT, N0, ConstMinusOne, ISD::SETGT);
01745     }
01746 
01747     // Fold bit comparisons when we can.
01748     if ((Cond == ISD::SETEQ || Cond == ISD::SETNE) &&
01749         (VT == N0.getValueType() ||
01750          (isTypeLegal(VT) && VT.bitsLE(N0.getValueType()))) &&
01751         N0.getOpcode() == ISD::AND) {
01752       auto &DL = DAG.getDataLayout();
01753       if (auto *AndRHS = dyn_cast<ConstantSDNode>(N0.getOperand(1))) {
01754         EVT ShiftTy = DCI.isBeforeLegalize()
01755                           ? getPointerTy(DL)
01756                           : getShiftAmountTy(N0.getValueType(), DL);
01757         if (Cond == ISD::SETNE && C1 == 0) {// (X & 8) != 0  -->  (X & 8) >> 3
01758           // Perform the xform if the AND RHS is a single bit.
01759           if (AndRHS->getAPIntValue().isPowerOf2()) {
01760             return DAG.getNode(ISD::TRUNCATE, dl, VT,
01761                               DAG.getNode(ISD::SRL, dl, N0.getValueType(), N0,
01762                    DAG.getConstant(AndRHS->getAPIntValue().logBase2(), dl,
01763                                    ShiftTy)));
01764           }
01765         } else if (Cond == ISD::SETEQ && C1 == AndRHS->getAPIntValue()) {
01766           // (X & 8) == 8  -->  (X & 8) >> 3
01767           // Perform the xform if C1 is a single bit.
01768           if (C1.isPowerOf2()) {
01769             return DAG.getNode(ISD::TRUNCATE, dl, VT,
01770                                DAG.getNode(ISD::SRL, dl, N0.getValueType(), N0,
01771                                       DAG.getConstant(C1.logBase2(), dl,
01772                                                       ShiftTy)));
01773           }
01774         }
01775       }
01776     }
01777 
01778     if (C1.getMinSignedBits() <= 64 &&
01779         !isLegalICmpImmediate(C1.getSExtValue())) {
01780       // (X & -256) == 256 -> (X >> 8) == 1
01781       if ((Cond == ISD::SETEQ || Cond == ISD::SETNE) &&
01782           N0.getOpcode() == ISD::AND && N0.hasOneUse()) {
01783         if (auto *AndRHS = dyn_cast<ConstantSDNode>(N0.getOperand(1))) {
01784           const APInt &AndRHSC = AndRHS->getAPIntValue();
01785           if ((-AndRHSC).isPowerOf2() && (AndRHSC & C1) == C1) {
01786             unsigned ShiftBits = AndRHSC.countTrailingZeros();
01787             auto &DL = DAG.getDataLayout();
01788             EVT ShiftTy = DCI.isBeforeLegalize()
01789                               ? getPointerTy(DL)
01790                               : getShiftAmountTy(N0.getValueType(), DL);
01791             EVT CmpTy = N0.getValueType();
01792             SDValue Shift = DAG.getNode(ISD::SRL, dl, CmpTy, N0.getOperand(0),
01793                                         DAG.getConstant(ShiftBits, dl,
01794                                                         ShiftTy));
01795             SDValue CmpRHS = DAG.getConstant(C1.lshr(ShiftBits), dl, CmpTy);
01796             return DAG.getSetCC(dl, VT, Shift, CmpRHS, Cond);
01797           }
01798         }
01799       } else if (Cond == ISD::SETULT || Cond == ISD::SETUGE ||
01800                  Cond == ISD::SETULE || Cond == ISD::SETUGT) {
01801         bool AdjOne = (Cond == ISD::SETULE || Cond == ISD::SETUGT);
01802         // X <  0x100000000 -> (X >> 32) <  1
01803         // X >= 0x100000000 -> (X >> 32) >= 1
01804         // X <= 0x0ffffffff -> (X >> 32) <  1
01805         // X >  0x0ffffffff -> (X >> 32) >= 1
01806         unsigned ShiftBits;
01807         APInt NewC = C1;
01808         ISD::CondCode NewCond = Cond;
01809         if (AdjOne) {
01810           ShiftBits = C1.countTrailingOnes();
01811           NewC = NewC + 1;
01812           NewCond = (Cond == ISD::SETULE) ? ISD::SETULT : ISD::SETUGE;
01813         } else {
01814           ShiftBits = C1.countTrailingZeros();
01815         }
01816         NewC = NewC.lshr(ShiftBits);
01817         if (ShiftBits && NewC.getMinSignedBits() <= 64 &&
01818           isLegalICmpImmediate(NewC.getSExtValue())) {
01819           auto &DL = DAG.getDataLayout();
01820           EVT ShiftTy = DCI.isBeforeLegalize()
01821                             ? getPointerTy(DL)
01822                             : getShiftAmountTy(N0.getValueType(), DL);
01823           EVT CmpTy = N0.getValueType();
01824           SDValue Shift = DAG.getNode(ISD::SRL, dl, CmpTy, N0,
01825                                       DAG.getConstant(ShiftBits, dl, ShiftTy));
01826           SDValue CmpRHS = DAG.getConstant(NewC, dl, CmpTy);
01827           return DAG.getSetCC(dl, VT, Shift, CmpRHS, NewCond);
01828         }
01829       }
01830     }
01831   }
01832 
01833   if (isa<ConstantFPSDNode>(N0.getNode())) {
01834     // Constant fold or commute setcc.
01835     SDValue O = DAG.FoldSetCC(VT, N0, N1, Cond, dl);
01836     if (O.getNode()) return O;
01837   } else if (auto *CFP = dyn_cast<ConstantFPSDNode>(N1.getNode())) {
01838     // If the RHS of an FP comparison is a constant, simplify it away in
01839     // some cases.
01840     if (CFP->getValueAPF().isNaN()) {
01841       // If an operand is known to be a nan, we can fold it.
01842       switch (ISD::getUnorderedFlavor(Cond)) {
01843       default: llvm_unreachable("Unknown flavor!");
01844       case 0:  // Known false.
01845         return DAG.getConstant(0, dl, VT);
01846       case 1:  // Known true.
01847         return DAG.getConstant(1, dl, VT);
01848       case 2:  // Undefined.
01849         return DAG.getUNDEF(VT);
01850       }
01851     }
01852 
01853     // Otherwise, we know the RHS is not a NaN.  Simplify the node to drop the
01854     // constant if knowing that the operand is non-nan is enough.  We prefer to
01855     // have SETO(x,x) instead of SETO(x, 0.0) because this avoids having to
01856     // materialize 0.0.
01857     if (Cond == ISD::SETO || Cond == ISD::SETUO)
01858       return DAG.getSetCC(dl, VT, N0, N0, Cond);
01859 
01860     // If the condition is not legal, see if we can find an equivalent one
01861     // which is legal.
01862     if (!isCondCodeLegal(Cond, N0.getSimpleValueType())) {
01863       // If the comparison was an awkward floating-point == or != and one of
01864       // the comparison operands is infinity or negative infinity, convert the
01865       // condition to a less-awkward <= or >=.
01866       if (CFP->getValueAPF().isInfinity()) {
01867         if (CFP->getValueAPF().isNegative()) {
01868           if (Cond == ISD::SETOEQ &&
01869               isCondCodeLegal(ISD::SETOLE, N0.getSimpleValueType()))
01870             return DAG.getSetCC(dl, VT, N0, N1, ISD::SETOLE);
01871           if (Cond == ISD::SETUEQ &&
01872               isCondCodeLegal(ISD::SETOLE, N0.getSimpleValueType()))
01873             return DAG.getSetCC(dl, VT, N0, N1, ISD::SETULE);
01874           if (Cond == ISD::SETUNE &&
01875               isCondCodeLegal(ISD::SETUGT, N0.getSimpleValueType()))
01876             return DAG.getSetCC(dl, VT, N0, N1, ISD::SETUGT);
01877           if (Cond == ISD::SETONE &&
01878               isCondCodeLegal(ISD::SETUGT, N0.getSimpleValueType()))
01879             return DAG.getSetCC(dl, VT, N0, N1, ISD::SETOGT);
01880         } else {
01881           if (Cond == ISD::SETOEQ &&
01882               isCondCodeLegal(ISD::SETOGE, N0.getSimpleValueType()))
01883             return DAG.getSetCC(dl, VT, N0, N1, ISD::SETOGE);
01884           if (Cond == ISD::SETUEQ &&
01885               isCondCodeLegal(ISD::SETOGE, N0.getSimpleValueType()))
01886             return DAG.getSetCC(dl, VT, N0, N1, ISD::SETUGE);
01887           if (Cond == ISD::SETUNE &&
01888               isCondCodeLegal(ISD::SETULT, N0.getSimpleValueType()))
01889             return DAG.getSetCC(dl, VT, N0, N1, ISD::SETULT);
01890           if (Cond == ISD::SETONE &&
01891               isCondCodeLegal(ISD::SETULT, N0.getSimpleValueType()))
01892             return DAG.getSetCC(dl, VT, N0, N1, ISD::SETOLT);
01893         }
01894       }
01895     }
01896   }
01897 
01898   if (N0 == N1) {
01899     // The sext(setcc()) => setcc() optimization relies on the appropriate
01900     // constant being emitted.
01901     uint64_t EqVal = 0;
01902     switch (getBooleanContents(N0.getValueType())) {
01903     case UndefinedBooleanContent:
01904     case ZeroOrOneBooleanContent:
01905       EqVal = ISD::isTrueWhenEqual(Cond);
01906       break;
01907     case ZeroOrNegativeOneBooleanContent:
01908       EqVal = ISD::isTrueWhenEqual(Cond) ? -1 : 0;
01909       break;
01910     }
01911 
01912     // We can always fold X == X for integer setcc's.
01913     if (N0.getValueType().isInteger()) {
01914       return DAG.getConstant(EqVal, dl, VT);
01915     }
01916     unsigned UOF = ISD::getUnorderedFlavor(Cond);
01917     if (UOF == 2)   // FP operators that are undefined on NaNs.
01918       return DAG.getConstant(EqVal, dl, VT);
01919     if (UOF == unsigned(ISD::isTrueWhenEqual(Cond)))
01920       return DAG.getConstant(EqVal, dl, VT);
01921     // Otherwise, we can't fold it.  However, we can simplify it to SETUO/SETO
01922     // if it is not already.
01923     ISD::CondCode NewCond = UOF == 0 ? ISD::SETO : ISD::SETUO;
01924     if (NewCond != Cond && (DCI.isBeforeLegalizeOps() ||
01925           getCondCodeAction(NewCond, N0.getSimpleValueType()) == Legal))
01926       return DAG.getSetCC(dl, VT, N0, N1, NewCond);
01927   }
01928 
01929   if ((Cond == ISD::SETEQ || Cond == ISD::SETNE) &&
01930       N0.getValueType().isInteger()) {
01931     if (N0.getOpcode() == ISD::ADD || N0.getOpcode() == ISD::SUB ||
01932         N0.getOpcode() == ISD::XOR) {
01933       // Simplify (X+Y) == (X+Z) -->  Y == Z
01934       if (N0.getOpcode() == N1.getOpcode()) {
01935         if (N0.getOperand(0) == N1.getOperand(0))
01936           return DAG.getSetCC(dl, VT, N0.getOperand(1), N1.getOperand(1), Cond);
01937         if (N0.getOperand(1) == N1.getOperand(1))
01938           return DAG.getSetCC(dl, VT, N0.getOperand(0), N1.getOperand(0), Cond);
01939         if (DAG.isCommutativeBinOp(N0.getOpcode())) {
01940           // If X op Y == Y op X, try other combinations.
01941           if (N0.getOperand(0) == N1.getOperand(1))
01942             return DAG.getSetCC(dl, VT, N0.getOperand(1), N1.getOperand(0),
01943                                 Cond);
01944           if (N0.getOperand(1) == N1.getOperand(0))
01945             return DAG.getSetCC(dl, VT, N0.getOperand(0), N1.getOperand(1),
01946                                 Cond);
01947         }
01948       }
01949 
01950       // If RHS is a legal immediate value for a compare instruction, we need
01951       // to be careful about increasing register pressure needlessly.
01952       bool LegalRHSImm = false;
01953 
01954       if (auto *RHSC = dyn_cast<ConstantSDNode>(N1)) {
01955         if (auto *LHSR = dyn_cast<ConstantSDNode>(N0.getOperand(1))) {
01956           // Turn (X+C1) == C2 --> X == C2-C1
01957           if (N0.getOpcode() == ISD::ADD && N0.getNode()->hasOneUse()) {
01958             return DAG.getSetCC(dl, VT, N0.getOperand(0),
01959                                 DAG.getConstant(RHSC->getAPIntValue()-
01960                                                 LHSR->getAPIntValue(),
01961                                 dl, N0.getValueType()), Cond);
01962           }
01963 
01964           // Turn (X^C1) == C2 into X == C1^C2 iff X&~C1 = 0.
01965           if (N0.getOpcode() == ISD::XOR)
01966             // If we know that all of the inverted bits are zero, don't bother
01967             // performing the inversion.
01968             if (DAG.MaskedValueIsZero(N0.getOperand(0), ~LHSR->getAPIntValue()))
01969               return
01970                 DAG.getSetCC(dl, VT, N0.getOperand(0),
01971                              DAG.getConstant(LHSR->getAPIntValue() ^
01972                                                RHSC->getAPIntValue(),
01973                                              dl, N0.getValueType()),
01974                              Cond);
01975         }
01976 
01977         // Turn (C1-X) == C2 --> X == C1-C2
01978         if (auto *SUBC = dyn_cast<ConstantSDNode>(N0.getOperand(0))) {
01979           if (N0.getOpcode() == ISD::SUB && N0.getNode()->hasOneUse()) {
01980             return
01981               DAG.getSetCC(dl, VT, N0.getOperand(1),
01982                            DAG.getConstant(SUBC->getAPIntValue() -
01983                                              RHSC->getAPIntValue(),
01984                                            dl, N0.getValueType()),
01985                            Cond);
01986           }
01987         }
01988 
01989         // Could RHSC fold directly into a compare?
01990         if (RHSC->getValueType(0).getSizeInBits() <= 64)
01991           LegalRHSImm = isLegalICmpImmediate(RHSC->getSExtValue());
01992       }
01993 
01994       // Simplify (X+Z) == X -->  Z == 0
01995       // Don't do this if X is an immediate that can fold into a cmp
01996       // instruction and X+Z has other uses. It could be an induction variable
01997       // chain, and the transform would increase register pressure.
01998       if (!LegalRHSImm || N0.getNode()->hasOneUse()) {
01999         if (N0.getOperand(0) == N1)
02000           return DAG.getSetCC(dl, VT, N0.getOperand(1),
02001                               DAG.getConstant(0, dl, N0.getValueType()), Cond);
02002         if (N0.getOperand(1) == N1) {
02003           if (DAG.isCommutativeBinOp(N0.getOpcode()))
02004             return DAG.getSetCC(dl, VT, N0.getOperand(0),
02005                                 DAG.getConstant(0, dl, N0.getValueType()),
02006                                 Cond);
02007           if (N0.getNode()->hasOneUse()) {
02008             assert(N0.getOpcode() == ISD::SUB && "Unexpected operation!");
02009             auto &DL = DAG.getDataLayout();
02010             // (Z-X) == X  --> Z == X<<1
02011             SDValue SH = DAG.getNode(
02012                 ISD::SHL, dl, N1.getValueType(), N1,
02013                 DAG.getConstant(1, dl,
02014                                 getShiftAmountTy(N1.getValueType(), DL)));
02015             if (!DCI.isCalledByLegalizer())
02016               DCI.AddToWorklist(SH.getNode());
02017             return DAG.getSetCC(dl, VT, N0.getOperand(0), SH, Cond);
02018           }
02019         }
02020       }
02021     }
02022 
02023     if (N1.getOpcode() == ISD::ADD || N1.getOpcode() == ISD::SUB ||
02024         N1.getOpcode() == ISD::XOR) {
02025       // Simplify  X == (X+Z) -->  Z == 0
02026       if (N1.getOperand(0) == N0)
02027         return DAG.getSetCC(dl, VT, N1.getOperand(1),
02028                         DAG.getConstant(0, dl, N1.getValueType()), Cond);
02029       if (N1.getOperand(1) == N0) {
02030         if (DAG.isCommutativeBinOp(N1.getOpcode()))
02031           return DAG.getSetCC(dl, VT, N1.getOperand(0),
02032                           DAG.getConstant(0, dl, N1.getValueType()), Cond);
02033         if (N1.getNode()->hasOneUse()) {
02034           assert(N1.getOpcode() == ISD::SUB && "Unexpected operation!");
02035           auto &DL = DAG.getDataLayout();
02036           // X == (Z-X)  --> X<<1 == Z
02037           SDValue SH = DAG.getNode(
02038               ISD::SHL, dl, N1.getValueType(), N0,
02039               DAG.getConstant(1, dl, getShiftAmountTy(N0.getValueType(), DL)));
02040           if (!DCI.isCalledByLegalizer())
02041             DCI.AddToWorklist(SH.getNode());
02042           return DAG.getSetCC(dl, VT, SH, N1.getOperand(0), Cond);
02043         }
02044       }
02045     }
02046 
02047     // Simplify x&y == y to x&y != 0 if y has exactly one bit set.
02048     // Note that where y is variable and is known to have at most
02049     // one bit set (for example, if it is z&1) we cannot do this;
02050     // the expressions are not equivalent when y==0.
02051     if (N0.getOpcode() == ISD::AND)
02052       if (N0.getOperand(0) == N1 || N0.getOperand(1) == N1) {
02053         if (ValueHasExactlyOneBitSet(N1, DAG)) {
02054           Cond = ISD::getSetCCInverse(Cond, /*isInteger=*/true);
02055           if (DCI.isBeforeLegalizeOps() ||
02056               isCondCodeLegal(Cond, N0.getSimpleValueType())) {
02057             SDValue Zero = DAG.getConstant(0, dl, N1.getValueType());
02058             return DAG.getSetCC(dl, VT, N0, Zero, Cond);
02059           }
02060         }
02061       }
02062     if (N1.getOpcode() == ISD::AND)
02063       if (N1.getOperand(0) == N0 || N1.getOperand(1) == N0) {
02064         if (ValueHasExactlyOneBitSet(N0, DAG)) {
02065           Cond = ISD::getSetCCInverse(Cond, /*isInteger=*/true);
02066           if (DCI.isBeforeLegalizeOps() ||
02067               isCondCodeLegal(Cond, N1.getSimpleValueType())) {
02068             SDValue Zero = DAG.getConstant(0, dl, N0.getValueType());
02069             return DAG.getSetCC(dl, VT, N1, Zero, Cond);
02070           }
02071         }
02072       }
02073   }
02074 
02075   // Fold away ALL boolean setcc's.
02076   SDValue Temp;
02077   if (N0.getValueType() == MVT::i1 && foldBooleans) {
02078     switch (Cond) {
02079     default: llvm_unreachable("Unknown integer setcc!");
02080     case ISD::SETEQ:  // X == Y  -> ~(X^Y)
02081       Temp = DAG.getNode(ISD::XOR, dl, MVT::i1, N0, N1);
02082       N0 = DAG.getNOT(dl, Temp, MVT::i1);
02083       if (!DCI.isCalledByLegalizer())
02084         DCI.AddToWorklist(Temp.getNode());
02085       break;
02086     case ISD::SETNE:  // X != Y   -->  (X^Y)
02087       N0 = DAG.getNode(ISD::XOR, dl, MVT::i1, N0, N1);
02088       break;
02089     case ISD::SETGT:  // X >s Y   -->  X == 0 & Y == 1  -->  ~X & Y
02090     case ISD::SETULT: // X <u Y   -->  X == 0 & Y == 1  -->  ~X & Y
02091       Temp = DAG.getNOT(dl, N0, MVT::i1);
02092       N0 = DAG.getNode(ISD::AND, dl, MVT::i1, N1, Temp);
02093       if (!DCI.isCalledByLegalizer())
02094         DCI.AddToWorklist(Temp.getNode());
02095       break;
02096     case ISD::SETLT:  // X <s Y   --> X == 1 & Y == 0  -->  ~Y & X
02097     case ISD::SETUGT: // X >u Y   --> X == 1 & Y == 0  -->  ~Y & X
02098       Temp = DAG.getNOT(dl, N1, MVT::i1);
02099       N0 = DAG.getNode(ISD::AND, dl, MVT::i1, N0, Temp);
02100       if (!DCI.isCalledByLegalizer())
02101         DCI.AddToWorklist(Temp.getNode());
02102       break;
02103     case ISD::SETULE: // X <=u Y  --> X == 0 | Y == 1  -->  ~X | Y
02104     case ISD::SETGE:  // X >=s Y  --> X == 0 | Y == 1  -->  ~X | Y
02105       Temp = DAG.getNOT(dl, N0, MVT::i1);
02106       N0 = DAG.getNode(ISD::OR, dl, MVT::i1, N1, Temp);
02107       if (!DCI.isCalledByLegalizer())
02108         DCI.AddToWorklist(Temp.getNode());
02109       break;
02110     case ISD::SETUGE: // X >=u Y  --> X == 1 | Y == 0  -->  ~Y | X
02111     case ISD::SETLE:  // X <=s Y  --> X == 1 | Y == 0  -->  ~Y | X
02112       Temp = DAG.getNOT(dl, N1, MVT::i1);
02113       N0 = DAG.getNode(ISD::OR, dl, MVT::i1, N0, Temp);
02114       break;
02115     }
02116     if (VT != MVT::i1) {
02117       if (!DCI.isCalledByLegalizer())
02118         DCI.AddToWorklist(N0.getNode());
02119       // FIXME: If running after legalize, we probably can't do this.
02120       N0 = DAG.getNode(ISD::ZERO_EXTEND, dl, VT, N0);
02121     }
02122     return N0;
02123   }
02124 
02125   // Could not fold it.
02126   return SDValue();
02127 }
02128 
02129 /// Returns true (and the GlobalValue and the offset) if the node is a
02130 /// GlobalAddress + offset.
02131 bool TargetLowering::isGAPlusOffset(SDNode *N, const GlobalValue *&GA,
02132                                     int64_t &Offset) const {
02133   if (auto *GASD = dyn_cast<GlobalAddressSDNode>(N)) {
02134     GA = GASD->getGlobal();
02135     Offset += GASD->getOffset();
02136     return true;
02137   }
02138 
02139   if (N->getOpcode() == ISD::ADD) {
02140     SDValue N1 = N->getOperand(0);
02141     SDValue N2 = N->getOperand(1);
02142     if (isGAPlusOffset(N1.getNode(), GA, Offset)) {
02143       if (auto *V = dyn_cast<ConstantSDNode>(N2)) {
02144         Offset += V->getSExtValue();
02145         return true;
02146       }
02147     } else if (isGAPlusOffset(N2.getNode(), GA, Offset)) {
02148       if (auto *V = dyn_cast<ConstantSDNode>(N1)) {
02149         Offset += V->getSExtValue();
02150         return true;
02151       }
02152     }
02153   }
02154 
02155   return false;
02156 }
02157 
02158 SDValue TargetLowering::PerformDAGCombine(SDNode *N,
02159                                           DAGCombinerInfo &DCI) const {
02160   // Default implementation: no optimization.
02161   return SDValue();
02162 }
02163 
02164 //===----------------------------------------------------------------------===//
02165 //  Inline Assembler Implementation Methods
02166 //===----------------------------------------------------------------------===//
02167 
02168 TargetLowering::ConstraintType
02169 TargetLowering::getConstraintType(StringRef Constraint) const {
02170   unsigned S = Constraint.size();
02171 
02172   if (S == 1) {
02173     switch (Constraint[0]) {
02174     default: break;
02175     case 'r': return C_RegisterClass;
02176     case 'm':    // memory
02177     case 'o':    // offsetable
02178     case 'V':    // not offsetable
02179       return C_Memory;
02180     case 'i':    // Simple Integer or Relocatable Constant
02181     case 'n':    // Simple Integer
02182     case 'E':    // Floating Point Constant
02183     case 'F':    // Floating Point Constant
02184     case 's':    // Relocatable Constant
02185     case 'p':    // Address.
02186     case 'X':    // Allow ANY value.
02187     case 'I':    // Target registers.
02188     case 'J':
02189     case 'K':
02190     case 'L':
02191     case 'M':
02192     case 'N':
02193     case 'O':
02194     case 'P':
02195     case '<':
02196     case '>':
02197       return C_Other;
02198     }
02199   }
02200 
02201   if (S > 1 && Constraint[0] == '{' && Constraint[S-1] == '}') {
02202     if (S == 8 && Constraint.substr(1, 6) == "memory") // "{memory}"
02203       return C_Memory;
02204     return C_Register;
02205   }
02206   return C_Unknown;
02207 }
02208 
02209 /// Try to replace an X constraint, which matches anything, with another that
02210 /// has more specific requirements based on the type of the corresponding
02211 /// operand.
02212 const char *TargetLowering::LowerXConstraint(EVT ConstraintVT) const{
02213   if (ConstraintVT.isInteger())
02214     return "r";
02215   if (ConstraintVT.isFloatingPoint())
02216     return "f";      // works for many targets
02217   return nullptr;
02218 }
02219 
02220 /// Lower the specified operand into the Ops vector.
02221 /// If it is invalid, don't add anything to Ops.
02222 void TargetLowering::LowerAsmOperandForConstraint(SDValue Op,
02223                                                   std::string &Constraint,
02224                                                   std::vector<SDValue> &Ops,
02225                                                   SelectionDAG &DAG) const {
02226 
02227   if (Constraint.length() > 1) return;
02228 
02229   char ConstraintLetter = Constraint[0];
02230   switch (ConstraintLetter) {
02231   default: break;
02232   case 'X':     // Allows any operand; labels (basic block) use this.
02233     if (Op.getOpcode() == ISD::BasicBlock) {
02234       Ops.push_back(Op);
02235       return;
02236     }
02237     // fall through
02238   case 'i':    // Simple Integer or Relocatable Constant
02239   case 'n':    // Simple Integer
02240   case 's': {  // Relocatable Constant
02241     // These operands are interested in values of the form (GV+C), where C may
02242     // be folded in as an offset of GV, or it may be explicitly added.  Also, it
02243     // is possible and fine if either GV or C are missing.
02244     ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op);
02245     GlobalAddressSDNode *GA = dyn_cast<GlobalAddressSDNode>(Op);
02246 
02247     // If we have "(add GV, C)", pull out GV/C
02248     if (Op.getOpcode() == ISD::ADD) {
02249       C = dyn_cast<ConstantSDNode>(Op.getOperand(1));
02250       GA = dyn_cast<GlobalAddressSDNode>(Op.getOperand(0));
02251       if (!C || !GA) {
02252         C = dyn_cast<ConstantSDNode>(Op.getOperand(0));
02253         GA = dyn_cast<GlobalAddressSDNode>(Op.getOperand(1));
02254       }
02255       if (!C || !GA)
02256         C = nullptr, GA = nullptr;
02257     }
02258 
02259     // If we find a valid operand, map to the TargetXXX version so that the
02260     // value itself doesn't get selected.
02261     if (GA) {   // Either &GV   or   &GV+C
02262       if (ConstraintLetter != 'n') {
02263         int64_t Offs = GA->getOffset();
02264         if (C) Offs += C->getZExtValue();
02265         Ops.push_back(DAG.getTargetGlobalAddress(GA->getGlobal(),
02266                                                  C ? SDLoc(C) : SDLoc(),
02267                                                  Op.getValueType(), Offs));
02268       }
02269       return;
02270     }
02271     if (C) {   // just C, no GV.
02272       // Simple constants are not allowed for 's'.
02273       if (ConstraintLetter != 's') {
02274         // gcc prints these as sign extended.  Sign extend value to 64 bits
02275         // now; without this it would get ZExt'd later in
02276         // ScheduleDAGSDNodes::EmitNode, which is very generic.
02277         Ops.push_back(DAG.getTargetConstant(C->getAPIntValue().getSExtValue(),
02278                                             SDLoc(C), MVT::i64));
02279       }
02280       return;
02281     }
02282     break;
02283   }
02284   }
02285 }
02286 
02287 std::pair<unsigned, const TargetRegisterClass *>
02288 TargetLowering::getRegForInlineAsmConstraint(const TargetRegisterInfo *RI,
02289                                              StringRef Constraint,
02290                                              MVT VT) const {
02291   if (Constraint.empty() || Constraint[0] != '{')
02292     return std::make_pair(0u, static_cast<TargetRegisterClass*>(nullptr));
02293   assert(*(Constraint.end()-1) == '}' && "Not a brace enclosed constraint?");
02294 
02295   // Remove the braces from around the name.
02296   StringRef RegName(Constraint.data()+1, Constraint.size()-2);
02297 
02298   std::pair<unsigned, const TargetRegisterClass*> R =
02299     std::make_pair(0u, static_cast<const TargetRegisterClass*>(nullptr));
02300 
02301   // Figure out which register class contains this reg.
02302   for (TargetRegisterInfo::regclass_iterator RCI = RI->regclass_begin(),
02303        E = RI->regclass_end(); RCI != E; ++RCI) {
02304     const TargetRegisterClass *RC = *RCI;
02305 
02306     // If none of the value types for this register class are valid, we
02307     // can't use it.  For example, 64-bit reg classes on 32-bit targets.
02308     if (!isLegalRC(RC))
02309       continue;
02310 
02311     for (TargetRegisterClass::iterator I = RC->begin(), E = RC->end();
02312          I != E; ++I) {
02313       if (RegName.equals_lower(RI->getName(*I))) {
02314         std::pair<unsigned, const TargetRegisterClass*> S =
02315           std::make_pair(*I, RC);
02316 
02317         // If this register class has the requested value type, return it,
02318         // otherwise keep searching and return the first class found
02319         // if no other is found which explicitly has the requested type.
02320         if (RC->hasType(VT))
02321           return S;
02322         else if (!R.second)
02323           R = S;
02324       }
02325     }
02326   }
02327 
02328   return R;
02329 }
02330 
02331 //===----------------------------------------------------------------------===//
02332 // Constraint Selection.
02333 
02334 /// Return true of this is an input operand that is a matching constraint like
02335 /// "4".
02336 bool TargetLowering::AsmOperandInfo::isMatchingInputConstraint() const {
02337   assert(!ConstraintCode.empty() && "No known constraint!");
02338   return isdigit(static_cast<unsigned char>(ConstraintCode[0]));
02339 }
02340 
02341 /// If this is an input matching constraint, this method returns the output
02342 /// operand it matches.
02343 unsigned TargetLowering::AsmOperandInfo::getMatchedOperand() const {
02344   assert(!ConstraintCode.empty() && "No known constraint!");
02345   return atoi(ConstraintCode.c_str());
02346 }
02347 
02348 /// Split up the constraint string from the inline assembly value into the
02349 /// specific constraints and their prefixes, and also tie in the associated
02350 /// operand values.
02351 /// If this returns an empty vector, and if the constraint string itself
02352 /// isn't empty, there was an error parsing.
02353 TargetLowering::AsmOperandInfoVector
02354 TargetLowering::ParseConstraints(const DataLayout &DL,
02355                                  const TargetRegisterInfo *TRI,
02356                                  ImmutableCallSite CS) const {
02357   /// Information about all of the constraints.
02358   AsmOperandInfoVector ConstraintOperands;
02359   const InlineAsm *IA = cast<InlineAsm>(CS.getCalledValue());
02360   unsigned maCount = 0; // Largest number of multiple alternative constraints.
02361 
02362   // Do a prepass over the constraints, canonicalizing them, and building up the
02363   // ConstraintOperands list.
02364   unsigned ArgNo = 0;   // ArgNo - The argument of the CallInst.
02365   unsigned ResNo = 0;   // ResNo - The result number of the next output.
02366 
02367   for (InlineAsm::ConstraintInfo &CI : IA->ParseConstraints()) {
02368     ConstraintOperands.emplace_back(std::move(CI));
02369     AsmOperandInfo &OpInfo = ConstraintOperands.back();
02370 
02371     // Update multiple alternative constraint count.
02372     if (OpInfo.multipleAlternatives.size() > maCount)
02373       maCount = OpInfo.multipleAlternatives.size();
02374 
02375     OpInfo.ConstraintVT = MVT::Other;
02376 
02377     // Compute the value type for each operand.
02378     switch (OpInfo.Type) {
02379     case InlineAsm::isOutput:
02380       // Indirect outputs just consume an argument.
02381       if (OpInfo.isIndirect) {
02382         OpInfo.CallOperandVal = const_cast<Value *>(CS.getArgument(ArgNo++));
02383         break;
02384       }
02385 
02386       // The return value of the call is this value.  As such, there is no
02387       // corresponding argument.
02388       assert(!CS.getType()->isVoidTy() &&
02389              "Bad inline asm!");
02390       if (StructType *STy = dyn_cast<StructType>(CS.getType())) {
02391         OpInfo.ConstraintVT =
02392             getSimpleValueType(DL, STy->getElementType(ResNo));
02393       } else {
02394         assert(ResNo == 0 && "Asm only has one result!");
02395         OpInfo.ConstraintVT = getSimpleValueType(DL, CS.getType());
02396       }
02397       ++ResNo;
02398       break;
02399     case InlineAsm::isInput:
02400       OpInfo.CallOperandVal = const_cast<Value *>(CS.getArgument(ArgNo++));
02401       break;
02402     case InlineAsm::isClobber:
02403       // Nothing to do.
02404       break;
02405     }
02406 
02407     if (OpInfo.CallOperandVal) {
02408       llvm::Type *OpTy = OpInfo.CallOperandVal->getType();
02409       if (OpInfo.isIndirect) {
02410         llvm::PointerType *PtrTy = dyn_cast<PointerType>(OpTy);
02411         if (!PtrTy)
02412           report_fatal_error("Indirect operand for inline asm not a pointer!");
02413         OpTy = PtrTy->getElementType();
02414       }
02415 
02416       // Look for vector wrapped in a struct. e.g. { <16 x i8> }.
02417       if (StructType *STy = dyn_cast<StructType>(OpTy))
02418         if (STy->getNumElements() == 1)
02419           OpTy = STy->getElementType(0);
02420 
02421       // If OpTy is not a single value, it may be a struct/union that we
02422       // can tile with integers.
02423       if (!OpTy->isSingleValueType() && OpTy->isSized()) {
02424         unsigned BitSize = DL.getTypeSizeInBits(OpTy);
02425         switch (BitSize) {
02426         default: break;
02427         case 1:
02428         case 8:
02429         case 16:
02430         case 32:
02431         case 64:
02432         case 128:
02433           OpInfo.ConstraintVT =
02434             MVT::getVT(IntegerType::get(OpTy->getContext(), BitSize), true);
02435           break;
02436         }
02437       } else if (PointerType *PT = dyn_cast<PointerType>(OpTy)) {
02438         unsigned PtrSize = DL.getPointerSizeInBits(PT->getAddressSpace());
02439         OpInfo.ConstraintVT = MVT::getIntegerVT(PtrSize);
02440       } else {
02441         OpInfo.ConstraintVT = MVT::getVT(OpTy, true);
02442       }
02443     }
02444   }
02445 
02446   // If we have multiple alternative constraints, select the best alternative.
02447   if (!ConstraintOperands.empty()) {
02448     if (maCount) {
02449       unsigned bestMAIndex = 0;
02450       int bestWeight = -1;
02451       // weight:  -1 = invalid match, and 0 = so-so match to 5 = good match.
02452       int weight = -1;
02453       unsigned maIndex;
02454       // Compute the sums of the weights for each alternative, keeping track
02455       // of the best (highest weight) one so far.
02456       for (maIndex = 0; maIndex < maCount; ++maIndex) {
02457         int weightSum = 0;
02458         for (unsigned cIndex = 0, eIndex = ConstraintOperands.size();
02459             cIndex != eIndex; ++cIndex) {
02460           AsmOperandInfo& OpInfo = ConstraintOperands[cIndex];
02461           if (OpInfo.Type == InlineAsm::isClobber)
02462             continue;
02463 
02464           // If this is an output operand with a matching input operand,
02465           // look up the matching input. If their types mismatch, e.g. one
02466           // is an integer, the other is floating point, or their sizes are
02467           // different, flag it as an maCantMatch.
02468           if (OpInfo.hasMatchingInput()) {
02469             AsmOperandInfo &Input = ConstraintOperands[OpInfo.MatchingInput];
02470             if (OpInfo.ConstraintVT != Input.ConstraintVT) {
02471               if ((OpInfo.ConstraintVT.isInteger() !=
02472                    Input.ConstraintVT.isInteger()) ||
02473                   (OpInfo.ConstraintVT.getSizeInBits() !=
02474                    Input.ConstraintVT.getSizeInBits())) {
02475                 weightSum = -1;  // Can't match.
02476                 break;
02477               }
02478             }
02479           }
02480           weight = getMultipleConstraintMatchWeight(OpInfo, maIndex);
02481           if (weight == -1) {
02482             weightSum = -1;
02483             break;
02484           }
02485           weightSum += weight;
02486         }
02487         // Update best.
02488         if (weightSum > bestWeight) {
02489           bestWeight = weightSum;
02490           bestMAIndex = maIndex;
02491         }
02492       }
02493 
02494       // Now select chosen alternative in each constraint.
02495       for (unsigned cIndex = 0, eIndex = ConstraintOperands.size();
02496           cIndex != eIndex; ++cIndex) {
02497         AsmOperandInfo& cInfo = ConstraintOperands[cIndex];
02498         if (cInfo.Type == InlineAsm::isClobber)
02499           continue;
02500         cInfo.selectAlternative(bestMAIndex);
02501       }
02502     }
02503   }
02504 
02505   // Check and hook up tied operands, choose constraint code to use.
02506   for (unsigned cIndex = 0, eIndex = ConstraintOperands.size();
02507       cIndex != eIndex; ++cIndex) {
02508     AsmOperandInfo& OpInfo = ConstraintOperands[cIndex];
02509 
02510     // If this is an output operand with a matching input operand, look up the
02511     // matching input. If their types mismatch, e.g. one is an integer, the
02512     // other is floating point, or their sizes are different, flag it as an
02513     // error.
02514     if (OpInfo.hasMatchingInput()) {
02515       AsmOperandInfo &Input = ConstraintOperands[OpInfo.MatchingInput];
02516 
02517       if (OpInfo.ConstraintVT != Input.ConstraintVT) {
02518         std::pair<unsigned, const TargetRegisterClass *> MatchRC =
02519             getRegForInlineAsmConstraint(TRI, OpInfo.ConstraintCode,
02520                                          OpInfo.ConstraintVT);
02521         std::pair<unsigned, const TargetRegisterClass *> InputRC =
02522             getRegForInlineAsmConstraint(TRI, Input.ConstraintCode,
02523                                          Input.ConstraintVT);
02524         if ((OpInfo.ConstraintVT.isInteger() !=
02525              Input.ConstraintVT.isInteger()) ||
02526             (MatchRC.second != InputRC.second)) {
02527           report_fatal_error("Unsupported asm: input constraint"
02528                              " with a matching output constraint of"
02529                              " incompatible type!");
02530         }
02531       }
02532     }
02533   }
02534 
02535   return ConstraintOperands;
02536 }
02537 
02538 /// Return an integer indicating how general CT is.
02539 static unsigned getConstraintGenerality(TargetLowering::ConstraintType CT) {
02540   switch (CT) {
02541   case TargetLowering::C_Other:
02542   case TargetLowering::C_Unknown:
02543     return 0;
02544   case TargetLowering::C_Register:
02545     return 1;
02546   case TargetLowering::C_RegisterClass:
02547     return 2;
02548   case TargetLowering::C_Memory:
02549     return 3;
02550   }
02551   llvm_unreachable("Invalid constraint type");
02552 }
02553 
02554 /// Examine constraint type and operand type and determine a weight value.
02555 /// This object must already have been set up with the operand type
02556 /// and the current alternative constraint selected.
02557 TargetLowering::ConstraintWeight
02558   TargetLowering::getMultipleConstraintMatchWeight(
02559     AsmOperandInfo &info, int maIndex) const {
02560   InlineAsm::ConstraintCodeVector *rCodes;
02561   if (maIndex >= (int)info.multipleAlternatives.size())
02562     rCodes = &info.Codes;
02563   else
02564     rCodes = &info.multipleAlternatives[maIndex].Codes;
02565   ConstraintWeight BestWeight = CW_Invalid;
02566 
02567   // Loop over the options, keeping track of the most general one.
02568   for (unsigned i = 0, e = rCodes->size(); i != e; ++i) {
02569     ConstraintWeight weight =
02570       getSingleConstraintMatchWeight(info, (*rCodes)[i].c_str());
02571     if (weight > BestWeight)
02572       BestWeight = weight;
02573   }
02574 
02575   return BestWeight;
02576 }
02577 
02578 /// Examine constraint type and operand type and determine a weight value.
02579 /// This object must already have been set up with the operand type
02580 /// and the current alternative constraint selected.
02581 TargetLowering::ConstraintWeight
02582   TargetLowering::getSingleConstraintMatchWeight(
02583     AsmOperandInfo &info, const char *constraint) const {
02584   ConstraintWeight weight = CW_Invalid;
02585   Value *CallOperandVal = info.CallOperandVal;
02586     // If we don't have a value, we can't do a match,
02587     // but allow it at the lowest weight.
02588   if (!CallOperandVal)
02589     return CW_Default;
02590   // Look at the constraint type.
02591   switch (*constraint) {
02592     case 'i': // immediate integer.
02593     case 'n': // immediate integer with a known value.
02594       if (isa<ConstantInt>(CallOperandVal))
02595         weight = CW_Constant;
02596       break;
02597     case 's': // non-explicit intregal immediate.
02598       if (isa<GlobalValue>(CallOperandVal))
02599         weight = CW_Constant;
02600       break;
02601     case 'E': // immediate float if host format.
02602     case 'F': // immediate float.
02603       if (isa<ConstantFP>(CallOperandVal))
02604         weight = CW_Constant;
02605       break;
02606     case '<': // memory operand with autodecrement.
02607     case '>': // memory operand with autoincrement.
02608     case 'm': // memory operand.
02609     case 'o': // offsettable memory operand
02610     case 'V': // non-offsettable memory operand
02611       weight = CW_Memory;
02612       break;
02613     case 'r': // general register.
02614     case 'g': // general register, memory operand or immediate integer.
02615               // note: Clang converts "g" to "imr".
02616       if (CallOperandVal->getType()->isIntegerTy())
02617         weight = CW_Register;
02618       break;
02619     case 'X': // any operand.
02620     default:
02621       weight = CW_Default;
02622       break;
02623   }
02624   return weight;
02625 }
02626 
02627 /// If there are multiple different constraints that we could pick for this
02628 /// operand (e.g. "imr") try to pick the 'best' one.
02629 /// This is somewhat tricky: constraints fall into four classes:
02630 ///    Other         -> immediates and magic values
02631 ///    Register      -> one specific register
02632 ///    RegisterClass -> a group of regs
02633 ///    Memory        -> memory
02634 /// Ideally, we would pick the most specific constraint possible: if we have
02635 /// something that fits into a register, we would pick it.  The problem here
02636 /// is that if we have something that could either be in a register or in
02637 /// memory that use of the register could cause selection of *other*
02638 /// operands to fail: they might only succeed if we pick memory.  Because of
02639 /// this the heuristic we use is:
02640 ///
02641 ///  1) If there is an 'other' constraint, and if the operand is valid for
02642 ///     that constraint, use it.  This makes us take advantage of 'i'
02643 ///     constraints when available.
02644 ///  2) Otherwise, pick the most general constraint present.  This prefers
02645 ///     'm' over 'r', for example.
02646 ///
02647 static void ChooseConstraint(TargetLowering::AsmOperandInfo &OpInfo,
02648                              const TargetLowering &TLI,
02649                              SDValue Op, SelectionDAG *DAG) {
02650   assert(OpInfo.Codes.size() > 1 && "Doesn't have multiple constraint options");
02651   unsigned BestIdx = 0;
02652   TargetLowering::ConstraintType BestType = TargetLowering::C_Unknown;
02653   int BestGenerality = -1;
02654 
02655   // Loop over the options, keeping track of the most general one.
02656   for (unsigned i = 0, e = OpInfo.Codes.size(); i != e; ++i) {
02657     TargetLowering::ConstraintType CType =
02658       TLI.getConstraintType(OpInfo.Codes[i]);
02659 
02660     // If this is an 'other' constraint, see if the operand is valid for it.
02661     // For example, on X86 we might have an 'rI' constraint.  If the operand
02662     // is an integer in the range [0..31] we want to use I (saving a load
02663     // of a register), otherwise we must use 'r'.
02664     if (CType == TargetLowering::C_Other && Op.getNode()) {
02665       assert(OpInfo.Codes[i].size() == 1 &&
02666              "Unhandled multi-letter 'other' constraint");
02667       std::vector<SDValue> ResultOps;
02668       TLI.LowerAsmOperandForConstraint(Op, OpInfo.Codes[i],
02669                                        ResultOps, *DAG);
02670       if (!ResultOps.empty()) {
02671         BestType = CType;
02672         BestIdx = i;
02673         break;
02674       }
02675     }
02676 
02677     // Things with matching constraints can only be registers, per gcc
02678     // documentation.  This mainly affects "g" constraints.
02679     if (CType == TargetLowering::C_Memory && OpInfo.hasMatchingInput())
02680       continue;
02681 
02682     // This constraint letter is more general than the previous one, use it.
02683     int Generality = getConstraintGenerality(CType);
02684     if (Generality > BestGenerality) {
02685       BestType = CType;
02686       BestIdx = i;
02687       BestGenerality = Generality;
02688     }
02689   }
02690 
02691   OpInfo.ConstraintCode = OpInfo.Codes[BestIdx];
02692   OpInfo.ConstraintType = BestType;
02693 }
02694 
02695 /// Determines the constraint code and constraint type to use for the specific
02696 /// AsmOperandInfo, setting OpInfo.ConstraintCode and OpInfo.ConstraintType.
02697 void TargetLowering::ComputeConstraintToUse(AsmOperandInfo &OpInfo,
02698                                             SDValue Op,
02699                                             SelectionDAG *DAG) const {
02700   assert(!OpInfo.Codes.empty() && "Must have at least one constraint");
02701 
02702   // Single-letter constraints ('r') are very common.
02703   if (OpInfo.Codes.size() == 1) {
02704     OpInfo.ConstraintCode = OpInfo.Codes[0];
02705     OpInfo.ConstraintType = getConstraintType(OpInfo.ConstraintCode);
02706   } else {
02707     ChooseConstraint(OpInfo, *this, Op, DAG);
02708   }
02709 
02710   // 'X' matches anything.
02711   if (OpInfo.ConstraintCode == "X" && OpInfo.CallOperandVal) {
02712     // Labels and constants are handled elsewhere ('X' is the only thing
02713     // that matches labels).  For Functions, the type here is the type of
02714     // the result, which is not what we want to look at; leave them alone.
02715     Value *v = OpInfo.CallOperandVal;
02716     if (isa<BasicBlock>(v) || isa<ConstantInt>(v) || isa<Function>(v)) {
02717       OpInfo.CallOperandVal = v;
02718       return;
02719     }
02720 
02721     // Otherwise, try to resolve it to something we know about by looking at
02722     // the actual operand type.
02723     if (const char *Repl = LowerXConstraint(OpInfo.ConstraintVT)) {
02724       OpInfo.ConstraintCode = Repl;
02725       OpInfo.ConstraintType = getConstraintType(OpInfo.ConstraintCode);
02726     }
02727   }
02728 }
02729 
02730 /// \brief Given an exact SDIV by a constant, create a multiplication
02731 /// with the multiplicative inverse of the constant.
02732 static SDValue BuildExactSDIV(const TargetLowering &TLI, SDValue Op1, APInt d,
02733                               SDLoc dl, SelectionDAG &DAG,
02734                               std::vector<SDNode *> &Created) {
02735   assert(d != 0 && "Division by zero!");
02736 
02737   // Shift the value upfront if it is even, so the LSB is one.
02738   unsigned ShAmt = d.countTrailingZeros();
02739   if (ShAmt) {
02740     // TODO: For UDIV use SRL instead of SRA.
02741     SDValue Amt =
02742         DAG.getConstant(ShAmt, dl, TLI.getShiftAmountTy(Op1.getValueType(),
02743                                                         DAG.getDataLayout()));
02744     SDNodeFlags Flags;
02745     Flags.setExact(true);
02746     Op1 = DAG.getNode(ISD::SRA, dl, Op1.getValueType(), Op1, Amt, &Flags);
02747     Created.push_back(Op1.getNode());
02748     d = d.ashr(ShAmt);
02749   }
02750 
02751   // Calculate the multiplicative inverse, using Newton's method.
02752   APInt t, xn = d;
02753   while ((t = d*xn) != 1)
02754     xn *= APInt(d.getBitWidth(), 2) - t;
02755 
02756   SDValue Op2 = DAG.getConstant(xn, dl, Op1.getValueType());
02757   SDValue Mul = DAG.getNode(ISD::MUL, dl, Op1.getValueType(), Op1, Op2);
02758   Created.push_back(Mul.getNode());
02759   return Mul;
02760 }
02761 
02762 SDValue TargetLowering::BuildSDIVPow2(SDNode *N, const APInt &Divisor,
02763                                       SelectionDAG &DAG,
02764                                       std::vector<SDNode *> *Created) const {
02765   AttributeSet Attr = DAG.getMachineFunction().getFunction()->getAttributes();
02766   const TargetLowering &TLI = DAG.getTargetLoweringInfo();
02767   if (TLI.isIntDivCheap(N->getValueType(0), Attr))
02768     return SDValue(N,0); // Lower SDIV as SDIV
02769   return SDValue();
02770 }
02771 
02772 /// \brief Given an ISD::SDIV node expressing a divide by constant,
02773 /// return a DAG expression to select that will generate the same value by
02774 /// multiplying by a magic number.
02775 /// Ref: "Hacker's Delight" or "The PowerPC Compiler Writer's Guide".
02776 SDValue TargetLowering::BuildSDIV(SDNode *N, const APInt &Divisor,
02777                                   SelectionDAG &DAG, bool IsAfterLegalization,
02778                                   std::vector<SDNode *> *Created) const {
02779   assert(Created && "No vector to hold sdiv ops.");
02780 
02781   EVT VT = N->getValueType(0);
02782   SDLoc dl(N);
02783 
02784   // Check to see if we can do this.
02785   // FIXME: We should be more aggressive here.
02786   if (!isTypeLegal(VT))
02787     return SDValue();
02788 
02789   // If the sdiv has an 'exact' bit we can use a simpler lowering.
02790   if (cast<BinaryWithFlagsSDNode>(N)->Flags.hasExact())
02791     return BuildExactSDIV(*this, N->getOperand(0), Divisor, dl, DAG, *Created);
02792 
02793   APInt::ms magics = Divisor.magic();
02794 
02795   // Multiply the numerator (operand 0) by the magic value
02796   // FIXME: We should support doing a MUL in a wider type
02797   SDValue Q;
02798   if (IsAfterLegalization ? isOperationLegal(ISD::MULHS, VT) :
02799                             isOperationLegalOrCustom(ISD::MULHS, VT))
02800     Q = DAG.getNode(ISD::MULHS, dl, VT, N->getOperand(0),
02801                     DAG.getConstant(magics.m, dl, VT));
02802   else if (IsAfterLegalization ? isOperationLegal(ISD::SMUL_LOHI, VT) :
02803                                  isOperationLegalOrCustom(ISD::SMUL_LOHI, VT))
02804     Q = SDValue(DAG.getNode(ISD::SMUL_LOHI, dl, DAG.getVTList(VT, VT),
02805                               N->getOperand(0),
02806                               DAG.getConstant(magics.m, dl, VT)).getNode(), 1);
02807   else
02808     return SDValue();       // No mulhs or equvialent
02809   // If d > 0 and m < 0, add the numerator
02810   if (Divisor.isStrictlyPositive() && magics.m.isNegative()) {
02811     Q = DAG.getNode(ISD::ADD, dl, VT, Q, N->getOperand(0));
02812     Created->push_back(Q.getNode());
02813   }
02814   // If d < 0 and m > 0, subtract the numerator.
02815   if (Divisor.isNegative() && magics.m.isStrictlyPositive()) {
02816     Q = DAG.getNode(ISD::SUB, dl, VT, Q, N->getOperand(0));
02817     Created->push_back(Q.getNode());
02818   }
02819   auto &DL = DAG.getDataLayout();
02820   // Shift right algebraic if shift value is nonzero
02821   if (magics.s > 0) {
02822     Q = DAG.getNode(
02823         ISD::SRA, dl, VT, Q,
02824         DAG.getConstant(magics.s, dl, getShiftAmountTy(Q.getValueType(), DL)));
02825     Created->push_back(Q.getNode());
02826   }
02827   // Extract the sign bit and add it to the quotient
02828   SDValue T =
02829       DAG.getNode(ISD::SRL, dl, VT, Q,
02830                   DAG.getConstant(VT.getScalarSizeInBits() - 1, dl,
02831                                   getShiftAmountTy(Q.getValueType(), DL)));
02832   Created->push_back(T.getNode());
02833   return DAG.getNode(ISD::ADD, dl, VT, Q, T);
02834 }
02835 
02836 /// \brief Given an ISD::UDIV node expressing a divide by constant,
02837 /// return a DAG expression to select that will generate the same value by
02838 /// multiplying by a magic number.
02839 /// Ref: "Hacker's Delight" or "The PowerPC Compiler Writer's Guide".
02840 SDValue TargetLowering::BuildUDIV(SDNode *N, const APInt &Divisor,
02841                                   SelectionDAG &DAG, bool IsAfterLegalization,
02842                                   std::vector<SDNode *> *Created) const {
02843   assert(Created && "No vector to hold udiv ops.");
02844 
02845   EVT VT = N->getValueType(0);
02846   SDLoc dl(N);
02847   auto &DL = DAG.getDataLayout();
02848 
02849   // Check to see if we can do this.
02850   // FIXME: We should be more aggressive here.
02851   if (!isTypeLegal(VT))
02852     return SDValue();
02853 
02854   // FIXME: We should use a narrower constant when the upper
02855   // bits are known to be zero.
02856   APInt::mu magics = Divisor.magicu();
02857 
02858   SDValue Q = N->getOperand(0);
02859 
02860   // If the divisor is even, we can avoid using the expensive fixup by shifting
02861   // the divided value upfront.
02862   if (magics.a != 0 && !Divisor[0]) {
02863     unsigned Shift = Divisor.countTrailingZeros();
02864     Q = DAG.getNode(
02865         ISD::SRL, dl, VT, Q,
02866         DAG.getConstant(Shift, dl, getShiftAmountTy(Q.getValueType(), DL)));
02867     Created->push_back(Q.getNode());
02868 
02869     // Get magic number for the shifted divisor.
02870     magics = Divisor.lshr(Shift).magicu(Shift);
02871     assert(magics.a == 0 && "Should use cheap fixup now");
02872   }
02873 
02874   // Multiply the numerator (operand 0) by the magic value
02875   // FIXME: We should support doing a MUL in a wider type
02876   if (IsAfterLegalization ? isOperationLegal(ISD::MULHU, VT) :
02877                             isOperationLegalOrCustom(ISD::MULHU, VT))
02878     Q = DAG.getNode(ISD::MULHU, dl, VT, Q, DAG.getConstant(magics.m, dl, VT));
02879   else if (IsAfterLegalization ? isOperationLegal(ISD::UMUL_LOHI, VT) :
02880                                  isOperationLegalOrCustom(ISD::UMUL_LOHI, VT))
02881     Q = SDValue(DAG.getNode(ISD::UMUL_LOHI, dl, DAG.getVTList(VT, VT), Q,
02882                             DAG.getConstant(magics.m, dl, VT)).getNode(), 1);
02883   else
02884     return SDValue();       // No mulhu or equvialent
02885 
02886   Created->push_back(Q.getNode());
02887 
02888   if (magics.a == 0) {
02889     assert(magics.s < Divisor.getBitWidth() &&
02890            "We shouldn't generate an undefined shift!");
02891     return DAG.getNode(
02892         ISD::SRL, dl, VT, Q,
02893         DAG.getConstant(magics.s, dl, getShiftAmountTy(Q.getValueType(), DL)));
02894   } else {
02895     SDValue NPQ = DAG.getNode(ISD::SUB, dl, VT, N->getOperand(0), Q);
02896     Created->push_back(NPQ.getNode());
02897     NPQ = DAG.getNode(
02898         ISD::SRL, dl, VT, NPQ,
02899         DAG.getConstant(1, dl, getShiftAmountTy(NPQ.getValueType(), DL)));
02900     Created->push_back(NPQ.getNode());
02901     NPQ = DAG.getNode(ISD::ADD, dl, VT, NPQ, Q);
02902     Created->push_back(NPQ.getNode());
02903     return DAG.getNode(
02904         ISD::SRL, dl, VT, NPQ,
02905         DAG.getConstant(magics.s - 1, dl,
02906                         getShiftAmountTy(NPQ.getValueType(), DL)));
02907   }
02908 }
02909 
02910 bool TargetLowering::
02911 verifyReturnAddressArgumentIsConstant(SDValue Op, SelectionDAG &DAG) const {
02912   if (!isa<ConstantSDNode>(Op.getOperand(0))) {
02913     DAG.getContext()->emitError("argument to '__builtin_return_address' must "
02914                                 "be a constant integer");
02915     return true;
02916   }
02917 
02918   return false;
02919 }
02920 
02921 //===----------------------------------------------------------------------===//
02922 // Legalization Utilities
02923 //===----------------------------------------------------------------------===//
02924 
02925 bool TargetLowering::expandMUL(SDNode *N, SDValue &Lo, SDValue &Hi, EVT HiLoVT,
02926                                SelectionDAG &DAG, SDValue LL, SDValue LH,
02927                                SDValue RL, SDValue RH) const {
02928   EVT VT = N->getValueType(0);
02929   SDLoc dl(N);
02930 
02931   bool HasMULHS = isOperationLegalOrCustom(ISD::MULHS, HiLoVT);
02932   bool HasMULHU = isOperationLegalOrCustom(ISD::MULHU, HiLoVT);
02933   bool HasSMUL_LOHI = isOperationLegalOrCustom(ISD::SMUL_LOHI, HiLoVT);
02934   bool HasUMUL_LOHI = isOperationLegalOrCustom(ISD::UMUL_LOHI, HiLoVT);
02935   if (HasMULHU || HasMULHS || HasUMUL_LOHI || HasSMUL_LOHI) {
02936     unsigned OuterBitSize = VT.getSizeInBits();
02937     unsigned InnerBitSize = HiLoVT.getSizeInBits();
02938     unsigned LHSSB = DAG.ComputeNumSignBits(N->getOperand(0));
02939     unsigned RHSSB = DAG.ComputeNumSignBits(N->getOperand(1));
02940 
02941     // LL, LH, RL, and RH must be either all NULL or all set to a value.
02942     assert((LL.getNode() && LH.getNode() && RL.getNode() && RH.getNode()) ||
02943            (!LL.getNode() && !LH.getNode() && !RL.getNode() && !RH.getNode()));
02944 
02945     if (!LL.getNode() && !RL.getNode() &&
02946         isOperationLegalOrCustom(ISD::TRUNCATE, HiLoVT)) {
02947       LL = DAG.getNode(ISD::TRUNCATE, dl, HiLoVT, N->getOperand(0));
02948       RL = DAG.getNode(ISD::TRUNCATE, dl, HiLoVT, N->getOperand(1));
02949     }
02950 
02951     if (!LL.getNode())
02952       return false;
02953 
02954     APInt HighMask = APInt::getHighBitsSet(OuterBitSize, InnerBitSize);
02955     if (DAG.MaskedValueIsZero(N->getOperand(0), HighMask) &&
02956         DAG.MaskedValueIsZero(N->getOperand(1), HighMask)) {
02957       // The inputs are both zero-extended.
02958       if (HasUMUL_LOHI) {
02959         // We can emit a umul_lohi.
02960         Lo = DAG.getNode(ISD::UMUL_LOHI, dl, DAG.getVTList(HiLoVT, HiLoVT), LL,
02961                          RL);
02962         Hi = SDValue(Lo.getNode(), 1);
02963         return true;
02964       }
02965       if (HasMULHU) {
02966         // We can emit a mulhu+mul.
02967         Lo = DAG.getNode(ISD::MUL, dl, HiLoVT, LL, RL);
02968         Hi = DAG.getNode(ISD::MULHU, dl, HiLoVT, LL, RL);
02969         return true;
02970       }
02971     }
02972     if (LHSSB > InnerBitSize && RHSSB > InnerBitSize) {
02973       // The input values are both sign-extended.
02974       if (HasSMUL_LOHI) {
02975         // We can emit a smul_lohi.
02976         Lo = DAG.getNode(ISD::SMUL_LOHI, dl, DAG.getVTList(HiLoVT, HiLoVT), LL,
02977                          RL);
02978         Hi = SDValue(Lo.getNode(), 1);
02979         return true;
02980       }
02981       if (HasMULHS) {
02982         // We can emit a mulhs+mul.
02983         Lo = DAG.getNode(ISD::MUL, dl, HiLoVT, LL, RL);
02984         Hi = DAG.getNode(ISD::MULHS, dl, HiLoVT, LL, RL);
02985         return true;
02986       }
02987     }
02988 
02989     if (!LH.getNode() && !RH.getNode() &&
02990         isOperationLegalOrCustom(ISD::SRL, VT) &&
02991         isOperationLegalOrCustom(ISD::TRUNCATE, HiLoVT)) {
02992       auto &DL = DAG.getDataLayout();
02993       unsigned ShiftAmt = VT.getSizeInBits() - HiLoVT.getSizeInBits();
02994       SDValue Shift = DAG.getConstant(ShiftAmt, dl, getShiftAmountTy(VT, DL));
02995       LH = DAG.getNode(ISD::SRL, dl, VT, N->getOperand(0), Shift);
02996       LH = DAG.getNode(ISD::TRUNCATE, dl, HiLoVT, LH);
02997       RH = DAG.getNode(ISD::SRL, dl, VT, N->getOperand(1), Shift);
02998       RH = DAG.getNode(ISD::TRUNCATE, dl, HiLoVT, RH);
02999     }
03000 
03001     if (!LH.getNode())
03002       return false;
03003 
03004     if (HasUMUL_LOHI) {
03005       // Lo,Hi = umul LHS, RHS.
03006       SDValue UMulLOHI = DAG.getNode(ISD::UMUL_LOHI, dl,
03007                                      DAG.getVTList(HiLoVT, HiLoVT), LL, RL);
03008       Lo = UMulLOHI;
03009       Hi = UMulLOHI.getValue(1);
03010       RH = DAG.getNode(ISD::MUL, dl, HiLoVT, LL, RH);
03011       LH = DAG.getNode(ISD::MUL, dl, HiLoVT, LH, RL);
03012       Hi = DAG.getNode(ISD::ADD, dl, HiLoVT, Hi, RH);
03013       Hi = DAG.getNode(ISD::ADD, dl, HiLoVT, Hi, LH);
03014       return true;
03015     }
03016     if (HasMULHU) {
03017       Lo = DAG.getNode(ISD::MUL, dl, HiLoVT, LL, RL);
03018       Hi = DAG.getNode(ISD::MULHU, dl, HiLoVT, LL, RL);
03019       RH = DAG.getNode(ISD::MUL, dl, HiLoVT, LL, RH);
03020       LH = DAG.getNode(ISD::MUL, dl, HiLoVT, LH, RL);
03021       Hi = DAG.getNode(ISD::ADD, dl, HiLoVT, Hi, RH);
03022       Hi = DAG.getNode(ISD::ADD, dl, HiLoVT, Hi, LH);
03023       return true;
03024     }
03025   }
03026   return false;
03027 }
03028 
03029 bool TargetLowering::expandFP_TO_SINT(SDNode *Node, SDValue &Result,
03030                                SelectionDAG &DAG) const {
03031   EVT VT = Node->getOperand(0).getValueType();
03032   EVT NVT = Node->getValueType(0);
03033   SDLoc dl(SDValue(Node, 0));
03034 
03035   // FIXME: Only f32 to i64 conversions are supported.
03036   if (VT != MVT::f32 || NVT != MVT::i64)
03037     return false;
03038 
03039   // Expand f32 -> i64 conversion
03040   // This algorithm comes from compiler-rt's implementation of fixsfdi:
03041   // https://github.com/llvm-mirror/compiler-rt/blob/master/lib/builtins/fixsfdi.c
03042   EVT IntVT = EVT::getIntegerVT(*DAG.getContext(),
03043                                 VT.getSizeInBits());
03044   SDValue ExponentMask = DAG.getConstant(0x7F800000, dl, IntVT);
03045   SDValue ExponentLoBit = DAG.getConstant(23, dl, IntVT);
03046   SDValue Bias = DAG.getConstant(127, dl, IntVT);
03047   SDValue SignMask = DAG.getConstant(APInt::getSignBit(VT.getSizeInBits()), dl,
03048                                      IntVT);
03049   SDValue SignLowBit = DAG.getConstant(VT.getSizeInBits() - 1, dl, IntVT);
03050   SDValue MantissaMask = DAG.getConstant(0x007FFFFF, dl, IntVT);
03051 
03052   SDValue Bits = DAG.getNode(ISD::BITCAST, dl, IntVT, Node->getOperand(0));
03053 
03054   auto &DL = DAG.getDataLayout();
03055   SDValue ExponentBits = DAG.getNode(
03056       ISD::SRL, dl, IntVT, DAG.getNode(ISD::AND, dl, IntVT, Bits, ExponentMask),
03057       DAG.getZExtOrTrunc(ExponentLoBit, dl, getShiftAmountTy(IntVT, DL)));
03058   SDValue Exponent = DAG.getNode(ISD::SUB, dl, IntVT, ExponentBits, Bias);
03059 
03060   SDValue Sign = DAG.getNode(
03061       ISD::SRA, dl, IntVT, DAG.getNode(ISD::AND, dl, IntVT, Bits, SignMask),
03062       DAG.getZExtOrTrunc(SignLowBit, dl, getShiftAmountTy(IntVT, DL)));
03063   Sign = DAG.getSExtOrTrunc(Sign, dl, NVT);
03064 
03065   SDValue R = DAG.getNode(ISD::OR, dl, IntVT,
03066       DAG.getNode(ISD::AND, dl, IntVT, Bits, MantissaMask),
03067       DAG.getConstant(0x00800000, dl, IntVT));
03068 
03069   R = DAG.getZExtOrTrunc(R, dl, NVT);
03070 
03071   R = DAG.getSelectCC(
03072       dl, Exponent, ExponentLoBit,
03073       DAG.getNode(ISD::SHL, dl, NVT, R,
03074                   DAG.getZExtOrTrunc(
03075                       DAG.getNode(ISD::SUB, dl, IntVT, Exponent, ExponentLoBit),
03076                       dl, getShiftAmountTy(IntVT, DL))),
03077       DAG.getNode(ISD::SRL, dl, NVT, R,
03078                   DAG.getZExtOrTrunc(
03079                       DAG.getNode(ISD::SUB, dl, IntVT, ExponentLoBit, Exponent),
03080                       dl, getShiftAmountTy(IntVT, DL))),
03081       ISD::SETGT);
03082 
03083   SDValue Ret = DAG.getNode(ISD::SUB, dl, NVT,
03084       DAG.getNode(ISD::XOR, dl, NVT, R, Sign),
03085       Sign);
03086 
03087   Result = DAG.getSelectCC(dl, Exponent, DAG.getConstant(0, dl, IntVT),
03088       DAG.getConstant(0, dl, NVT), Ret, ISD::SETLT);
03089   return true;
03090 }
03091 
03092 //===----------------------------------------------------------------------===//
03093 // Implementation of Emulated TLS Model
03094 //===----------------------------------------------------------------------===//
03095 
03096 SDValue TargetLowering::LowerToTLSEmulatedModel(const GlobalAddressSDNode *GA,
03097                                                 SelectionDAG &DAG) const {
03098   // Access to address of TLS varialbe xyz is lowered to a function call:
03099   //   __emutls_get_address( address of global variable named "__emutls_v.xyz" )
03100   EVT PtrVT = getPointerTy(DAG.getDataLayout());
03101   PointerType *VoidPtrType = Type::getInt8PtrTy(*DAG.getContext());
03102   SDLoc dl(GA);
03103 
03104   ArgListTy Args;
03105   ArgListEntry Entry;
03106   std::string NameString = ("__emutls_v." + GA->getGlobal()->getName()).str();
03107   Module *VariableModule = const_cast<Module*>(GA->getGlobal()->getParent());
03108   StringRef EmuTlsVarName(NameString);
03109   GlobalVariable *EmuTlsVar = VariableModule->getNamedGlobal(EmuTlsVarName);
03110   assert(EmuTlsVar && "Cannot find EmuTlsVar ");
03111   Entry.Node = DAG.getGlobalAddress(EmuTlsVar, dl, PtrVT);
03112   Entry.Ty = VoidPtrType;
03113   Args.push_back(Entry);
03114 
03115   SDValue EmuTlsGetAddr = DAG.getExternalSymbol("__emutls_get_address", PtrVT);
03116 
03117   TargetLowering::CallLoweringInfo CLI(DAG);
03118   CLI.setDebugLoc(dl).setChain(DAG.getEntryNode());
03119   CLI.setCallee(CallingConv::C, VoidPtrType, EmuTlsGetAddr, std::move(Args), 0);
03120   std::pair<SDValue, SDValue> CallResult = LowerCallTo(CLI);
03121 
03122   // TLSADDR will be codegen'ed as call. Inform MFI that function has calls.
03123   // At last for X86 targets, maybe good for other targets too?
03124   MachineFrameInfo *MFI = DAG.getMachineFunction().getFrameInfo();
03125   MFI->setAdjustsStack(true);  // Is this only for X86 target?
03126   MFI->setHasCalls(true);
03127 
03128   assert((GA->getOffset() == 0) &&
03129          "Emulated TLS must have zero offset in GlobalAddressSDNode");
03130   return CallResult.first;
03131 }