This is an archive of the discontinued LLVM Phabricator instance.

[PredicateInfo] Factor out PredicateInfoBuilder (NFC)
ClosedPublic

Authored by nikic on Apr 16 2020, 1:28 PM.

Details

Summary

When running IPSCCP on a module with many small functions, memory usage is currently dominated by PredicateInfo, which is a huge structure (partially due to some unfortunate nested SmallVector use). However, most of it is actually only temporary analysis state, and does not need to be retained after initial construction.

This patch factors the temporary state out into a separate structure that is only live during the analysis.

Diff Detail

Event Timeline

nikic created this revision.Apr 16 2020, 1:28 PM
Herald added a project: Restricted Project. · View Herald TranscriptApr 16 2020, 1:28 PM
fhahn added inline comments.Apr 16 2020, 2:21 PM
include/llvm/Transforms/Utils/PredicateInfo.h
191–192

Could all those helpers be moved into State?

That way, we would not need to thread the parameter through the code and we would even more cleanly separate the build phase. If it is possible to move the construction parts into State, it might make sense to rename it to something like PredicateInfoBuilder and PredicateInfo itself would only contain PredicateMap, CreatedDeclarations, AllInfos. The builder could hold references to those.

nikic marked an inline comment as done.Apr 16 2020, 2:36 PM
nikic added inline comments.
include/llvm/Transforms/Utils/PredicateInfo.h
191–192

That should be possible, if we pass a PredicateInfo reference into State (and make it a friend class), so that we have access to AllInfos etc. I'll give it a try.

nikic updated this revision to Diff 258381.Apr 17 2020, 11:29 AM
nikic retitled this revision from [PredicateInfo] Factor out temporary state (NFC) to [PredicateInfo] Factor out PredicateInfoBuilder (NFC).

Move most state & logic into PredicateInfoBuilder

fhahn accepted this revision.Apr 18 2020, 6:29 AM

LGTM, thanks! As noted I think it would be slightly better to keep passing the OpsToRename explicitly, but I don't feel too strongly about that

lib/Transforms/Utils/PredicateInfo.cpp
493

I think it would be slightly better to keep passing OpsToRename to various places, as it makes things a bit more explicit; that's the main list op operations to rename.

This revision is now accepted and ready to land.Apr 18 2020, 6:29 AM
nikic marked an inline comment as done.Apr 18 2020, 7:20 AM
nikic added inline comments.
lib/Transforms/Utils/PredicateInfo.cpp
493

Hm, why do you think that OpsToRename should be handled differently than other state like ValueInfo?

In fact, now that I look a bit more closely at this, I think there's some duplication going on here, in that the values stored in OpsToRename should be the same as the keys of ValueInfoNums. I guess this is stored separate to preserve order?

fhahn added inline comments.Apr 18 2020, 12:27 PM
lib/Transforms/Utils/PredicateInfo.cpp
493

Hm, why do you think that OpsToRename should be handled differently than other state like ValueInfo?

I think passing it to renameUses makes it clearer at the call site & function signature *what* uses are renamed, although it's true that it currently queries some other information as well. I have a few patches somewhere, which expose renameUses for general SSA renaming and there it would be convenient to just pass in the list of uses to rename.

In fact, now that I look a bit more closely at this, I think there's some duplication going on here, in that the values stored in OpsToRename should be the same as the keys of ValueInfoNums. I guess this is stored separate to preserve order?

ValueInfoNums maps values to their ValueInfo entry and I think it is used to ensure that there's a single ValueInfo per value. I guess alternatively we could just use a map Value* -> ValueInfo, but then we would have to iterate over the keys of the map. That would safe sizeof(unsigned) per value to rename, but iterating over the keys in the map should be more expensive in terms of runtime.

nikic updated this revision to Diff 258550.Apr 18 2020, 1:05 PM

Keep OpsToRename as explicit argument.

nikic marked an inline comment as done.Apr 18 2020, 1:18 PM
nikic added inline comments.
lib/Transforms/Utils/PredicateInfo.cpp
493

I think passing it to renameUses makes it clearer at the call site & function signature *what* uses are renamed, although it's true that it currently queries some other information as well. I have a few patches somewhere, which expose renameUses for general SSA renaming and there it would be convenient to just pass in the list of uses to rename.

Fair enough, I've changed the code back to pass OpsToRename explicitly.

ValueInfoNums maps values to their ValueInfo entry and I think it is used to ensure that there's a single ValueInfo per value. I guess alternatively we could just use a map Value* -> ValueInfo, but then we would have to iterate over the keys of the map. That would safe sizeof(unsigned) per value to rename, but iterating over the keys in the map should be more expensive in terms of runtime.

I think the split into ValueInfoNums and ValueInfos here is because ValueInfo is large, so storing it in a DenseMap is inefficient. Using a DenseMap of integers that index into a separate vector avoids that.

This revision was automatically updated to reflect the committed changes.