Compilerbauhome Compilerbau: Optimierung von Endrekursion und Funktionsaufrufen Prof. Dr. Uwe Schmidt FH Wedel
Der ppl-Compiler
CodeerzeugungInhaltsverzeichnisSprung- und Peephole-Optimierung

Optimierung von Endrekursion und Funktionsaufrufen

weiter

Optimierung von Rekursionen

Endrekursion und einfache Rekursion
Bei der Programmierung in einem funktionalen Stil werden Wiederholungen mit Hilfe von rekursiven Aufrufen einer Funktion realisiert. Dabei tritt häufig der Fall auf, das aus der Funktion, die gerade ausgeführt wird, die Funktion selbst oder eine andere aufgerufen wird.
 
Ist dieser Aufruf die letzte Berechnung innerhalb der Funktion (oder Prozedur), so kann der Aufruf bei einer direkten Rekursion zu einem Sprung an den Anfang des Prozedurrumpfes optimiert werden. Dieses bringt zwei Vorteile: Es wird für den Aufruf kein Kellerrahmen (stack-frame) angelegt und somit auch nicht wieder freigegen, spart also Laufzeit. Außerdem wird der momentane Kellerrahmen als "neuer" Rahmen genutzt, so dass kein zusätzlicher Speicher für den Aufruf verbraucht wird. Solche Rekursion kann also in eine Schleife, oder genauer in einen unbedingten Sprung, transformiert werden.
 
Wird als letztes eine andere Funktion aufgerufen, so kann ebenfalls optimiert werden: Die Argumente liegen vor Ausführung des Unterprogrammsprungs schon auf dem Auswertekeller, es wird aus dem momentanen Kellerrahmen nur noch die Rückkehradresse benötigt. Wird diese ebenfalls auf den Auswertekeller geschrieben, so kann der gesamte Rahmen abgebaut werden und ein unbedingter Sprung auf die zu rufende Funktion ausgeführt werden. Hierdurch wird also keine Laufzeit gespart, wohl aber Speicherplatz im Laufzeit-Keller.
weiter
reine Endrekursion
Das Optimierungs-Schema für die reine Endrekursion:
 
_ggt:
        entry   ...
        store   <return-addr>
s_ggt:
        store   <form-param2>
        store   <form-param1>
        ...
        load    <act-param1>
        load    <act-param2>
        pushj   _ggt        <-- letzte Berechnung
e_ggt:
        load    <return-addr>
        exit
        popj
 
_ggt:
        entry   ...
        store   <return-addr>
s_ggt:
        store   <form-param2>
        store   <form-param1>
        ...
        load    <act-param1>
        load    <act-param2>
        jmp     s_ggt        <-- letzte Berechnung
e_ggt:
        load    <return-addr>
        exit
        popj
 
Dieses spart Laufzeit und Speicherplatz
weiter
Funktionsaufruf als letzte Berechnung
Das Optimierungs-Schema für den Aufruf einer anderen Funktion:
 
_f:
        ...
        load    <act-param1>
        ...
        load    <act-paramN>
        pushj   _g
        jmp     e_f
        ...
e_f:
        load    <return-addr>
        exit
        popj
 
_f:
        ...
        load    <act-param1>
        ...
        load    <act-paramN>
        load    <return-addr>
        exit
        jmp        _g
        jmp     e_f
        ...
e_f:
        load    <return-addr>
        exit
        popj
 
Hierdurch wird Speicherplatz auf dem Laufzeitkeller eingespart.
Durch diese Optimierung kann toter Code entstehen. Dieser wird bei der Peephole-Optimierung eliminiert.
weiter
weiter

Aufrufe: die Quelle: ppl/examples/tailRecursion.ppl

   1function ggt(x,y : int) : int
   2  if x = y
   3  then x
   4  else if x > y
   5  then ggt(x - y, y)
   6  else tgg(x, y)
   7;
   8
   9function tgg(x,y : int) : int
  10  ggt(y, x)
  11;
  12
  13function f(x : int) :int
  14  if x >= 0
  15  then
  16    g(x)
  17  else
  18    f(x + 1)
  19;
  20
  21function g(x : int) : int
  22  if x >= 0
  23  then
  24    g(x - 1)
  25  else
  26    f(x)
  27;
  28 
  29begin
  30 var i : int;
  31 i := ggt(13, 8)
  32end
weiter
weiter

Aufrufe: der nicht optimierte Assemblercode ppl/examples/tailRecursion.gencode

   1.text
   2        loadi   13
   3        loadi   8
   4        pushj   _ggt
   5        store   m[0]
   6        undef
   7        store   m[0]
   8        terminate
   9_ggt:
  10        entry   3
  11        store   l[0]
  12s_ggt:
  13        store   l[1]
  14        store   l[2]
  15        load    l[2]
  16        load    l[1]
  17        eqi
  18        brfalse l0
  19        load    l[2]
  20        jmp     l1
  21l0:
  22        load    l[2]
  23        load    l[1]
  24        gti
  25        brfalse l2
  26        load    l[2]
  27        load    l[1]
  28        subi
  29        load    l[1]
  30        pushj   _ggt
  31        jmp     l3
  32l2:
  33        load    l[2]
  34        load    l[1]
  35        pushj   _tgg
  36l3:
  37l1:
  38e_ggt:
  39        load    l[0]
  40        exit
  41        popj
  42_tgg:
  43        entry   3
  44        store   l[0]
  45s_tgg:
  46        store   l[1]
  47        store   l[2]
  48        load    l[1]
  49        load    l[2]
  50        pushj   _ggt
  51e_tgg:
  52        load    l[0]
  53        exit
  54        popj
  55_f:
  56        entry   2
  57        store   l[0]
  58s_f:
  59        store   l[1]
  60        load    l[1]
  61        loadi   0
  62        gei
  63        brfalse l4
  64        load    l[1]
  65        pushj   _g
  66        jmp     l5
  67l4:
  68        load    l[1]
  69        loadi   1
  70        addi
  71        pushj   _f
  72l5:
  73e_f:
  74        load    l[0]
  75        exit
  76        popj
  77_g:
  78        entry   2
  79        store   l[0]
  80s_g:
  81        store   l[1]
  82        load    l[1]
  83        loadi   0
  84        gei
  85        brfalse l6
  86        load    l[1]
  87        loadi   1
  88        subi
  89        pushj   _g
  90        jmp     l7
  91l6:
  92        load    l[1]
  93        pushj   _f
  94l7:
  95e_g:
  96        load    l[0]
  97        exit
  98        popj
  99
 100.data   1
weiter
weiter

Aufrufe: der optimierte Assemblercode ppl/examples/tailRecursion.optcode

   1.text
   2        loadi   13
   3        loadi   8
   4        pushj   _ggt
   5        store   m[0]
   6        undef
   7        store   m[0]
   8        terminate
   9_ggt:
  10        entry   3
  11        store   l[0]
  12s_ggt:
  13        store   l[1]
  14        dup
  15        store   l[2]
  16        load    l[1]
  17        eqi
  18        brfalse l0
  19        load    l[2]
  20        jmp     e_ggt
  21l0:
  22        load    l[2]
  23        load    l[1]
  24        gti
  25        brfalse l2
  26        load    l[2]
  27        load    l[1]
  28        subi
  29        load    l[1]
  30        jmp     s_ggt
  31l2:
  32        load    l[2]
  33        load    l[1]
  34        load    l[0]
  35        exit
  36        jmp     _tgg
  37e_ggt:
  38        load    l[0]
  39        exit
  40        popj
  41_tgg:
  42        entry   3
  43        store   l[0]
  44        store   l[1]
  45        store   l[2]
  46        load    l[1]
  47        load    l[2]
  48        load    l[0]
  49        exit
  50        jmp     _ggt
  51_f:
  52        entry   2
  53        store   l[0]
  54s_f:
  55        dup
  56        store   l[1]
  57        loadi   0
  58        gei
  59        brfalse l4
  60        load    l[1]
  61        load    l[0]
  62        exit
  63        jmp     _g
  64l4:
  65        load    l[1]
  66        incri
  67        jmp     s_f
  68_g:
  69        entry   2
  70        store   l[0]
  71s_g:
  72        dup
  73        store   l[1]
  74        loadi   0
  75        gei
  76        brfalse l6
  77        load    l[1]
  78        decri
  79        jmp     s_g
  80l6:
  81        load    l[1]
  82        load    l[0]
  83        exit
  84        jmp     _f
  85
  86.data   1
weiter
weiter

Aufrufe: die Instruktionen im Vergleich ppl/examples/tailRecursion.diffcode

   1.text                               .text
   2        loadi   13                          loadi   13
   3        loadi   8                           loadi   8
   4        pushj   _ggt                        pushj   _ggt
   5        store   m[0]                        store   m[0]
   6        undef                               undef
   7        store   m[0]                        store   m[0]
   8        terminate                           terminate
   9_ggt:                               _ggt:
  10        entry   3                           entry   3
  11        store   l[0]                        store   l[0]
  12s_ggt:                              s_ggt:
  13        store   l[1]                        store   l[1]
  14                                 >          dup
  15        store   l[2]                        store   l[2]
  16        load    l[2]             <
  17        load    l[1]                        load    l[1]
  18        eqi                                 eqi
  19        brfalse l0                          brfalse l0
  20        load    l[2]                        load    l[2]
  21        jmp     l1               |          jmp     e_ggt
  22l0:                                 l0:
  23        load    l[2]                        load    l[2]
  24        load    l[1]                        load    l[1]
  25        gti                                 gti
  26        brfalse l2                          brfalse l2
  27        load    l[2]                        load    l[2]
  28        load    l[1]                        load    l[1]
  29        subi                                subi
  30        load    l[1]                        load    l[1]
  31        pushj   _ggt             |          jmp     s_ggt
  32        jmp     l3               <
  33l2:                                 l2:
  34        load    l[2]                        load    l[2]
  35        load    l[1]                        load    l[1]
  36        pushj   _tgg             |          load    l[0]
  37l3:                              |          exit
  38l1:                              |          jmp     _tgg
  39e_ggt:                              e_ggt:
  40        load    l[0]                        load    l[0]
  41        exit                                exit
  42        popj                                popj
  43_tgg:                               _tgg:
  44        entry   3                           entry   3
  45        store   l[0]                        store   l[0]
  46s_tgg:                           <
  47        store   l[1]                        store   l[1]
  48        store   l[2]                        store   l[2]
  49        load    l[1]                        load    l[1]
  50        load    l[2]                        load    l[2]
  51        pushj   _ggt             <
  52e_tgg:                           <
  53        load    l[0]                        load    l[0]
  54        exit                                exit
  55        popj                     |          jmp     _ggt
  56_f:                                 _f:
  57        entry   2                           entry   2
  58        store   l[0]                        store   l[0]
  59s_f:                                s_f:
  60                                 >          dup
  61        store   l[1]                        store   l[1]
  62        load    l[1]             <
  63        loadi   0                           loadi   0
  64        gei                                 gei
  65        brfalse l4                          brfalse l4
  66        load    l[1]                        load    l[1]
  67        pushj   _g               <
  68        jmp     l5               <
  69l4:                              <
  70        load    l[1]             <
  71        loadi   1                <
  72        addi                     <
  73        pushj   _f               <
  74l5:                              <
  75e_f:                             <
  76        load    l[0]                        load    l[0]
  77        exit                                exit
  78        popj                     |          jmp     _g
  79                                 >  l4:
  80                                 >          load    l[1]
  81                                 >          incri
  82                                 >          jmp     s_f
  83_g:                                 _g:
  84        entry   2                           entry   2
  85        store   l[0]                        store   l[0]
  86s_g:                                s_g:
  87                                 >          dup
  88        store   l[1]                        store   l[1]
  89        load    l[1]             <
  90        loadi   0                           loadi   0
  91        gei                                 gei
  92        brfalse l6                          brfalse l6
  93        load    l[1]                        load    l[1]
  94        loadi   1                |          decri
  95        subi                     |          jmp     s_g
  96        pushj   _g               <
  97        jmp     l7               <
  98l6:                                 l6:
  99        load    l[1]                        load    l[1]
 100        pushj   _f               <
 101l7:                              <
 102e_g:                             <
 103        load    l[0]                        load    l[0]
 104        exit                                exit
 105        popj                     |          jmp     _f
 106
 107.data   1                           .data   1
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
CodeerzeugungInhaltsverzeichnisSprung- und Peephole-Optimierung
Letzte Änderung: 09.01.2017
© Prof. Dr. Uwe Schmidt
Prof. Dr. Uwe Schmidt FH Wedel