Document SCC determinism

I've documented the guarantees that stronglyConnCompFromEdgedVertices
provides and commented on the call sites to explain why they are
OK from determinism standpoint. I've changed the functions to
nonDetUFM versions, so that it's explicit they could introduce
nondeterminism.  I haven't defined container (VarSet, NameSet)
specific versions, so that we have less functions to worry about.

Test Plan: this is mostly just documentation,
it should have no runtime effect

Reviewers: bgamari, simonmar, austin, simonpj

Reviewed By: simonpj

Subscribers: thomie

Differential Revision: https://phabricator.haskell.org/D2194

GHC Trac Issues: #4012

2 files changed, 25 insertions, 2 deletions

diff --git a/compiler/utils/Digraph.hs b/compiler/utils/Digraph.hs
index 2c90c1e41e..1d6ef24e61 100644
--- a/compiler/utils/Digraph.hs
+++ b/compiler/utils/Digraph.hs
@@ -94,6 +94,7 @@ type Node key payload = (payload, key, [key])
 emptyGraph :: Graph a
 emptyGraph = Graph (array (1, 0) []) (error "emptyGraph") (const Nothing)
 
+-- See Note [Deterministic SCC]
 graphFromEdgedVertices
         :: Ord key                      -- We only use Ord for efficiency,
                                         -- it doesn't effect the result, so
@@ -200,6 +201,18 @@ depend on earlier ones, but not vice versa i.e. later components only have
 edges going from them to earlier ones.
 -}
 
+{-
+Note [Deterministic SCC]
+~~~~~~~~~~~~~~~~~~~~~~~~
+stronglyConnCompFromEdgedVertices and stronglyConnCompFromEdgedVerticesR
+provide a following guarantee:
+Given a deterministically ordered list of nodes it returns a deterministically
+ordered list of strongly connected components, where the list of vertices
+in an SCC is also deterministically ordered.
+Note that the order of edges doesn't need to be deterministic for this to work.
+We use the order of nodes to normalize the order of edges.
+-}
+
 stronglyConnCompG :: Graph node -> [SCC node]
 stronglyConnCompG graph = decodeSccs graph forest
   where forest = {-# SCC "Digraph.scc" #-} scc (gr_int_graph graph)
@@ -216,6 +229,7 @@ decodeSccs Graph { gr_int_graph = graph, gr_vertex_to_node = vertex_fn } forest
 
 
 -- The following two versions are provided for backwards compatability:
+-- See Note [Deterministic SCC]
 stronglyConnCompFromEdgedVertices
         :: Ord key
         => [Node key payload]
@@ -226,6 +240,7 @@ stronglyConnCompFromEdgedVertices
 
 -- The "R" interface is used when you expect to apply SCC to
 -- (some of) the result of SCC, so you dont want to lose the dependency info
+-- See Note [Deterministic SCC]
 stronglyConnCompFromEdgedVerticesR
         :: Ord key
         => [Node key payload]
diff --git a/compiler/utils/UniqFM.hs b/compiler/utils/UniqFM.hs
index 590358ab40..2ff635268d 100644
--- a/compiler/utils/UniqFM.hs
+++ b/compiler/utils/UniqFM.hs
@@ -61,7 +61,7 @@ module UniqFM (
         isNullUFM,
         lookupUFM, lookupUFM_Directly,
         lookupWithDefaultUFM, lookupWithDefaultUFM_Directly,
-        nonDetEltsUFM, eltsUFM, keysUFM, splitUFM,
+        nonDetEltsUFM, eltsUFM, nonDetKeysUFM, keysUFM, splitUFM,
         ufmToSet_Directly,
         ufmToList, ufmToIntMap,
         joinUFM, pprUniqFM, pprUFM, pluralUFM
@@ -303,10 +303,18 @@ anyUFM p (UFM m) = M.fold ((||) . p) False m
 allUFM :: (elt -> Bool) -> UniqFM elt -> Bool
 allUFM p (UFM m) = M.fold ((&&) . p) True m
 
--- See Note [Deterministic UniqFM] to learn about nondeterminism
+-- See Note [Deterministic UniqFM] to learn about nondeterminism.
+-- If you use this please provide a justification why it doesn't introduce
+-- nondeterminism.
 nonDetEltsUFM :: UniqFM elt -> [elt]
 nonDetEltsUFM (UFM m) = M.elems m
 
+-- See Note [Deterministic UniqFM] to learn about nondeterminism.
+-- If you use this please provide a justification why it doesn't introduce
+-- nondeterminism.
+nonDetKeysUFM :: UniqFM elt -> [Unique]
+nonDetKeysUFM (UFM m) = map getUnique $ M.keys m
+
 ufmToIntMap :: UniqFM elt -> M.IntMap elt
 ufmToIntMap (UFM m) = m