Differential D48545 Diff 155368 llvm/trunk/utils/TableGen/CodeGenDAGPatterns.cpp

Changeset View

Standalone View

llvm/trunk/utils/TableGen/CodeGenDAGPatterns.cpp

Show First 20 Lines • Show All 1,657 Lines • ▼ Show 20 Lines	if (Operator->getName() == "set" \|\|
return 0; // All return nothing.		return 0; // All return nothing.

if (Operator->isSubClassOf("Intrinsic"))		if (Operator->isSubClassOf("Intrinsic"))
return CDP.getIntrinsic(Operator).IS.RetVTs.size();		return CDP.getIntrinsic(Operator).IS.RetVTs.size();

if (Operator->isSubClassOf("SDNode"))		if (Operator->isSubClassOf("SDNode"))
return CDP.getSDNodeInfo(Operator).getNumResults();		return CDP.getSDNodeInfo(Operator).getNumResults();

if (Operator->isSubClassOf("PatFrag")) {		if (Operator->isSubClassOf("PatFrags")) {
// If we've already parsed this pattern fragment, get it. Otherwise, handle		// If we've already parsed this pattern fragment, get it. Otherwise, handle
// the forward reference case where one pattern fragment references another		// the forward reference case where one pattern fragment references another
// before it is processed.		// before it is processed.
if (TreePattern *PFRec = CDP.getPatternFragmentIfRead(Operator))		if (TreePattern *PFRec = CDP.getPatternFragmentIfRead(Operator)) {
return PFRec->getOnlyTree()->getNumTypes();		// The number of results of a fragment with alternative records is the
		// maximum number of results across all alternatives.
		unsigned NumResults = 0;
		for (auto T : PFRec->getTrees())
		NumResults = std::max(NumResults, T->getNumTypes());
		return NumResults;
		}

// Get the result tree.		ListInit *LI = Operator->getValueAsListInit("Fragments");
DagInit *Tree = Operator->getValueAsDag("Fragment");		assert(LI && "Invalid Fragment");
		unsigned NumResults = 0;
		for (Init *I : LI->getValues()) {
Record *Op = nullptr;		Record *Op = nullptr;
if (Tree)		if (DagInit *Dag = dyn_cast<DagInit>(I))
if (DefInit *DI = dyn_cast<DefInit>(Tree->getOperator()))		if (DefInit *DI = dyn_cast<DefInit>(Dag->getOperator()))
Op = DI->getDef();		Op = DI->getDef();
assert(Op && "Invalid Fragment");		assert(Op && "Invalid Fragment");
return GetNumNodeResults(Op, CDP);		NumResults = std::max(NumResults, GetNumNodeResults(Op, CDP));
		}
		return NumResults;
}		}

if (Operator->isSubClassOf("Instruction")) {		if (Operator->isSubClassOf("Instruction")) {
CodeGenInstruction &InstInfo = CDP.getTargetInfo().getInstruction(Operator);		CodeGenInstruction &InstInfo = CDP.getTargetInfo().getInstruction(Operator);

unsigned NumDefsToAdd = InstInfo.Operands.NumDefs;		unsigned NumDefsToAdd = InstInfo.Operands.NumDefs;

// Subtract any defaulted outputs.		// Subtract any defaulted outputs.
▲ Show 20 Lines • Show All 149 Lines • ▼ Show 20 Lines	for (unsigned i = 0, e = getNumChildren(); i != e; ++i) {
} else {		} else {
getChild(i)->SubstituteFormalArguments(ArgMap);		getChild(i)->SubstituteFormalArguments(ArgMap);
}		}
}		}
}		}


/// InlinePatternFragments - If this pattern refers to any pattern		/// InlinePatternFragments - If this pattern refers to any pattern
/// fragments, inline them into place, giving us a pattern without any		/// fragments, return the set of inlined versions (this can be more than
/// PatFrag references.		/// one if a PatFrags record has multiple alternatives).
TreePatternNodePtr TreePatternNode::InlinePatternFragments(TreePatternNodePtr T,		void TreePatternNode::InlinePatternFragments(
TreePattern &TP) {		TreePatternNodePtr T, TreePattern &TP,
		std::vector<TreePatternNodePtr> &OutAlternatives) {

if (TP.hasError())		if (TP.hasError())
return nullptr;		return;

		if (isLeaf()) {
		OutAlternatives.push_back(T); // nothing to do.
		return;
		}

if (isLeaf())
return T; // nothing to do.
Record *Op = getOperator();		Record *Op = getOperator();

if (!Op->isSubClassOf("PatFrag")) {		if (!Op->isSubClassOf("PatFrags")) {
// Just recursively inline children nodes.		if (getNumChildren() == 0) {
		OutAlternatives.push_back(T);
		return;
		}

		// Recursively inline children nodes.
		std::vector<std::vector<TreePatternNodePtr> > ChildAlternatives;
		ChildAlternatives.resize(getNumChildren());
for (unsigned i = 0, e = getNumChildren(); i != e; ++i) {		for (unsigned i = 0, e = getNumChildren(); i != e; ++i) {
TreePatternNodePtr Child = getChildShared(i);		TreePatternNodePtr Child = getChildShared(i);
TreePatternNodePtr NewChild = Child->InlinePatternFragments(Child, TP);		Child->InlinePatternFragments(Child, TP, ChildAlternatives[i]);
		// If there are no alternatives for any child, there are no
		// alternatives for this expression as whole.
		if (ChildAlternatives[i].empty())
		return;

		for (auto NewChild : ChildAlternatives[i])
assert((Child->getPredicateFns().empty() \|\|		assert((Child->getPredicateFns().empty() \|\|
NewChild->getPredicateFns() == Child->getPredicateFns()) &&		NewChild->getPredicateFns() == Child->getPredicateFns()) &&
"Non-empty child predicate clobbered!");		"Non-empty child predicate clobbered!");
		}

setChild(i, std::move(NewChild));		// The end result is an all-pairs construction of the resultant pattern.
		std::vector<unsigned> Idxs;
		Idxs.resize(ChildAlternatives.size());
		bool NotDone;
		do {
		// Create the variant and add it to the output list.
		std::vector<TreePatternNodePtr> NewChildren;
		for (unsigned i = 0, e = ChildAlternatives.size(); i != e; ++i)
		NewChildren.push_back(ChildAlternatives[i][Idxs[i]]);
		TreePatternNodePtr R = std::make_shared<TreePatternNode>(
		getOperator(), NewChildren, getNumTypes());

		// Copy over properties.
		R->setName(getName());
		R->setPredicateFns(getPredicateFns());
		R->setTransformFn(getTransformFn());
		for (unsigned i = 0, e = getNumTypes(); i != e; ++i)
		R->setType(i, getExtType(i));

		// Register alternative.
		OutAlternatives.push_back(R);

		// Increment indices to the next permutation by incrementing the
		// indices from last index backward, e.g., generate the sequence
		// [0, 0], [0, 1], [1, 0], [1, 1].
		int IdxsIdx;
		for (IdxsIdx = Idxs.size() - 1; IdxsIdx >= 0; --IdxsIdx) {
		if (++Idxs[IdxsIdx] == ChildAlternatives[IdxsIdx].size())
		Idxs[IdxsIdx] = 0;
		else
		break;
}		}
return T;		NotDone = (IdxsIdx >= 0);
		} while (NotDone);

		return;
}		}

// Otherwise, we found a reference to a fragment. First, look up its		// Otherwise, we found a reference to a fragment. First, look up its
// TreePattern record.		// TreePattern record.
TreePattern *Frag = TP.getDAGPatterns().getPatternFragment(Op);		TreePattern *Frag = TP.getDAGPatterns().getPatternFragment(Op);

// Verify that we are passing the right number of operands.		// Verify that we are passing the right number of operands.
if (Frag->getNumArgs() != Children.size()) {		if (Frag->getNumArgs() != Children.size()) {
TP.error("'" + Op->getName() + "' fragment requires " +		TP.error("'" + Op->getName() + "' fragment requires " +
Twine(Frag->getNumArgs()) + " operands!");		Twine(Frag->getNumArgs()) + " operands!");
return {nullptr};		return;
}		}

TreePatternNodePtr FragTree = Frag->getOnlyTree()->clone();

TreePredicateFn PredFn(Frag);
if (!PredFn.isAlwaysTrue())
FragTree->addPredicateFn(PredFn);

// Resolve formal arguments to their actual value.
if (Frag->getNumArgs()) {
// Compute the map of formal to actual arguments.		// Compute the map of formal to actual arguments.
std::map<std::string, TreePatternNodePtr> ArgMap;		std::map<std::string, TreePatternNodePtr> ArgMap;
for (unsigned i = 0, e = Frag->getNumArgs(); i != e; ++i) {		for (unsigned i = 0, e = Frag->getNumArgs(); i != e; ++i) {
const TreePatternNodePtr &Child = getChildShared(i);		const TreePatternNodePtr &Child = getChildShared(i);
ArgMap[Frag->getArgName(i)] = Child->InlinePatternFragments(Child, TP);		ArgMap[Frag->getArgName(i)] = Child;
}		}

		// Loop over all fragment alternatives.
		for (auto Alternative : Frag->getTrees()) {
		TreePatternNodePtr FragTree = Alternative->clone();

		TreePredicateFn PredFn(Frag);
		if (!PredFn.isAlwaysTrue())
		FragTree->addPredicateFn(PredFn);

		// Resolve formal arguments to their actual value.
		if (Frag->getNumArgs())
FragTree->SubstituteFormalArguments(ArgMap);		FragTree->SubstituteFormalArguments(ArgMap);
}

		// Transfer types. Note that the resolved alternative may have fewer
		// (but not more) results than the PatFrags node.
FragTree->setName(getName());		FragTree->setName(getName());
for (unsigned i = 0, e = Types.size(); i != e; ++i)		for (unsigned i = 0, e = FragTree->getNumTypes(); i != e; ++i)
FragTree->UpdateNodeType(i, getExtType(i), TP);		FragTree->UpdateNodeType(i, getExtType(i), TP);

// Transfer in the old predicates.		// Transfer in the old predicates.
for (const TreePredicateFn &Pred : getPredicateFns())		for (const TreePredicateFn &Pred : getPredicateFns())
FragTree->addPredicateFn(Pred);		FragTree->addPredicateFn(Pred);

// The fragment we inlined could have recursive inlining that is needed. See		// 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.		// if there are any pattern fragments in it and inline them as needed.
return FragTree->InlinePatternFragments(FragTree, TP);		FragTree->InlinePatternFragments(FragTree, TP, OutAlternatives);
		}
}		}

/// getImplicitType - Check to see if the specified record has an implicit		/// getImplicitType - Check to see if the specified record has an implicit
/// type which should be applied to it. This will infer the type of register		/// type which should be applied to it. This will infer the type of register
/// references from the register file information, for example.		/// references from the register file information, for example.
///		///
/// When Unnamed is set, return the type of a DAG operand with no name, such as		/// When Unnamed is set, return the type of a DAG operand with no name, such as
/// the F8RC register class argument in:		/// the F8RC register class argument in:
Show All 30 Lines	if (R->isSubClassOf("RegisterClass")) {
// In a named operand, the register class provides the possible set of		// In a named operand, the register class provides the possible set of
// types.		// types.
if (NotRegisters)		if (NotRegisters)
return TypeSetByHwMode(); // Unknown.		return TypeSetByHwMode(); // Unknown.
const CodeGenTarget &T = TP.getDAGPatterns().getTargetInfo();		const CodeGenTarget &T = TP.getDAGPatterns().getTargetInfo();
return TypeSetByHwMode(T.getRegisterClass(R).getValueTypes());		return TypeSetByHwMode(T.getRegisterClass(R).getValueTypes());
}		}

if (R->isSubClassOf("PatFrag")) {		if (R->isSubClassOf("PatFrags")) {
assert(ResNo == 0 && "FIXME: PatFrag with multiple results?");		assert(ResNo == 0 && "FIXME: PatFrag with multiple results?");
// Pattern fragment types will be resolved when they are inlined.		// Pattern fragment types will be resolved when they are inlined.
return TypeSetByHwMode(); // Unknown.		return TypeSetByHwMode(); // Unknown.
}		}

if (R->isSubClassOf("Register")) {		if (R->isSubClassOf("Register")) {
assert(ResNo == 0 && "Registers only produce one result!");		assert(ResNo == 0 && "Registers only produce one result!");
if (NotRegisters)		if (NotRegisters)
▲ Show 20 Lines • Show All 235 Lines • ▼ Show 20 Lines	if (IntInit *II = dyn_cast<IntInit>(getLeafValue())) {
break;		break;
}		}
return MadeChange;		return MadeChange;
}		}

return false;		return false;
}		}

// special handling for set, which isn't really an SDNode.
if (getOperator()->getName() == "set") {
assert(getNumTypes() == 0 && "Set doesn't produce a value");
assert(getNumChildren() >= 2 && "Missing RHS of a set?");
unsigned NC = getNumChildren();

TreePatternNode *SetVal = getChild(NC-1);
bool MadeChange = SetVal->ApplyTypeConstraints(TP, NotRegisters);

for (unsigned i = 0; i < NC-1; ++i) {
TreePatternNode *Child = getChild(i);
MadeChange \|= Child->ApplyTypeConstraints(TP, NotRegisters);

// Types of operands must match.
MadeChange \|= Child->UpdateNodeType(0, SetVal->getExtType(i), TP);
MadeChange \|= SetVal->UpdateNodeType(i, Child->getExtType(0), TP);
}
return MadeChange;
}

if (getOperator()->getName() == "implicit") {
assert(getNumTypes() == 0 && "Node doesn't produce a value");

bool MadeChange = false;
for (unsigned i = 0; i < getNumChildren(); ++i)
MadeChange \|= getChild(i)->ApplyTypeConstraints(TP, NotRegisters);
return MadeChange;
}

if (const CodeGenIntrinsic *Int = getIntrinsicInfo(CDP)) {		if (const CodeGenIntrinsic *Int = getIntrinsicInfo(CDP)) {
bool MadeChange = false;		bool MadeChange = false;

// Apply the result type to the node.		// Apply the result type to the node.
unsigned NumRetVTs = Int->IS.RetVTs.size();		unsigned NumRetVTs = Int->IS.RetVTs.size();
unsigned NumParamVTs = Int->IS.ParamVTs.size();		unsigned NumParamVTs = Int->IS.ParamVTs.size();

for (unsigned i = 0, e = NumRetVTs; i != e; ++i)		for (unsigned i = 0, e = NumRetVTs; i != e; ++i)
▲ Show 20 Lines • Show All 294 Lines • ▼ Show 20 Lines
TreePatternNodePtr TreePattern::ParseTreePattern(Init *TheInit,		TreePatternNodePtr TreePattern::ParseTreePattern(Init *TheInit,
StringRef OpName) {		StringRef OpName) {
if (DefInit *DI = dyn_cast<DefInit>(TheInit)) {		if (DefInit *DI = dyn_cast<DefInit>(TheInit)) {
Record *R = DI->getDef();		Record *R = DI->getDef();

// Direct reference to a leaf DagNode or PatFrag? Turn it into a		// Direct reference to a leaf DagNode or PatFrag? Turn it into a
// TreePatternNode of its own. For example:		// TreePatternNode of its own. For example:
/// (foo GPR, imm) -> (foo GPR, (imm))		/// (foo GPR, imm) -> (foo GPR, (imm))
if (R->isSubClassOf("SDNode") \|\| R->isSubClassOf("PatFrag"))		if (R->isSubClassOf("SDNode") \|\| R->isSubClassOf("PatFrags"))
return ParseTreePattern(		return ParseTreePattern(
DagInit::get(DI, nullptr,		DagInit::get(DI, nullptr,
std::vector<std::pair<Init, StringInit> >()),		std::vector<std::pair<Init, StringInit> >()),
OpName);		OpName);

// Input argument?		// Input argument?
TreePatternNodePtr Res = std::make_shared<TreePatternNode>(DI, 1);		TreePatternNodePtr Res = std::make_shared<TreePatternNode>(DI, 1);
if (R->getName() == "node" && !OpName.empty()) {		if (R->getName() == "node" && !OpName.empty()) {
▲ Show 20 Lines • Show All 56 Lines • ▼ Show 20 Lines	if (Operator->isSubClassOf("ValueType")) {
New->UpdateNodeType(0, getValueTypeByHwMode(Operator, CGH), *this);		New->UpdateNodeType(0, getValueTypeByHwMode(Operator, CGH), *this);

if (!OpName.empty())		if (!OpName.empty())
error("ValueType cast should not have a name!");		error("ValueType cast should not have a name!");
return New;		return New;
}		}

// Verify that this is something that makes sense for an operator.		// Verify that this is something that makes sense for an operator.
if (!Operator->isSubClassOf("PatFrag") &&		if (!Operator->isSubClassOf("PatFrags") &&
!Operator->isSubClassOf("SDNode") &&		!Operator->isSubClassOf("SDNode") &&
!Operator->isSubClassOf("Instruction") &&		!Operator->isSubClassOf("Instruction") &&
!Operator->isSubClassOf("SDNodeXForm") &&		!Operator->isSubClassOf("SDNodeXForm") &&
!Operator->isSubClassOf("Intrinsic") &&		!Operator->isSubClassOf("Intrinsic") &&
!Operator->isSubClassOf("ComplexPattern") &&		!Operator->isSubClassOf("ComplexPattern") &&
Operator->getName() != "set" &&		Operator->getName() != "set" &&
Operator->getName() != "implicit")		Operator->getName() != "implicit")
error("Unrecognized node '" + Operator->getName() + "'!");		error("Unrecognized node '" + Operator->getName() + "'!");
▲ Show 20 Lines • Show All 305 Lines • ▼ Show 20 Lines


/// ParsePatternFragments - Parse all of the PatFrag definitions in the .td		/// ParsePatternFragments - Parse all of the PatFrag definitions in the .td
/// file, building up the PatternFragments map. After we've collected them all,		/// file, building up the PatternFragments map. After we've collected them all,
/// inline fragments together as necessary, so that there are no references left		/// inline fragments together as necessary, so that there are no references left
/// inside a pattern fragment to a pattern fragment.		/// inside a pattern fragment to a pattern fragment.
///		///
void CodeGenDAGPatterns::ParsePatternFragments(bool OutFrags) {		void CodeGenDAGPatterns::ParsePatternFragments(bool OutFrags) {
std::vector<Record*> Fragments = Records.getAllDerivedDefinitions("PatFrag");		std::vector<Record*> Fragments = Records.getAllDerivedDefinitions("PatFrags");

// First step, parse all of the fragments.		// First step, parse all of the fragments.
for (Record *Frag : Fragments) {		for (Record *Frag : Fragments) {
if (OutFrags != Frag->isSubClassOf("OutPatFrag"))		if (OutFrags != Frag->isSubClassOf("OutPatFrag"))
continue;		continue;

DagInit *Tree = Frag->getValueAsDag("Fragment");		ListInit *LI = Frag->getValueAsListInit("Fragments");
TreePattern *P =		TreePattern *P =
(PatternFragments[Frag] = llvm::make_unique<TreePattern>(		(PatternFragments[Frag] = llvm::make_unique<TreePattern>(
Frag, Tree, !Frag->isSubClassOf("OutPatFrag"),		Frag, LI, !Frag->isSubClassOf("OutPatFrag"),
*this)).get();		*this)).get();

// Validate the argument list, converting it to set, to discard duplicates.		// Validate the argument list, converting it to set, to discard duplicates.
std::vector<std::string> &Args = P->getArgList();		std::vector<std::string> &Args = P->getArgList();
// Copy the args so we can take StringRefs to them.		// Copy the args so we can take StringRefs to them.
auto ArgsCopy = Args;		auto ArgsCopy = Args;
SmallDenseSet<StringRef, 4> OperandsSet;		SmallDenseSet<StringRef, 4> OperandsSet;
OperandsSet.insert(ArgsCopy.begin(), ArgsCopy.end());		OperandsSet.insert(ArgsCopy.begin(), ArgsCopy.end());
Show All 31 Lines	for (Record *Frag : Fragments) {
if (!OperandsSet.empty())		if (!OperandsSet.empty())
P->error("Operands list does not contain an entry for operand '" +		P->error("Operands list does not contain an entry for operand '" +
*OperandsSet.begin() + "'!");		*OperandsSet.begin() + "'!");

// If there is a code init for this fragment, keep track of the fact that		// If there is a code init for this fragment, keep track of the fact that
// this fragment uses it.		// this fragment uses it.
TreePredicateFn PredFn(P);		TreePredicateFn PredFn(P);
if (!PredFn.isAlwaysTrue())		if (!PredFn.isAlwaysTrue())
P->getOnlyTree()->addPredicateFn(PredFn);		for (auto T : P->getTrees())
		T->addPredicateFn(PredFn);

// If there is a node transformation corresponding to this, keep track of		// If there is a node transformation corresponding to this, keep track of
// it.		// it.
Record *Transform = Frag->getValueAsDef("OperandTransform");		Record *Transform = Frag->getValueAsDef("OperandTransform");
if (!getSDNodeTransform(Transform).second.empty()) // not noop xform?		if (!getSDNodeTransform(Transform).second.empty()) // not noop xform?
P->getOnlyTree()->setTransformFn(Transform);		for (auto T : P->getTrees())
		T->setTransformFn(Transform);
}		}

// Now that we've parsed all of the tree fragments, do a closure on them so		// Now that we've parsed all of the tree fragments, do a closure on them so
// that there are not references to PatFrags left inside of them.		// that there are not references to PatFrags left inside of them.
for (Record *Frag : Fragments) {		for (Record *Frag : Fragments) {
if (OutFrags != Frag->isSubClassOf("OutPatFrag"))		if (OutFrags != Frag->isSubClassOf("OutPatFrag"))
continue;		continue;

▲ Show 20 Lines • Show All 95 Lines • ▼ Show 20 Lines	static bool HandleUse(TreePattern &I, TreePatternNodePtr Pat,
} else {		} else {
assert(Slot->getNumChildren() == 0 && "can't be a use with children!");		assert(Slot->getNumChildren() == 0 && "can't be a use with children!");
SlotRec = Slot->getOperator();		SlotRec = Slot->getOperator();
}		}

// Ensure that the inputs agree if we've already seen this input.		// Ensure that the inputs agree if we've already seen this input.
if (Rec != SlotRec)		if (Rec != SlotRec)
I.error("All $" + Pat->getName() + " inputs must agree with each other");		I.error("All $" + Pat->getName() + " inputs must agree with each other");
		// Ensure that the types can agree as well.
		Slot->UpdateNodeType(0, Pat->getExtType(0), I);
		Pat->UpdateNodeType(0, Slot->getExtType(0), I);
if (Slot->getExtTypes() != Pat->getExtTypes())		if (Slot->getExtTypes() != Pat->getExtTypes())
I.error("All $" + Pat->getName() + " inputs must agree with each other");		I.error("All $" + Pat->getName() + " inputs must agree with each other");
return true;		return true;
}		}

/// FindPatternInputsAndOutputs - Scan the specified TreePatternNode (which is		/// FindPatternInputsAndOutputs - Scan the specified TreePatternNode (which is
/// part of "I", the instruction), computing the set of inputs and outputs of		/// part of "I", the instruction), computing the set of inputs and outputs of
/// the pattern. Report errors if we see anything naughty.		/// the pattern. Report errors if we see anything naughty.
void CodeGenDAGPatterns::FindPatternInputsAndOutputs(		void CodeGenDAGPatterns::FindPatternInputsAndOutputs(
TreePattern &I, TreePatternNodePtr Pat,		TreePattern &I, TreePatternNodePtr Pat,
std::map<std::string, TreePatternNodePtr> &InstInputs,		std::map<std::string, TreePatternNodePtr> &InstInputs,
std::map<std::string, TreePatternNodePtr> &InstResults,		std::map<std::string, TreePatternNodePtr> &InstResults,
std::vector<Record *> &InstImpResults) {		std::vector<Record *> &InstImpResults) {

		// The instruction pattern still has unresolved fragments. For named
		// nodes we must resolve those here. This may not result in multiple
		// alternatives.
		if (!Pat->getName().empty()) {
		TreePattern SrcPattern(I.getRecord(), Pat, true, *this);
		SrcPattern.InlinePatternFragments();
		SrcPattern.InferAllTypes();
		Pat = SrcPattern.getOnlyTree();
		}

if (Pat->isLeaf()) {		if (Pat->isLeaf()) {
bool isUse = HandleUse(I, Pat, InstInputs);		bool isUse = HandleUse(I, Pat, InstInputs);
if (!isUse && Pat->getTransformFn())		if (!isUse && Pat->getTransformFn())
I.error("Cannot specify a transform function for a non-input value!");		I.error("Cannot specify a transform function for a non-input value!");
return;		return;
}		}

if (Pat->getOperator()->getName() == "implicit") {		if (Pat->getOperator()->getName() == "implicit") {
Show All 35 Lines	void CodeGenDAGPatterns::FindPatternInputsAndOutputs(

if (Pat->getTransformFn())		if (Pat->getTransformFn())
I.error("Cannot specify a transform function on a set node!");		I.error("Cannot specify a transform function on a set node!");

// Check the set destinations.		// Check the set destinations.
unsigned NumDests = Pat->getNumChildren()-1;		unsigned NumDests = Pat->getNumChildren()-1;
for (unsigned i = 0; i != NumDests; ++i) {		for (unsigned i = 0; i != NumDests; ++i) {
TreePatternNodePtr Dest = Pat->getChildShared(i);		TreePatternNodePtr Dest = Pat->getChildShared(i);
		// For set destinations we also must resolve fragments here.
		TreePattern DestPattern(I.getRecord(), Dest, false, *this);
		DestPattern.InlinePatternFragments();
		DestPattern.InferAllTypes();
		Dest = DestPattern.getOnlyTree();

if (!Dest->isLeaf())		if (!Dest->isLeaf())
I.error("set destination should be a register!");		I.error("set destination should be a register!");

DefInit *Val = dyn_cast<DefInit>(Dest->getLeafValue());		DefInit *Val = dyn_cast<DefInit>(Dest->getLeafValue());
if (!Val) {		if (!Val) {
I.error("set destination should be a register!");		I.error("set destination should be a register!");
continue;		continue;
}		}
Show All 26 Lines
class InstAnalyzer {		class InstAnalyzer {
const CodeGenDAGPatterns &CDP;		const CodeGenDAGPatterns &CDP;
public:		public:
bool hasSideEffects;		bool hasSideEffects;
bool mayStore;		bool mayStore;
bool mayLoad;		bool mayLoad;
bool isBitcast;		bool isBitcast;
bool isVariadic;		bool isVariadic;
		bool hasChain;

InstAnalyzer(const CodeGenDAGPatterns &cdp)		InstAnalyzer(const CodeGenDAGPatterns &cdp)
: CDP(cdp), hasSideEffects(false), mayStore(false), mayLoad(false),		: CDP(cdp), hasSideEffects(false), mayStore(false), mayLoad(false),
isBitcast(false), isVariadic(false) {}		isBitcast(false), isVariadic(false), hasChain(false) {}

void Analyze(const TreePattern *Pat) {
// Assume only the first tree is the pattern. The others are clobber nodes.
AnalyzeNode(Pat->getTree(0).get());
}

void Analyze(const PatternToMatch &Pat) {		void Analyze(const PatternToMatch &Pat) {
AnalyzeNode(Pat.getSrcPattern());		const TreePatternNode *N = Pat.getSrcPattern();
		AnalyzeNode(N);
		// These properties are detected only on the root node.
		isBitcast = IsNodeBitcast(N);
}		}

private:		private:
bool IsNodeBitcast(const TreePatternNode *N) const {		bool IsNodeBitcast(const TreePatternNode *N) const {
if (hasSideEffects \|\| mayLoad \|\| mayStore \|\| isVariadic)		if (hasSideEffects \|\| mayLoad \|\| mayStore \|\| isVariadic)
return false;		return false;

if (N->getNumChildren() != 2)		if (N->isLeaf())
return false;

const TreePatternNode *N0 = N->getChild(0);
if (!N0->isLeaf() \|\| !isa<DefInit>(N0->getLeafValue()))
return false;

const TreePatternNode *N1 = N->getChild(1);
if (N1->isLeaf())
return false;		return false;
if (N1->getNumChildren() != 1 \|\| !N1->getChild(0)->isLeaf())		if (N->getNumChildren() != 1 \|\| !N->getChild(0)->isLeaf())
return false;		return false;

const SDNodeInfo &OpInfo = CDP.getSDNodeInfo(N1->getOperator());		const SDNodeInfo &OpInfo = CDP.getSDNodeInfo(N->getOperator());
if (OpInfo.getNumResults() != 1 \|\| OpInfo.getNumOperands() != 1)		if (OpInfo.getNumResults() != 1 \|\| OpInfo.getNumOperands() != 1)
return false;		return false;
return OpInfo.getEnumName() == "ISD::BITCAST";		return OpInfo.getEnumName() == "ISD::BITCAST";
}		}

public:		public:
void AnalyzeNode(const TreePatternNode *N) {		void AnalyzeNode(const TreePatternNode *N) {
if (N->isLeaf()) {		if (N->isLeaf()) {
Show All 9 Lines	if (N->isLeaf()) {
}		}
return;		return;
}		}

// Analyze children.		// Analyze children.
for (unsigned i = 0, e = N->getNumChildren(); i != e; ++i)		for (unsigned i = 0, e = N->getNumChildren(); i != e; ++i)
AnalyzeNode(N->getChild(i));		AnalyzeNode(N->getChild(i));

// Ignore set nodes, which are not SDNodes.
if (N->getOperator()->getName() == "set") {
isBitcast = IsNodeBitcast(N);
return;
}

// Notice properties of the node.		// Notice properties of the node.
if (N->NodeHasProperty(SDNPMayStore, CDP)) mayStore = true;		if (N->NodeHasProperty(SDNPMayStore, CDP)) mayStore = true;
if (N->NodeHasProperty(SDNPMayLoad, CDP)) mayLoad = true;		if (N->NodeHasProperty(SDNPMayLoad, CDP)) mayLoad = true;
if (N->NodeHasProperty(SDNPSideEffect, CDP)) hasSideEffects = true;		if (N->NodeHasProperty(SDNPSideEffect, CDP)) hasSideEffects = true;
if (N->NodeHasProperty(SDNPVariadic, CDP)) isVariadic = true;		if (N->NodeHasProperty(SDNPVariadic, CDP)) isVariadic = true;
		if (N->NodeHasProperty(SDNPHasChain, CDP)) hasChain = true;

if (const CodeGenIntrinsic *IntInfo = N->getIntrinsicInfo(CDP)) {		if (const CodeGenIntrinsic *IntInfo = N->getIntrinsicInfo(CDP)) {
// If this is an intrinsic, analyze it.		// If this is an intrinsic, analyze it.
if (IntInfo->ModRef & CodeGenIntrinsic::MR_Ref)		if (IntInfo->ModRef & CodeGenIntrinsic::MR_Ref)
mayLoad = true;// These may load memory.		mayLoad = true;// These may load memory.

if (IntInfo->ModRef & CodeGenIntrinsic::MR_Mod)		if (IntInfo->ModRef & CodeGenIntrinsic::MR_Mod)
mayStore = true;// Intrinsics that can write to memory are 'mayStore'.		mayStore = true;// Intrinsics that can write to memory are 'mayStore'.
▲ Show 20 Lines • Show All 46 Lines • ▼ Show 20 Lines	static bool InferFromPattern(CodeGenInstruction &InstInfo,
}		}

// Transfer inferred flags.		// Transfer inferred flags.
InstInfo.hasSideEffects \|= PatInfo.hasSideEffects;		InstInfo.hasSideEffects \|= PatInfo.hasSideEffects;
InstInfo.mayStore \|= PatInfo.mayStore;		InstInfo.mayStore \|= PatInfo.mayStore;
InstInfo.mayLoad \|= PatInfo.mayLoad;		InstInfo.mayLoad \|= PatInfo.mayLoad;

// These flags are silently added without any verification.		// These flags are silently added without any verification.
		// FIXME: To match historical behavior of TableGen, for now add those flags
		// only when we're inferring from the primary instruction pattern.
		if (PatDef->isSubClassOf("Instruction")) {
InstInfo.isBitcast \|= PatInfo.isBitcast;		InstInfo.isBitcast \|= PatInfo.isBitcast;
		InstInfo.hasChain \|= PatInfo.hasChain;
		InstInfo.hasChain_Inferred = true;
		}

// Don't infer isVariadic. This flag means something different on SDNodes and		// Don't infer isVariadic. This flag means something different on SDNodes and
// instructions. For example, a CALL SDNode is variadic because it has the		// instructions. For example, a CALL SDNode is variadic because it has the
// call arguments as operands, but a CALL instruction is not variadic - it		// call arguments as operands, but a CALL instruction is not variadic - it
// has argument registers as implicit, not explicit uses.		// has argument registers as implicit, not explicit uses.

return Error;		return Error;
}		}
▲ Show 20 Lines • Show All 54 Lines • ▼ Show 20 Lines	static bool checkOperandClass(CGIOperandList::OperandInfo &OI,

// Patterns can also be ComplexPattern instances.		// Patterns can also be ComplexPattern instances.
if (Leaf->isSubClassOf("ComplexPattern"))		if (Leaf->isSubClassOf("ComplexPattern"))
return true;		return true;

return false;		return false;
}		}

const DAGInstruction &CodeGenDAGPatterns::parseInstructionPattern(		void CodeGenDAGPatterns::parseInstructionPattern(
CodeGenInstruction &CGI, ListInit *Pat, DAGInstMap &DAGInsts) {		CodeGenInstruction &CGI, ListInit *Pat, DAGInstMap &DAGInsts) {

assert(!DAGInsts.count(CGI.TheDef) && "Instruction already parsed!");		assert(!DAGInsts.count(CGI.TheDef) && "Instruction already parsed!");

// Parse the instruction.		// Parse the instruction.
auto I = llvm::make_unique<TreePattern>(CGI.TheDef, Pat, true, *this);		TreePattern I(CGI.TheDef, Pat, true, *this);
// Inline pattern fragments into it.
I->InlinePatternFragments();

// Infer as many types as possible. If we cannot infer all of them, we can
// never do anything with this instruction pattern: report it to the user.
if (!I->InferAllTypes())
I->error("Could not infer all types in pattern!");

// InstInputs - Keep track of all of the inputs of the instruction, along		// InstInputs - Keep track of all of the inputs of the instruction, along
// with the record they are declared as.		// with the record they are declared as.
std::map<std::string, TreePatternNodePtr> InstInputs;		std::map<std::string, TreePatternNodePtr> InstInputs;

// InstResults - Keep track of all the virtual registers that are 'set'		// InstResults - Keep track of all the virtual registers that are 'set'
// in the instruction, including what reg class they are.		// in the instruction, including what reg class they are.
std::map<std::string, TreePatternNodePtr> InstResults;		std::map<std::string, TreePatternNodePtr> InstResults;

std::vector<Record*> InstImpResults;		std::vector<Record*> InstImpResults;

// Verify that the top-level forms in the instruction are of void type, and		// Verify that the top-level forms in the instruction are of void type, and
// fill in the InstResults map.		// fill in the InstResults map.
SmallString<32> TypesString;		SmallString<32> TypesString;
for (unsigned j = 0, e = I->getNumTrees(); j != e; ++j) {		for (unsigned j = 0, e = I.getNumTrees(); j != e; ++j) {
TypesString.clear();		TypesString.clear();
TreePatternNodePtr Pat = I->getTree(j);		TreePatternNodePtr Pat = I.getTree(j);
if (Pat->getNumTypes() != 0) {		if (Pat->getNumTypes() != 0) {
raw_svector_ostream OS(TypesString);		raw_svector_ostream OS(TypesString);
for (unsigned k = 0, ke = Pat->getNumTypes(); k != ke; ++k) {		for (unsigned k = 0, ke = Pat->getNumTypes(); k != ke; ++k) {
if (k > 0)		if (k > 0)
OS << ", ";		OS << ", ";
Pat->getExtType(k).writeToStream(OS);		Pat->getExtType(k).writeToStream(OS);
}		}
I->error("Top-level forms in instruction pattern should have"		I.error("Top-level forms in instruction pattern should have"
" void types, has types " +		" void types, has types " +
OS.str());		OS.str());
}		}

// Find inputs and outputs, and verify the structure of the uses/defs.		// Find inputs and outputs, and verify the structure of the uses/defs.
FindPatternInputsAndOutputs(*I, Pat, InstInputs, InstResults,		FindPatternInputsAndOutputs(I, Pat, InstInputs, InstResults,
InstImpResults);		InstImpResults);
}		}

// Now that we have inputs and outputs of the pattern, inspect the operands		// Now that we have inputs and outputs of the pattern, inspect the operands
// list for the instruction. This determines the order that operands are		// list for the instruction. This determines the order that operands are
// added to the machine instruction the node corresponds to.		// added to the machine instruction the node corresponds to.
unsigned NumResults = InstResults.size();		unsigned NumResults = InstResults.size();

// Parse the operands list from the (ops) list, validating it.		// Parse the operands list from the (ops) list, validating it.
assert(I->getArgList().empty() && "Args list should still be empty here!");		assert(I.getArgList().empty() && "Args list should still be empty here!");

// Check that all of the results occur first in the list.		// Check that all of the results occur first in the list.
std::vector<Record*> Results;		std::vector<Record*> Results;
SmallVector<TreePatternNodePtr, 2> ResNodes;		SmallVector<TreePatternNodePtr, 2> ResNodes;
for (unsigned i = 0; i != NumResults; ++i) {		for (unsigned i = 0; i != NumResults; ++i) {
if (i == CGI.Operands.size())		if (i == CGI.Operands.size())
I->error("'" + InstResults.begin()->first +		I.error("'" + InstResults.begin()->first +
"' set but does not appear in operand list!");		"' set but does not appear in operand list!");
const std::string &OpName = CGI.Operands[i].Name;		const std::string &OpName = CGI.Operands[i].Name;

// Check that it exists in InstResults.		// Check that it exists in InstResults.
TreePatternNodePtr RNode = InstResults[OpName];		TreePatternNodePtr RNode = InstResults[OpName];
if (!RNode)		if (!RNode)
I->error("Operand $" + OpName + " does not exist in operand list!");		I.error("Operand $" + OpName + " does not exist in operand list!");


Record *R = cast<DefInit>(RNode->getLeafValue())->getDef();		Record *R = cast<DefInit>(RNode->getLeafValue())->getDef();
ResNodes.push_back(std::move(RNode));		ResNodes.push_back(std::move(RNode));
if (!R)		if (!R)
I->error("Operand $" + OpName + " should be a set destination: all "		I.error("Operand $" + OpName + " should be a set destination: all "
"outputs must occur before inputs in operand list!");		"outputs must occur before inputs in operand list!");

if (!checkOperandClass(CGI.Operands[i], R))		if (!checkOperandClass(CGI.Operands[i], R))
I->error("Operand $" + OpName + " class mismatch!");		I.error("Operand $" + OpName + " class mismatch!");

// Remember the return type.		// Remember the return type.
Results.push_back(CGI.Operands[i].Rec);		Results.push_back(CGI.Operands[i].Rec);

// Okay, this one checks out.		// Okay, this one checks out.
InstResults.erase(OpName);		InstResults.erase(OpName);
}		}

// Loop over the inputs next. Make a copy of InstInputs so we can destroy		// Loop over the inputs next. Make a copy of InstInputs so we can destroy
// the copy while we're checking the inputs.		// the copy while we're checking the inputs.
std::map<std::string, TreePatternNodePtr> InstInputsCheck(InstInputs);		std::map<std::string, TreePatternNodePtr> InstInputsCheck(InstInputs);

std::vector<TreePatternNodePtr> ResultNodeOperands;		std::vector<TreePatternNodePtr> ResultNodeOperands;
std::vector<Record*> Operands;		std::vector<Record*> Operands;
for (unsigned i = NumResults, e = CGI.Operands.size(); i != e; ++i) {		for (unsigned i = NumResults, e = CGI.Operands.size(); i != e; ++i) {
CGIOperandList::OperandInfo &Op = CGI.Operands[i];		CGIOperandList::OperandInfo &Op = CGI.Operands[i];
const std::string &OpName = Op.Name;		const std::string &OpName = Op.Name;
if (OpName.empty())		if (OpName.empty())
I->error("Operand #" + Twine(i) + " in operands list has no name!");		I.error("Operand #" + Twine(i) + " in operands list has no name!");

if (!InstInputsCheck.count(OpName)) {		if (!InstInputsCheck.count(OpName)) {
// If this is an operand with a DefaultOps set filled in, we can ignore		// If this is an operand with a DefaultOps set filled in, we can ignore
// this. When we codegen it, we will do so as always executed.		// this. When we codegen it, we will do so as always executed.
if (Op.Rec->isSubClassOf("OperandWithDefaultOps")) {		if (Op.Rec->isSubClassOf("OperandWithDefaultOps")) {
// Does it have a non-empty DefaultOps field? If so, ignore this		// Does it have a non-empty DefaultOps field? If so, ignore this
// operand.		// operand.
if (!getDefaultOperand(Op.Rec).DefaultOps.empty())		if (!getDefaultOperand(Op.Rec).DefaultOps.empty())
continue;		continue;
}		}
I->error("Operand $" + OpName +		I.error("Operand $" + OpName +
" does not appear in the instruction pattern");		" does not appear in the instruction pattern");
}		}
TreePatternNodePtr InVal = InstInputsCheck[OpName];		TreePatternNodePtr InVal = InstInputsCheck[OpName];
InstInputsCheck.erase(OpName); // It occurred, remove from map.		InstInputsCheck.erase(OpName); // It occurred, remove from map.

if (InVal->isLeaf() && isa<DefInit>(InVal->getLeafValue())) {		if (InVal->isLeaf() && isa<DefInit>(InVal->getLeafValue())) {
Record InRec = static_cast<DefInit>(InVal->getLeafValue())->getDef();		Record InRec = static_cast<DefInit>(InVal->getLeafValue())->getDef();
if (!checkOperandClass(Op, InRec))		if (!checkOperandClass(Op, InRec))
I->error("Operand $" + OpName + "'s register class disagrees"		I.error("Operand $" + OpName + "'s register class disagrees"
" between the operand and pattern");		" between the operand and pattern");
}		}
Operands.push_back(Op.Rec);		Operands.push_back(Op.Rec);

// Construct the result for the dest-pattern operand list.		// Construct the result for the dest-pattern operand list.
TreePatternNodePtr OpNode = InVal->clone();		TreePatternNodePtr OpNode = InVal->clone();

// No predicate is useful on the result.		// No predicate is useful on the result.
OpNode->clearPredicateFns();		OpNode->clearPredicateFns();

// Promote the xform function to be an explicit node if set.		// Promote the xform function to be an explicit node if set.
if (Record *Xform = OpNode->getTransformFn()) {		if (Record *Xform = OpNode->getTransformFn()) {
OpNode->setTransformFn(nullptr);		OpNode->setTransformFn(nullptr);
std::vector<TreePatternNodePtr> Children;		std::vector<TreePatternNodePtr> Children;
Children.push_back(OpNode);		Children.push_back(OpNode);
OpNode = std::make_shared<TreePatternNode>(Xform, Children,		OpNode = std::make_shared<TreePatternNode>(Xform, Children,
OpNode->getNumTypes());		OpNode->getNumTypes());
}		}

ResultNodeOperands.push_back(std::move(OpNode));		ResultNodeOperands.push_back(std::move(OpNode));
}		}

if (!InstInputsCheck.empty())		if (!InstInputsCheck.empty())
I->error("Input operand $" + InstInputsCheck.begin()->first +		I.error("Input operand $" + InstInputsCheck.begin()->first +
" occurs in pattern but not in operands list!");		" occurs in pattern but not in operands list!");

TreePatternNodePtr ResultPattern = std::make_shared<TreePatternNode>(		TreePatternNodePtr ResultPattern = std::make_shared<TreePatternNode>(
I->getRecord(), ResultNodeOperands,		I.getRecord(), ResultNodeOperands,
GetNumNodeResults(I->getRecord(), *this));		GetNumNodeResults(I.getRecord(), *this));
// Copy fully inferred output node types to instruction result pattern.		// Copy fully inferred output node types to instruction result pattern.
for (unsigned i = 0; i != NumResults; ++i) {		for (unsigned i = 0; i != NumResults; ++i) {
assert(ResNodes[i]->getNumTypes() == 1 && "FIXME: Unhandled");		assert(ResNodes[i]->getNumTypes() == 1 && "FIXME: Unhandled");
ResultPattern->setType(i, ResNodes[i]->getExtType(0));		ResultPattern->setType(i, ResNodes[i]->getExtType(0));
}		}

		// FIXME: Assume only the first tree is the pattern. The others are clobber
		// nodes.
		TreePatternNodePtr Pattern = I.getTree(0);
		TreePatternNodePtr SrcPattern;
		if (Pattern->getOperator()->getName() == "set") {
		SrcPattern = Pattern->getChild(Pattern->getNumChildren()-1)->clone();
		} else{
		// Not a set (store or something?)
		SrcPattern = Pattern;
		}

// Create and insert the instruction.		// Create and insert the instruction.
// FIXME: InstImpResults should not be part of DAGInstruction.		// FIXME: InstImpResults should not be part of DAGInstruction.
Record *R = I->getRecord();		Record *R = I.getRecord();
DAGInstruction &TheInst =
DAGInsts.emplace(std::piecewise_construct, std::forward_as_tuple(R),		DAGInsts.emplace(std::piecewise_construct, std::forward_as_tuple(R),
std::forward_as_tuple(std::move(I), Results, Operands,		std::forward_as_tuple(Results, Operands, InstImpResults,
InstImpResults)).first->second;		SrcPattern, ResultPattern));

// Use a temporary tree pattern to infer all types and make sure that the
// constructed result is correct. This depends on the instruction already
// being inserted into the DAGInsts map.
TreePattern Temp(TheInst.getPattern()->getRecord(), ResultPattern, false,
*this);
Temp.InferAllTypes(&TheInst.getPattern()->getNamedNodesMap());

TheInst.setResultPattern(Temp.getOnlyTree());		LLVM_DEBUG(I.dump());

return TheInst;
}		}

/// ParseInstructions - Parse all of the instructions, inlining and resolving		/// ParseInstructions - Parse all of the instructions, inlining and resolving
/// any fragments involved. This populates the Instructions list with fully		/// any fragments involved. This populates the Instructions list with fully
/// resolved instructions.		/// resolved instructions.
void CodeGenDAGPatterns::ParseInstructions() {		void CodeGenDAGPatterns::ParseInstructions() {
std::vector<Record*> Instrs = Records.getAllDerivedDefinitions("Instruction");		std::vector<Record*> Instrs = Records.getAllDerivedDefinitions("Instruction");

Show All 23 Lines	if (!LI \|\| LI->empty() \|\| hasNullFragReference(LI)) {
for (unsigned j = InstInfo.Operands.NumDefs,		for (unsigned j = InstInfo.Operands.NumDefs,
e = InstInfo.Operands.size(); j < e; ++j)		e = InstInfo.Operands.size(); j < e; ++j)
Operands.push_back(InstInfo.Operands[j].Rec);		Operands.push_back(InstInfo.Operands[j].Rec);
}		}

// Create and insert the instruction.		// Create and insert the instruction.
std::vector<Record*> ImpResults;		std::vector<Record*> ImpResults;
Instructions.insert(std::make_pair(Instr,		Instructions.insert(std::make_pair(Instr,
DAGInstruction(nullptr, Results, Operands, ImpResults)));		DAGInstruction(Results, Operands, ImpResults)));
continue; // no pattern.		continue; // no pattern.
}		}

CodeGenInstruction &CGI = Target.getInstruction(Instr);		CodeGenInstruction &CGI = Target.getInstruction(Instr);
const DAGInstruction &DI = parseInstructionPattern(CGI, LI, Instructions);		parseInstructionPattern(CGI, LI, Instructions);

(void)DI;
LLVM_DEBUG(DI.getPattern()->dump());
}		}

// If we can, convert the instructions to be patterns that are matched!		// If we can, convert the instructions to be patterns that are matched!
for (auto &Entry : Instructions) {		for (auto &Entry : Instructions) {
		Record *Instr = Entry.first;
DAGInstruction &TheInst = Entry.second;		DAGInstruction &TheInst = Entry.second;
TreePattern *I = TheInst.getPattern();		TreePatternNodePtr SrcPattern = TheInst.getSrcPattern();
if (!I) continue; // No pattern.		TreePatternNodePtr ResultPattern = TheInst.getResultPattern();

if (PatternRewriter)		if (SrcPattern && ResultPattern) {
PatternRewriter(I);		TreePattern Pattern(Instr, SrcPattern, true, *this);
// FIXME: Assume only the first tree is the pattern. The others are clobber		TreePattern Result(Instr, ResultPattern, false, *this);
// nodes.		ParseOnePattern(Instr, Pattern, Result, TheInst.getImpResults());
TreePatternNodePtr Pattern = I->getTree(0);
TreePatternNodePtr SrcPattern;
if (Pattern->getOperator()->getName() == "set") {
SrcPattern = Pattern->getChild(Pattern->getNumChildren()-1)->clone();
} else{
// Not a set (store or something?)
SrcPattern = Pattern;
}		}

Record *Instr = Entry.first;
ListInit *Preds = Instr->getValueAsListInit("Predicates");
int Complexity = Instr->getValueAsInt("AddedComplexity");
AddPatternToMatch(
I,
PatternToMatch(Instr, makePredList(Preds), SrcPattern,
TheInst.getResultPattern(), TheInst.getImpResults(),
Complexity, Instr->getID()));
}		}
}		}

typedef std::pair<TreePatternNode *, unsigned> NameRecord;		typedef std::pair<TreePatternNode *, unsigned> NameRecord;

static void FindNames(TreePatternNode *P,		static void FindNames(TreePatternNode *P,
std::map<std::string, NameRecord> &Names,		std::map<std::string, NameRecord> &Names,
TreePattern *PatternTop) {		TreePattern *PatternTop) {
▲ Show 20 Lines • Show All 69 Lines • ▼ Show 20 Lines	void CodeGenDAGPatterns::AddPatternToMatch(TreePattern *Pattern,

PatternsToMatch.push_back(PTM);		PatternsToMatch.push_back(PTM);
}		}

void CodeGenDAGPatterns::InferInstructionFlags() {		void CodeGenDAGPatterns::InferInstructionFlags() {
ArrayRef<const CodeGenInstruction*> Instructions =		ArrayRef<const CodeGenInstruction*> Instructions =
Target.getInstructionsByEnumValue();		Target.getInstructionsByEnumValue();

// First try to infer flags from the primary instruction pattern, if any.
SmallVector<CodeGenInstruction*, 8> Revisit;
unsigned Errors = 0;		unsigned Errors = 0;
for (unsigned i = 0, e = Instructions.size(); i != e; ++i) {
CodeGenInstruction &InstInfo =
const_cast<CodeGenInstruction &>(*Instructions[i]);

// Get the primary instruction pattern.
const TreePattern *Pattern = getInstruction(InstInfo.TheDef).getPattern();
if (!Pattern) {
if (InstInfo.hasUndefFlags())
Revisit.push_back(&InstInfo);
continue;
}
InstAnalyzer PatInfo(*this);
PatInfo.Analyze(Pattern);
Errors += InferFromPattern(InstInfo, PatInfo, InstInfo.TheDef);
}

// Second, look for single-instruction patterns defined outside the		// Try to infer flags from all patterns in PatternToMatch. These include
// instruction.		// both the primary instruction patterns (which always come first) and
		// patterns defined outside the instruction.
for (const PatternToMatch &PTM : ptms()) {		for (const PatternToMatch &PTM : ptms()) {
// We can only infer from single-instruction patterns, otherwise we won't		// We can only infer from single-instruction patterns, otherwise we won't
// know which instruction should get the flags.		// know which instruction should get the flags.
SmallVector<Record*, 8> PatInstrs;		SmallVector<Record*, 8> PatInstrs;
getInstructionsInTree(PTM.getDstPattern(), PatInstrs);		getInstructionsInTree(PTM.getDstPattern(), PatInstrs);
if (PatInstrs.size() != 1)		if (PatInstrs.size() != 1)
continue;		continue;

// Get the single instruction.		// Get the single instruction.
CodeGenInstruction &InstInfo = Target.getInstruction(PatInstrs.front());		CodeGenInstruction &InstInfo = Target.getInstruction(PatInstrs.front());

// Only infer properties from the first pattern. We'll verify the others.		// Only infer properties from the first pattern. We'll verify the others.
if (InstInfo.InferredFrom)		if (InstInfo.InferredFrom)
continue;		continue;

InstAnalyzer PatInfo(*this);		InstAnalyzer PatInfo(*this);
PatInfo.Analyze(PTM);		PatInfo.Analyze(PTM);
Errors += InferFromPattern(InstInfo, PatInfo, PTM.getSrcRecord());		Errors += InferFromPattern(InstInfo, PatInfo, PTM.getSrcRecord());
}		}

if (Errors)		if (Errors)
PrintFatalError("pattern conflicts");		PrintFatalError("pattern conflicts");

// Revisit instructions with undefined flags and no pattern.		// If requested by the target, guess any undefined properties.
if (Target.guessInstructionProperties()) {		if (Target.guessInstructionProperties()) {
for (CodeGenInstruction *InstInfo : Revisit) {		for (unsigned i = 0, e = Instructions.size(); i != e; ++i) {
		CodeGenInstruction *InstInfo =
		const_cast<CodeGenInstruction *>(Instructions[i]);
if (InstInfo->InferredFrom)		if (InstInfo->InferredFrom)
continue;		continue;
// The mayLoad and mayStore flags default to false.		// The mayLoad and mayStore flags default to false.
// Conservatively assume hasSideEffects if it wasn't explicit.		// Conservatively assume hasSideEffects if it wasn't explicit.
if (InstInfo->hasSideEffects_Unset)		if (InstInfo->hasSideEffects_Unset)
InstInfo->hasSideEffects = true;		InstInfo->hasSideEffects = true;
}		}
return;		return;
}		}

// Complain about any flags that are still undefined.		// Complain about any flags that are still undefined.
for (CodeGenInstruction *InstInfo : Revisit) {		for (unsigned i = 0, e = Instructions.size(); i != e; ++i) {
		CodeGenInstruction *InstInfo =
		const_cast<CodeGenInstruction *>(Instructions[i]);
if (InstInfo->InferredFrom)		if (InstInfo->InferredFrom)
continue;		continue;
if (InstInfo->hasSideEffects_Unset)		if (InstInfo->hasSideEffects_Unset)
PrintError(InstInfo->TheDef->getLoc(),		PrintError(InstInfo->TheDef->getLoc(),
"Can't infer hasSideEffects from patterns");		"Can't infer hasSideEffects from patterns");
if (InstInfo->mayStore_Unset)		if (InstInfo->mayStore_Unset)
PrintError(InstInfo->TheDef->getLoc(),		PrintError(InstInfo->TheDef->getLoc(),
"Can't infer mayStore from patterns");		"Can't infer mayStore from patterns");
▲ Show 20 Lines • Show All 95 Lines • ▼ Show 20 Lines	for (unsigned i = 0, e = N->getNumTypes(); i != e; ++i) {
// Otherwise, force its type to an arbitrary choice.		// Otherwise, force its type to an arbitrary choice.
if (TI.forceArbitrary(N->getExtType(i)))		if (TI.forceArbitrary(N->getExtType(i)))
return true;		return true;
}		}

return false;		return false;
}		}

void CodeGenDAGPatterns::ParsePatterns() {		void CodeGenDAGPatterns::ParseOnePattern(Record *TheDef,
std::vector<Record*> Patterns = Records.getAllDerivedDefinitions("Pattern");		TreePattern &Pattern, TreePattern &Result,
		const std::vector<Record *> &InstImpResults) {
for (Record *CurPattern : Patterns) {
DagInit *Tree = CurPattern->getValueAsDag("PatternToMatch");

// If the pattern references the null_frag, there's nothing to do.
if (hasNullFragReference(Tree))
continue;

TreePattern Pattern(CurPattern, Tree, true, *this);		// Inline pattern fragments and expand multiple alternatives.

// Inline pattern fragments into it.
Pattern.InlinePatternFragments();		Pattern.InlinePatternFragments();

ListInit *LI = CurPattern->getValueAsListInit("ResultInstrs");
if (LI->empty()) continue; // no pattern.

// Parse the instruction.
TreePattern Result(CurPattern, LI, false, *this);

// Inline pattern fragments into it.
Result.InlinePatternFragments();		Result.InlinePatternFragments();

if (Result.getNumTrees() != 1)		if (Result.getNumTrees() != 1)
Result.error("Cannot handle instructions producing instructions "		Result.error("Cannot use multi-alternative fragments in result pattern!");
"with temporaries yet!");

		// Infer types.
bool IterateInference;		bool IterateInference;
bool InferredAllPatternTypes, InferredAllResultTypes;		bool InferredAllPatternTypes, InferredAllResultTypes;
do {		do {
// Infer as many types as possible. If we cannot infer all of them, we		// Infer as many types as possible. If we cannot infer all of them, we
// can never do anything with this pattern: report it to the user.		// can never do anything with this pattern: report it to the user.
InferredAllPatternTypes =		InferredAllPatternTypes =
Pattern.InferAllTypes(&Pattern.getNamedNodesMap());		Pattern.InferAllTypes(&Pattern.getNamedNodesMap());

// Infer as many types as possible. If we cannot infer all of them, we		// Infer as many types as possible. If we cannot infer all of them, we
// can never do anything with this pattern: report it to the user.		// can never do anything with this pattern: report it to the user.
InferredAllResultTypes =		InferredAllResultTypes =
Result.InferAllTypes(&Pattern.getNamedNodesMap());		Result.InferAllTypes(&Pattern.getNamedNodesMap());

IterateInference = false;		IterateInference = false;

// Apply the type of the result to the source pattern. This helps us		// Apply the type of the result to the source pattern. This helps us
// resolve cases where the input type is known to be a pointer type (which		// resolve cases where the input type is known to be a pointer type (which
// is considered resolved), but the result knows it needs to be 32- or		// is considered resolved), but the result knows it needs to be 32- or
// 64-bits. Infer the other way for good measure.		// 64-bits. Infer the other way for good measure.
for (unsigned i = 0, e = std::min(Result.getTree(0)->getNumTypes(),		for (auto T : Pattern.getTrees())
Pattern.getTree(0)->getNumTypes());		for (unsigned i = 0, e = std::min(Result.getOnlyTree()->getNumTypes(),
		T->getNumTypes());
i != e; ++i) {		i != e; ++i) {
IterateInference = Pattern.getTree(0)->UpdateNodeType(		IterateInference \|= T->UpdateNodeType(
i, Result.getTree(0)->getExtType(i), Result);		i, Result.getOnlyTree()->getExtType(i), Result);
IterateInference \|= Result.getTree(0)->UpdateNodeType(		IterateInference \|= Result.getOnlyTree()->UpdateNodeType(
i, Pattern.getTree(0)->getExtType(i), Result);		i, T->getExtType(i), Result);
}		}

// If our iteration has converged and the input pattern's types are fully		// If our iteration has converged and the input pattern's types are fully
// resolved but the result pattern is not fully resolved, we may have a		// resolved but the result pattern is not fully resolved, we may have a
// situation where we have two instructions in the result pattern and		// situation where we have two instructions in the result pattern and
// the instructions require a common register class, but don't care about		// the instructions require a common register class, but don't care about
// what actual MVT is used. This is actually a bug in our modelling:		// what actual MVT is used. This is actually a bug in our modelling:
// output patterns should have register classes, not MVTs.		// output patterns should have register classes, not MVTs.
//		//
// In any case, to handle this, we just go through and disambiguate some		// In any case, to handle this, we just go through and disambiguate some
// arbitrary types to the result pattern's nodes.		// arbitrary types to the result pattern's nodes.
if (!IterateInference && InferredAllPatternTypes &&		if (!IterateInference && InferredAllPatternTypes &&
!InferredAllResultTypes)		!InferredAllResultTypes)
IterateInference =		IterateInference =
ForceArbitraryInstResultType(Result.getTree(0).get(), Result);		ForceArbitraryInstResultType(Result.getTree(0).get(), Result);
} while (IterateInference);		} while (IterateInference);

// Verify that we inferred enough types that we can do something with the		// Verify that we inferred enough types that we can do something with the
// pattern and result. If these fire the user has to add type casts.		// pattern and result. If these fire the user has to add type casts.
if (!InferredAllPatternTypes)		if (!InferredAllPatternTypes)
Pattern.error("Could not infer all types in pattern!");		Pattern.error("Could not infer all types in pattern!");
if (!InferredAllResultTypes) {		if (!InferredAllResultTypes) {
Pattern.dump();		Pattern.dump();
Result.error("Could not infer all types in pattern result!");		Result.error("Could not infer all types in pattern result!");
}		}

// Validate that the input pattern is correct.
std::map<std::string, TreePatternNodePtr> InstInputs;
std::map<std::string, TreePatternNodePtr> InstResults;
std::vector<Record*> InstImpResults;
for (unsigned j = 0, ee = Pattern.getNumTrees(); j != ee; ++j)
FindPatternInputsAndOutputs(Pattern, Pattern.getTree(j), InstInputs,
InstResults, InstImpResults);

// Promote the xform function to be an explicit node if set.		// Promote the xform function to be an explicit node if set.
const TreePatternNodePtr &DstPattern = Result.getOnlyTree();		const TreePatternNodePtr &DstPattern = Result.getOnlyTree();
std::vector<TreePatternNodePtr> ResultNodeOperands;		std::vector<TreePatternNodePtr> ResultNodeOperands;
for (unsigned ii = 0, ee = DstPattern->getNumChildren(); ii != ee; ++ii) {		for (unsigned ii = 0, ee = DstPattern->getNumChildren(); ii != ee; ++ii) {
TreePatternNodePtr OpNode = DstPattern->getChildShared(ii);		TreePatternNodePtr OpNode = DstPattern->getChildShared(ii);
if (Record *Xform = OpNode->getTransformFn()) {		if (Record *Xform = OpNode->getTransformFn()) {
OpNode->setTransformFn(nullptr);		OpNode->setTransformFn(nullptr);
std::vector<TreePatternNodePtr> Children;		std::vector<TreePatternNodePtr> Children;
Children.push_back(OpNode);		Children.push_back(OpNode);
OpNode = std::make_shared<TreePatternNode>(Xform, Children,		OpNode = std::make_shared<TreePatternNode>(Xform, Children,
OpNode->getNumTypes());		OpNode->getNumTypes());
}		}
ResultNodeOperands.push_back(OpNode);		ResultNodeOperands.push_back(OpNode);
}		}

TreePatternNodePtr DstShared =		TreePatternNodePtr DstShared =
DstPattern->isLeaf()		DstPattern->isLeaf()
? DstPattern		? DstPattern
: std::make_shared<TreePatternNode>(DstPattern->getOperator(),		: std::make_shared<TreePatternNode>(DstPattern->getOperator(),
ResultNodeOperands,		ResultNodeOperands,
DstPattern->getNumTypes());		DstPattern->getNumTypes());

for (unsigned i = 0, e = Result.getOnlyTree()->getNumTypes(); i != e; ++i)		for (unsigned i = 0, e = Result.getOnlyTree()->getNumTypes(); i != e; ++i)
DstShared->setType(i, Result.getOnlyTree()->getExtType(i));		DstShared->setType(i, Result.getOnlyTree()->getExtType(i));

TreePattern Temp(Result.getRecord(), DstShared, false, *this);		TreePattern Temp(Result.getRecord(), DstShared, false, *this);
Temp.InferAllTypes();		Temp.InferAllTypes();

		ListInit *Preds = TheDef->getValueAsListInit("Predicates");
		int Complexity = TheDef->getValueAsInt("AddedComplexity");

		if (PatternRewriter)
		PatternRewriter(&Pattern);

// A pattern may end up with an "impossible" type, i.e. a situation		// A pattern may end up with an "impossible" type, i.e. a situation
// where all types have been eliminated for some node in this pattern.		// where all types have been eliminated for some node in this pattern.
// This could occur for intrinsics that only make sense for a specific		// This could occur for intrinsics that only make sense for a specific
// value type, and use a specific register class. If, for some mode,		// value type, and use a specific register class. If, for some mode,
// that register class does not accept that type, the type inference		// that register class does not accept that type, the type inference
// will lead to a contradiction, which is not an error however, but		// will lead to a contradiction, which is not an error however, but
// a sign that this pattern will simply never match.		// a sign that this pattern will simply never match.
if (Pattern.getTree(0)->hasPossibleType() &&		if (Temp.getOnlyTree()->hasPossibleType())
Temp.getOnlyTree()->hasPossibleType()) {		for (auto T : Pattern.getTrees())
ListInit *Preds = CurPattern->getValueAsListInit("Predicates");		if (T->hasPossibleType())
int Complexity = CurPattern->getValueAsInt("AddedComplexity");
if (PatternRewriter)
PatternRewriter(&Pattern);
AddPatternToMatch(&Pattern,		AddPatternToMatch(&Pattern,
PatternToMatch(CurPattern, makePredList(Preds),		PatternToMatch(TheDef, makePredList(Preds),
Pattern.getTree(0), Temp.getOnlyTree(),		T, Temp.getOnlyTree(),
std::move(InstImpResults), Complexity,		InstImpResults, Complexity,
CurPattern->getID()));		TheDef->getID()));
}		}

		void CodeGenDAGPatterns::ParsePatterns() {
		std::vector<Record*> Patterns = Records.getAllDerivedDefinitions("Pattern");

		for (Record *CurPattern : Patterns) {
		DagInit *Tree = CurPattern->getValueAsDag("PatternToMatch");

		// If the pattern references the null_frag, there's nothing to do.
		if (hasNullFragReference(Tree))
		continue;

		TreePattern Pattern(CurPattern, Tree, true, *this);

		ListInit *LI = CurPattern->getValueAsListInit("ResultInstrs");
		if (LI->empty()) continue; // no pattern.

		// Parse the instruction.
		TreePattern Result(CurPattern, LI, false, *this);

		if (Result.getNumTrees() != 1)
		Result.error("Cannot handle instructions producing instructions "
		"with temporaries yet!");

		// Validate that the input pattern is correct.
		std::map<std::string, TreePatternNodePtr> InstInputs;
		std::map<std::string, TreePatternNodePtr> InstResults;
		std::vector<Record*> InstImpResults;
		for (unsigned j = 0, ee = Pattern.getNumTrees(); j != ee; ++j)
		FindPatternInputsAndOutputs(Pattern, Pattern.getTree(j), InstInputs,
		InstResults, InstImpResults);

		ParseOnePattern(CurPattern, Pattern, Result, InstImpResults);
}		}
}		}

static void collectModes(std::set<unsigned> &Modes, const TreePatternNode *N) {		static void collectModes(std::set<unsigned> &Modes, const TreePatternNode *N) {
for (const TypeSetByHwMode &VTS : N->getExtTypes())		for (const TypeSetByHwMode &VTS : N->getExtTypes())
for (const auto &I : VTS)		for (const auto &I : VTS)
Modes.insert(I.first);		Modes.insert(I.first);

▲ Show 20 Lines • Show All 411 Lines • Show Last 20 Lines