Invalid optimization in the presence of shift instructions?

[Quuxplusone]

Bugzilla Link	PR34133
Status	NEW
Importance	P normal
Reported by	Cristian Cadar (c.cadar@imperial.ac.uk)
Reported on	2017-08-09 03:58:19 -0700
Last modified on	2017-09-17 07:33:51 -0700
Version	trunk
Hardware	PC Linux
CC	dan@su-root.co.uk, ditaliano@apple.com, efriedma@quicinc.com, llvm-bugs@lists.llvm.org, llvm-dev@redking.me.uk, nunoplopes@sapo.pt, regehr@cs.utah.edu, sanjoy@playingwithpointers.com, spatel+llvm@rotateright.com
Fixed by commit(s)
Attachments
Blocks
Blocked by
See also	PR20997

Consider the program below:

$ cat shift.c
int a = 0;
int foo(int x) { return (a < 2) || (a >> x) ; }

int main() {
  return foo(100);
}

$ clang -O1 -emit-llvm -c shift.c
$ llvm-dis shift.bc
$ cat shift.ll
...
define i32 @foo(i32) local_unnamed_addr #0 {
  %2 = load i32, i32* @a, align 4, !tbaa !1
  %3 = icmp slt i32 %2, 2
  %4 = ashr i32 %2, %0
  %5 = icmp ne i32 %4, 0
  %6 = or i1 %3, %5
  %7 = zext i1 %6 to i32
  ret i32 %7
}
...
define i32 @main() local_unnamed_addr #0 {
  %1 = tail call i32 @foo(i32 100)
  ret i32 %1
}
...

Note that in the C code, the || operator has short-circuiting
behaviour, so "a >> x" should not be evaluated since the first clause
is true.  However, the optimization generates code that always
executes the corresponding ashr instruction, which has undefined
behaviour in this case, as the shift amount is 100.  So is this
optimization valid?

We discovered this while working with KLEE, which generates an
overshift error when the code is compiled with -O1, but not with -O0,
so we'd like to understand whether KLEE's behaviour is correct here.
Note that UBSan does not complain here, as its instrumentation
disables the optimization.

Thank you,
Cristian

[Quuxplusone]

Yes, there's a known bug here. See http://lists.llvm.org/pipermail/llvm-dev/2017-May/113272.html .

[Quuxplusone]

Yes, there's a known bug here. See http://lists.llvm.org/pipermail/llvm-dev/2017-May/113272.html .

@Eli : Is there a bug on bugzilla tracking this?

Just to note the sequence of optimization passes for this example is

sroa, early-cse, simplifycfg, instcombine

Without the instcombine the IR contains a select instruction which is what is discussed in mailing list post linked to.

You can see this by running something like this

clang -O0 -S -emit-llvm -o - shift.c  | opt -S -print-after-all
-print-before-all -filter-print-funcs=foo -sroa -early-cse
-simplifycfg -instcombine 2>&1 > /dev/null
| less

[Quuxplusone]

There's at least https://bugs.llvm.org/show_bug.cgi?id=20997
It's the same problem.