llvm/test/Transforms/PhaseOrdering/lower-table-based-cttz.ll

   1 ;; This tests lowering of the implementations of table-based ctz
   2 ;; algorithm to the llvm.cttz instruction in the -O3 case.
   3
   4 ;; C producer:
   5 ;; int ctz1 (unsigned x)
   6 ;; {
   7 ;; static const char table[32] =
   8 ;;    {
   9 ;;     0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8,
  10 ;;      31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
  11 ;;    };
  12 ;;   return table[((unsigned)((x & -x) * 0x077CB531U)) >> 27];
  13 ;; }
  14 ;; Compiled as: clang -O3 test.c -S -emit-llvm -Xclang -disable-llvm-optzns
  15
  16 ; RUN: opt -O3 -S < %s | FileCheck %s
  17
  18 ; CHECK: call range(i32 0, 33) i32 @llvm.cttz.i32
  19
  20 @ctz1.table = internal constant [32 x i8] c"\00\01\1C\02\1D\0E\18\03\1E\16\14\0F\19\11\04\08\1F\1B\0D\17\15\13\10\07\1A\0C\12\06\0B\05\0A\09", align 16
  21
  22 define i32 @ctz1(i32 noundef %x) {
  23 entry:
  24   %x.addr = alloca i32, align 4
  25   store i32 %x, ptr %x.addr, align 4
  26   %0 = load i32, ptr %x.addr, align 4
  27   %1 = load i32, ptr %x.addr, align 4
  28   %sub = sub i32 0, %1
  29   %and = and i32 %0, %sub
  30   %mul = mul i32 %and, 125613361
  31   %shr = lshr i32 %mul, 27
  32   %idxprom = zext i32 %shr to i64
  33   %arrayidx = getelementptr inbounds [32 x i8], ptr @ctz1.table, i64 0, i64 %idxprom
  34   %2 = load i8, ptr %arrayidx, align 1
  35   %conv = sext i8 %2 to i32
  36   ret i32 %conv
  37 }