[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

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

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

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

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

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

In LLVM Variables start with uppercase letters.

Also, I would just call it "Instructions"

1253

Please use uppercase.

1540

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

2030

Uppercase, variable name.

lib/Analysis/ScopBuilder.cpp

635

Uppercase, variable name.

lib/Analysis/ScopInfo.cpp

1654

Uppercase variable name.

4663

Uppercase variable name.

test/ScopInfo/statement.ll

15

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!

include/polly/ScopInfo.h

struct InvariantEquivClassTy {
   ///
   /// These memory accesses access the pointer location that identifies
   /// this equivalence class. They are treated as invariant and hoisted during
   /// code generation.
   MemoryAccessList InvariantAccesses;
 
   /// The execution context under which the memory location is accessed
   ///
   /// It is the union of the execution domains of the memory accesses in the
   /// InvariantAccesses list.
   isl_set *ExecutionContext;
 
   /// The type of the invariant access
   ///
   /// It is used to differentiate between differently typed invariant loads from
   /// the same location.
   Type *AccessType;

 /// 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 *> bbInst);
 
   /// 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:
   ///
   /// Non-affine subregions can have multiple exiting blocks that are incoming
   /// blocks of the PHI nodes. This map ensures that there is only one write
   /// operation for the complete subregion. A PHI selecting the relevant value
   /// will be inserted.
   DenseMap<PHINode *, MemoryAccess *> PHIWrites;
 
   //@}
 
   /// A SCoP statement represents either a basic block (affine/precise case) or
   /// a whole region (non-affine case).
   ///
   /// Only one of the following two members will therefore be set and indicate
   /// which kind of statement this is.
   ///
   ///{
 
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 *> bbInst;
+
   /// Build the statement.
   //@{
   void buildDomain();
 
   /// Fill NestLoops with loops surrounding this statement.
   void collectSurroundingLoops();
 
   /// Build the access relation of all memory accesses.
MemoryAccess *lookupInputAccessOf(Value *Val) const {
     return nullptr;
   }
 
   /// Add @p Access to this statement's list of accesses.
   void addAccess(MemoryAccess *Access);
 
   /// Remove a MemoryAccess from this statement.
   ///
   /// Note that scalar accesses that are caused by MA will
   /// be eliminated too.
   void removeMemoryAccess(MemoryAccess *MA);
 
   /// Remove @p MA from this statement.
   ///
   /// In contrast to removeMemoryAccess(), no other access will be eliminated.
   void removeSingleMemoryAccess(MemoryAccess *MA);
 
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);
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);
+  void addScopStmt(BasicBlock *BB, Loop *SurroundingLoop,
+                   std::vector<Instruction *> bbInst);
 
   /// 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.

lib/Analysis/ScopBuilder.cpp

bool ScopBuilder::buildAccessMultiDimParam(MemAccInst Inst, ScopStmt *Stmt) {
   if (ElementSize != DelinearizedSize)
     scop->invalidate(DELINEARIZATION, Inst->getDebugLoc());
 
   addArrayAccess(Inst, AccType, BasePointer->getValue(), ElementType, true,
                  AccItr->second.DelinearizedSubscripts, Sizes, Val);
   return true;
 }
 
 bool ScopBuilder::buildAccessMemIntrinsic(MemAccInst Inst, ScopStmt *Stmt) {
   auto *MemIntr = dyn_cast_or_null<MemIntrinsic>(Inst);
 
   if (MemIntr == nullptr)
     return false;
 
   auto *L = LI.getLoopFor(Inst->getParent());
   auto *LengthVal = SE.getSCEVAtScope(MemIntr->getLength(), L);
   assert(LengthVal);
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 *> bbInst;
+      for (Instruction &Inst : *I->getNodeAs<BasicBlock>())
+        bbInst.push_back(&Inst);
       Loop *SurroundingLoop = LI.getLoopFor(I->getNodeAs<BasicBlock>());
-      scop->addScopStmt(I->getNodeAs<BasicBlock>(), SurroundingLoop);
+      scop->addScopStmt(I->getNodeAs<BasicBlock>(), SurroundingLoop, bbInst);
     }
 }
 
 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.

lib/Analysis/ScopInfo.cpp

 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 *> bbInst)
     : Parent(parent), InvalidDomain(nullptr), Domain(nullptr), BB(&bb),
-      R(nullptr), Build(nullptr), SurroundingLoop(SurroundingLoop) {
+      R(nullptr), Build(nullptr), SurroundingLoop(SurroundingLoop),
+      bbInst(bbInst) {
 
   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 : bbInst)
+    OS.indent(4) << *Inst << "\n";
+
+  OS.indent(4) << "}\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);
+
+  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;
mapToDimension(__isl_take isl_union_set *USet, int N) {
   (void)Res;
 
   assert(Res == isl_stat_ok);
 
   isl_union_set_free(USet);
   return isl_multi_union_pw_aff_from_union_pw_multi_aff(Data.Res);
 }
 
-void Scop::addScopStmt(BasicBlock *BB, Loop *SurroundingLoop) {
+void Scop::addScopStmt(BasicBlock *BB, Loop *SurroundingLoop,
+                       std::vector<Instruction *> bbInst) {
   assert(BB && "Unexpected nullptr!");
-  Stmts.emplace_back(*this, *BB, SurroundingLoop);
+  Stmts.emplace_back(*this, *BB, SurroundingLoop, bbInst);
   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();

test/ScopInfo/statement.ll

+; RUN: opt %loadPolly -polly-scops -analyze < %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:      %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
+; 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
+}