This is an archive of the discontinued LLVM Phabricator instance.

Make processInstruction from LCSSA.cpp externally available.
ClosedPublic

Authored by mzolotukhin on Jul 14 2016, 12:47 PM.

Details

Summary

When a pass tries to keep LCSSA form it's often convenient to be able to update
LCSSA for one instruction rather than for the entire loop. This patch makes the
processInstruction from LCSSA externally available under a name
formLCSSAForInstruction. The API is almost unchanged, and I'm open to
suggestions how to make it better. Currently for instance we have a couple of
arguments whose purpose might be not obvious for the routine user.

Diff Detail

Event Timeline

mzolotukhin retitled this revision from to Make processInstruction from LCSSA.cpp externally available..
mzolotukhin updated this object.
mzolotukhin added reviewers: chandlerc, sanjoy, hfinkel.
mzolotukhin added a subscriber: llvm-commits.
chandlerc edited edge metadata.Jul 14 2016, 3:25 PM

Should the declaration for this go into LCSSA.h instead of into LoopUtils.h?

include/llvm/Transforms/Utils/LoopUtils.h
326

No need for '\brief'.

332–334

They aren't just preserved. The CFG isn't mutated, and it might be useful to explicitly call that out.

lib/Transforms/Utils/LCSSA.cpp
191–194

At least for the one caller of this here, fixing this FIXME would also eliminate the need for the exit blocks and pred cache parameters. Would it eliminate the need for them in the other call sites you have in mind?

mzolotukhin edited edge metadata.
  • Replace recursion with a worklist.
  • Rebase on ToT.
  • Remove no longer needed arguments.
  • Remove \brief.
mzolotukhin marked 3 inline comments as done.Jul 14 2016, 9:38 PM

Hi Chandler,

Thanks for taking a look! I updated the patch: now we need less arguments and don't have that recursion.

Michael

I think you need to accept the worklist as an argument, so that the cache (and exit blocks) can be shared across what are in this patch repeated top-level invocations (in addition to the recursive aspect).

Essentially, we should walk the loop push each instruction into a worklist, and then call this routine on that to process it until all the instructions are in LCSSA form.

  • Accept worklist of instructions instead of a single instruction as an argument.
  • Some formatting fixes.
chandlerc accepted this revision.Jul 14 2016, 11:59 PM
chandlerc edited edge metadata.

LGTM with a tweak below. Also see my note about the exit blocks.

lib/Transforms/Utils/LCSSA.cpp
77–78

Hoist these outside the loop and clear them on each iteration?

84–85

Wow, I really didn't think about how costly this'll end up being...

I think your patch is probably fine as-is because the exit blocks lists are probably pretty small in practice.

But I think in a follow-up patch we should change this to use a better API. The fact that the LoopInfo analysis just populates a small vector is pretty horrible. We should add a nice iterator that just walks the exit blocks and use that so there is no copying or churn here. Then I think the worklist becomes a complete win. It should also mean you can do stuff across multiple loops if useful here without really stressing about it.

Does that make sense to you?

This revision is now accepted and ready to land.Jul 14 2016, 11:59 PM
This revision was automatically updated to reflect the committed changes.