This is an archive of the discontinued LLVM Phabricator instance.

[LCSSA] Perform LCSSA verification only for current loop nest
ClosedPublic

Authored by igor-laevsky on Oct 21 2016, 10:30 AM.

Details

Summary

This change continues fixing compile time issues with LCSSA verification (started in https://reviews.llvm.org/D25364)

Currently after running pass on a single loop-nest we run LCSSA verification for all
loops in the function. This proves to be overly expensive and often not needed since
we were changing only single loop nest. Instead I propose to adopt same technique as was
used for the LoopInfo verification. We will explicitly call LCSSA verification for each
loop nest as part of the LPPassManager iteration.

This is a bit non trivial due to the fact that not all loop passes require LCSSA. See
LoopPassPrinter for example. This means that before doing verification we need to check
if LCSSA was preserved by the current pass. In order to do this we can ask "mustPreserveAnalysisID(LCSSAID)".
Unfortunately LCSSA is part of the TransformsUtils library which depends on Analysis
library and we can't reference LCSSAID without introducing cyclic library dependence.

In order to overcome this problem I've added new analysis pass called "LCSSAVerificationPass".
It's transitively required by the LCSSA transform and preserved by all loop passes. It's
only purpose is to indicate to the LPPassManager when we need to run LCSSA verification
and when we don't.

This solution feels a bit wrong and error prone (it's enough to forget to preserve
LCSSAVerificationPass in order to miss verification). However we discussed this in
the "LCSSA verification for the top-level loops" llvm-dev thread and it seemed like
the best one.

Diff Detail

Event Timeline

igor-laevsky retitled this revision from to [LCSSA] Perform LCSSA verification only for current loop nest.
igor-laevsky updated this object.
igor-laevsky added a subscriber: llvm-commits.
igor-laevsky updated this object.
igor-laevsky added a reviewer: bogner.
mzolotukhin accepted this revision.Oct 27 2016, 12:09 PM
mzolotukhin edited edge metadata.

Hi Igor,

Sorry for the delay in review. We've discussed this issue already, and the patch does seem like what we agreed on (modulo minor nitpicks).

However, I still feel uneasy about a couple of things. First, adding an extra fake pass for LCSSA verification looks really awkward (I have read the explanation you provided). Second, this all is caused by the fact that not all passes currently require LCSSA, but I'd rather change that, even independently on the patch in question. Do we have other loop passes, except the printer pass, that don't require LCSSA?

Also, related, but not affecting the patch question: what are the slowdowns that you see with full verification after you fixed the recursive verification routine?

I think that this patch can be committed so that your work is no longer affected by the slowdowns, but I would like to continue this discussion and consider other solutions again.

Thanks,
Michael

include/llvm/Analysis/LoopPass.h
160

s/lcssa/LCSSA/

include/llvm/InitializePasses.h
171

This change looks unnecessary (there are no spaces before & in lines below anyway).

lib/Transforms/Utils/LCSSA.cpp
336

s/lcssa/LCSSA/
Let's be consistent :-)

This revision is now accepted and ready to land.Oct 27 2016, 12:09 PM
This revision was automatically updated to reflect the committed changes.

Hi Michael,

Thanks for the comments!

With linearized implementation of the LCSSA verification we were still experiencing slowdown of the same order of magnitude (10x).

Besides printers there are IVUsers, LoopExtractor and LoopStrengthReduce passes which don't require LCSSA. I don't think it's a big problem if we add explicit LCSSA dependence to them. My biggest concern was about loop printers because there we really want to print ir exactly as it is. It would seem quite unexpected if printer pass will suddenly transform the IR.