Merge lp:~mgiuca/mars/switchfactor into lp:mars

[Matt Giuca]

[Matt Giuca (mgiuca)]

Branch is complete. It has two new capabilities over trunk:
- CFG code for switches is completely different and much simpler.
- Errors are produced for incomplete switches.

Test cases and documentation are up to date and correct.

This has two ramifications for merging:
- Other branches of trunk may need to be modified, perhaps heavily, if they deal with the CFG representation of switches.
- Some Mars code may break due to the additional error. (But it shouldn't -- the manual already specified that this was an error). All official Mars code in the trunk has been tested and works.

[lp:~mgiuca/mars/switchfactor]

981. By Matt Giuca on 2010-01-25

Merged from trunk -- Repeated variable in pattern test.

982. By Matt Giuca on 2010-01-25

Test suite: switch: Added 3 new test cases from other switch examples.

983. By Matt Giuca on 2010-01-25

doc/dev/switchfactor: Added another fully-worked example, from a test case (note in the test case where the full working is).

[Matt Giuca (mgiuca)]

All good.

review: Approve

=== added directory 'doc/dev'
=== added file 'doc/dev/index.rst'
--- doc/dev/index.rst	1970-01-01 00:00:00 +0000
+++ doc/dev/index.rst	2010-01-25 07:28:13 +0000
@@ -0,0 +1,31 @@
+.. Mars Documentation
+   Copyright (C) 2010 Matt Giuca
+   19/1/2010
+
+.. This program is free software: you can redistribute it and/or modify
+   it under the terms of the GNU General Public License as published by
+   the Free Software Foundation, either version 3 of the License, or
+   (at your option) any later version.
+
+.. This program is distributed in the hope that it will be useful,
+   but WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+   GNU General Public License for more details.
+
+.. You should have received a copy of the GNU General Public License
+   along with this program.  If not, see <http://www.gnu.org/licenses/>.
+
+.. _ref-dev:
+
+Developer Documentation
+=======================
+
+.. sectionauthor:: Matt Giuca <[e-mail]>
+
+This section contains information about the workings of *Mars*, for developers
+and other interested parties.
+
+.. toctree::
+   :maxdepth: 2
+
+   switchfactor.rst

=== added file 'doc/dev/switchfactor.rst'
--- doc/dev/switchfactor.rst	1970-01-01 00:00:00 +0000
+++ doc/dev/switchfactor.rst	2010-01-25 07:28:13 +0000
@@ -0,0 +1,795 @@
+.. Mars Documentation
+   Copyright (C) 2010 Matt Giuca
+   19/1/2010
+
+.. This program is free software: you can redistribute it and/or modify
+   it under the terms of the GNU General Public License as published by
+   the Free Software Foundation, either version 3 of the License, or
+   (at your option) any later version.
+
+.. This program is distributed in the hope that it will be useful,
+   but WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+   GNU General Public License for more details.
+
+.. You should have received a copy of the GNU General Public License
+   along with this program.  If not, see <http://www.gnu.org/licenses/>.
+
+.. _ref-switchfactor:
+
+**************************
+Switch factoring algorithm
+**************************
+
+.. sectionauthor:: Matt Giuca <[e-mail]>
+
+This is the algorithm in Mars for transforming an AST-level switch statement
+to a CFG-level one. This flattens patterns out into multi-level switch
+statements, so it is a non-recursive data structure (like the rest of CFG),
+and represents the actual execution paths taken by the machine. It also
+generates errors and warnings for malformed switch statements in the source.
+
+First, we transform each case into a ":token:`matcher`", a temporary data
+structure representing a single case in an equivalent, but flattened, form.
+For each case, recurse through the pattern structure, and generate a flat
+"matcher".  This results in a list of matchers, corresponding to the original
+list of cases.
+
+.. productionlist::
+   matcher: `pair`(`list`(`match`), `stmt_block`)
+
+A matcher list is an assoc list associating sequences of ":token:`match`"es
+with blocks, just like a switch is an assoc list associating patterns with
+blocks. A ":token:`match`" is a pattern without arguments (ctors have arities
+rather than arguments) -- unlike patterns, matches don't recurse.
+
+.. productionlist::
+   match: `match_any` | `match_var` | `match_ctor`(Name, Arity) | `match_intlit`(Val)
+
+A key operation in this algorithm is **generate_matcher_code**, which
+generates low-level code from a matcher list. This recursive operation
+performs most of the work, once the matcher list is generated. It is called
+as::
+
+ generate_matcher_code(arg_list, matcher_list)
+
+Where `arg_list` is a list of atoms (variable names), denoting the variables
+holding the switch values for the match list. The `arg_list` is always shorter
+or equal in length to the `matcher_list`, as arg_list only has the arguments
+for the current level, while `matcher_list` is fully expanded out.
+
+Example::
+
+ switch x:
+     case Pair(A, 1)
+     case Pair(B, 2)
+     case Pair(A, 3)
+     case Pair(q, _)
+     case Pair(A, 5)
+
+We want the final output to be::
+
+ switch x:
+     case Pair:
+         a = x.Pair(0)
+         n = x.Pair(1)
+         switch a:
+             case A:
+                 switch n:
+                     case 1
+                     case 3
+                     default: q = a
+             case B:
+                 switch n:
+                     case 2
+                     default: q = a
+             default: q = a
+
+The arguments to pair are patterns, so this data structure is recursive. We
+want to flatten it out. Therefore, the matchers we generate are:
+
+    [(Pair/2,A,1)-block1, (Pair/2,B,2)-block2, (Pair/2,A,3)-block3, (Pair/2,q,_)-block4, (Pair/2,A,5)-block5]
+
+(All the match arguments would have an arity, such as A/0 and 1/0, but we
+don't show /0 in the list above. But not the default arguments, such as q.)
+
+Now the constructors have no arguments -- we have a flat list of patterns. Note
+that we recursively flatten this data, so if A had two arguments, we could see
+a matcher like:
+
+    (Pair/2,A/2,J,K,1)-block1
+
+This reads operationally, "match a Pair, match the Pair's first argument with
+A, match the A's first argument with J and its second with K, then match the
+Pair's second argument with 1." So matchers are just a flat data structure for
+representing the same information as the case statement, but with an
+additional operational reading. Not all matchers have the same number of
+steps, as different ctors have different arities.
+
+Now before we generate code for the matchers, we add a layer of abstraction
+over the blocks, to avoid duplicating blocks when we duplicate matchers.
+Hence, our matcher list becomes:
+
+    [(Pair/2,A,1)-"block1", (Pair/2,B,2)-"block2", (Pair/2,A,3)-"block3", (Pair/2,q,_)-"block4", (Pair/2,A,5)-"block5"]
+
+    "block1": block1
+
+    "block2": block2
+
+    "block3": block3
+
+    "block4": block4
+
+    "block5": block5
+
+(The unquoted block names represent the full block code; the quoted ones
+represent a thin reference to the block name).
+
+The overall algorithm, outside of generating matcher code, goes, for
+switch(`switchvar`, `cases`):
+
+1. Construct the matcher list, `matcher_list`, from cases, by flattening out
+   the switch statement.
+
+   * Generate the code for each target block, and store the Block Ids in the
+     matcher list, not the blocks themselves.
+2. Call :func:`generate_matcher_code` ([`switchvar`], `matcher_list`).
+
+The result is a CFG-level switch statement. CFG-level switch statements are
+very simple jump tables. They switch over an atom, and map ints and ctor names
+to block IDs. They have an optional default clause, which is required to be
+last. It is up to the backend to decide what to do if there is no default
+clause, but the backend is free to exhibit undefined behaviour if a switch
+doesn't match and there is no default clause, as the code generator will never
+generate such an instruction due to exhaustive check, described below.
+
+In this example, we call::
+
+ generate_matcher_code(["x"], [(Pair/2,A,1)-"block1", (Pair/2,B,2)-"block2",
+                               (Pair/2,A,3)-"block3", (Pair/2,q,_)-"block4",
+                               (Pair/2,A,5)-"block5"])
+
+======================================
+Generating code for a list of matchers
+======================================
+
+.. function:: generate_matcher_code(arg_list, matcher_list)
+
+Summary of the algorithm: Focus only on the first argument for each matcher --
+the rest will be handled by recursion. Convert variable-binding matchers into
+wildcard/default matchers which bind a variable in their code. For every
+relevant head value, group together every possible matcher (those with an
+exact match, and wildcard/default matchers). Make these groupings into switch
+statements, and recurse to generate the body.
+
+Note that we assume we will switch on arguments from left to right. We could
+also pick a more intelligent order, such as choosing the argument with the
+most distinct cases first (which means earlier switches eliminate the most
+cases). In this case, the example below would choose the 2nd argument first,
+but we'll assume left-to-right for now. Note that the flattening means we have
+to make this decision *before* generating the matcher list.
+
+Each call to :func:`generate_matcher_code` is given a block to write to (this
+block will be completed by the end of the call). When a choice is required,
+the block will be finished with a switch statement, and new blocks will be
+created for each case (and finished off by recursive calls). When no choice is
+required, some code may be appended to the block, and then the (single)
+recursive call will complete the same block.
+
+Calls to :func:`generate_matcher_code` may also append phi instructions to the
+target blocks (which is the mechanism used to make explicit variable
+bindings).
+
+The function also needs to track two tables, for keeping variable bindings.
+Ultimately, variable bindings are stored in phi instructions in the target
+blocks, but during the code generation, we track them separately, because we
+can't build phi nodes piece-by-piece. The **binding table** only moves down
+through the stack, so any changes made to it are undone on the way up. This
+maps :class:`blockid` to :class:`varname` to :class:`varname`, such that if
+BB-BoundVar maps to SourceVar, it says "if BB wants BoundVar, it is currently
+available in SourceVar." The **phi table** moves down and up through the
+stack, so changes made to it are permanent throughout the algorithm. This is a
+multimap mapping :class:`blockid` to :class:`varname` to
+:class:`pair(blockid,varname)`, such that if TargetBlock-BoundVar maps to
+SourceBlock-SourceVar, it says "TargetBlock should have a phi node for
+BoundVar, where one entry maps SourceBlock to SourceVar." Both tables start
+out empty.
+
+Base case
+---------
+
+When `arg_list` is empty. It should always be the case that
+`matcher_list` contains exactly one element (but assume it has multiple and
+pick the first), whose match list is empty. In this case, generate a branch to
+the block named by the first element of `matcher_list`.
+
+Also add entries to the phi table for the target block. Get the target block
+out of the binding table. For each entry in this table (BoundVar-SourceVar),
+create a phi table entry (TargetBlock-BoundVar) = (CurrentBlock-SourceVar).
+
+Step 1 -- Update binding table with explicit variable bindings
+--------------------------------------------------------------
+
+The first step of the operation (which in the current example will do nothing,
+but we'll see it working later) is to update the binding table for explicit
+variable bindings (as distinct from the implicit temporary variables, which
+are created during switch generation). For each matcher whose first argument
+is a variable name:
+
+1. Add an entry in the binding table mapping (that matcher's block - the first
+   variable in `arg_list`) to the given variable name. For example, if
+   `arg_list` [1] is "a" and the first entry in a matcher is "q", then the
+   variable "q" must be bound to the first switch value. Therefore, add to the
+   binding table (``<matcher's block>`` - `q`) -> `a`.
+2. Replace the first argument of the matcher with match_any ("_"). This is
+   sound, as variables match anything, and we no longer need to worry about
+   the variable binding, as it will be taken care of as soon as we branch to
+   the code.
+
+Step 2 -- Create association list
+---------------------------------
+
+The next step is to create an assoc list for every head value of interest, for
+the first argument. The assoc list maps "match"es onto match lists. "Head
+value" means the ctor without its arguments, or the integer. "Of interest"
+means the head values referred to by any matcher. Head values which are never
+referred to (e.g., all the integers which aren't explicitly mentioned) are all
+the same as far as we're concerned.
+
+Now we have to be *very careful* to preserve order, because default matchers
+which are before more specific matchers need to supersede the specific ones.
+(This assumes a language like Haskell, where the first match is chosen, not
+Prolog/Mercury, where the order technically doesn't matter.) The grouping of
+matchers with the same head will conceptually change the order, but this
+*never* matters, because when we make a grouping, it is a committed choice. In
+other words, once a match is made, we cover all possible subsequent cases
+inside the match, and never fall back out to a default case. So we don't
+re-order within a group, but once we have selected the groupings, their order
+doesn't matter (though we keep them in order for the sake of predictable code
+generation).
+
+Let's return to our example, with the matcher list:
+
+    [(Pair/2,A,1)-"block1", (Pair/2,B,2)-"block2", (Pair/2,A,3)-"block3", (Pair/2,q,_)-"block4", (Pair/2,A,5)-"block5"]
+
+The resulting assoc list is very basic at this level, since all of the
+matchers have the same head, Pair/2:
+
+    Pair/2: [(A,1)-"block1", (B,2)-"block2", (A,3)-"block3", (q,_)-"block4", (A,5)-"block5"]
+
+It's difficult to see at this stage, but the operation is to take each head
+value of interest, and give it its own entry in the assoc list. Then, place in
+the assoc list any matcher which begins with either the head value, or a "_".
+
+* For matchers which begin with the head value, remove the first column of the
+  matcher (so the matched head value no longer appears in the match list).
+* For matchers which begin with a "_", replace the first column of the
+  matcher (the "_") with one "_" for each argument of the head value (0 or
+  more). For example, if placing a default matcher in the Cons/2 row, replace
+  its front "_" with "_", "_" -- one for each argument. If placing a default
+  matcher in the Nil row, remove its front "_".
+
+If there are any default cases, also create an assoc list entry for "_", and
+only place in the assoc list any matcher which begins with a "_". Remove the
+first column of such matchers, as if matching a 0-arity head value.
+
+**Horizontal rule**: For any matcher (looking at the remaining matches), if it
+is *covered* by all of the matchers already on a row, remove it, as it is
+redundant. By "covered", I mean for all of the remaining matches, if it is an
+exact match, it already appears in a previous matcher, or if it is a default,
+there is already a default in the previous matchers or between them they
+include all constructors of that type. When removing a matcher, if the first
+argument is not a default match, give a warning, as it is a useless clause.
+
+**Vertical rule**: For any assoc list entry, if its head is *covered* by all
+of the entries already in the table, remove it, as it is redundant. By
+"covered", I mean if it is an exact match, that head already appeared in the
+assoc list. If it is a default, there is already a default in the assoc list
+or between them, all entries include all constructors of that type. When
+removing an assoc list entry, give a warning for each matcher, as they are all
+useless. (Perhaps do not give a warning for a default matcher covered by all
+constructors, as that probably represents defensive programming. For example,
+the programmer might just be using the default rule as an assert because he
+doesn't trust the compiler to generate "not exhaustive" errors -- then again,
+maybe it should be a warning because he should trust the compiler!) When a
+default entry is placed in the assoc list, it will always be the last (this is
+a structural requirement of the CFG-level switch statement).
+
+Once this grouping is done (at each level), test that there is *either* a
+default case, or that all ctors of the switch type have a case. If not, it is
+a compiler error ("switch not exhaustive"). The error message should include
+all of the missing cases ("requires default case or cases for A, B, C"), if it
+is an ADT. If it is an integer type, it must have a default case, so the error
+message should just read "switch not exhaustive: default case required for
+switch on integer".
+
+Step 3 -- Generate switch statement and implicit unpacking instructions
+-----------------------------------------------------------------------
+
+This enables us to generate the top-level switch statement. Switch over the
+first variable of `arg_list`, and generate a case statement for each assoc
+list entry. If the assoc list entry is default, generate the "default" clause
+of the switch statement (which must be last). Within each case statement, we
+unpack all arguments, giving them a temporary name.
+
+**Unnecessary optimisation**: If the variable's original pattern is _ in all
+matchers, don't unpack it -- note that to know this, you actually shouldn't
+erase the variable name in step 1, or you won't know which are needed and
+which aren't. Also, if their pattern is a variable name in all matchers, we
+can use that variable name and avoid the mov instruction on a later recursion
+of step 1, but for an optimising backend like LLVM, that won't save anything.
+
+::
+
+ <continue current block>
+     switch x:
+         case Pair: goto casepair
+
+ casepair:
+     a = x.Pair(0)
+     n = x.Pair(1)
+     <generate_matcher_code([a,n], [(A,1)-"block1", (B,2)-"block2",
+                                    (A,3)-"block3", (q,_)-"block4",
+                                    (A,5)-"block5"])>
+
+**Optimisation**: If `arg_list` has a single element, and there were no
+variables unpacked, then all recursive calls will be base cases with a simple
+goto. Avoid generating a bunch of new goto-only blocks by making the case
+statements directly branch to the first target block in each case, as the base
+case would. Must also update the phi table as the base case does.
+
+**Optimisation**: I naively generated a single-case switch statement. Instead,
+we should avoid generating such a thing. If there is exactly one entry in the
+assoc list, just generate the unpacking code directly::
+
+ <continue current block>
+     a = x.Pair(0)
+     n = x.Pair(1)
+     <generate_matcher_code([a,n], [(A,1)-"block1", (B,2)-"block2",
+                                    (A,3)-"block3", (q,_)-"block4",
+                                   (A,5)-"block5"])>
+
+Step 4 -- Recurse
+-----------------
+
+Now we recurse on :func:`generate_matcher_code`. The recursive calls are shown
+in the example above. Note that we recurse once for each assoc list entry (so
+we iterate, then recurse).
+
+The `arg_list` on the recursive calls is the current `arg_list` with the first
+element removed, and the unpacked temporary variable names prepended. These
+new arguments correspond to the first entries in the new matcher lists. The
+`matcher_list` on the recursive calls is simply the corresponding value in the
+assoc list, for this head.
+
+================================================================
+Afterwards -- Generating phi code for explicit variable bindings
+================================================================
+
+After all calls to :func:`generate_matcher_code` have ended, the phi table has
+been built. This describes exactly where each target block should read the
+variable bindings from, conditionally dependent on the block it came from.
+
+These should be converted into phi instructions for each block, in the obvious
+way. **Unnecessary optimisation**: Any entries in the phi table which have the
+same source variable name for every source block can be converted into mov
+instructions instead.
+
+======================
+Completing the example
+======================
+
+I now present the rest of the worked example, stepping through the recursive
+calls. ::
+
+ generate_matcher_code([a,n], [(A,1)-"block1", (B,2)-"block2", (A,3)-"block3",
+                               (q,_)-"block4", (A,5)-"block5"])
+
+First, we apply step 1, binding q for the matcher for (q,_).
+
+1. prepend to the actual code of block 4, the instruction "q = a" (where a is
+   the first variable we are matching against).
+2. Replace q with _ in the matchers list. Hence:
+
+   [(A,1)-"block1", (B,2)-"block2", (A,3)-"block3", (_,_)-"block4", (A,5)-"block5"]
+
+Now we again group together the matchers by their first argument -- this time
+we have multiple ctors and default matchers in the first argument. For every
+matched ctor, we duplicate all of the default matchers. Thus, the groups are:
+
+ A: [(1)-"block1", (3)-"block3", (_)-"block4", (5)-"block5"]
+
+ B: [(2)-"block2", (_)-"block4"]
+
+ _: [(_)-"block4"]
+
+Note that block4 was duplicated for the A group, even though it did not
+explicitly match A. This preserves the semantics of the switch statement -- if
+we had not duplicated it, then matching A would discount that default case. As
+explained above, when duplicating a default value, first test to see if it is
+*covered* by all of the matchers before it, and if so, do not duplicate.
+
+This allows us to generate the next switch statement::
+
+ switch a:
+     case A:
+         <generate_matcher_code([n], [(1)-"block1", (3)-"block3",
+                                      (_)-"block4", (5)-"block5"])>
+     case B:
+         <generate_matcher_code([n], [(2)-"block2", (_)-"block4"])>
+     default:
+         <generate_matcher_code([n], [(_)-"block4"])>
+
+Now that we have three cases, we iterate over all of them, and recurse three
+times.
+
+The assoc list for case A:
+
+    1: [()-"block1"]
+
+    3: [()-"block3"]
+
+    _: [()-"block4"]
+
+(Applying the vertical rule to remove the entry "5: [()-"block5"]").
+
+The assoc list for case B:
+
+    2: [()-"block2"]
+
+    _: [()-"block4"]
+
+The assoc list for the default case:
+
+    _: [()-"block4"]
+
+This brings us to seven base cases, of <generate_matcher_code([],
+[()-"blockn"])>, which just generates the goto statement to the given block.
+
+We end up with this code::
+
+ switch a:
+     case A:
+         switch n:
+             case 1: goto "block1"
+             case 3: goto "block3"
+             default: goto "block4"
+     case B:
+         switch n:
+             case 2: goto "block2"
+             default: goto "block4"
+     default: goto "block4"
+
+Then we generate all of the code for each block. Note that each block only has
+code generated once, but may be targeted by multiple case statements, such as
+block4.
+
+================
+Further examples
+================
+
+Above example, continued
+------------------------
+
+Now, let us imagine a slightly different scenario, where we had these
+matchers:
+
+    A: [(1,_)-"block1", (3,7)-"block3", (_,_)-"block4", (5,_)-"block5"]
+
+(Same as above for case A, but with an extra argument.) This means, by the
+rule above, we need to copy the default match for each concrete match. Hence,
+we generate the following grouping for case A:
+
+    1: [(_)-"block1", (_)-"block4"]
+
+    3: [(7)-"block3", (_)-"block4"]
+
+    _: [(_)-"block4"]
+
+    5: [(_)-"block5", (_)-"block4"]
+
+This is inefficient, but perfectly correct. Operationally, it reads: "If you
+match 1, match all and go to block1, and if that fails, match all and go to
+block4." (Obviously, we will pick block1). Then, "If you match 3, match 7 and
+go to block3, or match all and go to block4". Then it says "Match all and go
+to block4." Finally, "If you match 5, match all and go to block5, and if that
+fails, match all and go to block4." There are two forms of redundancy here.
+
+First, once a default case occurs, all subsequent cases can be removed
+(preferably with a warning):
+
+    1: [(_)-"block1", (_)-"block4"]
+
+    3: [(7)-"block3", (_)-"block4"]
+
+    _: [(_)-"block4"]
+
+Second, once a matcher which *cannot fail* is seen, all subsequent matchers
+can be removed:
+
+    1: [(_)-"block1"]
+
+    3: [(7)-"block3", (_)-"block4"]
+
+    _: [(_)-"block4"]
+
+This still perfectly preserves the semantics of the above matcher list --
+there is no possibility of going to block5, or block4 from a match of 1.
+
+However, we would like to generate a warning in this last case as well, which
+would be spurious if we duplicated any defaults then eliminated them again. So
+we need to avoid duplicating in the first place.
+
+Therefore: When duplicating a default value, first test to see if any of the
+matchers before it will always succeed, and if so, do not duplicate.
+
+Now, we can be even more judicious in preventing duplication. First, don't
+just assume a matcher set cannot fail if it has a default case -- also check
+for exhaustive ctor coverage. Secondly, it's not necessary for the matchers to
+be unable to fail, it is merely sufficient for them to cover the duplicated
+patterns. So: When duplicating a default value, first test to see if it is
+covered by all of the matchers before it, and if so, do not duplicate.
+
+Also: Do not think of it as "duplicating" the default values. Simpler to think
+of it as "projecting" away all values which don't match. So, include all exact
+matches and also default values. Then, eliminate all later matches which are
+covered by earlier matches, giving a warning iff the eliminated matches are
+exact (and therefore are useless). If they are default matches, then they
+aren't useless unless covered by all constructors on the outside -- they
+should have already been checked by the vertical rule.
+
+An example of this:
+
+    [(1,A)-"block1", (1,B)-"block2", (2,A)-"block3", (_,B)-"block4", (_,_)-"block5"]
+
+Naively transformed:
+
+    1: [(A)-"block1", (B)-"block2", (B)-"block4", (_)-"block5"]
+
+    2: [(A)-"block3", (B)-"block4", (_)-"block5"]
+
+    _: [(B)-"block4", (_)-"block5"]
+
+However, we didn't need to duplicate the (_,B) case to case 1, as it is
+covered by the (1,B) case. So:
+
+    1: [(A)-"block1", (B)-"block2", (_)-"block5"]
+
+    2: [(A)-"block3", (B)-"block4", (_)-"block5"]
+
+    _: [(B)-"block4", (_)-"block5"]
+
+If A and B are the only ctors for the switch type, then it would not be
+necessary to copy the (_,_) case either if 1 or 2 is matched, as it is covered
+in both cases:
+
+    1: [(A)-"block1", (B)-"block2"]
+
+    2: [(A)-"block3", (B)-"block4"]
+
+    _: [(B)-"block4", (_)-"block5"]
+
+Tricky variable binding example
+-------------------------------
+
+Consider this code::
+
+ switch x:
+     case Pair(49, Box(3))
+     case Pair(m, Box(n))
+
+This example is important because in this case, the binding for `n` depends on
+the path taken to the second block. This explains the need for Phi
+instructions when making variable bindings. In this example, the second case's
+`n` variable needs to be copied from a temporary unpack variable -- which
+variable will depend on whether the first number was 49.
+
+Args: [x]
+
+Binds: []
+
+Matchers::
+
+ Pair, 49, Box, 3 - block1
+ Pair, m, Box, n - block2
+
+Assoc::
+
+ Pair: [49, Box, 3]-block1, [m, Box, n]-block2
+
+Codegen::
+
+ entry:
+     a = x.Pair(0)
+     b = x.Pair(1)
+     <continue>
+
+----
+
+Args: [a,b]
+
+Binds: []
+
+Matchers::
+
+ 49, Box, 3 - block1
+ m, Box, n - block2
+
+Bind m=a in block2's binding table.
+
+::
+
+ 49, Box, 3 - block1
+ _, Box, n - block2
+
+Assoc list::
+
+ 49: [Box, 3]-block1, [Box, n]-block2
+ _: [Box, n]-block2
+
+Codegen::
+
+     <continue entry>
+
+     switch a:
+         case 49: goto case49
+         default: goto default
+ case49:
+     <continue>
+ default:
+     <continue>
+
+----
+
+**(case 49)**
+
+Args: [b]
+
+Binds: [(block2-m)=a]
+
+Matchers::
+
+ Box, 3 - block1
+ Box, n - block2
+
+Assoc list::
+
+ Box: [3]-block1, [n]-block2
+
+Codegen::
+
+     <continue case49>
+     c = b.Box(0)
+     <continue>
+
+----
+
+**(case 49, Box)**
+
+Args: [c]
+
+Binds: [(block2-m)=a]
+
+Matchers::
+
+ 3 - block1
+ n - block2
+
+Bind n=c in block2's binding table.
+
+.. note:: A phi is required, as the binding is different to that below.
+
+::
+
+ 3 - block1
+ _ - block2
+
+Codegen::
+
+     <continue case49>
+     switch c:
+         case 3: goto block1
+         default: goto block2
+
+.. note:: This isn't quite the base case. We could recurse once more,
+          generating two new blocks, and then each block would consist
+          entirely of a goto. However, this pre-base-case allows more
+          efficient code generation.
+
+Write to phi table: (block2-m)=(case49-a)
+
+Write to phi table: (block2-n)=(case49-c)
+
+----
+
+**(case default)**
+
+Args: [b]
+
+Binds: [(block2-m)=a]
+
+Matchers::
+
+ Box, n - block2
+
+Assoc list::
+
+ Box: [n]-block2
+
+Codegen::
+
+     <continue default>
+     d = b.Box(0)
+     <continue>
+
+----
+
+**(case default, Box)**
+
+Args: [d]
+
+Binds: [(block2-m)=a]
+
+Matchers::
+
+ n - block2
+
+Bind n=d in block2's binding table.
+
+.. note:: A phi is required, as the binding is different to that above.
+
+::
+
+ _ - block2
+
+Assoc list::
+
+ _: []-block2
+
+Codegen::
+
+     <continue default>
+     goto block2
+
+Write to phi table: (block2-m)=(default-a)
+
+Write to phi table: (block2-n)=(default-d)
+
+----
+
+**(Final generated code)**
+
+Final phi table::
+
+ (block2-m)=[(case49-a), (default-a)]
+ (block2-n)=[(case49-c), (default-d)]
+
+::
+
+ entry:
+     a = x.Pair(0)
+     b = x.Pair(1)
+     switch a:
+         case 49: goto case49
+         default: goto default
+
+ case49:
+     c = b.Box(0)
+     switch c:
+         case 3: goto block1
+         default: goto block2
+
+ default:
+     d = b.Box(0)
+     goto block2
+
+ block1:
+     ...
+
+ block2:
+     n = phi(case49 = c, default = d)
+     m = phi(case49 = a, default = a)
+     ...
+
+.. note:: The phi node for m in block2 may be converted into a mov
+          instruction, because the binding is the same for all predecessors.

=== modified file 'doc/index.rst'
--- doc/index.rst	2009-10-02 06:21:23 +0000
+++ doc/index.rst	2010-01-25 07:28:13 +0000
@@ -35,6 +35,7 @@
    ref/index.rst
    lib/index.rst
    faq.rst
+   dev/index.rst
    testing.rst
 
 Indices and tables

=== modified file 'doc/ref/stmts.rst'
--- doc/ref/stmts.rst	2009-02-05 07:36:52 +0000
+++ doc/ref/stmts.rst	2010-01-25 07:28:13 +0000
@@ -227,14 +227,6 @@
 proven either by having a wildcard pattern (underscore or variable), or by
 matching all alternatives of a user-defined data type.
 
-.. warning::
-   The current implementation does not obey this last rule. Currently, this
-   check is made at runtime, not compile time. If no case of a switch
-   statement matches, the program will terminate with a runtime error,
-   "pattern match failure".
-   Programmers should ensure that the above rule holds statically for all
-   switch statements, as a future version may enforce this rule.
-
 Note that the effects of variable binding outlast the :keyword:`switch`
 statement. Their binding is like an
 :ref:`assignment statement <ref-assignment-statements>`.

=== modified file 'src/ast_cfg.m'
--- src/ast_cfg.m	2010-01-25 01:23:14 +0000
+++ src/ast_cfg.m	2010-01-25 07:28:13 +0000
@@ -29,12 +29,13 @@
 :- interface.
 
 :- import_module ir.
+:- import_module tables.
 
 :- import_module list.
 
 % prog_to_cfg(!Program) converts all functions in a program to CFG form,
 % calling func_to_cfg on each of them.
-:- pred prog_to_cfg(program::in, program::out) is det.
+:- pred prog_to_cfg(progtable::in, program::in, program::out) is det.
 
 % func_to_cfg(!Function) converts a function to CFG form if possible.
 % Built-in functions and CFG functions remain the same.
@@ -44,7 +45,7 @@
 % - There exists a viable code path which does not return a value.
 % - There is an attempt to read from a variable which may not have been
 %   assigned on some or all code paths.
-:- pred func_to_cfg(function::in, function::out) is det.
+:- pred func_to_cfg(progtable::in, function::in, function::out) is det.
 
 % expr_to_instrs(+Expr, -VarName, -Instrs).
 % Converts a single expression into a sequence of low-level instructions
@@ -68,28 +69,35 @@
 :- implementation.
 
 :- import_module pair.
+:- import_module assoc_list.
 :- import_module map.
+:- import_module multi_map.
+:- import_module svmap.
+:- import_module svmulti_map.
 :- import_module maybe.
 :- import_module string.
 :- import_module int.
+:- import_module integer.
 :- import_module exception.
 
 :- import_module cfg.
 :- import_module context.
-
-prog_to_cfg(program(Nodes0), program(Nodes)) :-
-    prog_nodes_to_cfg(Nodes0, Nodes).
-
-:- pred prog_nodes_to_cfg(list(program_node)::in, list(program_node)::out).
-prog_nodes_to_cfg([], []).
-prog_nodes_to_cfg([Node0|Nodes0], [Node|Nodes]) :-
+:- import_module util.
+
+prog_to_cfg(PT, program(Nodes0), program(Nodes)) :-
+    prog_nodes_to_cfg(PT, Nodes0, Nodes).
+
+:- pred prog_nodes_to_cfg(progtable::in,
+    list(program_node)::in, list(program_node)::out).
+prog_nodes_to_cfg(_, [], []).
+prog_nodes_to_cfg(PT, [Node0|Nodes0], [Node|Nodes]) :-
     ( Node0 = pfunction(Func0) ->
-        func_to_cfg(Func0, Func),
+        func_to_cfg(PT, Func0, Func),
         Node = pfunction(Func)
     ;
         Node = Node0
     ),
-    prog_nodes_to_cfg(Nodes0, Nodes).
+    prog_nodes_to_cfg(PT, Nodes0, Nodes).
 
 :- pred new_def_map(def_map::out) is det.
 new_def_map(Map) :-
@@ -111,7 +119,7 @@
 def_map_insert_local(Name-_, !DefMap) :-
     map.det_insert(!.DefMap, Name, unbound, !:DefMap).
 
-func_to_cfg(!Func) :-
+func_to_cfg(PT, !Func) :-
     % Create a new defmap with all of the params.
     new_def_map(DefMap0),
     Params = !.Func ^ func_params,
@@ -123,28 +131,28 @@
         Params = yes(YesParams),
         foldl(def_map_insert_param, YesParams, DefMap0, DefMap)
     ),
-    func_body_to_cfg(DefMap, !.Func ^ func_context, !.Func ^ func_body,
+    func_body_to_cfg(PT, DefMap, !.Func ^ func_context, !.Func ^ func_body,
         CFGBody),
     !:Func = !.Func ^ func_body := CFGBody.
 
 % Note: def_map argument should have all of the function's parameters already
 % bound in the map.
-:- pred func_body_to_cfg(def_map::in, context::in,
+:- pred func_body_to_cfg(progtable::in, def_map::in, context::in,
     func_body::in, func_body::out) is det.
-func_body_to_cfg(_DefMap, _Ctx, B@func_builtin, B).
-func_body_to_cfg(_DefMap, _Ctx, B@func_body_cfg(_,_), B).
-func_body_to_cfg(DefMap0, Ctx, func_body_ast(Decls,Stmts), NewFuncBody) :-
+func_body_to_cfg(_PT, _DefMap, _Ctx, B@func_builtin, B).
+func_body_to_cfg(_PT, _DefMap, _Ctx, B@func_body_cfg(_,_), B).
+func_body_to_cfg(PT, DefMap0, Ctx, func_body_ast(Decls,Stmts), NewFuncBody) :-
     NewFuncBody = 'new func_body_cfg'(Decls, CFG),
     % Insert all of the function's locals into the defmap, unbound
     foldl(def_map_insert_local, Decls, DefMap0, DefMap),
-    ast_to_cfg(DefMap, Ctx, Stmts, CFG).
+    ast_to_cfg(PT, DefMap, Ctx, Stmts, CFG).
 
 % ast_to_cfg(DefMap, Stmts, CFG) converts a statement block (AST form) to a
 % control flow graph, translating the code.
 % This also performs error checking (see func_to_cfg).
-:- some [S] pred ast_to_cfg(def_map::in, context::in, stmt_block::in,
-    cfg(S)::out) is det.
-ast_to_cfg(DefMap, Ctx, Stmts, CFG) :-
+:- some [S] pred ast_to_cfg(progtable::in, def_map::in, context::in,
+    stmt_block::in, cfg(S)::out) is det.
+ast_to_cfg(PT, DefMap, Ctx, Stmts, CFG) :-
     some [!CFG]
     (
         % Need to create the entry block and exit block so that
@@ -153,8 +161,8 @@
         !:CFG = cfg.new_cfg,
         Entry = cfg.get_entry(!.CFG),
         Exit = cfg.get_exit(!.CFG),
-        stmt_block_to_cfg(Stmts, Entry, Exit, DefMap, map.init, AfterPredMap,
-            map.init, ExitPredMap, !CFG),
+        stmt_block_to_cfg(PT, Stmts, Entry, Exit, DefMap,
+            map.init,AfterPredMap, map.init, ExitPredMap, !CFG),
         % The union of AfterPredMap and ExitPredMap contains information about
         % all predecessors to Exit. Use this to compute phi instructions for
         % Exit.
@@ -464,38 +472,39 @@
 % for the purpose of computing phis.
 % Throws a context error if there is an attempt to read from a variable which
 % may not have been assigned on some or all code paths.
-:- pred stmt_block_to_cfg(stmt_block::in, bbref(S)::in, bbref(S)::in,
-    def_map::in, pred_map(S)::in, pred_map(S)::out,
+:- pred stmt_block_to_cfg(progtable::in, stmt_block::in, bbref(S)::in,
+    bbref(S)::in, def_map::in, pred_map(S)::in, pred_map(S)::out,
     pred_map(S)::in, pred_map(S)::out, cfg(S)::in, cfg(S)::out)
     is det.
-stmt_block_to_cfg(Stmts, BBCurrent, BBAfter, DefMap, !AfterPredMap,
+stmt_block_to_cfg(PT, Stmts, BBCurrent, BBAfter, DefMap, !AfterPredMap,
     !ExitPredMap, !CFG) :-
     map.init(SubscriptMap),
-    stmt_block_to_cfg(Stmts, BBCurrent, BBAfter, SubscriptMap, DefMap,
+    stmt_block_to_cfg(PT, Stmts, BBCurrent, BBAfter, SubscriptMap, DefMap,
         !AfterPredMap, !ExitPredMap, !CFG).
 
-:- pred stmt_block_to_cfg(stmt_block::in, bbref(S)::in, bbref(S)::in,
+:- pred stmt_block_to_cfg(progtable::in, stmt_block::in, bbref(S)::in,
+    bbref(S)::in,
     subscript_map::in, def_map::in, pred_map(S)::in, pred_map(S)::out,
     pred_map(S)::in, pred_map(S)::out, cfg(S)::in, cfg(S)::out) is det.
-stmt_block_to_cfg([], BBCurrent, BBAfter, _SubscriptMap, DefMap,
+stmt_block_to_cfg(_PT, [], BBCurrent, BBAfter, _SubscriptMap, DefMap,
     !AfterPredMap, !ExitPredMap, !CFG) :-
     % Special case for empty block - just branch to BBAfter.
     add_to_pred_map(BBCurrent, DefMap, BBAfter, !AfterPredMap, !CFG),
     cfg.set_terminator(BBCurrent, branch(BBAfter, blank_context), !CFG).
-stmt_block_to_cfg([S], BBCurrent, BBAfter, SubscriptMap, DefMap,
+stmt_block_to_cfg(PT, [S], BBCurrent, BBAfter, SubscriptMap, DefMap,
     !AfterPredMap, !ExitPredMap, !CFG) :-
     % Base-case for the last statement in a block - compile statement into
     % BBCurrent, but end up by branching to BBAfter.
-    stmt_to_cfg_last(S, BBCurrent, BBAfter, SubscriptMap, DefMap,
+    stmt_to_cfg_last(PT, S, BBCurrent, BBAfter, SubscriptMap, DefMap,
         !AfterPredMap, !ExitPredMap, !CFG).
-stmt_block_to_cfg([S|Ss@[_|_]], BBCurrent, BBAfter, SubscriptMap0, DefMap0,
+stmt_block_to_cfg(PT, [S|Ss@[_|_]], BBCurrent, BBAfter, SubscriptMap0,DefMap0,
     !AfterPredMap, !ExitPredMap, !CFG) :-
     % Compile a single statement into BBCurrent. BBContinue is the block to
     % compile subsequent statements into (may be equal to BBCurrent).
-    stmt_to_cfg(S, BBCurrent, BBContinue, SubscriptMap0, SubscriptMap,
+    stmt_to_cfg(PT, S, BBCurrent, BBContinue, SubscriptMap0, SubscriptMap,
         DefMap0, DefMap, !ExitPredMap, !CFG),
     % Compile subsequent statements into BBContinue.
-    stmt_block_to_cfg(Ss, BBContinue, BBAfter, SubscriptMap, DefMap,
+    stmt_block_to_cfg(PT, Ss, BBContinue, BBAfter, SubscriptMap, DefMap,
         !AfterPredMap, !ExitPredMap, !CFG).
 
 %%% HIGH-LEVEL STATEMENT-COMPILATION PREDICATES %%%
@@ -514,18 +523,18 @@
 %   will be completed (have a terminator set), and SubscriptMap will be reset
 %   to refer to the new block (and typically be empty).
 % May also update def_map with any new variable definitions.
-:- pred stmt_to_cfg(stmt::in, bbref(S)::in, bbref(S)::out,
+:- pred stmt_to_cfg(progtable::in, stmt::in, bbref(S)::in, bbref(S)::out,
         subscript_map::in, subscript_map::out, def_map::in, def_map::out,
         pred_map(S)::in, pred_map(S)::out, cfg(S)::in, cfg(S)::out) is det.
-stmt_to_cfg(basic_stmt(S,Ctx), !BBRef, !SubscriptMap, !DefMap, !ExitPredMap,
-    !CFG) :-
+stmt_to_cfg(_PT, basic_stmt(S,Ctx), !BBRef, !SubscriptMap, !DefMap,
+    !ExitPredMap, !CFG) :-
     basic_stmt_to_cfg(S, Ctx, !.BBRef, !SubscriptMap, !DefMap, !CFG).
-stmt_to_cfg(compound_stmt(S,Ctx), BBCurrent, BBAfter, !SubscriptMap,
+stmt_to_cfg(PT, compound_stmt(S,Ctx), BBCurrent, BBAfter, !SubscriptMap,
     !DefMap, !ExitPredMap, !CFG) :-
     % Generate a target block for the compound statement to branch to
     cfg.new_basic_block(BBAfter, !CFG),
-    compound_stmt_to_cfg(S, Ctx, BBCurrent, BBAfter, !.SubscriptMap, !.DefMap,
-        map.init, AfterPredMap, !ExitPredMap, !CFG),
+    compound_stmt_to_cfg(PT, S, Ctx, BBCurrent, BBAfter, !.SubscriptMap,
+        !.DefMap, map.init, AfterPredMap, !ExitPredMap, !CFG),
     % AfterPredMap contains information about all predecessors to BBAfter.
     % Use this to compute phi instructions for BBAfter and update DefMap.
     AfterID = ref_id(BBAfter, !.CFG),
@@ -544,19 +553,19 @@
 % for the purpose of computing phis.
 % May update DefMap with new bindings, but SubscriptMap is read-only (since it
 % will definitely branch to a new block).
-:- pred stmt_to_cfg_last(stmt::in, bbref(S)::in, bbref(S)::in,
+:- pred stmt_to_cfg_last(progtable::in, stmt::in, bbref(S)::in, bbref(S)::in,
     subscript_map::in, def_map::in, pred_map(S)::in, pred_map(S)::out,
     pred_map(S)::in, pred_map(S)::out, cfg(S)::in, cfg(S)::out) is det.
-stmt_to_cfg_last(basic_stmt(S,Ctx), BBCurrent, BBAfter, SubscriptMap,
+stmt_to_cfg_last(_PT, basic_stmt(S,Ctx), BBCurrent, BBAfter, SubscriptMap,
     DefMap, !AfterPredMap, !ExitPredMap, !CFG) :-
     basic_stmt_to_cfg(S, Ctx, BBCurrent, SubscriptMap, _, DefMap, NewDefMap,
         !CFG),
     % Branch to the provided BBAfter
     add_to_pred_map(BBCurrent, NewDefMap, BBAfter, !AfterPredMap, !CFG),
     cfg.set_terminator(BBCurrent, branch(BBAfter, Ctx), !CFG).
-stmt_to_cfg_last(compound_stmt(S,Ctx), BBCurrent, BBAfter, SubscriptMap,
+stmt_to_cfg_last(PT, compound_stmt(S,Ctx), BBCurrent, BBAfter, SubscriptMap,
     DefMap, !AfterPredMap, !ExitPredMap, !CFG) :-
-    compound_stmt_to_cfg(S, Ctx, BBCurrent, BBAfter, SubscriptMap,
+    compound_stmt_to_cfg(PT, S, Ctx, BBCurrent, BBAfter, SubscriptMap,
         DefMap, !AfterPredMap, !ExitPredMap, !CFG).
 
 %%% LOW-LEVEL STATEMENT-COMPILATION PREDICATES %%%
@@ -729,11 +738,11 @@
 % SubscriptMap is read-only (since it will definitely branch to a new block).
 % DefMap is read-only (the resulting def-maps should be appended to
 % AfterPredMap).
-:- pred compound_stmt_to_cfg(compound_stmt::in, context::in, bbref(S)::in,
-    bbref(S)::in, subscript_map::in, def_map::in,
+:- pred compound_stmt_to_cfg(progtable::in, compound_stmt::in, context::in,
+    bbref(S)::in, bbref(S)::in, subscript_map::in, def_map::in,
     pred_map(S)::in, pred_map(S)::out, pred_map(S)::in, pred_map(S)::out,
     cfg(S)::in, cfg(S)::out) is det.
-compound_stmt_to_cfg(return(Expr), Ctx, BBCurrent, _BBAfter, SubscriptMap,
+compound_stmt_to_cfg(_PT,return(Expr), Ctx, BBCurrent, _BBAfter, SubscriptMap,
     DefMap0, !AfterPredMap, !ExitPredMap, !CFG) :-
     % Return is expressed in CFG as $RET = expr, followed by a branch to the
     % exit block.
@@ -742,17 +751,26 @@
     ExitBlock = cfg.get_exit(!.CFG),
     add_to_pred_map(BBCurrent, DefMap, ExitBlock, !ExitPredMap, !CFG),
     cfg.set_terminator(BBCurrent, branch(ExitBlock, Ctx), !CFG).
-compound_stmt_to_cfg(switch(Ctrl0, Cases0), Ctx, BBCurrent, BBAfter,
+compound_stmt_to_cfg(PT, switch(Ctrl0, Cases0), Ctx, BBCurrent, BBAfter,
     SubscriptMap, DefMap, !AfterPredMap, !ExitPredMap, !CFG) :-
     % Calculate the condition expression at the end of BBCurrent
     apply_def_map_to_expr(DefMap, Ctx, Ctrl0, Ctrl),
     BlockID = ref_id(BBCurrent, !.CFG),
     expr_to_instrs(BlockID, Ctx, Ctrl, CtrlVar, CtrlInstrs, SubscriptMap, _),
     cfg.append_instrs(BBCurrent, CtrlInstrs, !CFG),
-    list.map_foldl3(case_stmt_to_cfg(BBCurrent,BBAfter,SubscriptMap,DefMap),
+    % Convert all patterns to use SSA variables, and generate CFG code for the
+    % bodies of all case statements. The resulting Cases contains goto
+    % statements for each generated block.
+    list.map_foldl3(case_stmt_to_jmp(PT,BBCurrent,BBAfter,SubscriptMap,DefMap),
         Cases0, Cases, !AfterPredMap, !ExitPredMap, !CFG),
-    cfg.set_terminator(BBCurrent, t_switch(CtrlVar, Cases, Ctx), !CFG).
-compound_stmt_to_cfg(if_then_else(Cond0,ThenPart,ElsePart), Ctx, BBCurrent,
+    % Now begin switch factoring transformation
+    % Convert each case statement to a matcher (flatten the patterns)
+    Matchers = list.map(case_to_matcher, Cases),
+    % Generate all switch code. This terminates the current block.
+    generate_matcher_code(PT, [CtrlVar], Matchers, map.init, BBCurrent,
+        SubscriptMap, Ctx, map.init, PhiTable, !CFG),
+    map.foldl(generate_case_block_phis, PhiTable, !CFG).
+compound_stmt_to_cfg(PT, if_then_else(Cond0,ThenPart,ElsePart), Ctx,BBCurrent,
     BBAfter, SubscriptMap, DefMap, !AfterPredMap, !ExitPredMap, !CFG) :-
     % Calculate the condition expression at the end of BBCurrent
     apply_def_map_to_expr(DefMap, Ctx, Cond0, Cond),
@@ -762,7 +780,7 @@
     % Create a new basic block for the "then" part.
     cfg.new_basic_block(ThenEnter, !CFG),
     cfg.append_predecessor(ThenEnter, BBCurrent, !CFG),
-    stmt_block_to_cfg(ThenPart, ThenEnter, BBAfter, DefMap, !AfterPredMap,
+    stmt_block_to_cfg(PT, ThenPart, ThenEnter, BBAfter, DefMap, !AfterPredMap,
         !ExitPredMap, !CFG),
     ( list.is_empty(ElsePart) ->
         % Branch straight to the "after" block if the condition fails
@@ -773,14 +791,14 @@
         % Create a new basic block for the "else" part.
         cfg.new_basic_block(ElseEnter, !CFG),
         cfg.append_predecessor(ElseEnter, BBCurrent, !CFG),
-        stmt_block_to_cfg(ElsePart, ElseEnter, BBAfter, DefMap, !AfterPredMap,
-            !ExitPredMap, !CFG),
+        stmt_block_to_cfg(PT, ElsePart, ElseEnter, BBAfter, DefMap,
+            !AfterPredMap, !ExitPredMap, !CFG),
         % Have the current block terminate by branching into the then/else
         % blocks
         cfg.set_terminator(BBCurrent,
             cond_branch(CondVar,ThenEnter,ElseEnter,Ctx), !CFG)
     ).
-compound_stmt_to_cfg(while(Cond0, Body), Ctx, BBCurrent, BBAfter,
+compound_stmt_to_cfg(PT, while(Cond0, Body), Ctx, BBCurrent, BBAfter,
     SubscriptMap, DefMap, !AfterPredMap, !ExitPredMap, !CFG) :-
     % Create a new basic block for the condition and body
     cfg.new_basic_block(CondBlock, !CFG),
@@ -800,7 +818,7 @@
 
     % Do the whole fixpoint. Updates CFG by setting CondBlock's phis, and
     % compiling Body.
-    while_fixpoint(CondBlock, BodyEnter, Body, CondBlockPredMap,
+    while_fixpoint(PT, CondBlock, BodyEnter, Body, CondBlockPredMap,
         !ExitPredMap, DefMap, CondBlockDefMap, !CFG),
 
     % CondBlock branches to BodyBlock or BBAfter, based on the condition
@@ -825,22 +843,24 @@
 % Updates the CFG as follows:
 %  - Sets the phis of CondBlock to the computed phi nodes.
 %  - Compiles the body into BodyEnter, branching to CondBlock.
-:- pred while_fixpoint(bbref(S)::in, bbref(S)::in, stmt_block::in,
+:- pred while_fixpoint(progtable::in, bbref(S)::in, bbref(S)::in,
+    stmt_block::in,
     pred_map(S)::in, pred_map(S)::in, pred_map(S)::out,
     def_map::in, def_map::out, cfg(S)::in, cfg(S)::out) is det.
-while_fixpoint(CondBlock, BodyEnter, Body, CondPredMap, !ExitPredMap,
+while_fixpoint(PT, CondBlock, BodyEnter, Body, CondPredMap, !ExitPredMap,
     !DefMap, !CFG) :-
     % First iteration, assume there are no phis
-    while_fixpoint_(CondBlock, BodyEnter, Body, CondPredMap, [], !ExitPredMap,
-        !DefMap, !CFG).
+    while_fixpoint_(PT, CondBlock, BodyEnter, Body, CondPredMap, [],
+        !ExitPredMap, !DefMap, !CFG).
 
-:- pred while_fixpoint_(bbref(S)::in, bbref(S)::in, stmt_block::in,
+:- pred while_fixpoint_(progtable::in, bbref(S)::in, bbref(S)::in,
+    stmt_block::in,
     pred_map(S)::in, list(phi(S))::in, pred_map(S)::in, pred_map(S)::out,
     def_map::in, def_map::out, cfg(S)::in, cfg(S)::out) is det.
-while_fixpoint_(CondBlock, BodyEnter, Body, CondPredMap0, Phis0,
+while_fixpoint_(PT, CondBlock, BodyEnter, Body, CondPredMap0, Phis0,
     !ExitPredMap, !CondDefMap, !CFG) :-
     % Compute CondPredMap (after another iteration of the body)
-    stmt_block_to_cfg(Body, BodyEnter, CondBlock, !.CondDefMap,
+    stmt_block_to_cfg(PT, Body, BodyEnter, CondBlock, !.CondDefMap,
         CondPredMap0, CondPredMap, !ExitPredMap, !.CFG, PotentialFinalCFG),
     % Now we can compute the phis for the cond block
     CondBlockID = ref_id(CondBlock, !.CFG),
@@ -853,13 +873,416 @@
         !:CondDefMap = CondDefMap1
     ;
         % Now iterate till fixpoint
-        while_fixpoint_(CondBlock, BodyEnter, Body, CondPredMap, Phis,
+        while_fixpoint_(PT, CondBlock, BodyEnter, Body, CondPredMap, Phis,
             !ExitPredMap, CondDefMap1, !:CondDefMap, !CFG)
     ).
 
-% case_stmt_to_cfg(+BBAfter, +SubscriptMap, +DefMap, +CaseStmt, -CFGCaseStmt,
+% Intermediate representation of a case statement -- still contains recursive
+% patterns, but branches to block references rather than containing AST code.
+% (This is half-way between a case_stmt and a matcher.)
+:- type jmp_case_stmt(S)
+    --->    jmp_case_stmt(pattern, cfg.bbref(S), context.context).
+
+% Intermediate representation for switch statements being factored
+% A "matcher" is like a flattened case statement. Rather than having just a
+% single pattern, it has a list of matches, which represent the pattern heads
+% which need to be matched, in order, in a depth-first left-to-right traversal
+% of the pattern tree.
+:- type matcher(S)
+    --->    matcher(list(match), cfg.bbref(S)).
+% A match is the head of a pattern -- same as a pattern but ctors aren't
+% recursive.
+:- type match
+            % "_" pattern (don't care / wildcard)
+    --->    match_any
+            % Variable. Matches anything, and binds a new variable of the
+            % given name.
+    ;       match_var(varname)
+            % Constructor match. Matches only values with the given ctor
+            % name and arity.
+    ;       match_ctor(string, int)
+            % Integer literal. Matches exactly this value.
+    ;       match_intlit(integer).
+
+% Binding table for switch generation. Determines, for a given target block
+% and bound variable name, which source variable holds the value of the bound
+% variable.
+:- type binding_table(S) == map(cfg.bbref(S), map(varname, varname)).
+
+% Phi table for switch generation. Dynamically-constructed table of phi nodes
+% for blocks which are targets of case statements.
+:- type phi_table(S) == map(cfg.bbref(S),
+                            multi_map(varname, pair(cfg.bbref(S), varname))).
+
+% Create a new entry in the phi table.
+:- pred create_phi_table_entry(bbref(S)::in, varname::in, bbref(S)::in,
+    varname::in, phi_table(S)::in, phi_table(S)::out) is det.
+create_phi_table_entry(Target, BoundVar, SourceBlock, SourceVar, !PhiTable) :-
+    ( map.search(!.PhiTable, Target, TPM) ->
+        TargetPhiMap0 = TPM
+    ;
+        TargetPhiMap0 = multi_map.init
+    ),
+    Source = SourceBlock-SourceVar,
+    multi_map.add(TargetPhiMap0, BoundVar, Source, TargetPhiMap),
+    svmap.set(Target, TargetPhiMap, !PhiTable).
+
+% Flatten a case statement out to a "matcher"
+:- func case_to_matcher(jmp_case_stmt(S)) = matcher(S).
+case_to_matcher(jmp_case_stmt(Pat, BBRef, _)) = matcher(Matches, BBRef) :-
+    Matches = pattern_to_matches(Pat).
+
+% Flatten a pattern out to a list of matches
+:- func pattern_to_matches(pattern) = list(match).
+pattern_to_matches(Pat0) = Matches :-
+    Pat = Pat0 ^ pat_pattern,
+    % Convert the pattern Pat into a flat list of matches, Matches
+    (
+        Pat = pat_any,
+        Matches = [match_any]
+    ;
+        Pat = pat_var(Varname),
+        Matches = [match_var(Varname)]
+    ;
+        % Nullary constructor -- just treat as if 0-ary
+        Pat = pat_ctor(Name, no),
+        Matches = [match_ctor(Name, 0)]
+    ;
+        Pat = pat_ctor(Name, yes(Patterns)),
+        FirstMatch = match_ctor(Name, list.length(Patterns)),
+        % Need to recurse, and subsequently match all sub-patterns
+        % Generate matches for each sub-pattern, then condense all into one
+        % continuous list.
+        SubMatches = list.condense(list.map(pattern_to_matches, Patterns)),
+        % Place the first match at the front, then the subsequent matches.
+        Matches = [FirstMatch|SubMatches]
+    ;
+        Pat = pat_intlit(Val),
+        Matches = [match_intlit(Val)]
+    ).
+
+% generate_matcher_code(ArgList, MatcherList, BindingTable, BBCurrent,
+%                       SubscriptMap, SwitchCtx, !PhiTable, !CFG).
+% Generates switch code for a list of matchers. ArgList is a list of variable
+% names which will be matched in order against the patterns in each matcher of
+% MatcherList.
+% The code is appended to block BBCurrent (may also generate new blocks).
+% (The matches in each matcher of MatcherList may be longer than ArgList, as a
+% top-level variable may occupy many elements of MatcherList).
+% This algorithm is explained in detail in doc/dev/switchfactor.
+:- pred generate_matcher_code(progtable::in, list(varname)::in,
+    list(matcher(S))::in,
+    binding_table(S)::in, bbref(S)::in, subscript_map::in, context::in,
+    phi_table(S)::in, phi_table(S)::out, cfg(S)::in, cfg(S)::out) is det.
+generate_matcher_code(_PT, [], MatcherList, BindingTable, BBCurrent,
+    _SubscriptMap, Ctx, !PhiTable, !CFG) :-
+    % Base case -- No more args to switch on.
+    % This generates a branch, which is inefficient code. This should usually
+    % be handled on the recursive call, meaning that you should usually not
+    % get here at all.
+    % Expect that the first item in MatcherList has 0 matches, so just branch
+    % to it.
+    (
+        MatcherList = [],
+        throw("ast_cfg.generate_matcher_code: No matchers remaining.")
+    ;
+        MatcherList = [matcher([_|_], _)|_],
+        throw("ast_cfg.generate_matcher_code: "
+            ++ "ArgList empty, matcher not empty.")
+    ;
+        MatcherList = [matcher([], Target)|_]
+    ),
+    % Just generate a branch to the Target of the first matcher
+    cfg.append_predecessor(Target, BBCurrent, !CFG),
+    cfg.set_terminator(BBCurrent, branch(Target, Ctx), !CFG),
+    % Create entries in the phi table for each entry in the binding table
+    ( map.search(BindingTable, Target, TargetBinding) ->
+        map.foldl((pred(BoundVar::in,SourceVar::in,Phi0::in,Phi::out) is det:-
+                % For each binding table entry (BoundVar-SourceVar), create a
+                % phi table entry (Target-BoundVar) = (BBCurrent-SourceVar).
+                create_phi_table_entry(Target, BoundVar, BBCurrent, SourceVar,
+                                       Phi0, Phi)
+            ), TargetBinding, !PhiTable)
+    ;
+        true
+    ).
+generate_matcher_code(PT, [MatchVar|RestVars], MatcherList0, BindingTable0,
+    BBCurrent, SubscriptMap0, Ctx, !PhiTable, !CFG) :-
+    % Generate code for matching MatchVar against the first pattern in each
+    % matcher of MatcherList, then recurse.
+
+    % Step 1 - Store explicit variable bindings
+    % If the first argument of a matcher is match_var, add a variable binding
+    % instruction to its target block.
+    % Modify MatcherList, replacing all initial match_vars with match_any.
+    list.map_foldl(matcher_variable_binding(MatchVar),
+        MatcherList0, MatcherList, BindingTable0, BindingTable),
+
+    % Step 2 - Create association list
+    % The values we're going to switch on
+    ValuesOfInterest = list.remove_dups(list.map(matcher_first_match,
+                                                 MatcherList)),
+    AssocList = list.map((func(K) = K-select_matchers(K, MatcherList)),
+                         ValuesOfInterest),
+
+    % Test for incomplete switch (error case)
+    switch_exhaustion_check(PT, ValuesOfInterest, Ctx),
+
+    % Step 3 - Generate switch statement
+    % We create exactly one case (incl. default) for each value of interest
+    % This also gets AssocListBlocks, which has a third column, the block ID,
+    % and also has any entries after the first "_" removed.
+    ( (list.length(AssocList) = 1 ; AssocList = [match_any-_|_]) ->
+        % Special case -- Only one case or first case is default
+        % Do not generate a switch statement. Just continue on from the end of
+        % the current block.
+        Match-Matchers = list.det_head(AssocList),
+        AssocListBlocks = [{Match, Matchers, BBCurrent}],
+        % The target block is the same as the current one -- keep the same
+        % subscript map
+        SubscriptMap = SubscriptMap0
+    ;
+        % Generate the switch statement
+        generate_case_stmts(BBCurrent, AssocList, Cases, Default,
+                            AssocListBlocks, !CFG),
+        % Write the switch statement to the current block
+        cfg.set_terminator(BBCurrent, t_switch(MatchVar, Cases, Default, Ctx),
+                           !CFG),
+        % All of the new blocks are fresh, so the target block's subscript map
+        % is empty
+        SubscriptMap = map.init
+    ),
+
+    % Step 4 - Write implicit unpacking instructions to each block and recurse
+    % Start the new block with a fresh subscript map
+    % (This calls generate_matcher_code for each target block).
+    list.foldl2(write_unpack_instructions(PT,MatchVar, RestVars, BindingTable,
+                                          SubscriptMap, Ctx),
+                AssocListBlocks, !PhiTable, !CFG),
+
+    true.
+
+% matcher_variable_binding(MatchVar, !Matcher, !BindingTable).
+% If Matcher's first match is a match_var, creates a binding from MatchVar to
+% the given variable name, in the Matcher's target block. Also updates
+% Matcher, replacing the match_var with match_any.
+:- pred matcher_variable_binding(varname::in, matcher(S)::in, matcher(S)::out,
+    binding_table(S)::in, binding_table(S)::out) is det.
+matcher_variable_binding(MatchVar, !Matcher, !BindingTable) :-
+    ( !.Matcher = matcher([match_var(BindVar)|Rest], TargetBB) ->
+        % Add a binding table entry for TargetBB
+        ( map.search(!.BindingTable, TargetBB, BlockTable_) ->
+            BlockTable0 = BlockTable_
+        ;
+            BlockTable0 = map.init
+        ),
+        svmap.det_insert(BindVar, MatchVar, BlockTable0, BlockTable),
+        svmap.set(TargetBB, BlockTable, !BindingTable),
+        % Replace match_var with match_any
+        !:Matcher = matcher([match_any|Rest], TargetBB)
+    ;
+        true
+    ).
+
+% Gets the first match of a matcher.
+% Aborts if there is none.
+:- func matcher_first_match(matcher(S)) = match.
+matcher_first_match(matcher([First|_],_)) = First.
+matcher_first_match(matcher([],_)) = throw("Matcher is empty").
+
+% Selects all matchers which begin with match.
+% Removes the match from the beginning, and adjusts wildcard matches so they
+% have the correct number of start entries.
+:- func select_matchers(match, list(matcher(S))) = list(matcher(S)).
+select_matchers(StartMatch, Matchers) = FilteredMatchers :-
+    list.filter_map(select_matcher(StartMatch), Matchers, FilteredMatchers).
+
+:- pred select_matcher(match::in, matcher(S)::in, matcher(S)::out) is semidet.
+select_matcher(StartMatch, Matcher0, Matcher) :-
+    Matcher0 = matcher([First|Rest], Target),
+    ( First = StartMatch ->
+        % First match is correct (ctor, intlit or _). Just remove it.
+        Matcher = matcher(Rest, Target)
+    ; First = match_any ->
+        % First match is _. Always match, but carefully adjust.
+        ( StartMatch = match_ctor(_, Arity) ->
+            % The wildcard match is matching a ctor, so we need to perform
+            % sub-matches (which would all be wildcards)
+            Matcher = matcher(list.duplicate(Arity, match_any) ++ Rest,
+                              Target)
+        ;
+            Matcher = matcher(Rest, Target)
+        )
+    ;
+        fail
+    ).
+
+% Given a list of matches, representing the cases at one level of a switch
+% statement, test that the switch (at that level) cannot possibly fail.
+% This means it has a default, or all cases are covered for the switched type.
+% If a switch fails this test, throws a context error. Otherwise, succeeds.
+:- pred switch_exhaustion_check(progtable::in, list(match)::in, context::in)
+    is det.
+switch_exhaustion_check(PT, Matches, Ctx) :-
+    ( list.member(match_any, Matches) ->
+        % Fine -- The switch has a default case
+        true
+    % Block ends with a switch with no default. Closely analyse its cases
+    % to determine whether it is exhaustive.
+    % Note: List must be entirely match_intlit or match_ctor
+    ; SomeMatch = list.head(Matches) ->
+        % Any match will do, since they all (must) have the same type
+        % We are only interested in the match's type
+        (
+            SomeMatch = match_ctor(SomeCtor, _),
+            % Use SomeCtor to retrieve the typedef we are switching over
+            % (Any Ctor will do). This is easier than finding the typedef from
+            % a type value.
+            ( tables.lookup_ctor(PT, SomeCtor, SwitchTypeDef, _) ->
+                % Get the names of all ctors for the type
+                AllCtors = map(func(Ctor) = Ctor ^ ctor_name,
+                    SwitchTypeDef ^ typedef_ctors),
+                % Get the names of all ctors named in a case
+                MatchCtors = map((func(Match) = CtorName :-
+                        ( Match = match_ctor(C, _) ->
+                            CtorName = C
+                        ;
+                            throw("ast_cfg: Not all matches are ctors")
+                        )),
+                    Matches),
+                % The two sets should be equal
+                % Delete each element of CaseCtor from AllCtors
+                % UnhandledCtors = AllCtors / CaseCtors (should be empty)
+                list.foldl((pred(MatchCtor::in, AC0::in, AC::out) is det :-
+                            ( list.delete_first(AC0, MatchCtor, AC_) ->
+                                AC = AC_
+                            ;
+                                throw("ast_cfg: Match " ++ MatchCtor ++
+                                    " not a member of switch type")
+                            )
+                        ),
+                    MatchCtors, AllCtors, UnhandledCtors),
+                ( list.is_empty(UnhandledCtors) ->
+                    % Fine -- All cases handled in switch
+                    true
+                ;
+                    context.throw_error(
+                        "Incomplete switch: requires case(s) for "
+                        ++ string.join_list(", ", UnhandledCtors), Ctx)
+                )
+            ;
+                throw("ast_cfg: Ctor name not defined")
+            )
+        ;
+            SomeMatch = match_intlit(_),
+            % It is ALWAYS an error to have an int switch without a default
+            % case, since you can't cover all the ints.
+            context.throw_error("Incomplete switch: requires default case "
+                ++ "for switch on integer", Ctx)
+        ;
+            SomeMatch = match_any,
+            throw("ast_cfg: match_any in match list")
+        ;
+            SomeMatch = match_var(_),
+            throw("ast_cfg: match_var in match list")
+        )
+    ;
+        throw("ast_cfg: Switch check on empty match list")
+    ).
+
+% generate_case_stmts(+BBCurrent, +AssocList, -Cases, -Default,
+%                     -AssocListBlocks, !CFG).
+% Given an assoc list (a match for each case, mapped to a list of matchers),
+% generate a case statement for each matcher, and create a new target block in
+% the CFG for the case statement.
+% Returns AssocListBlocks, which is AssocList augmented with a target block
+% for each AssocList entry.
+% Will ignore any matches after a match_any. Aborts on match_var.
+:- pred generate_case_stmts(bbref(S)::in,
+    assoc_list(match, list(matcher(S)))::in,
+    assoc_list(case_value, bbref(S))::out, maybe(bbref(S))::out,
+    list({match, list(matcher(S)), bbref(S)})::out,
+    cfg(S)::in, cfg(S)::out) is det.
+% Base case: No matches. Therefore no cases and no default.
+generate_case_stmts(_, [], [], no, [], !CFG).
+% Base case: Match is "_". Therefore, generate a default case and stop.
+generate_case_stmts(BBCurrent, [match_any-M|_], [], yes(Default), [ALB],
+    !CFG) :-
+    cfg.new_basic_block(Default, !CFG),
+    cfg.append_predecessor(Default, BBCurrent, !CFG),
+    ALB = {match_any, M, Default}.
+% Error case: Match is a var. Should have been taken out by now.
+generate_case_stmts(_, [match_var(_)-_|_], _, _, _, !CFG) :-
+    throw("ast_cfg.generate_case_stmts: Found match_var").
+generate_case_stmts(BBCurrent, [match_ctor(Name, Arity)-M|Matches],
+    [Case|Cases], Default, [ALB|ALBs], !CFG) :-
+    cfg.new_basic_block(Target, !CFG),
+    cfg.append_predecessor(Target, BBCurrent, !CFG),
+    Case = case_ctor(Name) - Target,
+    ALB = {match_ctor(Name, Arity), M, Target},
+    % Recurse
+    generate_case_stmts(BBCurrent, Matches, Cases, Default, ALBs, !CFG).
+generate_case_stmts(BBCurrent, [match_intlit(Val)-M|Matches],
+    [Case|Cases], Default, [ALB|ALBs], !CFG) :-
+    cfg.new_basic_block(Target, !CFG),
+    cfg.append_predecessor(Target, BBCurrent, !CFG),
+    Case = case_intlit(Val) - Target,
+    ALB = {match_intlit(Val), M, Target},
+    % Recurse
+    generate_case_stmts(BBCurrent, Matches, Cases, Default, ALBs, !CFG).
+
+% write_unpack_instructions(SourceVar, RestVars, BindingTable, SubscriptMap,
+%                           Ctx, {Match, Matchers, Block}, !PhiTable, !CFG).
+% Writes implicit record unpacking instructions for the constructor mentioned
+% by Match to the end of Block, and then calls generate_matcher_code to
+% recursively generate the rest of the switch statement for that block.
+:- pred write_unpack_instructions(progtable::in, varname::in,
+    list(varname)::in, binding_table(S)::in, subscript_map::in, context::in,
+    {match, list(matcher(S)), bbref(S)}::in,
+    phi_table(S)::in, phi_table(S)::out, cfg(S)::in, cfg(S)::out) is det.
+write_unpack_instructions(PT, SourceVar, RestVars, BindingTable, SubscriptMap,
+                          Ctx, AssocEntry, !PhiTable, !CFG) :-
+    {Match, Matchers, Block} = AssocEntry,
+    ( Match = match_ctor(Name, Arity) ->
+        % Write Arity unpack instructions to Block
+        % Store the names of the unpacked vars in UnpackedVars
+        list.map_foldl2((pred(VarID::in, TempVName::out, SM0::in, SM::out,
+                              C0::in, C::out) is det :-
+                % Write one, then recurse
+                new_temp_variable(ref_id(Block, C0), TempVName, SM0, SM),
+                Instr = instr(ld_field_idx(TempVName, SourceVar, Name, VarID),
+                              context.blank_context),
+                cfg.append_instr(Block, Instr, C0, C)
+            ), util.range(Arity), UnpackedVars, SubscriptMap, _, !CFG)
+    ;
+        UnpackedVars = []
+    ),
+    % Construct the new ArgList.
+    % First, need to switch on all of the unpacked variables, then the
+    % remaining ArgList variables.
+    ArgList = UnpackedVars ++ RestVars,
+    % Recursively call generate_matcher_code for this block
+    generate_matcher_code(PT, ArgList, Matchers, BindingTable, Block,
+                          SubscriptMap, Ctx, !PhiTable, !CFG).
+
+% generate_case_block_phis(TargetBlock, Phis, !CFG).
+% Generates all phis for case block TargetBlock. Phis is the phi table entry
+% for TargetBlock, a multimap mapping bound varnames to source block/varname
+% pairs.
+:- pred generate_case_block_phis(bbref(S)::in,
+    multi_map(varname, pair(bbref(S), varname))::in, cfg(S)::in, cfg(S)::out)
+    is det.
+generate_case_block_phis(TargetBlock, Phis, !CFG) :-
+    map.foldl((pred(BoundVar::in, Bindings::in, CFG0::in, CFG::out) is det :-
+            % For each phi
+            Preds = map.from_assoc_list(Bindings),
+            PhiInstr = phi(BoundVar, Preds),
+            cfg.append_phi(TargetBlock, PhiInstr, CFG0, CFG)
+        ), Phis, !CFG).
+
+% case_stmt_to_jmp(+BBAfter, +SubscriptMap, +DefMap, +CaseStmt, -CFGCaseStmt,
 %   !AfterPredMap, !ExitPredMap, !CFG).
-% Compiles a case statement into a CFG case statement (which is
+% Compiles a case statement into a jmp case statement (which is
 % branch-oriented rather than sub-statement-block-oriented).
 % Compiles the sub-statement-block in the case statement to new basic blocks,
 % which will ultimately branch to BBAfter.
@@ -870,12 +1293,12 @@
 % SubscriptMap is read-only (since it will definitely branch to a new block).
 % DefMap is read-only (the resulting def-maps should be appended to
 % AfterPredMap).
-:- pred case_stmt_to_cfg(bbref(S)::in, bbref(S)::in,
-    subscript_map::in, def_map::in, case_stmt::in, cfg_case_stmt(S)::out,
+:- pred case_stmt_to_jmp(progtable::in, bbref(S)::in, bbref(S)::in,
+    subscript_map::in, def_map::in, case_stmt::in, jmp_case_stmt(S)::out,
     pred_map(S)::in, pred_map(S)::out, pred_map(S)::in, pred_map(S)::out,
     cfg(S)::in, cfg(S)::out) is det.
-case_stmt_to_cfg(BBCurrent, BBAfter, SubscriptMap, DefMap,
-    case_stmt(Pattern0, Stmts, Ctx), cfg_case_stmt(Pattern, BBFirst, Ctx),
+case_stmt_to_jmp(PT, BBCurrent, BBAfter, SubscriptMap, DefMap,
+    case_stmt(Pattern0, Stmts, Ctx), jmp_case_stmt(Pattern, BBFirst, Ctx),
     !AfterPredMap, !ExitPredMap, !CFG) :-
     % Traverse the pattern and uniquely label each newly-introduced
     % variable, as well as adding them to DefMap.
@@ -884,8 +1307,7 @@
         InnerScopeDefMap),
 
     cfg.new_basic_block(BBFirst, !CFG),
-    cfg.append_predecessor(BBFirst, BBCurrent, !CFG),
-    stmt_block_to_cfg(Stmts, BBFirst, BBAfter, InnerScopeDefMap,
+    stmt_block_to_cfg(PT, Stmts, BBFirst, BBAfter, InnerScopeDefMap,
         !AfterPredMap, !ExitPredMap, !CFG).
 
 % pattern_to_ssa(BlockID, !Pattern, !SubscriptMap, !DefMap).

=== modified file 'src/interpret.m'
--- src/interpret.m	2010-01-25 01:23:14 +0000
+++ src/interpret.m	2010-01-25 07:28:13 +0000
@@ -128,6 +128,7 @@
 :- import_module svmap.
 :- import_module set.
 :- import_module pair.
+:- import_module assoc_list.
 :- import_module array.
 :- import_module exception.
 :- import_module store.
@@ -468,6 +469,20 @@
     env_assign_local(Dst, Result, !Env).
 exec_instr_(ld_field(_Dst, _Val, _FieldName), _Ctx, !Env, !IO) :-
     throw("Not Implemented: Field reference").
+exec_instr_(ld_field_idx(Dst, ValName, Ctor, Idx), _Ctx, !Env, !IO) :-
+    read_var(!.Env, ValName, Val, !IO),
+    ( Val = val_term(Ctor, Fields) ->       % Must match supplied Ctor name
+        ( list.index0(Fields, Idx, FieldVal) ->     % Fail if bounds error
+            Result = FieldVal
+        ;
+            throw("Interpreter Error: Field index out of range")
+        )
+    ; Val = val_term(_, _) ->
+        throw("Interpreter Error: Field reference with wrong ctor")
+    ;
+        throw("Interpreter Error: Field reference to something not an ADT")
+    ),
+    env_assign_local(Dst, Result, !Env).
 exec_instr_(call(Dst, Func, Args), _Ctx, !Env, !IO) :-
     % Evaluate Func and Arg (eagerly)
     read_var(!.Env, Func, FuncVal, !IO),
@@ -627,9 +642,9 @@
     % Execute the terminator
     Term = Block ^ bb_terminator,
     (
-        Term = t_switch(Control, Cases, _),
+        Term = t_switch(Control, Cases, Default, _),
         read_var(!.Env, Control, ControlVal, !IO),
-        exec_cases(CFG, BBRef, !Env, ControlVal, Cases, !IO)
+        exec_cases(CFG, BBRef, !Env, ControlVal, Cases, Default, !IO)
     ;
         Term = cond_branch(Cond, Then, Else, _),
         read_var(!.Env, Cond, CondVal, !IO),
@@ -668,69 +683,47 @@
         throw("Interpreter Error: Phi missing prececessor in CFG")
     ).
 
-% exec_cases(CFG, Predecessor, !Env, ControlValue, Cases, !IO).
+% exec_cases(CFG, Predecessor, !Env, ControlValue, Cases, Default, !IO).
 % Performs a switch over Cases, and executes the first one which matches.
 :- pred exec_cases(cfg(S)::in, bbref(S)::in, env::in, env::out,
-    value::in, list(cfg_case_stmt(S))::in, io::di, io::uo) is det.
-exec_cases(_CFG, _Predecessor, !Env, _ControlValue, [], !IO) :-
-    % No pattern matched
-    % XXX Should be checked statically so this never occurs, and therefore, we
-    % raise an interpreter error at this point.
-    % Currently, no check is made, and ast_cfg goes nuts if a switch
-    % statement isn't handled by default. Therefore, we need to raise a
-    % friendly runtime error for the time being.
-    throw_mars_error("Pattern match failure").
-    %throw("Interpreter Error: Pattern match failure").
-exec_cases(CFG, Predecessor, !Env, ControlValue, [Case|Cases], !IO) :-
-    Case = cfg_case_stmt(Pattern, Target, _Ctx),
-    ( pattern_match(Pattern, ControlValue, !Env) ->
-        % Succeeded. Branch to Target (with the new bindings) and ignore the
-        % remaining Cases.
+    value::in, assoc_list(case_value, bbref(S))::in, maybe(bbref(S))::in,
+    io::di, io::uo) is det.
+exec_cases(CFG, Predecessor, !Env, _ControlValue, [], Default, !IO) :-
+    % No case matched, execute the default
+    (
+        Default = yes(DefTarget),
+        exec_block(CFG, Predecessor, DefTarget, !Env, !IO)
+    ;
+        Default = no,
+        % Should never occur -- by the invariant of t_switch, there MUST be a
+        % default case if the case statements are not exhaustive.
+        % (This should be guaranteed by ast_cfg). Therefore, internal error.
+        throw("Interpreter Error: No case matched and no default case")
+    ).
+exec_cases(CFG, Predecessor, !Env, ControlValue, [Case|Cases], Default,!IO) :-
+    Case = CaseVal - Target,
+    ( check_case_value(CaseVal, ControlValue) ->
+        % Succeeded. Branch to Target and ignore the remaining Cases.
         exec_block(CFG, Predecessor, Target, !Env, !IO)
     ;
         % That match failed. Try the rest.
-        exec_cases(CFG, Predecessor, !Env, ControlValue, Cases, !IO)
+        exec_cases(CFG, Predecessor, !Env, ControlValue, Cases, Default, !IO)
     ).
 
-% pattern_match(Pattern, Value, !Env).
-% Matches Value against Pattern, making bindings in !Env if successful.
-% Fails if the pattern match fails.
-:- pred pattern_match(pattern::in, value::in, env::in, env::out) is semidet.
-pattern_match(pattern(Pattern, _PatType), Value, !Env) :-
+% check_case_value(CaseVal, Value).
+% Succeeds if Value matches the case value CaseVal.
+:- pred check_case_value(case_value::in, value::in) is semidet.
+check_case_value(CaseVal, Value) :-
     (
-        Pattern = pat_any
-        % Done, succeed with no bindings
-    ;
-        Pattern = pat_var(VarName),
-        % Succeed, and bind
-        env_assign_local(VarName, Value, !Env)
-    ;
-        Pattern = pat_ctor(CtorName, SubPatterns),
-        Value = val_term(CtorName, SubValues),              % Can fail
-        % Recursively match all sub-terms with sub-patterns
-        (
-            SubPatterns = yes(YesSubPatterns),
-            pattern_match_list(YesSubPatterns, SubValues, !Env)  % Can fail
-        ;
-            SubPatterns = no
-        )
-    ;
-        Pattern = pat_intlit(Int),
+        CaseVal = case_ctor(CtorName),
+        Value = val_term(CtorName, _)   % Can fail
+        % Note: Do not recurse; succeed regardless of the term's arguments
+    ;
+        CaseVal = case_intlit(Int),
         % Succeed if the value is a matching int
         Value = val_int(Int)    % Can fail
     ).
 
-% pattern_match_list(Patterns, Values, !Env).
-% Matches Values against Patterns, making bindings in !Env if successful.
-% Succeeds only if each value matches its corresponding pattern, and the lists
-% are exactly the same length.
-:- pred pattern_match_list(list(pattern)::in, list(value)::in,
-    env::in, env::out) is semidet.
-pattern_match_list([], [], !Env).
-pattern_match_list([P|Ps], [V|Vs], !Env) :-
-    pattern_match(P, V, !Env),          % Can fail
-    pattern_match_list(Ps, Vs, !Env).   % Can fail
-
 % -------------------------------------------------------------------------- %
 % BUILTINS
 % -------------------------------------------------------------------------- %

=== modified file 'src/ir.m'
--- src/ir.m	2010-01-25 01:23:14 +0000
+++ src/ir.m	2010-01-25 07:28:13 +0000
@@ -51,6 +51,7 @@
 :- import_module string.
 :- import_module bool.
 :- import_module list.
+:- import_module assoc_list.
 :- import_module maybe.
 :- import_module pair.
 
@@ -207,6 +208,9 @@
             % Load a field of a variable into a variable.
             % (R, S, F) <=> R := S.F
     ;       ld_field(varname, varname, string)
+            % Load a field of a variable, by constructor(index)
+            % (R, S, C, I) <=> R := S.C(I)
+    ;       ld_field_idx(varname, varname, string, int)
             % Function call. (Result, Function, Args).
     ;       call(varname, varname, list(varname))
             % Partial function application. (Result, Function, Args).
@@ -219,10 +223,17 @@
 % type" used to prevent terminators from referencing basic blocks in the wrong
 % CFG.
 :- type terminator_instr(S)
-            % Switch instruction. Performs pattern matching of algebraic data
-            % types. Branches to the first basic block to match the pattern
-            % (binding variables from the pattern over the block's scope).
-    --->    t_switch(varname, list(cfg_case_stmt(S)), context.context)
+            % t_switch(ControlVar, Cases, Default).
+            % Simplified switch instruction. Performs matching of algebraic
+            % data types' head values, or integers.
+            % If ControlVar matches one of the Cases, branches to that basic
+            % block. Otherwise, branches to Default.
+            % Default is optional, but may ONLY be omitted if the cases cover
+            % all possible values of an ADT, and is mandatory for switches
+            % over integers.
+            % Two cases may not have the same case value.
+    --->    t_switch(varname, assoc_list(case_value, bbref(S)),
+                     maybe(bbref(S)), context.context)
             % Conditional branch instruction. Expr must be of type Int.
             % Evaluates Expr, then branches to the first basic block if it is
             % nonzero, or the second basic block if it is zero.
@@ -241,11 +252,7 @@
 % An AST representation's case statement.
 :- type case_stmt
     --->    case_stmt(pattern, stmt_block, context.context).
-
-% A CFG representation's case statement.
-:- type cfg_case_stmt(S)
-    --->    cfg_case_stmt(pattern, cfg.bbref(S), context.context).
-% A pattern (part of a case statement).
+% An AST representation's pattern (part of a case statement).
 :- type pattern
     --->    pattern(
                 pat_pattern :: pattern_,
@@ -263,6 +270,15 @@
             % Integer literal. Matches exactly this value.
     ;       pat_intlit(integer).
 
+% A value which is matched by a case of a t_switch instruction in CFG
+% representation.
+:- type case_value
+            % Constructor match. Matches only values with the given ctor
+            % name, without checking arity or arguments.
+    --->    case_ctor(string)
+            % Integer literal. Matches exactly this value.
+    ;       case_intlit(integer).
+
 % A uniqueness annotation for a particular argument of a function
 :- type argmode
     --->    argmode(

=== modified file 'src/mars.m'
--- src/mars.m	2010-01-22 01:54:37 +0000
+++ src/mars.m	2010-01-25 07:28:13 +0000
@@ -155,7 +155,7 @@
     % Typecheck the program
     typecheck.check_program(ProgTable, Prog, Prog_Checked),
     % Convert the program from AST representation into CFG representation
-    ast_cfg.prog_to_cfg(Prog_Checked, ProgCFG),
+    ast_cfg.prog_to_cfg(ProgTable, Prog_Checked, ProgCFG),
     % Build another ProgTable
     tables.build_progtable(ProgCFG, builtins.builtins_progtable,
         ProgTableCFG),

=== modified file 'src/marsc.m'
--- src/marsc.m	2010-01-22 01:54:37 +0000
+++ src/marsc.m	2010-01-25 07:28:13 +0000
@@ -155,7 +155,7 @@
     check_main_func(ProgTable, MainFunc),
     ( backend_use_cfg(BackendName) ->
         % Convert the program from AST representation into CFG representation
-        ast_cfg.prog_to_cfg(Prog_Checked, Prog2),
+        ast_cfg.prog_to_cfg(ProgTable, Prog_Checked, Prog2),
         % Build another ProgTable
         tables.build_progtable(Prog2, builtins.builtins_progtable,
             ProgTable2)

=== modified file 'src/pretty.m'
--- src/pretty.m	2010-01-25 01:23:14 +0000
+++ src/pretty.m	2010-01-25 07:28:13 +0000
@@ -367,6 +367,10 @@
     io.write_string(ir.varname_to_string_noescape(Dst), !IO),
     io.write_string(" = ", !IO),
     io.write_string(ir.varname_to_string_noescape(Obj) ++ "." ++ Field, !IO).
+print_instr_(Indent, ld_field_idx(Dst, Obj, Ctor, Index), !IO) :-
+    indent(Indent, !IO),
+    io.format("%s = %s.%s(%d)", [s(ir.varname_to_string_noescape(Dst)),
+        s(ir.varname_to_string_noescape(Obj)), s(Ctor), i(Index)], !IO).
 print_instr_(Indent, call(Dst, Func, Args), !IO) :-
     indent(Indent, !IO),
     io.write_string(ir.varname_to_string_noescape(Dst), !IO),
@@ -386,12 +390,22 @@
 
 :- pred print_terminator_instr(int::in, cfg(S)::in, terminator_instr(S)::in,
     io::di,io::uo) is det.
-print_terminator_instr(Indent, CFG, t_switch(Control, Cases, _), !IO) :-
+print_terminator_instr(Indent, CFG, t_switch(Control,Cases,Default,_), !IO) :-
     indent(Indent, !IO),
     io.write_string("switch ", !IO),
     io.write_string(ir.varname_to_string_noescape(Control), !IO),
     io.write_string(":\n", !IO),
-    foldl(print_cfg_case(Indent+1, CFG), Cases, !IO).
+    foldl(print_cfg_case(Indent+1, CFG), Cases, !IO),
+    % Print the default case, if any
+    (
+        Default = yes(DefTarget),
+        indent(Indent+1, !IO),
+        io.write_string("default: goto ", !IO),
+        io.write(cfg.ref_id(DefTarget, CFG), !IO),
+        io.nl(!IO)
+    ;
+        Default = no
+    ).
 print_terminator_instr(Indent, CFG, cond_branch(Cond, ThenPart, ElsePart, _),
     !IO) :-
     indent(Indent, !IO),
@@ -419,16 +433,6 @@
     io.write_string(":\n", !IO),
     foldl(print_stmt(Indent+1), Stmts, !IO).
 
-:- pred print_cfg_case(int::in, cfg(S)::in, cfg_case_stmt(S)::in,
-    io::di, io::uo) is det.
-print_cfg_case(Indent, CFG, cfg_case_stmt(Pattern, Target, _), !IO) :-
-    indent(Indent, !IO),
-    io.write_string("case ", !IO),
-    io.write_string(string_pattern(Pattern), !IO),
-    io.write_string(": goto ", !IO),
-    io.write(cfg.ref_id(Target, CFG), !IO),
-    io.nl(!IO).
-
 string_pattern(pattern(P,_)) = string_pattern_(P).
 
 :- func string_pattern_(pattern_) = string.
@@ -447,6 +451,20 @@
     ).
 string_pattern_(pat_intlit(I)) = integer.to_string(I).
 
+:- pred print_cfg_case(int::in, cfg(S)::in, pair(case_value, bbref(S))::in,
+    io::di, io::uo) is det.
+print_cfg_case(Indent, CFG, CaseVal - Target, !IO) :-
+    indent(Indent, !IO),
+    io.write_string("case ", !IO),
+    io.write_string(string_caseval(CaseVal), !IO),
+    io.write_string(": goto ", !IO),
+    io.write(cfg.ref_id(Target, CFG), !IO),
+    io.nl(!IO).
+
+:- func string_caseval(case_value) = string.
+string_caseval(case_ctor(Name)) = Name.
+string_caseval(case_intlit(I)) = integer.to_string(I).
+
 print_function_head(Func, !IO) :-
     io.write_string(Func^func_name, !IO),
     (

=== modified file 'test/cases/compiler/switch.mar'
--- test/cases/compiler/switch.mar	2010-01-25 05:33:55 +0000
+++ test/cases/compiler/switch.mar	2010-01-25 07:28:13 +0000
@@ -13,6 +13,9 @@
     B
     C
 
+type Box(a):
+    Box(a)
+
 # Test cases with multiple levels of pattern matching
 def switchtest(x :: Foo) :: Int:
     switch x:
@@ -56,6 +59,46 @@
             x = a
     return add(x, a)
 
+# Test trivial (unconditional) binding of a variable
+# Although the test suite won't test for this, it should be compiled to code
+# without a switch, because there is no actual condition.
+def trivialbind(x :: Int) :: Int:
+    switch x:
+        case n:
+            return n
+
+# Test simple binding of a variable
+def simplebind(x :: Int) :: Int:
+    switch x:
+        case 1:
+            return 2
+        case n:
+            return n
+
+# Test binding of a variable on multiple paths
+# Fully-worked example in doc/dev/switchfactor.
+def trickybind(x :: Pair(Int, Box(Int))) :: Int:
+    switch x:
+        case Pair(49, Box(3)):
+            return -1
+        case Pair(m, Box(n)):
+            return add(m, n)
+
+# From fully-worked example in doc/dev/switchfactor.
+# Test that factoring doesn't break the precedence of the cases
+def factor(x :: Pair(Bar, Int)) :: Int:
+    switch x:
+        case Pair(B, 1):
+            return 1
+        case Pair(C, 2):
+            return 2
+        case Pair(B, 3):
+            return 3
+        case Pair(q, _):
+            return 4
+        case Pair(B, 5):        # Redundant rule: Should never be chosen
+            return 5
+
 # Unit test for switchtest function
 def test_switch(_x :: Int) :: Int:
     begin_case("switch")
@@ -88,3 +131,69 @@
     assert_eq(scopes(B), 8, "scopes(B) != 8")
     end_case("switch (scopes)")
     return 0
+
+def test_trivialbind(_x :: Int) :: Int:
+    begin_case("switch (trivialbind)")
+    assert_eq(trivialbind(7), 7, "trivialbind(7) != 7")
+    end_case("switch (trivialbind)")
+    return 0
+
+def test_simplebind(_x :: Int) :: Int:
+    begin_case("switch (simplebind)")
+    assert_eq(simplebind(1), 2, "simplebind(1) != 2")
+    end_case("switch (simplebind)")
+
+    begin_case("switch (simplebind)")
+    assert_eq(simplebind(7), 7, "simplebind(7) != 7")
+    end_case("switch (simplebind)")
+    return 0
+
+def test_trickybind(_x :: Int) :: Int:
+    begin_case("switch (trickybind)")
+    assert_eq(trickybind(Pair(49, Box(3))), -1, "trickybind(Pair(49, Box(3))) != -1")
+    end_case("switch (trickybind)")
+
+    begin_case("switch (trickybind)")
+    assert_eq(trickybind(Pair(49, Box(2))), 51, "trickybind(Pair(49, Box(2))) != 51")
+    end_case("switch (trickybind)")
+
+    begin_case("switch (trickybind)")
+    assert_eq(trickybind(Pair(7, Box(3))), 10, "trickybind(Pair(7, Box(3))) != 10")
+    end_case("switch (trickybind)")
+
+    begin_case("switch (trickybind)")
+    assert_eq(trickybind(Pair(2, Box(2))), 4, "trickybind(Pair(2, Box(2))) != 4")
+    end_case("switch (trickybind)")
+    return 0
+
+def test_factor() :: Int:
+    begin_case("switch (factoring)")
+    assert_eq(factor(Pair(B, 1)), 1, "factor(Pair(B, 1)) != 1")
+    end_case("switch (factoring)")
+    begin_case("switch (factoring)")
+    assert_eq(factor(Pair(B, 2)), 4, "factor(Pair(B, 2)) != 4")
+    end_case("switch (factoring)")
+    begin_case("switch (factoring)")
+    assert_eq(factor(Pair(B, 3)), 3, "factor(Pair(B, 3)) != 3")
+    end_case("switch (factoring)")
+    begin_case("switch (factoring)")
+    assert_eq(factor(Pair(B, 4)), 4, "factor(Pair(B, 4)) != 4")
+    end_case("switch (factoring)")
+    # Try to trick compiler -- should pick default case, not B,5 case
+    begin_case("switch (factoring)")
+    assert_eq(factor(Pair(B, 5)), 4, "factor(Pair(B, 5)) != 4")
+    end_case("switch (factoring)")
+
+    begin_case("switch (factoring)")
+    assert_eq(factor(Pair(C, 2)), 2, "factor(Pair(C, 2)) != 2")
+    end_case("switch (factoring)")
+    begin_case("switch (factoring)")
+    assert_eq(factor(Pair(C, 3)), 4, "factor(Pair(C, 3)) != 4")
+    end_case("switch (factoring)")
+
+    # Make sure default case also works when initial constructor has no
+    # possible match
+    begin_case("switch (factoring)")
+    assert_eq(factor(Pair(A(7), 2)), 4, "factor(Pair(A(7), 2)) != 4")
+    end_case("switch (factoring)")
+    return 0

=== modified file 'test/cases/compiler/switchfail.mar'
--- test/cases/compiler/switchfail.mar	2010-01-08 01:36:52 +0000
+++ test/cases/compiler/switchfail.mar	2010-01-25 07:28:13 +0000
@@ -1,7 +1,5 @@
 # Test failing switch statements (which do not cover all cases)
 
-import unittest
-
 type Foo:
     X(a :: Bar)
     Y(x :: Int)

=== modified file 'test/cases/compiler/switchfail.mtc'
--- test/cases/compiler/switchfail.mtc	2010-01-08 01:36:52 +0000
+++ test/cases/compiler/switchfail.mtc	2010-01-25 07:28:13 +0000
@@ -1,9 +1,5 @@
 # vim: filetype=yaml
-
-# Runtime tests
-# Note: Not including unit tests; this just tests some runtime errors
-
-run:
-    - call: matchfail(X(C))
-      stderr: |
-        Runtime Error: Pattern match failure
+compile:
+    outcome: compile_error
+    errors: |
+        switchfail.mar:15: (matchfail) Incomplete switch: requires case(s) for C.

=== added file 'test/cases/compiler/switchfail2.mar'
--- test/cases/compiler/switchfail2.mar	1970-01-01 00:00:00 +0000
+++ test/cases/compiler/switchfail2.mar	2010-01-25 07:28:13 +0000
@@ -0,0 +1,13 @@
+# Test failing switch statements (which do not cover all cases)
+
+type Foo:
+    A(x :: Int)
+    B(x :: Int)
+    C
+
+# Test failing cases with multiple levels of pattern matching
+def matchfail(x :: Foo) :: Int:
+    switch x:
+        # Matches A, but not B or C
+        case A(i):
+            return i

=== added file 'test/cases/compiler/switchfail2.mtc'
--- test/cases/compiler/switchfail2.mtc	1970-01-01 00:00:00 +0000
+++ test/cases/compiler/switchfail2.mtc	2010-01-25 07:28:13 +0000
@@ -0,0 +1,5 @@
+# vim: filetype=yaml
+compile:
+    outcome: compile_error
+    errors: |
+        switchfail2.mar:10: (matchfail) Incomplete switch: requires case(s) for B, C.

=== added file 'test/cases/compiler/switchfail3.mar'
--- test/cases/compiler/switchfail3.mar	1970-01-01 00:00:00 +0000
+++ test/cases/compiler/switchfail3.mar	2010-01-25 07:28:13 +0000
@@ -0,0 +1,10 @@
+# Test failing switch statements (which do not cover all cases)
+
+# Test failing cases with multiple levels of pattern matching
+def matchfail(x :: Int) :: Int:
+    switch x:
+        # Matches some integer values, but has no default case
+        case 0:
+            return 1
+        case 13:
+            return x

=== added file 'test/cases/compiler/switchfail3.mtc'
--- test/cases/compiler/switchfail3.mtc	1970-01-01 00:00:00 +0000
+++ test/cases/compiler/switchfail3.mtc	2010-01-25 07:28:14 +0000
@@ -0,0 +1,5 @@
+# vim: filetype=yaml
+compile:
+    outcome: compile_error
+    errors: |
+        switchfail3.mar:5: (matchfail) Incomplete switch: requires default case for switch on integer.