Index: llvm/trunk/lib/CodeGen/SelectionDAG/SelectionDAG.cpp
===================================================================
--- llvm/trunk/lib/CodeGen/SelectionDAG/SelectionDAG.cpp
+++ llvm/trunk/lib/CodeGen/SelectionDAG/SelectionDAG.cpp
@@ -2353,9 +2353,23 @@
     break;
   }
   case ISD::CTTZ:
-  case ISD::CTTZ_ZERO_UNDEF:
+  case ISD::CTTZ_ZERO_UNDEF: {
+    computeKnownBits(Op.getOperand(0), Known2, DemandedElts, Depth + 1);
+    // If we have a known 1, its position is our upper bound.
+    unsigned PossibleTZ = Known2.One.countTrailingZeros();
+    unsigned LowBits = Log2_32(PossibleTZ) + 1;
+    Known.Zero.setBitsFrom(LowBits);
+    break;
+  }
   case ISD::CTLZ:
-  case ISD::CTLZ_ZERO_UNDEF:
+  case ISD::CTLZ_ZERO_UNDEF: {
+    computeKnownBits(Op.getOperand(0), Known2, DemandedElts, Depth + 1);
+    // If we have a known 1, its position is our upper bound.
+    unsigned PossibleLZ = Known2.One.countLeadingZeros();
+    unsigned LowBits = Log2_32(PossibleLZ) + 1;
+    Known.Zero.setBitsFrom(LowBits);
+    break;
+  }
   case ISD::CTPOP: {
     Known.Zero.setBitsFrom(Log2_32(BitWidth)+1);
     break;
Index: llvm/trunk/test/CodeGen/X86/clz.ll
===================================================================
--- llvm/trunk/test/CodeGen/X86/clz.ll
+++ llvm/trunk/test/CodeGen/X86/clz.ll
@@ -786,7 +786,6 @@
 ; X32-NEXT:    orb $2, %al
 ; X32-NEXT:    movzbl %al, %eax
 ; X32-NEXT:    bsfl %eax, %eax
-; X32-NEXT:    andb $1, %al
 ; X32-NEXT:    # kill: %AL<def> %AL<kill> %EAX<kill>
 ; X32-NEXT:    retl
 ;
@@ -795,7 +794,6 @@
 ; X64-NEXT:    orb $2, %dil
 ; X64-NEXT:    movzbl %dil, %eax
 ; X64-NEXT:    bsfl %eax, %eax
-; X64-NEXT:    andb $1, %al
 ; X64-NEXT:    # kill: %AL<def> %AL<kill> %EAX<kill>
 ; X64-NEXT:    retq
 ;
@@ -805,7 +803,6 @@
 ; X32-CLZ-NEXT:    orb $2, %al
 ; X32-CLZ-NEXT:    movzbl %al, %eax
 ; X32-CLZ-NEXT:    tzcntl %eax, %eax
-; X32-CLZ-NEXT:    andb $1, %al
 ; X32-CLZ-NEXT:    # kill: %AL<def> %AL<kill> %EAX<kill>
 ; X32-CLZ-NEXT:    retl
 ;
@@ -814,7 +811,6 @@
 ; X64-CLZ-NEXT:    orb $2, %dil
 ; X64-CLZ-NEXT:    movzbl %dil, %eax
 ; X64-CLZ-NEXT:    tzcntl %eax, %eax
-; X64-CLZ-NEXT:    andb $1, %al
 ; X64-CLZ-NEXT:    # kill: %AL<def> %AL<kill> %EAX<kill>
 ; X64-CLZ-NEXT:    retq
   %x2 = or i8 %x, 2
@@ -830,8 +826,7 @@
 ; X32-NEXT:    orb $64, %al
 ; X32-NEXT:    movzbl %al, %eax
 ; X32-NEXT:    bsrl %eax, %eax
-; X32-NEXT:    notl %eax
-; X32-NEXT:    andb $1, %al
+; X32-NEXT:    xorl $7, %eax
 ; X32-NEXT:    # kill: %AL<def> %AL<kill> %EAX<kill>
 ; X32-NEXT:    retl
 ;
@@ -840,8 +835,7 @@
 ; X64-NEXT:    orb $64, %dil
 ; X64-NEXT:    movzbl %dil, %eax
 ; X64-NEXT:    bsrl %eax, %eax
-; X64-NEXT:    notl %eax
-; X64-NEXT:    andb $1, %al
+; X64-NEXT:    xorl $7, %eax
 ; X64-NEXT:    # kill: %AL<def> %AL<kill> %EAX<kill>
 ; X64-NEXT:    retq
 ;
@@ -852,7 +846,6 @@
 ; X32-CLZ-NEXT:    movzbl %al, %eax
 ; X32-CLZ-NEXT:    lzcntl %eax, %eax
 ; X32-CLZ-NEXT:    addl $-24, %eax
-; X32-CLZ-NEXT:    andb $1, %al
 ; X32-CLZ-NEXT:    # kill: %AL<def> %AL<kill> %EAX<kill>
 ; X32-CLZ-NEXT:    retl
 ;
@@ -862,7 +855,6 @@
 ; X64-CLZ-NEXT:    movzbl %dil, %eax
 ; X64-CLZ-NEXT:    lzcntl %eax, %eax
 ; X64-CLZ-NEXT:    addl $-24, %eax
-; X64-CLZ-NEXT:    andb $1, %al
 ; X64-CLZ-NEXT:    # kill: %AL<def> %AL<kill> %EAX<kill>
 ; X64-CLZ-NEXT:    retq