Update to use the new MathExtras.h support for log2 computation.
authorChris Lattner <sabre@nondot.org>
Tue, 2 Aug 2005 19:26:06 +0000 (19:26 +0000)
committerChris Lattner <sabre@nondot.org>
Tue, 2 Aug 2005 19:26:06 +0000 (19:26 +0000)
Patch contributed by Jim Laskey!

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@22594 91177308-0d34-0410-b5e6-96231b3b80d8

lib/CodeGen/SelectionDAG/SelectionDAG.cpp
lib/Target/Alpha/AlphaISelPattern.cpp
lib/Target/IA64/IA64ISelPattern.cpp
lib/Target/PowerPC/PPC32ISelSimple.cpp
lib/Target/PowerPC/PPC64ISelPattern.cpp
lib/Target/PowerPC/PPCAsmPrinter.cpp
lib/Target/PowerPC/PPCISelPattern.cpp
lib/Target/SparcV9/SparcV9BurgISel.cpp
lib/Target/TargetData.cpp
lib/Target/X86/X86ISelPattern.cpp
lib/Target/X86/X86ISelSimple.cpp

index 530422dacb4f89eba0f806841a1ee4c9d6b24da6..e45e708ede6ffce3326beeedce4f364717784374 100644 (file)
@@ -16,6 +16,7 @@
 #include "llvm/GlobalValue.h"
 #include "llvm/Assembly/Writer.h"
 #include "llvm/CodeGen/MachineBasicBlock.h"
+#include "llvm/Support/MathExtras.h"
 #include "llvm/Target/TargetLowering.h"
 #include <iostream>
 #include <set>
@@ -45,15 +46,6 @@ static bool isAssociativeBinOp(unsigned Opcode) {
   }
 }
 
-static unsigned ExactLog2(uint64_t Val) {
-  unsigned Count = 0;
-  while (Val != 1) {
-    Val >>= 1;
-    ++Count;
-  }
-  return Count;
-}
-
 // isInvertibleForFree - Return true if there is no cost to emitting the logical
 // inverse of this node.
 static bool isInvertibleForFree(SDOperand N) {
@@ -527,7 +519,7 @@ SDOperand SelectionDAG::getSetCC(ISD::CondCode Cond, MVT::ValueType VT,
             // Perform the xform if the AND RHS is a single bit.
             if ((AndRHS->getValue() & (AndRHS->getValue()-1)) == 0) {
               return getNode(ISD::SRL, VT, N1,
-                             getConstant(ExactLog2(AndRHS->getValue()),
+                             getConstant(Log2_64(AndRHS->getValue()),
                                                    TLI.getShiftAmountTy()));
             }
           } else if (Cond == ISD::SETEQ && C2 == AndRHS->getValue()) {
@@ -535,7 +527,7 @@ SDOperand SelectionDAG::getSetCC(ISD::CondCode Cond, MVT::ValueType VT,
             // Perform the xform if C2 is a single bit.
             if ((C2 & (C2-1)) == 0) {
               return getNode(ISD::SRL, VT, N1,
-                             getConstant(ExactLog2(C2),TLI.getShiftAmountTy()));
+                             getConstant(Log2_64(C2),TLI.getShiftAmountTy()));
             }
           }
         }
@@ -956,7 +948,7 @@ SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT,
 
       // FIXME: Move this to the DAG combiner when it exists.
       if ((C2 & C2-1) == 0) {
-        SDOperand ShAmt = getConstant(ExactLog2(C2), TLI.getShiftAmountTy());
+        SDOperand ShAmt = getConstant(Log2_64(C2), TLI.getShiftAmountTy());
         return getNode(ISD::SHL, VT, N1, ShAmt);
       }
       break;
@@ -974,7 +966,7 @@ SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT,
     case ISD::UDIV:
       // FIXME: Move this to the DAG combiner when it exists.
       if ((C2 & C2-1) == 0 && C2) {
-        SDOperand ShAmt = getConstant(ExactLog2(C2), TLI.getShiftAmountTy());
+        SDOperand ShAmt = getConstant(Log2_64(C2), TLI.getShiftAmountTy());
         return getNode(ISD::SRL, VT, N1, ShAmt);
       }
       break;
@@ -1410,7 +1402,7 @@ SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT,
               // exists.
               if (ConstantSDNode *AC = dyn_cast<ConstantSDNode>(N2))
                 if ((AC->getValue() & (AC->getValue()-1)) == 0) {
-                  unsigned ShCtV = ExactLog2(AC->getValue());
+                  unsigned ShCtV = Log2_64(AC->getValue());
                   ShCtV = MVT::getSizeInBits(XType)-ShCtV-1;
                   SDOperand ShCt = getConstant(ShCtV, TLI.getShiftAmountTy());
                   SDOperand Shift = getNode(ISD::SRL, XType,
index 2697544cf22cec4229e206ac56c0454739f75b47..9b1619ffced814eb0e71214c9b08862c6db9b6c8 100644 (file)
@@ -801,20 +801,6 @@ SDOperand AlphaISel::BuildUDIVSequence(SDOperand N) {
   return Q;
 }
 
-//From PPC32
-/// ExactLog2 - This function solves for (Val == 1 << (N-1)) and returns N.  It
-/// returns zero when the input is not exactly a power of two.
-static unsigned ExactLog2(uint64_t Val) {
-  if (Val == 0 || (Val & (Val-1))) return 0;
-  unsigned Count = 0;
-  while (Val != 1) {
-    Val >>= 1;
-    ++Count;
-  }
-  return Count;
-}
-
-
 //These describe LDAx
 static const int IMM_LOW  = -32768;
 static const int IMM_HIGH = 32767;
index ab6bb2c9393a6f6faafabc11cd22c39e6a3eb351..62b195c6598a16959e06399a7f94f5a5a3d75372 100644 (file)
@@ -847,29 +847,6 @@ SDOperand ISel::BuildConstmulSequence(SDOperand N) {
   return finalresult;
 }
 
-/// ExactLog2 - This function solves for (Val == 1 << (N-1)) and returns N.  It
-/// returns zero when the input is not exactly a power of two.
-static unsigned ExactLog2(uint64_t Val) {
-  if (Val == 0 || (Val & (Val-1))) return 0;
-  unsigned Count = 0;
-  while (Val != 1) {
-    Val >>= 1;
-    ++Count;
-  }
-  return Count;
-}
-
-/// ExactLog2sub1 - This function solves for (Val == (1 << (N-1))-1)
-/// and returns N.  It returns 666 if Val is not 2^n -1 for some n.
-static unsigned ExactLog2sub1(uint64_t Val) {
-  unsigned int n;
-  for(n=0; n<64; n++) {
-    if(Val==(uint64_t)((1LL<<n)-1))
-      return n;
-  }
-  return 666;
-}
-
 /// ponderIntegerDivisionBy - When handling integer divides, if the divide
 /// is by a constant such that we can efficiently codegen it, this
 /// function says what to do. Currently, it returns 0 if the division must
@@ -882,7 +859,8 @@ static unsigned ponderIntegerDivisionBy(SDOperand N, bool isSigned,
 
   int64_t v = (int64_t)cast<ConstantSDNode>(N)->getSignExtended();
 
-  if ((Imm = ExactLog2(v))) { // if a division by a power of two, say so
+  if (isPowerOf2_64(v)) { // if a division by a power of two, say so
+    Imm = Log2_64(v);
     return 1;
   }
 
@@ -895,7 +873,8 @@ static unsigned ponderIntegerAndWith(SDOperand N, unsigned& Imm) {
 
   int64_t v = (int64_t)cast<ConstantSDNode>(N)->getSignExtended();
 
-  if ((Imm = ExactLog2sub1(v))!=666) { // if ANDing with ((2^n)-1) for some n
+  if (isMask_64(v)) { // if ANDing with ((2^n)-1) for some n
+    Imm = Log2_64(v);
     return 1; // say so
   }
 
index aabee9524992a3c9f14746f030eb8e9e12fbdc9c..8771db21bb7e469632776de9f665f79747ac26c1 100644 (file)
 #include "llvm/Target/TargetMachine.h"
 #include "llvm/Support/GetElementPtrTypeIterator.h"
 #include "llvm/Support/InstVisitor.h"
+#include "llvm/Support/MathExtras.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/ADT/Statistic.h"
 #include <vector>
 using namespace llvm;
 
+
+// IsRunOfOnes - returns true if Val consists of one contiguous run of 1's with
+// any number of 0's on either side.  the 1's are allowed to wrap from LSB to
+// MSB.  so 0x000FFF0, 0x0000FFFF, and 0xFF0000FF are all runs.  0x0F0F0000 is
+// not, since all 1's are not contiguous.
+static bool IsRunOfOnes(unsigned Val, unsigned &MB, unsigned &ME) {
+  if (isShiftedMask_32(Val)) {
+    // look for the first non-zero bit
+    MB = CountLeadingZeros_32(Val);
+    // look for the first zero bit after the run of ones
+    ME = CountLeadingZeros_32((Val - 1) ^ Val);
+    return true;
+  } else if (isShiftedMask_32(Val = ~Val)) { // invert mask
+    // effectively look for the first zero bit
+    ME = CountLeadingZeros_32(Val) - 1;
+    // effectively look for the first one bit after the run of zeros
+    MB = CountLeadingZeros_32((Val - 1) ^ Val) + 1;
+    return true;
+  }
+  // no run present
+  return false;
+}
+
 namespace {
   /// TypeClass - Used by the PowerPC backend to group LLVM types by their basic
   /// PPC Representation.
@@ -2085,73 +2109,6 @@ void PPC32ISel::emitBinaryFPOperation(MachineBasicBlock *BB,
   BuildMI(*BB, IP, Opcode, 2, DestReg).addReg(Op0r).addReg(Op1r);
 }
 
-// ExactLog2 - This function solves for (Val == 1 << (N-1)) and returns N.  It
-// returns zero when the input is not exactly a power of two.
-static unsigned ExactLog2(unsigned Val) {
-  if (Val == 0 || (Val & (Val-1))) return 0;
-  unsigned Count = 0;
-  while (Val != 1) {
-    Val >>= 1;
-    ++Count;
-  }
-  return Count;
-}
-
-// isRunOfOnes - returns true if Val consists of one contiguous run of 1's with
-// any number of 0's on either side.  the 1's are allowed to wrap from LSB to
-// MSB.  so 0x000FFF0, 0x0000FFFF, and 0xFF0000FF are all runs.  0x0F0F0000 is
-// not, since all 1's are not contiguous.
-static bool isRunOfOnes(unsigned Val, unsigned &MB, unsigned &ME) {
-  bool isRun = true;
-  MB = 0;
-  ME = 0;
-
-  // look for first set bit
-  int i = 0;
-  for (; i < 32; i++) {
-    if ((Val & (1 << (31 - i))) != 0) {
-      MB = i;
-      ME = i;
-      break;
-    }
-  }
-
-  // look for last set bit
-  for (; i < 32; i++) {
-    if ((Val & (1 << (31 - i))) == 0)
-      break;
-    ME = i;
-  }
-
-  // look for next set bit
-  for (; i < 32; i++) {
-    if ((Val & (1 << (31 - i))) != 0)
-      break;
-  }
-
-  // if we exhausted all the bits, we found a match at this point for 0*1*0*
-  if (i == 32)
-    return true;
-
-  // since we just encountered more 1's, if it doesn't wrap around to the
-  // most significant bit of the word, then we did not find a match to 1*0*1* so
-  // exit.
-  if (MB != 0)
-    return false;
-
-  // look for last set bit
-  for (MB = i; i < 32; i++) {
-    if ((Val & (1 << (31 - i))) == 0)
-      break;
-  }
-
-  // if we exhausted all the bits, then we found a match for 1*0*1*, otherwise,
-  // the value is not a run of ones.
-  if (i == 32)
-    return true;
-  return false;
-}
-
 /// isInsertAndHalf - Helper function for emitBitfieldInsert.  Returns true if
 /// OpUser has one use, is used by an or instruction, and is itself an and whose
 /// second operand is a constant int.  Optionally, set OrI to the Or instruction
@@ -2281,7 +2238,7 @@ bool PPC32ISel::emitBitfieldInsert(User *OpUser, unsigned DestReg) {
   // succeeded in matching one of the cases for generating rlwimi.  Update the
   // skip lists and users of the Instruction::Or.
   unsigned MB, ME;
-  if (((TgtMask ^ InsMask) == 0xFFFFFFFF) && isRunOfOnes(InsMask, MB, ME)) {
+  if (((TgtMask ^ InsMask) == 0xFFFFFFFF) && IsRunOfOnes(InsMask, MB, ME)) {
     SkipList.push_back(Op0User);
     SkipList.push_back(Op1User);
     SkipList.push_back(OptAndI);
@@ -2320,7 +2277,7 @@ bool PPC32ISel::emitBitfieldExtract(MachineBasicBlock *MBB,
   if (matched == false)
     return false;
 
-  if (isRunOfOnes(Imm, MB, ME)) {
+  if (IsRunOfOnes(Imm, MB, ME)) {
     unsigned SrcReg = getReg(Op, MBB, IP);
     BuildMI(*MBB, IP, PPC::RLWINM, 4, DestReg).addReg(SrcReg).addImm(Rotate)
       .addImm(MB).addImm(ME);
@@ -2361,7 +2318,7 @@ void PPC32ISel::emitBinaryConstOperation(MachineBasicBlock *MBB,
 
   if (Opcode == 2 && !Op1->isNullValue()) {
     unsigned MB, ME, mask = Op1->getRawValue();
-    if (isRunOfOnes(mask, MB, ME)) {
+    if (IsRunOfOnes(mask, MB, ME)) {
       BuildMI(*MBB, IP, PPC::RLWINM, 4, DestReg).addReg(Op0Reg).addImm(0)
         .addImm(MB).addImm(ME);
       return;
@@ -2582,7 +2539,9 @@ void PPC32ISel::doMultiplyConst(MachineBasicBlock *MBB,
   }
 
   // If the element size is exactly a power of 2, use a shift to get it.
-  if (unsigned Shift = ExactLog2(CI->getRawValue())) {
+  uint64_t C = CI->getRawValue();
+  if (isPowerOf2_64(C)) {
+    unsigned Shift = Log2_64(C);
     ConstantUInt *ShiftCI = ConstantUInt::get(Type::UByteTy, Shift);
     emitShiftOperation(MBB, IP, Op0, ShiftCI, true, Op0->getType(), 0, DestReg);
     return;
@@ -2729,8 +2688,8 @@ void PPC32ISel::emitDivRemOperation(MachineBasicBlock *MBB,
         return;
       }
 
-      unsigned log2V = ExactLog2(V);
-      if (log2V != 0 && Ty->isSigned()) {
+      if (isPowerOf2_32(V) && Ty->isSigned()) {
+        unsigned log2V = Log2_32(V);
         unsigned Op0Reg = getReg(Op0, MBB, IP);
         unsigned TmpReg = makeAnotherReg(Op0->getType());
 
index 854ccf024f8ffebbcbe47488f46586d5b8dc02eb..e5b53f58e954e4bcc5d8f254fea9b0c5958a2bd9 100644 (file)
@@ -34,7 +34,7 @@
 using namespace llvm;
 
 //===----------------------------------------------------------------------===//
-//  PPC32TargetLowering - PPC32 Implementation of the TargetLowering interface
+//  PPC64TargetLowering - PPC64 Implementation of the TargetLowering interface
 namespace {
   class PPC64TargetLowering : public TargetLowering {
     int VarArgsFrameIndex;            // FrameIndex for start of varargs area.
@@ -258,6 +258,7 @@ PPC64TargetLowering::LowerCallTo(SDOperand Chain,
 
     // Just to be safe, we'll always reserve the full 48 bytes of linkage area
     // plus 64 bytes of argument space in case any called code gets funky on us.
+    // (Required by ABI to support var arg)
     if (NumBytes < 112) NumBytes = 112;
 
     // Adjust the stack pointer for the new arguments...
@@ -397,7 +398,7 @@ namespace {
 Statistic<>NotLogic("ppc-codegen", "Number of inverted logical ops");
 Statistic<>FusedFP("ppc-codegen", "Number of fused fp operations");
 //===--------------------------------------------------------------------===//
-/// ISel - PPC32 specific code to select PPC32 machine instructions for
+/// ISel - PPC64 specific code to select PPC64 machine instructions for
 /// SelectionDAG operations.
 //===--------------------------------------------------------------------===//
 class ISel : public SelectionDAGISel {
@@ -447,18 +448,6 @@ public:
   void SelectBranchCC(SDOperand N);
 };
 
-/// ExactLog2 - This function solves for (Val == 1 << (N-1)) and returns N.  It
-/// returns zero when the input is not exactly a power of two.
-static unsigned ExactLog2(unsigned Val) {
-  if (Val == 0 || (Val & (Val-1))) return 0;
-  unsigned Count = 0;
-  while (Val != 1) {
-    Val >>= 1;
-    ++Count;
-  }
-  return Count;
-}
-
 /// getImmediateForOpcode - This method returns a value indicating whether
 /// the ConstantSDNode N can be used as an immediate to Opcode.  The return
 /// values are either 0, 1 or 2.  0 indicates that either N is not a
@@ -477,25 +466,25 @@ static unsigned getImmediateForOpcode(SDOperand N, unsigned Opcode,
   switch(Opcode) {
   default: return 0;
   case ISD::ADD:
-    if (v <= 32767 && v >= -32768) { Imm = v & 0xFFFF; return 1; }
+    if (isInt16(v))            { Imm = v & 0xFFFF; return 1; }
     if ((v & 0x0000FFFF) == 0) { Imm = v >> 16; return 2; }
     break;
   case ISD::AND:
   case ISD::XOR:
   case ISD::OR:
-    if (v >= 0 && v <= 65535) { Imm = v & 0xFFFF; return 1; }
+    if (isUInt16(v))           { Imm = v & 0xFFFF; return 1; }
     if ((v & 0x0000FFFF) == 0) { Imm = v >> 16; return 2; }
     break;
   case ISD::MUL:
   case ISD::SUB:
-    if (v <= 32767 && v >= -32768) { Imm = v & 0xFFFF; return 1; }
+    if (isInt16(v))            { Imm = v & 0xFFFF; return 1; }
     break;
   case ISD::SETCC:
-    if (U && (v >= 0 && v <= 65535)) { Imm = v & 0xFFFF; return 1; }
-    if (!U && (v <= 32767 && v >= -32768)) { Imm = v & 0xFFFF; return 1; }
+    if (U && isUInt16(v))      { Imm = v & 0xFFFF; return 1; }
+    if (!U && isInt16(v))      { Imm = v & 0xFFFF; return 1; }
     break;
   case ISD::SDIV:
-    if ((Imm = ExactLog2(v))) { return 3; }
+    if (isPowerOf2_32(v))      { Imm = Log2_32(v); return 3; }
     break;
   }
   return 0;
@@ -1636,7 +1625,7 @@ void ISel::Select(SDOperand N) {
 }
 
 
-/// createPPC32PatternInstructionSelector - This pass converts an LLVM function
+/// createPPC64PatternInstructionSelector - This pass converts an LLVM function
 /// into a machine code representation using pattern matching and a machine
 /// description file.
 ///
index 6a28711f70491aee3581aeebbc45dd0f6773a243..90abbd22f65e8b1c1ef46e3df0b0b0d31541c91f 100644 (file)
@@ -698,7 +698,7 @@ bool AIXAsmPrinter::doFinalization(Module &M) {
       O << "\t.lcomm " << Name << ",16,_global.bss_c";
     } else {
       O << "\t.comm " << Name << "," << TD.getTypeSize(I->getType())
-        << "," << log2((unsigned)TD.getTypeAlignment(I->getType()));
+        << "," << Log2_32((unsigned)TD.getTypeAlignment(I->getType()));
     }
     O << "\t\t# ";
     WriteAsOperand(O, I, true, true, &M);
index fa737e3416890f114a95e8a69e0a5236f601e617..0e36b0ff76cf293b982f7c2bcc3976dbb0cb360d 100644 (file)
 #include <algorithm>
 using namespace llvm;
 
+
+// IsRunOfOnes - returns true if Val consists of one contiguous run of 1's with
+// any number of 0's on either side.  the 1's are allowed to wrap from LSB to
+// MSB.  so 0x000FFF0, 0x0000FFFF, and 0xFF0000FF are all runs.  0x0F0F0000 is
+// not, since all 1's are not contiguous.
+static bool IsRunOfOnes(unsigned Val, unsigned &MB, unsigned &ME) {
+  if (isShiftedMask_32(Val)) {
+    // look for the first non-zero bit
+    MB = CountLeadingZeros_32(Val);
+    // look for the first zero bit after the run of ones
+    ME = CountLeadingZeros_32((Val - 1) ^ Val);
+    return true;
+  } else if (isShiftedMask_32(Val = ~Val)) { // invert mask
+    // effectively look for the first zero bit
+    ME = CountLeadingZeros_32(Val) - 1;
+    // effectively look for the first one bit after the run of zeros
+    MB = CountLeadingZeros_32((Val - 1) ^ Val) + 1;
+    return true;
+  }
+  // no run present
+  return false;
+}
+
 //===----------------------------------------------------------------------===//
 //  PPC32TargetLowering - PPC32 Implementation of the TargetLowering interface
 namespace {
@@ -321,6 +344,7 @@ PPC32TargetLowering::LowerCallTo(SDOperand Chain,
 
     // Just to be safe, we'll always reserve the full 24 bytes of linkage area
     // plus 32 bytes of argument space in case any called code gets funky on us.
+    // (Required by ABI to support var arg)
     if (NumBytes < 56) NumBytes = 56;
 
     // Adjust the stack pointer for the new arguments...
@@ -664,36 +688,36 @@ static unsigned getImmediateForOpcode(SDOperand N, unsigned Opcode,
   switch(Opcode) {
   default: return 0;
   case ISD::ADD:
-    if (v <= 32767 && v >= -32768) { Imm = v & 0xFFFF; return 1; }
+    if (isInt16(v))             { Imm = v & 0xFFFF; return 1; }
     if ((v & 0x0000FFFF) == 0) { Imm = v >> 16; return 2; }
     break;
   case ISD::AND: {
     unsigned MB, ME;
     if (IsRunOfOnes(v, MB, ME)) { Imm = MB << 16 | ME & 0xFFFF; return 5; }
-    if (v >= 0 && v <= 65535) { Imm = v & 0xFFFF; return 1; }
+    if (isUInt16(v))            { Imm = v & 0xFFFF; return 1; }
     if ((v & 0x0000FFFF) == 0) { Imm = v >> 16; return 2; }
     break;
   }
   case ISD::XOR:
   case ISD::OR:
-    if (v >= 0 && v <= 65535) { Imm = v & 0xFFFF; return 1; }
+    if (isUInt16(v))            { Imm = v & 0xFFFF; return 1; }
     if ((v & 0x0000FFFF) == 0) { Imm = v >> 16; return 2; }
     break;
   case ISD::MUL:
-    if (v <= 32767 && v >= -32768) { Imm = v & 0xFFFF; return 1; }
+    if (isInt16(v))             { Imm = v & 0xFFFF; return 1; }
     break;
   case ISD::SUB:
     // handle subtract-from separately from subtract, since subi is really addi
-    if (U && v <= 32767 && v >= -32768) { Imm = v & 0xFFFF; return 1; }
-    if (!U && v <= 32768 && v >= -32767) { Imm = (-v) & 0xFFFF; return 1; }
+    if (U && isInt16(v))        { Imm = v    & 0xFFFF; return 1; }
+    if (!U && isInt16(-v))      { Imm = (-v) & 0xFFFF; return 1; }
     break;
   case ISD::SETCC:
-    if (U && (v >= 0 && v <= 65535)) { Imm = v & 0xFFFF; return 1; }
-    if (!U && (v <= 32767 && v >= -32768)) { Imm = v & 0xFFFF; return 1; }
+    if (U && isUInt16(v))       { Imm = v & 0xFFFF; return 1; }
+    if (!U && isInt16(v))       { Imm = v & 0xFFFF; return 1; }
     break;
   case ISD::SDIV:
-    if ((Imm = ExactLog2(v))) { return 3; }
-    if ((Imm = ExactLog2(-v))) { Imm = -Imm; return 3; }
+    if (isPowerOf2_32(v))       { Imm = Log2_32(v); return 3; }
+    if (isPowerOf2_32(-v))      { Imm = Log2_32(-v); return 3; }
     if (v <= -2 || v >= 2) { return 4; }
     break;
   case ISD::UDIV:
@@ -807,7 +831,7 @@ struct mu {
 static struct ms magic(int d) {
   int p;
   unsigned int ad, anc, delta, q1, r1, q2, r2, t;
-  const unsigned int two31 = 2147483648U; // 2^31
+  const unsigned int two31 = 0x80000000U;
   struct ms mag;
 
   ad = abs(d);
index 5d48e620e356eca4b493253ad2d2324a36e6558f..fd03641786be1f192d3d06cd2054246186ba626d 100644 (file)
@@ -2306,7 +2306,6 @@ CreateMulConstInstruction(const TargetMachine &target, Function* F,
                                                    constOp->getType(),
                                                    isValidConst);
     if (isValidConst) {
-      unsigned pow;
       bool needNeg = false;
       if (C < 0) {
         needNeg = true;
@@ -2323,7 +2322,8 @@ CreateMulConstInstruction(const TargetMachine &target, Function* F,
         else
           M = BuildMI(V9::ADDr,3).addReg(lval).addMReg(Zero).addRegDef(destVal);
         mvec.push_back(M);
-      } else if (isPowerOf2(C, pow)) {
+      } else if (isPowerOf2_64(C)) {
+        unsigned pow = Log2_64(C);
         if(!needNeg) {
         unsigned opSize = target.getTargetData().getTypeSize(resultType);
         MachineOpCode opCode = (opSize <= 32)? V9::SLLr5 : V9::SLLXr6;
@@ -2464,7 +2464,6 @@ static void CreateDivConstInstruction(TargetMachine &target,
   const Type* resultType = instrNode->getInstruction()->getType();
 
   if (resultType->isInteger()) {
-    unsigned pow;
     bool isValidConst;
     int64_t C = (int64_t) ConvertConstantToIntType(target, constOp,
                                                    constOp->getType(),
@@ -2479,7 +2478,8 @@ static void CreateDivConstInstruction(TargetMachine &target,
       if (C == 1) {
         mvec.push_back(BuildMI(V9::ADDr, 3).addReg(LHS).addMReg(ZeroReg)
                        .addRegDef(destVal));
-      } else if (isPowerOf2(C, pow)) {
+      } else if (isPowerOf2_64(C)) {
+        unsigned pow = Log2_64(C);
         unsigned opCode;
         Value* shiftOperand;
         unsigned opSize = target.getTargetData().getTypeSize(resultType);
@@ -2539,7 +2539,7 @@ static void CreateDivConstInstruction(TargetMachine &target,
                        .addRegDef(destVal));
       }
 
-      if (needNeg && (C == 1 || isPowerOf2(C, pow))) {
+      if (needNeg && (C == 1 || isPowerOf2_64(C))) {
         // insert <reg = SUB 0, reg> after the instr to flip the sign
         mvec.push_back(CreateIntNegInstruction(target, destVal));
       }
index 3c71fdc3e0e95535738c0bc85d91c0659688de3e..75e76fe18605989cebcc9e4bd40a3c4ba6b4a918 100644 (file)
@@ -229,7 +229,7 @@ unsigned char TargetData::getTypeAlignment(const Type *Ty) const {
 unsigned char TargetData::getTypeAlignmentShift(const Type *Ty) const {
   unsigned Align = getTypeAlignment(Ty);
   assert(!(Align & (Align-1)) && "Alignment is not a power of two!");
-  return log2(Align);
+  return Log2_32(Align);
 }
 
 /// getIntPtrType - Return an unsigned integer type that is the same size or
index 7a06f056b1ee134ebf3e1b71316dfff12def4c9c..41bd222e110996cc3ab595adb3327d6502a01e5e 100644 (file)
@@ -3023,7 +3023,7 @@ unsigned ISel::SelectExpr(SDOperand N) {
           RHS = -RHS;
         }
         if (RHS && (RHS & (RHS-1)) == 0) {   // Signed division by power of 2?
-          unsigned Log = log2(RHS);
+          unsigned Log = Log2_32(RHS);
           unsigned SAROpc, SHROpc, ADDOpc, NEGOpc;
           switch (N.getValueType()) {
           default: assert("Unknown type to signed divide!");
index d844b3634bce7ba41e92ecef728462cb0c4d7eaf..80cfb2b4c190ca7aa0c2280702952f95dfd13369 100644 (file)
@@ -29,6 +29,7 @@
 #include "llvm/Target/TargetOptions.h"
 #include "llvm/Support/GetElementPtrTypeIterator.h"
 #include "llvm/Support/InstVisitor.h"
+#include "llvm/Support/MathExtras.h"
 #include "llvm/ADT/Statistic.h"
 using namespace llvm;
 
@@ -2496,19 +2497,6 @@ void X86ISel::doMultiply(MachineBasicBlock *MBB,
   }
 }
 
-// ExactLog2 - This function solves for (Val == 1 << (N-1)) and returns N.  It
-// returns zero when the input is not exactly a power of two.
-static unsigned ExactLog2(unsigned Val) {
-  if (Val == 0 || (Val & (Val-1))) return 0;
-  unsigned Count = 0;
-  while (Val != 1) {
-    Val >>= 1;
-    ++Count;
-  }
-  return Count+1;
-}
-
-
 /// doMultiplyConst - This function is specialized to efficiently codegen an 8,
 /// 16, or 32-bit integer multiply by a constant.
 void X86ISel::doMultiplyConst(MachineBasicBlock *MBB,
@@ -2573,35 +2561,37 @@ void X86ISel::doMultiplyConst(MachineBasicBlock *MBB,
   }
 
   // If the element size is exactly a power of 2, use a shift to get it.
-  if (unsigned Shift = ExactLog2(ConstRHS)) {
+  if (isPowerOf2_32(ConstRHS)) {
+    unsigned Shift = Log2_32(ConstRHS);
     switch (Class) {
     default: assert(0 && "Unknown class for this function!");
     case cByte:
-      BuildMI(*MBB, IP, X86::SHL8ri,2, DestReg).addReg(op0Reg).addImm(Shift-1);
+      BuildMI(*MBB, IP, X86::SHL8ri,2, DestReg).addReg(op0Reg).addImm(Shift);
       return;
     case cShort:
-      BuildMI(*MBB, IP, X86::SHL16ri,2, DestReg).addReg(op0Reg).addImm(Shift-1);
+      BuildMI(*MBB, IP, X86::SHL16ri,2, DestReg).addReg(op0Reg).addImm(Shift);
       return;
     case cInt:
-      BuildMI(*MBB, IP, X86::SHL32ri,2, DestReg).addReg(op0Reg).addImm(Shift-1);
+      BuildMI(*MBB, IP, X86::SHL32ri,2, DestReg).addReg(op0Reg).addImm(Shift);
       return;
     }
   }
 
   // If the element size is a negative power of 2, use a shift/neg to get it.
-  if (unsigned Shift = ExactLog2(-ConstRHS)) {
+  if (isPowerOf2_32(-ConstRHS)) {
+    unsigned Shift = Log2_32(-ConstRHS);
     TmpReg = makeAnotherReg(DestTy);
     BuildMI(*MBB, IP, NEGrTab[Class], 1, TmpReg).addReg(op0Reg);
     switch (Class) {
     default: assert(0 && "Unknown class for this function!");
     case cByte:
-      BuildMI(*MBB, IP, X86::SHL8ri,2, DestReg).addReg(TmpReg).addImm(Shift-1);
+      BuildMI(*MBB, IP, X86::SHL8ri,2, DestReg).addReg(TmpReg).addImm(Shift);
       return;
     case cShort:
-      BuildMI(*MBB, IP, X86::SHL16ri,2, DestReg).addReg(TmpReg).addImm(Shift-1);
+      BuildMI(*MBB, IP, X86::SHL16ri,2, DestReg).addReg(TmpReg).addImm(Shift);
       return;
     case cInt:
-      BuildMI(*MBB, IP, X86::SHL32ri,2, DestReg).addReg(TmpReg).addImm(Shift-1);
+      BuildMI(*MBB, IP, X86::SHL32ri,2, DestReg).addReg(TmpReg).addImm(Shift);
       return;
     }
   }
@@ -2917,7 +2907,8 @@ void X86ISel::emitDivRemOperation(MachineBasicBlock *BB,
         V = -V;
         isNeg = true;      // Maybe it's a negative power of 2.
       }
-      if (unsigned Log = ExactLog2(V)) {
+      if (isPowerOf2_32(V)) {
+        unsigned Log = Log2_32(V);
         --Log;
         unsigned Op0Reg = getReg(Op0, BB, IP);
         unsigned TmpReg = makeAnotherReg(Op0->getType());