llvm/test/Transforms/InstCombine/narrow.ll

   1 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
   2 ; RUN: opt < %s -passes=instcombine -S | FileCheck %s
   3
   4 target datalayout = "n8:16:32:64"
   5
   6 ; Eliminating the casts in this testcase (by narrowing the AND operation)
   7 ; allows instcombine to realize the function always returns false.
   8
   9 define i1 @test1(i32 %A, i32 %B) {
  10 ; CHECK-LABEL: @test1(
  11 ; CHECK-NEXT:    ret i1 false
  12 ;
  13   %C1 = icmp slt i32 %A, %B
  14   %ELIM1 = zext i1 %C1 to i32
  15   %C2 = icmp sgt i32 %A, %B
  16   %ELIM2 = zext i1 %C2 to i32
  17   %C3 = and i32 %ELIM1, %ELIM2
  18   %ELIM3 = trunc i32 %C3 to i1
  19   ret i1 %ELIM3
  20 }
  21
  22 ; The next 6 (3 logic ops * (scalar+vector)) tests show potential cases for narrowing a bitwise logic op.
  23
  24 define i32 @shrink_xor(i64 %a) {
  25 ; CHECK-LABEL: @shrink_xor(
  26 ; CHECK-NEXT:    [[TMP1:%.*]] = trunc i64 [[A:%.*]] to i32
  27 ; CHECK-NEXT:    [[TRUNC:%.*]] = xor i32 [[TMP1]], 1
  28 ; CHECK-NEXT:    ret i32 [[TRUNC]]
  29 ;
  30   %xor = xor i64 %a, 1
  31   %trunc = trunc i64 %xor to i32
  32   ret i32 %trunc
  33 }
  34
  35 ; Vectors (with splat constants) should get the same transform.
  36
  37 define <2 x i32> @shrink_xor_vec(<2 x i64> %a) {
  38 ; CHECK-LABEL: @shrink_xor_vec(
  39 ; CHECK-NEXT:    [[TMP1:%.*]] = trunc <2 x i64> [[A:%.*]] to <2 x i32>
  40 ; CHECK-NEXT:    [[TRUNC:%.*]] = xor <2 x i32> [[TMP1]], splat (i32 2)
  41 ; CHECK-NEXT:    ret <2 x i32> [[TRUNC]]
  42 ;
  43   %xor = xor <2 x i64> %a, <i64 2, i64 2>
  44   %trunc = trunc <2 x i64> %xor to <2 x i32>
  45   ret <2 x i32> %trunc
  46 }
  47
  48 ; Source and dest types are not in the datalayout.
  49
  50 define i3 @shrink_or(i6 %a) {
  51 ; CHECK-LABEL: @shrink_or(
  52 ; CHECK-NEXT:    [[TMP1:%.*]] = trunc i6 [[A:%.*]] to i3
  53 ; CHECK-NEXT:    [[TRUNC:%.*]] = or i3 [[TMP1]], 1
  54 ; CHECK-NEXT:    ret i3 [[TRUNC]]
  55 ;
  56   %or = or i6 %a, 33
  57   %trunc = trunc i6 %or to i3
  58   ret i3 %trunc
  59 }
  60
  61 ; Vectors (with non-splat constants) should get the same transform.
  62
  63 define <2 x i8> @shrink_or_vec(<2 x i16> %a) {
  64 ; CHECK-LABEL: @shrink_or_vec(
  65 ; CHECK-NEXT:    [[TMP1:%.*]] = trunc <2 x i16> [[A:%.*]] to <2 x i8>
  66 ; CHECK-NEXT:    [[TRUNC:%.*]] = or <2 x i8> [[TMP1]], <i8 -1, i8 0>
  67 ; CHECK-NEXT:    ret <2 x i8> [[TRUNC]]
  68 ;
  69   %or = or <2 x i16> %a, <i16 -1, i16 256>
  70   %trunc = trunc <2 x i16> %or to <2 x i8>
  71   ret <2 x i8> %trunc
  72 }
  73
  74 ; We discriminate against weird types.
  75
  76 define i31 @shrink_and(i64 %a) {
  77 ; CHECK-LABEL: @shrink_and(
  78 ; CHECK-NEXT:    [[AND:%.*]] = and i64 [[A:%.*]], 42
  79 ; CHECK-NEXT:    [[TRUNC:%.*]] = trunc nuw nsw i64 [[AND]] to i31
  80 ; CHECK-NEXT:    ret i31 [[TRUNC]]
  81 ;
  82   %and = and i64 %a, 42
  83   %trunc = trunc i64 %and to i31
  84   ret i31 %trunc
  85 }
  86
  87 ; Chop the top of the constant(s) if needed.
  88
  89 define <2 x i32> @shrink_and_vec(<2 x i33> %a) {
  90 ; CHECK-LABEL: @shrink_and_vec(
  91 ; CHECK-NEXT:    [[TMP1:%.*]] = trunc <2 x i33> [[A:%.*]] to <2 x i32>
  92 ; CHECK-NEXT:    [[TRUNC:%.*]] = and <2 x i32> [[TMP1]], <i32 0, i32 6>
  93 ; CHECK-NEXT:    ret <2 x i32> [[TRUNC]]
  94 ;
  95   %and = and <2 x i33> %a, <i33 4294967296, i33 6>
  96   %trunc = trunc <2 x i33> %and to <2 x i32>
  97   ret <2 x i32> %trunc
  98 }
  99
 100 ; FIXME:
 101 ; This is based on an 'any_of' loop construct.
 102 ; By narrowing the phi and logic op, we simplify away the zext and the final icmp.
 103
 104 define i1 @searchArray1(i32 %needle, ptr %haystack) {
 105 ; CHECK-LABEL: @searchArray1(
 106 ; CHECK-NEXT:  entry:
 107 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 108 ; CHECK:       loop:
 109 ; CHECK-NEXT:    [[INDVAR:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[INDVAR_NEXT:%.*]], [[LOOP]] ]
 110 ; CHECK-NEXT:    [[FOUND:%.*]] = phi i8 [ 0, [[ENTRY]] ], [ [[OR:%.*]], [[LOOP]] ]
 111 ; CHECK-NEXT:    [[TMP0:%.*]] = sext i32 [[INDVAR]] to i64
 112 ; CHECK-NEXT:    [[IDX:%.*]] = getelementptr i32, ptr [[HAYSTACK:%.*]], i64 [[TMP0]]
 113 ; CHECK-NEXT:    [[LD:%.*]] = load i32, ptr [[IDX]], align 4
 114 ; CHECK-NEXT:    [[CMP1:%.*]] = icmp eq i32 [[LD]], [[NEEDLE:%.*]]
 115 ; CHECK-NEXT:    [[ZEXT:%.*]] = zext i1 [[CMP1]] to i8
 116 ; CHECK-NEXT:    [[OR]] = or i8 [[FOUND]], [[ZEXT]]
 117 ; CHECK-NEXT:    [[INDVAR_NEXT]] = add i32 [[INDVAR]], 1
 118 ; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp eq i32 [[INDVAR_NEXT]], 1000
 119 ; CHECK-NEXT:    br i1 [[EXITCOND]], label [[EXIT:%.*]], label [[LOOP]]
 120 ; CHECK:       exit:
 121 ; CHECK-NEXT:    [[TOBOOL:%.*]] = icmp ne i8 [[OR]], 0
 122 ; CHECK-NEXT:    ret i1 [[TOBOOL]]
 123 ;
 124 entry:
 125   br label %loop
 126
 127 loop:
 128   %indvar = phi i32 [ 0, %entry ], [ %indvar.next, %loop ]
 129   %found = phi i8 [ 0, %entry ], [ %or, %loop ]
 130   %idx = getelementptr i32, ptr %haystack, i32 %indvar
 131   %ld = load i32, ptr %idx
 132   %cmp1 = icmp eq i32 %ld, %needle
 133   %zext = zext i1 %cmp1 to i8
 134   %or = or i8 %found, %zext
 135   %indvar.next = add i32 %indvar, 1
 136   %exitcond = icmp eq i32 %indvar.next, 1000
 137   br i1 %exitcond, label %exit, label %loop
 138
 139 exit:
 140   %tobool = icmp ne i8 %or, 0
 141   ret i1 %tobool
 142 }
 143
 144 ; FIXME:
 145 ; This is based on an 'all_of' loop construct.
 146 ; By narrowing the phi and logic op, we simplify away the zext and the final icmp.
 147
 148 define i1 @searchArray2(i32 %hay, ptr %haystack) {
 149 ; CHECK-LABEL: @searchArray2(
 150 ; CHECK-NEXT:  entry:
 151 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 152 ; CHECK:       loop:
 153 ; CHECK-NEXT:    [[INDVAR:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[INDVAR_NEXT:%.*]], [[LOOP]] ]
 154 ; CHECK-NEXT:    [[FOUND:%.*]] = phi i8 [ 1, [[ENTRY]] ], [ [[AND:%.*]], [[LOOP]] ]
 155 ; CHECK-NEXT:    [[IDX:%.*]] = getelementptr i32, ptr [[HAYSTACK:%.*]], i64 [[INDVAR]]
 156 ; CHECK-NEXT:    [[LD:%.*]] = load i32, ptr [[IDX]], align 4
 157 ; CHECK-NEXT:    [[CMP1:%.*]] = icmp eq i32 [[LD]], [[HAY:%.*]]
 158 ; CHECK-NEXT:    [[AND]] = select i1 [[CMP1]], i8 [[FOUND]], i8 0
 159 ; CHECK-NEXT:    [[INDVAR_NEXT]] = add i64 [[INDVAR]], 1
 160 ; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp eq i64 [[INDVAR_NEXT]], 1000
 161 ; CHECK-NEXT:    br i1 [[EXITCOND]], label [[EXIT:%.*]], label [[LOOP]]
 162 ; CHECK:       exit:
 163 ; CHECK-NEXT:    [[TOBOOL:%.*]] = icmp ne i8 [[AND]], 0
 164 ; CHECK-NEXT:    ret i1 [[TOBOOL]]
 165 ;
 166 entry:
 167   br label %loop
 168
 169 loop:
 170   %indvar = phi i64 [ 0, %entry ], [ %indvar.next, %loop ]
 171   %found = phi i8 [ 1, %entry ], [ %and, %loop ]
 172   %idx = getelementptr i32, ptr %haystack, i64 %indvar
 173   %ld = load i32, ptr %idx
 174   %cmp1 = icmp eq i32 %ld, %hay
 175   %zext = zext i1 %cmp1 to i8
 176   %and = and i8 %found, %zext
 177   %indvar.next = add i64 %indvar, 1
 178   %exitcond = icmp eq i64 %indvar.next, 1000
 179   br i1 %exitcond, label %exit, label %loop
 180
 181 exit:
 182   %tobool = icmp ne i8 %and, 0
 183   ret i1 %tobool
 184 }
 185
 186 ; FIXME:
 187 ; Narrowing should work with an 'xor' and is not limited to bool types.
 188
 189 define i32 @shrinkLogicAndPhi1(i8 %x, i1 %cond) {
 190 ; CHECK-LABEL: @shrinkLogicAndPhi1(
 191 ; CHECK-NEXT:  entry:
 192 ; CHECK-NEXT:    br i1 [[COND:%.*]], label [[IF:%.*]], label [[ENDIF:%.*]]
 193 ; CHECK:       if:
 194 ; CHECK-NEXT:    br label [[ENDIF]]
 195 ; CHECK:       endif:
 196 ; CHECK-NEXT:    [[PHI:%.*]] = phi i32 [ 21, [[ENTRY:%.*]] ], [ 33, [[IF]] ]
 197 ; CHECK-NEXT:    [[ZEXT:%.*]] = zext i8 [[X:%.*]] to i32
 198 ; CHECK-NEXT:    [[LOGIC:%.*]] = xor i32 [[PHI]], [[ZEXT]]
 199 ; CHECK-NEXT:    ret i32 [[LOGIC]]
 200 ;
 201 entry:
 202   br i1 %cond, label %if, label %endif
 203 if:
 204   br label %endif
 205 endif:
 206   %phi = phi i32 [ 21, %entry], [ 33, %if ]
 207   %zext = zext i8 %x to i32
 208   %logic = xor i32 %phi, %zext
 209   ret i32 %logic
 210 }
 211
 212 ; FIXME:
 213 ; Narrowing should work with an 'xor' and is not limited to bool types.
 214 ; Test that commuting the xor operands does not inhibit optimization.
 215
 216 define i32 @shrinkLogicAndPhi2(i8 %x, i1 %cond) {
 217 ; CHECK-LABEL: @shrinkLogicAndPhi2(
 218 ; CHECK-NEXT:  entry:
 219 ; CHECK-NEXT:    br i1 [[COND:%.*]], label [[IF:%.*]], label [[ENDIF:%.*]]
 220 ; CHECK:       if:
 221 ; CHECK-NEXT:    br label [[ENDIF]]
 222 ; CHECK:       endif:
 223 ; CHECK-NEXT:    [[PHI:%.*]] = phi i32 [ 21, [[ENTRY:%.*]] ], [ 33, [[IF]] ]
 224 ; CHECK-NEXT:    [[ZEXT:%.*]] = zext i8 [[X:%.*]] to i32
 225 ; CHECK-NEXT:    [[LOGIC:%.*]] = xor i32 [[PHI]], [[ZEXT]]
 226 ; CHECK-NEXT:    ret i32 [[LOGIC]]
 227 ;
 228 entry:
 229   br i1 %cond, label %if, label %endif
 230 if:
 231   br label %endif
 232 endif:
 233   %phi = phi i32 [ 21, %entry], [ 33, %if ]
 234   %zext = zext i8 %x to i32
 235   %logic = xor i32 %zext, %phi
 236   ret i32 %logic
 237 }
 238