From 45ddb245c50c2f3a109ad22174e9b52ad6de0ac7 Mon Sep 17 00:00:00 2001 From: Roman Lebedev Date: Tue, 3 Nov 2020 20:19:45 +0300 Subject: [PATCH] [NFC][LoopIdiom] Add basic test coverage for 'left-shift until bittest` idiom --- .../LoopIdiom/X86/left-shift-until-bittest.ll | 764 +++++++++++++++++++++ 1 file changed, 764 insertions(+) create mode 100644 llvm/test/Transforms/LoopIdiom/X86/left-shift-until-bittest.ll diff --git a/llvm/test/Transforms/LoopIdiom/X86/left-shift-until-bittest.ll b/llvm/test/Transforms/LoopIdiom/X86/left-shift-until-bittest.ll new file mode 100644 index 0000000..6e3e5f7 --- /dev/null +++ b/llvm/test/Transforms/LoopIdiom/X86/left-shift-until-bittest.ll @@ -0,0 +1,764 @@ +; NOTE: Assertions have been autogenerated by utils/update_test_checks.py +; RUN: opt -debugify -loop-idiom -mtriple=x86_64 -mcpu=core-avx2 < %s -S | FileCheck -check-prefixes=ALL,LZCNT %s +; RUN: opt -debugify -loop-idiom -mtriple=x86_64 -mcpu=corei7 < %s -S | FileCheck -check-prefixes=ALL,NOLZCNT %s + +declare i32 @gen32() +declare void @use32(i32) +declare void @use1(i1) +declare void @external_side_effect() + +; The patterns here are all have the same base form: +; while (!(x & (1U << bit))) +; x <<= 1; +; .. which is an uncountable loop. +; We should transform it into it's countable form. + +; Most basic example. +define i32 @p0_32(i32 %x, i32 %bit) { +; ALL-LABEL: @p0_32( +; ALL-NEXT: entry: +; ALL-NEXT: [[BITMASK:%.*]] = shl i32 1, [[BIT:%.*]], [[DBG16:!dbg !.*]] +; ALL-NEXT: call void @llvm.dbg.value(metadata i32 [[BITMASK]], [[META9:metadata !.*]], metadata !DIExpression()), [[DBG16]] +; ALL-NEXT: br label [[LOOP:%.*]], [[DBG17:!dbg !.*]] +; ALL: loop: +; ALL-NEXT: [[X_CURR:%.*]] = phi i32 [ [[X:%.*]], [[ENTRY:%.*]] ], [ [[X_NEXT:%.*]], [[LOOP]] ], [[DBG18:!dbg !.*]] +; ALL-NEXT: call void @llvm.dbg.value(metadata i32 [[X_CURR]], [[META11:metadata !.*]], metadata !DIExpression()), [[DBG18]] +; ALL-NEXT: [[X_CURR_BITMASKED:%.*]] = and i32 [[X_CURR]], [[BITMASK]], [[DBG19:!dbg !.*]] +; ALL-NEXT: call void @llvm.dbg.value(metadata i32 [[X_CURR_BITMASKED]], [[META12:metadata !.*]], metadata !DIExpression()), [[DBG19]] +; ALL-NEXT: [[X_CURR_ISBITUNSET:%.*]] = icmp eq i32 [[X_CURR_BITMASKED]], 0, [[DBG20:!dbg !.*]] +; ALL-NEXT: call void @llvm.dbg.value(metadata i1 [[X_CURR_ISBITUNSET]], [[META13:metadata !.*]], metadata !DIExpression()), [[DBG20]] +; ALL-NEXT: [[X_NEXT]] = shl i32 [[X_CURR]], 1, [[DBG21:!dbg !.*]] +; ALL-NEXT: call void @llvm.dbg.value(metadata i32 [[X_NEXT]], [[META15:metadata !.*]], metadata !DIExpression()), [[DBG21]] +; ALL-NEXT: br i1 [[X_CURR_ISBITUNSET]], label [[LOOP]], label [[END:%.*]], [[DBG22:!dbg !.*]] +; ALL: end: +; ALL-NEXT: [[X_CURR_LCSSA:%.*]] = phi i32 [ [[X_CURR]], [[LOOP]] ], [[DBG18]] +; ALL-NEXT: call void @llvm.dbg.value(metadata i32 [[X_CURR_LCSSA]], [[META11]], metadata !DIExpression()), [[DBG18]] +; ALL-NEXT: ret i32 [[X_CURR_LCSSA]], [[DBG23:!dbg !.*]] +; +entry: + %bitmask = shl i32 1, %bit + br label %loop + +loop: + %x.curr = phi i32 [ %x, %entry ], [ %x.next, %loop ] + %x.curr.bitmasked = and i32 %x.curr, %bitmask + %x.curr.isbitunset = icmp eq i32 %x.curr.bitmasked, 0 + %x.next = shl i32 %x.curr, 1 + br i1 %x.curr.isbitunset, label %loop, label %end + +end: + ret i32 %x.curr +} + +; Same, but in some other bit width. +define i16 @p0_16(i16 %x, i16 %bit) { +; ALL-LABEL: @p0_16( +; ALL-NEXT: entry: +; ALL-NEXT: [[BITMASK:%.*]] = shl i16 1, [[BIT:%.*]], [[DBG32:!dbg !.*]] +; ALL-NEXT: call void @llvm.dbg.value(metadata i16 [[BITMASK]], [[META26:metadata !.*]], metadata !DIExpression()), [[DBG32]] +; ALL-NEXT: br label [[LOOP:%.*]], [[DBG33:!dbg !.*]] +; ALL: loop: +; ALL-NEXT: [[X_CURR:%.*]] = phi i16 [ [[X:%.*]], [[ENTRY:%.*]] ], [ [[X_NEXT:%.*]], [[LOOP]] ], [[DBG34:!dbg !.*]] +; ALL-NEXT: call void @llvm.dbg.value(metadata i16 [[X_CURR]], [[META28:metadata !.*]], metadata !DIExpression()), [[DBG34]] +; ALL-NEXT: [[X_CURR_BITMASKED:%.*]] = and i16 [[X_CURR]], [[BITMASK]], [[DBG35:!dbg !.*]] +; ALL-NEXT: call void @llvm.dbg.value(metadata i16 [[X_CURR_BITMASKED]], [[META29:metadata !.*]], metadata !DIExpression()), [[DBG35]] +; ALL-NEXT: [[X_CURR_ISBITUNSET:%.*]] = icmp eq i16 [[X_CURR_BITMASKED]], 0, [[DBG36:!dbg !.*]] +; ALL-NEXT: call void @llvm.dbg.value(metadata i1 [[X_CURR_ISBITUNSET]], [[META30:metadata !.*]], metadata !DIExpression()), [[DBG36]] +; ALL-NEXT: [[X_NEXT]] = shl i16 [[X_CURR]], 1, [[DBG37:!dbg !.*]] +; ALL-NEXT: call void @llvm.dbg.value(metadata i16 [[X_NEXT]], [[META31:metadata !.*]], metadata !DIExpression()), [[DBG37]] +; ALL-NEXT: br i1 [[X_CURR_ISBITUNSET]], label [[LOOP]], label [[END:%.*]], [[DBG38:!dbg !.*]] +; ALL: end: +; ALL-NEXT: [[X_CURR_LCSSA:%.*]] = phi i16 [ [[X_CURR]], [[LOOP]] ], [[DBG34]] +; ALL-NEXT: call void @llvm.dbg.value(metadata i16 [[X_CURR_LCSSA]], [[META28]], metadata !DIExpression()), [[DBG34]] +; ALL-NEXT: ret i16 [[X_CURR_LCSSA]], [[DBG39:!dbg !.*]] +; +entry: + %bitmask = shl i16 1, %bit + br label %loop + +loop: + %x.curr = phi i16 [ %x, %entry ], [ %x.next, %loop ] + %x.curr.bitmasked = and i16 %x.curr, %bitmask + %x.curr.isbitunset = icmp eq i16 %x.curr.bitmasked, 0 + %x.next = shl i16 %x.curr, 1 + br i1 %x.curr.isbitunset, label %loop, label %end + +end: + ret i16 %x.curr +} + +; Check that loop backedge's cmp-br order is correctly handled +define i32 @p1(i32 %x, i32 %bit) { +; ALL-LABEL: @p1( +; ALL-NEXT: entry: +; ALL-NEXT: [[BITMASK:%.*]] = shl i32 1, [[BIT:%.*]], [[DBG47:!dbg !.*]] +; ALL-NEXT: call void @llvm.dbg.value(metadata i32 [[BITMASK]], [[META42:metadata !.*]], metadata !DIExpression()), [[DBG47]] +; ALL-NEXT: br label [[LOOP:%.*]], [[DBG48:!dbg !.*]] +; ALL: loop: +; ALL-NEXT: [[X_CURR:%.*]] = phi i32 [ [[X:%.*]], [[ENTRY:%.*]] ], [ [[X_NEXT:%.*]], [[LOOP]] ], [[DBG49:!dbg !.*]] +; ALL-NEXT: call void @llvm.dbg.value(metadata i32 [[X_CURR]], [[META43:metadata !.*]], metadata !DIExpression()), [[DBG49]] +; ALL-NEXT: [[X_CURR_BITMASKED:%.*]] = and i32 [[X_CURR]], [[BITMASK]], [[DBG50:!dbg !.*]] +; ALL-NEXT: call void @llvm.dbg.value(metadata i32 [[X_CURR_BITMASKED]], [[META44:metadata !.*]], metadata !DIExpression()), [[DBG50]] +; ALL-NEXT: [[X_CURR_ISBITUNSET:%.*]] = icmp ne i32 [[X_CURR_BITMASKED]], 0, [[DBG51:!dbg !.*]] +; ALL-NEXT: call void @llvm.dbg.value(metadata i1 [[X_CURR_ISBITUNSET]], [[META45:metadata !.*]], metadata !DIExpression()), [[DBG51]] +; ALL-NEXT: [[X_NEXT]] = shl i32 [[X_CURR]], 1, [[DBG52:!dbg !.*]] +; ALL-NEXT: call void @llvm.dbg.value(metadata i32 [[X_NEXT]], [[META46:metadata !.*]], metadata !DIExpression()), [[DBG52]] +; ALL-NEXT: br i1 [[X_CURR_ISBITUNSET]], label [[END:%.*]], label [[LOOP]], [[DBG53:!dbg !.*]] +; ALL: end: +; ALL-NEXT: [[X_CURR_LCSSA:%.*]] = phi i32 [ [[X_CURR]], [[LOOP]] ], [[DBG49]] +; ALL-NEXT: call void @llvm.dbg.value(metadata i32 [[X_CURR_LCSSA]], [[META43]], metadata !DIExpression()), [[DBG49]] +; ALL-NEXT: ret i32 [[X_CURR_LCSSA]], [[DBG54:!dbg !.*]] +; +entry: + %bitmask = shl i32 1, %bit + br label %loop + +loop: + %x.curr = phi i32 [ %x, %entry ], [ %x.next, %loop ] + %x.curr.bitmasked = and i32 %x.curr, %bitmask + %x.curr.isbitunset = icmp ne i32 %x.curr.bitmasked, 0 ; swapped predicate + %x.next = shl i32 %x.curr, 1 + br i1 %x.curr.isbitunset, label %end, label %loop ; swapped dests + +end: + ret i32 %x.curr +} + +; `and` is commutative, so ensure that order is irrelevant +define i32 @p2(i32 %x, i32 %bit) { +; ALL-LABEL: @p2( +; ALL-NEXT: entry: +; ALL-NEXT: [[BITMASK:%.*]] = shl i32 1, [[BIT:%.*]], [[DBG62:!dbg !.*]] +; ALL-NEXT: call void @llvm.dbg.value(metadata i32 [[BITMASK]], [[META57:metadata !.*]], metadata !DIExpression()), [[DBG62]] +; ALL-NEXT: br label [[LOOP:%.*]], [[DBG63:!dbg !.*]] +; ALL: loop: +; ALL-NEXT: [[X_CURR:%.*]] = phi i32 [ [[X:%.*]], [[ENTRY:%.*]] ], [ [[X_NEXT:%.*]], [[LOOP]] ], [[DBG64:!dbg !.*]] +; ALL-NEXT: call void @llvm.dbg.value(metadata i32 [[X_CURR]], [[META58:metadata !.*]], metadata !DIExpression()), [[DBG64]] +; ALL-NEXT: [[X_CURR_BITMASKED:%.*]] = and i32 [[BITMASK]], [[X_CURR]], [[DBG65:!dbg !.*]] +; ALL-NEXT: call void @llvm.dbg.value(metadata i32 [[X_CURR_BITMASKED]], [[META59:metadata !.*]], metadata !DIExpression()), [[DBG65]] +; ALL-NEXT: [[X_CURR_ISBITUNSET:%.*]] = icmp eq i32 [[X_CURR_BITMASKED]], 0, [[DBG66:!dbg !.*]] +; ALL-NEXT: call void @llvm.dbg.value(metadata i1 [[X_CURR_ISBITUNSET]], [[META60:metadata !.*]], metadata !DIExpression()), [[DBG66]] +; ALL-NEXT: [[X_NEXT]] = shl i32 [[X_CURR]], 1, [[DBG67:!dbg !.*]] +; ALL-NEXT: call void @llvm.dbg.value(metadata i32 [[X_NEXT]], [[META61:metadata !.*]], metadata !DIExpression()), [[DBG67]] +; ALL-NEXT: br i1 [[X_CURR_ISBITUNSET]], label [[LOOP]], label [[END:%.*]], [[DBG68:!dbg !.*]] +; ALL: end: +; ALL-NEXT: [[X_CURR_LCSSA:%.*]] = phi i32 [ [[X_CURR]], [[LOOP]] ], [[DBG64]] +; ALL-NEXT: call void @llvm.dbg.value(metadata i32 [[X_CURR_LCSSA]], [[META58]], metadata !DIExpression()), [[DBG64]] +; ALL-NEXT: ret i32 [[X_CURR_LCSSA]], [[DBG69:!dbg !.*]] +; +entry: + %bitmask = shl i32 1, %bit + br label %loop + +loop: + %x.curr = phi i32 [ %x, %entry ], [ %x.next, %loop ] + %x.curr.bitmasked = and i32 %bitmask, %x.curr ; swapped + %x.curr.isbitunset = icmp eq i32 %x.curr.bitmasked, 0 + %x.next = shl i32 %x.curr, 1 + br i1 %x.curr.isbitunset, label %loop, label %end + +end: + ret i32 %x.curr +} + +; PHI node does not have any particular order for it's incomings, +; but check that the other order still works. +define i32 @p3(i32 %x, i32 %bit) { +; ALL-LABEL: @p3( +; ALL-NEXT: entry: +; ALL-NEXT: [[BITMASK:%.*]] = shl i32 1, [[BIT:%.*]], [[DBG77:!dbg !.*]] +; ALL-NEXT: call void @llvm.dbg.value(metadata i32 [[BITMASK]], [[META72:metadata !.*]], metadata !DIExpression()), [[DBG77]] +; ALL-NEXT: br label [[LOOP:%.*]], [[DBG78:!dbg !.*]] +; ALL: loop: +; ALL-NEXT: [[X_CURR:%.*]] = phi i32 [ [[X_NEXT:%.*]], [[LOOP]] ], [ [[X:%.*]], [[ENTRY:%.*]] ], [[DBG79:!dbg !.*]] +; ALL-NEXT: call void @llvm.dbg.value(metadata i32 [[X_CURR]], [[META73:metadata !.*]], metadata !DIExpression()), [[DBG79]] +; ALL-NEXT: [[X_CURR_BITMASKED:%.*]] = and i32 [[X_CURR]], [[BITMASK]], [[DBG80:!dbg !.*]] +; ALL-NEXT: call void @llvm.dbg.value(metadata i32 [[X_CURR_BITMASKED]], [[META74:metadata !.*]], metadata !DIExpression()), [[DBG80]] +; ALL-NEXT: [[X_CURR_ISBITUNSET:%.*]] = icmp eq i32 [[X_CURR_BITMASKED]], 0, [[DBG81:!dbg !.*]] +; ALL-NEXT: call void @llvm.dbg.value(metadata i1 [[X_CURR_ISBITUNSET]], [[META75:metadata !.*]], metadata !DIExpression()), [[DBG81]] +; ALL-NEXT: [[X_NEXT]] = shl i32 [[X_CURR]], 1, [[DBG82:!dbg !.*]] +; ALL-NEXT: call void @llvm.dbg.value(metadata i32 [[X_NEXT]], [[META76:metadata !.*]], metadata !DIExpression()), [[DBG82]] +; ALL-NEXT: br i1 [[X_CURR_ISBITUNSET]], label [[LOOP]], label [[END:%.*]], [[DBG83:!dbg !.*]] +; ALL: end: +; ALL-NEXT: [[X_CURR_LCSSA:%.*]] = phi i32 [ [[X_CURR]], [[LOOP]] ], [[DBG79]] +; ALL-NEXT: call void @llvm.dbg.value(metadata i32 [[X_CURR_LCSSA]], [[META73]], metadata !DIExpression()), [[DBG79]] +; ALL-NEXT: ret i32 [[X_CURR_LCSSA]], [[DBG84:!dbg !.*]] +; +entry: + %bitmask = shl i32 1, %bit + br label %loop + +loop: + %x.curr = phi i32 [ %x.next, %loop ], [ %x, %entry ] + %x.curr.bitmasked = and i32 %x.curr, %bitmask + %x.curr.isbitunset = icmp eq i32 %x.curr.bitmasked, 0 + %x.next = shl i32 %x.curr, 1 + br i1 %x.curr.isbitunset, label %loop, label %end + +end: + ret i32 %x.curr +} + +;------------------------------------------------------------------------------- +; Negative tests + +; The %bitmask must be outside of the loop. +define i32 @n4(i32 %x, i32 %bit) { +; ALL-LABEL: @n4( +; ALL-NEXT: entry: +; ALL-NEXT: br label [[LOOP:%.*]], [[DBG92:!dbg !.*]] +; ALL: loop: +; ALL-NEXT: [[X_CURR:%.*]] = phi i32 [ [[X:%.*]], [[ENTRY:%.*]] ], [ [[X_NEXT:%.*]], [[LOOP]] ], [[DBG93:!dbg !.*]] +; ALL-NEXT: call void @llvm.dbg.value(metadata i32 [[X_CURR]], [[META87:metadata !.*]], metadata !DIExpression()), [[DBG93]] +; ALL-NEXT: [[BITMASK:%.*]] = shl i32 1, [[BIT:%.*]], [[DBG94:!dbg !.*]] +; ALL-NEXT: call void @llvm.dbg.value(metadata i32 [[BITMASK]], [[META88:metadata !.*]], metadata !DIExpression()), [[DBG94]] +; ALL-NEXT: [[X_CURR_BITMASKED:%.*]] = and i32 [[X_CURR]], [[BITMASK]], [[DBG95:!dbg !.*]] +; ALL-NEXT: call void @llvm.dbg.value(metadata i32 [[X_CURR_BITMASKED]], [[META89:metadata !.*]], metadata !DIExpression()), [[DBG95]] +; ALL-NEXT: [[X_CURR_ISBITUNSET:%.*]] = icmp eq i32 [[X_CURR_BITMASKED]], 0, [[DBG96:!dbg !.*]] +; ALL-NEXT: call void @llvm.dbg.value(metadata i1 [[X_CURR_ISBITUNSET]], [[META90:metadata !.*]], metadata !DIExpression()), [[DBG96]] +; ALL-NEXT: [[X_NEXT]] = shl i32 [[X_CURR]], 1, [[DBG97:!dbg !.*]] +; ALL-NEXT: call void @llvm.dbg.value(metadata i32 [[X_NEXT]], [[META91:metadata !.*]], metadata !DIExpression()), [[DBG97]] +; ALL-NEXT: br i1 [[X_CURR_ISBITUNSET]], label [[LOOP]], label [[END:%.*]], [[DBG98:!dbg !.*]] +; ALL: end: +; ALL-NEXT: [[X_CURR_LCSSA:%.*]] = phi i32 [ [[X_CURR]], [[LOOP]] ], [[DBG93]] +; ALL-NEXT: call void @llvm.dbg.value(metadata i32 [[X_CURR_LCSSA]], [[META87]], metadata !DIExpression()), [[DBG93]] +; ALL-NEXT: ret i32 [[X_CURR_LCSSA]], [[DBG99:!dbg !.*]] +; +entry: + br label %loop + +loop: + %x.curr = phi i32 [ %x, %entry ], [ %x.next, %loop ] + %bitmask = shl i32 1, %bit ; not loop-invariant + %x.curr.bitmasked = and i32 %x.curr, %bitmask + %x.curr.isbitunset = icmp eq i32 %x.curr.bitmasked, 0 + %x.next = shl i32 %x.curr, 1 + br i1 %x.curr.isbitunset, label %loop, label %end + +end: + ret i32 %x.curr +} + +; The %bitmask must be loop-invariant +define i32 @n5(i32 %x, i32 %bit) { +; ALL-LABEL: @n5( +; ALL-NEXT: entry: +; ALL-NEXT: br label [[LOOP:%.*]], [[DBG107:!dbg !.*]] +; ALL: loop: +; ALL-NEXT: [[X_CURR:%.*]] = phi i32 [ [[X:%.*]], [[ENTRY:%.*]] ], [ [[X_NEXT:%.*]], [[LOOP]] ], [[DBG108:!dbg !.*]] +; ALL-NEXT: call void @llvm.dbg.value(metadata i32 [[X_CURR]], [[META102:metadata !.*]], metadata !DIExpression()), [[DBG108]] +; ALL-NEXT: [[BITMASK:%.*]] = call i32 @gen32(), [[DBG109:!dbg !.*]] +; ALL-NEXT: call void @llvm.dbg.value(metadata i32 [[BITMASK]], [[META103:metadata !.*]], metadata !DIExpression()), [[DBG109]] +; ALL-NEXT: [[X_CURR_BITMASKED:%.*]] = and i32 [[X_CURR]], [[BITMASK]], [[DBG110:!dbg !.*]] +; ALL-NEXT: call void @llvm.dbg.value(metadata i32 [[X_CURR_BITMASKED]], [[META104:metadata !.*]], metadata !DIExpression()), [[DBG110]] +; ALL-NEXT: [[X_CURR_ISBITUNSET:%.*]] = icmp eq i32 [[X_CURR_BITMASKED]], 0, [[DBG111:!dbg !.*]] +; ALL-NEXT: call void @llvm.dbg.value(metadata i1 [[X_CURR_ISBITUNSET]], [[META105:metadata !.*]], metadata !DIExpression()), [[DBG111]] +; ALL-NEXT: [[X_NEXT]] = shl i32 [[X_CURR]], 1, [[DBG112:!dbg !.*]] +; ALL-NEXT: call void @llvm.dbg.value(metadata i32 [[X_NEXT]], [[META106:metadata !.*]], metadata !DIExpression()), [[DBG112]] +; ALL-NEXT: br i1 [[X_CURR_ISBITUNSET]], label [[LOOP]], label [[END:%.*]], [[DBG113:!dbg !.*]] +; ALL: end: +; ALL-NEXT: [[X_CURR_LCSSA:%.*]] = phi i32 [ [[X_CURR]], [[LOOP]] ], [[DBG108]] +; ALL-NEXT: call void @llvm.dbg.value(metadata i32 [[X_CURR_LCSSA]], [[META102]], metadata !DIExpression()), [[DBG108]] +; ALL-NEXT: ret i32 [[X_CURR_LCSSA]], [[DBG114:!dbg !.*]] +; +entry: + br label %loop + +loop: + %x.curr = phi i32 [ %x, %entry ], [ %x.next, %loop ] + %bitmask = call i32 @gen32() ; really not loop-invariant + %x.curr.bitmasked = and i32 %x.curr, %bitmask + %x.curr.isbitunset = icmp eq i32 %x.curr.bitmasked, 0 + %x.next = shl i32 %x.curr, 1 + br i1 %x.curr.isbitunset, label %loop, label %end + +end: + ret i32 %x.curr +} + +; The %bitmask must be a left-shift of a single bit. +define i32 @n6(i32 %x, i32 %bit) { +; ALL-LABEL: @n6( +; ALL-NEXT: entry: +; ALL-NEXT: [[BITMASK:%.*]] = shl i32 2, [[BIT:%.*]], [[DBG122:!dbg !.*]] +; ALL-NEXT: call void @llvm.dbg.value(metadata i32 [[BITMASK]], [[META117:metadata !.*]], metadata !DIExpression()), [[DBG122]] +; ALL-NEXT: br label [[LOOP:%.*]], [[DBG123:!dbg !.*]] +; ALL: loop: +; ALL-NEXT: [[X_CURR:%.*]] = phi i32 [ [[X:%.*]], [[ENTRY:%.*]] ], [ [[X_NEXT:%.*]], [[LOOP]] ], [[DBG124:!dbg !.*]] +; ALL-NEXT: call void @llvm.dbg.value(metadata i32 [[X_CURR]], [[META118:metadata !.*]], metadata !DIExpression()), [[DBG124]] +; ALL-NEXT: [[X_CURR_BITMASKED:%.*]] = and i32 [[X_CURR]], [[BITMASK]], [[DBG125:!dbg !.*]] +; ALL-NEXT: call void @llvm.dbg.value(metadata i32 [[X_CURR_BITMASKED]], [[META119:metadata !.*]], metadata !DIExpression()), [[DBG125]] +; ALL-NEXT: [[X_CURR_ISBITUNSET:%.*]] = icmp eq i32 [[X_CURR_BITMASKED]], 0, [[DBG126:!dbg !.*]] +; ALL-NEXT: call void @llvm.dbg.value(metadata i1 [[X_CURR_ISBITUNSET]], [[META120:metadata !.*]], metadata !DIExpression()), [[DBG126]] +; ALL-NEXT: [[X_NEXT]] = shl i32 [[X_CURR]], 1, [[DBG127:!dbg !.*]] +; ALL-NEXT: call void @llvm.dbg.value(metadata i32 [[X_NEXT]], [[META121:metadata !.*]], metadata !DIExpression()), [[DBG127]] +; ALL-NEXT: br i1 [[X_CURR_ISBITUNSET]], label [[LOOP]], label [[END:%.*]], [[DBG128:!dbg !.*]] +; ALL: end: +; ALL-NEXT: [[X_CURR_LCSSA:%.*]] = phi i32 [ [[X_CURR]], [[LOOP]] ], [[DBG124]] +; ALL-NEXT: call void @llvm.dbg.value(metadata i32 [[X_CURR_LCSSA]], [[META118]], metadata !DIExpression()), [[DBG124]] +; ALL-NEXT: ret i32 [[X_CURR_LCSSA]], [[DBG129:!dbg !.*]] +; +entry: + %bitmask = shl i32 2, %bit ; not what we are looking for. + br label %loop + +loop: + %x.curr = phi i32 [ %x, %entry ], [ %x.next, %loop ] + %x.curr.bitmasked = and i32 %x.curr, %bitmask + %x.curr.isbitunset = icmp eq i32 %x.curr.bitmasked, 0 + %x.next = shl i32 %x.curr, 1 + br i1 %x.curr.isbitunset, label %loop, label %end + +end: + ret i32 %x.curr +} + +; Bad recurrence - should be a left-shift by 1. +define i32 @n7(i32 %x, i32 %bit) { +; ALL-LABEL: @n7( +; ALL-NEXT: entry: +; ALL-NEXT: [[BITMASK:%.*]] = shl i32 1, [[BIT:%.*]], [[DBG137:!dbg !.*]] +; ALL-NEXT: call void @llvm.dbg.value(metadata i32 [[BITMASK]], [[META132:metadata !.*]], metadata !DIExpression()), [[DBG137]] +; ALL-NEXT: br label [[LOOP:%.*]], [[DBG138:!dbg !.*]] +; ALL: loop: +; ALL-NEXT: [[X_CURR:%.*]] = phi i32 [ [[X:%.*]], [[ENTRY:%.*]] ], [ [[X_NEXT:%.*]], [[LOOP]] ], [[DBG139:!dbg !.*]] +; ALL-NEXT: call void @llvm.dbg.value(metadata i32 [[X_CURR]], [[META133:metadata !.*]], metadata !DIExpression()), [[DBG139]] +; ALL-NEXT: [[X_CURR_BITMASKED:%.*]] = and i32 [[X_CURR]], [[BITMASK]], [[DBG140:!dbg !.*]] +; ALL-NEXT: call void @llvm.dbg.value(metadata i32 [[X_CURR_BITMASKED]], [[META134:metadata !.*]], metadata !DIExpression()), [[DBG140]] +; ALL-NEXT: [[X_CURR_ISBITUNSET:%.*]] = icmp eq i32 [[X_CURR_BITMASKED]], 0, [[DBG141:!dbg !.*]] +; ALL-NEXT: call void @llvm.dbg.value(metadata i1 [[X_CURR_ISBITUNSET]], [[META135:metadata !.*]], metadata !DIExpression()), [[DBG141]] +; ALL-NEXT: [[X_NEXT]] = shl i32 [[X_CURR]], 2, [[DBG142:!dbg !.*]] +; ALL-NEXT: call void @llvm.dbg.value(metadata i32 [[X_NEXT]], [[META136:metadata !.*]], metadata !DIExpression()), [[DBG142]] +; ALL-NEXT: br i1 [[X_CURR_ISBITUNSET]], label [[LOOP]], label [[END:%.*]], [[DBG143:!dbg !.*]] +; ALL: end: +; ALL-NEXT: [[X_CURR_LCSSA:%.*]] = phi i32 [ [[X_CURR]], [[LOOP]] ], [[DBG139]] +; ALL-NEXT: call void @llvm.dbg.value(metadata i32 [[X_CURR_LCSSA]], [[META133]], metadata !DIExpression()), [[DBG139]] +; ALL-NEXT: ret i32 [[X_CURR_LCSSA]], [[DBG144:!dbg !.*]] +; +entry: + %bitmask = shl i32 1, %bit + br label %loop + +loop: + %x.curr = phi i32 [ %x, %entry ], [ %x.next, %loop ] + %x.curr.bitmasked = and i32 %x.curr, %bitmask + %x.curr.isbitunset = icmp eq i32 %x.curr.bitmasked, 0 + %x.next = shl i32 %x.curr, 2 ; wrong shift amount. + br i1 %x.curr.isbitunset, label %loop, label %end + +end: + ret i32 %x.curr +} + +; The comparison is not what we are looking for. +define i32 @n8(i32 %x, i32 %bit) { +; ALL-LABEL: @n8( +; ALL-NEXT: entry: +; ALL-NEXT: [[BITMASK:%.*]] = shl i32 1, [[BIT:%.*]], [[DBG152:!dbg !.*]] +; ALL-NEXT: call void @llvm.dbg.value(metadata i32 [[BITMASK]], [[META147:metadata !.*]], metadata !DIExpression()), [[DBG152]] +; ALL-NEXT: br label [[LOOP:%.*]], [[DBG153:!dbg !.*]] +; ALL: loop: +; ALL-NEXT: [[X_CURR:%.*]] = phi i32 [ [[X:%.*]], [[ENTRY:%.*]] ], [ [[X_NEXT:%.*]], [[LOOP]] ], [[DBG154:!dbg !.*]] +; ALL-NEXT: call void @llvm.dbg.value(metadata i32 [[X_CURR]], [[META148:metadata !.*]], metadata !DIExpression()), [[DBG154]] +; ALL-NEXT: [[X_CURR_BITMASKED:%.*]] = and i32 [[X_CURR]], [[BITMASK]], [[DBG155:!dbg !.*]] +; ALL-NEXT: call void @llvm.dbg.value(metadata i32 [[X_CURR_BITMASKED]], [[META149:metadata !.*]], metadata !DIExpression()), [[DBG155]] +; ALL-NEXT: [[X_CURR_ISBITUNSET:%.*]] = icmp ne i32 [[X_CURR_BITMASKED]], [[BITMASK]], [[DBG156:!dbg !.*]] +; ALL-NEXT: call void @llvm.dbg.value(metadata i1 [[X_CURR_ISBITUNSET]], [[META150:metadata !.*]], metadata !DIExpression()), [[DBG156]] +; ALL-NEXT: [[X_NEXT]] = shl i32 [[X_CURR]], 1, [[DBG157:!dbg !.*]] +; ALL-NEXT: call void @llvm.dbg.value(metadata i32 [[X_NEXT]], [[META151:metadata !.*]], metadata !DIExpression()), [[DBG157]] +; ALL-NEXT: br i1 [[X_CURR_ISBITUNSET]], label [[LOOP]], label [[END:%.*]], [[DBG158:!dbg !.*]] +; ALL: end: +; ALL-NEXT: [[X_CURR_LCSSA:%.*]] = phi i32 [ [[X_CURR]], [[LOOP]] ], [[DBG154]] +; ALL-NEXT: call void @llvm.dbg.value(metadata i32 [[X_CURR_LCSSA]], [[META148]], metadata !DIExpression()), [[DBG154]] +; ALL-NEXT: ret i32 [[X_CURR_LCSSA]], [[DBG159:!dbg !.*]] +; +entry: + %bitmask = shl i32 1, %bit + br label %loop + +loop: + %x.curr = phi i32 [ %x, %entry ], [ %x.next, %loop ] + %x.curr.bitmasked = and i32 %x.curr, %bitmask + %x.curr.isbitunset = icmp ne i32 %x.curr.bitmasked, %bitmask ; should be `==0` + %x.next = shl i32 %x.curr, 1 + br i1 %x.curr.isbitunset, label %loop, label %end + +end: + ret i32 %x.curr +} + +; We should loop while %x.curr.bitmasked is 0, not exit when it is 0. +define i32 @n9(i32 %x, i32 %bit) { +; ALL-LABEL: @n9( +; ALL-NEXT: entry: +; ALL-NEXT: [[BITMASK:%.*]] = shl i32 1, [[BIT:%.*]], [[DBG167:!dbg !.*]] +; ALL-NEXT: call void @llvm.dbg.value(metadata i32 [[BITMASK]], [[META162:metadata !.*]], metadata !DIExpression()), [[DBG167]] +; ALL-NEXT: br label [[LOOP:%.*]], [[DBG168:!dbg !.*]] +; ALL: loop: +; ALL-NEXT: [[X_CURR:%.*]] = phi i32 [ [[X:%.*]], [[ENTRY:%.*]] ], [ [[X_NEXT:%.*]], [[LOOP]] ], [[DBG169:!dbg !.*]] +; ALL-NEXT: call void @llvm.dbg.value(metadata i32 [[X_CURR]], [[META163:metadata !.*]], metadata !DIExpression()), [[DBG169]] +; ALL-NEXT: [[X_CURR_BITMASKED:%.*]] = and i32 [[X_CURR]], [[BITMASK]], [[DBG170:!dbg !.*]] +; ALL-NEXT: call void @llvm.dbg.value(metadata i32 [[X_CURR_BITMASKED]], [[META164:metadata !.*]], metadata !DIExpression()), [[DBG170]] +; ALL-NEXT: [[X_CURR_ISBITUNSET:%.*]] = icmp eq i32 [[X_CURR_BITMASKED]], 0, [[DBG171:!dbg !.*]] +; ALL-NEXT: call void @llvm.dbg.value(metadata i1 [[X_CURR_ISBITUNSET]], [[META165:metadata !.*]], metadata !DIExpression()), [[DBG171]] +; ALL-NEXT: [[X_NEXT]] = shl i32 [[X_CURR]], 1, [[DBG172:!dbg !.*]] +; ALL-NEXT: call void @llvm.dbg.value(metadata i32 [[X_NEXT]], [[META166:metadata !.*]], metadata !DIExpression()), [[DBG172]] +; ALL-NEXT: br i1 [[X_CURR_ISBITUNSET]], label [[END:%.*]], label [[LOOP]], [[DBG173:!dbg !.*]] +; ALL: end: +; ALL-NEXT: [[X_CURR_LCSSA:%.*]] = phi i32 [ [[X_CURR]], [[LOOP]] ], [[DBG169]] +; ALL-NEXT: call void @llvm.dbg.value(metadata i32 [[X_CURR_LCSSA]], [[META163]], metadata !DIExpression()), [[DBG169]] +; ALL-NEXT: ret i32 [[X_CURR_LCSSA]], [[DBG174:!dbg !.*]] +; +entry: + %bitmask = shl i32 1, %bit + br label %loop + +loop: + %x.curr = phi i32 [ %x, %entry ], [ %x.next, %loop ] + %x.curr.bitmasked = and i32 %x.curr, %bitmask + %x.curr.isbitunset = icmp eq i32 %x.curr.bitmasked, 0 + %x.next = shl i32 %x.curr, 1 + br i1 %x.curr.isbitunset, label %end, label %loop ; wrong order of successors + +end: + ret i32 %x.curr +} + +; We should loop while %x.curr.bitmasked is 0, not while it is not 0. +define i32 @n10(i32 %x, i32 %bit) { +; ALL-LABEL: @n10( +; ALL-NEXT: entry: +; ALL-NEXT: [[BITMASK:%.*]] = shl i32 1, [[BIT:%.*]], [[DBG182:!dbg !.*]] +; ALL-NEXT: call void @llvm.dbg.value(metadata i32 [[BITMASK]], [[META177:metadata !.*]], metadata !DIExpression()), [[DBG182]] +; ALL-NEXT: br label [[LOOP:%.*]], [[DBG183:!dbg !.*]] +; ALL: loop: +; ALL-NEXT: [[X_CURR:%.*]] = phi i32 [ [[X:%.*]], [[ENTRY:%.*]] ], [ [[X_NEXT:%.*]], [[LOOP]] ], [[DBG184:!dbg !.*]] +; ALL-NEXT: call void @llvm.dbg.value(metadata i32 [[X_CURR]], [[META178:metadata !.*]], metadata !DIExpression()), [[DBG184]] +; ALL-NEXT: [[X_CURR_BITMASKED:%.*]] = and i32 [[X_CURR]], [[BITMASK]], [[DBG185:!dbg !.*]] +; ALL-NEXT: call void @llvm.dbg.value(metadata i32 [[X_CURR_BITMASKED]], [[META179:metadata !.*]], metadata !DIExpression()), [[DBG185]] +; ALL-NEXT: [[X_CURR_ISBITUNSET:%.*]] = icmp ne i32 [[X_CURR_BITMASKED]], 0, [[DBG186:!dbg !.*]] +; ALL-NEXT: call void @llvm.dbg.value(metadata i1 [[X_CURR_ISBITUNSET]], [[META180:metadata !.*]], metadata !DIExpression()), [[DBG186]] +; ALL-NEXT: [[X_NEXT]] = shl i32 [[X_CURR]], 1, [[DBG187:!dbg !.*]] +; ALL-NEXT: call void @llvm.dbg.value(metadata i32 [[X_NEXT]], [[META181:metadata !.*]], metadata !DIExpression()), [[DBG187]] +; ALL-NEXT: br i1 [[X_CURR_ISBITUNSET]], label [[LOOP]], label [[END:%.*]], [[DBG188:!dbg !.*]] +; ALL: end: +; ALL-NEXT: [[X_CURR_LCSSA:%.*]] = phi i32 [ [[X_CURR]], [[LOOP]] ], [[DBG184]] +; ALL-NEXT: call void @llvm.dbg.value(metadata i32 [[X_CURR_LCSSA]], [[META178]], metadata !DIExpression()), [[DBG184]] +; ALL-NEXT: ret i32 [[X_CURR_LCSSA]], [[DBG189:!dbg !.*]] +; +entry: + %bitmask = shl i32 1, %bit + br label %loop + +loop: + %x.curr = phi i32 [ %x, %entry ], [ %x.next, %loop ] + %x.curr.bitmasked = and i32 %x.curr, %bitmask + %x.curr.isbitunset = icmp ne i32 %x.curr.bitmasked, 0 ; wrong predicate + %x.next = shl i32 %x.curr, 1 + br i1 %x.curr.isbitunset, label %loop, label %end + +end: + ret i32 %x.curr +} + +; PHI node is not a recurrence +define i32 @n11(i32 %x, i32 %bit) { +; ALL-LABEL: @n11( +; ALL-NEXT: entry: +; ALL-NEXT: [[BITMASK:%.*]] = shl i32 1, [[BIT:%.*]], [[DBG197:!dbg !.*]] +; ALL-NEXT: call void @llvm.dbg.value(metadata i32 [[BITMASK]], [[META192:metadata !.*]], metadata !DIExpression()), [[DBG197]] +; ALL-NEXT: br label [[LOOP:%.*]], [[DBG198:!dbg !.*]] +; ALL: loop: +; ALL-NEXT: call void @llvm.dbg.value(metadata i32 [[X:%.*]], [[META193:metadata !.*]], metadata !DIExpression()), [[DBG199:!dbg !.*]] +; ALL-NEXT: [[X_CURR_BITMASKED:%.*]] = and i32 [[X]], [[BITMASK]], [[DBG200:!dbg !.*]] +; ALL-NEXT: call void @llvm.dbg.value(metadata i32 [[X_CURR_BITMASKED]], [[META194:metadata !.*]], metadata !DIExpression()), [[DBG200]] +; ALL-NEXT: [[X_CURR_ISBITUNSET:%.*]] = icmp eq i32 [[X_CURR_BITMASKED]], 0, [[DBG201:!dbg !.*]] +; ALL-NEXT: call void @llvm.dbg.value(metadata i1 [[X_CURR_ISBITUNSET]], [[META195:metadata !.*]], metadata !DIExpression()), [[DBG201]] +; ALL-NEXT: [[X_NEXT:%.*]] = shl i32 [[X]], 1, [[DBG202:!dbg !.*]] +; ALL-NEXT: call void @llvm.dbg.value(metadata i32 [[X_NEXT]], [[META196:metadata !.*]], metadata !DIExpression()), [[DBG202]] +; ALL-NEXT: br i1 [[X_CURR_ISBITUNSET]], label [[LOOP]], label [[END:%.*]], [[DBG203:!dbg !.*]] +; ALL: end: +; ALL-NEXT: ret i32 [[X]], [[DBG204:!dbg !.*]] +; +entry: + %bitmask = shl i32 1, %bit + br label %loop + +loop: + %x.curr = phi i32 [ %x, %entry ], [ %x, %loop ] ; should use %x.next when coming from %loop + %x.curr.bitmasked = and i32 %x.curr, %bitmask + %x.curr.isbitunset = icmp eq i32 %x.curr.bitmasked, 0 + %x.next = shl i32 %x.curr, 1 + br i1 %x.curr.isbitunset, label %loop, label %end + +end: + ret i32 %x.curr +} + +; Masking wrong value +define i32 @n12(i32 %x, i32 %bit) { +; ALL-LABEL: @n12( +; ALL-NEXT: entry: +; ALL-NEXT: [[BITMASK:%.*]] = shl i32 1, [[BIT:%.*]], [[DBG212:!dbg !.*]] +; ALL-NEXT: call void @llvm.dbg.value(metadata i32 [[BITMASK]], [[META207:metadata !.*]], metadata !DIExpression()), [[DBG212]] +; ALL-NEXT: br label [[LOOP:%.*]], [[DBG213:!dbg !.*]] +; ALL: loop: +; ALL-NEXT: [[X_CURR:%.*]] = phi i32 [ [[X:%.*]], [[ENTRY:%.*]] ], [ [[X_NEXT:%.*]], [[LOOP]] ], [[DBG214:!dbg !.*]] +; ALL-NEXT: call void @llvm.dbg.value(metadata i32 [[X_CURR]], [[META208:metadata !.*]], metadata !DIExpression()), [[DBG214]] +; ALL-NEXT: [[X_CURR_BITMASKED:%.*]] = and i32 [[X]], [[BITMASK]], [[DBG215:!dbg !.*]] +; ALL-NEXT: call void @llvm.dbg.value(metadata i32 [[X_CURR_BITMASKED]], [[META209:metadata !.*]], metadata !DIExpression()), [[DBG215]] +; ALL-NEXT: [[X_CURR_ISBITUNSET:%.*]] = icmp eq i32 [[X_CURR_BITMASKED]], 0, [[DBG216:!dbg !.*]] +; ALL-NEXT: call void @llvm.dbg.value(metadata i1 [[X_CURR_ISBITUNSET]], [[META210:metadata !.*]], metadata !DIExpression()), [[DBG216]] +; ALL-NEXT: [[X_NEXT]] = shl i32 [[X_CURR]], 1, [[DBG217:!dbg !.*]] +; ALL-NEXT: call void @llvm.dbg.value(metadata i32 [[X_NEXT]], [[META211:metadata !.*]], metadata !DIExpression()), [[DBG217]] +; ALL-NEXT: br i1 [[X_CURR_ISBITUNSET]], label [[LOOP]], label [[END:%.*]], [[DBG218:!dbg !.*]] +; ALL: end: +; ALL-NEXT: [[X_CURR_LCSSA:%.*]] = phi i32 [ [[X_CURR]], [[LOOP]] ], [[DBG214]] +; ALL-NEXT: call void @llvm.dbg.value(metadata i32 [[X_CURR_LCSSA]], [[META208]], metadata !DIExpression()), [[DBG214]] +; ALL-NEXT: ret i32 [[X_CURR_LCSSA]], [[DBG219:!dbg !.*]] +; +entry: + %bitmask = shl i32 1, %bit + br label %loop + +loop: + %x.curr = phi i32 [ %x, %entry ], [ %x.next, %loop ] + %x.curr.bitmasked = and i32 %x, %bitmask ; should use %x.curr, not %x + %x.curr.isbitunset = icmp eq i32 %x.curr.bitmasked, 0 + %x.next = shl i32 %x.curr, 1 + br i1 %x.curr.isbitunset, label %loop, label %end + +end: + ret i32 %x.curr +} + +; Checking wrong value +define i32 @n13(i32 %x, i32 %bit) { +; ALL-LABEL: @n13( +; ALL-NEXT: entry: +; ALL-NEXT: [[BITMASK:%.*]] = shl i32 1, [[BIT:%.*]], [[DBG227:!dbg !.*]] +; ALL-NEXT: call void @llvm.dbg.value(metadata i32 [[BITMASK]], [[META222:metadata !.*]], metadata !DIExpression()), [[DBG227]] +; ALL-NEXT: br label [[LOOP:%.*]], [[DBG228:!dbg !.*]] +; ALL: loop: +; ALL-NEXT: [[X_CURR:%.*]] = phi i32 [ [[X:%.*]], [[ENTRY:%.*]] ], [ [[X_NEXT:%.*]], [[LOOP]] ], [[DBG229:!dbg !.*]] +; ALL-NEXT: call void @llvm.dbg.value(metadata i32 [[X_CURR]], [[META223:metadata !.*]], metadata !DIExpression()), [[DBG229]] +; ALL-NEXT: [[X_CURR_BITMASKED:%.*]] = and i32 [[X_CURR]], [[BITMASK]], [[DBG230:!dbg !.*]] +; ALL-NEXT: call void @llvm.dbg.value(metadata i32 [[X_CURR_BITMASKED]], [[META224:metadata !.*]], metadata !DIExpression()), [[DBG230]] +; ALL-NEXT: [[X_CURR_ISBITUNSET:%.*]] = icmp eq i32 [[X_CURR]], 0, [[DBG231:!dbg !.*]] +; ALL-NEXT: call void @llvm.dbg.value(metadata i1 [[X_CURR_ISBITUNSET]], [[META225:metadata !.*]], metadata !DIExpression()), [[DBG231]] +; ALL-NEXT: [[X_NEXT]] = shl i32 [[X_CURR]], 1, [[DBG232:!dbg !.*]] +; ALL-NEXT: call void @llvm.dbg.value(metadata i32 [[X_NEXT]], [[META226:metadata !.*]], metadata !DIExpression()), [[DBG232]] +; ALL-NEXT: br i1 [[X_CURR_ISBITUNSET]], label [[LOOP]], label [[END:%.*]], [[DBG233:!dbg !.*]] +; ALL: end: +; ALL-NEXT: [[X_CURR_LCSSA:%.*]] = phi i32 [ [[X_CURR]], [[LOOP]] ], [[DBG229]] +; ALL-NEXT: call void @llvm.dbg.value(metadata i32 [[X_CURR_LCSSA]], [[META223]], metadata !DIExpression()), [[DBG229]] +; ALL-NEXT: ret i32 [[X_CURR_LCSSA]], [[DBG234:!dbg !.*]] +; +entry: + %bitmask = shl i32 1, %bit + br label %loop + +loop: + %x.curr = phi i32 [ %x, %entry ], [ %x.next, %loop ] + %x.curr.bitmasked = and i32 %x.curr, %bitmask + %x.curr.isbitunset = icmp eq i32 %x.curr, 0 ; should be checking %x.curr.bitmasked + %x.next = shl i32 %x.curr, 1 + br i1 %x.curr.isbitunset, label %loop, label %end + +end: + ret i32 %x.curr +} + +define i32 @n14(i32 %x, i32 %bit) { +; ALL-LABEL: @n14( +; ALL-NEXT: entry: +; ALL-NEXT: [[BITMASK:%.*]] = shl i32 1, [[BIT:%.*]], [[DBG242:!dbg !.*]] +; ALL-NEXT: call void @llvm.dbg.value(metadata i32 [[BITMASK]], [[META237:metadata !.*]], metadata !DIExpression()), [[DBG242]] +; ALL-NEXT: br label [[LOOP:%.*]], [[DBG243:!dbg !.*]] +; ALL: loop: +; ALL-NEXT: [[X_CURR:%.*]] = phi i32 [ [[X:%.*]], [[ENTRY:%.*]] ], [ [[X_NEXT:%.*]], [[LOOP]] ], [[DBG244:!dbg !.*]] +; ALL-NEXT: call void @llvm.dbg.value(metadata i32 [[X_CURR]], [[META238:metadata !.*]], metadata !DIExpression()), [[DBG244]] +; ALL-NEXT: [[X_CURR_BITMASKED:%.*]] = and i32 [[X_CURR]], [[BITMASK]], [[DBG245:!dbg !.*]] +; ALL-NEXT: call void @llvm.dbg.value(metadata i32 [[X_CURR_BITMASKED]], [[META239:metadata !.*]], metadata !DIExpression()), [[DBG245]] +; ALL-NEXT: [[X_CURR_ISBITUNSET:%.*]] = icmp eq i32 [[X_CURR_BITMASKED]], 0, [[DBG246:!dbg !.*]] +; ALL-NEXT: call void @llvm.dbg.value(metadata i1 [[X_CURR_ISBITUNSET]], [[META240:metadata !.*]], metadata !DIExpression()), [[DBG246]] +; ALL-NEXT: [[X_NEXT]] = shl i32 [[X]], 1, [[DBG247:!dbg !.*]] +; ALL-NEXT: call void @llvm.dbg.value(metadata i32 [[X_NEXT]], [[META241:metadata !.*]], metadata !DIExpression()), [[DBG247]] +; ALL-NEXT: br i1 [[X_CURR_ISBITUNSET]], label [[LOOP]], label [[END:%.*]], [[DBG248:!dbg !.*]] +; ALL: end: +; ALL-NEXT: [[X_CURR_LCSSA:%.*]] = phi i32 [ [[X_CURR]], [[LOOP]] ], [[DBG244]] +; ALL-NEXT: call void @llvm.dbg.value(metadata i32 [[X_CURR_LCSSA]], [[META238]], metadata !DIExpression()), [[DBG244]] +; ALL-NEXT: ret i32 [[X_CURR_LCSSA]], [[DBG249:!dbg !.*]] +; +entry: + %bitmask = shl i32 1, %bit + br label %loop + +loop: + %x.curr = phi i32 [ %x, %entry ], [ %x.next, %loop ] + %x.curr.bitmasked = and i32 %x.curr, %bitmask + %x.curr.isbitunset = icmp eq i32 %x.curr.bitmasked, 0 + %x.next = shl i32 %x, 1 ; should be shifting %x.curr + br i1 %x.curr.isbitunset, label %loop, label %end + +end: + ret i32 %x.curr +} + +;------------------------------------------------------------------------------- +; Tests with extra cruft. + +; If loop body has any extra instructions we don't want to deal with it. +define i32 @n15(i32 %x, i32 %bit) { +; ALL-LABEL: @n15( +; ALL-NEXT: entry: +; ALL-NEXT: [[BITMASK:%.*]] = shl i32 1, [[BIT:%.*]], [[DBG257:!dbg !.*]] +; ALL-NEXT: call void @llvm.dbg.value(metadata i32 [[BITMASK]], [[META252:metadata !.*]], metadata !DIExpression()), [[DBG257]] +; ALL-NEXT: br label [[LOOP:%.*]], [[DBG258:!dbg !.*]] +; ALL: loop: +; ALL-NEXT: [[X_CURR:%.*]] = phi i32 [ [[X:%.*]], [[ENTRY:%.*]] ], [ [[X_NEXT:%.*]], [[LOOP]] ], [[DBG259:!dbg !.*]] +; ALL-NEXT: call void @llvm.dbg.value(metadata i32 [[X_CURR]], [[META253:metadata !.*]], metadata !DIExpression()), [[DBG259]] +; ALL-NEXT: call void @external_side_effect(), [[DBG260:!dbg !.*]] +; ALL-NEXT: [[X_CURR_BITMASKED:%.*]] = and i32 [[X_CURR]], [[BITMASK]], [[DBG261:!dbg !.*]] +; ALL-NEXT: call void @llvm.dbg.value(metadata i32 [[X_CURR_BITMASKED]], [[META254:metadata !.*]], metadata !DIExpression()), [[DBG261]] +; ALL-NEXT: [[X_CURR_ISBITUNSET:%.*]] = icmp eq i32 [[X_CURR_BITMASKED]], 0, [[DBG262:!dbg !.*]] +; ALL-NEXT: call void @llvm.dbg.value(metadata i1 [[X_CURR_ISBITUNSET]], [[META255:metadata !.*]], metadata !DIExpression()), [[DBG262]] +; ALL-NEXT: [[X_NEXT]] = shl i32 [[X_CURR]], 1, [[DBG263:!dbg !.*]] +; ALL-NEXT: call void @llvm.dbg.value(metadata i32 [[X_NEXT]], [[META256:metadata !.*]], metadata !DIExpression()), [[DBG263]] +; ALL-NEXT: br i1 [[X_CURR_ISBITUNSET]], label [[LOOP]], label [[END:%.*]], [[DBG264:!dbg !.*]] +; ALL: end: +; ALL-NEXT: [[X_CURR_LCSSA:%.*]] = phi i32 [ [[X_CURR]], [[LOOP]] ], [[DBG259]] +; ALL-NEXT: call void @llvm.dbg.value(metadata i32 [[X_CURR_LCSSA]], [[META253]], metadata !DIExpression()), [[DBG259]] +; ALL-NEXT: ret i32 [[X_CURR_LCSSA]], [[DBG265:!dbg !.*]] +; +entry: + %bitmask = shl i32 1, %bit + br label %loop + +loop: + %x.curr = phi i32 [ %x, %entry ], [ %x.next, %loop ] + call void @external_side_effect() ; not part of idiom. + %x.curr.bitmasked = and i32 %x.curr, %bitmask + %x.curr.isbitunset = icmp eq i32 %x.curr.bitmasked, 0 + %x.next = shl i32 %x.curr, 1 + br i1 %x.curr.isbitunset, label %loop, label %end + +end: + ret i32 %x.curr +} + +; In-loop instructions should not have uses outside of the loop. +define i32 @n16(i32 %x, i32 %bit) { +; ALL-LABEL: @n16( +; ALL-NEXT: entry: +; ALL-NEXT: [[BITMASK:%.*]] = shl i32 1, [[BIT:%.*]], [[DBG273:!dbg !.*]] +; ALL-NEXT: call void @llvm.dbg.value(metadata i32 [[BITMASK]], [[META268:metadata !.*]], metadata !DIExpression()), [[DBG273]] +; ALL-NEXT: br label [[LOOP:%.*]], [[DBG274:!dbg !.*]] +; ALL: loop: +; ALL-NEXT: [[X_CURR:%.*]] = phi i32 [ [[X:%.*]], [[ENTRY:%.*]] ], [ [[X_NEXT:%.*]], [[LOOP]] ], [[DBG275:!dbg !.*]] +; ALL-NEXT: call void @llvm.dbg.value(metadata i32 [[X_CURR]], [[META269:metadata !.*]], metadata !DIExpression()), [[DBG275]] +; ALL-NEXT: [[X_CURR_BITMASKED:%.*]] = and i32 [[X_CURR]], [[BITMASK]], [[DBG276:!dbg !.*]] +; ALL-NEXT: call void @llvm.dbg.value(metadata i32 [[X_CURR_BITMASKED]], [[META270:metadata !.*]], metadata !DIExpression()), [[DBG276]] +; ALL-NEXT: [[X_CURR_ISBITUNSET:%.*]] = icmp eq i32 [[X_CURR_BITMASKED]], 0, [[DBG277:!dbg !.*]] +; ALL-NEXT: call void @llvm.dbg.value(metadata i1 [[X_CURR_ISBITUNSET]], [[META271:metadata !.*]], metadata !DIExpression()), [[DBG277]] +; ALL-NEXT: [[X_NEXT]] = shl i32 [[X_CURR]], 1, [[DBG278:!dbg !.*]] +; ALL-NEXT: call void @llvm.dbg.value(metadata i32 [[X_NEXT]], [[META272:metadata !.*]], metadata !DIExpression()), [[DBG278]] +; ALL-NEXT: br i1 [[X_CURR_ISBITUNSET]], label [[LOOP]], label [[END:%.*]], [[DBG279:!dbg !.*]] +; ALL: end: +; ALL-NEXT: [[X_CURR_LCSSA:%.*]] = phi i32 [ [[X_CURR]], [[LOOP]] ], [[DBG275]] +; ALL-NEXT: [[X_CURR_BITMASKED_LCSSA:%.*]] = phi i32 [ [[X_CURR_BITMASKED]], [[LOOP]] ], [[DBG276]] +; ALL-NEXT: call void @llvm.dbg.value(metadata i32 [[X_CURR_LCSSA]], [[META269]], metadata !DIExpression()), [[DBG275]] +; ALL-NEXT: call void @use32(i32 [[X_CURR_BITMASKED_LCSSA]]), [[DBG280:!dbg !.*]] +; ALL-NEXT: ret i32 [[X_CURR_LCSSA]], [[DBG281:!dbg !.*]] +; +entry: + %bitmask = shl i32 1, %bit + br label %loop + +loop: + %x.curr = phi i32 [ %x, %entry ], [ %x.next, %loop ] + %x.curr.bitmasked = and i32 %x.curr, %bitmask + %x.curr.isbitunset = icmp eq i32 %x.curr.bitmasked, 0 + %x.next = shl i32 %x.curr, 1 + br i1 %x.curr.isbitunset, label %loop, label %end + +end: + call void @use32(i32 %x.curr.bitmasked) + ret i32 %x.curr +} +define i32 @n17(i32 %x, i32 %bit) { +; ALL-LABEL: @n17( +; ALL-NEXT: entry: +; ALL-NEXT: [[BITMASK:%.*]] = shl i32 1, [[BIT:%.*]], [[DBG289:!dbg !.*]] +; ALL-NEXT: call void @llvm.dbg.value(metadata i32 [[BITMASK]], [[META284:metadata !.*]], metadata !DIExpression()), [[DBG289]] +; ALL-NEXT: br label [[LOOP:%.*]], [[DBG290:!dbg !.*]] +; ALL: loop: +; ALL-NEXT: [[X_CURR:%.*]] = phi i32 [ [[X:%.*]], [[ENTRY:%.*]] ], [ [[X_NEXT:%.*]], [[LOOP]] ], [[DBG291:!dbg !.*]] +; ALL-NEXT: call void @llvm.dbg.value(metadata i32 [[X_CURR]], [[META285:metadata !.*]], metadata !DIExpression()), [[DBG291]] +; ALL-NEXT: [[X_CURR_BITMASKED:%.*]] = and i32 [[X_CURR]], [[BITMASK]], [[DBG292:!dbg !.*]] +; ALL-NEXT: call void @llvm.dbg.value(metadata i32 [[X_CURR_BITMASKED]], [[META286:metadata !.*]], metadata !DIExpression()), [[DBG292]] +; ALL-NEXT: [[X_CURR_ISBITUNSET:%.*]] = icmp eq i32 [[X_CURR_BITMASKED]], 0, [[DBG293:!dbg !.*]] +; ALL-NEXT: call void @llvm.dbg.value(metadata i1 [[X_CURR_ISBITUNSET]], [[META287:metadata !.*]], metadata !DIExpression()), [[DBG293]] +; ALL-NEXT: [[X_NEXT]] = shl i32 [[X_CURR]], 1, [[DBG294:!dbg !.*]] +; ALL-NEXT: call void @llvm.dbg.value(metadata i32 [[X_NEXT]], [[META288:metadata !.*]], metadata !DIExpression()), [[DBG294]] +; ALL-NEXT: br i1 [[X_CURR_ISBITUNSET]], label [[LOOP]], label [[END:%.*]], [[DBG295:!dbg !.*]] +; ALL: end: +; ALL-NEXT: [[X_CURR_LCSSA:%.*]] = phi i32 [ [[X_CURR]], [[LOOP]] ], [[DBG291]] +; ALL-NEXT: [[X_CURR_ISBITUNSET_LCSSA:%.*]] = phi i1 [ [[X_CURR_ISBITUNSET]], [[LOOP]] ], [[DBG293]] +; ALL-NEXT: call void @llvm.dbg.value(metadata i32 [[X_CURR_LCSSA]], [[META285]], metadata !DIExpression()), [[DBG291]] +; ALL-NEXT: call void @use1(i1 [[X_CURR_ISBITUNSET_LCSSA]]), [[DBG296:!dbg !.*]] +; ALL-NEXT: ret i32 [[X_CURR_LCSSA]], [[DBG297:!dbg !.*]] +; +entry: + %bitmask = shl i32 1, %bit + br label %loop + +loop: + %x.curr = phi i32 [ %x, %entry ], [ %x.next, %loop ] + %x.curr.bitmasked = and i32 %x.curr, %bitmask + %x.curr.isbitunset = icmp eq i32 %x.curr.bitmasked, 0 + %x.next = shl i32 %x.curr, 1 + br i1 %x.curr.isbitunset, label %loop, label %end + +end: + call void @use1(i1 %x.curr.isbitunset) + ret i32 %x.curr +} +define i32 @n18(i32 %x, i32 %bit) { +; ALL-LABEL: @n18( +; ALL-NEXT: entry: +; ALL-NEXT: [[BITMASK:%.*]] = shl i32 1, [[BIT:%.*]], [[DBG305:!dbg !.*]] +; ALL-NEXT: call void @llvm.dbg.value(metadata i32 [[BITMASK]], [[META300:metadata !.*]], metadata !DIExpression()), [[DBG305]] +; ALL-NEXT: br label [[LOOP:%.*]], [[DBG306:!dbg !.*]] +; ALL: loop: +; ALL-NEXT: [[X_CURR:%.*]] = phi i32 [ [[X:%.*]], [[ENTRY:%.*]] ], [ [[X_NEXT:%.*]], [[LOOP]] ], [[DBG307:!dbg !.*]] +; ALL-NEXT: call void @llvm.dbg.value(metadata i32 [[X_CURR]], [[META301:metadata !.*]], metadata !DIExpression()), [[DBG307]] +; ALL-NEXT: [[X_CURR_BITMASKED:%.*]] = and i32 [[X_CURR]], [[BITMASK]], [[DBG308:!dbg !.*]] +; ALL-NEXT: call void @llvm.dbg.value(metadata i32 [[X_CURR_BITMASKED]], [[META302:metadata !.*]], metadata !DIExpression()), [[DBG308]] +; ALL-NEXT: [[X_CURR_ISBITUNSET:%.*]] = icmp eq i32 [[X_CURR_BITMASKED]], 0, [[DBG309:!dbg !.*]] +; ALL-NEXT: call void @llvm.dbg.value(metadata i1 [[X_CURR_ISBITUNSET]], [[META303:metadata !.*]], metadata !DIExpression()), [[DBG309]] +; ALL-NEXT: [[X_NEXT]] = shl i32 [[X_CURR]], 1, [[DBG310:!dbg !.*]] +; ALL-NEXT: call void @llvm.dbg.value(metadata i32 [[X_NEXT]], [[META304:metadata !.*]], metadata !DIExpression()), [[DBG310]] +; ALL-NEXT: br i1 [[X_CURR_ISBITUNSET]], label [[LOOP]], label [[END:%.*]], [[DBG311:!dbg !.*]] +; ALL: end: +; ALL-NEXT: [[X_CURR_LCSSA:%.*]] = phi i32 [ [[X_CURR]], [[LOOP]] ], [[DBG307]] +; ALL-NEXT: [[X_NEXT_LCSSA:%.*]] = phi i32 [ [[X_NEXT]], [[LOOP]] ], [[DBG310]] +; ALL-NEXT: call void @llvm.dbg.value(metadata i32 [[X_CURR_LCSSA]], [[META301]], metadata !DIExpression()), [[DBG307]] +; ALL-NEXT: call void @use32(i32 [[X_NEXT_LCSSA]]), [[DBG312:!dbg !.*]] +; ALL-NEXT: ret i32 [[X_CURR_LCSSA]], [[DBG313:!dbg !.*]] +; +entry: + %bitmask = shl i32 1, %bit + br label %loop + +loop: + %x.curr = phi i32 [ %x, %entry ], [ %x.next, %loop ] + %x.curr.bitmasked = and i32 %x.curr, %bitmask + %x.curr.isbitunset = icmp eq i32 %x.curr.bitmasked, 0 + %x.next = shl i32 %x.curr, 1 + br i1 %x.curr.isbitunset, label %loop, label %end + +end: + call void @use32(i32 %x.next) + ret i32 %x.curr +} -- 2.7.4