[Polly] Added the list of Instructions to output in ScopInfo pass

[nandini12396]

Summary

This patch outputs all the list of instructions in BlockStmts.

[bollu]

@nandini12396: Thanks for the patch! Other than the minor nitpicks that I have, LGTM :)

Nitpick: I was hoping the patch could be submitted with context. By context, I mean the context not available that is written in the Phabricator UI. For a patch "with context", consider this one, where you have the: ▲ Show 20 Lines • Show All 57 Lines • ▼ Show 20 Line(s) available.

Generating Context:

Context using git:

If you are uploading patches directly using git, the way to generate context is by using git -U<number of lines> or git --unified=<number of lines>. I don't use this, but I believe @Meinersbur mentioned using that, and that he uses 99999 or some absurdly large number like that to get all the context.

TL,DR: $ git diff <branch> <other branch> -U999999

Context using arcanist:

I personally use arc, which is a command line tool for Phabricator. It handles a lot of the stuff for you, and I find the experience much nicer. There's some documentation on how to use it for LLVM here. arc automatically generates the context information, so it's somewhat easier to use.

Submitting a new patch:

arc-to-new-patch

$ arc diff --reviewers=efriedma,jdoerfert,Meinersbur,gareevroman,sebpop,zinob,huihuiz,pollydev,grosser,philip.pfaffe,etherzhhb master --nolint --nounit

• the --reviewers specifies who is reviewing the code. You can add / remove people from that list.
• --nolint --nounit asks arc to ignore running lint and unit tests, because Phabricator isn't setup to run these for LLVM is my understanding of this (I could be wrong, could someone confirm this?)
• master is the branch against which you want to generate the diff. this can be changed to another branch if you want to.

Updating a patch:

arc-to-update

$ arc diff --update D32639  master --nolint --nounit

• D32639 is the patch number. You can change this to D33163 for example for this case.
• Once again, master is the branch against which you want to diff.

Setting up arcanist:

If I recall correctly, you will need to setup git-svn to be able to use arcanist. There's not much to do, except to add these lines into the .git/config file inside your polly repository:

.git/config

...
[svn-remote "svn"]
  url = https://[e-mail]/svn/llvm-project/polly/trunk
  fetch = :refs/remotes/origin/master
...

• There are also general instructions for git-svn [documented here: LINK](http://llvm.org/docs/GettingStarted.html#developers-work-with-git-svn) should work.

• Setting up arcanist is somewhat annoying, but I believe it simplifies the experience of actually submitting a patch IMO.

include/polly/ScopInfo.h

1117 ↗

(On Diff #98891)

Would it be possible to have the std::vector<Instructor*> BBToInst be moved? As in, can the constructor be changed to:

new-constructor

ScopStmt(Scop &parent, BasicBlock &bb, Loop *SurroundingLoop,
         std::vector<Instruction *> &&BBToInst);

1225 ↗

(On Diff #98891)

Are there any uses of BBToInst other than to print the instructions? If not, can we change it to:

std::vector<const Instruction*> BBToInst;

If there are other uses where we mutate the Instruction, then this is perfectly fine.

1482 ↗

(On Diff #98891)

Could you please add a comment to printInstructions explaining what it does?

[Meinersbur]

I cannot apply the patch. Can you rebase to the latest trunk?

include/polly/ScopInfo.h

1225 ↗

(On Diff #98891)

Could you reconsider the name? BBToInst indicates a kind of map, and there are no BasicBlocks involed.

Please don't add const.

1. The instructions are going to be used for other things than printing them.
2. llvm::Instruction (or more generally, llvm::Value) is not a type intended to be passed const. Few functions, even not modifying the instruction take const Instruction* (such as ScalarEvolution::getSCEV)
3. llvm::Instruction is a type whose object's are identified by their address. That is, after modifying it (e.g. replaceAllUsesWith changes one of its operands), it is still considered the same instruction. const does not allow sich modifications.
4. llvm::Instruction uses intrusive linked links (such as ilist_node_with_parent<Instruction, BasicBlock>). That is, const inhibits changing in which such list the instruction is contained in.

lib/Analysis/ScopBuilder.cpp

427 ↗

(On Diff #98891)

You can move this declaration into the else branch, avoiding it being initialized when not used.

[grosser]

@nandini12396 : Hey Nandini, any update on this? ;-)

[nandini12396]

@bollu : Thank you very much for the detailed explanation. :) I will submit a patch with context from next time.
@Meinersbur ; I have rebased, changed the name of the list and moved the declaration to else.
@grosser : Sorry for delay. I will quickly update the diff after printing instructions per statement.

[grosser]

Hi Nandini,

any update? ;-)

[nandini12396]

Rebased and added context.

[nandini12396]

This comment was removed by nandini12396.

[grosser]

Hi Nandini,

thanks for the update. Find below some more comments.

I also saw that with your patch we currently get 118 unexpected failures when running 'make check-polly'. They seem to be caused because we print instructions now always. I think this might be too verbose in general. Can we make instruction printing optional and hide it behind a flag?

include/polly/ScopInfo.h

1145 ↗

(On Diff #100290)

In LLVM Variables start with uppercase letters.

Also, I would just call it "Instructions"

1253 ↗

(On Diff #100290)

Please use uppercase.

1540 ↗

(On Diff #100290)

Add an empty line between print() and the comment that follows it.

2030 ↗

(On Diff #100290)

Uppercase, variable name.

lib/Analysis/ScopBuilder.cpp

635 ↗

(On Diff #100290)

Uppercase, variable name.

lib/Analysis/ScopInfo.cpp

1654 ↗

(On Diff #100290)

Uppercase variable name.

4663 ↗

(On Diff #100290)

Uppercase variable name.

test/ScopInfo/statement.ll

15 ↗

(On Diff #100290)

These CHECK lines do not seem correct. If I run

po -polly-process-unprofitable  -polly-remarks-minimal  -polly-use-llvm-names  -polly-scops -analyze < /home/grosser/Projects/polly/git/tools/polly/test/ScopInfo/statement.ll

I get:

Statements {
	Stmt_Stmt
        Domain :=
            { Stmt_Stmt[i0] : 0 <= i0 <= 1023 };
        Schedule :=
            { Stmt_Stmt[i0] -> [i0] };
        MustWriteAccess :=	[Reduction Type: NONE] [Scalar: 0]
            { Stmt_Stmt[i0] -> MemRef_A[i0] };
        MustWriteAccess :=	[Reduction Type: NONE] [Scalar: 0]
            { Stmt_Stmt[i0] -> MemRef_B[i0] };
        Instructions {
  %idxprom = sext i32 %i.0 to i64
  %arrayidx = getelementptr inbounds i32, i32* %A, i64 %idxprom
  store i32 %i.0, i32* %arrayidx, align 4
  %idxprom1 = sext i32 %i.0 to i64
  %arrayidx2 = getelementptr inbounds i32, i32* %B, i64 %idxprom1
  store i32 %i.0, i32* %arrayidx2, align 4
  br label %for.inc
}
}

These four "CHECK" lines do not make sense:

; CHECK-NEXT:      %i.0 = phi i32 [ 0, %entry ], [ %add, %for.inc ]
​; CHECK-NEXT:      %cmp = icmp slt i32 %i.0, 1024
​; CHECK-NEXT:      br i1 %cmp, label %for.body, label %for.end
; CHECK-NEXT:      br label %Stmt

Also, the indentation seems off.

[nandini12396]

Addressed comments given by Tobias Sir.

[grosser]

Thank you Nandini, this looks good. I committed the change!

polly/trunk/include/polly/ScopInfo.h

 /// accesses.
 /// At the moment every statement represents a single basic block of LLVM-IR.
 class ScopStmt {
 public:
   ScopStmt(const ScopStmt &) = delete;
   const ScopStmt &operator=(const ScopStmt &) = delete;
 
   /// Create the ScopStmt from a BasicBlock.
-  ScopStmt(Scop &parent, BasicBlock &bb, Loop *SurroundingLoop);
+  ScopStmt(Scop &parent, BasicBlock &bb, Loop *SurroundingLoop,
+           std::vector<Instruction *> Instructions);
 
   /// Create an overapproximating ScopStmt for the region @p R.
   ScopStmt(Scop &parent, Region &R, Loop *SurroundingLoop);
 
   /// Create a copy statement.
   ///
   /// @param Stmt       The parent statement.
   /// @param SourceRel  The source location.
private:
 
   SmallVector<Loop *, 4> NestLoops;
 
   std::string BaseName;
 
   /// The closest loop that contains this statement.
   Loop *SurroundingLoop;
 
+  /// Vector for Instructions in a BB.
+  std::vector<Instruction *> Instructions;
+
   /// Build the statement.
   //@{
   void buildDomain();
 
   /// Fill NestLoops with loops surrounding this statement.
   void collectSurroundingLoops();
 
   /// Build the access relation of all memory accesses.
public:
   /// Align the parameters in the statement to the scop context
   void realignParams();
 
   /// Print the ScopStmt.
   ///
   /// @param OS The output stream the ScopStmt is printed to.
   void print(raw_ostream &OS) const;
 
+  /// Print the instructions in ScopStmt.
+  ///
+  void printInstructions(raw_ostream &OS) const;
+
   /// Print the ScopStmt to stderr.
   void dump() const;
 };
 
 /// Print ScopStmt S to raw_ostream O.
 static inline raw_ostream &operator<<(raw_ostream &O, const ScopStmt &S) {
   S.print(O);
   return O;
private:
   /// Create a new SCoP statement for @p BB.
   ///
   /// A new statement for @p BB will be created and added to the statement
   /// vector
   /// and map.
   ///
   /// @param BB              The basic block we build the statement for.
   /// @param SurroundingLoop The loop the created statement is contained in.
-  void addScopStmt(BasicBlock *BB, Loop *SurroundingLoop);
+  /// @param Instructions    The instructions in the basic block.
+  void addScopStmt(BasicBlock *BB, Loop *SurroundingLoop,
+                   std::vector<Instruction *> Instructions);
 
   /// 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.

polly/trunk/lib/Analysis/ScopBuilder.cpp

if (scop->isNonAffineSubRegion(&SR)) {
     scop->addScopStmt(&SR, SurroundingLoop);
     return;
   }
 
   for (auto I = SR.element_begin(), E = SR.element_end(); I != E; ++I)
     if (I->isSubRegion())
       buildStmts(*I->getNodeAs<Region>());
     else {
+      std::vector<Instruction *> Instructions;
+      for (Instruction &Inst : *I->getNodeAs<BasicBlock>())
+        Instructions.push_back(&Inst);
       Loop *SurroundingLoop = LI.getLoopFor(I->getNodeAs<BasicBlock>());
-      scop->addScopStmt(I->getNodeAs<BasicBlock>(), SurroundingLoop);
+      scop->addScopStmt(I->getNodeAs<BasicBlock>(), SurroundingLoop,
+                        Instructions);
     }
 }
 
 void ScopBuilder::buildAccessFunctions(BasicBlock &BB,
                                        Region *NonAffineSubRegion,
                                        bool IsExitBlock) {
   // We do not build access functions for error blocks, as they may contain
   // instructions we can not model.

polly/trunk/lib/Analysis/ScopInfo.cpp

 
 bool polly::UseInstructionNames;
 static cl::opt<bool, true> XUseInstructionNames(
     "polly-use-llvm-names",
     cl::desc("Use LLVM-IR names when deriving statement names"),
     cl::location(UseInstructionNames), cl::Hidden, cl::init(false),
     cl::ZeroOrMore, cl::cat(PollyCategory));
 
+static cl::opt<bool> PollyPrintInstructions(
+    "polly-print-instructions", cl::desc("Output instructions per ScopStmt"),
+    cl::Hidden, cl::Optional, cl::init(false), cl::cat(PollyCategory));
+
 //===----------------------------------------------------------------------===//
 
 // Create a sequence of two schedules. Either argument may be null and is
 // interpreted as the empty schedule. Can also return null if both schedules are
 // empty.
 static __isl_give isl_schedule *
 combineInSequence(__isl_take isl_schedule *Prev,
                   __isl_take isl_schedule *Succ) {

 ScopStmt::ScopStmt(Scop &parent, Region &R, Loop *SurroundingLoop)
     : Parent(parent), InvalidDomain(nullptr), Domain(nullptr), BB(nullptr),
       R(&R), Build(nullptr), SurroundingLoop(SurroundingLoop) {
 
   BaseName = getIslCompatibleName(
       "Stmt", R.getNameStr(), parent.getNextStmtIdx(), "", UseInstructionNames);
 }
 
-ScopStmt::ScopStmt(Scop &parent, BasicBlock &bb, Loop *SurroundingLoop)
+ScopStmt::ScopStmt(Scop &parent, BasicBlock &bb, Loop *SurroundingLoop,
+                   std::vector<Instruction *> Instructions)
     : Parent(parent), InvalidDomain(nullptr), Domain(nullptr), BB(&bb),
-      R(nullptr), Build(nullptr), SurroundingLoop(SurroundingLoop) {
+      R(nullptr), Build(nullptr), SurroundingLoop(SurroundingLoop),
+      Instructions(Instructions) {
 
   BaseName = getIslCompatibleName("Stmt", &bb, parent.getNextStmtIdx(), "",
                                   UseInstructionNames);
 }
 
 ScopStmt::ScopStmt(Scop &parent, __isl_take isl_map *SourceRel,
                    __isl_take isl_map *TargetRel, __isl_take isl_set *NewDomain)
     : Parent(parent), InvalidDomain(nullptr), Domain(NewDomain), BB(nullptr),
__isl_give isl_id *ScopStmt::getDomainId() const {
   return isl_set_get_tuple_id(Domain);
 }
 
 ScopStmt::~ScopStmt() {
   isl_set_free(Domain);
   isl_set_free(InvalidDomain);
 }
 
+void ScopStmt::printInstructions(raw_ostream &OS) const {
+  OS << "Instructions {\n";
+
+  for (Instruction *Inst : Instructions)
+    OS.indent(16) << *Inst << "\n";
+
+  OS.indent(16) << "}\n";
+}
+
 void ScopStmt::print(raw_ostream &OS) const {
   OS << "\t" << getBaseName() << "\n";
   OS.indent(12) << "Domain :=\n";
 
   if (Domain) {
     OS.indent(16) << getDomainStr() << ";\n";
   } else
     OS.indent(16) << "n/a\n";
 
   OS.indent(12) << "Schedule :=\n";
 
   if (Domain) {
     OS.indent(16) << getScheduleStr() << ";\n";
   } else
     OS.indent(16) << "n/a\n";
 
   for (MemoryAccess *Access : MemAccs)
     Access->print(OS);
+
+  if (PollyPrintInstructions)
+    printInstructions(OS.indent(12));
 }
 
 void ScopStmt::dump() const { print(dbgs()); }
 
 void ScopStmt::removeAccessData(MemoryAccess *MA) {
   if (MA->isRead() && MA->isOriginalValueKind()) {
     bool Found = ValueReads.erase(MA->getAccessValue());
     (void)Found;
static isl::multi_union_pw_aff mapToDimension(isl::union_set USet, int N) {
   isl::stat Res = USet.foreach_set(Lambda);
   (void)Res;
 
   assert(Res == isl::stat::ok);
 
   return isl::multi_union_pw_aff(isl::union_pw_multi_aff(Result));
 }
 
-void Scop::addScopStmt(BasicBlock *BB, Loop *SurroundingLoop) {
+void Scop::addScopStmt(BasicBlock *BB, Loop *SurroundingLoop,
+                       std::vector<Instruction *> Instructions) {
   assert(BB && "Unexpected nullptr!");
-  Stmts.emplace_back(*this, *BB, SurroundingLoop);
+  Stmts.emplace_back(*this, *BB, SurroundingLoop, Instructions);
   auto *Stmt = &Stmts.back();
   StmtMap[BB] = Stmt;
 }
 
 void Scop::addScopStmt(Region *R, Loop *SurroundingLoop) {
   assert(R && "Unexpected nullptr!");
   Stmts.emplace_back(*this, *R, SurroundingLoop);
   auto *Stmt = &Stmts.back();

polly/trunk/test/ScopInfo/statement.ll

+; RUN: opt %loadPolly -polly-scops -analyze -polly-print-instructions < %s | FileCheck %s
+
+;      void func(int *A, int *B){
+;        for (int i = 0; i < 1024; i+=1) {
+;      Stmt:
+;          A[i] = i;
+;          B[i] = i;
+;        }
+;      }
+
+; CHECK:       Instructions {
+; CHECK-NEXT:      %idxprom = sext i32 %i.0 to i64
+; CHECK-NEXT:      %arrayidx = getelementptr inbounds i32, i32* %A, i64 %idxprom
+; CHECK-NEXT:      store i32 %i.0, i32* %arrayidx, align 4
+; CHECK-NEXT:      %idxprom1 = sext i32 %i.0 to i64
+; CHECK-NEXT:      %arrayidx2 = getelementptr inbounds i32, i32* %B, i64 %idxprom1
+; CHECK-NEXT:      store i32 %i.0, i32* %arrayidx2, align 4
+; CHECK-NEXT:      br label %for.inc
+; CHECK-NEXT:    }
+
+; Function Attrs: noinline nounwind uwtable
+define void @func(i32* %A, i32* %B) #0 {
+entry:
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.inc, %entry
+  %i.0 = phi i32 [ 0, %entry ], [ %add, %for.inc ]
+  %cmp = icmp slt i32 %i.0, 1024
+  br i1 %cmp, label %for.body, label %for.end
+
+for.body:                                         ; preds = %for.cond
+  br label %Stmt
+
+Stmt:                                             ; preds = %for.body
+  %idxprom = sext i32 %i.0 to i64
+  %arrayidx = getelementptr inbounds i32, i32* %A, i64 %idxprom
+  store i32 %i.0, i32* %arrayidx, align 4
+  %idxprom1 = sext i32 %i.0 to i64
+  %arrayidx2 = getelementptr inbounds i32, i32* %B, i64 %idxprom1
+  store i32 %i.0, i32* %arrayidx2, align 4
+  br label %for.inc
+
+for.inc:                                          ; preds = %Stmt
+  %add = add nsw i32 %i.0, 1
+  br label %for.cond
+
+for.end:                                          ; preds = %for.cond
+  ret void
+}