[Polly] [IslNodeBuilder] [NFC] Refactor materialization of loop induction variables of loops outside scops into a separate function.

[bollu]

Summary

Currently, this functionality is duplicated and the filtering of loops thattakes place in getReferencesInSubtree is not documented. Add some documentation
and centralise the materlization of the loop induction variables.

[philip.pfaffe]

Comments inline.

lib/CodeGen/IslNodeBuilder.cpp

317

contained

319

How are the Loops induction variables?

904

This requires documentation, and likely a static.

[bollu]

• [NFC] address phillip's comments

[bollu]

@grosser- ping?

[grosser]

LGTM.

[bollu]

Closed by rL310192. Not sure why Phab did not pick this up automatically, I had a Differential Revision: line in the commit.

include/polly/CodeGen/IslNodeBuilder.h

private:
   /// by the write memory access. @p NewAccesses contains for each access
   /// the isl ast expression that describes the location accessed.
   ///
   /// @param Stmt The copy statement that contains the accesses.
   /// @param NewAccesses The hash table that contains remappings from memory
   ///                    ids to new access expressions.
   void generateCopyStmt(ScopStmt *Stmt,
                         __isl_keep isl_id_to_ast_expr *NewAccesses);
+
+  /// Materialize a canonical loop induction variable for `L`, which is a loop
+  /// that is *not* present in the Scop.
+  ///
+  /// Note that this is materialized at the point where the `Builder` is
+  /// currently pointing.
+  /// We also populate the `OutsideLoopIterations` map with `L`s SCEV to keep
+  /// track of the induction variable.
+  /// See [Code generation of induction variables of loops outside Scops]
+  Value *materializeNonScopLoopInductionVariable(const Loop *L);
 };
 
 #endif // POLLY_ISL_NODE_BUILDER_H

lib/CodeGen/IslNodeBuilder.cpp

void IslNodeBuilder::getReferencesInSubtree(__isl_keep isl_ast_node *For,
 
   for (const SCEV *Expr : SCEVs) {
     findValues(Expr, SE, Values);
     findLoops(Expr, Loops);
   }
 
   Values.remove_if([](const Value *V) { return isa<GlobalValue>(V); });
 
+  /// Note: Code generation of induction variables of loops outside Scops
+  ///
   /// Remove loops that contain the scop or that are part of the scop, as they
   /// are considered local. This leaves only loops that are before the scop, but
   /// do not contain the scop itself.
+  /// We ignore loops perfectly contain the Scop because these are already
+  /// generated at `IslNodeBuilder::addParameters`. These `Loops` are loop
+  /// induction variables that are referred to by the Scop, but the Scop
+  /// is not fully contained in these Loops. Since there can be many of these,
+  /// we choose to codegen these on-demand.
+  /// @see IslNodeBuilder::materializeNonScopLoopInductionVariable.
   Loops.remove_if([this](const Loop *L) {
     return S.contains(L) || L->contains(S.getEntry());
   });
 
   // Contains Values that may need to be replaced with other values
   // due to replacements from the ValueMap. We should make sure
   // that we return correctly remapped values.
   // NOTE: this code path is tested by:
void IslNodeBuilder::createForParallel(__isl_take isl_ast_node *For) {
   SetVector<Value *> SubtreeValues;
   SetVector<const Loop *> Loops;
 
   getReferencesInSubtree(For, SubtreeValues, Loops);
 
   // Create for all loops we depend on values that contain the current loop
   // iteration. These values are necessary to generate code for SCEVs that
   // depend on such loops. As a result we need to pass them to the subfunction.
+  // See [Code generation of induction variables of loops outside Scops]
   for (const Loop *L : Loops) {
-    const SCEV *OuterLIV = SE.getAddRecExpr(SE.getUnknown(Builder.getInt64(0)),
-                                            SE.getUnknown(Builder.getInt64(1)),
-                                            L, SCEV::FlagAnyWrap);
-    Value *V = generateSCEV(OuterLIV);
-    OutsideLoopIterations[L] = SE.getUnknown(V);
-    SubtreeValues.insert(V);
+    Value *LoopInductionVar = materializeNonScopLoopInductionVariable(L);
+    SubtreeValues.insert(LoopInductionVar);
   }
 
   ValueMapT NewValues;
   ParallelLoopGenerator ParallelLoopGen(Builder, LI, DT, DL);
 
   IV = ParallelLoopGen.createParallelLoop(ValueLB, ValueUB, ValueInc,
                                           SubtreeValues, NewValues, &LoopBody);
   BasicBlock::iterator AfterLoop = Builder.GetInsertPoint();
auto *AccessExpr =
       isl_id_to_ast_expr_get(NewAccesses, (*ReadAccess)->getId().release());
   auto *LoadValue = ExprBuilder.create(AccessExpr);
   AccessExpr =
       isl_id_to_ast_expr_get(NewAccesses, (*WriteAccess)->getId().release());
   auto *StoreAddr = ExprBuilder.createAccessAddress(AccessExpr);
   Builder.CreateStore(LoadValue, StoreAddr);
 }
 
+Value *IslNodeBuilder::materializeNonScopLoopInductionVariable(const Loop *L) {
+  assert(OutsideLoopIterations.find(L) == OutsideLoopIterations.end() &&
+         "trying to materialize loop induction variable twice");
+  const SCEV *OuterLIV = SE.getAddRecExpr(SE.getUnknown(Builder.getInt64(0)),
+                                          SE.getUnknown(Builder.getInt64(1)), L,
+                                          SCEV::FlagAnyWrap);
+  Value *V = generateSCEV(OuterLIV);
+  OutsideLoopIterations[L] = SE.getUnknown(V);
+  return V;
+}
+
 void IslNodeBuilder::createUser(__isl_take isl_ast_node *User) {
   LoopToScevMapT LTS;
   isl_id *Id;
   ScopStmt *Stmt;
 
   isl_ast_expr *Expr = isl_ast_node_user_get_expr(User);
   isl_ast_expr *StmtExpr = isl_ast_expr_get_op_arg(Expr, 0);
   Id = isl_ast_expr_get_id(StmtExpr);
void IslNodeBuilder::addParameters(__isl_take isl_set *Context) {
   // not generate code for them here, but only at the point of code generation
   // where these values are needed.
   Loop *L = LI.getLoopFor(S.getEntry());
 
   while (L != nullptr && S.contains(L))
     L = L->getParentLoop();
 
   while (L != nullptr) {
-    const SCEV *OuterLIV = SE.getAddRecExpr(SE.getUnknown(Builder.getInt64(0)),
-                                            SE.getUnknown(Builder.getInt64(1)),
-                                            L, SCEV::FlagAnyWrap);
-    Value *V = generateSCEV(OuterLIV);
-    OutsideLoopIterations[L] = SE.getUnknown(V);
+    materializeNonScopLoopInductionVariable(L);
     L = L->getParentLoop();
   }
 
   isl_set_free(Context);
 }
 
 Value *IslNodeBuilder::generateSCEV(const SCEV *Expr) {
   /// We pass the insert location of our Builder, as Polly ensures during IR