From bc72c8f0d8dbab5e1ce748cc390254a06e9a5c0a Mon Sep 17 00:00:00 2001 From: Andrea Di Biagio Date: Mon, 9 Jun 2014 12:32:53 +0000 Subject: [PATCH] [DAG] Expose NoSignedWrap, NoUnsignedWrap and Exact flags to SelectionDAG. This patch modifies SelectionDAGBuilder to construct SDNodes with associated NoSignedWrap, NoUnsignedWrap and Exact flags coming from IR BinaryOperator instructions. Added a new SDNode type called 'BinaryWithFlagsSDNode' to allow accessing nsw/nuw/exact flags during codegen. Patch by Marcello Maggioni. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@210467 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/CodeGen/SelectionDAG.h | 24 ++++--- include/llvm/CodeGen/SelectionDAGNodes.h | 48 +++++++++++++ lib/CodeGen/SelectionDAG/DAGCombiner.cpp | 13 +++- lib/CodeGen/SelectionDAG/SelectionDAG.cpp | 71 ++++++++++++++++--- .../SelectionDAG/SelectionDAGBuilder.cpp | 39 ++++++++-- lib/CodeGen/SelectionDAG/TargetLowering.cpp | 3 +- test/CodeGen/X86/2014-05-30-CombineAddNSW.ll | 20 ++++++ 7 files changed, 192 insertions(+), 26 deletions(-) create mode 100644 test/CodeGen/X86/2014-05-30-CombineAddNSW.ll diff --git a/include/llvm/CodeGen/SelectionDAG.h b/include/llvm/CodeGen/SelectionDAG.h index c6d716a5355..610ba25f45e 100644 --- a/include/llvm/CodeGen/SelectionDAG.h +++ b/include/llvm/CodeGen/SelectionDAG.h @@ -612,14 +612,14 @@ public: /// SDValue getNode(unsigned Opcode, SDLoc DL, EVT VT); SDValue getNode(unsigned Opcode, SDLoc DL, EVT VT, SDValue N); - SDValue getNode(unsigned Opcode, SDLoc DL, EVT VT, SDValue N1, SDValue N2); - SDValue getNode(unsigned Opcode, SDLoc DL, EVT VT, - SDValue N1, SDValue N2, SDValue N3); - SDValue getNode(unsigned Opcode, SDLoc DL, EVT VT, - SDValue N1, SDValue N2, SDValue N3, SDValue N4); - SDValue getNode(unsigned Opcode, SDLoc DL, EVT VT, - SDValue N1, SDValue N2, SDValue N3, SDValue N4, - SDValue N5); + SDValue getNode(unsigned Opcode, SDLoc DL, EVT VT, SDValue N1, SDValue N2, + bool nuw = false, bool nsw = false, bool exact = false); + SDValue getNode(unsigned Opcode, SDLoc DL, EVT VT, SDValue N1, SDValue N2, + SDValue N3); + SDValue getNode(unsigned Opcode, SDLoc DL, EVT VT, SDValue N1, SDValue N2, + SDValue N3, SDValue N4); + SDValue getNode(unsigned Opcode, SDLoc DL, EVT VT, SDValue N1, SDValue N2, + SDValue N3, SDValue N4, SDValue N5); SDValue getNode(unsigned Opcode, SDLoc DL, EVT VT, ArrayRef Ops); SDValue getNode(unsigned Opcode, SDLoc DL, EVT VT, ArrayRef Ops); @@ -927,7 +927,9 @@ public: /// getNodeIfExists - Get the specified node if it's already available, or /// else return NULL. - SDNode *getNodeIfExists(unsigned Opcode, SDVTList VTs, ArrayRef Ops); + SDNode *getNodeIfExists(unsigned Opcode, SDVTList VTs, ArrayRef Ops, + bool nuw = false, bool nsw = false, + bool exact = false); /// getDbgValue - Creates a SDDbgValue node. /// @@ -1184,6 +1186,10 @@ private: void allnodes_clear(); + BinarySDNode *GetBinarySDNode(unsigned Opcode, SDLoc DL, SDVTList VTs, + SDValue N1, SDValue N2, bool nuw, bool nsw, + bool exact); + /// VTList - List of non-single value types. FoldingSet VTListMap; diff --git a/include/llvm/CodeGen/SelectionDAGNodes.h b/include/llvm/CodeGen/SelectionDAGNodes.h index 09cac428418..b2092688432 100644 --- a/include/llvm/CodeGen/SelectionDAGNodes.h +++ b/include/llvm/CodeGen/SelectionDAGNodes.h @@ -49,6 +49,24 @@ template struct DenseMapInfo; template struct simplify_type; template struct ilist_traits; +/// isBinOpWithFlags - Returns true if the opcode is a binary operation +/// with flags. +static bool isBinOpWithFlags(unsigned Opcode) { + switch (Opcode) { + case ISD::SDIV: + case ISD::UDIV: + case ISD::SRA: + case ISD::SRL: + case ISD::MUL: + case ISD::ADD: + case ISD::SUB: + case ISD::SHL: + return true; + default: + return false; + } +} + void checkForCycles(const SDNode *N, const SelectionDAG *DAG = nullptr, bool force = false); @@ -939,6 +957,36 @@ public: } }; +/// BinaryWithFlagsSDNode - This class is an extension of BinarySDNode +/// used from those opcodes that have associated extra flags. +class BinaryWithFlagsSDNode : public BinarySDNode { + enum { NUW = (1 << 0), NSW = (1 << 1), EXACT = (1 << 2) }; + +public: + BinaryWithFlagsSDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTs, + SDValue X, SDValue Y) + : BinarySDNode(Opc, Order, dl, VTs, X, Y) {} + /// getRawSubclassData - Return the SubclassData value, which contains an + /// encoding of the flags. + /// This function should be used to add subclass data to the NodeID value. + unsigned getRawSubclassData() const { return SubclassData; } + void setHasNoUnsignedWrap(bool b) { + SubclassData = (SubclassData & ~NUW) | (b ? NUW : 0); + } + void setHasNoSignedWrap(bool b) { + SubclassData = (SubclassData & ~NSW) | (b ? NSW : 0); + } + void setIsExact(bool b) { + SubclassData = (SubclassData & ~EXACT) | (b ? EXACT : 0); + } + bool hasNoUnsignedWrap() const { return SubclassData & NUW; } + bool hasNoSignedWrap() const { return SubclassData & NSW; } + bool isExact() const { return SubclassData & EXACT; } + static bool classof(const SDNode *N) { + return isBinOpWithFlags(N->getOpcode()); + } +}; + /// TernarySDNode - This class is used for three-operand SDNodes. This is solely /// to allow co-allocation of node operands with the node itself. class TernarySDNode : public SDNode { diff --git a/lib/CodeGen/SelectionDAG/DAGCombiner.cpp b/lib/CodeGen/SelectionDAG/DAGCombiner.cpp index 6a962fd69e0..8ec0c45eaff 100644 --- a/lib/CodeGen/SelectionDAG/DAGCombiner.cpp +++ b/lib/CodeGen/SelectionDAG/DAGCombiner.cpp @@ -1325,9 +1325,16 @@ SDValue DAGCombiner::combine(SDNode *N) { // Constant operands are canonicalized to RHS. if (isa(N0) || !isa(N1)) { - SDValue Ops[] = { N1, N0 }; - SDNode *CSENode = DAG.getNodeIfExists(N->getOpcode(), N->getVTList(), - Ops); + SDValue Ops[] = {N1, N0}; + SDNode *CSENode; + if (const BinaryWithFlagsSDNode *BinNode = + dyn_cast(N)) { + CSENode = DAG.getNodeIfExists( + N->getOpcode(), N->getVTList(), Ops, BinNode->hasNoUnsignedWrap(), + BinNode->hasNoSignedWrap(), BinNode->isExact()); + } else { + CSENode = DAG.getNodeIfExists(N->getOpcode(), N->getVTList(), Ops); + } if (CSENode) return SDValue(CSENode, 0); } diff --git a/lib/CodeGen/SelectionDAG/SelectionDAG.cpp b/lib/CodeGen/SelectionDAG/SelectionDAG.cpp index b701add2de3..010431e5328 100644 --- a/lib/CodeGen/SelectionDAG/SelectionDAG.cpp +++ b/lib/CodeGen/SelectionDAG/SelectionDAG.cpp @@ -48,6 +48,7 @@ #include "llvm/Target/TargetSelectionDAGInfo.h" #include #include + using namespace llvm; /// makeVTList - Return an instance of the SDVTList struct initialized with the @@ -381,6 +382,20 @@ static void AddNodeIDOperands(FoldingSetNodeID &ID, } } +static void AddBinaryNodeIDCustom(FoldingSetNodeID &ID, bool nuw, bool nsw, + bool exact) { + ID.AddBoolean(nuw); + ID.AddBoolean(nsw); + ID.AddBoolean(exact); +} + +/// AddBinaryNodeIDCustom - Add BinarySDNodes special infos +static void AddBinaryNodeIDCustom(FoldingSetNodeID &ID, unsigned Opcode, + bool nuw, bool nsw, bool exact) { + if (isBinOpWithFlags(Opcode)) + AddBinaryNodeIDCustom(ID, nuw, nsw, exact); +} + static void AddNodeIDNode(FoldingSetNodeID &ID, unsigned short OpC, SDVTList VTList, ArrayRef OpList) { AddNodeIDOpcode(ID, OpC); @@ -473,6 +488,19 @@ static void AddNodeIDCustom(FoldingSetNodeID &ID, const SDNode *N) { ID.AddInteger(ST->getPointerInfo().getAddrSpace()); break; } + case ISD::SDIV: + case ISD::UDIV: + case ISD::SRA: + case ISD::SRL: + case ISD::MUL: + case ISD::ADD: + case ISD::SUB: + case ISD::SHL: { + const BinaryWithFlagsSDNode *BinNode = cast(N); + AddBinaryNodeIDCustom(ID, N->getOpcode(), BinNode->hasNoUnsignedWrap(), + BinNode->hasNoSignedWrap(), BinNode->isExact()); + break; + } case ISD::ATOMIC_CMP_SWAP: case ISD::ATOMIC_SWAP: case ISD::ATOMIC_LOAD_ADD: @@ -926,6 +954,25 @@ void SelectionDAG::allnodes_clear() { DeallocateNode(AllNodes.begin()); } +BinarySDNode *SelectionDAG::GetBinarySDNode(unsigned Opcode, SDLoc DL, + SDVTList VTs, SDValue N1, + SDValue N2, bool nuw, bool nsw, + bool exact) { + if (isBinOpWithFlags(Opcode)) { + BinaryWithFlagsSDNode *FN = new (NodeAllocator) BinaryWithFlagsSDNode( + Opcode, DL.getIROrder(), DL.getDebugLoc(), VTs, N1, N2); + FN->setHasNoUnsignedWrap(nuw); + FN->setHasNoSignedWrap(nsw); + FN->setIsExact(exact); + + return FN; + } + + BinarySDNode *N = new (NodeAllocator) + BinarySDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(), VTs, N1, N2); + return N; +} + void SelectionDAG::clear() { allnodes_clear(); OperandAllocator.Reset(); @@ -2936,7 +2983,7 @@ SDValue SelectionDAG::FoldConstantArithmetic(unsigned Opcode, EVT VT, } SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT, SDValue N1, - SDValue N2) { + SDValue N2, bool nuw, bool nsw, bool exact) { ConstantSDNode *N1C = dyn_cast(N1.getNode()); ConstantSDNode *N2C = dyn_cast(N2.getNode()); switch (Opcode) { @@ -3376,22 +3423,25 @@ SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT, SDValue N1, } // Memoize this node if possible. - SDNode *N; + BinarySDNode *N; SDVTList VTs = getVTList(VT); + const bool BinOpHasFlags = isBinOpWithFlags(Opcode); if (VT != MVT::Glue) { - SDValue Ops[] = { N1, N2 }; + SDValue Ops[] = {N1, N2}; FoldingSetNodeID ID; AddNodeIDNode(ID, Opcode, VTs, Ops); + if (BinOpHasFlags) + AddBinaryNodeIDCustom(ID, Opcode, nuw, nsw, exact); void *IP = nullptr; if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) return SDValue(E, 0); - N = new (NodeAllocator) BinarySDNode(Opcode, DL.getIROrder(), - DL.getDebugLoc(), VTs, N1, N2); + N = GetBinarySDNode(Opcode, DL, VTs, N1, N2, nuw, nsw, exact); + CSEMap.InsertNode(N, IP); } else { - N = new (NodeAllocator) BinarySDNode(Opcode, DL.getIROrder(), - DL.getDebugLoc(), VTs, N1, N2); + + N = GetBinarySDNode(Opcode, DL, VTs, N1, N2, nuw, nsw, exact); } AllNodes.push_back(N); @@ -5606,10 +5656,13 @@ SelectionDAG::getTargetInsertSubreg(int SRIdx, SDLoc DL, EVT VT, /// getNodeIfExists - Get the specified node if it's already available, or /// else return NULL. SDNode *SelectionDAG::getNodeIfExists(unsigned Opcode, SDVTList VTList, - ArrayRef Ops) { - if (VTList.VTs[VTList.NumVTs-1] != MVT::Glue) { + ArrayRef Ops, bool nuw, bool nsw, + bool exact) { + if (VTList.VTs[VTList.NumVTs - 1] != MVT::Glue) { FoldingSetNodeID ID; AddNodeIDNode(ID, Opcode, VTList, Ops); + if (isBinOpWithFlags(Opcode)) + AddBinaryNodeIDCustom(ID, nuw, nsw, exact); void *IP = nullptr; if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) return E; diff --git a/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp b/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp index 8d10a80b4d2..c568d3ebcf9 100644 --- a/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp +++ b/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp @@ -2784,8 +2784,22 @@ void SelectionDAGBuilder::visitFSub(const User &I) { void SelectionDAGBuilder::visitBinary(const User &I, unsigned OpCode) { SDValue Op1 = getValue(I.getOperand(0)); SDValue Op2 = getValue(I.getOperand(1)); - setValue(&I, DAG.getNode(OpCode, getCurSDLoc(), - Op1.getValueType(), Op1, Op2)); + + bool nuw = false; + bool nsw = false; + bool exact = false; + if (const OverflowingBinaryOperator *OFBinOp = + dyn_cast(&I)) { + nuw = OFBinOp->hasNoUnsignedWrap(); + nsw = OFBinOp->hasNoSignedWrap(); + } + if (const PossiblyExactOperator *ExactOp = + dyn_cast(&I)) + exact = ExactOp->isExact(); + + SDValue BinNodeValue = DAG.getNode(OpCode, getCurSDLoc(), Op1.getValueType(), + Op1, Op2, nuw, nsw, exact); + setValue(&I, BinNodeValue); } void SelectionDAGBuilder::visitShift(const User &I, unsigned Opcode) { @@ -2816,8 +2830,25 @@ void SelectionDAGBuilder::visitShift(const User &I, unsigned Opcode) { Op2 = DAG.getZExtOrTrunc(Op2, DL, MVT::i32); } - setValue(&I, DAG.getNode(Opcode, getCurSDLoc(), - Op1.getValueType(), Op1, Op2)); + bool nuw = false; + bool nsw = false; + bool exact = false; + + if (Opcode == ISD::SRL || Opcode == ISD::SRA || Opcode == ISD::SHL) { + + if (const OverflowingBinaryOperator *OFBinOp = + dyn_cast(&I)) { + nuw = OFBinOp->hasNoUnsignedWrap(); + nsw = OFBinOp->hasNoSignedWrap(); + } + if (const PossiblyExactOperator *ExactOp = + dyn_cast(&I)) + exact = ExactOp->isExact(); + } + + SDValue Res = DAG.getNode(Opcode, getCurSDLoc(), Op1.getValueType(), Op1, Op2, + nuw, nsw, exact); + setValue(&I, Res); } void SelectionDAGBuilder::visitSDiv(const User &I) { diff --git a/lib/CodeGen/SelectionDAG/TargetLowering.cpp b/lib/CodeGen/SelectionDAG/TargetLowering.cpp index 3731aeae374..75bbbe749e5 100644 --- a/lib/CodeGen/SelectionDAG/TargetLowering.cpp +++ b/lib/CodeGen/SelectionDAG/TargetLowering.cpp @@ -2617,7 +2617,8 @@ SDValue TargetLowering::BuildExactSDIV(SDValue Op1, SDValue Op2, SDLoc dl, if (ShAmt) { // TODO: For UDIV use SRL instead of SRA. SDValue Amt = DAG.getConstant(ShAmt, getShiftAmountTy(Op1.getValueType())); - Op1 = DAG.getNode(ISD::SRA, dl, Op1.getValueType(), Op1, Amt); + Op1 = DAG.getNode(ISD::SRA, dl, Op1.getValueType(), Op1, Amt, false, false, + true); d = d.ashr(ShAmt); } diff --git a/test/CodeGen/X86/2014-05-30-CombineAddNSW.ll b/test/CodeGen/X86/2014-05-30-CombineAddNSW.ll new file mode 100644 index 00000000000..4580795880a --- /dev/null +++ b/test/CodeGen/X86/2014-05-30-CombineAddNSW.ll @@ -0,0 +1,20 @@ +; RUN: llc < %s -march=x86-64 | FileCheck %s +; CHECK: addl + +; The two additions are the same , but have different flags. +; In theory this code should never be generated by the frontend, but this +; tries to test that two identical instructions with two different flags +; actually generate two different nodes. +; +; Normally the combiner would see this condition without the flags +; and optimize the result of the sub into a register clear +; (the final result would be 0). With the different flags though the combiner +; needs to keep the add + sub nodes, because the two nodes result as different +; nodes and so cannot assume that the subtraction of the two nodes +; generates 0 as result +define i32 @foo(i32 %a, i32 %b) { + %1 = add i32 %a, %b + %2 = add nsw i32 %a, %b + %3 = sub i32 %1, %2 + ret i32 %3 +} -- 2.34.1