[PowerPC] [NFC] rename PPCLoopPreIncPrep.cpp to PPCLoopInstrFormPrep.cpp after D67088

[shchenz]

Summary

This is NFC code clean work after D67088. In that patch, we extend loop instructions prep for ds/dq form.

This patch only changes the file name PPCLoopPreIncPrep.cpp to PPCLoopInstrFormPrep.cpp for better reviewing of the content change of file PPCLoopInstrFormPrep.cpp.

[jsji]

No sure how you create the patch and review, but the patch still DOES NOT look right. So I create https://reviews.llvm.org/D70716, you can see that the diff is showing as move V there now.

Please review it there. Thanks.

[shchenz]

is it caused by the way I sent out the review? I git mv the file, git diff to get diff patch and upload the diff patch here. Not sure which step is wrong. I will abandon this patch.

[jsji]

In D70704#1760907, @shchenz wrote:

is it caused by the way I sent out the review? I git mv the file, git diff to get diff patch and upload the diff patch here. Not sure which step is wrong. I will abandon this patch.

I believe it is git diff you use that cause problem. You should use git format-patch.

llvm/lib/Target/PowerPC/CMakeLists.txt

add_llvm_target(PowerPCCodeGen
   PPCCTRLoops.cpp
   PPCHazardRecognizers.cpp
   PPCInstrInfo.cpp
   PPCISelDAGToDAG.cpp
   PPCISelLowering.cpp
   PPCEarlyReturn.cpp
   PPCFastISel.cpp
   PPCFrameLowering.cpp
-  PPCLoopPreIncPrep.cpp
+  PPCLoopInstrFormPrep.cpp
   PPCMCInstLower.cpp
   PPCMachineFunctionInfo.cpp
   PPCMachineScheduler.cpp
   PPCMIPeephole.cpp
   PPCRegisterInfo.cpp
   PPCQPXLoadSplat.cpp
   PPCSubtarget.cpp
   PPCTargetMachine.cpp

llvm/lib/Target/PowerPC/PPCLoopInstrFormPrep.cpp

+//===------ PPCLoopPreIncPrep.cpp - Loop Pre-Inc. AM Prep. Pass -----------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// This file implements a pass to prepare loops for ppc preferred addressing
+// modes, leveraging different instruction form. (eg: DS/DQ form, D/DS form with
+// update)
+// Additional PHIs are created for loop induction variables used by load/store
+// instructions so that preferred addressing modes can be used.
+//
+// 1: DS/DQ form preparation, prepare the load/store instructions so that they
+//    can satisfy the DS/DQ form displacement requirements.
+//    Generically, this means transforming loops like this:
+//    for (int i = 0; i < n; ++i) {
+//      unsigned long x1 = *(unsigned long *)(p + i + 5);
+//      unsigned long x2 = *(unsigned long *)(p + i + 9);
+//    }
+//
+//    to look like this:
+//
+//    unsigned NewP = p + 5;
+//    for (int i = 0; i < n; ++i) {
+//      unsigned long x1 = *(unsigned long *)(i + NewP);
+//      unsigned long x2 = *(unsigned long *)(i + NewP + 4);
+//    }
+//
+// 2: D/DS form with update preparation, prepare the load/store instructions so
+//    that we can use update form to do pre-increment.
+//    Generically, this means transforming loops like this:
+//    for (int i = 0; i < n; ++i)
+//      array[i] = c;
+//
+//    to look like this:
+//
+//    T *p = array[-1];
+//    for (int i = 0; i < n; ++i)
+//      *++p = c;
+//===----------------------------------------------------------------------===//
+
+#define DEBUG_TYPE "ppc-loop-preinc-prep"
+
+#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"
+#include "llvm/IR/Instructions.h"
+#include "llvm/IR/IntrinsicInst.h"
+#include "llvm/IR/Module.h"
+#include "llvm/IR/Type.h"
+#include "llvm/IR/Value.h"
+#include "llvm/InitializePasses.h"
+#include "llvm/Pass.h"
+#include "llvm/Support/Casting.h"
+#include "llvm/Support/CommandLine.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"
+#include <cassert>
+#include <iterator>
+#include <utility>
+
+using namespace llvm;
+
+// By default, we limit this to creating 16 common bases out of loops per
+// function. 16 is a little over half of the allocatable register set.
+static cl::opt<unsigned> MaxVarsPrep("ppc-formprep-max-vars",
+                                 cl::Hidden, cl::init(16),
+  cl::desc("Potential common base number threshold per function for PPC loop "
+           "prep"));
+
+static cl::opt<bool> PreferUpdateForm("ppc-formprep-prefer-update",
+                                 cl::init(true), cl::Hidden,
+  cl::desc("prefer update form when ds form is also a update form"));
+
+// Sum of following 3 per loop thresholds for all loops can not be larger
+// than MaxVarsPrep.
+// By default, we limit this to creating 9 PHIs for one loop.
+// 9 and 3 for each kind prep are exterimental values on Power9.
+static cl::opt<unsigned> MaxVarsUpdateForm("ppc-preinc-prep-max-vars",
+                                 cl::Hidden, cl::init(3),
+  cl::desc("Potential PHI threshold per loop for PPC loop prep of update "
+           "form"));
+
+static cl::opt<unsigned> MaxVarsDSForm("ppc-dsprep-max-vars",
+                                 cl::Hidden, cl::init(3),
+  cl::desc("Potential PHI threshold per loop for PPC loop prep of DS form"));
+
+static cl::opt<unsigned> MaxVarsDQForm("ppc-dqprep-max-vars",
+                                 cl::Hidden, cl::init(3),
+  cl::desc("Potential PHI threshold per loop for PPC loop prep of DQ form"));
+
+
+// If would not be profitable if the common base has only one load/store, ISEL
+// should already be able to choose best load/store form based on offset for
+// single load/store. Set minimal profitable value default to 2 and make it as
+// an option.
+static cl::opt<unsigned> DispFormPrepMinThreshold("ppc-dispprep-min-threshold",
+                                    cl::Hidden, cl::init(2),
+  cl::desc("Minimal common base load/store instructions triggering DS/DQ form "
+           "preparation"));
+
+STATISTIC(PHINodeAlreadyExistsUpdate, "PHI node already in pre-increment form");
+STATISTIC(PHINodeAlreadyExistsDS, "PHI node already in DS form");
+STATISTIC(PHINodeAlreadyExistsDQ, "PHI node already in DQ form");
+STATISTIC(DSFormChainRewritten, "Num of DS form chain rewritten");
+STATISTIC(DQFormChainRewritten, "Num of DQ form chain rewritten");
+STATISTIC(UpdFormChainRewritten, "Num of update form chain rewritten");
+
+namespace {
+  struct BucketElement {
+    BucketElement(const SCEVConstant *O, Instruction *I) : Offset(O), Instr(I) {}
+    BucketElement(Instruction *I) : Offset(nullptr), Instr(I) {}
+
+    const SCEVConstant *Offset;
+    Instruction *Instr;
+  };
+
+  struct Bucket {
+    Bucket(const SCEV *B, Instruction *I) : BaseSCEV(B),
+                                            Elements(1, BucketElement(I)) {}
+
+    const SCEV *BaseSCEV;
+    SmallVector<BucketElement, 16> Elements;
+  };
+
+  // "UpdateForm" is not a real PPC instruction form, it stands for dform
+  // load/store with update like ldu/stdu, or Prefetch intrinsic.
+  // For DS form instructions, their displacements must be multiple of 4.
+  // For DQ form instructions, their displacements must be multiple of 16.
+  enum InstrForm { UpdateForm = 1, DSForm = 4, DQForm = 16 };
+
+  class PPCLoopPreIncPrep : public FunctionPass {
+  public:
+    static char ID; // Pass ID, replacement for typeid
+
+    PPCLoopPreIncPrep() : FunctionPass(ID) {
+      initializePPCLoopPreIncPrepPass(*PassRegistry::getPassRegistry());
+    }
+
+    PPCLoopPreIncPrep(PPCTargetMachine &TM) : FunctionPass(ID), TM(&TM) {
+      initializePPCLoopPreIncPrepPass(*PassRegistry::getPassRegistry());
+    }
+
+    void getAnalysisUsage(AnalysisUsage &AU) const override {
+      AU.addPreserved<DominatorTreeWrapperPass>();
+      AU.addRequired<LoopInfoWrapperPass>();
+      AU.addPreserved<LoopInfoWrapperPass>();
+      AU.addRequired<ScalarEvolutionWrapperPass>();
+    }
+
+    bool runOnFunction(Function &F) override;
+
+  private:
+    PPCTargetMachine *TM = nullptr;
+    const PPCSubtarget *ST; 
+    DominatorTree *DT;
+    LoopInfo *LI;
+    ScalarEvolution *SE;
+    bool PreserveLCSSA;
+
+    /// Successful preparation number for Update/DS/DQ form in all inner most
+    /// loops. One successful preparation will put one common base out of loop,
+    /// this may leads to register presure like LICM does.
+    /// Make sure total preparation number can be controlled by option.
+    unsigned SuccPrepCount;
+
+    bool runOnLoop(Loop *L);
+
+    /// Check if required PHI node is already exist in Loop \p L.
+    bool alreadyPrepared(Loop *L, Instruction* MemI,
+                         const SCEV *BasePtrStartSCEV,
+                         const SCEVConstant *BasePtrIncSCEV,
+                         InstrForm Form);
+
+    /// Collect condition matched(\p isValidCandidate() returns true)
+    /// candidates in Loop \p L.
+    SmallVector<Bucket, 16>
+    collectCandidates(Loop *L,
+                      std::function<bool(const Instruction *, const Value *)>
+                          isValidCandidate,
+                      unsigned MaxCandidateNum);
+
+    /// Add a candidate to candidates \p Buckets.
+    void addOneCandidate(Instruction *MemI, const SCEV *LSCEV,
+                         SmallVector<Bucket, 16> &Buckets,
+                         unsigned MaxCandidateNum);
+
+    /// Prepare all candidates in \p Buckets for update form.
+    bool updateFormPrep(Loop *L, SmallVector<Bucket, 16> &Buckets);
+
+    /// Prepare all candidates in \p Buckets for displacement form, now for
+    /// ds/dq.
+    bool dispFormPrep(Loop *L, SmallVector<Bucket, 16> &Buckets,
+                      InstrForm Form);
+
+    /// Prepare for one chain \p BucketChain, find the best base element and
+    /// update all other elements in \p BucketChain accordingly.
+    /// \p Form is used to find the best base element.
+    /// If success, best base element must be stored as the first element of
+    /// \p BucketChain.
+    /// Return false if no base element found, otherwise return true.
+    bool prepareBaseForDispFormChain(Bucket &BucketChain,
+                                     InstrForm Form);
+
+    /// Prepare for one chain \p BucketChain, find the best base element and
+    /// update all other elements in \p BucketChain accordingly.
+    /// If success, best base element must be stored as the first element of
+    /// \p BucketChain.
+    /// Return false if no base element found, otherwise return true.
+    bool prepareBaseForUpdateFormChain(Bucket &BucketChain);
+
+    /// Rewrite load/store instructions in \p BucketChain according to
+    /// preparation.
+    bool rewriteLoadStores(Loop *L, Bucket &BucketChain,
+                           SmallSet<BasicBlock *, 16> &BBChanged,
+                           InstrForm Form);
+  };
+
+} // end anonymous namespace
+
+char PPCLoopPreIncPrep::ID = 0;
+static const char *name = "Prepare loop for pre-inc. addressing modes";
+INITIALIZE_PASS_BEGIN(PPCLoopPreIncPrep, DEBUG_TYPE, name, false, false)
+INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
+INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass)
+INITIALIZE_PASS_END(PPCLoopPreIncPrep, DEBUG_TYPE, name, false, false)
+
+static const std::string PHINodeNameSuffix    = ".phi";
+static const std::string CastNodeNameSuffix   = ".cast";
+static const std::string GEPNodeIncNameSuffix = ".inc";
+static const std::string GEPNodeOffNameSuffix = ".off";
+
+FunctionPass *llvm::createPPCLoopPreIncPrepPass(PPCTargetMachine &TM) {
+  return new PPCLoopPreIncPrep(TM);
+}
+
+static bool IsPtrInBounds(Value *BasePtr) {
+  Value *StrippedBasePtr = BasePtr;
+  while (BitCastInst *BC = dyn_cast<BitCastInst>(StrippedBasePtr))
+    StrippedBasePtr = BC->getOperand(0);
+  if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(StrippedBasePtr))
+    return GEP->isInBounds();
+
+  return false;
+}
+
+static std::string getInstrName(const Value *I, const std::string Suffix) {
+  assert(I && "Invalid paramater!");
+  if (I->hasName())
+    return (I->getName() + Suffix).str();
+  else
+    return ""; 
+}
+
+static Value *GetPointerOperand(Value *MemI) {
+  if (LoadInst *LMemI = dyn_cast<LoadInst>(MemI)) {
+    return LMemI->getPointerOperand();
+  } else if (StoreInst *SMemI = dyn_cast<StoreInst>(MemI)) {
+    return SMemI->getPointerOperand();
+  } else if (IntrinsicInst *IMemI = dyn_cast<IntrinsicInst>(MemI)) {
+    if (IMemI->getIntrinsicID() == Intrinsic::prefetch)
+      return IMemI->getArgOperand(0);
+  }
+
+  return nullptr;
+}
+
+bool PPCLoopPreIncPrep::runOnFunction(Function &F) {
+  if (skipFunction(F))
+    return false;
+
+  LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
+  SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
+  auto *DTWP = getAnalysisIfAvailable<DominatorTreeWrapperPass>();
+  DT = DTWP ? &DTWP->getDomTree() : nullptr;
+  PreserveLCSSA = mustPreserveAnalysisID(LCSSAID);
+  ST = TM ? TM->getSubtargetImpl(F) : nullptr;
+  SuccPrepCount = 0;
+
+  bool MadeChange = false;
+
+  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;
+}
+
+void PPCLoopPreIncPrep::addOneCandidate(Instruction *MemI, const SCEV *LSCEV,
+                                        SmallVector<Bucket, 16> &Buckets,
+                                        unsigned MaxCandidateNum) {
+  assert((MemI && GetPointerOperand(MemI)) &&
+         "Candidate should be a memory instruction.");
+  assert(LSCEV && "Invalid SCEV for Ptr value.");
+  bool FoundBucket = false;
+  for (auto &B : Buckets) {
+    const SCEV *Diff = SE->getMinusSCEV(LSCEV, B.BaseSCEV);
+    if (const auto *CDiff = dyn_cast<SCEVConstant>(Diff)) {
+      B.Elements.push_back(BucketElement(CDiff, MemI));
+      FoundBucket = true;
+      break;
+    }
+  }
+
+  if (!FoundBucket) {
+    if (Buckets.size() == MaxCandidateNum)
+      return;
+    Buckets.push_back(Bucket(LSCEV, MemI));
+  }
+}
+
+SmallVector<Bucket, 16> PPCLoopPreIncPrep::collectCandidates(
+    Loop *L,
+    std::function<bool(const Instruction *, const Value *)> isValidCandidate,
+    unsigned MaxCandidateNum) {
+  SmallVector<Bucket, 16> Buckets;
+  for (const auto &BB : L->blocks())
+    for (auto &J : *BB) {
+      Value *PtrValue;
+      Instruction *MemI;
+
+      if (LoadInst *LMemI = dyn_cast<LoadInst>(&J)) {
+        MemI = LMemI;
+        PtrValue = LMemI->getPointerOperand();
+      } else if (StoreInst *SMemI = dyn_cast<StoreInst>(&J)) {
+        MemI = SMemI;
+        PtrValue = SMemI->getPointerOperand();
+      } else if (IntrinsicInst *IMemI = dyn_cast<IntrinsicInst>(&J)) {
+        if (IMemI->getIntrinsicID() == Intrinsic::prefetch) {
+          MemI = IMemI;
+          PtrValue = IMemI->getArgOperand(0);
+        } else continue;
+      } else continue;
+
+      unsigned PtrAddrSpace = PtrValue->getType()->getPointerAddressSpace();
+      if (PtrAddrSpace)
+        continue;
+
+      if (L->isLoopInvariant(PtrValue))
+        continue;
+
+      const SCEV *LSCEV = SE->getSCEVAtScope(PtrValue, L);
+      const SCEVAddRecExpr *LARSCEV = dyn_cast<SCEVAddRecExpr>(LSCEV);
+      if (!LARSCEV || LARSCEV->getLoop() != L)
+        continue;
+
+      if (isValidCandidate(&J, PtrValue))
+        addOneCandidate(MemI, LSCEV, Buckets, MaxCandidateNum);
+    }
+  return Buckets;
+}
+
+bool PPCLoopPreIncPrep::prepareBaseForDispFormChain(Bucket &BucketChain,
+                                                    InstrForm Form) {
+  // RemainderOffsetInfo details:
+  // key:            value of (Offset urem DispConstraint). For DSForm, it can
+  //                 be [0, 4).
+  // first of pair:  the index of first BucketElement whose remainder is equal
+  //                 to key. For key 0, this value must be 0.
+  // second of pair: number of load/stores with the same remainder.
+  DenseMap<unsigned, std::pair<unsigned, unsigned>> RemainderOffsetInfo;
+
+  for (unsigned j = 0, je = BucketChain.Elements.size(); j != je; ++j) {
+    if (!BucketChain.Elements[j].Offset)
+      RemainderOffsetInfo[0] = std::make_pair(0, 1);
+    else {
+      unsigned Remainder =
+          BucketChain.Elements[j].Offset->getAPInt().urem(Form);
+      if (RemainderOffsetInfo.find(Remainder) == RemainderOffsetInfo.end())
+        RemainderOffsetInfo[Remainder] = std::make_pair(j, 1);
+      else
+        RemainderOffsetInfo[Remainder].second++;
+    }
+  }
+  // Currently we choose the most profitable base as the one which has the max
+  // number of load/store with same remainder.
+  // FIXME: adjust the base selection strategy according to load/store offset
+  // distribution.
+  // For example, if we have one candidate chain for DS form preparation, which
+  // contains following load/stores with different remainders:
+  // 1: 10 load/store whose remainder is 1;
+  // 2: 9 load/store whose remainder is 2;
+  // 3: 1 for remainder 3 and 0 for remainder 0; 
+  // Now we will choose the first load/store whose remainder is 1 as base and
+  // adjust all other load/stores according to new base, so we will get 10 DS
+  // form and 10 X form.
+  // But we should be more clever, for this case we could use two bases, one for
+  // remainder 1 and the other for remainder 2, thus we could get 19 DS form and 1
+  // X form.
+  unsigned MaxCountRemainder = 0;
+  for (unsigned j = 0; j < (unsigned)Form; j++)
+    if ((RemainderOffsetInfo.find(j) != RemainderOffsetInfo.end()) &&
+        RemainderOffsetInfo[j].second >
+            RemainderOffsetInfo[MaxCountRemainder].second)
+      MaxCountRemainder = j;
+
+  // Abort when there are too few insts with common base.
+  if (RemainderOffsetInfo[MaxCountRemainder].second < DispFormPrepMinThreshold)
+    return false;
+
+  // If the first value is most profitable, no needed to adjust BucketChain
+  // elements as they are substracted the first value when collecting.
+  if (MaxCountRemainder == 0)
+    return true;
+
+  // Adjust load/store to the new chosen base.
+  const SCEV *Offset =
+      BucketChain.Elements[RemainderOffsetInfo[MaxCountRemainder].first].Offset;
+  BucketChain.BaseSCEV = SE->getAddExpr(BucketChain.BaseSCEV, Offset);
+  for (auto &E : BucketChain.Elements) {
+    if (E.Offset)
+      E.Offset = cast<SCEVConstant>(SE->getMinusSCEV(E.Offset, Offset));
+    else
+      E.Offset = cast<SCEVConstant>(SE->getNegativeSCEV(Offset));
+  }
+
+  std::swap(BucketChain.Elements[RemainderOffsetInfo[MaxCountRemainder].first],
+            BucketChain.Elements[0]);
+  return true;
+}
+
+// FIXME: implement a more clever base choosing policy.
+// Currently we always choose an exist load/store offset. This maybe lead to
+// suboptimal code sequences. For example, for one DS chain with offsets
+// {-32769, 2003, 2007, 2011}, we choose -32769 as base offset, and left disp
+// for load/stores are {0, 34772, 34776, 34780}. Though each offset now is a
+// multipler of 4, it cannot be represented by sint16.
+bool PPCLoopPreIncPrep::prepareBaseForUpdateFormChain(Bucket &BucketChain) {
+  // We have a choice now of which instruction's memory operand we use as the
+  // base for the generated PHI. Always picking the first instruction in each
+  // bucket does not work well, specifically because that instruction might
+  // be a prefetch (and there are no pre-increment dcbt variants). Otherwise,
+  // the choice is somewhat arbitrary, because the backend will happily
+  // generate direct offsets from both the pre-incremented and
+  // post-incremented pointer values. Thus, we'll pick the first non-prefetch
+  // instruction in each bucket, and adjust the recurrence and other offsets
+  // accordingly.
+  for (int j = 0, je = BucketChain.Elements.size(); j != je; ++j) {
+    if (auto *II = dyn_cast<IntrinsicInst>(BucketChain.Elements[j].Instr))
+      if (II->getIntrinsicID() == Intrinsic::prefetch)
+        continue;
+
+    // If we'd otherwise pick the first element anyway, there's nothing to do.
+    if (j == 0)
+      break;
+
+    // If our chosen element has no offset from the base pointer, there's
+    // nothing to do.
+    if (!BucketChain.Elements[j].Offset ||
+        BucketChain.Elements[j].Offset->isZero())
+      break;
+
+    const SCEV *Offset = BucketChain.Elements[j].Offset;
+    BucketChain.BaseSCEV = SE->getAddExpr(BucketChain.BaseSCEV, Offset);
+    for (auto &E : BucketChain.Elements) {
+      if (E.Offset)
+        E.Offset = cast<SCEVConstant>(SE->getMinusSCEV(E.Offset, Offset));
+      else
+        E.Offset = cast<SCEVConstant>(SE->getNegativeSCEV(Offset));
+    }
+
+    std::swap(BucketChain.Elements[j], BucketChain.Elements[0]);
+    break;
+  }
+  return true;
+}
+
+bool PPCLoopPreIncPrep::rewriteLoadStores(Loop *L, Bucket &BucketChain,
+                                          SmallSet<BasicBlock *, 16> &BBChanged,
+                                          InstrForm Form) {
+  bool MadeChange = false;
+  const SCEVAddRecExpr *BasePtrSCEV =
+      cast<SCEVAddRecExpr>(BucketChain.BaseSCEV);
+  if (!BasePtrSCEV->isAffine())
+    return MadeChange;
+
+  LLVM_DEBUG(dbgs() << "PIP: Transforming: " << *BasePtrSCEV << "\n");
+
+  assert(BasePtrSCEV->getLoop() == L && "AddRec for the wrong loop?");
+
+  // The instruction corresponding to the Bucket's BaseSCEV must be the first
+  // in the vector of elements.
+  Instruction *MemI = BucketChain.Elements.begin()->Instr;
+  Value *BasePtr = GetPointerOperand(MemI);
+  assert(BasePtr && "No pointer operand");
+
+  Type *I8Ty = Type::getInt8Ty(MemI->getParent()->getContext());
+  Type *I8PtrTy = Type::getInt8PtrTy(MemI->getParent()->getContext(),
+    BasePtr->getType()->getPointerAddressSpace());
+
+  if (!SE->isLoopInvariant(BasePtrSCEV->getStart(), L))
+    return MadeChange;
+
+  const SCEVConstant *BasePtrIncSCEV =
+    dyn_cast<SCEVConstant>(BasePtrSCEV->getStepRecurrence(*SE));
+  if (!BasePtrIncSCEV)
+    return MadeChange;
+
+  // For some DS form load/store instructions, it can also be an update form,
+  // if the stride is a multipler of 4. Use update form if prefer it.
+  bool CanPreInc = (Form == UpdateForm ||
+                    ((Form == DSForm) && !BasePtrIncSCEV->getAPInt().urem(4) &&
+                     PreferUpdateForm));
+  const SCEV *BasePtrStartSCEV = nullptr;
+  if (CanPreInc)
+    BasePtrStartSCEV =
+        SE->getMinusSCEV(BasePtrSCEV->getStart(), BasePtrIncSCEV);
+  else
+    BasePtrStartSCEV = BasePtrSCEV->getStart();
+
+  if (!isSafeToExpand(BasePtrStartSCEV, *SE))
+    return MadeChange;
+
+  if (alreadyPrepared(L, MemI, BasePtrStartSCEV, BasePtrIncSCEV, Form))
+    return MadeChange;
+
+  LLVM_DEBUG(dbgs() << "PIP: New start is: " << *BasePtrStartSCEV << "\n");
+
+  BasicBlock *Header = L->getHeader();
+  unsigned HeaderLoopPredCount = pred_size(Header);
+  BasicBlock *LoopPredecessor = L->getLoopPredecessor();
+
+  PHINode *NewPHI =
+      PHINode::Create(I8PtrTy, HeaderLoopPredCount,
+                      getInstrName(MemI, PHINodeNameSuffix),
+                      Header->getFirstNonPHI());
+
+  SCEVExpander SCEVE(*SE, Header->getModule()->getDataLayout(), "pistart");
+  Value *BasePtrStart = SCEVE.expandCodeFor(BasePtrStartSCEV, I8PtrTy,
+                                            LoopPredecessor->getTerminator());
+
+  // Note that LoopPredecessor might occur in the predecessor list multiple
+  // times, and we need to add it the right number of times.
+  for (const auto &PI : predecessors(Header)) {
+    if (PI != LoopPredecessor)
+      continue;
+
+    NewPHI->addIncoming(BasePtrStart, LoopPredecessor);
+  }
+
+  Instruction *PtrInc = nullptr;
+  Instruction *NewBasePtr = nullptr;
+  if (CanPreInc) {
+    Instruction *InsPoint = &*Header->getFirstInsertionPt();
+    PtrInc = GetElementPtrInst::Create(
+        I8Ty, NewPHI, BasePtrIncSCEV->getValue(),
+        getInstrName(MemI, GEPNodeIncNameSuffix), InsPoint);
+    cast<GetElementPtrInst>(PtrInc)->setIsInBounds(IsPtrInBounds(BasePtr));
+    for (const auto &PI : predecessors(Header)) {
+      if (PI == LoopPredecessor)
+        continue;
+
+      NewPHI->addIncoming(PtrInc, PI);
+    }
+    if (PtrInc->getType() != BasePtr->getType())
+      NewBasePtr = new BitCastInst(
+          PtrInc, BasePtr->getType(),
+          getInstrName(PtrInc, CastNodeNameSuffix), InsPoint);
+    else
+      NewBasePtr = PtrInc;
+  } else {
+    // Note that LoopPredecessor might occur in the predecessor list multiple
+    // times, and we need to make sure no more incoming value for them in PHI.
+    for (const auto &PI : predecessors(Header)) {
+      if (PI == LoopPredecessor)
+        continue;
+
+      // For the latch predecessor, we need to insert a GEP just before the
+      // terminator to increase the address.
+      BasicBlock *BB = PI;
+      Instruction *InsPoint = BB->getTerminator();
+      PtrInc = GetElementPtrInst::Create(
+          I8Ty, NewPHI, BasePtrIncSCEV->getValue(),
+          getInstrName(MemI, GEPNodeIncNameSuffix), InsPoint);
+
+      cast<GetElementPtrInst>(PtrInc)->setIsInBounds(IsPtrInBounds(BasePtr));
+
+      NewPHI->addIncoming(PtrInc, PI);
+    }
+    PtrInc = NewPHI;
+    if (NewPHI->getType() != BasePtr->getType())
+      NewBasePtr =
+          new BitCastInst(NewPHI, BasePtr->getType(),
+                          getInstrName(NewPHI, CastNodeNameSuffix),
+                          &*Header->getFirstInsertionPt());
+    else
+      NewBasePtr = NewPHI;
+  }
+
+  if (Instruction *IDel = dyn_cast<Instruction>(BasePtr))
+    BBChanged.insert(IDel->getParent());
+  BasePtr->replaceAllUsesWith(NewBasePtr);
+  RecursivelyDeleteTriviallyDeadInstructions(BasePtr);
+
+  // Keep track of the replacement pointer values we've inserted so that we
+  // don't generate more pointer values than necessary.
+  SmallPtrSet<Value *, 16> NewPtrs;
+  NewPtrs.insert(NewBasePtr);
+
+  for (auto I = std::next(BucketChain.Elements.begin()),
+       IE = BucketChain.Elements.end(); I != IE; ++I) {
+    Value *Ptr = GetPointerOperand(I->Instr);
+    assert(Ptr && "No pointer operand");
+    if (NewPtrs.count(Ptr))
+      continue;
+
+    Instruction *RealNewPtr;
+    if (!I->Offset || I->Offset->getValue()->isZero()) {
+      RealNewPtr = NewBasePtr;
+    } else {
+      Instruction *PtrIP = dyn_cast<Instruction>(Ptr);
+      if (PtrIP && isa<Instruction>(NewBasePtr) &&
+          cast<Instruction>(NewBasePtr)->getParent() == PtrIP->getParent())
+        PtrIP = nullptr;
+      else if (PtrIP && isa<PHINode>(PtrIP))
+        PtrIP = &*PtrIP->getParent()->getFirstInsertionPt();
+      else if (!PtrIP)
+        PtrIP = I->Instr;
+
+      GetElementPtrInst *NewPtr = GetElementPtrInst::Create(
+          I8Ty, PtrInc, I->Offset->getValue(),
+          getInstrName(I->Instr, GEPNodeOffNameSuffix), PtrIP);
+      if (!PtrIP)
+        NewPtr->insertAfter(cast<Instruction>(PtrInc));
+      NewPtr->setIsInBounds(IsPtrInBounds(Ptr));
+      RealNewPtr = NewPtr;
+    }
+
+    if (Instruction *IDel = dyn_cast<Instruction>(Ptr))
+      BBChanged.insert(IDel->getParent());
+
+    Instruction *ReplNewPtr;
+    if (Ptr->getType() != RealNewPtr->getType()) {
+      ReplNewPtr = new BitCastInst(RealNewPtr, Ptr->getType(),
+        getInstrName(Ptr, CastNodeNameSuffix));
+      ReplNewPtr->insertAfter(RealNewPtr);
+    } else
+      ReplNewPtr = RealNewPtr;
+
+    Ptr->replaceAllUsesWith(ReplNewPtr);
+    RecursivelyDeleteTriviallyDeadInstructions(Ptr);
+
+    NewPtrs.insert(RealNewPtr);
+  }
+
+  MadeChange = true;
+
+  SuccPrepCount++;  
+
+  if (Form == DSForm && !CanPreInc)
+    DSFormChainRewritten++;
+  else if (Form == DQForm)
+    DQFormChainRewritten++;
+  else if (Form == UpdateForm || (Form == DSForm && CanPreInc))
+    UpdFormChainRewritten++;
+
+  return MadeChange;
+}
+
+bool PPCLoopPreIncPrep::updateFormPrep(Loop *L,
+                                       SmallVector<Bucket, 16> &Buckets) {
+  bool MadeChange = false;
+  if (Buckets.empty())
+    return MadeChange;
+  SmallSet<BasicBlock *, 16> BBChanged;
+  for (auto &Bucket : Buckets)
+    // The base address of each bucket is transformed into a phi and the others
+    // are rewritten based on new base.
+    if (prepareBaseForUpdateFormChain(Bucket))
+      MadeChange |= rewriteLoadStores(L, Bucket, BBChanged, UpdateForm);
+
+  if (MadeChange)
+    for (auto &BB : L->blocks())
+      if (BBChanged.count(BB))
+        DeleteDeadPHIs(BB);
+  return MadeChange;
+}
+
+bool PPCLoopPreIncPrep::dispFormPrep(Loop *L, SmallVector<Bucket, 16> &Buckets,
+                                     InstrForm Form) {
+  bool MadeChange = false;
+
+  if (Buckets.empty())
+    return MadeChange;
+
+  SmallSet<BasicBlock *, 16> BBChanged;
+  for (auto &Bucket : Buckets) {
+    if (Bucket.Elements.size() < DispFormPrepMinThreshold)
+      continue;
+    if (prepareBaseForDispFormChain(Bucket, Form))
+      MadeChange |= rewriteLoadStores(L, Bucket, BBChanged, Form);
+  }
+
+  if (MadeChange)
+    for (auto &BB : L->blocks())
+      if (BBChanged.count(BB))
+        DeleteDeadPHIs(BB);
+  return MadeChange;
+}
+
+// In order to prepare for the preferred instruction form, 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 matched start and increment as the
+// one we wanted to create.
+bool PPCLoopPreIncPrep::alreadyPrepared(Loop *L, Instruction* MemI,
+                                        const SCEV *BasePtrStartSCEV,
+                                        const SCEVConstant *BasePtrIncSCEV,
+                                        InstrForm Form) {
+  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 (PHIBasePtrIncSCEV == BasePtrIncSCEV) {
+          // The existing PHI (CurrentPHINode) has the same start and increment
+          // as the PHI that we wanted to create.
+          if (Form == UpdateForm &&
+              PHIBasePtrSCEV->getStart() == BasePtrStartSCEV) {
+            ++PHINodeAlreadyExistsUpdate;
+            return true;
+          } 
+          if (Form == DSForm || Form == DQForm) {
+            const SCEVConstant *Diff = dyn_cast<SCEVConstant>(
+                SE->getMinusSCEV(PHIBasePtrSCEV->getStart(), BasePtrStartSCEV));
+            if (Diff && !Diff->getAPInt().urem(Form)) {
+              if (Form == DSForm)
+                ++PHINodeAlreadyExistsDS;
+              else
+                ++PHINodeAlreadyExistsDQ;
+              return true;
+            }
+          } 
+        }
+      }
+    }
+  }
+  return false;
+}
+
+bool PPCLoopPreIncPrep::runOnLoop(Loop *L) {
+  bool MadeChange = false;
+
+  // Only prep. the inner-most loop
+  if (!L->empty())
+    return MadeChange;
+
+  // Return if already done enough preparation.
+  if (SuccPrepCount >= MaxVarsPrep)
+    return MadeChange;
+
+  LLVM_DEBUG(dbgs() << "PIP: Examining: " << *L << "\n");
+
+  BasicBlock *LoopPredecessor = L->getLoopPredecessor();
+  // If there is no loop predecessor, or the loop predecessor's terminator
+  // returns a value (which might contribute to determining the loop's
+  // iteration space), insert a new preheader for the loop.
+  if (!LoopPredecessor ||
+      !LoopPredecessor->getTerminator()->getType()->isVoidTy()) {
+    LoopPredecessor = InsertPreheaderForLoop(L, DT, LI, nullptr, PreserveLCSSA);
+    if (LoopPredecessor)
+      MadeChange = true;
+  }
+  if (!LoopPredecessor) {
+    LLVM_DEBUG(dbgs() << "PIP fails since no predecessor for current loop.\n");
+    return MadeChange;
+  }
+  // Check if a load/store has update form. This lambda is used by function
+  // collectCandidates which can collect candidates for types defined by lambda.
+  auto isUpdateFormCandidate = [&] (const Instruction *I,
+                                    const Value *PtrValue) {
+    assert((PtrValue && I) && "Invalid parameter!");
+    // There are no update forms for Altivec vector load/stores.
+    if (ST && ST->hasAltivec() &&
+        PtrValue->getType()->getPointerElementType()->isVectorTy())
+      return false;
+    // See getPreIndexedAddressParts, the displacement for LDU/STDU has to
+    // be 4's multiple (DS-form). For i64 loads/stores when the displacement
+    // fits in a 16-bit signed field but isn't a multiple of 4, it will be
+    // useless and possible to break some original well-form addressing mode
+    // to make this pre-inc prep for it.
+    if (PtrValue->getType()->getPointerElementType()->isIntegerTy(64)) {
+      const SCEV *LSCEV = SE->getSCEVAtScope(const_cast<Value *>(PtrValue), L);
+      const SCEVAddRecExpr *LARSCEV = dyn_cast<SCEVAddRecExpr>(LSCEV);
+      if (!LARSCEV || LARSCEV->getLoop() != L)
+        return false;
+      if (const SCEVConstant *StepConst =
+              dyn_cast<SCEVConstant>(LARSCEV->getStepRecurrence(*SE))) {
+        const APInt &ConstInt = StepConst->getValue()->getValue();
+        if (ConstInt.isSignedIntN(16) && ConstInt.srem(4) != 0)
+          return false;
+      }
+    }
+    return true;
+  };
+  
+  // Check if a load/store has DS form.
+  auto isDSFormCandidate = [] (const Instruction *I, const Value *PtrValue) {
+    assert((PtrValue && I) && "Invalid parameter!");
+    // FIXME: 32 bit instruction lwa is also DS form.
+    return !isa<IntrinsicInst>(I) &&
+           ((PtrValue->getType()->getPointerElementType()->isIntegerTy(64)) ||
+            (PtrValue->getType()->getPointerElementType()->isFloatTy()) ||
+            (PtrValue->getType()->getPointerElementType()->isDoubleTy()));
+  };
+
+  // Check if a load/store has DQ form.
+  auto isDQFormCandidate = [&] (const Instruction *I, const Value *PtrValue) {
+    assert((PtrValue && I) && "Invalid parameter!");
+    return !isa<IntrinsicInst>(I) && ST && ST->hasP9Vector() &&
+           (PtrValue->getType()->getPointerElementType()->isVectorTy());
+  };
+
+  // intrinsic for update form.
+  SmallVector<Bucket, 16> UpdateFormBuckets =
+      collectCandidates(L, isUpdateFormCandidate, MaxVarsUpdateForm);
+
+  // Prepare for update form.
+  if (!UpdateFormBuckets.empty())
+    MadeChange |= updateFormPrep(L, UpdateFormBuckets);
+
+  // Collect buckets of comparable addresses used by loads and stores for DS
+  // form.
+  SmallVector<Bucket, 16> DSFormBuckets =
+      collectCandidates(L, isDSFormCandidate, MaxVarsDSForm);
+
+  // Prepare for DS form.
+  if (!DSFormBuckets.empty())
+    MadeChange |= dispFormPrep(L, DSFormBuckets, DSForm);
+
+  // Collect buckets of comparable addresses used by loads and stores for DQ
+  // form.
+  SmallVector<Bucket, 16> DQFormBuckets =
+      collectCandidates(L, isDQFormCandidate, MaxVarsDQForm);
+
+  // Prepare for DQ form.
+  if (!DQFormBuckets.empty())
+    MadeChange |= dispFormPrep(L, DQFormBuckets, DQForm);
+
+  return MadeChange;
+}

llvm/lib/Target/PowerPC/PPCLoopPreIncPrep.cpp

-//===------ PPCLoopPreIncPrep.cpp - Loop Pre-Inc. AM Prep. Pass -----------===//
-//
-// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
-// See https://llvm.org/LICENSE.txt for license information.
-// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
-//
-//===----------------------------------------------------------------------===//
-//
-// This file implements a pass to prepare loops for ppc preferred addressing
-// modes, leveraging different instruction form. (eg: DS/DQ form, D/DS form with
-// update)
-// Additional PHIs are created for loop induction variables used by load/store
-// instructions so that preferred addressing modes can be used.
-//
-// 1: DS/DQ form preparation, prepare the load/store instructions so that they
-//    can satisfy the DS/DQ form displacement requirements.
-//    Generically, this means transforming loops like this:
-//    for (int i = 0; i < n; ++i) {
-//      unsigned long x1 = *(unsigned long *)(p + i + 5);
-//      unsigned long x2 = *(unsigned long *)(p + i + 9);
-//    }
-//
-//    to look like this:
-//
-//    unsigned NewP = p + 5;
-//    for (int i = 0; i < n; ++i) {
-//      unsigned long x1 = *(unsigned long *)(i + NewP);
-//      unsigned long x2 = *(unsigned long *)(i + NewP + 4);
-//    }
-//
-// 2: D/DS form with update preparation, prepare the load/store instructions so
-//    that we can use update form to do pre-increment.
-//    Generically, this means transforming loops like this:
-//    for (int i = 0; i < n; ++i)
-//      array[i] = c;
-//
-//    to look like this:
-//
-//    T *p = array[-1];
-//    for (int i = 0; i < n; ++i)
-//      *++p = c;
-//===----------------------------------------------------------------------===//
-
-#define DEBUG_TYPE "ppc-loop-preinc-prep"
-
-#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"
-#include "llvm/IR/Instructions.h"
-#include "llvm/IR/IntrinsicInst.h"
-#include "llvm/IR/Module.h"
-#include "llvm/IR/Type.h"
-#include "llvm/IR/Value.h"
-#include "llvm/InitializePasses.h"
-#include "llvm/Pass.h"
-#include "llvm/Support/Casting.h"
-#include "llvm/Support/CommandLine.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"
-#include <cassert>
-#include <iterator>
-#include <utility>
-
-using namespace llvm;
-
-// By default, we limit this to creating 16 common bases out of loops per
-// function. 16 is a little over half of the allocatable register set.
-static cl::opt<unsigned> MaxVarsPrep("ppc-formprep-max-vars",
-                                 cl::Hidden, cl::init(16),
-  cl::desc("Potential common base number threshold per function for PPC loop "
-           "prep"));
-
-static cl::opt<bool> PreferUpdateForm("ppc-formprep-prefer-update",
-                                 cl::init(true), cl::Hidden,
-  cl::desc("prefer update form when ds form is also a update form"));
-
-// Sum of following 3 per loop thresholds for all loops can not be larger
-// than MaxVarsPrep.
-// By default, we limit this to creating 9 PHIs for one loop.
-// 9 and 3 for each kind prep are exterimental values on Power9.
-static cl::opt<unsigned> MaxVarsUpdateForm("ppc-preinc-prep-max-vars",
-                                 cl::Hidden, cl::init(3),
-  cl::desc("Potential PHI threshold per loop for PPC loop prep of update "
-           "form"));
-
-static cl::opt<unsigned> MaxVarsDSForm("ppc-dsprep-max-vars",
-                                 cl::Hidden, cl::init(3),
-  cl::desc("Potential PHI threshold per loop for PPC loop prep of DS form"));
-
-static cl::opt<unsigned> MaxVarsDQForm("ppc-dqprep-max-vars",
-                                 cl::Hidden, cl::init(3),
-  cl::desc("Potential PHI threshold per loop for PPC loop prep of DQ form"));
-
-
-// If would not be profitable if the common base has only one load/store, ISEL
-// should already be able to choose best load/store form based on offset for
-// single load/store. Set minimal profitable value default to 2 and make it as
-// an option.
-static cl::opt<unsigned> DispFormPrepMinThreshold("ppc-dispprep-min-threshold",
-                                    cl::Hidden, cl::init(2),
-  cl::desc("Minimal common base load/store instructions triggering DS/DQ form "
-           "preparation"));
-
-STATISTIC(PHINodeAlreadyExistsUpdate, "PHI node already in pre-increment form");
-STATISTIC(PHINodeAlreadyExistsDS, "PHI node already in DS form");
-STATISTIC(PHINodeAlreadyExistsDQ, "PHI node already in DQ form");
-STATISTIC(DSFormChainRewritten, "Num of DS form chain rewritten");
-STATISTIC(DQFormChainRewritten, "Num of DQ form chain rewritten");
-STATISTIC(UpdFormChainRewritten, "Num of update form chain rewritten");
-
-namespace {
-  struct BucketElement {
-    BucketElement(const SCEVConstant *O, Instruction *I) : Offset(O), Instr(I) {}
-    BucketElement(Instruction *I) : Offset(nullptr), Instr(I) {}
-
-    const SCEVConstant *Offset;
-    Instruction *Instr;
-  };
-
-  struct Bucket {
-    Bucket(const SCEV *B, Instruction *I) : BaseSCEV(B),
-                                            Elements(1, BucketElement(I)) {}
-
-    const SCEV *BaseSCEV;
-    SmallVector<BucketElement, 16> Elements;
-  };
-
-  // "UpdateForm" is not a real PPC instruction form, it stands for dform
-  // load/store with update like ldu/stdu, or Prefetch intrinsic.
-  // For DS form instructions, their displacements must be multiple of 4.
-  // For DQ form instructions, their displacements must be multiple of 16.
-  enum InstrForm { UpdateForm = 1, DSForm = 4, DQForm = 16 };
-
-  class PPCLoopPreIncPrep : public FunctionPass {
-  public:
-    static char ID; // Pass ID, replacement for typeid
-
-    PPCLoopPreIncPrep() : FunctionPass(ID) {
-      initializePPCLoopPreIncPrepPass(*PassRegistry::getPassRegistry());
-    }
-
-    PPCLoopPreIncPrep(PPCTargetMachine &TM) : FunctionPass(ID), TM(&TM) {
-      initializePPCLoopPreIncPrepPass(*PassRegistry::getPassRegistry());
-    }
-
-    void getAnalysisUsage(AnalysisUsage &AU) const override {
-      AU.addPreserved<DominatorTreeWrapperPass>();
-      AU.addRequired<LoopInfoWrapperPass>();
-      AU.addPreserved<LoopInfoWrapperPass>();
-      AU.addRequired<ScalarEvolutionWrapperPass>();
-    }
-
-    bool runOnFunction(Function &F) override;
-
-  private:
-    PPCTargetMachine *TM = nullptr;
-    const PPCSubtarget *ST; 
-    DominatorTree *DT;
-    LoopInfo *LI;
-    ScalarEvolution *SE;
-    bool PreserveLCSSA;
-
-    /// Successful preparation number for Update/DS/DQ form in all inner most
-    /// loops. One successful preparation will put one common base out of loop,
-    /// this may leads to register presure like LICM does.
-    /// Make sure total preparation number can be controlled by option.
-    unsigned SuccPrepCount;
-
-    bool runOnLoop(Loop *L);
-
-    /// Check if required PHI node is already exist in Loop \p L.
-    bool alreadyPrepared(Loop *L, Instruction* MemI,
-                         const SCEV *BasePtrStartSCEV,
-                         const SCEVConstant *BasePtrIncSCEV,
-                         InstrForm Form);
-
-    /// Collect condition matched(\p isValidCandidate() returns true)
-    /// candidates in Loop \p L.
-    SmallVector<Bucket, 16>
-    collectCandidates(Loop *L,
-                      std::function<bool(const Instruction *, const Value *)>
-                          isValidCandidate,
-                      unsigned MaxCandidateNum);
-
-    /// Add a candidate to candidates \p Buckets.
-    void addOneCandidate(Instruction *MemI, const SCEV *LSCEV,
-                         SmallVector<Bucket, 16> &Buckets,
-                         unsigned MaxCandidateNum);
-
-    /// Prepare all candidates in \p Buckets for update form.
-    bool updateFormPrep(Loop *L, SmallVector<Bucket, 16> &Buckets);
-
-    /// Prepare all candidates in \p Buckets for displacement form, now for
-    /// ds/dq.
-    bool dispFormPrep(Loop *L, SmallVector<Bucket, 16> &Buckets,
-                      InstrForm Form);
-
-    /// Prepare for one chain \p BucketChain, find the best base element and
-    /// update all other elements in \p BucketChain accordingly.
-    /// \p Form is used to find the best base element.
-    /// If success, best base element must be stored as the first element of
-    /// \p BucketChain.
-    /// Return false if no base element found, otherwise return true.
-    bool prepareBaseForDispFormChain(Bucket &BucketChain,
-                                     InstrForm Form);
-
-    /// Prepare for one chain \p BucketChain, find the best base element and
-    /// update all other elements in \p BucketChain accordingly.
-    /// If success, best base element must be stored as the first element of
-    /// \p BucketChain.
-    /// Return false if no base element found, otherwise return true.
-    bool prepareBaseForUpdateFormChain(Bucket &BucketChain);
-
-    /// Rewrite load/store instructions in \p BucketChain according to
-    /// preparation.
-    bool rewriteLoadStores(Loop *L, Bucket &BucketChain,
-                           SmallSet<BasicBlock *, 16> &BBChanged,
-                           InstrForm Form);
-  };
-
-} // end anonymous namespace
-
-char PPCLoopPreIncPrep::ID = 0;
-static const char *name = "Prepare loop for pre-inc. addressing modes";
-INITIALIZE_PASS_BEGIN(PPCLoopPreIncPrep, DEBUG_TYPE, name, false, false)
-INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
-INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass)
-INITIALIZE_PASS_END(PPCLoopPreIncPrep, DEBUG_TYPE, name, false, false)
-
-static const std::string PHINodeNameSuffix    = ".phi";
-static const std::string CastNodeNameSuffix   = ".cast";
-static const std::string GEPNodeIncNameSuffix = ".inc";
-static const std::string GEPNodeOffNameSuffix = ".off";
-
-FunctionPass *llvm::createPPCLoopPreIncPrepPass(PPCTargetMachine &TM) {
-  return new PPCLoopPreIncPrep(TM);
-}
-
-static bool IsPtrInBounds(Value *BasePtr) {
-  Value *StrippedBasePtr = BasePtr;
-  while (BitCastInst *BC = dyn_cast<BitCastInst>(StrippedBasePtr))
-    StrippedBasePtr = BC->getOperand(0);
-  if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(StrippedBasePtr))
-    return GEP->isInBounds();
-
-  return false;
-}
-
-static std::string getInstrName(const Value *I, const std::string Suffix) {
-  assert(I && "Invalid paramater!");
-  if (I->hasName())
-    return (I->getName() + Suffix).str();
-  else
-    return ""; 
-}
-
-static Value *GetPointerOperand(Value *MemI) {
-  if (LoadInst *LMemI = dyn_cast<LoadInst>(MemI)) {
-    return LMemI->getPointerOperand();
-  } else if (StoreInst *SMemI = dyn_cast<StoreInst>(MemI)) {
-    return SMemI->getPointerOperand();
-  } else if (IntrinsicInst *IMemI = dyn_cast<IntrinsicInst>(MemI)) {
-    if (IMemI->getIntrinsicID() == Intrinsic::prefetch)
-      return IMemI->getArgOperand(0);
-  }
-
-  return nullptr;
-}
-
-bool PPCLoopPreIncPrep::runOnFunction(Function &F) {
-  if (skipFunction(F))
-    return false;
-
-  LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
-  SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
-  auto *DTWP = getAnalysisIfAvailable<DominatorTreeWrapperPass>();
-  DT = DTWP ? &DTWP->getDomTree() : nullptr;
-  PreserveLCSSA = mustPreserveAnalysisID(LCSSAID);
-  ST = TM ? TM->getSubtargetImpl(F) : nullptr;
-  SuccPrepCount = 0;
-
-  bool MadeChange = false;
-
-  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;
-}
-
-void PPCLoopPreIncPrep::addOneCandidate(Instruction *MemI, const SCEV *LSCEV,
-                                        SmallVector<Bucket, 16> &Buckets,
-                                        unsigned MaxCandidateNum) {
-  assert((MemI && GetPointerOperand(MemI)) &&
-         "Candidate should be a memory instruction.");
-  assert(LSCEV && "Invalid SCEV for Ptr value.");
-  bool FoundBucket = false;
-  for (auto &B : Buckets) {
-    const SCEV *Diff = SE->getMinusSCEV(LSCEV, B.BaseSCEV);
-    if (const auto *CDiff = dyn_cast<SCEVConstant>(Diff)) {
-      B.Elements.push_back(BucketElement(CDiff, MemI));
-      FoundBucket = true;
-      break;
-    }
-  }
-
-  if (!FoundBucket) {
-    if (Buckets.size() == MaxCandidateNum)
-      return;
-    Buckets.push_back(Bucket(LSCEV, MemI));
-  }
-}
-
-SmallVector<Bucket, 16> PPCLoopPreIncPrep::collectCandidates(
-    Loop *L,
-    std::function<bool(const Instruction *, const Value *)> isValidCandidate,
-    unsigned MaxCandidateNum) {
-  SmallVector<Bucket, 16> Buckets;
-  for (const auto &BB : L->blocks())
-    for (auto &J : *BB) {
-      Value *PtrValue;
-      Instruction *MemI;
-
-      if (LoadInst *LMemI = dyn_cast<LoadInst>(&J)) {
-        MemI = LMemI;
-        PtrValue = LMemI->getPointerOperand();
-      } else if (StoreInst *SMemI = dyn_cast<StoreInst>(&J)) {
-        MemI = SMemI;
-        PtrValue = SMemI->getPointerOperand();
-      } else if (IntrinsicInst *IMemI = dyn_cast<IntrinsicInst>(&J)) {
-        if (IMemI->getIntrinsicID() == Intrinsic::prefetch) {
-          MemI = IMemI;
-          PtrValue = IMemI->getArgOperand(0);
-        } else continue;
-      } else continue;
-
-      unsigned PtrAddrSpace = PtrValue->getType()->getPointerAddressSpace();
-      if (PtrAddrSpace)
-        continue;
-
-      if (L->isLoopInvariant(PtrValue))
-        continue;
-
-      const SCEV *LSCEV = SE->getSCEVAtScope(PtrValue, L);
-      const SCEVAddRecExpr *LARSCEV = dyn_cast<SCEVAddRecExpr>(LSCEV);
-      if (!LARSCEV || LARSCEV->getLoop() != L)
-        continue;
-
-      if (isValidCandidate(&J, PtrValue))
-        addOneCandidate(MemI, LSCEV, Buckets, MaxCandidateNum);
-    }
-  return Buckets;
-}
-
-bool PPCLoopPreIncPrep::prepareBaseForDispFormChain(Bucket &BucketChain,
-                                                    InstrForm Form) {
-  // RemainderOffsetInfo details:
-  // key:            value of (Offset urem DispConstraint). For DSForm, it can
-  //                 be [0, 4).
-  // first of pair:  the index of first BucketElement whose remainder is equal
-  //                 to key. For key 0, this value must be 0.
-  // second of pair: number of load/stores with the same remainder.
-  DenseMap<unsigned, std::pair<unsigned, unsigned>> RemainderOffsetInfo;
-
-  for (unsigned j = 0, je = BucketChain.Elements.size(); j != je; ++j) {
-    if (!BucketChain.Elements[j].Offset)
-      RemainderOffsetInfo[0] = std::make_pair(0, 1);
-    else {
-      unsigned Remainder =
-          BucketChain.Elements[j].Offset->getAPInt().urem(Form);
-      if (RemainderOffsetInfo.find(Remainder) == RemainderOffsetInfo.end())
-        RemainderOffsetInfo[Remainder] = std::make_pair(j, 1);
-      else
-        RemainderOffsetInfo[Remainder].second++;
-    }
-  }
-  // Currently we choose the most profitable base as the one which has the max
-  // number of load/store with same remainder.
-  // FIXME: adjust the base selection strategy according to load/store offset
-  // distribution.
-  // For example, if we have one candidate chain for DS form preparation, which
-  // contains following load/stores with different remainders:
-  // 1: 10 load/store whose remainder is 1;
-  // 2: 9 load/store whose remainder is 2;
-  // 3: 1 for remainder 3 and 0 for remainder 0; 
-  // Now we will choose the first load/store whose remainder is 1 as base and
-  // adjust all other load/stores according to new base, so we will get 10 DS
-  // form and 10 X form.
-  // But we should be more clever, for this case we could use two bases, one for
-  // remainder 1 and the other for remainder 2, thus we could get 19 DS form and 1
-  // X form.
-  unsigned MaxCountRemainder = 0;
-  for (unsigned j = 0; j < (unsigned)Form; j++)
-    if ((RemainderOffsetInfo.find(j) != RemainderOffsetInfo.end()) &&
-        RemainderOffsetInfo[j].second >
-            RemainderOffsetInfo[MaxCountRemainder].second)
-      MaxCountRemainder = j;
-
-  // Abort when there are too few insts with common base.
-  if (RemainderOffsetInfo[MaxCountRemainder].second < DispFormPrepMinThreshold)
-    return false;
-
-  // If the first value is most profitable, no needed to adjust BucketChain
-  // elements as they are substracted the first value when collecting.
-  if (MaxCountRemainder == 0)
-    return true;
-
-  // Adjust load/store to the new chosen base.
-  const SCEV *Offset =
-      BucketChain.Elements[RemainderOffsetInfo[MaxCountRemainder].first].Offset;
-  BucketChain.BaseSCEV = SE->getAddExpr(BucketChain.BaseSCEV, Offset);
-  for (auto &E : BucketChain.Elements) {
-    if (E.Offset)
-      E.Offset = cast<SCEVConstant>(SE->getMinusSCEV(E.Offset, Offset));
-    else
-      E.Offset = cast<SCEVConstant>(SE->getNegativeSCEV(Offset));
-  }
-
-  std::swap(BucketChain.Elements[RemainderOffsetInfo[MaxCountRemainder].first],
-            BucketChain.Elements[0]);
-  return true;
-}
-
-// FIXME: implement a more clever base choosing policy.
-// Currently we always choose an exist load/store offset. This maybe lead to
-// suboptimal code sequences. For example, for one DS chain with offsets
-// {-32769, 2003, 2007, 2011}, we choose -32769 as base offset, and left disp
-// for load/stores are {0, 34772, 34776, 34780}. Though each offset now is a
-// multipler of 4, it cannot be represented by sint16.
-bool PPCLoopPreIncPrep::prepareBaseForUpdateFormChain(Bucket &BucketChain) {
-  // We have a choice now of which instruction's memory operand we use as the
-  // base for the generated PHI. Always picking the first instruction in each
-  // bucket does not work well, specifically because that instruction might
-  // be a prefetch (and there are no pre-increment dcbt variants). Otherwise,
-  // the choice is somewhat arbitrary, because the backend will happily
-  // generate direct offsets from both the pre-incremented and
-  // post-incremented pointer values. Thus, we'll pick the first non-prefetch
-  // instruction in each bucket, and adjust the recurrence and other offsets
-  // accordingly.
-  for (int j = 0, je = BucketChain.Elements.size(); j != je; ++j) {
-    if (auto *II = dyn_cast<IntrinsicInst>(BucketChain.Elements[j].Instr))
-      if (II->getIntrinsicID() == Intrinsic::prefetch)
-        continue;
-
-    // If we'd otherwise pick the first element anyway, there's nothing to do.
-    if (j == 0)
-      break;
-
-    // If our chosen element has no offset from the base pointer, there's
-    // nothing to do.
-    if (!BucketChain.Elements[j].Offset ||
-        BucketChain.Elements[j].Offset->isZero())
-      break;
-
-    const SCEV *Offset = BucketChain.Elements[j].Offset;
-    BucketChain.BaseSCEV = SE->getAddExpr(BucketChain.BaseSCEV, Offset);
-    for (auto &E : BucketChain.Elements) {
-      if (E.Offset)
-        E.Offset = cast<SCEVConstant>(SE->getMinusSCEV(E.Offset, Offset));
-      else
-        E.Offset = cast<SCEVConstant>(SE->getNegativeSCEV(Offset));
-    }
-
-    std::swap(BucketChain.Elements[j], BucketChain.Elements[0]);
-    break;
-  }
-  return true;
-}
-
-bool PPCLoopPreIncPrep::rewriteLoadStores(Loop *L, Bucket &BucketChain,
-                                          SmallSet<BasicBlock *, 16> &BBChanged,
-                                          InstrForm Form) {
-  bool MadeChange = false;
-  const SCEVAddRecExpr *BasePtrSCEV =
-      cast<SCEVAddRecExpr>(BucketChain.BaseSCEV);
-  if (!BasePtrSCEV->isAffine())
-    return MadeChange;
-
-  LLVM_DEBUG(dbgs() << "PIP: Transforming: " << *BasePtrSCEV << "\n");
-
-  assert(BasePtrSCEV->getLoop() == L && "AddRec for the wrong loop?");
-
-  // The instruction corresponding to the Bucket's BaseSCEV must be the first
-  // in the vector of elements.
-  Instruction *MemI = BucketChain.Elements.begin()->Instr;
-  Value *BasePtr = GetPointerOperand(MemI);
-  assert(BasePtr && "No pointer operand");
-
-  Type *I8Ty = Type::getInt8Ty(MemI->getParent()->getContext());
-  Type *I8PtrTy = Type::getInt8PtrTy(MemI->getParent()->getContext(),
-    BasePtr->getType()->getPointerAddressSpace());
-
-  if (!SE->isLoopInvariant(BasePtrSCEV->getStart(), L))
-    return MadeChange;
-
-  const SCEVConstant *BasePtrIncSCEV =
-    dyn_cast<SCEVConstant>(BasePtrSCEV->getStepRecurrence(*SE));
-  if (!BasePtrIncSCEV)
-    return MadeChange;
-
-  // For some DS form load/store instructions, it can also be an update form,
-  // if the stride is a multipler of 4. Use update form if prefer it.
-  bool CanPreInc = (Form == UpdateForm ||
-                    ((Form == DSForm) && !BasePtrIncSCEV->getAPInt().urem(4) &&
-                     PreferUpdateForm));
-  const SCEV *BasePtrStartSCEV = nullptr;
-  if (CanPreInc)
-    BasePtrStartSCEV =
-        SE->getMinusSCEV(BasePtrSCEV->getStart(), BasePtrIncSCEV);
-  else
-    BasePtrStartSCEV = BasePtrSCEV->getStart();
-
-  if (!isSafeToExpand(BasePtrStartSCEV, *SE))
-    return MadeChange;
-
-  if (alreadyPrepared(L, MemI, BasePtrStartSCEV, BasePtrIncSCEV, Form))
-    return MadeChange;
-
-  LLVM_DEBUG(dbgs() << "PIP: New start is: " << *BasePtrStartSCEV << "\n");
-
-  BasicBlock *Header = L->getHeader();
-  unsigned HeaderLoopPredCount = pred_size(Header);
-  BasicBlock *LoopPredecessor = L->getLoopPredecessor();
-
-  PHINode *NewPHI =
-      PHINode::Create(I8PtrTy, HeaderLoopPredCount,
-                      getInstrName(MemI, PHINodeNameSuffix),
-                      Header->getFirstNonPHI());
-
-  SCEVExpander SCEVE(*SE, Header->getModule()->getDataLayout(), "pistart");
-  Value *BasePtrStart = SCEVE.expandCodeFor(BasePtrStartSCEV, I8PtrTy,
-                                            LoopPredecessor->getTerminator());
-
-  // Note that LoopPredecessor might occur in the predecessor list multiple
-  // times, and we need to add it the right number of times.
-  for (const auto &PI : predecessors(Header)) {
-    if (PI != LoopPredecessor)
-      continue;
-
-    NewPHI->addIncoming(BasePtrStart, LoopPredecessor);
-  }
-
-  Instruction *PtrInc = nullptr;
-  Instruction *NewBasePtr = nullptr;
-  if (CanPreInc) {
-    Instruction *InsPoint = &*Header->getFirstInsertionPt();
-    PtrInc = GetElementPtrInst::Create(
-        I8Ty, NewPHI, BasePtrIncSCEV->getValue(),
-        getInstrName(MemI, GEPNodeIncNameSuffix), InsPoint);
-    cast<GetElementPtrInst>(PtrInc)->setIsInBounds(IsPtrInBounds(BasePtr));
-    for (const auto &PI : predecessors(Header)) {
-      if (PI == LoopPredecessor)
-        continue;
-
-      NewPHI->addIncoming(PtrInc, PI);
-    }
-    if (PtrInc->getType() != BasePtr->getType())
-      NewBasePtr = new BitCastInst(
-          PtrInc, BasePtr->getType(),
-          getInstrName(PtrInc, CastNodeNameSuffix), InsPoint);
-    else
-      NewBasePtr = PtrInc;
-  } else {
-    // Note that LoopPredecessor might occur in the predecessor list multiple
-    // times, and we need to make sure no more incoming value for them in PHI.
-    for (const auto &PI : predecessors(Header)) {
-      if (PI == LoopPredecessor)
-        continue;
-
-      // For the latch predecessor, we need to insert a GEP just before the
-      // terminator to increase the address.
-      BasicBlock *BB = PI;
-      Instruction *InsPoint = BB->getTerminator();
-      PtrInc = GetElementPtrInst::Create(
-          I8Ty, NewPHI, BasePtrIncSCEV->getValue(),
-          getInstrName(MemI, GEPNodeIncNameSuffix), InsPoint);
-
-      cast<GetElementPtrInst>(PtrInc)->setIsInBounds(IsPtrInBounds(BasePtr));
-
-      NewPHI->addIncoming(PtrInc, PI);
-    }
-    PtrInc = NewPHI;
-    if (NewPHI->getType() != BasePtr->getType())
-      NewBasePtr =
-          new BitCastInst(NewPHI, BasePtr->getType(),
-                          getInstrName(NewPHI, CastNodeNameSuffix),
-                          &*Header->getFirstInsertionPt());
-    else
-      NewBasePtr = NewPHI;
-  }
-
-  if (Instruction *IDel = dyn_cast<Instruction>(BasePtr))
-    BBChanged.insert(IDel->getParent());
-  BasePtr->replaceAllUsesWith(NewBasePtr);
-  RecursivelyDeleteTriviallyDeadInstructions(BasePtr);
-
-  // Keep track of the replacement pointer values we've inserted so that we
-  // don't generate more pointer values than necessary.
-  SmallPtrSet<Value *, 16> NewPtrs;
-  NewPtrs.insert(NewBasePtr);
-
-  for (auto I = std::next(BucketChain.Elements.begin()),
-       IE = BucketChain.Elements.end(); I != IE; ++I) {
-    Value *Ptr = GetPointerOperand(I->Instr);
-    assert(Ptr && "No pointer operand");
-    if (NewPtrs.count(Ptr))
-      continue;
-
-    Instruction *RealNewPtr;
-    if (!I->Offset || I->Offset->getValue()->isZero()) {
-      RealNewPtr = NewBasePtr;
-    } else {
-      Instruction *PtrIP = dyn_cast<Instruction>(Ptr);
-      if (PtrIP && isa<Instruction>(NewBasePtr) &&
-          cast<Instruction>(NewBasePtr)->getParent() == PtrIP->getParent())
-        PtrIP = nullptr;
-      else if (PtrIP && isa<PHINode>(PtrIP))
-        PtrIP = &*PtrIP->getParent()->getFirstInsertionPt();
-      else if (!PtrIP)
-        PtrIP = I->Instr;
-
-      GetElementPtrInst *NewPtr = GetElementPtrInst::Create(
-          I8Ty, PtrInc, I->Offset->getValue(),
-          getInstrName(I->Instr, GEPNodeOffNameSuffix), PtrIP);
-      if (!PtrIP)
-        NewPtr->insertAfter(cast<Instruction>(PtrInc));
-      NewPtr->setIsInBounds(IsPtrInBounds(Ptr));
-      RealNewPtr = NewPtr;
-    }
-
-    if (Instruction *IDel = dyn_cast<Instruction>(Ptr))
-      BBChanged.insert(IDel->getParent());
-
-    Instruction *ReplNewPtr;
-    if (Ptr->getType() != RealNewPtr->getType()) {
-      ReplNewPtr = new BitCastInst(RealNewPtr, Ptr->getType(),
-        getInstrName(Ptr, CastNodeNameSuffix));
-      ReplNewPtr->insertAfter(RealNewPtr);
-    } else
-      ReplNewPtr = RealNewPtr;
-
-    Ptr->replaceAllUsesWith(ReplNewPtr);
-    RecursivelyDeleteTriviallyDeadInstructions(Ptr);
-
-    NewPtrs.insert(RealNewPtr);
-  }
-
-  MadeChange = true;
-
-  SuccPrepCount++;  
-
-  if (Form == DSForm && !CanPreInc)
-    DSFormChainRewritten++;
-  else if (Form == DQForm)
-    DQFormChainRewritten++;
-  else if (Form == UpdateForm || (Form == DSForm && CanPreInc))
-    UpdFormChainRewritten++;
-
-  return MadeChange;
-}
-
-bool PPCLoopPreIncPrep::updateFormPrep(Loop *L,
-                                       SmallVector<Bucket, 16> &Buckets) {
-  bool MadeChange = false;
-  if (Buckets.empty())
-    return MadeChange;
-  SmallSet<BasicBlock *, 16> BBChanged;
-  for (auto &Bucket : Buckets)
-    // The base address of each bucket is transformed into a phi and the others
-    // are rewritten based on new base.
-    if (prepareBaseForUpdateFormChain(Bucket))
-      MadeChange |= rewriteLoadStores(L, Bucket, BBChanged, UpdateForm);
-
-  if (MadeChange)
-    for (auto &BB : L->blocks())
-      if (BBChanged.count(BB))
-        DeleteDeadPHIs(BB);
-  return MadeChange;
-}
-
-bool PPCLoopPreIncPrep::dispFormPrep(Loop *L, SmallVector<Bucket, 16> &Buckets,
-                                     InstrForm Form) {
-  bool MadeChange = false;
-
-  if (Buckets.empty())
-    return MadeChange;
-
-  SmallSet<BasicBlock *, 16> BBChanged;
-  for (auto &Bucket : Buckets) {
-    if (Bucket.Elements.size() < DispFormPrepMinThreshold)
-      continue;
-    if (prepareBaseForDispFormChain(Bucket, Form))
-      MadeChange |= rewriteLoadStores(L, Bucket, BBChanged, Form);
-  }
-
-  if (MadeChange)
-    for (auto &BB : L->blocks())
-      if (BBChanged.count(BB))
-        DeleteDeadPHIs(BB);
-  return MadeChange;
-}
-
-// In order to prepare for the preferred instruction form, 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 matched start and increment as the
-// one we wanted to create.
-bool PPCLoopPreIncPrep::alreadyPrepared(Loop *L, Instruction* MemI,
-                                        const SCEV *BasePtrStartSCEV,
-                                        const SCEVConstant *BasePtrIncSCEV,
-                                        InstrForm Form) {
-  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 (PHIBasePtrIncSCEV == BasePtrIncSCEV) {
-          // The existing PHI (CurrentPHINode) has the same start and increment
-          // as the PHI that we wanted to create.
-          if (Form == UpdateForm &&
-              PHIBasePtrSCEV->getStart() == BasePtrStartSCEV) {
-            ++PHINodeAlreadyExistsUpdate;
-            return true;
-          } 
-          if (Form == DSForm || Form == DQForm) {
-            const SCEVConstant *Diff = dyn_cast<SCEVConstant>(
-                SE->getMinusSCEV(PHIBasePtrSCEV->getStart(), BasePtrStartSCEV));
-            if (Diff && !Diff->getAPInt().urem(Form)) {
-              if (Form == DSForm)
-                ++PHINodeAlreadyExistsDS;
-              else
-                ++PHINodeAlreadyExistsDQ;
-              return true;
-            }
-          } 
-        }
-      }
-    }
-  }
-  return false;
-}
-
-bool PPCLoopPreIncPrep::runOnLoop(Loop *L) {
-  bool MadeChange = false;
-
-  // Only prep. the inner-most loop
-  if (!L->empty())
-    return MadeChange;
-
-  // Return if already done enough preparation.
-  if (SuccPrepCount >= MaxVarsPrep)
-    return MadeChange;
-
-  LLVM_DEBUG(dbgs() << "PIP: Examining: " << *L << "\n");
-
-  BasicBlock *LoopPredecessor = L->getLoopPredecessor();
-  // If there is no loop predecessor, or the loop predecessor's terminator
-  // returns a value (which might contribute to determining the loop's
-  // iteration space), insert a new preheader for the loop.
-  if (!LoopPredecessor ||
-      !LoopPredecessor->getTerminator()->getType()->isVoidTy()) {
-    LoopPredecessor = InsertPreheaderForLoop(L, DT, LI, nullptr, PreserveLCSSA);
-    if (LoopPredecessor)
-      MadeChange = true;
-  }
-  if (!LoopPredecessor) {
-    LLVM_DEBUG(dbgs() << "PIP fails since no predecessor for current loop.\n");
-    return MadeChange;
-  }
-  // Check if a load/store has update form. This lambda is used by function
-  // collectCandidates which can collect candidates for types defined by lambda.
-  auto isUpdateFormCandidate = [&] (const Instruction *I,
-                                    const Value *PtrValue) {
-    assert((PtrValue && I) && "Invalid parameter!");
-    // There are no update forms for Altivec vector load/stores.
-    if (ST && ST->hasAltivec() &&
-        PtrValue->getType()->getPointerElementType()->isVectorTy())
-      return false;
-    // See getPreIndexedAddressParts, the displacement for LDU/STDU has to
-    // be 4's multiple (DS-form). For i64 loads/stores when the displacement
-    // fits in a 16-bit signed field but isn't a multiple of 4, it will be
-    // useless and possible to break some original well-form addressing mode
-    // to make this pre-inc prep for it.
-    if (PtrValue->getType()->getPointerElementType()->isIntegerTy(64)) {
-      const SCEV *LSCEV = SE->getSCEVAtScope(const_cast<Value *>(PtrValue), L);
-      const SCEVAddRecExpr *LARSCEV = dyn_cast<SCEVAddRecExpr>(LSCEV);
-      if (!LARSCEV || LARSCEV->getLoop() != L)
-        return false;
-      if (const SCEVConstant *StepConst =
-              dyn_cast<SCEVConstant>(LARSCEV->getStepRecurrence(*SE))) {
-        const APInt &ConstInt = StepConst->getValue()->getValue();
-        if (ConstInt.isSignedIntN(16) && ConstInt.srem(4) != 0)
-          return false;
-      }
-    }
-    return true;
-  };
-  
-  // Check if a load/store has DS form.
-  auto isDSFormCandidate = [] (const Instruction *I, const Value *PtrValue) {
-    assert((PtrValue && I) && "Invalid parameter!");
-    // FIXME: 32 bit instruction lwa is also DS form.
-    return !isa<IntrinsicInst>(I) &&
-           ((PtrValue->getType()->getPointerElementType()->isIntegerTy(64)) ||
-            (PtrValue->getType()->getPointerElementType()->isFloatTy()) ||
-            (PtrValue->getType()->getPointerElementType()->isDoubleTy()));
-  };
-
-  // Check if a load/store has DQ form.
-  auto isDQFormCandidate = [&] (const Instruction *I, const Value *PtrValue) {
-    assert((PtrValue && I) && "Invalid parameter!");
-    return !isa<IntrinsicInst>(I) && ST && ST->hasP9Vector() &&
-           (PtrValue->getType()->getPointerElementType()->isVectorTy());
-  };
-
-  // intrinsic for update form.
-  SmallVector<Bucket, 16> UpdateFormBuckets =
-      collectCandidates(L, isUpdateFormCandidate, MaxVarsUpdateForm);
-
-  // Prepare for update form.
-  if (!UpdateFormBuckets.empty())
-    MadeChange |= updateFormPrep(L, UpdateFormBuckets);
-
-  // Collect buckets of comparable addresses used by loads and stores for DS
-  // form.
-  SmallVector<Bucket, 16> DSFormBuckets =
-      collectCandidates(L, isDSFormCandidate, MaxVarsDSForm);
-
-  // Prepare for DS form.
-  if (!DSFormBuckets.empty())
-    MadeChange |= dispFormPrep(L, DSFormBuckets, DSForm);
-
-  // Collect buckets of comparable addresses used by loads and stores for DQ
-  // form.
-  SmallVector<Bucket, 16> DQFormBuckets =
-      collectCandidates(L, isDQFormCandidate, MaxVarsDQForm);
-
-  // Prepare for DQ form.
-  if (!DQFormBuckets.empty())
-    MadeChange |= dispFormPrep(L, DQFormBuckets, DQForm);
-
-  return MadeChange;
-}

llvm/utils/gn/secondary/llvm/lib/Target/PowerPC/BUILD.gn

sources = [
     "PPCEarlyReturn.cpp",
     "PPCExpandISEL.cpp",
     "PPCFastISel.cpp",
     "PPCFrameLowering.cpp",
     "PPCHazardRecognizers.cpp",
     "PPCISelDAGToDAG.cpp",
     "PPCISelLowering.cpp",
     "PPCInstrInfo.cpp",
-    "PPCLoopPreIncPrep.cpp",
+    "PPCLoopInstrFormPrep.cpp",
     "PPCLowerMASSVEntries.cpp",
     "PPCMCInstLower.cpp",
     "PPCMIPeephole.cpp",
     "PPCMachineFunctionInfo.cpp",
     "PPCMachineScheduler.cpp",
     "PPCPreEmitPeephole.cpp",
     "PPCQPXLoadSplat.cpp",
     "PPCReduceCRLogicals.cpp",