A SelectionDAG
representation shows data and instructions in the form of nodes. Similar to the InstCombine
pass in the LLVM IR, these nodes can be combined and optimized to form a minimized SelectionDAG
. But, it's not just a DAGCombine
operation that optimizes the SelectionDAG. A DAGLegalize
phase may generate some unnecessary DAG nodes, which are cleaned up by subsequent runs of the DAG optimization pass. This finally represents the SelectionDAG
in a more simple and elegant way.
There are lots and lots of function members (most of them are named like this: visit**()
) provided in the DAGCombiner
class to perform optimizations by folding, reordering, combining, and modifying SDNode
nodes. Note that, from the DAGCombiner
constructor, we can guess that some optimizations require alias analysis information:
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(); }
18.118.2.225