#include <iostream>
using namespace llvm;
+#define ENABLE_NEW_ISEL
+
+
static cl::opt<bool>
GenDebug("gen-debug", cl::desc("Generate debug code"), cl::init(false));
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();
// 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.
bool &ResNodeDecled, bool isRoot = false) {
const CodeGenTarget &T = CGP.getTargetInfo();
unsigned OpNo = (unsigned)N->NodeHasProperty(SDNPHasChain, CGP);
- bool HasInFlag = N->NodeHasProperty(SDNPInFlag, 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) + ");");
}
emitCheck(VarMapEntry + " == " + RootName);
return;
}
-
- if (!N->isLeaf())
- OperatorMap[N->getName()] = N->getOperator();
}
ChainSuffix + utostr(OpNo), FoundChain);
}
- // Handle cases when root is a complex pattern.
- const ComplexPattern *CP;
- if (N->isLeaf() && (CP = N->getComplexPatternInfo(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) {
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(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 = N->getComplexPatternInfo(CGP))) {
- for (unsigned i = 0; i < CP->getNumOperands(); ++i) {
+ 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.
}
NodeOps.push_back(getValueName(Val));
}
-
- if (ModifiedVal)
- VariableMap[VarName] = Val;
return NodeOps;
}
if (N->isLeaf()) {
}
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\");");
}
}
// 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;"));
}
<< "}\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);
<< "// by the instruction selector.\n";
OS << "#include \"llvm/CodeGen/DAGISelHeader.h\"\n\n";
- EmitNodeTransforms(OS);
+ DEBUG(errs() << "\n\nALL PATTERNS TO MATCH:\n\n";
+ for (CodeGenDAGPatterns::ptm_iterator I = CGP.ptm_begin(),
+ E = CGP.ptm_end(); I != E; ++I) {
+ errs() << "PATTERN: "; I->getSrcPattern()->dump();
+ errs() << "\nRESULT: "; I->getDstPattern()->dump();
+ errs() << "\n";
+ });
+
+ // FIXME: These are being used by hand written code, gross.
EmitPredicateFunctions(OS);
-
- DEBUG(errs() << "\n\nALL PATTERNS TO MATCH:\n\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) {
- DEBUG(errs() << "PATTERN: "; I->getSrcPattern()->dump());
- DEBUG(errs() << "\nRESULT: "; I->getDstPattern()->dump());
- DEBUG(errs() << "\n");
+ 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 variant of each pattern into a Matcher.
+ std::vector<Matcher*> PatternMatchers;
+ for (unsigned i = 0, e = Patterns.size(); i != e; ++i) {
+ for (unsigned Variant = 0; ; ++Variant) {
+ if (Matcher *M = ConvertPatternToMatcher(*Patterns[i], Variant, CGP))
+ PatternMatchers.push_back(M);
+ else
+ break;
+ }
}
+
+
+ Matcher *TheMatcher = new ScopeMatcher(&PatternMatchers[0],
+ PatternMatchers.size());
+
+ TheMatcher = OptimizeMatcher(TheMatcher, CGP);
+ //Matcher->dump();
+ EmitMatcherTable(TheMatcher, CGP, OS);
+ delete TheMatcher;
+#else
+ EmitNodeTransforms(OS);
+
// 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);
-
-#if 0
- MatcherNode *Matcher = 0;
- // Walk the patterns backwards, building a matcher for each and adding it to
- // the matcher for the whole target.
- for (CodeGenDAGPatterns::ptm_iterator I = CGP.ptm_begin(),
- E = CGP.ptm_end(); I != E;) {
- const PatternToMatch &Pattern = *--E;
- MatcherNode *N = ConvertPatternToMatcher(Pattern, CGP);
-
- if (Matcher == 0)
- Matcher = N;
- else
- Matcher = new PushMatcherNode(N, Matcher);
- }
-
- // OptimizeMatcher(Matcher);
- EmitMatcherTable(Matcher, OS);
- //Matcher->dump();
- delete Matcher;
#endif
}