[PowerPC] Fix compile time issue in recursive CTR analysis code

[tejohnson]

Summary

Avoid re-examining operands on recursive walk looking for CTR.
This was causing huge compile time after some earlier optimization
created a large expression.

The start of the expression (created by IndVarSimplify) looked like:

%469 = lshr i64 trunc (i128 xor (i128 udiv (i128 mul (i128 zext (i64 add (i64 trunc (i128 xor (i128 lshr (i128 mul (i128 zext (i64 add (i64 trunc (i128 xor (i128 lshr (i128 mul (i128 zext (i64 add (i64 trunc (i128 xor (i128 lshr (i128 mul (i128 zext (i64 add (i64 trunc (i128 xor (i128 lshr (i128 mul (i128 zext (i64 add (i64 trunc (i128 xor (i128 lshr (i128 mul (i128 zext (i64 add (i64 trunc (i128 xor (i128 lshr (i128 mul (i128 zext (i64 add (i64 trunc (i128 xor (i128 lshr (i128 mul (i128 zext (i64 add (i64 trunc (i128 xor (i128 lshr (i128 mul (i128 zext (i64 add (i64 trunc (i128 xor (i128 lshr (i128 mul (i128 zext (i64 add (i64 trunc (i128 xor (i128 lshr (i128 mul (i128 zext (i64 add (i64 trunc (i128 xor (i128 lshr (i128 mul (i128 zext (i64 add (i64 trunc (i128 xor (i128 lshr (i128 mul (i128 zext (i64 add (i64 trunc (i128 xor (i128 lshr (i128 mul (i128 zext (i64 add (i64 trunc (i128 xor (i128 lshr (i128 mul (i128 zext (i64 add (i64 trunc (i128 xor (i128 lshr (i128 mul (i128 zext (i64 add (i64 trunc (i128 xor (i128 lshr (i128 mul (i128 zext (i64 add (i64 trunc (i128 xor (i128 lshr (i128 mul (i128 zext (i64 add (i64 trunc (i128 xor (i128 lshr (i128 mul (i128 zext (i64 add (i64 trunc (i128 xor (i128 lshr (i128 mul (i128 zext (i64 add (i64 trunc (i128 xor (i128 lshr (i128 mul (i128 zext (i64 add (i64 trunc (i128 xor (i128 lshr (i128 mul (i128 zext (i64 add (i64 trunc (i128 xor (i128 lshr (i128 mul (i128 zext (i64 add (i64 trunc (i128 xor (i128 lshr (i128 mul (i128 zext (i64 add (i64 trunc (i128 xor (i128 lshr (i128 mul (i128 zext (i64 add (i64 trunc (i128 xor (i128 lshr (i128 mul (i128 zext (i64 add (i64 trunc (i128 xor (i128 lshr (i128 mul (i128 zext (i64 add (i64 ptrtoint (i8 @_ZN4absl13hash_internal13CityHashState5kSeedE to i64), i64 120) to i128), i128 8192506886679785011), i128 64), i128 mul (i128 zext (i64 add (i64 ptrtoint (i8 @_ZN4absl13hash_internal13CityHashState5kSeedE to i64), i64 120) to i128), i128 8192506886679785011)) to i64), i64 45) to i128), i128 8192506886679785011), i128 64), i128 mul (i128 zext (i64 add (i64 trunc (i128 xor (i128 lshr (i128 mul (i128 zext (i64 add (i64 ptrtoint (i8 @_ZN4absl13hash_internal13CityHashState5kSeedE to i64), i64 120) to i128), i128 8192506886679785011), i128 64), i128 mul (i128 zext (i64 add (i64 ptrtoint (i8 @_ZN4absl13hash_internal13CityHashState5kSeedE to i64), i64 120) to i128), i128 8192506886679785011)) to i64), i64 45) to i128), ...

with the _ZN4absl13hash_internal13CityHashState5kSeedE referenced many times.

[MaskRay]

llvm/lib/Target/PowerPC/PPCTargetTransformInfo.cpp

508

How about SmallPtrSet<const Value *, 4> (or 4 -> another integer)?

[tejohnson]

Address comment

[MaskRay]

Generally looks good, but the title needs to be clarified. This piece of code is related to an optimization which uses CTR as the loop count register.

For context, D6786 introduced mightUseCTR. rL251582 made it recurse into the constant.

IIUC, with ThinLTO's ImportConstantsWithRefs optimization, a constant can be very large, and recursing into it for every instruction can make the compilation slow. Is that the case?

[tejohnson]

In D75790#1915590, @MaskRay wrote:

Generally looks good, but the title needs to be clarified. This piece of code is related to an optimization which uses CTR as the loop count register.

Updated the title.

For context, D6786 introduced mightUseCTR. rL251582 made it recurse into the constant.

IIUC, with ThinLTO's ImportConstantsWithRefs optimization, a constant can be very large, and recursing into it for every instruction can make the compilation slow. Is that the case?

No, the constant itself was quite simple. Importing it simply enabled some additional optimization (in IndVarSimplify) that created a huge instruction expression. It was iterating that expression, not the constant itself, that is so slow.

[MaskRay]

In D75790#1915671, @tejohnson wrote:

In D75790#1915590, @MaskRay wrote:

Generally looks good, but the title needs to be clarified. This piece of code is related to an optimization which uses CTR as the loop count register.

Updated the title.

For context, D6786 introduced mightUseCTR. rL251582 made it recurse into the constant.

IIUC, with ThinLTO's ImportConstantsWithRefs optimization, a constant can be very large, and recursing into it for every instruction can make the compilation slow. Is that the case?

No, the constant itself was quite simple. Importing it simply enabled some additional optimization (in IndVarSimplify) that created a huge instruction expression. It was iterating that expression, not the constant itself, that is so slow.

It'd be nice to give a (reduced) example in the description, even if testing it reliably may be unrealistic.

[tejohnson]

In D75790#1915719, @MaskRay wrote:

In D75790#1915671, @tejohnson wrote:

In D75790#1915590, @MaskRay wrote:

Generally looks good, but the title needs to be clarified. This piece of code is related to an optimization which uses CTR as the loop count register.

Updated the title.

For context, D6786 introduced mightUseCTR. rL251582 made it recurse into the constant.

IIUC, with ThinLTO's ImportConstantsWithRefs optimization, a constant can be very large, and recursing into it for every instruction can make the compilation slow. Is that the case?

No, the constant itself was quite simple. Importing it simply enabled some additional optimization (in IndVarSimplify) that created a huge instruction expression. It was iterating that expression, not the constant itself, that is so slow.

It'd be nice to give a (reduced) example in the description, even if testing it reliably may be unrealistic.

I showed the start of the expression that causes the analysis to re-analyze the same operand many times.

llvm/lib/Target/PowerPC/PPCTargetTransformInfo.h

class PPCTTIImpl : public BasicTTIImplBase<PPCTTIImpl> {
   typedef TargetTransformInfo TTI;
   friend BaseT;
 
   const PPCSubtarget *ST;
   const PPCTargetLowering *TLI;
 
   const PPCSubtarget *getST() const { return ST; }
   const PPCTargetLowering *getTLI() const { return TLI; }
-  bool mightUseCTR(BasicBlock *BB, TargetLibraryInfo *LibInfo);
+  bool mightUseCTR(BasicBlock *BB, TargetLibraryInfo *LibInfo,
+                   SmallPtrSetImpl<const Value *> &Visited);
 
 public:
   explicit PPCTTIImpl(const PPCTargetMachine *TM, const Function &F)
       : BaseT(TM, F.getParent()->getDataLayout()), ST(TM->getSubtargetImpl(F)),
         TLI(ST->getTargetLowering()) {}
 
   /// \name Scalar TTI Implementations
   /// @{

llvm/lib/Target/PowerPC/PPCTargetTransformInfo.cpp

if (U->getType()->isVectorTy()) {
     // Instructions that need to be split should cost more.
     std::pair<int, MVT> LT = TLI->getTypeLegalizationCost(DL, U->getType());
     return LT.first * BaseT::getUserCost(U, Operands);
   }
 
   return BaseT::getUserCost(U, Operands);
 }
 
-bool PPCTTIImpl::mightUseCTR(BasicBlock *BB,
-                             TargetLibraryInfo *LibInfo) {
+bool PPCTTIImpl::mightUseCTR(BasicBlock *BB, TargetLibraryInfo *LibInfo,
+                             SmallPtrSetImpl<const Value *> &Visited) {
   const PPCTargetMachine &TM = ST->getTargetMachine();
 
   // Loop through the inline asm constraints and look for something that
   // clobbers ctr.
   auto asmClobbersCTR = [](InlineAsm *IA) {
     InlineAsm::ConstraintInfoVector CIV = IA->ParseConstraints();
     for (unsigned i = 0, ie = CIV.size(); i < ie; ++i) {
       InlineAsm::ConstraintInfo &C = CIV[i];
       if (C.Type != InlineAsm::isInput)
         for (unsigned j = 0, je = C.Codes.size(); j < je; ++j)
           if (StringRef(C.Codes[j]).equals_lower("{ctr}"))
             return true;
     }
     return false;
   };
 
   // Determining the address of a TLS variable results in a function call in
   // certain TLS models.
-  std::function<bool(const Value*)> memAddrUsesCTR =
-    [&memAddrUsesCTR, &TM](const Value *MemAddr) -> bool {
+  std::function<bool(const Value *)> memAddrUsesCTR =
+      [&memAddrUsesCTR, &TM, &Visited](const Value *MemAddr) -> bool {
+    // No need to traverse again if we already checked this operand.
+    if (!Visited.insert(MemAddr).second)
+      return false;
     const auto *GV = dyn_cast<GlobalValue>(MemAddr);
     if (!GV) {
       // Recurse to check for constants that refer to TLS global variables.
       if (const auto *CV = dyn_cast<Constant>(MemAddr))
         for (const auto &CO : CV->operands())
           if (memAddrUsesCTR(CO))
             return true;
 
for (BasicBlock *BB : L->blocks())
       Metrics.analyzeBasicBlock(BB, *this, EphValues);
     // 6 is an approximate latency for the mtctr instruction.
     if (Metrics.NumInsts <= (6 * SchedModel.getIssueWidth()))
       return false;
   }
 
   // We don't want to spill/restore the counter register, and so we don't
   // want to use the counter register if the loop contains calls.
+  SmallPtrSet<const Value *, 4> Visited;
   for (Loop::block_iterator I = L->block_begin(), IE = L->block_end();
        I != IE; ++I)
-    if (mightUseCTR(*I, LibInfo))
+    if (mightUseCTR(*I, LibInfo, Visited))
       return false;
 
   SmallVector<BasicBlock*, 4> ExitingBlocks;
   L->getExitingBlocks(ExitingBlocks);
 
   // If there is an exit edge known to be frequently taken,
   // we should not transform this loop.
   for (auto &BB : ExitingBlocks) {