This is an archive of the discontinued LLVM Phabricator instance.

[RDA] Don't explicitly store outgoing reaching defs (NFCI)
Needs ReviewPublic

Authored by nikic on Apr 7 2020, 1:27 PM.

Details

Summary

We currently explicitly store the last reaching def at the end of a basic block. However, this information is already available as the last element in the reaching definitions vector -- they only differ in whether the reaching def is relative to the start or the end of the basic block.

This patch removes the separate MBBOutRegsInfos and instead computes the incoming reaching defs on the fly. For that purpose it does cache the number of (non-debug) instructions in each block.

Assuming D77513 as baseline, this drops the memory requirement per basic block per reg unit from 12 to 8 bytes, which makes for an extra 1% saving on sqlite compilation. It's not completely free (with about 0.05% increase in instructions retired), but that seems like a good tradeoff.

Diff Detail

Event Timeline

nikic created this revision.Apr 7 2020, 1:27 PM
Herald added a project: Restricted Project. · View Herald TranscriptApr 7 2020, 1:27 PM
samparker added inline comments.Apr 8 2020, 7:59 AM
lib/CodeGen/ReachingDefAnalysis.cpp
98

Maybe now would be a good time to encapsulate these MBB details in their own class, instead of several separate vectors and a vector of vectors?

nikic marked an inline comment as done.Apr 8 2020, 2:03 PM
nikic added inline comments.
lib/CodeGen/ReachingDefAnalysis.cpp
98

I'm planning to submit one more patch (last one, I promise!) that changes the reaching def storage from MBBNumber => RegUnit => Defs to RegUnit => MBBNumber => Defs, because that allows us not to allocate any storage for register units that are unused in a function. Prototype implementation at https://gist.github.com/nikic/45d4c76338637331bd7048348398833d. Haven't put this up yet, because I didn't measure an actual max-rss improvement with it. I suspect that RDA memory usage is now low enough that the peak memory usage moved somewhere else.

In any case, with that patch the reaching defs storage would not be indexed by MBBNumber first anymore, so it would have to be separate from the NumInsts storage.

samparker added inline comments.Apr 14 2020, 2:24 AM
lib/CodeGen/ReachingDefAnalysis.cpp
98

Okay. Maybe another way to make this code a bit easier to follow would be to make getIncomingReachingDef take the Unit and the predecessor?