Check-in [a19796b4e5]
Bounty program for improvements to Tcl and certain Tcl packages.

Overview
Comment: Oops - didn't commit images for callframe.md! family | ancestors | descendants | both | files | file ages | folders a19796b4e5fb57d906cd20a7ad436d093ac397cd4fbf3e6752bbe5a785ca839e kbk 2019-03-26 20:45:25
Context
 2019-06-08 22:21 Remove cfRedundancy' header - added prematurely before method structure actually designed. check-in: 74a853f4cd user: kbk tags: kbk-refactor-callframe 2019-03-26 20:45 Oops - didn't commit images for callframe.md! check-in: a19796b4e5 user: kbk tags: kbk-refactor-callframe 2019-02-25 04:41 More about code motion check-in: 2f51c8d73b user: kbk tags: kbk-refactor-callframe
Changes

     > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > >  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63   

     > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > >  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 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 107   

     > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > >  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65   

Changes to doc/20190216callframe/callframe.md.

 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  doSomething cfout cfin moreArgs the input callframe will never again be used. ## TASK 4: Loop-invariant stores ## References $DREC93$ Karl-Heinz Drechsler and Manfred P. Stadel. "A variation of Knoop, Rüthing, and Steffen's _Lazy Code Motion_". _ACM SIGPLAN Notices_ 28:5 (May, 1993), pp. 29-38. [] $SIMP96$ Loren Taylor Simpson. 1996. "Value-Driven Redundancy Elimination". Ph.D. Dissertation. Rice University, Houston, TX, USA. AAI9631092. [] $VanD04$ VanDrunen, Thomas J. "Partial redundancy elimination for global value numbering." PhD thesis, Purdue University, West Lafayette, Indiana (August, 2004) []   > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > < | | | > > > > > > > > > > > >  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  doSomething cfout cfin moreArgs the input callframe will never again be used. ## TASK 4: Loop-invariant stores We have seen in Task 3 that'moveFromCallFrame' instructions can be placed speculatively to convert partial availability of a needed expression to full availability (and remove a 'moveFromCallFrame' later in the program on a 'busier' execution path). In a similar manner, 'moveToCallFrame' instructions can be placed speculatively at the head of blocks in order to make partially dead assignments ("faint" assignments in the terminology of $KNOO94$) fully dead and eliminate a 'moveToCallFrame' on an eariler path of the program. $LO98$ demonstrates how this partial liveness analysis is precisely dual to partial availability analysis, and introduces a dual form to Static Single Assignment (SSA), called Static Single Use (SSU). This latter form has similar advantages to SSA in that the dependency chain, here from definition to use rather than from use to definition, is factored so that there are explicit deviation points (dual to the merge points represented by φ operations in SSA form), and all divergence analysis can be limited to those points (just as confluence analysis can be limited to φ operations.) Since this analysis, and the liveness analysis on SSA values that is used to insert free instructions, appear to be the only places where factored _du_-chains are of interest in the quadcode compiler, it appears that converting programs to SSU (or combined SSA/SSU) form will not be profitable, compared with the additional expense of performing the analysis on an un-factored data flow graph. For this reason, the more computationally complex analysis of $KNOO94$ will be followed, but modified to operate on basic blocks rather than individual instructions. We begin with the liveness analysis of Task 2. We augment 'liveness' with the concept of partial liveness. The data flow equations will look like ![\textt{LIVE\_OUT}[B] = \begin{Bmatrix} \displaystyle \bigcap_{S \in \textt{succ}[B]} \textt{LIVE\_IN}[S],& S \text{ is not an exit block} \\ \displaystyle \left\{ v \in \textt{LOCALVARS}~|~v~\text{might alias a nonlocal variable} \right\},&\text{otherwise}\end{matrix}](liveout.svg) ![\textt{PLIVE\_OUT}[B] = \begin{Bmatrix} \displaystyle \bigcup_{S \in \textt{succ}[B]} \textt{PLIVE\_IN}[S],& S \text{ is not an exit block} \\ \displaystyle \left\{ v \in \textt{LOCALVARS}~|~v~\text{might alias a nonlocal variable} \right\},&\text{otherwise}\end{matrix}](pliveout.svg) ![\textt{LIVE\_IN}[B] = \textt{process}(B, \textt{LIVE\_OUT}[B])](livein.svg) ![\textt{PLIVE\_IN}[B] = \textt{process}(B, \textt{PLIVE\_OUT}[B])](plivein.svg) In these equations, _process_ represents the basic-block-level upward analysis from Task 2. The _LIVE_ and _PLIVE_ sets are sets of (callframe, variable) pairs, and it is assumed that the arguments to the intersection and union are translated if the callframe appears in a φ operation. Liveness corresponds to the 'availability' of the partial redundancy elimination. Just as a 'moveFromCallFrame' may not be hoisted over the point where it is available, a 'moveToCallFrame' may not be sunk past the point where it is live. Similarly, 'moveToCallFrame' creates values and corresponds to anticipability. Just as it is of no benefit to insert a 'moveFromCallFrame' for a value that is not anticipated, it is of no benefit to insert a 'moveToCallFrame' for a value that is already present. ## References $DREC93$ Karl-Heinz Drechsler and Manfred P. Stadel. "A variation of Knoop, Rüthing, and Steffen's _Lazy Code Motion_". _ACM SIGPLAN Notices_ 28:5 (May, 1993), pp. 29-38. [] $KNOO94$ Jens Knoop, Oliver Rüthing, and Bernhard Steffen. "Partial dead code elimination". Proc. 1994 ACM SIGPLAN Conf. Orlando, Fla. USA: ACM, June 1994, pp. 147-158. [] $LO98$ Raymond Lo, Fred Chow, Robert Kennedy, Shin-Ming Liu, and Peng Tu. "Register promotion by sparse partial redundancy elimination of loads and stores." Proc. 1998 ACM SIGPLAN Conf. Programming Language Design and Implementation (PLDI '98). Montreal, Canada: ACM, June, 1998, pp. 26-37. [] $SIMP96$ Loren Taylor Simpson. 1996. "Value-Driven Redundancy Elimination". Ph.D. Dissertation. Rice University, Houston, TX, USA. AAI9631092. [] $VanD04$ VanDrunen, Thomas J. "Partial redundancy elimination for global value numbering." PhD thesis, Purdue University, West Lafayette, Indiana (August, 2004) [] 

     > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > >  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62   

     > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > >  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 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 107 108 109 110 111 112 113 114 115 116 117 118 119 120 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 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165   
     > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > >  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65   
     > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > >  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 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 107 108 109 110 111 112 113 114 115 116 117 118 119 120 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 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168