[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 ↗

(On Diff #111153)

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

189 ↗

(On Diff #111153)

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

203 ↗

(On Diff #111153)

Extra spaces inside parens.

212 ↗

(On Diff #111153)

I don't believe that getSCEVAtScope can return nullptr.

219 ↗

(On Diff #111153)

This can't be null.

223 ↗

(On Diff #111153)

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

234 ↗

(On Diff #111153)

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

417 ↗

(On Diff #111153)

Space after if.

[stefanp]

Updated based on comments from Hal Finkel.

[hfinkel]

lib/Target/PowerPC/PPCLoopPreIncPrep.cpp

65 ↗

(On Diff #111389)

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

193 ↗

(On Diff #111389)

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

206 ↗

(On Diff #111389)

Extra spaces inside < >.

207 ↗

(On Diff #111389)

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 ↗

(On Diff #111389)

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

llvm/trunk/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, "PHI node already in pre-increment form");
+
 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;
 }
 
+// In order to prepare for the pre-increment a PHI is added.
+// This function will check to see if that PHI already exists and will return
+//  true if it found an existing PHI with the same start and increment as the
+//  one we wanted to create.
+bool PPCLoopPreIncPrep::alreadyPrepared(Loop *L, Instruction* MemI,
+                                        const SCEV *BasePtrStartSCEV,
+                                        const SCEVConstant *BasePtrIncSCEV) {
+  BasicBlock *BB = MemI->getParent();
+  if (!BB)
+    return false;
+
+  BasicBlock *PredBB = L->getLoopPredecessor();
+  BasicBlock *LatchBB = L->getLoopLatch();
+
+  if (!PredBB || !LatchBB)
+    return false;
+
+  // Run through the PHIs and see if we have some that looks like a preparation
+  iterator_range<BasicBlock::phi_iterator> PHIIter = BB->phis();
+  for (auto & CurrentPHI : PHIIter) {
+    PHINode *CurrentPHINode = dyn_cast<PHINode>(&CurrentPHI);
+    if (!CurrentPHINode)
+      continue;
+
+    if (!SE->isSCEVable(CurrentPHINode->getType()))
+      continue;
+
+    const SCEV *PHISCEV = SE->getSCEVAtScope(CurrentPHINode, L);
+
+    const SCEVAddRecExpr *PHIBasePtrSCEV = dyn_cast<SCEVAddRecExpr>(PHISCEV);
+    if (!PHIBasePtrSCEV)
+      continue;
+
+    const SCEVConstant *PHIBasePtrIncSCEV =
+      dyn_cast<SCEVConstant>(PHIBasePtrSCEV->getStepRecurrence(*SE));
+    if (!PHIBasePtrIncSCEV)
+      continue;
+
+    if (CurrentPHINode->getNumIncomingValues() == 2) {
+      if ( (CurrentPHINode->getIncomingBlock(0) == LatchBB &&
+            CurrentPHINode->getIncomingBlock(1) == PredBB) ||
+            (CurrentPHINode->getIncomingBlock(1) == LatchBB &&
+            CurrentPHINode->getIncomingBlock(0) == PredBB) ) {
+        if (PHIBasePtrSCEV->getStart() == BasePtrStartSCEV &&
+            PHIBasePtrIncSCEV == BasePtrIncSCEV) {
+          // The existing PHI (CurrentPHINode) has the same start and increment
+          //  as the PHI that we wanted to create.
+          ++PHINodeAlreadyExists;
+          return true;
+        }
+      }
+    }
+  }
+  return false;
+}
+
 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());
 

llvm/trunk/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
+}
+