Bisecting revealed commit r270559

Author: Than McIntosh <thanm@google.com>
Date:   Tue May 24 13:23:44 2016 +0000

    Rework/enhance stack coloring data flow analysis.

    Replace bidirectional flow analysis to compute liveness with forward
    analysis pass. Treat lifetimes as starting when there is a first
    reference to the stack slot, as opposed to starting at the point of the
    lifetime.start intrinsic, so as to increase the number of stack
    variables we can overlap.

    Reviewers: gbiv, qcolumbet, wmi
    Differential Revision: http://reviews.llvm.org/D18827

    Bug: 25776

being the cause. I assume this just revealed a bug in Polly. I find this somewhat surprising since I had SPEC2006 passing well after May last year. The only explanation I have is that test-suite/lnt changed as well since then (both were trunk and not bisected).

The issue are the lifetime markers left behind by Polly. They are removed from the generated code, but the original code still contains them. 

In particular, the code before Polly was:

    llvm.lifetime.start(&var)
    [...]
    llvm.lifetime.end(&var)

The code after Polly looks like:

    if (VersioningCond) {
    } else {
      llvm.lifetime.start(&var)
    }
    [...]
    llvm.lifetime.end(&var)

Such that there are execution paths (the one taken in the test-suite execution) where llvm.lifetime.start is not executed before llvm.lifetime.end. According the semantics in http://llvm.org/docs/LangRef.html#llvm-lifetime-start-intrinsic this doesn't seem wrong. It just means that &var is never dead before the llvm.lifetime.end marker.

This variant fixes it:

    if (VersioningCond) {
      llvm.lifetime.start(&var)
    } else {
      llvm.lifetime.start(&var)
    }
    [...]
    llvm.lifetime.end(&var)


I don't know whether the fault is at Polly to generate such code or with http://reviews.llvm.org/D18827 which does not correctly interpret the lifetimes. If it's Polly's fault, then I don't still know whether the second version is correct or does not miscompile because of other reasons. Polly at the moment cannot ensure the correct positioning of llvm.lifetime.start (that is, before every use that originally comes after llvm.lifetime.start)

What's happening here is that stack coloring is deciding to overlap stack slot 0 (corresponding to the variable "iterations") with stack slot 1 (corresponding to the variable "simParams"), which is definitely incorrect -- these variables do not have disjoint lifetimes.

Looking at the IR in the base (-O3, no polly) case, the lifetime start marker for "iterations" appears towards the end of the entry block, meaning that the code for the first few lines of the functions looks roughly like

    define i32 @main(i32 %argc, i8** nocapture readonly %argv) ...
    entry:
      %iterations = alloca i32, align 4
      %simParams = alloca %class.SimParameters, align 8
      ...
      %comp = alloca %class.ResultSet, align 8
      %0 = bitcast i32* %iterations to i8*
      call void @llvm.lifetime.start(i64 4, i8* nonnull %0) #11
      store i32 -1, i32* %iterations, align 4, !tbaa !1
      %sub = and i32 %argc, 1
      %tobool = icmp eq i32 %sub, 0
      br i1 %tobool, label %if.then, label %for.cond.preheader

    ...

    if.then:                                          ; preds = %entry
      %2 = load i8*, i8** %argv, align 8, !tbaa !5
      tail call void @_z10exit_usagepkc(i8* %2)
      unreachable

This is the normal pattern for a function's top-level local variables (e.g. lifetime start appears in the entry block). Looking at the coming into the optimizer with Polly turned on, I see the following instead:

    define i32 @main(i32 %argc, i8** nocapture readonly %argv) local_unnamed_addr #3 personality i8* bitcast (i32 (...)* @__gxx_personality_v0 to i8*) {
    entry:
      %iterations = alloca i32, align 4
      %0 = bitcast i32* %iterations to i8*
      %simParams = alloca %class.SimParameters, align 8
      ...
      %comp = alloca %class.ResultSet, align 8
      %1 = and i32 %argc, 1
      %2 = icmp eq i32 %1, 0
      br i1 %2, label %if.then, label %for.cond.preheader

    if.then:                                          ; preds = %entry
      call void @llvm.lifetime.start(i64 4, i8* nonnull %0) #11
      %3 = load i8*, i8** %argv, align 8, !tbaa !1
      tail call void @_Z10exit_usagePKc(i8* %3)
      unreachable

    for.cond.preheader:                               ; preds = %entry
      store i32 -1, i32* %iterations, align 4, !alias.scope !5, !noalias !7
      %cmp528 = icmp sgt i32 %argc, 1
      br i1 %cmp528, label %for.body.lr.ph, label %if.then50

Note that the lifetime start marker for "iterations" has been relocated, pushed down into the block containing the no-return call to exit (oddly, the bitcast feeding the lifetime start still seems to be stuck up in the entry block, not sure why). It would be nice to understand why the initial placement of the markers is happening this way.

The current implementation of stack coloring uses forward data flow analysis, meaning that it computes live intervals by propagating uses of a given slot in block N to N's successors, until hitting a "lifetime end" marker for the slot.

In addition, a given slot is classified as "normal" or "conservative", where "normal" implies that all uses of the slot are dominated by the lifetime start marker and "conservative" means that we found some path from the entry block to a use of a slot that didn't go through a start marker for the slot.

For "normal" slots, the live interval for the slot is treated as starting at the first use for it after the start marker, whereas for "conservative" slots we treat the marker itself as the start of the lifetime (for more detail on this, see http://llvm.org/viewvc/llvm-project/llvm/trunk/lib/CodeGen/StackColoring.cpp?view=markup&pathrev=297904#l161).

In this case the slots for both "iterations" and "simParams" are being treated conservatively, however the conservative treatment doesn't help much due to the migration of the start lifetime for slot 0 out of the entry block. 

The reason this case works with the old version of stack coloring was that it used bidirectional flow analysis -- propagating not just from first uses down to lifetime ends, but also backwards (from a use block back to its predecessors), upwards within the control flow graph. This produces a more extensive lifetime for the "iterations" slot, resulting in an interference between the two slots that inhibits overlap.

I don't see an easy fix for this in StackColoring, short of going back to the bidirectional scheme. The old bidirectional analysis would "fix" the problem in this specific instance, but it is easy to think of examples where the bidirectional method would also fail if optimization passes are allowed to arbitrarily relocate markers.

I think at some level or another stack coloring has to trust that the lifetime start/end markers are a source of "truth". If optimization passes prior to stack coloring can move markers wherever they want, then there is really no point looking at the markers at all (which would greatly impair the effectiveness of stack coloring).

Fixed in r299585.

However, I am leaving this bug open because while r299585 fixes the problem for 444.namd, it may not fix it in the general case.

Given that the lifetime start itself is a conditional that is outside of the SCoP;

    if (c) {
      llvm.lifetime.start(&var)
        [...]
    } else {
      llvm.lifetime.start(&var)
        [...]
    }
    [...]
    llvm.lifetime.end(&var)

then after r299585 we would generate

    if (c) {
      if (VersioningCond) {
        [...]
      } else {
        [...]
      }
    } else {
      llvm.lifetime.start(&var)
        [...]
    }
    [...]
    llvm.lifetime.end(&var)

Where again some paths cross llvm.lifetime.start while others don't.

According the the required form suggested by Daniel Berlin in
http://lists.llvm.org/pipermail/llvm-dev/2017-March/111669.html
we need to hoist the llvm.ifetime.start markers to before the loop versioning, respectively sink the llvm.ifetime.end markers behind it:

    if (c) {
      llvm.lifetime.start(&var)
      if (VersioningCond) {
        [...]
      } else {
        [...]
      }
    } else {
      llvm.lifetime.start(&var)
        [...]
    }
    [...]
    llvm.lifetime.end(&var)