doc/guide/src/Restore.adoc

   1 Restore
   2 =======
   3
   4 <:Restore:> is a rewrite pass for the <:SSA:> and <:SSA2:>
   5 <:IntermediateLanguage:>s, invoked from <:KnownCase:> and
   6 <:LocalRef:>.
   7
   8 == Description ==
   9
  10 This pass restores the SSA condition for a violating <:SSA:> or
  11 <:SSA2:> program; the program must satisfy:
  12 ____
  13 Every path from the root to a use of a variable (excluding globals)
  14 passes through a def of that variable.
  15 ____
  16
  17 == Implementation ==
  18
  19 * <!ViewGitFile(mlton,master,mlton/ssa/restore.sig)>
  20 * <!ViewGitFile(mlton,master,mlton/ssa/restore.fun)>
  21 * <!ViewGitFile(mlton,master,mlton/ssa/restore2.sig)>
  22 * <!ViewGitFile(mlton,master,mlton/ssa/restore2.fun)>
  23
  24 == Details and Notes ==
  25
  26 Based primarily on Section 19.1 of <!Cite(Appel98, Modern Compiler
  27 Implementation in ML)>.
  28
  29 The main deviation is the calculation of liveness of the violating
  30 variables, which is used to predicate the insertion of phi arguments.
  31 This is due to the algorithm's bias towards imperative languages, for
  32 which it makes the assumption that all variables are defined in the
  33 start block and all variables are "used" at exit.
  34
  35 This is "optimized" for restoration of functions with small numbers of
  36 violating variables -- use bool vectors to represent sets of violating
  37 variables.
  38
  39 Also, we use a `Promise.t` to suspend part of the dominance frontier
  40 computation.