//===----------------------------------------------------------------------===//
#include "DAGISelEmitter.h"
+#include "DAGISelMatcher.h"
#include "Record.h"
#include "llvm/ADT/StringExtras.h"
#include "llvm/Support/CommandLine.h"
#include <iostream>
using namespace llvm;
+//#define ENABLE_NEW_ISEL
+
+
static cl::opt<bool>
GenDebug("gen-debug", cl::desc("Generate debug code"), cl::init(false));
return S;
}
-/// NodeIsComplexPattern - return true if N is a leaf node and a subclass of
-/// ComplexPattern.
-static bool NodeIsComplexPattern(TreePatternNode *N) {
- return (N->isLeaf() &&
- dynamic_cast<DefInit*>(N->getLeafValue()) &&
- static_cast<DefInit*>(N->getLeafValue())->getDef()->
- isSubClassOf("ComplexPattern"));
-}
-
-/// NodeGetComplexPattern - return the pointer to the ComplexPattern if N
-/// is a leaf node and a subclass of ComplexPattern, else it returns NULL.
-static const ComplexPattern *NodeGetComplexPattern(TreePatternNode *N,
- CodeGenDAGPatterns &CGP) {
- if (N->isLeaf() &&
- dynamic_cast<DefInit*>(N->getLeafValue()) &&
- static_cast<DefInit*>(N->getLeafValue())->getDef()->
- isSubClassOf("ComplexPattern")) {
- return &CGP.getComplexPattern(static_cast<DefInit*>(N->getLeafValue())
- ->getDef());
- }
- return NULL;
-}
-
/// getPatternSize - Return the 'size' of this pattern. We want to match large
/// patterns before small ones. This is used to determine the size of a
/// pattern.
// Later we can allow complexity / cost for each pattern to be (optionally)
// specified. To get best possible pattern match we'll need to dynamically
// calculate the complexity of all patterns a dag can potentially map to.
- const ComplexPattern *AM = NodeGetComplexPattern(P, CGP);
+ const ComplexPattern *AM = P->getComplexPatternInfo(CGP);
if (AM)
Size += AM->getNumOperands() * 3;
else if (Child->isLeaf()) {
if (dynamic_cast<IntInit*>(Child->getLeafValue()))
Size += 5; // Matches a ConstantSDNode (+3) and a specific value (+2).
- else if (NodeIsComplexPattern(Child))
+ else if (Child->getComplexPatternInfo(CGP))
Size += getPatternSize(Child, CGP);
else if (!Child->getPredicateFns().empty())
++Size;
typedef std::pair<unsigned, std::string> CodeLine;
typedef std::vector<CodeLine> CodeList;
- typedef std::vector<std::pair<const PatternToMatch*, CodeList> > PatternList;
bool operator()(const std::pair<const PatternToMatch*, CodeList> &LHSPair,
const std::pair<const PatternToMatch*, CodeList> &RHSPair) {
/// getRegisterValueType - Look up and return the ValueType of the specified
/// register. If the register is a member of multiple register classes which
/// have different associated types, return MVT::Other.
-static MVT::SimpleValueType getRegisterValueType(Record *R, const CodeGenTarget &T) {
+static MVT::SimpleValueType getRegisterValueType(Record *R,
+ const CodeGenTarget &T) {
bool FoundRC = false;
MVT::SimpleValueType VT = MVT::Other;
const std::vector<CodeGenRegisterClass> &RCs = T.getRegisterClasses();
return VT;
}
-
-/// RemoveAllTypes - A quick recursive walk over a pattern which removes all
-/// type information from it.
-static void RemoveAllTypes(TreePatternNode *N) {
- N->removeTypes();
- if (!N->isLeaf())
- for (unsigned i = 0, e = N->getNumChildren(); i != e; ++i)
- RemoveAllTypes(N->getChild(i));
-}
-
-/// NodeHasProperty - return true if TreePatternNode has the specified
-/// property.
-static bool NodeHasProperty(TreePatternNode *N, SDNP Property,
- CodeGenDAGPatterns &CGP) {
- if (N->isLeaf()) {
- const ComplexPattern *CP = NodeGetComplexPattern(N, CGP);
- if (CP)
- return CP->hasProperty(Property);
- return false;
- }
- Record *Operator = N->getOperator();
- if (!Operator->isSubClassOf("SDNode")) return false;
-
- return CGP.getSDNodeInfo(Operator).hasProperty(Property);
-}
-
-static bool PatternHasProperty(TreePatternNode *N, SDNP Property,
- CodeGenDAGPatterns &CGP) {
- if (NodeHasProperty(N, Property, CGP))
- return true;
-
- for (unsigned i = 0, e = N->getNumChildren(); i != e; ++i) {
- TreePatternNode *Child = N->getChild(i);
- if (PatternHasProperty(Child, Property, CGP))
- return true;
- }
-
- return false;
-}
-
static std::string getOpcodeName(Record *Op, CodeGenDAGPatterns &CGP) {
return CGP.getSDNodeInfo(Op).getEnumName();
}
-static
-bool DisablePatternForFastISel(TreePatternNode *N, CodeGenDAGPatterns &CGP) {
- bool isStore = !N->isLeaf() &&
- getOpcodeName(N->getOperator(), CGP) == "ISD::STORE";
- if (!isStore && NodeHasProperty(N, SDNPHasChain, CGP))
- return false;
-
- bool HasChain = false;
- for (unsigned i = 0, e = N->getNumChildren(); i != e; ++i) {
- TreePatternNode *Child = N->getChild(i);
- if (PatternHasProperty(Child, SDNPHasChain, CGP)) {
- HasChain = true;
- break;
- }
- }
- return HasChain;
-}
-
//===----------------------------------------------------------------------===//
// Node Transformation emitter implementation.
//
if (P->getOnlyTree()->isLeaf())
OS << "inline bool Predicate_" << PatFragRecord->getName()
- << "(SDNode *N) {\n";
+ << "(SDNode *N) const {\n";
else {
std::string ClassName =
CGP.getSDNodeInfo(P->getOnlyTree()->getOperator()).getSDClassName();
const char *C2 = ClassName == "SDNode" ? "N" : "inN";
OS << "inline bool Predicate_" << PatFragRecord->getName()
- << "(SDNode *" << C2 << ") {\n";
+ << "(SDNode *" << C2 << ") const {\n";
if (ClassName != "SDNode")
OS << " " << ClassName << " *N = cast<" << ClassName << ">(inN);\n";
}
// Node to name mapping
std::map<std::string, std::string> VariableMap;
- // Node to operator mapping
- std::map<std::string, Record*> OperatorMap;
// Name of the folded node which produces a flag.
std::pair<std::string, unsigned> FoldedFlag;
// Names of all the folded nodes which produce chains.
return true;
}
- unsigned OpNo =
- (unsigned) NodeHasProperty(Pat, SDNPHasChain, CGP);
+ unsigned OpNo = (unsigned)Pat->NodeHasProperty(SDNPHasChain, CGP);
for (unsigned i = 0, e = Pat->getNumChildren(); i != e; ++i, ++OpNo)
if (InsertOneTypeCheck(Pat->getChild(i), Other->getChild(i),
Prefix + utostr(OpNo)))
bool &ChainEmitted, bool &InFlagDecled,
bool &ResNodeDecled, bool isRoot = false) {
const CodeGenTarget &T = CGP.getTargetInfo();
- unsigned OpNo =
- (unsigned) NodeHasProperty(N, SDNPHasChain, CGP);
- bool HasInFlag = NodeHasProperty(N, SDNPInFlag, CGP);
+ unsigned OpNo = (unsigned)N->NodeHasProperty(SDNPHasChain, CGP);
for (unsigned i = 0, e = N->getNumChildren(); i != e; ++i, ++OpNo) {
TreePatternNode *Child = N->getChild(i);
if (!Child->isLeaf()) {
}
}
- if (HasInFlag) {
+ if (N->NodeHasProperty(SDNPInFlag, CGP)) {
if (!InFlagDecled) {
emitCode("SDValue InFlag = " + getNodeName(RootName) +
"->getOperand(" + utostr(OpNo) + ");");
InFlagDecled = true;
} else
+ abort();
emitCode("InFlag = " + getNodeName(RootName) +
"->getOperand(" + utostr(OpNo) + ");");
}
const std::string &RootName,
const std::string &ChainSuffix,
bool &FoundChain) {
-
// Save loads/stores matched by a pattern.
if (!N->isLeaf() && N->getName().empty()) {
- if (NodeHasProperty(N, SDNPMemOperand, CGP))
+ if (N->NodeHasProperty(SDNPMemOperand, CGP))
LSI.push_back(getNodeName(RootName));
}
if (isRoot) {
// Record input varargs info.
NumInputRootOps = N->getNumChildren();
-
- if (DisablePatternForFastISel(N, CGP))
- emitCheck("OptLevel != CodeGenOpt::None");
-
emitCheck(PredicateCheck);
}
")->getSExtValue() == INT64_C(" +
itostr(II->getValue()) + ")");
return;
- } else if (!NodeIsComplexPattern(N)) {
- assert(0 && "Cannot match this as a leaf value!");
- abort();
}
+ assert(N->getComplexPatternInfo(CGP) != 0 &&
+ "Cannot match this as a leaf value!");
}
// If this node has a name associated with it, capture it in VariableMap. If
emitCheck(VarMapEntry + " == " + RootName);
return;
}
-
- if (!N->isLeaf())
- OperatorMap[N->getName()] = N->getOperator();
}
// Emit code to load the child nodes and match their contents recursively.
unsigned OpNo = 0;
- bool NodeHasChain = NodeHasProperty (N, SDNPHasChain, CGP);
- bool HasChain = PatternHasProperty(N, SDNPHasChain, CGP);
- bool EmittedUseCheck = false;
+ bool NodeHasChain = N->NodeHasProperty(SDNPHasChain, CGP);
+ bool HasChain = N->TreeHasProperty(SDNPHasChain, CGP);
if (HasChain) {
if (NodeHasChain)
OpNo = 1;
if (!isRoot) {
- // Multiple uses of actual result?
- emitCheck(getValueName(RootName) + ".hasOneUse()");
- EmittedUseCheck = true;
- if (NodeHasChain) {
+ // Check if it's profitable to fold the node. e.g. Check for multiple uses
+ // of actual result?
+ std::string ParentName(RootName.begin(), RootName.end()-1);
+ if (!NodeHasChain) {
+ // If this is just an interior node, check to see if it has a single
+ // use. If the node has multiple uses and the pattern has a load as
+ // an operand, then we can't fold the load.
+ emitCheck(getValueName(RootName) + ".hasOneUse()");
+ } else if (!N->isLeaf()) { // ComplexPatterns do their own legality check.
// If the immediate use can somehow reach this node through another
// path, then can't fold it either or it will create a cycle.
// e.g. In the following diagram, XX can reach ld through YY. If
// / [YY]
// | ^
// [XX]-------|
+
+ // We know we need the check if N's parent is not the root.
bool NeedCheck = P != Pattern;
if (!NeedCheck) {
+ // If the parent is the root and the node has more than one operand,
+ // we need to check.
const SDNodeInfo &PInfo = CGP.getSDNodeInfo(P->getOperator());
NeedCheck =
P->getOperator() == CGP.get_intrinsic_void_sdnode() ||
}
if (NeedCheck) {
- std::string ParentName(RootName.begin(), RootName.end()-1);
- emitCheck("IsLegalAndProfitableToFold(" + getNodeName(RootName) +
+ emitCheck("IsProfitableToFold(" + getValueName(RootName) +
+ ", " + getNodeName(ParentName) + ", N)");
+ emitCheck("IsLegalToFold(" + getValueName(RootName) +
", " + getNodeName(ParentName) + ", N)");
+ } else {
+ // Otherwise, just verify that the node only has a single use.
+ emitCheck(getValueName(RootName) + ".hasOneUse()");
}
}
}
if (NodeHasChain) {
if (FoundChain) {
- emitCheck("(" + ChainName + ".getNode() == " +
- getNodeName(RootName) + " || "
- "IsChainCompatible(" + ChainName + ".getNode(), " +
- getNodeName(RootName) + "))");
+ emitCheck("IsChainCompatible(" + ChainName + ".getNode(), " +
+ getNodeName(RootName) + ")");
OrigChains.push_back(std::make_pair(ChainName,
getValueName(RootName)));
} else
FoundChain = true;
ChainName = "Chain" + ChainSuffix;
- emitInit("SDValue " + ChainName + " = " + getNodeName(RootName) +
- "->getOperand(0);");
+
+ if (!N->getComplexPatternInfo(CGP) ||
+ isRoot)
+ emitInit("SDValue " + ChainName + " = " + getNodeName(RootName) +
+ "->getOperand(0);");
}
}
- // Don't fold any node which reads or writes a flag and has multiple uses.
- // FIXME: We really need to separate the concepts of flag and "glue". Those
- // real flag results, e.g. X86CMP output, can have multiple uses.
- // FIXME: If the optional incoming flag does not exist. Then it is ok to
- // fold it.
- if (!isRoot &&
- (PatternHasProperty(N, SDNPInFlag, CGP) ||
- PatternHasProperty(N, SDNPOptInFlag, CGP) ||
- PatternHasProperty(N, SDNPOutFlag, CGP))) {
- if (!EmittedUseCheck) {
- // Multiple uses of actual result?
- emitCheck(getValueName(RootName) + ".hasOneUse()");
- }
- }
-
// If there are node predicates for this, emit the calls.
for (unsigned i = 0, e = N->getPredicateFns().size(); i != e; ++i)
emitCheck(N->getPredicateFns()[i] + "(" + getNodeName(RootName) + ")");
ChainSuffix + utostr(OpNo), FoundChain);
}
- // Handle cases when root is a complex pattern.
- const ComplexPattern *CP;
- if (isRoot && N->isLeaf() && (CP = NodeGetComplexPattern(N, CGP))) {
+ // Handle complex patterns.
+ if (const ComplexPattern *CP = N->getComplexPatternInfo(CGP)) {
std::string Fn = CP->getSelectFunc();
unsigned NumOps = CP->getNumOperands();
for (unsigned i = 0; i < NumOps; ++i) {
emitCode("SDValue Chain" + ChainSuffix + ";");
}
- std::string Code = Fn + "(" +
- getNodeName(RootName) + ", " +
- getValueName(RootName);
+ std::string Code = Fn + "(N, "; // always pass in the root.
+ Code += getValueName(RootName);
for (unsigned i = 0; i < NumOps; i++)
Code += ", CPTmp" + RootName + "_" + utostr(i);
if (CP->hasProperty(SDNPHasChain)) {
ChainName = "Chain" + ChainSuffix;
- Code += ", CPInChain, Chain" + ChainSuffix;
+ Code += ", CPInChain, " + ChainName;
}
emitCheck(Code + ")");
}
CInfo.getEnumName());
EmitMatchCode(Child, Parent, RootName, ChainSuffix, FoundChain);
bool HasChain = false;
- if (NodeHasProperty(Child, SDNPHasChain, CGP)) {
+ if (Child->NodeHasProperty(SDNPHasChain, CGP)) {
HasChain = true;
FoldedChains.push_back(std::make_pair(getValueName(RootName),
CInfo.getNumResults()));
}
- if (NodeHasProperty(Child, SDNPOutFlag, CGP)) {
+ if (Child->NodeHasProperty(SDNPOutFlag, CGP)) {
assert(FoldedFlag.first == "" && FoldedFlag.second == 0 &&
"Pattern folded multiple nodes which produce flags?");
FoldedFlag = std::make_pair(getValueName(RootName),
CInfo.getNumResults() + (unsigned)HasChain);
}
- } else {
- // If this child has a name associated with it, capture it in VarMap. If
- // we already saw this in the pattern, emit code to verify dagness.
- if (!Child->getName().empty()) {
- std::string &VarMapEntry = VariableMap[Child->getName()];
- if (VarMapEntry.empty()) {
- VarMapEntry = getValueName(RootName);
- } else {
- // If we get here, this is a second reference to a specific name.
- // Since we already have checked that the first reference is valid,
- // we don't have to recursively match it, just check that it's the
- // same as the previously named thing.
- emitCheck(VarMapEntry + " == " + getValueName(RootName));
- Duplicates.insert(getValueName(RootName));
- return;
- }
+ return;
+ }
+
+ if (const ComplexPattern *CP = Child->getComplexPatternInfo(CGP)) {
+ EmitMatchCode(Child, Parent, RootName, ChainSuffix, FoundChain);
+ bool HasChain = false;
+
+ if (Child->NodeHasProperty(SDNPHasChain, CGP)) {
+ HasChain = true;
+ const SDNodeInfo &PInfo = CGP.getSDNodeInfo(Parent->getOperator());
+ FoldedChains.push_back(std::make_pair("CPInChain",
+ PInfo.getNumResults()));
}
-
- // Handle leaves of various types.
- if (DefInit *DI = dynamic_cast<DefInit*>(Child->getLeafValue())) {
- Record *LeafRec = DI->getDef();
- if (LeafRec->isSubClassOf("RegisterClass") ||
- LeafRec->isSubClassOf("PointerLikeRegClass")) {
- // Handle register references. Nothing to do here.
- } else if (LeafRec->isSubClassOf("Register")) {
- // Handle register references.
- } else if (LeafRec->isSubClassOf("ComplexPattern")) {
- // Handle complex pattern.
- const ComplexPattern *CP = NodeGetComplexPattern(Child, CGP);
- std::string Fn = CP->getSelectFunc();
- unsigned NumOps = CP->getNumOperands();
- for (unsigned i = 0; i < NumOps; ++i) {
- emitDecl("CPTmp" + RootName + "_" + utostr(i));
- emitCode("SDValue CPTmp" + RootName + "_" + utostr(i) + ";");
- }
- if (CP->hasProperty(SDNPHasChain)) {
- const SDNodeInfo &PInfo = CGP.getSDNodeInfo(Parent->getOperator());
- FoldedChains.push_back(std::make_pair("CPInChain",
- PInfo.getNumResults()));
- ChainName = "Chain" + ChainSuffix;
- emitDecl("CPInChain");
- emitDecl(ChainName);
- emitCode("SDValue CPInChain;");
- emitCode("SDValue " + ChainName + ";");
- }
-
- std::string Code = Fn + "(N, ";
- if (CP->hasProperty(SDNPHasChain)) {
- std::string ParentName(RootName.begin(), RootName.end()-1);
- Code += getValueName(ParentName) + ", ";
- }
- Code += getValueName(RootName);
- for (unsigned i = 0; i < NumOps; i++)
- Code += ", CPTmp" + RootName + "_" + utostr(i);
- if (CP->hasProperty(SDNPHasChain))
- Code += ", CPInChain, Chain" + ChainSuffix;
- emitCheck(Code + ")");
- } else if (LeafRec->getName() == "srcvalue") {
- // Place holder for SRCVALUE nodes. Nothing to do here.
- } else if (LeafRec->isSubClassOf("ValueType")) {
- // Make sure this is the specified value type.
- emitCheck("cast<VTSDNode>(" + getNodeName(RootName) +
- ")->getVT() == MVT::" + LeafRec->getName());
- } else if (LeafRec->isSubClassOf("CondCode")) {
- // Make sure this is the specified cond code.
- emitCheck("cast<CondCodeSDNode>(" + getNodeName(RootName) +
- ")->get() == ISD::" + LeafRec->getName());
- } else {
-#ifndef NDEBUG
- Child->dump();
- errs() << " ";
-#endif
- assert(0 && "Unknown leaf type!");
- }
-
- // If there are node predicates for this, emit the calls.
- for (unsigned i = 0, e = Child->getPredicateFns().size(); i != e; ++i)
- emitCheck(Child->getPredicateFns()[i] + "(" + getNodeName(RootName) +
- ")");
- } else if (IntInit *II =
- dynamic_cast<IntInit*>(Child->getLeafValue())) {
- unsigned NTmp = TmpNo++;
- emitCode("ConstantSDNode *Tmp"+ utostr(NTmp) +
- " = dyn_cast<ConstantSDNode>("+
- getNodeName(RootName) + ");");
- emitCheck("Tmp" + utostr(NTmp));
- unsigned CTmp = TmpNo++;
- emitCode("int64_t CN"+ utostr(CTmp) +
- " = Tmp" + utostr(NTmp) + "->getSExtValue();");
- emitCheck("CN" + utostr(CTmp) + " == "
- "INT64_C(" +itostr(II->getValue()) + ")");
+ if (Child->NodeHasProperty(SDNPOutFlag, CGP)) {
+ assert(FoldedFlag.first == "" && FoldedFlag.second == 0 &&
+ "Pattern folded multiple nodes which produce flags?");
+ FoldedFlag = std::make_pair(getValueName(RootName),
+ CP->getNumOperands() + (unsigned)HasChain);
+ }
+ return;
+ }
+
+ // If this child has a name associated with it, capture it in VarMap. If
+ // we already saw this in the pattern, emit code to verify dagness.
+ if (!Child->getName().empty()) {
+ std::string &VarMapEntry = VariableMap[Child->getName()];
+ if (VarMapEntry.empty()) {
+ VarMapEntry = getValueName(RootName);
+ } else {
+ // If we get here, this is a second reference to a specific name.
+ // Since we already have checked that the first reference is valid,
+ // we don't have to recursively match it, just check that it's the
+ // same as the previously named thing.
+ emitCheck(VarMapEntry + " == " + getValueName(RootName));
+ Duplicates.insert(getValueName(RootName));
+ return;
+ }
+ }
+
+ // Handle leaves of various types.
+ if (DefInit *DI = dynamic_cast<DefInit*>(Child->getLeafValue())) {
+ Record *LeafRec = DI->getDef();
+ if (LeafRec->isSubClassOf("RegisterClass") ||
+ LeafRec->isSubClassOf("PointerLikeRegClass")) {
+ // Handle register references. Nothing to do here.
+ } else if (LeafRec->isSubClassOf("Register")) {
+ // Handle register references.
+ } else if (LeafRec->getName() == "srcvalue") {
+ // Place holder for SRCVALUE nodes. Nothing to do here.
+ } else if (LeafRec->isSubClassOf("ValueType")) {
+ // Make sure this is the specified value type.
+ emitCheck("cast<VTSDNode>(" + getNodeName(RootName) +
+ ")->getVT() == MVT::" + LeafRec->getName());
+ } else if (LeafRec->isSubClassOf("CondCode")) {
+ // Make sure this is the specified cond code.
+ emitCheck("cast<CondCodeSDNode>(" + getNodeName(RootName) +
+ ")->get() == ISD::" + LeafRec->getName());
} else {
#ifndef NDEBUG
Child->dump();
+ errs() << " ";
#endif
assert(0 && "Unknown leaf type!");
}
+
+ // If there are node predicates for this, emit the calls.
+ for (unsigned i = 0, e = Child->getPredicateFns().size(); i != e; ++i)
+ emitCheck(Child->getPredicateFns()[i] + "(" + getNodeName(RootName) +
+ ")");
+ return;
}
+
+ if (IntInit *II = dynamic_cast<IntInit*>(Child->getLeafValue())) {
+ unsigned NTmp = TmpNo++;
+ emitCode("ConstantSDNode *Tmp"+ utostr(NTmp) +
+ " = dyn_cast<ConstantSDNode>("+
+ getNodeName(RootName) + ");");
+ emitCheck("Tmp" + utostr(NTmp));
+ unsigned CTmp = TmpNo++;
+ emitCode("int64_t CN"+ utostr(CTmp) +
+ " = Tmp" + utostr(NTmp) + "->getSExtValue();");
+ emitCheck("CN" + utostr(CTmp) + " == "
+ "INT64_C(" +itostr(II->getValue()) + ")");
+ return;
+ }
+#ifndef NDEBUG
+ Child->dump();
+#endif
+ assert(0 && "Unknown leaf type!");
}
/// EmitResultCode - Emit the action for a pattern. Now that it has matched
if (!N->getName().empty()) {
const std::string &VarName = N->getName();
std::string Val = VariableMap[VarName];
- bool ModifiedVal = false;
if (Val.empty()) {
errs() << "Variable '" << VarName << " referenced but not defined "
<< "and not caught earlier!\n";
abort();
}
- if (Val[0] == 'T' && Val[1] == 'm' && Val[2] == 'p') {
- // Already selected this operand, just return the tmpval.
- NodeOps.push_back(getValueName(Val));
- return NodeOps;
- }
- const ComplexPattern *CP;
unsigned ResNo = TmpNo++;
if (!N->isLeaf() && N->getOperator()->getName() == "imm") {
assert(N->getExtTypes().size() == 1 && "Multiple types not handled!");
" = CurDAG->getTargetConstant(((" + CastType +
") cast<ConstantSDNode>(" + Val + ")->getZExtValue()), " +
getEnumName(N->getTypeNum(0)) + ");");
- // Add Tmp<ResNo> to VariableMap, so that we don't multiply select this
- // value if used multiple times by this pattern result.
- Val = TmpVar;
- ModifiedVal = true;
- NodeOps.push_back(getValueName(Val));
+ NodeOps.push_back(getValueName(TmpVar));
} else if (!N->isLeaf() && N->getOperator()->getName() == "fpimm") {
assert(N->getExtTypes().size() == 1 && "Multiple types not handled!");
std::string TmpVar = "Tmp" + utostr(ResNo);
" = CurDAG->getTargetConstantFP(*cast<ConstantFPSDNode>(" +
Val + ")->getConstantFPValue(), cast<ConstantFPSDNode>(" +
Val + ")->getValueType(0));");
- // Add Tmp<ResNo> to VariableMap, so that we don't multiply select this
- // value if used multiple times by this pattern result.
- Val = TmpVar;
- ModifiedVal = true;
- NodeOps.push_back(getValueName(Val));
- } else if (!N->isLeaf() && N->getOperator()->getName() == "texternalsym"){
- Record *Op = OperatorMap[N->getName()];
- // Transform ExternalSymbol to TargetExternalSymbol
- if (Op && Op->getName() == "externalsym") {
- std::string TmpVar = "Tmp"+utostr(ResNo);
- emitCode("SDValue " + TmpVar + " = CurDAG->getTarget"
- "ExternalSymbol(cast<ExternalSymbolSDNode>(" +
- Val + ")->getSymbol(), " +
- getEnumName(N->getTypeNum(0)) + ");");
- // Add Tmp<ResNo> to VariableMap, so that we don't multiply select
- // this value if used multiple times by this pattern result.
- Val = TmpVar;
- ModifiedVal = true;
- }
- NodeOps.push_back(getValueName(Val));
- } else if (!N->isLeaf() && (N->getOperator()->getName() == "tglobaladdr"
- || N->getOperator()->getName() == "tglobaltlsaddr")) {
- Record *Op = OperatorMap[N->getName()];
- // Transform GlobalAddress to TargetGlobalAddress
- if (Op && (Op->getName() == "globaladdr" ||
- Op->getName() == "globaltlsaddr")) {
- std::string TmpVar = "Tmp" + utostr(ResNo);
- emitCode("SDValue " + TmpVar + " = CurDAG->getTarget"
- "GlobalAddress(cast<GlobalAddressSDNode>(" + Val +
- ")->getGlobal(), " + getEnumName(N->getTypeNum(0)) +
- ");");
- // Add Tmp<ResNo> to VariableMap, so that we don't multiply select
- // this value if used multiple times by this pattern result.
- Val = TmpVar;
- ModifiedVal = true;
+ NodeOps.push_back(getValueName(TmpVar));
+ } else if (const ComplexPattern *CP = N->getComplexPatternInfo(CGP)) {
+ for (unsigned i = 0; i < CP->getNumOperands(); ++i)
+ NodeOps.push_back(getValueName("CPTmp" + Val + "_" + utostr(i)));
+ } else {
+ // This node, probably wrapped in a SDNodeXForm, behaves like a leaf
+ // node even if it isn't one. Don't select it.
+ if (!LikeLeaf) {
+ if (isRoot && N->isLeaf()) {
+ emitCode("ReplaceUses(SDValue(N, 0), " + Val + ");");
+ emitCode("return NULL;");
+ }
}
NodeOps.push_back(getValueName(Val));
- } else if (!N->isLeaf()
- && (N->getOperator()->getName() == "texternalsym"
- || N->getOperator()->getName() == "tconstpool")) {
- // Do not rewrite the variable name, since we don't generate a new
- // temporary.
- NodeOps.push_back(getValueName(Val));
- } else if (N->isLeaf() && (CP = NodeGetComplexPattern(N, CGP))) {
- for (unsigned i = 0; i < CP->getNumOperands(); ++i) {
- NodeOps.push_back(getValueName("CPTmp" + Val + "_" + utostr(i)));
- }
- } else {
- // This node, probably wrapped in a SDNodeXForm, behaves like a leaf
- // node even if it isn't one. Don't select it.
- if (!LikeLeaf) {
- if (isRoot && N->isLeaf()) {
- emitCode("ReplaceUses(SDValue(N, 0), " + Val + ");");
- emitCode("return NULL;");
- }
- }
- NodeOps.push_back(getValueName(Val));
- }
-
- if (ModifiedVal) {
- VariableMap[VarName] = Val;
}
return NodeOps;
}
bool HasImpInputs = isRoot && Inst.getNumImpOperands() > 0;
bool HasImpResults = isRoot && DstRegs.size() > 0;
bool NodeHasOptInFlag = isRoot &&
- PatternHasProperty(Pattern, SDNPOptInFlag, CGP);
+ Pattern->TreeHasProperty(SDNPOptInFlag, CGP);
bool NodeHasInFlag = isRoot &&
- PatternHasProperty(Pattern, SDNPInFlag, CGP);
+ Pattern->TreeHasProperty(SDNPInFlag, CGP);
bool NodeHasOutFlag = isRoot &&
- PatternHasProperty(Pattern, SDNPOutFlag, CGP);
+ Pattern->TreeHasProperty(SDNPOutFlag, CGP);
bool NodeHasChain = InstPatNode &&
- PatternHasProperty(InstPatNode, SDNPHasChain, CGP);
- bool InputHasChain = isRoot &&
- NodeHasProperty(Pattern, SDNPHasChain, CGP);
+ InstPatNode->TreeHasProperty(SDNPHasChain, CGP);
+ bool InputHasChain = isRoot && Pattern->NodeHasProperty(SDNPHasChain, CGP);
unsigned NumResults = Inst.getNumResults();
unsigned NumDstRegs = HasImpResults ? DstRegs.size() : 0;
}
if (IsVariadic)
emitCode("SmallVector<SDValue, 8> Ops" + utostr(OpcNo) + ";");
-
+
// How many results is this pattern expected to produce?
unsigned NumPatResults = 0;
for (unsigned i = 0, e = Pattern->getExtTypes().size(); i != e; i++) {
"N->getDebugLoc(), MVT::Other, "
"&InChains[0], InChains.size());");
if (GenDebug) {
- emitCode("CurDAG->setSubgraphColor(" + ChainName +".getNode(), \"yellow\");");
- emitCode("CurDAG->setSubgraphColor(" + ChainName +".getNode(), \"black\");");
+ emitCode("CurDAG->setSubgraphColor(" + ChainName +
+ ".getNode(), \"yellow\");");
+ emitCode("CurDAG->setSubgraphColor(" + ChainName +
+ ".getNode(), \"black\");");
}
}
utostr(FoldedFlag.second) + ")");
ReplaceTos.push_back("InFlag");
} else {
- assert(NodeHasProperty(Pattern, SDNPOutFlag, CGP));
+ assert(Pattern->NodeHasProperty(SDNPOutFlag, CGP));
ReplaceFroms.push_back("SDValue(N, " +
utostr(NumPatResults + (unsigned)InputHasChain)
+ ")");
bool FoundChain = false;
Emitter.EmitMatchCode(Pattern.getSrcPattern(), NULL, "N", "", FoundChain);
- // TP - Get *SOME* tree pattern, we don't care which.
+ // TP - Get *SOME* tree pattern, we don't care which. It is only used for
+ // diagnostics, which we know are impossible at this point.
TreePattern &TP = *CGP.pf_begin()->second;
// At this point, we know that we structurally match the pattern, but the
// types are resolved.
//
TreePatternNode *Pat = Pattern.getSrcPattern()->clone();
- RemoveAllTypes(Pat);
+ Pat->RemoveAllTypes();
do {
// Resolve/propagate as many types as possible.
void DAGISelEmitter::EmitInstructionSelector(raw_ostream &OS) {
const CodeGenTarget &Target = CGP.getTargetInfo();
-
+
// Get the namespace to insert instructions into.
std::string InstNS = Target.getInstNamespace();
if (!InstNS.empty()) InstNS += "::";
for (CodeGenDAGPatterns::ptm_iterator I = CGP.ptm_begin(),
E = CGP.ptm_end(); I != E; ++I) {
const PatternToMatch &Pattern = *I;
-
TreePatternNode *Node = Pattern.getSrcPattern();
if (!Node->isLeaf()) {
PatternsByOpcode[getOpcodeName(Node->getOperator(), CGP)].
if (dynamic_cast<IntInit*>(Node->getLeafValue())) {
PatternsByOpcode[getOpcodeName(CGP.getSDNodeNamed("imm"), CGP)].
push_back(&Pattern);
- } else if ((CP = NodeGetComplexPattern(Node, CGP))) {
+ } else if ((CP = Node->getComplexPatternInfo(CGP))) {
std::vector<Record*> OpNodes = CP->getRootNodes();
for (unsigned j = 0, e = OpNodes.size(); j != e; j++) {
PatternsByOpcode[getOpcodeName(OpNodes[j], CGP)]
// Replace the emission code within selection routines with calls to the
// emission functions.
if (GenDebug)
- GeneratedCode.push_back(std::make_pair(0, "CurDAG->setSubgraphColor(N, \"red\");"));
- CallerCode = "SDNode *Result = Emit_" + utostr(EmitFuncNum) + CallerCode;
+ GeneratedCode.push_back(std::make_pair(0,
+ "CurDAG->setSubgraphColor(N, \"red\");"));
+ CallerCode = "SDNode *Result = Emit_" + utostr(EmitFuncNum) +CallerCode;
GeneratedCode.push_back(std::make_pair(3, CallerCode));
if (GenDebug) {
GeneratedCode.push_back(std::make_pair(0, "if(Result) {"));
- GeneratedCode.push_back(std::make_pair(0, " CurDAG->setSubgraphColor(Result, \"yellow\");"));
- GeneratedCode.push_back(std::make_pair(0, " CurDAG->setSubgraphColor(Result, \"black\");"));
+ GeneratedCode.push_back(std::make_pair(0,
+ " CurDAG->setSubgraphColor(Result, \"yellow\");"));
+ GeneratedCode.push_back(std::make_pair(0,
+ " CurDAG->setSubgraphColor(Result, \"black\");"));
GeneratedCode.push_back(std::make_pair(0, "}"));
- //GeneratedCode.push_back(std::make_pair(0, "CurDAG->setSubgraphColor(N, \"black\");"));
}
GeneratedCode.push_back(std::make_pair(0, "return Result;"));
}
// catch the case where nothing handles a pattern.
if (mightNotMatch) {
OS << "\n";
- if (OpName != "ISD::INTRINSIC_W_CHAIN" &&
- OpName != "ISD::INTRINSIC_WO_CHAIN" &&
- OpName != "ISD::INTRINSIC_VOID")
- OS << " CannotYetSelect(N);\n";
- else
- OS << " CannotYetSelectIntrinsic(N);\n";
-
+ OS << " CannotYetSelect(N);\n";
OS << " return NULL;\n";
}
OS << "}\n\n";
}
OS << " } // end of big switch.\n\n"
- << " if (N->getOpcode() != ISD::INTRINSIC_W_CHAIN &&\n"
- << " N->getOpcode() != ISD::INTRINSIC_WO_CHAIN &&\n"
- << " N->getOpcode() != ISD::INTRINSIC_VOID) {\n"
- << " CannotYetSelect(N);\n"
- << " } else {\n"
- << " CannotYetSelectIntrinsic(N);\n"
- << " }\n"
+ << " CannotYetSelect(N);\n"
<< " return NULL;\n"
<< "}\n\n";
}
+namespace {
+// PatternSortingPredicate - return true if we prefer to match LHS before RHS.
+// In particular, we want to match maximal patterns first and lowest cost within
+// a particular complexity first.
+struct PatternSortingPredicate2 {
+ PatternSortingPredicate2(CodeGenDAGPatterns &cgp) : CGP(cgp) {}
+ CodeGenDAGPatterns &CGP;
+
+ bool operator()(const PatternToMatch *LHS,
+ const PatternToMatch *RHS) {
+ unsigned LHSSize = getPatternSize(LHS->getSrcPattern(), CGP);
+ unsigned RHSSize = getPatternSize(RHS->getSrcPattern(), CGP);
+ LHSSize += LHS->getAddedComplexity();
+ RHSSize += RHS->getAddedComplexity();
+ if (LHSSize > RHSSize) return true; // LHS -> bigger -> less cost
+ if (LHSSize < RHSSize) return false;
+
+ // If the patterns have equal complexity, compare generated instruction cost
+ unsigned LHSCost = getResultPatternCost(LHS->getDstPattern(), CGP);
+ unsigned RHSCost = getResultPatternCost(RHS->getDstPattern(), CGP);
+ if (LHSCost < RHSCost) return true;
+ if (LHSCost > RHSCost) return false;
+
+ return getResultPatternSize(LHS->getDstPattern(), CGP) <
+ getResultPatternSize(RHS->getDstPattern(), CGP);
+ }
+};
+}
+
+
void DAGISelEmitter::run(raw_ostream &OS) {
EmitSourceFileHeader("DAG Instruction Selector for the " +
CGP.getTargetInfo().getName() + " target", OS);
DEBUG(errs() << "\n");
}
+#ifdef ENABLE_NEW_ISEL
+ // Add all the patterns to a temporary list so we can sort them.
+ std::vector<const PatternToMatch*> Patterns;
+ for (CodeGenDAGPatterns::ptm_iterator I = CGP.ptm_begin(), E = CGP.ptm_end();
+ I != E; ++I)
+ Patterns.push_back(&*I);
+
+ // We want to process the matches in order of minimal cost. Sort the patterns
+ // so the least cost one is at the start.
+ // FIXME: Eliminate "PatternSortingPredicate" and rename.
+ std::stable_sort(Patterns.begin(), Patterns.end(),
+ PatternSortingPredicate2(CGP));
+
+
+ // Convert each pattern into Matcher's.
+ std::vector<Matcher*> PatternMatchers;
+ for (unsigned i = 0, e = Patterns.size(); i != e; ++i)
+ PatternMatchers.push_back(ConvertPatternToMatcher(*Patterns[i], CGP));
+
+ Matcher *TheMatcher = new ScopeMatcher(&PatternMatchers[0],
+ PatternMatchers.size());
+
+ TheMatcher = OptimizeMatcher(TheMatcher);
+ //Matcher->dump();
+ EmitMatcherTable(TheMatcher, OS);
+ delete TheMatcher;
+
+#else
// At this point, we have full information about the 'Patterns' we need to
// parse, both implicitly from instructions as well as from explicit pattern
// definitions. Emit the resultant instruction selector.
EmitInstructionSelector(OS);
-
+#endif
}