StackColoring can wrongly merge stack slots: marker semantics poorly defined

[Quuxplusone]

Bugzilla Link	PR16095
Status	NEW
Importance	P normal
Reported by	Mark Seaborn (mseaborn@chromium.org)
Reported on	2013-05-21 12:19:00 -0700
Last modified on	2013-05-22 12:40:03 -0700
Version	trunk
Hardware	All All
CC	evan.cheng@apple.com, geek4civic@gmail.com, llvm-bugs@lists.llvm.org, nadav.rotem@me.com, rafael@espindo.la
Fixed by commit(s)
Attachments
Blocks
Blocked by
See also

LLVM's StackColoring pass wrongly merges the stack slots %buf1 and %buf2 in the
following example:

declare void @llvm.lifetime.start(i64, i8*)
declare void @llvm.lifetime.end(i64, i8*)
declare void @ext_func(i8*)

define void @mycall(i8* %addr) {
  %buf1 = alloca i8, i32 100000
  %buf2 = alloca i8, i32 100000

  ; If the alloca reference is sufficiently deeply nested,
  ; GetUnderlyingObject() won't look through it.
  %buf2_cast1 = bitcast i8* %buf2 to i8*
  %buf2_cast2 = bitcast i8* %buf2_cast1 to i8*
  %buf2_cast3 = bitcast i8* %buf2_cast2 to i8*
  %buf2_cast4 = bitcast i8* %buf2_cast3 to i8*
  %buf2_cast5 = bitcast i8* %buf2_cast4 to i8*
  %buf2_cast6 = bitcast i8* %buf2_cast5 to i8*
  %buf2_cast7 = bitcast i8* %buf2_cast6 to i8*

  call void @llvm.lifetime.start(i64 -1, i8* %buf2)
  call void @llvm.lifetime.end(i64 -1, i8* %buf2)
  ; lifetime.end(%buf2) means that %buf2 is dead here.

  call void @llvm.lifetime.start(i64 -1, i8* %buf1)
  call void @ext_func(i8* %buf1)

  call void @llvm.lifetime.start(i64 -1, i8* %buf2_cast7)

  ; Both %buf1 and %buf2 are live at this point, but StackColoring
  ; will wrongly regard %buf2 as dead and merge it with %buf1.
  call void @ext_func(i8* %buf2)

  ret void
}

Actual output:

$ llc -mtriple=x86_64-none-gnu stack-coloring.ll -o -
...
        subq    $100008, %rsp           # imm = 0x186A8
...

Expected output, which also occurs if we change the last lifetime.start() to
use %buf2_cast6 instead of %buf2_cast7:

$ llc -mtriple=x86_64-none-gnu stack-coloring.ll -o -
...
        subq    $200008, %rsp           # imm = 0x30D48
...

This happens because SelectionDAGBuilder uses GetUnderlyingObjects() to find
the alloca instructions that a lifetime.start() or end() call refers to.  But
GetUnderlyingObjects() has a default MaxLookup limit of 6.

As a result, StackColoring only sees a subset of the lifetime markers.  But
ignoring subsets of the lifetime markers is not safe in general, because a
lifetime.start marker counteracts the effect of a lifetime.end marker (as
above), and vice versa.

The semantics of lifetime.start/end currently aren't very well defined.  The
LLVM Language Reference doesn't specify whether bitcasts/GEPs/PHIs of allocas
are valid arguments to lifetime.start/end.  Given that this affects the
safeness of the StackColoring, this should probably be fixed.

[Quuxplusone]

Cloned to PR13951422.

[Quuxplusone]

Mark, can you try to run this with the 'ProtectFromEscapeAllocas' flag ?

We have code for detecting escaped allocas but the current behavior is not to do anything. If you enable this flag it will assert on debug mode. We can easily change it to ignore the escaped alloca.

[Quuxplusone]

xref: rdar://13951422