Page MenuHomePhabricator

[LiveDebugVariables] Add cache for SkipPHIsLabelsAndDebug to prevent iterating the same set of PHI/LABEL/Debug instructions repeatedly.
ClosedPublic

Authored by wmi on Jan 19 2021, 9:58 AM.

Details

Summary

We run into a compiling timeout problem when building a target after its SampleFDO profile is updated. It is because some very large blocks with a bunch of PHIs at the beginning. LiveDebugVariables::emitDebugValues called during VirtRegRewriter phase searchs the insertion point for those large BBs repeatedly in SkipPHIsLabelsAndDebug, and each time SkipPHIsLabelsAndDebug needs to go through the same set of PHIs before it can find the first non PHI/Label/Debug instruction as an insertion point. This patch adds a cache to save the last position for the sequence which has been checked in the previous call of SkipPHIsLabelsAndDebug.

Diff Detail

Event Timeline

wmi created this revision.Jan 19 2021, 9:58 AM
wmi requested review of this revision.Jan 19 2021, 9:58 AM
Herald added a project: Restricted Project. · View Herald TranscriptJan 19 2021, 9:58 AM
wmi added a comment.Thu, Jan 28, 12:17 PM

friendly ping.

dblaikie added inline comments.Thu, Jan 28, 1:51 PM
llvm/lib/CodeGen/LiveDebugVariables.cpp
1310–1316

Could you store iterators in the map instead of pointers? Would save having to do the &* dance on the way in and the MachineBasicBlock::iterator dance on the way out?
Also, it'd be good to avoid the extra BBSkipInstsMap lookup, if possible. Would this work?

auto& I = BBSkipInstsMap.insert(MBB, MBB->begin()).first->second;
I = MBB->SkipPHIsLabelsAndDebug(I);
return I;
wmi added inline comments.Thu, Jan 28, 3:38 PM
llvm/lib/CodeGen/LiveDebugVariables.cpp
1310–1316

Could you store iterators in the map instead of pointers? Would save having to do the &* dance on the way in and the MachineBasicBlock::iterator dance on the way out?

Good idea. MachineBasicBlock is an ilist so iterator should be valid after new instruction is inserted if ilist has the same property as std::list.

Also, it'd be good to avoid the extra BBSkipInstsMap lookup, if possible. Would this work?
auto& I = BBSkipInstsMap.insert(MBB, MBB->begin()).first->second;
I = MBB->SkipPHIsLabelsAndDebug(I);
return I;

That may not work. If we insert MBB->begin() into the map, after the last call of SkipPHIsLabelsAndDebug, there may be new non-phis/non-labels/non-debuginstrs inserted at the beginning of MBB and the old begin iterator saved in the map will become stale. When we call SkipPHIsLabelsAndDebug next time, it will skip those non-phis/labels/debug instructions which is not welcomed.

Note for the case that the return value of SkipPHIsLabelsAndDebug is not MBB->begin(), we will save std::prev of the returned iterator because the newly inserted instructions after last call of SkipPHIsLabelsAndDebug will be searched next time.

wmi updated this revision to Diff 319994.Thu, Jan 28, 4:40 PM

Address dblaikie's comment.

dblaikie accepted this revision.Thu, Jan 28, 5:27 PM
dblaikie added inline comments.
llvm/lib/CodeGen/LiveDebugVariables.cpp
1310–1316

Hmm, not quite following.

after the last call of SkipPHIsLabelsAndDebug, there may be new non-phis/non-labels/non-debuginstrs inserted at the beginning of MBB and the old begin iterator saved in the map will become stale. When we call SkipPHIsLabelsAndDebug next time, it will skip those non-phis/labels/debug instructions which is not welcomed.

Wouldn't that problem exist also... oh, I see. That's why you go back by 1.

Hmm. I guess if the map contained Optional<iterator> values it might look like this:

auto &O = BBSkipInstsMap[MBB];
auto B = MBB->Begin();
auto I = MBB->SkipPHIsLabelsAndDebug(O ? std::next(*O) : B);
if (I != B)
  O.emplace(std::prev(I));

Simplifies the code somewhat, avoids the double-lookup, but adds a bunch of memory overhead - making the values larger, and storing lots of None values where the current code avoids the entry entirely. So probably not worth it.

1311–1312

Is this comment incorrect? It sounds like from your other comments that MBB->begin() is never in the map?

1327

I guess this could be I != BeginIt - could save updates when the search doesn't find a new spot? & might be marginally cheaper comparison than calling begin() again?

This revision is now accepted and ready to land.Thu, Jan 28, 5:27 PM
wmi added inline comments.Thu, Jan 28, 5:38 PM
llvm/lib/CodeGen/LiveDebugVariables.cpp
1311–1312

Good catch. Will fix it.

1327

That is better. Thanks.

wmi updated this revision to Diff 320044.Thu, Jan 28, 9:57 PM

Address David's comment.

This revision was landed with ongoing or failed builds.Thu, Jan 28, 9:58 PM
This revision was automatically updated to reflect the committed changes.