Powered by ViewCVS 1.0-dev
| 1 : | anton | 1.1 | \ get some data on potential (partial) inlining |
| 2 : | |||
| 3 : | \ Copyright (C) 2004 Free Software Foundation, Inc. | ||
| 4 : | |||
| 5 : | \ This file is part of Gforth. | ||
| 6 : | |||
| 7 : | \ Gforth is free software; you can redistribute it and/or | ||
| 8 : | \ modify it under the terms of the GNU General Public License | ||
| 9 : | \ as published by the Free Software Foundation; either version 2 | ||
| 10 : | \ of the License, or (at your option) any later version. | ||
| 11 : | |||
| 12 : | \ This program is distributed in the hope that it will be useful, | ||
| 13 : | \ but WITHOUT ANY WARRANTY; without even the implied warranty of | ||
| 14 : | \ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | ||
| 15 : | \ GNU General Public License for more details. | ||
| 16 : | |||
| 17 : | \ You should have received a copy of the GNU General Public License | ||
| 18 : | \ along with this program; if not, write to the Free Software | ||
| 19 : | \ Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111, USA. | ||
| 20 : | |||
| 21 : | |||
| 22 : | \ relies on some Gforth internals | ||
| 23 : | |||
| 24 : | \ !! assumption: each file is included only once; otherwise you get | ||
| 25 : | \ the counts for just one of the instances of the file. This can be | ||
| 26 : | \ fixed by making sure that every source position occurs only once as | ||
| 27 : | \ a profile point. | ||
| 28 : | |||
| 29 : | true constant count-calls? \ do some profiling of colon definitions etc. | ||
| 30 : | |||
| 31 : | \ for true COUNT-CALLS?: | ||
| 32 : | |||
| 33 : | \ What data do I need for evaluating the effectiveness of (partial) inlining? | ||
| 34 : | |||
| 35 : | \ static and dynamic counts of everything: | ||
| 36 : | |||
| 37 : | \ original BB length (histogram and average) | ||
| 38 : | \ BB length with partial inlining (histogram and average) | ||
| 39 : | \ since we cannot partially inline library calls, we use a parameter | ||
| 40 : | \ that represents the amount of partial inlining we can expect there. | ||
| 41 : | \ number of tail calls (original and after partial inlining) | ||
| 42 : | \ number of calls (original and after partial inlining) | ||
| 43 : | \ reason for BB end: call, return, execute, branch | ||
| 44 : | |||
| 45 : | \ how many static calls are there to a word? How many of the dynamic | ||
| 46 : | \ calls call just a single word? | ||
| 47 : | |||
| 48 : | anton | 1.2 | \ how much does inlining called-once words help? |
| 49 : | \ how much does inlining words without control flow help? | ||
| 50 : | \ how much does partial inlining help? | ||
| 51 : | \ what's the overlap? | ||
| 52 : | \ optimizing return-to-returns (tail calls), return-to-calls, call-to-calls | ||
| 53 : | |||
| 54 : | anton | 1.1 | struct |
| 55 : | anton | 1.3 | cell% field list-next |
| 56 : | anton | 1.2 | end-struct list% |
| 57 : | |||
| 58 : | list% | ||
| 59 : | anton | 1.7 | cell% 2* field profile-count \ how often this profile point is performed |
| 60 : | anton | 1.1 | cell% 2* field profile-sourcepos |
| 61 : | anton | 1.6 | cell% field profile-char \ character position in line |
| 62 : | cell% field profile-bblen \ number of primitives in BB | ||
| 63 : | anton | 1.7 | cell% field profile-bblenpi \ bblen after partial inlining |
| 64 : | cell% field profile-callee-postlude \ 0 or (for calls) callee postlude len | ||
| 65 : | cell% field profile-tailof \ 0 or (for tail bbs) pointer to coldef bb | ||
| 66 : | anton | 1.6 | cell% field profile-colondef? \ is this a colon definition start |
| 67 : | cell% field profile-calls \ static calls to the colon def (calls%) | ||
| 68 : | cell% field profile-straight-line \ may contain calls, but no other CF | ||
| 69 : | cell% field profile-calls-from \ static calls in the colon def | ||
| 70 : | anton | 1.7 | cell% field profile-exits \ number of exits in this colon def |
| 71 : | cell% 2* field profile-execs \ number of EXECUTEs etc. of this colon def | ||
| 72 : | cell% field profile-prelude \ first BB-len of colon def (incl. callee) | ||
| 73 : | cell% field profile-postlude \ last BB-len of colon def (incl. callee) | ||
| 74 : | end-struct profile% \ profile point | ||
| 75 : | anton | 1.1 | |
| 76 : | anton | 1.2 | list% |
| 77 : | anton | 1.3 | cell% field calls-call \ ptr to profile point of bb containing the call |
| 78 : | anton | 1.2 | end-struct calls% |
| 79 : | |||
| 80 : | anton | 1.1 | variable profile-points \ linked list of profile% |
| 81 : | 0 profile-points ! | ||
| 82 : | variable next-profile-point-p \ the address where the next pp will be stored | ||
| 83 : | profile-points next-profile-point-p ! | ||
| 84 : | anton | 1.3 | variable last-colondef-profile \ pointer to the pp of last colon definition |
| 85 : | variable current-profile-point | ||
| 86 : | anton | 1.5 | variable library-calls 0 library-calls ! \ list of calls to library colon defs |
| 87 : | anton | 1.4 | variable in-compile,? in-compile,? off |
| 88 : | anton | 1.6 | variable all-bbs 0 all-bbs ! \ list of all basic blocks |
| 89 : | anton | 1.2 | |
| 90 : | \ list stuff | ||
| 91 : | |||
| 92 : | anton | 1.3 | : map-list ( ... list xt -- ... ) |
| 93 : | { xt } begin { list } | ||
| 94 : | list while | ||
| 95 : | list xt execute | ||
| 96 : | list list-next @ | ||
| 97 : | repeat ; | ||
| 98 : | |||
| 99 : | : drop-1+ drop 1+ ; | ||
| 100 : | |||
| 101 : | : list-length ( list -- u ) | ||
| 102 : | 0 swap ['] drop-1+ map-list ; | ||
| 103 : | |||
| 104 : | : insert-list ( listp listpp -- ) | ||
| 105 : | \ insert list node listp into list pointed to by listpp in front | ||
| 106 : | tuck @ over list-next ! | ||
| 107 : | swap ! ; | ||
| 108 : | |||
| 109 : | : insert-list-end ( listp listppp -- ) | ||
| 110 : | \ insert list node listp into list, with listppp indicating the | ||
| 111 : | \ position to insert at, and indicating the position behind the | ||
| 112 : | \ new element afterwards. | ||
| 113 : | 2dup @ insert-list | ||
| 114 : | swap list-next swap ! ; | ||
| 115 : | anton | 1.2 | |
| 116 : | anton | 1.3 | \ calls |
| 117 : | |||
| 118 : | : new-call ( profile-point -- call ) | ||
| 119 : | calls% %alloc tuck calls-call ! ; | ||
| 120 : | anton | 1.2 | |
| 121 : | \ profile-point stuff | ||
| 122 : | |||
| 123 : | anton | 1.1 | : new-profile-point ( -- addr ) |
| 124 : | profile% %alloc >r | ||
| 125 : | 0. r@ profile-count 2! | ||
| 126 : | current-sourcepos r@ profile-sourcepos 2! | ||
| 127 : | >in @ r@ profile-char ! | ||
| 128 : | anton | 1.7 | 0 r@ profile-callee-postlude ! |
| 129 : | 0 r@ profile-tailof ! | ||
| 130 : | anton | 1.6 | r@ profile-colondef? off |
| 131 : | 0 r@ profile-bblen ! | ||
| 132 : | anton | 1.7 | -100000000 r@ profile-bblenpi ! |
| 133 : | current-profile-point @ profile-bblenpi @ -100000000 = if | ||
| 134 : | current-profile-point @ dup profile-bblen @ swap profile-bblenpi ! | ||
| 135 : | endif | ||
| 136 : | anton | 1.6 | 0 r@ profile-calls ! |
| 137 : | r@ profile-straight-line on | ||
| 138 : | 0 r@ profile-calls-from ! | ||
| 139 : | anton | 1.7 | 0 r@ profile-exits ! |
| 140 : | 0. r@ profile-execs 2! | ||
| 141 : | 0 r@ profile-prelude ! | ||
| 142 : | 0 r@ profile-postlude ! | ||
| 143 : | anton | 1.3 | r@ next-profile-point-p insert-list-end |
| 144 : | r@ current-profile-point ! | ||
| 145 : | anton | 1.6 | r@ new-call all-bbs insert-list |
| 146 : | anton | 1.1 | r> ; |
| 147 : | |||
| 148 : | : print-profile ( -- ) | ||
| 149 : | profile-points @ begin | ||
| 150 : | dup while | ||
| 151 : | dup >r | ||
| 152 : | r@ profile-sourcepos 2@ .sourcepos ." :" | ||
| 153 : | r@ profile-char @ 0 .r ." : " | ||
| 154 : | r@ profile-count 2@ 0 d.r cr | ||
| 155 : | anton | 1.2 | r> list-next @ |
| 156 : | anton | 1.1 | repeat |
| 157 : | drop ; | ||
| 158 : | |||
| 159 : | : print-profile-coldef ( -- ) | ||
| 160 : | profile-points @ begin | ||
| 161 : | dup while | ||
| 162 : | dup >r | ||
| 163 : | r@ profile-colondef? @ if | ||
| 164 : | r@ profile-sourcepos 2@ .sourcepos ." :" | ||
| 165 : | r@ profile-char @ 3 .r ." : " | ||
| 166 : | r@ profile-count 2@ 10 d.r | ||
| 167 : | r@ profile-straight-line @ space 2 .r | ||
| 168 : | anton | 1.3 | r@ profile-calls @ list-length 4 .r |
| 169 : | anton | 1.1 | cr |
| 170 : | endif | ||
| 171 : | anton | 1.2 | r> list-next @ |
| 172 : | anton | 1.1 | repeat |
| 173 : | drop ; | ||
| 174 : | |||
| 175 : | anton | 1.3 | : 1= ( u -- f ) |
| 176 : | 1 = ; | ||
| 177 : | |||
| 178 : | : 2= ( u -- f ) | ||
| 179 : | 2 = ; | ||
| 180 : | |||
| 181 : | : 3= ( u -- f ) | ||
| 182 : | 3 = ; | ||
| 183 : | |||
| 184 : | : 1u> ( u -- f ) | ||
| 185 : | 1 u> ; | ||
| 186 : | |||
| 187 : | : call-count+ ( ud1 callp -- ud2 ) | ||
| 188 : | calls-call @ profile-count 2@ d+ ; | ||
| 189 : | |||
| 190 : | anton | 1.5 | : count-dyncalls ( calls -- ud ) |
| 191 : | 0. rot ['] call-count+ map-list ; | ||
| 192 : | |||
| 193 : | : add-calls ( statistics1 xt-test profpp -- statistics2 xt-test ) | ||
| 194 : | \ add statistics for callee profpp up, if the number of static | ||
| 195 : | \ calls to profpp satisfies xt-test ( u -- f ); see below for what | ||
| 196 : | \ statistics are computed. | ||
| 197 : | anton | 1.3 | { xt-test p } |
| 198 : | anton | 1.5 | p profile-colondef? @ if |
| 199 : | anton | 1.3 | p profile-calls @ { calls } |
| 200 : | calls list-length { stat } | ||
| 201 : | anton | 1.5 | stat xt-test execute if |
| 202 : | { d: ud-dyn-callee d: ud-dyn-caller u-stat u-exec-callees u-callees } | ||
| 203 : | ud-dyn-callee p profile-count 2@ 2dup { d: de } d+ | ||
| 204 : | ud-dyn-caller calls count-dyncalls 2dup { d: dr } d+ | ||
| 205 : | u-stat stat + | ||
| 206 : | u-exec-callees de dr d<> - | ||
| 207 : | u-callees 1+ | ||
| 208 : | anton | 1.3 | endif |
| 209 : | endif | ||
| 210 : | xt-test ; | ||
| 211 : | |||
| 212 : | : print-stat-line ( xt -- ) | ||
| 213 : | anton | 1.5 | >r 0. 0. 0 0 0 r> profile-points @ ['] add-calls map-list drop |
| 214 : | anton | 1.3 | ( ud-dyn-callee ud-dyn-caller u-stat ) |
| 215 : | anton | 1.5 | 6 u.r 7 u.r 7 u.r 12 ud.r 12 ud.r space ; |
| 216 : | |||
| 217 : | : print-library-stats ( -- ) | ||
| 218 : | library-calls @ list-length 20 u.r \ static callers | ||
| 219 : | library-calls @ count-dyncalls 12 ud.r \ dynamic callers | ||
| 220 : | 13 spaces ; | ||
| 221 : | anton | 1.3 | |
| 222 : | anton | 1.6 | : bblen+ ( u1 callp -- u2 ) |
| 223 : | calls-call @ profile-bblen @ + ; | ||
| 224 : | |||
| 225 : | : dyn-bblen+ ( ud1 callp -- ud2 ) | ||
| 226 : | calls-call @ dup profile-count 2@ rot profile-bblen @ 1 m*/ d+ ; | ||
| 227 : | |||
| 228 : | : print-bb-statistics ( -- ) | ||
| 229 : | ." static dynamic" cr | ||
| 230 : | all-bbs @ list-length 6 u.r all-bbs @ count-dyncalls 12 ud.r ." basic blocks" cr | ||
| 231 : | 0 all-bbs @ ['] bblen+ map-list 6 u.r | ||
| 232 : | 0. all-bbs @ ['] dyn-bblen+ map-list 12 ud.r ." primitives" cr | ||
| 233 : | ; | ||
| 234 : | |||
| 235 : | anton | 1.3 | : print-statistics ( -- ) |
| 236 : | anton | 1.5 | ." callee exec'd static dyn-caller dyn-callee condition" cr |
| 237 : | anton | 1.3 | ['] 0= print-stat-line ." calls to coldefs with 0 callers" cr |
| 238 : | ['] 1= print-stat-line ." calls to coldefs with 1 callers" cr | ||
| 239 : | ['] 2= print-stat-line ." calls to coldefs with 2 callers" cr | ||
| 240 : | ['] 3= print-stat-line ." calls to coldefs with 3 callers" cr | ||
| 241 : | ['] 1u> print-stat-line ." calls to coldefs with >1 callers" cr | ||
| 242 : | anton | 1.5 | print-library-stats ." library calls" cr |
| 243 : | anton | 1.6 | print-bb-statistics |
| 244 : | anton | 1.3 | ; |
| 245 : | |||
| 246 : | anton | 1.1 | : dinc ( profilep -- ) |
| 247 : | \ increment double pointed to by d-addr | ||
| 248 : | profile-count dup 2@ 1. d+ rot 2! ; | ||
| 249 : | |||
| 250 : | : profile-this ( -- ) | ||
| 251 : | anton | 1.4 | in-compile,? @ in-compile,? on |
| 252 : | new-profile-point POSTPONE literal POSTPONE dinc | ||
| 253 : | in-compile,? ! ; | ||
| 254 : | anton | 1.1 | |
| 255 : | \ Various words trigger PROFILE-THIS. In order to avoid getting | ||
| 256 : | \ several calls to PROFILE-THIS from a compiling word (like ?EXIT), we | ||
| 257 : | \ just wait until the next word is parsed by the text interpreter (in | ||
| 258 : | \ compile state) and call PROFILE-THIS only once then. The whole | ||
| 259 : | \ BEFORE-WORD hooking etc. is there for this. | ||
| 260 : | |||
| 261 : | \ The reason that we do this is because we use the source position for | ||
| 262 : | \ the profiling information, and there's only one source position for | ||
| 263 : | \ ?EXIT. If we used the threaded code position instead, we would see | ||
| 264 : | \ that ?EXIT compiles to several threaded-code words, and could use | ||
| 265 : | \ different profile points for them. However, usually dealing with | ||
| 266 : | \ the source is more practical. | ||
| 267 : | |||
| 268 : | \ Another benefit is that we can ask for profiling anywhere in a | ||
| 269 : | \ control-flow word (even before it compiles its own stuff). | ||
| 270 : | |||
| 271 : | \ Potential problem: Consider "COMPILING ] [" where COMPILING compiles | ||
| 272 : | \ a whole colon definition (and triggers our profiler), but during the | ||
| 273 : | \ compilation of the colon definition there is no parsing. Afterwards | ||
| 274 : | \ you get interpret state at first (no profiling, either), but after | ||
| 275 : | \ the "]" you get parsing in compile state, and PROFILE-THIS gets | ||
| 276 : | \ called (and compiles code that is never executed). It would be | ||
| 277 : | \ better if we had a way of knowing whether we are in a colon def or | ||
| 278 : | \ not (and used that knowledge instead of STATE). | ||
| 279 : | |||
| 280 : | anton | 1.6 | Defer before-word-profile ( -- ) |
| 281 : | ' noop IS before-word-profile | ||
| 282 : | anton | 1.1 | |
| 283 : | anton | 1.6 | : before-word1 ( -- ) |
| 284 : | before-word-profile defers before-word ; | ||
| 285 : | anton | 1.1 | |
| 286 : | anton | 1.6 | ' before-word1 IS before-word |
| 287 : | anton | 1.1 | |
| 288 : | anton | 1.6 | : profile-this-compiling ( -- ) |
| 289 : | state @ if | ||
| 290 : | profile-this | ||
| 291 : | ['] noop IS before-word-profile | ||
| 292 : | endif ; | ||
| 293 : | |||
| 294 : | : cock-profiler ( -- ) | ||
| 295 : | \ as in cock the gun - pull the trigger | ||
| 296 : | ['] profile-this-compiling IS before-word-profile | ||
| 297 : | [ count-calls? ] [if] \ we are at a non-colondef profile point | ||
| 298 : | last-colondef-profile @ profile-straight-line off | ||
| 299 : | [endif] | ||
| 300 : | ; | ||
| 301 : | anton | 1.1 | |
| 302 : | : hook-profiling-into ( "name" -- ) | ||
| 303 : | \ make (deferred word) "name" call cock-profiler, too | ||
| 304 : | ' >body >r :noname | ||
| 305 : | anton | 1.6 | POSTPONE cock-profiler |
| 306 : | anton | 1.1 | r@ @ compile, \ old hook behaviour |
| 307 : | POSTPONE ; | ||
| 308 : | r> ! ; \ change hook behaviour | ||
| 309 : | |||
| 310 : | : note-execute ( -- ) | ||
| 311 : | anton | 1.7 | \ end of BB due to execute, dodefer, perform |
| 312 : | profile-this \ should actually happen after the word, but the | ||
| 313 : | \ error is probably small | ||
| 314 : | anton | 1.1 | ; |
| 315 : | |||
| 316 : | : note-call ( addr -- ) | ||
| 317 : | \ addr is the body address of a called colon def or does handler | ||
| 318 : | anton | 1.5 | dup ['] (does>2) >body = if \ adjust does handler address |
| 319 : | 4 cells here 1 cells - +! | ||
| 320 : | anton | 1.1 | endif |
| 321 : | anton | 1.7 | { addr } |
| 322 : | current-profile-point @ { lastbb } | ||
| 323 : | profile-this | ||
| 324 : | current-profile-point @ { thisbb } | ||
| 325 : | thisbb new-call { call-node } | ||
| 326 : | over 3 cells + @ ['] dinc >body = if | ||
| 327 : | anton | 1.5 | \ non-library call |
| 328 : | anton | 1.7 | !! update profile-bblenpi of last and current pp |
| 329 : | addr cell+ @ { callee-pp } | ||
| 330 : | callee-pp profile-postlude @ thisbb profile-callee-postlude ! | ||
| 331 : | call-node callee-pp profile-calls insert-list | ||
| 332 : | anton | 1.5 | else ( addr call-prof-point ) |
| 333 : | anton | 1.7 | call-node library-calls insert-list |
| 334 : | anton | 1.5 | endif ; |
| 335 : | anton | 1.4 | |
| 336 : | anton | 1.1 | : prof-compile, ( xt -- ) |
| 337 : | anton | 1.4 | in-compile,? @ if |
| 338 : | DEFERS compile, EXIT | ||
| 339 : | endif | ||
| 340 : | anton | 1.6 | 1 current-profile-point @ profile-bblen +! |
| 341 : | anton | 1.7 | dup CASE |
| 342 : | ['] execute of note-execute endof | ||
| 343 : | ['] perform of note-execute endof | ||
| 344 : | dup >does-code if | ||
| 345 : | dup >does-code note-call | ||
| 346 : | then | ||
| 347 : | dup >code-address CASE | ||
| 348 : | docol: OF dup >body note-call ENDOF | ||
| 349 : | dodefer: OF note-execute ENDOF | ||
| 350 : | \ dofield: OF >body @ POSTPONE literal ['] + peephole-compile, EXIT ENDOF | ||
| 351 : | \ code words and ;code-defined words (code words could be optimized): | ||
| 352 : | ENDCASE | ||
| 353 : | anton | 1.1 | ENDCASE |
| 354 : | DEFERS compile, ; | ||
| 355 : | |||
| 356 : | anton | 1.4 | : :-hook-profile ( -- ) |
| 357 : | defers :-hook | ||
| 358 : | next-profile-point-p @ | ||
| 359 : | profile-this | ||
| 360 : | anton | 1.7 | @ dup last-colondef-profile ! ( current-profile-point ) |
| 361 : | 1 over profile-bblenpi ! | ||
| 362 : | anton | 1.4 | profile-colondef? on ; |
| 363 : | |||
| 364 : | anton | 1.7 | : exit-hook-profile ( -- ) |
| 365 : | defers exit-hook | ||
| 366 : | 1 last-colondef-profile @ profile-exits +! ; | ||
| 367 : | |||
| 368 : | : ;-hook-profile ( -- ) | ||
| 369 : | \ ;-hook is called before the POSTPONE EXIT | ||
| 370 : | defers ;-hook | ||
| 371 : | last-colondef-profile @ { col } | ||
| 372 : | current-profile-point @ { bb } | ||
| 373 : | col profile-bblen @ col profile-prelude +! | ||
| 374 : | col profile-exits @ 0= if | ||
| 375 : | col bb profile-tailof ! | ||
| 376 : | bb profile-bblen @ bb profile-callee-postlude @ + | ||
| 377 : | col profile-postlude ! | ||
| 378 : | 1 bb profile-bblenpi ! | ||
| 379 : | \ not counting the EXIT | ||
| 380 : | endif ; | ||
| 381 : | |||
| 382 : | anton | 1.6 | hook-profiling-into then-like |
| 383 : | \ hook-profiling-into if-like \ subsumed by other-control-flow | ||
| 384 : | \ hook-profiling-into ahead-like \ subsumed by other-control-flow | ||
| 385 : | hook-profiling-into other-control-flow | ||
| 386 : | hook-profiling-into begin-like | ||
| 387 : | hook-profiling-into again-like | ||
| 388 : | hook-profiling-into until-like | ||
| 389 : | anton | 1.1 | ' :-hook-profile IS :-hook |
| 390 : | anton | 1.4 | ' prof-compile, IS compile, |
| 391 : | anton | 1.7 | ' exit-hook-profile IS exit-hook |
| 392 : | ' ;-hook-profile IS ;-hook |
|
CVS Admin Powered by ViewCVS 1.0-dev |
ViewCVS and CVS Help |