[Polly][ScopBuilder] Introduce -polly-stmt-granularity=scalar-indep option.

[Meinersbur]

Summary

The option splits BasicBlocks into minimal statements such that no additional scalar dependencies are introduced.

The algorithm is based on a union-find structure, and unites sets if putting them into separate statements would introduce a scalar dependencies. As a consequence, instructions may be split into separate statements such their relative order is different than the statements they are in. This is accounted for instructions whose relative order matters (e.g. memory accesses).

The algorithm is generic in that heuristic changes can be made with relative ease. We might relax the order requirement for read-reads or accesses to different base pointers. Forwardable instructions can be made to not cause a join.

This implementation gives us a speed-up of 82% in SPEC 2006 456.hmmer benchmark by allowing loop-distribution in a hot loop.

[nandini12396]

@Meinersbur : A quick q. Even if the split introduced new scalar dependences, wouldnt forward op tree pass take care of it?

[bollu]

lib/Analysis/ScopBuilder.cpp

110

Nit: Could you add a one line explanation as to what the granularity refers to, please?

758

I don't understand, what is this loop trying to do? As best as I can tell, it checks that if we have seen Leader previously (Inserted == false), then we fuse Leader` with everything that was added after Leader.

Is this to ensure that in situations like this:

A
B
A

A and B are forced into the same basic block?

Either way, I'd appreciate it if it was written in a separate function or something, because it seems nice and modular.

766

Nit: could you please provide the concrete type used here? (Instruction *)

772

AFAICT, we don't need to call getLeaderValue on SeenLeaders.back(), because SeenLeaders only contains leaders.

787

Nit: please give this a concrete type (Instruction *)

796

Nit: could you factor this out into a separate function or a lambda? insertLeaderInstructions(...), or insertEquivalenceClassInstructions

[Meinersbur]

In D38403#884413, @nandini12396 wrote:

@Meinersbur : A quick q. Even if the split introduced new scalar dependences, wouldnt forward op tree pass take care of it?

ForwardOpTree cannot forward everything, only 'speculatable' instructions and loads that are known to not have changed.

Even though this might cover a large number of cases, I tried to get something that conservatively doesn't do anything worse than it was before. More aggressive strategies (such as splitting each write access into its own statement) can be implemented as well.

[grosser]

Cool. Would be great to see the LICM working.

[grosser]

I mean see it working with LICM. Thanks Michael!

[nandini12396]

In D38403#884443, @Meinersbur wrote:

ForwardOpTree cannot forward everything, only 'speculatable' instructions and loads that are known to not have changed.

Ok. So, this option will, in future cover https://reviews.llvm.org/D37337#859617 ?

[Meinersbur]

• Add unit tests
• Refactor
• Handle scalar dependencies due to incoming values
• Add comments

[Meinersbur]

In D38403#884578, @nandini12396 wrote:

In D38403#884443, @Meinersbur wrote:

ForwardOpTree cannot forward everything, only 'speculatable' instructions and loads that are known to not have changed.

Ok. So, this option will, in future cover https://reviews.llvm.org/D37337#859617 ?

Yes, although I think Tobias also had in mind what ForwardOpTree does today. Currently getScopStmt(Instruction*) allows returning only a single ScopStmt anyway, such that at this stage we cannot duplicate instructions into multiple statements. Although we could choose a 'primary' location for each instruction. There is definitely still room for improvement.

lib/Analysis/ScopBuilder.cpp

772

Former leaders may have merged into other leaders since it was added.

[grosser]

Hi Michael,

thanks for the update. Is the commit message up-to-date (AKA is the WIP still open or has it been resolved). Would be good to know before I start a more in-depth review!

Best,
Tobias

test/ScopInfo/granularity_scalar-indep.ll

5

interleaved

[Meinersbur]

In D38403#888103, @grosser wrote:

Hi Michael,

thanks for the update. Is the commit message up-to-date (AKA is the WIP still open or has it been resolved). Would be good to know before I start a more in-depth review!

The issue has been resolved bt commits rr314662 to r314665. I removed the [WIP] tag, but forgot to update the summary.

[bollu]

lib/Analysis/ScopBuilder.cpp

683

Just to clarify: An Instruction I is ordered if there exists an instruction J such that I; J != J; I, correct?

711

Consider joinPHIWritesToEpilogue?

771

Consider a name such as joinAllAfterEpilogue? I feel that this name carries the intent a little better.

test/ScopInfo/granularity_scalar-indep_noepilogue.ll

3 ↗

(On Diff #117659)

Nit: epilogie -> epilogue

[Meinersbur]

lib/Analysis/ScopBuilder.cpp

683

Not exactly, but it's the right idea.

Nit: Equality (!=) is not the right relation. If I;J is a tuple, then those are never equal. If it is a set, they are always equal. What you mean is some equivalence relation for semantics, which is difficult to define formally. I also don't intend to guarantee that if this function is true, that such an instruction J exists. Interactions with a third instruction K between I and J might also be possible, or depend on the code around. It is more that if it returns false and any permutation of non-ordered instructions have the same semantics in any context.

I'd stay with a verbal definition.

711

I call "epilogue" the last statement of a basic block where the PHI writes are added to. That is, PHI writes are always in the epilogue, whether this function is called or not.

More exact would be joinStatementsContainingDefinitionsOfIncomingValuesInSuccessorBlockWithEpilogue.

If PHI writes are added to the statement containing the definition instead of the writes, this function becomes useless. I hope to implement that sometime.

771

Good idea.

test/ScopInfo/granularity_scalar-indep.ll

5

thanks

test/ScopInfo/granularity_scalar-indep_noepilogue.ll

3 ↗

(On Diff #117659)

thanks

[bollu]

Thanks for the very clean patch :) I really like reviewing your code, it's always really well written.

lib/Analysis/ScopBuilder.cpp

683

Thanks for the correction!

Consider adding the explanation you just gave to the comment, in that case?

"An unordered instruction is an instruction, such that a sequence of unordered instructions can be permuted without changing semantics. An ordered instruction is an instruction that is not unordered."

[grosser]

Very cool. That looks good to me (after addressing Siddharth's comments).

lib/Analysis/ScopBuilder.cpp

681

its semantics

[Meinersbur]

• Address comments
• Fix return instead of continue bug

include/polly/ScopBuilder.h

class ScopBuilder {
   /// Should an instruction be modeled in a ScopStmt.
   ///
   /// @param Inst The instruction to check.
   /// @param L    The loop in which context the instruction is looked at.
   ///
   /// @returns True if the instruction should be modeled.
   bool shouldModelInst(Instruction *Inst, Loop *L);
 
+  void buildSequentialBlockStmts(BasicBlock *BB);
+
+  void buildEqivClassBlockStmts(BasicBlock *BB);
+
   /// Create ScopStmt for all BBs and non-affine subregions of @p SR.
   ///
   /// @param SR A subregion of @p R.
   ///
   /// Some of the statements might be optimized away later when they do not
   /// access any memory and thus have no effect.
   void buildStmts(Region &SR);
 

lib/Analysis/ScopBuilder.cpp

 #include "polly/ScopDetectionDiagnostic.h"
 #include "polly/ScopInfo.h"
 #include "polly/Support/SCEVValidator.h"
 #include "polly/Support/ScopHelper.h"
 #include "polly/Support/VirtualInstruction.h"
 #include "llvm/ADT/APInt.h"
 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/EquivalenceClasses.h"
 #include "llvm/ADT/SetVector.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/Analysis/OptimizationDiagnosticInfo.h"
 #include "llvm/Analysis/RegionInfo.h"
 #include "llvm/Analysis/RegionIterator.h"
 #include "llvm/Analysis/ScalarEvolution.h"

 // Multiplicative reductions can be disabled separately as these kind of
 // operations can overflow easily. Additive reductions and bit operations
 // are in contrast pretty stable.
 static cl::opt<bool> DisableMultiplicativeReductions(
     "polly-disable-multiplicative-reductions",
     cl::desc("Disable multiplicative reductions"), cl::Hidden, cl::ZeroOrMore,
     cl::init(false), cl::cat(PollyCategory));
 
+enum class GranularityChoice { BasicBlocks, ScalarIndepependence };
+
+static cl::opt<GranularityChoice> StmtGranularity(
+    "polly-stmt-granularity",
+    cl::desc("Select the statement granularity algorithm"),
+    cl::values(clEnumValN(GranularityChoice::BasicBlocks, "bb",
+                          "Entire basic blocks granularity"),
+               clEnumValN(GranularityChoice::ScalarIndepependence,
+                          "scalar-indep", "Scalar independence heuristic")),
+    cl::init(GranularityChoice::BasicBlocks), cl::cat(PollyCategory));
+
 void ScopBuilder::buildPHIAccesses(ScopStmt *PHIStmt, PHINode *PHI,
                                    Region *NonAffineSubRegion,
                                    bool IsExitBlock) {
   // PHI nodes that are in the exit block of the region, hence if IsExitBlock is
   // true, are not modeled as ordinary PHI nodes as they are not part of the
   // region. However, we model the operands in the predecessor blocks that are
   // part of the region as regular scalar accesses.
 
void ScopBuilder::buildAccessFunctions() {
   }
 }
 
 bool ScopBuilder::shouldModelInst(Instruction *Inst, Loop *L) {
   return !isa<TerminatorInst>(Inst) && !isIgnoredIntrinsic(Inst) &&
          !canSynthesize(Inst, *scop, &SE, L);
 }
 
+static bool isOrderedInstruction(const Instruction &Inst) {
+  return Inst.mayHaveSideEffects() || Inst.mayReadOrWriteMemory();
+}
+
+void ScopBuilder::buildSequentialBlockStmts(BasicBlock *BB) {
+  Loop *SurroundingLoop = LI.getLoopFor(BB);
+
+  int Count = 0;
+  std::vector<Instruction *> Instructions;
+  for (Instruction &Inst : *BB) {
+    if (shouldModelInst(&Inst, SurroundingLoop))
+      Instructions.push_back(&Inst);
+    if (Inst.getMetadata("polly_split_after")) {
+      scop->addScopStmt(BB, SurroundingLoop, Instructions, Count);
+      Count++;
+      Instructions.clear();
+    }
+  }
+
+  scop->addScopStmt(BB, SurroundingLoop, Instructions, Count);
+}
+
+void ScopBuilder::buildEqivClassBlockStmts(BasicBlock *BB) {
+  Loop *L = LI.getLoopFor(BB);
+
+  EquivalenceClasses<Instruction *> UnionFind;
+  Instruction *PHIWrites = nullptr;
+  UnionFind.insert(PHIWrites);
+  for (Instruction &Inst : *BB) {
+    if (!shouldModelInst(&Inst, L))
+      continue;
+    UnionFind.insert(&Inst);
+  }
+
+  // Ensure that instructions using the same scalar will be in the same
+  // statement.
+  for (Instruction &Inst : *BB) {
+    if (UnionFind.findValue(&Inst) == UnionFind.end())
+      continue;
+
+    if (auto PHI = dyn_cast<PHINode>(&Inst)) {
+      continue;
+    }
+
+    for (auto &Op : Inst.operands()) {
+      auto Def = dyn_cast<Instruction>(Op.get());
+      if (!Def)
+        continue;
+      if (Def->getParent() != BB)
+        continue;
+      if (UnionFind.findValue(Def) == UnionFind.end())
+        continue;
+      UnionFind.unionSets(&Inst, Def);
+    }
+  }
+
+  // Join the PHI write epilogue if necessary.
+  for (auto Succ : successors(BB)) {
+    for (auto &SuccInst : *Succ) {
+      auto SuccPHI = dyn_cast<PHINode>(&SuccInst);
+      if (!SuccPHI)
+        break;
+
+      auto IncomingVal = SuccPHI->getIncomingValueForBlock(BB);
+      auto IncomingInst = dyn_cast<Instruction>(IncomingVal);
+      if (!IncomingInst)
+        continue;
+      if (IncomingInst->getParent() != BB)
+        continue;
+      if (UnionFind.findValue(IncomingInst) == UnionFind.end())
+        continue;
+      UnionFind.unionSets(PHIWrites, IncomingInst);
+    }
+  }
+
+  // Ensure that the order of ordered instructions does not change.
+  SetVector<Instruction *> SeenLeaders; // TODO: Maybe string an iterator here
+                                        // would not make repeated
+                                        // getLeaderValue() necessary.
+  for (Instruction &Inst : *BB) {
+    if (!isOrderedInstruction(Inst))
+      continue;
+
+    auto LeaderIt = UnionFind.findLeader(&Inst);
+    if (LeaderIt == UnionFind.member_end())
+      continue;
+
+    auto Leader = *LeaderIt;
+    auto Inserted = SeenLeaders.insert(Leader);
+    if (Inserted)
+      continue;
+
+    for (auto Prev : reverse(SeenLeaders)) {
+      auto PrevLeader = UnionFind.getLeaderValue(SeenLeaders.back());
+      if (PrevLeader == Leader)
+        break;
+      UnionFind.unionSets(Prev, Leader);
+    }
+  }
+
+  SmallPtrSet<Instruction *, 16> ProcessedLeaders;
+  int Count = UnionFind.getNumClasses() > 1;
+  for (Instruction &Inst : *BB) {
+    auto LeaderIt = UnionFind.findLeader(&Inst);
+    assert((LeaderIt != UnionFind.member_end()) == shouldModelInst(&Inst, L));
+    if (LeaderIt == UnionFind.member_end())
+      continue;
+
+    auto Leader = *LeaderIt;
+    auto P = ProcessedLeaders.insert(Leader);
+    if (!P.second)
+      continue;
+
+    std::vector<Instruction *> Instructions;
+
+    // FIXME: Maybe we can avoid this nested loop; I am not sure whether
+    // UnionFind preserves the member's order.
+    for (Instruction &LeaderInst : *BB) {
+      auto LeaderInstLeaderIt = UnionFind.findLeader(&LeaderInst);
+      if (LeaderInstLeaderIt == UnionFind.member_end())
+        continue;
+
+      auto InstLeader = *LeaderInstLeaderIt;
+      if (InstLeader != Leader)
+        continue;
+
+      Instructions.push_back(&LeaderInst);
+    }
+
+    scop->addScopStmt(BB, L, Instructions, Count);
+    Count += 1;
+  }
+
+  auto EpiLeader = UnionFind.getLeaderValue(PHIWrites);
+  if (!ProcessedLeaders.count(EpiLeader))
+    scop->addScopStmt(BB, L, {}, Count);
+}
+
 void ScopBuilder::buildStmts(Region &SR) {
   if (scop->isNonAffineSubRegion(&SR)) {
     std::vector<Instruction *> Instructions;
     Loop *SurroundingLoop =
         getFirstNonBoxedLoopFor(SR.getEntry(), LI, scop->getBoxedLoops());
     for (Instruction &Inst : *SR.getEntry())
       if (shouldModelInst(&Inst, SurroundingLoop))
         Instructions.push_back(&Inst);
     scop->addScopStmt(&SR, SurroundingLoop, Instructions);
     return;
   }
 
   for (auto I = SR.element_begin(), E = SR.element_end(); I != E; ++I)
     if (I->isSubRegion())
       buildStmts(*I->getNodeAs<Region>());
     else {
-      int Count = 0;
-      std::vector<Instruction *> Instructions;
-      for (Instruction &Inst : *I->getNodeAs<BasicBlock>()) {
-        Loop *L = LI.getLoopFor(Inst.getParent());
-        if (shouldModelInst(&Inst, L))
-          Instructions.push_back(&Inst);
-        if (Inst.getMetadata("polly_split_after")) {
-          Loop *SurroundingLoop = LI.getLoopFor(I->getNodeAs<BasicBlock>());
-          scop->addScopStmt(I->getNodeAs<BasicBlock>(), SurroundingLoop,
-                            Instructions, Count);
-          Count++;
-          Instructions.clear();
-        }
+      auto *BB = I->getNodeAs<BasicBlock>();
+      switch (StmtGranularity) {
+      case GranularityChoice::BasicBlocks:
+        buildSequentialBlockStmts(BB);
+        break;
+      case GranularityChoice::ScalarIndepependence:
+        buildEqivClassBlockStmts(BB);
+        break;
       }
-      Loop *SurroundingLoop = LI.getLoopFor(I->getNodeAs<BasicBlock>());
-      scop->addScopStmt(I->getNodeAs<BasicBlock>(), SurroundingLoop,
-                        Instructions, Count);
     }
 }
 
 void ScopBuilder::buildAccessFunctions(ScopStmt *Stmt, BasicBlock &BB,
                                        Region *NonAffineSubRegion,
                                        bool IsExitBlock) {
   assert(
       !Stmt == IsExitBlock &&
       "The exit BB is the only one that cannot be represented by a statement");
   assert(IsExitBlock || Stmt->represents(&BB));
 
   // We do not build access functions for error blocks, as they may contain
   // instructions we can not model.
   if (isErrorBlock(BB, scop->getRegion(), LI, DT) && !IsExitBlock)
     return;
 
+  if (Stmt && Stmt->isBlockStmt() &&
+      (StmtGranularity == GranularityChoice::ScalarIndepependence)) {
+    // FIXME: Ugly workaround; Invariant loads should not be added to any
+    // statement in the first place.
+    if (Stmt == scop->getStmtListFor(&BB)[0]) {
+      for (auto &InvLoad : scop->getRequiredInvariantLoads()) {
+        if (InvLoad->getParent() != &BB)
+          continue;
+
+        // scop->getOrCreateScopArrayInfo(InvLoad->getPointerOperand(),
+        // InvLoad->getType(), { nullptr }, MemoryKind::Array);
+        auto Stmt = scop->getStmtListFor(&BB)[0];
+        buildMemoryAccess(MemAccInst(InvLoad), Stmt);
+      }
+    }
+
+    for (auto *Inst : Stmt->getInstructions()) {
+      PHINode *PHI = dyn_cast<PHINode>(Inst);
+      if (PHI)
+        buildPHIAccesses(Stmt, PHI, NonAffineSubRegion, IsExitBlock);
+      else
+        buildScalarDependences(Stmt, Inst);
+
+      if (auto MemInst = MemAccInst::dyn_cast(Inst)) {
+        assert(Stmt &&
+               "Cannot build access function in non-existing statement");
+        buildMemoryAccess(MemInst, Stmt);
+      }
+    }
+
+    for (Instruction &Inst : BB) {
+      buildEscapingDependences(&Inst);
+    }
+
+    return;
+  }
+
   int Count = 0;
   bool Split = false;
   for (Instruction &Inst : BB) {
     if (Split) {
       Split = false;
       Count++;
     }
     if (Inst.getMetadata("polly_split_after"))
return RN->isSubRegion() ? RN->getNodeAs<Region>()->getEntry()
                            : RN->getNodeAs<BasicBlock>();
 }
 
 void ScopBuilder::buildScop(Region &R, AssumptionCache &AC,
                             OptimizationRemarkEmitter &ORE) {
   scop.reset(new Scop(R, SE, LI, DT, *SD.getDetectionContext(&R), ORE));
 
   buildStmts(R);
+
+  //  auto &Inv = scop->getRequiredInvariantLoads();
+  //  for (auto &InvLoad : Inv) {
+  //    scop->getOrCreateScopArrayInfo(InvLoad->getPointerOperand(),
+  // InvLoad->getType(), {nullptr}, MemoryKind::Array);
+
+  //    auto Stmt = scop->getStmtListFor(InvLoad->getParent())[0];
+  //    buildMemoryAccess(MemAccInst( InvLoad), Stmt);
+  //  }
   buildAccessFunctions();
 
   // In case the region does not have an exiting block we will later (during
   // code generation) split the exit block. This will move potential PHI nodes
   // from the current exit block into the new region exiting block. Hence, PHI
   // nodes that are at this point not part of the region will be.
   // To handle these PHI nodes later we will now model their operands as scalar
   // accesses. Note that we do not model anything in the exit block if we have

test/ScopInfo/granularity_scalar-indep.ll

+; RUN: opt %loadPolly -polly-stmt-granularity=scalar-indep -polly-print-instructions -polly-scops -analyze < %s | FileCheck %s -match-full-lines
+;
+; Split a block into two independant statements that share no scalar.
+;
+; for (int j = 0; j < n; j += 1) {
+; bodyA:
+;   double val = B[j];
+;
+; bodyB:
+;   A[j] = val;
+; }
+;
+define void @func(i32 %n, double* noalias nonnull %A, double* noalias nonnull %B) {
+entry:
+  br label %for
+
+for:
+  %j = phi i32 [0, %entry], [%j.inc, %inc]
+  %j.cmp = icmp slt i32 %j, %n
+  br i1 %j.cmp, label %body, label %exit
+
+    body:
+      %valA = load double, double* %A
+      %valB = fadd double 21.0, 21.0
+      store double %valA, double* %A
+      store double %valB, double* %B
+      br label %inc
+
+inc:
+  %j.inc = add nuw nsw i32 %j, 1
+  br label %for
+
+exit:
+  br label %return
+
+return:
+  ret void
+}
+
+
+; CHECK:      Statements {
+; CHECK-NEXT:     Stmt_body1
+; CHECK-NEXT:         Domain :=
+; CHECK-NEXT:             [n] -> { Stmt_body1[i0] : 0 <= i0 < n };
+; CHECK-NEXT:         Schedule :=
+; CHECK-NEXT:             [n] -> { Stmt_body1[i0] -> [i0, 0] };
+; CHECK-NEXT:         ReadAccess :=       [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:             [n] -> { Stmt_body1[i0] -> MemRef_A[0] };
+; CHECK-NEXT:         MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:             [n] -> { Stmt_body1[i0] -> MemRef_A[0] };
+; CHECK-NEXT:         Instructions {
+; CHECK-NEXT:               %valA = load double, double* %A
+; CHECK-NEXT:               store double %valA, double* %A
+; CHECK-NEXT:         }
+; CHECK-NEXT:     Stmt_body2
+; CHECK-NEXT:         Domain :=
+; CHECK-NEXT:             [n] -> { Stmt_body2[i0] : 0 <= i0 < n };
+; CHECK-NEXT:         Schedule :=
+; CHECK-NEXT:             [n] -> { Stmt_body2[i0] -> [i0, 1] };
+; CHECK-NEXT:         MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:             [n] -> { Stmt_body2[i0] -> MemRef_B[0] };
+; CHECK-NEXT:         Instructions {
+; CHECK-NEXT:               %valB = fadd double 2.100000e+01, 2.100000e+01
+; CHECK-NEXT:               store double %valB, double* %B
+; CHECK-NEXT:         }
+; CHECK-NEXT: }