[ScopInfo] Use statement lists for entry blocks of region statements

[grosser]

Summary

By using statement lists in the entry blocks of region statements, instruction
level analyses also work on region statements.

We currently only model the entry block of a region statements, as this is
sufficient for most transformations the known-passes currently execute. Modeling
instructions in the presence of control flow (e.g. infinite loops) is left
out to not increase code complexity too much. It can be added when good use
cases are found.

[BlockGenerator] Generate entry block of regions from instruction lists

The adds code generation support for the previous commit.

[Meinersbur]

I don't see any correctness issues: LGTM.

include/polly/ScopInfo.h

1209

Instead of passing std::vector by value, wouldn't it be better to pass an ArrayRef?

lib/Analysis/ScopBuilder.cpp

667–670

Can we refactor this shared code (with block stmts) into e.g. common function?

lib/Analysis/ScopInfo.cpp

1684

Empty line?

3596–3597

This code is also shared with the block stmt case.

3600–3601

Should this be

if (BB != Stmt.getEntryBlock())
   continue;

?

lib/CodeGen/BlockGenerators.cpp

458

Simpler: Stmt.getEntryBlock() == BB which should work for the block stmt and region stmt case.

However, your version makes it more explicit what was intended.

[grosser]

include/polly/ScopInfo.h

1209

Possibly, but I wanted to mirror the existing code. I will commit this as a follow up cleanup.

lib/Analysis/ScopBuilder.cpp

667–670

I extracted out a method shouldModelInst. I could not include the loop, as I did not yet want to allow statement
splitting in region statements.

lib/Analysis/ScopInfo.cpp

3596–3597

Pulled out.

3600–3601

No. I added a comment:

// Skip entry basic block, as its instructions are already deleted as      
// part of the statement's instruction list.

lib/CodeGen/BlockGenerators.cpp

458

OK, then I will leave my code.

[grosser]

This was committed in 312211.

include/polly/ScopInfo.h

class ScopStmt {
   friend class ScopBuilder;
 
 public:
   /// Create the ScopStmt from a BasicBlock.
   ScopStmt(Scop &parent, BasicBlock &bb, Loop *SurroundingLoop,
            std::vector<Instruction *> Instructions, int Count);
 
   /// Create an overapproximating ScopStmt for the region @p R.
-  ScopStmt(Scop &parent, Region &R, Loop *SurroundingLoop);
+  ///
+  /// @param EntryBlockInstructions The list of instructions that belong to the
+  ///                               entry block of the region statement.
+  ///                               Instructions are only tracked for entry
+  ///                               blocks for now. We currently do not allow
+  ///                               to modify the instructions of blocks later
+  ///                               in the region statement.
+  ScopStmt(Scop &parent, Region &R, Loop *SurroundingLoop,
+           std::vector<Instruction *> EntryBlockInstructions);
 
   /// Create a copy statement.
   ///
   /// @param Stmt       The parent statement.
   /// @param SourceRel  The source location.
   /// @param TargetRel  The target location.
   /// @param Domain     The original domain under which the copy statement would
   ///                   be executed.
private:
   void addScopStmt(BasicBlock *BB, Loop *SurroundingLoop,
                    std::vector<Instruction *> Instructions, int Count);
 
   /// Create a new SCoP statement for @p R.
   ///
   /// A new statement for @p R will be created and added to the statement vector
   /// and map.
   ///
-  /// @param R               The region we build the statement for.
-  /// @param SurroundingLoop The loop the created statement is contained in.
-  void addScopStmt(Region *R, Loop *SurroundingLoop);
+  /// @param R                      The region we build the statement for.
+  /// @param SurroundingLoop        The loop the created statement is contained
+  ///                               in.
+  /// @param EntryBlockInstructions The (interesting) instructions in the
+  ///                               entry block of the region statement.
+  void addScopStmt(Region *R, Loop *SurroundingLoop,
+                   std::vector<Instruction *> EntryBlockInstructions);
 
   /// Update access dimensionalities.
   ///
   /// When detecting memory accesses different accesses to the same array may
   /// have built with different dimensionality, as outer zero-values dimensions
   /// may not have been recognized as separate dimensions. This function goes
   /// again over all memory accesses and updates their dimensionality to match
   /// the dimensionality of the underlying ScopArrayInfo object.

lib/Analysis/ScopBuilder.cpp

for (auto &Stmt : *scop) {
     Region *R = Stmt.getRegion();
     for (BasicBlock *BB : R->blocks())
       buildAccessFunctions(&Stmt, *BB, R);
   }
 }
 
 void ScopBuilder::buildStmts(Region &SR) {
   if (scop->isNonAffineSubRegion(&SR)) {
+    std::vector<Instruction *> Instructions;
     Loop *SurroundingLoop =
         getFirstNonBoxedLoopFor(SR.getEntry(), LI, scop->getBoxedLoops());
-    scop->addScopStmt(&SR, SurroundingLoop);
+    for (Instruction &Inst : *SR.getEntry())
+      if (!isa<TerminatorInst>(&Inst) && !isIgnoredIntrinsic(&Inst) &&
+          !canSynthesize(&Inst, *scop, &SE, 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;

lib/Analysis/ScopInfo.cpp

buildConditionSets(Scop &S, BasicBlock *BB, TerminatorInst *TI, Loop *L,
 
   Value *Condition = getConditionFromTerminator(TI);
   assert(Condition && "No condition for Terminator");
 
   return buildConditionSets(S, BB, Condition, TI, L, Domain, InvalidDomainMap,
                             ConditionSets);
 }
 
-ScopStmt::ScopStmt(Scop &parent, Region &R, Loop *SurroundingLoop)
+ScopStmt::ScopStmt(Scop &parent, Region &R, Loop *SurroundingLoop,
+                   std::vector<Instruction *> EntryBlockInstructions)
     : Parent(parent), InvalidDomain(nullptr), Domain(nullptr), R(&R),
-      Build(nullptr), SurroundingLoop(SurroundingLoop) {
+      Build(nullptr), SurroundingLoop(SurroundingLoop),
+      Instructions(EntryBlockInstructions)
+
+{
   BaseName = getIslCompatibleName(
       "Stmt", R.getNameStr(), parent.getNextStmtIdx(), "", UseInstructionNames);
 }
 
 ScopStmt::ScopStmt(Scop &parent, BasicBlock &bb, Loop *SurroundingLoop,
                    std::vector<Instruction *> Instructions, int Count)
     : Parent(parent), InvalidDomain(nullptr), Domain(nullptr), BB(&bb),
       Build(nullptr), SurroundingLoop(SurroundingLoop),
void ScopStmt::print(raw_ostream &OS, bool PrintInstructions) const {
   if (Domain) {
     OS.indent(16) << getScheduleStr() << ";\n";
   } else
     OS.indent(16) << "n/a\n";
 
   for (MemoryAccess *Access : MemAccs)
     Access->print(OS);
 
-  if (PrintInstructions && isBlockStmt())
+  if (PrintInstructions)
     printInstructions(OS.indent(12));
 }
 
 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
 LLVM_DUMP_METHOD void ScopStmt::dump() const { print(dbgs(), true); }
 #endif
 
 void ScopStmt::removeAccessData(MemoryAccess *MA) {

 
 void Scop::assumeNoOutOfBounds() {
   for (auto &Stmt : *this)
     for (auto &Access : Stmt)
       Access->assumeNoOutOfBound();
 }
 
 void Scop::removeFromStmtMap(ScopStmt &Stmt) {
-  if (Stmt.isRegionStmt())
+  if (Stmt.isRegionStmt()) {
+    for (Instruction *Inst : Stmt.getInstructions())
+      InstStmtMap.erase(Inst);
     for (BasicBlock *BB : Stmt.getRegion()->blocks()) {
       StmtMap.erase(BB);
+      if (BB == Stmt.getEntryBlock())
+        continue;
       for (Instruction &Inst : *BB)
         InstStmtMap.erase(&Inst);
     }
-  else {
+  } else {
     StmtMap.erase(Stmt.getBasicBlock());
     for (Instruction *Inst : Stmt.getInstructions())
       InstStmtMap.erase(Inst);
   }
 }
 
 void Scop::removeStmts(std::function<bool(ScopStmt &)> ShouldDelete) {
   for (auto StmtIt = Stmts.begin(), StmtEnd = Stmts.end(); StmtIt != StmtEnd;) {
void Scop::addScopStmt(BasicBlock *BB, Loop *SurroundingLoop,
   StmtMap[BB].push_back(Stmt);
   for (Instruction *Inst : Instructions) {
     assert(!InstStmtMap.count(Inst) &&
            "Unexpected statement corresponding to the instruction.");
     InstStmtMap[Inst] = Stmt;
   }
 }
 
-void Scop::addScopStmt(Region *R, Loop *SurroundingLoop) {
+void Scop::addScopStmt(Region *R, Loop *SurroundingLoop,
+                       std::vector<Instruction *> Instructions) {
   assert(R && "Unexpected nullptr!");
-  Stmts.emplace_back(*this, *R, SurroundingLoop);
+  Stmts.emplace_back(*this, *R, SurroundingLoop, Instructions);
   auto *Stmt = &Stmts.back();
   for (BasicBlock *BB : R->blocks()) {
     StmtMap[BB].push_back(Stmt);
     for (Instruction &Inst : *BB) {
       assert(!InstStmtMap.count(&Inst) &&
              "Unexpected statement corresponding to the instruction.");
       InstStmtMap[&Inst] = Stmt;
     }

lib/CodeGen/BlockGenerators.cpp

BasicBlock *BlockGenerator::copyBB(ScopStmt &Stmt, BasicBlock *BB,
   return CopyBB;
 }
 
 void BlockGenerator::copyBB(ScopStmt &Stmt, BasicBlock *BB, BasicBlock *CopyBB,
                             ValueMapT &BBMap, LoopToScevMapT &LTS,
                             isl_id_to_ast_expr *NewAccesses) {
   EntryBB = &CopyBB->getParent()->getEntryBlock();
 
-  if (Stmt.isBlockStmt())
+  // Block statements and the entry blocks of region statement are code
+  // generated from instruction lists. This allow us to optimize the
+  // instructions that belong to a certain scop statement. As the code
+  // structure of region statements might be arbitrary complex, optimizing the
+  // instruction list is not yet supported.
+  if (Stmt.isBlockStmt() || (Stmt.isRegionStmt() && Stmt.getEntryBlock() == BB))
     for (Instruction *Inst : Stmt.getInstructions())
       copyInstruction(Stmt, Inst, BBMap, LTS, NewAccesses);
   else
     for (Instruction &Inst : *BB)
       copyInstruction(Stmt, &Inst, BBMap, LTS, NewAccesses);
 }
 
 Value *BlockGenerator::getOrCreateAlloca(const MemoryAccess &Access) {

test/Isl/CodeGen/partial_write_in_region_with_loop.ll

 ; RUN: opt %loadPolly -polly-import-jscop \
 ; RUN: -polly-import-jscop-postfix=transformed -polly-codegen \
 ; RUN: -verify-dom-info -polly-allow-nonaffine-loops \
 ; RUN: -S < %s | FileCheck %s
 
 ; This test verifies that partial writes within non-affine loops are code
 ; generated correctly.
 
 ; CHECK:polly.stmt.bb3:
 ; CHECK-NEXT:  %polly.subregion.iv = phi i32 [ %polly.subregion.iv.inc, %polly.stmt.bb5.cont ], [ 0, %polly.stmt.bb3.entry ]
 ; CHECK-NEXT:  %polly.j.0 = phi i64 [ %j.0.phiops.reload, %polly.stmt.bb3.entry ], [ %p_tmp10, %polly.stmt.bb5.cont ]
-; CHECK-NEXT:  %p_tmp = mul nsw i64 %polly.indvar, %polly.indvar
-; CHECK-NEXT:  %p_tmp4 = icmp slt i64 %polly.j.0, %p_tmp
+; CHECK-NEXT:  %8 = zext i64 %polly.indvar to i65
+; CHECK-NEXT:  %9 = add i64 %polly.indvar, -1
+; CHECK-NEXT:  %10 = zext i64 %9 to i65
+; CHECK-NEXT:  %11 = mul i65 %8, %10
+; CHECK-NEXT:  %12 = lshr i65 %11, 1
+; CHECK-NEXT:  %13 = trunc i65 %12 to i64
+; CHECK-NEXT:  %14 = shl i64 %13, 1
+; CHECK-NEXT:  %15 = add i64 %polly.indvar, %14
+; CHECK-NEXT:  %p_tmp4 = icmp slt i64 %polly.j.0, %15
 ; CHECK-NEXT:  %polly.subregion.iv.inc = add i32 %polly.subregion.iv, 1
 ; CHECK-NEXT:  br i1 %p_tmp4, label %polly.stmt.bb5, label %polly.stmt.bb11.exit
 
 ; CHECK:polly.stmt.bb5:
 ; CHECK-NEXT:  %p_tmp6 = getelementptr inbounds float, float* %B, i64 42
 ; CHECK-NEXT:  %tmp7_p_scalar_ = load float, float* %p_tmp6
 ; CHECK-NEXT:  %p_tmp8 = fadd float %tmp7_p_scalar_, 1.000000e+00
-; CHECK-NEXT:  %8 = icmp sle i64 %polly.indvar, 9
-; CHECK-NEXT:  %polly.Stmt_bb3__TO__bb11_MayWrite2.cond = icmp ne i1 %8, false
+; CHECK-NEXT:  %16 = icmp sle i64 %polly.indvar, 9
+; CHECK-NEXT:  %polly.Stmt_bb3__TO__bb11_MayWrite2.cond = icmp ne i1 %16, false
 ; CHECK-NEXT:  br i1 %polly.Stmt_bb3__TO__bb11_MayWrite2.cond, label %polly.stmt.bb5.Stmt_bb3__TO__bb11_MayWrite2.partial, label %polly.stmt.bb5.cont
 
 ; CHECK:polly.stmt.bb5.Stmt_bb3__TO__bb11_MayWrite2.partial: ; preds = %polly.stmt.bb5
 ; CHECK-NEXT:  %polly.access.B3 = getelementptr float, float* %B, i64 42
 ; CHECK-NEXT:  store float %p_tmp8, float* %polly.access.B3
 ; CHECK-NEXT:  br label %polly.stmt.bb5.cont
 
 ; CHECK:polly.stmt.bb5.cont:

test/Isl/CodeGen/region-with-instructions.ll

+; RUN: opt %loadPolly -polly-codegen -S < %s | FileCheck %s
+
+; CHECK-LABEL:   polly.stmt.bb48:
+; CHECK-NEXT:   %scevgep = getelementptr i64, i64* %A, i64 %polly.indvar
+; CHECK-NEXT:   %tmp51_p_scalar_ = load i64, i64* %scevgep,
+; CHECK-NEXT:   %p_tmp52 = and i64 %tmp51_p_scalar_, %tmp26
+; CHECK-NEXT:   %p_tmp53 = icmp eq i64 %p_tmp52, %tmp26
+; CHECK-NEXT:   store i64 42, i64* %scevgep, align 8
+; CHECK-NEXT:   br i1 %p_tmp53, label %polly.stmt.bb54, label %polly.stmt.bb56.exit
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+define void @quux(i32 %arg, i32 %arg1, i64* %A, i64 %tmp9, i64 %tmp24, i64 %tmp14, i64 %tmp22, i64 %tmp44) {
+bb:
+  %tmp26 = or i64 %tmp22, %tmp24
+  br label %bb39
+
+bb39:                                             ; preds = %bb39, %bb38
+  %tmp45 = icmp eq i64 %tmp44, %tmp9
+  br i1 %tmp45, label %bb46, label %bb81
+
+bb46:                                             ; preds = %bb39
+  %tmp47 = or i64 1, %tmp14
+  br label %bb48
+
+bb48:                                             ; preds = %bb56, %bb46
+  %tmp49 = phi i64 [ 0, %bb46 ], [ %tmp57, %bb56 ]
+  %tmp50 = getelementptr inbounds i64, i64* %A, i64 %tmp49
+  %tmp51 = load i64, i64* %tmp50, align 8
+  %tmp52 = and i64 %tmp51, %tmp26
+  %tmp53 = icmp eq i64 %tmp52, %tmp26
+  store i64 42, i64* %tmp50, align 8
+  br i1 %tmp53, label %bb54, label %bb56
+
+bb54:                                             ; preds = %bb48
+  %tmp55 = xor i64 %tmp51, %tmp47
+  store i64 %tmp55, i64* %tmp50, align 8
+  br label %bb56
+
+bb56:                                             ; preds = %bb54, %bb48
+  %tmp57 = add nuw nsw i64 %tmp49, 1
+  %tmp58 = icmp eq i64 %tmp57, %tmp9
+  br i1 %tmp58, label %bb81, label %bb48
+
+bb81:                                             ; preds = %bb74, %bb56
+  ret void
+}

test/ScopInfo/region-with-instructions.ll

+; RUN: opt %loadPolly -polly-scops -analyze -polly-print-instructions \
+; RUN:     < %s | FileCheck %s
+
+; CHECK: Statements {
+; CHECK:  Stmt_bb46
+; CHECK:         Domain :=
+; CHECK:             [tmp44, tmp9] -> { Stmt_bb46[] : tmp9 = tmp44 };
+; CHECK:         Schedule :=
+; CHECK:             [tmp44, tmp9] -> { Stmt_bb46[] -> [0, 0] };
+; CHECK:         MustWriteAccess := [Reduction Type: NONE] [Scalar: 1]
+; CHECK:             [tmp44, tmp9] -> { Stmt_bb46[] -> MemRef_tmp47[] };
+; CHECK:         Instructions {
+; CHECK:               %tmp47 = or i64 1, %tmp14
+; CHECK:         }
+; CHECK:  Stmt_bb48__TO__bb56
+; CHECK:         Domain :=
+; CHECK:             [tmp44, tmp9] -> { Stmt_bb48__TO__bb56[i0] : tmp9 = tmp44 and 0 <= i0 < tmp44 };
+; CHECK:         Schedule :=
+; CHECK:             [tmp44, tmp9] -> { Stmt_bb48__TO__bb56[i0] -> [1, i0] };
+; CHECK:         ReadAccess :=  [Reduction Type: NONE] [Scalar: 0]
+; CHECK:             [tmp44, tmp9] -> { Stmt_bb48__TO__bb56[i0] -> MemRef_A[i0] };
+; CHECK:         MustWriteAccess := [Reduction Type: NONE] [Scalar: 0]
+; CHECK:             [tmp44, tmp9] -> { Stmt_bb48__TO__bb56[i0] -> MemRef_A[i0] };
+; CHECK:         ReadAccess :=  [Reduction Type: NONE] [Scalar: 1]
+; CHECK:             [tmp44, tmp9] -> { Stmt_bb48__TO__bb56[i0] -> MemRef_tmp47[] };
+; CHECK:         MayWriteAccess :=  [Reduction Type: NONE] [Scalar: 0]
+; CHECK:             [tmp44, tmp9] -> { Stmt_bb48__TO__bb56[i0] -> MemRef_A[i0] };
+; CHECK:         Instructions {
+; CHECK:               %tmp51 = load i64, i64* %tmp50, align 8
+; CHECK:               %tmp52 = and i64 %tmp51, %tmp26
+; CHECK:               %tmp53 = icmp eq i64 %tmp52, %tmp26
+; CHECK:               store i64 42, i64* %tmp50, align 8
+; CHECK:         }
+; CHECK: }
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+define void @quux(i32 %arg, i32 %arg1, i64* %A, i64 %tmp9, i64 %tmp24, i64 %tmp14, i64 %tmp22, i64 %tmp44) {
+bb:
+  %tmp26 = or i64 %tmp22, %tmp24
+  br label %bb39
+
+bb39:                                             ; preds = %bb39, %bb38
+  %tmp45 = icmp eq i64 %tmp44, %tmp9
+  br i1 %tmp45, label %bb46, label %bb81
+
+bb46:                                             ; preds = %bb39
+  %tmp47 = or i64 1, %tmp14
+  br label %bb48
+
+bb48:                                             ; preds = %bb56, %bb46
+  %tmp49 = phi i64 [ 0, %bb46 ], [ %tmp57, %bb56 ]
+  %tmp50 = getelementptr inbounds i64, i64* %A, i64 %tmp49
+  %tmp51 = load i64, i64* %tmp50, align 8
+  %tmp52 = and i64 %tmp51, %tmp26
+  %tmp53 = icmp eq i64 %tmp52, %tmp26
+  store i64 42, i64* %tmp50, align 8
+  br i1 %tmp53, label %bb54, label %bb56
+
+bb54:                                             ; preds = %bb48
+  %tmp55 = xor i64 %tmp51, %tmp47
+  store i64 %tmp55, i64* %tmp50, align 8
+  br label %bb56
+
+bb56:                                             ; preds = %bb54, %bb48
+  %tmp57 = add nuw nsw i64 %tmp49, 1
+  %tmp58 = icmp eq i64 %tmp57, %tmp9
+  br i1 %tmp58, label %bb81, label %bb48
+
+bb81:                                             ; preds = %bb74, %bb56
+  ret void
+}

test/ScopInfo/stmt_split_exit_of_region_stmt.ll

 ; RUN: opt %loadPolly -polly-scops -analyze -polly-print-instructions < %s | FileCheck %s
 ;
 ; CHECK:    Statements {
 ; CHECK-NEXT:   Stmt_Region__TO__Stmt
 ; CHECK-NEXT:       Domain :=
 ; CHECK-NEXT:           { Stmt_Region__TO__Stmt[i0] : 0 <= i0 <= 1023 };
 ; CHECK-NEXT:       Schedule :=
 ; CHECK-NEXT:           { Stmt_Region__TO__Stmt[i0] -> [i0, 0] };
 ; CHECK-NEXT:       MayWriteAccess := [Reduction Type: NONE] [Scalar: 0]
 ; CHECK-NEXT:           { Stmt_Region__TO__Stmt[i0] -> MemRef_C[0] };
+; CHECK-NEXT:       Instructions {
+; CHECK-NEXT:             %cond = fcmp oeq double 2.100000e+01, 2.100000e+01
+; CHECK-NEXT:       }
 ; CHECK-NEXT:   Stmt_Stmt
 ; CHECK-NEXT:       Domain :=
 ; CHECK-NEXT:           { Stmt_Stmt[i0] : 0 <= i0 <= 1023 };
 ; CHECK-NEXT:       Schedule :=
 ; CHECK-NEXT:           { Stmt_Stmt[i0] -> [i0, 1] };
 ; CHECK-NEXT:       MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 0]
 ; CHECK-NEXT:           { Stmt_Stmt[i0] -> MemRef_A[i0] };
 ; CHECK-NEXT:       Instructions {