DOM doesn't notice some equivalences through phis

DOM doesn't notice some equivalences through phis

[Daniel Berlin]

While working on GVN-PRE, I was originally planning on skipping the 
"eliminate" phase (which just eliminates the now fully redundant 
values), and letting DOM handle it.
But I can't, because DOM doesn't seem to notice they are now equivalent.

Here is a hand-constructed example that is the same as the code GVN-PRE 
generates prior to elimination:
int main(int argc, char **argv)
{
    int a;
     int b=argc + 13;
     int c=argc + 5;
     int pretmp;
     a = b + c;
     pretmp = a;
     /* Prevent DCE from removing our first occurrence */
     printf("%d\n", a);
     if (argc < 2)
     {

     }
     else
     {
         b = argc + 4;
         pretmp = b + c;
     }
     a = b + c;
     /* Prevent DCE from removing our second occurrence */
     printf("%d\n", a);
     /* Prevent DCE from removing the pretmp. */
     printf ("%d\n", pretmp);
}

Dom refuses to replace the second b + c with pretmp, even though they 
have the same value.

The SSA form of the above is

;; Function main (main)

main (argc, argv)
{
   int pretmp;
   int c;
   int b;
   int a;

   # BLOCK 0
   # PRED: ENTRY (fallthru)
<bb 0>:
   b_4 = argc_3 + 13;
   c_5 = argc_3 + 5;
   a_6 = b_4 + c_5;
   pretmp_7 = a_6;
   printf ("%d\n", a_6);
   if (argc_3 > 1) goto <L0>; else goto <L1>;

   # BLOCK 1
   # PRED: 0 (true)
<L0>:;
   b_9 = argc_3 + 4;
   pretmp_10 = b_9 + c_5;


   # BLOCK 2
   # PRED: 1 (fallthru) 0 (false)
   # pretmp_2 = PHI <a_6(0), pretmp_10(1)>;
   # b_1 = PHI <b_4(0), b_9(1)>;
<L1>:;
   a_8 = b_1 + c_5;
   printf ("%d\n", a_8);
   printf ("%d\n", pretmp_2);
   return;


(This has a critical edge that gets split, but this dump is from dom1.  
dom3, which runs after PRE, removes the empty BB from the split edge 
anyway.  Leaving that block in has no effect on whether b_1 + c_5 is 
eliminated)

pretmp_2's PHI has exactly the same values at the same points in the 
program as b_1 + c_5.

It might be a bit expensive to handle this case.
It has to, when it sees b_1 in the expression is defined by a phi, 
back-translate it on each predecessor, and see if it has an available 
expression for the translated expression (b_4 + c_5 in pred block 0, 
b_9 + c_5 in pred block 1) in each predecessor.
That would tell it that it has b_4 + c_5 available out of a_6 in 
predecessor block 0, and b_9 + c_5 available out of predecessor block 
1.
Then it could either introduce a new no-cost phi for those values, or 
see if one exists (honestly, it's probably cheaper to just introduce a 
new phi, even though one exists already in the form of the pretmp phi. 
Checking all the phis for the right values wouldn't be cheap).

I'm not sure how often it comes up, and i can take care of it as part 
of GVN-PRE, but it just means GVN-PRE will catch standard eliminations 
that DOM could, but doesn't.  And it means i can't let DOM just take 
care of eliminating the fully redundant expressions, which would have 
been nice in terms of code reuse.
Thoughts?
--Dan