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 |
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 46 47 48 49 50 51 52 53 54 |
}
# 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 {
nre {} reads 0 writes 0 readsNonLocal {} writesNonLocal {}
}
}
# quadcode::specializer method frameEffect___regexp --
#
|
| > |
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 .. 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 ... 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 ... 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 |
# 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.
................................................................................
# 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 \
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
................................................................................
}
}
# 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.
# TODO: my flagNRERequired
}
# quadcode::specializer method searchForInlines --
#
# Try to find opportunities to inline procedure instances into their
# callers.
#
................................................................................
my debug-inline {
puts "Can $inst be inlined? [dict get $canInline $inst]"
}
return [dict get $canInline $inst]
}
# quadcode::specializer flagNRERequired --
#
# 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:
#
#
# quadcode::specializer method frameEffect --
#
# Looks up what the effect of a command is on the callframe.
#
# Parameters:
# q - Quadcode instruction that invokes the command
|
> > > > > | > > > | | | > > > > > > | > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > |
68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 .. 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 ... 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 ... 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 |
# 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.
................................................................................
# 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
................................................................................
}
}
# 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.
#
................................................................................
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
...
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
|
# 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
................................................................................
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]
|
>
>
>
>
>
|
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
...
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
|
# 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
................................................................................
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]
|