doc/guide/src/XMLShrink.adoc

   1 XMLShrink
   2 =========
   3
   4 XMLShrink is an optimization pass for the <:XML:>
   5 <:IntermediateLanguage:>, invoked from <:XMLSimplify:>.
   6
   7 == Description ==
   8
   9 This pass performs optimizations based on a reduction system.
  10
  11 == Implementation ==
  12
  13 * <!ViewGitFile(mlton,master,mlton/xml/shrink.sig)>
  14 * <!ViewGitFile(mlton,master,mlton/xml/shrink.fun)>
  15
  16 == Details and Notes ==
  17
  18 The simplifier is based on <!Cite(AppelJim97, Shrinking Lambda
  19 Expressions in Linear Time)>.
  20
  21 The source program may contain functions that are only called once, or
  22 not even called at all.  Match compilation introduces many such
  23 functions.  In order to reduce the program size, speed up later
  24 phases, and improve the flow analysis, a source to source simplifier
  25 is run on <:XML:> after type inference and match compilation.
  26
  27 The simplifier implements the reductions shown below.  The reductions
  28 eliminate unnecessary declarations (see the side constraint in the
  29 figure), applications where the function is immediate, and case
  30 statements where the test is immediate.  Declarations can be
  31 eliminated only when the expression is nonexpansive (see Section 4.7
  32 of the <:DefinitionOfStandardML: Definition>), which is a syntactic
  33 condition that ensures that the expression has no effects
  34 (assignments, raises, or nontermination).  The reductions on case
  35 statements do not show the other irrelevant cases that may exist.  The
  36 reductions were chosen so that they were strongly normalizing and so
  37 that they never increased tree size.
  38
  39 * {empty}
  40 +
  41 --
  42 [source,sml]
  43 ----
  44 let x = e1 in e2
  45 ----
  46
  47 reduces to
  48
  49 [source,sml]
  50 ----
  51 e2 [x -> e1]
  52 ----
  53
  54 if `e1` is a constant or variable or if `e1` is nonexpansive and `x` occurs zero or one time in `e2`
  55 --
  56
  57 * {empty}
  58 +
  59 --
  60 [source,sml]
  61 ----
  62 (fn x => e1) e2
  63 ----
  64
  65 reduces to
  66
  67 [source,sml]
  68 ----
  69 let x = e2 in e1
  70 ----
  71 --
  72
  73 * {empty}
  74 +
  75 --
  76 [source,sml]
  77 ----
  78 e1 handle e2
  79 ----
  80
  81 reduces to
  82
  83 [source,sml]
  84 ----
  85 e1
  86 ----
  87
  88 if `e1` is nonexpansive
  89 --
  90
  91 * {empty}
  92 +
  93 --
  94 [source,sml]
  95 ----
  96 case let d in e end of p1 => e1 ...
  97 ----
  98
  99 reduces to
 100
 101 [source,sml]
 102 ----
 103 let d in case e of p1 => e1 ... end
 104 ----
 105 --
 106
 107 * {empty}
 108 +
 109 --
 110 [source,sml]
 111 ----
 112 case C e1 of C x => e2
 113 ----
 114
 115 reduces to
 116
 117 [source,sml]
 118 ----
 119 let x = e1 in e2
 120 ----
 121 --