Page MenuHomePhabricator

[CodeGen] Provide an advanced shrink-wrapping interface
Needs ReviewPublic

Authored by thegameg on Jan 5 2018, 7:24 AM.

Details

Summary

In order to extend shrink-wrapping we need to make some changes to the interface.

When trying to extend shrink-wrapping I came across the following limitations in terms of interface:

  • We cannot have multiple save points.
  • We cannot have multiple restore points.
  • We cannot choose which registers are being saved / restored for each block.
  • We cannot separate the Prologue / Epilogue emission from the callee saved register storing / loading.
  • We cannot reuse the same algorithm to shrink-wrap anything else than CSRs and stack usage.

The goal here would be to provide an interface that would allow us to develop shrink-wrapping extensions in-tree, and being able to switch between implementations without actually having to handle both interfaces in PEI.

In order to be able to simply re-use this, we need to know which basic blocks use which element (as an input), and which basic blocks are the best suited for saving / restoring each element (as an output).

For that, the interface is split in two parts:

ShrinkWrapInfo: it is an interface that determines the "uses" to be used by the shrink-wrapping algorithm.
Example of uses:

  • For shrink-wrapping CSR save / restore points: uses/defs of CSRs
  • For shrink-wrapping stack setup code: uses/defs of SP, FP, FrameIndex operands

In order to have individual shrink-wrapping for each element, we map every different element to an index and store it in a BitVector. If there is an use of the element in a basic block, the bit at the index of the element is set. The interface provides uses per basic block:

const BitVector *getUses(unsigned MBBNum) const

In order to choose what a "use" is, this class has to be sub-classed and it has to compute the uses per basic block that are consumed by getUses().

  • Example 1: Callee saved registers:
0:
    elements:         r0 r1 r2 r3 r4 r5 r6 r7 r8 r9
    BitVector index:  0  1  2  3  4  5  6  7  8  9
    BitVector values: 1  0  0  0  0  0  0  0  0  1
    This means that r0 and r9 are used in %bb.0.
  • Example 2: Stack + CSRs:
0:
      elements:         Stack r0 r1
      BitVector index:  0     1  2
      BitVector values: 1     0  1
4:
      elements:         Stack r0 r1
      BitVector index:  0     1  2
      BitVector values: 0     1  0

This means that r0 is used in %bb.4 and the Stack and r0 are used in %bb.0.

Providing this as an input to the shrink-wrapping algorithm allows the algorithm to be independent of the meaning of the input.

ShrinkWrapper: it is an interface for the shrink-wrapping algorithm. It makes it easy to switch between the current one (dominator-based) and other ones like Fred Chow's. This interface provides a result in the following format:

  • DenseMap<unsigned, BitVector> Saves, Restores.
  • It maps a MachineBasicBlock number to a BitVector containing the elements that need to be saved / restored.
  • Example 1: Saves:
0:
    elements:         r0 r1 r2 r3 r4 r5 r6 r7 r8 r9
    BitVector index:  0  1  2  3  4  5  6  7  8  9
    BitVector values: 1  0  0  0  0  0  0  0  0  1

This means that r0 and r9 need to be saved in %bb.0.

  • Example 2: Saves:
0:
      elements:         Stack r0 r1
      BitVector index:  0     1  2
      BitVector values: 1     0  1
4:
      elements:         Stack r0 r1
      BitVector index:  0     1  2
      BitVector values: 0     1  0

This means that we have to set up the stack and save r1 in %bb.0, and save r0 in %bb.4.

In order to implement an algorithm, this class has to be sub-classed and compute the results of Saves and Restores in the constructor.

The current dominator-based algorithm port to this interface can allow us to experiment with shrink-wrapping registers and stack uses individually, through the ShrinkWrapInfo class.

This class is meant to be used from PEI to collect better save / restore points, but for now I'll keep it in the ShrinkWrap pass to simplify the review of the patch and focus on the design of the interface.

For this review, I recommend to start by reviewing ShrinkWrapper.h and the ShrinkWrapper / ShrinkWrapInfo abstract classes. The DominatorShrinkWrapper is the port of the current shrink-wrapper to this new interface, and the CSRFIShrinkWrapInfo collects all the basic blocks that use any CSRs or the stack.

Diff Detail

Event Timeline

thegameg created this revision.Jan 5 2018, 7:24 AM

Through this change, do you intend to support the partial shrink-wrapping? What other extensions are you planning on after this change?

Through this change, do you intend to support the partial shrink-wrapping? What other extensions are you planning on after this change?

After this change I want to experiment with shrink-wrapping CSRs separately and have one save point per register. This would still use the current dominator-based algorithm and would basically allow us to fix all the issues that we encounter in terms of unwinding, debugging, PEI and FrameLowering assumptions about prologues and epilogues, etc.

Then the bigger plan is to integrate https://reviews.llvm.org/D30808 in tree and iterate on it until the results are satisfying enough to switch to it as the default algorithm, but IMO a lot of work will have to go into actually supporting "partial shrink-wrapping" than the algorithm itself.

thegameg updated this revision to Diff 128923.Jan 8 2018, 6:45 AM

DefaultShrinkWrapper doesn't need the RegScavenger, only DefaultShrinkWrapInfo.

davide added a subscriber: davide.Jan 8 2018, 8:24 AM
qcolombet added inline comments.Jan 10 2018, 9:38 AM
lib/CodeGen/DefaultShrinkWrapper.cpp
1 ↗(On Diff #128923)

Could we use a different name that Default because given the plan is to change the default, this is just going to be confusing :)

junbuml added inline comments.Jan 30 2018, 1:27 PM
include/llvm/CodeGen/ShrinkWrapper.h
61

This means that r0 is used in %bb.4 and the Stack and r1 are used in

lib/CodeGen/DefaultShrinkWrapper.cpp
98 ↗(On Diff #128923)

Just to remind you that your previous commit (r322584) should be applied in this function.

178 ↗(On Diff #128923)

As we handle CSRs/FI all together in the current implementation, it will be good to mention that '0' implicitly means that.

393 ↗(On Diff #128923)

I think Elt should be printed together here.

407 ↗(On Diff #128923)

Don't you need do increase NumCandidates here ?

thegameg updated this revision to Diff 132237.Jan 31 2018, 3:03 PM
thegameg marked 5 inline comments as done.

Split DefaultShrinkWrapper and DefaultShrinkWrapInfo into:

  • DominatorShrinkWrapper
  • CSRFIShrinkWrapInfo

I'm not very happy with these names, but I couldn't think of anything else.

Also,

  • Rebase
  • Fix NumCandidates increment
  • Add enum to give more meaning to the bit 0
thegameg edited the summary of this revision. (Show Details)Jan 31 2018, 3:07 PM
thegameg updated this revision to Diff 132896.Feb 5 2018, 3:59 PM
  • Stop looping if none of the elements are tracked anymore.
  • Let the caller decide what to do with untracked elements.
  • Comments / style updates.
junbuml added inline comments.Feb 6 2018, 9:00 AM
lib/CodeGen/CSRFIShrinkWrapInfo.cpp
103–104

Little confusing about this comment. Should it be like : since we cannot restore before a terminator using CSR?

107

Don't we need to check all terminators in MBB, instead of checking if MI is a terminator?

lib/CodeGen/CSRFIShrinkWrapInfo.h
57

typo : ressources

lib/CodeGen/DominatorShrinkWrapper.cpp
213

what about something like hasElementToTrack() ?

lib/CodeGen/ShrinkWrap.cpp
107–126

Why don't we make this as a method in ShringWrapper?

thegameg updated this revision to Diff 133072.Feb 6 2018, 1:57 PM
thegameg marked 2 inline comments as done.

Address review concerns.

lib/CodeGen/CSRFIShrinkWrapInfo.cpp
107

Is that really necessary? I couldn't find any way in which this approach (marking the successors) doesn't work.

lib/CodeGen/CSRFIShrinkWrapInfo.h
57

Sorry, I'm not sure what the issue is here?

lib/CodeGen/ShrinkWrap.cpp
107–126

My plan is to separate the ShrinkWrapper and ShrinkWrapInfo from MachineFrameInfo, so that it can be reused easily.

One of my next steps is to move the invocation from the ShrinkWrap pass to PEI. That way, we can easily switch between CSRFIShrinkWrapInfo and something like PartialShrinkWrapInfo where we would track more than one element, so we would have more than one element to save/restore.

For something like PartialShrinkWrapInfo, we would need more than MFI.SavePoint and MFI.RestorePoint. We would need to know which registers need to be saved in which basic block, and separately, where to emit the prologue/epilogue.

So I would like to keep the "interpretation" of the results of the ShrinkWrapper separate from the algorithm itself. We could think of some way to put this in CSRFIShrinkWrapInfo, but I'm not sure how to do it in a reusable way.

junbuml added inline comments.Feb 6 2018, 2:58 PM
lib/CodeGen/CSRFIShrinkWrapInfo.cpp
107

As far as I understand, if a block has an instruction using csr and also has a terminator using csr. Then, we have to mark its successors as used as well so that we can safely place the restore point after the terminator.
Assuming what I understand is correct, if MI using csr is a non-terminator, then current code may not mark its successor even when MBB's terminator use csr. When MBB is marked, we should also check if its terminators use csr before break in line 110.

lib/CodeGen/CSRFIShrinkWrapInfo.h
57

Sorry I meant typo in line 56 : ressources -> resources.

thegameg updated this revision to Diff 133337.Feb 7 2018, 4:49 PM
thegameg marked 3 inline comments as done.
  • Fix typo
  • Iterate on MBB in reverse to catch terminator uses first
lib/CodeGen/CSRFIShrinkWrapInfo.cpp
107

You're totally right, sorry. I was confused between CSRFIShrinkWrapInfo and a version which tracks multiple registers so it has to go through all the instructions.

How about iterating on the instructions in reverse order? We will reach terminators first, and if they use any CSR/FI, we can safely assume that if any non-terminator instructions use CSR/FI, the terminators have been checked first.

LGTM.
It seems to be a good start to extend shrink-wrapping.
I want to encourage other reviews to take a look.

lib/CodeGen/CSRFIShrinkWrapInfo.cpp
107

Looks good to me. Thanks!

vsk added a subscriber: vsk.Oct 24 2018, 12:26 PM
wuzish added a subscriber: wuzish.Aug 5 2019, 10:34 PM