<?xml version="1.0" encoding="UTF-8"?>
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
<html>
<head>
<!-- Generated by HsColour, http://www.cs.york.ac.uk/fp/darcs/hscolour/ -->
<title>cmm/ZipCfg.hs</title>
<link type='text/css' rel='stylesheet' href='hscolour.css' />
</head>
<body>
<pre><a name="line-1"></a><span class='hs-keyword'>module</span> <span class='hs-conid'>ZipCfg</span>
<a name="line-2"></a> <span class='hs-layout'>(</span> <span class='hs-comment'>-- These data types and names are carefully thought out</span>
<a name="line-3"></a> <span class='hs-conid'>Graph</span><span class='hs-layout'>(</span><span class='hs-keyglyph'>..</span><span class='hs-layout'>)</span><span class='hs-layout'>,</span> <span class='hs-conid'>LGraph</span><span class='hs-layout'>(</span><span class='hs-keyglyph'>..</span><span class='hs-layout'>)</span><span class='hs-layout'>,</span> <span class='hs-conid'>FGraph</span><span class='hs-layout'>(</span><span class='hs-keyglyph'>..</span><span class='hs-layout'>)</span>
<a name="line-4"></a> <span class='hs-layout'>,</span> <span class='hs-conid'>Block</span><span class='hs-layout'>(</span><span class='hs-keyglyph'>..</span><span class='hs-layout'>)</span><span class='hs-layout'>,</span> <span class='hs-conid'>ZBlock</span><span class='hs-layout'>(</span><span class='hs-keyglyph'>..</span><span class='hs-layout'>)</span><span class='hs-layout'>,</span> <span class='hs-conid'>ZHead</span><span class='hs-layout'>(</span><span class='hs-keyglyph'>..</span><span class='hs-layout'>)</span><span class='hs-layout'>,</span> <span class='hs-conid'>ZTail</span><span class='hs-layout'>(</span><span class='hs-keyglyph'>..</span><span class='hs-layout'>)</span><span class='hs-layout'>,</span> <span class='hs-conid'>ZLast</span><span class='hs-layout'>(</span><span class='hs-keyglyph'>..</span><span class='hs-layout'>)</span>
<a name="line-5"></a> <span class='hs-layout'>,</span> <span class='hs-varid'>insertBlock</span>
<a name="line-6"></a> <span class='hs-layout'>,</span> <span class='hs-conid'>HavingSuccessors</span><span class='hs-layout'>,</span> <span class='hs-varid'>succs</span><span class='hs-layout'>,</span> <span class='hs-varid'>fold_succs</span>
<a name="line-7"></a> <span class='hs-layout'>,</span> <span class='hs-conid'>LastNode</span><span class='hs-layout'>,</span> <span class='hs-varid'>mkBranchNode</span><span class='hs-layout'>,</span> <span class='hs-varid'>isBranchNode</span><span class='hs-layout'>,</span> <span class='hs-varid'>branchNodeTarget</span>
<a name="line-8"></a>
<a name="line-9"></a> <span class='hs-comment'>-- Observers and transformers</span>
<a name="line-10"></a> <span class='hs-comment'>-- (open to renaming suggestions here)</span>
<a name="line-11"></a> <span class='hs-layout'>,</span> <span class='hs-varid'>blockId</span><span class='hs-layout'>,</span> <span class='hs-varid'>zip</span><span class='hs-layout'>,</span> <span class='hs-varid'>unzip</span><span class='hs-layout'>,</span> <span class='hs-varid'>last</span><span class='hs-layout'>,</span> <span class='hs-varid'>goto_end</span><span class='hs-layout'>,</span> <span class='hs-varid'>zipht</span><span class='hs-layout'>,</span> <span class='hs-varid'>tailOfLast</span>
<a name="line-12"></a> <span class='hs-layout'>,</span> <span class='hs-varid'>splice_tail</span><span class='hs-layout'>,</span> <span class='hs-varid'>splice_head</span><span class='hs-layout'>,</span> <span class='hs-varid'>splice_head_only'</span><span class='hs-layout'>,</span> <span class='hs-varid'>splice_head'</span>
<a name="line-13"></a> <span class='hs-layout'>,</span> <span class='hs-varid'>of_block_list</span><span class='hs-layout'>,</span> <span class='hs-varid'>to_block_list</span>
<a name="line-14"></a> <span class='hs-layout'>,</span> <span class='hs-varid'>graphOfLGraph</span>
<a name="line-15"></a> <span class='hs-layout'>,</span> <span class='hs-varid'>map_blocks</span><span class='hs-layout'>,</span> <span class='hs-varid'>map_one_block</span><span class='hs-layout'>,</span> <span class='hs-varid'>map_nodes</span><span class='hs-layout'>,</span> <span class='hs-varid'>mapM_blocks</span>
<a name="line-16"></a> <span class='hs-layout'>,</span> <span class='hs-varid'>postorder_dfs</span><span class='hs-layout'>,</span> <span class='hs-varid'>postorder_dfs_from</span><span class='hs-layout'>,</span> <span class='hs-varid'>postorder_dfs_from_except</span>
<a name="line-17"></a> <span class='hs-layout'>,</span> <span class='hs-varid'>fold_layout</span>
<a name="line-18"></a> <span class='hs-layout'>,</span> <span class='hs-varid'>fold_blocks</span><span class='hs-layout'>,</span> <span class='hs-varid'>fold_fwd_block</span>
<a name="line-19"></a> <span class='hs-layout'>,</span> <span class='hs-varid'>translate</span>
<a name="line-20"></a>
<a name="line-21"></a> <span class='hs-layout'>,</span> <span class='hs-varid'>pprLgraph</span><span class='hs-layout'>,</span> <span class='hs-varid'>pprGraph</span>
<a name="line-22"></a>
<a name="line-23"></a> <span class='hs-layout'>,</span> <span class='hs-varid'>entry</span> <span class='hs-comment'>-- exported for the convenience of ZipDataflow0, at least for now</span>
<a name="line-24"></a>
<a name="line-25"></a> <span class='hs-comment'>{-
<a name="line-26"></a> -- the following functions might one day be useful and can be found
<a name="line-27"></a> -- either below or in ZipCfgExtras:
<a name="line-28"></a> , entry, exit, focus, focusp, unfocus
<a name="line-29"></a> , ht_to_block, ht_to_last,
<a name="line-30"></a> , splice_focus_entry, splice_focus_exit
<a name="line-31"></a> , foldM_fwd_block
<a name="line-32"></a> -}</span>
<a name="line-33"></a>
<a name="line-34"></a> <span class='hs-layout'>)</span>
<a name="line-35"></a><span class='hs-keyword'>where</span>
<a name="line-36"></a>
<a name="line-37"></a><span class='hs-cpp'>#include "HsVersions.h"</span>
<a name="line-38"></a>
<a name="line-39"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>BlockId</span> <span class='hs-layout'>(</span> <span class='hs-conid'>BlockId</span><span class='hs-layout'>,</span> <span class='hs-conid'>BlockEnv</span><span class='hs-layout'>,</span> <span class='hs-varid'>emptyBlockEnv</span><span class='hs-layout'>,</span> <span class='hs-varid'>lookupBlockEnv</span><span class='hs-layout'>,</span> <span class='hs-varid'>extendBlockEnv</span>
<a name="line-40"></a> <span class='hs-layout'>,</span> <span class='hs-conid'>BlockSet</span><span class='hs-layout'>,</span> <span class='hs-varid'>emptyBlockSet</span><span class='hs-layout'>,</span> <span class='hs-varid'>unitBlockSet</span><span class='hs-layout'>,</span> <span class='hs-varid'>elemBlockSet</span><span class='hs-layout'>,</span> <span class='hs-varid'>extendBlockSet</span>
<a name="line-41"></a> <span class='hs-layout'>,</span> <span class='hs-varid'>delFromBlockEnv</span><span class='hs-layout'>,</span> <span class='hs-varid'>foldBlockEnv'</span><span class='hs-layout'>,</span> <span class='hs-varid'>mapBlockEnv</span>
<a name="line-42"></a> <span class='hs-layout'>,</span> <span class='hs-varid'>eltsBlockEnv</span><span class='hs-layout'>,</span> <span class='hs-varid'>isNullBEnv</span><span class='hs-layout'>,</span> <span class='hs-varid'>plusBlockEnv</span><span class='hs-layout'>)</span>
<a name="line-43"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>CmmExpr</span> <span class='hs-layout'>(</span> <span class='hs-conid'>UserOfLocalRegs</span><span class='hs-layout'>(</span><span class='hs-keyglyph'>..</span><span class='hs-layout'>)</span> <span class='hs-layout'>)</span>
<a name="line-44"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>PprCmm</span><span class='hs-conid'>()</span>
<a name="line-45"></a>
<a name="line-46"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>Outputable</span> <span class='hs-varid'>hiding</span> <span class='hs-layout'>(</span><span class='hs-varid'>empty</span><span class='hs-layout'>)</span>
<a name="line-47"></a>
<a name="line-48"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>Data</span><span class='hs-varop'>.</span><span class='hs-conid'>Maybe</span>
<a name="line-49"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>Prelude</span> <span class='hs-varid'>hiding</span> <span class='hs-layout'>(</span><span class='hs-varid'>zip</span><span class='hs-layout'>,</span> <span class='hs-varid'>unzip</span><span class='hs-layout'>,</span> <span class='hs-varid'>last</span><span class='hs-layout'>)</span>
<a name="line-50"></a>
<a name="line-51"></a><span class='hs-comment'>-------------------------------------------------------------------------</span>
<a name="line-52"></a><span class='hs-comment'>-- GENERIC ZIPPER-BASED CONTROL-FLOW GRAPH --</span>
<a name="line-53"></a><span class='hs-comment'>-------------------------------------------------------------------------</span>
<a name="line-54"></a><span class='hs-comment'>{-
<a name="line-55"></a>
<a name="line-56"></a>This module defines datatypes used to represent control-flow graphs,
<a name="line-57"></a>along with some functions for analyzing and splicing graphs.
<a name="line-58"></a>Functions for building graphs are found in a separate module 'MkZipCfg'.
<a name="line-59"></a>
<a name="line-60"></a>Every graph has a distinguished entry point. A graph has at least one
<a name="line-61"></a>exit; most exits are instructions (or statements) like 'jump' or
<a name="line-62"></a>'return', which transfer control to other procedures, but a graph may
<a name="line-63"></a>have up to one 'fall through' exit. (A graph that represents an
<a name="line-64"></a>entire Haskell or C-- procedure does not have a 'fall through' exit.)
<a name="line-65"></a>
<a name="line-66"></a>A graph is a collection of basic blocks. A basic block begins with a
<a name="line-67"></a>label (unique id; see Note [Unique BlockId]) which is followed by a
<a name="line-68"></a>sequence of zero or more 'middle' nodes; the basic block ends with a
<a name="line-69"></a>'last' node. Each 'middle' node is a single-entry, single-exit,
<a name="line-70"></a>uninterruptible computation. A 'last' node is a single-entry,
<a name="line-71"></a>multiple-exit computation. A last node may have zero or more successors,
<a name="line-72"></a>which are identified by their unique ids.
<a name="line-73"></a>
<a name="line-74"></a>A special case of last node is the ``default exit,'' which represents
<a name="line-75"></a>'falling off the end' of the graph. Such a node is always represented by
<a name="line-76"></a>the data constructor 'LastExit'. A graph may contain at most one
<a name="line-77"></a>'LastExit' node, and a graph representing a full procedure should not
<a name="line-78"></a>contain any 'LastExit' nodes. 'LastExit' nodes are used only to splice
<a name="line-79"></a>graphs together, either during graph construction (see module 'MkZipCfg')
<a name="line-80"></a>or during optimization (see module 'ZipDataflow').
<a name="line-81"></a>
<a name="line-82"></a>A graph is parameterized over the types of middle and last nodes. Each of
<a name="line-83"></a>these types will typically be instantiated with a subset of C-- statements
<a name="line-84"></a>(see module 'ZipCfgCmmRep') or a subset of machine instructions (yet to be
<a name="line-85"></a>implemented as of August 2007).
<a name="line-86"></a>
<a name="line-87"></a>
<a name="line-88"></a>Note [Kinds of Graphs]
<a name="line-89"></a>~~~~~~~~~~~~~~~~~~~~~~
<a name="line-90"></a>This module exposes three representations of graphs. In order of
<a name="line-91"></a>increasing complexity, they are:
<a name="line-92"></a>
<a name="line-93"></a> Graph m l The basic graph with its distinguished entry point
<a name="line-94"></a>
<a name="line-95"></a> LGraph m l A graph with a *labelled* entry point
<a name="line-96"></a>
<a name="line-97"></a> FGraph m l A labelled graph with the *focus* on a particular edge
<a name="line-98"></a>
<a name="line-99"></a>There are three types because each type offers a slightly different
<a name="line-100"></a>invariant or cost model.
<a name="line-101"></a>
<a name="line-102"></a> * The distinguished entry of a Graph has no label. Because labels must be
<a name="line-103"></a> unique, acquiring one requires a supply of Unique labels (BlockId's).
<a name="line-104"></a> The primary advantage of the Graph representation is that we can build a
<a name="line-105"></a> small Graph purely functionally, without needing a fresh BlockId or
<a name="line-106"></a> Unique. For example, during optimization we can easily rewrite a single
<a name="line-107"></a> middle node into a Graph containing a sequence of two middle nodes
<a name="line-108"></a> followed by LastExit.
<a name="line-109"></a>
<a name="line-110"></a> * In an LGraph, every basic block is labelled. The primary advantage of
<a name="line-111"></a> this representation is its simplicity: each basic block can be treated
<a name="line-112"></a> like any other. This representation is used for mapping, folding, and
<a name="line-113"></a> translation, as well as layout.
<a name="line-114"></a>
<a name="line-115"></a> Like any graph, an LGraph still has a distinguished entry point,
<a name="line-116"></a> which you can discover using 'lg_entry'.
<a name="line-117"></a>
<a name="line-118"></a> * An FGraph is an LGraph with the *focus* on one particular edge. The
<a name="line-119"></a> primary advantage of this representation is that it provides
<a name="line-120"></a> constant-time access to the nodes connected by that edge, and it also
<a name="line-121"></a> allows constant-time, functional *replacement* of those nodes---in the
<a name="line-122"></a> style of Huet's 'zipper'.
<a name="line-123"></a>
<a name="line-124"></a>None of these representations is ideally suited to the incremental
<a name="line-125"></a>construction of large graphs. A separate module, 'MkZipCfg', provides a
<a name="line-126"></a>fourth representation that is asymptotically optimal for such construction.
<a name="line-127"></a>
<a name="line-128"></a>-}</span>
<a name="line-129"></a>
<a name="line-130"></a><span class='hs-comment'>--------------- Representation --------------------</span>
<a name="line-131"></a>
<a name="line-132"></a><span class='hs-comment'>-- | A basic block is a 'first' node, followed by zero or more 'middle'</span>
<a name="line-133"></a><span class='hs-comment'>-- nodes, followed by a 'last' node.</span>
<a name="line-134"></a>
<a name="line-135"></a><span class='hs-comment'>-- eventually this module should probably replace the original Cmm, but for</span>
<a name="line-136"></a><span class='hs-comment'>-- now we leave it to dynamic invariants what can be found where</span>
<a name="line-137"></a>
<a name="line-138"></a><a name="ZLast"></a><span class='hs-keyword'>data</span> <span class='hs-conid'>ZLast</span> <span class='hs-varid'>l</span>
<a name="line-139"></a> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>LastExit</span> <span class='hs-comment'>-- fall through; used for the block that has no last node</span>
<a name="line-140"></a> <span class='hs-comment'>-- LastExit is a device used only for graphs under </span>
<a name="line-141"></a> <span class='hs-comment'>-- construction, or framgments of graph under optimisation,</span>
<a name="line-142"></a> <span class='hs-comment'>-- so we don't want to pollute the 'l' type parameter with it</span>
<a name="line-143"></a> <span class='hs-keyglyph'>|</span> <span class='hs-conid'>LastOther</span> <span class='hs-varid'>l</span>
<a name="line-144"></a>
<a name="line-145"></a><span class='hs-comment'>--So that we don't have orphan instances, this goes here or in CmmExpr.</span>
<a name="line-146"></a><span class='hs-comment'>--At least UserOfLocalRegs (ZLast Last) is needed (Last defined elsewhere),</span>
<a name="line-147"></a><span class='hs-comment'>--but there's no need for non-Haskell98 instances for that.</span>
<a name="line-148"></a><span class='hs-keyword'>instance</span> <span class='hs-conid'>UserOfLocalRegs</span> <span class='hs-varid'>a</span> <span class='hs-keyglyph'>=></span> <span class='hs-conid'>UserOfLocalRegs</span> <span class='hs-layout'>(</span><span class='hs-conid'>ZLast</span> <span class='hs-varid'>a</span><span class='hs-layout'>)</span> <span class='hs-keyword'>where</span>
<a name="line-149"></a> <span class='hs-varid'>foldRegsUsed</span> <span class='hs-varid'>f</span> <span class='hs-varid'>z</span> <span class='hs-layout'>(</span><span class='hs-conid'>LastOther</span> <span class='hs-varid'>l</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>foldRegsUsed</span> <span class='hs-varid'>f</span> <span class='hs-varid'>z</span> <span class='hs-varid'>l</span>
<a name="line-150"></a> <span class='hs-varid'>foldRegsUsed</span> <span class='hs-sel'>_f</span> <span class='hs-varid'>z</span> <span class='hs-conid'>LastExit</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>z</span>
<a name="line-151"></a>
<a name="line-152"></a>
<a name="line-153"></a><a name="ZHead"></a><span class='hs-keyword'>data</span> <span class='hs-conid'>ZHead</span> <span class='hs-varid'>m</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>ZFirst</span> <span class='hs-conid'>BlockId</span>
<a name="line-154"></a> <span class='hs-keyglyph'>|</span> <span class='hs-conid'>ZHead</span> <span class='hs-layout'>(</span><span class='hs-conid'>ZHead</span> <span class='hs-varid'>m</span><span class='hs-layout'>)</span> <span class='hs-varid'>m</span>
<a name="line-155"></a> <span class='hs-comment'>-- ZHead is a (reversed) sequence of middle nodes labeled by a BlockId</span>
<a name="line-156"></a><a name="ZTail"></a><span class='hs-keyword'>data</span> <span class='hs-conid'>ZTail</span> <span class='hs-varid'>m</span> <span class='hs-varid'>l</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>ZLast</span> <span class='hs-layout'>(</span><span class='hs-conid'>ZLast</span> <span class='hs-varid'>l</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>|</span> <span class='hs-conid'>ZTail</span> <span class='hs-varid'>m</span> <span class='hs-layout'>(</span><span class='hs-conid'>ZTail</span> <span class='hs-varid'>m</span> <span class='hs-varid'>l</span><span class='hs-layout'>)</span>
<a name="line-157"></a> <span class='hs-comment'>-- ZTail is a sequence of middle nodes followed by a last node</span>
<a name="line-158"></a>
<a name="line-159"></a><span class='hs-comment'>-- | Blocks and flow graphs; see Note [Kinds of graphs]</span>
<a name="line-160"></a>
<a name="line-161"></a><a name="Block"></a><span class='hs-keyword'>data</span> <span class='hs-conid'>Block</span> <span class='hs-varid'>m</span> <span class='hs-varid'>l</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>Block</span> <span class='hs-layout'>{</span> <span class='hs-varid'>bid</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>BlockId</span>
<a name="line-162"></a> <span class='hs-layout'>,</span> <span class='hs-varid'>tail</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>ZTail</span> <span class='hs-varid'>m</span> <span class='hs-varid'>l</span> <span class='hs-layout'>}</span>
<a name="line-163"></a>
<a name="line-164"></a><a name="Graph"></a><span class='hs-keyword'>data</span> <span class='hs-conid'>Graph</span> <span class='hs-varid'>m</span> <span class='hs-varid'>l</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>Graph</span> <span class='hs-layout'>{</span> <span class='hs-varid'>g_entry</span> <span class='hs-keyglyph'>::</span> <span class='hs-layout'>(</span><span class='hs-conid'>ZTail</span> <span class='hs-varid'>m</span> <span class='hs-varid'>l</span><span class='hs-layout'>)</span><span class='hs-layout'>,</span> <span class='hs-varid'>g_blocks</span> <span class='hs-keyglyph'>::</span> <span class='hs-layout'>(</span><span class='hs-conid'>BlockEnv</span> <span class='hs-layout'>(</span><span class='hs-conid'>Block</span> <span class='hs-varid'>m</span> <span class='hs-varid'>l</span><span class='hs-layout'>)</span><span class='hs-layout'>)</span> <span class='hs-layout'>}</span>
<a name="line-165"></a>
<a name="line-166"></a><a name="LGraph"></a><span class='hs-keyword'>data</span> <span class='hs-conid'>LGraph</span> <span class='hs-varid'>m</span> <span class='hs-varid'>l</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>LGraph</span> <span class='hs-layout'>{</span> <span class='hs-varid'>lg_entry</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>BlockId</span>
<a name="line-167"></a> <span class='hs-layout'>,</span> <span class='hs-varid'>lg_blocks</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>BlockEnv</span> <span class='hs-layout'>(</span><span class='hs-conid'>Block</span> <span class='hs-varid'>m</span> <span class='hs-varid'>l</span><span class='hs-layout'>)</span><span class='hs-layout'>}</span>
<a name="line-168"></a> <span class='hs-comment'>-- Invariant: lg_entry is in domain( lg_blocks )</span>
<a name="line-169"></a>
<a name="line-170"></a><a name="ZBlock"></a><span class='hs-comment'>-- | And now the zipper. The focus is between the head and tail.</span>
<a name="line-171"></a><a name="ZBlock"></a><span class='hs-comment'>-- We cannot ever focus on an inter-block edge.</span>
<a name="line-172"></a><a name="ZBlock"></a><span class='hs-keyword'>data</span> <span class='hs-conid'>ZBlock</span> <span class='hs-varid'>m</span> <span class='hs-varid'>l</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>ZBlock</span> <span class='hs-layout'>(</span><span class='hs-conid'>ZHead</span> <span class='hs-varid'>m</span><span class='hs-layout'>)</span> <span class='hs-layout'>(</span><span class='hs-conid'>ZTail</span> <span class='hs-varid'>m</span> <span class='hs-varid'>l</span><span class='hs-layout'>)</span>
<a name="line-173"></a><a name="FGraph"></a><span class='hs-keyword'>data</span> <span class='hs-conid'>FGraph</span> <span class='hs-varid'>m</span> <span class='hs-varid'>l</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>FGraph</span> <span class='hs-layout'>{</span> <span class='hs-varid'>fg_entry</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>BlockId</span>
<a name="line-174"></a> <span class='hs-layout'>,</span> <span class='hs-varid'>fg_focus</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>ZBlock</span> <span class='hs-varid'>m</span> <span class='hs-varid'>l</span>
<a name="line-175"></a> <span class='hs-layout'>,</span> <span class='hs-varid'>fg_others</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>BlockEnv</span> <span class='hs-layout'>(</span><span class='hs-conid'>Block</span> <span class='hs-varid'>m</span> <span class='hs-varid'>l</span><span class='hs-layout'>)</span> <span class='hs-layout'>}</span>
<a name="line-176"></a> <span class='hs-comment'>-- Invariant: the block represented by 'fg_focus' is *not*</span>
<a name="line-177"></a> <span class='hs-comment'>-- in the map 'fg_others'</span>
<a name="line-178"></a>
<a name="line-179"></a><span class='hs-comment'>---- Utility functions ---</span>
<a name="line-180"></a>
<a name="line-181"></a><a name="blockId"></a><span class='hs-definition'>blockId</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>Block</span> <span class='hs-varid'>m</span> <span class='hs-varid'>l</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>BlockId</span>
<a name="line-182"></a><a name="zip"></a><span class='hs-definition'>zip</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>ZBlock</span> <span class='hs-varid'>m</span> <span class='hs-varid'>l</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Block</span> <span class='hs-varid'>m</span> <span class='hs-varid'>l</span>
<a name="line-183"></a><a name="unzip"></a><span class='hs-definition'>unzip</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>Block</span> <span class='hs-varid'>m</span> <span class='hs-varid'>l</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>ZBlock</span> <span class='hs-varid'>m</span> <span class='hs-varid'>l</span>
<a name="line-184"></a>
<a name="line-185"></a><a name="last"></a><span class='hs-definition'>last</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>ZBlock</span> <span class='hs-varid'>m</span> <span class='hs-varid'>l</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>ZLast</span> <span class='hs-varid'>l</span>
<a name="line-186"></a><a name="goto_end"></a><span class='hs-definition'>goto_end</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>ZBlock</span> <span class='hs-varid'>m</span> <span class='hs-varid'>l</span> <span class='hs-keyglyph'>-></span> <span class='hs-layout'>(</span><span class='hs-conid'>ZHead</span> <span class='hs-varid'>m</span><span class='hs-layout'>,</span> <span class='hs-conid'>ZLast</span> <span class='hs-varid'>l</span><span class='hs-layout'>)</span>
<a name="line-187"></a>
<a name="line-188"></a><a name="tailOfLast"></a><span class='hs-definition'>tailOfLast</span> <span class='hs-keyglyph'>::</span> <span class='hs-varid'>l</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>ZTail</span> <span class='hs-varid'>m</span> <span class='hs-varid'>l</span>
<a name="line-189"></a>
<a name="line-190"></a><span class='hs-comment'>-- | Take a head and tail and go to beginning or end. The asymmetry</span>
<a name="line-191"></a><span class='hs-comment'>-- in the types and names is a bit unfortunate, but 'Block m l' is</span>
<a name="line-192"></a><span class='hs-comment'>-- effectively '(BlockId, ZTail m l)' and is accepted in many more places.</span>
<a name="line-193"></a>
<a name="line-194"></a><a name="ht_to_block"></a><span class='hs-definition'>ht_to_block</span><span class='hs-layout'>,</span> <span class='hs-varid'>zipht</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>ZHead</span> <span class='hs-varid'>m</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>ZTail</span> <span class='hs-varid'>m</span> <span class='hs-varid'>l</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Block</span> <span class='hs-varid'>m</span> <span class='hs-varid'>l</span>
<a name="line-195"></a><a name="ht_to_last"></a><span class='hs-definition'>ht_to_last</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>ZHead</span> <span class='hs-varid'>m</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>ZTail</span> <span class='hs-varid'>m</span> <span class='hs-varid'>l</span> <span class='hs-keyglyph'>-></span> <span class='hs-layout'>(</span><span class='hs-conid'>ZHead</span> <span class='hs-varid'>m</span><span class='hs-layout'>,</span> <span class='hs-conid'>ZLast</span> <span class='hs-varid'>l</span><span class='hs-layout'>)</span>
<a name="line-196"></a>
<a name="line-197"></a><span class='hs-comment'>-- | We can splice a single-entry, single-exit LGraph onto a head or a tail.</span>
<a name="line-198"></a><span class='hs-comment'>-- For a head, we have a head 'h' followed by a LGraph 'g'.</span>
<a name="line-199"></a><span class='hs-comment'>-- The entry node of 'g' gets joined to 'h', forming the entry into</span>
<a name="line-200"></a><span class='hs-comment'>-- the new LGraph. The exit of 'g' becomes the new head.</span>
<a name="line-201"></a><span class='hs-comment'>-- For both arguments and results, the order of values is the order of</span>
<a name="line-202"></a><span class='hs-comment'>-- control flow: before splicing, the head flows into the LGraph; after</span>
<a name="line-203"></a><span class='hs-comment'>-- splicing, the LGraph flows into the head.</span>
<a name="line-204"></a><span class='hs-comment'>-- Splicing a tail is the dual operation.</span>
<a name="line-205"></a><span class='hs-comment'>-- (In order to maintain the order-means-control-flow convention, the</span>
<a name="line-206"></a><span class='hs-comment'>-- orders are reversed.)</span>
<a name="line-207"></a><span class='hs-comment'>--</span>
<a name="line-208"></a><span class='hs-comment'>-- For example, assume</span>
<a name="line-209"></a><span class='hs-comment'>-- head = [L: x:=0]</span>
<a name="line-210"></a><span class='hs-comment'>-- grph = (M, [M: <stuff>,</span>
<a name="line-211"></a><span class='hs-comment'>-- <blocks>,</span>
<a name="line-212"></a><span class='hs-comment'>-- N: y:=x; LastExit])</span>
<a name="line-213"></a><span class='hs-comment'>-- tail = [return (y,x)]</span>
<a name="line-214"></a><span class='hs-comment'>--</span>
<a name="line-215"></a><span class='hs-comment'>-- Then splice_head head grph</span>
<a name="line-216"></a><span class='hs-comment'>-- = ((L, [L: x:=0; goto M,</span>
<a name="line-217"></a><span class='hs-comment'>-- M: <stuff>,</span>
<a name="line-218"></a><span class='hs-comment'>-- <blocks>])</span>
<a name="line-219"></a><span class='hs-comment'>-- , N: y:=x)</span>
<a name="line-220"></a><span class='hs-comment'>--</span>
<a name="line-221"></a><span class='hs-comment'>-- Then splice_tail grph tail</span>
<a name="line-222"></a><span class='hs-comment'>-- = ( <stuff></span>
<a name="line-223"></a><span class='hs-comment'>-- , (???, [<blocks>,</span>
<a name="line-224"></a><span class='hs-comment'>-- N: y:=x; return (y,x)])</span>
<a name="line-225"></a>
<a name="line-226"></a><a name="splice_head"></a><span class='hs-definition'>splice_head</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>ZHead</span> <span class='hs-varid'>m</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>LGraph</span> <span class='hs-varid'>m</span> <span class='hs-varid'>l</span> <span class='hs-keyglyph'>-></span> <span class='hs-layout'>(</span><span class='hs-conid'>LGraph</span> <span class='hs-varid'>m</span> <span class='hs-varid'>l</span><span class='hs-layout'>,</span> <span class='hs-conid'>ZHead</span> <span class='hs-varid'>m</span><span class='hs-layout'>)</span>
<a name="line-227"></a><a name="splice_head'"></a><span class='hs-definition'>splice_head'</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>ZHead</span> <span class='hs-varid'>m</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Graph</span> <span class='hs-varid'>m</span> <span class='hs-varid'>l</span> <span class='hs-keyglyph'>-></span> <span class='hs-layout'>(</span><span class='hs-conid'>BlockEnv</span> <span class='hs-layout'>(</span><span class='hs-conid'>Block</span> <span class='hs-varid'>m</span> <span class='hs-varid'>l</span><span class='hs-layout'>)</span><span class='hs-layout'>,</span> <span class='hs-conid'>ZHead</span> <span class='hs-varid'>m</span><span class='hs-layout'>)</span>
<a name="line-228"></a><a name="splice_tail"></a><span class='hs-definition'>splice_tail</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>Graph</span> <span class='hs-varid'>m</span> <span class='hs-varid'>l</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>ZTail</span> <span class='hs-varid'>m</span> <span class='hs-varid'>l</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Graph</span> <span class='hs-varid'>m</span> <span class='hs-varid'>l</span>
<a name="line-229"></a>
<a name="line-230"></a><a name="splice_head_only"></a><span class='hs-comment'>-- | We can also splice a single-entry, no-exit Graph into a head.</span>
<a name="line-231"></a><span class='hs-definition'>splice_head_only</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>ZHead</span> <span class='hs-varid'>m</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>LGraph</span> <span class='hs-varid'>m</span> <span class='hs-varid'>l</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>LGraph</span> <span class='hs-varid'>m</span> <span class='hs-varid'>l</span>
<a name="line-232"></a><a name="splice_head_only'"></a><span class='hs-definition'>splice_head_only'</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>ZHead</span> <span class='hs-varid'>m</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Graph</span> <span class='hs-varid'>m</span> <span class='hs-varid'>l</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>LGraph</span> <span class='hs-varid'>m</span> <span class='hs-varid'>l</span>
<a name="line-233"></a>
<a name="line-234"></a>
<a name="line-235"></a><span class='hs-comment'>-- | A safe operation </span>
<a name="line-236"></a>
<a name="line-237"></a><a name="of_block_list"></a><span class='hs-comment'>-- | Conversion to and from the environment form is convenient. For</span>
<a name="line-238"></a><span class='hs-comment'>-- layout or dataflow, however, one will want to use 'postorder_dfs'</span>
<a name="line-239"></a><span class='hs-comment'>-- in order to get the blocks in an order that relates to the control</span>
<a name="line-240"></a><span class='hs-comment'>-- flow in the procedure.</span>
<a name="line-241"></a><span class='hs-definition'>of_block_list</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>BlockId</span> <span class='hs-keyglyph'>-></span> <span class='hs-keyglyph'>[</span><span class='hs-conid'>Block</span> <span class='hs-varid'>m</span> <span class='hs-varid'>l</span><span class='hs-keyglyph'>]</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>LGraph</span> <span class='hs-varid'>m</span> <span class='hs-varid'>l</span> <span class='hs-comment'>-- N log N</span>
<a name="line-242"></a><a name="to_block_list"></a><span class='hs-definition'>to_block_list</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>LGraph</span> <span class='hs-varid'>m</span> <span class='hs-varid'>l</span> <span class='hs-keyglyph'>-></span> <span class='hs-keyglyph'>[</span><span class='hs-conid'>Block</span> <span class='hs-varid'>m</span> <span class='hs-varid'>l</span><span class='hs-keyglyph'>]</span> <span class='hs-comment'>-- N log N</span>
<a name="line-243"></a>
<a name="line-244"></a><a name="graphOfLGraph"></a><span class='hs-comment'>-- | Conversion from LGraph to Graph</span>
<a name="line-245"></a><span class='hs-definition'>graphOfLGraph</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>LastNode</span> <span class='hs-varid'>l</span> <span class='hs-keyglyph'>=></span> <span class='hs-conid'>LGraph</span> <span class='hs-varid'>m</span> <span class='hs-varid'>l</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Graph</span> <span class='hs-varid'>m</span> <span class='hs-varid'>l</span>
<a name="line-246"></a><span class='hs-definition'>graphOfLGraph</span> <span class='hs-layout'>(</span><span class='hs-conid'>LGraph</span> <span class='hs-varid'>eid</span> <span class='hs-varid'>blocks</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>Graph</span> <span class='hs-layout'>(</span><span class='hs-conid'>ZLast</span> <span class='hs-varop'>$</span> <span class='hs-varid'>mkBranchNode</span> <span class='hs-varid'>eid</span><span class='hs-layout'>)</span> <span class='hs-varid'>blocks</span>
<a name="line-247"></a>
<a name="line-248"></a>
<a name="line-249"></a><span class='hs-comment'>-- | Traversal: 'postorder_dfs' returns a list of blocks reachable</span>
<a name="line-250"></a><span class='hs-comment'>-- from the entry node. This list has the following property:</span>
<a name="line-251"></a><span class='hs-comment'>--</span>
<a name="line-252"></a><span class='hs-comment'>-- Say a "back reference" exists if one of a block's</span>
<a name="line-253"></a><span class='hs-comment'>-- control-flow successors precedes it in the output list</span>
<a name="line-254"></a><span class='hs-comment'>--</span>
<a name="line-255"></a><span class='hs-comment'>-- Then there are as few back references as possible</span>
<a name="line-256"></a><span class='hs-comment'>--</span>
<a name="line-257"></a><span class='hs-comment'>-- The output is suitable for use in</span>
<a name="line-258"></a><span class='hs-comment'>-- a forward dataflow problem. For a backward problem, simply reverse</span>
<a name="line-259"></a><span class='hs-comment'>-- the list. ('postorder_dfs' is sufficiently tricky to implement that</span>
<a name="line-260"></a><span class='hs-comment'>-- one doesn't want to try and maintain both forward and backward</span>
<a name="line-261"></a><span class='hs-comment'>-- versions.)</span>
<a name="line-262"></a>
<a name="line-263"></a><a name="postorder_dfs"></a><span class='hs-definition'>postorder_dfs</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>LastNode</span> <span class='hs-varid'>l</span> <span class='hs-keyglyph'>=></span> <span class='hs-conid'>LGraph</span> <span class='hs-varid'>m</span> <span class='hs-varid'>l</span> <span class='hs-keyglyph'>-></span> <span class='hs-keyglyph'>[</span><span class='hs-conid'>Block</span> <span class='hs-varid'>m</span> <span class='hs-varid'>l</span><span class='hs-keyglyph'>]</span>
<a name="line-264"></a>
<a name="line-265"></a><a name="fold_layout"></a><span class='hs-comment'>-- | For layout, we fold over pairs of 'Block m l' and 'Maybe BlockId'</span>
<a name="line-266"></a><span class='hs-comment'>-- in layout order. The 'Maybe BlockId', if present, identifies the</span>
<a name="line-267"></a><span class='hs-comment'>-- block that will be the layout successor of the current block. This</span>
<a name="line-268"></a><span class='hs-comment'>-- may be useful to help an emitter omit the final 'goto' of a block</span>
<a name="line-269"></a><span class='hs-comment'>-- that flows directly to its layout successor.</span>
<a name="line-270"></a><span class='hs-comment'>--</span>
<a name="line-271"></a><span class='hs-comment'>-- For example: fold_layout f z [ L1:B1, L2:B2, L3:B3 ]</span>
<a name="line-272"></a><span class='hs-comment'>-- = z <$> f (L1:B1) (Just L2)</span>
<a name="line-273"></a><span class='hs-comment'>-- <$> f (L2:B2) (Just L3)</span>
<a name="line-274"></a><span class='hs-comment'>-- <$> f (L3:B3) Nothing</span>
<a name="line-275"></a><span class='hs-comment'>-- where a <$> f = f a</span>
<a name="line-276"></a><span class='hs-definition'>fold_layout</span> <span class='hs-keyglyph'>::</span>
<a name="line-277"></a> <span class='hs-conid'>LastNode</span> <span class='hs-varid'>l</span> <span class='hs-keyglyph'>=></span> <span class='hs-layout'>(</span><span class='hs-conid'>Block</span> <span class='hs-varid'>m</span> <span class='hs-varid'>l</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Maybe</span> <span class='hs-conid'>BlockId</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>a</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>a</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>a</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>LGraph</span> <span class='hs-varid'>m</span> <span class='hs-varid'>l</span><span class='hs-keyglyph'>-></span> <span class='hs-varid'>a</span>
<a name="line-278"></a>
<a name="line-279"></a><a name="fold_blocks"></a><span class='hs-comment'>-- | We can also fold over blocks in an unspecified order. The</span>
<a name="line-280"></a><span class='hs-comment'>-- 'ZipCfgExtras' module provides a monadic version, which we</span>
<a name="line-281"></a><span class='hs-comment'>-- haven't needed (else it would be here).</span>
<a name="line-282"></a><span class='hs-definition'>fold_blocks</span> <span class='hs-keyglyph'>::</span> <span class='hs-layout'>(</span><span class='hs-conid'>Block</span> <span class='hs-varid'>m</span> <span class='hs-varid'>l</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>a</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>a</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>a</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>LGraph</span> <span class='hs-varid'>m</span> <span class='hs-varid'>l</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>a</span>
<a name="line-283"></a>
<a name="line-284"></a><a name="fold_fwd_block"></a><span class='hs-comment'>-- | Fold from first to last</span>
<a name="line-285"></a><span class='hs-definition'>fold_fwd_block</span> <span class='hs-keyglyph'>::</span> <span class='hs-layout'>(</span><span class='hs-conid'>BlockId</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>a</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>a</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>-></span> <span class='hs-layout'>(</span><span class='hs-varid'>m</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>a</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>a</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>-></span>
<a name="line-286"></a> <span class='hs-layout'>(</span><span class='hs-conid'>ZLast</span> <span class='hs-varid'>l</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>a</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>a</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Block</span> <span class='hs-varid'>m</span> <span class='hs-varid'>l</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>a</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>a</span>
<a name="line-287"></a>
<a name="line-288"></a><a name="map_one_block"></a><span class='hs-definition'>map_one_block</span> <span class='hs-keyglyph'>::</span> <span class='hs-layout'>(</span><span class='hs-conid'>BlockId</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>BlockId</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>-></span> <span class='hs-layout'>(</span><span class='hs-varid'>m</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>m'</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>-></span> <span class='hs-layout'>(</span><span class='hs-varid'>l</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>l'</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Block</span> <span class='hs-varid'>m</span> <span class='hs-varid'>l</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Block</span> <span class='hs-varid'>m'</span> <span class='hs-varid'>l'</span>
<a name="line-289"></a>
<a name="line-290"></a><a name="map_nodes"></a><span class='hs-definition'>map_nodes</span> <span class='hs-keyglyph'>::</span> <span class='hs-layout'>(</span><span class='hs-conid'>BlockId</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>BlockId</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>-></span> <span class='hs-layout'>(</span><span class='hs-varid'>m</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>m'</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>-></span> <span class='hs-layout'>(</span><span class='hs-varid'>l</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>l'</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>LGraph</span> <span class='hs-varid'>m</span> <span class='hs-varid'>l</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>LGraph</span> <span class='hs-varid'>m'</span> <span class='hs-varid'>l'</span>
<a name="line-291"></a> <span class='hs-comment'>-- mapping includes the entry id!</span>
<a name="line-292"></a>
<a name="line-293"></a><a name="map_blocks"></a><span class='hs-definition'>map_blocks</span> <span class='hs-keyglyph'>::</span> <span class='hs-layout'>(</span><span class='hs-conid'>Block</span> <span class='hs-varid'>m</span> <span class='hs-varid'>l</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Block</span> <span class='hs-varid'>m'</span> <span class='hs-varid'>l'</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>LGraph</span> <span class='hs-varid'>m</span> <span class='hs-varid'>l</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>LGraph</span> <span class='hs-varid'>m'</span> <span class='hs-varid'>l'</span>
<a name="line-294"></a><a name="mapM_blocks"></a><span class='hs-definition'>mapM_blocks</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>Monad</span> <span class='hs-varid'>mm</span>
<a name="line-295"></a> <span class='hs-keyglyph'>=></span> <span class='hs-layout'>(</span><span class='hs-conid'>Block</span> <span class='hs-varid'>m</span> <span class='hs-varid'>l</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>mm</span> <span class='hs-layout'>(</span><span class='hs-conid'>Block</span> <span class='hs-varid'>m'</span> <span class='hs-varid'>l'</span><span class='hs-layout'>)</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>LGraph</span> <span class='hs-varid'>m</span> <span class='hs-varid'>l</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>mm</span> <span class='hs-layout'>(</span><span class='hs-conid'>LGraph</span> <span class='hs-varid'>m'</span> <span class='hs-varid'>l'</span><span class='hs-layout'>)</span>
<a name="line-296"></a>
<a name="line-297"></a><a name="translate"></a><span class='hs-comment'>-- | These translation functions are speculative. I hope eventually</span>
<a name="line-298"></a><span class='hs-comment'>-- they will be used in the native-code back ends ---NR</span>
<a name="line-299"></a><span class='hs-definition'>translate</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>Monad</span> <span class='hs-varid'>tm</span> <span class='hs-keyglyph'>=></span>
<a name="line-300"></a> <span class='hs-layout'>(</span><span class='hs-varid'>m</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>tm</span> <span class='hs-layout'>(</span><span class='hs-conid'>LGraph</span> <span class='hs-varid'>m'</span> <span class='hs-varid'>l'</span><span class='hs-layout'>)</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>-></span>
<a name="line-301"></a> <span class='hs-layout'>(</span><span class='hs-varid'>l</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>tm</span> <span class='hs-layout'>(</span><span class='hs-conid'>LGraph</span> <span class='hs-varid'>m'</span> <span class='hs-varid'>l'</span><span class='hs-layout'>)</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>-></span>
<a name="line-302"></a> <span class='hs-layout'>(</span><span class='hs-conid'>LGraph</span> <span class='hs-varid'>m</span> <span class='hs-varid'>l</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>tm</span> <span class='hs-layout'>(</span><span class='hs-conid'>LGraph</span> <span class='hs-varid'>m'</span> <span class='hs-varid'>l'</span><span class='hs-layout'>)</span><span class='hs-layout'>)</span>
<a name="line-303"></a>
<a name="line-304"></a><span class='hs-comment'>{-
<a name="line-305"></a>-- | It's possible that another form of translation would be more suitable:
<a name="line-306"></a>translateA :: (m -> Agraph m' l') -> (l -> AGraph m' l') -> LGraph m l -> LGraph m' l'
<a name="line-307"></a>-}</span>
<a name="line-308"></a>
<a name="line-309"></a><span class='hs-comment'>------------------- Last nodes</span>
<a name="line-310"></a>
<a name="line-311"></a><span class='hs-comment'>-- | We can't make a graph out of just any old 'last node' type. A last node</span>
<a name="line-312"></a><span class='hs-comment'>-- has to be able to find its successors, and we need to be able to create and</span>
<a name="line-313"></a><span class='hs-comment'>-- identify unconditional branches. We put these capabilities in a type class.</span>
<a name="line-314"></a><span class='hs-comment'>-- Moreover, the property of having successors is also shared by 'Block's and</span>
<a name="line-315"></a><span class='hs-comment'>-- 'ZTails', so it is useful to have that property in a type class of its own.</span>
<a name="line-316"></a>
<a name="line-317"></a><a name="HavingSuccessors"></a><span class='hs-keyword'>class</span> <span class='hs-conid'>HavingSuccessors</span> <span class='hs-varid'>b</span> <span class='hs-keyword'>where</span>
<a name="line-318"></a> <span class='hs-varid'>succs</span> <span class='hs-keyglyph'>::</span> <span class='hs-varid'>b</span> <span class='hs-keyglyph'>-></span> <span class='hs-keyglyph'>[</span><span class='hs-conid'>BlockId</span><span class='hs-keyglyph'>]</span>
<a name="line-319"></a> <span class='hs-varid'>fold_succs</span> <span class='hs-keyglyph'>::</span> <span class='hs-layout'>(</span><span class='hs-conid'>BlockId</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>a</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>a</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>b</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>a</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>a</span>
<a name="line-320"></a>
<a name="line-321"></a> <span class='hs-varid'>fold_succs</span> <span class='hs-varid'>add</span> <span class='hs-varid'>l</span> <span class='hs-varid'>z</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>foldr</span> <span class='hs-varid'>add</span> <span class='hs-varid'>z</span> <span class='hs-varop'>$</span> <span class='hs-varid'>succs</span> <span class='hs-varid'>l</span>
<a name="line-322"></a>
<a name="line-323"></a><a name="LastNode"></a><span class='hs-keyword'>class</span> <span class='hs-conid'>HavingSuccessors</span> <span class='hs-varid'>l</span> <span class='hs-keyglyph'>=></span> <span class='hs-conid'>LastNode</span> <span class='hs-varid'>l</span> <span class='hs-keyword'>where</span>
<a name="line-324"></a> <span class='hs-varid'>mkBranchNode</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>BlockId</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>l</span>
<a name="line-325"></a> <span class='hs-varid'>isBranchNode</span> <span class='hs-keyglyph'>::</span> <span class='hs-varid'>l</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Bool</span>
<a name="line-326"></a> <span class='hs-varid'>branchNodeTarget</span> <span class='hs-keyglyph'>::</span> <span class='hs-varid'>l</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>BlockId</span> <span class='hs-comment'>-- panics if not branch node</span>
<a name="line-327"></a> <span class='hs-comment'>-- ^ N.B. This interface seems to make for more congenial clients than a</span>
<a name="line-328"></a> <span class='hs-comment'>-- single function of type 'l -> Maybe BlockId'</span>
<a name="line-329"></a>
<a name="line-330"></a><span class='hs-keyword'>instance</span> <span class='hs-conid'>HavingSuccessors</span> <span class='hs-varid'>l</span> <span class='hs-keyglyph'>=></span> <span class='hs-conid'>HavingSuccessors</span> <span class='hs-layout'>(</span><span class='hs-conid'>ZLast</span> <span class='hs-varid'>l</span><span class='hs-layout'>)</span> <span class='hs-keyword'>where</span>
<a name="line-331"></a> <span class='hs-varid'>succs</span> <span class='hs-conid'>LastExit</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>[]</span>
<a name="line-332"></a> <span class='hs-varid'>succs</span> <span class='hs-layout'>(</span><span class='hs-conid'>LastOther</span> <span class='hs-varid'>l</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>succs</span> <span class='hs-varid'>l</span>
<a name="line-333"></a> <span class='hs-varid'>fold_succs</span> <span class='hs-keyword'>_</span> <span class='hs-conid'>LastExit</span> <span class='hs-varid'>z</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>z</span>
<a name="line-334"></a> <span class='hs-varid'>fold_succs</span> <span class='hs-varid'>f</span> <span class='hs-layout'>(</span><span class='hs-conid'>LastOther</span> <span class='hs-varid'>l</span><span class='hs-layout'>)</span> <span class='hs-varid'>z</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>fold_succs</span> <span class='hs-varid'>f</span> <span class='hs-varid'>l</span> <span class='hs-varid'>z</span>
<a name="line-335"></a>
<a name="line-336"></a><span class='hs-keyword'>instance</span> <span class='hs-conid'>LastNode</span> <span class='hs-varid'>l</span> <span class='hs-keyglyph'>=></span> <span class='hs-conid'>LastNode</span> <span class='hs-layout'>(</span><span class='hs-conid'>ZLast</span> <span class='hs-varid'>l</span><span class='hs-layout'>)</span> <span class='hs-keyword'>where</span>
<a name="line-337"></a> <span class='hs-varid'>mkBranchNode</span> <span class='hs-varid'>id</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>LastOther</span> <span class='hs-varop'>$</span> <span class='hs-varid'>mkBranchNode</span> <span class='hs-varid'>id</span>
<a name="line-338"></a> <span class='hs-varid'>isBranchNode</span> <span class='hs-conid'>LastExit</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>False</span>
<a name="line-339"></a> <span class='hs-varid'>isBranchNode</span> <span class='hs-layout'>(</span><span class='hs-conid'>LastOther</span> <span class='hs-varid'>l</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>isBranchNode</span> <span class='hs-varid'>l</span>
<a name="line-340"></a> <span class='hs-varid'>branchNodeTarget</span> <span class='hs-conid'>LastExit</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>panic</span> <span class='hs-str'>"branchNodeTarget LastExit"</span>
<a name="line-341"></a> <span class='hs-varid'>branchNodeTarget</span> <span class='hs-layout'>(</span><span class='hs-conid'>LastOther</span> <span class='hs-varid'>l</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>branchNodeTarget</span> <span class='hs-varid'>l</span>
<a name="line-342"></a>
<a name="line-343"></a><span class='hs-keyword'>instance</span> <span class='hs-conid'>LastNode</span> <span class='hs-varid'>l</span> <span class='hs-keyglyph'>=></span> <span class='hs-conid'>HavingSuccessors</span> <span class='hs-layout'>(</span><span class='hs-conid'>ZBlock</span> <span class='hs-varid'>m</span> <span class='hs-varid'>l</span><span class='hs-layout'>)</span> <span class='hs-keyword'>where</span>
<a name="line-344"></a> <span class='hs-varid'>succs</span> <span class='hs-varid'>b</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>succs</span> <span class='hs-layout'>(</span><span class='hs-varid'>last</span> <span class='hs-varid'>b</span><span class='hs-layout'>)</span>
<a name="line-345"></a>
<a name="line-346"></a><span class='hs-keyword'>instance</span> <span class='hs-conid'>LastNode</span> <span class='hs-varid'>l</span> <span class='hs-keyglyph'>=></span> <span class='hs-conid'>HavingSuccessors</span> <span class='hs-layout'>(</span><span class='hs-conid'>Block</span> <span class='hs-varid'>m</span> <span class='hs-varid'>l</span><span class='hs-layout'>)</span> <span class='hs-keyword'>where</span>
<a name="line-347"></a> <span class='hs-varid'>succs</span> <span class='hs-varid'>b</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>succs</span> <span class='hs-layout'>(</span><span class='hs-varid'>unzip</span> <span class='hs-varid'>b</span><span class='hs-layout'>)</span>
<a name="line-348"></a>
<a name="line-349"></a><span class='hs-keyword'>instance</span> <span class='hs-conid'>LastNode</span> <span class='hs-varid'>l</span> <span class='hs-keyglyph'>=></span> <span class='hs-conid'>HavingSuccessors</span> <span class='hs-layout'>(</span><span class='hs-conid'>ZTail</span> <span class='hs-varid'>m</span> <span class='hs-varid'>l</span><span class='hs-layout'>)</span> <span class='hs-keyword'>where</span>
<a name="line-350"></a> <span class='hs-varid'>succs</span> <span class='hs-varid'>b</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>succs</span> <span class='hs-layout'>(</span><span class='hs-varid'>lastTail</span> <span class='hs-varid'>b</span><span class='hs-layout'>)</span>
<a name="line-351"></a>
<a name="line-352"></a>
<a name="line-353"></a>
<a name="line-354"></a><span class='hs-comment'>-- ================ IMPLEMENTATION ================--</span>
<a name="line-355"></a>
<a name="line-356"></a><span class='hs-comment'>----- block manipulations</span>
<a name="line-357"></a>
<a name="line-358"></a><span class='hs-definition'>blockId</span> <span class='hs-layout'>(</span><span class='hs-conid'>Block</span> <span class='hs-varid'>id</span> <span class='hs-keyword'>_</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>id</span>
<a name="line-359"></a>
<a name="line-360"></a><span class='hs-comment'>-- | Convert block between forms.</span>
<a name="line-361"></a><span class='hs-comment'>-- These functions are tail-recursive, so we can go as deep as we like</span>
<a name="line-362"></a><span class='hs-comment'>-- without fear of stack overflow. </span>
<a name="line-363"></a>
<a name="line-364"></a><span class='hs-definition'>ht_to_block</span> <span class='hs-varid'>head</span> <span class='hs-varid'>tail</span> <span class='hs-keyglyph'>=</span> <span class='hs-keyword'>case</span> <span class='hs-varid'>head</span> <span class='hs-keyword'>of</span>
<a name="line-365"></a> <span class='hs-conid'>ZFirst</span> <span class='hs-varid'>id</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Block</span> <span class='hs-varid'>id</span> <span class='hs-varid'>tail</span>
<a name="line-366"></a> <span class='hs-conid'>ZHead</span> <span class='hs-varid'>h</span> <span class='hs-varid'>m</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>ht_to_block</span> <span class='hs-varid'>h</span> <span class='hs-layout'>(</span><span class='hs-conid'>ZTail</span> <span class='hs-varid'>m</span> <span class='hs-varid'>tail</span><span class='hs-layout'>)</span>
<a name="line-367"></a>
<a name="line-368"></a><span class='hs-definition'>ht_to_last</span> <span class='hs-varid'>head</span> <span class='hs-layout'>(</span><span class='hs-conid'>ZLast</span> <span class='hs-varid'>l</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-layout'>(</span><span class='hs-varid'>head</span><span class='hs-layout'>,</span> <span class='hs-varid'>l</span><span class='hs-layout'>)</span>
<a name="line-369"></a><span class='hs-definition'>ht_to_last</span> <span class='hs-varid'>head</span> <span class='hs-layout'>(</span><span class='hs-conid'>ZTail</span> <span class='hs-varid'>m</span> <span class='hs-varid'>t</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>ht_to_last</span> <span class='hs-layout'>(</span><span class='hs-conid'>ZHead</span> <span class='hs-varid'>head</span> <span class='hs-varid'>m</span><span class='hs-layout'>)</span> <span class='hs-varid'>t</span>
<a name="line-370"></a>
<a name="line-371"></a><a name="zipht"></a><span class='hs-definition'>zipht</span> <span class='hs-varid'>h</span> <span class='hs-varid'>t</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>ht_to_block</span> <span class='hs-varid'>h</span> <span class='hs-varid'>t</span>
<a name="line-372"></a><span class='hs-definition'>zip</span> <span class='hs-layout'>(</span><span class='hs-conid'>ZBlock</span> <span class='hs-varid'>h</span> <span class='hs-varid'>t</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>ht_to_block</span> <span class='hs-varid'>h</span> <span class='hs-varid'>t</span>
<a name="line-373"></a><span class='hs-definition'>goto_end</span> <span class='hs-layout'>(</span><span class='hs-conid'>ZBlock</span> <span class='hs-varid'>h</span> <span class='hs-varid'>t</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>ht_to_last</span> <span class='hs-varid'>h</span> <span class='hs-varid'>t</span>
<a name="line-374"></a>
<a name="line-375"></a><span class='hs-definition'>unzip</span> <span class='hs-layout'>(</span><span class='hs-conid'>Block</span> <span class='hs-varid'>id</span> <span class='hs-varid'>t</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>ZBlock</span> <span class='hs-layout'>(</span><span class='hs-conid'>ZFirst</span> <span class='hs-varid'>id</span><span class='hs-layout'>)</span> <span class='hs-varid'>t</span>
<a name="line-376"></a>
<a name="line-377"></a><a name="head_id"></a><span class='hs-definition'>head_id</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>ZHead</span> <span class='hs-varid'>m</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>BlockId</span>
<a name="line-378"></a><span class='hs-definition'>head_id</span> <span class='hs-layout'>(</span><span class='hs-conid'>ZFirst</span> <span class='hs-varid'>id</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>id</span>
<a name="line-379"></a><span class='hs-definition'>head_id</span> <span class='hs-layout'>(</span><span class='hs-conid'>ZHead</span> <span class='hs-varid'>h</span> <span class='hs-keyword'>_</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>head_id</span> <span class='hs-varid'>h</span>
<a name="line-380"></a>
<a name="line-381"></a><span class='hs-definition'>last</span> <span class='hs-layout'>(</span><span class='hs-conid'>ZBlock</span> <span class='hs-keyword'>_</span> <span class='hs-varid'>t</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>lastTail</span> <span class='hs-varid'>t</span>
<a name="line-382"></a>
<a name="line-383"></a><a name="lastTail"></a><span class='hs-definition'>lastTail</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>ZTail</span> <span class='hs-varid'>m</span> <span class='hs-varid'>l</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>ZLast</span> <span class='hs-varid'>l</span>
<a name="line-384"></a><span class='hs-definition'>lastTail</span> <span class='hs-layout'>(</span><span class='hs-conid'>ZLast</span> <span class='hs-varid'>l</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>l</span>
<a name="line-385"></a><span class='hs-definition'>lastTail</span> <span class='hs-layout'>(</span><span class='hs-conid'>ZTail</span> <span class='hs-keyword'>_</span> <span class='hs-varid'>t</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>lastTail</span> <span class='hs-varid'>t</span>
<a name="line-386"></a>
<a name="line-387"></a><span class='hs-definition'>tailOfLast</span> <span class='hs-varid'>l</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>ZLast</span> <span class='hs-layout'>(</span><span class='hs-conid'>LastOther</span> <span class='hs-varid'>l</span><span class='hs-layout'>)</span> <span class='hs-comment'>-- tedious to write in every client</span>
<a name="line-388"></a>
<a name="line-389"></a>
<a name="line-390"></a><span class='hs-comment'>------------------ simple graph manipulations</span>
<a name="line-391"></a>
<a name="line-392"></a><a name="focus"></a><span class='hs-definition'>focus</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>BlockId</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>LGraph</span> <span class='hs-varid'>m</span> <span class='hs-varid'>l</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>FGraph</span> <span class='hs-varid'>m</span> <span class='hs-varid'>l</span> <span class='hs-comment'>-- focus on edge out of node with id </span>
<a name="line-393"></a><span class='hs-definition'>focus</span> <span class='hs-varid'>id</span> <span class='hs-layout'>(</span><span class='hs-conid'>LGraph</span> <span class='hs-varid'>entry</span> <span class='hs-varid'>blocks</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span>
<a name="line-394"></a> <span class='hs-keyword'>case</span> <span class='hs-varid'>lookupBlockEnv</span> <span class='hs-varid'>blocks</span> <span class='hs-varid'>id</span> <span class='hs-keyword'>of</span>
<a name="line-395"></a> <span class='hs-conid'>Just</span> <span class='hs-varid'>b</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>FGraph</span> <span class='hs-varid'>entry</span> <span class='hs-layout'>(</span><span class='hs-varid'>unzip</span> <span class='hs-varid'>b</span><span class='hs-layout'>)</span> <span class='hs-layout'>(</span><span class='hs-varid'>delFromBlockEnv</span> <span class='hs-varid'>blocks</span> <span class='hs-varid'>id</span><span class='hs-layout'>)</span>
<a name="line-396"></a> <span class='hs-conid'>Nothing</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>panic</span> <span class='hs-str'>"asked for nonexistent block in flow graph"</span>
<a name="line-397"></a>
<a name="line-398"></a><a name="entry"></a><span class='hs-definition'>entry</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>LGraph</span> <span class='hs-varid'>m</span> <span class='hs-varid'>l</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>FGraph</span> <span class='hs-varid'>m</span> <span class='hs-varid'>l</span> <span class='hs-comment'>-- focus on edge out of entry node </span>
<a name="line-399"></a><span class='hs-definition'>entry</span> <span class='hs-varid'>g</span><span class='hs-keyglyph'>@</span><span class='hs-layout'>(</span><span class='hs-conid'>LGraph</span> <span class='hs-varid'>eid</span> <span class='hs-keyword'>_</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>focus</span> <span class='hs-varid'>eid</span> <span class='hs-varid'>g</span>
<a name="line-400"></a>
<a name="line-401"></a><a name="splitp_blocks"></a><span class='hs-comment'>-- | pull out a block satisfying the predicate, if any</span>
<a name="line-402"></a><span class='hs-definition'>splitp_blocks</span> <span class='hs-keyglyph'>::</span> <span class='hs-layout'>(</span><span class='hs-conid'>Block</span> <span class='hs-varid'>m</span> <span class='hs-varid'>l</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Bool</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>BlockEnv</span> <span class='hs-layout'>(</span><span class='hs-conid'>Block</span> <span class='hs-varid'>m</span> <span class='hs-varid'>l</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>-></span>
<a name="line-403"></a> <span class='hs-conid'>Maybe</span> <span class='hs-layout'>(</span><span class='hs-conid'>Block</span> <span class='hs-varid'>m</span> <span class='hs-varid'>l</span><span class='hs-layout'>,</span> <span class='hs-conid'>BlockEnv</span> <span class='hs-layout'>(</span><span class='hs-conid'>Block</span> <span class='hs-varid'>m</span> <span class='hs-varid'>l</span><span class='hs-layout'>)</span><span class='hs-layout'>)</span>
<a name="line-404"></a><span class='hs-definition'>splitp_blocks</span> <span class='hs-varid'>p</span> <span class='hs-varid'>blocks</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>lift</span> <span class='hs-varop'>$</span> <span class='hs-varid'>foldBlockEnv'</span> <span class='hs-varid'>scan</span> <span class='hs-layout'>(</span><span class='hs-conid'>Nothing</span><span class='hs-layout'>,</span> <span class='hs-varid'>emptyBlockEnv</span><span class='hs-layout'>)</span> <span class='hs-varid'>blocks</span>
<a name="line-405"></a> <span class='hs-keyword'>where</span> <span class='hs-varid'>scan</span> <span class='hs-varid'>b</span> <span class='hs-layout'>(</span><span class='hs-varid'>yes</span><span class='hs-layout'>,</span> <span class='hs-varid'>no</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span>
<a name="line-406"></a> <span class='hs-keyword'>case</span> <span class='hs-varid'>yes</span> <span class='hs-keyword'>of</span>
<a name="line-407"></a> <span class='hs-conid'>Nothing</span> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>p</span> <span class='hs-varid'>b</span> <span class='hs-keyglyph'>-></span> <span class='hs-layout'>(</span><span class='hs-conid'>Just</span> <span class='hs-varid'>b</span><span class='hs-layout'>,</span> <span class='hs-varid'>no</span><span class='hs-layout'>)</span>
<a name="line-408"></a> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>otherwise</span> <span class='hs-keyglyph'>-></span> <span class='hs-layout'>(</span><span class='hs-varid'>yes</span><span class='hs-layout'>,</span> <span class='hs-varid'>insertBlock</span> <span class='hs-varid'>b</span> <span class='hs-varid'>no</span><span class='hs-layout'>)</span>
<a name="line-409"></a> <span class='hs-conid'>Just</span> <span class='hs-keyword'>_</span> <span class='hs-keyglyph'>-></span> <span class='hs-layout'>(</span><span class='hs-varid'>yes</span><span class='hs-layout'>,</span> <span class='hs-varid'>insertBlock</span> <span class='hs-varid'>b</span> <span class='hs-varid'>no</span><span class='hs-layout'>)</span>
<a name="line-410"></a> <span class='hs-varid'>lift</span> <span class='hs-layout'>(</span><span class='hs-conid'>Nothing</span><span class='hs-layout'>,</span> <span class='hs-keyword'>_</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>Nothing</span>
<a name="line-411"></a> <span class='hs-varid'>lift</span> <span class='hs-layout'>(</span><span class='hs-conid'>Just</span> <span class='hs-varid'>b</span><span class='hs-layout'>,</span> <span class='hs-varid'>bs</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>Just</span> <span class='hs-layout'>(</span><span class='hs-varid'>b</span><span class='hs-layout'>,</span> <span class='hs-varid'>bs</span><span class='hs-layout'>)</span>
<a name="line-412"></a>
<a name="line-413"></a><a name="insertBlock"></a><span class='hs-comment'>-- | 'insertBlock' should not be used to /replace/ an existing block</span>
<a name="line-414"></a><span class='hs-comment'>-- but only to insert a new one</span>
<a name="line-415"></a><span class='hs-definition'>insertBlock</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>Block</span> <span class='hs-varid'>m</span> <span class='hs-varid'>l</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>BlockEnv</span> <span class='hs-layout'>(</span><span class='hs-conid'>Block</span> <span class='hs-varid'>m</span> <span class='hs-varid'>l</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>BlockEnv</span> <span class='hs-layout'>(</span><span class='hs-conid'>Block</span> <span class='hs-varid'>m</span> <span class='hs-varid'>l</span><span class='hs-layout'>)</span>
<a name="line-416"></a><span class='hs-definition'>insertBlock</span> <span class='hs-varid'>b</span> <span class='hs-varid'>bs</span> <span class='hs-keyglyph'>=</span>
<a name="line-417"></a> <span class='hs-conid'>ASSERT</span> <span class='hs-layout'>(</span><span class='hs-varid'>isNothing</span> <span class='hs-varop'>$</span> <span class='hs-varid'>lookupBlockEnv</span> <span class='hs-varid'>bs</span> <span class='hs-varid'>id</span><span class='hs-layout'>)</span>
<a name="line-418"></a> <span class='hs-varid'>extendBlockEnv</span> <span class='hs-varid'>bs</span> <span class='hs-varid'>id</span> <span class='hs-varid'>b</span>
<a name="line-419"></a> <span class='hs-keyword'>where</span> <span class='hs-varid'>id</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>blockId</span> <span class='hs-varid'>b</span>
<a name="line-420"></a>
<a name="line-421"></a><a name="single_exit"></a><span class='hs-comment'>-- | Used in assertions; tells if a graph has exactly one exit</span>
<a name="line-422"></a><span class='hs-definition'>single_exit</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>LGraph</span> <span class='hs-varid'>l</span> <span class='hs-varid'>m</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Bool</span>
<a name="line-423"></a><span class='hs-definition'>single_exit</span> <span class='hs-varid'>g</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>foldBlockEnv'</span> <span class='hs-varid'>check</span> <span class='hs-num'>0</span> <span class='hs-layout'>(</span><span class='hs-varid'>lg_blocks</span> <span class='hs-varid'>g</span><span class='hs-layout'>)</span> <span class='hs-varop'>==</span> <span class='hs-num'>1</span>
<a name="line-424"></a> <span class='hs-keyword'>where</span> <span class='hs-varid'>check</span> <span class='hs-varid'>block</span> <span class='hs-varid'>count</span> <span class='hs-keyglyph'>=</span> <span class='hs-keyword'>case</span> <span class='hs-varid'>last</span> <span class='hs-layout'>(</span><span class='hs-varid'>unzip</span> <span class='hs-varid'>block</span><span class='hs-layout'>)</span> <span class='hs-keyword'>of</span>
<a name="line-425"></a> <span class='hs-conid'>LastExit</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>count</span> <span class='hs-varop'>+</span> <span class='hs-layout'>(</span><span class='hs-num'>1</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>Int</span><span class='hs-layout'>)</span>
<a name="line-426"></a> <span class='hs-keyword'>_</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>count</span>
<a name="line-427"></a>
<a name="line-428"></a><a name="single_exitg"></a><span class='hs-comment'>-- | Used in assertions; tells if a graph has exactly one exit</span>
<a name="line-429"></a><span class='hs-definition'>single_exitg</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>Graph</span> <span class='hs-varid'>l</span> <span class='hs-varid'>m</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Bool</span>
<a name="line-430"></a><span class='hs-definition'>single_exitg</span> <span class='hs-layout'>(</span><span class='hs-conid'>Graph</span> <span class='hs-varid'>tail</span> <span class='hs-varid'>blocks</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>foldBlockEnv'</span> <span class='hs-varid'>add</span> <span class='hs-layout'>(</span><span class='hs-varid'>exit_count</span> <span class='hs-layout'>(</span><span class='hs-varid'>lastTail</span> <span class='hs-varid'>tail</span><span class='hs-layout'>)</span><span class='hs-layout'>)</span> <span class='hs-varid'>blocks</span> <span class='hs-varop'>==</span> <span class='hs-num'>1</span>
<a name="line-431"></a> <span class='hs-keyword'>where</span> <span class='hs-varid'>add</span> <span class='hs-varid'>block</span> <span class='hs-varid'>count</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>count</span> <span class='hs-varop'>+</span> <span class='hs-varid'>exit_count</span> <span class='hs-layout'>(</span><span class='hs-varid'>last</span> <span class='hs-layout'>(</span><span class='hs-varid'>unzip</span> <span class='hs-varid'>block</span><span class='hs-layout'>)</span><span class='hs-layout'>)</span>
<a name="line-432"></a> <span class='hs-varid'>exit_count</span> <span class='hs-conid'>LastExit</span> <span class='hs-keyglyph'>=</span> <span class='hs-num'>1</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>Int</span>
<a name="line-433"></a> <span class='hs-varid'>exit_count</span> <span class='hs-keyword'>_</span> <span class='hs-keyglyph'>=</span> <span class='hs-num'>0</span>
<a name="line-434"></a>
<a name="line-435"></a><span class='hs-comment'>------------------ graph traversals</span>
<a name="line-436"></a>
<a name="line-437"></a><span class='hs-comment'>-- | This is the most important traversal over this data structure. It drops</span>
<a name="line-438"></a><span class='hs-comment'>-- unreachable code and puts blocks in an order that is good for solving forward</span>
<a name="line-439"></a><span class='hs-comment'>-- dataflow problems quickly. The reverse order is good for solving backward</span>
<a name="line-440"></a><span class='hs-comment'>-- dataflow problems quickly. The forward order is also reasonably good for</span>
<a name="line-441"></a><span class='hs-comment'>-- emitting instructions, except that it will not usually exploit Forrest</span>
<a name="line-442"></a><span class='hs-comment'>-- Baskett's trick of eliminating the unconditional branch from a loop. For</span>
<a name="line-443"></a><span class='hs-comment'>-- that you would need a more serious analysis, probably based on dominators, to</span>
<a name="line-444"></a><span class='hs-comment'>-- identify loop headers.</span>
<a name="line-445"></a><span class='hs-comment'>--</span>
<a name="line-446"></a><span class='hs-comment'>-- The ubiquity of 'postorder_dfs' is one reason for the ubiquity of the 'LGraph'</span>
<a name="line-447"></a><span class='hs-comment'>-- representation, when for most purposes the plain 'Graph' representation is</span>
<a name="line-448"></a><span class='hs-comment'>-- more mathematically elegant (but results in more complicated code).</span>
<a name="line-449"></a><span class='hs-comment'>--</span>
<a name="line-450"></a><span class='hs-comment'>-- Here's an easy way to go wrong! Consider</span>
<a name="line-451"></a><span class='hs-comment'>-- @</span>
<a name="line-452"></a><span class='hs-comment'>-- A -> [B,C]</span>
<a name="line-453"></a><span class='hs-comment'>-- B -> D</span>
<a name="line-454"></a><span class='hs-comment'>-- C -> D</span>
<a name="line-455"></a><span class='hs-comment'>-- @</span>
<a name="line-456"></a><span class='hs-comment'>-- Then ordinary dfs would give [A,B,D,C] which has a back ref from C to D.</span>
<a name="line-457"></a><span class='hs-comment'>-- Better to get [A,B,C,D]</span>
<a name="line-458"></a>
<a name="line-459"></a>
<a name="line-460"></a><span class='hs-definition'>postorder_dfs</span> <span class='hs-varid'>g</span><span class='hs-keyglyph'>@</span><span class='hs-layout'>(</span><span class='hs-conid'>LGraph</span> <span class='hs-keyword'>_</span> <span class='hs-varid'>blockenv</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span>
<a name="line-461"></a> <span class='hs-keyword'>let</span> <span class='hs-conid'>FGraph</span> <span class='hs-varid'>id</span> <span class='hs-varid'>eblock</span> <span class='hs-keyword'>_</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>entry</span> <span class='hs-varid'>g</span> <span class='hs-keyword'>in</span>
<a name="line-462"></a> <span class='hs-varid'>zip</span> <span class='hs-varid'>eblock</span> <span class='hs-conop'>:</span> <span class='hs-varid'>postorder_dfs_from_except</span> <span class='hs-varid'>blockenv</span> <span class='hs-varid'>eblock</span> <span class='hs-layout'>(</span><span class='hs-varid'>unitBlockSet</span> <span class='hs-varid'>id</span><span class='hs-layout'>)</span>
<a name="line-463"></a>
<a name="line-464"></a><a name="postorder_dfs_from_except"></a><span class='hs-definition'>postorder_dfs_from_except</span> <span class='hs-keyglyph'>::</span> <span class='hs-layout'>(</span><span class='hs-conid'>HavingSuccessors</span> <span class='hs-varid'>b</span><span class='hs-layout'>,</span> <span class='hs-conid'>LastNode</span> <span class='hs-varid'>l</span><span class='hs-layout'>)</span>
<a name="line-465"></a> <span class='hs-keyglyph'>=></span> <span class='hs-conid'>BlockEnv</span> <span class='hs-layout'>(</span><span class='hs-conid'>Block</span> <span class='hs-varid'>m</span> <span class='hs-varid'>l</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>b</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>BlockSet</span> <span class='hs-keyglyph'>-></span> <span class='hs-keyglyph'>[</span><span class='hs-conid'>Block</span> <span class='hs-varid'>m</span> <span class='hs-varid'>l</span><span class='hs-keyglyph'>]</span>
<a name="line-466"></a><span class='hs-definition'>postorder_dfs_from_except</span> <span class='hs-varid'>blocks</span> <span class='hs-varid'>b</span> <span class='hs-varid'>visited</span> <span class='hs-keyglyph'>=</span>
<a name="line-467"></a> <span class='hs-varid'>vchildren</span> <span class='hs-layout'>(</span><span class='hs-varid'>get_children</span> <span class='hs-varid'>b</span><span class='hs-layout'>)</span> <span class='hs-layout'>(</span><span class='hs-keyglyph'>\</span><span class='hs-varid'>acc</span> <span class='hs-sel'>_visited</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>acc</span><span class='hs-layout'>)</span> <span class='hs-conid'>[]</span> <span class='hs-varid'>visited</span>
<a name="line-468"></a> <span class='hs-keyword'>where</span>
<a name="line-469"></a> <span class='hs-comment'>-- vnode ::</span>
<a name="line-470"></a> <span class='hs-comment'>-- Block m l -> ([Block m l] -> BlockSet -> a) -> [Block m l] -> BlockSet -> a</span>
<a name="line-471"></a> <span class='hs-varid'>vnode</span> <span class='hs-varid'>block</span><span class='hs-keyglyph'>@</span><span class='hs-layout'>(</span><span class='hs-conid'>Block</span> <span class='hs-varid'>id</span> <span class='hs-keyword'>_</span><span class='hs-layout'>)</span> <span class='hs-varid'>cont</span> <span class='hs-varid'>acc</span> <span class='hs-varid'>visited</span> <span class='hs-keyglyph'>=</span>
<a name="line-472"></a> <span class='hs-keyword'>if</span> <span class='hs-varid'>elemBlockSet</span> <span class='hs-varid'>id</span> <span class='hs-varid'>visited</span> <span class='hs-keyword'>then</span>
<a name="line-473"></a> <span class='hs-varid'>cont</span> <span class='hs-varid'>acc</span> <span class='hs-varid'>visited</span>
<a name="line-474"></a> <span class='hs-keyword'>else</span>
<a name="line-475"></a> <span class='hs-keyword'>let</span> <span class='hs-varid'>cont'</span> <span class='hs-varid'>acc</span> <span class='hs-varid'>visited</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>cont</span> <span class='hs-layout'>(</span><span class='hs-varid'>block</span><span class='hs-conop'>:</span><span class='hs-varid'>acc</span><span class='hs-layout'>)</span> <span class='hs-varid'>visited</span> <span class='hs-keyword'>in</span>
<a name="line-476"></a> <span class='hs-varid'>vchildren</span> <span class='hs-layout'>(</span><span class='hs-varid'>get_children</span> <span class='hs-varid'>block</span><span class='hs-layout'>)</span> <span class='hs-varid'>cont'</span> <span class='hs-varid'>acc</span> <span class='hs-layout'>(</span><span class='hs-varid'>extendBlockSet</span> <span class='hs-varid'>visited</span> <span class='hs-varid'>id</span><span class='hs-layout'>)</span>
<a name="line-477"></a> <span class='hs-varid'>vchildren</span> <span class='hs-varid'>bs</span> <span class='hs-varid'>cont</span> <span class='hs-varid'>acc</span> <span class='hs-varid'>visited</span> <span class='hs-keyglyph'>=</span>
<a name="line-478"></a> <span class='hs-keyword'>let</span> <span class='hs-varid'>next</span> <span class='hs-varid'>children</span> <span class='hs-varid'>acc</span> <span class='hs-varid'>visited</span> <span class='hs-keyglyph'>=</span>
<a name="line-479"></a> <span class='hs-keyword'>case</span> <span class='hs-varid'>children</span> <span class='hs-keyword'>of</span> <span class='hs-conid'>[]</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>cont</span> <span class='hs-varid'>acc</span> <span class='hs-varid'>visited</span>
<a name="line-480"></a> <span class='hs-layout'>(</span><span class='hs-varid'>b</span><span class='hs-conop'>:</span><span class='hs-varid'>bs</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>vnode</span> <span class='hs-varid'>b</span> <span class='hs-layout'>(</span><span class='hs-varid'>next</span> <span class='hs-varid'>bs</span><span class='hs-layout'>)</span> <span class='hs-varid'>acc</span> <span class='hs-varid'>visited</span>
<a name="line-481"></a> <span class='hs-keyword'>in</span> <span class='hs-varid'>next</span> <span class='hs-varid'>bs</span> <span class='hs-varid'>acc</span> <span class='hs-varid'>visited</span>
<a name="line-482"></a> <span class='hs-varid'>get_children</span> <span class='hs-varid'>block</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>foldl</span> <span class='hs-varid'>add_id</span> <span class='hs-conid'>[]</span> <span class='hs-layout'>(</span><span class='hs-varid'>succs</span> <span class='hs-varid'>block</span><span class='hs-layout'>)</span>
<a name="line-483"></a> <span class='hs-varid'>add_id</span> <span class='hs-varid'>rst</span> <span class='hs-varid'>id</span> <span class='hs-keyglyph'>=</span> <span class='hs-keyword'>case</span> <span class='hs-varid'>lookupBlockEnv</span> <span class='hs-varid'>blocks</span> <span class='hs-varid'>id</span> <span class='hs-keyword'>of</span>
<a name="line-484"></a> <span class='hs-conid'>Just</span> <span class='hs-varid'>b</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>b</span> <span class='hs-conop'>:</span> <span class='hs-varid'>rst</span>
<a name="line-485"></a> <span class='hs-conid'>Nothing</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>rst</span>
<a name="line-486"></a>
<a name="line-487"></a><a name="postorder_dfs_from"></a><span class='hs-definition'>postorder_dfs_from</span>
<a name="line-488"></a> <span class='hs-keyglyph'>::</span> <span class='hs-layout'>(</span><span class='hs-conid'>HavingSuccessors</span> <span class='hs-varid'>b</span><span class='hs-layout'>,</span> <span class='hs-conid'>LastNode</span> <span class='hs-varid'>l</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=></span> <span class='hs-conid'>BlockEnv</span> <span class='hs-layout'>(</span><span class='hs-conid'>Block</span> <span class='hs-varid'>m</span> <span class='hs-varid'>l</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>b</span> <span class='hs-keyglyph'>-></span> <span class='hs-keyglyph'>[</span><span class='hs-conid'>Block</span> <span class='hs-varid'>m</span> <span class='hs-varid'>l</span><span class='hs-keyglyph'>]</span>
<a name="line-489"></a><span class='hs-definition'>postorder_dfs_from</span> <span class='hs-varid'>blocks</span> <span class='hs-varid'>b</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>postorder_dfs_from_except</span> <span class='hs-varid'>blocks</span> <span class='hs-varid'>b</span> <span class='hs-varid'>emptyBlockSet</span>
<a name="line-490"></a>
<a name="line-491"></a>
<a name="line-492"></a>
<a name="line-493"></a><span class='hs-comment'>-- | Slightly more complicated than the usual fold because we want to tell block</span>
<a name="line-494"></a><span class='hs-comment'>-- 'b1' what its inline successor is going to be, so that if 'b1' ends with</span>
<a name="line-495"></a><span class='hs-comment'>-- 'goto b2', the goto can be omitted.</span>
<a name="line-496"></a>
<a name="line-497"></a><span class='hs-definition'>fold_layout</span> <span class='hs-varid'>f</span> <span class='hs-varid'>z</span> <span class='hs-varid'>g</span><span class='hs-keyglyph'>@</span><span class='hs-layout'>(</span><span class='hs-conid'>LGraph</span> <span class='hs-varid'>eid</span> <span class='hs-keyword'>_</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>fold</span> <span class='hs-layout'>(</span><span class='hs-varid'>postorder_dfs</span> <span class='hs-varid'>g</span><span class='hs-layout'>)</span> <span class='hs-varid'>z</span>
<a name="line-498"></a> <span class='hs-keyword'>where</span> <span class='hs-varid'>fold</span> <span class='hs-varid'>blocks</span> <span class='hs-varid'>z</span> <span class='hs-keyglyph'>=</span>
<a name="line-499"></a> <span class='hs-keyword'>case</span> <span class='hs-varid'>blocks</span> <span class='hs-keyword'>of</span> <span class='hs-conid'>[]</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>z</span>
<a name="line-500"></a> <span class='hs-keyglyph'>[</span><span class='hs-varid'>b</span><span class='hs-keyglyph'>]</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>f</span> <span class='hs-varid'>b</span> <span class='hs-conid'>Nothing</span> <span class='hs-varid'>z</span>
<a name="line-501"></a> <span class='hs-varid'>b1</span> <span class='hs-conop'>:</span> <span class='hs-varid'>b2</span> <span class='hs-conop'>:</span> <span class='hs-varid'>bs</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>fold</span> <span class='hs-layout'>(</span><span class='hs-varid'>b2</span> <span class='hs-conop'>:</span> <span class='hs-varid'>bs</span><span class='hs-layout'>)</span> <span class='hs-layout'>(</span><span class='hs-varid'>f</span> <span class='hs-varid'>b1</span> <span class='hs-layout'>(</span><span class='hs-varid'>nextlabel</span> <span class='hs-varid'>b2</span><span class='hs-layout'>)</span> <span class='hs-varid'>z</span><span class='hs-layout'>)</span>
<a name="line-502"></a> <span class='hs-varid'>nextlabel</span> <span class='hs-layout'>(</span><span class='hs-conid'>Block</span> <span class='hs-varid'>id</span> <span class='hs-keyword'>_</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span>
<a name="line-503"></a> <span class='hs-keyword'>if</span> <span class='hs-varid'>id</span> <span class='hs-varop'>==</span> <span class='hs-varid'>eid</span> <span class='hs-keyword'>then</span> <span class='hs-varid'>panic</span> <span class='hs-str'>"entry as successor"</span>
<a name="line-504"></a> <span class='hs-keyword'>else</span> <span class='hs-conid'>Just</span> <span class='hs-varid'>id</span>
<a name="line-505"></a>
<a name="line-506"></a><span class='hs-comment'>-- | The rest of the traversals are straightforward</span>
<a name="line-507"></a>
<a name="line-508"></a><span class='hs-definition'>map_blocks</span> <span class='hs-varid'>f</span> <span class='hs-layout'>(</span><span class='hs-conid'>LGraph</span> <span class='hs-varid'>eid</span> <span class='hs-varid'>blocks</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>LGraph</span> <span class='hs-varid'>eid</span> <span class='hs-layout'>(</span><span class='hs-varid'>mapBlockEnv</span> <span class='hs-varid'>f</span> <span class='hs-varid'>blocks</span><span class='hs-layout'>)</span>
<a name="line-509"></a>
<a name="line-510"></a><span class='hs-definition'>map_nodes</span> <span class='hs-varid'>idm</span> <span class='hs-varid'>middle</span> <span class='hs-varid'>last</span> <span class='hs-layout'>(</span><span class='hs-conid'>LGraph</span> <span class='hs-varid'>eid</span> <span class='hs-varid'>blocks</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span>
<a name="line-511"></a> <span class='hs-conid'>LGraph</span> <span class='hs-layout'>(</span><span class='hs-varid'>idm</span> <span class='hs-varid'>eid</span><span class='hs-layout'>)</span> <span class='hs-layout'>(</span><span class='hs-varid'>mapBlockEnv</span> <span class='hs-layout'>(</span><span class='hs-varid'>map_one_block</span> <span class='hs-varid'>idm</span> <span class='hs-varid'>middle</span> <span class='hs-varid'>last</span><span class='hs-layout'>)</span> <span class='hs-varid'>blocks</span><span class='hs-layout'>)</span>
<a name="line-512"></a>
<a name="line-513"></a><span class='hs-definition'>map_one_block</span> <span class='hs-varid'>idm</span> <span class='hs-varid'>middle</span> <span class='hs-varid'>last</span> <span class='hs-layout'>(</span><span class='hs-conid'>Block</span> <span class='hs-varid'>id</span> <span class='hs-varid'>t</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>Block</span> <span class='hs-layout'>(</span><span class='hs-varid'>idm</span> <span class='hs-varid'>id</span><span class='hs-layout'>)</span> <span class='hs-layout'>(</span><span class='hs-varid'>tail</span> <span class='hs-varid'>t</span><span class='hs-layout'>)</span>
<a name="line-514"></a> <span class='hs-keyword'>where</span> <span class='hs-varid'>tail</span> <span class='hs-layout'>(</span><span class='hs-conid'>ZTail</span> <span class='hs-varid'>m</span> <span class='hs-varid'>t</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>ZTail</span> <span class='hs-layout'>(</span><span class='hs-varid'>middle</span> <span class='hs-varid'>m</span><span class='hs-layout'>)</span> <span class='hs-layout'>(</span><span class='hs-varid'>tail</span> <span class='hs-varid'>t</span><span class='hs-layout'>)</span>
<a name="line-515"></a> <span class='hs-varid'>tail</span> <span class='hs-layout'>(</span><span class='hs-conid'>ZLast</span> <span class='hs-conid'>LastExit</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>ZLast</span> <span class='hs-conid'>LastExit</span>
<a name="line-516"></a> <span class='hs-varid'>tail</span> <span class='hs-layout'>(</span><span class='hs-conid'>ZLast</span> <span class='hs-layout'>(</span><span class='hs-conid'>LastOther</span> <span class='hs-varid'>l</span><span class='hs-layout'>)</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>ZLast</span> <span class='hs-layout'>(</span><span class='hs-conid'>LastOther</span> <span class='hs-layout'>(</span><span class='hs-varid'>last</span> <span class='hs-varid'>l</span><span class='hs-layout'>)</span><span class='hs-layout'>)</span>
<a name="line-517"></a>
<a name="line-518"></a>
<a name="line-519"></a><span class='hs-definition'>mapM_blocks</span> <span class='hs-varid'>f</span> <span class='hs-layout'>(</span><span class='hs-conid'>LGraph</span> <span class='hs-varid'>eid</span> <span class='hs-varid'>blocks</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>blocks'</span> <span class='hs-varop'>>>=</span> <span class='hs-varid'>return</span> <span class='hs-varop'>.</span> <span class='hs-conid'>LGraph</span> <span class='hs-varid'>eid</span>
<a name="line-520"></a> <span class='hs-keyword'>where</span> <span class='hs-varid'>blocks'</span> <span class='hs-keyglyph'>=</span>
<a name="line-521"></a> <span class='hs-varid'>foldBlockEnv'</span> <span class='hs-layout'>(</span><span class='hs-keyglyph'>\</span><span class='hs-varid'>b</span> <span class='hs-varid'>mblocks</span> <span class='hs-keyglyph'>-></span> <span class='hs-keyword'>do</span> <span class='hs-layout'>{</span> <span class='hs-varid'>blocks</span> <span class='hs-keyglyph'><-</span> <span class='hs-varid'>mblocks</span>
<a name="line-522"></a> <span class='hs-layout'>;</span> <span class='hs-varid'>b</span> <span class='hs-keyglyph'><-</span> <span class='hs-varid'>f</span> <span class='hs-varid'>b</span>
<a name="line-523"></a> <span class='hs-layout'>;</span> <span class='hs-varid'>return</span> <span class='hs-varop'>$</span> <span class='hs-varid'>insertBlock</span> <span class='hs-varid'>b</span> <span class='hs-varid'>blocks</span> <span class='hs-layout'>}</span><span class='hs-layout'>)</span>
<a name="line-524"></a> <span class='hs-layout'>(</span><span class='hs-varid'>return</span> <span class='hs-varid'>emptyBlockEnv</span><span class='hs-layout'>)</span> <span class='hs-varid'>blocks</span>
<a name="line-525"></a>
<a name="line-526"></a><span class='hs-definition'>fold_blocks</span> <span class='hs-varid'>f</span> <span class='hs-varid'>z</span> <span class='hs-layout'>(</span><span class='hs-conid'>LGraph</span> <span class='hs-keyword'>_</span> <span class='hs-varid'>blocks</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>foldBlockEnv'</span> <span class='hs-varid'>f</span> <span class='hs-varid'>z</span> <span class='hs-varid'>blocks</span>
<a name="line-527"></a><span class='hs-definition'>fold_fwd_block</span> <span class='hs-varid'>first</span> <span class='hs-varid'>middle</span> <span class='hs-varid'>last</span> <span class='hs-layout'>(</span><span class='hs-conid'>Block</span> <span class='hs-varid'>id</span> <span class='hs-varid'>t</span><span class='hs-layout'>)</span> <span class='hs-varid'>z</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>tail</span> <span class='hs-varid'>t</span> <span class='hs-layout'>(</span><span class='hs-varid'>first</span> <span class='hs-varid'>id</span> <span class='hs-varid'>z</span><span class='hs-layout'>)</span>
<a name="line-528"></a> <span class='hs-keyword'>where</span> <span class='hs-varid'>tail</span> <span class='hs-layout'>(</span><span class='hs-conid'>ZTail</span> <span class='hs-varid'>m</span> <span class='hs-varid'>t</span><span class='hs-layout'>)</span> <span class='hs-varid'>z</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>tail</span> <span class='hs-varid'>t</span> <span class='hs-layout'>(</span><span class='hs-varid'>middle</span> <span class='hs-varid'>m</span> <span class='hs-varid'>z</span><span class='hs-layout'>)</span>
<a name="line-529"></a> <span class='hs-varid'>tail</span> <span class='hs-layout'>(</span><span class='hs-conid'>ZLast</span> <span class='hs-varid'>l</span><span class='hs-layout'>)</span> <span class='hs-varid'>z</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>last</span> <span class='hs-varid'>l</span> <span class='hs-varid'>z</span>
<a name="line-530"></a>
<a name="line-531"></a><span class='hs-definition'>of_block_list</span> <span class='hs-varid'>e</span> <span class='hs-varid'>blocks</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>LGraph</span> <span class='hs-varid'>e</span> <span class='hs-varop'>$</span> <span class='hs-varid'>foldr</span> <span class='hs-varid'>insertBlock</span> <span class='hs-varid'>emptyBlockEnv</span> <span class='hs-varid'>blocks</span>
<a name="line-532"></a><span class='hs-definition'>to_block_list</span> <span class='hs-layout'>(</span><span class='hs-conid'>LGraph</span> <span class='hs-keyword'>_</span> <span class='hs-varid'>blocks</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>eltsBlockEnv</span> <span class='hs-varid'>blocks</span>
<a name="line-533"></a>
<a name="line-534"></a>
<a name="line-535"></a><span class='hs-comment'>-- We want to be able to scrutinize a single-entry, single-exit 'LGraph' for</span>
<a name="line-536"></a><span class='hs-comment'>-- splicing purposes. There are two useful cases: the 'LGraph' is a single block</span>
<a name="line-537"></a><span class='hs-comment'>-- or it isn't. We use continuation-passing style.</span>
<a name="line-538"></a>
<a name="line-539"></a><a name="prepare_for_splicing"></a><span class='hs-definition'>prepare_for_splicing</span> <span class='hs-keyglyph'>::</span>
<a name="line-540"></a> <span class='hs-conid'>LGraph</span> <span class='hs-varid'>m</span> <span class='hs-varid'>l</span> <span class='hs-keyglyph'>-></span> <span class='hs-layout'>(</span><span class='hs-conid'>ZTail</span> <span class='hs-varid'>m</span> <span class='hs-varid'>l</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>a</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>-></span> <span class='hs-layout'>(</span><span class='hs-conid'>ZTail</span> <span class='hs-varid'>m</span> <span class='hs-varid'>l</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>ZHead</span> <span class='hs-varid'>m</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>BlockEnv</span> <span class='hs-layout'>(</span><span class='hs-conid'>Block</span> <span class='hs-varid'>m</span> <span class='hs-varid'>l</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>a</span><span class='hs-layout'>)</span>
<a name="line-541"></a> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>a</span>
<a name="line-542"></a><span class='hs-definition'>prepare_for_splicing</span> <span class='hs-varid'>g</span> <span class='hs-varid'>single</span> <span class='hs-varid'>multi</span> <span class='hs-keyglyph'>=</span>
<a name="line-543"></a> <span class='hs-keyword'>let</span> <span class='hs-conid'>FGraph</span> <span class='hs-keyword'>_</span> <span class='hs-varid'>gentry</span> <span class='hs-varid'>gblocks</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>entry</span> <span class='hs-varid'>g</span>
<a name="line-544"></a> <span class='hs-conid'>ZBlock</span> <span class='hs-keyword'>_</span> <span class='hs-varid'>etail</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>gentry</span>
<a name="line-545"></a> <span class='hs-keyword'>in</span> <span class='hs-keyword'>if</span> <span class='hs-varid'>isNullBEnv</span> <span class='hs-varid'>gblocks</span> <span class='hs-keyword'>then</span>
<a name="line-546"></a> <span class='hs-keyword'>case</span> <span class='hs-varid'>last</span> <span class='hs-varid'>gentry</span> <span class='hs-keyword'>of</span>
<a name="line-547"></a> <span class='hs-conid'>LastExit</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>single</span> <span class='hs-varid'>etail</span>
<a name="line-548"></a> <span class='hs-keyword'>_</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>panic</span> <span class='hs-str'>"bad single block"</span>
<a name="line-549"></a> <span class='hs-keyword'>else</span>
<a name="line-550"></a> <span class='hs-keyword'>case</span> <span class='hs-varid'>splitp_blocks</span> <span class='hs-varid'>is_exit</span> <span class='hs-varid'>gblocks</span> <span class='hs-keyword'>of</span>
<a name="line-551"></a> <span class='hs-conid'>Nothing</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>panic</span> <span class='hs-str'>"Can't find an exit block"</span>
<a name="line-552"></a> <span class='hs-conid'>Just</span> <span class='hs-layout'>(</span><span class='hs-varid'>gexit</span><span class='hs-layout'>,</span> <span class='hs-varid'>gblocks</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>-></span>
<a name="line-553"></a> <span class='hs-keyword'>let</span> <span class='hs-layout'>(</span><span class='hs-varid'>gh</span><span class='hs-layout'>,</span> <span class='hs-varid'>gl</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>goto_end</span> <span class='hs-varop'>$</span> <span class='hs-varid'>unzip</span> <span class='hs-varid'>gexit</span> <span class='hs-keyword'>in</span>
<a name="line-554"></a> <span class='hs-keyword'>case</span> <span class='hs-varid'>gl</span> <span class='hs-keyword'>of</span> <span class='hs-conid'>LastExit</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>multi</span> <span class='hs-varid'>etail</span> <span class='hs-varid'>gh</span> <span class='hs-varid'>gblocks</span>
<a name="line-555"></a> <span class='hs-keyword'>_</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>panic</span> <span class='hs-str'>"exit is not exit?!"</span>
<a name="line-556"></a>
<a name="line-557"></a><a name="prepare_for_splicing'"></a><span class='hs-definition'>prepare_for_splicing'</span> <span class='hs-keyglyph'>::</span>
<a name="line-558"></a> <span class='hs-conid'>Graph</span> <span class='hs-varid'>m</span> <span class='hs-varid'>l</span> <span class='hs-keyglyph'>-></span> <span class='hs-layout'>(</span><span class='hs-conid'>ZTail</span> <span class='hs-varid'>m</span> <span class='hs-varid'>l</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>a</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>-></span> <span class='hs-layout'>(</span><span class='hs-conid'>ZTail</span> <span class='hs-varid'>m</span> <span class='hs-varid'>l</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>ZHead</span> <span class='hs-varid'>m</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>BlockEnv</span> <span class='hs-layout'>(</span><span class='hs-conid'>Block</span> <span class='hs-varid'>m</span> <span class='hs-varid'>l</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>a</span><span class='hs-layout'>)</span>
<a name="line-559"></a> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>a</span>
<a name="line-560"></a><span class='hs-definition'>prepare_for_splicing'</span> <span class='hs-layout'>(</span><span class='hs-conid'>Graph</span> <span class='hs-varid'>etail</span> <span class='hs-varid'>gblocks</span><span class='hs-layout'>)</span> <span class='hs-varid'>single</span> <span class='hs-varid'>multi</span> <span class='hs-keyglyph'>=</span>
<a name="line-561"></a> <span class='hs-keyword'>if</span> <span class='hs-varid'>isNullBEnv</span> <span class='hs-varid'>gblocks</span> <span class='hs-keyword'>then</span>
<a name="line-562"></a> <span class='hs-keyword'>case</span> <span class='hs-varid'>lastTail</span> <span class='hs-varid'>etail</span> <span class='hs-keyword'>of</span>
<a name="line-563"></a> <span class='hs-conid'>LastExit</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>single</span> <span class='hs-varid'>etail</span>
<a name="line-564"></a> <span class='hs-keyword'>_</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>panic</span> <span class='hs-str'>"bad single block"</span>
<a name="line-565"></a> <span class='hs-keyword'>else</span>
<a name="line-566"></a> <span class='hs-keyword'>case</span> <span class='hs-varid'>splitp_blocks</span> <span class='hs-varid'>is_exit</span> <span class='hs-varid'>gblocks</span> <span class='hs-keyword'>of</span>
<a name="line-567"></a> <span class='hs-conid'>Nothing</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>panic</span> <span class='hs-str'>"Can't find an exit block"</span>
<a name="line-568"></a> <span class='hs-conid'>Just</span> <span class='hs-layout'>(</span><span class='hs-varid'>gexit</span><span class='hs-layout'>,</span> <span class='hs-varid'>gblocks</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>-></span>
<a name="line-569"></a> <span class='hs-keyword'>let</span> <span class='hs-layout'>(</span><span class='hs-varid'>gh</span><span class='hs-layout'>,</span> <span class='hs-varid'>gl</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>goto_end</span> <span class='hs-varop'>$</span> <span class='hs-varid'>unzip</span> <span class='hs-varid'>gexit</span> <span class='hs-keyword'>in</span>
<a name="line-570"></a> <span class='hs-keyword'>case</span> <span class='hs-varid'>gl</span> <span class='hs-keyword'>of</span> <span class='hs-conid'>LastExit</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>multi</span> <span class='hs-varid'>etail</span> <span class='hs-varid'>gh</span> <span class='hs-varid'>gblocks</span>
<a name="line-571"></a> <span class='hs-keyword'>_</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>panic</span> <span class='hs-str'>"exit is not exit?!"</span>
<a name="line-572"></a>
<a name="line-573"></a><a name="is_exit"></a><span class='hs-definition'>is_exit</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>Block</span> <span class='hs-varid'>m</span> <span class='hs-varid'>l</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Bool</span>
<a name="line-574"></a><span class='hs-definition'>is_exit</span> <span class='hs-varid'>b</span> <span class='hs-keyglyph'>=</span> <span class='hs-keyword'>case</span> <span class='hs-varid'>last</span> <span class='hs-layout'>(</span><span class='hs-varid'>unzip</span> <span class='hs-varid'>b</span><span class='hs-layout'>)</span> <span class='hs-keyword'>of</span> <span class='hs-layout'>{</span> <span class='hs-conid'>LastExit</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>True</span><span class='hs-layout'>;</span> <span class='hs-keyword'>_</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>False</span> <span class='hs-layout'>}</span>
<a name="line-575"></a>
<a name="line-576"></a><span class='hs-definition'>splice_head</span> <span class='hs-varid'>head</span> <span class='hs-varid'>g</span><span class='hs-keyglyph'>@</span><span class='hs-layout'>(</span><span class='hs-conid'>LGraph</span> <span class='hs-keyword'>_</span> <span class='hs-keyword'>_</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span>
<a name="line-577"></a> <span class='hs-conid'>ASSERT</span> <span class='hs-layout'>(</span><span class='hs-varid'>single_exit</span> <span class='hs-varid'>g</span><span class='hs-layout'>)</span> <span class='hs-varid'>prepare_for_splicing</span> <span class='hs-varid'>g</span> <span class='hs-varid'>splice_one_block</span> <span class='hs-varid'>splice_many_blocks</span>
<a name="line-578"></a> <span class='hs-keyword'>where</span> <span class='hs-varid'>eid</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>head_id</span> <span class='hs-varid'>head</span>
<a name="line-579"></a> <span class='hs-varid'>splice_one_block</span> <span class='hs-varid'>tail'</span> <span class='hs-keyglyph'>=</span>
<a name="line-580"></a> <span class='hs-keyword'>case</span> <span class='hs-varid'>ht_to_last</span> <span class='hs-varid'>head</span> <span class='hs-varid'>tail'</span> <span class='hs-keyword'>of</span>
<a name="line-581"></a> <span class='hs-layout'>(</span><span class='hs-varid'>head</span><span class='hs-layout'>,</span> <span class='hs-conid'>LastExit</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>-></span> <span class='hs-layout'>(</span><span class='hs-conid'>LGraph</span> <span class='hs-varid'>eid</span> <span class='hs-varid'>emptyBlockEnv</span><span class='hs-layout'>,</span> <span class='hs-varid'>head</span><span class='hs-layout'>)</span>
<a name="line-582"></a> <span class='hs-keyword'>_</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>panic</span> <span class='hs-str'>"spliced LGraph without exit"</span>
<a name="line-583"></a> <span class='hs-varid'>splice_many_blocks</span> <span class='hs-varid'>entry</span> <span class='hs-varid'>exit</span> <span class='hs-varid'>others</span> <span class='hs-keyglyph'>=</span>
<a name="line-584"></a> <span class='hs-layout'>(</span><span class='hs-conid'>LGraph</span> <span class='hs-varid'>eid</span> <span class='hs-layout'>(</span><span class='hs-varid'>insertBlock</span> <span class='hs-layout'>(</span><span class='hs-varid'>zipht</span> <span class='hs-varid'>head</span> <span class='hs-varid'>entry</span><span class='hs-layout'>)</span> <span class='hs-varid'>others</span><span class='hs-layout'>)</span><span class='hs-layout'>,</span> <span class='hs-varid'>exit</span><span class='hs-layout'>)</span>
<a name="line-585"></a>
<a name="line-586"></a><span class='hs-definition'>splice_head'</span> <span class='hs-varid'>head</span> <span class='hs-varid'>g</span> <span class='hs-keyglyph'>=</span>
<a name="line-587"></a> <span class='hs-conid'>ASSERT</span> <span class='hs-layout'>(</span><span class='hs-varid'>single_exitg</span> <span class='hs-varid'>g</span><span class='hs-layout'>)</span> <span class='hs-varid'>prepare_for_splicing'</span> <span class='hs-varid'>g</span> <span class='hs-varid'>splice_one_block</span> <span class='hs-varid'>splice_many_blocks</span>
<a name="line-588"></a> <span class='hs-keyword'>where</span> <span class='hs-varid'>splice_one_block</span> <span class='hs-varid'>tail'</span> <span class='hs-keyglyph'>=</span>
<a name="line-589"></a> <span class='hs-keyword'>case</span> <span class='hs-varid'>ht_to_last</span> <span class='hs-varid'>head</span> <span class='hs-varid'>tail'</span> <span class='hs-keyword'>of</span>
<a name="line-590"></a> <span class='hs-layout'>(</span><span class='hs-varid'>head</span><span class='hs-layout'>,</span> <span class='hs-conid'>LastExit</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>-></span> <span class='hs-layout'>(</span><span class='hs-varid'>emptyBlockEnv</span><span class='hs-layout'>,</span> <span class='hs-varid'>head</span><span class='hs-layout'>)</span>
<a name="line-591"></a> <span class='hs-keyword'>_</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>panic</span> <span class='hs-str'>"spliced LGraph without exit"</span>
<a name="line-592"></a> <span class='hs-varid'>splice_many_blocks</span> <span class='hs-varid'>entry</span> <span class='hs-varid'>exit</span> <span class='hs-varid'>others</span> <span class='hs-keyglyph'>=</span>
<a name="line-593"></a> <span class='hs-layout'>(</span><span class='hs-varid'>insertBlock</span> <span class='hs-layout'>(</span><span class='hs-varid'>zipht</span> <span class='hs-varid'>head</span> <span class='hs-varid'>entry</span><span class='hs-layout'>)</span> <span class='hs-varid'>others</span><span class='hs-layout'>,</span> <span class='hs-varid'>exit</span><span class='hs-layout'>)</span>
<a name="line-594"></a>
<a name="line-595"></a><span class='hs-comment'>-- splice_tail :: Graph m l -> ZTail m l -> Graph m l</span>
<a name="line-596"></a><span class='hs-definition'>splice_tail</span> <span class='hs-varid'>g</span> <span class='hs-varid'>tail</span> <span class='hs-keyglyph'>=</span>
<a name="line-597"></a> <span class='hs-conid'>ASSERT</span> <span class='hs-layout'>(</span><span class='hs-varid'>single_exitg</span> <span class='hs-varid'>g</span><span class='hs-layout'>)</span> <span class='hs-varid'>prepare_for_splicing'</span> <span class='hs-varid'>g</span> <span class='hs-varid'>splice_one_block</span> <span class='hs-varid'>splice_many_blocks</span>
<a name="line-598"></a> <span class='hs-keyword'>where</span> <span class='hs-varid'>splice_one_block</span> <span class='hs-varid'>tail'</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>Graph</span> <span class='hs-layout'>(</span><span class='hs-varid'>tail'</span> <span class='hs-varop'>`append_tails`</span> <span class='hs-varid'>tail</span><span class='hs-layout'>)</span> <span class='hs-varid'>emptyBlockEnv</span>
<a name="line-599"></a> <span class='hs-varid'>append_tails</span> <span class='hs-layout'>(</span><span class='hs-conid'>ZLast</span> <span class='hs-conid'>LastExit</span><span class='hs-layout'>)</span> <span class='hs-varid'>tail</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>tail</span>
<a name="line-600"></a> <span class='hs-varid'>append_tails</span> <span class='hs-layout'>(</span><span class='hs-conid'>ZLast</span> <span class='hs-keyword'>_</span><span class='hs-layout'>)</span> <span class='hs-keyword'>_</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>panic</span> <span class='hs-str'>"spliced single block without LastExit"</span>
<a name="line-601"></a> <span class='hs-varid'>append_tails</span> <span class='hs-layout'>(</span><span class='hs-conid'>ZTail</span> <span class='hs-varid'>m</span> <span class='hs-varid'>t</span><span class='hs-layout'>)</span> <span class='hs-varid'>tail</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>ZTail</span> <span class='hs-varid'>m</span> <span class='hs-layout'>(</span><span class='hs-varid'>append_tails</span> <span class='hs-varid'>t</span> <span class='hs-varid'>tail</span><span class='hs-layout'>)</span>
<a name="line-602"></a> <span class='hs-varid'>splice_many_blocks</span> <span class='hs-varid'>entry</span> <span class='hs-varid'>exit</span> <span class='hs-varid'>others</span> <span class='hs-keyglyph'>=</span>
<a name="line-603"></a> <span class='hs-conid'>Graph</span> <span class='hs-varid'>entry</span> <span class='hs-layout'>(</span><span class='hs-varid'>insertBlock</span> <span class='hs-layout'>(</span><span class='hs-varid'>zipht</span> <span class='hs-varid'>exit</span> <span class='hs-varid'>tail</span><span class='hs-layout'>)</span> <span class='hs-varid'>others</span><span class='hs-layout'>)</span>
<a name="line-604"></a>
<a name="line-605"></a><span class='hs-comment'>{-
<a name="line-606"></a>splice_tail g tail =
<a name="line-607"></a> AS SERT (single_exit g) prepare_for_splicing g splice_one_block splice_many_blocks
<a name="line-608"></a> where splice_one_block tail' = -- return tail' .. tail
<a name="line-609"></a> case ht_to_last (ZFirst (lg_entry g)) tail' of
<a name="line-610"></a> (head', LastExit) ->
<a name="line-611"></a> case ht_to_block head' tail of
<a name="line-612"></a> Block id t | id == lg_entry g -> (t, LGraph id emptyBlockEnv)
<a name="line-613"></a> _ -> panic "entry in; garbage out"
<a name="line-614"></a> _ -> panic "spliced single block without Exit"
<a name="line-615"></a> splice_many_blocks entry exit others =
<a name="line-616"></a> (entry, LGraph (lg_entry g) (insertBlock (zipht exit tail) others))
<a name="line-617"></a>-}</span>
<a name="line-618"></a>
<a name="line-619"></a><span class='hs-definition'>splice_head_only</span> <span class='hs-varid'>head</span> <span class='hs-varid'>g</span> <span class='hs-keyglyph'>=</span>
<a name="line-620"></a> <span class='hs-keyword'>let</span> <span class='hs-conid'>FGraph</span> <span class='hs-varid'>eid</span> <span class='hs-varid'>gentry</span> <span class='hs-varid'>gblocks</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>entry</span> <span class='hs-varid'>g</span>
<a name="line-621"></a> <span class='hs-keyword'>in</span> <span class='hs-keyword'>case</span> <span class='hs-varid'>gentry</span> <span class='hs-keyword'>of</span>
<a name="line-622"></a> <span class='hs-conid'>ZBlock</span> <span class='hs-layout'>(</span><span class='hs-conid'>ZFirst</span> <span class='hs-keyword'>_</span><span class='hs-layout'>)</span> <span class='hs-varid'>tail</span> <span class='hs-keyglyph'>-></span>
<a name="line-623"></a> <span class='hs-conid'>LGraph</span> <span class='hs-varid'>eid</span> <span class='hs-layout'>(</span><span class='hs-varid'>insertBlock</span> <span class='hs-layout'>(</span><span class='hs-varid'>zipht</span> <span class='hs-varid'>head</span> <span class='hs-varid'>tail</span><span class='hs-layout'>)</span> <span class='hs-varid'>gblocks</span><span class='hs-layout'>)</span>
<a name="line-624"></a> <span class='hs-keyword'>_</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>panic</span> <span class='hs-str'>"entry not at start of block?!"</span>
<a name="line-625"></a>
<a name="line-626"></a><span class='hs-definition'>splice_head_only'</span> <span class='hs-varid'>head</span> <span class='hs-layout'>(</span><span class='hs-conid'>Graph</span> <span class='hs-varid'>tail</span> <span class='hs-varid'>gblocks</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span>
<a name="line-627"></a> <span class='hs-keyword'>let</span> <span class='hs-varid'>eblock</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>zipht</span> <span class='hs-varid'>head</span> <span class='hs-varid'>tail</span> <span class='hs-keyword'>in</span>
<a name="line-628"></a> <span class='hs-conid'>LGraph</span> <span class='hs-layout'>(</span><span class='hs-varid'>blockId</span> <span class='hs-varid'>eblock</span><span class='hs-layout'>)</span> <span class='hs-layout'>(</span><span class='hs-varid'>insertBlock</span> <span class='hs-varid'>eblock</span> <span class='hs-varid'>gblocks</span><span class='hs-layout'>)</span>
<a name="line-629"></a> <span class='hs-comment'>-- the offset probably should never be used, but well, it's correct for this LGraph</span>
<a name="line-630"></a>
<a name="line-631"></a>
<a name="line-632"></a><span class='hs-comment'>--- Translation</span>
<a name="line-633"></a>
<a name="line-634"></a><span class='hs-definition'>translate</span> <span class='hs-varid'>txm</span> <span class='hs-varid'>txl</span> <span class='hs-layout'>(</span><span class='hs-conid'>LGraph</span> <span class='hs-varid'>eid</span> <span class='hs-varid'>blocks</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span>
<a name="line-635"></a> <span class='hs-keyword'>do</span> <span class='hs-varid'>blocks'</span> <span class='hs-keyglyph'><-</span> <span class='hs-varid'>foldBlockEnv'</span> <span class='hs-varid'>txblock</span> <span class='hs-layout'>(</span><span class='hs-varid'>return</span> <span class='hs-varid'>emptyBlockEnv</span><span class='hs-layout'>)</span> <span class='hs-varid'>blocks</span>
<a name="line-636"></a> <span class='hs-varid'>return</span> <span class='hs-varop'>$</span> <span class='hs-conid'>LGraph</span> <span class='hs-varid'>eid</span> <span class='hs-varid'>blocks'</span>
<a name="line-637"></a> <span class='hs-keyword'>where</span>
<a name="line-638"></a> <span class='hs-comment'>-- txblock ::</span>
<a name="line-639"></a> <span class='hs-comment'>-- Block m l -> tm (BlockEnv (Block m' l')) -> tm (BlockEnv (Block m' l'))</span>
<a name="line-640"></a> <span class='hs-varid'>txblock</span> <span class='hs-layout'>(</span><span class='hs-conid'>Block</span> <span class='hs-varid'>id</span> <span class='hs-varid'>t</span><span class='hs-layout'>)</span> <span class='hs-varid'>expanded</span> <span class='hs-keyglyph'>=</span>
<a name="line-641"></a> <span class='hs-keyword'>do</span> <span class='hs-varid'>blocks'</span> <span class='hs-keyglyph'><-</span> <span class='hs-varid'>expanded</span>
<a name="line-642"></a> <span class='hs-varid'>txtail</span> <span class='hs-layout'>(</span><span class='hs-conid'>ZFirst</span> <span class='hs-varid'>id</span><span class='hs-layout'>)</span> <span class='hs-varid'>t</span> <span class='hs-varid'>blocks'</span>
<a name="line-643"></a> <span class='hs-comment'>-- txtail :: ZHead m' -> ZTail m l -> BlockEnv (Block m' l') -></span>
<a name="line-644"></a> <span class='hs-comment'>-- tm (BlockEnv (Block m' l'))</span>
<a name="line-645"></a> <span class='hs-varid'>txtail</span> <span class='hs-varid'>h</span> <span class='hs-layout'>(</span><span class='hs-conid'>ZTail</span> <span class='hs-varid'>m</span> <span class='hs-varid'>t</span><span class='hs-layout'>)</span> <span class='hs-varid'>blocks'</span> <span class='hs-keyglyph'>=</span>
<a name="line-646"></a> <span class='hs-keyword'>do</span> <span class='hs-varid'>m'</span> <span class='hs-keyglyph'><-</span> <span class='hs-varid'>txm</span> <span class='hs-varid'>m</span>
<a name="line-647"></a> <span class='hs-keyword'>let</span> <span class='hs-layout'>(</span><span class='hs-varid'>g</span><span class='hs-layout'>,</span> <span class='hs-varid'>h'</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>splice_head</span> <span class='hs-varid'>h</span> <span class='hs-varid'>m'</span>
<a name="line-648"></a> <span class='hs-varid'>txtail</span> <span class='hs-varid'>h'</span> <span class='hs-varid'>t</span> <span class='hs-layout'>(</span><span class='hs-varid'>plusBlockEnv</span> <span class='hs-layout'>(</span><span class='hs-varid'>lg_blocks</span> <span class='hs-varid'>g</span><span class='hs-layout'>)</span> <span class='hs-varid'>blocks'</span><span class='hs-layout'>)</span>
<a name="line-649"></a> <span class='hs-varid'>txtail</span> <span class='hs-varid'>h</span> <span class='hs-layout'>(</span><span class='hs-conid'>ZLast</span> <span class='hs-layout'>(</span><span class='hs-conid'>LastOther</span> <span class='hs-varid'>l</span><span class='hs-layout'>)</span><span class='hs-layout'>)</span> <span class='hs-varid'>blocks'</span> <span class='hs-keyglyph'>=</span>
<a name="line-650"></a> <span class='hs-keyword'>do</span> <span class='hs-varid'>l'</span> <span class='hs-keyglyph'><-</span> <span class='hs-varid'>txl</span> <span class='hs-varid'>l</span>
<a name="line-651"></a> <span class='hs-varid'>return</span> <span class='hs-varop'>$</span> <span class='hs-varid'>plusBlockEnv</span> <span class='hs-layout'>(</span><span class='hs-varid'>lg_blocks</span> <span class='hs-layout'>(</span><span class='hs-varid'>splice_head_only</span> <span class='hs-varid'>h</span> <span class='hs-varid'>l'</span><span class='hs-layout'>)</span><span class='hs-layout'>)</span> <span class='hs-varid'>blocks'</span>
<a name="line-652"></a> <span class='hs-varid'>txtail</span> <span class='hs-varid'>h</span> <span class='hs-layout'>(</span><span class='hs-conid'>ZLast</span> <span class='hs-conid'>LastExit</span><span class='hs-layout'>)</span> <span class='hs-varid'>blocks'</span> <span class='hs-keyglyph'>=</span>
<a name="line-653"></a> <span class='hs-varid'>return</span> <span class='hs-varop'>$</span> <span class='hs-varid'>insertBlock</span> <span class='hs-layout'>(</span><span class='hs-varid'>zipht</span> <span class='hs-varid'>h</span> <span class='hs-layout'>(</span><span class='hs-conid'>ZLast</span> <span class='hs-conid'>LastExit</span><span class='hs-layout'>)</span><span class='hs-layout'>)</span> <span class='hs-varid'>blocks'</span>
<a name="line-654"></a>
<a name="line-655"></a><span class='hs-comment'>----------------------------------------------------------------</span>
<a name="line-656"></a><span class='hs-comment'>---- Prettyprinting</span>
<a name="line-657"></a><span class='hs-comment'>----------------------------------------------------------------</span>
<a name="line-658"></a>
<a name="line-659"></a><span class='hs-comment'>-- putting this code in PprCmmZ leads to circular imports :-(</span>
<a name="line-660"></a>
<a name="line-661"></a><span class='hs-keyword'>instance</span> <span class='hs-layout'>(</span><span class='hs-conid'>Outputable</span> <span class='hs-varid'>m</span><span class='hs-layout'>,</span> <span class='hs-conid'>Outputable</span> <span class='hs-varid'>l</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=></span> <span class='hs-conid'>Outputable</span> <span class='hs-layout'>(</span><span class='hs-conid'>ZTail</span> <span class='hs-varid'>m</span> <span class='hs-varid'>l</span><span class='hs-layout'>)</span> <span class='hs-keyword'>where</span>
<a name="line-662"></a> <span class='hs-varid'>ppr</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>pprTail</span>
<a name="line-663"></a>
<a name="line-664"></a><span class='hs-keyword'>instance</span> <span class='hs-layout'>(</span><span class='hs-conid'>Outputable</span> <span class='hs-varid'>m</span><span class='hs-layout'>,</span> <span class='hs-conid'>Outputable</span> <span class='hs-varid'>l</span><span class='hs-layout'>,</span> <span class='hs-conid'>LastNode</span> <span class='hs-varid'>l</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=></span> <span class='hs-conid'>Outputable</span> <span class='hs-layout'>(</span><span class='hs-conid'>Graph</span> <span class='hs-varid'>m</span> <span class='hs-varid'>l</span><span class='hs-layout'>)</span> <span class='hs-keyword'>where</span>
<a name="line-665"></a> <span class='hs-varid'>ppr</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>pprGraph</span>
<a name="line-666"></a>
<a name="line-667"></a><span class='hs-keyword'>instance</span> <span class='hs-layout'>(</span><span class='hs-conid'>Outputable</span> <span class='hs-varid'>m</span><span class='hs-layout'>,</span> <span class='hs-conid'>Outputable</span> <span class='hs-varid'>l</span><span class='hs-layout'>,</span> <span class='hs-conid'>LastNode</span> <span class='hs-varid'>l</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=></span> <span class='hs-conid'>Outputable</span> <span class='hs-layout'>(</span><span class='hs-conid'>LGraph</span> <span class='hs-varid'>m</span> <span class='hs-varid'>l</span><span class='hs-layout'>)</span> <span class='hs-keyword'>where</span>
<a name="line-668"></a> <span class='hs-varid'>ppr</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>pprLgraph</span>
<a name="line-669"></a>
<a name="line-670"></a><span class='hs-keyword'>instance</span> <span class='hs-layout'>(</span><span class='hs-conid'>Outputable</span> <span class='hs-varid'>m</span><span class='hs-layout'>,</span> <span class='hs-conid'>Outputable</span> <span class='hs-varid'>l</span><span class='hs-layout'>,</span> <span class='hs-conid'>LastNode</span> <span class='hs-varid'>l</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=></span> <span class='hs-conid'>Outputable</span> <span class='hs-layout'>(</span><span class='hs-conid'>Block</span> <span class='hs-varid'>m</span> <span class='hs-varid'>l</span><span class='hs-layout'>)</span> <span class='hs-keyword'>where</span>
<a name="line-671"></a> <span class='hs-varid'>ppr</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>pprBlock</span>
<a name="line-672"></a>
<a name="line-673"></a><span class='hs-keyword'>instance</span> <span class='hs-layout'>(</span><span class='hs-conid'>Outputable</span> <span class='hs-varid'>l</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=></span> <span class='hs-conid'>Outputable</span> <span class='hs-layout'>(</span><span class='hs-conid'>ZLast</span> <span class='hs-varid'>l</span><span class='hs-layout'>)</span> <span class='hs-keyword'>where</span>
<a name="line-674"></a> <span class='hs-varid'>ppr</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>pprLast</span>
<a name="line-675"></a>
<a name="line-676"></a><a name="pprTail"></a><span class='hs-definition'>pprTail</span> <span class='hs-keyglyph'>::</span> <span class='hs-layout'>(</span><span class='hs-conid'>Outputable</span> <span class='hs-varid'>m</span><span class='hs-layout'>,</span> <span class='hs-conid'>Outputable</span> <span class='hs-varid'>l</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=></span> <span class='hs-conid'>ZTail</span> <span class='hs-varid'>m</span> <span class='hs-varid'>l</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>SDoc</span>
<a name="line-677"></a><span class='hs-definition'>pprTail</span> <span class='hs-layout'>(</span><span class='hs-conid'>ZTail</span> <span class='hs-varid'>m</span> <span class='hs-varid'>t</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>ppr</span> <span class='hs-varid'>m</span> <span class='hs-varop'>$$</span> <span class='hs-varid'>ppr</span> <span class='hs-varid'>t</span>
<a name="line-678"></a><span class='hs-definition'>pprTail</span> <span class='hs-layout'>(</span><span class='hs-conid'>ZLast</span> <span class='hs-varid'>l</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>ppr</span> <span class='hs-varid'>l</span>
<a name="line-679"></a>
<a name="line-680"></a><a name="pprLast"></a><span class='hs-definition'>pprLast</span> <span class='hs-keyglyph'>::</span> <span class='hs-layout'>(</span><span class='hs-conid'>Outputable</span> <span class='hs-varid'>l</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=></span> <span class='hs-conid'>ZLast</span> <span class='hs-varid'>l</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>SDoc</span>
<a name="line-681"></a><span class='hs-definition'>pprLast</span> <span class='hs-conid'>LastExit</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>text</span> <span class='hs-str'>"<exit>"</span>
<a name="line-682"></a><span class='hs-definition'>pprLast</span> <span class='hs-layout'>(</span><span class='hs-conid'>LastOther</span> <span class='hs-varid'>l</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>ppr</span> <span class='hs-varid'>l</span>
<a name="line-683"></a>
<a name="line-684"></a><a name="pprBlock"></a><span class='hs-definition'>pprBlock</span> <span class='hs-keyglyph'>::</span> <span class='hs-layout'>(</span><span class='hs-conid'>Outputable</span> <span class='hs-varid'>m</span><span class='hs-layout'>,</span> <span class='hs-conid'>Outputable</span> <span class='hs-varid'>l</span><span class='hs-layout'>,</span> <span class='hs-conid'>LastNode</span> <span class='hs-varid'>l</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=></span> <span class='hs-conid'>Block</span> <span class='hs-varid'>m</span> <span class='hs-varid'>l</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>SDoc</span>
<a name="line-685"></a><span class='hs-definition'>pprBlock</span> <span class='hs-layout'>(</span><span class='hs-conid'>Block</span> <span class='hs-varid'>id</span> <span class='hs-varid'>tail</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span>
<a name="line-686"></a> <span class='hs-varid'>ppr</span> <span class='hs-varid'>id</span> <span class='hs-varop'><></span> <span class='hs-varid'>colon</span>
<a name="line-687"></a> <span class='hs-varop'>$$</span> <span class='hs-layout'>(</span><span class='hs-varid'>nest</span> <span class='hs-num'>3</span> <span class='hs-layout'>(</span><span class='hs-varid'>ppr</span> <span class='hs-varid'>tail</span><span class='hs-layout'>)</span><span class='hs-layout'>)</span>
<a name="line-688"></a>
<a name="line-689"></a><a name="pprLgraph"></a><span class='hs-definition'>pprLgraph</span> <span class='hs-keyglyph'>::</span> <span class='hs-layout'>(</span><span class='hs-conid'>Outputable</span> <span class='hs-varid'>m</span><span class='hs-layout'>,</span> <span class='hs-conid'>Outputable</span> <span class='hs-varid'>l</span><span class='hs-layout'>,</span> <span class='hs-conid'>LastNode</span> <span class='hs-varid'>l</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=></span> <span class='hs-conid'>LGraph</span> <span class='hs-varid'>m</span> <span class='hs-varid'>l</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>SDoc</span>
<a name="line-690"></a><span class='hs-definition'>pprLgraph</span> <span class='hs-varid'>g</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>text</span> <span class='hs-str'>"{"</span> <span class='hs-varop'><></span> <span class='hs-varid'>text</span> <span class='hs-str'>"offset"</span> <span class='hs-varop'>$$</span>
<a name="line-691"></a> <span class='hs-varid'>nest</span> <span class='hs-num'>2</span> <span class='hs-layout'>(</span><span class='hs-varid'>vcat</span> <span class='hs-varop'>$</span> <span class='hs-varid'>map</span> <span class='hs-varid'>ppr</span> <span class='hs-varid'>blocks</span><span class='hs-layout'>)</span> <span class='hs-varop'>$$</span> <span class='hs-varid'>text</span> <span class='hs-str'>"}"</span>
<a name="line-692"></a> <span class='hs-keyword'>where</span> <span class='hs-varid'>blocks</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>postorder_dfs</span> <span class='hs-varid'>g</span>
<a name="line-693"></a>
<a name="line-694"></a><a name="pprGraph"></a><span class='hs-definition'>pprGraph</span> <span class='hs-keyglyph'>::</span> <span class='hs-layout'>(</span><span class='hs-conid'>Outputable</span> <span class='hs-varid'>m</span><span class='hs-layout'>,</span> <span class='hs-conid'>Outputable</span> <span class='hs-varid'>l</span><span class='hs-layout'>,</span> <span class='hs-conid'>LastNode</span> <span class='hs-varid'>l</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=></span> <span class='hs-conid'>Graph</span> <span class='hs-varid'>m</span> <span class='hs-varid'>l</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>SDoc</span>
<a name="line-695"></a><span class='hs-definition'>pprGraph</span> <span class='hs-layout'>(</span><span class='hs-conid'>Graph</span> <span class='hs-varid'>tail</span> <span class='hs-varid'>blockenv</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span>
<a name="line-696"></a> <span class='hs-varid'>text</span> <span class='hs-str'>"{"</span> <span class='hs-varop'>$$</span> <span class='hs-varid'>nest</span> <span class='hs-num'>2</span> <span class='hs-layout'>(</span><span class='hs-varid'>ppr</span> <span class='hs-varid'>tail</span> <span class='hs-varop'>$$</span> <span class='hs-layout'>(</span><span class='hs-varid'>vcat</span> <span class='hs-varop'>$</span> <span class='hs-varid'>map</span> <span class='hs-varid'>ppr</span> <span class='hs-varid'>blocks</span><span class='hs-layout'>)</span><span class='hs-layout'>)</span> <span class='hs-varop'>$$</span> <span class='hs-varid'>text</span> <span class='hs-str'>"}"</span>
<a name="line-697"></a> <span class='hs-keyword'>where</span> <span class='hs-varid'>blocks</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>postorder_dfs_from</span> <span class='hs-varid'>blockenv</span> <span class='hs-varid'>tail</span>
<a name="line-698"></a>
</pre></body>
</html>
