GlobalISel: Add computeKnownBitsForTargetInstr

[arsenm]

Summary

I think we can save the MRI argument from these since it's in
GISelKnownBits already, but currently not accessible.

Implementation deferred to avoid dependency on other patches.

[arsenm]

ping

[dsanders]

llvm/lib/CodeGen/GlobalISel/GISelKnownBits.cpp

472

This TODO hasn't quite been handled. It's also intended to cover the case where you have target specific instructions (e.g. AArch64::ADDWrr), pseudo-instructions, or target-specific generic opcodes.

To cover this case we also need to call TL.computeNumSignBitsForTargetInstr() for the default: case

481

FirstAnswer is 1 so this if-statement is already inside the std::max

482

Why update a variable that and return that rather than just returning the answer as per the other code paths?

[arsenm]

llvm/lib/CodeGen/GlobalISel/GISelKnownBits.cpp

472

This is called in the default case

482

This is following the structure of the DAG implementation for eventually plugging in the default handling with computeKnownBits

[arsenm]

Handle the fallback to computeKnownBits, copied directly from the DAG version. This should really get a test, but I don't think there's any operation that is implemented that should hit this path

[foad]

llvm/lib/CodeGen/GlobalISel/GISelKnownBits.cpp

500–507

I've simplified the SelectionDAG version of this code a bit in 7cdbf1ed4b94259a3aad2a7575e928fa61b0e57e.

[dsanders]

LGTM after syncing up with @foad's change to use countLeadingOnes() in DAGISel

llvm/lib/CodeGen/GlobalISel/GISelKnownBits.cpp

482

Ok, that makes sense

[arsenm]

aa63eb6a461dcfd9cd3f1c09de36e75e8394634f

llvm/include/llvm/CodeGen/GlobalISel/GISelKnownBits.h

virtual void computeKnownBitsImpl(Register R, KnownBits &Known,
                                     unsigned Depth = 0);
 
   unsigned computeNumSignBits(Register R, const APInt &DemandedElts,
                               unsigned Depth = 0);
   unsigned computeNumSignBits(Register R, unsigned Depth = 0);
 
   // KnownBitsAPI
   KnownBits getKnownBits(Register R);
+  KnownBits getKnownBits(Register R, const APInt &DemandedElts,
+                         unsigned Depth = 0);
+
   // Calls getKnownBits for first operand def of MI.
   KnownBits getKnownBits(MachineInstr &MI);
   APInt getKnownZeroes(Register R);
   APInt getKnownOnes(Register R);
 
   /// \return true if 'V & Mask' is known to be zero in DemandedElts. We use
   /// this predicate to simplify operations downstream.
   /// Mask is known to be zero for bits that V cannot have.

llvm/include/llvm/CodeGen/TargetLowering.h

public:
   /// information about sign bits to the DAG Combiner. The DemandedElts
   /// argument allows us to only collect the minimum sign bits that are shared
   /// by the requested vector elements.
   virtual unsigned ComputeNumSignBitsForTargetNode(SDValue Op,
                                                    const APInt &DemandedElts,
                                                    const SelectionDAG &DAG,
                                                    unsigned Depth = 0) const;
 
+  /// This method can be implemented by targets that want to expose additional
+  /// information about sign bits to GlobalISel combiners. The DemandedElts
+  /// argument allows us to only collect the minimum sign bits that are shared
+  /// by the requested vector elements.
+  virtual unsigned computeNumSignBitsForTargetInstr(GISelKnownBits &Analysis,
+                                                    Register R,
+                                                    const APInt &DemandedElts,
+                                                    const MachineRegisterInfo &MRI,
+                                                    unsigned Depth = 0) const;
+
   /// Attempt to simplify any target nodes based on the demanded vector
   /// elements, returning true on success. Otherwise, analyze the expression and
   /// return a mask of KnownUndef and KnownZero elements for the expression
   /// (used to simplify the caller). The KnownUndef/Zero elements may only be
   /// accurate for those bits in the DemandedMask.
   virtual bool SimplifyDemandedVectorEltsForTargetNode(
       SDValue Op, const APInt &DemandedElts, APInt &KnownUndef,
       APInt &KnownZero, TargetLoweringOpt &TLO, unsigned Depth = 0) const;

llvm/lib/CodeGen/GlobalISel/GISelKnownBits.cpp

if (Alignment)
     Known.Zero.setLowBits(Log2(Alignment));
 }
 
 KnownBits GISelKnownBits::getKnownBits(MachineInstr &MI) {
   return getKnownBits(MI.getOperand(0).getReg());
 }
 
 KnownBits GISelKnownBits::getKnownBits(Register R) {
-  KnownBits Known;
-  LLT Ty = MRI.getType(R);
+  const LLT Ty = MRI.getType(R);
   APInt DemandedElts =
       Ty.isVector() ? APInt::getAllOnesValue(Ty.getNumElements()) : APInt(1, 1);
+  return getKnownBits(R, DemandedElts);
+}
+
+KnownBits GISelKnownBits::getKnownBits(Register R, const APInt &DemandedElts,
+                                       unsigned Depth) {
   // For now, we only maintain the cache during one request.
   assert(ComputeKnownBitsCache.empty() && "Cache should have been cleared");
+
+  KnownBits Known;
   computeKnownBitsImpl(R, Known, DemandedElts);
   ComputeKnownBitsCache.clear();
   return Known;
 }
 
 bool GISelKnownBits::signBitIsZero(Register R) {
   LLT Ty = MRI.getType(R);
   unsigned BitWidth = Ty.getScalarSizeInBits();
unsigned GISelKnownBits::computeNumSignBits(Register R,
 
   if (Depth == getMaxDepth())
     return 1;
 
   if (!DemandedElts)
     return 1; // No demanded elts, better to assume we don't know anything.
 
   LLT DstTy = MRI.getType(R);
+  const unsigned TyBits = DstTy.getScalarSizeInBits();
 
   // Handle the case where this is called on a register that does not have a
   // type constraint. This is unlikely to occur except by looking through copies
   // but it is possible for the initial register being queried to be in this
   // state.
   if (!DstTy.isValid())
     return 1;
 
+  unsigned FirstAnswer = 1;
   switch (Opcode) {
   case TargetOpcode::COPY: {
     MachineOperand &Src = MI.getOperand(1);
     if (Src.getReg().isVirtual() && Src.getSubReg() == 0 &&
         MRI.getType(Src.getReg()).isValid()) {
       // Don't increment Depth for this one since we didn't do any work.
       return computeNumSignBits(Src.getReg(), DemandedElts, Depth);
     }
case TargetOpcode::G_TRUNC: {
     // Check if the sign bits of source go down as far as the truncated value.
     unsigned DstTyBits = DstTy.getScalarSizeInBits();
     unsigned NumSrcBits = SrcTy.getScalarSizeInBits();
     unsigned NumSrcSignBits = computeNumSignBits(Src, DemandedElts, Depth + 1);
     if (NumSrcSignBits > (NumSrcBits - DstTyBits))
       return NumSrcSignBits - (NumSrcBits - DstTyBits);
     break;
   }
-  default:
+  case TargetOpcode::G_INTRINSIC:
+  case TargetOpcode::G_INTRINSIC_W_SIDE_EFFECTS:
+  default: {
+    unsigned NumBits =
+      TL.computeNumSignBitsForTargetInstr(*this, R, DemandedElts, MRI, Depth);
+    if (NumBits > 1)
+      FirstAnswer = std::max(FirstAnswer, NumBits);
     break;
   }
+  }
 
-  // TODO: Handle target instructions
-  // TODO: Fall back to known bits
-  return 1;
+  // Finally, if we can prove that the top bits of the result are 0's or 1's,
+  // use this information.
+  KnownBits Known = getKnownBits(R, DemandedElts, Depth);
+  APInt Mask;
+  if (Known.isNonNegative()) {        // sign bit is 0
+    Mask = Known.Zero;
+  } else if (Known.isNegative()) {  // sign bit is 1;
+    Mask = Known.One;
+  } else {
+    // Nothing known.
+    return FirstAnswer;
+  }
+
+  // Okay, we know that the sign bit in Mask is set.  Use CLZ to determine
+  // the number of identical bits in the top of the input value.
+  Mask = ~Mask;
+  Mask <<= Mask.getBitWidth() - TyBits;
+
+  // Return # leading zeros.  We use 'min' here in case Val was zero before
+  // shifting.  We don't want to return '64' as for an i32 "0".
+  return std::max(FirstAnswer, std::min(TyBits, Mask.countLeadingZeros()));
 }
 
 unsigned GISelKnownBits::computeNumSignBits(Register R, unsigned Depth) {
   LLT Ty = MRI.getType(R);
   APInt DemandedElts = Ty.isVector()
                            ? APInt::getAllOnesValue(Ty.getNumElements())
                            : APInt(1, 1);
   return computeNumSignBits(R, DemandedElts, Depth);

llvm/lib/CodeGen/SelectionDAG/TargetLowering.cpp

assert((Op.getOpcode() >= ISD::BUILTIN_OP_END ||
           Op.getOpcode() == ISD::INTRINSIC_WO_CHAIN ||
           Op.getOpcode() == ISD::INTRINSIC_W_CHAIN ||
           Op.getOpcode() == ISD::INTRINSIC_VOID) &&
          "Should use ComputeNumSignBits if you don't know whether Op"
          " is a target node!");
   return 1;
 }
 
+unsigned TargetLowering::computeNumSignBitsForTargetInstr(
+  GISelKnownBits &Analysis, Register R, const APInt &DemandedElts,
+  const MachineRegisterInfo &MRI, unsigned Depth) const {
+  return 1;
+}
+
 bool TargetLowering::SimplifyDemandedVectorEltsForTargetNode(
     SDValue Op, const APInt &DemandedElts, APInt &KnownUndef, APInt &KnownZero,
     TargetLoweringOpt &TLO, unsigned Depth) const {
   assert((Op.getOpcode() >= ISD::BUILTIN_OP_END ||
           Op.getOpcode() == ISD::INTRINSIC_WO_CHAIN ||
           Op.getOpcode() == ISD::INTRINSIC_W_CHAIN ||
           Op.getOpcode() == ISD::INTRINSIC_VOID) &&
          "Should use SimplifyDemandedVectorElts if you don't know whether Op"