[HardwareLoops] NFC - move hardware loop checking code to isHardwareLoopProfitable()

[shchenz]

Summary

Move more hardware checking codes into isHardwareLoopProfitable():
1: a more accurate result about hardware loop converting for target hook canSaveCmp() (Currently only used in PowerPC)
2: counter NumHWLoops is also more accurate.

This is a NFC patch.

[samparker]

llvm/lib/Analysis/TargetTransformInfo.cpp

157

Looks like this logic can be simplified now as UseLoopGuard is only ever equal to ForceGuardLoopEntry.

[shchenz]

address @samparker comments.

[shchenz]

llvm/lib/Analysis/TargetTransformInfo.cpp

157

Good idea. Get your point. No matter 'test and set' form may fallback to the 'set' form or not, it will not impact that the Loop is a hardware loop. Updated accordingly.

[samparker]

Thanks, LGTM

[stella.stamenova]

I am not sure if you've seen this yet, but this broke the Windows LLDB bot:

http://lab.llvm.org:8011/builders/lldb-x64-windows-ninja/builds/6478

[sbc100]

This broke my build too. Could be related to the fact that I build with -DBUILD_SHARED_LIBS=ON?

[steven_wu]

This added an extra dependency from Analysis -> TransformUtils. I don't think this dependency is a good idea, so is adding preheader in analysis pass.

[sbc100]

I tried adding a dependency on TransformUtils to Analysis/LLVMBuild.txt but that generated:

CMake Error at CMakeLists.txt:711 (message):
  Unexpected failure executing llvm-build: llvm-build: fatal error: found
  cycle to u'Analysis' after following: u'AArch64CodeGen' (required library)
  -> u'Analysis' (required library) -> u'TransformUtils' (required library)
  -> Analysis

Does this mean that this change violates the dependency graph? Assuming you can repro, with -DBUILD_SHARED_LIBS=ON then perhaps we can revert this while a solution is found?

[saugustine]

This revision violates some rules about the build structure.

In particular, Analysis shouldn't depend on Transforms, and the new includes in TargetTransform.cpp make it do so.

These headers would have to be moved into the includes directory for this to be a viable change.

One possible fix would be to move TargetTransform.cpp from Analysis into Transform/Utils.

I propose we that we revert this revision.

[sfertile]

In D64197#1576464, @sbc100 wrote:

I tried adding a dependency on TransformUtils to Analysis/LLVMBuild.txt but that generated:

CMake Error at CMakeLists.txt:711 (message):
  Unexpected failure executing llvm-build: llvm-build: fatal error: found
  cycle to u'Analysis' after following: u'AArch64CodeGen' (required library)
  -> u'Analysis' (required library) -> u'TransformUtils' (required library)
  -> Analysis

Does this mean that this change violates the dependency graph? Assuming you can repro, with -DBUILD_SHARED_LIBS=ON then perhaps we can revert this while a solution is found?

Between modifying the CFG in an analysis pass and breaking the shared libs build, I think reverting for now is a good idea.

[jsji]

Reverted in https://reviews.llvm.org/rL365520.

[sfertile]

In D64197#1576519, @jsji wrote:

Reverted in https://reviews.llvm.org/rL365520.

Thanks Jinsong.

[shchenz]

Thanks for reverting @jsji . I will see how to fix it.

llvm/include/llvm/Analysis/TargetTransformInfo.h

bool IsNestingLegal = false;    // Can a hardware loop be a parent to
                                   // another hardware loop?
   bool CounterInReg = false;      // Should loop counter be updated in
                                   // the loop via a phi?
   bool PerformEntryTest = false;  // Generate the intrinsic which also performs
                                   // icmp ne zero on the loop counter value and
                                   // produces an i1 to guard the loop entry.
   bool isHardwareLoopCandidate(ScalarEvolution &SE, LoopInfo &LI,
                                DominatorTree &DT, bool ForceNestedLoop = false,
-                               bool ForceHardwareLoopPHI = false);
+                               bool ForceHardwareLoopPHI = false,
+                               bool ForceGuardLoopEntry = false);
   bool canAnalyze(LoopInfo &LI);
 };
 
 /// This pass provides access to the codegen interfaces that are needed
 /// for IR-level transformations.
 class TargetTransformInfo {
 public:
   /// Construct a TTI object using a type implementing the \c Concept

llvm/lib/Analysis/TargetTransformInfo.cpp

 #include "llvm/IR/IntrinsicInst.h"
 #include "llvm/IR/Module.h"
 #include "llvm/IR/Operator.h"
 #include "llvm/IR/PatternMatch.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/ErrorHandling.h"
 #include "llvm/Analysis/CFG.h"
 #include "llvm/Analysis/LoopIterator.h"
+#include "llvm/Transforms/Utils.h"
+#include "llvm/Transforms/Utils/LoopUtils.h" 
+#include "llvm/Analysis/ScalarEvolutionExpander.h"
 #include <utility>
 
 using namespace llvm;
 using namespace PatternMatch;
 
 #define DEBUG_TYPE "tti"
 
 static cl::opt<bool> EnableReduxCost("costmodel-reduxcost", cl::init(false),
bool HardwareLoopInfo::canAnalyze(LoopInfo &LI) {
   if (containsIrreducibleCFG<const BasicBlock *>(RPOT, LI))
     return false;
   return true;
 }
 
 bool HardwareLoopInfo::isHardwareLoopCandidate(ScalarEvolution &SE,
                                                LoopInfo &LI, DominatorTree &DT,
                                                bool ForceNestedLoop,
-                                               bool ForceHardwareLoopPHI) {
+                                               bool ForceHardwareLoopPHI,
+                                               bool ForceGuardLoopEntry) {
   SmallVector<BasicBlock *, 4> ExitingBlocks;
   L->getExitingBlocks(ExitingBlocks);
 
   for (SmallVectorImpl<BasicBlock *>::iterator I = ExitingBlocks.begin(),
                                                IE = ExitingBlocks.end();
        I != IE; ++I) {
     BasicBlock *BB = *I;
 
for (SmallVectorImpl<BasicBlock *>::iterator I = ExitingBlocks.begin(),
     // has a latch block.
     ExitBlock = *I;
     ExitCount = EC;
     break;
   }
 
   if (!ExitBlock)
     return false;
+
+  BasicBlock *Preheader = L->getLoopPreheader();
+
+  // If we don't have a preheader, then insert one.
+  if (!Preheader)
+    Preheader = InsertPreheaderForLoop(L, &DT, &LI, nullptr, true);
+  if (!Preheader)
+    return false;
+
+  // Make sure we have a valid Loop Count
+  if (!ExitCount->getType()->isPointerTy() && ExitCount->getType() != CountType)
+    ExitCount = SE.getZeroExtendExpr(ExitCount, CountType);
+
+  ExitCount = SE.getAddExpr(ExitCount, SE.getOne(CountType));
+
+  BasicBlock *BB = L->getLoopPreheader();
+  bool UseLoopGuard = false;
+  if (!SE.isLoopEntryGuardedByCond(L, ICmpInst::ICMP_NE, ExitCount,
+                                   SE.getZero(ExitCount->getType())))
+    UseLoopGuard |= ForceGuardLoopEntry;
+
+  if (UseLoopGuard && BB->getSinglePredecessor() &&
+      cast<BranchInst>(BB->getTerminator())->isUnconditional())
+    BB = BB->getSinglePredecessor();
+
+  if (!isSafeToExpandAt(ExitCount, BB->getTerminator(), SE)) {
+    LLVM_DEBUG(dbgs() << "Not a Hardware Loop: unsafe to expand ExitCount "
+                      << *ExitCount << "\n");
+    return false;
+  }
+
   return true;
 }
 
 TargetTransformInfo::TargetTransformInfo(const DataLayout &DL)
     : TTIImpl(new Model<NoTTIImpl>(NoTTIImpl(DL))) {}
 
 TargetTransformInfo::~TargetTransformInfo() {}
 

llvm/lib/CodeGen/HardwareLoops.cpp

 /// the target, by querying TargetTransformInfo. A hardware loop comprises of
 /// two intrinsics: one, outside the loop, to set the loop iteration count and
 /// another, in the exit block, to decrement the counter. The decremented value
 /// can either be carried through the loop via a phi or handled in some opaque
 /// way by the target.
 ///
 //===----------------------------------------------------------------------===//
 
-#include "llvm/Pass.h"
 #include "llvm/PassRegistry.h"
 #include "llvm/PassSupport.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/AssumptionCache.h"
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/Analysis/ScalarEvolution.h"
 #include "llvm/Analysis/ScalarEvolutionExpander.h"
 #include "llvm/Analysis/TargetTransformInfo.h"
 #include "llvm/CodeGen/Passes.h"
 #include "llvm/CodeGen/TargetPassConfig.h"
 #include "llvm/IR/BasicBlock.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/IRBuilder.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/IntrinsicInst.h"
 #include "llvm/IR/Value.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Transforms/Scalar.h"
-#include "llvm/Transforms/Utils.h"
 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
 #include "llvm/Transforms/Utils/Local.h"
-#include "llvm/Transforms/Utils/LoopUtils.h"
 
 #define DEBUG_TYPE "hardware-loops"
 
 #define HW_LOOPS_NAME "Hardware Loop Insertion"
 
 using namespace llvm;
 
 static cl::opt<bool>
public:
     bool TryConvertLoop(HardwareLoopInfo &HWLoopInfo);
 
   private:
     ScalarEvolution *SE = nullptr;
     LoopInfo *LI = nullptr;
     const DataLayout *DL = nullptr;
     const TargetTransformInfo *TTI = nullptr;
     DominatorTree *DT = nullptr;
-    bool PreserveLCSSA = false;
     AssumptionCache *AC = nullptr;
     TargetLibraryInfo *LibInfo = nullptr;
     Module *M = nullptr;
     bool MadeChange = false;
   };
 
   class HardwareLoop {
     // Expand the trip count scev into a value that we can use.
bool HardwareLoops::runOnFunction(Function &F) {
 
   LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
   SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
   DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
   TTI = &getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
   DL = &F.getParent()->getDataLayout();
   auto *TLIP = getAnalysisIfAvailable<TargetLibraryInfoWrapperPass>();
   LibInfo = TLIP ? &TLIP->getTLI() : nullptr;
-  PreserveLCSSA = mustPreserveAnalysisID(LCSSAID);
   AC = &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
   M = F.getParent();
 
   for (LoopInfo::iterator I = LI->begin(), E = LI->end(); I != E; ++I) {
     Loop *L = *I;
     if (!L->getParentLoop())
       TryConvertLoop(L);
   }
if (TTI->isHardwareLoopProfitable(L, *SE, *AC, LibInfo, HWLoopInfo) ||
     return MadeChange && (!HWLoopInfo.IsNestingLegal && !ForceNestedLoop);
   }
 
   return false;
 }
 
 bool HardwareLoops::TryConvertLoop(HardwareLoopInfo &HWLoopInfo) {
 
-  Loop *L = HWLoopInfo.L;
-  LLVM_DEBUG(dbgs() << "HWLoops: Try to convert profitable loop: " << *L);
+  LLVM_DEBUG(dbgs() << "HWLoops: Try to convert profitable loop: "
+                    << *HWLoopInfo.L);
 
   if (!HWLoopInfo.isHardwareLoopCandidate(*SE, *LI, *DT, ForceNestedLoop,
-                                          ForceHardwareLoopPHI))
+                                          ForceHardwareLoopPHI,
+                                          ForceGuardLoopEntry))
     return false;
 
   assert(
       (HWLoopInfo.ExitBlock && HWLoopInfo.ExitBranch && HWLoopInfo.ExitCount) &&
       "Hardware Loop must have set exit info.");
 
-  BasicBlock *Preheader = L->getLoopPreheader();
-
-  // If we don't have a preheader, then insert one.
-  if (!Preheader)
-    Preheader = InsertPreheaderForLoop(L, DT, LI, nullptr, PreserveLCSSA);
-  if (!Preheader)
-    return false;
-
+  // Now start to converting...
   HardwareLoop HWLoop(HWLoopInfo, *SE, *DL);
   HWLoop.Create();
   ++NumHWLoops;
   return true;
 }
 
 void HardwareLoop::Create() {
   LLVM_DEBUG(dbgs() << "HWLoops: Converting loop..\n");
- 
   Value *LoopCountInit = InitLoopCount();
-  if (!LoopCountInit)
-    return;
+
+  assert(LoopCountInit && "Hardware Loop must have a loop count");
 
   InsertIterationSetup(LoopCountInit);
 
   if (UsePHICounter || ForceHardwareLoopPHI) {
     Instruction *LoopDec = InsertLoopRegDec(LoopCountInit);
     Value *EltsRem = InsertPHICounter(LoopCountInit, LoopDec);
     LoopDec->setOperand(0, EltsRem);
     UpdateBranch(LoopDec);

 }
 
 Value *HardwareLoop::InitLoopCount() {
   LLVM_DEBUG(dbgs() << "HWLoops: Initialising loop counter value:\n");
   // Can we replace a conditional branch with an intrinsic that sets the
   // loop counter and tests that is not zero?
 
   SCEVExpander SCEVE(SE, DL, "loopcnt");
-  if (!ExitCount->getType()->isPointerTy() &&
-      ExitCount->getType() != CountType)
-    ExitCount = SE.getZeroExtendExpr(ExitCount, CountType);
-
-  ExitCount = SE.getAddExpr(ExitCount, SE.getOne(CountType));
 
   // If we're trying to use the 'test and set' form of the intrinsic, we need
   // to replace a conditional branch that is controlling entry to the loop. It
   // is likely (guaranteed?) that the preheader has an unconditional branch to
   // the loop header, so also check if it has a single predecessor.
   if (SE.isLoopEntryGuardedByCond(L, ICmpInst::ICMP_NE, ExitCount,
-                                  SE.getZero(ExitCount->getType()))) {
-    LLVM_DEBUG(dbgs() << " - Attempting to use test.set counter.\n");
+                                  SE.getZero(ExitCount->getType())))
     UseLoopGuard |= ForceGuardLoopEntry;
-  } else
+  else
     UseLoopGuard = false;
   
   BasicBlock *BB = L->getLoopPreheader();
   if (UseLoopGuard && BB->getSinglePredecessor() &&
-      cast<BranchInst>(BB->getTerminator())->isUnconditional())
+      cast<BranchInst>(BB->getTerminator())->isUnconditional()) {
+    LLVM_DEBUG(dbgs() << " - Attempting to use test.set counter.\n");
     BB = BB->getSinglePredecessor();
-
-  if (!isSafeToExpandAt(ExitCount, BB->getTerminator(), SE)) {
-    LLVM_DEBUG(dbgs() << "- Bailing, unsafe to expand ExitCount "
-               << *ExitCount << "\n");
-    return nullptr;
   }
 
   Value *Count = SCEVE.expandCodeFor(ExitCount, CountType,
                                      BB->getTerminator());
 
   // FIXME: We've expanded Count where we hope to insert the counter setting
   // intrinsic. But, in the case of the 'test and set' form, we may fallback to
   // the just 'set' form and in which case the insertion block is most likely