Please use GitHub pull requests for new patches. Phabricator shutdown timeline

Differential D58070 Diff 192859 llvm/trunk/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

Changeset View

Standalone View

llvm/trunk/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

This file is larger than 256 KB, so syntax highlighting is disabled by default.

Show First 20 Lines • Show All 131 Lines • ▼ Show 20 Lines	class DAGCombiner {
SmallVector<SDNode *, 64> Worklist;		SmallVector<SDNode *, 64> Worklist;

/// Mapping from an SDNode to its position on the worklist.		/// Mapping from an SDNode to its position on the worklist.
///		///
/// This is used to find and remove nodes from the worklist (by nulling		/// This is used to find and remove nodes from the worklist (by nulling
/// them) when they are deleted from the underlying DAG. It relies on		/// them) when they are deleted from the underlying DAG. It relies on
/// stable indices of nodes within the worklist.		/// stable indices of nodes within the worklist.
DenseMap<SDNode *, unsigned> WorklistMap;		DenseMap<SDNode *, unsigned> WorklistMap;
		/// This records all nodes attempted to add to the worklist since we
		/// considered a new worklist entry. As we keep do not add duplicate nodes
		/// in the worklist, this is different from the tail of the worklist.
		SmallSetVector<SDNode *, 32> PruningList;

/// Set of nodes which have been combined (at least once).		/// Set of nodes which have been combined (at least once).
///		///
/// This is used to allow us to reliably add any operands of a DAG node		/// This is used to allow us to reliably add any operands of a DAG node
/// which have not yet been combined to the worklist.		/// which have not yet been combined to the worklist.
SmallPtrSet<SDNode *, 32> CombinedNodes;		SmallPtrSet<SDNode *, 32> CombinedNodes;

// AA - Used for DAG load/store alias analysis.		// AA - Used for DAG load/store alias analysis.
AliasAnalysis *AA;		AliasAnalysis *AA;

/// When an instruction is simplified, add all users of the instruction to		/// When an instruction is simplified, add all users of the instruction to
/// the work lists because they might get more simplified now.		/// the work lists because they might get more simplified now.
void AddUsersToWorklist(SDNode *N) {		void AddUsersToWorklist(SDNode *N) {
for (SDNode *Node : N->uses())		for (SDNode *Node : N->uses())
AddToWorklist(Node);		AddToWorklist(Node);
}		}

		// Prune potentially dangling nodes. This is called after
		// any visit to a node, but should also be called during a visit after any
		// failed combine which may have created a DAG node.
		void clearAddedDanglingWorklistEntries() {
		// Check any nodes added to the worklist to see if they are prunable.
		while (!PruningList.empty()) {
		auto *N = PruningList.pop_back_val();
		if (N->use_empty())
		recursivelyDeleteUnusedNodes(N);
		}
		}

		SDNode *getNextWorklistEntry() {
		// Before we do any work, remove nodes that are not in use.
		clearAddedDanglingWorklistEntries();
		SDNode *N = nullptr;
		// The Worklist holds the SDNodes in order, but it may contain null
		// entries.
		while (!N && !Worklist.empty()) {
		N = Worklist.pop_back_val();
		}

		if (N) {
		bool GoodWorklistEntry = WorklistMap.erase(N);
		(void)GoodWorklistEntry;
		assert(GoodWorklistEntry &&
		"Found a worklist entry without a corresponding map entry!");
		}
		return N;
		}

/// Call the node-specific routine that folds each particular type of node.		/// Call the node-specific routine that folds each particular type of node.
SDValue visit(SDNode *N);		SDValue visit(SDNode *N);

public:		public:
DAGCombiner(SelectionDAG &D, AliasAnalysis *AA, CodeGenOpt::Level OL)		DAGCombiner(SelectionDAG &D, AliasAnalysis *AA, CodeGenOpt::Level OL)
: DAG(D), TLI(D.getTargetLoweringInfo()), Level(BeforeLegalizeTypes),		: DAG(D), TLI(D.getTargetLoweringInfo()), Level(BeforeLegalizeTypes),
OptLevel(OL), AA(AA) {		OptLevel(OL), AA(AA) {
ForCodeSize = DAG.getMachineFunction().getFunction().optForSize();		ForCodeSize = DAG.getMachineFunction().getFunction().optForSize();

MaximumLegalStoreInBits = 0;		MaximumLegalStoreInBits = 0;
for (MVT VT : MVT::all_valuetypes())		for (MVT VT : MVT::all_valuetypes())
if (EVT(VT).isSimple() && VT != MVT::Other &&		if (EVT(VT).isSimple() && VT != MVT::Other &&
TLI.isTypeLegal(EVT(VT)) &&		TLI.isTypeLegal(EVT(VT)) &&
VT.getSizeInBits() >= MaximumLegalStoreInBits)		VT.getSizeInBits() >= MaximumLegalStoreInBits)
MaximumLegalStoreInBits = VT.getSizeInBits();		MaximumLegalStoreInBits = VT.getSizeInBits();
}		}

		void ConsiderForPruning(SDNode *N) {
		// Mark this for potential pruning.
		PruningList.insert(N);
		}

/// Add to the worklist making sure its instance is at the back (next to be		/// Add to the worklist making sure its instance is at the back (next to be
/// processed.)		/// processed.)
void AddToWorklist(SDNode *N) {		void AddToWorklist(SDNode *N) {
assert(N->getOpcode() != ISD::DELETED_NODE &&		assert(N->getOpcode() != ISD::DELETED_NODE &&
"Deleted Node added to Worklist");		"Deleted Node added to Worklist");

// Skip handle nodes as they can't usefully be combined and confuse the		// Skip handle nodes as they can't usefully be combined and confuse the
// zero-use deletion strategy.		// zero-use deletion strategy.
if (N->getOpcode() == ISD::HANDLENODE)		if (N->getOpcode() == ISD::HANDLENODE)
return;		return;

		ConsiderForPruning(N);

if (WorklistMap.insert(std::make_pair(N, Worklist.size())).second)		if (WorklistMap.insert(std::make_pair(N, Worklist.size())).second)
Worklist.push_back(N);		Worklist.push_back(N);
}		}

/// Remove all instances of N from the worklist.		/// Remove all instances of N from the worklist.
void removeFromWorklist(SDNode *N) {		void removeFromWorklist(SDNode *N) {
CombinedNodes.erase(N);		CombinedNodes.erase(N);
		PruningList.remove(N);

auto It = WorklistMap.find(N);		auto It = WorklistMap.find(N);
if (It == WorklistMap.end())		if (It == WorklistMap.end())
return; // Not in the worklist.		return; // Not in the worklist.

// Null out the entry rather than erasing it to avoid a linear operation.		// Null out the entry rather than erasing it to avoid a linear operation.
Worklist[It->second] = nullptr;		Worklist[It->second] = nullptr;
WorklistMap.erase(It);		WorklistMap.erase(It);
▲ Show 20 Lines • Show All 449 Lines • ▼ Show 20 Lines

class WorklistInserter : public SelectionDAG::DAGUpdateListener {		class WorklistInserter : public SelectionDAG::DAGUpdateListener {
DAGCombiner &DC;		DAGCombiner &DC;

public:		public:
explicit WorklistInserter(DAGCombiner &dc)		explicit WorklistInserter(DAGCombiner &dc)
: SelectionDAG::DAGUpdateListener(dc.getDAG()), DC(dc) {}		: SelectionDAG::DAGUpdateListener(dc.getDAG()), DC(dc) {}

// This should eventually be pruning.		// FIXME: Ideally we could add N to the worklist, but this causes exponential
void NodeInserted(SDNode *N) override { }		// compile time costs in large DAGs, e.g. Halide.
		void NodeInserted(SDNode *N) override { DC.ConsiderForPruning(N); }
};		};

} // end anonymous namespace		} // end anonymous namespace

//===----------------------------------------------------------------------===//		//===----------------------------------------------------------------------===//
// TargetLowering::DAGCombinerInfo implementation		// TargetLowering::DAGCombinerInfo implementation
//===----------------------------------------------------------------------===//		//===----------------------------------------------------------------------===//

▲ Show 20 Lines • Show All 749 Lines • ▼ Show 20 Lines	void DAGCombiner::Run(CombineLevel AtLevel) {
for (SDNode &Node : DAG.allnodes())		for (SDNode &Node : DAG.allnodes())
AddToWorklist(&Node);		AddToWorklist(&Node);

// Create a dummy node (which is not added to allnodes), that adds a reference		// 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		// to the root node, preventing it from being deleted, and tracking any
// changes of the root.		// changes of the root.
HandleSDNode Dummy(DAG.getRoot());		HandleSDNode Dummy(DAG.getRoot());

// While the worklist isn't empty, find a node and try to combine it.		// While we have a valid worklist entry node, try to combine it.
while (!WorklistMap.empty()) {		while (SDNode *N = getNextWorklistEntry()) {
SDNode *N;
// The Worklist holds the SDNodes in order, but it may contain null entries.
do {
N = Worklist.pop_back_val();
} while (!N);

bool GoodWorklistEntry = WorklistMap.erase(N);
(void)GoodWorklistEntry;
assert(GoodWorklistEntry &&
"Found a worklist entry without a corresponding map entry!");

// If N has no uses, it is dead. Make sure to revisit all N's operands once		// If N has no uses, it is dead. Make sure to revisit all N's operands once
// N is deleted from the DAG, since they too may now be dead or may have a		// N is deleted from the DAG, since they too may now be dead or may have a
// reduced number of uses, allowing other xforms.		// reduced number of uses, allowing other xforms.
if (recursivelyDeleteUnusedNodes(N))		if (recursivelyDeleteUnusedNodes(N))
continue;		continue;

WorklistRemover DeadNodes(*this);		WorklistRemover DeadNodes(*this);

▲ Show 20 Lines • Show All 18,463 Lines • Show Last 20 Lines