[FuncSpec] Support specialising recursive functions
authorSjoerd Meijer <sjoerd.meijer@arm.com>
Tue, 3 Aug 2021 19:42:09 +0000 (20:42 +0100)
committerSjoerd Meijer <sjoerd.meijer@arm.com>
Wed, 4 Aug 2021 07:07:04 +0000 (08:07 +0100)
commit30fbb06979077740961ebc46853e28ab1f999f9d
tree7c93e538b0444384a457f179dac428437a633ddd
parent486b6013f967ff80f8fa4d20bf5b93e94ce72aa0
[FuncSpec] Support specialising recursive functions

This adds support for specialising recursive functions. For example:

    int Global = 1;
    void recursiveFunc(int *arg) {
      if (*arg < 4) {
        print(*arg);
        recursiveFunc(*arg + 1);
      }
    }
    void main() {
      recursiveFunc(&Global);
    }

After 3 iterations of function specialisation, followed by inlining of the
specialised versions of recursiveFunc, the main function looks like this:

    void main() {
      print(1);
      print(2);
      print(3);
    }

To support this, the following has been added:
- Update the solver and state of the new specialised functions,
- An optimisation to propagate constant stack values after each iteration of
  function specialisation, which is necessary for the next iteration to
  recognise the constant values and trigger.

Specialising recursive functions is (at the moment) controlled by option
-func-specialization-max-iters and is opt-in for compile-time reasons. I.e.,
the default is -func-specialization-max-iters=1, but for the example above we
would need to use -func-specialization-max-iters=3. Future work is to see if we
can increase the default, or improve the cost-model/heuristics to control
compile-times.

Differential Revision: https://reviews.llvm.org/D106426
llvm/lib/Transforms/IPO/FunctionSpecialization.cpp
llvm/test/Transforms/FunctionSpecialization/function-specialization-recursive.ll
llvm/test/Transforms/FunctionSpecialization/function-specialization-recursive2.ll [new file with mode: 0644]
llvm/test/Transforms/FunctionSpecialization/function-specialization-recursive3.ll [new file with mode: 0644]
llvm/test/Transforms/FunctionSpecialization/function-specialization-recursive4.ll [new file with mode: 0644]