[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

538–539

[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

671–674

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!

include/polly/ScopInfo.h

       return BB == getBasicBlock();
     return getRegion()->contains(BB);
   }
 
   /// Return whether this statement contains @p Inst.
   bool contains(Instruction *Inst) const {
     if (!Inst)
       return false;
+    if (isBlockStmt())
+      return std::find(Instructions.begin(), Instructions.end(), Inst) !=
+             Instructions.end();
     return represents(Inst->getParent());
   }
 
   /// Return the closest innermost loop that contains this statement, but is not
   /// contained in it.
   ///
   /// For block statement, this is just the loop that contains the block. Region
   /// statements can contain boxed loops, so getting the loop of one of the

   /// counter. By doing this, we guarantee that the context is deleted when we
   /// delete the last object that creates isl objects with the context.
   std::shared_ptr<isl_ctx> IslCtx;
 
   /// A map from basic blocks to vector of SCoP statements. Currently this
   /// vector comprises only of a single statement.
   DenseMap<BasicBlock *, std::vector<ScopStmt *>> StmtMap;
 
+  /// A map from instructions to SCoP statements.
+  DenseMap<Instruction *, ScopStmt *> InstStmtMap;
+
   /// A map from basic blocks to their domains.
   DenseMap<BasicBlock *, isl::set> DomainMap;
 
   /// Constraints on parameters.
   isl_set *Context;
 
   /// The affinator used to translate SCEVs to isl expressions.
   SCEVAffinator Affinator;

   std::string getContextStr() const;
 
   /// Get an isl string representing the assumed context.
   std::string getAssumedContextStr() const;
 
   /// Get an isl string representing the invalid context.
   std::string getInvalidContextStr() const;
 
-  /// Return the ScopStmt for the given @p BB or nullptr if there is
-  ///        none.
-  ScopStmt *getStmtFor(BasicBlock *BB) const;
-
   /// Return the list of ScopStmts that represent the given @p BB.
   ArrayRef<ScopStmt *> getStmtListFor(BasicBlock *BB) const;
 
   /// Return the last statement representing @p BB.
   ///
   /// Of the sequence of statements that represent a @p BB, this is the last one
   /// to be executed. It is typically used to determine which instruction to add
   /// a MemoryKind::PHI WRITE to. For this purpose, it is not strictly required
   /// to be executed last, only that the incoming value is available in it.
   ScopStmt *getLastStmtFor(BasicBlock *BB) const;
 
   /// Return the ScopStmts that represents the Region @p R, or nullptr if
   ///        it is not represented by any statement in this Scop.
   ArrayRef<ScopStmt *> getStmtListFor(Region *R) const;
 
   /// Return the ScopStmts that represents @p RN; can return nullptr if
   ///        the RegionNode is not within the SCoP or has been removed due to
   ///        simplifications.
   ArrayRef<ScopStmt *> getStmtListFor(RegionNode *RN) const;
 
   /// Return the ScopStmt an instruction belongs to, or nullptr if it
   ///        does not belong to any statement in this Scop.
   ScopStmt *getStmtFor(Instruction *Inst) const {
-    return getStmtFor(Inst->getParent());
+    return InstStmtMap.lookup(Inst);
   }
 
   /// Return the number of statements in the SCoP.
   size_t getSize() const { return Stmts.size(); }
 
   /// @name Statements Iterators
   ///
   /// These iterators iterate over all statements of this Scop.

lib/Analysis/ScopInfo.cpp

 void ScopStmt::addAccess(MemoryAccess *Access, bool Prepend) {
   Instruction *AccessInst = Access->getAccessInstruction();
 
   if (Access->isArrayKind()) {
     MemoryAccessList &MAL = InstructionToAccess[AccessInst];
     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;
   } else if (Access->isValueKind() && Access->isRead()) {
     Value *AccessVal = Access->getAccessValue();
     assert(!ValueReads.lookup(AccessVal));
 
     ValueReads[AccessVal] = Access;

 void Scop::assumeNoOutOfBounds() {
   for (auto &Stmt : *this)
     for (auto &Access : Stmt)
       Access->assumeNoOutOfBound();
 }
 
 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.getInstructions())
+      InstStmtMap.erase(Inst);
+  }
 }
 
 void Scop::removeStmts(std::function<bool(ScopStmt &)> ShouldDelete) {
   for (auto StmtIt = Stmts.begin(), StmtEnd = Stmts.end(); StmtIt != StmtEnd;) {
     if (!ShouldDelete(*StmtIt)) {
       StmtIt++;
       continue;
     }
 
     removeFromStmtMap(*StmtIt);
     StmtIt = Stmts.erase(StmtIt);
   }
 }
 
 void Scop::removeStmtNotInDomainMap() {
   auto ShouldDelete = [this](ScopStmt &Stmt) -> bool {
     return !this->DomainMap.lookup(Stmt.getEntryBlock());
   };
   removeStmts(ShouldDelete);
 }
 
 void Scop::simplifySCoP(bool AfterHoisting) {
 
   auto ShouldDelete = [AfterHoisting](ScopStmt &Stmt) -> bool {
     bool RemoveStmt = Stmt.isEmpty();
 
     // Remove read only statements only after invariant load hoisting.
     if (!RemoveStmt && AfterHoisting) {
       bool OnlyRead = true;
       for (MemoryAccess *MA : Stmt) {
         if (MA->isRead())
           continue;
 

     return nullptr;
 
   addAssumption(INVARIANTLOAD, WrittenCtx.copy(), LI->getDebugLoc(),
                 AS_RESTRICTION, LI->getParent());
   return WrittenCtx;
 }
 
 void Scop::verifyInvariantLoads() {
   auto &RIL = getRequiredInvariantLoads();
   for (LoadInst *LI : RIL) {
     assert(LI && contains(LI));
-    ScopStmt *Stmt = getStmtFor(LI);
-    if (Stmt && Stmt->getArrayAccessOrNULLFor(LI)) {
-      invalidate(INVARIANTLOAD, LI->getDebugLoc(), LI->getParent());
-      return;
-    }
+    // If there exists a statement in the scop which has a memory access for
+    // @p LI, then mark this scop as infeasible for optimization.
+    for (ScopStmt &Stmt : Stmts)
+      if (Stmt.getArrayAccessOrNULLFor(LI)) {
+        invalidate(INVARIANTLOAD, LI->getDebugLoc(), LI->getParent());
+        return;
+      }
   }
 }
 
 void Scop::hoistInvariantLoads() {
   if (!PollyInvariantLoadHoisting)
     return;
 
   isl::union_map Writes = getWrites();

 
 isl::schedule Scop::getScheduleTree() const {
   return isl::manage(isl_schedule_intersect_domain(isl_schedule_copy(Schedule),
                                                    getDomains().release()));
 }
 
 void Scop::setSchedule(__isl_take isl_union_map *NewSchedule) {
   auto *S = isl_schedule_from_domain(getDomains().release());
   S = isl_schedule_insert_partial_schedule(
       S, isl_multi_union_pw_aff_from_union_map(NewSchedule));
   isl_schedule_free(Schedule);
   Schedule = S;
 }
 
 void Scop::setScheduleTree(__isl_take isl_schedule *NewSchedule) {
   isl_schedule_free(Schedule);
   Schedule = NewSchedule;
 }
 
 bool Scop::restrictDomains(__isl_take isl_union_set *Domain) {
   bool Changed = false;
   for (ScopStmt &Stmt : *this) {
     isl_union_set *StmtDomain =
         isl_union_set_from_set(Stmt.getDomain().release());
     isl_union_set *NewStmtDomain = isl_union_set_intersect(
         isl_union_set_copy(StmtDomain), isl_union_set_copy(Domain));
 

   auto Result = isl::union_pw_multi_aff::empty(USet.get_space());
 
   auto Lambda = [&Result, N](isl::set S) -> isl::stat {
     int Dim = S.dim(isl::dim::set);
     auto PMA = isl::pw_multi_aff::project_out_map(S.get_space(), isl::dim::set,
                                                   N, Dim - N);
     if (N > 1)
       PMA = PMA.drop_dims(isl::dim::out, 0, N - 1);
 
     Result = Result.add_pw_multi_aff(PMA);
     return isl::stat::ok;
   };
 
   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,
                        std::vector<Instruction *> Instructions) {
   assert(BB && "Unexpected nullptr!");
   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::map SourceRel, isl::map TargetRel,
                             isl::set Domain) {
 #ifndef NDEBUG
   isl::set SourceDomain = SourceRel.domain();
   isl::set TargetDomain = TargetRel.domain();
   assert(Domain.is_subset(TargetDomain) &&

     auto &NextLoopData = LoopStack.back();
 
     if (Schedule) {
       isl::union_set Domain = give(isl_schedule_get_domain(Schedule));
       isl::multi_union_pw_aff MUPA = mapToDimension(Domain, LoopStack.size());
       Schedule = isl_schedule_insert_partial_schedule(Schedule, MUPA.release());
       NextLoopData.Schedule =
           combineInSequence(NextLoopData.Schedule, Schedule);
     }
 
     NextLoopData.NumBlocksProcessed += NumBlocksProcessed;
     LoopData = NextLoopData;
   }
 }
 
-ScopStmt *Scop::getStmtFor(BasicBlock *BB) const {
-  auto StmtMapIt = StmtMap.find(BB);
-  if (StmtMapIt == StmtMap.end())
-    return nullptr;
-  assert(StmtMapIt->second.size() == 1);
-  return StmtMapIt->second.front();
-}
-
 ArrayRef<ScopStmt *> Scop::getStmtListFor(BasicBlock *BB) const {
   auto StmtMapIt = StmtMap.find(BB);
   if (StmtMapIt == StmtMap.end())
     return {};
   assert(StmtMapIt->second.size() == 1 &&
          "Each statement corresponds to exactly one BB.");
   return StmtMapIt->second;
 }

lib/Transform/ForwardOpTree.cpp

ForwardingDecision forwardSpeculatable(ScopStmt *TargetStmt,
     //    because we do not forward PHINodes)
     // 4. Not leak memory if executed multiple times (i.e. malloc)
     //
     // Instruction::mayHaveSideEffects is not sufficient because it considers
     // malloc to not have side-effects. llvm::isSafeToSpeculativelyExecute is
     // not sufficient because it allows memory accesses.
     if (mayBeMemoryDependent(*UseInst))
       return FD_NotApplicable;
 
     if (DoIt) {
       // To ensure the right order, prepend this instruction before its
       // operands. This ensures that its operands are inserted before the
       // instruction using them.
       // TODO: The operand tree is not really a tree, but a DAG. We should be
       // able to handle DAGs without duplication.
       TargetStmt->prependInstruction(UseInst);
       NumInstructionsCopied++;
       TotalInstructionsCopied++;
case VirtualUse::Intra:
       // reuse the information about UseStmt for DefStmt
       DefStmt = UseStmt;
       DefToTarget = UseToTarget;
 
       LLVM_FALLTHROUGH;
     case VirtualUse::Inter:
       Instruction *Inst = cast<Instruction>(UseVal);
 
-      if (!DefStmt)
+      if (!DefStmt) {
         DefStmt = S->getStmtFor(Inst);
-      assert(DefStmt && "Value must be defined somewhere");
+        if (!DefStmt)
+          return FD_CannotForward;
+      }
+
       DefLoop = LI->getLoopFor(Inst->getParent());
 
       if (DefToTarget.is_null() && !Known.is_null()) {
         // { UseDomain[] -> DefDomain[] }
         isl::map UseToDef = computeUseToDefFlowDependency(UseStmt, DefStmt);
 
         // { DefDomain[] -> UseDomain[] -> TargetDomain[] } shortened to
         // { DefDomain[] -> TargetDomain[] }