in llvm/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp [2732:3641]
void SelectionDAGISel::SelectCodeCommon(SDNode *NodeToMatch,
const unsigned char *MatcherTable,
unsigned TableSize) {
// FIXME: Should these even be selected? Handle these cases in the caller?
switch (NodeToMatch->getOpcode()) {
default:
break;
case ISD::EntryToken: // These nodes remain the same.
case ISD::BasicBlock:
case ISD::Register:
case ISD::RegisterMask:
case ISD::HANDLENODE:
case ISD::MDNODE_SDNODE:
case ISD::TargetConstant:
case ISD::TargetConstantFP:
case ISD::TargetConstantPool:
case ISD::TargetFrameIndex:
case ISD::TargetExternalSymbol:
case ISD::MCSymbol:
case ISD::TargetBlockAddress:
case ISD::TargetJumpTable:
case ISD::TargetGlobalTLSAddress:
case ISD::TargetGlobalAddress:
case ISD::TokenFactor:
case ISD::CopyFromReg:
case ISD::CopyToReg:
case ISD::EH_LABEL:
case ISD::ANNOTATION_LABEL:
case ISD::LIFETIME_START:
case ISD::LIFETIME_END:
case ISD::PSEUDO_PROBE:
NodeToMatch->setNodeId(-1); // Mark selected.
return;
case ISD::AssertSext:
case ISD::AssertZext:
case ISD::AssertAlign:
ReplaceUses(SDValue(NodeToMatch, 0), NodeToMatch->getOperand(0));
CurDAG->RemoveDeadNode(NodeToMatch);
return;
case ISD::INLINEASM:
case ISD::INLINEASM_BR:
Select_INLINEASM(NodeToMatch);
return;
case ISD::READ_REGISTER:
Select_READ_REGISTER(NodeToMatch);
return;
case ISD::WRITE_REGISTER:
Select_WRITE_REGISTER(NodeToMatch);
return;
case ISD::UNDEF:
Select_UNDEF(NodeToMatch);
return;
case ISD::FREEZE:
Select_FREEZE(NodeToMatch);
return;
case ISD::ARITH_FENCE:
Select_ARITH_FENCE(NodeToMatch);
return;
}
assert(!NodeToMatch->isMachineOpcode() && "Node already selected!");
// Set up the node stack with NodeToMatch as the only node on the stack.
SmallVector<SDValue, 8> NodeStack;
SDValue N = SDValue(NodeToMatch, 0);
NodeStack.push_back(N);
// MatchScopes - Scopes used when matching, if a match failure happens, this
// indicates where to continue checking.
SmallVector<MatchScope, 8> MatchScopes;
// RecordedNodes - This is the set of nodes that have been recorded by the
// state machine. The second value is the parent of the node, or null if the
// root is recorded.
SmallVector<std::pair<SDValue, SDNode*>, 8> RecordedNodes;
// MatchedMemRefs - This is the set of MemRef's we've seen in the input
// pattern.
SmallVector<MachineMemOperand*, 2> MatchedMemRefs;
// These are the current input chain and glue for use when generating nodes.
// Various Emit operations change these. For example, emitting a copytoreg
// uses and updates these.
SDValue InputChain, InputGlue;
// ChainNodesMatched - If a pattern matches nodes that have input/output
// chains, the OPC_EmitMergeInputChains operation is emitted which indicates
// which ones they are. The result is captured into this list so that we can
// update the chain results when the pattern is complete.
SmallVector<SDNode*, 3> ChainNodesMatched;
LLVM_DEBUG(dbgs() << "ISEL: Starting pattern match\n");
// Determine where to start the interpreter. Normally we start at opcode #0,
// but if the state machine starts with an OPC_SwitchOpcode, then we
// accelerate the first lookup (which is guaranteed to be hot) with the
// OpcodeOffset table.
unsigned MatcherIndex = 0;
if (!OpcodeOffset.empty()) {
// Already computed the OpcodeOffset table, just index into it.
if (N.getOpcode() < OpcodeOffset.size())
MatcherIndex = OpcodeOffset[N.getOpcode()];
LLVM_DEBUG(dbgs() << " Initial Opcode index to " << MatcherIndex << "\n");
} else if (MatcherTable[0] == OPC_SwitchOpcode) {
// Otherwise, the table isn't computed, but the state machine does start
// with an OPC_SwitchOpcode instruction. Populate the table now, since this
// is the first time we're selecting an instruction.
unsigned Idx = 1;
while (true) {
// Get the size of this case.
unsigned CaseSize = MatcherTable[Idx++];
if (CaseSize & 128)
CaseSize = GetVBR(CaseSize, MatcherTable, Idx);
if (CaseSize == 0) break;
// Get the opcode, add the index to the table.
uint16_t Opc = MatcherTable[Idx++];
Opc |= (unsigned short)MatcherTable[Idx++] << 8;
if (Opc >= OpcodeOffset.size())
OpcodeOffset.resize((Opc+1)*2);
OpcodeOffset[Opc] = Idx;
Idx += CaseSize;
}
// Okay, do the lookup for the first opcode.
if (N.getOpcode() < OpcodeOffset.size())
MatcherIndex = OpcodeOffset[N.getOpcode()];
}
while (true) {
assert(MatcherIndex < TableSize && "Invalid index");
#ifndef NDEBUG
unsigned CurrentOpcodeIndex = MatcherIndex;
#endif
BuiltinOpcodes Opcode = (BuiltinOpcodes)MatcherTable[MatcherIndex++];
switch (Opcode) {
case OPC_Scope: {
// Okay, the semantics of this operation are that we should push a scope
// then evaluate the first child. However, pushing a scope only to have
// the first check fail (which then pops it) is inefficient. If we can
// determine immediately that the first check (or first several) will
// immediately fail, don't even bother pushing a scope for them.
unsigned FailIndex;
while (true) {
unsigned NumToSkip = MatcherTable[MatcherIndex++];
if (NumToSkip & 128)
NumToSkip = GetVBR(NumToSkip, MatcherTable, MatcherIndex);
// Found the end of the scope with no match.
if (NumToSkip == 0) {
FailIndex = 0;
break;
}
FailIndex = MatcherIndex+NumToSkip;
unsigned MatcherIndexOfPredicate = MatcherIndex;
(void)MatcherIndexOfPredicate; // silence warning.
// If we can't evaluate this predicate without pushing a scope (e.g. if
// it is a 'MoveParent') or if the predicate succeeds on this node, we
// push the scope and evaluate the full predicate chain.
bool Result;
MatcherIndex = IsPredicateKnownToFail(MatcherTable, MatcherIndex, N,
Result, *this, RecordedNodes);
if (!Result)
break;
LLVM_DEBUG(
dbgs() << " Skipped scope entry (due to false predicate) at "
<< "index " << MatcherIndexOfPredicate << ", continuing at "
<< FailIndex << "\n");
++NumDAGIselRetries;
// Otherwise, we know that this case of the Scope is guaranteed to fail,
// move to the next case.
MatcherIndex = FailIndex;
}
// If the whole scope failed to match, bail.
if (FailIndex == 0) break;
// Push a MatchScope which indicates where to go if the first child fails
// to match.
MatchScope NewEntry;
NewEntry.FailIndex = FailIndex;
NewEntry.NodeStack.append(NodeStack.begin(), NodeStack.end());
NewEntry.NumRecordedNodes = RecordedNodes.size();
NewEntry.NumMatchedMemRefs = MatchedMemRefs.size();
NewEntry.InputChain = InputChain;
NewEntry.InputGlue = InputGlue;
NewEntry.HasChainNodesMatched = !ChainNodesMatched.empty();
MatchScopes.push_back(NewEntry);
continue;
}
case OPC_RecordNode: {
// Remember this node, it may end up being an operand in the pattern.
SDNode *Parent = nullptr;
if (NodeStack.size() > 1)
Parent = NodeStack[NodeStack.size()-2].getNode();
RecordedNodes.push_back(std::make_pair(N, Parent));
continue;
}
case OPC_RecordChild0: case OPC_RecordChild1:
case OPC_RecordChild2: case OPC_RecordChild3:
case OPC_RecordChild4: case OPC_RecordChild5:
case OPC_RecordChild6: case OPC_RecordChild7: {
unsigned ChildNo = Opcode-OPC_RecordChild0;
if (ChildNo >= N.getNumOperands())
break; // Match fails if out of range child #.
RecordedNodes.push_back(std::make_pair(N->getOperand(ChildNo),
N.getNode()));
continue;
}
case OPC_RecordMemRef:
if (auto *MN = dyn_cast<MemSDNode>(N))
MatchedMemRefs.push_back(MN->getMemOperand());
else {
LLVM_DEBUG(dbgs() << "Expected MemSDNode "; N->dump(CurDAG);
dbgs() << '\n');
}
continue;
case OPC_CaptureGlueInput:
// If the current node has an input glue, capture it in InputGlue.
if (N->getNumOperands() != 0 &&
N->getOperand(N->getNumOperands()-1).getValueType() == MVT::Glue)
InputGlue = N->getOperand(N->getNumOperands()-1);
continue;
case OPC_MoveChild: {
unsigned ChildNo = MatcherTable[MatcherIndex++];
if (ChildNo >= N.getNumOperands())
break; // Match fails if out of range child #.
N = N.getOperand(ChildNo);
NodeStack.push_back(N);
continue;
}
case OPC_MoveChild0: case OPC_MoveChild1:
case OPC_MoveChild2: case OPC_MoveChild3:
case OPC_MoveChild4: case OPC_MoveChild5:
case OPC_MoveChild6: case OPC_MoveChild7: {
unsigned ChildNo = Opcode-OPC_MoveChild0;
if (ChildNo >= N.getNumOperands())
break; // Match fails if out of range child #.
N = N.getOperand(ChildNo);
NodeStack.push_back(N);
continue;
}
case OPC_MoveParent:
// Pop the current node off the NodeStack.
NodeStack.pop_back();
assert(!NodeStack.empty() && "Node stack imbalance!");
N = NodeStack.back();
continue;
case OPC_CheckSame:
if (!::CheckSame(MatcherTable, MatcherIndex, N, RecordedNodes)) break;
continue;
case OPC_CheckChild0Same: case OPC_CheckChild1Same:
case OPC_CheckChild2Same: case OPC_CheckChild3Same:
if (!::CheckChildSame(MatcherTable, MatcherIndex, N, RecordedNodes,
Opcode-OPC_CheckChild0Same))
break;
continue;
case OPC_CheckPatternPredicate:
if (!::CheckPatternPredicate(MatcherTable, MatcherIndex, *this)) break;
continue;
case OPC_CheckPredicate:
if (!::CheckNodePredicate(MatcherTable, MatcherIndex, *this,
N.getNode()))
break;
continue;
case OPC_CheckPredicateWithOperands: {
unsigned OpNum = MatcherTable[MatcherIndex++];
SmallVector<SDValue, 8> Operands;
for (unsigned i = 0; i < OpNum; ++i)
Operands.push_back(RecordedNodes[MatcherTable[MatcherIndex++]].first);
unsigned PredNo = MatcherTable[MatcherIndex++];
if (!CheckNodePredicateWithOperands(N.getNode(), PredNo, Operands))
break;
continue;
}
case OPC_CheckComplexPat: {
unsigned CPNum = MatcherTable[MatcherIndex++];
unsigned RecNo = MatcherTable[MatcherIndex++];
assert(RecNo < RecordedNodes.size() && "Invalid CheckComplexPat");
// If target can modify DAG during matching, keep the matching state
// consistent.
std::unique_ptr<MatchStateUpdater> MSU;
if (ComplexPatternFuncMutatesDAG())
MSU.reset(new MatchStateUpdater(*CurDAG, &NodeToMatch, RecordedNodes,
MatchScopes));
if (!CheckComplexPattern(NodeToMatch, RecordedNodes[RecNo].second,
RecordedNodes[RecNo].first, CPNum,
RecordedNodes))
break;
continue;
}
case OPC_CheckOpcode:
if (!::CheckOpcode(MatcherTable, MatcherIndex, N.getNode())) break;
continue;
case OPC_CheckType:
if (!::CheckType(MatcherTable, MatcherIndex, N, TLI,
CurDAG->getDataLayout()))
break;
continue;
case OPC_CheckTypeRes: {
unsigned Res = MatcherTable[MatcherIndex++];
if (!::CheckType(MatcherTable, MatcherIndex, N.getValue(Res), TLI,
CurDAG->getDataLayout()))
break;
continue;
}
case OPC_SwitchOpcode: {
unsigned CurNodeOpcode = N.getOpcode();
unsigned SwitchStart = MatcherIndex-1; (void)SwitchStart;
unsigned CaseSize;
while (true) {
// Get the size of this case.
CaseSize = MatcherTable[MatcherIndex++];
if (CaseSize & 128)
CaseSize = GetVBR(CaseSize, MatcherTable, MatcherIndex);
if (CaseSize == 0) break;
uint16_t Opc = MatcherTable[MatcherIndex++];
Opc |= (unsigned short)MatcherTable[MatcherIndex++] << 8;
// If the opcode matches, then we will execute this case.
if (CurNodeOpcode == Opc)
break;
// Otherwise, skip over this case.
MatcherIndex += CaseSize;
}
// If no cases matched, bail out.
if (CaseSize == 0) break;
// Otherwise, execute the case we found.
LLVM_DEBUG(dbgs() << " OpcodeSwitch from " << SwitchStart << " to "
<< MatcherIndex << "\n");
continue;
}
case OPC_SwitchType: {
MVT CurNodeVT = N.getSimpleValueType();
unsigned SwitchStart = MatcherIndex-1; (void)SwitchStart;
unsigned CaseSize;
while (true) {
// Get the size of this case.
CaseSize = MatcherTable[MatcherIndex++];
if (CaseSize & 128)
CaseSize = GetVBR(CaseSize, MatcherTable, MatcherIndex);
if (CaseSize == 0) break;
MVT CaseVT = (MVT::SimpleValueType)MatcherTable[MatcherIndex++];
if (CaseVT == MVT::iPTR)
CaseVT = TLI->getPointerTy(CurDAG->getDataLayout());
// If the VT matches, then we will execute this case.
if (CurNodeVT == CaseVT)
break;
// Otherwise, skip over this case.
MatcherIndex += CaseSize;
}
// If no cases matched, bail out.
if (CaseSize == 0) break;
// Otherwise, execute the case we found.
LLVM_DEBUG(dbgs() << " TypeSwitch[" << EVT(CurNodeVT).getEVTString()
<< "] from " << SwitchStart << " to " << MatcherIndex
<< '\n');
continue;
}
case OPC_CheckChild0Type: case OPC_CheckChild1Type:
case OPC_CheckChild2Type: case OPC_CheckChild3Type:
case OPC_CheckChild4Type: case OPC_CheckChild5Type:
case OPC_CheckChild6Type: case OPC_CheckChild7Type:
if (!::CheckChildType(MatcherTable, MatcherIndex, N, TLI,
CurDAG->getDataLayout(),
Opcode - OPC_CheckChild0Type))
break;
continue;
case OPC_CheckCondCode:
if (!::CheckCondCode(MatcherTable, MatcherIndex, N)) break;
continue;
case OPC_CheckChild2CondCode:
if (!::CheckChild2CondCode(MatcherTable, MatcherIndex, N)) break;
continue;
case OPC_CheckValueType:
if (!::CheckValueType(MatcherTable, MatcherIndex, N, TLI,
CurDAG->getDataLayout()))
break;
continue;
case OPC_CheckInteger:
if (!::CheckInteger(MatcherTable, MatcherIndex, N)) break;
continue;
case OPC_CheckChild0Integer: case OPC_CheckChild1Integer:
case OPC_CheckChild2Integer: case OPC_CheckChild3Integer:
case OPC_CheckChild4Integer:
if (!::CheckChildInteger(MatcherTable, MatcherIndex, N,
Opcode-OPC_CheckChild0Integer)) break;
continue;
case OPC_CheckAndImm:
if (!::CheckAndImm(MatcherTable, MatcherIndex, N, *this)) break;
continue;
case OPC_CheckOrImm:
if (!::CheckOrImm(MatcherTable, MatcherIndex, N, *this)) break;
continue;
case OPC_CheckImmAllOnesV:
if (!ISD::isConstantSplatVectorAllOnes(N.getNode()))
break;
continue;
case OPC_CheckImmAllZerosV:
if (!ISD::isConstantSplatVectorAllZeros(N.getNode()))
break;
continue;
case OPC_CheckFoldableChainNode: {
assert(NodeStack.size() != 1 && "No parent node");
// Verify that all intermediate nodes between the root and this one have
// a single use (ignoring chains, which are handled in UpdateChains).
bool HasMultipleUses = false;
for (unsigned i = 1, e = NodeStack.size()-1; i != e; ++i) {
unsigned NNonChainUses = 0;
SDNode *NS = NodeStack[i].getNode();
for (auto UI = NS->use_begin(), UE = NS->use_end(); UI != UE; ++UI)
if (UI.getUse().getValueType() != MVT::Other)
if (++NNonChainUses > 1) {
HasMultipleUses = true;
break;
}
if (HasMultipleUses) break;
}
if (HasMultipleUses) break;
// Check to see that the target thinks this is profitable to fold and that
// we can fold it without inducing cycles in the graph.
if (!IsProfitableToFold(N, NodeStack[NodeStack.size()-2].getNode(),
NodeToMatch) ||
!IsLegalToFold(N, NodeStack[NodeStack.size()-2].getNode(),
NodeToMatch, OptLevel,
true/*We validate our own chains*/))
break;
continue;
}
case OPC_EmitInteger:
case OPC_EmitStringInteger: {
MVT::SimpleValueType VT =
(MVT::SimpleValueType)MatcherTable[MatcherIndex++];
int64_t Val = MatcherTable[MatcherIndex++];
if (Val & 128)
Val = GetVBR(Val, MatcherTable, MatcherIndex);
if (Opcode == OPC_EmitInteger)
Val = decodeSignRotatedValue(Val);
RecordedNodes.push_back(std::pair<SDValue, SDNode*>(
CurDAG->getTargetConstant(Val, SDLoc(NodeToMatch),
VT), nullptr));
continue;
}
case OPC_EmitRegister: {
MVT::SimpleValueType VT =
(MVT::SimpleValueType)MatcherTable[MatcherIndex++];
unsigned RegNo = MatcherTable[MatcherIndex++];
RecordedNodes.push_back(std::pair<SDValue, SDNode*>(
CurDAG->getRegister(RegNo, VT), nullptr));
continue;
}
case OPC_EmitRegister2: {
// For targets w/ more than 256 register names, the register enum
// values are stored in two bytes in the matcher table (just like
// opcodes).
MVT::SimpleValueType VT =
(MVT::SimpleValueType)MatcherTable[MatcherIndex++];
unsigned RegNo = MatcherTable[MatcherIndex++];
RegNo |= MatcherTable[MatcherIndex++] << 8;
RecordedNodes.push_back(std::pair<SDValue, SDNode*>(
CurDAG->getRegister(RegNo, VT), nullptr));
continue;
}
case OPC_EmitConvertToTarget: {
// Convert from IMM/FPIMM to target version.
unsigned RecNo = MatcherTable[MatcherIndex++];
assert(RecNo < RecordedNodes.size() && "Invalid EmitConvertToTarget");
SDValue Imm = RecordedNodes[RecNo].first;
if (Imm->getOpcode() == ISD::Constant) {
const ConstantInt *Val=cast<ConstantSDNode>(Imm)->getConstantIntValue();
Imm = CurDAG->getTargetConstant(*Val, SDLoc(NodeToMatch),
Imm.getValueType());
} else if (Imm->getOpcode() == ISD::ConstantFP) {
const ConstantFP *Val=cast<ConstantFPSDNode>(Imm)->getConstantFPValue();
Imm = CurDAG->getTargetConstantFP(*Val, SDLoc(NodeToMatch),
Imm.getValueType());
}
RecordedNodes.push_back(std::make_pair(Imm, RecordedNodes[RecNo].second));
continue;
}
case OPC_EmitMergeInputChains1_0: // OPC_EmitMergeInputChains, 1, 0
case OPC_EmitMergeInputChains1_1: // OPC_EmitMergeInputChains, 1, 1
case OPC_EmitMergeInputChains1_2: { // OPC_EmitMergeInputChains, 1, 2
// These are space-optimized forms of OPC_EmitMergeInputChains.
assert(!InputChain.getNode() &&
"EmitMergeInputChains should be the first chain producing node");
assert(ChainNodesMatched.empty() &&
"Should only have one EmitMergeInputChains per match");
// Read all of the chained nodes.
unsigned RecNo = Opcode - OPC_EmitMergeInputChains1_0;
assert(RecNo < RecordedNodes.size() && "Invalid EmitMergeInputChains");
ChainNodesMatched.push_back(RecordedNodes[RecNo].first.getNode());
// FIXME: What if other value results of the node have uses not matched
// by this pattern?
if (ChainNodesMatched.back() != NodeToMatch &&
!RecordedNodes[RecNo].first.hasOneUse()) {
ChainNodesMatched.clear();
break;
}
// Merge the input chains if they are not intra-pattern references.
InputChain = HandleMergeInputChains(ChainNodesMatched, CurDAG);
if (!InputChain.getNode())
break; // Failed to merge.
continue;
}
case OPC_EmitMergeInputChains: {
assert(!InputChain.getNode() &&
"EmitMergeInputChains should be the first chain producing node");
// This node gets a list of nodes we matched in the input that have
// chains. We want to token factor all of the input chains to these nodes
// together. However, if any of the input chains is actually one of the
// nodes matched in this pattern, then we have an intra-match reference.
// Ignore these because the newly token factored chain should not refer to
// the old nodes.
unsigned NumChains = MatcherTable[MatcherIndex++];
assert(NumChains != 0 && "Can't TF zero chains");
assert(ChainNodesMatched.empty() &&
"Should only have one EmitMergeInputChains per match");
// Read all of the chained nodes.
for (unsigned i = 0; i != NumChains; ++i) {
unsigned RecNo = MatcherTable[MatcherIndex++];
assert(RecNo < RecordedNodes.size() && "Invalid EmitMergeInputChains");
ChainNodesMatched.push_back(RecordedNodes[RecNo].first.getNode());
// FIXME: What if other value results of the node have uses not matched
// by this pattern?
if (ChainNodesMatched.back() != NodeToMatch &&
!RecordedNodes[RecNo].first.hasOneUse()) {
ChainNodesMatched.clear();
break;
}
}
// If the inner loop broke out, the match fails.
if (ChainNodesMatched.empty())
break;
// Merge the input chains if they are not intra-pattern references.
InputChain = HandleMergeInputChains(ChainNodesMatched, CurDAG);
if (!InputChain.getNode())
break; // Failed to merge.
continue;
}
case OPC_EmitCopyToReg:
case OPC_EmitCopyToReg2: {
unsigned RecNo = MatcherTable[MatcherIndex++];
assert(RecNo < RecordedNodes.size() && "Invalid EmitCopyToReg");
unsigned DestPhysReg = MatcherTable[MatcherIndex++];
if (Opcode == OPC_EmitCopyToReg2)
DestPhysReg |= MatcherTable[MatcherIndex++] << 8;
if (!InputChain.getNode())
InputChain = CurDAG->getEntryNode();
InputChain = CurDAG->getCopyToReg(InputChain, SDLoc(NodeToMatch),
DestPhysReg, RecordedNodes[RecNo].first,
InputGlue);
InputGlue = InputChain.getValue(1);
continue;
}
case OPC_EmitNodeXForm: {
unsigned XFormNo = MatcherTable[MatcherIndex++];
unsigned RecNo = MatcherTable[MatcherIndex++];
assert(RecNo < RecordedNodes.size() && "Invalid EmitNodeXForm");
SDValue Res = RunSDNodeXForm(RecordedNodes[RecNo].first, XFormNo);
RecordedNodes.push_back(std::pair<SDValue,SDNode*>(Res, nullptr));
continue;
}
case OPC_Coverage: {
// This is emitted right before MorphNode/EmitNode.
// So it should be safe to assume that this node has been selected
unsigned index = MatcherTable[MatcherIndex++];
index |= (MatcherTable[MatcherIndex++] << 8);
dbgs() << "COVERED: " << getPatternForIndex(index) << "\n";
dbgs() << "INCLUDED: " << getIncludePathForIndex(index) << "\n";
continue;
}
case OPC_EmitNode: case OPC_MorphNodeTo:
case OPC_EmitNode0: case OPC_EmitNode1: case OPC_EmitNode2:
case OPC_MorphNodeTo0: case OPC_MorphNodeTo1: case OPC_MorphNodeTo2: {
uint16_t TargetOpc = MatcherTable[MatcherIndex++];
TargetOpc |= (unsigned short)MatcherTable[MatcherIndex++] << 8;
unsigned EmitNodeInfo = MatcherTable[MatcherIndex++];
// Get the result VT list.
unsigned NumVTs;
// If this is one of the compressed forms, get the number of VTs based
// on the Opcode. Otherwise read the next byte from the table.
if (Opcode >= OPC_MorphNodeTo0 && Opcode <= OPC_MorphNodeTo2)
NumVTs = Opcode - OPC_MorphNodeTo0;
else if (Opcode >= OPC_EmitNode0 && Opcode <= OPC_EmitNode2)
NumVTs = Opcode - OPC_EmitNode0;
else
NumVTs = MatcherTable[MatcherIndex++];
SmallVector<EVT, 4> VTs;
for (unsigned i = 0; i != NumVTs; ++i) {
MVT::SimpleValueType VT =
(MVT::SimpleValueType)MatcherTable[MatcherIndex++];
if (VT == MVT::iPTR)
VT = TLI->getPointerTy(CurDAG->getDataLayout()).SimpleTy;
VTs.push_back(VT);
}
if (EmitNodeInfo & OPFL_Chain)
VTs.push_back(MVT::Other);
if (EmitNodeInfo & OPFL_GlueOutput)
VTs.push_back(MVT::Glue);
// This is hot code, so optimize the two most common cases of 1 and 2
// results.
SDVTList VTList;
if (VTs.size() == 1)
VTList = CurDAG->getVTList(VTs[0]);
else if (VTs.size() == 2)
VTList = CurDAG->getVTList(VTs[0], VTs[1]);
else
VTList = CurDAG->getVTList(VTs);
// Get the operand list.
unsigned NumOps = MatcherTable[MatcherIndex++];
SmallVector<SDValue, 8> Ops;
for (unsigned i = 0; i != NumOps; ++i) {
unsigned RecNo = MatcherTable[MatcherIndex++];
if (RecNo & 128)
RecNo = GetVBR(RecNo, MatcherTable, MatcherIndex);
assert(RecNo < RecordedNodes.size() && "Invalid EmitNode");
Ops.push_back(RecordedNodes[RecNo].first);
}
// If there are variadic operands to add, handle them now.
if (EmitNodeInfo & OPFL_VariadicInfo) {
// Determine the start index to copy from.
unsigned FirstOpToCopy = getNumFixedFromVariadicInfo(EmitNodeInfo);
FirstOpToCopy += (EmitNodeInfo & OPFL_Chain) ? 1 : 0;
assert(NodeToMatch->getNumOperands() >= FirstOpToCopy &&
"Invalid variadic node");
// Copy all of the variadic operands, not including a potential glue
// input.
for (unsigned i = FirstOpToCopy, e = NodeToMatch->getNumOperands();
i != e; ++i) {
SDValue V = NodeToMatch->getOperand(i);
if (V.getValueType() == MVT::Glue) break;
Ops.push_back(V);
}
}
// If this has chain/glue inputs, add them.
if (EmitNodeInfo & OPFL_Chain)
Ops.push_back(InputChain);
if ((EmitNodeInfo & OPFL_GlueInput) && InputGlue.getNode() != nullptr)
Ops.push_back(InputGlue);
// Check whether any matched node could raise an FP exception. Since all
// such nodes must have a chain, it suffices to check ChainNodesMatched.
// We need to perform this check before potentially modifying one of the
// nodes via MorphNode.
bool MayRaiseFPException = false;
for (auto *N : ChainNodesMatched)
if (mayRaiseFPException(N) && !N->getFlags().hasNoFPExcept()) {
MayRaiseFPException = true;
break;
}
// Create the node.
MachineSDNode *Res = nullptr;
bool IsMorphNodeTo = Opcode == OPC_MorphNodeTo ||
(Opcode >= OPC_MorphNodeTo0 && Opcode <= OPC_MorphNodeTo2);
if (!IsMorphNodeTo) {
// If this is a normal EmitNode command, just create the new node and
// add the results to the RecordedNodes list.
Res = CurDAG->getMachineNode(TargetOpc, SDLoc(NodeToMatch),
VTList, Ops);
// Add all the non-glue/non-chain results to the RecordedNodes list.
for (unsigned i = 0, e = VTs.size(); i != e; ++i) {
if (VTs[i] == MVT::Other || VTs[i] == MVT::Glue) break;
RecordedNodes.push_back(std::pair<SDValue,SDNode*>(SDValue(Res, i),
nullptr));
}
} else {
assert(NodeToMatch->getOpcode() != ISD::DELETED_NODE &&
"NodeToMatch was removed partway through selection");
SelectionDAG::DAGNodeDeletedListener NDL(*CurDAG, [&](SDNode *N,
SDNode *E) {
CurDAG->salvageDebugInfo(*N);
auto &Chain = ChainNodesMatched;
assert((!E || !is_contained(Chain, N)) &&
"Chain node replaced during MorphNode");
llvm::erase_value(Chain, N);
});
Res = cast<MachineSDNode>(MorphNode(NodeToMatch, TargetOpc, VTList,
Ops, EmitNodeInfo));
}
// Set the NoFPExcept flag when no original matched node could
// raise an FP exception, but the new node potentially might.
if (!MayRaiseFPException && mayRaiseFPException(Res)) {
SDNodeFlags Flags = Res->getFlags();
Flags.setNoFPExcept(true);
Res->setFlags(Flags);
}
// If the node had chain/glue results, update our notion of the current
// chain and glue.
if (EmitNodeInfo & OPFL_GlueOutput) {
InputGlue = SDValue(Res, VTs.size()-1);
if (EmitNodeInfo & OPFL_Chain)
InputChain = SDValue(Res, VTs.size()-2);
} else if (EmitNodeInfo & OPFL_Chain)
InputChain = SDValue(Res, VTs.size()-1);
// If the OPFL_MemRefs glue is set on this node, slap all of the
// accumulated memrefs onto it.
//
// FIXME: This is vastly incorrect for patterns with multiple outputs
// instructions that access memory and for ComplexPatterns that match
// loads.
if (EmitNodeInfo & OPFL_MemRefs) {
// Only attach load or store memory operands if the generated
// instruction may load or store.
const MCInstrDesc &MCID = TII->get(TargetOpc);
bool mayLoad = MCID.mayLoad();
bool mayStore = MCID.mayStore();
// We expect to have relatively few of these so just filter them into a
// temporary buffer so that we can easily add them to the instruction.
SmallVector<MachineMemOperand *, 4> FilteredMemRefs;
for (MachineMemOperand *MMO : MatchedMemRefs) {
if (MMO->isLoad()) {
if (mayLoad)
FilteredMemRefs.push_back(MMO);
} else if (MMO->isStore()) {
if (mayStore)
FilteredMemRefs.push_back(MMO);
} else {
FilteredMemRefs.push_back(MMO);
}
}
CurDAG->setNodeMemRefs(Res, FilteredMemRefs);
}
LLVM_DEBUG(if (!MatchedMemRefs.empty() && Res->memoperands_empty()) dbgs()
<< " Dropping mem operands\n";
dbgs() << " " << (IsMorphNodeTo ? "Morphed" : "Created")
<< " node: ";
Res->dump(CurDAG););
// If this was a MorphNodeTo then we're completely done!
if (IsMorphNodeTo) {
// Update chain uses.
UpdateChains(Res, InputChain, ChainNodesMatched, true);
return;
}
continue;
}
case OPC_CompleteMatch: {
// The match has been completed, and any new nodes (if any) have been
// created. Patch up references to the matched dag to use the newly
// created nodes.
unsigned NumResults = MatcherTable[MatcherIndex++];
for (unsigned i = 0; i != NumResults; ++i) {
unsigned ResSlot = MatcherTable[MatcherIndex++];
if (ResSlot & 128)
ResSlot = GetVBR(ResSlot, MatcherTable, MatcherIndex);
assert(ResSlot < RecordedNodes.size() && "Invalid CompleteMatch");
SDValue Res = RecordedNodes[ResSlot].first;
assert(i < NodeToMatch->getNumValues() &&
NodeToMatch->getValueType(i) != MVT::Other &&
NodeToMatch->getValueType(i) != MVT::Glue &&
"Invalid number of results to complete!");
assert((NodeToMatch->getValueType(i) == Res.getValueType() ||
NodeToMatch->getValueType(i) == MVT::iPTR ||
Res.getValueType() == MVT::iPTR ||
NodeToMatch->getValueType(i).getSizeInBits() ==
Res.getValueSizeInBits()) &&
"invalid replacement");
ReplaceUses(SDValue(NodeToMatch, i), Res);
}
// Update chain uses.
UpdateChains(NodeToMatch, InputChain, ChainNodesMatched, false);
// If the root node defines glue, we need to update it to the glue result.
// TODO: This never happens in our tests and I think it can be removed /
// replaced with an assert, but if we do it this the way the change is
// NFC.
if (NodeToMatch->getValueType(NodeToMatch->getNumValues() - 1) ==
MVT::Glue &&
InputGlue.getNode())
ReplaceUses(SDValue(NodeToMatch, NodeToMatch->getNumValues() - 1),
InputGlue);
assert(NodeToMatch->use_empty() &&
"Didn't replace all uses of the node?");
CurDAG->RemoveDeadNode(NodeToMatch);
return;
}
}
// If the code reached this point, then the match failed. See if there is
// another child to try in the current 'Scope', otherwise pop it until we
// find a case to check.
LLVM_DEBUG(dbgs() << " Match failed at index " << CurrentOpcodeIndex
<< "\n");
++NumDAGIselRetries;
while (true) {
if (MatchScopes.empty()) {
CannotYetSelect(NodeToMatch);
return;
}
// Restore the interpreter state back to the point where the scope was
// formed.
MatchScope &LastScope = MatchScopes.back();
RecordedNodes.resize(LastScope.NumRecordedNodes);
NodeStack.clear();
NodeStack.append(LastScope.NodeStack.begin(), LastScope.NodeStack.end());
N = NodeStack.back();
if (LastScope.NumMatchedMemRefs != MatchedMemRefs.size())
MatchedMemRefs.resize(LastScope.NumMatchedMemRefs);
MatcherIndex = LastScope.FailIndex;
LLVM_DEBUG(dbgs() << " Continuing at " << MatcherIndex << "\n");
InputChain = LastScope.InputChain;
InputGlue = LastScope.InputGlue;
if (!LastScope.HasChainNodesMatched)
ChainNodesMatched.clear();
// Check to see what the offset is at the new MatcherIndex. If it is zero
// we have reached the end of this scope, otherwise we have another child
// in the current scope to try.
unsigned NumToSkip = MatcherTable[MatcherIndex++];
if (NumToSkip & 128)
NumToSkip = GetVBR(NumToSkip, MatcherTable, MatcherIndex);
// If we have another child in this scope to match, update FailIndex and
// try it.
if (NumToSkip != 0) {
LastScope.FailIndex = MatcherIndex+NumToSkip;
break;
}
// End of this scope, pop it and try the next child in the containing
// scope.
MatchScopes.pop_back();
}
}
}