Analysis of Find Copies
Sept 3, 1998
Isaac Jones
2. Definitions
Given a simple copy statement, C, the next reference of the variable on the right hand side, V, determines if C is "good for swapping". If V is "used" on any path, then C is "not good for swapping". In some cases, since V is a copy of the variable on the left, V2, V2 could be used in place of V, this fact makes the analysis of swapability conservative. If V is defined on all paths, or if V goes out of scope before being referenced again, then C is "good for swapping". 		Example 2.1
Good for swapping (defined)		 

{
	int x;
	int y;//V
	x = y;//C
	y = 5;
}
Example 2.2
Good for swapping (out of scope, or UN-definition)		 

{
	int x;
	int y;//V
	x = y;//C
}
Example 2.3
Not good for swapping (use)		 


{
	int x, z;
	int y;//V
	x = y;//C
	z = y + 1;
}
3. Uses
The above two examples are the only statements that constitutes a definition.Either V appears on the left side of an assignment statement, or V goes out of scope. Exactly what constitutes a use is more complex.
Example 3.1
the appearance of V on the right side of a copy statement 		x = V;
a[i] = V;
Example 3.2
the appearance of V within an expression 		x = V + 1;
V = V + 1;
if (V > 3);
Example 3.3
output of V 		print(V);
Example 3.4
unary expressions 		V++;
Example 3.5
function/procedure parameters or array indices 		x = f(v);
f(v);
print(a[V]);
4. Branches
The complexity of data flow problems such as this comes from branch analysis. If there were no branches, we could merely look for the first reference of V after C. However, due to branches, V can be referenced along several paths, and we must therefore examine references of V along all paths. 		If V is used on some path, even if it is defined on some path, then C is "not good for swapping" If V is defined on all paths, or if V definitely goes out of scope before being referenced, or if V is defined on some path, and goes out of scope on another, then C is "good for swapping"
Example 4.1
use on some path: 
{
	x = V;//C
	if (b)
	{
		z = V;
	}	
	else
	{
		V = z;
	}
}
Example 4.2
defined on all paths 
{
	x = V;//C
	if (b)
	{
		V = 0;
	}
	else
	{
		V = 1;
	}
}
Example 4.3
definitely goes out of scope 
{
	int V;
	x = V;//c
	if (b)
	{
		print (true);
	}
	else
	{
		print (false);
	}
}
Example 4.4
defined on some path, and goes out of scope on another 
{
	int V;
	x V;//c;
	if (b)
	{
		print (true);
		//unused
	}
	else
	{
		V = 1;
		//defined
	}
}
5. Procedural Analysis
There was no inter-procedural analysis done. If V is passed as a parameter, then it is considered a use, even if it is not used inside that function. The reason for this is that binding variables to the procedures they were defined in makes the analysis far more complex. This makes for a conservative estimate of swapability. This is a limitation of the algorithm.
Example 5.1
parameter use, not good for swapping (V is defined) 
f(int x)
	{
		x = 4;
	}
main
	{
		int V;
		x = V;
		f(V);
	}
Example 5.2
parameter use, not good for swapping (V is used) 
f(int x)
	{
		print(x);
	}
main
	{
		int V;
		x = V;
		f(V);
	}
6. Globals and Inter-Procedural Analysis
In the case of global variable V, the paths of definition-reference pairs is context insensitive between functions. Again, the reason for this is that binding variables to the procedures they were defined in makes the analysis far more complex. This means that for some C, there may be a reference on some UN-realizable path which is considered a use. This makes for a conservative analysis. This is why, in the "raw" data file, you may see up to twenty uses for some C with global variable g on the right side of the copy. This is a limitation of the algorithm. 		global_int g; 
p1()
{
	int x = g;//definition
	p2();
}

p2()
{
	print ("hello");
}

p3()
{
	p2();
	int z = g + 1;//use
}
7. Alias Analysis
Because it is possible for V to have aliases, the analysis would be unsafe if it did not account for references of aliases of V. Therefore alias analysis of references was performed. Because of the nature alias analysis and branches, it must be noted that any possible alias of V is considered, making the overall analysis conservative.
Example 7.1
use of alias of V 
{
	int x, z, V, *p;
	p = &V;
	x = V;
	z = (*p); //use
}
Example 7.2
definition of alias of V 
{
	int x, V, *p;
	p = &V;
	x = V;
	(*p) = 5; //definition
}
Example 7.3
alias on some path 
{
	int x, V *p;

	if (b)
	{
		p = &V;
	}
	x = V;
	z = (*p); //possible use
}