GlobalISel: ComputeNumSignBits from load range metadata

[arsenm]

Summary

We're missing SimplifyDemandedBits styles of optimizations,
so one case differs from the DAG from not trimming the constant.
The other case is an optimization we get that the DAG doesn't do to
split the 64-bit shift.

[paquette]

LGTM

[arsenm]

llvm/lib/CodeGen/GlobalISel/GISelKnownBits.cpp

722

Probably should still factor this in

[foad]

llvm/lib/CodeGen/GlobalISel/GISelKnownBits.cpp

609

Needs a comment, and possibly a better name, since this is not just looking at the range metadata, it is also handling different kinds of load opcode.

630

How could we hit this?

722

If you can rely on MMO->getSizeInBits() == CR.getBitWidth() then computeNumSignBitsFromRangeMetadata has already done this.

[arsenm]

llvm/lib/CodeGen/GlobalISel/GISelKnownBits.cpp

630

The anyextload case (or if the metadata was on a casted to vector result type)

[arsenm]

Add comment

[aemerson]

llvm/lib/CodeGen/GlobalISel/GISelKnownBits.cpp

706–707

This can now be return TyBits - Ld->getMemSizeInBits() + 1;

721–722

ditto

[arsenm]

Use getMemSizeInBits

[foad]

llvm/lib/CodeGen/GlobalISel/GISelKnownBits.cpp

630

I don't understand the "casted to vector" case - is there a test case for that?

633

Can this just go in the default case above?

689

What exactly is this check for?

[arsenm]

llvm/lib/CodeGen/GlobalISel/GISelKnownBits.cpp

630

It's the case where every load is legalized to an s32 (which I'd like to stop doing eventually). Apparently it's not reachable in the globalisel version since we don't handle the extract_vector_elt look through yet

633

This was to defend against the vector case, TyBits is the scalar size

689

You're only looking for element 0 if it's a vector result type

[arsenm]

Add mir test (although kind of pointless, we can't hit this case here yet). Also copy the endianness check from the DAG version

llvm/include/llvm/CodeGen/GlobalISel/GenericMachineInstrs.h

 };
 
 /// Represents any generic load, including sign/zero extending variants.
 class GAnyLoad : public GLoadStore {
 public:
   /// Get the definition register of the loaded value.
   Register getDstReg() const { return getOperand(0).getReg(); }
 
+  /// Returns the Ranges that describes the dereference.
+  const MDNode *getRanges() const {
+    return getMMO().getRanges();
+  }
+
   static bool classof(const MachineInstr *MI) {
     switch (MI->getOpcode()) {
     case TargetOpcode::G_LOAD:
     case TargetOpcode::G_ZEXTLOAD:
     case TargetOpcode::G_SEXTLOAD:
       return true;
     default:
       return false;

llvm/lib/CodeGen/GlobalISel/GISelKnownBits.cpp

 //===- lib/CodeGen/GlobalISel/GISelKnownBits.cpp --------------*- C++ *-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 /// Provides analysis for querying information about KnownBits during GISel
 /// passes.
 //
 //===----------------------------------------------------------------------===//
 #include "llvm/CodeGen/GlobalISel/GISelKnownBits.h"
 #include "llvm/Analysis/ValueTracking.h"
+#include "llvm/CodeGen/GlobalISel/GenericMachineInstrs.h"
 #include "llvm/CodeGen/GlobalISel/Utils.h"
 #include "llvm/CodeGen/MachineFrameInfo.h"
 #include "llvm/CodeGen/MachineRegisterInfo.h"
 #include "llvm/CodeGen/TargetLowering.h"
 #include "llvm/CodeGen/TargetOpcodes.h"
+#include "llvm/IR/ConstantRange.h"
 #include "llvm/IR/Module.h"
 
 #define DEBUG_TYPE "gisel-known-bits"
 
 using namespace llvm;
 
 char llvm::GISelKnownBitsAnalysis::ID = 0;
 
unsigned GISelKnownBits::computeNumSignBitsMin(Register Src0, Register Src1,
                                                unsigned Depth) {
   // Test src1 first, since we canonicalize simpler expressions to the RHS.
   unsigned Src1SignBits = computeNumSignBits(Src1, DemandedElts, Depth);
   if (Src1SignBits == 1)
     return 1;
   return std::min(computeNumSignBits(Src0, DemandedElts, Depth), Src1SignBits);
 }
 
+static unsigned computeNumSignBitsFromRangeMetadata(const GAnyLoad *Ld,
+                                                    unsigned TyBits) {
+  const MDNode *Ranges = Ld->getRanges();
+  if (!Ranges)
+    return 1;
+
+  ConstantRange CR = getConstantRangeFromMetadata(*Ranges);
+  if (TyBits > CR.getBitWidth()) {
+    switch (Ld->getOpcode()) {
+    case TargetOpcode::G_SEXTLOAD:
+      CR = CR.signExtend(TyBits);
+      break;
+    case TargetOpcode::G_ZEXTLOAD:
+      CR = CR.zeroExtend(TyBits);
+      break;
+    default:
+      break;
+    }
+  }
+
+  if (TyBits != CR.getBitWidth())
+    return 1;
+
+  return std::min(CR.getSignedMin().getNumSignBits(),
+                  CR.getSignedMax().getNumSignBits());
+}
+
 unsigned GISelKnownBits::computeNumSignBits(Register R,
                                             const APInt &DemandedElts,
                                             unsigned Depth) {
   MachineInstr &MI = *MRI.getVRegDef(R);
   unsigned Opcode = MI.getOpcode();
 
   if (Opcode == TargetOpcode::G_CONSTANT)
     return MI.getOperand(1).getCImm()->getValue().getNumSignBits();
unsigned GISelKnownBits::computeNumSignBits(Register R,
   case TargetOpcode::G_ASSERT_SEXT:
   case TargetOpcode::G_SEXT_INREG: {
     // Max of the input and what this extends.
     Register Src = MI.getOperand(1).getReg();
     unsigned SrcBits = MI.getOperand(2).getImm();
     unsigned InRegBits = TyBits - SrcBits + 1;
     return std::max(computeNumSignBits(Src, DemandedElts, Depth + 1), InRegBits);
   }
+  case TargetOpcode::G_LOAD: {
+    GLoad *Ld = cast<GLoad>(&MI);
+    if (DemandedElts != 1)
+      break;
+
+    return computeNumSignBitsFromRangeMetadata(Ld, TyBits);
+  }
   case TargetOpcode::G_SEXTLOAD: {
+    GSExtLoad *Ld = cast<GSExtLoad>(&MI);
+
     // FIXME: We need an in-memory type representation.
     if (DstTy.isVector())
       return 1;
 
+    unsigned NumBits = computeNumSignBitsFromRangeMetadata(Ld, TyBits);
+    if (NumBits != 1)
+      return NumBits;
+
     // e.g. i16->i32 = '17' bits known.
     const MachineMemOperand *MMO = *MI.memoperands_begin();
     return TyBits - MMO->getSizeInBits() + 1;
   }
   case TargetOpcode::G_ZEXTLOAD: {
+    GZExtLoad *Ld = cast<GZExtLoad>(&MI);
+
     // FIXME: We need an in-memory type representation.
     if (DstTy.isVector())
       return 1;
 
+    unsigned NumBits = computeNumSignBitsFromRangeMetadata(Ld, TyBits);
+    if (NumBits != 1)
+      return NumBits;
+
     // e.g. i16->i32 = '16' bits known.
     const MachineMemOperand *MMO = *MI.memoperands_begin();
     return TyBits - MMO->getSizeInBits();
   }
   case TargetOpcode::G_TRUNC: {
     Register Src = MI.getOperand(1).getReg();
     LLT SrcTy = MRI.getType(Src);
 
     // Check if the sign bits of source go down as far as the truncated value.
     unsigned DstTyBits = DstTy.getScalarSizeInBits();
     unsigned NumSrcBits = SrcTy.getScalarSizeInBits();

llvm/test/CodeGen/AMDGPU/load-range-metadata-sign-bits.ll

 ; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
-; RUN: llc -mtriple=amdgcn-amd-amdhsa -mcpu=gfx900 -verify-machineinstrs < %s | FileCheck -enable-var-scope -check-prefix=GCN %s
+; RUN: llc -global-isel=0 -mtriple=amdgcn-amd-amdhsa -mcpu=gfx900 -verify-machineinstrs < %s | FileCheck -enable-var-scope -check-prefixes=GCN,SDAG %s
+; RUN: llc -global-isel=1 -mtriple=amdgcn-amd-amdhsa -mcpu=gfx900 -verify-machineinstrs < %s | FileCheck -enable-var-scope -check-prefixes=GCN,GISEL %s
+
 
 define i32 @range_metadata_sext_i8_signed_range_i32(ptr addrspace(1) %ptr) {
 ; GCN-LABEL: range_metadata_sext_i8_signed_range_i32:
 ; GCN:       ; %bb.0:
 ; GCN-NEXT:    s_waitcnt vmcnt(0) expcnt(0) lgkmcnt(0)
 ; GCN-NEXT:    global_load_dword v0, v[0:1], off glc
 ; GCN-NEXT:    s_waitcnt vmcnt(0)
 ; GCN-NEXT:    s_setpc_b64 s[30:31]

 ; GCN-NEXT:    s_setpc_b64 s[30:31]
   %val = load volatile i32, ptr addrspace(1) %ptr, align 4, !range !2 ; [-255, 128)
   %shl = shl i32 %val, 24
   %ashr = ashr i32 %shl, 24
   ret i32 %ashr
 }
 
 define i32 @range_metadata_sext_i8_neg_neg_range_i32(ptr addrspace(1) %ptr) {
-; GCN-LABEL: range_metadata_sext_i8_neg_neg_range_i32:
-; GCN:       ; %bb.0:
-; GCN-NEXT:    s_waitcnt vmcnt(0) expcnt(0) lgkmcnt(0)
-; GCN-NEXT:    global_load_dword v0, v[0:1], off glc
-; GCN-NEXT:    s_waitcnt vmcnt(0)
-; GCN-NEXT:    v_and_b32_e32 v0, 63, v0
-; GCN-NEXT:    s_setpc_b64 s[30:31]
+; SDAG-LABEL: range_metadata_sext_i8_neg_neg_range_i32:
+; SDAG:       ; %bb.0:
+; SDAG-NEXT:    s_waitcnt vmcnt(0) expcnt(0) lgkmcnt(0)
+; SDAG-NEXT:    global_load_dword v0, v[0:1], off glc
+; SDAG-NEXT:    s_waitcnt vmcnt(0)
+; SDAG-NEXT:    v_and_b32_e32 v0, 63, v0
+; SDAG-NEXT:    s_setpc_b64 s[30:31]
+;
+; GISEL-LABEL: range_metadata_sext_i8_neg_neg_range_i32:
+; GISEL:       ; %bb.0:
+; GISEL-NEXT:    s_waitcnt vmcnt(0) expcnt(0) lgkmcnt(0)
+; GISEL-NEXT:    global_load_dword v0, v[0:1], off glc
+; GISEL-NEXT:    s_waitcnt vmcnt(0)
+; GISEL-NEXT:    v_and_b32_e32 v0, 0x7f, v0
+; GISEL-NEXT:    s_setpc_b64 s[30:31]
   %val = load volatile i32, ptr addrspace(1) %ptr, align 4, !range !3
   %shl = shl i32 %val, 25
   %ashr = ashr i32 %shl, 25
   ret i32 %ashr
 }
 
 define i32 @range_metadata_sextload_i8_signed_range_i4_i32(ptr addrspace(1) %ptr) {
 ; GCN-LABEL: range_metadata_sextload_i8_signed_range_i4_i32:

 ; GCN-NEXT:    s_setpc_b64 s[30:31]
   %val = load volatile i32, ptr addrspace(1) %ptr, align 4, !range !6
   %shl = shl i32 %val, 31
   %ashr = ashr i32 %shl, 31
   ret i32 %ashr
 }
 
 define i64 @range_metadata_sext_i8_signed_range_i64(ptr addrspace(1) %ptr) {
-; GCN-LABEL: range_metadata_sext_i8_signed_range_i64:
-; GCN:       ; %bb.0:
-; GCN-NEXT:    s_waitcnt vmcnt(0) expcnt(0) lgkmcnt(0)
-; GCN-NEXT:    global_load_dwordx2 v[0:1], v[0:1], off glc
-; GCN-NEXT:    s_waitcnt vmcnt(0)
-; GCN-NEXT:    v_lshlrev_b32_e32 v1, 23, v0
-; GCN-NEXT:    v_ashrrev_i64 v[0:1], 55, v[0:1]
-; GCN-NEXT:    s_setpc_b64 s[30:31]
+; SDAG-LABEL: range_metadata_sext_i8_signed_range_i64:
+; SDAG:       ; %bb.0:
+; SDAG-NEXT:    s_waitcnt vmcnt(0) expcnt(0) lgkmcnt(0)
+; SDAG-NEXT:    global_load_dwordx2 v[0:1], v[0:1], off glc
+; SDAG-NEXT:    s_waitcnt vmcnt(0)
+; SDAG-NEXT:    v_lshlrev_b32_e32 v1, 23, v0
+; SDAG-NEXT:    v_ashrrev_i64 v[0:1], 55, v[0:1]
+; SDAG-NEXT:    s_setpc_b64 s[30:31]
+;
+; GISEL-LABEL: range_metadata_sext_i8_signed_range_i64:
+; GISEL:       ; %bb.0:
+; GISEL-NEXT:    s_waitcnt vmcnt(0) expcnt(0) lgkmcnt(0)
+; GISEL-NEXT:    global_load_dwordx2 v[0:1], v[0:1], off glc
+; GISEL-NEXT:    s_waitcnt vmcnt(0)
+; GISEL-NEXT:    v_bfe_i32 v0, v0, 0, 9
+; GISEL-NEXT:    v_ashrrev_i32_e32 v1, 31, v0
+; GISEL-NEXT:    s_setpc_b64 s[30:31]
   %val = load volatile i64, ptr addrspace(1) %ptr, align 4, !range !7
   %shl = shl i64 %val, 55
   %ashr = ashr i64 %shl, 55
   ret i64 %ashr
 }
 
 define i64 @range_metadata_sext_i32_signed_range_i64(ptr addrspace(1) %ptr) {
 ; GCN-LABEL: range_metadata_sext_i32_signed_range_i64: