add pragmas to control Software Pipelining optimisation

[avl]

Summary

[PIPELINER] add two pragmas to control Software Pipelining optimisation.

  
#pragma clang loop pipeline(disable)
  
    Disable SWP optimization for the next loop.
    “disable” is the only possible value.
  
#pragma clang loop pipeline_initiation_interval(number)
  
    Set value of initiation interval for SWP
    optimization to specified number value for
    the next loop. Number is the positive value
    greater than 0.
  
These pragmas could be used for debugging or reducing
compile time purposes. It is possible to disable SWP for
concrete loops to save compilation time or to find bugs
by not doing SWP to certain loops. It is possible to set
value of initiation interval to concrete number to save
compilation time by not doing extra pipeliner passes or
to check created schedule for specific initiation interval.

That is llvm part of the fix

Clang part of fix: https://reviews.llvm.org/D55710

[avl]

make setMII, setMAX_II to be private.

[Meinersbur]

I recently added a WarnMissedTransformationsPass (lib/Transforms/Scalar/WarnMissedTransformations.cpp) which emits a warning if a #pragma clang loop has not been applied, for any reason. It would be nince if it would work for #pragma clang loop as well. For instance, if the target backend does not support yet. My implementation is located after the midend loop passes, so it cannot be adapted directly.

[avl]

Ok, I will investigate on how to add this functionality.

[avl]

Michael, I evaluated what should be done to implement warnings about missed transformations for pragma clang loop pipeine. It requires modifications for WarnMissedTransformations pass or creating another one which will work after MIR generated, it would also be neccessary to change metadata handling in MachinePipeliner.cpp. I am OK to do all of these. Though I would prefer to do it as a separate patch.

Would it be OK to integrate this patch in it`s current state and create another patch for warning about missed transformation for #pragma clang loop pipeline ?

[Meinersbur]

In D56403#1353857, @alexey.lapshin wrote:

Would it be OK to integrate this patch in it`s current state and create another patch for warning about missed transformation for #pragma clang loop pipeline ?

Yes.

However, I don't feel qualified for reviewing this patch.

lib/CodeGen/MachinePipeliner.cpp

826 ↗

(On Diff #180541)

[nit] unnecessary empty line

859 ↗

(On Diff #180541)

[nit] unnecessary empty line

878–880 ↗

(On Diff #180541)

[nit] No braces necessary

[avl]

merge with separated MachinePipeliner.h/.cpp and address comments.

[avl]

ping.

[bcahoon]

Just a couple of minor comments on formatting. Otherwise, it looks good to me. Thanks!

include/llvm/CodeGen/MachinePipeliner.h

66 ↗

(On Diff #181758)

DisabledByPragma - variable names should start with an upper case letter according to the LLVM Coding Standards.

86 ↗

(On Diff #181758)

I don't think you need (or should have) both default member initializer for disabledByPramga/II_setByPragma and a member initializer list. I believe LLVM encourages using the default member initializer.

lib/CodeGen/MachinePipeliner.cpp

365 ↗

(On Diff #181758)

no need for braces

[avl]

Thank You! Brendon, Could you integrate that fix please ? I do no have commit access yet. As to your comments - how it would be better to handle them - do I need to upload new revision now or just to do them with another fix ?

[bcahoon]

Hi Alexey,

I can merge the patch for you, and make the minor changes. I encourage you to get commit access, especially if you're going to make more contributions.

Thanks,
Brendon

[avl]

Hi Brendon,

[avl]

Hi Brendon,

That would be great!   
Sure, I am going to request commit access. I just need to have several successful patches already integrated for that.

Thank You, Alexey.

llvm/trunk/include/llvm/CodeGen/MachinePipeliner.h

 class MachinePipeliner : public MachineFunctionPass {
 public:
   MachineFunction *MF = nullptr;
   const MachineLoopInfo *MLI = nullptr;
   const MachineDominatorTree *MDT = nullptr;
   const InstrItineraryData *InstrItins;
   const TargetInstrInfo *TII = nullptr;
   RegisterClassInfo RegClassInfo;
+  bool disabledByPragma = false;
+  unsigned II_setByPragma = 0;
 
 #ifndef NDEBUG
   static int NumTries;
 #endif
 
   /// Cache the target analysis information about the loop.
   struct LoopInfo {
     MachineBasicBlock *TBB = nullptr;
void getAnalysisUsage(AnalysisUsage &AU) const override {
     MachineFunctionPass::getAnalysisUsage(AU);
   }
 
 private:
   void preprocessPhiNodes(MachineBasicBlock &B);
   bool canPipelineLoop(MachineLoop &L);
   bool scheduleLoop(MachineLoop &L);
   bool swingModuloScheduler(MachineLoop &L);
+  void setPragmaPipelineOptions(MachineLoop &L);
 };
 
 /// This class builds the dependence graph for the instructions in a loop,
 /// and attempts to schedule the instructions using the SMS algorithm.
 class SwingSchedulerDAG : public ScheduleDAGInstrs {
   MachinePipeliner &Pass;
   /// The minimum initiation interval between iterations for this schedule.
   unsigned MII = 0;
+  /// The maximum initiation interval between iterations for this schedule.
+  unsigned MAX_II = 0;
   /// Set to true if a valid pipelined schedule is found for the loop.
   bool Scheduled = false;
   MachineLoop &Loop;
   LiveIntervals &LIS;
   const RegisterClassInfo &RegClassInfo;
+  unsigned II_setByPragma = 0;
 
   /// A toplogical ordering of the SUnits, which is needed for changing
   /// dependences and iterating over the SUnits.
   ScheduleDAGTopologicalSort Topo;
 
   struct NodeInfo {
     int ASAP = 0;
     int ALAP = 0;
class SwingSchedulerDAG : public ScheduleDAGInstrs {
   };
 
   struct CopyToPhiMutation : public ScheduleDAGMutation {
     void apply(ScheduleDAGInstrs *DAG) override;
   };
 
 public:
   SwingSchedulerDAG(MachinePipeliner &P, MachineLoop &L, LiveIntervals &lis,
-                    const RegisterClassInfo &rci)
+                    const RegisterClassInfo &rci, unsigned II)
       : ScheduleDAGInstrs(*P.MF, P.MLI, false), Pass(P), Loop(L), LIS(lis),
-        RegClassInfo(rci), Topo(SUnits, &ExitSU) {
+        RegClassInfo(rci), II_setByPragma(II), Topo(SUnits, &ExitSU) {
     P.MF->getSubtarget().getSMSMutations(Mutations);
     if (SwpEnableCopyToPhi)
       Mutations.push_back(llvm::make_unique<CopyToPhiMutation>());
   }
 
   void schedule() override;
   void finishBlock() override;
 
public:
   unsigned getDistance(SUnit *U, SUnit *V, const SDep &Dep) {
     // Instructions that feed a Phi have a distance of 1. Computing larger
     // values for arrays requires data dependence information.
     if (V->getInstr()->isPHI() && Dep.getKind() == SDep::Anti)
       return 1;
     return 0;
   }
 
-  /// Set the Minimum Initiation Interval for this schedule attempt.
-  void setMII(unsigned mii) { MII = mii; }
-
   void applyInstrChange(MachineInstr *MI, SMSchedule &Schedule);
 
   void fixupRegisterOverlaps(std::deque<SUnit *> &Instrs);
 
   /// Return the new base register that was stored away for the changed
   /// instruction.
   unsigned getInstrBaseReg(SUnit *SU) {
     DenseMap<SUnit *, std::pair<unsigned, int64_t>>::iterator It =
void rewriteScheduledInstr(MachineBasicBlock *BB, SMSchedule &Schedule,
                              InstrMapTy &InstrMap, unsigned CurStageNum,
                              unsigned PhiNum, MachineInstr *Phi,
                              unsigned OldReg, unsigned NewReg,
                              unsigned PrevReg = 0);
   bool canUseLastOffsetValue(MachineInstr *MI, unsigned &BasePos,
                              unsigned &OffsetPos, unsigned &NewBase,
                              int64_t &NewOffset);
   void postprocessDAG();
+  /// Set the Minimum Initiation Interval for this schedule attempt.
+  void setMII(unsigned ResMII, unsigned RecMII);
+  /// Set the Maximum Initiation Interval for this schedule attempt.
+  void setMAX_II();
 };
 
 /// A NodeSet contains a set of SUnit DAG nodes with additional information
 /// that assigns a priority to the set.
 class NodeSet {
   SetVector<SUnit *> Nodes;
   bool HasRecurrence = false;
   unsigned RecMII = 0;

llvm/trunk/lib/CodeGen/MachinePipeliner.cpp

#ifndef NDEBUG
   int Limit = SwpLoopLimit;
   if (Limit >= 0) {
     if (NumTries >= SwpLoopLimit)
       return Changed;
     NumTries++;
   }
 #endif
 
-  if (!canPipelineLoop(L))
+  setPragmaPipelineOptions(L);
+  if (!canPipelineLoop(L)) {
+    LLVM_DEBUG(dbgs() << "\n!!! Can not pipeline loop.\n");
     return Changed;
+  }
 
   ++NumTrytoPipeline;
 
   Changed = swingModuloScheduler(L);
 
   return Changed;
 }
 
+void MachinePipeliner::setPragmaPipelineOptions(MachineLoop &L) {
+  MachineBasicBlock *LBLK = L.getTopBlock();
+
+  if (LBLK == nullptr)
+    return;
+
+  const BasicBlock *BBLK = LBLK->getBasicBlock();
+  if (BBLK == nullptr)
+    return;
+
+  const Instruction *TI = BBLK->getTerminator();
+  if (TI == nullptr)
+    return;
+
+  MDNode *LoopID = TI->getMetadata(LLVMContext::MD_loop);
+  if (LoopID == nullptr)
+    return;
+
+  assert(LoopID->getNumOperands() > 0 && "requires atleast one operand");
+  assert(LoopID->getOperand(0) == LoopID && "invalid loop");
+
+  for (unsigned i = 1, e = LoopID->getNumOperands(); i < e; ++i) {
+    MDNode *MD = dyn_cast<MDNode>(LoopID->getOperand(i));
+
+    if (MD == nullptr)
+      continue;
+
+    MDString *S = dyn_cast<MDString>(MD->getOperand(0));
+
+    if (S == nullptr)
+      continue;
+
+    if (S->getString() == "llvm.loop.pipeline.initiationinterval") {
+      assert(MD->getNumOperands() == 2 &&
+             "Pipeline initiation interval hint metadata should have two operands.");
+      II_setByPragma =
+          mdconst::extract<ConstantInt>(MD->getOperand(1))->getZExtValue();
+      assert(II_setByPragma >= 1 && "Pipeline initiation interval must be positive.");
+    } else if (S->getString() == "llvm.loop.pipeline.disable") {
+      disabledByPragma = true;
+    }
+  }
+}
+
 /// Return true if the loop can be software pipelined.  The algorithm is
 /// restricted to loops with a single basic block.  Make sure that the
 /// branch in the loop can be analyzed.
 bool MachinePipeliner::canPipelineLoop(MachineLoop &L) {
   if (L.getNumBlocks() != 1)
     return false;
 
+  if (disabledByPragma)
+    return false;
+
   // Check if the branch can't be understood because we can't do pipelining
   // if that's the case.
   LI.TBB = nullptr;
   LI.FBB = nullptr;
   LI.BrCond.clear();
   if (TII->analyzeBranch(*L.getHeader(), LI.TBB, LI.FBB, LI.BrCond))
     return false;
 

 
 /// The SMS algorithm consists of the following main steps:
 /// 1. Computation and analysis of the dependence graph.
 /// 2. Ordering of the nodes (instructions).
 /// 3. Attempt to Schedule the loop.
 bool MachinePipeliner::swingModuloScheduler(MachineLoop &L) {
   assert(L.getBlocks().size() == 1 && "SMS works on single blocks only.");
 
-  SwingSchedulerDAG SMS(*this, L, getAnalysis<LiveIntervals>(), RegClassInfo);
+  SwingSchedulerDAG SMS(*this, L, getAnalysis<LiveIntervals>(), RegClassInfo,
+                        II_setByPragma);
 
   MachineBasicBlock *MBB = L.getHeader();
   // The kernel should not include any terminator instructions.  These
   // will be added back later.
   SMS.startBlock(MBB);
 
   // Compute the number of 'real' instructions in the basic block by
   // ignoring terminators.
   unsigned size = MBB->size();
   for (MachineBasicBlock::iterator I = MBB->getFirstTerminator(),
                                    E = MBB->instr_end();
        I != E; ++I, --size)
     ;
 
   SMS.enterRegion(MBB, MBB->begin(), MBB->getFirstTerminator(), size);
   SMS.schedule();
   SMS.exitRegion();
 
   SMS.finishBlock();
   return SMS.hasNewSchedule();
 }
 
+void SwingSchedulerDAG::setMII(unsigned ResMII, unsigned RecMII) {
+  if (II_setByPragma > 0)
+    MII = II_setByPragma;
+  else
+    MII = std::max(ResMII, RecMII);
+}
+
+void SwingSchedulerDAG::setMAX_II() {
+  if (II_setByPragma > 0)
+    MAX_II = II_setByPragma;
+  else
+    MAX_II = MII + 10;
+}
+
 /// We override the schedule function in ScheduleDAGInstrs to implement the
 /// scheduling part of the Swing Modulo Scheduling algorithm.
 void SwingSchedulerDAG::schedule() {
   AliasAnalysis *AA = &Pass.getAnalysis<AAResultsWrapperPass>().getAAResults();
   buildSchedGraph(AA);
   addLoopCarriedDependences(AA);
   updatePhiDependences();
   Topo.InitDAGTopologicalSorting();
void SwingSchedulerDAG::schedule() {
   unsigned RecMII = calculateRecMII(NodeSets);
 
   fuseRecs(NodeSets);
 
   // This flag is used for testing and can cause correctness problems.
   if (SwpIgnoreRecMII)
     RecMII = 0;
 
-  MII = std::max(ResMII, RecMII);
-  LLVM_DEBUG(dbgs() << "MII = " << MII << " (rec=" << RecMII
-                    << ", res=" << ResMII << ")\n");
+  setMII(ResMII, RecMII);
+  setMAX_II();
+
+  LLVM_DEBUG(dbgs() << "MII = " << MII << " MAX_II = " << MAX_II
+                    << " (rec=" << RecMII << ", res=" << ResMII << ")\n");
 
   // Can't schedule a loop without a valid MII.
   if (MII == 0)
     return;
 
   // Don't pipeline large loops.
   if (SwpMaxMii != -1 && (int)MII > SwpMaxMii)
     return;

 
 /// Process the nodes in the computed order and create the pipelined schedule
 /// of the instructions, if possible. Return true if a schedule is found.
 bool SwingSchedulerDAG::schedulePipeline(SMSchedule &Schedule) {
   if (NodeOrder.empty())
     return false;
 
   bool scheduleFound = false;
+  unsigned II = 0;
   // Keep increasing II until a valid schedule is found.
-  for (unsigned II = MII; II < MII + 10 && !scheduleFound; ++II) {
+  for (II = MII; II <= MAX_II && !scheduleFound; ++II) {
     Schedule.reset();
     Schedule.setInitiationInterval(II);
     LLVM_DEBUG(dbgs() << "Try to schedule with " << II << "\n");
 
     SetVector<SUnit *>::iterator NI = NodeOrder.begin();
     SetVector<SUnit *>::iterator NE = NodeOrder.end();
     do {
       SUnit *SU = *NI;
do {
       });
     } while (++NI != NE && scheduleFound);
 
     // If a schedule is found, check if it is a valid schedule too.
     if (scheduleFound)
       scheduleFound = Schedule.isValidSchedule(this);
   }
 
-  LLVM_DEBUG(dbgs() << "Schedule Found? " << scheduleFound << "\n");
+  LLVM_DEBUG(dbgs() << "Schedule Found? " << scheduleFound << " (II=" << II
+                    << ")\n");
 
   if (scheduleFound)
     Schedule.finalizeSchedule(this);
   else
     Schedule.reset();
 
   return scheduleFound && Schedule.getMaxStageCount() > 0;
 }

llvm/trunk/test/CodeGen/Hexagon/swp-pragma-disable.ii

+; RUN: llc -disable-lsr -march=hexagon -enable-pipeliner  \
+; RUN:     -debug-only=pipeliner < %s 2>&1 > /dev/null | FileCheck %s
+; REQUIRES: asserts
+;
+; Test that checks if pipeliner disabled by pragma 
+
+; CHECK: Can not pipeline loop 
+
+; Function Attrs: nounwind
+define void @f0(i32* nocapture %a0, i32 %a1) #0 {
+b0:
+  %v0 = icmp sgt i32 %a1, 1
+  br i1 %v0, label %b1, label %b4
+
+b1:                                               ; preds = %b0
+  %v1 = load i32, i32* %a0, align 4
+  %v2 = add i32 %v1, 10
+  %v3 = getelementptr i32, i32* %a0, i32 1
+  %v4 = add i32 %a1, -1
+  br label %b2
+
+b2:                                               ; preds = %b2, %b1
+  %v5 = phi i32 [ %v12, %b2 ], [ %v4, %b1 ]
+  %v6 = phi i32* [ %v11, %b2 ], [ %v3, %b1 ]
+  %v7 = phi i32 [ %v10, %b2 ], [ %v2, %b1 ]
+  store i32 %v7, i32* %v6, align 4
+  %v8 = add i32 %v7, 10
+  %v9 = getelementptr i32, i32* %v6, i32 -1
+  store i32 %v8, i32* %v9, align 4
+  %v10 = add i32 %v7, 10
+  %v11 = getelementptr i32, i32* %v6, i32 1
+  %v12 = add i32 %v5, -1
+  %v13 = icmp eq i32 %v12, 0
+  br i1 %v13, label %b3, label %b2
+
+b3:                                               ; preds = %b2
+  br label %b4 , !llvm.loop !2
+
+b4:                                               ; preds = %b3, %b0
+  ret void
+}
+
+attributes #0 = { nounwind }
+
+!0 = !{i32 1, !"wchar_size", i32 4}
+!1 = !{!2, !2, i64 0}
+!2 = distinct !{!2, !3}
+!3 = !{!"llvm.loop.pipeline.disable", i1 true}
+

llvm/trunk/test/CodeGen/Hexagon/swp-pragma-initiation-interval.ii

+; RUN: llc -disable-lsr -march=hexagon -enable-pipeliner  \
+; RUN:     -debug-only=pipeliner < %s 2>&1 > /dev/null | FileCheck %s
+; REQUIRES: asserts
+;
+; Test that checks if the II set by pragma was taken by pipeliner.
+
+; CHECK: MII = 2 MAX_II = 2 
+
+; Function Attrs: nounwind
+define void @f0(i32* nocapture %a0, i32 %a1) #0 {
+b0:
+  %v0 = icmp sgt i32 %a1, 1
+  br i1 %v0, label %b1, label %b4
+
+b1:                                               ; preds = %b0
+  %v1 = load i32, i32* %a0, align 4
+  %v2 = add i32 %v1, 10
+  %v3 = getelementptr i32, i32* %a0, i32 1
+  %v4 = add i32 %a1, -1
+  br label %b2
+
+b2:                                               ; preds = %b2, %b1
+  %v5 = phi i32 [ %v12, %b2 ], [ %v4, %b1 ]
+  %v6 = phi i32* [ %v11, %b2 ], [ %v3, %b1 ]
+  %v7 = phi i32 [ %v10, %b2 ], [ %v2, %b1 ]
+  store i32 %v7, i32* %v6, align 4
+  %v8 = add i32 %v7, 10
+  %v9 = getelementptr i32, i32* %v6, i32 -1
+  store i32 %v8, i32* %v9, align 4
+  %v10 = add i32 %v7, 10
+  %v11 = getelementptr i32, i32* %v6, i32 1
+  %v12 = add i32 %v5, -1
+  %v13 = icmp eq i32 %v12, 0
+  br i1 %v13, label %b3, label %b2
+
+b3:                                               ; preds = %b2
+  br label %b4 , !llvm.loop !2
+
+b4:                                               ; preds = %b3, %b0
+  ret void
+}
+
+attributes #0 = { nounwind }
+
+!0 = !{i32 1, !"wchar_size", i32 4}
+!1 = !{!2, !2, i64 0}
+!2 = distinct !{!2, !3}
+!3 = !{!"llvm.loop.pipeline.initiationinterval", i32 2}
+

llvm/trunk/test/CodeGen/Hexagon/swp-resmii-1.ll

 ; RUN: llc -march=hexagon -enable-pipeliner -debug-only=pipeliner < %s -o - 2>&1 > /dev/null | FileCheck %s
 ; REQUIRES: asserts
 
 ; Test that checks that we compute the correct ResMII for haar.
 
-; CHECK: MII = 4 (rec=1, res=4)
+; CHECK: MII = 4 MAX_II = 14 (rec=1, res=4)
 
 ; Function Attrs: nounwind
 define void @f0(i16* noalias nocapture readonly %a0, i32 %a1, i32 %a2, i32 %a3, i8* noalias nocapture %a4, i32 %a5) #0 {
 b0:
   %v0 = ashr i32 %a3, 2
   %v1 = ashr i32 %a3, 1
   %v2 = add i32 %v1, %v0
   %v3 = icmp sgt i32 %a2, 0

llvm/trunk/test/CodeGen/Hexagon/swp-resmii.ll

 ; RUN: llc -disable-lsr -march=hexagon -enable-pipeliner  \
 ; RUN:     -debug-only=pipeliner < %s 2>&1 > /dev/null | FileCheck %s
 ; REQUIRES: asserts
 ;
 ; Test that checks if the ResMII is 1.
 
-; CHECK: MII = 1 (rec=1, res=1)
+; CHECK: MII = 1 MAX_II = 11 (rec=1, res=1)
 
 ; Function Attrs: nounwind
 define void @f0(i32* nocapture %a0, i32 %a1) #0 {
 b0:
   %v0 = icmp sgt i32 %a1, 1
   br i1 %v0, label %b1, label %b4
 
 b1:                                               ; preds = %b0