[Polly] Do not store scalar accesses in InstructionToAccess

[Meinersbur]

Summary

At code generation, scalar reads are generated before the other statement's instructions, respectively scalar writes after them, in contrast to array accesses which are "executed" with the instructions they are linked to. Therefore it makes sense to not map the scalar accesses to a place of execution. Follow-up patches (e.g. D13762) will also remove some of the directs links from a scalar access to a single instruction, such that only having array accesses in InstructionToAccess ensures its consistency.

[grosser]

Hi Michael,

the patch looks generally fine. I am only slightly concerned your removal of the instruction to multiple read/write accesses. As it seems to not be strictly necessary, I wonder if we should rather leave the multi read/write accesses in?

include/polly/ScopInfo.h

811

I understand that with the currently supported features we now only have a single read/write access per statement, but I do not think this will/should hold in general. If we e.g. model function calls or intrinsics like _atomic_exchange_n this won't hold any more. Hence, I personally would prefer to not specialize too much here.

959

trailing

lib/Analysis/ScopInfo.cpp

3967

This pattern seems rather repetitive. It happens five times at least. Does it make sense to add the "if (!Acc) ..." part directly to addMemoryAccess?

[grosser]

This comment was removed by grosser.

[jdoerfert]

include/polly/ScopInfo.h

814

Now that I think about it, maybe leading and trailing is not the best wording here. While it is literally true, it doesn't help to understand why they are leading/trailing. Maybe if we combine leading with the DependentScalars from D13611 and and rename trailing writes in escaping writes the purpose/need becomes clear.

lib/Analysis/ScopInfo.cpp

1483–1485

You mentioned at some point we should extract the "removeMemoryAccesses" from this function and I now see the need. In D13611 this happened we could use some fancy lambda magic like this to get rid of the weird traversal order if we can still get the same "runtime".

lib/CodeGen/BlockGenerators.cpp

390–392

MAVec It's not a list ;)

[Meinersbur]

In D13676#265724, @grosser wrote:

the patch looks generally fine. I am only slightly concerned your removal of the instruction to multiple read/write accesses. As it seems to not be strictly necessary, I wonder if we should rather leave the multi read/write accesses in?

This was one of the things I was most happy to simplify. No more memory management of lists in lists, or the difficulty to understand when a MemoryAccess is connected to an instruction.

include/polly/ScopInfo.h

811

D13616 also assumes there is exactly one explicit access per instruction (lookupExplicitAccessFor).

Function calls cannot be modeled with any fixed number of MemoryAccesses.

Atomic exchange is more interesting. Not sure how to model this, it could also be a single MemoryAccess of a special type. If not, it would still be at most one read and one write per instructions, for which we do not need the overhead of a list. (e.g. two maps InstructionToReadAccess+InstructionToWriteAccess; or a single map to a pair<MemoryAccess*,MemoryAccess*>)

814

I don't know what DependentScalars are meant to be, but those reads are not 'dependent' nor necessarily scalars (but also PHIs).

'writes' are also not escaping. Escaping also already has a meaning of values that are used after the scop.

For me, a name describing the content is sufficient. There can be multiple reasons why something is in there, which can be described in a comment.

lib/Analysis/ScopInfo.cpp

1483–1485

Shouldn't that be a separate patch?

3967

No, Acc is added to different lists each time.

The alternative would be to have some detection logic in addMemoryAccess to which list the access it to add, but more error prone than simple NULL checks.

[llvm-commits]

Meinersbur added a comment.

In http://reviews.llvm.org/D13676#265724, @grosser wrote:

the patch looks generally fine. I am only slightly concerned your removal of the instruction to multiple read/write accesses. As it seems to not be strictly necessary, I wonder if we should rather leave the multi read/write accesses in?

This was one of the things I was most happy to simplify. No more memory management of lists in lists, or the difficulty to understand when a MemoryAccess is connected to an instruction.

With this patch but multiple accesses per instruction we would still
simplify both. All MemoryAccesses connected to an instruction would be
real (explicit) memory accesses (maybe) caused by that instruction.

Comment at: include/polly/ScopInfo.h:746
@@ +745,3 @@
+ /// @brief Mapping from instructions to explicit memory accesses.
+ DenseMap<const Instruction *, MemoryAccess *> InstructionToAccess;

+

grosser wrote:

I understand that with the currently supported features we now only have a single read/write access per statement, but I do not think this will/should hold in general. If we e.g. model function calls or intrinsics like _atomic_exchange_n this won't hold any more. Hence, I personally would prefer to not specialize too much here.

D13616 also assumes there is exactly one explicit access per instruction (lookupExplicitAccessFor).

Because at the moment there is. But that is different from cutting
support for something else. I only used the fact that there can be at
most one explicit access at the moment to simplify the algorithm.

Function calls cannot be modeled with any fixed number of MemoryAccesses.

I am not sure how this generalization is helping the discussion or what
it even means. In any way, that sentence above doesn't suffice to
ignore the function call modeling problem.

Atomic exchange is more interesting. Not sure how to model this, it could also be a single MemoryAccess of a special type. If not, it would still be at most one read and one write per instructions, for which we do not need the overhead of a list. (e.g. two maps InstructionToReadAccess+InstructionToWriteAccess; or a single map to a pair<MemoryAccess*,MemoryAccess*>)

Comment at: include/polly/ScopInfo.h:749
@@ +748,3 @@
+ /// @brief Implicit loads at the beginning of a statement.
+ MemoryAccessVec LeadingReads;

+

jdoerfert wrote:

Now that I think about it, maybe leading and trailing is not the best wording here. While it is literally true, it doesn't help to understand why they are leading/trailing. Maybe if we combine leading with the DependentScalars from D13611 and and rename trailing writes in escaping writes the purpose/need becomes clear.

I don't know what DependentScalars are meant to be, but those reads are not 'dependent' nor necessarily scalars (but also PHIs).

1. DependentScalars are scalars that need to be recomputed in order to generate code for that statement (it says something like this in the comment). Leading loads are scalars that need to be reloaded in order to .. (copy text from above). Already the definition is so similar that we should merge those two.
2. Generally PHIs and PHI operands are considered scalars too.

'writes' are also not escaping. Escaping also already has a meaning of values that are used after the scop.

Escaping the block/statement or escaping the SCoP, whatever. In the end
it is almost the same and it is not important. Important is that they
need to be communicated from the defining statement (where they escape)
to somewhere else and we do that via memory. That they are tailing the
statement is a mere side effect and isn't even like that at the moment.

For me, a name describing the content is sufficient. There can be multiple reasons why something is in there, which can be described in a comment.

I don't understand this part. Are you saying leading/trailing are
descriptive enough to understand what is going on and why?

Comment at: lib/Analysis/ScopInfo.cpp:1375
@@ -1360,7 +1374,3 @@

• // Remove all memory accesses in @p InvMAs from this statement together
• // with all scalar accesses that were caused by them. The tricky iteration
• // order uses is needed because the MemAccs is a vector and the order in
• // which the accesses of each memory access list (MAL) are stored in this
• // vector is reversed.

+ // Remove the MemoryAccess from all lists.

for (MemoryAccess *MA : InvMAs) {

---

jdoerfert wrote:

You mentioned at some point we should extract the "removeMemoryAccesses" from this function and I now see the need. In D13611 this happened we could use some fancy lambda magic like this to get rid of the weird traversal order if we can still get the same "runtime".

Shouldn't that be a separate patch?

Yes, and if it would happen prior to any of those we would have
smaller diffs, thus my comment.

Comment at: lib/Analysis/ScopInfo.cpp:3488
@@ -3458,1 +3487,3 @@
+ return;
+ Acc->getStatement()->addLeadingLoad(Acc);

}

grosser wrote:

This pattern seems rather repetitive. It happens five times at least. Does it make sense to add the "if (!Acc) ..." part directly to addMemoryAccess?

No, Acc is added to different lists each time.

The alternative would be to have some detection logic in addMemoryAccess to which list the access it to add, but more error prone than simple NULL checks.

We could simply hand the list to the method instead of guessing?

In any case:
{

...
if (!A)
  return
B;

}

>

{

...
if (A)
  B;

}

http://reviews.llvm.org/D13676

• signature.asc219 BDownload
• msg-20112-44.txt162 BDownload

[Meinersbur]

As both of you voted for keeping the InstructionToAccess as a map-of-lists, I will undo that part in an update.

[Meinersbur]

Make InstructionToAccess a map-of-lists again, consistently use LeadingLoads/TrailingStores in BlockGenerator. addressing smaller comments

[Meinersbur]

In D13676#265946, @llvm-commits wrote:

Comment at: include/polly/ScopInfo.h:746
@@ +745,3 @@
+ /// @brief Mapping from instructions to explicit memory accesses.
+ DenseMap<const Instruction *, MemoryAccess *> InstructionToAccess;

+

grosser wrote:

I understand that with the currently supported features we now only have a single read/write access per statement, but I do not think this will/should hold in general. If we e.g. model function calls or intrinsics like _atomic_exchange_n this won't hold any more. Hence, I personally would prefer to not specialize too much here.

D13616 also assumes there is exactly one explicit access per instruction (lookupExplicitAccessFor).

Because at the moment there is. But that is different from cutting
support for something else. I only used the fact that there can be at
most one explicit access at the moment to simplify the algorithm.

Function calls cannot be modeled with any fixed number of MemoryAccesses.

I am not sure how this generalization is helping the discussion or what
it even means. In any way, that sentence above doesn't suffice to
ignore the function call modeling problem.

How do you model a function calls that accesses data like this:

for (int i = 0; i < n; i+=1)
   A[i] = xyz;

The number of accesses is only known at runtime, hence one cannot add a MemoryAccess for each write.

'writes' are also not escaping. Escaping also already has a meaning of values that are used after the scop.

Escaping the block/statement or escaping the SCoP, whatever. In the end
it is almost the same and it is not important. Important is that they
need to be communicated from the defining statement (where they escape)
to somewhere else and we do that via memory. That they are tailing the
statement is a mere side effect and isn't even like that at the moment.

This patch depends on D13487. Sorry, seems I didn't mark it as such.

For me, a name describing the content is sufficient. There can be multiple reasons why something is in there, which can be described in a comment.

I don't understand this part. Are you saying leading/trailing are
descriptive enough to understand what is going on and why?

It is enough to know what the vectors contains, which is all that matters for their names. How elements are put in there and what they are used for is better explained in a comment.

Comment at: lib/Analysis/ScopInfo.cpp:1375
@@ -1360,7 +1374,3 @@

• // Remove all memory accesses in @p InvMAs from this statement together
• // with all scalar accesses that were caused by them. The tricky iteration
• // order uses is needed because the MemAccs is a vector and the order in
• // which the accesses of each memory access list (MAL) are stored in this
• // vector is reversed.

+ // Remove the MemoryAccess from all lists.

for (MemoryAccess *MA : InvMAs) {

---

jdoerfert wrote:

You mentioned at some point we should extract the "removeMemoryAccesses" from this function and I now see the need. In D13611 this happened we could use some fancy lambda magic like this to get rid of the weird traversal order if we can still get the same "runtime".

Shouldn't that be a separate patch?

Yes, and if it would happen prior to any of those we would have
smaller diffs, thus my comment.

I cannot work on hypothetical patches. When I asked that editing ScopStmt could be refactored out, you said when necessary. It hasn't become more necessary with this patch. However, I'd welcome if you commit such refactoring either prior of after this patch.

Could you answer withing the web interface? Phabricator screws up formatting from emails and has "llvm-commits" as author.

[Meinersbur]

rebase to r250627

[Meinersbur]

Rebase to 252942, fix for Isl/Ast/runtime_context_with_error_blocks.ll

[Meinersbur]

Rebase to r254150

[Meinersbur]

Rebase to r254343

[grosser]

Hi Michael,

from my perspective the patch looks good to me, except the name concerns Johannes raised. Having looked into some of the other patches, I see this small (but apparently recurring) issue again. I started a mailing list discussion to hopefully resolve this once and for all.

Best,
Tobias

include/polly/ScopInfo.h

685

This change is unrelated. Please commit it separately.

[Meinersbur]

Rebase to r255107; remove not required changes mostly in comments.

[Meinersbur]

Rebase to r255474; use new naming scheme for access kinds.

[Meinersbur]

Remove explicit LeadingReads and TrailingWrites vectors; they are implicit by iterating over all MemoryAccesses with a filter

[grosser]

Thank you Michael for this rebase. This new change is now clearly minimal such that we can now focus on the semantic change.

There are good points for this patch:

We currently do not use the InstructionToArray mapping for scalars, it was originally not introduced with scalars in mind and - in fact - us adding scalars to this mapping introduced bugs at various places (which I just fixed).

As your patch also allows us to avoid the construction of redundant scalar memory accesses in a ScopStmt, I am clearly in favor of adding it.

I understand that in certain situations we might want to know if an instruction caused scalar memory accesses, but I think such information should probably be maintained separately. Adding functionality seems to be rather simple (and orthogonal). Hence, we can do it when the need arises.

From my point this patch is ready to commit, but let's see if people at the phone call tonight have any further thoughts.

[grosser]

Accepted if my minor comments have been addressed.

[Meinersbur]

Rebase to r256124

[Meinersbur]

In D13676#313647, @grosser wrote:

Accepted if my minor comments have been addressed.

What comments are you referring to?

[grosser]

No comments. I thought I had some, but I did not.
It's fine to commit as it is.

Tobias

include/polly/ScopInfo.h

public:
 
   /// @brief Whether this is an access of an explicit load or store in the IR.
   bool isExplicit() const { return Origin == EXPLICIT; }
 
   /// @brief Whether this access represents a register access or models PHI
   /// nodes.
   bool isImplicit() const { return !isExplicit(); }
 
+  /// @brief is this MemoryAccess representing a use or def of an llvm::Value?
+  bool isScalar() const { return Origin == SCALAR; }
+
   /// @brief Is this MemoryAccess modeling special PHI node accesses?
   bool isPHI() const { return Origin == PHI; }
 
   /// @brief Is this MemoryAccess modeling the accesses of a PHI node in the
   /// SCoP's exit block?
   bool isExitPHI() const { return Origin == EXIT_PHI; }
 
   /// @brief Get the statement that contains this memory access.
private:
   isl_set *Domain;
 
   /// The memory accesses of this statement.
   ///
   /// The only side effects of a statement are its memory accesses.
   typedef SmallVector<MemoryAccess *, 8> MemoryAccessVec;
   MemoryAccessVec MemAccs;
 
-  /// @brief Mapping from instructions to (scalar) memory accesses.
+  /// @brief Mapping from instructions to explicit memory accesses.
   DenseMap<const Instruction *, MemoryAccessList *> InstructionToAccess;
 
+  /// @brief Implicit loads at the beginning of a statement.
+  MemoryAccessVec LeadingReads;
+
+  /// @bried Implicit stores at the end of a statement.
+  MemoryAccessVec TrailingWrites;
+
   //@}
 
   /// @brief 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.
   ///
   ///{
public:
   Region *getRegion() const { return R; }
 
   /// @brief Return true if this statement represents a whole region.
   bool isRegionStmt() const { return R != nullptr; }
 
   /// @brief Return true if this statement does not contain any accesses.
   bool isEmpty() const { return MemAccs.empty(); }
 
-  /// @brief Return the (scalar) memory accesses for @p Inst.
+  /// @brief Return the explicit memory accesses for @p Inst.
   const MemoryAccessList &getAccessesFor(const Instruction *Inst) const {
     MemoryAccessList *MAL = lookupAccessesFor(Inst);
     assert(MAL && "Cannot get memory accesses because they do not exist!");
     return *MAL;
   }
 
-  /// @brief Return the (scalar) memory accesses for @p Inst if any.
+  /// @brief Return the explicit memory accesses for @p Inst if any.
   MemoryAccessList *lookupAccessesFor(const Instruction *Inst) const {
     auto It = InstructionToAccess.find(Inst);
     if (It == InstructionToAccess.end())
       return nullptr;
     return It->getSecond()->empty() ? nullptr : It->getSecond();
   }
 
-  /// @brief Return the __first__ (scalar) memory access for @p Inst.
+  /// @brief Return the explicit memory access for @p Inst.
   const MemoryAccess &getAccessFor(const Instruction *Inst) const {
     MemoryAccess *MA = lookupAccessFor(Inst);
     assert(MA && "Cannot get memory access because it does not exist!");
     return *MA;
   }
 
-  /// @brief Return the __first__ (scalar) memory access for @p Inst if any.
+  /// @brief Return the explicit memory access for @p Inst if any.
   MemoryAccess *lookupAccessFor(const Instruction *Inst) const {
     auto It = InstructionToAccess.find(Inst);
     if (It == InstructionToAccess.end())
       return nullptr;
     return It->getSecond()->empty() ? nullptr : It->getSecond()->front();
   }
 
+  /// @brief Return the vector of leading implicit loads.
+  const MemoryAccessVec &getLeadingReads() const { return LeadingReads; }
+
+  /// @brief Return the vector of trailing implicit stores.
+  const MemoryAccessVec &getTrailingWrites() const { return TrailingWrites; }
+
   void setBasicBlock(BasicBlock *Block) {
     // TODO: Handle the case where the statement is a region statement, thus
     //       the entry block was split and needs to be changed in the region R.
     assert(BB && "Cannot set a block for a region statement");
     BB = Block;
   }
 
   /// @brief Add @p Access to this statement's list of accesses.
-  void addAccess(MemoryAccess *Access);
+  void addExplicitAccess(MemoryAccess *Access);
+
+  /// @brief Add @p Access to this statement's list of implicit loads.
+  void addLeadingLoad(MemoryAccess *Access);
+
+  /// @brief Add @p Access to this statement's list of implicit stores.
+  void addTrailingWrite(MemoryAccess *Access);
 
   /// @brief Remove the memory access in @p InvMAs.
   ///
   /// Note that scalar accesses that are caused by any access in @p InvMAs will
   /// be eliminated too.
   void removeMemoryAccesses(MemoryAccessList &InvMAs);
 
   typedef MemoryAccessVec::iterator iterator;
class ScopInfo : public RegionPass {
   /// @param Type        The kind of access.
   /// @param BaseAddress The accessed array's base address.
   /// @param ElemBytes   Size of accessed array element.
   /// @param Affine      Whether all subscripts are affine expressions.
   /// @param AccessValue Value read or written.
   /// @param Subscripts  Access subscripts per dimension.
   /// @param Sizes       The array diminsion's sizes.
   /// @param Origin      Purpose of this access.
-  void addMemoryAccess(BasicBlock *BB, Instruction *Inst,
-                       MemoryAccess::AccessType Type, Value *BaseAddress,
-                       unsigned ElemBytes, bool Affine, Value *AccessValue,
+  ///
+  /// @return The newly created MemoryAccess instance or NULL if the access
+  ///         would have no effect.
+  MemoryAccess *addMemoryAccess(BasicBlock *BB, Instruction *Inst,
+                                MemoryAccess::AccessType Type,
+                                Value *BaseAddress, unsigned ElemBytes,
+                                bool Affine, Value *AccessValue,
                                 ArrayRef<const SCEV *> Subscripts,
                                 ArrayRef<const SCEV *> Sizes,
                                 MemoryAccess::AccessOrigin Origin);
 
   /// @brief Create a MemoryAccess that represents either a LoadInst or
   /// StoreInst.
   ///
   /// @param MemAccInst  The LoadInst or StoreInst.
   /// @param Type        The kind of access.
   /// @param BaseAddress The accessed array's base address.
   /// @param ElemBytes   Size of accessed array element.

lib/Analysis/ScopInfo.cpp

for (MemoryAccess *Access : MemAccs) {
 
     const ScopArrayInfo *SAI = getParent()->getOrCreateScopArrayInfo(
         Access->getBaseAddr(), ElementType, Access->Sizes, Ty);
 
     Access->buildAccessRelation(SAI);
   }
 }
 
-void ScopStmt::addAccess(MemoryAccess *Access) {
+void ScopStmt::addExplicitAccess(MemoryAccess *Access) {
+  assert(Access->isExplicit());
   Instruction *AccessInst = Access->getAccessInstruction();
 
   MemoryAccessList *&MAL = InstructionToAccess[AccessInst];
   if (!MAL)
     MAL = new MemoryAccessList();
   MAL->emplace_front(Access);
   MemAccs.push_back(MAL->front());
 }
 
+void ScopStmt::addLeadingLoad(MemoryAccess *Access) {
+  assert(Access->isImplicit());
+  assert(Access->isRead());
+
+  LeadingReads.push_back(Access);
+  MemAccs.push_back(Access);
+}
+
+void ScopStmt::addTrailingWrite(MemoryAccess *Access) {
+  assert(Access->isImplicit());
+  assert(Access->isWrite());
+
+  TrailingWrites.push_back(Access);
+  MemAccs.push_back(Access);
+}
+
 void ScopStmt::realignParams() {
   for (MemoryAccess *MA : *this)
     MA->realignParams();
 
   Domain = isl_set_align_params(Domain, Parent.getParamSpace());
 }
 
 /// @brief Add @p BSet to the set @p User if @p BSet is bounded.
if (Domain) {
     OS.indent(16) << "n/a\n";
 
   for (MemoryAccess *Access : MemAccs)
     Access->print(OS);
 }
 
 void ScopStmt::dump() const { print(dbgs()); }
 
 void ScopStmt::removeMemoryAccesses(MemoryAccessList &InvMAs) {
   // Remove all memory accesses in @p InvMAs from this statement
   // together with all scalar accesses that were caused by them.
   for (MemoryAccess *MA : InvMAs) {
     auto Predicate = [&](MemoryAccess *Acc) {
       return Acc->getAccessInstruction() == MA->getAccessInstruction();
     };
+    LeadingReads.erase(
+        std::remove_if(LeadingReads.begin(), LeadingReads.end(), Predicate),
+        LeadingReads.end());
     MemAccs.erase(std::remove_if(MemAccs.begin(), MemAccs.end(), Predicate),
                   MemAccs.end());
+    TrailingWrites.erase(
+        std::remove_if(TrailingWrites.begin(), TrailingWrites.end(), Predicate),
+        TrailingWrites.end());
     InstructionToAccess.erase(MA->getAccessInstruction());
     delete lookupAccessesFor(MA->getAccessInstruction());
   }
 }
 
 //===----------------------------------------------------------------------===//
 /// Scop class implement
 
for (BasicBlock::iterator I = BB.begin(), E = --BB.end(); I != E; ++I) {
 
     if (buildScalarDependences(Inst, &R, NonAffineSubRegion)) {
       if (!isa<StoreInst>(Inst))
         addScalarWriteAccess(Inst);
     }
   }
 }
 
-void ScopInfo::addMemoryAccess(BasicBlock *BB, Instruction *Inst,
+MemoryAccess *ScopInfo::addMemoryAccess(BasicBlock *BB, Instruction *Inst,
                                         MemoryAccess::AccessType Type,
                                         Value *BaseAddress, unsigned ElemBytes,
                                         bool Affine, Value *AccessValue,
                                         ArrayRef<const SCEV *> Subscripts,
                                         ArrayRef<const SCEV *> Sizes,
                                         MemoryAccess::AccessOrigin Origin) {
   ScopStmt *Stmt = scop->getStmtForBasicBlock(BB);
 
   // Do not create a memory access for anything not in the SCoP. It would be
   // ignored anyway.
   if (!Stmt)
-    return;
+    return nullptr;
 
   AccFuncSetType &AccList = AccFuncMap[BB];
   Value *BaseAddr = BaseAddress;
   std::string BaseName = getIslCompatibleName("MemRef_", BaseAddr, "");
 
   bool isApproximated =
       Stmt->isRegionStmt() && (Stmt->getRegion()->getEntry() != BB);
   if (isApproximated && Type == MemoryAccess::MUST_WRITE)
     Type = MemoryAccess::MAY_WRITE;
 
   AccList.emplace_back(Stmt, Inst, Type, BaseAddress, ElemBytes, Affine,
                        Subscripts, Sizes, AccessValue, Origin, BaseName);
-  Stmt->addAccess(&AccList.back());
+  return &AccList.back();
 }
 
 void ScopInfo::addExplicitAccess(
     Instruction *MemAccInst, MemoryAccess::AccessType Type, Value *BaseAddress,
     unsigned ElemBytes, bool IsAffine, ArrayRef<const SCEV *> Subscripts,
     ArrayRef<const SCEV *> Sizes, Value *AccessValue) {
   assert(isa<LoadInst>(MemAccInst) || isa<StoreInst>(MemAccInst));
   assert(isa<LoadInst>(MemAccInst) == (Type == MemoryAccess::READ));
-  addMemoryAccess(MemAccInst->getParent(), MemAccInst, Type, BaseAddress,
-                  ElemBytes, IsAffine, AccessValue, Subscripts, Sizes,
-                  MemoryAccess::EXPLICIT);
+  MemoryAccess *Acc = addMemoryAccess(
+      MemAccInst->getParent(), MemAccInst, Type, BaseAddress, ElemBytes,
+      IsAffine, AccessValue, Subscripts, Sizes, MemoryAccess::EXPLICIT);
+  if (Acc)
+    Acc->getStatement()->addExplicitAccess(Acc);
 }
 void ScopInfo::addScalarWriteAccess(Instruction *Value) {
-  addMemoryAccess(Value->getParent(), Value, MemoryAccess::MUST_WRITE, Value, 1,
-                  true, Value, ArrayRef<const SCEV *>(),
+  MemoryAccess *Acc =
+      addMemoryAccess(Value->getParent(), Value, MemoryAccess::MUST_WRITE,
+                      Value, 1, true, Value, ArrayRef<const SCEV *>(),
                       ArrayRef<const SCEV *>(), MemoryAccess::SCALAR);
+  if (Acc)
+    Acc->getStatement()->addTrailingWrite(Acc);
 }
 void ScopInfo::addScalarReadAccess(Value *Value, Instruction *User) {
   assert(!isa<PHINode>(User));
-  addMemoryAccess(User->getParent(), User, MemoryAccess::READ, Value, 1, true,
-                  Value, ArrayRef<const SCEV *>(), ArrayRef<const SCEV *>(),
-                  MemoryAccess::SCALAR);
+  MemoryAccess *Acc = addMemoryAccess(
+      User->getParent(), User, MemoryAccess::READ, Value, 1, true, Value,
+      ArrayRef<const SCEV *>(), ArrayRef<const SCEV *>(), MemoryAccess::SCALAR);
+  if (Acc)
+    Acc->getStatement()->addLeadingLoad(Acc);
 }
 void ScopInfo::addScalarReadAccess(Value *Value, PHINode *User,
                                    BasicBlock *UserBB) {
-  addMemoryAccess(UserBB, User, MemoryAccess::READ, Value, 1, true, Value,
-                  ArrayRef<const SCEV *>(), ArrayRef<const SCEV *>(),
-                  MemoryAccess::SCALAR);
+  MemoryAccess *Acc = addMemoryAccess(
+      UserBB, User, MemoryAccess::READ, Value, 1, true, Value,
+      ArrayRef<const SCEV *>(), ArrayRef<const SCEV *>(), MemoryAccess::SCALAR);
+  if (Acc)
+    Acc->getStatement()->addLeadingLoad(Acc);
 }
 void ScopInfo::addPHIWriteAccess(PHINode *PHI, BasicBlock *IncomingBlock,
                                  Value *IncomingValue, bool IsExitBlock) {
+  MemoryAccess *Acc =
       addMemoryAccess(IncomingBlock, IncomingBlock->getTerminator(),
                       MemoryAccess::MUST_WRITE, PHI, 1, true, IncomingValue,
                       ArrayRef<const SCEV *>(), ArrayRef<const SCEV *>(),
                       IsExitBlock ? MemoryAccess::EXIT_PHI : MemoryAccess::PHI);
+  if (Acc)
+    Acc->getStatement()->addTrailingWrite(Acc);
 }
 void ScopInfo::addPHIReadAccess(PHINode *PHI) {
-  addMemoryAccess(PHI->getParent(), PHI, MemoryAccess::READ, PHI, 1, true, PHI,
-                  ArrayRef<const SCEV *>(), ArrayRef<const SCEV *>(),
-                  MemoryAccess::PHI);
+  MemoryAccess *Acc = addMemoryAccess(
+      PHI->getParent(), PHI, MemoryAccess::READ, PHI, 1, true, PHI,
+      ArrayRef<const SCEV *>(), ArrayRef<const SCEV *>(), MemoryAccess::PHI);
+  if (Acc)
+    Acc->getStatement()->addLeadingLoad(Acc);
 }
 
 void ScopInfo::buildScop(Region &R, DominatorTree &DT, AssumptionCache &AC) {
   unsigned MaxLoopDepth = getMaxLoopDepthInRegion(R, *LI, *SD);
   scop = new Scop(R, AccFuncMap, *SD, *SE, DT, *LI, ctx, MaxLoopDepth);
 
   buildStmts(R);
   buildAccessFunctions(R, R);
 

lib/CodeGen/BlockGenerators.cpp

void BlockGenerator::handleOutsideUsers(const Region &R, Instruction *Inst,
   // Get or create an escape alloca for this instruction.
   auto *ScalarAddr = Address ? Address : getOrCreateScalarAlloca(Inst);
 
   // Remember that this instruction has escape uses and the escape alloca.
   EscapeMap[Inst] = std::make_pair(ScalarAddr, std::move(EscapeUsers));
 }
 
 void BlockGenerator::generateScalarLoads(ScopStmt &Stmt, ValueMapT &BBMap) {
-  for (MemoryAccess *MA : Stmt) {
-    if (MA->isExplicit() || MA->isWrite())
-      continue;
+  for (MemoryAccess *MA : Stmt.getLeadingReads()) {
+    assert(MA->isImplicit());
+    assert(MA->isRead());
 
     auto *Address = getOrCreateAlloca(*MA);
     BBMap[MA->getBaseAddr()] =
         Builder.CreateLoad(Address, Address->getName() + ".reload");
   }
 }
 
 Value *BlockGenerator::getNewScalarValue(Value *ScalarValue, const Region &R,

 void BlockGenerator::generateScalarStores(ScopStmt &Stmt, LoopToScevMapT &LTS,
                                           ValueMapT &BBMap) {
   const Region &R = Stmt.getParent()->getRegion();
 
   assert(Stmt.isBlockStmt() && "Region statements need to use the "
                                "generateScalarStores() function in the "
                                "RegionGenerator");
 
-  for (MemoryAccess *MA : Stmt) {
-    if (MA->isExplicit() || MA->isRead())
-      continue;
+  for (MemoryAccess *MA : Stmt.getTrailingWrites()) {
+    assert(MA->isImplicit());
+    assert(MA->isWrite());
 
     Value *Val = MA->getAccessValue();
     auto *Address = getOrCreateAlloca(*MA);
 
     Val = getNewScalarValue(Val, R, Stmt, LTS, BBMap);
     Builder.CreateStore(Val, Address);
   }
 }