This is an archive of the discontinued LLVM Phabricator instance.

Modularizing LICM
ClosedPublic

Authored by ashutosh.nema on Jan 30 2015, 1:51 AM.

Details

Summary

LICM has ‘SinkRegion’, ‘HoistRegion’, ‘PromoteAliasSet’ as core features.
Currently these core features are tied up with LICM pass.
If someone wants any of these feature then he has to schedule LICM as a complete pass.
Also there is no way to call any of these feature in a pass.

This change is to expose LICM core functionalities as a utility.

Following is high level description of changes:

  1. Added declaration of ‘SinkRegion’, ‘HoistRegion’ and ‘PromoteAliasSet’ in ‘LoopUtils.h’
  1. Following members functions of LICM has moved out of class and marked as static functions. ‘inSubLoop’, ‘isNotUsedInLoop’, ‘canSinkOrHoistInst’, ‘hoist’, ‘sink’, ‘CloneInstructionInExitBlock’ ‘isSafeToExecuteUnconditionally’, ‘pointerInvalidatedByLoop’, ‘isGuaranteedToExecute’
  1. Updated these functions with their dependencies.
  1. LICM pass is now more like a wrapper pass, calling SinkRegion, HoistRegion, PromoteAliasSet utility.
  1. Caller to ‘SinkRegion’, ‘HoistRegion’ and ‘PromoteAliasSet should provide all the required arguments.

For now I kept everything to same LICM.cpp but later we can move ‘SinkRegion’, ‘HoistRegion’,
‘PromoteAliasSet’ and helper functions to separate utility file (i.e. LICMCore.cpp)

Please review this change, suggestions are welcome.

Diff Detail

Repository
rL LLVM

Event Timeline

ashutosh.nema retitled this revision from to Modularizing LICM.
ashutosh.nema updated this object.
ashutosh.nema edited the test plan for this revision. (Show Details)
ashutosh.nema added reviewers: reames, bruno.
ashutosh.nema set the repository for this revision to rL LLVM.
ashutosh.nema added a subscriber: Unknown Object (MLST).

I think this generally looks reasonable.

Please don't expose the MayThrow and HeaderMayThrow variables without also pulling out a utility routine to compute them (making a function out of the relevant part of LICM::runOnLoop is fine). Then encapsulate them into a structure. We could call this something like LICMSafetyInfo, and the routine could be called computeLICMSafetyInfo. These are really internal details, and I don't want multiple callers to replicate their logic, and we might want to extend this preprocessing in the future.

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

Don't include this header. Just add a forward declaration below.

18

Same here (it is only used by reference below).

79

Please include variable names here, leaving out the ones that are obvious from the type is fine, but the scalar parameters should have them for clarity.

(same for the ones below)

[Given that I'd like these parameters encapsulated, this comment is just for general reference]

lib/Transforms/Scalar/LICM.cpp
1038

Indenting looks odd here.

Thanks Hal for reviewing this change.
Your suggestions looks fine, will work on it.

Bruno, Philip:
If possible please review this change.

Regards,
Ashutosh

bruno edited edge metadata.Feb 2 2015, 2:33 PM

Hi,

The approach looks good. Aside from Hal's suggestions, only a few comments.

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

Please don't repeat the function/method in the comments. Use "\brief" instead. Also fix this issue in other places of the patch too.

lib/Transforms/Scalar/LICM.cpp
1050

Any specific reason why this was moved to the end of the file?

Thanks Bruno for reviewing this change.
Your suggestion looks fine, will work on it.

Comment at: lib/Transforms/Scalar/LICM.cpp:995
@@ +994,2 @@
+}

+

Any specific reason why this was moved to the end of the file?

'inSubLoop' & ' pointerInvalidatedByLoop' was member function of 'LICM'
These are defined in class itself. Its required to move these out of LICM class
Because these has usage in exposed utility & dependent routines (i.e. SinkRegion).
For now these are kept in same file, but later I'm planning to move these to
other utility file(i.e. LICMCore.cpp)

Regards,
Ashutosh

reames edited edge metadata.Feb 3 2015, 9:34 AM

With comments by others addressed, LGTM.

lib/Transforms/Scalar/LICM.cpp
440

This name is fine for now, but if this is exposed somewhere outside of LICM we'll need a clearer name. This isn't "safe to execute anywhere" its "safe to execute in the preheader".

Thanks Philip for reviewing this change.
I'm not planning to expose 'isSafeToExecuteUnconditionally' but we can change name of it.

Regards,
Ashutosh

ashutosh.nema added a reviewer: hfinkel.

Thanks Hal, Philip & Bruno for review.

Incorporated review comments.

Changes in this patch:

  1. Introduced 'LICMSafetyInfo', earlier 'MayThrow' & 'HeaderMayThrow' was exposed outside. But now 'SinkRegion', 'HoistRegion' and 'PromoteAliasSet' will compute safety information.
  2. Removed newly included headers in 'LoopUtils.h' Instead used forward declaration.
  3. Corrected indentation issues.
  4. Corrected comments to function by removing function names.
  5. Earlier return status of 'PromoteAliasSet' was not getting used, corrected to set 'Changed'.

Please check updated changes, your suggestions and comments are welcome.

hfinkel edited edge metadata.Feb 16 2015, 6:29 AM

Thanks Hal, Philip & Bruno for review.

Incorporated review comments.

Changes in this patch:

  1. Introduced 'LICMSafetyInfo', earlier 'MayThrow' & 'HeaderMayThrow' was exposed outside. But now 'SinkRegion', 'HoistRegion' and 'PromoteAliasSet' will compute safety information.

But this means that each of these functions now needs to re-scan the loop to compute the safety information. I was hoping to avoid this extra expense. Please expose LICMSafetyInfo, and the utility function to compute it.

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

Please describe here, and in the function descriptions below, what is expected to be in the AliasSetTracker.

Thanks Hal, your comments looks fine will incorporate.

Regards,
Ashutosh

ashutosh.nema edited edge metadata.

Over previous patch this change includes following:

  1. LICMSafetyInfo exposed outside with a utility computeLICMSafetyInfo to compute. Earlier 'SinkRegion', 'HoistRegion' and 'PromoteAliasSet' was computing it, re computation was extra expense, to avoid it now the caller to these can compute it and pass it as a argument.
  1. Updated comments to functions.
hfinkel added inline comments.Feb 17 2015, 1:09 AM
lib/Transforms/Scalar/LICM.cpp
75

You need this definition in the header or else no other client will be able to create one of these.

76

Move { to the end of the previous line.

84

Generically, we don't indent the contents of an anonymous namespace (this does not really matter here, because you need to move this struct to the header and not have it in an anonymous namespace).

Thanks Hal.
Sure I'll move ' LICMSafetyInfo' to a header file.
I'm planning to keep it in "LoopUtils.h".

Also can I move exposed functions(i.e. HoistRegion, SinkRegion, PromoteAliasSets & computeLICMSafetyInfo)
and dependent routines to a separate file under utils i.e. "lib/Transforms/Utils/LICMCore.cpp" ?

Regards,
Ashutosh

Thanks Hal.
Sure I'll move ' LICMSafetyInfo' to a header file.
I'm planning to keep it in "LoopUtils.h".

Also can I move exposed functions(i.e. HoistRegion, SinkRegion, PromoteAliasSets & computeLICMSafetyInfo)
and dependent routines to a separate file under utils i.e. "lib/Transforms/Utils/LICMCore.cpp" ?

We can move them, but please do that in a separate patch. The current scheme seems to be to have: lib/Transforms/Scalar/LICMPass.cpp and lib/Transforms/Utils/LICM.cpp.

Regards,
Ashutosh

We can move them, but please do that in a separate patch.
The current scheme seems to be to have: lib/Transforms/Scalar/LICMPass.cpp and lib/Transforms/Utils/LICM.cpp.

Sure, will do it in separate patch.

Regards,
Ashutosh

Over previous patch this change includes following:

  1. struct LICMSafetyInfo moved to LoopUtils.h.
hfinkel added inline comments.Feb 17 2015, 6:13 AM
include/llvm/Transforms/Utils/LoopUtils.h
75

Please improve the description of what needs to be in the AliasSetTracker. Should it contain all memory accesses in the loop?

100

This function seems poorly named given its description as, "Try to promote memory values to scalars by sinking stores out of the loop and moving loads to before the loop." Maybe promoteLoopAccessesToScalars?

Comment at: include/llvm/Transforms/Utils/LoopUtils.h:85
@@ +84,3 @@
+/ iteration. Takes DomTreeNode, AliasAnalysis, LoopInfo,
+DominatorTree,
/ DataLayout, TargetLibraryInfo, Loop, AliasSet

+information for the input loop /// and loop safety information as argument. It returns changed status.

Please improve the description of what needs to be in the AliasSetTracker.
Should it contain all memory accesses in the loop?

Sure Hal, will add more explanation here.
Here alias set information for all the instructions in loop.

+bool promoteAliasSet(AliasSet &, SmallVectorImpl<BasicBlock*> &,
+ SmallVectorImpl<Instruction*> &,
This function seems poorly named given its description as, "Try to promote
memory values to scalars by sinking stores out of the loop and moving loads
to before the loop." Maybe promoteLoopAccessesToScalars?

Looks OK, will update accordingly.

Regards,
Ashutosh

Over previous patch this change includes following:

  1. Updated function description.
  2. Changed name of 'PromoteAliasSet' to 'promoteLoopAccessesToScalars'.
hfinkel accepted this revision.Feb 19 2015, 8:17 PM
hfinkel edited edge metadata.

LGTM, thanks!

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

all instructions of loop -> all instructions of the loop

This revision is now accepted and ready to land.Feb 19 2015, 8:17 PM
ashutosh.nema edited edge metadata.

Thanks Hal, incorporated your comment.

This is my first changes on llvm, and I don’t have checkin rights.

Also not very sure about checkin process, If possible can you make checkin for me ?

Regards,
Ashutosh

hfinkel closed this revision.Feb 22 2015, 10:37 AM

r230178, thanks!