From 150b7ab23eb63b47808b573f828e6f14834d1cf3 Mon Sep 17 00:00:00 2001 From: Krzysztof Parzyszek Date: Thu, 16 Feb 2017 18:53:04 +0000 Subject: [PATCH] [RDF] Differentiate between defining and clobbering nodes Defining nodes should not alias with one another, while clobbering nodes can. When pushing defs on stacks, push clobbers first, link non-clobbering defs, then push the defs. The data flow in a statement is now: uses -> clobbers -> defs. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@295356 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/Target/Hexagon/HexagonOptAddrMode.cpp | 2 +- lib/Target/Hexagon/RDFCopy.cpp | 2 +- lib/Target/Hexagon/RDFGraph.cpp | 90 ++++++++++++++++++++--- lib/Target/Hexagon/RDFGraph.h | 7 +- 4 files changed, 88 insertions(+), 13 deletions(-) diff --git a/lib/Target/Hexagon/HexagonOptAddrMode.cpp b/lib/Target/Hexagon/HexagonOptAddrMode.cpp index 73fa0b3e5a3..49d5cb34a0d 100644 --- a/lib/Target/Hexagon/HexagonOptAddrMode.cpp +++ b/lib/Target/Hexagon/HexagonOptAddrMode.cpp @@ -617,7 +617,7 @@ bool HexagonOptAddrMode::constructDefMap(MachineBasicBlock *B) { for (NodeAddr IA : BA.Addr->members(*DFG)) { updateMap(IA); - DFG->pushDefs(IA, DefM); + DFG->pushAllDefs(IA, DefM); } MachineDomTreeNode *N = MDT->getNode(B); diff --git a/lib/Target/Hexagon/RDFCopy.cpp b/lib/Target/Hexagon/RDFCopy.cpp index 392871628d9..392ab7af6c2 100644 --- a/lib/Target/Hexagon/RDFCopy.cpp +++ b/lib/Target/Hexagon/RDFCopy.cpp @@ -104,7 +104,7 @@ bool CopyPropagation::scanBlock(MachineBasicBlock *B) { } updateMap(IA); - DFG.pushDefs(IA, DefM); + DFG.pushAllDefs(IA, DefM); } MachineDomTreeNode *N = MDT.getNode(B); diff --git a/lib/Target/Hexagon/RDFGraph.cpp b/lib/Target/Hexagon/RDFGraph.cpp index 600a5163196..f3ef6207a80 100644 --- a/lib/Target/Hexagon/RDFGraph.cpp +++ b/lib/Target/Hexagon/RDFGraph.cpp @@ -617,8 +617,12 @@ bool TargetOperandInfo::isPreserving(const MachineInstr &In, unsigned OpNum) // Check if the definition of RR produces an unspecified value. bool TargetOperandInfo::isClobbering(const MachineInstr &In, unsigned OpNum) const { + const MachineOperand &Op = In.getOperand(OpNum); + if (Op.isRegMask()) + return true; + assert(Op.isReg()); if (In.isCall()) - if (In.getOperand(OpNum).isImplicit()) + if (Op.isDef() && Op.isDead()) return true; return false; } @@ -1022,13 +1026,63 @@ void DataFlowGraph::releaseBlock(NodeId B, DefStackMap &DefM) { } } +// Push all definitions from the instruction node IA to an appropriate +// stack in DefM. +void DataFlowGraph::pushAllDefs(NodeAddr IA, DefStackMap &DefM) { + pushClobbers(IA, DefM); + pushDefs(IA, DefM); +} + +// Push all definitions from the instruction node IA to an appropriate +// stack in DefM. +void DataFlowGraph::pushClobbers(NodeAddr IA, DefStackMap &DefM) { + NodeSet Visited; + std::set Defined; + + // The important objectives of this function are: + // - to be able to handle instructions both while the graph is being + // constructed, and after the graph has been constructed, and + // - maintain proper ordering of definitions on the stack for each + // register reference: + // - if there are two or more related defs in IA (i.e. coming from + // the same machine operand), then only push one def on the stack, + // - if there are multiple unrelated defs of non-overlapping + // subregisters of S, then the stack for S will have both (in an + // unspecified order), but the order does not matter from the data- + // -flow perspective. + + for (NodeAddr DA : IA.Addr->members_if(IsDef, *this)) { + if (Visited.count(DA.Id)) + continue; + if (!(DA.Addr->getFlags() & NodeAttrs::Clobbering)) + continue; + + NodeList Rel = getRelatedRefs(IA, DA); + NodeAddr PDA = Rel.front(); + RegisterRef RR = PDA.Addr->getRegRef(*this); + + // Push the definition on the stack for the register and all aliases. + // The def stack traversal in linkNodeUp will check the exact aliasing. + DefM[RR.Reg].push(DA); + Defined.insert(RR.Reg); + for (RegisterId A : PRI.getAliasSet(RR.Reg)) { + // Check that we don't push the same def twice. + assert(A != RR.Reg); + if (!Defined.count(A)) + DefM[A].push(DA); + } + // Mark all the related defs as visited. + for (NodeAddr T : Rel) + Visited.insert(T.Id); + } +} + // Push all definitions from the instruction node IA to an appropriate // stack in DefM. void DataFlowGraph::pushDefs(NodeAddr IA, DefStackMap &DefM) { - NodeList Defs = IA.Addr->members_if(IsDef, *this); NodeSet Visited; #ifndef NDEBUG - RegisterSet Defined; + std::set Defined; #endif // The important objectives of this function are: @@ -1043,9 +1097,11 @@ void DataFlowGraph::pushDefs(NodeAddr IA, DefStackMap &DefM) { // unspecified order), but the order does not matter from the data- // -flow perspective. - for (NodeAddr DA : Defs) { + for (NodeAddr DA : IA.Addr->members_if(IsDef, *this)) { if (Visited.count(DA.Id)) continue; + if (DA.Addr->getFlags() & NodeAttrs::Clobbering) + continue; NodeList Rel = getRelatedRefs(IA, DA); NodeAddr PDA = Rel.front(); @@ -1053,7 +1109,7 @@ void DataFlowGraph::pushDefs(NodeAddr IA, DefStackMap &DefM) { #ifndef NDEBUG // Assert if the register is defined in two or more unrelated defs. // This could happen if there are two or more def operands defining it. - if (!Defined.insert(RR).second) { + if (!Defined.insert(RR.Reg).second) { MachineInstr *MI = NodeAddr(IA).Addr->getCode(); dbgs() << "Multiple definitions of register: " << Print(RR, *this) << " in\n " << *MI @@ -1611,13 +1667,15 @@ void DataFlowGraph::linkRefUp(NodeAddr IA, NodeAddr TA, } // Create data-flow links for all reference nodes in the statement node SA. -void DataFlowGraph::linkStmtRefs(DefStackMap &DefM, NodeAddr SA) { +template +void DataFlowGraph::linkStmtRefs(DefStackMap &DefM, NodeAddr SA, + Predicate P) { #ifndef NDEBUG RegisterSet Defs; #endif // Link all nodes (upwards in the data-flow) with their reaching defs. - for (NodeAddr RA : SA.Addr->members(*this)) { + for (NodeAddr RA : SA.Addr->members_if(P, *this)) { uint16_t Kind = RA.Addr->getKind(); assert(Kind == NodeAttrs::Def || Kind == NodeAttrs::Use); RegisterRef RR = RA.Addr->getRegRef(*this); @@ -1646,6 +1704,13 @@ void DataFlowGraph::linkBlockRefs(DefStackMap &DefM, NodeAddr BA) { // Push block delimiters. markBlock(BA.Id, DefM); + auto IsClobber = [this] (NodeAddr RA) -> bool { + return IsDef(RA) && (RA.Addr->getFlags() & NodeAttrs::Clobbering); + }; + auto IsNoClobber = [this] (NodeAddr RA) -> bool { + return IsDef(RA) && !(RA.Addr->getFlags() & NodeAttrs::Clobbering); + }; + assert(BA.Addr && "block node address is needed to create a data-flow link"); // For each non-phi instruction in the block, link all the defs and uses // to their reaching defs. For any member of the block (including phis), @@ -1653,10 +1718,17 @@ void DataFlowGraph::linkBlockRefs(DefStackMap &DefM, NodeAddr BA) { for (NodeAddr IA : BA.Addr->members(*this)) { // Ignore phi nodes here. They will be linked part by part from the // predecessors. - if (IA.Addr->getKind() == NodeAttrs::Stmt) - linkStmtRefs(DefM, IA); + if (IA.Addr->getKind() == NodeAttrs::Stmt) { + linkStmtRefs(DefM, IA, IsUse); + linkStmtRefs(DefM, IA, IsClobber); + } // Push the definitions on the stack. + pushClobbers(IA, DefM); + + if (IA.Addr->getKind() == NodeAttrs::Stmt) + linkStmtRefs(DefM, IA, IsNoClobber); + pushDefs(IA, DefM); } diff --git a/lib/Target/Hexagon/RDFGraph.h b/lib/Target/Hexagon/RDFGraph.h index 92c317c4d3c..bf4018ba7fc 100644 --- a/lib/Target/Hexagon/RDFGraph.h +++ b/lib/Target/Hexagon/RDFGraph.h @@ -729,7 +729,7 @@ namespace rdf { typedef std::unordered_map DefStackMap; void build(unsigned Options = BuildOptions::None); - void pushDefs(NodeAddr IA, DefStackMap &DM); + void pushAllDefs(NodeAddr IA, DefStackMap &DM); void markBlock(NodeId B, DefStackMap &DefM); void releaseBlock(NodeId B, DefStackMap &DefM); @@ -844,9 +844,12 @@ namespace rdf { NodeAddr BA); void removeUnusedPhis(); + void pushClobbers(NodeAddr IA, DefStackMap &DM); + void pushDefs(NodeAddr IA, DefStackMap &DM); template void linkRefUp(NodeAddr IA, NodeAddr TA, DefStack &DS); - void linkStmtRefs(DefStackMap &DefM, NodeAddr SA); + template void linkStmtRefs(DefStackMap &DefM, + NodeAddr SA, Predicate P); void linkBlockRefs(DefStackMap &DefM, NodeAddr BA); void unlinkUseDF(NodeAddr UA); -- 2.50.1