[SelectionDAG] Try to recompute LiveOutInfo of PHI

[junbuml]

Summary

This change try to recompute LiveOutInfo for a PHI, which was invalidated, once its predecessors are all visited. This allows us to add AssertZext while building DAG, which enable eliminating redundant zexts during the DAGCombine phase.

[junbuml]

Kindling ping. please let me know any comment and also add other reviewers who could look over the code.

[mcrosier]

Just a few general comments.

include/llvm/CodeGen/FunctionLoweringInfo.h

187

Please add a comment specifying what is contained in this set.

271

The function name should begin with a lower case letter and the doxygen comment shouldn't have the function name. This differs from the style of the surrounding code, but we should make the jump to the preferred style.

lib/CodeGen/SelectionDAG/FunctionLoweringInfo.cpp

413

Perhaps add a few comments describing the function and the assumptions it makes.

[junbuml]

Addressed Chad's comments.

[junbuml]

Kindly ping. Please let me know any comment.

[hfinkel]

Do you have a test case?

It looks like you're making this algorithm directly recursive with a worst-case recursion depth given only by the number of blocks. Is the right? Can we say something about the worst case here?

[junbuml]

Sorry, I dropped the test case by mistake in my previous update; added it now.
Yes, the worst-case recursion depth is the number of blocks if every block has back edges, and a value used in the last block is passed through PHIs in every block.

include/llvm/CodeGen/FunctionLoweringInfo.h

public:
   /// 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.
   SmallPtrSet<const BasicBlock*, 4> VisitedBBs;
 
+  /// Record PHIs invalidated for computing LiveOutRegInfo.
+  SmallPtrSet<const PHINode *, 4> InvalidatedPHIs;
+
   /// PHINodesToUpdate - A list of phi instructions whose operand list will
   /// be updated after processing the current basic block.
   /// TODO: This isn't per-function state, it's per-basic-block state. But
   /// there's no other convenient place for it to live right now.
   std::vector<std::pair<MachineInstr*, unsigned> > PHINodesToUpdate;
   unsigned OrigNumPHINodesToUpdate;
 
   /// If the current MBB is a landing pad, the exception pointer and exception
void AddLiveOutRegInfo(unsigned Reg, unsigned NumSignBits,
     LOI.KnownOne = KnownOne;
     LOI.KnownZero = KnownZero;
   }
 
   /// ComputePHILiveOutRegInfo - Compute LiveOutInfo for a PHI's destination
   /// register based on the LiveOutInfo of its operands.
   void ComputePHILiveOutRegInfo(const PHINode*);
 
+  /// Try to recompute LiveOutInfo for a PHI which was invalidated before.
+  const LiveOutInfo *tryToRecomputePHILiveOutRegInfo(Value *V,
+                                                     unsigned BitWidth);
+
   /// 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*, unsigned>::const_iterator It = ValueMap.find(PN);
     if (It == ValueMap.end())
       return;
 

lib/CodeGen/SelectionDAG/FunctionLoweringInfo.cpp

if (BitWidth > LOI->KnownZero.getBitWidth()) {
     LOI->NumSignBits = 1;
     LOI->KnownZero = LOI->KnownZero.zextOrTrunc(BitWidth);
     LOI->KnownOne = LOI->KnownOne.zextOrTrunc(BitWidth);
   }
 
   return LOI;
 }
 
+/// Try to recompute LiveOutRegInfo for an invalidated PHI when it's referred as
+/// an input value in a later block if its predecessors are all visited at that
+/// point.
+const FunctionLoweringInfo::LiveOutInfo *
+FunctionLoweringInfo::tryToRecomputePHILiveOutRegInfo(Value *V,
+                                                      unsigned BitWidth) {
+  PHINode *Phi = dyn_cast<PHINode>(V);
+  if (!Phi || !InvalidatedPHIs.count(Phi))
+    return nullptr;
+
+  const BasicBlock *LLVMBB = Phi->getParent();
+  for (const_pred_iterator PI = pred_begin(LLVMBB), PE = pred_end(LLVMBB);
+       PI != PE; ++PI) {
+    if (!VisitedBBs.count(*PI) || MBBMap[*PI] == MBB)
+      return nullptr;
+  }
+  // If all predecessors are visited, retry to compute LiveOutRegInfo.
+  unsigned SrcReg = ValueMap[Phi];
+  InvalidatedPHIs.erase(Phi);
+  ComputePHILiveOutRegInfo(Phi);
+  return GetLiveOutRegInfo(SrcReg, BitWidth);
+}
+
 /// 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;
assert(ValueMap.count(V) && "V should have been placed in ValueMap when its"
                                 "CopyToReg node was created.");
     unsigned SrcReg = ValueMap[V];
     if (!TargetRegisterInfo::isVirtualRegister(SrcReg)) {
       DestLOI.IsValid = false;
       return;
     }
     const LiveOutInfo *SrcLOI = GetLiveOutRegInfo(SrcReg, BitWidth);
     if (!SrcLOI) {
+      if (!(SrcLOI = tryToRecomputePHILiveOutRegInfo(V, BitWidth))) {
         DestLOI.IsValid = false;
         return;
       }
+    }
     DestLOI = *SrcLOI;
   }
 
   assert(DestLOI.KnownZero.getBitWidth() == BitWidth &&
          DestLOI.KnownOne.getBitWidth() == BitWidth &&
          "Masks should have the same bit width as the type.");
 
   for (unsigned i = 1, e = PN->getNumIncomingValues(); i != e; ++i) {
assert(ValueMap.count(V) && "V should have been placed in ValueMap when "
                                 "its CopyToReg node was created.");
     unsigned SrcReg = ValueMap[V];
     if (!TargetRegisterInfo::isVirtualRegister(SrcReg)) {
       DestLOI.IsValid = false;
       return;
     }
     const LiveOutInfo *SrcLOI = GetLiveOutRegInfo(SrcReg, BitWidth);
     if (!SrcLOI) {
+      if (!(SrcLOI = tryToRecomputePHILiveOutRegInfo(V, BitWidth))) {
         DestLOI.IsValid = false;
         return;
       }
+    }
     DestLOI.NumSignBits = std::min(DestLOI.NumSignBits, SrcLOI->NumSignBits);
     DestLOI.KnownZero &= SrcLOI->KnownZero;
     DestLOI.KnownOne &= SrcLOI->KnownOne;
   }
 }
 
 /// setArgumentFrameIndex - Record frame index for the byval
 /// argument. This overrides previous frame index entry for this argument,

lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp

if (FuncInfo->InsertPt != FuncInfo->MBB->begin())
       FastIS->setLastLocalValue(&*std::prev(FuncInfo->InsertPt));
     else
       FastIS->setLastLocalValue(nullptr);
   }
   createSwiftErrorEntriesInEntryBlock(FuncInfo, FastIS, TLI, TII, SDB);
 
   // Iterate over all basic blocks in the function.
   for (const BasicBlock *LLVMBB : RPOT) {
+    FuncInfo->MBB = FuncInfo->MBBMap[LLVMBB];
     if (OptLevel != CodeGenOpt::None) {
       bool AllPredsVisited = true;
       for (const_pred_iterator PI = pred_begin(LLVMBB), PE = pred_end(LLVMBB);
            PI != PE; ++PI) {
         if (!FuncInfo->VisitedBBs.count(*PI)) {
           AllPredsVisited = false;
           break;
         }
       }
 
       if (AllPredsVisited) {
         for (BasicBlock::const_iterator I = LLVMBB->begin();
              const PHINode *PN = dyn_cast<PHINode>(I); ++I)
           FuncInfo->ComputePHILiveOutRegInfo(PN);
       } else {
         for (BasicBlock::const_iterator I = LLVMBB->begin();
-             const PHINode *PN = dyn_cast<PHINode>(I); ++I)
+             const PHINode *PN = dyn_cast<PHINode>(I); ++I) {
           FuncInfo->InvalidatePHILiveOutRegInfo(PN);
+          FuncInfo->InvalidatedPHIs.insert(PN);
+        }
       }
 
       FuncInfo->VisitedBBs.insert(LLVMBB);
     }
 
     BasicBlock::const_iterator const Begin =
         LLVMBB->getFirstNonPHI()->getIterator();
     BasicBlock::const_iterator const End = LLVMBB->end();
     BasicBlock::const_iterator BI = End;
 
-    FuncInfo->MBB = FuncInfo->MBBMap[LLVMBB];
     if (!FuncInfo->MBB)
       continue; // Some blocks like catchpads have no code or MBB.
 
     // Insert new instructions after any phi or argument setup code.
     FuncInfo->InsertPt = FuncInfo->MBB->end();
 
     // Setup an EH landing-pad block.
     FuncInfo->ExceptionPointerVirtReg = 0;

test/CodeGen/AArch64/selectdag-assertzext.ll

+; RUN: llc < %s -mtriple=aarch64--linux-gnu | FileCheck %s
+
+; This test is to check an AND instruction for zext is not generated in %while.end
+; by adding AssertZext to CopyFromReg for %idx while building DAG.
+
+; CHECK-LABEL: @checkLiveoutInfo
+; CHECK: ldrb w[[LD:[0-9]+]], [x1]
+; CHECK-LABEL: %while.end
+; CHECK-NOT: and w{{[0-9]+}}, w[[LD]], #0xff
+
+@CA = common global i8* null, align 8
+
+define i32 @checkLiveoutInfo(i64 %c,i8* %s) {
+entry:
+  %l1 = load i8, i8* %s, align 1
+  %cmp12 = icmp eq i8 %l1, 0
+  br i1 %cmp12, label %while.end, label %land.rhs.preheader
+
+land.rhs.preheader:                               ; preds = %entry
+  %scevgep = getelementptr i8, i8* %s, i64 -1
+  br label %land.rhs
+
+land.rhs:                                         ; preds = %land.rhs.preheader, %while.body
+  %lsr.iv = phi i8* [ %scevgep, %land.rhs.preheader ], [ %scevgep16, %while.body ]
+  %invalidatedPhi = phi i8 [ %l2, %while.body ], [ %l1, %land.rhs.preheader ]
+  %cmp4 = icmp eq i64 %c, 0
+  br i1 %cmp4, label %while.body, label %while.end
+
+while.body:                                       ; preds = %land.rhs
+  %l2 = load i8, i8* %lsr.iv, align 1
+  %cmp = icmp eq i8 %l2, 0
+  %scevgep16 = getelementptr i8, i8* %lsr.iv, i64 -1
+  br i1 %cmp, label %while.end, label %land.rhs
+
+while.end:                                        ; preds = %land.rhs, %while.body, %entry
+  %idx= phi i8 [ 0, %entry ], [ %invalidatedPhi, %land.rhs ], [ 0, %while.body ]
+  %l3 = load i8*, i8** @CA, align 8
+  %zext1 = zext i8 %idx to i64
+  %arrayidx = getelementptr inbounds i8, i8* %l3, i64 %zext1
+  %l4 = load i8, i8* %arrayidx, align 1
+  %zext2 = zext i8 %l4  to i32
+  ret i32 %zext2
+}