[tree-ssa] DCE and conditionals

[Andrew MacLeod <amacleod at redhat dot com>]

I think we need to change the dce optimization slightly. When we turn on
copy propagation, we get an interesting situation:


before copy-prop, we see:

# BLOCK 13 (d.c:26).  PRED: 12 11.  SUCC: 15 14.
                #   iftmp.18_22 = PHI <iftmp.18_84(11), p_83(12)>;
                if (y_46 < iftmp.18_22)
                  {
                    
                    # BLOCK 14 (d.c:48).  PRED: 13.  SUCC: 16.
                    iftmp.19_87 = y_46
                  }
                else
                  {
                    
                    # BLOCK 15 (d.c:48).  PRED: 13.  SUCC: 16.
                    iftmp.19_88 = iftmp.18_22
                  };
                
                # BLOCK 16 (d.c:48).  PRED: 15 14.  SUCC: 18 17.
                #   iftmp.19_26 = PHI <iftmp.19_87(14), iftmp.19_88(15)>;
                p_89 = iftmp.19_26;


When we propagate some copies, we see:

# BLOCK 13 (d.c:26).  PRED: 12 11.  SUCC: 15 14.
                #   iftmp.18_22 = PHI <iftmp.18_84(11), p_83(12)>;
                (void)0;
                if (y_46 < iftmp.18_22)
                  {
                    
                    # BLOCK 14 (d.c:48).  PRED: 13.  SUCC: 16.
                    iftmp.19_87 = y_46
                  }
                else
                  {
                    
                    # BLOCK 15 (d.c:48).  PRED: 13.  SUCC: 16.
                    iftmp.19_88 = iftmp.18_22
                  };
                
                # BLOCK 16 (d.c:48).  PRED: 15 14.  SUCC: 18 17.
                #   iftmp.19_26 = PHI <y_46(14), iftmp.18_22(15)>;
                p_89 = iftmp.19_26;


So dead code comes along, and now both branches of the conditional are
dead, DCE happily deletes them, and then deletes the conditional too. 

Unfortunately, we can't delete the conditional. We have 2 different
values coming in on the PHI node which will definately not coalesce to
the same variable.  That means the conditional *is* still required, even
though it looks like it isn't.

So we have a few choices. Im not really interested in trying to handcuff
copy propagation. Its doing the right thing. This is the reason the out
of ssa pass exists. If one or both of those copies are required in the
end, they will be inserted as long as the CFG skeleton hasn't been
ruined.  

I would say when we have a PHI that DCE decides is required, we need to
check the blocks of the incoming edges to the PHI's block, and if the
last stmt in the parent of those predecessor blocks is a COND_EXPR or a
SWITCH_EXPR, we have to mark that instruction as necessary.
(linearize_condition_expr also needs to be taught that if an IF has an
empty then and else block, it still can't be removed if there is a PHI
node in the immediate postdominator of the if.)

That fixes this problem, but there is a side effect. If both values
coming into the PHI work out to the same value, then we've kept the
conditional and the instructions feeding it live for no good reason at
all.

That means we want someone, perhaps a very fast little pass of its own
that we can call when we want it, that goes into PHI nodes, looks at
them, and decides when they can be replaced with a copy.

ie, if it saw 
   #   iftmp.19_26 = PHI <iftmp.18_22(14), iftmp.18_22(15)>,

it could replace the PHI with
    iftmp.19_26 = iftmp.18_22

Then DCE could eliminate the conditional feeding the PHI node.  I
suspect this case is less common, however.

We're still left with what I think is the more common case, where the
PHI value looks more like:

    #   iftmp.18_26 = PHI <iftmp.18_24(14), iftmp.18_22(15)>
  
So we have to keep the PHI live, which keeps the conditional live.
However, when coalescing registers, we might discover that all 3 of
these values are going to coalesce to iftmp.18.

That means the out-of-ssa pass has made the conditional and all it's
feeding instructions dead. But its too late, we're out of SSA form now.

So we might be able to improve on our little "quick-phi-elimination"
pass, and give it an optional var_map. We can call it from the
out-of-ssa pass with the coalesced var_map. No instructions have been
re-written yet, but we do have our mapping ready on how we are going to
re-write it.

The phi-eliminator could then determine that all incoming parameters to
a PHI are going to be coalesced together, and eliminate the PHI node,
replacing it with a copy from one of the coalesced parameters, if
necessary.

We would then run DCE one final time before rewriting. Eliminating more
instructions isn't going to cause our partition mapping to be invalid,
the worst thing that would happen is we miss a coalesce that might now
be possible. I would again think that case would be rather rare.

That means we'd be running DCE just before rewrite, and again part way
through it. (We'd only run it the second time if the phi-eliminator said
it removed something of interest.) ( I suspect the phi eliminator should
also be called from cleanup_cfg(), if it isn't already doing something
like that)

Do you think this is reasonable, or is there a better way to do this?

Andrew.

PS then we have a case like :



if (t_5>0)
  a_2 = a_1;
else
  a_3 = a_0;
lab:
  a5 = PHI (a_2, a_3, a_4)  /* a_4 comes in from a goto lab:.  */

if these all coalesce together, the out-of-ssa DCE call would then
eliminate this PHI as well. This conditional would be very hard to
eliminate any other way