llvm dev - Jun 2016 - [GSoC 2016] [Weekly Status] Interprocedural Register Allocation

> On Jun 20, 2016, at 12:53 PM, Sanjoy Das via llvm-dev <llvm-dev at
lists.llvm.org> wrote:
> 
> Hi Vivek,
> 
> vivek pandya via llvm-dev wrote:
> >     int foo() {
> >     return 12;
> >     }
> >
> >     int bar(int a) {
> >     return foo() + a;
> >     }
> >
> >     int (*fp)() = 0;
> >     int (*fp1)(int) = 0;
> >
> >     int main() {
> >     fp = foo;
> >     fp();
> >     fp1 = bar;
> >     fp1(15);
> >     return 0;
> >     }
> 
> IMO it is waste of time trying to do a better job at the IPRA level on
> IR like the above ^.  LLVM should be folding the indirect calls to
> direct calls at the IR level, and if it isn't that's a bug in the
IR
> level optimizer.
+1 from me.

The interesting cases are the non-obvious ones (assumeing foo/bar have the same
parameters). Things gets interesting once you have uncertainty in the mix. The
minimally interesting case would look like this:

int main() {
    int (*fp)();
    if (rand()) {
        fp = foo;
    } else {
        fp = bar;
    }
    fp(42);
}

However predicting the possible targets of a call is IMO a question of computing
a call graph datastructure and improving upon that. We should be sure that we
discuss and implement this independently of the register allocation work!

- Matthias

On Tue, Jun 21, 2016 at 1:45 AM, Matthias Braun <matze at braunis.de>
wrote:
>
> > On Jun 20, 2016, at 12:53 PM, Sanjoy Das via llvm-dev <
> llvm-dev at lists.llvm.org> wrote:
> >
> > Hi Vivek,
> >
> > vivek pandya via llvm-dev wrote:
> > >     int foo() {
> > >     return 12;
> > >     }
> > >
> > >     int bar(int a) {
> > >     return foo() + a;
> > >     }
> > >
> > >     int (*fp)() = 0;
> > >     int (*fp1)(int) = 0;
> > >
> > >     int main() {
> > >     fp = foo;
> > >     fp();
> > >     fp1 = bar;
> > >     fp1(15);
> > >     return 0;
> > >     }
> >
> > IMO it is waste of time trying to do a better job at the IPRA level on
> > IR like the above ^.  LLVM should be folding the indirect calls to
> > direct calls at the IR level, and if it isn't that's a bug in
the IR
> > level optimizer.
> +1 from me.
>
> Yes at -O3 level simple indirect calls including virtual functions are
getting optimized to direct call.

> The interesting cases are the non-obvious ones (assumeing foo/bar have the
> same parameters). Things gets interesting once you have uncertainty in the
> mix. The minimally interesting case would look like this:
>
> int main() {
>     int (*fp)();
>     if (rand()) {
>         fp = foo;
>     } else {
>         fp = bar;
>     }
>     fp(42);
> }
>
I tried this case and my simple hack fails to optimize it :-) . This
requires discussion on IRC.

Sincerely,
-Vivek

> However predicting the possible targets of a call is IMO a question of
> computing a call graph datastructure and improving upon that. We should be
> sure that we discuss and implement this independently of the register
> allocation work!
>
> - Matthias
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160621/386d09b3/attachment.html>

Hello LLVM Developers,

Please follow summary of work done during this week.

Implementation:
===========
During this week patch for bug fix 28144 is updated after finding more
refinement in remarks calculation. As per suggestion from Matthias Braun
and Hal Finkel regmask calculation code is same as
MachineRegisterInfo::isPhysRegModified() except no check of isNoReturnDef()
is required. So we proposed to add a bool argument SkipNoReturnDef with
default value false to isPhysRegModified method so that with out breaking
current use of isPhysRegModified we can reuse that code for the purpose of
IPRA. The patch can be found here : http://reviews.llvm.org/D21395

With IPRA to improve code quality, call site with local functions are
forced to have caller saved registers ( more improved heuristics will be
implemented ) I have been experimenting this on my local machine and I
discovered that tail call optimization is getting affected due to this
optimization and some test case in test-suite fails with segmentation fault
or infinite recursion due to counter value gets overwritten. Please find
more details and example bug at
https://groups.google.com/d/msg/llvm-dev/TSoYxeMMzxM/rb9e_M2iEwAJ

I have also tried a very simple method to handle indirect function in IPRA
but at higher optimization level, indirect function calls are getting
converted to direct function calls so I request interested community member
to guide me. We can have discussion about this on Monday morning (PDT).
More discussion on this can be found at here :
https://groups.google.com/d/msg/llvm-dev/dPk3lKwH1kU/GNfhD_jKEQAJ


Testing:

=====
During this week I think that IPRA optimization is more stabilized after
having bug fix so have run test-suite with that and also as per suggestion
form Quentin Colombet I tested test-suite with only codegen order changed
to bottom up on call graph.  Overall this codegen order improves runtime
and compile time. I have shared results here:

https://docs.google.com/document/d/1At3QqEWmeDEXnDVz-CGh2GDlYQR3VRz3ipIfcXoLC3c/edit?usp=sharing


https://docs.google.com/document/d/1hS-Cj3mEDqUCTKTYaJpoJpVOBk5E2wHK9XSGLowNPeM/edit?usp=sharing

Plan for next week:
=============1) Rebase pending patches and get the review process completed.
2) Solve tail call related bug.
3) Discuss some ideas and heuristics for improving IPRA.
4) Discuss how to handle indirect function call with in IPRA.
5) More testing with llvm test-suite

Sincerely,
Vivek


On Tue, Jun 21, 2016 at 9:26 AM, vivek pandya <vivekvpandya at gmail.com>
wrote:
>
>
> On Tue, Jun 21, 2016 at 1:45 AM, Matthias Braun <matze at braunis.de>
wrote:
>
>>
>> > On Jun 20, 2016, at 12:53 PM, Sanjoy Das via llvm-dev <
>> llvm-dev at lists.llvm.org> wrote:
>> >
>> > Hi Vivek,
>> >
>> > vivek pandya via llvm-dev wrote:
>> > >     int foo() {
>> > >     return 12;
>> > >     }
>> > >
>> > >     int bar(int a) {
>> > >     return foo() + a;
>> > >     }
>> > >
>> > >     int (*fp)() = 0;
>> > >     int (*fp1)(int) = 0;
>> > >
>> > >     int main() {
>> > >     fp = foo;
>> > >     fp();
>> > >     fp1 = bar;
>> > >     fp1(15);
>> > >     return 0;
>> > >     }
>> >
>> > IMO it is waste of time trying to do a better job at the IPRA
level on
>> > IR like the above ^.  LLVM should be folding the indirect calls to
>> > direct calls at the IR level, and if it isn't that's a bug
in the IR
>> > level optimizer.
>> +1 from me.
>>
>> Yes at -O3 level simple indirect calls including virtual functions are
> getting optimized to direct call.
>
>
>> The interesting cases are the non-obvious ones (assumeing foo/bar have
>> the same parameters). Things gets interesting once you have uncertainty
in
>> the mix. The minimally interesting case would look like this:
>>
>> int main() {
>>     int (*fp)();
>>     if (rand()) {
>>         fp = foo;
>>     } else {
>>         fp = bar;
>>     }
>>     fp(42);
>> }
>>
>
> I tried this case and my simple hack fails to optimize it :-) . This
> requires discussion on IRC.
>
> Sincerely,
> -Vivek
>
>
>> However predicting the possible targets of a call is IMO a question of
>> computing a call graph datastructure and improving upon that. We should
be
>> sure that we discuss and implement this independently of the register
>> allocation work!
>>
>> - Matthias
>>
>>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160626/ff5f596f/attachment.html>