Compilerbauhome Compilerbau & Formale Sprachen: Sprung- und Peephole-Optimierung Prof. Dr. Uwe Schmidt FH Wedel
Der ppl-Compiler
Optimierung von Endrekursion und FunktionsaufrufenInhaltsverzeichnisAssemblieren

Sprung- und Peephole-Optimierung

weiter

Peephole- und Sprungoptimierung

Peephole- Optimierung
 In einer Zielmaschine gibt es häufig Spezialinstruktionen, die vom Codegenerator unberücksichtigt bleiben. Diese können in der Peephole-Optimierung ausgenutzt werden. Hier werden bestimmte Folgen von Instruktionen in kürzere oder schnellere Instruktionen transformiert.
 
 Die ppl-VM besitzt drei Instruktionen, die nicht vom Codegenerator erzeugt werden:
dup
 zum Verdoppeln des obersten Wertes auf dem Auswerte-Keller
incr
 eine einstellige Operation zum Inkrementieren des obersten Wertes auf dem Keller
decr
 analog zu incr zum Dekrementieren
weiter
store / load Optimierung
 Damit können folgende lokale Verbesserungen gemacht werden
Codemuster
        store <addr>
        load  <addr>
optimiert
        dup
        store <addr>
 
 Dieses spart einen Hauptspeicherzugriff.
incr / decr Optimierung
 Das Inkrementieren und Dekrementieren von Variable kann vereinfacht werden:
Codemuster
        loadi 1      loadi 1
        addi         subi
optimiert
        incri        decri
 
 Einfache Sprünge können eliminiert werden:
 
        jmp l1
l1:
 
 kann ersatzlos gestrichen werden.
 
 Außerdem kann alles hinter einem unbedingten Sprung bis zur nächsten Marke gelöscht werden.
Codemuster
        jmp l1
        <instr1>
        ...
        <instrN>
l2:
optimiert
        jmp l1
l2:
weiter
Sprung- Instruktionen
 Durch die strukturierten Anweisungen und deren unabhängiger Übersetzung können Sprungketten entstehen. Die Sprungziele können so verändert werden, dass die Ziele direkt angesprungen werden.
Codemuster
        br...  l1
        ...
l1:
        jmp l2
        ...
l2:
optimiert
        br...  l2
        ...
l1:
        jmp l2
        ...
l2:
 
 Diese Optimierung führt nur in wenigen Fällen zu Verkürzung des Codes, verbessert aber die Laufzeit.
weiter
weiter

Sprünge: die Quelle ppl/examples/jump.ppl

   1begin
   2  var i,j : int := 1,2
   3  ;
   4  if i = 1 or j = 2
   5  then
   6    while i /= 0 do
   7      i := i-1
   8    endwhile
   9  endif
  10  ;
  11  while i > 1 do
  12    while j > i do
  13      j := j - 1
  14    endwhile
  15    ;
  16    i := i - 1
  17  endwhile
  18  ;
  19  if 1 /= 0
  20  then
  21    i := i + 1
  22  endif
  23  ;
  24  if 1 = 0
  25  then
  26    i := i - 1
  27  endif
  28end
weiter
weiter

Sprünge: der nicht optimierte Assemblercode ppl/examples/jump.gencode

   1.text
   2        loadi   1
   3        loadi   2
   4        store   m[1]
   5        store   m[0]
   6        load    m[0]
   7        loadi   1
   8        eqi
   9        brtrue  l2
  10        load    m[1]
  11        loadi   2
  12        eqi
  13        brfalse l0
  14l2:
  15        jmp     l3
  16l4:
  17        load    m[0]
  18        loadi   1
  19        subi
  20        store   m[0]
  21l3:
  22        load    m[0]
  23        loadi   0
  24        eqi
  25        brfalse l4
  26l0:
  27        jmp     l5
  28l6:
  29        jmp     l7
  30l8:
  31        load    m[1]
  32        loadi   1
  33        subi
  34        store   m[1]
  35l7:
  36        load    m[1]
  37        load    m[0]
  38        gti
  39        brtrue  l8
  40        load    m[0]
  41        loadi   1
  42        subi
  43        store   m[0]
  44l5:
  45        load    m[0]
  46        loadi   1
  47        gti
  48        brtrue  l6
  49        loadi   1
  50        loadi   0
  51        eqi
  52        brtrue  l9
  53        load    m[0]
  54        loadi   1
  55        addi
  56        store   m[0]
  57l9:
  58        loadi   1
  59        loadi   0
  60        eqi
  61        brfalse l11
  62        load    m[0]
  63        loadi   1
  64        subi
  65        store   m[0]
  66l11:
  67        undef
  68        store   m[0]
  69        undef
  70        store   m[1]
  71        terminate
  72
  73.data   2
weiter
weiter

Sprünge: der optimierte Assemblercode ppl/examples/jump.optcode

   1.text
   2        loadi   1
   3        loadi   2
   4        store   m[1]
   5        dup
   6        store   m[0]
   7        loadi   1
   8        eqi
   9        brtrue  l3
  10        load    m[1]
  11        loadi   2
  12        eqi
  13        brfalse l5
  14        jmp     l3
  15l4:
  16        load    m[0]
  17        decri
  18        store   m[0]
  19l3:
  20        load    m[0]
  21        loadi   0
  22        eqi
  23        brfalse l4
  24        jmp     l5
  25l8:
  26        load    m[1]
  27        decri
  28        store   m[1]
  29l7:
  30        load    m[1]
  31        load    m[0]
  32        gti
  33        brtrue  l8
  34        load    m[0]
  35        decri
  36        store   m[0]
  37l5:
  38        load    m[0]
  39        loadi   1
  40        gti
  41        brtrue  l7
  42        loadi   1
  43        loadi   0
  44        eqi
  45        brtrue  l9
  46        load    m[0]
  47        incri
  48        store   m[0]
  49l9:
  50        loadi   1
  51        loadi   0
  52        eqi
  53        brfalse l11
  54        load    m[0]
  55        decri
  56        store   m[0]
  57l11:
  58        undef
  59        store   m[0]
  60        undef
  61        store   m[1]
  62        terminate
  63
  64.data   2
weiter
weiter

Sprünge: die Instruktionen im Vergleich ppl/examples/jump.diffcode

   1.text                               .text
   2        loadi   1                           loadi   1
   3        loadi   2                           loadi   2
   4        store   m[1]                        store   m[1]
   5                                 >          dup
   6        store   m[0]                        store   m[0]
   7        load    m[0]             <
   8        loadi   1                           loadi   1
   9        eqi                                 eqi
  10        brtrue  l2               |          brtrue  l3
  11        load    m[1]                        load    m[1]
  12        loadi   2                           loadi   2
  13        eqi                                 eqi
  14        brfalse l0               |          brfalse l5
  15l2:                              <
  16        jmp     l3                          jmp     l3
  17l4:                                 l4:
  18        load    m[0]                        load    m[0]
  19        loadi   1                |          decri
  20        subi                     <
  21        store   m[0]                        store   m[0]
  22l3:                                 l3:
  23        load    m[0]                        load    m[0]
  24        loadi   0                           loadi   0
  25        eqi                                 eqi
  26        brfalse l4                          brfalse l4
  27l0:                              <
  28        jmp     l5                          jmp     l5
  29l6:                              <
  30        jmp     l7               <
  31l8:                                 l8:
  32        load    m[1]                        load    m[1]
  33        loadi   1                |          decri
  34        subi                     <
  35        store   m[1]                        store   m[1]
  36l7:                                 l7:
  37        load    m[1]                        load    m[1]
  38        load    m[0]                        load    m[0]
  39        gti                                 gti
  40        brtrue  l8                          brtrue  l8
  41        load    m[0]                        load    m[0]
  42        loadi   1                |          decri
  43        subi                     <
  44        store   m[0]                        store   m[0]
  45l5:                                 l5:
  46        load    m[0]                        load    m[0]
  47        loadi   1                           loadi   1
  48        gti                                 gti
  49        brtrue  l6               |          brtrue  l7
  50        loadi   1                           loadi   1
  51        loadi   0                           loadi   0
  52        eqi                                 eqi
  53        brtrue  l9                          brtrue  l9
  54        load    m[0]                        load    m[0]
  55        loadi   1                |          incri
  56        addi                     <
  57        store   m[0]                        store   m[0]
  58l9:                                 l9:
  59        loadi   1                           loadi   1
  60        loadi   0                           loadi   0
  61        eqi                                 eqi
  62        brfalse l11                         brfalse l11
  63        load    m[0]                        load    m[0]
  64        loadi   1                |          decri
  65        subi                     <
  66        store   m[0]                        store   m[0]
  67l11:                                l11:
  68        undef                               undef
  69        store   m[0]                        store   m[0]
  70        undef                               undef
  71        store   m[1]                        store   m[1]
  72        terminate                           terminate
  73
  74.data   2                           .data   2
weiter
weiter

Das Optimieren ppl/src/PPL/OptimizeInstr.hs

   1-- $Id: OptimizeInstr.hs,v 1.4 2006/01/24 21:37:07 uwe Exp $
   2
   3module PPL.OptimizeInstr
   4    ( optimizeInstr
   5    )
   6where
   7
   8import PPL.Instructions
   9
  10import Data.Maybe
  11
  12type LabSubst   = [(Label, Label)]
  13
  14optimizeInstr   :: Executable -> Executable
  15optimizeInstr (is, ds)
  16    = ((peephole . removeUnusedLabels . jumpChaining . optimizeTailRecursion) is, ds)
  17
  18jumpChaining    :: Code -> Code
  19jumpChaining is
  20    = let
  21      labTab    = buildLabSubst [] is
  22      is'       = renameLabels labTab is
  23      in
  24      is'
  25
  26buildLabSubst   :: LabSubst -> Code -> LabSubst
  27
  28-- real jump chaining
  29buildLabSubst lt (  (Label l1)
  30                  : (Jump (Symb l2))
  31                  : is2)
  32    = buildLabSubst lt1 is2
  33      where
  34      lt1 = insLabSubst l1 l2 lt
  35
  36-- labels with equal values are collapsed
  37buildLabSubst lt (        (Label l1)
  38                   : is1@((Label l2)
  39                          : _))
  40    = buildLabSubst lt1 is1
  41      where
  42      lt1 = insLabSubst l1 l2 lt
  43
  44-- default rules
  45buildLabSubst lt (_:is1)
  46    = buildLabSubst lt is1
  47
  48buildLabSubst lt []
  49    = lt
  50
  51
  52-- --------------------
  53
  54insLabSubst     :: Label -> Label -> LabSubst -> LabSubst
  55insLabSubst l1 l2 lt
  56    = if (l2,l1) `elem` lt || l1 == l2
  57      then lt
  58      else (l1, l2) : lt'
  59           where
  60           lt'  = map renameWith lt
  61           renameWith (l1',l2')
  62               | l2' == l1
  63                   = (l1', l2)
  64           renameWith p
  65               = p
  66
  67newLabName      :: LabSubst -> Label -> Label
  68newLabName lt l
  69    = case lookup l lt of
  70      Just l1 -> l1
  71      Nothing -> l
  72
  73renameLabels    :: LabSubst -> Code -> Code
  74
  75-- remove alias labels
  76
  77renameLabels lt ((Label l1) : is1)
  78    | isJust (lookup l1 lt)
  79        =  renameLabels lt is1
  80
  81-- default
  82renameLabels lt (i1:is)
  83    = renameLab lt i1 : renameLabels lt is
  84
  85renameLabels _ []
  86    = []
  87
  88renameLab       :: LabSubst -> Instr -> Instr
  89
  90renameLab lt (Branch cond (Symb l1))
  91    = Branch cond (Symb (newLabName lt l1))
  92
  93renameLab lt (Jump (Symb l1))
  94    = Jump (Symb (newLabName lt l1))
  95
  96renameLab _lt i
  97    = i
  98
  99-- --------------------
 100
 101usedLabels      :: Code -> [Label]
 102usedLabels
 103    = concat . map lab
 104      where
 105      lab (Branch _ (Symb l))   = [l]
 106      lab (Jump     (Symb l))   = [l]
 107      lab _                     = []
 108
 109removeUnusedLabels      :: Code -> Code
 110removeUnusedLabels cs
 111    = filter usedLabel cs
 112      where
 113      used = usedLabels cs
 114
 115      usedLabel (Label l@(c:_))
 116          = c == '_'                    -- global label
 117            ||
 118            l `elem` used               -- label is referenced in jump or branch
 119      usedLabel _
 120          = True
 121
 122-- --------------------
 123
 124-- peephole optimizations
 125-- local instruction optimization
 126
 127peephole                :: Code -> Code
 128
 129-- remove instructions following unconditional jumps
 130
 131peephole (i1@(Jump _l1)
 132          : i2
 133          : is
 134         )
 135    | noLabel i2
 136      = peephole (i1:is)
 137
 138-- remove jump to following instruction
 139
 140peephole (Jump (Symb l1)
 141          : is2@(Label l2
 142                 : _
 143                )
 144         )
 145    | l1 == l2
 146        = peephole is2
 147
 148-- remove conditional branch to following instruction
 149
 150peephole (Branch _ (Symb l1)
 151          : is2@(Label l2
 152                 : _
 153                )
 154         )
 155    | l1 == l2
 156        = Pop
 157          : peephole is2
 158
 159-- conditional branches with constants
 160
 161peephole (LoadI val
 162          : Branch cond lab
 163          : is
 164         )
 165    | (val /= 0) == cond
 166        = peephole (Jump lab : is)
 167    | otherwise
 168        = peephole is
 169
 170-- optimize store load sequences
 171
 172peephole (Store a1
 173          : Load a2
 174          : is
 175         )
 176    | a1 == a2
 177        = Dup
 178          : peephole (Store a1 : is)
 179
 180-- optimize increment and decrement
 181
 182peephole (LoadI 1
 183          : Compute OPaddi
 184          : is
 185         )
 186    = Compute OPincri
 187      : peephole is
 188
 189peephole (LoadI 1
 190          : Compute OPsubi
 191          : is
 192         )
 193    = Compute OPdecri
 194      : peephole is
 195
 196peephole (Pop
 197          : LoadU
 198          : is
 199         )
 200    = peephole is
 201
 202-- next step
 203
 204peephole (i1:is1)
 205    = i1 : peephole is1
 206
 207peephole []
 208    = []
 209
 210-- --------------------
 211
 212noLabel                 :: Instr -> Bool
 213
 214noLabel (Label _)       = False
 215noLabel _               = True
 216
 217-- --------------------
 218
 219optimizeCalls           :: LabSubst -> Code -> Code
 220optimizeCalls lt cs@( Label sl
 221                      : Entry _
 222                      : Store _
 223                      : Label sl1
 224                      : cs4
 225                    )
 226    = take 4 cs
 227      ++
 228      optimize1Fct cs4
 229      where
 230      el1 = 'e' : sl
 231      el = newLabName lt el1
 232
 233      optimize1Fct cs'@( Exit           -- function exit detected
 234                         : PopJ         -- optimize rest
 235                         : rest'
 236                       )
 237          = take 2 cs'
 238            ++
 239            optimizeCalls lt rest'
 240
 241      optimize1Fct ( PushJ fct@(Symb target)
 242                     : Jump (Symb l1)
 243                     : rest
 244                   )
 245                                        -- pure tail recursion detected
 246                                        -- subroutine call substituted
 247                                        -- by a jump to routine start
 248          | target == sl && newLabName lt l1 == el
 249              = Jump (Symb sl1)
 250                : optimize1Fct rest
 251                                        -- tail recursion to another function
 252                                        -- load return address
 253                                        -- remove stack frame
 254                                        -- and jump
 255          | newLabName lt l1 == el
 256              = Load (LocA 0)
 257                : Exit
 258                : Jump fct
 259                : optimize1Fct rest
 260
 261                                        -- same as above for calls
 262                                        -- directly in front of exit code
 263      optimize1Fct ( PushJ fct@(Symb target)
 264                     : cs1@( Label l1
 265                             : _rest
 266                           )
 267                   )
 268          | target == sl && newLabName lt l1 == el
 269              = Jump (Symb sl1)
 270                : optimize1Fct cs1
 271                
 272          | newLabName lt l1 == el
 273              = Load (LocA 0)
 274                : Exit
 275                : Jump fct
 276                : optimize1Fct cs1
 277
 278                                        -- continue search for calls
 279      optimize1Fct (c : cs1)
 280          = c : optimize1Fct cs1
 281
 282      optimize1Fct []
 283          = []
 284
 285optimizeCalls lt (c1 : cs1)
 286    = c1 : optimizeCalls lt cs1
 287
 288optimizeCalls _ []
 289    = []
 290
 291-- optimize tail recursion
 292-- 1. step: collect all function entry end exit points
 293-- 2. step: look for function calls
 294
 295optimizeTailRecursion   :: Code -> Code
 296optimizeTailRecursion cs
 297    = optimizeCalls labTab cs
 298      where
 299      labTab = buildLabSubst [] cs
 300
 301-- --------------------
weiter
SeitenanfangDer ppl-Compiler
Optimierung von Endrekursion und FunktionsaufrufenInhaltsverzeichnisAssemblieren
Letzte Änderung: 14.02.2012
© Prof. Dr. Uwe Schmidt
Prof. Dr. Uwe Schmidt FH Wedel