Errata in ASSAPRE

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.