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.

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.

Thomas VanDrunen
Last modified: Wed Nov 7 10:41:07 CST 2012