[Polly] Workaround for SDiv/SRem referenced from SCEVExpander

[Meinersbur]

Summary

polly::SCEVValidator extends the notion of ScalarEvolution values by allowing SDiv and SRem instructions in them. These are handled by polly::SCEVAffinator, but not by llvm::SCEVExpander. SCEVExpander instead references the original values that might be defined only afterwards.

This patch is a workaround by copying those referenceable SDivs/SRems to the polly.start block where the SCEV is expanded and can use the copied instructions. This pessimistically copies values even if not used by any SCoP parameter to avoid making SCEVExpander generate illegal code and recursivity.

Ideally, one introduces SCEVSDiv and SCEVSRem classes to get rid of this and other such workarounds in Polly.

[jdoerfert]

Some initial questions to get an idea of this patch.

lib/CodeGen/IslNodeBuilder.cpp

58

Why do we need this?

724

What type does Inst have if not Instruction &?

731

How can we look at an instruction twice (if we always copy the instruction as noted below)?

737

Can we just copy it without all the checks if we can move it?

[Meinersbur]

Note that I I hope this is a temporary workaround and we can get LLVM to implement SCEVSRemExpr and SCEVSDivExpr.

lib/CodeGen/IslNodeBuilder.cpp

58

LLVM defines SDivOperator, but not SRemOperator

724

The worklist push below is of type llvm::User*, but it might indeed be unnecessary here (and below since the cast has already been done)

731

If used in operands of two instructions?!? I obviously don't understand your question.

737

The move in the comment is outdated. I tried to move it in an previous implementation and found that moving doesn't come without problems.

There is still nothing to do if SCEVValidator rejected it.

[jdoerfert]

Some comments and a proposal.

lib/CodeGen/IslNodeBuilder.cpp

58

Why don't you cast to SRem and SDiv instructions instead of operators?

724

I do not see anything of type User between 720 and 727 but as long as we agree that the cast is not necessary I don't care.

737

Wait, moving doesn't come with problems or does? If the latter, which problems?

My proposal is not to move instructions at all but copy the SDiv and SRem instructions including the operands trees to the new location. Can you comment on that?

[grosser]

Hi Michael,

I just committed another test case (test/Isl/CodeGen/inner_scev_2.ll) that has a similar problem, but unfortunately still fails with this patch applied.

In general, I think your approach of moving the relevant instructions out of the scop is a good one, but just seems to be a little incomplete.

One very similar approach could be to go

codgenSCEV(SCEV S)

1. Scan S for SCEV Unknowns X that refer to instructions in SCoP
2. for each operand Op of X: a) get SCEV of Op b) codegenSCEV(SCEV of Op) c) create new instruction that uses the newly code generated operands as input
3. Replace all X with new instructions
4. Only now SCEVExpand the SCEV (after we know it has no problematic SCEUnknowns any more)

Maybe this gives you some inspiration of how to go ahead.

Best,
Tobias

[jdoerfert]

In D12053#225339, @grosser wrote:

codgenSCEV(SCEV S)

1. Scan S for SCEV Unknowns X that refer to instructions in SCoP
2. for each operand Op of X: a) get SCEV of Op b) codegenSCEV(SCEV of Op) c) create new instruction that uses the newly code generated operands as input
3. Replace all X with new instructions
4. Only now SCEVExpand the SCEV (after we know it has no problematic SCEUnknowns any more)

Maybe this gives you some inspiration of how to go ahead.

I was actually thinking something similar and apperently it works for the two test cases at hand and regardless where (in which kind of SCEV) the SDiv/SRem are hiding. See: http://reviews.llvm.org/D12066

lib/CodeGen/IslNodeBuilder.cpp

58

I got it,.. you would need to use the opcode instead.

[grosser]

Very cool, I think this makes sense.

Michael, as you had a close look into this already, I would be interested what you think
about this approach?

Best,
Tobias

jdoerfert added a comment.

In http://reviews.llvm.org/D12053#225339, @grosser wrote:

codgenSCEV(SCEV S)

1. Scan S for SCEV Unknowns X that refer to instructions in SCoP
2. for each operand Op of X: a) get SCEV of Op b) codegenSCEV(SCEV of Op) c) create new instruction that uses the newly code generated operands as input
3. Replace all X with new instructions
4. Only now SCEVExpand the SCEV (after we know it has no problematic SCEUnknowns any more)
   
   Maybe this gives you some inspiration of how to go ahead.

I was actually thinking something similar and apperently it works for the two test cases at hand and regardless where (in which kind of SCEV) the SDiv/SRem are hiding. See: http://reviews.llvm.org/D12066

Comment at: lib/CodeGen/IslNodeBuilder.cpp:58
@@ -53,1 +57,3 @@
+}
+

__isl_give isl_ast_expr *

---

jdoerfert wrote:

Meinersbur wrote:

jdoerfert wrote:

Why do we need this?

LLVM defines SDivOperator, but not SRemOperator

Why don't you cast to SRem and SDiv instructions instead of operators?

I got it,.. you would need to use the opcode instead.

http://reviews.llvm.org/D12053

[Meinersbur]

Abandoned in favor of D12066 or some more general solution in ScalarEvolution itself.

include/polly/CodeGen/IslNodeBuilder.h

   // ivs.
   IslExprBuilder::IDToValueTy IDToValue;
 
+  /// @brief Move SDiv and SRem instructions to before the region.
+  ///
+  /// SCEVValidator accepts SDiv and SRem instruction for which no SCEV
+  /// representation exists. Correspondingly, SCEVExpander does not generate
+  /// code for it and instead directly uses the result of the SDiv/SRem
+  /// instructions. Those might be defined only in the region and hence
+  /// referencing them in the prologue setting up parameters yields invalid
+  /// code.
+  /// We avoid this by moving all SDivs and SRems to before the prologue so
+  /// referencing them for parameters is valid.
+  ///
+  /// @param ValueReplacer Receives the associations of values defined inside
+  /// the SCoP to equivalent ones available at the entry of the optimized SCoP.
+  void moveInvariantDivRem(ValueToValueMap &ValueReplacer);
+
   /// Generate code for a given SCEV*
   ///
   /// This function generates code for a given SCEV expression. It generated

lib/CodeGen/IslNodeBuilder.cpp

 using namespace polly;
 using namespace llvm;
 
+namespace llvm {
+// Missing in LLVM
+class SRemOperator
+    : public ConcreteOperator<PossiblyExactOperator, Instruction::SRem> {};
+}
+
 __isl_give isl_ast_expr *
 IslNodeBuilder::getUpperBound(__isl_keep isl_ast_node *For,
                               ICmpInst::Predicate &Predicate) {

   llvm_unreachable("Unknown isl_ast_node type");
 }
 
+void IslNodeBuilder::moveInvariantDivRem(ValueToValueMap &ValueReplacer) {
+  Region &R = S.getRegion();
+  auto &InsertLocation = *(--(Builder.GetInsertBlock()->end()));
+  auto InsertBlock = InsertLocation.getParent();
+  assert(!R.contains(InsertBlock));
+
+  SmallVector<Instruction *, 64> Worklist;
+  for (auto BB : R.blocks()) {
+    for (auto &Inst : *BB) {
+      if (isa<SDivOperator>(Inst) || isa<SRemOperator>(Inst))
+        Worklist.push_back(&cast<Instruction>(Inst));
+    }
+  }
+
+  while (!Worklist.empty()) {
+    auto Item = Worklist.pop_back_val();
+    if (ValueReplacer.count(Item))
+      continue; // Already processed
+
+    // This is the condition SCEVValidator uses to accept an SDiv/SRem as valid
+    // SCEV. If not accepted, we also do not need to move it.
+    if (!isa<ConstantInt>(Item->getOperand(1)))
+      continue;
+
+    bool DepWithinRegion = false;
+    for (auto &Op : Item->operands()) {
+      auto Scev = SE.getSCEV(&*Op);
+      if (hasScalarDepsInsideRegion(Scev, &R)) {
+        DepWithinRegion = true;
+        break;
+      }
+    }
+    if (DepWithinRegion)
+      continue; // Not movable
+
+    auto NewItem = Item->clone();
+    ValueReplacer[Item] = NewItem;
+    for (auto &Op : NewItem->operands()) {
+      const SCEV *Scev = SE.getSCEV(&*Op);
+      Scev = SCEVParameterRewriter::rewrite(Scev, SE, ValueReplacer);
+      auto NewOperand = generateSCEV(Scev);
+      Op.set(NewOperand);
+    }
+    InsertBlock->getInstList().insert(InsertLocation, NewItem);
+
+    // Maybe users of the moved SDiv/SRem can now be moved as well.
+    for (auto User : Item->users()) {
+      if (!isa<Instruction>(User))
+        continue;
+      auto UserInst = cast<Instruction>(User);
+
+      if (!R.contains(UserInst))
+        continue;
+
+      if (isa<SDivOperator>(UserInst) || isa<SRemOperator>(UserInst))
+        Worklist.push_back(cast<Instruction>(UserInst));
+    }
+  }
+}
+
 void IslNodeBuilder::addParameters(__isl_take isl_set *Context) {
+  Region &R = S.getRegion();
 
+  ValueToValueMap ParamValueReplacer;
+  moveInvariantDivRem(ParamValueReplacer);
   for (unsigned i = 0; i < isl_set_dim(Context, isl_dim_param); ++i) {
     isl_id *Id;
 
     Id = isl_set_get_dim_id(Context, isl_dim_param, i);
-    IDToValue[Id] = generateSCEV((const SCEV *)isl_id_get_user(Id));
+    const SCEV *Scev = (const SCEV *)isl_id_get_user(Id);
+    // Scev may reference value definitions from inside the SCoP. Replace them
+    // with equivalant definitions defined in the polly.start block.
+    Scev = SCEVParameterRewriter::rewrite(Scev, SE, ParamValueReplacer);
+    assert(!hasScalarDepsInsideRegion(Scev, &R));
+    IDToValue[Id] = generateSCEV(Scev);
 
     isl_id_free(Id);
   }

   // scop itself, but as the number of such scops may be arbitrarily large we do
   // not generate code for them here, but only at the point of code generation
   // where these values are needed.
-  Region &R = S.getRegion();
   Loop *L = LI.getLoopFor(R.getEntry());
 
   while (L != nullptr && R.contains(L))

test/Isl/CodeGen/inner_scev.ll

-; RUN: opt %loadPolly -S -polly-no-early-exit -polly-detect-unprofitable -polly-codegen < %s
+; RUN: opt %loadPolly -S -polly-no-early-exit -polly-detect-unprofitable -polly-codegen < %s | FileCheck %s
 ;
 ; Excerpt from the test-suite's oggenc reduced using bugpoint.
 ;

 ; computation of the SCEV to before the scop that references %div44, which is
 ; not available then.
 ;
-; XFAIL: *
+; CHECK-LABEL: polly.split_new_and_old:
+; CHECK:         sdiv i64 0, 2
+; CHECK:         sext i32 %4 to i64
+; CHECK-LABEL: for.cond.30.preheader:
 ;
+; CHECK-LABEL: polly.cond:
+; CHECK:         %14 = sext i32 %2 to i64
+
 target triple = "x86_64-unknown-linux-gnu"
 
 define void @_vorbis_apply_window(float* %d) {