lkml.org 
[lkml]   [2014]   [Feb]   [27]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
    /
    Date
    SubjectRe: [RFC][PATCH 0/5] arch: atomic rework
    From
    On Thu, Feb 27, 2014 at 7:37 AM, Torvald Riegel <triegel@redhat.com> wrote:
    >
    > I agree that just considering syntactic properties of the program seems
    > to be insufficient. Making it instead depend on whether there is a
    > "semantic" dependency due to a value being "necessary" to compute a
    > result seems better. However, whether a value is "necessary" might not
    > be obvious, and I understand Paul's argument that he does not want to
    > have to reason about all potential compiler optimizations. Thus, I
    > believe we need to specify when a value is "necessary".

    I suspect it's hard to really strictly define, but at the same time I
    actually think that compiler writers (and users, for that matter) have
    little problem understanding the concept and intent.

    I do think that listing operations might be useful to give good
    examples of what is a "necessary" value, and - perhaps more
    importantly - what can break the value from being "necessary".
    Especially the gotchas.

    > I have a suggestion for a somewhat different formulation of the feature
    > that you seem to have in mind, which I'll discuss below. Excuse the
    > verbosity of the following, but I'd rather like to avoid
    > misunderstandings than save a few words.

    Ok, I'm going to cut most of the verbiage since it's long and I'm not
    commenting on most of it.

    But

    > Based on these thoughts, we could specify the new mo_consume guarantees
    > roughly as follows:
    >
    > An evaluation E (in an execution) has a value dependency to an
    > atomic and mo_consume load L (in an execution) iff:
    > * L's type holds more than one value (ruling out constants
    > etc.),
    > * L is sequenced-before E,
    > * L's result is used by the abstract machine to compute E,
    > * E is value-dependency-preserving code (defined below), and
    > * at the time of execution of E, L can possibly have returned at
    > least two different values under the assumption that L itself
    > could have returned any value allowed by L's type.
    >
    > If a memory access A's targeted memory location has a value
    > dependency on a mo_consume load L, and an action X
    > inter-thread-happens-before L, then X happens-before A.

    I think this mostly works.

    > Regarding the latter, we make a fresh start at each mo_consume load (ie,
    > we assume we know nothing -- L could have returned any possible value);
    > I believe this is easier to reason about than other scopes like function
    > granularities (what happens on inlining?), or translation units. It
    > should also be simple to implement for compilers, and would hopefully
    > not constrain optimization too much.
    >
    > [...]
    >
    > Paul's litmus test would work, because we guarantee to the programmer
    > that it can assume that the mo_consume load would return any value
    > allowed by the type; effectively, this forbids the compiler analysis
    > Paul thought about:

    So realistically, since with the new wording we can ignore the silly
    cases (ie "p-p") and we can ignore the trivial-to-optimize compiler
    cases ("if (p == &variable) .. use p"), and you would forbid the
    "global value range optimization case" that Paul bright up, what
    remains would seem to be just really subtle compiler transformations
    of data dependencies to control dependencies.

    And the only such thing I can think of is basically compiler-initiated
    value-prediction, presumably directed by PGO (since now if the value
    prediction is in the source code, it's considered to break the value
    chain).

    The good thing is that afaik, value-prediction is largely not used in
    real life, afaik. There are lots of papers on it, but I don't think
    anybody actually does it (although I can easily see some
    specint-specific optimization pattern that is build up around it).

    And even value prediction is actually fine, as long as the compiler
    can see the memory *source* of the value prediction (and it isn't a
    mo_consume). So it really ends up limiting your value prediction in
    very simple ways: you cannot do it to function arguments if they are
    registers. But you can still do value prediction on values you loaded
    from memory, if you can actually *see* that memory op.

    Of course, on more strongly ordered CPU's, even that "register
    argument" limitation goes away.

    So I agree that there is basically no real optimization constraint.
    Value-prediction is of dubious value to begin with, and the actual
    constraint on its use if some compiler writer really wants to is not
    onerous.

    > What I have in mind is roughly the following (totally made-up syntax --
    > suggestions for how to do this properly are very welcome):
    > * Have a type modifier (eg, like restrict), that specifies that
    > operations on data of this type are preserving value dependencies:

    So I'm not violently opposed, but I think the upsides are not great.
    Note that my earlier suggestion to use "restrict" wasn't because I
    believed the annotation itself would be visible, but basically just as
    a legalistic promise to the compiler that *if* it found an alias, then
    it didn't need to worry about ordering. So to me, that type modifier
    was about conceptual guarantees, not about actual value chains.

    Anyway, the reason I don't believe any type modifier (and
    "[[carries_dependency]]" is basically just that) is worth it is simply
    that it adds a real burden on the programmer, without actually giving
    the programmer any real upside:

    Within a single function, the compiler already sees that mo_consume
    source, and so doing a type-based restriction doesn't really help. The
    information is already there, without any burden on the programmer.

    And across functions, the compiler has already - by definition -
    mostly lost sight of all the things it could use to reduce the value
    space. Even Paul's example doesn't really work if the use of the
    "mo_consume" value has been passed to another function, because inside
    a separate function, the compiler couldn't see that the value it uses
    comes from only two possible values.

    And as mentioned, even *if* the compiler wants to do value prediction
    that turns a data dependency into a control dependency, the limitation
    to say "no, you can't do it unless you saw where the value got loaded"
    really isn't that onerous.

    I bet that if you ask actual production compiler people (as opposed to
    perhaps academia), none of them actually really believe in value
    prediction to begin with.

    > What do you think?
    >
    > Is this meaningful regarding what current hardware offers, or will it do
    > (or might do in the future) value prediction on it's own?

    I can pretty much guarantee that when/if hardware does value
    prediction on its own, it will do so without exposing it as breaking
    the data dependency.

    The thing is, a CPU is actually *much* better situated at doing
    speculative memory accesses, because a CPU already has all the
    infrastructure to do speculation in general.

    And for a CPU, once you do value speculation, guaranteeing the memory
    ordering is *trivial*: all you need to do is to track the "speculated"
    memory instruction until you check the value (which you obviously have
    to do anyway, otherwise you're not doing value _prediction_, you're
    just doing "value wild guessing" ;^), and when you check the value you
    also check that the cacheline hasn't been evicted out-of-order.

    This is all stuff that CPU people already do. If you have
    transactional memory, you already have all the resources to do this.
    Or, even without transactional memory, if like Intel you have a memory
    model that says "loads are done in order" but you actually wildly
    speculate loads and just check before retiring instructions that the
    cachelines didn't get evicted out of order, you already have all the
    hardware to do value prediction *without* making it visible in the
    memory order.

    This, btw, is one reason why people who think that compilers should be
    overly smart and do fancy tricks are incompetent. People who thought
    that Itanium was a great idea ("Let's put the complexity in the
    compiler, and make a simple CPU") are simply objectively *wrong*.
    People who think that value prediction by a compiler is a good idea
    are not people you should really care about.

    Linus


    \
     
     \ /
      Last update: 2014-02-27 18:41    [W:3.302 / U:0.024 seconds]
    ©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site