[cfe-dev] Disable certain llvm optimizations at clang frontend

[Y Song via cfe-dev]

On Mon, Jun 22, 2020 at 3:42 PM Hal Finkel <hfinkel at anl.gov> wrote:
>
> On 6/21/20 2:30 AM, Y Song wrote:
> > On Fri, Jun 19, 2020 at 6:20 PM Hal Finkel <hfinkel at anl.gov> wrote:
> >>
> >> On 6/19/20 3:08 PM, Eli Friedman wrote:
> >>> (Reply inline)
> >>>
> >>>> -----Original Message-----
> >>>> From: cfe-dev <cfe-dev-bounces at lists.llvm.org> On Behalf Of Y Song via cfe-
> >>>> dev
> >>>> Sent: Friday, June 19, 2020 11:40 AM
> >>>> To: Hal Finkel <hfinkel at anl.gov>
> >>>> Cc: Andrii Nakryiko <andrii.nakryiko at gmail.com>; Clang Dev <cfe-
> >>>> dev at lists.llvm.org>; Alexei Starovoitov <ast at kernel.org>
> >>>> Subject: [EXT] Re: [cfe-dev] Disable certain llvm optimizations at clang
> >>>> frontend
> >>>>
> >>>> Just to be more specific about what transformations we want to disable:
> >>>>     (1). Undo a transformation in InstCombine/InstCombineAndOrXor.cpp
> >>>>           (https://reviews.llvm.org/D72787)
> >>>>           This transformation created a new variable "var.off" for comparison but
> >>>>           using the original variable "var" later on. The kernel verifier does not
> >>>>           have a better range of "var" at its use place and this may cause
> >>>>           verification failure.
> >>>>
> >>>>           To generalize, BPF prefers the single variable is refined and used later
> >>>>           for each verification. New variable can be created and used for further
> >>>>           value range refinement, but all later usage of old variable should be
> >>>>           replaced with the new variable.
> >>>>      (2). Prevent speculative code motion
> >>>>             (https://reviews.llvm.org/D82112, https://reviews.llvm.org/D81859)
> >>>>            If the code in the original program may not execute under
> >>>> certain conditions,
> >>>>            we could like the code not to execute in the final byte code
> >>>> under the same
> >>>>            condition, regardless of whether it is safe to execute or not.
> >>>>
> >>>>       I guess we could have two attributes here:
> >>>>          - "refine-value-range-with-original-var" (false by default, true for BPF)
> >>>>          - "no-speculative-code-motion" (false by default, true for BPF)
> >>> Looking at this, I'm worried that there's a bigger disconnect between the way LLVM reasons about IR, vs. what the BPF verifier can actually handle.  It isn't reasonable to blindly disable code motion; that's chasing after the symptoms of the problem, not solving the underlying issue.
> >>>
> >>> If I understand correctly, the underlying issue is that BPF has a notion of a "CFG guard": you can have a condition and a branch, and instructions inside the region guarded by that branch have different rules from instructions outside that region, based on that condition.  Both clang and LLVM optimizations are completely
> > bpf verifier is briefly described in the comments here:
> >    https://github.com/torvalds/linux/blob/master/kernel/bpf/verifier.c#L38
> >
> > It is a path sensitive verifier. It will go through all possible paths
> > to ensure all memory accesses are safe.
> > The verifier is able to carry refined info across function calls.
> > The condition may refine a value range, e.g.,
> >     unsigned a = foo(); /* " a" is an unsigned int, could be any value
> > 0 <= "a" <= UINT_MAX */
> >     if (a < 128) {
> >       /* varifier concludes "a" range now is [0, 127]. */
> >       ...  * (p + a) ...   /* test whether *(p + [0, 127]) is legal or not.
> >    }
> >
> > But verifier is not smart enough to do backtracking now, so if you have code
> >     unsigned a = foo();
> >     b = a + 10;
> >     if (b < 128) {
> >         ... * (p + a) ...    /* b will be [10, 127], but a is [0, UINT_MAX]. */
> >     }
> > The verifier may reject the above code as (p + a) may be out of bound
> > of legal permitted memory range.
> >
> > Why verifier did not then implement backtracking? There are a few reasons:
> >     - This is actually not very common. As long as the program does not
> > have control flow like the above triggering a particular instcombine
> > transformation, the compiler actually did a good job avoiding the
> > above pattern to avoid a second copy of the same variable. But if this
> > actually happens, it often cause a lot of
> > frustration for developers as their codes are perfectly okay and they
> > often do not know how to please
> > the verifier.
> >     - verifier is already very complex. Adding generic backtracking
> > will add a lot of complexity to verifier.
> > More states may need to be kept during verification process and this
> > will require more kernel memory. The verifier will become slower too.
> >
> > The same for speculative code motion. Yes, the current verifier may
> > reject a pointer arithmetic (say pkt_ptr += UINT_MAX). But in really,
> > this pkt_ptr += UINT_MAX may just a speculative move and later on
> > pkt_ptr = original_legal_pkt_ptr + 10 will assign proper value before
> > actual memory access. In this case, the verifier will be wrong to
> > reject the program.
> >
> > Not all speculative code motion will cause problems. Some scalar
> > speculative code motion totally fine. Or if the speculative code
> > motion still within ptr valid range, it will be fine too.
> >
> > My original proposal to disable certain optimizations are a big
> > hammer, just to get it work so the developer can move on. I totally
> > agree that using func attribute to disable certain specific
> > optimizations may happen to work for some cases, but it may not work
> > for all cases since other optimizations may perform optimizations.
>
>
> Thanks, this is helpful. One question: Is the information used by the
> verifier available at compile time? It seems like what you want here is

We have identified some compiler optimizations in instcombine and
simplifyCFG may generate verifier unfriendly code. Yes, we could do
IR analysis to identify these patterns, may not be 100% but should be
close.

Completely modelling what verifier did in llvm is complex. Verifier
interacts with kernel subsystem with helper functions and these
helper functions having some semantics utilized with the verifier.
Bringing kernel helpers to llvm does not sound a good idea.
Verifier implements a path sensitive verification framework. To replicate
in llvm probably not a good idea as there are constant changes to
verifier and it is very hard to keep them sync. So here, in llvm the
best probably
to identify known IR patterns where verifier unfriendly code may be
generated and prevent them from generating (preferred) or undo them
if already generated.


> for the backend to iterate over the IR, perform the verification, and in
> cases where it would fail, push the relevant parts of the use-def chain
> down into the blocks with their eventual users.

This is a good idea. The issue is instCombine and SimplifyCFG happens
before any backend IR passes. So backend will have to undo some of
these optimizations. For speculative code motion, the backend probably
hard to do since it does not even know the code is speculative generated.

Can we prevent these optimizations happening in the first place?

In addition to my previous three ideas:
   - function attribute to state intention,
   - clang IR generation with certain variable barriers.
   - new TLI functions used by bpf backend and additional bpf backend
     IR phases.

Two more ideas here:
(1). Is it possible to implement an generic IR pass (before InstCombine
and SimplifyCFG) which takes some hints from backend to modify IR
to favor BPF verifier?
(2). is it possible that clang frontend provides a hook for target to
provide a pass manager or at least having a say
to the pass manager? This way, target may disable certain passes?
I realize this is a big hammer approach. But Considering here that our
main goal is to improve development experience and performance
is not a goal, maybe it is still acceptable?

>
>   -Hal
>
> ...
>
>
> >>    -Hal
> >>
> >>
> >> --
> >> Hal Finkel
> >> Lead, Compiler Technology and Programming Languages
> >> Leadership Computing Facility
> >> Argonne National Laboratory
> >>
> --
> Hal Finkel
> Lead, Compiler Technology and Programming Languages
> Leadership Computing Facility
> Argonne National Laboratory
>