This is the mail archive of the mailing list for the GCC project.

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: mark_operand_necessary in tree-ssa-dce.c

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
necessary. And if it was already marked as necessary, we return before
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
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

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?


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]