[PowerPC] Enable MachinePipeliner for P9 with -ppc-enable-pipeliner

[jsji]

Summary

Implement necessary target hooks to enable MachinePipeliner for P9 only.
The pass is off on PowerPC by def ault,
can be enabled with -ppc-enable-pipeliner for P9.

[jsji]

Ping.. The machine independent part has been committed. Thanks. @bcahoon

Any comments and feedback to this PowerPC specific part are appreciated. @hfinkel @nemanjai @kbarton @steven.zhang Thanks.

[hfinkel]

llvm/lib/Target/PowerPC/PPCInstrInfo.cpp

3938

FWIW, I find this method a bit strange. Do we need have a MachineLoopInfo available such that we could just check in the preheader of the loop?

3962

We generally don't directly recurse though the CFG, but use a worklist and a loop. Can you do that here?

4003

Extra space before 'to'.

4007

Period at the end of the comment.

llvm/lib/Target/PowerPC/PPCSubtarget.cpp

192

Given that this is off by default anyway, why is it enabled only for the P9?

[jsji]

llvm/lib/Target/PowerPC/PPCSubtarget.cpp

192

It is mainly because only P9 has InstrSchedModel , P8 and below are still using Itineraries.
And it needs additional non trivial effort to enable DFA support for P8 and below, due to DFA limitation.
Considering our future process will use InstrSchedModel, we chose to enable InstrSchedModel first for now.

[jsji]

Use worklist instead, and fix comments.

llvm/lib/Target/PowerPC/PPCInstrInfo.cpp

3938

In short, yes.
MachinePipeliner have MachineLoopInfo, and it also make sure that we call reduceLoopCount with prolog MBBs that set up the pipeline, so we are safe to assume that the loop set-up instruction will be in a predecessor block only.

3962

Sure.

[hfinkel]

llvm/lib/Target/PowerPC/PPCInstrInfo.cpp

3938

I'd not give it a 100% guarantee, but if you only check in the preheader, do you miss anything?

(you could check, perhaps, by putting an assert in the current logic to see if you every find the mtctr in some block other than the preheader).

[jsji]

llvm/lib/Target/PowerPC/PPCInstrInfo.cpp

3938

Oh, sorry, did not read carefully, the 'yes' in my last comment was for 'predecessors' not 'preheader' - we assume that mtctr will be in predecessors of Prolog MBBs, no necessary in preheader only.

I guess you question is about whether we may miss some opportunity here - can NOT find mtctr in some case when mtctr is NOT in predecessors?

From the code in MachinePipeliner, I think we should not missing anything here. But I will try your suggestion to double confirm.

[jsji]

llvm/lib/Target/PowerPC/PPCInstrInfo.cpp

3938

you could check, perhaps, by putting an assert in the current logic to see if you ever find the mtctr in some block other than the preheader

Added asserts before return nullptr, and run test with testsuites, no assert found.
Also added some MBB dump for all the BBs we found mtctr, and check all the MBBs that contains mtctr (5000+ mtctr found in testsuites), all of them are in preheader, nothing special found.

I also look into PPCCTRLoops where we generate mtctr, and looks like that we will only Insert the count into the preheader , and PPCCTRLoopsVerify also trying to find MTCTR8loop/MTCTRloop in predecessors only.

I am not aware of any following passes that might move mtctr to other places.

@hfinkel Do you have any cases in mind that I should check again?

[hfinkel]

llvm/lib/Target/PowerPC/PPCInstrInfo.cpp

3938

Nope. That's what I suspected that you might find. I think that just checking the preheader, should it exist, will be sufficient here in practice. I recommend doing that, and then if we find cases where we need to do more, revisit at that time.

[jsji]

Update TII interface to pass down preheader, and find mtctr in preheader only.

[jsji]

llvm/lib/Target/PowerPC/PPCInstrInfo.cpp

3938

Updated patch to just check in preheader.

[hfinkel]

llvm/lib/Target/PowerPC/PPCInstrInfo.cpp

3947

Two things:

1. Never use assert(0 && ...), that's what llvm_unreachable is for.
2. Don't assert here, just return nullptr. This is not actually an error, it *could* happen, and the compiler shouldn't crash. If you'd like, add a STATISTIC to count the number of times this happens.

[jsji]

Remove the assert(0).

[jsji]

llvm/lib/Target/PowerPC/PPCInstrInfo.cpp

3947

You are right, I should have removed this before posting it. Thanks.

[hfinkel]

llvm/lib/Target/PowerPC/PPCInstrInfo.cpp

3978

This return value is incorrect if Offset was zero?

[jsji]

Update return code for Zero count.

[jsji]

Thanks for catching this.

llvm/lib/Target/PowerPC/PPCInstrInfo.cpp

3978

Good catch. Although we shouldn't call reduceLoopCount with trip count == 0, this should be fixed.

[jsji]

Ping... Any further comments and feedback? @hfinkel . Thanks!

[hfinkel]

LGTM

[timshen]

Hi,

This patch seems to fail under Asan at https://github.com/llvm-mirror/llvm/blob/28bea3dbfef348e53cf48f921e96a35b642b3950/lib/CodeGen/MachinePipeliner.cpp#L3736.

I verified that lower_bound() may return Indices.end() upon running the test CodeGen/PowerPC/sms-simple.ll.

[jsji]

In D62164#1539033, @timshen wrote:

Hi,

This patch seems to fail under Asan at https://github.com/llvm-mirror/llvm/blob/28bea3dbfef348e53cf48f921e96a35b642b3950/lib/CodeGen/MachinePipeliner.cpp#L3736.

I verified that lower_bound() may return Indices.end() upon running the test CodeGen/PowerPC/sms-simple.ll.

Thanks, yes, it looks like an issue exposed by power enablement. I have removed sms-simple.ll temporarily to unblock build bot. I will investigate and fix the root cause.

[jsji]

Thanks, yes, it looks like an issue exposed by power enablement. I have removed sms-simple.ll temporarily to unblock build bot. I will investigate and fix the root cause.

https://reviews.llvm.org/D63282 created for the fix.

llvm/include/llvm/CodeGen/TargetSubtargetInfo.h

public:
   /// scheduler (though see below for an option to turn this off and use the
   /// TargetLowering preference). It does not yet disable the postRA scheduler.
   virtual bool enableMachineScheduler() const;
 
   /// True if the machine scheduler should disable the TLI preference
   /// for preRA scheduling with the source level scheduler.
   virtual bool enableMachineSchedDefaultSched() const { return true; }
 
+  /// True if the subtarget should run MachinePipeliner
+  virtual bool enableMachinePipeliner() const { return true; };
+
   /// True if the subtarget should enable joining global copies.
   ///
   /// By default this is enabled if the machine scheduler is enabled, but
   /// can be overridden.
   virtual bool enableJoinGlobalCopies() const;
 
   /// True if the subtarget should run a scheduler after register allocation.
   ///

llvm/lib/CodeGen/MachinePipeliner.cpp

bool MachinePipeliner::runOnMachineFunction(MachineFunction &mf) {
   if (!EnableSWP)
     return false;
 
   if (mf.getFunction().getAttributes().hasAttribute(
           AttributeList::FunctionIndex, Attribute::OptimizeForSize) &&
       !EnableSWPOptSize.getPosition())
     return false;
 
+  if (!mf.getSubtarget().enableMachinePipeliner())
+    return false;
+
   // Cannot pipeline loops without instruction itineraries if we are using
   // DFA for the pipeliner.
   if (mf.getSubtarget().useDFAforSMS() &&
       (!mf.getSubtarget().getInstrItineraryData() ||
        mf.getSubtarget().getInstrItineraryData()->isEmpty()))
     return false;
 
   MF = &mf;

llvm/lib/Target/PowerPC/PPCInstrInfo.h

switch (regClass) {
           return PPC::VSX32 + (Reg - PPC::V0);
         break;
       // Other RegClass doesn't need mapping
       default:
         break;
     }
     return Reg;
   }
+
+  /// Check \p Opcode is BDNZ (Decrement CTR and branch if it is still nonzero).
+  bool isBDNZ(unsigned Opcode) const;
+
+  /// Find the hardware loop instruction used to set-up the specified loop.
+  /// On PPC, we have two instructions used to set-up the hardware loop
+  /// (MTCTRloop, MTCTR8loop) with corresponding endloop (BDNZ, BDNZ8)
+  /// instructions to indicate the end of a loop.
+  MachineInstr *findLoopInstr(const MachineBasicBlock &BB, unsigned EndLoopOp,
+                              const MachineBasicBlock &TargetBB) const;
+
+  /// Analyze the loop code to find the loop induction variable and compare used
+  /// to compute the number of iterations. Currently, we analyze loop that are
+  /// controlled using hardware loops.  In this case, the induction variable
+  /// instruction is null.  For all other cases, this function returns true,
+  /// which means we're unable to analyze it. \p IndVarInst and \p CmpInst will
+  /// return new values when we can analyze the readonly loop \p L, otherwise,
+  /// nothing got changed
+  bool analyzeLoop(MachineLoop &L, MachineInstr *&IndVarInst,
+                   MachineInstr *&CmpInst) const override;
+  /// Generate code to reduce the loop iteration by one and check if the loop
+  /// is finished.  Return the value/register of the new loop count.  We need
+  /// this function when peeling off one or more iterations of a loop. This
+  /// function assumes the last iteration is peeled first.
+  unsigned reduceLoopCount(MachineBasicBlock &MBB,
+                           MachineInstr *IndVar, MachineInstr &Cmp,
+                           SmallVectorImpl<MachineOperand> &Cond,
+                           SmallVectorImpl<MachineInstr *> &PrevInsts,
+                           unsigned Iter, unsigned MaxIter) const override;
 };
 
 }
 
 #endif

llvm/lib/Target/PowerPC/PPCInstrInfo.cpp

else
                isSignOrZeroExtended(*MISrc2, SignExt, Depth+1);
   }
 
   default:
     break;
   }
   return false;
 }
+
+bool PPCInstrInfo::isBDNZ(unsigned Opcode) const {
+  return (Opcode == (Subtarget.isPPC64() ? PPC::BDNZ8 : PPC::BDNZ));
+}
+
+bool PPCInstrInfo::analyzeLoop(MachineLoop &L, MachineInstr *&IndVarInst,
+                               MachineInstr *&CmpInst) const {
+  MachineBasicBlock *LoopEnd = L.getBottomBlock();
+  MachineBasicBlock::iterator I = LoopEnd->getFirstTerminator();
+  // We really "analyze" only CTR loops right now.
+  if (I != LoopEnd->end() && isBDNZ(I->getOpcode())) {
+    IndVarInst = nullptr;
+    CmpInst = &*I;
+    return false;
+  }
+  return true;
+}
+
+MachineInstr *
+PPCInstrInfo::findLoopInstr(const MachineBasicBlock &BB, unsigned EndLoopOp,
+                            const MachineBasicBlock &TargetBB) const {
+
+  unsigned LOOPi = (Subtarget.isPPC64() ? PPC::MTCTR8loop : PPC::MTCTRloop);
+
+  // The loop set-up instruction will be in a predecessor block
+  SmallPtrSet<MachineBasicBlock *, 8> Visited;
+  SmallVector<MachineBasicBlock *, 8> WorkList(BB.pred_begin(), BB.pred_end());
+  while (!WorkList.empty()) {
+    MachineBasicBlock *PB = WorkList.pop_back_val();
+    // If this has been visited, already skip it.
+    if (!Visited.insert(PB).second)
+      continue;
+    if (PB == &BB)
+      continue;
+    for (auto &I : PB->instrs()) {
+      unsigned Opc = I.getOpcode();
+      if (Opc == LOOPi)
+        return &I;
+      // We've reached a different loop, which means the loop01 has been
+      // removed.
+      if (Opc == EndLoopOp && I.getOperand(0).getMBB() != &TargetBB)
+        return nullptr;
+    }
+    WorkList.append(PB->pred_begin(), PB->pred_end());
+  }
+  return nullptr;
+}
+
+unsigned
+PPCInstrInfo::reduceLoopCount(MachineBasicBlock &MBB, MachineInstr *IndVar,
+                              MachineInstr &Cmp,
+                              SmallVectorImpl<MachineOperand> &Cond,
+                              SmallVectorImpl<MachineInstr *> &PrevInsts,
+                              unsigned Iter, unsigned MaxIter) const {
+  // We expect a hardware loop currently. This means that IndVar is set
+  // to null, and the compare is the ENDLOOP instruction.
+  assert((!IndVar) && isBDNZ(Cmp.getOpcode()) && "Expecting a CTR loop");
+  MachineFunction *MF = MBB.getParent();
+  DebugLoc DL = Cmp.getDebugLoc();
+  MachineInstr *Loop =
+      findLoopInstr(MBB, Cmp.getOpcode(), *Cmp.getOperand(0).getMBB());
+  if (!Loop)
+    return 0;
+  unsigned LoopCountReg = Loop->getOperand(0).getReg();
+  MachineRegisterInfo &MRI = MF->getRegInfo();
+  MachineInstr *LoopCount = MRI.getUniqueVRegDef(LoopCountReg);
+
+  if (!LoopCount)
+    return 0;
+  // If the loop trip count is a compile-time value, then just change the
+  // value.
+  if (LoopCount->getOpcode() == PPC::LI8 || LoopCount->getOpcode() == PPC::LI) {
+    int64_t Offset = LoopCount->getOperand(1).getImm();
+    if (Offset <= 1) {
+      LoopCount->eraseFromParent();
+      Loop->eraseFromParent();
+    } else
+      LoopCount->getOperand(1).setImm(Offset - 1);
+    return Offset - 1;
+  }
+
+  // The loop trip count is a run-time value.
+  // We need to subtract one from the trip count,
+  // and insert branch later to check if we're done with the loop.
+
+  // Since BDZ/BDZ8 that we will insert will also decrease the ctr by 1,
+  // so we don't need to generate any thing here.
+  Cond.push_back(MachineOperand::CreateImm(0));
+  Cond.push_back(MachineOperand::CreateReg(
+      Subtarget.isPPC64() ? PPC::CTR8 : PPC::CTR, true));
+  return LoopCountReg;
+}
+

llvm/lib/Target/PowerPC/PPCSubtarget.h

public:
   bool isAIXABI() const { return TargetTriple.isOSAIX(); }
   bool isSVR4ABI() const { return !isDarwinABI() && !isAIXABI(); }
   bool isELFv2ABI() const;
 
   /// Originally, this function return hasISEL(). Now we always enable it,
   /// but may expand the ISEL instruction later.
   bool enableEarlyIfConversion() const override { return true; }
 
-  // Scheduling customization.
+  /// Scheduling customization.
   bool enableMachineScheduler() const override;
-  // This overrides the PostRAScheduler bit in the SchedModel for each CPU.
+  /// Pipeliner customization.
+  bool enableMachinePipeliner() const override;
+  /// Machine Pipeliner customization
+  bool useDFAforSMS() const override;
+  /// This overrides the PostRAScheduler bit in the SchedModel for each CPU.
   bool enablePostRAScheduler() const override;
   AntiDepBreakMode getAntiDepBreakMode() const override;
   void getCriticalPathRCs(RegClassVector &CriticalPathRCs) const override;
 
   void overrideSchedPolicy(MachineSchedPolicy &Policy,
                            unsigned NumRegionInstrs) const override;
   bool useAA() const override;
 

llvm/lib/Target/PowerPC/PPCSubtarget.cpp

 
 static cl::opt<bool> UseSubRegLiveness("ppc-track-subreg-liveness",
 cl::desc("Enable subregister liveness tracking for PPC"), cl::Hidden);
 
 static cl::opt<bool> QPXStackUnaligned("qpx-stack-unaligned",
   cl::desc("Even when QPX is enabled the stack is not 32-byte aligned"),
   cl::Hidden);
 
+static cl::opt<bool>
+    EnableMachinePipeliner("ppc-enable-pipeliner",
+                           cl::desc("Enable Machine Pipeliner for PPC"),
+                           cl::init(false), cl::Hidden);
+
 PPCSubtarget &PPCSubtarget::initializeSubtargetDependencies(StringRef CPU,
                                                             StringRef FS) {
   initializeEnvironment();
   initSubtargetFeatures(CPU, FS);
   return *this;
 }
 
 PPCSubtarget::PPCSubtarget(const Triple &TT, const std::string &CPU,
bool PPCSubtarget::hasLazyResolverStub(const GlobalValue *GV) const {
   // 32 bit macho has no relocation for a-b if a is undefined, even if b is in
   // the section that is being relocated. This means we have to use o load even
   // for GVs that are known to be local to the dso.
   if (GV->isDeclarationForLinker() || GV->hasCommonLinkage())
     return true;
   return false;
 }
 
-bool PPCSubtarget::enableMachineScheduler() const {
-  return true;
+bool PPCSubtarget::enableMachineScheduler() const { return true; }
+
+bool PPCSubtarget::enableMachinePipeliner() const {
+  return (DarwinDirective == PPC::DIR_PWR9) && EnableMachinePipeliner;
 }
 
+bool PPCSubtarget::useDFAforSMS() const { return false; }
+
 // This overrides the PostRAScheduler bit in the SchedModel for each CPU.
 bool PPCSubtarget::enablePostRAScheduler() const { return true; }
 
 PPCGenSubtargetInfo::AntiDepBreakMode PPCSubtarget::getAntiDepBreakMode() const {
   return TargetSubtargetInfo::ANTIDEP_ALL;
 }
 
 void PPCSubtarget::getCriticalPathRCs(RegClassVector &CriticalPathRCs) const {

llvm/lib/Target/PowerPC/PPCTargetMachine.cpp

if (getPPCTargetMachine().isPositionIndependent()) {
     // PPCTLSDynamicCallPass uses LiveIntervals which previously dependent on
     // LiveVariables. This (unnecessary) dependency has been removed now,
     // however a stage-2 clang build fails without LiveVariables computed here.
     addPass(&LiveVariablesID, false);
     addPass(createPPCTLSDynamicCallPass());
   }
   if (EnableExtraTOCRegDeps)
     addPass(createPPCTOCRegDepsPass());
+
+  if (getOptLevel() != CodeGenOpt::None)
+    addPass(&MachinePipelinerID);
 }
 
 void PPCPassConfig::addPreSched2() {
   if (getOptLevel() != CodeGenOpt::None) {
     addPass(&IfConverterID);
 
     // This optimization must happen after anything that might do store-to-load
     // forwarding. Here we're after RA (and, thus, when spills are inserted)

llvm/test/CodeGen/PowerPC/sms-simple.ll

+; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
+; RUN: llc < %s -ppc-vsr-nums-as-vr -mtriple=powerpc64-unknown-linux-gnu \
+; RUN:       -verify-machineinstrs -ppc-asm-full-reg-names -mcpu=pwr9 --ppc-enable-pipeliner \
+; RUN:       | FileCheck %s
+
+@x = dso_local local_unnamed_addr global <{ i32, i32, i32, i32, [1020 x i32] }> <{ i32 1, i32 2, i32 3, i32 4, [1020 x i32] zeroinitializer }>, align 4
+@y = common dso_local global [1024 x i32] zeroinitializer, align 4
+
+; Function Attrs: norecurse nounwind
+define dso_local i32* @foo() local_unnamed_addr #0 {
+; CHECK-LABEL: foo:
+; CHECK:       # %bb.0: # %entry
+; CHECK-NEXT:    addis r5, r2, x@toc@ha
+; CHECK-NEXT:    addi r5, r5, x@toc@l
+; CHECK-NEXT:    addis r6, r2, y@toc@ha
+; CHECK-NEXT:    li r7, 340
+; CHECK-NEXT:    addi r3, r6, y@toc@l
+; CHECK-NEXT:    lwz r6, y@toc@l(r6)
+; CHECK-NEXT:    mtctr r7
+; CHECK-NEXT:    addi r5, r5, -8
+; CHECK-NEXT:    lwzu r7, 12(r5)
+; CHECK-NEXT:    maddld r6, r7, r7, r6
+; CHECK-NEXT:    lwz r7, 4(r5)
+; CHECK-NEXT:    addi r4, r3, -8
+; CHECK-NEXT:    stwu r6, 12(r4)
+; CHECK-NEXT:    maddld r6, r7, r7, r6
+; CHECK-NEXT:    lwz r7, 8(r5)
+; CHECK-NEXT:    .p2align 4
+; CHECK-NEXT:  .LBB0_1: # %for.body
+; CHECK:         maddld r7, r7, r7, r6
+; CHECK-NEXT:    lwzu r8, 12(r5)
+; CHECK-NEXT:    maddld r8, r8, r8, r7
+; CHECK-NEXT:    stw r6, 4(r4)
+; CHECK-NEXT:    lwz r6, 4(r5)
+; CHECK-NEXT:    maddld r6, r6, r6, r8
+; CHECK-NEXT:    stw r7, 8(r4)
+; CHECK-NEXT:    lwz r7, 8(r5)
+; CHECK-NEXT:    stwu r8, 12(r4)
+; CHECK-NEXT:    bdnz .LBB0_1
+; CHECK-NEXT:  # %bb.2:
+; CHECK-NEXT:    maddld r5, r7, r7, r6
+; CHECK-NEXT:    stw r6, 4(r4)
+; CHECK-NEXT:    stw r5, 8(r4)
+; CHECK-NEXT:    blr
+entry:
+  %.pre = load i32, i32* getelementptr inbounds ([1024 x i32], [1024 x i32]* @y, i64 0, i64 0), align 4
+  br label %for.body
+
+for.cond.cleanup:                                 ; preds = %for.body
+  ret i32* getelementptr inbounds ([1024 x i32], [1024 x i32]* @y, i64 0, i64 0)
+
+for.body:                                         ; preds = %for.body, %entry
+  %0 = phi i32 [ %.pre, %entry ], [ %add.2, %for.body ]
+  %indvars.iv = phi i64 [ 1, %entry ], [ %indvars.iv.next.2, %for.body ]
+  %arrayidx2 = getelementptr inbounds [1024 x i32], [1024 x i32]* bitcast (<{ i32, i32, i32, i32, [1020 x i32] }>* @x to [1024 x i32]*), i64 0, i64 %indvars.iv
+  %1 = load i32, i32* %arrayidx2, align 4
+  %mul = mul nsw i32 %1, %1
+  %add = add nsw i32 %mul, %0
+  %arrayidx6 = getelementptr inbounds [1024 x i32], [1024 x i32]* @y, i64 0, i64 %indvars.iv
+  store i32 %add, i32* %arrayidx6, align 4
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  %arrayidx2.1 = getelementptr inbounds [1024 x i32], [1024 x i32]* bitcast (<{ i32, i32, i32, i32, [1020 x i32] }>* @x to [1024 x i32]*), i64 0, i64 %indvars.iv.next
+  %2 = load i32, i32* %arrayidx2.1, align 4
+  %mul.1 = mul nsw i32 %2, %2
+  %add.1 = add nsw i32 %mul.1, %add
+  %arrayidx6.1 = getelementptr inbounds [1024 x i32], [1024 x i32]* @y, i64 0, i64 %indvars.iv.next
+  store i32 %add.1, i32* %arrayidx6.1, align 4
+  %indvars.iv.next.1 = add nuw nsw i64 %indvars.iv, 2
+  %arrayidx2.2 = getelementptr inbounds [1024 x i32], [1024 x i32]* bitcast (<{ i32, i32, i32, i32, [1020 x i32] }>* @x to [1024 x i32]*), i64 0, i64 %indvars.iv.next.1
+  %3 = load i32, i32* %arrayidx2.2, align 4
+  %mul.2 = mul nsw i32 %3, %3
+  %add.2 = add nsw i32 %mul.2, %add.1
+  %arrayidx6.2 = getelementptr inbounds [1024 x i32], [1024 x i32]* @y, i64 0, i64 %indvars.iv.next.1
+  store i32 %add.2, i32* %arrayidx6.2, align 4
+  %indvars.iv.next.2 = add nuw nsw i64 %indvars.iv, 3
+  %exitcond.2 = icmp eq i64 %indvars.iv.next.2, 1024
+  br i1 %exitcond.2, label %for.cond.cleanup, label %for.body
+}