Compilerbauhome Compilerbau & Formale Sprachen: 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 2 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 gesammte 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: tailRecursion.ppl ppl/examples/tailRecursion.ppl

   1-- $Id: tailRecursion.ppl,v 1.2 2007-01-11 21:29:59 uwe Exp $
   2
   3function ggt(x,y : int) : int
   4  if x = y
   5  then x
   6  else if x > y
   7  then ggt(x - y, y)
   8  else tgg(x, y)
   9;
  10
  11function tgg(x,y : int) : int
  12  ggt(y, x)
  13;
  14
  15function f(x : int) :int
  16  if x >= 0
  17  then
  18    g(x)
  19  else
  20    f(x + 1)
  21;
  22
  23function g(x : int) : int
  24  if x >= 0
  25  then
  26    g(x - 1)
  27  else
  28    f(x)
  29;
  30 
  31begin
  32 var i : int;
  33 i := ggt(13, 8)
  34end
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: OptimizeInstr.hs 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
CodeerzeugungInhaltsverzeichnisSprung- und Peephole-Optimierung
Letzte Änderung: 14.02.2012
© Prof. Dr. Uwe Schmidt
Prof. Dr. Uwe Schmidt FH Wedel