[PATCH]: Implement must-def kill operand

[Daniel Berlin]

On Oct 20, 2004, at 1:56 PM, Diego Novillo wrote:

> On Wed, 2004-10-20 at 13:53, Daniel Berlin wrote:
>
>> I assume nobody really had much problem with the *other* parts of the
>> patch?
>>
> The rest looked OK to me.  It was just the needed mechanical changes to
> support an RHS in V_MUST_DEFs.
>

Actually, we forgot a part.
Currently, all arguments used in v_must_def rhs's are marked as 
unnecessary.

This is done so that

<maybe_dead statement>
<dead_statement>
<use of dead statement result in v_must_def>

Doesn't result in dead statement being kept alive.

However, if the result of dead-statement is a phi node, the phi node 
itself may need to be kept alive (but not it's feeding statements).
p_9 == default_def here
I've elided the non-p, non def'ing p statements.


# BLOCK 2
# PRED: 6 [64.6%]  (true) 3 [89.0%]  (dfs_back,true)
# p_2 = PHI <p_17(3), p_9(6)>;
<L1>:;
#   p_15 = V_MUST_DEF <p_2>;
   p = D.4836_14;
#   p_17 = V_MAY_DEF <p_15>;
   f_11 ();
# SUCC: 3 [100.0%]  (fallthru)

# BLOCK 3
# PRED: 2 [100.0%]  (fallthru)
   <L5>:;
#   VUSE <p_17>;
   p.25_24 = p;
...
# SUCC: 4 [11.0%]  (loop_exit,false) 2 [89.0%]  (dfs_back,true)


# BLOCK 6
# PRED: 1 [100.0%]  (fallthru)
<L6>:;
#   VUSE <p_9>;
p.25_29 = p;
# SUCC: 2 [64.6%]  (true) 4 [35.4%]  (false)


Because no  kill operands are marked as necessary, dce decides p_2 is 
dead.
But p_2 is necessary, because it's arguments aren't dead, so we have 
nothing to put in the RHS of the kill otherwise.
It's just that the only use of p_2 is in a must-def rhs.
If we let DCE delete that phi, the renamer will put it back, because 
it's necessary to rename the rhs of the must_def.
So we have a couple of options for handling this:

1. Do a quick propagation pass in DCE to make sure def-def phis that 
are used in necessary statements don't die. (at that point, plain 
def-def renaming will work)
2. Mark the must-def operand as necessary if it's a phi, and the only 
immediate use of the phi is in the must-def operand (I'm assuming it 
could appear in a may-def or vuse somewhere else, in which case it's 
necessary).
3. Use the full renamer, which will simply put the phi back after DCE 
removes it.

Welcome to the beginning of the circle again :)
--Dan