MLIR  17.0.0git
RootOrdering.cpp File Reference
#include "RootOrdering.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/DenseSet.h"
#include "llvm/ADT/SmallVector.h"
#include <queue>
#include <utility>
Include dependency graph for RootOrdering.cpp:

Go to the source code of this file.

## Functions

static SmallVector< ValuegetCycle (const DenseMap< Value, Value > &parents, Value rep)
Returns the cycle implied by the specified parent relation, starting at the given node. More...

static void contract (RootOrderingGraph &graph, ArrayRef< Value > cycle, const DenseMap< Value, unsigned > &parentDepths, DenseMap< Value, Value > &actualSource, DenseMap< Value, Value > &actualTarget)
Contracts the specified cycle in the given graph in-place. More...

## ◆ contract()

 static void contract ( RootOrderingGraph & graph, ArrayRef< Value > cycle, const DenseMap< Value, unsigned > & parentDepths, DenseMap< Value, Value > & actualSource, DenseMap< Value, Value > & actualTarget )
static

Contracts the specified cycle in the given graph in-place.

The parentsCost map specifies, for each node in the cycle, the lowest cost among the edges entering that node. Then, the nodes in the cycle C are replaced with a single node v_C (the first node in the cycle). All edges (u, v) entering the cycle, v \in C, are replaced with a single edge (u, v_C) with an appropriately chosen cost, and the selected node v is marked in the output map actualTarget[u]. All edges (u, v) leaving the cycle, u \in C, are replaced with a single edge (v_C, v), and the selected node u is marked in the ouptut map actualSource[v].

Definition at line 48 of file RootOrdering.cpp.

## ◆ getCycle()

 static SmallVector getCycle ( const DenseMap< Value, Value > & parents, Value rep )
static

Returns the cycle implied by the specified parent relation, starting at the given node.

Definition at line 27 of file RootOrdering.cpp.

Referenced by mlir::pdl_to_pdl_interp::OptimalBranching::solve().