Compilerbauhome Compilerbau: 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

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