[Polly] Remove dependency of `Scop::getStmtFor(Inst)` on `getStmtFor(BB)`. [NFC].

[nandini12396]

Summary

We are working towards removing uses of Scop::getStmtFor(BB). In this patch, we remove dependency of Scop::getStmtFor(Inst) on getStmtFor(BB). To do so, we introduce a map of instructions to their corresponding scop statements and use it to get the instructions' statement.

[Meinersbur]

This is good, just the additional assertion would be nice.

lib/Analysis/ScopInfo.cpp

4759

[Suggestion] Could you add an assertion here that checks that the instruction is not yet mapped to something else?

4769

Here too.

[nandini12396]

Addressed comments.

[Meinersbur]

lib/Analysis/ScopInfo.cpp

4829–4830

[Serious] InstStmtMap[&Inst] modifies the map inside an assert statement. Such side-effects may cause Polly to behave differently in debug than in release builds. While currently the element is added anyway, some future change may add the element only under some condition and forget this assert that still adds it. It is good practice to avoid side-effects in asserts in the first place.

Please use InstStmtMap.count(&Inst) instead.

[Meinersbur]

lib/Analysis/ScopInfo.cpp

5003–5006

I think

return InstStmtMap.lookup(Inst);

does exactly the same.

[Meinersbur]

lib/Analysis/ScopInfo.cpp

4828

To fix the fx_basic_util_crash.ll case, only map the instructions that are actually in the statement (The Instructions vector).

However, this causes 31 other tests to break, particularly on assert(Parent.getStmtFor(AccessVal) == this). That assertion can be removed, it is suficient if the value is syntesizable in the statement.

Then there are still 3 other failing tests remaining.

[nandini12396]

lib/Analysis/ScopInfo.cpp

4829–4830

Sure.

5003–5006

Done. Thank you.

[nandini12396]

lib/Analysis/ScopInfo.cpp

4828

yes, I had earlier inserted only the instructions of the Instructions vector into the Map. But I reverted because I didnt understand how can this be a non-functional change?
Apart from that assertion for me, only 2 other tests fail on !Inst->mayReadOrWriteMemory(). Im thinking why so..
And Im also thinking why this should fix the fx_basic_util_crash.ll case.

[nandini12396]

lib/Analysis/ScopInfo.cpp

4828

Oh, I see. Sorry, I missed your comment about the test case where you said "We should probably not try to verify the arguments of synthesizable instructions."

[Meinersbur]

lib/Analysis/ScopInfo.cpp

4828

But I reverted because I didnt understand how can this be a non-functional change?

It is "No Functional Change Intended". We want Polly to behave exactly the same, but prepare for necessary later changes. Even if it means we break internal interfaces.

In this case, once we split a BB into two statement, we have don't know to which statement associate a synthesiable instruction. It might be used in both, yet getInstruction() of neither contains it.

The straightforward thing is to not associate with any of them. getStmtFor(Instruction*) must not return a statement. The alternatives would be adding it to both/all statement's instruction list or one of them arbitrarily. Maybe you have an argument why one of them is better?

Preparing for instructions that belong to no statement must therefore be done anyway.

[Meinersbur]

lib/Analysis/ScopInfo.cpp

3804

[Serious] Only remove those in the statement's instruction list. Otherwise this also removes the links of all other statements representing this BasicBlock.

[nandini12396]

@Meinersbur : This change leads to failure of ForwardOpTree/noforward_synthesizable_unknownit.ll because getStmtFor synthesizable instruction returns nullptr, which makes DefStmt null in line 227.

[Meinersbur]

This is an interesting case because %i.trunc is synthesizable within the loop, but not outside of it.

What getStmtFor(BB) is trying to get here is some statement where it transfer the llvm::Value from (using a MemoryKind::Value WRITE/READ pair).

A "sophisticated" solution would be to select one statement in the loop (the last would be good) and insert a MemoryKind::Value WRITE there.

A simple solution, which is also the status quo before this patch, is to bail out (return FD_CannotForward)

[nandini12396]

Rebase & fix test-case failure as suggested.

[Meinersbur]

lib/Analysis/ScopInfo.cpp

4095

[Suggestion] Could you add a comment what is happening here?

lib/Transform/ForwardOpTree.cpp

164 ↗

(On Diff #109948)

[Serious] The statement where UseInst is defined should be the preferred one. The last statement of a BasicBlock is only a backup. Using any BB else than the preferred one would require to add another scalar write (currently not implemented in ForwardOpTree), which is what -polly-optree is trying to avoid.

The case is probably rare enough that we could also just return FD_CannotForward.

if (!DefStmt)
  return FD_CannotForward;

Note that in a recent commit this line has been moved to forwardTree.

[nandini12396]

Address comments

[Meinersbur]

lib/Transform/ForwardOpTree.cpp

669 ↗

(On Diff #110279)

Please don't use assignments in conditionals (unless its an initializer of an inline variable declaration). It's hard to see whether its a typo of (==) or meant to have side-effects.

[nandini12396]

split if condition.

[Meinersbur]

LGTM.

Thanks a lot!

lib/Analysis/ScopInfo.cpp

     MAL.emplace_front(Access);
   } else if (Access->isValueKind() && Access->isWrite()) {
     Instruction *AccessVal = cast<Instruction>(Access->getAccessValue());
-    assert(Parent.getStmtFor(AccessVal) == this);
     assert(!ValueWrites.lookup(AccessVal));
 
     ValueWrites[AccessVal] = Access;

 
 void Scop::removeFromStmtMap(ScopStmt &Stmt) {
   if (Stmt.isRegionStmt())
-    for (BasicBlock *BB : Stmt.getRegion()->blocks())
+    for (BasicBlock *BB : Stmt.getRegion()->blocks()) {
       StmtMap.erase(BB);
-  else
+      for (Instruction &Inst : *BB)
+        InstStmtMap.erase(&Inst);
+    }
+  else {
     StmtMap.erase(Stmt.getBasicBlock());
+    for (Instruction &Inst : *Stmt.getBasicBlock())
+      InstStmtMap.erase(&Inst);
+  }
 }
 
 void Scop::removeStmts(std::function<bool(ScopStmt &)> ShouldDelete) {

   Stmts.emplace_back(*this, *BB, SurroundingLoop, Instructions);
   auto *Stmt = &Stmts.back();
   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) {
   assert(R && "Unexpected nullptr!");
   Stmts.emplace_back(*this, *R, SurroundingLoop);
   auto *Stmt = &Stmts.back();
-  for (BasicBlock *BB : R->blocks())
+  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;
+    }
+  }
 }
 
 ScopStmt *Scop::addScopStmt(__isl_take isl_map *SourceRel,