http://gcc.gnu.org/bugzilla/show_bug.cgi?id=29776
--- Comment #4 from Uros Bizjak <ubizjak at gmail dot com> 2012-07-30 11:36:23 UTC --- > Perhaps REE can be taught about ctz giving a non-negative result. Maybe we need some VRP pass to remove these extensions. Please note an example from (duplicate) PR54115, where we generate: #include <stdint.h> uint64_t foo(long x){ return __builtin_ctzl(x); } foo: bsfq %rdi, %rax cltq this is DImode -> DImode operation, followed by sign-extend from SImode partial reg. Your examples in comment #3: bsfl %esi, %esi movslq %esi, %rsi can be "fixed" by slapping any_extend:DI to CTZ pattern, to consume either ZERO_EXTEND or SIGN_EXTEND of the value (it doesn't matter for ranges [0..(some small number)]). The DImode example above can be "fixed" by adding SUBREG to all patterns. But, I think that there is more optimal implementation than exploding the number of bit manipulating patterns.