Applying compiler optimizations

The fact that two system calls appear as a sequence in the graph does not, by itself, imply that the system calls can be grouped together. This is because even if two system calls follow each other in the trace, the system calls in the program code may be separated by arbitrary user code that does not include system calls. Replacing these calls by a multi-call would require moving the intervening code into the multi-call, which may compromise safety. Instead, we use compiler techniques like function inlining, code motion, and loop unrolling to transform the program and create sequences of system calls that can be optimized. The use of these standard and well-understood optimization techniques ensures that the transformations are correctness preserving and that the optimized program behaves the same as the original [1]. This also allows tools such as those for checking program safety to be used on the optimized program in the same way as they would for the original. Although code rearrangement is a common compiler transformation, to our knowledge it has not been used to optimize system calls as done here.

A number of program transformations can be used to rearrange the statements in a program to allow system call grouping without affecting the observable behavior of the program. A simple example involves interchanging independent statements. Two statements are said to be independent if neither one reads from or writes to any variable that may be written to by the other. Two adjacent statements that are independent and have no externally visible side-effects may be interchanged without affecting a program's observable behavior. This transformation can be used to move two system calls in a program closer to each other, so as to allow them to be grouped into a multi-call. Note that such system calls may actually start out in different procedures, but can be brought together (and hence, optimized) using techniques such as function inlining.

Another useful transformation is loop unrolling. In the control flow graph (figure 1.b), the if statement in basic block B2 prevents the read and the write system calls from being grouped together. Programs like FTP, encryption programs, and compression programs (e.g., gzip and pzip) exhibit similar control dependencies. In cases like this where the dependency appears within a loop, loop unrolling can sometimes be used to eliminate the dependency. In the case of the copy program in figure 1, for example, unrolling the loop once and combining the footer of one iteration with the header of the next iteration results in the code shown below, with adjacent system calls within the loop that are now candidates for the multi-call optimization:

	n = read(inp, buff, N);
	while (n > 0) { 
		write(out, buff, n); 
		n = read(inp, buff, N); 
	}