src/ERTL/build.ml

   1 (* Pasted from Pottier's PP compiler *)
   2
   3 open ERTL
   4 open Interference
   5
   6 let build (int_fun : internal_function) =
   7
   8   (* Perform liveness analysis. *)
   9
  10   let liveafter = Liveness.analyze int_fun in
  11
  12   (* Create an interference graph whose vertices are the procedure's
  13      pseudo-registers. This graph initially has no edges. *)
  14
  15   let graph = create int_fun.f_locals in
  16
  17   (* Every pseudo register interferes with special forbidden registers. *)
  18
  19   let graph = mkiph graph int_fun.f_locals I8051.forbidden in
  20
  21   (* Iterate over all statements in the control flow graph and populate the
  22      interference graph with interference and preference edges. *)
  23
  24   let graph =
  25     Label.Map.fold (fun label stmt graph ->
  26       let live = liveafter label in
  27       match Liveness.eliminable live stmt with
  28
  29       | Some _ ->
  30
  31           (* This statement is eliminable and should be ignored. Eliminable
  32              statements have not been eliminated yet, because we are still
  33              in between ERTL and LTL. They *will* be eliminated soon, though,
  34              so there is no reason to take them into account while building
  35              the interference graph. *)
  36
  37           graph
  38
  39       | None ->
  40
  41           (* Create interference edges. The general rule is, every
  42              pseudo-register or hardware register that is defined (written) by
  43              a statement interferes with every pseudo-register or hardware
  44              register (other than itself) that is live immediately after the
  45              statement executes.
  46
  47              An exception to the general rule can be made for move
  48              statements. In a move statement, we do not need the source
  49              and destination pseudo-registers to be assigned distinct hardware
  50              registers, since they contain the same value -- in fact, we would
  51              like them to be assigned the same hardware register. So, for a
  52              move statement, we let the register that is defined (written)
  53              interfere with every pseudo-register, other than itself *and
  54              other than the source pseudo-register*, that is live immediately
  55              after the statement executes. This optimization is explained in
  56              Chapter 10 of Appel's book (p. 221).
  57
  58              This special case is only a hack that works in many cases. There
  59              are cases where it doesn't suffice. For instance, if two
  60              successive move statements have the same source [r0], then
  61              their destinations [r1] and [r2] *will* be considered as
  62              interfering, even though it would in fact be correct and
  63              desirable to map both of them to the same hardware register. A
  64              more general solution would be to perform a static analysis that
  65              determines, for every program point, which pseudo-registers
  66              definitely hold the same value, and to exploit this information
  67              to build fewer interference edges. *)
  68
  69           let defined = Liveness.defined stmt in
  70           let exceptions =
  71             match stmt with
  72             | St_move (_, sourcer, _)
  73             | St_set_hdw (_, sourcer, _) ->
  74                  Liveness.L.psingleton sourcer
  75             | St_get_hdw (_, sourcehwr, _) ->
  76                  Liveness.L.hsingleton sourcehwr
  77             | _ ->
  78                 Liveness.L.bottom
  79           in
  80           let graph =
  81             mki graph (Liveness.L.diff live exceptions) defined
  82           in
  83
  84 (*
  85           (* Two registers written at the same time are interfering (they
  86              obviously should not be associated the same address).
  87              Only happens with St_addr. *)
  88
  89           let graph =
  90             match stmt with
  91               | St_addr (r1, r2, _, _) ->
  92                 mki graph (Liveness.L.psingleton r1) (Liveness.L.psingleton r2)
  93               | _ ->
  94                 graph
  95           in
  96 *)
  97
  98           (* Create preference edges between pseudo-registers. Two registers
  99              should preferably be assigned the same color when they are
 100              related by a move statement, so that the move statement can
 101              be eliminated. *)
 102
 103           let graph =
 104             match stmt with
 105             | St_move (r1, r2, _) ->
 106                 mkppp graph r1 r2
 107             | St_get_hdw (r, hwr, _)
 108             | St_set_hdw (hwr, r, _) ->
 109                 mkpph graph r hwr
 110             | _ ->
 111                 graph
 112           in
 113   (*
 114
 115           (* Add interference edges between the hardware register [$zero]
 116              and every pseudo-register that the statement renders
 117              nonzeroable. See [Zero] for an explanation. *)
 118
 119           let graph =
 120             mkiph graph (Zero.nonzeroable i) (MIPS.RegisterSet.singleton MIPS.zero)
 121           in
 122   *)
 123           graph
 124
 125     ) int_fun.f_graph graph
 126   in
 127
 128   (* Done. *)
 129
 130   liveafter, graph
 131