From e39650a805425ffdbd79692c7d1bad80f7332dae Mon Sep 17 00:00:00 2001 From: Chris Lattner Date: Tue, 16 Feb 2010 06:10:58 +0000 Subject: [PATCH] add support for the new isel matcher to generate (isprofitable|islegal)tofold checks. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@96331 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/CodeGen/DAGISelHeader.h | 17 ++++++- utils/TableGen/CodeGenDAGPatterns.h | 7 +++ utils/TableGen/DAGISelEmitter.cpp | 2 + utils/TableGen/DAGISelMatcher.cpp | 10 ++++ utils/TableGen/DAGISelMatcher.h | 30 ++++++++++- utils/TableGen/DAGISelMatcherEmitter.cpp | 6 +++ utils/TableGen/DAGISelMatcherGen.cpp | 63 ++++++++++++++++++++---- 7 files changed, 123 insertions(+), 12 deletions(-) diff --git a/include/llvm/CodeGen/DAGISelHeader.h b/include/llvm/CodeGen/DAGISelHeader.h index f9490a77caa..831475d9a5a 100644 --- a/include/llvm/CodeGen/DAGISelHeader.h +++ b/include/llvm/CodeGen/DAGISelHeader.h @@ -202,7 +202,9 @@ enum BuiltinOpcodes { OPC_CheckValueType, OPC_CheckComplexPat, OPC_CheckAndImm1, OPC_CheckAndImm2, OPC_CheckAndImm4, OPC_CheckAndImm8, - OPC_CheckOrImm1, OPC_CheckOrImm2, OPC_CheckOrImm4, OPC_CheckOrImm8 + OPC_CheckOrImm1, OPC_CheckOrImm2, OPC_CheckOrImm4, OPC_CheckOrImm8, + OPC_IsProfitableToFold, + OPC_IsLegalToFold }; struct MatchScope { @@ -379,6 +381,19 @@ SDNode *SelectCodeCommon(SDNode *NodeToMatch, const unsigned char *MatcherTable, case OPC_CheckOrImm8: if (CheckOrImmediate(N, GetInt8(MatcherTable, MatcherIndex))) break; continue; + + case OPC_IsProfitableToFold: + assert(!NodeStack.size() == 1 && "No parent node"); + if (!IsProfitableToFold(N, NodeStack[NodeStack.size()-2].getNode(), + NodeToMatch)) + break; + continue; + case OPC_IsLegalToFold: + assert(!NodeStack.size() == 1 && "No parent node"); + if (!IsLegalToFold(N, NodeStack[NodeStack.size()-2].getNode(), + NodeToMatch)) + break; + continue; } // If the code reached this point, then the match failed pop out to the next diff --git a/utils/TableGen/CodeGenDAGPatterns.h b/utils/TableGen/CodeGenDAGPatterns.h index 5eef9e1ddc6..f1f7bca1a8f 100644 --- a/utils/TableGen/CodeGenDAGPatterns.h +++ b/utils/TableGen/CodeGenDAGPatterns.h @@ -216,6 +216,13 @@ public: void setChild(unsigned i, TreePatternNode *N) { Children[i] = N; } + + /// hasChild - Return true if N is any of our children. + bool hasChild(const TreePatternNode *N) const { + for (unsigned i = 0, e = Children.size(); i != e; ++i) + if (Children[i] == N) return true; + return false; + } const std::vector &getPredicateFns() const {return PredicateFns;} void clearPredicateFns() { PredicateFns.clear(); } diff --git a/utils/TableGen/DAGISelEmitter.cpp b/utils/TableGen/DAGISelEmitter.cpp index d2e260e2e7e..243700fdb71 100644 --- a/utils/TableGen/DAGISelEmitter.cpp +++ b/utils/TableGen/DAGISelEmitter.cpp @@ -586,6 +586,8 @@ void PatternCodeEmitter::EmitMatchCode(TreePatternNode *N, TreePatternNode *P, // / [YY] // | ^ // [XX]-------| + + // We know we need the check if N's parent is not the root. bool NeedCheck = P != Pattern; if (!NeedCheck) { const SDNodeInfo &PInfo = CGP.getSDNodeInfo(P->getOperator()); diff --git a/utils/TableGen/DAGISelMatcher.cpp b/utils/TableGen/DAGISelMatcher.cpp index 1363aa3e812..3f75558e3dc 100644 --- a/utils/TableGen/DAGISelMatcher.cpp +++ b/utils/TableGen/DAGISelMatcher.cpp @@ -106,3 +106,13 @@ void CheckOrImmMatcherNode::print(raw_ostream &OS, unsigned indent) const { printChild(OS, indent); } +void CheckProfitableToFoldMatcherNode::print(raw_ostream &OS, + unsigned indent) const { + OS.indent(indent) << "CheckProfitableToFold\n"; + printChild(OS, indent); +} + +void CheckLegalToFoldMatcherNode::print(raw_ostream &OS, unsigned indent) const{ + OS.indent(indent) << "CheckLegalToFold\n"; + printChild(OS, indent); +} diff --git a/utils/TableGen/DAGISelMatcher.h b/utils/TableGen/DAGISelMatcher.h index 72bdb7bf277..8699d516ed8 100644 --- a/utils/TableGen/DAGISelMatcher.h +++ b/utils/TableGen/DAGISelMatcher.h @@ -48,7 +48,9 @@ public: CheckValueType, CheckComplexPat, CheckAndImm, - CheckOrImm + CheckOrImm, + CheckProfitableToFold, + CheckLegalToFold }; const KindTy Kind; @@ -355,8 +357,34 @@ public: virtual void print(raw_ostream &OS, unsigned indent = 0) const; }; + +/// CheckProfitableToFoldMatcherNode - This checks to see if the current node is +/// worthwhile to try to fold into a large pattern. +class CheckProfitableToFoldMatcherNode : public MatcherNodeWithChild { +public: + CheckProfitableToFoldMatcherNode() + : MatcherNodeWithChild(CheckProfitableToFold) {} + + static inline bool classof(const MatcherNode *N) { + return N->getKind() == CheckProfitableToFold; + } + + virtual void print(raw_ostream &OS, unsigned indent = 0) const; +}; + +/// CheckLegalToFoldMatcherNode - This checks to see if the current node is +/// legal to try to fold into a large pattern. +class CheckLegalToFoldMatcherNode : public MatcherNodeWithChild { +public: + CheckLegalToFoldMatcherNode() + : MatcherNodeWithChild(CheckLegalToFold) {} + static inline bool classof(const MatcherNode *N) { + return N->getKind() == CheckLegalToFold; + } + virtual void print(raw_ostream &OS, unsigned indent = 0) const; +}; } // end namespace llvm #endif diff --git a/utils/TableGen/DAGISelMatcherEmitter.cpp b/utils/TableGen/DAGISelMatcherEmitter.cpp index 1a41713c220..ee838d05a44 100644 --- a/utils/TableGen/DAGISelMatcherEmitter.cpp +++ b/utils/TableGen/DAGISelMatcherEmitter.cpp @@ -151,6 +151,12 @@ static unsigned EmitMatcher(const MatcherNode *N, formatted_raw_ostream &OS, OS << "OPC_CheckOrImm" << ClassifyInt(Val) << ", "; return EmitInt(Val, OS)+1; } + case MatcherNode::CheckProfitableToFold: + OS << "OPC_IsProfitableToFold,\n"; + return 1; + case MatcherNode::CheckLegalToFold: + OS << "OPC_IsLegalToFold,\n"; + return 1; } assert(0 && "Unreachable"); return 0; diff --git a/utils/TableGen/DAGISelMatcherGen.cpp b/utils/TableGen/DAGISelMatcherGen.cpp index afa258718f1..3ed076c7c7e 100644 --- a/utils/TableGen/DAGISelMatcherGen.cpp +++ b/utils/TableGen/DAGISelMatcherGen.cpp @@ -189,18 +189,61 @@ void MatcherGen::EmitOperatorMatchCode(const TreePatternNode *N, if (N->NodeHasProperty(SDNPHasChain, CGP)) OpNo = 1; - if (N->TreeHasProperty(SDNPHasChain, CGP)) { - // FIXME: Handle Chains with multiple uses etc. - // [ld] - // ^ ^ - // | | - // / \--- - // / [YY] - // | ^ - // [XX]-------| + // If this node is not the root and the subtree underneath it produces a + // chain, then the result of matching the node is also produce a chain. + // Beyond that, this means that we're also folding (at least) the root node + // into the node that produce the chain (for example, matching + // "(add reg, (load ptr))" as a add_with_memory on X86). This is problematic, + // if the 'reg' node also uses the load (say, its chain). Graphically: + // + // [LD] + // ^ ^ + // | \ DAG's like cheese. + // / | + // / [YY] + // | ^ + // [XX]--/ + // + // It would be invalid to fold XX and LD. In this case, folding the two + // nodes together would induce a cycle in the DAG, making it a cyclic DAG (!). + // To prevent this, we emit a dynamic check for legality before allowing this + // to be folded. + // + const TreePatternNode *Root = Pattern.getSrcPattern(); + if (N != Root && // Not the root of the pattern. + N->TreeHasProperty(SDNPHasChain, CGP)) { // Has a chain somewhere in tree. + + AddMatcherNode(new CheckProfitableToFoldMatcherNode()); + + // If this non-root node produces a chain, we may need to emit a validity + // check. + if (OpNo != 0) { + // If there is a node between the root and this node, then we definitely + // need to emit the check. + bool NeedCheck = !Root->hasChild(N); + + // If it *is* an immediate child of the root, we can still need a check if + // the root SDNode has multiple inputs. For us, this means that it is an + // intrinsic, has multiple operands, or has other inputs like chain or + // flag). + if (!NeedCheck) { + const SDNodeInfo &PInfo = CGP.getSDNodeInfo(Root->getOperator()); + NeedCheck = + Root->getOperator() == CGP.get_intrinsic_void_sdnode() || + Root->getOperator() == CGP.get_intrinsic_w_chain_sdnode() || + Root->getOperator() == CGP.get_intrinsic_wo_chain_sdnode() || + PInfo.getNumOperands() > 1 || + PInfo.hasProperty(SDNPHasChain) || + PInfo.hasProperty(SDNPInFlag) || + PInfo.hasProperty(SDNPOptInFlag); + } + + if (NeedCheck) + AddMatcherNode(new CheckLegalToFoldMatcherNode()); + } } - // FIXME: Handle Flags & .hasOneUse() + // FIXME: Handle EmittedUseCheck & Flags & .hasOneUse() for (unsigned i = 0, e = N->getNumChildren(); i != e; ++i, ++OpNo) { // Get the code suitable for matching this child. Move to the child, check -- 2.34.1