Errata in my dissertation

There are several mistakes in the presentation of the ASSAPRE algorithm, both as it appears in the SP&E paper and in my dissertation.

• (SP&E pg 1426, Figure 9; Dissertation pg 40, Figure 3.7) Basic block 7 should have "t16 <- phi(t6, t11)" instead of "t16 <- phi(t9, t11)", and "t18 <- t15 - t16" instead of "t18 <- t15 + t16".
• (SP&E pg 1427, Figure 10; Dissertation pg 46, Figure 3.9) In both parts a and b of the figure, basic block 7 should have "t16 <- phi(t6, t11)" instead of "t16 <- phi(t9, t11)", and "t18 <- t15 - t16" instead of "t18 <- t15 + t16".
• (SP&E pg 1431, last complete sentence) "...its operand will have the temporaries of both chis as killers" instead of "or both chis". (This has been corrected in the dissertation.)
• (SP&E pg 1432, Table III; Dissertation pg 43, Table 3.3) Last two entries should read "t15 - t16" rather than "t15 + t16".
• (SP&E pg 1432; Dissertation pg 52, Figure 3.12) The flow equations are not right. The union operations appearing in map_in are not true set unions. The map_in and map_out functions actually map from basic blocks to functions which map temporary variables to sets of chi-operands. The "unions" are actually merging the resulting chi-operand sets. Additionally, "map_in(t) = omega" should be "omega in map_in(t)". Finally, "clearb m" should be "clearb(m)" (this last appears correctly in the dissertation).
• (SP&E pg 1433; Dissertation pg 55) "In our example, all chis are willBeAvail except for the ones associated with t20, t24, and t25." This list should also include t23.
• (SP&E pg 1434; Dissertation pg 58) Second sentence of the subsection "Final program"; to match the rest of the text, the execution paths should be listed as "(1,2,4,5,7), (1,2,4,6,7), (1,3,4,5,7), and (1,3,4,6,7)".
• (SP&E pg 1435, Figure 12; Dissertation pg 57, Figure 3.14) The first instruction in Basic Block 5 should be "t8 <- t19". The last instruction in Basic Block 7 should be "t18 <- t22".
• The algorithm given for downsaftey has vulnerabilities. In the example below, the chi operand omega is not downsafe because it is never used on the path (3, 4, 6); however, it would be found to be downsafe because on the path (3, 5, 6), t2 replaces t1 as its killer, and instruction i kills it.

Much thanks to Max Hailperin and Alex Wauck for finding these. The diagram above is based on an example Dr Hailperin produced.

There is a series of mistakes in the presentation of the GVNPRE algorithm, both as it appears in the CC paper and in my disseration, specifically in the discussion of the following example which appears as Figure 3(a) in the CC paper (pg 174) and Figure 4.2(a) in my disseration (pg 66).

In the paragraph beginning with "For an antileader set..." (pg 175 in the CC paper) or the paragraph beginning with "Although our methd..." (pg 68-69 in the dissertation), each ocassion where t4 or t6 are mentioned should be replaced with t11; likewise v4 should be v11:

Consider basic block 6 in Figure [3(a)/4.2(a)], alternately with and without the instruction t11 <- o. In the case wehre we exclude that instruction, assume t11 to be global. Without the definition of t11, ANTIC_IN can be represented by the dag in Figure [3(c)/4.2(c)]. The nodes of the dag are pairs of values and the antileaders representing them; edges are determined by the operands of the antileader. If we suppose the block contains t11 <- o as it does in the program, then v11 : t11 is killed, along with all expression that depend on v11, in cascading effect. See Figure [3(d)/4.2(d)].

In the first paragraph of section 3.1 (pg 175 in the CC paper, pg 69 of the dissertation), "To compute AVAIL_IN and AVAIL_OUT" should be "To compute ANTIC_IN and AVAIL_OUT". Also (pg 176 in the CC paper, pg 70 in the dissertation), "we all all its antileaders to AVAIL_OUT" should be "we add all its antileaders to ANTIC_OUT".

In the CC paper only: Later on pg 176, the flow equation for ANTIC_OUT uses A as an abbreviation for ANTIC_IN (the dissertation does not use the abbreviation). On pg 177, there is a reference to "insertions from S" in the text and also a use of S in figure 4 of pg 178. This refers to a variable in the algorithmic description of BuildSets which was cut from the CC paper. It can be found on pg 75 of the dissertation.

On pg 75 of the dissertation, the algorithm of BuildSets has "...if find_leader(ANTIC_IN[b], v)" which should have b' instead. Later "lookup(e')" appears which should be "lookup(e)."

Thanks to Tom de Vries for identifying this.