From d8e91e46262bc44006913e6796843909f1ac7bcd Mon Sep 17 00:00:00 2001 From: Dimitry Andric Date: Sat, 19 Jan 2019 10:01:25 +0000 Subject: Vendor import of llvm trunk r351319 (just before the release_80 branch point): https://llvm.org/svn/llvm-project/llvm/trunk@351319 --- utils/TableGen/CodeGenDAGPatterns.cpp | 240 ++++++++++++++++++++++++---------- 1 file changed, 169 insertions(+), 71 deletions(-) (limited to 'utils/TableGen/CodeGenDAGPatterns.cpp') diff --git a/utils/TableGen/CodeGenDAGPatterns.cpp b/utils/TableGen/CodeGenDAGPatterns.cpp index cc2b9d788980..96c90c9cf6bd 100644 --- a/utils/TableGen/CodeGenDAGPatterns.cpp +++ b/utils/TableGen/CodeGenDAGPatterns.cpp @@ -13,7 +13,9 @@ //===----------------------------------------------------------------------===// #include "CodeGenDAGPatterns.h" +#include "llvm/ADT/BitVector.h" #include "llvm/ADT/DenseSet.h" +#include "llvm/ADT/MapVector.h" #include "llvm/ADT/STLExtras.h" #include "llvm/ADT/SmallSet.h" #include "llvm/ADT/SmallString.h" @@ -26,6 +28,7 @@ #include "llvm/TableGen/Record.h" #include #include +#include #include using namespace llvm; @@ -99,22 +102,29 @@ bool TypeSetByHwMode::isPossible() const { bool TypeSetByHwMode::insert(const ValueTypeByHwMode &VVT) { bool Changed = false; + bool ContainsDefault = false; + MVT DT = MVT::Other; + SmallDenseSet Modes; for (const auto &P : VVT) { unsigned M = P.first; Modes.insert(M); // Make sure there exists a set for each specific mode from VVT. Changed |= getOrCreate(M).insert(P.second).second; + // Cache VVT's default mode. + if (DefaultMode == M) { + ContainsDefault = true; + DT = P.second; + } } // If VVT has a default mode, add the corresponding type to all // modes in "this" that do not exist in VVT. - if (Modes.count(DefaultMode)) { - MVT DT = VVT.getType(DefaultMode); + if (ContainsDefault) for (auto &I : *this) if (!Modes.count(I.first)) Changed |= I.second.insert(DT).second; - } + return Changed; } @@ -198,16 +208,18 @@ void TypeSetByHwMode::writeToStream(const SetType &S, raw_ostream &OS) { } bool TypeSetByHwMode::operator==(const TypeSetByHwMode &VTS) const { - bool HaveDefault = hasDefault(); - if (HaveDefault != VTS.hasDefault()) + // The isSimple call is much quicker than hasDefault - check this first. + bool IsSimple = isSimple(); + bool VTSIsSimple = VTS.isSimple(); + if (IsSimple && VTSIsSimple) + return *begin() == *VTS.begin(); + + // Speedup: We have a default if the set is simple. + bool HaveDefault = IsSimple || hasDefault(); + bool VTSHaveDefault = VTSIsSimple || VTS.hasDefault(); + if (HaveDefault != VTSHaveDefault) return false; - if (isSimple()) { - if (VTS.isSimple()) - return *begin() == *VTS.begin(); - return false; - } - SmallDenseSet Modes; for (auto &I : *this) Modes.insert(I.first); @@ -731,17 +743,12 @@ bool TypeInfer::EnforceSameSize(TypeSetByHwMode &A, TypeSetByHwMode &B) { void TypeInfer::expandOverloads(TypeSetByHwMode &VTS) { ValidateOnExit _1(VTS, *this); - TypeSetByHwMode Legal = getLegalTypes(); - bool HaveLegalDef = Legal.hasDefault(); + const TypeSetByHwMode &Legal = getLegalTypes(); + assert(Legal.isDefaultOnly() && "Default-mode only expected"); + const TypeSetByHwMode::SetType &LegalTypes = Legal.get(DefaultMode); - for (auto &I : VTS) { - unsigned M = I.first; - if (!Legal.hasMode(M) && !HaveLegalDef) { - TP.error("Invalid mode " + Twine(M)); - return; - } - expandOverloads(I.second, Legal.get(M)); - } + for (auto &I : VTS) + expandOverloads(I.second, LegalTypes); } void TypeInfer::expandOverloads(TypeSetByHwMode::SetType &Out, @@ -793,17 +800,17 @@ void TypeInfer::expandOverloads(TypeSetByHwMode::SetType &Out, } } -TypeSetByHwMode TypeInfer::getLegalTypes() { +const TypeSetByHwMode &TypeInfer::getLegalTypes() { if (!LegalTypesCached) { + TypeSetByHwMode::SetType &LegalTypes = LegalCache.getOrCreate(DefaultMode); // Stuff all types from all modes into the default mode. const TypeSetByHwMode <S = TP.getDAGPatterns().getLegalTypes(); for (const auto &I : LTS) - LegalCache.insert(I.second); + LegalTypes.insert(I.second); LegalTypesCached = true; } - TypeSetByHwMode VTS; - VTS.getOrCreate(DefaultMode) = LegalCache; - return VTS; + assert(LegalCache.isDefaultOnly() && "Default-mode only expected"); + return LegalCache; } #ifndef NDEBUG @@ -819,6 +826,20 @@ TypeInfer::ValidateOnExit::~ValidateOnExit() { } #endif + +//===----------------------------------------------------------------------===// +// ScopedName Implementation +//===----------------------------------------------------------------------===// + +bool ScopedName::operator==(const ScopedName &o) const { + return Scope == o.Scope && Identifier == o.Identifier; +} + +bool ScopedName::operator!=(const ScopedName &o) const { + return !(*this == o); +} + + //===----------------------------------------------------------------------===// // TreePredicateFn Implementation //===----------------------------------------------------------------------===// @@ -1064,6 +1085,9 @@ bool TreePredicateFn::isPredefinedPredicateEqualTo(StringRef Field, return false; return Result == Value; } +bool TreePredicateFn::usesOperands() const { + return isPredefinedPredicateEqualTo("PredicateCodeUsesOperands", true); +} bool TreePredicateFn::isLoad() const { return isPredefinedPredicateEqualTo("IsLoad", true); } @@ -1245,7 +1269,7 @@ std::string TreePredicateFn::getCodeToRunOnSDNode() const { else Result = " auto *N = cast<" + ClassName.str() + ">(Node);\n"; - return Result + getPredCode(); + return (Twine(Result) + " (void)N;\n" + getPredCode()).str(); } //===----------------------------------------------------------------------===// @@ -1271,14 +1295,14 @@ static unsigned getPatternSize(const TreePatternNode *P, // If this node has some predicate function that must match, it adds to the // complexity of this node. - if (!P->getPredicateFns().empty()) + if (!P->getPredicateCalls().empty()) ++Size; // Count children in the count if they are also nodes. for (unsigned i = 0, e = P->getNumChildren(); i != e; ++i) { const TreePatternNode *Child = P->getChild(i); if (!Child->isLeaf() && Child->getNumTypes()) { - const TypeSetByHwMode &T0 = Child->getType(0); + const TypeSetByHwMode &T0 = Child->getExtType(0); // At this point, all variable type sets should be simple, i.e. only // have a default mode. if (T0.getMachineValueType() != MVT::Other) { @@ -1291,7 +1315,7 @@ static unsigned getPatternSize(const TreePatternNode *P, Size += 5; // Matches a ConstantSDNode (+3) and a specific value (+2). else if (Child->getComplexPatternInfo(CGP)) Size += getPatternSize(Child, CGP); - else if (!Child->getPredicateFns().empty()) + else if (!Child->getPredicateCalls().empty()) ++Size; } } @@ -1313,7 +1337,7 @@ std::string PatternToMatch::getPredicateCheck() const { SmallVector PredList; for (const Predicate &P : Predicates) PredList.push_back(&P); - llvm::sort(PredList.begin(), PredList.end(), deref()); + llvm::sort(PredList, deref()); std::string Check; for (unsigned i = 0, e = PredList.size(); i != e; ++i) { @@ -1746,13 +1770,19 @@ void TreePatternNode::print(raw_ostream &OS) const { OS << ")"; } - for (const TreePredicateFn &Pred : PredicateFns) - OS << "<>"; + for (const TreePredicateCall &Pred : PredicateCalls) { + OS << "<>"; + } if (TransformFn) OS << "<getName() << ">>"; if (!getName().empty()) OS << ":$" << getName(); + for (const ScopedName &Name : NamesAsPredicateArg) + OS << ":$pred:" << Name.getScope() << ":" << Name.getIdentifier(); } void TreePatternNode::dump() const { print(errs()); @@ -1769,7 +1799,7 @@ bool TreePatternNode::isIsomorphicTo(const TreePatternNode *N, const MultipleUseVarSet &DepVars) const { if (N == this) return true; if (N->isLeaf() != isLeaf() || getExtTypes() != N->getExtTypes() || - getPredicateFns() != N->getPredicateFns() || + getPredicateCalls() != N->getPredicateCalls() || getTransformFn() != N->getTransformFn()) return false; @@ -1807,8 +1837,9 @@ TreePatternNodePtr TreePatternNode::clone() const { getNumTypes()); } New->setName(getName()); + New->setNamesAsPredicateArg(getNamesAsPredicateArg()); New->Types = Types; - New->setPredicateFns(getPredicateFns()); + New->setPredicateCalls(getPredicateCalls()); New->setTransformFn(getTransformFn()); return New; } @@ -1840,8 +1871,8 @@ void TreePatternNode::SubstituteFormalArguments( // We found a use of a formal argument, replace it with its value. TreePatternNodePtr NewChild = ArgMap[Child->getName()]; assert(NewChild && "Couldn't find formal argument!"); - assert((Child->getPredicateFns().empty() || - NewChild->getPredicateFns() == Child->getPredicateFns()) && + assert((Child->getPredicateCalls().empty() || + NewChild->getPredicateCalls() == Child->getPredicateCalls()) && "Non-empty child predicate clobbered!"); setChild(i, std::move(NewChild)); } @@ -1887,8 +1918,8 @@ void TreePatternNode::InlinePatternFragments( return; for (auto NewChild : ChildAlternatives[i]) - assert((Child->getPredicateFns().empty() || - NewChild->getPredicateFns() == Child->getPredicateFns()) && + assert((Child->getPredicateCalls().empty() || + NewChild->getPredicateCalls() == Child->getPredicateCalls()) && "Non-empty child predicate clobbered!"); } @@ -1906,10 +1937,13 @@ void TreePatternNode::InlinePatternFragments( // Copy over properties. R->setName(getName()); - R->setPredicateFns(getPredicateFns()); + R->setNamesAsPredicateArg(getNamesAsPredicateArg()); + R->setPredicateCalls(getPredicateCalls()); R->setTransformFn(getTransformFn()); for (unsigned i = 0, e = getNumTypes(); i != e; ++i) R->setType(i, getExtType(i)); + for (unsigned i = 0, e = getNumResults(); i != e; ++i) + R->setResultIndex(i, getResultIndex(i)); // Register alternative. OutAlternatives.push_back(R); @@ -1941,10 +1975,19 @@ void TreePatternNode::InlinePatternFragments( return; } + TreePredicateFn PredFn(Frag); + unsigned Scope = 0; + if (TreePredicateFn(Frag).usesOperands()) + Scope = TP.getDAGPatterns().allocateScope(); + // Compute the map of formal to actual arguments. std::map ArgMap; for (unsigned i = 0, e = Frag->getNumArgs(); i != e; ++i) { - const TreePatternNodePtr &Child = getChildShared(i); + TreePatternNodePtr Child = getChildShared(i); + if (Scope != 0) { + Child = Child->clone(); + Child->addNameAsPredicateArg(ScopedName(Scope, Frag->getArgName(i))); + } ArgMap[Frag->getArgName(i)] = Child; } @@ -1952,9 +1995,8 @@ void TreePatternNode::InlinePatternFragments( for (auto Alternative : Frag->getTrees()) { TreePatternNodePtr FragTree = Alternative->clone(); - TreePredicateFn PredFn(Frag); if (!PredFn.isAlwaysTrue()) - FragTree->addPredicateFn(PredFn); + FragTree->addPredicateCall(PredFn, Scope); // Resolve formal arguments to their actual value. if (Frag->getNumArgs()) @@ -1967,8 +2009,8 @@ void TreePatternNode::InlinePatternFragments( FragTree->UpdateNodeType(i, getExtType(i), TP); // Transfer in the old predicates. - for (const TreePredicateFn &Pred : getPredicateFns()) - FragTree->addPredicateFn(Pred); + for (const TreePredicateCall &Pred : getPredicateCalls()) + FragTree->addPredicateCall(Pred); // The fragment we inlined could have recursive inlining that is needed. See // if there are any pattern fragments in it and inline them as needed. @@ -3032,13 +3074,6 @@ void CodeGenDAGPatterns::ParsePatternFragments(bool OutFrags) { P->error("Operands list does not contain an entry for operand '" + *OperandsSet.begin() + "'!"); - // If there is a code init for this fragment, keep track of the fact that - // this fragment uses it. - TreePredicateFn PredFn(P); - if (!PredFn.isAlwaysTrue()) - for (auto T : P->getTrees()) - T->addPredicateFn(PredFn); - // If there is a node transformation corresponding to this, keep track of // it. Record *Transform = Frag->getValueAsDef("OperandTransform"); @@ -3176,7 +3211,8 @@ static bool HandleUse(TreePattern &I, TreePatternNodePtr Pat, void CodeGenDAGPatterns::FindPatternInputsAndOutputs( TreePattern &I, TreePatternNodePtr Pat, std::map &InstInputs, - std::map &InstResults, + MapVector> + &InstResults, std::vector &InstImpResults) { // The instruction pattern still has unresolved fragments. For *named* @@ -3496,7 +3532,8 @@ void CodeGenDAGPatterns::parseInstructionPattern( // InstResults - Keep track of all the virtual registers that are 'set' // in the instruction, including what reg class they are. - std::map InstResults; + MapVector> + InstResults; std::vector InstImpResults; @@ -3533,19 +3570,28 @@ void CodeGenDAGPatterns::parseInstructionPattern( // Check that all of the results occur first in the list. std::vector Results; + std::vector ResultIndices; SmallVector ResNodes; for (unsigned i = 0; i != NumResults; ++i) { - if (i == CGI.Operands.size()) - I.error("'" + InstResults.begin()->first + - "' set but does not appear in operand list!"); + if (i == CGI.Operands.size()) { + const std::string &OpName = + std::find_if(InstResults.begin(), InstResults.end(), + [](const std::pair &P) { + return P.second; + }) + ->first; + + I.error("'" + OpName + "' set but does not appear in operand list!"); + } + const std::string &OpName = CGI.Operands[i].Name; // Check that it exists in InstResults. - TreePatternNodePtr RNode = InstResults[OpName]; - if (!RNode) + auto InstResultIter = InstResults.find(OpName); + if (InstResultIter == InstResults.end() || !InstResultIter->second) I.error("Operand $" + OpName + " does not exist in operand list!"); - + TreePatternNodePtr RNode = InstResultIter->second; Record *R = cast(RNode->getLeafValue())->getDef(); ResNodes.push_back(std::move(RNode)); if (!R) @@ -3558,8 +3604,11 @@ void CodeGenDAGPatterns::parseInstructionPattern( // Remember the return type. Results.push_back(CGI.Operands[i].Rec); + // Remember the result index. + ResultIndices.push_back(std::distance(InstResults.begin(), InstResultIter)); + // Okay, this one checks out. - InstResults.erase(OpName); + InstResultIter->second = nullptr; } // Loop over the inputs next. @@ -3598,7 +3647,7 @@ void CodeGenDAGPatterns::parseInstructionPattern( TreePatternNodePtr OpNode = InVal->clone(); // No predicate is useful on the result. - OpNode->clearPredicateFns(); + OpNode->clearPredicateCalls(); // Promote the xform function to be an explicit node if set. if (Record *Xform = OpNode->getTransformFn()) { @@ -3623,6 +3672,7 @@ void CodeGenDAGPatterns::parseInstructionPattern( for (unsigned i = 0; i != NumResults; ++i) { assert(ResNodes[i]->getNumTypes() == 1 && "FIXME: Unhandled"); ResultPattern->setType(i, ResNodes[i]->getExtType(0)); + ResultPattern->setResultIndex(i, ResultIndices[i]); } // FIXME: Assume only the first tree is the pattern. The others are clobber @@ -3737,7 +3787,7 @@ std::vector CodeGenDAGPatterns::makePredList(ListInit *L) { } // Sort so that different orders get canonicalized to the same string. - llvm::sort(Preds.begin(), Preds.end()); + llvm::sort(Preds); return Preds; } @@ -4082,7 +4132,8 @@ void CodeGenDAGPatterns::ParsePatterns() { // Validate that the input pattern is correct. std::map InstInputs; - std::map InstResults; + MapVector> + InstResults; std::vector InstImpResults; for (unsigned j = 0, ee = Pattern.getNumTrees(); j != ee; ++j) FindPatternInputsAndOutputs(Pattern, Pattern.getTree(j), InstInputs, @@ -4253,7 +4304,8 @@ static void CombineChildVariants( // Copy over properties. R->setName(Orig->getName()); - R->setPredicateFns(Orig->getPredicateFns()); + R->setNamesAsPredicateArg(Orig->getNamesAsPredicateArg()); + R->setPredicateCalls(Orig->getPredicateCalls()); R->setTransformFn(Orig->getTransformFn()); for (unsigned i = 0, e = Orig->getNumTypes(); i != e; ++i) R->setType(i, Orig->getExtType(i)); @@ -4305,7 +4357,7 @@ GatherChildrenOfAssociativeOpcode(TreePatternNodePtr N, Record *Operator = N->getOperator(); // Only permit raw nodes. - if (!N->getName().empty() || !N->getPredicateFns().empty() || + if (!N->getName().empty() || !N->getPredicateCalls().empty() || N->getTransformFn()) { Children.push_back(N); return; @@ -4456,8 +4508,18 @@ void CodeGenDAGPatterns::GenerateVariants() { // intentionally do not reconsider these. Any variants of added patterns have // already been added. // - for (unsigned i = 0, e = PatternsToMatch.size(); i != e; ++i) { - MultipleUseVarSet DepVars; + const unsigned NumOriginalPatterns = PatternsToMatch.size(); + BitVector MatchedPatterns(NumOriginalPatterns); + std::vector MatchedPredicates(NumOriginalPatterns, + BitVector(NumOriginalPatterns)); + + typedef std::pair> + DepsAndVariants; + std::map PatternsWithVariants; + + // Collect patterns with more than one variant. + for (unsigned i = 0; i != NumOriginalPatterns; ++i) { + MultipleUseVarSet DepVars; std::vector Variants; FindDepVars(PatternsToMatch[i].getSrcPattern(), DepVars); LLVM_DEBUG(errs() << "Dependent/multiply used variables: "); @@ -4467,14 +4529,46 @@ void CodeGenDAGPatterns::GenerateVariants() { *this, DepVars); assert(!Variants.empty() && "Must create at least original variant!"); - if (Variants.size() == 1) // No additional variants for this pattern. + if (Variants.size() == 1) // No additional variants for this pattern. continue; LLVM_DEBUG(errs() << "FOUND VARIANTS OF: "; PatternsToMatch[i].getSrcPattern()->dump(); errs() << "\n"); + PatternsWithVariants[i] = std::make_pair(DepVars, Variants); + + // Cache matching predicates. + if (MatchedPatterns[i]) + continue; + + const std::vector &Predicates = + PatternsToMatch[i].getPredicates(); + + BitVector &Matches = MatchedPredicates[i]; + MatchedPatterns.set(i); + Matches.set(i); + + // Don't test patterns that have already been cached - it won't match. + for (unsigned p = 0; p != NumOriginalPatterns; ++p) + if (!MatchedPatterns[p]) + Matches[p] = (Predicates == PatternsToMatch[p].getPredicates()); + + // Copy this to all the matching patterns. + for (int p = Matches.find_first(); p != -1; p = Matches.find_next(p)) + if (p != (int)i) { + MatchedPatterns.set(p); + MatchedPredicates[p] = Matches; + } + } + + for (auto it : PatternsWithVariants) { + unsigned i = it.first; + const MultipleUseVarSet &DepVars = it.second.first; + const std::vector &Variants = it.second.second; + for (unsigned v = 0, e = Variants.size(); v != e; ++v) { TreePatternNodePtr Variant = Variants[v]; + BitVector &Matches = MatchedPredicates[i]; LLVM_DEBUG(errs() << " VAR#" << v << ": "; Variant->dump(); errs() << "\n"); @@ -4483,8 +4577,7 @@ void CodeGenDAGPatterns::GenerateVariants() { bool AlreadyExists = false; for (unsigned p = 0, e = PatternsToMatch.size(); p != e; ++p) { // Skip if the top level predicates do not match. - if (PatternsToMatch[i].getPredicates() != - PatternsToMatch[p].getPredicates()) + if (!Matches[p]) continue; // Check to see if this variant already exists. if (Variant->isIsomorphicTo(PatternsToMatch[p].getSrcPattern(), @@ -4503,6 +4596,11 @@ void CodeGenDAGPatterns::GenerateVariants() { Variant, PatternsToMatch[i].getDstPatternShared(), PatternsToMatch[i].getDstRegs(), PatternsToMatch[i].getAddedComplexity(), Record::getNewUID())); + MatchedPredicates.push_back(Matches); + + // Add a new match the same as this pattern. + for (auto &P : MatchedPredicates) + P.push_back(P[i]); } LLVM_DEBUG(errs() << "\n"); -- cgit v1.2.3