Some DAG node will be replaced in this pass over the DAG nodes for a basic block.
References:
llvm/lib/CodeGen/SelectionDAG/LegalizeTypes.cpp
/// This is the main entry point for the type legalizer. This does a top-down
/// traversal of the dag, legalizing types as it goes. Returns "true" if it made
/// any changes.
bool DAGTypeLegalizer::run() {
bool Changed = false;
// Create a dummy node (which is not added to allnodes), that adds a reference
// to the root node, preventing it from being deleted, and tracking any
// changes of the root.
HandleSDNode Dummy(DAG.getRoot());
Dummy.setNodeId(Unanalyzed);
// The root of the dag may dangle to deleted nodes until the type legalizer is
// done. Set it to null to avoid confusion.
DAG.setRoot(SDValue());
// Walk all nodes in the graph, assigning them a NodeId of 'ReadyToProcess'
// (and remembering them) if they are leaves and assigning 'Unanalyzed' if
// non-leaves.
for (SDNode &Node : DAG.allnodes()) {
if (Node.getNumOperands() == 0) {
AddToWorklist(&Node);
} else {
Node.setNodeId(Unanalyzed);
}
}
// Now that we have a set of nodes to process, handle them all.
while (!Worklist.empty()) {
#ifndef EXPENSIVE_CHECKS
if (EnableExpensiveChecks)
#endif
PerformExpensiveChecks();
SDNode *N = Worklist.back();
Worklist.pop_back();
assert(N->getNodeId() == ReadyToProcess &&
"Node should be ready if on worklist!");
LLVM_DEBUG(dbgs() << "Legalizing node: "; N->dump(&DAG));
if (IgnoreNodeResults(N)) {
LLVM_DEBUG(dbgs() << "Ignoring node results\n");
goto ScanOperands;
}
// Scan the values produced by the node, checking to see if any result
// types are illegal.
for (unsigned i = 0, NumResults = N->getNumValues(); i < NumResults; ++i) {
EVT ResultVT = N->getValueType(i);
LLVM_DEBUG(dbgs() << "Analyzing result type: " << ResultVT.getEVTString()
<< "\n");
switch (getTypeAction(ResultVT)) {
case TargetLowering::TypeLegal:
LLVM_DEBUG(dbgs() << "Legal result type\n");
break;
// The following calls must take care of *all* of the node's results,
// not just the illegal result they were passed (this includes results
// with a legal type). Results can be remapped using ReplaceValueWith,
// or their promoted/expanded/etc values registered in PromotedIntegers,
// ExpandedIntegers etc.
case TargetLowering::TypePromoteInteger:
PromoteIntegerResult(N, i);
Changed = true;
goto NodeDone;
case TargetLowering::TypeExpandInteger:
ExpandIntegerResult(N, i);
Changed = true;
goto NodeDone;
case TargetLowering::TypeSoftenFloat:
SoftenFloatResult(N, i);
Changed = true;
goto NodeDone;
case TargetLowering::TypeExpandFloat:
ExpandFloatResult(N, i);
Changed = true;
goto NodeDone;
case TargetLowering::TypeScalarizeVector:
ScalarizeVectorResult(N, i);
Changed = true;
goto NodeDone;
case TargetLowering::TypeSplitVector:
SplitVectorResult(N, i);
Changed = true;
goto NodeDone;
case TargetLowering::TypeWidenVector:
WidenVectorResult(N, i);
Changed = true;
goto NodeDone;
case TargetLowering::TypePromoteFloat:
PromoteFloatResult(N, i);
Changed = true;
goto NodeDone;
}
}
ScanOperands:
// Scan the operand list for the node, handling any nodes with operands that
// are illegal.
{
unsigned NumOperands = N->getNumOperands();
bool NeedsReanalyzing = false;
unsigned i;
for (i = 0; i != NumOperands; ++i) {
if (IgnoreNodeResults(N->getOperand(i).getNode()))
continue;
const auto Op = N->getOperand(i);
LLVM_DEBUG(dbgs() << "Analyzing operand: "; Op.dump(&DAG));
EVT OpVT = Op.getValueType();
switch (getTypeAction(OpVT)) {
case TargetLowering::TypeLegal:
LLVM_DEBUG(dbgs() << "Legal operand\n");
continue;
// The following calls must either replace all of the node's results
// using ReplaceValueWith, and return "false"; or update the node's
// operands in place, and return "true".
case TargetLowering::TypePromoteInteger:
NeedsReanalyzing = PromoteIntegerOperand(N, i);
Changed = true;
break;
case TargetLowering::TypeExpandInteger:
NeedsReanalyzing = ExpandIntegerOperand(N, i);
Changed = true;
break;
case TargetLowering::TypeSoftenFloat:
NeedsReanalyzing = SoftenFloatOperand(N, i);
Changed = true;
break;
case TargetLowering::TypeExpandFloat:
NeedsReanalyzing = ExpandFloatOperand(N, i);
Changed = true;
break;
case TargetLowering::TypeScalarizeVector:
NeedsReanalyzing = ScalarizeVectorOperand(N, i);
Changed = true;
break;
case TargetLowering::TypeSplitVector:
NeedsReanalyzing = SplitVectorOperand(N, i);
Changed = true;
break;
case TargetLowering::TypeWidenVector:
NeedsReanalyzing = WidenVectorOperand(N, i);
Changed = true;
break;
case TargetLowering::TypePromoteFloat:
NeedsReanalyzing = PromoteFloatOperand(N, i);
Changed = true;
break;
}
break;
}
// The sub-method updated N in place. Check to see if any operands are new,
// and if so, mark them. If the node needs revisiting, don't add all users
// to the worklist etc.
if (NeedsReanalyzing) {
assert(N->getNodeId() == ReadyToProcess && "Node ID recalculated?");
N->setNodeId(NewNode);
// Recompute the NodeId and correct processed operands, adding the node to
// the worklist if ready.
SDNode *M = AnalyzeNewNode(N);
if (M == N)
// The node didn't morph - nothing special to do, it will be revisited.
continue;
// The node morphed - this is equivalent to legalizing by replacing every
// value of N with the corresponding value of M. So do that now.
assert(N->getNumValues() == M->getNumValues() &&
"Node morphing changed the number of results!");
for (unsigned i = 0, e = N->getNumValues(); i != e; ++i)
// Replacing the value takes care of remapping the new value.
ReplaceValueWith(SDValue(N, i), SDValue(M, i));
assert(N->getNodeId() == NewNode && "Unexpected node state!");
// The node continues to live on as part of the NewNode fungus that
// grows on top of the useful nodes. Nothing more needs to be done
// with it - move on to the next node.
continue;
}
if (i == NumOperands) {
LLVM_DEBUG(dbgs() << "Legally typed node: "; N->dump(&DAG);
dbgs() << "\n");
}
}
NodeDone:
// If we reach here, the node was processed, potentially creating new nodes.
// Mark it as processed and add its users to the worklist as appropriate.
assert(N->getNodeId() == ReadyToProcess && "Node ID recalculated?");
N->setNodeId(Processed);
for (SDNode::use_iterator UI = N->use_begin(), E = N->use_end();
UI != E; ++UI) {
SDNode *User = *UI;
int NodeId = User->getNodeId();
// This node has two options: it can either be a new node or its Node ID
// may be a count of the number of operands it has that are not ready.
if (NodeId > 0) {
User->setNodeId(NodeId-1);
// If this was the last use it was waiting on, add it to the ready list.
if (NodeId-1 == ReadyToProcess)
Worklist.push_back(User);
continue;
}
// If this is an unreachable new node, then ignore it. If it ever becomes
// reachable by being used by a newly created node then it will be handled
// by AnalyzeNewNode.
if (NodeId == NewNode)
continue;
// Otherwise, this node is new: this is the first operand of it that
// became ready. Its new NodeId is the number of operands it has minus 1
// (as this node is now processed).
assert(NodeId == Unanalyzed && "Unknown node ID!");
User->setNodeId(User->getNumOperands() - 1);
// If the node only has a single operand, it is now ready.
if (User->getNumOperands() == 1)
Worklist.push_back(User);
}
}
#ifndef EXPENSIVE_CHECKS
if (EnableExpensiveChecks)
#endif
PerformExpensiveChecks();
// If the root changed (e.g. it was a dead load) update the root.
DAG.setRoot(Dummy.getValue());
// Remove dead nodes. This is important to do for cleanliness but also before
// the checking loop below. Implicit folding by the DAG.getNode operators and
// node morphing can cause unreachable nodes to be around with their flags set
// to new.
DAG.RemoveDeadNodes();
// In a debug build, scan all the nodes to make sure we found them all. This
// ensures that there are no cycles and that everything got processed.
#ifndef NDEBUG
for (SDNode &Node : DAG.allnodes()) {
bool Failed = false;
// Check that all result types are legal.
if (!IgnoreNodeResults(&Node))
for (unsigned i = 0, NumVals = Node.getNumValues(); i < NumVals; ++i)
if (!isTypeLegal(Node.getValueType(i))) {
dbgs() << "Result type " << i << " illegal: ";
Node.dump(&DAG);
Failed = true;
}
// Check that all operand types are legal.
for (unsigned i = 0, NumOps = Node.getNumOperands(); i < NumOps; ++i)
if (!IgnoreNodeResults(Node.getOperand(i).getNode()) &&
!isTypeLegal(Node.getOperand(i).getValueType())) {
dbgs() << "Operand type " << i << " illegal: ";
Node.getOperand(i).dump(&DAG);
Failed = true;
}
if (Node.getNodeId() != Processed) {
if (Node.getNodeId() == NewNode)
dbgs() << "New node not analyzed?\n";
else if (Node.getNodeId() == Unanalyzed)
dbgs() << "Unanalyzed node not noticed?\n";
else if (Node.getNodeId() > 0)
dbgs() << "Operand not processed?\n";
else if (Node.getNodeId() == ReadyToProcess)
dbgs() << "Not added to worklist?\n";
Failed = true;
}
if (Failed) {
Node.dump(&DAG); dbgs() << "\n";
llvm_unreachable(nullptr);
}
}
#endif
return Changed;
}
If you could revise
the fundmental principles of
computer system design
to improve security...
... what would you change?