Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
Comment: | Compute NRE requirement for compiled procedures |
---|---|
Timelines: | family | ancestors | descendants | both | kbk-nre |
Files: | files | file ages | folders |
SHA3-256: |
4602a634be0f23f6ff94331820f3d4ab |
User & Date: | kbk 2018-03-19 02:05:59.801 |
Context
2018-03-27
| ||
01:44 | merge trunk check-in: 6b733cc796 user: kbk tags: kbk-nre | |
2018-03-19
| ||
02:05 | Compute NRE requirement for compiled procedures check-in: 4602a634be user: kbk tags: kbk-nre | |
2018-03-18
| ||
23:58 | Add NRE indication to the command table. At this point no compilable Core commands require NRE. This is expected to change in the future. check-in: ab0a234378 user: kbk tags: kbk-nre | |
Changes
Changes to quadcode/builtin_specials.tcl.
︙ | ︙ | |||
39 40 41 42 43 44 45 | } # TODO: We can't analyze [lsort -command] yet, but we could. What it would # take is to generate bytecode for the command prefix with two dummy # arguments, and then determine the effect of the bytecode on the # callframe. | | > | 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 | } # TODO: We can't analyze [lsort -command] yet, but we could. What it would # take is to generate bytecode for the command prefix with two dummy # arguments, and then determine the effect of the bytecode on the # callframe. # error "lsort -command is not supported yet" return { error "lsort -command is not supported yet" nre {} reads 0 writes 0 readsNonLocal {} writesNonLocal {} } } # quadcode::specializer method frameEffect___regexp -- # |
︙ | ︙ |
Changes to quadcode/specializer.tcl.
︙ | ︙ | |||
68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 | # processed further. # frameEffect - Dictionary whose keys are instance names and whose # values are dictionaries describing the procedure # instances' effect on the caller's callframe. # instanceBeingAnalyzed - Holds the instance name of the current procedure # during a call to type analysis in the quadcode # database. # onWorklist - Dictionary whose keys are the instance names of the # procedures on the worklist for analysis and whose values # are their positions in the heap. # precedence - Dictionary whose keys are fully qualified procedure names # (without types) and whose values are the positions of # those procedures in depth-first numbering and hence # the order in which they should be analyzed. # requiredInstances - Two level dictionary. The first level keys are # fully qualified procedure names (without types) # and the second level keys are lists of types. # The values are immaterial. This dictionary tracks # procedure instances explicity requested by an # external caller # returnType - Dictionary whose keys are instance names and whose values # are the return types of those procedure instances. # typeInf - Dictionary whose keys are instance names and whose values # are quadcode databases for the instances variable canInline cmdAttr database dependencies dependents \ | > > > > > | | 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 | # processed further. # frameEffect - Dictionary whose keys are instance names and whose # values are dictionaries describing the procedure # instances' effect on the caller's callframe. # instanceBeingAnalyzed - Holds the instance name of the current procedure # during a call to type analysis in the quadcode # database. # nreActive - Dictionary whose keys are instance names of procedures # being analyzed for NRE requirement, and whose values # are immaterial. A procedure is present if it is currently # being analyzed; this flag is used to check whether the # procedure is recursive. # onWorklist - Dictionary whose keys are the instance names of the # procedures on the worklist for analysis and whose values # are their positions in the heap. # precedence - Dictionary whose keys are fully qualified procedure names # (without types) and whose values are the positions of # those procedures in depth-first numbering and hence # the order in which they should be analyzed. # requiredInstances - Two level dictionary. The first level keys are # fully qualified procedure names (without types) # and the second level keys are lists of types. # The values are immaterial. This dictionary tracks # procedure instances explicity requested by an # external caller # returnType - Dictionary whose keys are instance names and whose values # are the return types of those procedure instances. # typeInf - Dictionary whose keys are instance names and whose values # are quadcode databases for the instances variable canInline cmdAttr database dependencies dependents \ diagnostics diagnosticSeq failed frameEffect nreActive \ instanceBeingAnalyzed onWorklist precedence requiredInstances \ returnType typeInf # Local commands: # worklist - List of procedures awaiting type analysis. This list is # organized as a binary heap in order by precedence of the # procedure, and within that, in lexicographic order by |
︙ | ︙ | |||
368 369 370 371 372 373 374 | } } # Once all the procedures are fully typed, there's a final pass needed # to determine which ones can be called directly, and which ones must # be NRE. | > > > | | 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 | } } # Once all the procedures are fully typed, there's a final pass needed # to determine which ones can be called directly, and which ones must # be NRE. my debug-specializer { puts "Analyze NRE requirements" } my nreRequired } # quadcode::specializer method searchForInlines -- # # Try to find opportunities to inline procedure instances into their # callers. # |
︙ | ︙ | |||
490 491 492 493 494 495 496 | my debug-inline { puts "Can $inst be inlined? [dict get $canInline $inst]" } return [dict get $canInline $inst] } | | | > > > > > > | > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > | 498 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520 521 522 523 524 525 526 527 528 529 530 531 532 533 534 535 536 537 538 539 540 541 542 543 544 545 546 547 548 549 550 551 552 553 554 555 556 557 558 559 560 561 562 563 564 565 566 567 568 569 570 571 572 573 574 575 576 577 578 579 580 581 582 583 584 585 586 587 588 589 590 591 592 593 594 595 596 597 598 599 600 601 602 603 604 605 606 607 608 609 610 611 612 613 614 615 616 617 618 619 620 621 622 | my debug-inline { puts "Can $inst be inlined? [dict get $canInline $inst]" } return [dict get $canInline $inst] } # quadcode::specializer nreRequired -- # # Determines which procedure instances in the call graph require # non-recursive evaluation. # # Results: # None. # # Side effects: # Calls the translator instance to set the 'NRE' flag on any procedure # requiring non-recursive evaluation # # A procedure requires NRE for any of the following reasons: # # 1. It does anything that might change the active coroutine. # 2. It invokes unknown, non-compiled commands. # 3. It invokes any Core command that requires NRE. # 4. It is directly or indirectly recursive. # 5. It invokes, directly or indirectly, any other command that # might require NRE. # # We perform a depth-first traversal of the call graph to analyze NRE. # This is done with the help of the quadcode::transformer object. We call # the transformer's 'needsNRE' method for each required instance, and it # calls back to the specializer's 'needsNRE' method for each invoked command. oo::define quadcode::specializer method nreRequired {} { set nreActive {} dict for {instance db} $typeInf { my debug-specializer { puts "NRE: $instance" } dict set nreActive $instance {} set needs [$db needsNRE] my debug-specializer { puts [format {NRE: %s %s NRE} $instance \ [expr {$needs ? "needs" : "does not need"}]] } dict unset nreActive $instance } } # quadcode::specializer method needsNRE -- # # Tests whether an individual procedure instance requires NRE. # # Parameters: # name - Name of the command to analyze # alist - List of quadcode values for the command's arguments # atypes - List of typecodes of the types of the arguments. # # Results: # Returns 1 if the command needs NRE, 0 otherwise. oo::define quadcode::specializer method needsNRE {q atypes} { set name [lindex $q 3 1] my debug-specializer { puts [format "%*sDoes %s(%s) need NRE?" [dict size $nreActive] {} \ $name $atypes] } set instance [list $name $atypes] if {[dict exists $nreActive $instance]} { my debug-specializer { puts [format "%*s Yes. It's recursive" [dict size $nreActive] {}] } return 1; # The procedure is recursive. } if {[dict exists $typeInf $instance]} { # The instance is a compiled command that we have not # visited. Find out whether it needs NRE set db [dict get $typeInf $instance] dict set nreActive $instance {} set result [$db needsNRE] dict unset nreActive $instance my debug-specializer { puts [format "%*s %s. Translator says so." \ [dict size $nreActive] {} \ [expr {$result ? "Yes" : "No"}]] } return $result } # The instance is not a compiled command. It may be a builtin. if {[dict exists $cmdAttr $name]} { set attrs [dict get $cmdAttr $name] if {[dict exists $attrs special]} { set method frameEffect_[string map {:: __} $name] set attrs [my $method $q] } if {! [dict exists $attrs nre]} { my debug-specializer { puts [format "%*s No. It's builtin" [dict size $nreActive] {}] } return 0 } } # We don't know what the instance is, so require NRE my debug-specializer { puts [format "%*s Yes. It's not understood." [dict size $nreActive] {}] } return 1 } # quadcode::specializer method frameEffect -- # # Looks up what the effect of a command is on the callframe. # # Parameters: # q - Quadcode instruction that invokes the command |
︙ | ︙ |
Changes to quadcode/transformer.tcl.
︙ | ︙ | |||
121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 | # 3 - the variable has been analyzed, and might or # might not exist depending on code path. # # TYPE INFERENCE # # types - Dictionary whose keys are variable names and whose values # are the numeric codes for the variable types. variable bytecode quadindex fixup variable debugged specializer originProc sourcefile ns variable quads vars links bbstart variable bbcontent bbpred variable bbidom bbkids bblevel bbnlevels varcount variable duchain udchain variable varExists variable types variable ptype ns_counters # Constructor - # # Keyword arguments (following the positional arguments): # -debug {list} # Accepts a list of keys. For each key in the list, a | > > > > | 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 | # 3 - the variable has been analyzed, and might or # might not exist depending on code path. # # TYPE INFERENCE # # types - Dictionary whose keys are variable names and whose values # are the numeric codes for the variable types. # # nre - Flag that is 1 if this procedure requires non-recursive # evaluation, and 0 otherwise variable bytecode quadindex fixup variable debugged specializer originProc sourcefile ns variable quads vars links bbstart variable bbcontent bbpred variable bbidom bbkids bblevel bbnlevels varcount variable duchain udchain variable varExists variable types variable nre variable ptype ns_counters # Constructor - # # Keyword arguments (following the positional arguments): # -debug {list} # Accepts a list of keys. For each key in the list, a |
︙ | ︙ | |||
680 681 682 683 684 685 686 687 688 689 690 691 692 693 694 695 696 697 | source [file join $quadcode::libdir flatten.tcl] source [file join $quadcode::libdir fqcmd.tcl] source [file join $quadcode::libdir inline.tcl] source [file join $quadcode::libdir invoke.tcl] source [file join $quadcode::libdir liveranges.tcl] source [file join $quadcode::libdir narrow.tcl] source [file join $quadcode::libdir nodesplit.tcl] source [file join $quadcode::libdir renameTemps.tcl] source [file join $quadcode::libdir ssa.tcl] source [file join $quadcode::libdir translate.tcl] source [file join $quadcode::libdir typecheck.tcl] source [file join $quadcode::libdir types.tcl] source [file join $quadcode::libdir upvar.tcl] source [file join $quadcode::libdir varargs.tcl] source [file join $quadcode::libdir widen.tcl] #source [file join $quadcode::libdir exists.tcl] #source [file join $quadcode::libdir interval.tcl] | > | 684 685 686 687 688 689 690 691 692 693 694 695 696 697 698 699 700 701 702 | source [file join $quadcode::libdir flatten.tcl] source [file join $quadcode::libdir fqcmd.tcl] source [file join $quadcode::libdir inline.tcl] source [file join $quadcode::libdir invoke.tcl] source [file join $quadcode::libdir liveranges.tcl] source [file join $quadcode::libdir narrow.tcl] source [file join $quadcode::libdir nodesplit.tcl] source [file join $quadcode::libdir nre.tcl] source [file join $quadcode::libdir renameTemps.tcl] source [file join $quadcode::libdir ssa.tcl] source [file join $quadcode::libdir translate.tcl] source [file join $quadcode::libdir typecheck.tcl] source [file join $quadcode::libdir types.tcl] source [file join $quadcode::libdir upvar.tcl] source [file join $quadcode::libdir varargs.tcl] source [file join $quadcode::libdir widen.tcl] #source [file join $quadcode::libdir exists.tcl] #source [file join $quadcode::libdir interval.tcl] |