Re: mark_operand_necessary in tree-ssa-dce.c

[Daniel Berlin <dberlin at dberlin dot org>]

On Thu, 27 Jan 2005, Jeffrey A Law wrote:

> On Wed, 2005-01-26 at 15:08 -0500, Daniel Berlin wrote:
> > Can someone (ben, i think you wrote this code) please explain to me
> why we
> > require a processed sbitmap in this function?
> >
> > ISTM that if we are here, we are going to always mark the statement
> as
> > necessary. And if it was already marked as necessary, we return before
> we
> > put it on the worklist again anyway.
> I'm not sure your logic is correct.
>
> > My thinking goes like this:
> >
> > 1 If the processed bit is true, we would have returned 3 lines
> > later anyway, because the only time the processed bit can be already
> true
> > is when necessary is true.
> Not true.  Consider the case where PHIONLY is true and STMT is not a phi
> node.  We would have marked the SSA_NAME as necessary,

1. PHIONLY can only be true when we are marking must-def kill phis, which 
is done after we have marked the regular statements and phis, but not 
must-def kill operands (becase the regular code doesn't mark those 
because they are not necessary *unless* we have to keep the phi around to 
merge the killed versions)
 2. PHIONLY won't mark non-phi nodes as necessary.
Therefore, if STMT is not a phi node, it won't mark it.
3. Any SSA_NAME it has seen when phionly is true must be necessary, or it 
wouldn't be in a necessary statement, and we never would have called this 
function on it with PHIONLY true (see mark_really_necessary_kill_operands)

>  but the
> underlying statement may not be marked as necesssary.

We only mark the kill operands of statements that are necessary
see mark_really_necessary_kill_operands

> If we ever call
> mark_operand_necessary with the same SSA_NAME again we will return
> without ever setting NECESSARY for the PHI node.

This can only be true if you mixed phionly and not phionly.
This doesn't happen, and would cause other breakage.

Otherwise, it would hit see it was not a phi, and DTRT,
or it would be a PHI, and we *would* have to mark it, which is the right 
thing.

Remember, if we had seen this before the 
mark_really_necessary_kill_operand_phis code, it would have properly been 
marked necessary, and it would be returning anyway.

> If we dropped PROCESSED bitmap, then we would mark the PHI node as
> necessary in that case.



> Which I believe would keep PHIs around that
> are unnecessary (see the comment before
> mark_really_necessary_kill_operand_phis

I added this code, and the comment.  The code was added not to remove
*more* phi nodes, but to remove *less* phi nodes.
When we added a kill operand to the must-def to say what version it 
killed, that kill operand was
1. Not a use, and therefore, shouldn't be followed by the regular dce 
marking code.
2. Has to be kept valid.

The kill operand may be a phi result if we are killing the merge of two 
versions.

However, since that isn't a use, the normal dce marking code would mark 
these phis as unnecessary (which may or may not be true, depending on what 
other code it was going to remove).

The two options were to remove all the phi nodes it wanted, and 
let the rewriter sort it out and reinsert phi nodes, or do something 
smarter, which was to determine which phi nodes we still needed by the 
kill operands of the necessary statements, which is what the rewriter 
would have rediscovered and inserted for us anyway.

We chose the "do something smarter" option.
The rewriter is only called to fix the must-def-kill reaching 
definitions, not to insert phi nodes.

mark_really_necessary_kill_operands goes through all the now-necessary 
statements (IE what DCE doesn't plan on removing), and figures out which 
of the kill phis are going to be alive, and marks them necessary, to avoid 
having the renamer calculate dominance frontiers, and then decide it 
needs to reinsert the exact same phi nodes anyway :).

Would it convince you if i bootstrapped/regtested  with and without the 
patch, dumping the number of phi nodes after DCE, and verifying that it doesn't 
cause us to keep a single extra phi node?

--Dan