Merge pull request #1079 from freechipsproject/dependency-api

Add Dependency API

5 files changed, 1022 insertions, 19 deletions

diff --git a/src/main/scala/firrtl/Compiler.scala b/src/main/scala/firrtl/Compiler.scala
index c01564d2..b72fd4ce 100644
--- a/src/main/scala/firrtl/Compiler.scala
+++ b/src/main/scala/firrtl/Compiler.scala
@@ -11,7 +11,7 @@ import firrtl.annotations._
 import firrtl.ir.Circuit
 import firrtl.Utils.throwInternalError
 import firrtl.annotations.transforms.{EliminateTargetPaths, ResolvePaths}
-import firrtl.options.StageUtils
+import firrtl.options.{StageUtils, TransformLike}
 
 /** Container of all annotations for a Firrtl compiler */
 class AnnotationSeq private (private[firrtl] val underlying: List[Annotation]) {
@@ -169,7 +169,7 @@ final case object UnknownForm extends CircuitForm(-1) {
 // scalastyle:on magic.number
 
 /** The basic unit of operating on a Firrtl AST */
-abstract class Transform extends LazyLogging {
+abstract class Transform extends TransformLike[CircuitState] {
   /** A convenience function useful for debugging and error messages */
   def name: String = this.getClass.getSimpleName
   /** The [[firrtl.CircuitForm]] that this transform requires to operate on */
@@ -185,6 +185,8 @@ abstract class Transform extends LazyLogging {
     */
   protected def execute(state: CircuitState): CircuitState
 
+  def transform(state: CircuitState): CircuitState = execute(state)
+
   /** Convenience method to get annotations relevant to this Transform
     *
     * @param state The [[CircuitState]] form which to extract annotations
diff --git a/src/main/scala/firrtl/graph/DiGraph.scala b/src/main/scala/firrtl/graph/DiGraph.scala
index 1cac34b5..3fa0ade7 100644
--- a/src/main/scala/firrtl/graph/DiGraph.scala
+++ b/src/main/scala/firrtl/graph/DiGraph.scala
@@ -64,13 +64,14 @@ class DiGraph[T] private[graph] (private[graph] val edges: LinkedHashMap[T, Link
     */
   def findSinks: Set[T] = reverse.findSources
 
-  /** Linearizes (topologically sorts) a DAG
-    *
+  /** Linearizes (topologically sorts) a DAG using a DFS. This can be seeded with an order to use for the DFS if the user
+    * wants to tease out a special ordering of the DAG.
+    * @param seed an optional sequence of vertices to use. This will default to the vertices ordering provided by getVertices.
     * @throws CyclicException if the graph is cyclic
     * @return a Map[T,T] from each visited node to its predecessor in the
     * traversal
     */
-  def linearize: Seq[T] = {
+  def seededLinearize(seed: Option[Seq[T]] = None): Seq[T] = {
     // permanently marked nodes are implicitly held in order
     val order = new mutable.ArrayBuffer[T]
     // invariant: no intersection between unmarked and tempMarked
@@ -80,7 +81,7 @@ class DiGraph[T] private[graph] (private[graph] val edges: LinkedHashMap[T, Link
     case class LinearizeFrame[T](v: T, expanded: Boolean)
     val callStack = mutable.Stack[LinearizeFrame[T]]()
 
-    unmarked ++= getVertices
+    unmarked ++= seed.getOrElse(getVertices)
     while (unmarked.nonEmpty) {
       callStack.push(LinearizeFrame(unmarked.head, false))
       while (callStack.nonEmpty) {
@@ -133,6 +134,14 @@ class DiGraph[T] private[graph] (private[graph] val edges: LinkedHashMap[T, Link
     foundPath
   }
 
+  /** Linearizes (topologically sorts) a DAG
+    *
+    * @throws CyclicException if the graph is cyclic
+    * @return a Map[T,T] from each visited node to its predecessor in the
+    * traversal
+    */
+  def linearize: Seq[T] = seededLinearize(None)
+
   /** Performs breadth-first search on the directed graph
     *
     * @param root the start node
@@ -187,7 +196,7 @@ class DiGraph[T] private[graph] (private[graph] val edges: LinkedHashMap[T, Link
     * @return a Seq[T] of nodes defining an arbitrary valid path
     */
   def path(start: T, end: T): Seq[T] = path(start, end, Set.empty[T])
-  
+
   /** Finds a path (if one exists) from one node to another, with a blacklist
     *
     * @param start the start node
diff --git a/src/main/scala/firrtl/options/DependencyManager.scala b/src/main/scala/firrtl/options/DependencyManager.scala
new file mode 100644
index 00000000..2afc085d
--- /dev/null
+++ b/src/main/scala/firrtl/options/DependencyManager.scala
@@ -0,0 +1,363 @@
+// See LICENSE for license details.
+
+package firrtl.options
+
+import firrtl.AnnotationSeq
+import firrtl.graph.{DiGraph, CyclicException}
+
+import scala.collection.Set
+import scala.collection.immutable.{Set => ISet}
+import scala.collection.mutable.{ArrayBuffer, HashMap, LinkedHashMap, LinkedHashSet, Queue}
+
+/** An exception arising from an in a [[DependencyManager]] */
+case class DependencyManagerException(message: String, cause: Throwable = null) extends RuntimeException(message, cause)
+
+/** A [[firrtl.options.TransformLike TransformLike]] that resolves a linear ordering of dependencies based on
+  * requirements.
+  * @tparam A the type over which this transforms
+  * @tparam B the type of the [[firrtl.options.TransformLike TransformLike]]
+  */
+trait DependencyManager[A, B <: TransformLike[A] with DependencyAPI[B]] extends TransformLike[A] with DependencyAPI[B] {
+
+  /** Requested [[firrtl.options.TransformLike TransformLike]]s that should be run. Internally, this will be converted to
+    * a set based on the ordering defined here.
+    */
+  def targets: Seq[Class[B]]
+  private lazy val _targets: LinkedHashSet[Class[B]] = targets
+    .foldLeft(new LinkedHashSet[Class[B]]()){ case (a, b) => a += b }
+
+  /** A sequence of [[firrtl.Transform]]s that have been run. Internally, this will be converted to an ordered set.
+    */
+  def currentState: Seq[Class[B]]
+  private lazy val _currentState: LinkedHashSet[Class[B]] = currentState
+    .foldLeft(new LinkedHashSet[Class[B]]()){ case (a, b) => a += b }
+
+  /** Existing transform objects that have already been constructed */
+  def knownObjects: Set[B]
+
+  /** A sequence of wrappers to apply to the resulting [[firrtl.options.TransformLike TransformLike]] sequence. This can
+    * be used to, e.g., add automated pre-processing and post-processing.
+    */
+  def wrappers: Seq[(B) => B] = Seq.empty
+
+  /** Store of conversions between classes and objects. Objects that do not exist in the map will be lazily constructed.
+    */
+  protected lazy val classToObject: LinkedHashMap[Class[B], B] = {
+    val init = LinkedHashMap[Class[B], B](knownObjects.map(x => x.getClass.asInstanceOf[Class[B]] -> x).toSeq: _*)
+    (_targets ++ _currentState)
+      .filter(!init.contains(_))
+      .map(x => init(x) = safeConstruct(x))
+    init
+  }
+
+  /** A method that will create a copy of this [[firrtl.options.DependencyManager DependencyManager]], but with different
+    * requirements. This is used to solve sub-problems arising from invalidations.
+    */
+  protected def copy(
+    targets: Seq[Class[B]],
+    currentState: Seq[Class[B]],
+    knownObjects: ISet[B] = classToObject.values.toSet): B
+
+  /** Implicit conversion from Class[B] to B */
+  private implicit def cToO(c: Class[B]): B = classToObject.getOrElseUpdate(c, safeConstruct(c))
+
+  /** Implicit conversion from B to Class[B] */
+  private implicit def oToC(b: B): Class[B] = b.getClass.asInstanceOf[Class[B]]
+
+  /** Modified breadth-first search that supports multiple starting nodes and a custom extractor that can be used to
+    * generate/filter the edges to explore. Additionally, this will include edges to previously discovered nodes.
+    */
+  private def bfs( start: LinkedHashSet[Class[B]],
+                   blacklist: LinkedHashSet[Class[B]],
+                   extractor: B => Set[Class[B]] ): LinkedHashMap[B, LinkedHashSet[B]] = {
+
+    val (queue, edges) = {
+      val a: Queue[Class[B]]                    = Queue(start.toSeq:_*)
+      val b: LinkedHashMap[B, LinkedHashSet[B]] = LinkedHashMap[B, LinkedHashSet[B]](
+        start.map((cToO(_) -> LinkedHashSet[B]())).toSeq:_*)
+      (a, b)
+    }
+
+    while (queue.nonEmpty) {
+      val u: Class[B] = queue.dequeue
+      for (v: Class[B] <- extractor(classToObject(u))) {
+        if (!blacklist.contains(v) && !edges.contains(v)) {
+          queue.enqueue(v)
+        }
+        if (!edges.contains(v)) {
+          val obj = cToO(v)
+          edges(obj) = LinkedHashSet.empty
+          classToObject += (v -> obj)
+        }
+        edges(classToObject(u)) = edges(classToObject(u)) + classToObject(v)
+      }
+    }
+
+    edges
+  }
+
+  /** Pull in all registered [[firrtl.options.TransformLike TransformLike]] once [[firrtl.options.TransformLike
+    * TransformLike]] registration is integrated
+    * @todo implement this
+    */
+  private lazy val registeredTransforms: Set[B] = Set.empty
+
+  /** A directed graph consisting of prerequisite edges */
+  private lazy val prerequisiteGraph: DiGraph[B] = {
+    val edges = bfs(
+      start = _targets -- _currentState,
+      blacklist = _currentState,
+      extractor = (p: B) => new LinkedHashSet[Class[B]]() ++ p.prerequisites -- _currentState)
+    DiGraph(edges)
+  }
+
+  /** A directed graph consisting of prerequisites derived from only those transforms which are supposed to run. This
+    * pulls in dependents for transforms which are not in the target set.
+    */
+  private lazy val dependentsGraph: DiGraph[B] = {
+    val v = new LinkedHashSet() ++ prerequisiteGraph.getVertices
+    DiGraph(new LinkedHashMap() ++ v.map(vv => vv -> ((new LinkedHashSet() ++ vv.dependents).map(cToO) & v))).reverse
+  }
+
+  /** A directed graph consisting of prerequisites derived from ALL targets. This is necessary for defining targets for
+    * [[DependencyManager]] sub-problems.
+    */
+  private lazy val otherDependents: DiGraph[B] = {
+    val edges = {
+      val x = new LinkedHashMap ++ _targets
+        .map(classToObject)
+        .map{ a => a -> prerequisiteGraph.getVertices.filter(a._dependents(_)) }
+      x
+        .values
+        .reduce(_ ++ _)
+        .foldLeft(x){ case (xx, y) => if (xx.contains(y)) { xx } else { xx ++ Map(y -> Set.empty[B]) } }
+    }
+    DiGraph(edges).reverse
+  }
+
+  /** A directed graph consisting of all prerequisites, including prerequisites derived from dependents */
+  lazy val dependencyGraph: DiGraph[B] = prerequisiteGraph + dependentsGraph
+
+  /** A directed graph consisting of invalidation edges */
+  lazy val invalidateGraph: DiGraph[B] = {
+    val v = dependencyGraph.getVertices
+    DiGraph(
+      bfs(
+        start = _targets -- _currentState,
+        blacklist = _currentState,
+        extractor = (p: B) => v.filter(p.invalidates).map(_.asClass).toSet))
+      .reverse
+  }
+
+  /** Wrap a possible [[CyclicException]] thrown by a thunk in a [[DependencyManagerException]] */
+  private def cyclePossible[A](a: String, diGraph: DiGraph[_])(thunk: => A): A = try { thunk } catch {
+    case e: CyclicException =>
+      throw new DependencyManagerException(
+        s"""|No transform ordering possible due to cyclic dependency in $a with cycles:
+            |${diGraph.findSCCs.filter(_.size > 1).mkString("    - ", "\n    - ", "")}""".stripMargin, e)
+  }
+
+  /** Wrap an [[IllegalAccessException]] due to attempted object construction in a [[DependencyManagerException]] */
+  private def safeConstruct[A](a: Class[A]): A = try { a.newInstance } catch {
+    case e: IllegalAccessException => throw new DependencyManagerException(
+      s"Failed to construct '$a'! (Did you try to construct an object?)", e)
+    case e: InstantiationException => throw new DependencyManagerException(
+      s"Failed to construct '$a'! (Did you try to construct an inner class or a class with parameters?)", e)
+  }
+
+  /** An ordering of [[firrtl.options.TransformLike TransformLike]]s that causes the requested [[DependencyManager.targets
+    * targets]] to be executed starting from the [[DependencyManager.currentState currentState]]. This ordering respects
+    * prerequisites, dependents, and invalidates of all constituent [[firrtl.options.TransformLike TransformLike]]s.
+    * This uses an algorithm that attempts to reduce the number of re-lowerings due to invalidations. Re-lowerings are
+    * implemented as new [[DependencyManager]]s.
+    * @throws DependencyManagerException if a cycle exists in either the [[DependencyManager.dependencyGraph
+    * dependencyGraph]] or the [[DependencyManager.invalidateGraph invalidateGraph]].
+    */
+  lazy val transformOrder: Seq[B] = {
+
+    /* Topologically sort the dependency graph using the invalidate graph topological sort as a seed. This has the effect of
+     * reducing (perhaps minimizing?) the number of work re-lowerings.
+     */
+    val sorted = {
+      val seed = cyclePossible("invalidates", invalidateGraph){ invalidateGraph.linearize }.reverse
+
+      cyclePossible("prerequisites/dependents", dependencyGraph) {
+        dependencyGraph
+          .seededLinearize(Some(seed))
+          .reverse
+          .dropWhile(b => _currentState.contains(b))
+      }
+    }
+
+    val (state, lowerers) = {
+      /* [todo] Seq is inefficient here, but Array has ClassTag problems. Use something else? */
+      val (s, l) = sorted.foldLeft((_currentState, Seq[B]())){ case ((state, out), in) =>
+        /* The prerequisites are both prerequisites AND dependents. */
+        val prereqs = new LinkedHashSet() ++ in.prerequisites ++
+          dependencyGraph.getEdges(in).toSeq.map(oToC) ++
+          otherDependents.getEdges(in).toSeq.map(oToC)
+        val missing = (prereqs -- state)
+        val preprocessing: Option[B] = {
+          if (missing.nonEmpty) { Some(this.copy(prereqs.toSeq, state.toSeq)) }
+          else                  { None                                     }
+        }
+        ((state ++ missing + in).map(cToO).filterNot(in.invalidates).map(oToC), out ++ preprocessing :+ in)
+      }
+      val missing = (_targets -- s)
+      val postprocessing: Option[B] = {
+        if (missing.nonEmpty) { Some(this.copy(_targets.toSeq, s.toSeq)) }
+        else                  { None                        }
+      }
+
+      (s ++ missing, l ++ postprocessing)
+    }
+
+    if (!_targets.subsetOf(state)) {
+      throw new DependencyManagerException(
+        s"The final state ($state) did not include the requested targets (${targets})!")
+    }
+    lowerers
+  }
+
+  /** A version of the [[DependencyManager.transformOrder transformOrder]] that flattens the transforms of any internal
+    * [[DependencyManager]]s.
+    */
+  lazy val flattenedTransformOrder: Seq[B] = transformOrder.flatMap {
+    case p: DependencyManager[A, B] => p.flattenedTransformOrder
+    case p => Some(p)
+  }
+
+  final override def transform(annotations: A): A = {
+
+    /* A local store of each wrapper to it's underlying class. */
+    val wrapperToClass = new HashMap[B, Class[B]]
+
+    /* The determined, flat order of transforms is wrapped with surrounding transforms while populating wrapperToClass so
+     * that each wrapped transform object can be dereferenced to its underlying class. Each wrapped transform is then
+     * applied while tracking the state of the underlying A. If the state ever disagrees with a prerequisite, then this
+     * throws an exception.
+     */
+    flattenedTransformOrder
+      .map{ t =>
+        val w = wrappers.foldLeft(t){ case (tx, wrapper) => wrapper(tx) }
+        wrapperToClass += (w -> t)
+        w
+      }.foldLeft((annotations, _currentState)){ case ((a, state), t) =>
+          if (!t.prerequisites.toSet.subsetOf(state)) {
+            throw new DependencyManagerException(
+              s"""|Tried to execute '$t' for which run-time prerequisites were not satisfied:
+                  |  state: ${state.mkString("\n    -", "\n    -", "")}
+                  |  prerequisites: ${prerequisites.mkString("\n    -", "\n    -", "")}""".stripMargin)
+          }
+          (t.transform(a), ((state + wrapperToClass(t)).map(cToO).filterNot(t.invalidates).map(oToC)))
+      }._1
+  }
+
+  /** This colormap uses Colorbrewer's 4-class OrRd color scheme */
+  protected val colormap = Seq("#fef0d9", "#fdcc8a", "#fc8d59", "#d7301f")
+
+  /** Get a name of some [[firrtl.options.TransformLike TransformLike]] */
+  private def transformName(transform: B, suffix: String = ""): String = s""""${transform.name}$suffix""""
+
+  /** Convert all prerequisites, dependents, and invalidates to a Graphviz representation.
+    * @param file the name of the output file
+    */
+  def dependenciesToGraphviz: String = {
+
+    def toGraphviz(digraph: DiGraph[B], attributes: String = "", tab: String = "    "): Option[String] = {
+      val edges =
+        digraph
+          .getEdgeMap
+          .collect{ case (v, edges) if edges.nonEmpty => (v -> edges) }
+          .map{ case (v, edges) =>
+            s"""${transformName(v)} -> ${edges.map(e => transformName(e)).mkString("{ ", " ", " }")}""" }
+
+      if (edges.isEmpty) { None } else {
+        Some(
+          s"""|  { $attributes
+              |${edges.mkString(tab, "\n" + tab, "")}
+              |  }""".stripMargin
+        )
+      }
+    }
+
+    val connections =
+      Seq( (prerequisiteGraph, "edge []"),
+           (dependentsGraph,   """edge [color="#de2d26"]"""),
+           (invalidateGraph,   "edge [minlen=2,style=dashed,constraint=false]") )
+        .flatMap{ case (a, b) => toGraphviz(a, b) }
+        .mkString("\n")
+
+    val nodes =
+      (prerequisiteGraph + dependentsGraph + invalidateGraph + otherDependents)
+        .getVertices
+        .map(v => s"""${transformName(v)} [label="${v.getClass.getSimpleName}"]""")
+
+    s"""|digraph DependencyManager {
+        |  graph [rankdir=BT]
+        |  node [fillcolor="${colormap(0)}",style=filled,shape=box]
+        |${nodes.mkString("  ", "\n" + "  ", "")}
+        |$connections
+        |}
+        |""".stripMargin
+  }
+
+  def transformOrderToGraphviz(colormap: Seq[String] = colormap): String = {
+
+    def rotate[A](a: Seq[A]): Seq[A] = a match {
+      case Nil => Nil
+      case car :: cdr => cdr :+ car
+      case car => car
+    }
+
+    val sorted = ArrayBuffer.empty[String]
+
+    def rec(pm: DependencyManager[A, B], cm: Seq[String], tab: String = "", id: Int = 0): (String, Int) = {
+      var offset = id
+
+      val targets = pm._targets.toSeq.map(_.getSimpleName).mkString(", ")
+      val state = pm._currentState.toSeq.map(_.getSimpleName).mkString(", ")
+
+      val header = s"""|${tab}subgraph cluster_$id {
+                       |$tab  label="targets: $targets\\nstate: $state"
+                       |$tab  labeljust=l
+                       |$tab  node [fillcolor="${cm.head}"]""".stripMargin
+
+      val body = pm.transformOrder.map{
+        case a: DependencyManager[A, B] =>
+          val (str, d) = rec(a, rotate(cm), tab + "  ", offset + 1)
+          offset = d
+          str
+        case a =>
+          val name = s"""${transformName(a, "_" + id)}"""
+          sorted += name
+          s"""$tab  $name [label="${a.getClass.getSimpleName}"]"""
+      }.mkString("\n")
+
+      (Seq(header, body, s"$tab}").mkString("\n"), offset)
+    }
+
+    s"""|digraph DependencyManagerTransformOrder {
+        |  graph [rankdir=TB]
+        |  node [style=filled,shape=box]
+        |${rec(this, colormap, "  ")._1}
+        |  ${sorted.mkString(" -> ")}
+        |}""".stripMargin
+  }
+
+}
+
+/** A [[Phase]] that will ensure that some other [[Phase]]s and their prerequisites are executed.
+  *
+  * This tries to determine a phase ordering such that an [[AnnotationSeq]] ''output'' is produced that has had all of
+  * the requested [[Phase]] target transforms run without having them be invalidated.
+  * @param targets the [[Phase]]s you want to run
+  */
+class PhaseManager(
+  val targets: Seq[Class[Phase]],
+  val currentState: Seq[Class[Phase]] = Seq.empty,
+  val knownObjects: Set[Phase] = Set.empty) extends Phase with DependencyManager[AnnotationSeq, Phase] {
+
+  protected def copy(a: Seq[Class[Phase]], b: Seq[Class[Phase]], c: ISet[Phase]) = new PhaseManager(a, b, c)
+
+}
diff --git a/src/main/scala/firrtl/options/Phase.scala b/src/main/scala/firrtl/options/Phase.scala
index 7ed964e8..e5aa87ec 100644
--- a/src/main/scala/firrtl/options/Phase.scala
+++ b/src/main/scala/firrtl/options/Phase.scala
@@ -6,6 +6,7 @@ import firrtl.AnnotationSeq
 
 import logger.LazyLogging
 
+import scala.collection.mutable.LinkedHashSet
 
 /** A polymorphic mathematical transform
   * @tparam A the transformed type
@@ -23,15 +24,87 @@ trait TransformLike[A] extends LazyLogging {
 
 }
 
+/** Mixin that defines dependencies between [[firrtl.options.TransformLike TransformLike]]s (hereafter referred to as
+  * "transforms")
+  *
+  * This trait forms the basis of the Dependency API of the Chisel/FIRRTL Hardware Compiler Framework. Dependencies are
+  * defined in terms of prerequisistes, dependents, and invalidates. A prerequisite is a transform that must run before
+  * this transform. A dependent is a transform that must run ''after'' this transform. (This can be viewed as a means of
+  * injecting a prerequisite into some other transform.) Finally, invalidates define the set of transforms whose effects
+  * this transform undos/invalidates. (Invalidation then implies that a transform that is invalidated by this transform
+  * and needed by another transform will need to be re-run.)
+  *
+  * This Dependency API only defines dependencies. A concrete [[DependencyManager]] is expected to be used to statically
+  * resolve a linear ordering of transforms that satisfies dependency requirements.
+  * @tparam A some transform
+  * @define seqNote @note The use of a Seq here is to preserve input order. Internally, this will be converted to a private,
+  * ordered Set.
+  */
+trait DependencyAPI[A <: DependencyAPI[A]] { this: TransformLike[_] =>
+
+  /** All transform that must run before this transform
+    * $seqNote
+    */
+  def prerequisites: Seq[Class[A]] = Seq.empty
+  private[options] lazy val _prerequisites: LinkedHashSet[Class[A]] = new LinkedHashSet() ++ prerequisites.toSet
+
+  /** All transforms that must run ''after'' this transform
+    *
+    * ''This is a means of prerequisite injection into some other transform.'' Normally a transform will define its own
+    * prerequisites. Dependents exist for two main situations:
+    *
+    * First, they improve the composition of optional transforms. If some first transform is optional (e.g., an
+    * expensive validation check), you would like to be able to conditionally cause it to run. If it is listed as a
+    * prerequisite on some other, second transform then it must always run before that second transform. There's no way
+    * to turn it off. However, by listing the second transform as a dependent of the first transform, the first
+    * transform will only run (and be treated as a prerequisite of the second transform) if included in a list of target
+    * transforms that should be run.
+    *
+    * Second, an external library would like to inject some first transform before a second transform inside FIRRTL. In
+    * this situation, the second transform cannot have any knowledge of external libraries. The use of a dependent here
+    * allows for prerequisite injection into FIRRTL proper.
+    *
+    * @see [[firrtl.passes.CheckTypes]] for an example of an optional checking [[firrtl.Transform]]
+    * $seqNote
+    */
+  def dependents: Seq[Class[A]] = Seq.empty
+  private[options] lazy val _dependents: LinkedHashSet[Class[A]] = new LinkedHashSet() ++ dependents.toSet
+
+  /** A function that, given a transform will return true if this transform invalidates/undos the effects of the input
+    * transform
+    * @note Can a [[firrtl.options.Phase Phase]] ever invalidate itself?
+    */
+  def invalidates(a: A): Boolean = true
+
+  /** Helper method to return the underlying class */
+  final def asClass: Class[A] = this.getClass.asInstanceOf[Class[A]]
+
+  /** Implicit conversion that allows for terser specification of [[DependencyAPI.prerequisites prerequisites]] and
+    * [[DependencyAPI.dependents dependents]].
+    */
+  implicit def classHelper(a: Class[_ <: A]): Class[A] = a.asInstanceOf[Class[A]]
+
+}
+
+/** A trait indicating that no invalidations occur, i.e., all previous transforms are preserved
+  * @tparam A some [[TransformLike]]
+  */
+trait PreservesAll[A <: DependencyAPI[A]] { this: DependencyAPI[A] =>
+
+  override def invalidates(a: A): Boolean = false
+
+}
+
 /** A mathematical transformation of an [[AnnotationSeq]].
   *
-  * A [[Phase]] forms one unit in the Chisel/FIRRTL Hardware Compiler Framework (HCF). The HCF is built from a sequence
-  * of [[Phase]]s applied to an [[AnnotationSeq]]. Note that a [[Phase]] may consist of multiple phases internally.
+  * A [[firrtl.options.Phase Phase]] forms one unit in the Chisel/FIRRTL Hardware Compiler Framework (HCF). The HCF is
+  * built from a sequence of [[firrtl.options.Phase Phase]]s applied to an [[AnnotationSeq]]. Note that a
+  * [[firrtl.options.Phase Phase]] may consist of multiple phases internally.
   */
-abstract class Phase extends TransformLike[AnnotationSeq] {
+trait Phase extends TransformLike[AnnotationSeq] with DependencyAPI[Phase] {
 
-  /** The name of this [[Phase]]. This will be used to generate debug/error messages or when deleting annotations. This
-    * will default to the `simpleName` of the class.
+  /** The name of this [[firrtl.options.Phase Phase]]. This will be used to generate debug/error messages or when deleting
+    * annotations. This will default to the `simpleName` of the class.
     * @return this phase's name
     * @note Override this with your own implementation for different naming behavior.
     */
@@ -39,15 +112,15 @@ abstract class Phase extends TransformLike[AnnotationSeq] {
 
 }
 
-/** A [[TransformLike]] that internally ''translates'' the input type to some other type, transforms the internal type,
-  * and converts back to the original type.
+/** A [[firrtl.options.TransformLike TransformLike]] that internally ''translates'' the input type to some other type,
+  * transforms the internal type, and converts back to the original type.
   *
-  * This is intended to be used to insert a [[TransformLike]] parameterized by type `B` into a sequence of
-  * [[TransformLike]]s parameterized by type `A`.
-  * @tparam A the type of the [[TransformLike]]
+  * This is intended to be used to insert a [[firrtl.options.TransformLike TransformLike]] parameterized by type `B`
+  * into a sequence of [[firrtl.options.TransformLike TransformLike]]s parameterized by type `A`.
+  * @tparam A the type of the [[firrtl.options.TransformLike TransformLike]]
   * @tparam B the internal type
   */
-trait Translator[A, B] { this: TransformLike[A] =>
+trait Translator[A, B] extends TransformLike[A] {
 
   /** A method converting type `A` into type `B`
     * @param an object of type `A`
@@ -69,6 +142,6 @@ trait Translator[A, B] { this: TransformLike[A] =>
 
   /** Convert the input object to the internal type, transform the internal type, and convert back to the original type
     */
-  final def transform(a: A): A = internalTransform(a)
+  override final def transform(a: A): A = bToA(internalTransform(aToB(a)))
 
 }
diff --git a/src/test/scala/firrtlTests/options/PhaseManagerSpec.scala b/src/test/scala/firrtlTests/options/PhaseManagerSpec.scala
new file mode 100644
index 00000000..b68da0d8
--- /dev/null
+++ b/src/test/scala/firrtlTests/options/PhaseManagerSpec.scala
@@ -0,0 +1,556 @@
+// See LICENSE for license details.
+
+package firrtlTests.options
+
+import org.scalatest.{FlatSpec, Matchers}
+
+import firrtl.AnnotationSeq
+import firrtl.options.{DependencyManagerException, Phase, PhaseManager, PreservesAll}
+
+import java.io.{File, PrintWriter}
+
+import sys.process._
+
+trait IdentityPhase extends Phase {
+  def transform(annotations: AnnotationSeq): AnnotationSeq = annotations
+}
+
+/** Default [[Phase]] that has no prerequisites and invalidates nothing */
+class A extends IdentityPhase {
+
+  override def invalidates(phase: Phase): Boolean = false
+}
+
+/** [[Phase]] that requires [[A]] and invalidates nothing */
+class B extends IdentityPhase {
+  override def prerequisites: Seq[Class[Phase]] = Seq(classOf[A])
+  override def invalidates(phase: Phase): Boolean = false
+}
+
+/** [[Phase]] that requires [[B]] and invalidates nothing */
+class C extends IdentityPhase {
+  override def prerequisites: Seq[Class[Phase]] = Seq(classOf[A])
+  override def invalidates(phase: Phase): Boolean = false
+}
+
+/** [[Phase]] that requires [[A]] and invalidates [[A]] */
+class D extends IdentityPhase {
+  override def prerequisites: Seq[Class[Phase]] = Seq(classOf[A])
+  override def invalidates(phase: Phase): Boolean = phase match {
+    case _: A => true
+    case _ => false
+  }
+}
+
+/** [[Phase]] that requires [[B]] and invalidates nothing */
+class E extends IdentityPhase {
+  override def prerequisites: Seq[Class[Phase]] = Seq(classOf[B])
+  override def invalidates(phase: Phase): Boolean = false
+}
+
+/** [[Phase]] that requires [[B]] and [[C]] and invalidates [[E]] */
+class F extends IdentityPhase {
+  override def prerequisites: Seq[Class[Phase]] = Seq(classOf[B], classOf[C])
+  override def invalidates(phase: Phase): Boolean = phase match {
+    case _: E => true
+    case _ => false
+  }
+}
+
+
+/** [[Phase]] that requires [[C]] and invalidates [[F]] */
+class G extends IdentityPhase {
+  override def prerequisites: Seq[Class[Phase]] = Seq(classOf[C])
+  override def invalidates(phase: Phase): Boolean = phase match {
+    case _: F => true
+    case _ => false
+  }
+}
+
+class CyclicA extends IdentityPhase with PreservesAll[Phase] {
+  override def prerequisites: Seq[Class[Phase]] = Seq(classOf[CyclicB])
+}
+
+class CyclicB extends IdentityPhase with PreservesAll[Phase] {
+  override def prerequisites: Seq[Class[Phase]] = Seq(classOf[CyclicA])
+}
+
+class CyclicC extends IdentityPhase {
+  override def invalidates(a: Phase): Boolean = a match {
+    case _: CyclicD => true
+    case _ => false
+  }
+}
+
+class CyclicD extends IdentityPhase {
+  override def invalidates(a: Phase): Boolean = a match {
+    case _: CyclicC => true
+    case _ => false
+  }
+}
+
+object ComplicatedFixture {
+
+  class A extends IdentityPhase {
+    override def invalidates(phase: Phase): Boolean = false
+  }
+  class B extends IdentityPhase {
+    override def prerequisites: Seq[Class[Phase]] = Seq(classOf[A])
+    override def invalidates(phase: Phase): Boolean = false
+  }
+  class C extends IdentityPhase {
+    override def prerequisites: Seq[Class[Phase]] = Seq(classOf[A])
+    override def invalidates(phase: Phase): Boolean = phase match {
+      case _: B => true
+      case _ => false
+    }
+  }
+  class D extends IdentityPhase {
+    override def prerequisites: Seq[Class[Phase]] = Seq(classOf[B])
+    override def invalidates(phase: Phase): Boolean = phase match {
+      case _: C | _: E => true
+      case _ => false
+    }
+  }
+  class E extends IdentityPhase {
+    override def prerequisites: Seq[Class[Phase]] = Seq(classOf[B])
+    override def invalidates(phase: Phase): Boolean = false
+  }
+
+}
+
+object RepeatedAnalysisFixture {
+
+  trait InvalidatesAnalysis extends IdentityPhase {
+    override def invalidates(phase: Phase): Boolean = phase match {
+      case _: Analysis => true
+      case _ => false
+    }
+  }
+
+  class Analysis extends IdentityPhase {
+    override def invalidates(phase: Phase): Boolean = false
+  }
+  class A extends InvalidatesAnalysis {
+    override def prerequisites: Seq[Class[Phase]] = Seq(classOf[Analysis])
+  }
+  class B extends InvalidatesAnalysis {
+    override def prerequisites: Seq[Class[Phase]] = Seq(classOf[A], classOf[Analysis])
+  }
+  class C extends InvalidatesAnalysis {
+    override def prerequisites: Seq[Class[Phase]] = Seq(classOf[B], classOf[Analysis])
+  }
+
+}
+
+object InvertedAnalysisFixture {
+
+  class Analysis extends IdentityPhase {
+    override def invalidates(phase: Phase): Boolean = false
+  }
+  class A extends IdentityPhase {
+    override def prerequisites: Seq[Class[Phase]] = Seq(classOf[Analysis])
+    override def invalidates(phase: Phase): Boolean = phase match {
+      case _: Analysis => true
+      case _ => false
+    }
+  }
+  class B extends IdentityPhase {
+    override def prerequisites: Seq[Class[Phase]] = Seq(classOf[Analysis])
+    override def invalidates(phase: Phase): Boolean = phase match {
+      case _: Analysis | _: A => true
+      case _ => false
+    }
+  }
+  class C extends IdentityPhase {
+    override def prerequisites: Seq[Class[Phase]] = Seq(classOf[Analysis])
+    override def invalidates(phase: Phase): Boolean = phase match {
+      case _: Analysis | _: B => true
+      case _ => false
+    }
+  }
+
+}
+
+object DependentsFixture {
+
+  class First extends IdentityPhase {
+    override def invalidates(phase: Phase): Boolean = false
+  }
+
+  class Second extends IdentityPhase {
+    override val prerequisites: Seq[Class[Phase]] = Seq(classOf[First])
+    override def invalidates(phase: Phase): Boolean = false
+  }
+
+  /* This models a situation where a user has a custom Phase that they need to run before some other Phase. This is an
+   * abstract example of writing a Transform that cleans up combinational loops. This needs to run before combinational
+   * loop detection.
+   */
+  class Custom extends IdentityPhase {
+    override val prerequisites: Seq[Class[Phase]] = Seq(classOf[First])
+    override val dependents: Seq[Class[Phase]] = Seq(classOf[Second])
+    override def invalidates(phase: Phase): Boolean = false
+  }
+
+}
+
+object ChainedInvalidationFixture {
+
+  class A extends IdentityPhase {
+    override def invalidates(phase: Phase): Boolean = phase match {
+      case _: B => true
+      case _ => false
+    }
+  }
+  class B extends IdentityPhase {
+    override def invalidates(phase: Phase): Boolean = phase match {
+      case _: C => true
+      case _ => false
+    }
+  }
+  class C extends IdentityPhase {
+    override def invalidates(phase: Phase): Boolean = phase match {
+      case _: D => true
+      case _ => false
+    }
+  }
+  class D extends IdentityPhase {
+    override def invalidates(phase: Phase): Boolean = false
+  }
+  class E extends IdentityPhase {
+    override val prerequisites: Seq[Class[Phase]] = Seq(classOf[A], classOf[B], classOf[C], classOf[D])
+    override def invalidates(phase: Phase): Boolean = false
+  }
+
+}
+
+object UnrelatedFixture {
+
+  trait InvalidatesB8Dep { this: Phase =>
+    override def invalidates(a: Phase) = a match {
+      case _: B8Dep => true
+      case _        => false
+    }
+  }
+
+  class B0 extends IdentityPhase with InvalidatesB8Dep
+  class B1 extends IdentityPhase with PreservesAll[Phase]
+  class B2 extends IdentityPhase with PreservesAll[Phase]
+  class B3 extends IdentityPhase with PreservesAll[Phase]
+  class B4 extends IdentityPhase with PreservesAll[Phase]
+  class B5 extends IdentityPhase with PreservesAll[Phase]
+  class B6 extends IdentityPhase with PreservesAll[Phase]
+  class B7 extends IdentityPhase with PreservesAll[Phase]
+
+  class B8 extends IdentityPhase with PreservesAll[Phase]
+  class B9 extends IdentityPhase with PreservesAll[Phase]
+  class B10 extends IdentityPhase with PreservesAll[Phase]
+  class B11 extends IdentityPhase with PreservesAll[Phase]
+  class B12 extends IdentityPhase with PreservesAll[Phase]
+  class B13 extends IdentityPhase with PreservesAll[Phase]
+  class B14 extends IdentityPhase with PreservesAll[Phase]
+  class B15 extends IdentityPhase with PreservesAll[Phase]
+
+  class B6Sub extends B6 {
+    override val prerequisites = Seq(classOf[B6]).asInstanceOf[Seq[Class[Phase]]]
+    override val dependents = Seq(classOf[B7]).asInstanceOf[Seq[Class[Phase]]]
+  }
+
+  class B6_0 extends B6Sub
+  class B6_1 extends B6Sub
+  class B6_2 extends B6Sub
+  class B6_3 extends B6Sub
+  class B6_4 extends B6Sub
+  class B6_5 extends B6Sub
+  class B6_6 extends B6Sub
+  class B6_7 extends B6Sub
+  class B6_8 extends B6Sub
+  class B6_9 extends B6Sub
+  class B6_10 extends B6Sub
+  class B6_11 extends B6Sub
+  class B6_12 extends B6Sub
+  class B6_13 extends B6Sub
+  class B6_14 extends B6Sub
+  class B6_15 extends B6Sub
+
+  class B8Dep extends B8 {
+    override val dependents = Seq(classOf[B8]).asInstanceOf[Seq[Class[Phase]]]
+  }
+
+  class B8_0 extends B8Dep
+  class B8_1 extends B8Dep
+  class B8_2 extends B8Dep
+  class B8_3 extends B8Dep
+  class B8_4 extends B8Dep
+  class B8_5 extends B8Dep
+  class B8_6 extends B8Dep
+  class B8_7 extends B8Dep
+  class B8_8 extends B8Dep
+  class B8_9 extends B8Dep
+  class B8_10 extends B8Dep
+  class B8_11 extends B8Dep
+  class B8_12 extends B8Dep
+  class B8_13 extends B8Dep
+  class B8_14 extends B8Dep
+  class B8_15 extends B8Dep
+
+}
+
+class PhaseManagerSpec extends FlatSpec with Matchers {
+
+  def writeGraphviz(pm: PhaseManager, dir: String): Unit = {
+
+    /** Convert a Graphviz file to PNG using */
+    def maybeToPng(f: File): Unit = try {
+      s"dot -Tpng -O ${f}" !
+    } catch {
+      case _: java.io.IOException =>
+    }
+
+    val d = new File(dir)
+    d.mkdirs()
+
+    {
+      val f = new File(d + "/dependencyGraph.dot")
+      val w = new PrintWriter(f)
+      w.write(pm.dependenciesToGraphviz)
+      w.close
+      maybeToPng(f)
+    }
+
+    {
+      val f = new File(d + "/transformOrder.dot")
+      val w = new PrintWriter(new File(d + "/transformOrder.dot"))
+      try {
+        w.write(pm.transformOrderToGraphviz())
+        w.close
+        maybeToPng(f)
+      } catch {
+        case _: DependencyManagerException =>
+      }
+    }
+
+  }
+
+  implicit def f(a: Class[_ <: Phase]): Class[Phase] = a.asInstanceOf[Class[Phase]]
+
+  behavior of this.getClass.getName
+
+  it should "do nothing if all targets are reached" in {
+    val targets: Seq[Class[Phase]] = Seq(classOf[A], classOf[B], classOf[C], classOf[D])
+    val pm = new PhaseManager(targets, targets)
+
+    writeGraphviz(pm, "test_run_dir/PhaseManagerSpec/DoNothing")
+
+    pm.flattenedTransformOrder should be (empty)
+  }
+
+  it should "handle a simple dependency" in {
+    val targets: Seq[Class[Phase]] = Seq(classOf[B])
+    val order: Seq[Class[Phase]] = Seq(classOf[A], classOf[B])
+    val pm = new PhaseManager(targets)
+
+    writeGraphviz(pm, "test_run_dir/PhaseManagerSpec/SimpleDependency")
+
+    pm.flattenedTransformOrder.map(_.asClass) should be (order)
+  }
+
+  it should "handle a simple dependency with an invalidation" in {
+    val targets: Seq[Class[Phase]] = Seq(classOf[A], classOf[B], classOf[C], classOf[D])
+    val order: Seq[Class[Phase]] = Seq(classOf[A], classOf[D], classOf[A], classOf[B], classOf[C])
+    val pm = new PhaseManager(targets)
+
+    writeGraphviz(pm, "test_run_dir/PhaseManagerSpec/OneInvalidate")
+
+    pm.flattenedTransformOrder.map(_.asClass) should be (order)
+  }
+
+  it should "handle a dependency with two invalidates optimally" in {
+    val targets: Seq[Class[Phase]] = Seq(classOf[A], classOf[B], classOf[C], classOf[E], classOf[F], classOf[G])
+    val pm = new PhaseManager(targets)
+
+    writeGraphviz(pm, "test_run_dir/PhaseManagerSpec/TwoInvalidates")
+
+    pm.flattenedTransformOrder.size should be (targets.size)
+  }
+
+  it should "throw an exception for cyclic prerequisites" in {
+    val targets: Seq[Class[Phase]] = Seq(classOf[CyclicA], classOf[CyclicB])
+    val pm = new PhaseManager(targets)
+
+    writeGraphviz(pm, "test_run_dir/PhaseManagerSpec/CyclicPrerequisites")
+
+    intercept[DependencyManagerException]{ pm.flattenedTransformOrder }
+      .getMessage should startWith ("No transform ordering possible")
+  }
+
+  it should "throw an exception for cyclic invalidates" in {
+    val targets: Seq[Class[Phase]] = Seq(classOf[CyclicC], classOf[CyclicD])
+    val pm = new PhaseManager(targets)
+
+    writeGraphviz(pm, "test_run_dir/PhaseManagerSpec/CyclicInvalidates")
+
+    intercept[DependencyManagerException]{ pm.flattenedTransformOrder }
+      .getMessage should startWith ("No transform ordering possible")
+  }
+
+  it should "handle a complicated graph" in {
+    val f = ComplicatedFixture
+    val targets: Seq[Class[Phase]] = Seq(classOf[f.A], classOf[f.B], classOf[f.C], classOf[f.D], classOf[f.E])
+      .map(_.asInstanceOf[Class[Phase]])
+    val pm = new PhaseManager(targets)
+
+    writeGraphviz(pm, "test_run_dir/PhaseManagerSpec/Complicated")
+
+    info("only one phase was recomputed")
+    pm.flattenedTransformOrder.size should be (targets.size + 1)
+  }
+
+  it should "handle repeated recomputed analyses" in {
+    val f = RepeatedAnalysisFixture
+    val targets: Seq[Class[Phase]] = Seq(classOf[f.A], classOf[f.B], classOf[f.C])
+      .map(_.asInstanceOf[Class[Phase]])
+    val order: Seq[Class[Phase]] =
+      Seq( classOf[f.Analysis],
+           classOf[f.A],
+           classOf[f.Analysis],
+           classOf[f.B],
+           classOf[f.Analysis],
+           classOf[f.C])
+        .map(_.asInstanceOf[Class[Phase]])
+    val pm = new PhaseManager(targets)
+
+    writeGraphviz(pm, "test_run_dir/PhaseManagerSpec/RepeatedAnalysis")
+
+    pm.flattenedTransformOrder.map(_.asClass) should be (order)
+  }
+
+  it should "handle inverted repeated recomputed analyses" in {
+    val f = InvertedAnalysisFixture
+    val targets: Seq[Class[Phase]] = Seq(classOf[f.A], classOf[f.B], classOf[f.C])
+      .map(_.asInstanceOf[Class[Phase]])
+    val order: Seq[Class[Phase]] =
+      Seq( classOf[f.Analysis],
+           classOf[f.C],
+           classOf[f.Analysis],
+           classOf[f.B],
+           classOf[f.Analysis],
+           classOf[f.A])
+        .map(_.asInstanceOf[Class[Phase]])
+    val pm = new PhaseManager(targets)
+
+    writeGraphviz(pm, "test_run_dir/PhaseManagerSpec/InvertedRepeatedAnalysis")
+
+    pm.flattenedTransformOrder.map(_.asClass) should be (order)
+  }
+
+  /** This test shows how the dependents member can be used to run one transform before another. */
+  it should "handle a custom Phase with a dependent" in {
+    val f = DependentsFixture
+
+    info("without the custom transform it runs: First -> Second")
+    val pm = new PhaseManager(Seq(classOf[f.Second]).map(_.asInstanceOf[Class[Phase]]))
+    val orderNoCustom: Seq[Class[Phase]] = Seq(classOf[f.First], classOf[f.Second])
+      .map(_.asInstanceOf[Class[Phase]])
+    pm.flattenedTransformOrder.map(_.asClass) should be (orderNoCustom)
+
+    info("with the custom transform it runs:    First -> Custom -> Second")
+    val pmCustom = new PhaseManager(Seq(classOf[f.Custom], classOf[f.Second]).map(_.asInstanceOf[Class[Phase]]))
+    val orderCustom: Seq[Class[Phase]] = Seq(classOf[f.First], classOf[f.Custom], classOf[f.Second])
+      .map(_.asInstanceOf[Class[Phase]])
+
+    writeGraphviz(pmCustom, "test_run_dir/PhaseManagerSpec/SingleDependent")
+
+    pmCustom.flattenedTransformOrder.map(_.asClass) should be (orderCustom)
+  }
+
+  it should "handle chained invalidation" in {
+    val f = ChainedInvalidationFixture
+
+    val targets: Seq[Class[Phase]] = Seq(classOf[f.A], classOf[f.E])
+      .map(_.asInstanceOf[Class[Phase]])
+    val current: Seq[Class[Phase]] = Seq(classOf[f.B], classOf[f.C], classOf[f.D]).map(_.asInstanceOf[Class[Phase]])
+
+    val pm = new PhaseManager(targets, current)
+    val order: Seq[Class[Phase]] = Seq( classOf[f.A], classOf[f.B], classOf[f.C], classOf[f.D], classOf[f.E] )
+      .map(_.asInstanceOf[Class[Phase]])
+
+    writeGraphviz(pm, "test_run_dir/PhaseManagerSpec/ChainedInvalidate")
+
+    pm.flattenedTransformOrder.map(_.asClass) should be (order)
+  }
+
+  it should "maintain the order of input targets" in {
+    val f = UnrelatedFixture
+
+    /** A bunch of unrelated Phases. This ensures that these run in the order in which they are specified. */
+    val targets =
+      Seq( classOf[f.B0],
+           classOf[f.B1],
+           classOf[f.B2],
+           classOf[f.B3],
+           classOf[f.B4],
+           classOf[f.B5],
+           classOf[f.B6],
+           classOf[f.B7],
+           classOf[f.B8],
+           classOf[f.B9],
+           classOf[f.B10],
+           classOf[f.B11],
+           classOf[f.B12],
+           classOf[f.B13],
+           classOf[f.B14],
+           classOf[f.B15] ).asInstanceOf[Seq[Class[Phase]]]
+    /** A sequence of custom transforms that should all run after B6 and before B7. This exercises correct ordering of the
+      * prerequisiteGraph and dependentsGraph.
+      */
+    val prerequisiteTargets =
+      Seq( classOf[f.B6_0],
+           classOf[f.B6_1],
+           classOf[f.B6_2],
+           classOf[f.B6_3],
+           classOf[f.B6_4],
+           classOf[f.B6_5],
+           classOf[f.B6_6],
+           classOf[f.B6_7],
+           classOf[f.B6_8],
+           classOf[f.B6_9],
+           classOf[f.B6_10],
+           classOf[f.B6_11],
+           classOf[f.B6_12],
+           classOf[f.B6_13],
+           classOf[f.B6_14],
+           classOf[f.B6_15] ).asInstanceOf[Seq[Class[Phase]]]
+    /** A sequence of transforms that are invalidated by B0 and only define dependents on B8. This exercises the ordering
+      * defined by "otherDependents".
+      */
+    val current =
+      Seq( classOf[f.B8_0],
+           classOf[f.B8_1],
+           classOf[f.B8_2],
+           classOf[f.B8_3],
+           classOf[f.B8_4],
+           classOf[f.B8_5],
+           classOf[f.B8_6],
+           classOf[f.B8_7],
+           classOf[f.B8_8],
+           classOf[f.B8_9],
+           classOf[f.B8_10],
+           classOf[f.B8_11],
+           classOf[f.B8_12],
+           classOf[f.B8_13],
+           classOf[f.B8_14],
+           classOf[f.B8_15] ).asInstanceOf[Seq[Class[Phase]]]
+
+    /** The resulting order: B0--B6, B6_0--B6_B15, B7, B8_0--B8_15, B8--B15 */
+    val expected = targets.slice(0, 7) ++ prerequisiteTargets ++ Some(targets(7)) ++ current ++ targets.drop(8)
+
+    val pm = new PhaseManager(targets ++ prerequisiteTargets ++ current, current.reverse)
+
+    writeGraphviz(pm, "test_run_dir/PhaseManagerSpec/DeterministicOrder")
+
+    pm.flattenedTransformOrder.map(_.asClass) should be (expected)
+  }
+
+}