[LLVMbugs] [Bug 17130] New: bit-scan-reverse / count-leading-zeros loop not recognized

[bugzilla-daemon at llvm.org]

http://llvm.org/bugs/show_bug.cgi?id=17130

            Bug ID: 17130
           Summary: bit-scan-reverse / count-leading-zeros loop not
                    recognized
           Product: libraries
           Version: trunk
          Hardware: PC
                OS: All
            Status: NEW
          Severity: normal
          Priority: P
         Component: Scalar Optimizations
          Assignee: unassignedbugs at nondot.org
          Reporter: kkhoo at perfwizard.com
                CC: llvmbugs at cs.uiuc.edu
    Classification: Unclassified

This is very similar to bug 17128 (count trailing zeros), but I'm filing a
separate bug just in case the solution involves some differences in
implementation in the compiler.

On the surface, this one maps to existing hardware instructions (Power =
ctlzw/d, ARM = clz) more easily than count-trailing-zeros. x86 has bsr/lzcnt as
well as bsf/tzcnt.

Here's a test file with a couple of implementations of count-leading-zeros.
Currently, llvm recognizes that both functions have bit-testing loops ('bt'
instructions is generated), but doesn't know that they can be simplified to
count-leading-zeros:

$ ./clang -v
clang version 3.4 (trunk 189776)
Target: x86_64-apple-darwin11.4.2
Thread model: posix

$ cat lzcnt.c 
int lzcnt(int x) {
    int count = 0;
    int i = 31;
    while (i>=0 && (((x >> i) & 0x1) == 0)) {
        i--;
        count++;
    }
    return count;
}

int lzcnt2(int x) {
    int count = 0;
    int i;
    for (i=0; i<32; i++) {
        if ((x & (1 << (31-i))) != 0) break;
        count++;
    }
    return count;
}


$ ./clang -S -O3 -fomit-frame-pointer -march=core-avx2 -o /dev/stdout lzcnt.c 
    .section    __TEXT,__text,regular,pure_instructions
    .globl    _lzcnt
    .align    4, 0x90
_lzcnt:                                 ## @lzcnt
    .cfi_startproc
## BB#0:                                ## %entry
    xorl    %eax, %eax
    movl    $32, %ecx
    .align    4, 0x90
LBB0_1:                                 ## %land.rhs
                                        ## =>This Inner Loop Header: Depth=1
    decl    %ecx
    btl    %ecx, %edi
    jb    LBB0_3
## BB#2:                                ## %while.body
                                        ##   in Loop: Header=BB0_1 Depth=1
    incl    %eax
    testl    %ecx, %ecx
    jg    LBB0_1
LBB0_3:                                 ## %while.end
    ret
    .cfi_endproc

    .globl    _lzcnt2
    .align    4, 0x90
_lzcnt2:                                ## @lzcnt2
    .cfi_startproc
## BB#0:                                ## %entry
    xorl    %eax, %eax
    movl    $31, %ecx
    .align    4, 0x90
LBB1_1:                                 ## %for.body
                                        ## =>This Inner Loop Header: Depth=1
    btl    %ecx, %edi
    jb    LBB1_3
## BB#2:                                ## %if.end
                                        ##   in Loop: Header=BB1_1 Depth=1
    decl    %ecx
    incl    %eax
    cmpl    $32, %eax
    jl    LBB1_1
LBB1_3:                                 ## %for.end
    ret
    .cfi_endproc

-- 
You are receiving this mail because:
You are on the CC list for the bug.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-bugs/attachments/20130906/ed06bee1/attachment.html>