[llvm-dev] [RFC] PT.2 Add IR level interprocedural outliner for code size.

[River Riddle via llvm-dev]

Hey Dan,
  The intent from the beginning was to use the NewGVN infrastructure to
help do the numbering, partially inspired by your responses to the original
Machine Outliner RFC (That is actually how this started to some degree),
but the infrastructure wasn't quite ready when I started.

Thanks,
 River Riddle

On Thu, Sep 21, 2017 at 7:45 PM, Daniel Berlin <dberlin at dberlin.org> wrote:

> --- Algorithmic differences with the Machine Outliner ----
>>
>>           There was a lot of confusion on how exactly the algorithm I am
>> proposing differs from what is available in the Machine Outliner. The
>> similarities of the two outliners lie in the usage of a string matching
>> algorithm and candidate pruning. The first step in the algorithm is to
>> basically do the same common substring / pruning algorithm the post-RA MO
>> uses but with a specially chosen congruence relation. I’d like to delve
>> into the differences between the two:
>>
>> Congruence Detection:
>>
>> -        Machine Outliner
>>
>>   The machine outliner has the advantage of having this problem already
>> taken care of by the register allocator, it simply checks to see if the two
>> machine instructions are identical.
>>
>> -        IR Outliner
>>
>>   In the IR outliner we work on semantic equivalence, i.e. we care the
>> operations being performed are equivalent and not the values. This creates
>> a need to add verification that we do have exact equivalence when we need
>> it, e.g. ShuffleVector’s shuffle mask, not taking the address of InlineASM,
>> etc.
>>
>> A quick example of semantic equivalence:
>>
>> %1 = add i32 1, i32 2
>>
>> %2 = add i32 2, i32 3
>>
>> These two instructions are not identical because the values of the
>> operands are not identical. They are, however, semantically equivalent
>> because they both perform the add operation.
>>
>> This can be seen by simply removing the operand values used in the
>> calculations:
>>
>> %1 = add i32 , i32
>>
>> %2 = add i32 , i32
>>
>>
>> FWIW, you could use the core NewGVN structures (GVNExpression.h) to do
> this and just not fill in the operands.
> GVNSink does a variant of this by using them.
> In particular, the variant it does is: "do these instructions contribute
> to their uses in an equivalent way".  This is the same problem, but if you
> weren't going to be willing to add any function arguments to fill in
> operand values.
>
>
> IE
>
> /// [ %a1 = add i32 %b, 1  ]   [ %c1 = add i32 %d, 1  ]
> /// [ %a2 = xor i32 %a1, 1 ]   [ %c2 = xor i32 %c1, 1 ]
> ///                  \           /
> ///            [ %e = phi i32 %a2, %c2 ]
> ///            [ add i32 %e, 4         ]
>
>
> These would value number differently using a normal value numbering
> algorithm.
> GVNSink instead computes "could i common a1 and c1, could i do that by
> adding a phi".
>
>
> (Though i realize now the computation it performs can now be performed in
> a single pass. It's just the reverse of what we do in NewGVN. We look for
> things we can convert into phi of ops, it looks for things it can convert
> into op of phis to save instructions)
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20170921/d15476d6/attachment.html>