Page MenuHomePhabricator

[LCSSA] Don't let SSAUpdater to break LCSSA during LCSSA construction.
Needs ReviewPublic

Authored by mzolotukhin on Jan 10 2017, 2:07 PM.



This change essentially does the following:

  1. Factors out formLCSSAForOneInstruction, so that we can use the same instance of SSAUpdate for all rewritings corresponding to the same instruction.
  2. Starts to use a stricter check than just SSAUpdate.HasValueForBlock: we need to process the value even if SSAUpdater thinks it's available unless it's a PHI-node defined in this block.

(1) allows us to avoid generating duplicate phi-nodes in the same BB for
the same instruction - we did this because we cleared SSAUpdater on
every iteration in our Worklist loop. Now we only clear it once, before
processing an instruction.
(2) makes sure that we still generate LCSSA phi-nodes even in cases
where SSAUpdater thinks we have an available value.

Event Timeline

mzolotukhin retitled this revision from to [LCSSA] Don't let SSAUpdater to break LCSSA during LCSSA construction..
mzolotukhin updated this object.
mzolotukhin added reviewers: chandlerc, sanjoy, davide.
mzolotukhin added a subscriber: llvm-commits.
chandlerc edited edge metadata.Jan 19 2017, 4:11 PM

Thanks for the ping!


The only hesitation I really have here is that this makes us do a lot more memory allocations when we're rewriting a lot of instructions with a lot of uses.

Is it worthwhile to try and share the worklists in some way? Have you looked at whether this worklist is just always small and so it doesn't matter in practice?

mzolotukhin added inline comments.Jan 19 2017, 4:32 PM

Frankly, I haven't thought about that -- thanks for pointing this out!
We can have a single worklist object, which we'll pass to this function, and that should get rid of allocations you are concerned about. We cannot use the same worklist as in formLCSSAForInstructions though - we clear SSAUpdater when we leave formLCSSAForOneInstruction, and we leave it when the worklist is empty. If we want to reuse worklist from the upper function, we need to somehow introduce boundaries at which we need to clear SSAUpdater, and I don't see a good way to do it.

If that makes sense to you, I'll update the patch so that we don't create a new worklist for every invocation of formLCSSAForOneInstruction.

chandlerc added inline comments.Jan 19 2017, 4:37 PM

Yeah, that makes sense.

Do we ever really want formLCSSForOneInstruction? I wonder if we should just leave the single function and scope the SSAUpdater more tightly. Happy to leave the code structuring question up to you though.

sanjoy added inline comments.Jan 19 2017, 4:39 PM

Note: this cache become less effective since we're not reusing it for the entire worklist anymore.


Why is it legal to re-use the same SSAUpdater to rewrite uses for these newly inserted PHIs? Asking mostly because earlier SSAUpdate would get reset for each iteration of the inner loop on the worklist.


(Fix separately without review if you agree) Why not just a range for over an ArrayRef<Instruction *>?