llvm dev - Sep 2020 - [RFC] Framework for Finding and Using Similarity at the IR Level

Hi Andrew,

Thanks for this great work and presentation, I've also a huge interest in
code
size reduction.  I already looked at the first IR Outliner proposal,
and I really
like your more general approach.

I wanted to look at the impact on ARM targets, and managed to apply
your patchset
up to D87311 (the remaining ones which are related to call instructions and GEP
need to be reworked to be applied or work correctly). I looked at CTMark code
size other -Oz for both ARM and X86 and got a huge code size increase on both
targets (around 30% or 40% in Geomean) when compiled with -mllvm -ir-outliner.

Does it rings some bells on your side, is it expected given that the full series
is not applied, or did I just miss something ? From what I can observe, and as
you mentioned in your first mail, a lot of code is introduced to handle
parameters passing to outlined functions and the biggest code size increase was
observed after applying D87296.

Thanks a lot for this work and any hint on how to reproduce your results,
I'm
eager to play with it and give some help if needed.

Cheers,
Yvan


On Thu, 10 Sep 2020 at 00:00, Andrew Litteken via llvm-dev
<llvm-dev at lists.llvm.org> wrote:
>
> Thanks for the positive feedback!
>
> All the patches are up now:
>
> Elevating different constants to arguments: [IRSim][IROutliner] Adding
support for consolidating functions with different output arguments.
> Extracting require outputs: [IRSim][IROutliner] Adding support for
consolidating functions with different output arguments.
> Merging Output Blocks: [IRSim][IROutliner] Merging output blocks for
extracted functions with outputs
> Cost Model: [IRSim][IROutliner] Adding a cost model, and debug option to
turn the model off.
> OptRemarks: [IRSim][IROutliner] Adding OptRemarks for the IROutliner.
> Function Attribute Merging: [IRSim][IROutliner] Adding consistent function
attribute merging
> DebugInfo Handling: [IRSim][IROutliner] Adding DebugInfo handling for IR
outlined functions.
> Outlining from linkonceodr: [IRSim][IROutliner] Adding option to enable
outlining from linkonceodr functions
> Flexibility for Isomorphic Predicates: [IRSim] Adding support for
isomorphic predicates
> Flexibility for Commutative Instructions: [IRSim] Adding commutativity
matching to structure checking
> Matching call instructions for similarity identification: [IRSim] Letting
call instructions be legal for similarity identification.
> Outlining Calls: [IRSim][IROutliner] Allowing call instructions to be
outlined.
> Matching GEP instructions for similarity identification: [IRSim] Letting
gep instructions be legal for similarity identification.
> Outlining GEP instructions: [IRSim][IROutliner] Allowing GEP instructions
to be outlined.
>
> Feedback, comments and reviews are welcome!
>
> Andrew
>
> On Sep 2, 2020, at 5:04 AM, Renato Golin <rengolin at gmail.com>
wrote:
>
> Indeed, an awesome project and an excellent report!
>
> Code size doesn't really get much attention, so the level of detail and
the strong roadmap is refreshing.
>
>> Hopefully, the project will provide execution times along with
code-size reductions.
>
> I doubt it.
>
> Outlining will (almost?) always make for slower code due to a lot more
calls being made. But that's ok for embedded targets, that don't have
strong speculative machinery.
>
> Also, if the program fits versus doesn't, then it will run infinitely
faster. :D
>
> Kristof, do you know who at Arm would be good to review those patches?
>
> cheers,
> --renato
>
>
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev

Hi Yvan,

Glad to hear you’re interested! I’m not sure which ordering you’re looking at
the patches, but a cost model was not added to the outliner until D87299. So, if
that hasn’t been added I would expect some pretty big code increases since it
just outlines whatever similarity it finds first otherwise.

The cost model has also been slightly reworked since the initial results to be
more general, and try to use target hooks, but not all of the target hooks that
we would really want exist. So, if it has been applied, I’ll definitely need to
take a look.

Andrew
> On Sep 30, 2020, at 6:22 AM, Yvan Roux <yvan.roux at linaro.org>
wrote:
> 
> Hi Andrew,
> 
> Thanks for this great work and presentation, I've also a huge interest
in code
> size reduction.  I already looked at the first IR Outliner proposal,
> and I really
> like your more general approach.
> 
> I wanted to look at the impact on ARM targets, and managed to apply
> your patchset
> up to D87311 (the remaining ones which are related to call instructions and
GEP
> need to be reworked to be applied or work correctly). I looked at CTMark
code
> size other -Oz for both ARM and X86 and got a huge code size increase on
both
> targets (around 30% or 40% in Geomean) when compiled with -mllvm
-ir-outliner.
> 
> Does it rings some bells on your side, is it expected given that the full
series
> is not applied, or did I just miss something ? From what I can observe, and
as
> you mentioned in your first mail, a lot of code is introduced to handle
> parameters passing to outlined functions and the biggest code size increase
was
> observed after applying D87296.
> 
> Thanks a lot for this work and any hint on how to reproduce your results,
I'm
> eager to play with it and give some help if needed.
> 
> Cheers,
> Yvan
> 
> 
>> On Thu, 10 Sep 2020 at 00:00, Andrew Litteken via llvm-dev
>> <llvm-dev at lists.llvm.org> wrote:
>> 
>> Thanks for the positive feedback!
>> 
>> All the patches are up now:
>> 
>> Elevating different constants to arguments: [IRSim][IROutliner] Adding
support for consolidating functions with different output arguments.
>> Extracting require outputs: [IRSim][IROutliner] Adding support for
consolidating functions with different output arguments.
>> Merging Output Blocks: [IRSim][IROutliner] Merging output blocks for
extracted functions with outputs
>> Cost Model: [IRSim][IROutliner] Adding a cost model, and debug option
to turn the model off.
>> OptRemarks: [IRSim][IROutliner] Adding OptRemarks for the IROutliner.
>> Function Attribute Merging: [IRSim][IROutliner] Adding consistent
function attribute merging
>> DebugInfo Handling: [IRSim][IROutliner] Adding DebugInfo handling for
IR outlined functions.
>> Outlining from linkonceodr: [IRSim][IROutliner] Adding option to enable
outlining from linkonceodr functions
>> Flexibility for Isomorphic Predicates: [IRSim] Adding support for
isomorphic predicates
>> Flexibility for Commutative Instructions: [IRSim] Adding commutativity
matching to structure checking
>> Matching call instructions for similarity identification: [IRSim]
Letting call instructions be legal for similarity identification.
>> Outlining Calls: [IRSim][IROutliner] Allowing call instructions to be
outlined.
>> Matching GEP instructions for similarity identification: [IRSim]
Letting gep instructions be legal for similarity identification.
>> Outlining GEP instructions: [IRSim][IROutliner] Allowing GEP
instructions to be outlined.
>> 
>> Feedback, comments and reviews are welcome!
>> 
>> Andrew
>> 
>> On Sep 2, 2020, at 5:04 AM, Renato Golin <rengolin at gmail.com>
wrote:
>> 
>> Indeed, an awesome project and an excellent report!
>> 
>> Code size doesn't really get much attention, so the level of detail
and the strong roadmap is refreshing.
>> 
>>> Hopefully, the project will provide execution times along with
code-size reductions.
>> 
>> I doubt it.
>> 
>> Outlining will (almost?) always make for slower code due to a lot more
calls being made. But that's ok for embedded targets, that don't have
strong speculative machinery.
>> 
>> Also, if the program fits versus doesn't, then it will run
infinitely faster. :D
>> 
>> Kristof, do you know who at Arm would be good to review those patches?
>> 
>> cheers,
>> --renato
>> 
>> 
>> _______________________________________________
>> LLVM Developers mailing list
>> llvm-dev at lists.llvm.org
>> https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev

On Wed, 30 Sep 2020 at 16:48, Andrew Litteken <andrew.litteken at
gmail.com> wrote:
>
> Hi Yvan,
>
> Glad to hear you’re interested! I’m not sure which ordering you’re looking
at the patches, but a cost model was not added to the outliner until D87299. So,
if that hasn’t been added I would expect some pretty big code increases since it
just outlines whatever similarity it finds first otherwise.
>
> The cost model has also been slightly reworked since the initial results to
be more general, and try to use target hooks, but not all of the target hooks
that we would really want exist. So, if it has been applied, I’ll definitely
need to take a look.
I applied the patches in order on top of your commit of D86974
(15645d044bc) that is:
D86975 - D86976 - D86977 - D86978 - D87294 - D87296 - D87298 - D87299 - D87300
D87301 - D87302 - D87309 - D87310

So, the cost model was part of it, I don't remember if I had to
resolve some conflicts for
it, but I'll re-check and look if it was applied correctly.

Yvan

> Andrew
>
> > On Sep 30, 2020, at 6:22 AM, Yvan Roux <yvan.roux at linaro.org>
wrote:
> >
> > Hi Andrew,
> >
> > Thanks for this great work and presentation, I've also a huge
interest in code
> > size reduction.  I already looked at the first IR Outliner proposal,
> > and I really
> > like your more general approach.
> >
> > I wanted to look at the impact on ARM targets, and managed to apply
> > your patchset
> > up to D87311 (the remaining ones which are related to call
instructions and GEP
> > need to be reworked to be applied or work correctly). I looked at
CTMark code
> > size other -Oz for both ARM and X86 and got a huge code size increase
on both
> > targets (around 30% or 40% in Geomean) when compiled with -mllvm
-ir-outliner.
> >
> > Does it rings some bells on your side, is it expected given that the
full series
> > is not applied, or did I just miss something ? From what I can
observe, and as
> > you mentioned in your first mail, a lot of code is introduced to
handle
> > parameters passing to outlined functions and the biggest code size
increase was
> > observed after applying D87296.
> >
> > Thanks a lot for this work and any hint on how to reproduce your
results, I'm
> > eager to play with it and give some help if needed.
> >
> > Cheers,
> > Yvan
> >
> >
> >> On Thu, 10 Sep 2020 at 00:00, Andrew Litteken via llvm-dev
> >> <llvm-dev at lists.llvm.org> wrote:
> >>
> >> Thanks for the positive feedback!
> >>
> >> All the patches are up now:
> >>
> >> Elevating different constants to arguments: [IRSim][IROutliner]
Adding support for consolidating functions with different output arguments.
> >> Extracting require outputs: [IRSim][IROutliner] Adding support for
consolidating functions with different output arguments.
> >> Merging Output Blocks: [IRSim][IROutliner] Merging output blocks
for extracted functions with outputs
> >> Cost Model: [IRSim][IROutliner] Adding a cost model, and debug
option to turn the model off.
> >> OptRemarks: [IRSim][IROutliner] Adding OptRemarks for the
IROutliner.
> >> Function Attribute Merging: [IRSim][IROutliner] Adding consistent
function attribute merging
> >> DebugInfo Handling: [IRSim][IROutliner] Adding DebugInfo handling
for IR outlined functions.
> >> Outlining from linkonceodr: [IRSim][IROutliner] Adding option to
enable outlining from linkonceodr functions
> >> Flexibility for Isomorphic Predicates: [IRSim] Adding support for
isomorphic predicates
> >> Flexibility for Commutative Instructions: [IRSim] Adding
commutativity matching to structure checking
> >> Matching call instructions for similarity identification: [IRSim]
Letting call instructions be legal for similarity identification.
> >> Outlining Calls: [IRSim][IROutliner] Allowing call instructions to
be outlined.
> >> Matching GEP instructions for similarity identification: [IRSim]
Letting gep instructions be legal for similarity identification.
> >> Outlining GEP instructions: [IRSim][IROutliner] Allowing GEP
instructions to be outlined.
> >>
> >> Feedback, comments and reviews are welcome!
> >>
> >> Andrew
> >>
> >> On Sep 2, 2020, at 5:04 AM, Renato Golin <rengolin at
gmail.com> wrote:
> >>
> >> Indeed, an awesome project and an excellent report!
> >>
> >> Code size doesn't really get much attention, so the level of
detail and the strong roadmap is refreshing.
> >>
> >>> Hopefully, the project will provide execution times along with
code-size reductions.
> >>
> >> I doubt it.
> >>
> >> Outlining will (almost?) always make for slower code due to a lot
more calls being made. But that's ok for embedded targets, that don't
have strong speculative machinery.
> >>
> >> Also, if the program fits versus doesn't, then it will run
infinitely faster. :D
> >>
> >> Kristof, do you know who at Arm would be good to review those
patches?
> >>
> >> cheers,
> >> --renato
> >>
> >>
> >> _______________________________________________
> >> LLVM Developers mailing list
> >> llvm-dev at lists.llvm.org
> >> https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev