Def Use Optimization

The idea of this part of the optimizer is that we shouldn't do work in our compiled code that we don't care about in the long run.

Here's a dumb example program (Line numbers added)

0:int main(int argc, char **argv)
1:{
2:  int foo = argc;
3:  if (foo < argc)
4:    return 1;
5:  int x = 0;
6:  return x;
7:}

(Assume that the return value will be a special variable called RETURN)

We can build a data structure that tells us

• argv is set on line 0. Dependant on "nothing" (function parameter).
• argc is set on line 0. Dependant on "nothing".
• foo is set on line 2. Dependant on argc from line 0.
• x is set on line 5. Dependant on foo from line 2 and argc from line 0.
• RETURN is set on 4,6. Dependant on foo from line 2, argc from line 0, and x from line 5.

Now for the optimizations!

Since nothing depends on argv, we don't need to pay attention to it. Since nothing changes x after its definition until RETURN uses it, we can replace RETURN's use of x with its definition. Since nothing changes foo after its definition until line 3 uses it, the foo in that line can be replaced with the defintion of foo.

So we can translate program to:

0:int main(int argc) // making a note to things that call main that they should drop their last arg
1:{
2:  int foo = argc;
3:  if (argc < argc)
4:    return 1;
5:  int x = 0;
6:  return 0;
7:}

If we re-evaluate this, we see nothing uses foo or x. Thus we can translate again into

0:int main(int argc)
1:{
2:  if (argc < argc)
3:    return 1;
4:  return 0;
5:}

A truly clever program could notice that the binary expression in line 2 always evaluates to false, and thus the if statement never executes. Thus we should be able to go

0:int main()
1:{
2:  return 0;
3:}

The halting point seems to me to be if we run "Simplify" and see no difference. ...This is not a particularly efficient algorithm though.