Graph-coloring register allocators can eliminate copy instructions from a program by coalescing the interference graph nodes corresponding to the source and destination. Briggs showed that by limiting coalescing to those situations that he dubbed “conservative,” it could be prevented from causing spilling, that is, a situation where the allocator fails to assign a register to each live range. George and Appel adopted Briggs's conservativeness criterion in general, but provided an alternative criterion (the George test) to use in those cases where one of the nodes has been “precolored,” that is, preassigned a specific register. They motivated this alternative criterion by efficiency considerations, and provided no indication of the relative power of the two criteria. Thus it remained an open question whether the efficiency had been bought at the expense of reduced coalescing. Their implementation also used a limited version of the Briggs test, in place of the original, full version, without any comment on the impact of this substitution. In this article, we also present an analogously limited version of the George test.Thus we are now confronted with four different criteria for conservative coalescing: the full and limited Briggs tests and the full and limited George tests. We present a number of theorems characterizing the relative power of these different criteria, and a number of theorems characterizing the form of safety that each achieves. For example, we show that for coalescing with precolored nodes, the full George criterion is strictly more powerful than the full Briggs criterion, while offering an equally strong safety guarantee. Thus no coalesces are lost through George and Appel's introduction of the George test, and some can be gained without sacrificing safety.We also show that George and Appel's limited version of the Briggs test is probably undesirable. Although a slightly stronger safety result applies to it than to the full Briggs test, this comes at the expense of eliminating all coalesces that can reduce spilling.

The generally accepted wisdom among teachers of English composition is that a "rewrite cycle" should be used as a teaching strategy. Rather than expecting students to extrapolate from the grading comments on paper N what they should do differently on paper N + 1, it has become conventional to ask for a rewrite of paper N itself. Of course, there are many variations on this theme. For example, peer review may supplement or replace some of the rounds of grading.The panelists will explore some of the ways they have applied this pedagogic strategy in computer science courses. Most obviously, when we have our students write papers, we have them do rewrites. However, some of us don't stop there, but rather also apply the same idea to the writing of programs or mathematical analyses. This encourages our students to do a high-quality job, and to feel that they have truly mastered a topic.Clearly, there are tradeoffs and difficulties, principally involving time. The panelists will also discuss this aspect, indicating how they have coped with the pitfalls, and indicating what has worked well, and what not so well. Ultimately, however, all the panelists are optimistic about the value of rewrite cycles.After the panelists share their experiences, there will be some time for discussion with the audience. Based on the interest this topic provoked on the sigcse.members mailing list, and in ensuing private email, we look forward to an active audience. We will also make materials from the session available at http://www.gustavus.edu/~max/rewrite/

No abstract available.

Students come into CS1 with a variety of academic and programming backgrounds. Panelists and audience members will discuss the consequences of this fact, and explore a variety of strategies for coping with the situation.

We generalize Knoop et al.'s Lazy Code Motion (LCM) algorithm for partial redundancy elimination so that the generalized version also performs strength reduction. Although Knoop et al. have themselves extended LCM to strength reduction with their Lazy Strength Reduction algorithm, our approach differs substantially from theirs and results in a broader class of candidate expressions, stronger safety guarantees, and the elimination of the potential for performance loss instead of gain. Also, our general framework is not limited to traditional strength reduction, but rather can also handle a wide variety of optimizations in which data-flow information enables the replacement of a computation with a less expensive one. As a simple example, computations can be hoisted to points where they are constant foldable. Another example we sketch is the hoisting of polymorphic operations to points where type analysis provides leverage for optimization. Our general approach consists of placing computations so as to minimize their cost, rather than merely their number. So long as the cost differences between flowgraph nodes obey a certain natural constraint, a cost-optimal code motion transformation that does not unnecessarily prolong the lifetime of temporary varibles can be found using techniques completely analogous to LCM. Specifically, the cost differences can be discovered using a wide variety of forward data-flow analyses in a manner which we describe.

When teaching a course in compiler design, it is conventional to introduce the iterative calculation of least fixed points quite late in the course, in the guise of iterative data-flow analysis. In this paper I point out that the same mathematical and algorithmic ideas can be introduced much earlier, in the parsing portion of the course, as an explanation of the standard algorithm for computing the First sets of a context-free grammar. Doing so not only renders these techniques more familiar when they re-appear in data-flow analysis, it also provides a more sound foundation for the First algorithm than is typically offered. Moreover, these techniques deserve increased curricular prominence because they naturally lead to proofs of correctness for general non-deterministic algorithms that subsume multiple deterministic algorithms.