[PowerPC] Check if the pre-increment preparations have already been made so that they are not done twice

[stefanp]

Summary

Preparations to use the per-increment are sometimes done in the target independent pass Loop Strength Reduction.
We try to detect them in the PowerPC specific pass so that they are not done twice and so that we do not add PHIs that are not required.

[hfinkel]

lib/Target/PowerPC/PPCLoopPreIncPrep.cpp

186

Please add a comment here explaining what this function is doing.

189

Local variables start with a capital letter (here and a bunch of places below).

203

Extra spaces inside parens.

212

I don't believe that getSCEVAtScope can return nullptr.

219

This can't be null.

223

Indentation looks odd here (you might try running clang-format over the patch).

234

This phrasing is confusing (it sounds like you're saying that the start and the increment are identical to each other).

417

Space after if.

[stefanp]

Updated based on comments from Hal Finkel.

[hfinkel]

lib/Target/PowerPC/PPCLoopPreIncPrep.cpp

65

How about "PHI node already in pre-increment form" (no period at the end).

193

Remove this variable, it is not needed (and see comment below).

206

Extra spaces inside < >.

207

Please be consistent in capitalization. PHI is more common in LLVM than Phi, and we use PHI already in this source file. Make this PHIInter and so on.

235

FoundPHI is not needed. Instead of setting FoundPHI to true here, you can just

++PHINodeAlreadyExists;
return true;

[stefanp]

Update based on comments from Hal.

[hfinkel]

LGTM

lib/Target/PowerPC/PPCLoopPreIncPrep.cpp

 
 #include "PPC.h"
 #include "PPCSubtarget.h"
 #include "PPCTargetMachine.h"
 #include "llvm/ADT/DepthFirstIterator.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallSet.h"
 #include "llvm/ADT/SmallVector.h"
+#include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/Analysis/ScalarEvolution.h"
 #include "llvm/Analysis/ScalarEvolutionExpander.h"
 #include "llvm/Analysis/ScalarEvolutionExpressions.h"
 #include "llvm/IR/BasicBlock.h"
 #include "llvm/IR/CFG.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/Instruction.h"

 using namespace llvm;
 
 // By default, we limit this to creating 16 PHIs (which is a little over half
 // of the allocatable register set).
 static cl::opt<unsigned> MaxVars("ppc-preinc-prep-max-vars",
                                  cl::Hidden, cl::init(16),
   cl::desc("Potential PHI threshold for PPC preinc loop prep"));
 
+STATISTIC(PHINodeAlreadyExists, "The PHI Node already exists.");
+
 namespace llvm {
 
   void initializePPCLoopPreIncPrepPass(PassRegistry&);
 
 } // end namespace llvm
 
 namespace {
 
public:
 
     void getAnalysisUsage(AnalysisUsage &AU) const override {
       AU.addPreserved<DominatorTreeWrapperPass>();
       AU.addRequired<LoopInfoWrapperPass>();
       AU.addPreserved<LoopInfoWrapperPass>();
       AU.addRequired<ScalarEvolutionWrapperPass>();
     }
 
+    bool alreadyPrepared(Loop *L, Instruction* MemI,
+                         const SCEV *BasePtrStartSCEV,
+                         const SCEVConstant *BasePtrIncSCEV);
     bool runOnFunction(Function &F) override;
 
     bool runOnLoop(Loop *L);
     void simplifyLoopLatch(Loop *L);
     bool rotateLoop(Loop *L);
 
   private:
     PPCTargetMachine *TM = nullptr;
bool PPCLoopPreIncPrep::runOnFunction(Function &F) {
 
   for (auto I = LI->begin(), IE = LI->end(); I != IE; ++I)
     for (auto L = df_begin(*I), LE = df_end(*I); L != LE; ++L)
       MadeChange |= runOnLoop(*L);
 
   return MadeChange;
 }
 
+bool PPCLoopPreIncPrep::alreadyPrepared(Loop *L, Instruction* MemI,
+                                        const SCEV *BasePtrStartSCEV,
+                                        const SCEVConstant *BasePtrIncSCEV) {
+  bool foundPHI = false;
+
+  BasicBlock *BB = MemI->getParent();
+  if (!BB)
+    return foundPHI;
+
+  BasicBlock *predBB = L->getLoopPredecessor();
+  BasicBlock *latchBB = L->getLoopLatch();
+
+  if (!predBB || !latchBB)
+    return foundPHI;
+
+  // Run through the PHIs and see if we have some that looks like a preparation
+  iterator_range< BasicBlock::phi_iterator > phi_iter = BB->phis();
+  for ( auto & currentPhi : phi_iter ) {
+    PHINode *phiNode = dyn_cast<PHINode>(&currentPhi);
+    if (!phiNode)
+      continue;
+
+    if (!SE->isSCEVable(phiNode->getType()))
+      continue;
+
+    const SCEV *phiSCEV = SE->getSCEVAtScope(phiNode, L);
+    if (!phiSCEV)
+      continue;
+
+    const SCEVAddRecExpr *phiBasePtrSCEV = dyn_cast<SCEVAddRecExpr>(phiSCEV);
+    if (!phiBasePtrSCEV)
+      continue;
+
+    if (!phiBasePtrSCEV->getStart())
+      continue;
+
+    const SCEVConstant *phiBasePtrIncSCEV =
+    dyn_cast<SCEVConstant>(phiBasePtrSCEV->getStepRecurrence(*SE));
+    if (!phiBasePtrIncSCEV)
+      continue;
+
+    if (phiNode->getNumIncomingValues() == 2) {
+      if ( (phiNode->getIncomingBlock(0) == latchBB &&
+            phiNode->getIncomingBlock(1) == predBB) ||
+            (phiNode->getIncomingBlock(1) == latchBB &&
+            phiNode->getIncomingBlock(0) == predBB) ) {
+        if (phiBasePtrSCEV->getStart() == BasePtrStartSCEV &&
+            phiBasePtrIncSCEV == BasePtrIncSCEV) {
+          // Both the start and the increment are identical.
+          foundPHI = true;
+        }
+      }
+    }
+  }
+
+  if (foundPHI)
+    PHINodeAlreadyExists++;
+
+  return foundPHI;
+}
+
 bool PPCLoopPreIncPrep::runOnLoop(Loop *L) {
   bool MadeChange = false;
 
   // Only prep. the inner-most loop
   if (!L->empty())
     return MadeChange;
 
   DEBUG(dbgs() << "PIP: Examining: " << *L << "\n");
for (unsigned i = 0, e = Buckets.size(); i != e; ++i) {
     if (!BasePtrIncSCEV)
       continue;
     BasePtrStartSCEV = SE->getMinusSCEV(BasePtrStartSCEV, BasePtrIncSCEV);
     if (!isSafeToExpand(BasePtrStartSCEV, *SE))
       continue;
 
     DEBUG(dbgs() << "PIP: New start is: " << *BasePtrStartSCEV << "\n");
 
+    if(alreadyPrepared(L, MemI, BasePtrStartSCEV, BasePtrIncSCEV))
+      continue;
+
     PHINode *NewPHI = PHINode::Create(I8PtrTy, HeaderLoopPredCount,
       MemI->hasName() ? MemI->getName() + ".phi" : "",
       Header->getFirstNonPHI());
 
     SCEVExpander SCEVE(*SE, Header->getModule()->getDataLayout(), "pistart");
     Value *BasePtrStart = SCEVE.expandCodeFor(BasePtrStartSCEV, I8PtrTy,
       LoopPredecessor->getTerminator());
 

test/CodeGen/PowerPC/ppc64-pre-inc-no-extra-phi.ll

+; RUN: llc < %s -mtriple=powerpc64le-unknown-linux-gnu -mcpu=pwr9 -verify-machineinstrs | FileCheck %s
+; RUN: llc < %s -mtriple=powerpc64-unknown-linux-gnu -mcpu=pwr9 -verify-machineinstrs | FileCheck %s
+; RUN: llc < %s -mtriple=powerpc64le-unknown-linux-gnu -mcpu=pwr8 -verify-machineinstrs | FileCheck %s
+; RUN: llc < %s -mtriple=powerpc64-unknown-linux-gnu -mcpu=pwr8 -verify-machineinstrs | FileCheck %s
+
+@perm = common local_unnamed_addr global [100 x i64] zeroinitializer, align 8
+
+define void @sort_basket() local_unnamed_addr {
+entry:
+  br label %while.cond
+
+while.cond:
+  %l.0 = phi i64 [ 0, %entry ], [ %inc, %while.cond ]
+  %arrayidx = getelementptr inbounds [100 x i64], [100 x i64]* @perm, i64 0, i64 %l.0
+  %0 = load i64, i64* %arrayidx, align 8
+  %cmp = icmp sgt i64 %0, 0
+  %inc = add nuw nsw i64 %l.0, 1
+  br i1 %cmp, label %while.cond, label %while.end
+
+while.end:
+  store i64 0, i64* %arrayidx, align 8
+  ret void
+; CHECK-LABEL: sort_basket
+; CHECK: addi {{[0-9]+}}, {{[0-9]+}}, -8
+; CHECK-NOT: addi {{[0-9]+}}, {{[0-9]+}}, 8
+; CHECK: ldu {{[0-9]+}}, 8({{[0-9]+}})
+; CHECK-NOT: addi {{[0-9]+}}, {{[0-9]+}}, 8
+; CHECK: blr
+}
+