[CodeGenPrepare] Fix counting uses when folding addresses into memory instructions

[chill]

Summary

The counter of the number of instructions seen in FindAllMemoryUses
is reset after returning from a recursive invocation of FindAllMemoryUses
to the value it had before the call. In effect, depending on the shape of the uses
graph, the function may scan up to 2^N-1 instructions where N is the scan limit
(MaxMemoryUsesToScan). This does not look intuitive or intended.

This patch changes the counting to just count the scanned instructions, independent
of the shape of the references.

[mkazantsev]

llvm/test/CodeGen/Generic/addr-use-count.ll

1

Precommit test and use utils/update_llc_test_checks.py script to show what changed?

270

Do we really need so many cases to demonstrate what's going on?

llvm/lib/CodeGen/CodeGenPrepare.cpp

 
 /// Recursively walk all the uses of I until we find a memory use.
 /// If we find an obviously non-foldable instruction, return true.
 /// Add accessed addresses and types to MemoryUses.
 static bool FindAllMemoryUses(
     Instruction *I, SmallVectorImpl<std::pair<Value *, Type *>> &MemoryUses,
     SmallPtrSetImpl<Instruction *> &ConsideredInsts, const TargetLowering &TLI,
     const TargetRegisterInfo &TRI, bool OptSize, ProfileSummaryInfo *PSI,
-    BlockFrequencyInfo *BFI, int SeenInsts = 0) {
+    BlockFrequencyInfo *BFI, int &SeenInsts) {
   // If we already considered this instruction, we're done.
   if (!ConsideredInsts.insert(I).second)
     return false;
 
   // If this is an obviously unfoldable instruction, bail out.
   if (!MightBeFoldableInst(I))
     return true;
 
for (Use &U : I->uses()) {
     if (FindAllMemoryUses(UserI, MemoryUses, ConsideredInsts, TLI, TRI, OptSize,
                           PSI, BFI, SeenInsts))
       return true;
   }
 
   return false;
 }
 
+static bool FindAllMemoryUses(
+    Instruction *I, SmallVectorImpl<std::pair<Value *, Type *>> &MemoryUses,
+    const TargetLowering &TLI, const TargetRegisterInfo &TRI, bool OptSize,
+    ProfileSummaryInfo *PSI, BlockFrequencyInfo *BFI) {
+  int SeenInsts = 0;
+  SmallPtrSet<Instruction *, 16> ConsideredInsts;
+  return FindAllMemoryUses(I, MemoryUses, ConsideredInsts, TLI, TRI, OptSize,
+                           PSI, BFI, SeenInsts);
+}
+
+
 /// Return true if Val is already known to be live at the use site that we're
 /// folding it into. If so, there is no cost to include it in the addressing
 /// mode. KnownLive1 and KnownLive2 are two values that we know are live at the
 /// instruction already.
 bool AddressingModeMatcher::valueAlreadyLiveAtInst(Value *Val,
                                                    Value *KnownLive1,
                                                    Value *KnownLive2) {
   // If Val is either of the known-live values, we know it is live!
bool AddressingModeMatcher::isProfitableToFoldIntoAddressingMode(
   if (!BaseReg && !ScaledReg)
     return true;
 
   // If all uses of this instruction can have the address mode sunk into them,
   // we can remove the addressing mode and effectively trade one live register
   // for another (at worst.)  In this context, folding an addressing mode into
   // the use is just a particularly nice way of sinking it.
   SmallVector<std::pair<Value *, Type *>, 16> MemoryUses;
-  SmallPtrSet<Instruction *, 16> ConsideredInsts;
-  if (FindAllMemoryUses(I, MemoryUses, ConsideredInsts, TLI, TRI, OptSize, PSI,
-                        BFI))
+  if (FindAllMemoryUses(I, MemoryUses, TLI, TRI, OptSize, PSI, BFI))
     return false; // Has a non-memory, non-foldable use!
 
   // Now that we know that all uses of this instruction are part of a chain of
   // computation involving only operations that could theoretically be folded
   // into a memory use, loop over each of these memory operation uses and see
   // if they could  *actually* fold the instruction.  The assumption is that
   // addressing modes are cheap and that duplicating the computation involved
   // many times is worthwhile, even on a fastpath. For sinking candidates

llvm/test/CodeGen/Generic/addr-use-count.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -S -codegenprepare < %s | FileCheck %s
 ; REQUIRES: aarch64-registered-target
 
-; Test that `%addr` is sunk, even though the number of memory uses to scan exceeds the limit.
+; Test that `%addr` is not sunk, since the number of memory uses to scan exceeds the limit.
 
 target triple = "aarch64-linux"
 
 declare void @g(...)
 
 define void @f(ptr %p) {
 ; CHECK-LABEL: @f(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[SUNKADDR:%.*]] = getelementptr i8, ptr [[P:%.*]], i64 4
-; CHECK-NEXT:    [[T0:%.*]] = load i32, ptr [[SUNKADDR]], align 4
-; CHECK-NEXT:    [[T1:%.*]] = load i32, ptr [[SUNKADDR]], align 4
-; CHECK-NEXT:    [[T2:%.*]] = load i32, ptr [[SUNKADDR]], align 4
-; CHECK-NEXT:    [[T3:%.*]] = load i32, ptr [[SUNKADDR]], align 4
-; CHECK-NEXT:    [[T4:%.*]] = load i32, ptr [[SUNKADDR]], align 4
-; CHECK-NEXT:    [[T5:%.*]] = load i32, ptr [[SUNKADDR]], align 4
-; CHECK-NEXT:    [[T6:%.*]] = load i32, ptr [[SUNKADDR]], align 4
-; CHECK-NEXT:    [[T7:%.*]] = load i32, ptr [[SUNKADDR]], align 4
-; CHECK-NEXT:    [[T8:%.*]] = load i32, ptr [[SUNKADDR]], align 4
-; CHECK-NEXT:    [[T9:%.*]] = load i32, ptr [[SUNKADDR]], align 4
-; CHECK-NEXT:    [[T10:%.*]] = load i32, ptr [[SUNKADDR]], align 4
-; CHECK-NEXT:    [[T11:%.*]] = load i32, ptr [[SUNKADDR]], align 4
-; CHECK-NEXT:    [[T12:%.*]] = load i32, ptr [[SUNKADDR]], align 4
-; CHECK-NEXT:    [[T13:%.*]] = load i32, ptr [[SUNKADDR]], align 4
-; CHECK-NEXT:    [[T14:%.*]] = load i32, ptr [[SUNKADDR]], align 4
-; CHECK-NEXT:    [[T15:%.*]] = load i32, ptr [[SUNKADDR]], align 4
-; CHECK-NEXT:    [[T16:%.*]] = load i32, ptr [[SUNKADDR]], align 4
-; CHECK-NEXT:    [[T17:%.*]] = load i32, ptr [[SUNKADDR]], align 4
-; CHECK-NEXT:    [[T18:%.*]] = load i32, ptr [[SUNKADDR]], align 4
-; CHECK-NEXT:    [[SUNKADDR1:%.*]] = getelementptr i8, ptr [[P]], i64 8
-; CHECK-NEXT:    [[T19:%.*]] = load i32, ptr [[SUNKADDR1]], align 4
+; CHECK-NEXT:    [[ADDR:%.*]] = getelementptr i8, ptr [[P:%.*]], i32 4
+; CHECK-NEXT:    br label [[EXIT:%.*]]
+; CHECK:       exit:
+; CHECK-NEXT:    [[T0:%.*]] = load i32, ptr [[ADDR]], align 4
+; CHECK-NEXT:    [[T1:%.*]] = load i32, ptr [[ADDR]], align 4
+; CHECK-NEXT:    [[T2:%.*]] = load i32, ptr [[ADDR]], align 4
+; CHECK-NEXT:    [[T3:%.*]] = load i32, ptr [[ADDR]], align 4
+; CHECK-NEXT:    [[T4:%.*]] = load i32, ptr [[ADDR]], align 4
+; CHECK-NEXT:    [[T5:%.*]] = load i32, ptr [[ADDR]], align 4
+; CHECK-NEXT:    [[T6:%.*]] = load i32, ptr [[ADDR]], align 4
+; CHECK-NEXT:    [[T7:%.*]] = load i32, ptr [[ADDR]], align 4
+; CHECK-NEXT:    [[T8:%.*]] = load i32, ptr [[ADDR]], align 4
+; CHECK-NEXT:    [[T9:%.*]] = load i32, ptr [[ADDR]], align 4
+; CHECK-NEXT:    [[T10:%.*]] = load i32, ptr [[ADDR]], align 4
+; CHECK-NEXT:    [[T11:%.*]] = load i32, ptr [[ADDR]], align 4
+; CHECK-NEXT:    [[T12:%.*]] = load i32, ptr [[ADDR]], align 4
+; CHECK-NEXT:    [[T13:%.*]] = load i32, ptr [[ADDR]], align 4
+; CHECK-NEXT:    [[T14:%.*]] = load i32, ptr [[ADDR]], align 4
+; CHECK-NEXT:    [[T15:%.*]] = load i32, ptr [[ADDR]], align 4
+; CHECK-NEXT:    [[T16:%.*]] = load i32, ptr [[ADDR]], align 4
+; CHECK-NEXT:    [[T17:%.*]] = load i32, ptr [[ADDR]], align 4
+; CHECK-NEXT:    [[T18:%.*]] = load i32, ptr [[ADDR]], align 4
+; CHECK-NEXT:    [[ADDR_1:%.*]] = getelementptr i8, ptr [[ADDR]], i32 4
+; CHECK-NEXT:    [[T19:%.*]] = load i32, ptr [[ADDR_1]], align 4
 ; CHECK-NEXT:    call void @g(i32 [[T0]], i32 [[T1]], i32 [[T2]], i32 [[T3]], i32 [[T4]], i32 [[T5]], i32 [[T6]], i32 [[T7]], i32 [[T8]], i32 [[T9]], i32 [[T10]], i32 [[T11]], i32 [[T12]], i32 [[T13]], i32 [[T14]], i32 [[T15]], i32 [[T16]], i32 [[T17]], i32 [[T18]], i32 [[T19]])
 ; CHECK-NEXT:    ret void
 ;
 entry:
   %addr = getelementptr i8, ptr %p, i32 4
   br label %exit
 
 exit:
exit:
   %t18 = load i32, ptr %addr
   %addr.1 = getelementptr i8, ptr %addr, i32 4
   %t19 = load i32, ptr %addr.1
 
   call void @g(i32 %t0, i32 %t1, i32 %t2, i32 %t3, i32 %t4, i32 %t5, i32 %t6, i32 %t7,
   i32 %t8, i32 %t9, i32 %t10, i32 %t11, i32 %t12, i32 %t13, i32 %t14, i32 %t15, i32 %t16,
   i32 %t17, i32 %t18, i32 %t19)
   ret void
 }