When optimizing your code, you may want to remove the code that will never be executed in your program no mater what input the program takes or what path the program takes. In other words, there does not exist any path in the program that execute a part of code. Such code is called dead code and dead code elimination is a part of program optimization.
Example of Dead Code:
void foo()
{
int a=10;
b=a;
return;
b++; // Dead Code
}
In the above example "b++;" will never be executed in any of the program paths. The return statement transfers the control of the program to the point where foo() was called, hence b++ is never reached.
Any variable which is dead or is assigned to a dead variable is a faint variable. Different types of analysis are applied to a program to extract different information. The features of the analysis depend on kind of information we meed to extract.
Example of Dead Code:
void foo()
{
int a=10;
b=a;
return;
b++; // Dead Code
}
In the above example "b++;" will never be executed in any of the program paths. The return statement transfers the control of the program to the point where foo() was called, hence b++ is never reached.
Any variable which is dead or is assigned to a dead variable is a faint variable. Different types of analysis are applied to a program to extract different information. The features of the analysis depend on kind of information we meed to extract.
The two main features are:
1. Is the analysis a may analysis or a must analysis?
2. Is it a Forward flow analysis or a Backward flow analysis?
Let us start with the first point. When do we use a May analysis and when do we use a Must analysis? When the type of analysis depends on information propagated from all the paths, it is a must analysis, example Constant Propagation Analysis. Whereas, May analysis requires information propagated from atleast one of the paths, example Reaching Definitions Analysis. May analysis uses a union operator and Must analysis uses the intersection operator.
So, is Faint variable analysis a May analysis or a must?
Simple, usage of some faint variable v on any path will kill its faintness hence it must be faint on all the paths. So, it is a must analysis.
Second, is it a forward flow or a backward flow analysis?
The analysis that requires the information from the past is forward flow analysis and one which requires the information from the future is a backward flow analysis. As the faint variable analysis requires information about future(if the variable is assigned to a dead variable or is used in future) it is a Backward flow analysis.
As it is a backward flow must analysis, the initial statement or Binit is actually the last statement or Blast of the program with the initial inset as the universal set.
Example:
As it is a backward flow analysis the first inset will be (x,y,z) at out of 4. 4 is Binit .
Kill variables that are being used in print or return.
Gen variables that are being assigned values.
Statement
|
Kill
|
Gen
|
Inset
|
Outset
|
4
|
y
|
null
|
x,y,z
|
x,z
|
3
|
x
|
z
|
x,z
|
z
|
2
|
y
|
x
|
z
|
x,z
|
1
|
null
|
y
|
x,z
|
x,y,z
|