[SelectionDAG] Store LeadingZero count in LiveOutInfo instead of KnownBits.

[craig.topper]

Summary

Previously we stored two APInts for KnownBits. This information is
only ever used to create AssertZExts using the number of known
leading zeros. It's inefficient to store this information in APInt
form.

This patch switches the storage to store the number of leading zeros.

I've also removed the IsValid flag and now rely on default constructing
with the safest values and reseting to the safe values when we need
to invalidate. The IsValid flag was inconsistently used before.
We could default construct entries in LiveRegOut with IsValid=true and
BitWidth=1 instead of default constructing as IsValid=false.

[RKSimon]

How useful would it be to flip this - and generate some kind of ISD::AssertKnownBits node instead of ISD::AssertZext ?

[craig.topper]

In D122194#3399209, @RKSimon wrote:

How useful would it be to flip this - and generate some kind of ISD::AssertKnownBits node instead of ISD::AssertZext ?

I'm not sure. One case I do want to look at is trailing zeros for the reccurrence case that shows up in loop unrolling.

loop:
   X = phi [0, preheader], [X.increment, loop]
   ...
   or X, 1
   ...
   or X, 2
   ...
   or X, 3
   ...
   X.increment = add X, 4
   ...
   br loop

X has 2 trailing zero bits so the ORs can be converted back to ADDs.

Adding a trailing zeros field is a straightforward extension to this patch and is still less storage than the 2 APInts. I think we might be able to reuse the AssertAlign node for it.

[RKSimon]

Alignment, one bit and known negative values would all be nice to have - I'm just not sure if they'd make a huge difference.

[craig.topper]

In D122194#3399974, @RKSimon wrote:

Alignment, one bit and known negative values would all be nice to have - I'm just not sure if they'd make a huge difference.

For "one bit" would we have to call isKnownToBeAPowerOfTwo in addition to computeKnownBits?

[RKSimon]

In D122194#3399998, @craig.topper wrote:

In D122194#3399974, @RKSimon wrote:

Alignment, one bit and known negative values would all be nice to have - I'm just not sure if they'd make a huge difference.

For "one bit" would we have to call isKnownToBeAPowerOfTwo in addition to computeKnownBits?

one bit I meant KnownBits::countMaxPopulation() == 1 (i.e. all but one bit is known zero - it might be pow2 or zero)

[RKSimon]

Something else that we might benefit from is if we can tag when a live out value is known never to be poison/undef - I guess we can do that by adding a freeze.

[craig.topper]

In D122194#3399999, @RKSimon wrote:

In D122194#3399998, @craig.topper wrote:

In D122194#3399974, @RKSimon wrote:

Alignment, one bit and known negative values would all be nice to have - I'm just not sure if they'd make a huge difference.

For "one bit" would we have to call isKnownToBeAPowerOfTwo in addition to computeKnownBits?

one bit I meant KnownBits::countMaxPopulation() == 1 (i.e. all but one bit is known zero - it might be pow2 or zero)

Having both leading and trailing zeros and their sum being 1 less than the bitwidth would cover this right?

Any objection to this patch? Or do we think we need a fully general cross basic block known bits that we will hook up through something more than AssertZExt someday soon?

[RKSimon]

I have been meaning to investigate adding a general AssertKnownBits DAG node, but haven't done anything on this yet.

Is your main concern about saving memory in LiveOutInfo classes?

[craig.topper]

In D122194#3491983, @RKSimon wrote:

I have been meaning to investigate adding a general AssertKnownBits DAG node, but haven't done anything on this yet.

Is your main concern about saving memory in LiveOutInfo classes?

It saves memory. I think this simplifies how we keep track of this data being valid. We did an odd thing with a single bit KnownBits value before. See the code on line 422 of FunctionLoweringInfo::GetLiveOutRegInfo.

My original motivation was to try to solve the or_is_add problem on phi recurrences in unrolled loops. Those typically are trailing bits related where the phi has an aligned constant start value(usually 0), and that is incremented by an aligned constant. I was going to use matchSimpleRecurrence to detect that pattern in FunctionLoweringInfo's PHI handling then use that information to mark trailing zeros and add an AssertAlign. By explicitly storing trailing zeros and leading zeros separately instead of KnownBits I could restrict exactly when the AssertAlign would be inserted to only the phi case. Just inserting an AssertAlign based on the KnownBits we have now starts breaking lit tests. I haven't looked at it since March.

llvm/include/llvm/CodeGen/FunctionLoweringInfo.h

 //===- FunctionLoweringInfo.h - Lower functions from LLVM IR ---*- 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
 //
 //===----------------------------------------------------------------------===//
 //

 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/CodeGen/ISDOpcodes.h"
 #include "llvm/CodeGen/MachineBasicBlock.h"
 #include "llvm/CodeGen/TargetRegisterInfo.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/Type.h"
 #include "llvm/IR/Value.h"
-#include "llvm/Support/KnownBits.h"
 #include <cassert>
 #include <utility>
 #include <vector>
 
 namespace llvm {
 
 class Argument;
 class BasicBlock;
public:
 
   /// MBB - The current block.
   MachineBasicBlock *MBB;
 
   /// MBB - The current insert position inside the current block.
   MachineBasicBlock::iterator InsertPt;
 
   struct LiveOutInfo {
-    unsigned NumSignBits : 31;
-    unsigned IsValid : 1;
-    KnownBits Known = 1;
+    unsigned NumSignBits;
+    unsigned LeadingZeros;
 
-    LiveOutInfo() : NumSignBits(0), IsValid(true) {}
+    LiveOutInfo() : NumSignBits(1), LeadingZeros(0) {}
+
+    void reset() {
+      NumSignBits = 1;
+      LeadingZeros = 0;
+    }
   };
 
   /// Record the preferred extend type (ISD::SIGN_EXTEND or ISD::ZERO_EXTEND)
   /// for a value.
   DenseMap<const Value *, ISD::NodeType> PreferredExtendType;
 
   /// VisitedBBs - The set of basic blocks visited thus far by instruction
   /// selection.
public:
 
   /// GetLiveOutRegInfo - Gets LiveOutInfo for a register, returning NULL if the
   /// register is a PHI destination and the PHI's LiveOutInfo is not valid.
   const LiveOutInfo *GetLiveOutRegInfo(Register Reg) {
     if (!LiveOutRegInfo.inBounds(Reg))
       return nullptr;
 
     const LiveOutInfo *LOI = &LiveOutRegInfo[Reg];
-    if (!LOI->IsValid)
-      return nullptr;
-
     return LOI;
   }
 
-  /// GetLiveOutRegInfo - Gets LiveOutInfo for a register, returning NULL if the
-  /// register is a PHI destination and the PHI's LiveOutInfo is not valid. If
-  /// the register's LiveOutInfo is for a smaller bit width, it is extended to
-  /// the larger bit width by zero extension. The bit width must be no smaller
-  /// than the LiveOutInfo's existing bit width.
-  const LiveOutInfo *GetLiveOutRegInfo(Register Reg, unsigned BitWidth);
-
   /// AddLiveOutRegInfo - Adds LiveOutInfo for a register.
   void AddLiveOutRegInfo(Register Reg, unsigned NumSignBits,
-                         const KnownBits &Known) {
+                         unsigned LeadingZeros) {
     // Only install this information if it tells us something.
-    if (NumSignBits == 1 && Known.isUnknown())
+    if (NumSignBits == 1 && LeadingZeros == 0)
       return;
 
     LiveOutRegInfo.grow(Reg);
     LiveOutInfo &LOI = LiveOutRegInfo[Reg];
     LOI.NumSignBits = NumSignBits;
-    LOI.Known.One = Known.One;
-    LOI.Known.Zero = Known.Zero;
+    LOI.LeadingZeros = LeadingZeros;
   }
 
   /// ComputePHILiveOutRegInfo - Compute LiveOutInfo for a PHI's destination
   /// register based on the LiveOutInfo of its operands.
   void ComputePHILiveOutRegInfo(const PHINode*);
 
   /// InvalidatePHILiveOutRegInfo - Invalidates a PHI's LiveOutInfo, to be
   /// called when a block is visited before all of its predecessors.
   void InvalidatePHILiveOutRegInfo(const PHINode *PN) {
     // PHIs with no uses have no ValueMap entry.
     DenseMap<const Value*, Register>::const_iterator It = ValueMap.find(PN);
     if (It == ValueMap.end())
       return;
 
     Register Reg = It->second;
     if (Reg == 0)
       return;
 
     LiveOutRegInfo.grow(Reg);
-    LiveOutRegInfo[Reg].IsValid = false;
+    LiveOutRegInfo[Reg].reset();
   }
 
   /// setArgumentFrameIndex - Record frame index for the byval
   /// argument.
   void setArgumentFrameIndex(const Argument *A, int FI);
 
   /// getArgumentFrameIndex - Get frame index for the byval argument.
   int getArgumentFrameIndex(const Argument *A);

llvm/lib/CodeGen/SelectionDAG/FunctionLoweringInfo.cpp

 //===-- FunctionLoweringInfo.cpp ------------------------------------------===//
 //
 // 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
 //
 //===----------------------------------------------------------------------===//
 //
Register FunctionLoweringInfo::CreateRegs(Type *Ty, bool isDivergent) {
   return FirstReg;
 }
 
 Register FunctionLoweringInfo::CreateRegs(const Value *V) {
   return CreateRegs(V->getType(), DA && DA->isDivergent(V) &&
                     !TLI->requiresUniformRegister(*MF, V));
 }
 
-/// GetLiveOutRegInfo - Gets LiveOutInfo for a register, returning NULL if the
-/// register is a PHI destination and the PHI's LiveOutInfo is not valid. If
-/// the register's LiveOutInfo is for a smaller bit width, it is extended to
-/// the larger bit width by zero extension. The bit width must be no smaller
-/// than the LiveOutInfo's existing bit width.
-const FunctionLoweringInfo::LiveOutInfo *
-FunctionLoweringInfo::GetLiveOutRegInfo(Register Reg, unsigned BitWidth) {
-  if (!LiveOutRegInfo.inBounds(Reg))
-    return nullptr;
-
-  LiveOutInfo *LOI = &LiveOutRegInfo[Reg];
-  if (!LOI->IsValid)
-    return nullptr;
-
-  if (BitWidth > LOI->Known.getBitWidth()) {
-    LOI->NumSignBits = 1;
-    LOI->Known = LOI->Known.anyext(BitWidth);
-  }
-
-  return LOI;
-}
-
 /// ComputePHILiveOutRegInfo - Compute LiveOutInfo for a PHI's destination
 /// register based on the LiveOutInfo of its operands.
 void FunctionLoweringInfo::ComputePHILiveOutRegInfo(const PHINode *PN) {
   Type *Ty = PN->getType();
   if (!Ty->isIntegerTy() || Ty->isVectorTy())
     return;
 
   SmallVector<EVT, 1> ValueVTs;
void FunctionLoweringInfo::ComputePHILiveOutRegInfo(const PHINode *PN) {
   Register DestReg = ValueMap[PN];
   if (!Register::isVirtualRegister(DestReg))
     return;
   LiveOutRegInfo.grow(DestReg);
   LiveOutInfo &DestLOI = LiveOutRegInfo[DestReg];
 
   Value *V = PN->getIncomingValue(0);
   if (isa<UndefValue>(V) || isa<ConstantExpr>(V)) {
-    DestLOI.NumSignBits = 1;
-    DestLOI.Known = KnownBits(BitWidth);
+    DestLOI.reset();
     return;
   }
 
   if (ConstantInt *CI = dyn_cast<ConstantInt>(V)) {
     APInt Val = CI->getValue().zextOrSelf(BitWidth);
     DestLOI.NumSignBits = Val.getNumSignBits();
-    DestLOI.Known = KnownBits::makeConstant(Val);
+    DestLOI.LeadingZeros = Val.countLeadingZeros();
   } else {
     assert(ValueMap.count(V) && "V should have been placed in ValueMap when its"
                                 "CopyToReg node was created.");
     Register SrcReg = ValueMap[V];
     if (!Register::isVirtualRegister(SrcReg)) {
-      DestLOI.IsValid = false;
+      DestLOI.reset();
       return;
     }
-    const LiveOutInfo *SrcLOI = GetLiveOutRegInfo(SrcReg, BitWidth);
+    const LiveOutInfo *SrcLOI = GetLiveOutRegInfo(SrcReg);
     if (!SrcLOI) {
-      DestLOI.IsValid = false;
+      DestLOI.reset();
       return;
     }
     DestLOI = *SrcLOI;
   }
 
-  assert(DestLOI.Known.Zero.getBitWidth() == BitWidth &&
-         DestLOI.Known.One.getBitWidth() == BitWidth &&
-         "Masks should have the same bit width as the type.");
-
   for (unsigned i = 1, e = PN->getNumIncomingValues(); i != e; ++i) {
     Value *V = PN->getIncomingValue(i);
     if (isa<UndefValue>(V) || isa<ConstantExpr>(V)) {
-      DestLOI.NumSignBits = 1;
-      DestLOI.Known = KnownBits(BitWidth);
+      DestLOI.reset();
       return;
     }
 
     if (ConstantInt *CI = dyn_cast<ConstantInt>(V)) {
       APInt Val = CI->getValue().zextOrSelf(BitWidth);
       DestLOI.NumSignBits = std::min(DestLOI.NumSignBits, Val.getNumSignBits());
-      DestLOI.Known.Zero &= ~Val;
-      DestLOI.Known.One &= Val;
+      DestLOI.LeadingZeros =
+          std::min(DestLOI.LeadingZeros, Val.countLeadingZeros());
       continue;
     }
 
     assert(ValueMap.count(V) && "V should have been placed in ValueMap when "
                                 "its CopyToReg node was created.");
     Register SrcReg = ValueMap[V];
     if (!SrcReg.isVirtual()) {
-      DestLOI.IsValid = false;
+      DestLOI.reset();
       return;
     }
-    const LiveOutInfo *SrcLOI = GetLiveOutRegInfo(SrcReg, BitWidth);
+    const LiveOutInfo *SrcLOI = GetLiveOutRegInfo(SrcReg);
     if (!SrcLOI) {
-      DestLOI.IsValid = false;
+      DestLOI.reset();
       return;
     }
     DestLOI.NumSignBits = std::min(DestLOI.NumSignBits, SrcLOI->NumSignBits);
-    DestLOI.Known = KnownBits::commonBits(DestLOI.Known, SrcLOI->Known);
+    DestLOI.LeadingZeros = std::min(DestLOI.LeadingZeros, SrcLOI->LeadingZeros);
   }
 }
 
 /// setArgumentFrameIndex - Record frame index for the byval
 /// argument. This overrides previous frame index entry for this argument,
 /// if any.
 void FunctionLoweringInfo::setArgumentFrameIndex(const Argument *A,
                                                  int FI) {

llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp

 //===- SelectionDAGBuilder.cpp - Selection-DAG building -------------------===//
 //
 // 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
 //
 //===----------------------------------------------------------------------===//
 //
for (unsigned i = 0; i != NumRegs; ++i) {
 
       const FunctionLoweringInfo::LiveOutInfo *LOI =
         FuncInfo.GetLiveOutRegInfo(Regs[Part+i]);
       if (!LOI)
         continue;
 
       unsigned RegSize = RegisterVT.getScalarSizeInBits();
       unsigned NumSignBits = LOI->NumSignBits;
-      unsigned NumZeroBits = LOI->Known.countMinLeadingZeros();
+      unsigned NumZeroBits = LOI->LeadingZeros;
 
       if (NumZeroBits == RegSize) {
         // The current value is a zero.
         // Explicitly express that as it would be easier for
         // optimizations to kick in.
         Parts[i] = DAG.getConstant(0, dl, RegisterVT);
         continue;
       }

llvm/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp

 //===- SelectionDAGISel.cpp - Implement the SelectionDAGISel class --------===//
 //
 // 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
 //
 //===----------------------------------------------------------------------===//
 //
do {
 
     // Ignore non-integer values.
     SDValue Src = N->getOperand(2);
     EVT SrcVT = Src.getValueType();
     if (!SrcVT.isInteger())
       continue;
 
     unsigned NumSignBits = CurDAG->ComputeNumSignBits(Src);
-    Known = CurDAG->computeKnownBits(Src);
-    FuncInfo->AddLiveOutRegInfo(DestReg, NumSignBits, Known);
+    unsigned NumLeadingZeros =
+        CurDAG->computeKnownBits(Src).countMinLeadingZeros();
+    FuncInfo->AddLiveOutRegInfo(DestReg, NumSignBits, NumLeadingZeros);
   } while (!Worklist.empty());
 }
 
 void SelectionDAGISel::CodeGenAndEmitDAG() {
   StringRef GroupName = "sdag";
   StringRef GroupDescription = "Instruction Selection and Scheduling";
   std::string BlockName;
   bool MatchFilterBB = false; (void)MatchFilterBB;

llvm/lib/Target/AMDGPU/AMDGPUISelDAGToDAG.cpp

 //===-- AMDGPUISelDAGToDAG.cpp - A dag to dag inst selector for AMDGPU ----===//
 //
 // 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
 //
 //==-----------------------------------------------------------------------===//
 //

 #include "llvm/Analysis/LegacyDivergenceAnalysis.h"
 #include "llvm/Analysis/ValueTracking.h"
 #include "llvm/CodeGen/FunctionLoweringInfo.h"
 #include "llvm/CodeGen/SelectionDAG.h"
 #include "llvm/CodeGen/SelectionDAGISel.h"
 #include "llvm/CodeGen/SelectionDAGNodes.h"
 #include "llvm/IR/IntrinsicsAMDGPU.h"
 #include "llvm/InitializePasses.h"
+#include "llvm/Support/KnownBits.h"
 
 #ifdef EXPENSIVE_CHECKS
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/IR/Dominators.h"
 #endif
 
 #define DEBUG_TYPE "isel"