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

[Daniel Berlin via llvm-dev]

>
> --- 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/110bf4fe/attachment.html>