/ GENTLE PRIMER
/ Optimal Rule Selection
Cost-Driven Rule Selection
A rule gives the cost of the respective operation of the rule. For example, in the PLUS operation counts 20 in
'rule' StackCode(minus(X,Y)): StackCode(X) StackCode(Y) MINUS $ 20The total cost of translating minus(X,Y) with this rule would be 20 plus the total cost of translating X plus the total cost of translating Y.
The corresponding accumulator operation is cheaper:
'rule' AccuCode(minus(X, var(V)): AccuCode(X) ACCUMINUS(V) $ 10The computation of an expression is cheaper if performed in the accumulator; hence the translation of source source text
r := x-yis
LOADACCU x ACCUMINUS y STOREACCU rand not
PUSH a PUSH b MINUS POP rwhich is also a possible result of a series of rule applications.
If the expression appears in a context where stack code is required (the outer minus does not have a simple operand) as in
r := (x-y)-(a-b)it is computed on the stack:
PUSH x PUSH y MINUS PUSH a PUSH b MINUS MINUS POP rbecause an operation that moves the intermediate result from the stack to the accumulator would be too costly.
If a larger subexpression is used, then the cheaper accumulator computation outweighs the cost of the ACCUTOSTACK instruction. The input
r := (x-y-z)-(a-b)is translated into
LOADACCU x ACCUMINUS y ACCUMINUS z ACCUTOSTACK PUSH a PUSH b MINUS MINUS POP r