test/Transforms/InstCombine/bitreverse-hang.ll

   1 ; RUN: opt < %s -loop-unroll -instcombine -S | FileCheck %s
   2
   3 ; This test is a worst-case scenario for bitreversal/byteswap detection.
   4 ; After loop unrolling (the unrolled loop is unreadably large so it has been kept
   5 ; rolled here), we have a binary tree of OR operands (as bitreversal detection
   6 ; looks straight through shifts):
   7 ;
   8 ;  OR
   9 ;  | \
  10 ;  |  LSHR
  11 ;  | /
  12 ;  OR
  13 ;  | \
  14 ;  |  LSHR
  15 ;  | /
  16 ;  OR
  17 ;
  18 ; This results in exponential runtime. The loop here is 32 iterations which will
  19 ; totally hang if we don't deal with this case cleverly.
  20
  21 @b = common global i32 0, align 4
  22
  23 ; CHECK: define i32 @fn1
  24 define i32 @fn1() #0 {
  25 entry:
  26   %b.promoted = load i32, i32* @b, align 4, !tbaa !2
  27   br label %for.body
  28
  29 for.body:                                         ; preds = %for.body, %entry
  30   %or4 = phi i32 [ %b.promoted, %entry ], [ %or, %for.body ]
  31   %i.03 = phi i32 [ 0, %entry ], [ %inc, %for.body ]
  32   %shr = lshr i32 %or4, 1
  33   %or = or i32 %shr, %or4
  34   %inc = add nuw nsw i32 %i.03, 1
  35   %exitcond = icmp eq i32 %inc, 32
  36   br i1 %exitcond, label %for.end, label %for.body
  37
  38 for.end:                                          ; preds = %for.body
  39   store i32 %or, i32* @b, align 4, !tbaa !2
  40   ret i32 undef
  41 }
  42
  43 attributes #0 = { norecurse nounwind ssp uwtable "disable-tail-calls"="false" "less-precise-fpmad"="false" "no-frame-pointer-elim"="true" "no-frame-pointer-elim-non-leaf" "no-infs-fp-math"="false" "no-nans-fp-math"="false" "stack-protector-buffer-size"="8" "target-cpu"="core2" "target-features"="+cx16,+fxsr,+mmx,+sse,+sse2,+sse3,+ssse3" "unsafe-fp-math"="false" "use-soft-float"="false" }
  44
  45 !llvm.module.flags = !{!0}
  46 !llvm.ident = !{!1}
  47
  48 !0 = !{i32 1, !"PIC Level", i32 2}
  49 !1 = !{!"clang version 3.8.0"}
  50 !2 = !{!3, !3, i64 0}
  51 !3 = !{!"int", !4, i64 0}
  52 !4 = !{!"omnipotent char", !5, i64 0}
  53 !5 = !{!"Simple C/C++ TBAA"}