This is an archive of the discontinued LLVM Phabricator instance.

[CodeGen] Provide an advanced shrink-wrapping interface
AbandonedPublic

Authored by thegameg on Jul 31 2017, 1:20 PM.

Details

Summary

Based on Minimizing Register Usage Penalty at Procedure Calls - Fred C. Chow, this is an implementation of a shrink-wrapping algorithm supporting multiple save / restore blocks.

The algorithm is meant to provide a shrink-wrapping interface to any kind of input. We can think of callee-saved registers, stack usage, life_range markers, etc. as input data, and run the shrink-wrapper in order to find the most efficient save / restore points.

The ShrinkWrapInfo class is meant to be subclassed by the users of this algorithm, in order to provide more details.

  • Loops are handled using scc_iterators in order to handle irreducible loops and avoid placing any save / restore instruction inside a loop.
  • Uses on no-return paths will be ignored and won't affect the final save / restore points.
  • A "shrink-wrapping cost" is used to determine if the final placement is better than the default one (entry block, return blocks). This cost is nothing more than NumberOfSavesAndRestores * BlockFrequency * 100.
  • There is a verifier running only when EXPENSIVE_CHECKS is on, checking that all the paths are correctly handled, that there are no saves without restores, no restores without saves, and no nested saves of the same element.

This is a high-level algorithm, without any target-specific implementation.

Diff Detail

Event Timeline

thegameg created this revision.Jul 31 2017, 1:20 PM
lei added a subscriber: lei.Aug 22 2017, 2:31 PM
lei added inline comments.
lib/CodeGen/ShrinkWrapper.cpp
67

Since the MarkAsUsed lambda is always called with 3 parameters, there is no need to specify a default value for this lambda parameter.

431

IsSCCLoop is not used in this function.

thegameg updated this revision to Diff 113056.Aug 29 2017, 3:47 AM
thegameg marked 2 inline comments as done.

Thanks @lei for taking a look. I addressed your concerns.

lei added a comment.Aug 30 2017, 10:36 AM

Can you provide documentation on the various functions? I was trying to extend this for PPC and I had a hard time trying to figure out what I needed to do enable to get this working. I was able to see it did something for loops but it wasn't able to identify any shrink wrap opportunities for this simple tc:

int doSomething(int a, int b);

int test (int a, int b) {
  int c=a;
  if (a < b) {
    c = doSomething(0, a);
  }
  return c;
}
In D36109#856854, @lei wrote:

Can you provide documentation on the various functions? I was trying to extend this for PPC and I had a hard time trying to figure out what I needed to do enable to get this working.

Great! I tried to explain most of the bits here: https://lists.llvm.org/pipermail/llvm-dev/2017-August/116131.html. As I pointed out at the end of the email, you could take a look at:

Basically, what you're interested in is the ShrinkWrapInfo class. You will need to subclass that to adapt it to PPC's needs. This is similar to TargetFrameLowering::determineCalleeSaves, but you will need to map the CSR uses to a specific basic block of the function. For a generic behaviour just call determineCSRUses(), which tracks CSR uses using register units.

I was able to see it did something for loops

Right, the loop-specific behaviour here is only to avoid placing any save / restores inside a loop, if there are any uses. You shouldn't need to worry about it if you are only looking to implement this for PPC.

but it wasn't able to identify any shrink wrap opportunities for this simple tc:

int doSomething(int a, int b);

int test (int a, int b) {
  int c=a;
  if (a < b) {
    c = doSomething(0, a);
  }
  return c;
}

I'm not sure I can tell what's going on without knowing what flags you used, what's the MIR code that shrink-wrapping takes as an input, and what ShrinkWrapInfo marks as *used*. I would be more than happy to try it out!

Also, if you have any suggestions and remarks about the algorithm or the interface it provides to work with the target, don't hesitate!

thegameg abandoned this revision.Jan 8 2018, 8:21 AM

Going forward with this: https://reviews.llvm.org/D41765 which is a more incremental approach.

vsk added a subscriber: vsk.Oct 24 2018, 12:26 PM