From 8f5e3c74b678f961700d07911e0cebdc87fb43d5 Mon Sep 17 00:00:00 2001 From: Teresa Johnson Date: Fri, 6 Mar 2020 17:48:22 -0800 Subject: [PATCH] [PowerPC] Fix compile time issue in recursive CTR analysis code 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. Reviewers: hfinkel Subscribers: nemanjai, hiraditya, kbarton, jsji, shchenz, llvm-commits Tags: #llvm Differential Revision: https://reviews.llvm.org/D75790 --- llvm/lib/Target/PowerPC/PPCTargetTransformInfo.cpp | 14 +++++++++----- llvm/lib/Target/PowerPC/PPCTargetTransformInfo.h | 3 ++- 2 files changed, 11 insertions(+), 6 deletions(-) diff --git a/llvm/lib/Target/PowerPC/PPCTargetTransformInfo.cpp b/llvm/lib/Target/PowerPC/PPCTargetTransformInfo.cpp index 1bb78ed..db57097 100644 --- a/llvm/lib/Target/PowerPC/PPCTargetTransformInfo.cpp +++ b/llvm/lib/Target/PowerPC/PPCTargetTransformInfo.cpp @@ -217,8 +217,8 @@ unsigned PPCTTIImpl::getUserCost(const User *U, return BaseT::getUserCost(U, Operands); } -bool PPCTTIImpl::mightUseCTR(BasicBlock *BB, - TargetLibraryInfo *LibInfo) { +bool PPCTTIImpl::mightUseCTR(BasicBlock *BB, TargetLibraryInfo *LibInfo, + SmallPtrSetImpl &Visited) { const PPCTargetMachine &TM = ST->getTargetMachine(); // Loop through the inline asm constraints and look for something that @@ -237,8 +237,11 @@ bool PPCTTIImpl::mightUseCTR(BasicBlock *BB, // Determining the address of a TLS variable results in a function call in // certain TLS models. - std::function memAddrUsesCTR = - [&memAddrUsesCTR, &TM](const Value *MemAddr) -> bool { + std::function 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(MemAddr); if (!GV) { // Recurse to check for constants that refer to TLS global variables. @@ -502,9 +505,10 @@ bool PPCTTIImpl::isHardwareLoopProfitable(Loop *L, ScalarEvolution &SE, // 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 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 ExitingBlocks; diff --git a/llvm/lib/Target/PowerPC/PPCTargetTransformInfo.h b/llvm/lib/Target/PowerPC/PPCTargetTransformInfo.h index 5aea524..36ed6ff 100644 --- a/llvm/lib/Target/PowerPC/PPCTargetTransformInfo.h +++ b/llvm/lib/Target/PowerPC/PPCTargetTransformInfo.h @@ -33,7 +33,8 @@ class PPCTTIImpl : public BasicTTIImplBase { 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 &Visited); public: explicit PPCTTIImpl(const PPCTargetMachine *TM, const Function &F) -- 2.7.4