[Polly] Ensure unique implicit reads/writes at beginning/end of ScopStmts

[Meinersbur]

Summary

Previously, there could be a read scalar access for every use of a cross-stmt value and potentially multiple stores for a value definition. Check that such MemoryAccesses do not already exist before adding new ones. This will be used for De-LICM such that if removing a redundant read or write, there is no second variant left.

Instead of checking for each instruction individually whether it needs to be written, we can now "pull-in" a reload when required including the creation of a store of the definition which simplifies the creation of implicit MemoryAccesses a bit.

We also unify the PHI writes in non-affine subregions. Instead of writing them in the exiting block, we write them only in the subregion's exit. The former violates the requirement that implicits are not written until leaving the scop statement if the exiting block has also edges back into the subregion. In addition, generateScalarLoads and generateScalarStore do not have special versions for non-affine subregions anymore.

[Meinersbur]

Rebase to r250809; smaller changes to make the DeLICM patch smaller

[Meinersbur]

Rebase to r251341

Disappearing PHIs in exit nodes requires to remember incoming nodes explicitely. Might be a separate patches:

• Introduction of explicit EXIT_PHI origin to avoid quering whether the access instruction is a terminator
• Storing of incoming values/block for PHI accesses
• Unification of PHIs in sub-region exit BBs.

Alternatively, we might revive the part that ensures the existence and position of PHI nodes from D11870.

[Meinersbur]

Rebase to r254150

[Meinersbur]

Undo unnecessary changes in test cases

[Meinersbur]

test/Isl/CodeGen/uninitialized_scalar_memory.ll

8

Reminder to myself: Have to check why this is gone

test/ScopInfo/read-only-scalar-used-in-phi.ll

22

This is a EXIT_PHI access

test/ScopInfo/same-base-address-scalar-and-array.ll

7

The base address "out" is synthesizable (from a scop parameter) and therefore does not cause accesses. In current trunk there is still an access generated if ModelReadOnlyScalars==true and it is used by a PHI node. I am assuming this is not intentional.

There are multiple instances of this phenomenon in the tests.

[Meinersbur]

Rebase to r254343

[grosser]

Hi Michael,

thank you for submitting this patch. I just went though it a first time and the overall direction seems good. Uniqueing implicit read/write accesses is likely to make sense by itself and as it as it is useful for DeLICM (either pre-or-post polyhedrization), this change seems well motivated.

I did not yet manage to do a full review, but already posted a couple of comments. My first impression is that the patch is mostly non-controversial, but rather large (600 LoC). To make the individual changes easier to understand (and easier to bisect in case of bugs), it seems worth to split out the independent parts and commit them one-by-one (some of them are trivial). I still need to have a more in-depth look at the actual unification, which seems mostly straightforward but includes some moved code which - in this larger patch - is not easy
to compare. Also, It seems we now keep track of the same MemoryAccess in multiple lists. I still need to understand this better as well.

include/polly/CodeGen/BlockGenerators.h

798

Is this change unrelated? Assuming it is, you can probably commit this as obvious.

include/polly/ScopInfo.h

326

This is because a scalar may be used by multiple instructions in a ScopStmt and we only want to store one memory access for all of them. This makes sense (but could probably be mentioned in this comment).

361

OK, I see that you move from multiple to just a single PHI write access for non-affine regions. I wonder if this could be a separate patch?

836

elsewhere

841

elsewhere

848

Refold lines?

1046

This is independent, no? It it is, please commit it ahead of time.

1483

This seems to be unused after the patch.

lib/Analysis/ScopInfo.cpp

753

I can remove this change without test case failure. It seems unrelated. Can you drop this one (or commit it independently if you need this for debugging).

891

This seems good, but unrelated. Can you commit this ahead of time.

2010

This function is unused. Please remove from patch.

3395

This looks good, but it seems independently useful? Could you commit this by itself?

3589

This sentence is incomplete.

3618

did not "ensure"

3628

This seems unaddressed.

3851

guaranteed

3855

Earlier we skipped the last iteration, now we do not do this any more. Why is this safe?

Also, I wonder if some of this move to the range iterator could be committed ahead of time?

3859

This change seems independent. Can this be separated out?

[Meinersbur]

I think I already mentioned in a conversation that I could make two (larger) commits from this, depending on whether it makes sense:

• Introduction of the scalar access maps ScalarLoads/ScalarWrites and uniqueing the loads per stmt.
• Uniqueing of PHI writes for non-affine subregion statements

A drawback of this patch is that the getAccessInstructin() might be nullptr (because an access can be causes by multiple instructions) in some cases. I started the thread "Accessing the same element multiple times within one ScopStmt" on the polly-dev mailing list to discuss this.

Required for DeLICM was the collapse of PHI writes in non-affine regions because such write may only occur after exiting a stmt, but an exiting basic block can have an edge back into the non-affine region. Another way to implement this to split edges from the exiting block to the exit block (ie. insert a basic block) and create the PHI WRITE accesses there.

DeLICM naturally uniques writes because it determines for each (BB,mappable array element) what the content of the array element at the end of the BB should be.

include/polly/CodeGen/BlockGenerators.h

798

In some intermediate state, I made it return a PHINode instead of just an llvm::Value. I may have noticed that it never returns nullptr, but forgot to change the comment back.

I'll commit this separately include the type change, which IMHO makes sense.

include/polly/ScopInfo.h

1046

This was added with D13676. The explicit was added to contrast the usage of the functions introduced below

1483

This is a general accessor. Removing means that AccFuncMap is not accessible anymore from other code.

lib/Analysis/ScopInfo.cpp

753

I'll commit separately

891

is Scalar is introduced in D13676. It maybe should belong to that patch.

3395

getStmtForRegionNode was introduced in this patch

3855

It has become necessary with this patch. The terminator can be a legitimate user of a value, such as the condition. Omitting the terminator before was fine before because the terminator does not define a value itself.

3859

OK

[grosser]

Hi Michael,

two brief comments:

lib/Analysis/ScopInfo.cpp

891

As the two changes belong together, but are independent of anything else, I think you can just commit them directly (as obvious).

3395

As getStmtForRegionNode does not pull in other dependences, you can just commit the changes above and getStmtForRegionNode ahead of time.

[Meinersbur]

Split into D15693, D15681, D15510, D15483, D15706 and D15687.

include/polly/CodeGen/BlockGenerators.h

private:
   /// with references to new values, as defined by GlobalMap and BBMap.
   ///
   /// @param Stmt      The statement to code generate.
   /// @param PHI       The PHI instruction to copy.
   /// @param BBMap     A mapping from old values to their new values
   ///                  (for values recalculated within this basic block).
   /// @param LTS       A map from old loops to new induction variables as SCEVs.
   ///
-  /// @returns The copied instruction or nullptr if no copy was made.
+  /// @returns The copied PHI.
   virtual Value *copyPHIInstruction(ScopStmt &Stmt, PHINode *Inst,
                                     ValueMapT &BBMap,
                                     LoopToScevMapT &LTS) override;
 };
 }
 #endif

include/polly/ScopInfo.h

public:
   ///                    -----------------------------------
   ///                           |                   |
   /// ____________________________________  ____________________________________
   /// |UseBB1:                           |  |UseBB2:                           |
   /// |  %V.reload1 = load float* %V.s2a |  |  %V.reload2 = load float* %V.s2a |
   /// |  use float %V.reload1            |  |  use float %V.reload2            |
   /// ------------------------------------  ------------------------------------
   ///
-  /// #AccessInst is either the llvm::Value for WRITEs or the value's user for
-  /// READS. The #BaseAddr is represented by the value's definition (i.e. the
+  /// #AccessInst is either the llvm::Value for WRITEs or nullptr for reads.
+  /// The #BaseAddr is represented by the value's definition (i.e. the
   /// llvm::Value itself) as no such alloca yet exists before CodeGeneration.
   /// #AccessValue is also the llvm::Value itself.
   ///
   ///
   /// * Accesses to emulate PHI nodes within the SCoP
   ///
   /// PHIInst instructions such as
   ///
public:
   ///                             \            /
   ///                              \          /
   ///               _________________________________________
   ///               |JoinBlock:                             |
   ///               |  %PHI = load float, float* PHI.phiops |
   ///               -----------------------------------------
   ///
   /// Since the stores and loads do not exist in the analyzed code, the
-  /// #AccessInst of a load is the PHIInst and a incoming block's terminator for
-  /// stores. The #BaseAddr is represented through the PHINode because there
+  /// #AccessInst of a load is the PHIInst and a nullptr for stores (it can
+  /// represent multiple values that are leaving a non-affine region with
+  /// multiple exiting edges). The #BaseAddr is represented through the PHINode
+  /// because there
   /// also such alloca in the analyzed code. The #AccessValue is represented by
   /// the PHIInst itself.
   ///
   /// Note that there can also be a scalar write access for %PHI if used in a
   /// different BasicBlock, i.e. there can be a %PHI.phiops as well as a
   /// %PHI.s2a.
   ///
   ///
private:
   // @}
 
   // Properties describing the accessed element.
   // @{
 
   /// @brief The access instruction of this memory access.
   Instruction *AccessInstruction;
 
+  /// @brief Incoming block and value of a PHINode.
+  SmallVector<std::pair<BasicBlock *, Value *>, 4> Incoming;
+
   /// @brief The value associated with this memory access.
   ///
   ///  - For real memory accesses it is the loaded result or the stored value.
   ///  - For straight line scalar accesses it is the access instruction itself.
   ///  - For PHI operand accesses it is the operand value.
   ///
   AssertingVH<Value> AccessValue;
 
public:
   /// @param Sizes      Dimension lengths of the accessed array.
   /// @param BaseName   Name of the acessed array.
   MemoryAccess(ScopStmt *Stmt, Instruction *AccessInst, AccessType Type,
                Value *BaseAddress, unsigned ElemBytes, bool Affine,
                ArrayRef<const SCEV *> Subscripts, ArrayRef<const SCEV *> Sizes,
                Value *AccessValue, AccessOrigin Origin, StringRef BaseName);
   ~MemoryAccess();
 
+  void addIncoming(BasicBlock *IncomingBlock, Value *IncomingValue) {
+    assert(isAnyPHI());
+    Incoming.emplace_back(std::make_pair(IncomingBlock, IncomingValue));
+  }
+
+  ArrayRef<std::pair<BasicBlock *, Value *>> getIncoming() const {
+    assert(isAnyPHI());
+    return Incoming;
+  }
+
   /// @brief Get the type of a memory access.
   enum AccessType getType() { return AccType; }
 
   /// @brief Is this a reduction like access?
   bool isReductionLike() const { return RedType != RT_NONE; }
 
   /// @brief Is this a read memory access?
   bool isRead() const { return AccType == MemoryAccess::READ; }
public:
 
   /// @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 Doeas this access orginate from one of the two PHI types?
+  bool isAnyPHI() const { return isPHI() || isExitPHI(); }
+
   /// @brief Get the statement that contains this memory access.
   ScopStmt *getStatement() const { return Statement; }
 
   /// @brief Get the reduction type of this access
   ReductionType getReductionType() const { return RedType; }
 
   /// @brief Set the updated access relation read from JSCOP file.
   void setNewAccessRelation(__isl_take isl_map *NewAccessRelation);
private:
   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 The set of values defined elsewehere required in this ScopStmt and
+  ///        their SCALAR READ MemoryAccesses.
+  DenseMap<Value *, MemoryAccess *> ScalarReads;
+
+  /// @brief The set of values defined in this ScopStmt that are required
+  ///        elsewehere and their SCALAR WRITE MemoryAccesses.
+  DenseMap<Instruction *, MemoryAccess *> ScalarWrites;
+
+  /// @brief If this ScopStmt is an incoming block of a PHI node, its incoming
+  ///        value needs to be written as a trailing write.
+  ///
+  /// 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;
+
   //@}
 
   /// @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:
   }
 
   /// @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; }
 
+  /// @brief Return the MemoryAccess that reloads a value, or nullptr if not
+  ///        (yet) added.
+  MemoryAccess *lookupScalarReadOf(Value *Inst) const {
+    return ScalarReads.lookup(Inst);
+  }
+
+  /// @brief Return the MemoryAccess that writes the value of an instruction
+  ///        defined in this block, or nullptr if not (yet) added.
+  MemoryAccess *lookupScalarWriteOf(Instruction *Inst) const {
+    assert((isRegionStmt() && R->contains(Inst)) ||
+           (!isRegionStmt() && Inst->getParent() == BB));
+    return ScalarWrites.lookup(Inst);
+  }
+
+  /// @brief Return the PHI write MemoryAccess for the incoming values from any
+  ///        basic block in this ScopStmt, or nullptr if not (yet) added.
+  MemoryAccess *lookupPHIWriteOf(PHINode *PHI) const {
+    assert(isBlockStmt() || R->getExit() == PHI->getParent());
+    return PHIWrites.lookup(PHI);
+  }
+
   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.
+  /// @brief Add @p Access to this statement's list of explicit accesses.
   void addExplicitAccess(MemoryAccess *Access);
 
+  /// @brief Add @p Access to this statement's list of SCALAR READ accesses.
+  void addScalarRead(MemoryAccess *Access);
+
+  /// @brief Add @p Access to this statement's list of SCALAR WRITE accesses.
+  void addScalarWrite(MemoryAccess *Access);
+
+  /// @brief Add @p Access to this statement's list of PHI READ accesses.
+  void addPHIRead(MemoryAccess *Access);
+
+  /// @brief Add @p Access to this statement's list of PHI WRITE accesses.
+  void addPHIWrite(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.
   ///
public:
   /// @param  BB The BasicBlock that containing the access functions.
   ///
   /// @return All access functions in BB
   ///
   AccFuncSetType *getAccessFunctions(const BasicBlock *BB) {
     AccFuncMapType::iterator at = AccFuncMap.find(BB);
     return at != AccFuncMap.end() ? &(at->second) : 0;
   }
   //@}
 
   ScalarEvolution *getSE() const;
   ScopDetection &getSD() const { return SD; }
 
   /// @brief Get the count of parameters used in this Scop.
   ///
   /// @return The count of parameters used in this Scop.
   inline ParamVecType::size_type getNumParams() const {
public:
   std::string getAssumedContextStr() const;
 
   /// @brief Get an isl string representing the boundary context.
   std::string getBoundaryContextStr() const;
 
   /// @brief Return the stmt for the given @p BB or nullptr if none.
   ScopStmt *getStmtForBasicBlock(BasicBlock *BB) const;
 
+  /// @brief Return the ScopStmt that represents @p RN; can return nullptr if
+  /// the RegionNode is not within the SCoP or has been removed due to
+  /// simplifications.
+  ScopStmt *getStmtForRegionNode(RegionNode *RN) const;
+
   /// @brief 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.
   //@{
   typedef StmtSet::iterator iterator;
class ScopInfo : public RegionPass {
   void buildMemoryAccess(Instruction *Inst, Loop *L, Region *R,
                          const ScopDetection::BoxedLoopsSetTy *BoxedLoops,
                          const InvariantLoadsSetTy &ScopRIL);
 
   /// @brief Analyze and extract the cross-BB scalar dependences (or,
   ///        dataflow dependencies) of an instruction.
   ///
   /// @param Inst               The instruction to be analyzed
-  /// @param R                  The SCoP region
-  /// @param NonAffineSubRegion The non affine sub-region @p Inst is in.
-  ///
-  /// @return     True if the Instruction is used in other BB and a scalar write
-  ///             Access is required.
-  bool buildScalarDependences(Instruction *Inst, Region *R,
-                              Region *NonAffineSubRegio);
+  void buildScalarDependences(Instruction *Inst);
+
+  /// @brief Search for uses of the llvm::Value defined by @p Inst that are not
+  /// within the SCoP. If there is such use, add a SCALAR WRITE such that it is
+  /// available after the SCoP as escaping value.
+  void buildEscapingDependences(Instruction *Inst);
 
   /// @brief Create MemoryAccesses for the given PHI node in the given region.
   ///
   /// @param PHI                The PHI node to be handled
   /// @param R                  The SCoP region
   /// @param NonAffineSubRegion The non affine sub-region @p PHI is in.
   /// @param IsExitBlock        Flag to indicate that @p PHI is in the exit BB.
   void buildPHIAccesses(PHINode *PHI, Region &R, Region *NonAffineSubRegion,
class ScopInfo : public RegionPass {
   /// @param NonAffineSubRegion The non affine sub-region @p BB is in.
   /// @param IsExitBlock        Flag to indicate that @p BB is in the exit BB.
   void buildAccessFunctions(Region &R, BasicBlock &BB,
                             Region *NonAffineSubRegion = nullptr,
                             bool IsExitBlock = false);
 
   /// @brief Create a new MemoryAccess object and add it to #AccFuncMap.
   ///
+  /// @param Stmt        The ScopStmt this access will be added to.
   /// @param BB          The block where the access takes place.
   /// @param Inst        The instruction doing the access. It is not necessarily
   ///                    inside @p BB.
   /// @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.
   ///
   /// @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);
+  MemoryAccess *addMemoryAccess(
+      ScopStmt *Stmt, 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.
   /// @param IsAffine    Whether all subscripts are affine expressions.
   /// @param Subscripts  Access subscripts per dimension.
   /// @param Sizes       The array dimension's sizes.
   /// @param AccessValue Value read or written.
   /// @see AccessOrigin
   void addExplicitAccess(Instruction *MemAccInst, MemoryAccess::AccessType Type,
                          Value *BaseAddress, unsigned ElemBytes, bool IsAffine,
                          ArrayRef<const SCEV *> Subscripts,
                          ArrayRef<const SCEV *> Sizes, Value *AccessValue);
 
-  /// @brief Create a MemoryAccess for writing an llvm::Value.
+  /// @brief Ensure that there is a MemoryAccess that writes a value's
+  /// definition.
   ///
-  /// The access will be created at the @p Value's definition.
+  /// The access will be in the ScopStmt where @p Value is defined, if none
+  /// exists yet.
   ///
   /// @param Value The value to be written.
   /// @see addScalarReadAccess()
   /// @see AccessOrigin
-  void addScalarWriteAccess(Instruction *Value);
+  void ensureScalarStore(Instruction *Value);
 
-  /// @brief Create a MemoryAccess for reloading an llvm::Value.
-  ///
-  /// Use this overload only for non-PHI instructions.
+  /// @brief Ensures that a @p Value will be reloaded in the ScopStmt that
+  /// contains UserBB.
   ///
-  /// @param Value The scalar expected to be loaded.
-  /// @param User  User of the scalar; this is where the access is added.
-  /// @see addScalarWriteAccess()
-  /// @see AccessOrigin
-  void addScalarReadAccess(Value *Value, Instruction *User);
-
-  /// @brief Create a MemoryAccess for reloading an llvm::Value.
-  ///
-  /// This is for PHINodes using the scalar. As we model it, the used value must
-  /// be available at the incoming block instead of when hitting the
-  /// instruction.
-  ///
-  /// @param Value  The scalar expected to be loaded.
-  /// @param User   The PHI node referencing @p Value.
-  /// @param UserBB Incoming block for the incoming @p Value.
-  /// @see addPHIWriteAccess()
+  /// @param Value  The scalar expected to be loaded.
+  /// @param UserBB Where to reload the value.
   /// @see addScalarWriteAccess()
   /// @see AccessOrigin
-  void addScalarReadAccess(Value *Value, PHINode *User, BasicBlock *UserBB);
+  void ensureScalarReload(Value *Value, BasicBlock *UserBB);
 
   /// @brief Create a write MemoryAccess for the incoming block of a phi node.
   ///
   /// Each of the incoming blocks write their incoming value to be picked in the
   /// phi's block.
   ///
   /// @param PHI           PHINode under consideration.
   /// @param IncomingBlock Some predecessor block.
   /// @param IncomingValue @p PHI's value when coming from @p IncomingBlock.
   /// @param IsExitBlock   When true, uses the .s2a alloca instead of the
   ///                      .phiops one. Required for values escaping through a
   ///                      PHINode in the SCoP region's exit block.
   /// @see addPHIReadAccess()
   /// @see AccessOrigin
-  void addPHIWriteAccess(PHINode *PHI, BasicBlock *IncomingBlock,
+  void ensurePHIWriteAccess(PHINode *PHI, BasicBlock *IncomingBlock,
                             Value *IncomingValue, bool IsExitBlock);
 
   /// @brief Create a MemoryAccess for reading the value of a phi.
   ///
   /// The modeling assumes that all incoming blocks write their incoming value
   /// to the same location. Thus, this access will read the incoming block's
   /// value as instructed by this @p PHI.
   ///
   /// @param PHI PHINode under consideration; the READ access will be added

include/polly/Support/ScopHelper.h

 /// @param LI The LoopInfo analysis.
 /// @param SE The scalar evolution database.
 /// @param R The region out of which SSA names are parameters.
 /// @return If the instruction I can be regenerated from its
 ///         scalar evolution representation, return true,
 ///         otherwise return false.
 bool canSynthesize(const llvm::Value *V, const llvm::LoopInfo *LI,
                    llvm::ScalarEvolution *SE, const llvm::Region *R);
+
+/// @brief Return the block in which a value is used.
+///
+/// For normal instructions, this is the instruction's parent block. For PHI
+/// nodes, this is the incoming block of that use, because this is where the
+/// operand must be defined (i.e. its definition dominates this block).
+/// Non-instructions do not use operands at a specific point such that in this
+/// case this function returns nullptr.
+llvm::BasicBlock *getUseBlock(llvm::Use &U);
 }
 #endif

lib/Analysis/ScopInfo.cpp

void MemoryAccess::assumeNoOutOfBound() {
   Outside = isl_set_params(Outside);
 
   // Remove divs to avoid the construction of overly complicated assumptions.
   // Doing so increases the set of parameter combinations that are assumed to
   // not appear. This is always save, but may make the resulting run-time check
   // bail out more often than strictly necessary.
   Outside = isl_set_remove_divs(Outside);
   Outside = isl_set_complement(Outside);
-  Statement->getParent()->addAssumption(INBOUNDS, Outside,
-                                        getAccessInstruction()->getDebugLoc());
+  Statement->getParent()->addAssumption(
+      INBOUNDS, Outside,
+      getAccessInstruction() ? getAccessInstruction()->getDebugLoc() : nullptr);
   isl_space_free(Space);
 }
 
 void MemoryAccess::computeBoundsOnAccessRelation(unsigned ElementSize) {
   ScalarEvolution *SE = Statement->getParent()->getSE();
 
   Value *Ptr = getPointerOperand(*getAccessInstruction());
   if (!Ptr || !SE->isSCEVable(Ptr->getType()))
case MUST_WRITE:
     OS.indent(12) << "MustWriteAccess :=\t";
     break;
   case MAY_WRITE:
     OS.indent(12) << "MayWriteAccess :=\t";
     break;
   }
   OS << "[Reduction Type: " << getReductionType() << "] ";
   OS << "[Scalar: " << isImplicit() << "]\n";
+  if (AccessRelation)
     OS.indent(16) << getOriginalAccessRelationStr() << ";\n";
   if (hasNewAccessRelation())
     OS.indent(11) << "new: " << getNewAccessRelationStr() << ";\n";
 }
 
 void MemoryAccess::dump() const { print(errs()); }
 
 // Create a map in the size of the provided set domain, that maps from the
 // one element of the provided set domain to another element of the provided
void ScopStmt::buildAccessRelations() {
   for (MemoryAccess *Access : MemAccs) {
     Type *ElementType = Access->getAccessValue()->getType();
 
     ScopArrayInfo::ARRAYKIND Ty;
     if (Access->isPHI())
       Ty = ScopArrayInfo::KIND_PHI;
     else if (Access->isExitPHI())
       Ty = ScopArrayInfo::KIND_EXIT_PHI;
-    else if (Access->isImplicit())
+    else if (Access->isScalar())
       Ty = ScopArrayInfo::KIND_SCALAR;
     else
       Ty = ScopArrayInfo::KIND_ARRAY;
 
     const ScopArrayInfo *SAI = getParent()->getOrCreateScopArrayInfo(
         Access->getBaseAddr(), ElementType, Access->Sizes, Ty);
 
     Access->buildAccessRelation(SAI);
   }

 void ScopStmt::addTrailingWrite(MemoryAccess *Access) {
   assert(Access->isImplicit());
   assert(Access->isWrite());
 
   TrailingWrites.push_back(Access);
   MemAccs.push_back(Access);
 }
 
+void ScopStmt::addScalarRead(MemoryAccess *Access) {
+  assert(Access->isScalar() && Access->isRead());
+
+  Value *AccessVal = Access->getAccessValue();
+  assert(!ScalarReads.lookup(AccessVal));
+
+  ScalarReads[AccessVal] = Access;
+  addLeadingLoad(Access);
+}
+
+void ScopStmt::addScalarWrite(MemoryAccess *Access) {
+  assert(Access->isScalar() && Access->isWrite());
+
+  Instruction *AccessVal = cast<Instruction>(Access->getAccessValue());
+  assert(Parent.getStmtForBasicBlock(AccessVal->getParent()) == this);
+  assert(!ScalarWrites.lookup(cast<Instruction>(AccessVal)));
+
+  ScalarWrites[AccessVal] = Access;
+  addTrailingWrite(Access);
+}
+
+void ScopStmt::addPHIRead(MemoryAccess *Access) {
+  assert(Access->isPHI() && Access->isRead());
+
+  addLeadingLoad(Access);
+}
+
+void ScopStmt::addPHIWrite(MemoryAccess *Access) {
+  assert(Access->isImplicit() && Access->isWrite() &&
+         "The origin must be either PHI of SCALAR (for escaping PHI values in "
+         "the exit block)");
+
+  PHINode *PHI = cast<PHINode>(Access->getBaseAddr());
+  assert(!PHIWrites.lookup(PHI));
+
+  PHIWrites[PHI] = Access;
+  addTrailingWrite(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.

 ///{
 
 /// @brief Return the block that is the representing block for @p RN.
 static inline BasicBlock *getRegionNodeBasicBlock(RegionNode *RN) {
   return RN->isSubRegion() ? RN->getNodeAs<Region>()->getEntry()
                            : RN->getNodeAs<BasicBlock>();
 }
 
+static inline BasicBlock *getScopStmtBasicBlock(ScopStmt *Stmt) {
+  return Stmt->isRegionStmt() ? Stmt->getRegion()->getEntry()
+                              : Stmt->getBasicBlock();
+}
+
 /// @brief Return the @p idx'th block that is executed after @p RN.
 static inline BasicBlock *
 getRegionNodeSuccessor(RegionNode *RN, TerminatorInst *TI, unsigned idx) {
   if (RN->isSubRegion()) {
     assert(idx == 0);
     return RN->getNodeAs<Region>()->getExit();
   }
   return TI->getSuccessor(idx);
bool Scop::restrictDomains(__isl_take isl_union_set *Domain) {
   isl_union_set_free(Domain);
   return Changed;
 }
 
 ScalarEvolution *Scop::getSE() const { return SE; }
 
 bool Scop::isIgnored(RegionNode *RN) {
   BasicBlock *BB = getRegionNodeBasicBlock(RN);
+  ScopStmt *Stmt = getStmtForRegionNode(RN);
+
+  // If there is no stmt, then it already has been removed.
+  if (!Stmt)
+    return true;
 
   // Check if there are accesses contained.
-  bool ContainsAccesses = false;
-  if (!RN->isSubRegion())
-    ContainsAccesses = getAccessFunctions(BB);
-  else
-    for (BasicBlock *RBB : RN->getNodeAs<Region>()->blocks())
-      ContainsAccesses |= (getAccessFunctions(RBB) != nullptr);
-  if (!ContainsAccesses)
+  if (Stmt->isEmpty())
     return true;
 
   // Check for reachability via non-error blocks.
   if (!DomainMap.count(BB))
     return true;
 
   // Check if error blocks are contained.
   if (containsErrorBlock(RN, getRegion(), LI, DT))

 
 ScopStmt *Scop::getStmtForBasicBlock(BasicBlock *BB) const {
   auto StmtMapIt = StmtMap.find(BB);
   if (StmtMapIt == StmtMap.end())
     return nullptr;
   return StmtMapIt->second;
 }
 
+ScopStmt *Scop::getStmtForRegionNode(RegionNode *RN) const {
+  return getStmtForBasicBlock(getRegionNodeBasicBlock(RN));
+}
+
 int Scop::getRelativeLoopDepth(const Loop *L) const {
   Loop *OuterLoop =
       L ? R.outermostLoopInRegion(const_cast<Loop *>(L)) : nullptr;
   if (!OuterLoop)
     return -1;
   return L->getLoopDepth() - OuterLoop->getLoopDepth();
 }
 
 void ScopInfo::buildPHIAccesses(PHINode *PHI, Region &R,
                                 Region *NonAffineSubRegion, bool IsExitBlock) {
 
   // PHI nodes that are in the exit block of the region, hence if IsExitBlock is
   // true, are not modeled as ordinary PHI nodes as they are not part of the
   // region. However, we model the operands in the predecessor blocks that are
   // part of the region as regular scalar accesses.
 
   // If we can synthesize a PHI we can skip it, however only if it is in
   // the region. If it is not it can only be in the exit block of the region.
   // In this case we model the operands but not the PHI itself.
   if (!IsExitBlock && canSynthesize(PHI, LI, SE, &R))
     return;
 
+  // Do not build scalar dependences inside a non-affine subregion. Region
+  // entries can have a mix of incoming edges from within and outside the
+  // region, s.t. a PHI demotion is required as well.
+  // Should be equivalent to getStmtForBasicBlock() == get
+  if (NonAffineSubRegion && PHI->getParent() != NonAffineSubRegion->getEntry())
+    return;
+
   // PHI nodes are modeled as if they had been demoted prior to the SCoP
   // detection. Hence, the PHI is a load of a new memory location in which the
   // incoming value was written at the end of the incoming basic block.
-  bool OnlyNonAffineSubRegionOperands = true;
   for (unsigned u = 0; u < PHI->getNumIncomingValues(); u++) {
     Value *Op = PHI->getIncomingValue(u);
     BasicBlock *OpBB = PHI->getIncomingBlock(u);
 
-    // Do not build scalar dependences inside a non-affine subregion.
-    if (NonAffineSubRegion && NonAffineSubRegion->contains(OpBB))
-      continue;
-
-    OnlyNonAffineSubRegionOperands = false;
-
-    if (!R.contains(OpBB))
-      continue;
-
-    Instruction *OpI = dyn_cast<Instruction>(Op);
-    if (OpI) {
-      BasicBlock *OpIBB = OpI->getParent();
-      // As we pretend there is a use (or more precise a write) of OpI in OpBB
-      // we have to insert a scalar dependence from the definition of OpI to
-      // OpBB if the definition is not in OpBB.
-      if (scop->getStmtForBasicBlock(OpIBB) !=
-          scop->getStmtForBasicBlock(OpBB)) {
-        addScalarReadAccess(OpI, PHI, OpBB);
-        addScalarWriteAccess(OpI);
-      }
-    } else if (ModelReadOnlyScalars && !isa<Constant>(Op)) {
-      addScalarReadAccess(Op, PHI, OpBB);
-    }
-
-    addPHIWriteAccess(PHI, OpBB, Op, IsExitBlock);
+    ensurePHIWriteAccess(PHI, OpBB, Op, IsExitBlock);
   }
-
-  if (!OnlyNonAffineSubRegionOperands && !IsExitBlock) {
+  if (!IsExitBlock)
     addPHIReadAccess(PHI);
-  }
-}
-
-bool ScopInfo::buildScalarDependences(Instruction *Inst, Region *R,
-                                      Region *NonAffineSubRegion) {
-  bool canSynthesizeInst = canSynthesize(Inst, LI, SE, R);
-  if (isIgnoredIntrinsic(Inst))
-    return false;
 
-  bool AnyCrossStmtUse = false;
-  BasicBlock *ParentBB = Inst->getParent();
+void ScopInfo::buildScalarDependences(Instruction *Inst) {
+  assert(!isa<PHINode>(Inst));
 
-  for (User *U : Inst->users()) {
-    Instruction *UI = dyn_cast<Instruction>(U);
-
-    // Ignore the strange user
-    if (UI == 0)
-      continue;
-
-    BasicBlock *UseParent = UI->getParent();
-
-    // Ignore basic block local uses. A value that is defined in a scop, but
-    // used in a PHI node in the same basic block does not count as basic block
-    // local, as for such cases a control flow edge is passed between definition
-    // and use.
-    if (UseParent == ParentBB && !isa<PHINode>(UI))
-      continue;
-
-    // Uses by PHI nodes in the entry node count as external uses in case the
-    // use is through an incoming block that is itself not contained in the
-    // region.
-    if (R->getEntry() == UseParent) {
-      if (auto *PHI = dyn_cast<PHINode>(UI)) {
-        bool ExternalUse = false;
-        for (unsigned i = 0; i < PHI->getNumIncomingValues(); i++) {
-          if (PHI->getIncomingValue(i) == Inst &&
-              !R->contains(PHI->getIncomingBlock(i))) {
-            ExternalUse = true;
-            break;
-          }
-        }
-
-        if (ExternalUse) {
-          AnyCrossStmtUse = true;
-          continue;
-        }
-      }
-    }
-
-    // Do not build scalar dependences inside a non-affine subregion.
-    if (NonAffineSubRegion && NonAffineSubRegion->contains(UseParent))
-      continue;
-
-    // Check for PHI nodes in the region exit and skip them, if they will be
-    // modeled as PHI nodes.
-    //
-    // PHI nodes in the region exit that have more than two incoming edges need
-    // to be modeled as PHI-Nodes to correctly model the fact that depending on
-    // the control flow a different value will be assigned to the PHI node. In
-    // case this is the case, there is no need to create an additional normal
-    // scalar dependence. Hence, bail out before we register an "out-of-region"
-    // use for this definition.
-    if (isa<PHINode>(UI) && UI->getParent() == R->getExit() &&
-        !R->getExitingBlock())
-      continue;
-
-    // Check whether or not the use is in the SCoP.
-    if (!R->contains(UseParent)) {
-      AnyCrossStmtUse = true;
-      continue;
-    }
-
-    // If the instruction can be synthesized and the user is in the region
-    // we do not need to add scalar dependences.
-    if (canSynthesizeInst)
-      continue;
-
-    // No need to translate these scalar dependences into polyhedral form,
-    // because synthesizable scalars can be generated by the code generator.
-    if (canSynthesize(UI, LI, SE, R))
-      continue;
-
-    // Skip PHI nodes in the region as they handle their operands on their own.
-    if (isa<PHINode>(UI))
-      continue;
-
-    // Now U is used in another statement.
-    AnyCrossStmtUse = true;
-
-    // Do not build a read access that is not in the current SCoP
-    // Use the def instruction as base address of the MemoryAccess, so that it
-    // will become the name of the scalar access in the polyhedral form.
-    addScalarReadAccess(Inst, UI);
-  }
-
-  if (ModelReadOnlyScalars && !isa<PHINode>(Inst)) {
-    for (Value *Op : Inst->operands()) {
-      if (canSynthesize(Op, LI, SE, R))
-        continue;
-
-      if (Instruction *OpInst = dyn_cast<Instruction>(Op))
-        if (R->contains(OpInst))
-          continue;
-
-      if (isa<Constant>(Op))
-        continue;
-
-      addScalarReadAccess(Op, Inst);
-    }
-  }
-
-  return AnyCrossStmtUse;
+  // Pull-in required operands.
+  for (auto &Op : Inst->operands())
+    ensureScalarReload(Op.get(), Inst->getParent());
+}
+
+void ScopInfo::buildEscapingDependences(Instruction *Inst) {
+  Region *R = &scop->getRegion();
+
+  // Check for uses of this instruction outside the scop. Because we do not
+  // iterate over such instructions and therefore do not "ensured" the existence
+  // of a write, we must determine such use here.
+  for (Use &U : Inst->uses()) {
+    Instruction *UI = dyn_cast<Instruction>(U.getUser());
+    if (!UI)
+      continue;
+
+    BasicBlock *UseParent = getUseBlock(U);
+    BasicBlock *UserParent = UI->getParent();
+
+    // TODO: Explain condition
+    if (!R->contains(UseParent) ||
+        (isa<PHINode>(UI) && UserParent == R->getExit() &&
+         R->getExitingBlock())) {
+      // At least one escaping use found.
+      ensureScalarStore(Inst);
 }
 
 extern MapInsnToMemAcc InsnToMemAcc;
 
 void ScopInfo::buildMemoryAccess(
     Instruction *Inst, Loop *L, Region *R,
     const ScopDetection::BoxedLoopsSetTy *BoxedLoops,
     const InvariantLoadsSetTy &ScopRIL) {
void ScopInfo::buildAccessFunctions(Region &R, BasicBlock &BB,
   Loop *L = LI->getLoopFor(&BB);
 
   // The set of loops contained in non-affine subregions that are part of R.
   const ScopDetection::BoxedLoopsSetTy *BoxedLoops = SD->getBoxedLoops(&R);
 
   // The set of loads that are required to be invariant.
   auto &ScopRIL = *SD->getRequiredInvariantLoads(&R);
 
-  for (BasicBlock::iterator I = BB.begin(), E = --BB.end(); I != E; ++I) {
-    Instruction *Inst = &*I;
+  for (Instruction &Inst : BB) {
 
-    PHINode *PHI = dyn_cast<PHINode>(Inst);
+    PHINode *PHI = dyn_cast<PHINode>(&Inst);
     if (PHI)
       buildPHIAccesses(PHI, R, NonAffineSubRegion, IsExitBlock);
 
     // For the exit block we stop modeling after the last PHI node.
     if (!PHI && IsExitBlock)
       break;
 
     // TODO: At this point we only know that elements of ScopRIL have to be
     //       invariant and will be hoisted for the SCoP to be processed. Though,
     //       there might be other invariant accesses that will be hoisted and
     //       that would allow to make a non-affine access affine.
     if (isa<LoadInst>(Inst) || isa<StoreInst>(Inst))
-      buildMemoryAccess(Inst, L, &R, BoxedLoops, ScopRIL);
+      buildMemoryAccess(&Inst, L, &R, BoxedLoops, ScopRIL);
 
-    if (isIgnoredIntrinsic(Inst))
+    if (isIgnoredIntrinsic(&Inst))
       continue;
 
     // Do not build scalar dependences for required invariant loads as we will
     // hoist them later on anyway or drop the SCoP if we cannot.
-    if (ScopRIL.count(dyn_cast<LoadInst>(Inst)))
+    if (ScopRIL.count(dyn_cast<LoadInst>(&Inst)))
       continue;
 
-    if (buildScalarDependences(Inst, &R, NonAffineSubRegion)) {
-      if (!isa<StoreInst>(Inst))
-        addScalarWriteAccess(Inst);
-    }
+    if (!PHI)
+      buildScalarDependences(&Inst);
+    if (!IsExitBlock)
+      buildEscapingDependences(&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);
-
+MemoryAccess *ScopInfo::addMemoryAccess(
+    ScopStmt *Stmt, 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) {
   // Do not create a memory access for anything not in the SCoP. It would be
   // ignored anyway.
   if (!Stmt)
     return nullptr;
 
   AccFuncSetType &AccList = AccFuncMap[BB];
   Value *BaseAddr = BaseAddress;
   std::string BaseName = getIslCompatibleName("MemRef_", BaseAddr, "");
 
+  // The execution of an explicit store is not guranteed if not in the entry
+  // block of a subregion. By contrast, implicit writes must occur in
+  // well-formed IR code.
+  if (Origin == MemoryAccess::EXPLICIT) {
     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);
   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));
+  ScopStmt *Stmt = scop->getStmtForBasicBlock(MemAccInst->getParent());
   MemoryAccess *Acc = addMemoryAccess(
-      MemAccInst->getParent(), MemAccInst, Type, BaseAddress, ElemBytes,
+      Stmt, MemAccInst->getParent(), MemAccInst, Type, BaseAddress, ElemBytes,
       IsAffine, AccessValue, Subscripts, Sizes, MemoryAccess::EXPLICIT);
   if (Acc)
     Acc->getStatement()->addExplicitAccess(Acc);
 }
-void ScopInfo::addScalarWriteAccess(Instruction *Value) {
+
+void ScopInfo::ensureScalarStore(Instruction *Value) {
+  ScopStmt *Stmt = scop->getStmtForBasicBlock(Value->getParent());
+
+  // Value not defined within the SCoP.
+  if (!Stmt)
+    return;
+
+  // Do not process further if the value is already written.
+  if (Stmt->lookupScalarWriteOf(Value))
+    return;
+
   MemoryAccess *Acc =
-      addMemoryAccess(Value->getParent(), Value, MemoryAccess::MUST_WRITE,
+      addMemoryAccess(Stmt, Value->getParent(), Value, MemoryAccess::MUST_WRITE,
                       Value, 1, true, Value, ArrayRef<const SCEV *>(),
                       ArrayRef<const SCEV *>(), MemoryAccess::SCALAR);
   if (Acc)
-    Acc->getStatement()->addTrailingWrite(Acc);
+    Stmt->addScalarWrite(Acc);
 }
-void ScopInfo::addScalarReadAccess(Value *Value, Instruction *User) {
-  assert(!isa<PHINode>(User));
-  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) {
+
+void ScopInfo::ensureScalarReload(Value *Value, BasicBlock *UserBB) {
+
+  // There cannot be an "access" for constants.
+  if (isa<Constant>(Value) || isa<BasicBlock>(Value))
+    return;
+
+  // If the instruction can be synthesized and the user is in the region we do
+  // not need to add scalar dependences.
+  Region &ScopRegion = scop->getRegion();
+  if (canSynthesize(Value, LI, SE, &ScopRegion))
+    return;
+
+  // Determine the ScopStmt containing the value's definition and use. There is
+  // no definition ScopStmt if the value is a function argument, a global
+  // value, or defined outside the scop.
+  Instruction *ValueInst = dyn_cast<Instruction>(Value);
+  ScopStmt *ValueStmt =
+      ValueInst ? scop->getStmtForBasicBlock(ValueInst->getParent()) : nullptr;
+  ScopStmt *UserStmt = scop->getStmtForBasicBlock(UserBB);
+
+  // We do not model uses outside the scop.
+  if (!UserStmt)
+    return;
+
+  // Add MemoryAccess for invariant values only if requested.
+  if (!ModelReadOnlyScalars && !ValueStmt)
+    return;
+
+  // Ignore use-def chains within the same ScopStmt.
+  if (ValueStmt == UserStmt)
+    return;
+
+  // Do not create another MemoryAccess for reloading the value if one already
+  // exists.
+  if (UserStmt->lookupScalarReadOf(Value))
+    return;
+
   MemoryAccess *Acc = addMemoryAccess(
-      UserBB, User, MemoryAccess::READ, Value, 1, true, Value,
+      UserStmt, UserBB, nullptr, MemoryAccess::READ, Value, 1, true, Value,
       ArrayRef<const SCEV *>(), ArrayRef<const SCEV *>(), MemoryAccess::SCALAR);
-  if (Acc)
-    Acc->getStatement()->addLeadingLoad(Acc);
+  if (!Acc)
+    return;
+
+  UserStmt->addScalarRead(Acc);
+
+  // If we load the value, we should also ensure that it is written.
+  if (ValueStmt)
+    ensureScalarStore(ValueInst);
 }
-void ScopInfo::addPHIWriteAccess(PHINode *PHI, BasicBlock *IncomingBlock,
+
+void ScopInfo::ensurePHIWriteAccess(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);
+
+  ScopStmt *PHIStmt = scop->getStmtForBasicBlock(PHI->getParent());
+  ScopStmt *IncomingStmt = scop->getStmtForBasicBlock(IncomingBlock);
+
+  assert(IsExitBlock == !PHIStmt);
+  if (!IncomingStmt)
+    return;
+
+  // Take care for the incoming value being available in the incoming block.
+  // This must be done before the check for multiple PHI writes because multiple
+  // exiting edges from subregion each can be the effective written value of the
+  // subregion. As such, all of them must be made available in the subregion
+  // statement.
+  ensureScalarReload(IncomingValue, IncomingBlock);
+
+  // Do not add more than one MemoryAccess per PHINode and ScopStmt.
+  if (MemoryAccess *Acc = IncomingStmt->lookupPHIWriteOf(PHI)) {
+    assert(Acc->getAccessInstruction() == PHI);
+    Acc->addIncoming(IncomingBlock, IncomingValue);
+    return;
+  }
+
+  MemoryAccess *Acc = addMemoryAccess(
+      IncomingStmt, PHI->getParent(), PHI, MemoryAccess::MUST_WRITE, PHI, 1,
+      true, PHI, ArrayRef<const SCEV *>(), ArrayRef<const SCEV *>(),
+  assert(Acc);
+  Acc->addIncoming(IncomingBlock, IncomingValue);
+  IncomingStmt->addPHIWrite(Acc);
 }
+
 void ScopInfo::addPHIReadAccess(PHINode *PHI) {
+  ScopStmt *Stmt = scop->getStmtForBasicBlock(PHI->getParent());
   MemoryAccess *Acc = addMemoryAccess(
-      PHI->getParent(), PHI, MemoryAccess::READ, PHI, 1, true, PHI,
+      Stmt, PHI->getParent(), PHI, MemoryAccess::READ, PHI, 1, true, PHI,
       ArrayRef<const SCEV *>(), ArrayRef<const SCEV *>(), MemoryAccess::PHI);
   if (Acc)
-    Acc->getStatement()->addLeadingLoad(Acc);
+    Acc->getStatement()->addPHIRead(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,
                                         Value *Address) {
   // If there are escape users we get the alloca for this instruction and put it
   // in the EscapeMap for later finalization. Lastly, if the instruction was
   // copied multiple times we already did this and can exit.
   if (EscapeMap.count(Inst))
     return;
 
   EscapeUserVectorTy EscapeUsers;
-  for (User *U : Inst->users()) {
+  for (Use &U : Inst->uses()) {
 
     // Non-instruction user will never escape.
-    Instruction *UI = dyn_cast<Instruction>(U);
+    Instruction *UI = dyn_cast<Instruction>(U.getUser());
     if (!UI)
       continue;
 
-    if (R.contains(UI))
+    if (R.contains(getUseBlock(U)))
       continue;
 
     EscapeUsers.push_back(UI);
   }
 
   // Exit if no escape uses were found.
   if (EscapeUsers.empty())
     return;
Value *BlockGenerator::getNewScalarValue(Value *ScalarValue, const Region &R,
   //      (a) The value was defined in the current block, thus a copy is in
   //          the BBMap ==> use the mapped value.
   //      (b) The value was defined in a previous block, thus we demoted it
   //          earlier ==> use the reloaded value.
   Instruction *ScalarValueInst = dyn_cast<Instruction>(ScalarValue);
   if (!ScalarValueInst)
     return ScalarValue;
 
+  if (Value *ScalarValueCopy = BBMap.lookup(ScalarValueInst))
+    return /* Case (3a) */ ScalarValueCopy;
+
   if (!R.contains(ScalarValueInst)) {
     if (Value *ScalarValueCopy = GlobalMap.lookup(ScalarValueInst))
       return /* Case (3a) */ ScalarValueCopy;
     else
       return /* Case 2 */ ScalarValue;
   }
 
-  if (Value *ScalarValueCopy = BBMap.lookup(ScalarValueInst))
-    return /* Case (3a) */ ScalarValueCopy;
-
   if ((Stmt.isBlockStmt() &&
        Stmt.getBasicBlock() == ScalarValueInst->getParent()) ||
       (Stmt.isRegionStmt() && Stmt.getRegion()->contains(ScalarValueInst))) {
     auto SynthesizedValue = trySynthesizeNewValue(
         Stmt, ScalarValueInst, BBMap, LTS, getLoopForInst(ScalarValueInst));
 
     if (SynthesizedValue)
       return SynthesizedValue;
void BlockGenerator::generateScalarStores(ScopStmt &Stmt, LoopToScevMapT &LTS,
 
   assert(Stmt.isBlockStmt() && "Region statements need to use the "
                                "generateScalarStores() function in the "
                                "RegionGenerator");
 
   for (MemoryAccess *MA : Stmt.getTrailingWrites()) {
     assert(MA->isImplicit());
     assert(MA->isWrite());
+    assert(!MA->isAnyPHI() || MA->getIncoming().size() == 1);
 
-    Value *Val = MA->getAccessValue();
+    Value *Val =
+        MA->isAnyPHI() ? MA->getIncoming()[0].second : MA->getAccessValue();
     auto *Address = getOrCreateAlloca(*MA);
 
     Val = getNewScalarValue(Val, R, Stmt, LTS, BBMap);
     Builder.CreateStore(Val, Address);
   }
 }
 
 void BlockGenerator::createScalarInitialization(Scop &S) {
void RegionGenerator::copyStmt(ScopStmt &Stmt, LoopToScevMapT &LTS,
   generateScalarStores(Stmt, LTS, ValueMap);
   BlockMap.clear();
   RegionMaps.clear();
   IncompletePHINodeMap.clear();
 }
 
 void RegionGenerator::generateScalarStores(ScopStmt &Stmt, LoopToScevMapT &LTS,
                                            ValueMapT &BBMap) {
+  assert(Stmt.isRegionStmt());
   const Region &R = Stmt.getParent()->getRegion();
+  auto &SubR = *Stmt.getRegion();
 
-  assert(Stmt.getRegion() &&
-         "Block statements need to use the generateScalarStores() "
-         "function in the BlockGenerator");
-
-  for (MemoryAccess *MA : Stmt) {
-    if (MA->isExplicit() || MA->isRead())
-      continue;
+  for (MemoryAccess *MA : Stmt.getTrailingWrites()) {
+    assert(MA->isImplicit());
+    assert(MA->isWrite());
 
-    Instruction *ScalarInst = MA->getAccessInstruction();
-    Value *Val = MA->getAccessValue();
+    Value *NewVal;
+    if (MA->isAnyPHI()) {
+      auto Incoming = MA->getIncoming();
+      assert(!Incoming.empty());
+
+      if (Incoming.size() == 1) {
+        Value *OldVal = Incoming[0].second;
+        NewVal = getNewScalarValue(OldVal, R, Stmt, LTS, BBMap);
+      } else {
+        // Create a PHI of all possible outgoing values of this subregion.
 
-    // In case we add the store into an exiting block, we need to restore the
-    // position for stores in the exit node.
         BasicBlock *SavedInsertBB = Builder.GetInsertBlock();
-    auto SavedInsertionPoint = Builder.GetInsertPoint();
-    ValueMapT *LocalBBMap = &BBMap;
-
-    // Implicit writes induced by PHIs must be written in the incoming blocks.
-    if (MA->isPHI() || MA->isExitPHI()) {
-      BasicBlock *ExitingBB = ScalarInst->getParent();
-      BasicBlock *ExitingBBCopy = BlockMap[ExitingBB];
-      Builder.SetInsertPoint(ExitingBBCopy->getTerminator());
-
-      // For the incoming blocks, use the block's BBMap instead of the one for
-      // the entire region.
-      LocalBBMap = &RegionMaps[ExitingBBCopy];
+        auto SavedIP = Builder.GetInsertPoint();
+        PHINode *OrigPHI = cast<PHINode>(MA->getAccessInstruction());
+        BasicBlock *NewSubregionExit = Builder.GetInsertBlock();
+
+        // This can happen if the subregion is simplified after the ScopStmts
+        // have been created; simplification happens as part of CodeGeneration.
+        if (OrigPHI->getParent() != SubR.getExit()) {
+          BasicBlock *FormerExit = SubR.getExitingBlock();
+          if (FormerExit)
+            NewSubregionExit = BlockMap.lookup(FormerExit);
+        }
+
+        PHINode *NewPHI = PHINode::Create(OrigPHI->getType(), Incoming.size(),
+                                          "polly." + OrigPHI->getName(),
+                                          NewSubregionExit->getFirstNonPHI());
+
+        for (auto &Pair : Incoming) {
+          BasicBlock *OrigIncomingBlock = Pair.first;
+          BasicBlock *NewIncomingBlock = BlockMap.lookup(OrigIncomingBlock);
+          Builder.SetInsertPoint(NewIncomingBlock->getTerminator());
+          assert(RegionMaps.count(NewIncomingBlock));
+          ValueMapT *LocalBBMap = &RegionMaps[NewIncomingBlock];
+
+          Value *OrigIncomingValue = Pair.second;
+          Value *NewIncomingValue =
+              getNewScalarValue(OrigIncomingValue, R, Stmt, LTS, *LocalBBMap);
+          NewPHI->addIncoming(NewIncomingValue, NewIncomingBlock);
         }
 
-    auto Address = getOrCreateAlloca(*MA);
-
-    Val = getNewScalarValue(Val, R, Stmt, LTS, *LocalBBMap);
-    Builder.CreateStore(Val, Address);
+        Builder.SetInsertPoint(SavedInsertBB, SavedIP);
+        NewVal = NewPHI;
+      }
+    } else {
+      Value *OldVal = MA->getAccessValue();
+      NewVal = getNewScalarValue(OldVal, R, Stmt, LTS, BBMap);
+    }
 
-    // Restore the insertion point if necessary.
-    if (MA->isPHI() || MA->isExitPHI())
-      Builder.SetInsertPoint(SavedInsertBB, SavedInsertionPoint);
+    Value *Address = getOrCreateAlloca(*MA);
+    Builder.CreateStore(NewVal, Address);
   }
 }
 
 void RegionGenerator::addOperandToPHI(ScopStmt &Stmt, const PHINode *PHI,
                                       PHINode *PHICopy, BasicBlock *IncomingBB,
                                       LoopToScevMapT &LTS) {
   Region *StmtR = Stmt.getRegion();
 

lib/Support/ScopHelper.cpp

bool polly::canSynthesize(const Value *V, const llvm::LoopInfo *LI,
 
   if (const SCEV *Scev = SE->getSCEV(const_cast<Value *>(V)))
     if (!isa<SCEVCouldNotCompute>(Scev))
       if (!hasScalarDepsInsideRegion(Scev, R))
         return true;
 
   return false;
 }
+
+llvm::BasicBlock *polly::getUseBlock(llvm::Use &U) {
+  Instruction *UI = dyn_cast<Instruction>(U.getUser());
+  if (!UI)
+    return nullptr;
+
+  if (PHINode *PHI = dyn_cast<PHINode>(UI))
+    return PHI->getIncomingBlock(U);
+
+  return UI->getParent();
+}

test/Isl/CodeGen/non-affine-phi-node-expansion-2.ll

 ; RUN: opt %loadPolly -polly-codegen \
 ; RUN:     -S < %s | FileCheck %s
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 
 
 ; CHECK: polly.stmt.bb3:                                   ; preds = %polly.stmt.bb3.entry
 ; CHECK:   %tmp6_p_scalar_ = load double, double* %arg1{{[0-9]*}}, !alias.scope !0, !noalias !2
 ; CHECK:   %p_tmp7 = fadd double 1.000000e+00, %tmp6_p_scalar_
 ; CHECK:   %p_tmp8 = fcmp olt double 1.400000e+01, %p_tmp7
 ; CHECK:   br i1 %p_tmp8, label %polly.stmt.bb9, label %polly.stmt.bb10
 
 ; CHECK: polly.stmt.bb9:                                   ; preds = %polly.stmt.bb3
-; CHECK:   store double 1.000000e+00, double* %tmp12.phiops
 ; CHECK:   br label %polly.stmt.bb11.exit
 
 ; CHECK: polly.stmt.bb10:                                  ; preds = %polly.stmt.bb3
-; CHECK:   store double 2.000000e+00, double* %tmp12.phiops
 ; CHECK:   br label %polly.stmt.bb11.exit
 
+; CHECK: polly.stmt.bb11.exit:                             ; preds = %polly.stmt.bb10, %polly.stmt.bb9
+; CHECK:   %polly.tmp12 = phi double [ 1.000000e+00, %polly.stmt.bb9 ], [ 2.000000e+00, %polly.stmt.bb10 ]
+; CHECK:   store double %polly.tmp12, double* %tmp12.phiops
 
 define void @hoge(i32 %arg, [1024 x double]* %arg1) {
 bb:
   br label %bb2
 
 bb2:                                              ; preds = %bb
   br label %bb3
 

test/Isl/CodeGen/non-affine-phi-node-expansion-3.ll

loop:
   %val1 = fadd float 1.0, 2.0
   %val2 = fadd float 1.0, 2.0
   br i1 %cond0, label %branch1, label %backedge
 
 ; CHECK-LABEL: polly.stmt.loop:
 ; CHECK-NEXT: %p_val0 = fadd float 1.000000e+00, 2.000000e+00
 ; CHECK-NEXT: %p_val1 = fadd float 1.000000e+00, 2.000000e+00
 ; CHECK-NEXT: %p_val2 = fadd float 1.000000e+00, 2.000000e+00
-; CHECK-NEXT: store float %p_val0, float* %merge.phiops
 ; CHECK-NEXT: br i1
 
 branch1:
   br i1 %cond1, label %branch2, label %backedge
 
 ; CHECK-LABEL: polly.stmt.branch1:
-; CHECK-NEXT:    store float %p_val1, float* %merge.phiops
 ; CHECK-NEXT: br i1
 
 branch2:
   br label %backedge
 
 ; CHECK-LABEL: polly.stmt.branch2:
-; CHECK-NEXT:    store float %p_val2, float* %merge.phiops
 ; CHECK-NEXT:    br label
 
+; CHECK-LABEL: polly.stmt.backedge.exit:
+; CHECK:         %polly.merge = phi float [ %p_val0, %polly.stmt.loop ], [ %p_val1, %polly.stmt.branch1 ], [ %p_val2, %polly.stmt.branch2 ]
+
 backedge:
   %merge = phi float [%val0, %loop], [%val1, %branch1], [%val2, %branch2]
   %indvar.next = add i64 %indvar, 1
   store float %merge, float* %A
   %cmp = icmp sle i64 %indvar.next, 100
   br i1 %cmp, label %loop, label %exit
 
 exit:
   ret void
 }

test/Isl/CodeGen/non-affine-phi-node-expansion-4.ll

 ; RUN: opt %loadPolly -polly-codegen \
 ; RUN:     -S < %s | FileCheck %s
 
 define void @foo(float* %A, i1 %cond0, i1 %cond1) {
 entry:
   br label %loop
 
 loop:
   %indvar = phi i64 [0, %entry], [%indvar.next, %backedge]
   %val0 = fadd float 1.0, 2.0
   %val1 = fadd float 1.0, 2.0
   br i1 %cond0, label %branch1, label %backedge
 
 ; CHECK-LABEL: polly.stmt.loop:
 ; CHECK-NEXT:    %p_val0 = fadd float 1.000000e+00, 2.000000e+00
 ; CHECK-NEXT:    %p_val1 = fadd float 1.000000e+00, 2.000000e+00
-; CHECK-NEXT:    store float %p_val0, float* %merge.phiops
 ; CHECK-NEXT:    br i1
 
 ; The interesting instruction here is %val2, which does not dominate the exit of
 ; the non-affine region. Care needs to be taken when code-generating this write.
 ; Specifically, at some point we modeled this scalar write, which we tried to
 ; code generate in the exit block of the non-affine region.
 branch1:
   %val2 = fadd float 1.0, 2.0
   br i1 %cond1, label %branch2, label %backedge
 
 ; CHECK-LABEL: polly.stmt.branch1:
 ; CHECK-NEXT:    %p_val2 = fadd float 1.000000e+00, 2.000000e+00
-; CHECK-NEXT:    store float %p_val1, float* %merge.phiops
 ; CHECK-NEXT:    br i1
 
 branch2:
   br label %backedge
 
 ; CHECK-LABEL: polly.stmt.branch2:
-; CHECK-NEXT:    store float %p_val2, float* %merge.phiops
 ; CHECK-NEXT:    br label
 
+; CHECK-LABEL: polly.stmt.backedge.exit:
+; CHECK:         %polly.merge = phi float [ %p_val0, %polly.stmt.loop ], [ %p_val1, %polly.stmt.branch1 ], [ %p_val2, %polly.stmt.branch2 ]
+
 backedge:
   %merge = phi float [%val0, %loop], [%val1, %branch1], [%val2, %branch2]
   %indvar.next = add i64 %indvar, 1
   store float %merge, float* %A
   %cmp = icmp sle i64 %indvar.next, 100
   br i1 %cmp, label %loop, label %exit
 
 exit:
   ret void
 }

test/Isl/CodeGen/non-affine-region-exit-phi-incoming-synthesize.ll

 ; RUN: opt %loadPolly -polly-codegen -S < %s | FileCheck %s
 ;
 ; This caused the code generation to generate invalid code as the same BBMap was
 ; used for the whole non-affine region. When %add is synthesized for the
 ; incoming value of subregion_if first, the code for it was generated into
 ; subregion_if, but reused for the incoming value of subregion_exit, although it
 ; is not dominated by subregion_if.
 ;
 ; CHECK-LABEL: polly.stmt.subregion_entry:
 ; CHECK:         %[[R0:[0-9]*]] = add i32 %n, -2
-; CHECK:         store i32 %[[R0]], i32* %retval.s2a
 ;
 ; CHECK-LABEL: polly.stmt.subregion_if:
 ; CHECK:         %[[R1:[0-9]*]] = add i32 %n, -2
-; CHECK:         store i32 %[[R1]], i32* %retval.s2a
+;
+; CHECK-LABEL: polly.stmt.subregion_exit.region_exiting:
+; CHECK:         %polly.retval = phi i32 [ %[[R1]], %polly.stmt.subregion_if ], [ %[[R0]], %polly.stmt.subregion_entry ]
 ;
 ; CHECK-LABEL: polly.stmt.polly.merge_new_and_old.exit:
+; CHECK:         store i32 %polly.retval, i32* %retval.s2a
 ; CHECK:         load i32, i32* %retval.s2a
 
 define i32 @func(i32 %n){
 entry:
   br label %subregion_entry
 
 subregion_entry:
   %add = add nsw i32 %n, -2

test/Isl/CodeGen/out-of-scop-phi-node-use.ll

 ; RUN: opt %loadPolly -polly-codegen -S < %s | FileCheck %s
 
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 target triple = "x86_64-unknown-linux-gnu"
 
 ; CHECK-LABEL: polly.merge_new_and_old:
 ; CHECK-NEXT: %_s.sroa.343.0.ph5161118.ph.merge = phi i32 [ %_s.sroa.343.0.ph5161118.ph.final_reload, %polly.stmt.polly.merge_new_and_old.exit ], [ %_s.sroa.343.0.ph516.lcssa2357, %for.cond.981.region_exiting ]
 
 ; CHECK-LABEL: for.cond.981:
 ; CHECK-NEXT:  %_s.sroa.343.0.ph5161118 = phi i32 [ undef, %for.cond ], [ %_s.sroa.343.0.ph5161118.ph.merge, %polly.merge_new_and_old ]
 
+; CHECK-LABEL: polly.stmt.for.cond.981.region_exiting:
+; CHECK-NEXT:    %polly._s.sroa.343.0.ph5161118 = phi i32 [ undef, %polly.stmt.if.then.960 ], [ undef, %polly.stmt.if.else.969 ]
+; CHECK-NEXT:    br label %polly.stmt.polly.merge_new_and_old.exit
+
 ; CHECK-LABEL: polly.stmt.polly.merge_new_and_old.exit:
-; CHECK-NEXT: %_s.sroa.343.0.ph5161118.ph.final_reload = load i32, i32* %_s.sroa.343.0.ph5161118.s2a
+; CHECK-NEXT:    store i32 %polly._s.sroa.343.0.ph5161118, i32* %_s.sroa.343.0.ph5161118.s2a
+; CHECK-NEXT:    %_s.sroa.343.0.ph5161118.ph.final_reload = load i32, i32* %_s.sroa.343.0.ph5161118.s2a
 
 ; Function Attrs: nounwind uwtable
 define void @lzmaDecode() #0 {
 entry:
   br label %for.cond.outer.outer.outer
 
 for.cond:                                         ; preds = %for.cond.outer.outer.outer
   switch i32 undef, label %cleanup.1072 [

test/Isl/CodeGen/phi-defined-before-scop.ll

 ; RUN: opt %loadPolly -polly-codegen -S < %s | FileCheck %s
 
 ; CHECK-LABEL: polly.merge_new_and_old:
 ; CHECK-NEXT: %tmp7.ph.merge = phi %struct.wibble* [ %tmp7.ph.final_reload, %polly.stmt.bb5 ], [ %tmp7.ph, %bb6.region_exiting ]
 
 ; CHECK-LABEL: polly.stmt.bb3:
-; CHECK-NEXT: %tmp2.s2a.reload = load %struct.wibble*, %struct.wibble** %tmp2.s2a
 ; CHECK-NEXT: store %struct.wibble* %tmp2, %struct.wibble** %tmp7.s2a
 
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 
 %struct.blam = type { i32, i32, i32, i32, i32, i32, i32, i32, i32, i32 }
 %struct.wibble = type { i32, %struct.wibble*, %struct.wibble* }
 
 @global = external global %struct.blam*, align 8

test/Isl/CodeGen/pr25241.ll

 ; RUN: opt %loadPolly -polly-codegen -S < %s | FileCheck %s
 
 ; PR25241 (https://llvm.org/bugs/show_bug.cgi?id=25241)
 ; Ensure that synthesized values of a PHI node argument are generated in the
 ; incoming block, not in the PHI's block.
 
 ; CHECK-LABEL: polly.stmt.if.then.862:
 ; CHECK:         %[[R1:[0-9]+]] = add i32 %tmp, 1
-; CHECK:         store i32 %0, i32* %curr.3.s2a
 ; CHECK:         br label
 
 ; CHECK-LABEL: polly.stmt.polly.merge_new_and_old.exit:
+; CHECK:         store i32 %polly.curr.3, i32* %curr.3.s2a
 ; CHECK:         %curr.3.ph.final_reload = load i32, i32* %curr.3.s2a
 ; CHECK:         br label
 
 
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 target triple = "x86_64-unknown-linux-gnu"
 
 ; Function Attrs: nounwind uwtable

test/Isl/CodeGen/uninitialized_scalar_memory.ll

 ; RUN: opt %loadPolly -S -polly-codegen < %s | FileCheck %s
 ;
 ; Verify we initialize the scalar locations reserved for the incoming phi
 ; values.
 ;
 ; CHECK:      polly.start:
 ; CHECK-NEXT:   store float %ebig.0, float* %ebig.0.s2a
-; CHECK-NEXT:   store i32 %iebig.0, i32* %iebig.0.s2a
 ; CHECK-NEXT:   br label %polly.stmt.if.end.entry
 ;
 ;    int g(void);
 ;    float M;
 ;    int max(float *restrict xbig, int eres, int bres, float *restrict indx) {
 ;      int i, iebig;
 ;      float ebig;
 ;      for (i = 0; i < 4 + eres; i++) {

test/ScopInfo/NonAffine/non_affine_loop_used_later.ll

 ; CHECK:            Schedule :=
 ; CHECK:                [N] -> { Stmt_bb4__TO__bb18[i0] -> [i0, 1] };
 ; CHECK:            ReadAccess := [Reduction Type: NONE] [Scalar: 0]
 ; CHECK:                [N] -> { Stmt_bb4__TO__bb18[i0] -> MemRef_A[i0] };
 ; CHECK:            ReadAccess := [Reduction Type: NONE] [Scalar: 0]
 ; CHECK:                [N] -> { Stmt_bb4__TO__bb18[i0] -> MemRef_A[i0] };
 ; CHECK:            MayWriteAccess := [Reduction Type: NONE] [Scalar: 0]
 ; CHECK:                [N] -> { Stmt_bb4__TO__bb18[i0] -> MemRef_A[i0] };
-; CHECK:            ReadAccess := [Reduction Type: NONE] [Scalar: 1]
-; CHECK:                [N] -> { Stmt_bb4__TO__bb18[i0] -> MemRef_smax[] };
-; CHECK:            MayWriteAccess := [Reduction Type: NONE] [Scalar: 1]
+; CHECK:            MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
 ; CHECK:                [N] -> { Stmt_bb4__TO__bb18[i0] -> MemRef_j_2__phi[] };
 ; CHECK:            ReadAccess := [Reduction Type: NONE] [Scalar: 1]
 ; CHECK:                [N] -> { Stmt_bb4__TO__bb18[i0] -> MemRef_j_0[] };
-; CHECK:            MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
-; CHECK:                [N] -> { Stmt_bb4__TO__bb18[i0] -> MemRef_j_2__phi[] };
 ; CHECK:      Stmt_bb18
 ; CHECK:            Schedule :=
 ; CHECK:                [N] -> { Stmt_bb18[i0] -> [i0, 2] };
 ; CHECK:            MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
 ; CHECK:                [N] -> { Stmt_bb18[i0] -> MemRef_j_2[] };
 ; CHECK:            ReadAccess := [Reduction Type: NONE] [Scalar: 1]
 ; CHECK:                [N] -> { Stmt_bb18[i0] -> MemRef_j_2__phi[] };
 ; CHECK:            ReadAccess := [Reduction Type: NONE] [Scalar: 0]

test/ScopInfo/intra-non-affine-stmt-phi-node.ll

 ; RUN: opt %loadPolly -polly-scops -analyze \
 ; RUN:     -S < %s | FileCheck %s
 
 
 ; CHECK: Statements {
 ; CHECK-NEXT:   Stmt_loop__TO__backedge
 ; CHECK-NEXT:         Domain :=
 ; CHECK-NEXT:             { Stmt_loop__TO__backedge[i0] : i0 <= 100 and i0 >= 0 };
 ; CHECK-NEXT:         Schedule :=
 ; CHECK-NEXT:             { Stmt_loop__TO__backedge[i0] -> [i0, 0] };
 ; CHECK-NEXT:         MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
 ; CHECK-NEXT:             { Stmt_loop__TO__backedge[i0] -> MemRef_merge__phi[] };
-; CHECK-NEXT:         MayWriteAccess :=   [Reduction Type: NONE] [Scalar: 1]
-; CHECK-NEXT:             { Stmt_loop__TO__backedge[i0] -> MemRef_merge__phi[] };
-; CHECK-NEXT:         MayWriteAccess :=   [Reduction Type: NONE] [Scalar: 1]
-; CHECK-NEXT:             { Stmt_loop__TO__backedge[i0] -> MemRef_merge__phi[] };
 ; CHECK-NEXT:   Stmt_backedge
 ; CHECK-NEXT:         Domain :=
 ; CHECK-NEXT:             { Stmt_backedge[i0] : i0 <= 100 and i0 >= 0 };
 ; CHECK-NEXT:         Schedule :=
 ; CHECK-NEXT:             { Stmt_backedge[i0] -> [i0, 1] };
 ; CHECK-NEXT:         ReadAccess :=       [Reduction Type: NONE] [Scalar: 1]
 ; CHECK-NEXT:             { Stmt_backedge[i0] -> MemRef_merge__phi[] };
 ; CHECK-NEXT:         MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 0]

test/ScopInfo/invariant-loads-leave-read-only-statements.ll

 ; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s
 ; RUN: opt %loadPolly -polly-codegen -analyze < %s
 ;
 ;
 ; CHECK:         Statements {
 ; CHECK-NEXT:      Stmt_top_split
 ; CHECK-NEXT:            Domain :=
 ; CHECK-NEXT:                [p_0, p_1, p_2] -> { Stmt_top_split[] };
 ; CHECK-NEXT:            Schedule :=
 ; CHECK-NEXT:                [p_0, p_1, p_2] -> { Stmt_top_split[] -> [0, 0, 0, 0] };
 ; CHECK-NEXT:            MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
-; CHECK-NEXT:                [p_0, p_1, p_2] -> { Stmt_top_split[] -> MemRef_25[] };
-; CHECK-NEXT:            MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
 ; CHECK-NEXT:                [p_0, p_1, p_2] -> { Stmt_top_split[] -> MemRef_26[] };
+; CHECK-NEXT:            MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                [p_0, p_1, p_2] -> { Stmt_top_split[] -> MemRef_25[] };
 ; CHECK-NEXT:      Stmt_L_4
 ; CHECK-NEXT:            Domain :=
 ; CHECK-NEXT:                [p_0, p_1, p_2] -> { Stmt_L_4[i0, i1, i2] : i0 >= 0 and i0 <= -1 + p_0 and i1 >= 0 and i1 <= -1 + p_0 and i2 >= 0 and i2 <= -1 + p_0 };
 ; CHECK-NEXT:            Schedule :=
 ; CHECK-NEXT:                [p_0, p_1, p_2] -> { Stmt_L_4[i0, i1, i2] -> [1, i0, i1, i2] };
 ; CHECK-NEXT:            ReadAccess := [Reduction Type: NONE] [Scalar: 1]
-; CHECK-NEXT:                [p_0, p_1, p_2] -> { Stmt_L_4[i0, i1, i2] -> MemRef_25[] };
+; CHECK-NEXT:                [p_0, p_1, p_2] -> { Stmt_L_4[i0, i1, i2] -> MemRef_22[] };
+; CHECK-NEXT:            ReadAccess := [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                [p_0, p_1, p_2] -> { Stmt_L_4[i0, i1, i2] -> MemRef_19[] };
 ; CHECK-NEXT:            ReadAccess := [Reduction Type: NONE] [Scalar: 0]
 ; CHECK-NEXT:                [p_0, p_1, p_2] -> { Stmt_L_4[i0, i1, i2] -> MemRef_19[i1, i0] };
+; CHECK-NEXT:            ReadAccess := [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                [p_0, p_1, p_2] -> { Stmt_L_4[i0, i1, i2] -> MemRef_8[] };
+; CHECK-NEXT:            ReadAccess := [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                [p_0, p_1, p_2] -> { Stmt_L_4[i0, i1, i2] -> MemRef_5[] };
 ; CHECK-NEXT:            ReadAccess := [Reduction Type: NONE] [Scalar: 0]
 ; CHECK-NEXT:                [p_0, p_1, p_2] -> { Stmt_L_4[i0, i1, i2] -> MemRef_5[i2, i0] };
+; CHECK-NEXT:            ReadAccess := [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                [p_0, p_1, p_2] -> { Stmt_L_4[i0, i1, i2] -> MemRef_15[] };
+; CHECK-NEXT:            ReadAccess := [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                [p_0, p_1, p_2] -> { Stmt_L_4[i0, i1, i2] -> MemRef_12[] };
 ; CHECK-NEXT:            ReadAccess := [Reduction Type: NONE] [Scalar: 0]
 ; CHECK-NEXT:                [p_0, p_1, p_2] -> { Stmt_L_4[i0, i1, i2] -> MemRef_12[i2, i1] };
 ; CHECK-NEXT:            MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 0]
 ; CHECK-NEXT:                [p_0, p_1, p_2] -> { Stmt_L_4[i0, i1, i2] -> MemRef_19[i1, i0] };
+; CHECK-NEXT:            ReadAccess := [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                [p_0, p_1, p_2] -> { Stmt_L_4[i0, i1, i2] -> MemRef_25[] };
 ; CHECK-NEXT:    }
 ;
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 
 %jl_value_t = type { %jl_value_t* }
 
 define %jl_value_t* @julia_gemm_22583(%jl_value_t*, %jl_value_t**, i32) {
 top:

test/ScopInfo/many-scalar-dependences.ll

 ; CHECK:           { Stmt_bb11[i0, i1, i2] -> MemRef_x_3__phi[] };
 ; CHECK: Stmt_bb12
 ; CHECK:       Domain :=
 ; CHECK:           { Stmt_bb12[i0, i1, i2] : i0 <= 99 and i0 >= 0 and i1 <= 99 and i1 >= 0 and i2 <= 99 and i2 >= 0 };
 ; CHECK:       Schedule :=
 ; CHECK:           { Stmt_bb12[i0, i1, i2] -> [i0, 2, i1, 2, i2, 3] };
 ; CHECK:       ReadAccess :=       [Reduction Type: NONE] [Scalar: 1]
 ; CHECK:           { Stmt_bb12[i0, i1, i2] -> MemRef_x_3__phi[] };
-; CHECK:       MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
-; CHECK:           { Stmt_bb12[i0, i1, i2] -> MemRef_x_3[] };
 ; CHECK:       ReadAccess :=       [Reduction Type: NONE] [Scalar: 0]
 ; CHECK:           { Stmt_bb12[i0, i1, i2] -> MemRef_a[i0, i1] };
 ; CHECK:       MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 0]
 ; CHECK:           { Stmt_bb12[i0, i1, i2] -> MemRef_a[i0, i1] };
+; CHECK:       MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
+; CHECK:           { Stmt_bb12[i0, i1, i2] -> MemRef_x_3[] };
 ; CHECK: Stmt_bb16
 ; CHECK:       Domain :=
 ; CHECK:           { Stmt_bb16[i0, i1, i2] : i0 <= 99 and i0 >= 0 and i1 <= 99 and i1 >= 0 and i2 <= 99 and i2 >= 0 };
 ; CHECK:       Schedule :=
 ; CHECK:           { Stmt_bb16[i0, i1, i2] -> [i0, 2, i1, 2, i2, 4] };
 ; CHECK:       MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
 ; CHECK:           { Stmt_bb16[i0, i1, i2] -> MemRef_x_2__phi[] };
 ; CHECK:       ReadAccess :=       [Reduction Type: NONE] [Scalar: 1]

test/ScopInfo/non_affine_region_2.ll

 ; CHECK:         Schedule :=
 ; CHECK:             { Stmt_bb3__TO__bb18[i0] -> [i0, 0] };
 ; CHECK-NOT:         { Stmt_bb3__TO__bb18[i0] -> MemRef_x_0[] };
 ; CHECK-NOT:         { Stmt_bb3__TO__bb18[i0] -> MemRef_x_1[] };
 ; CHECK:         ReadAccess := [Reduction Type: NONE] [Scalar: 0]
 ; CHECK-NEXT:        { Stmt_bb3__TO__bb18[i0] -> MemRef_A[i0] };
 ; CHECK-NOT:         { Stmt_bb3__TO__bb18[i0] -> MemRef_x_0[] };
 ; CHECK-NOT:         { Stmt_bb3__TO__bb18[i0] -> MemRef_x_1[] };
-; CHECK:         MayWriteAccess := [Reduction Type: NONE] [Scalar: 1]
-; CHECK-NEXT:        { Stmt_bb3__TO__bb18[i0] -> MemRef_x_2__phi[] };
-; CHECK-NOT:         { Stmt_bb3__TO__bb18[i0] -> MemRef_x_0[] };
-; CHECK-NOT:         { Stmt_bb3__TO__bb18[i0] -> MemRef_x_1[] };
 ; CHECK:         MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
 ; CHECK-NEXT:        { Stmt_bb3__TO__bb18[i0] -> MemRef_x_2__phi[] };
 ; CHECK-NOT:         { Stmt_bb3__TO__bb18[i0] -> MemRef_x_0[] };
 ; CHECK-NOT:         { Stmt_bb3__TO__bb18[i0] -> MemRef_x_1[] };
 ; CHECK:   Stmt_bb18
 ; CHECK:         Domain :=
 ; CHECK:             { Stmt_bb18[i0] :
 ; CHECK-DAG:               i0 >= 0

test/ScopInfo/non_affine_region_3.ll

 ; CHECK-DAG:           i0 >= 0
 ; CHECK-DAG:         and
 ; CHECK-DAG:           i0 <= 1023
 ; CHECK:              }
 ; CHECK:         Schedule :=
 ; CHECK:             { Stmt_bb3__TO__bb18[i0] -> [i0, 0] };
 ; CHECK:         ReadAccess := [Reduction Type: NONE] [Scalar: 0]
 ; CHECK:             { Stmt_bb3__TO__bb18[i0] -> MemRef_A[i0] };
-; CHECK:         MayWriteAccess := [Reduction Type: NONE] [Scalar: 1]
-; CHECK:             { Stmt_bb3__TO__bb18[i0] -> MemRef_x_2__phi[] };
-; CHECK:         MayWriteAccess := [Reduction Type: NONE] [Scalar: 1]
-; CHECK:             { Stmt_bb3__TO__bb18[i0] -> MemRef_x_2__phi[] };
-; CHECK:         MayWriteAccess := [Reduction Type: NONE] [Scalar: 1]
-; CHECK:             { Stmt_bb3__TO__bb18[i0] -> MemRef_x_2__phi[] };
 ; CHECK:         MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
 ; CHECK:             { Stmt_bb3__TO__bb18[i0] -> MemRef_x_2__phi[] };
 ; CHECK:   Stmt_bb18
 ; CHECK:         Domain :=
 ; CHECK:             { Stmt_bb18[i0] :
 ; CHECK-DAG:           i0 >= 0
 ; CHECK-DAG:         and
 ; CHECK-DAG:           i0 <= 1023

test/ScopInfo/non_affine_region_4.ll

 ;        A[i] = x + y;
 ;      }
 ;    }
 ;
 ; CHECK:    Region: %bb1---%bb11
 ;
 ; CHECK: Arrays {
 ; CHECK:   i32 MemRef_A[*];
-; CHECK:   i32 MemRef_x; [BasePtrOrigin: MemRef_A]
 ; CHECK:   i32 MemRef_y__phi;
+; CHECK:   i32 MemRef_x; [BasePtrOrigin: MemRef_A]
 ; CHECK: }
 ;
 ; CHECK: Arrays (Bounds as pw_affs) {
 ; CHECK:   i32 MemRef_A[*];
-; CHECK:   i32 MemRef_x; [BasePtrOrigin: MemRef_A]
 ; CHECK:   i32 MemRef_y__phi;
+; CHECK:   i32 MemRef_x; [BasePtrOrigin: MemRef_A]
 ; CHECK: }
 ;
 ; CHECK:      Stmt_bb2__TO__bb7
 ; CHECK:            Domain :=
 ; CHECK:                { Stmt_bb2__TO__bb7[i0] :
 ; CHECK-DAG:               i0 >= 0
 ; CHECK-DAG:             and
 ; CHECK-DAG:               i0 <= 1023
 ; CHECK:                };
 ; CHECK:            Schedule :=
 ; CHECK:                { Stmt_bb2__TO__bb7[i0] -> [i0, 0] };
 ; CHECK:            ReadAccess := [Reduction Type: NONE] [Scalar: 0]
 ; CHECK:                { Stmt_bb2__TO__bb7[i0] -> MemRef_A[i0] };
 ; CHECK:            MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
-; CHECK:                { Stmt_bb2__TO__bb7[i0] -> MemRef_x[] };
-; CHECK:            MayWriteAccess := [Reduction Type: NONE] [Scalar: 1]
 ; CHECK:                { Stmt_bb2__TO__bb7[i0] -> MemRef_y__phi[] };
 ; CHECK:            MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
-; CHECK:                { Stmt_bb2__TO__bb7[i0] -> MemRef_y__phi[] };
+; CHECK:                { Stmt_bb2__TO__bb7[i0] -> MemRef_x[] };
 ; CHECK:      Stmt_bb7
 ; CHECK:            Domain :=
 ; CHECK:                { Stmt_bb7[i0] :
 ; CHECK-DAG:               i0 >= 0
 ; CHECK-DAG:             and
 ; CHECK-DAG:               i0 <= 1023
 ; CHECK:                };
 ; CHECK:            Schedule :=
 ; CHECK:                { Stmt_bb7[i0] -> [i0, 1] };
 ; CHECK:            ReadAccess := [Reduction Type: NONE] [Scalar: 1]
-; CHECK:                { Stmt_bb7[i0] -> MemRef_x[] };
-; CHECK:            ReadAccess := [Reduction Type: NONE] [Scalar: 1]
 ; CHECK:                { Stmt_bb7[i0] -> MemRef_y__phi[] };
+; CHECK:            ReadAccess := [Reduction Type: NONE] [Scalar: 1]
+; CHECK:                { Stmt_bb7[i0] -> MemRef_x[] };
 ; CHECK:            MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 0]
 ; CHECK:                { Stmt_bb7[i0] -> MemRef_A[i0] };
 ;
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 
 define void @f(i32* %A, i32 %b) {
 bb:
   br label %bb1

test/ScopInfo/out-of-scop-use-in-region-entry-phi-node.ll

+
 ; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s
 
 ; CHECK: MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
 ; CHECK-NEXT: [p_0] -> { Stmt_bb3[] -> MemRef_tmp5[] };
 
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 
 define void @hoge() {

test/ScopInfo/phi_condition_modeling_2.ll

 ; CHECK:            ReadAccess := [Reduction Type: NONE] [Scalar: 1]
 ; CHECK:                [N, c] -> { Stmt_bb8[i0] -> MemRef_tmp_0__phi[] };
 ; CHECK-NOT: Access
 ; CHECK:            MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
 ; CHECK:                [N, c] -> { Stmt_bb8[i0] -> MemRef_tmp_0[] };
 ; CHECK-NOT: Access
 ; CHECK-LABEL:      Stmt_bb8b
 ; CHECK-NOT: Access
-; CHECK:            ReadAccess := [Reduction Type: NONE] [Scalar: 1]
-; CHECK:                [N, c] -> { Stmt_bb8b[i0] -> MemRef_tmp_0[] };
-; CHECK-NOT: Access
 ; CHECK:            MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 0]
 ; CHECK:                [N, c] -> { Stmt_bb8b[i0] -> MemRef_A[i0] };
 ; CHECK-NOT: Access
+; CHECK:            ReadAccess := [Reduction Type: NONE] [Scalar: 1]
+; CHECK:                [N, c] -> { Stmt_bb8b[i0] -> MemRef_tmp_0[] };
+; CHECK-NOT: Access
 ; CHECK:    }
 
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 
 define void @f(i32* %A, i32 %c, i32 %N) {
 bb:
   %tmp = sext i32 %N to i64
   %tmp1 = sext i32 %c to i64

test/ScopInfo/phi_loop_carried_float.ll

 ; CHECK:                  [N] -> { Stmt_bb1[i0] -> MemRef_tmp_0[] };
 ; CHECK-NOT: Access
 ; CHECK-LABEL:   Stmt_bb4
 ; CHECK-NOT: Access
 ; CHECK:              MustWriteAccess :=  [Reduction Type: NONE]
 ; CHECK:                  [N] -> { Stmt_bb4[i0] -> MemRef_tmp_0__phi[] };
 ; CHECK-NOT: Access
 ; CHECK:              ReadAccess := [Reduction Type: NONE]
-; CHECK:                  [N] -> { Stmt_bb4[i0] -> MemRef_tmp_0[] };
+; CHECK:                  [N] -> { Stmt_bb4[i0] -> MemRef_A[i0] };
 ; CHECK-NOT: Access
 ; CHECK:              ReadAccess := [Reduction Type: NONE]
-; CHECK:                  [N] -> { Stmt_bb4[i0] -> MemRef_A[i0] };
+; CHECK:                  [N] -> { Stmt_bb4[i0] -> MemRef_tmp_0[] };
 ; CHECK-NOT: Access
 ; CHECK:      }
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 
 define void @f(float* %A, i32 %N) {
 bb:
   %tmp = sext i32 %N to i64
   br label %bb1

test/ScopInfo/phi_scalar_simple_1.ll

 for.cond:                                         ; preds = %for.inc4, %entry
 ; CHECK-LABEL: Stmt_for_cond
 ; CHECK:       ReadAccess := [Reduction Type: NONE] [Scalar: 1]
 ; CHECK:           [N] -> { Stmt_for_cond[i0] -> MemRef_x_addr_0__phi[] };
 ; CHECK-NOT: Access
 ; CHECK:       MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
 ; CHECK:           [N] -> { Stmt_for_cond[i0] -> MemRef_x_addr_0[] };
 ; CHECK-NOT: Access
-; CHECK:       MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
-; CHECK:           [N] -> { Stmt_for_cond[i0] -> MemRef_x_addr_0[] };
-; CHECK-NOT: Access
   %indvars.iv = phi i64 [ %indvars.iv.next, %for.inc4 ], [ 1, %entry ]
   %x.addr.0 = phi i32 [ %x, %entry ], [ %x.addr.1.lcssa, %for.inc4 ]
   %cmp = icmp slt i64 %indvars.iv, %tmp
   br i1 %cmp, label %for.body, label %for.end6
 
 for.body:                                         ; preds = %for.cond
 ; CHECK-LABEL: Stmt_for_body
 ; CHECK:       ReadAccess :=  [Reduction Type: NONE] [Scalar: 1]

 for.body3:                                        ; preds = %for.cond1
   br label %for.inc
 
 for.inc:                                          ; preds = %for.body3
 ; CHECK-LABEL: Stmt_for_inc
 ; CHECK:       MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
 ; CHECK:           [N] -> { Stmt_for_inc[i0, i1] -> MemRef_x_addr_1__phi[] };
 ; CHECK-NOT: Access
-; CHECK:       ReadAccess := [Reduction Type: NONE] [Scalar: 1]
-; CHECK:           [N] -> { Stmt_for_inc[i0, i1] -> MemRef_x_addr_1[] };
-; CHECK-NOT: Access
 ; CHECK:       ReadAccess := [Reduction Type: NONE] [Scalar: 0]
 ; CHECK:           [N] -> { Stmt_for_inc[i0, i1] -> MemRef_A[1 + i0] };
 ; CHECK-NOT: Access
+; CHECK:       ReadAccess := [Reduction Type: NONE] [Scalar: 1]
+; CHECK:           [N] -> { Stmt_for_inc[i0, i1] -> MemRef_x_addr_1[] };
+; CHECK-NOT: Access
   %arrayidx = getelementptr inbounds i32, i32* %A, i64 %indvars.iv
   %tmp1 = load i32, i32* %arrayidx, align 4
   %add = add nsw i32 %x.addr.1, %tmp1
   %inc = add nsw i32 %j.0, 1
   br label %for.cond1
 
 for.end:                                          ; preds = %for.cond1
 ; CHECK-LABEL: Stmt_for_end

test/ScopInfo/phi_scalar_simple_2.ll

 ; CHECK:         [N, c] -> { Stmt_for_cond[i0] -> MemRef_x_addr_0__phi[] };
 ; CHECK-NOT: Access
 ; CHECK:     MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
 ; CHECK:         [N, c] -> { Stmt_for_cond[i0] -> MemRef_x_addr_0[] };
 ; CHECK-NOT: Access
 ; CHECK:     MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 0]
 ; CHECK:         [N, c] -> { Stmt_for_cond[i0] -> MemRef_A[i0] };
 ; CHECK-NOT: Access
-; CHECK:     MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
-; CHECK:         [N, c] -> { Stmt_for_cond[i0] -> MemRef_x_addr_0[] };
-; CHECK-NOT: Access
   %indvars.iv = phi i64 [ %indvars.iv.next, %for.inc5 ], [ 0, %entry ]
   %x.addr.0 = phi i32 [ %x, %entry ], [ %x.addr.1, %for.inc5 ]
   %arrayidx2 = getelementptr inbounds i32, i32* %A, i64 %indvars.iv
   store i32 %x.addr.0, i32* %arrayidx2
   %cmp = icmp slt i64 %indvars.iv, %tmp
   br i1 %cmp, label %for.body, label %for.end7
 
 for.body:                                         ; preds = %for.cond

 ; CHECK-LABEL: Stmt_for_cond1
 ; CHECK-NOT: Access
 ; CHECK:     MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
 ; CHECK:         [N, c] -> { Stmt_for_cond1[i0, i1] -> MemRef_x_addr_1[] };
 ; CHECK-NOT: Access
 ; CHECK:     ReadAccess := [Reduction Type: NONE] [Scalar: 1]
 ; CHECK:         [N, c] -> { Stmt_for_cond1[i0, i1] -> MemRef_x_addr_1__phi[] };
 ; CHECK-NOT: Access
-; CHECK:     MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
-; CHECK:         [N, c] -> { Stmt_for_cond1[i0, i1] -> MemRef_x_addr_1[] };
-; CHECK-NOT: Access
-; CHECK:     MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
-; CHECK:         [N, c] -> { Stmt_for_cond1[i0, i1] -> MemRef_x_addr_1[] };
-; CHECK-NOT: Access
   %x.addr.1 = phi i32 [ %x.addr.0, %for.body ], [ %x.addr.2, %for.inc ]
   %j.0 = phi i32 [ 0, %for.body ], [ %inc, %for.inc ]
   %exitcond = icmp ne i32 %j.0, %N
   br i1 %exitcond, label %for.body3, label %for.end
 
 for.body3:                                        ; preds = %for.cond1
 ; CHECK-LABEL: Stmt_for_body3
 ; CHECK-NOT: Access
 ; CHECK:     ReadAccess := [Reduction Type: NONE] [Scalar: 1]
 ; CHECK:         [N, c] -> { Stmt_for_body3[i0, i1] -> MemRef_x_addr_1[] };
 ; CHECK-NOT: Access
 ; CHECK:     MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
 ; CHECK:         [N, c] -> { Stmt_for_body3[i0, i1] -> MemRef_x_addr_2__phi[] };
 ; CHECK-NOT: Access
   %cmp4 = icmp slt i64 %indvars.iv, %tmp1
   br i1 %cmp4, label %if.then, label %if.end
 
 if.then:                                          ; preds = %for.body3
 ; CHECK-LABEL: Stmt_if_then
 ; CHECK-NOT: Access
-; CHECK:     ReadAccess := [Reduction Type: NONE] [Scalar: 1]
-; CHECK:         [N, c] -> { Stmt_if_then[i0, i1] -> MemRef_x_addr_1[] };
-; CHECK-NOT: Access
 ; CHECK:     ReadAccess := [Reduction Type: NONE] [Scalar: 0]
 ; CHECK:         [N, c] -> { Stmt_if_then[i0, i1] -> MemRef_A[i0] };
 ; CHECK-NOT: Access
+; CHECK:     ReadAccess := [Reduction Type: NONE] [Scalar: 1]
+; CHECK:         [N, c] -> { Stmt_if_then[i0, i1] -> MemRef_x_addr_1[] };
+; CHECK-NOT: Access
 ; CHECK:     MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
 ; CHECK:         [N, c] -> { Stmt_if_then[i0, i1] -> MemRef_x_addr_2__phi[] };
 ; CHECK-NOT: Access
   %arrayidx = getelementptr inbounds i32, i32* %A, i64 %indvars.iv
   %tmp2 = load i32, i32* %arrayidx, align 4
   %add = add nsw i32 %x.addr.1, %tmp2
   br label %if.end
 

test/ScopInfo/pointer-used-as-base-pointer-and-scalar-read.ll

 ; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s
 
 ; In this test case we pass a pointer %A into a PHI node and also use this
 ; pointer as base pointer of an array store. As a result, we get both scalar
 ; and array memory accesses to A[] and A[0].
 
 ; CHECK: Arrays {
 ; CHECK:     float MemRef_A[*]; // Element size 4
-; CHECK:     float* MemRef_A; // Element size 8
 ; CHECK:     float* MemRef_x__phi; // Element size 8
-; CHECK:     float* MemRef_B; // Element size 8
 ; CHECK:     float* MemRef_C[*]; // Element size 8
 ; CHECK: }
 ; CHECK: Arrays (Bounds as pw_affs) {
 ; CHECK:     float MemRef_A[*]; // Element size 4
-; CHECK:     float* MemRef_A; // Element size 8
 ; CHECK:     float* MemRef_x__phi; // Element size 8
-; CHECK:     float* MemRef_B; // Element size 8
 ; CHECK:     float* MemRef_C[*]; // Element size 8
 ; CHECK: }
 ; CHECK: Alias Groups (0):
 ; CHECK:     n/a
 ; CHECK: Statements {
 ; CHECK:   Stmt_then
 ; CHECK:         Domain :=
 ; CHECK:             [p] -> { Stmt_then[i0] : p = 32 and i0 <= 999 and i0 >= 0 };
 ; CHECK:         Schedule :=
 ; CHECK:             [p] -> { Stmt_then[i0] -> [i0, 1] };
 ; CHECK:         MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 0]
 ; CHECK:             [p] -> { Stmt_then[i0] -> MemRef_A[0] };
-; CHECK:         ReadAccess :=       [Reduction Type: NONE] [Scalar: 1]
-; CHECK:             [p] -> { Stmt_then[i0] -> MemRef_A[] };
 ; CHECK:         MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
 ; CHECK:             [p] -> { Stmt_then[i0] -> MemRef_x__phi[] };
 ; CHECK:   Stmt_else
 ; CHECK:         Domain :=
 ; CHECK:             [p] -> { Stmt_else[i0] : (p >= 33 and i0 <= 999 and i0 >= 0) or (p <= 31 and i0 <= 999 and i0 >= 0) };
 ; CHECK:         Schedule :=
 ; CHECK:             [p] -> { Stmt_else[i0] -> [i0, 0] : p >= 33 or p <= 31 };
 ; CHECK:         MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 0]
 ; CHECK:             [p] -> { Stmt_else[i0] -> MemRef_A[0] };
-; CHECK:         ReadAccess :=       [Reduction Type: NONE] [Scalar: 1]
-; CHECK:             [p] -> { Stmt_else[i0] -> MemRef_B[] };
 ; CHECK:         MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
 ; CHECK:             [p] -> { Stmt_else[i0] -> MemRef_x__phi[] };
 ; CHECK:   Stmt_bb8
 ; CHECK:         Domain :=
 ; CHECK:             [p] -> { Stmt_bb8[i0] : (p >= 33 and i0 <= 999 and i0 >= 0) or (p <= 32 and i0 <= 999 and i0 >= 0) };
 ; CHECK:         Schedule :=
 ; CHECK:             [p] -> { Stmt_bb8[i0] -> [i0, 2] };
 ; CHECK:         ReadAccess :=       [Reduction Type: NONE] [Scalar: 1]

test/ScopInfo/read-only-scalar-used-in-phi.ll

 ; CHECK:       Domain :=
 ; CHECK:           { Stmt_next[] };
 ; CHECK:       Schedule :=
 ; CHECK:           { Stmt_next[] -> [0, 0] };
 ; CHECK:       ReadAccess :=       [Reduction Type: NONE] [Scalar: 1]
 ; CHECK:           { Stmt_next[] -> MemRef_sum[] };
 ; CHECK:       MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
 ; CHECK:           { Stmt_next[] -> MemRef_phisum__phi[] };
+; CHECK:       MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
+; CHECK:           { Stmt_next[] -> MemRef_phisummerge[] };
 ; CHECK: Stmt_bb1
 ; CHECK:       Domain :=
 ; CHECK:           { Stmt_bb1[i0] : i0 <= 100 and i0 >= 0 };
 ; CHECK:       Schedule :=
 ; CHECK:           { Stmt_bb1[i0] -> [1, i0] };
 ; CHECK:       MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
 ; CHECK:           { Stmt_bb1[i0] -> MemRef_phisum__phi[] };
 ; CHECK:       ReadAccess :=       [Reduction Type: NONE] [Scalar: 1]
 ; CHECK:           { Stmt_bb1[i0] -> MemRef_phisum__phi[] };
 ; CHECK:       ReadAccess :=       [Reduction Type: NONE] [Scalar: 0]
 ; CHECK:           { Stmt_bb1[i0] -> MemRef_A[i0] };
+; CHECK:       MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
+; CHECK:           { Stmt_bb1[i0] -> MemRef_phisummerge[] };
 
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 
 define float @foo(float %sum, float* %A) {
 bb:
   br label %next
 
 next:

test/ScopInfo/same-base-address-scalar-and-array.ll

 ; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s
 ;
 ; Verify we introduce two ScopArrayInfo objects (or virtual arrays) for the %out variable
 ; as it is used as a memory base pointer (%0) but also as a scalar (%out.addr.0.lcssa).
 ;
 ; CHECK:         Arrays {
-; CHECK-NEXT:        float* MemRef_out; // Element size 8
 ; CHECK-NEXT:        float* MemRef_out_addr_0_lcssa; // Element size 8
 ; CHECK-NEXT:        float MemRef_out[*]; // Element size 4
 ; CHECK-NEXT:    }
 ;
 target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
 
 ; Function Attrs: nounwind ssp uwtable
 define void @ff_celp_lp_synthesis_filterf(float* %out) #0 {

test/ScopInfo/scalar.ll

 ; CHECK:           [N] -> { Stmt_S1[i0] -> MemRef_a[i0] };
 ; CHECK:       MustWriteAccess :=
 ; CHECK:           [N] -> { Stmt_S1[i0] -> MemRef_val[] };
 ; CHECK: Stmt_S2
 ; CHECK:       Domain :=
 ; CHECK:           [N] -> { Stmt_S2[i0] : i0 >= 0 and i0 <= -1 + N };
 ; CHECK:       Schedule :=
 ; CHECK:           [N] -> { Stmt_S2[i0] -> [i0, 1] };
-; CHECK:       ReadAccess :=
-; CHECK:           [N] -> { Stmt_S2[i0] -> MemRef_val[] };
 ; CHECK:       MustWriteAccess :=
 ; CHECK:           [N] -> { Stmt_S2[i0] -> MemRef_a[i0] };
+; CHECK:       ReadAccess :=
+; CHECK:           [N] -> { Stmt_S2[i0] -> MemRef_val[] };

test/ScopInfo/tempscop-printing.ll

; CHECK-NOT:      Stmt_entry_next
   %init = load i64, i64* %init_ptr
   br label %for.j
 
 for.j:
 ; CHECK:      Stmt_for_j
   %indvar.j = phi i64 [ 0, %entry.next ], [ %indvar.j.next, %for.j ]
   %scevgep = getelementptr i64, i64* %A, i64 %indvar.j
   store i64 %init, i64* %scevgep
-; CHECK:          ReadAccess :=       [Reduction Type: NONE] [Scalar: 1]
-; CHECK-NEXT:         [N] -> { Stmt_for_j[i0, i1] -> MemRef_init[] };
 ; CHECK:          MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 0]
 ; CHECK-NEXT:         [N] -> { Stmt_for_j[i0, i1] -> MemRef_A[i1] };
+; CHECK:          ReadAccess :=       [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:         [N] -> { Stmt_for_j[i0, i1] -> MemRef_init[] };
   %indvar.j.next = add nsw i64 %indvar.j, 1
   %exitcond.j = icmp eq i64 %indvar.j.next, %N
   br i1 %exitcond.j, label %for.i.end, label %for.j
 
 for.i.end:
   %exitcond.i = icmp eq i64 %indvar.i.next, %N
   br i1 %exitcond.i, label %return, label %for.i
 
 return:
   ret void
 }