Quasistatic Constructs

In the first two sections of this chapter, I define several syntactic constructs for annotating C source code to aid a clever compiler --- namely, quasistatic variables and qif-qelse statements, and quasistatic parameters and qinfluence statements [] --- and give some examples to help describe them in detail. Then in the last section of this chapter, I will try to justify this particular approach. Note that I do not claim that these constructs are ideal, necessary, or even sufficient annotations for a clever compiler; however, there is great benefit in having something which can be implemented, tried, and discussed in concrete details rather than vague generalities.

Before proceeding, I give some general background premises.

• When the programmer uses annotations to indicate alternative code sequences in the source code, he or she is telling the clever compiler that there are alternative versions of the program which can be created by selecting different alternatives code sequences. Furthermore, the programmer is asserting that any of these versions of the program is functionally correct.

• Suppose in function A() the programmer indicates (the precise annotation mechanism is unimportant) a decision D1 is to be made by the clever compiler between code fragments A1, A2, and A3, and similarly in B() the programmer indicates an decision D2 between B1, B2, and B3, and in C() a decision D3 between C1 and C2. If the decisions D1, D2, and D3 can be made independently of each other, then there are already at least 18 different versions of this program. This multiplicative effect means that the number of versions of a program is potentially explosive.

•   It is useful to think of the different versions of the program as being located in a decision space. What constitutes dimensions of the space may vary; in the above example, one can consider the versions of the program to be lattice points in a three-dimensional space with the dimensions representing respectively the possible outcomes of D1, the possible outcomes of D2, and the possible outcomes of D3.

• Then the clever compiler's task can be formulated as searching the version space for the ``best'' version. A complete search is likely to be impractical because of the explosive number of versions --- however, once cast in this light, standard space-searching techniques (e.g., hill-climbing, simulated annealing) could be applied to this problem, to find a ``good'' although possibly not ``best'' version.

• In the interests of making an effective clever compiler possible, annotations should searching the space easier. One way of doing this is to choose annotations that allow the programmer to express whether or not multiple decisions are likely to interact with each other in terms of program performance. This has the drawback that programmers are often wrong about how different parts of their programs interact with respect to performance. However, in the above example, if the programmer somehow indicate to the clever compiler his or her belief that all three decisions are likely to have independent effects on program performance, then a clever compiler can organize its search accordingly. For example, once the compiler has tried D1= A1, D1= A2, and D1= A3 versions of the program (with D2= B1 and D3= C1 held constant), it might notice that the D1= A2 version performed best out of those three, and then explore the D1= A2 ``plane'' of the search space first.

• Quasistatic Variables and qif-qelse Statements
• Quasistatic Parameters and qinfluence Statements
• Justification