class DAGCombiner {
SelectionDAG &DAG;
const TargetLowering &TLI;
CombineLevel Level;
CodeGenOpt::Level OptLevel;
bool LegalOperations;
bool LegalTypes;

SmallPtrSet<SDNode*, 64> WorkListContents;
SmallVector<SDNode*, 64> WorkListOrder;

AliasAnalysis &AA;

// Add SDnodes users to worklist
void AddUsersToWorkList(SDNode *N) {
  for (SDNode::use_iterator UI = N->use_begin(),
        UE = N->use_end(); UI != UE; ++UI)
    AddToWorkList(*UI);
}
SDValue visit(SDNode *N);

public:

void AddToWorkList(SDNode *N) {
  WorkListContents.insert(N);
  WorkListOrder.push_back(N);
}

void removeFromWorkList(SDNode *N) {
  WorkListContents.erase(N);
}

// SDnode combine operations.
SDValue CombineTo(SDNode *N, const SDValue *To, unsigned NumTo,
bool AddTo = true);

SDValue CombineTo(SDNode *N, SDValue Res, bool AddTo = true) {
  return CombineTo(N, &Res, 1, AddTo);
}

SDValue CombineTo(SDNode *N, SDValue Res0, SDValue Res1,
bool AddTo = true) {
  SDValue To[] = { Res0, Res1 };
  return CombineTo(N, To, 2, AddTo);
}
void CommitTargetLoweringOpt(const TargetLowering::TargetLoweringOpt &TLO);

private:

bool SimplifyDemandedBits(SDValue Op) {
  unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
  APInt Demanded = APInt::getAllOnesValue(BitWidth);
  return SimplifyDemandedBits(Op, Demanded);
}
bool SimplifyDemandedBits(SDValue Op, const APInt &Demanded);

bool CombineToPreIndexedLoadStore(SDNode *N);

bool CombineToPostIndexedLoadStore(SDNode *N);

void ReplaceLoadWithPromotedLoad(SDNode *Load, SDNode *ExtLoad);

SDValue PromoteOperand(SDValue Op, EVT PVT, bool &Replace);

SDValue SExtPromoteOperand(SDValue Op, EVT PVT);

SDValue ZExtPromoteOperand(SDValue Op, EVT PVT);

SDValue PromoteIntBinOp(SDValue Op);

SDValue PromoteIntShiftOp(SDValue Op);

SDValue PromoteExtend(SDValue Op);

bool PromoteLoad(SDValue Op);

void ExtendSetCCUses(SmallVector<SDNode*, 4> SetCCs,
SDValue Trunc, SDValue ExtLoad, DebugLoc DL,
ISD::NodeType ExtType);

SDValue combine(SDNode *N);

// Various visit functions operating on instructions represented
// by SD node. Similar to instruction combining at IR level.
SDValue visitTokenFactor(SDNode *N);

SDValue visitMERGE_VALUES(SDNode *N);

SDValue visitADD(SDNode *N);
SDValue visitSUB(SDNode *N);
SDValue visitADDC(SDNode *N);
SDValue visitSUBC(SDNode *N);
SDValue visitADDE(SDNode *N);
SDValue visitSUBE(SDNode *N);
SDValue visitMUL(SDNode *N);

public:

DAGCombiner(SelectionDAG &D, AliasAnalysis &A, CodeGenOpt::Level OL)
: DAG(D), TLI(D.getTargetLoweringInfo()), Level(BeforeLegalizeTypes),
  OptLevel(OL), LegalOperations(false), LegalTypes(false), AA(A) {}

// Selection DAG transformation for following ops
SDValue DAGCombiner::visitMUL(SDNode *N) {
  SDValue N0 = N->getOperand(0);
  SDValue N1 = N->getOperand(1);
  ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0);
  ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1);
  EVT VT = N0.getValueType();
  if (VT.isVector()) {
    SDValue FoldedVOp = SimplifyVBinOp(N);
    if (FoldedVOp.getNode()) return FoldedVOp;
  }
  if (N0.getOpcode() == ISD::UNDEF || N1.getOpcode() == ISD::UNDEF)
    return DAG.getConstant(0, VT);

  if (N0C && N1C)
    return DAG.FoldConstantArithmetic(ISD::MUL, VT, N0C, N1C);

  if (N0C && !N1C)
    return DAG.getNode(ISD::MUL, N->getDebugLoc(), VT, N1, N0);

  if (N1C && N1C->isNullValue())
    return N1;

  if (N1C && N1C->isAllOnesValue())
    return DAG.getNode(ISD::SUB, N->getDebugLoc(), VT, DAG.getConstant(0, VT), N0);
  if (N1C && N1C->getAPIntValue().isPowerOf2())
    return DAG.getNode(ISD::SHL, N->getDebugLoc(), VT, N0,
           DAG.getConstant(N1C->getAPIntValue().logBase2(),
               getShiftAmountTy(N0.getValueType())));

  if (N1C && (-N1C->getAPIntValue()).isPowerOf2()) {
    unsigned Log2Val = (-N1C->getAPIntValue()).logBase2();
    return DAG.getNode(ISD::SUB, N->getDebugLoc(), VT, DAG.getConstant(0, VT),
    DAG.getNode(ISD::SHL, N->getDebugLoc(), VT, N0,
    DAG.getConstant(Log2Val, getShiftAmountTy(N0.getValueType()))));
  }

  if (N1C && N0.getOpcode() == ISD::SHL &&
      isa<ConstantSDNode>(N0.getOperand(1))) {
    SDValue C3 = DAG.getNode(ISD::SHL, N->getDebugLoc(), VT, N1, N0.getOperand(1));
    AddToWorkList(C3.getNode());
    return DAG.getNode(ISD::MUL, N->getDebugLoc(), VT,
    N0.getOperand(0), C3);
  }

  if (N0.getOpcode() == ISD::SHL && isa<ConstantSDNode>(N0.getOperand(1)) &&
      N0.getNode()->hasOneUse()) {
    Sh = N0; Y = N1;
  } else if (N1.getOpcode() == ISD::SHL && isa<ConstantSDNode>(N1.getOperand(1)) &&
            N1.getNode()->hasOneUse()) {
    Sh = N1; Y = N0;
  }
  if (Sh.getNode()) {
  SDValue Mul = DAG.getNode(ISD::MUL, N->getDebugLoc(), VT, Sh.getOperand(0), Y);
    return DAG.getNode(ISD::SHL, N->getDebugLoc(), VT,
    Mul, Sh.getOperand(1));
    }
  }
  if (N1C && N0.getOpcode() == ISD::ADD && N0.getNode()->hasOneUse() &&
      isa<ConstantSDNode>(N0.getOperand(1)))
    return DAG.getNode(ISD::ADD, N->getDebugLoc(), VT, DAG.getNode(ISD::MUL, N0.getDebugLoc(),
    VT, N0.getOperand(0), N1), DAG.getNode(ISD::MUL, N1.getDebugLoc(), VT, N0.getOperand(1), N1));

  SDValue RMUL = ReassociateOps(ISD::MUL, N->getDebugLoc(), N0, N1);

  if (RMUL.getNode() != 0) return RMUL;
  return SDValue();
}