Banning[1] formulated the side-effect analysis as computing the elements of the sets (subsequently referred to as the Banning sets):
The existing algorithms aim toward providing full and complete information for one or more of the above sets. However, for our method, this is always not necessary. To see why, first we introduce the GCC's classifications of functions in terms of their side effects.
By using an extension of C, GCC allows for functions to be annotated as const or pure[6]. These are two classes of functions with no or minimal side effects. const functions are functions that examine only their arguments. Furthermore, they have no effects besides their return value. pure functions, on the other hand, might potentially examine global value or value stored in memory, but they also have no effects except for their return value. So the class of const functions belongs as a subset of the class of pure functions. For convenience, we call functions that are neither const nor pure ``unreusable'' functions. Figure 1 gives an example of each type of functions, and figure 2 gives an example of how the applicable functions from figure 1 are annotated based on GCC's extension to C.
We can now see how const, pure, and unreusable functions relate to the types of side effects proposed by Banning. Both const and pure functions do not have any effects except their return value. Hence, any modification to global values or non-local memory in a function makes that function to be unreusable. Translated in terms of Banning's sets, a function must be unreusable if it contains one or more statements whose MOD set contains non-local variables. When we say non-local variables, we implicitly include variables whose value can be accessed (read or modified) through pointers passed to the function.
The REF set for a statement contains the variables whose value is referenced by the execution of the statement. Or we can also say that these variables are read through the execution of the statement. Hence, if a function contains a statement whose REF set includes non-local variables, then this function might be pure, but cannot be const. Whether the function is actually pure or not depends on the MOD set of the statements, as described in the previous paragraph.
The USE and DEF sets depend on flow-sensitive information[1]. In other words, to determine the USE and DEF sets for a particular statement in a function, we need to know the control-flow information in that function, including other function calls inside it. For this reason, it might not be clear how to annotate the function based on the USE and DEF sets. However, for our purposes, we do not need the information in these sets. For our analysis, we do not care whether a definition of a variable in a statement occurs by itself or whether the statement uses the value of the variable before its definition. The definition, on the other hand, implies that there is a modification to the variable. So we can put elements in the USE and DEF sets in the MOD set, and use the augmented MOD set in the same way as described above.
