Interprocedural Optimization - Example

Example

Program example; integer b; %A variable "global" to the procedure Silly. Procedure Silly(a,x) if x < 0 then a:=x + b else a:=-6; End Silly; %Reference to b, not a parameter, makes Silly "impure" in general. integer a,x; %These variables are visible to Silly only if parameters. x:=7; b:=5; Silly(a,x); Print x; Silly(x,a); Print x; Silly(b,b); print b; End example;

If the parameters to Silly are passed by value, the actions of the procedure have no effect on the original variables, and since Silly does nothing to its environment (read from a file, write to a file, modify global variables such as b, etc.) its code plus all invocations may be optimized away entirely, leaving the value of a undefined (which doesn't matter) so that just the print statements remain, and they for constant values.

If instead the parameters are passed by reference, then action on them within Silly does indeed affect the originals. This is usually done by passing the machine address of the parameters to the procedure so that the procedure's adjustments are to the original storage area. Thus in the case of call by reference, procedure Silly has an effect. Suppose that its invocations are expanded in place, with parameters identified by address: the code amounts to

x:=7; b:=5; if x < 0 then a:=x + b else a:=-6; print x; %a is changed. if a < 0 then x:=a + b else x:=-6; print x; %Because the parameters are swapped. if b < 0 then b:=b + b else b:=-6; print b; %Two versions of variable b in Silly, plus the global usage.

The compiler could then in this rather small example follow the constants along the logic (such as it is) and find that the predicates of the if-statements are constant and so...

x:=7; b:=5; a:=-6; print 7; %b is not referenced, so this usage remains "pure". x:=-1; print -1; %b is referenced... b:=-6; print -6; %b is modified via its parameter manifestation.

And since the assignments to a, b and x deliver nothing to the outside world - they do not appear in output statements, nor as input to subsequent calculations (whose results in turn do lead to output, else they also are needless) - there is no point in this code either, and so the result is

print 7; print -1; print -6;

A variant method for passing parameters that appears to be "by reference" is copy-in, copy-out whereby the procedure works on a local copy of the parameters whose values are copied back to the originals on exit from the procedure. If the procedure has access to the same parameter but in different ways as in invocations such as Silly(a,a) or Silly(a,b), discrepancies can arise. So, if the parameters were passed by copy-in, copy-out in left-to-right order then Silly(b,b) would expand into

p1:=b; p2:=b; %Copy in. Local variables p1 and p2 are equal. if p2 < 0 then p1:=p2 + b else p1:=-6; %Thus p1 may no longer equal p2. b:=p1; b:=p2; %Copy out. In left-to-right order, the value from p1 is overwritten.

And in this case, copying the value of p1 (which has been changed) to b is pointless, because it is immediately overwritten by the value of p2, which value has not been modified within the procedure from its original value of b, and so the third statement becomes

print 5; %Not -6

Such differences in behavior are likely to cause puzzlement, exacerbated by questions as to the order in which the parameters are copied: will it be left to right on exit as well as entry? These details are probably not carefully explained in the compiler manual, and if they are, they will likely be passed over as being not relevant to the immediate task and long forgotten by the time a problem arises. If (as is likely) temporary values are provided via a stack storage scheme, then it is likely that the copy-back process will be in the reverse order to the copy-in, which in this example would mean that p1 would be the last value returned to b instead.

The process of expanding a procedure in-line should not be regarded as a variant of textual replacement (as in macro expansions) because syntax errors may arise as when parameters are modified and the particular invocation uses constants as parameters. Because it is important to be sure that any constants supplied as parameters will not have their value changed (constants can be held in memory just as variables are) lest subsequent usages of that constant (made via reference to its memory location) go awry, a common technique is for the compiler to generate code copying the constant's value into a temporary variable whose address is passed to the procedure, and if its value is modified, no matter; it is never copied back to the location of the constant.

Put another way, a carefully-written test program can report on whether parameters are passed by value or reference, and if used, what sort of copy-in and copy-out scheme. However, variation is endless: simple parameters might be passed by copy whereas large aggregates such as arrays might be passed by reference; simple constants such as zero might be generated by special machine codes (such as Clear, or LoadZ) while more complex constants might be stored in memory tagged as read-only with any attempt at modifying it resulting in immediate program termination, etc.