[GSoC 2016] [Polly] [WIP] Perform copying to created arrays according to the packing transformation

[gareevroman]

Summary

This is the fourth patch to apply the BLIS matmul optimization pattern on matmul kernels (http://www.cs.utexas.edu/users/flame/pubs/TOMS-BLIS-Analytical.pdf). BLIS implements gemm as three nested loops around a macro-kernel, plus two packing routines. The macro-kernel is implemented in terms of two additional loops around a micro-kernel. The micro-kernel is a loop around a rank-1 (i.e., outer product) update. In this change we perform copying to created arrays, which is the last step to implement the packing transformation.

[gareevroman]

In this draft of the patch copy statements are represented as Scop statements whose values of BB and R fields are equal to nullptr. These statements have only two memory accesses. The first one represents reading from an array that should be packed. The second one represents writing to a created array. What do you think about it?

The current implementation of the idea have several drawbacks. I would be grateful for your comments and ideas about them.

One of the drawbacks is manual deletion of copy statements in IslNodeBuilder::generateCopyStmt. We could, for example, store mapping between packed memory accesses and copy statements, to be able to delete all created copy statements in a destructor of the Stmt class.

Another drawback is a location where the corresponding IR is generated. Should we generate it in BlockGenerators? Probably it requires addition of a new class (e.g. CopyGenerator). At the moment the corresponding IR is generated in IslNodeBuilder::generateCopyStmt.

I have one more question related to generation of the corresponding IR. As far as I understand, to generate it, we should create one load and one store intrusion. In the case of the load instruction, we could use IslExprBuilder::create. However, to generate the store instruction, we should probably be able to call IslExprBuilder::createAccessAddress that is a private member of the IslExprBuilder class. Maybe we should make it a public member (this approach is used in the patch).

The last question is related to utilization of extension nodes. I had to comment out the calls of ScheduleTreeOptimizer::isProfitableSchedule and isl_schedule_get_map, because otherwise I get the following error:

"/home/roman/Documents/polly/llvm/tools/polly/lib/External/isl/isl_schedule_tree.c:1820: cannot construct subtree schedule of tree with extension nodes"

How to apply isl_schedule_get_map in case a schedule tree has extension nodes?

[Meinersbur]

include/polly/CodeGen/IslExprBuilder.h

169 ↗

(On Diff #67148)

When becoming part of the public interface, please add doucmentation.

include/polly/CodeGen/IslNodeBuilder.h

353–354 ↗

(On Diff #67148)

It is not clear from where to where something is copied.

I'd expect parameters for specifying the source and target locations, the subrange to be copied and a mapping between the index in the source to the index of target.

lib/Analysis/ScopInfo.cpp

1443–1477 ↗

(On Diff #67148)

Please don't do significant work in the constructor. Constructors are for initializing members. Such code make reuse of that functionality from other parts more difficult and calling virtual member functions may not work as expected.

1468 ↗

(On Diff #67148)

Both memory accesses seem to read and write from the same array at the same index. This is not intended, is it?

lib/CodeGen/IslNodeBuilder.cpp

791 ↗

(On Diff #67148)

Why does this delete Stmt?

810 ↗

(On Diff #67148)

Would it be possible to handle the copy statements as special case of the BlockGenerator, just with BB set to nullptr?

[gareevroman]

Hi Michael,

thanks for the comments!

include/polly/CodeGen/IslExprBuilder.h

169 ↗

(On Diff #67148)

OK. However, I'm not sure whether it's fine to make it a public member.

include/polly/CodeGen/IslNodeBuilder.h

353–354 ↗

(On Diff #67148)

I think that we could use createCopyStmt for this purpose. It accepts an extension map of an extension node that helps to specify the subrange to be copied and a mapping between the index in the source to the index of target. Another parameter is a memory access whose original and new access relations specify the source and target locations, respectively. What do you think about it?

IslNodeBuilder::generateCopyStmt is used to generate IR that corresponds to the body of a copy statement. If we handle the copy statements as special case of the BlockGenerator, we could probably remove the function.

lib/Analysis/ScopInfo.cpp

1443–1477 ↗

(On Diff #67148)

OK.

1468 ↗

(On Diff #67148)

As far as I understand, they read and write from different arrays, if ScopArrayInfo objects accessed via the original and new access relations represent different BasePtrs. I'll add assert that checks it.

lib/CodeGen/IslNodeBuilder.cpp

791 ↗

(On Diff #67148)

As far as I understand, to avoid this manual deletion of copy statements, they should be stored in the Stmts, which is a std::list<ScopStmt> that contains all statements of the SCoP and filled using Scop::addScopStmt. The destructor of the SCoP clears the list and hence deletes the statements.

However, Scop::addScopStmt only creates a new SCoP statement for either a basic block or a region. Should we rewrite Scop::addScopStmt to be able to create a copy statement for a memory access? If we decide to do it, we should probably also have to make it public, because we'll call it in ScheduleTreeOptimizer.

810 ↗

(On Diff #67148)

I think that it's possible. Should we handle this case in BlockGenerator::copyStmt?

[Meinersbur]

include/polly/CodeGen/IslExprBuilder.h

169 ↗

(On Diff #67148)

OK with me (we don't really have a stable public interface at this level).

lib/Analysis/ScopInfo.cpp

1468 ↗

(On Diff #67148)

OK, I think I understand better now. It first create a no-op that reads and writes from/to the same location (MemA->getBaseAddr()/Subscripts) and only later the accesses are changed via setNewAccessRelation(). One two MemA->getOriginalAccessRelation(), the other to MemA->getAccessRelation().

I find this confusing, they are even using the same local variable NewAccessRelation for different accesses. I'd prefer to pass the source/target relation explicitly than taking from MemA. There is also no need to first initialize the MemoryAccesses using with an arbitrary access relation that is never used. You can add a constructor to initialize the AccessRelation with the right value from the beginning.

AFAIU memory accesses should be added using emplace_back on the access list returned by scop->getOrCreateAccessFunctions(). Since we dont have a BB, passing nullptr should be OK as well. Otherwise we are leaking memory.

lib/CodeGen/IslNodeBuilder.cpp

791 ↗

(On Diff #67148)

OK, you might want to change addScopStmt to something like

ScopStmt* Scop::addScopStmt(BasicBlock *BB, Region *R) {
  if (BB) {
    Stmts.emplace_back(*this, *BB);
    auto *Stmt = &Stmts.back();
    StmtMap[BB] = Stmt;
    return Stmt;
  } else if (R) {
    assert(R && "Either basic block or a region expected.");
    Stmts.emplace_back(*this, *R);
    auto *Stmt = &Stmts.back();
    for (BasicBlock *BB : R->blocks())
      StmtMap[BB] = Stmt;
    return Stmt;
  }

  Stmts.emplace_back(*this, (BasicBlock*)nullptr);
  return Stmts.back(); 
}

810 ↗

(On Diff #67148)

Yes, I think it would be preferable to be able to share code for generating index expressions (generateLocationAccessed)

lib/Transform/ScheduleOptimizer.cpp

651 ↗

(On Diff #67148)

@p DimNum (Renaming to just Dim could be useful to avoid confusion with "Number of Dimensions")

681 ↗

(On Diff #67148)

@brief

690 ↗

(On Diff #67148)

@p SecondOutputDimBound

[gareevroman]

Hi Michael,

thank you for the comments! I've tried to address them in a new version of the patch.

[gareevroman]

lib/Analysis/ScopInfo.cpp

1465–1499 ↗

(On Diff #68212)

I've modified constructors of ScopStmt and MemoryAccess in a new version of the patch. If you think that significant work is done in them, I'll try to factor out the code.

1490 ↗

(On Diff #68212)

OK, I think I understand better now. It first create a no-op that reads and writes from/to the same location (MemA->getBaseAddr()/Subscripts) and only later the accesses are changed via setNewAccessRelation(). One two MemA->getOriginalAccessRelation(), the other to MemA->getAccessRelation().

I find this confusing, they are even using the same local variable NewAccessRelation for different accesses. I'd prefer to pass the source/target relation explicitly than taking from MemA. There is also no need to first initialize the MemoryAccesses using with an arbitrary access relation that is never used. You can add a constructor to initialize the AccessRelation with the right value from the beginning.

I've tried to implement it. However, at the moment copy statements require domain of a corresponding statement that contains a memory access, which is copied. I'll try understand how to avoid it.

AFAIU memory accesses should be added using emplace_back on the access list returned by scop->getOrCreateAccessFunctions(). Since we dont have a BB, passing nullptr should be OK as well. Otherwise we are leaking memory.

Should we make getOrCreateAccessFunctions public in this case?

lib/CodeGen/IslNodeBuilder.cpp

783 ↗

(On Diff #68212)

I'm afraid that it's not possible to implement such a change, because there is no a constructor for a ScopStmt, that accepts pointers. Maybe I'm missing something.

I've tried to use overloaded addScopStmt of the following form

ScopStmt* Scop::addScopStmt(__isl_take isl_map *SourceRel, __isl_take isl_map *TargetRel, __isl_take isl_set *Domain) {
  Stmts.emplace_back(*this, SourceRel, TargetRel, Domain);
  return Stmts.back(); 
}

In case of arrays created by Polly, it causes an error, because ScopAnnotator::buildAliasScopes uses names of BasePtrs in the following line:

MDString::get(Ctx, (AliasScopeStr + BasePtr->getName()).str().c_str()));

However, BasePtrs aren't known at the moment of calling of the ScopAnnotator::buildAliasScopes, because at this moment they aren't allocated.

I haven't come up with a solution yet.

801 ↗

(On Diff #68212)

Sorry, I don't understand how to share generateLocationAccessed. If I'm not mistaken, in case of copy statements, basic blocks are empty and we can't call, for example, getPointerOperand. For the same reason I don't understand how generateLocationAccessed can be called in case of copy statements.

I thought that we could probably rewrite BlockGenerator::copyStmt and get something like this:

void BlockGenerator::copyStmt(ScopStmt &Stmt, LoopToScevMapT &LTS,	                              isl_id_to_ast_expr *NewAccesses) {

if (Stmt.isBlockStmt()) {
  ValueMapT BBMap;

  BasicBlock *BB = Stmt.getBasicBlock();
  copyBB(Stmt, BB, BBMap, LTS, NewAccesses);
  removeDeadInstructions(BB, BBMap);
} else {
  // handle a copy statement
}
}

[grosser]

Hi Roman,

I went once more over the patch. The overall direction looks good, but I have a couple of changes to suggest. Also, i believe we should separate the extensions to general Polly from your matmul specific changes. Specifically, I suggest to pull out two patches:

1. Simplify AccFuncMap to vector<> AccessFunctions

2. Introduction of CopyStmts (via jscop)

plus the final gemm patch. I know this adds some additional work, but as I said earlier I prefer to have clean and thought through patches, rather than rushing to push things in. Obviously, for your GSoC evaluation I will take into account that you spent additional time on cleaning and improving the general Polly infrastructure.

include/polly/CodeGen/IslExprBuilder.h

169 ↗

(On Diff #68212)

@brief Create LLVM-IR that computes the memory location of an access expression.

For a given isl_ast_expr[ession] of type isl_ast_op_access this function creates IR
that computes the address of the access expression refers to.

include/polly/CodeGen/IslNodeBuilder.h

382 ↗

(On Diff #68212)

@brief Create code for a copy statement

A copy statement is expected to have one read memory access and one write memory access (in this very order). Data is loaded from the location described by the read memory access and written to the location described by the write memory access. @p NewAccesses contains for each access the isl ast expression that describes the location accessed.

lib/Analysis/ScopInfo.cpp

1469 ↗

(On Diff #68212)

This will result in both copy statements to have the very same name. This is probably not what we want. Can we add a "_<id>" suffix that distinguishes multiple copy statements? (At best we keep track of the number of copy statements created for a scop and use this as an index.

1473 ↗

(On Diff #68212)

Passing 'nullptr' here means that we will not be able to distinguish accesses from different copy statements. Interestingly, it seems we are not even using this facility any more. getAccessFunctions() seems to be dead code and I also don't see the 'BB' argument of getOrCreateAccessFunctions() to be used.

The cleanest solution would probably prepare a cleanup patch that deletes getAccessFunctions and that transforms AccFuncMap into a std::vector<> AccessFunctions. This would remove avoid the need to pass a nullptr here, which really seems to be an unnecessary workaround.

lib/CodeGen/IslNodeBuilder.cpp

783 ↗

(On Diff #68212)

Maybe avoid the loop and just assume load first and store second. We will always generate the copyStmt like this, so there is no need to add complexity to be more generic. Please also add asserts that check that both accesses exist, that they use the same data type and that both accesses are array accesses for now.

801 ↗

(On Diff #68212)

I am fine with the solution you choose for now, but we may want to think later if we can structure this a little nicer.

lib/Transform/ScheduleOptimizer.cpp

716 ↗

(On Diff #68212)

where

1202 ↗

(On Diff #68212)

Ah, there ist the problem that extension nodes cannot be handled. Commenting this out is probably the worst choice. I would suggest to change isProfitableSchedule to take a ScheduleTree, and as a first condition in isProfitableSchedule check if the schedule contains extension nodes. In this case just assume its profitable (as we apparently did a larger change to make this happen).

test/Isl/CodeGen/MemAccess/mat_mul_pattern_data_layout.ll

19 ↗

(On Diff #68212)

Uh, I really dislike more and more the fact that your schedule transformation is tested here. Can we just add a flag to ScheduleOptimizer which dumps the new scop and check for the new scop containing the right statements? As well as the -polly-ast generating the right code?

Isl/CodeGen/MemAccess should really just test that we generate correct code for newly added memory accesses added through a jscop input.

[gareevroman]

Hi Tobias,

thank you for the comments! I'll try to address them.

test/Isl/CodeGen/MemAccess/mat_mul_pattern_data_layout.ll

19 ↗

(On Diff #68212)

Uh, I really dislike more and more the fact that your schedule transformation is tested here. Can we just add a flag to ScheduleOptimizer which dumps the new scop and check for the new scop containing the right statements? As well as the -polly-ast generating the right code?

I've tried to implement this in

Isl/CodeGen/MemAccess should really just test that we generate correct code for newly added memory accesses added through a jscop input.

It also causes the following error error:

/home/roman/Documents/polly/llvm/tools/polly/lib/External/isl/isl_schedule_tree.c:1820: cannot construct subtree schedule of tree with extension nodes

because S.getSchedule() called from IslAstInfo::printScop contain isl_schedule_get_map. Thank you for the comment. I'll try to understand how to avoid the issue.

[gareevroman]

test/Isl/CodeGen/MemAccess/mat_mul_pattern_data_layout.ll

19 ↗

(On Diff #68212)

I've tried to implement this in

I've tried to implement this in https://reviews.llvm.org/D23740.

[gareevroman]

This is a new version of the patch updated according to the comments.

Introduction of CopyStmts (via jscop)

Sorry, I haven't understood how to do it properly yet.

To import a copy statement, we could possibly specify its extension map and try to find its position in the schedule tree and insert it. To be able to import an exported copy statement, we should probably store its extension map. Maybe it is wrong way.

There is also a problem related to exporting CopyStmts. We use ScopStmt::getScheduleStr() to export a schedule of a statement. It calls ScopStmt::getSchedule that calls Scop::getSchedule, which calls isl_schedule_get_map that causes:

/home/roman/Documents/polly/llvm/tools/polly/lib/External/isl/isl_schedule_tree.c:1820: cannot construct subtree schedule of tree with extension nodes

For the same reason we can't use ScopInfo's to check the work of the IslScheduleOptimizer pass at the polyhedral level in this case (that's why I temporary use the previous variant of the test)

We could make ScopStmt::getScheduleStr() return an empty string in case a schedule tree has extension nodes. It doesn't solve a problem related to export of CopyStmts. However, it could probably help to build a test case.

lib/Transform/ScheduleOptimizer.cpp

1211 ↗

(On Diff #68816)

Could you please advise me how to check if the schedule contains extension nodes? Should we traverse the whole schedule tree and check types of every node?

[grosser]

Hi Roman,

thanks for this update:

In D23260#521804, @gareevroman wrote:

This is a new version of the patch updated according to the comments.

Introduction of CopyStmts (via jscop)

Sorry, I haven't understood how to do it properly yet.

To import a copy statement, we could possibly specify its extension map and try to find its position in the schedule tree and insert it. To be able to import an exported copy statement, we should probably store its extension map. Maybe it is wrong way.

Right. Extension nodes are complicated. In the end, we would probably need to import a full schedule tree to describe their positions correctly. However, for the first tests it's enough to just assume all new statements are inserted at the very top of the schedule tree. Your actual transformation will insert them somewhere else, but that's how it is.

There is also a problem related to exporting CopyStmts. We use ScopStmt::getScheduleStr() to export a schedule of a statement. It calls ScopStmt::getSchedule that calls Scop::getSchedule, which calls isl_schedule_get_map that causes:

/home/roman/Documents/polly/llvm/tools/polly/lib/External/isl/isl_schedule_tree.c:1820: cannot construct subtree schedule of tree with extension nodes

For the same reason we can't use ScopInfo's to check the work of the IslScheduleOptimizer pass at the polyhedral level in this case (that's why I temporary use the previous variant of the test)

We could make ScopStmt::getScheduleStr() return an empty string in case a schedule tree has extension nodes. It doesn't solve a problem related to export of CopyStmts. However, it could probably help to build a test case.

Yes, we can have it return an empty string. There are a couple of cases where a schedule tree with extension nodes cannot be moveled with a flat schedule. We probably need to handle them conservatively. (IslAst also uses getSchedule. In this case, we can probably replace it with getScheduleTree)

Best,
Tobias

include/polly/CodeGen/IslExprBuilder.h

173 ↗

(On Diff #68816)

Drop the 'of'

175 ↗

(On Diff #68816)

that has -> of

lib/Transform/ScheduleOptimizer.cpp

1211 ↗

(On Diff #68816)

Yes, this is probably the only choice. isl has some functions that allow to traverse the schedule tree. You could use these.

[gareevroman]

In D23260#521852, @grosser wrote:

Hi Roman,

thanks for this update:

Hi Tobias,

thank you for the comments!

In D23260#521804, @gareevroman wrote:

This is a new version of the patch updated according to the comments.

Introduction of CopyStmts (via jscop)

Sorry, I haven't understood how to do it properly yet.

To import a copy statement, we could possibly specify its extension map and try to find its position in the schedule tree and insert it. To be able to import an exported copy statement, we should probably store its extension map. Maybe it is wrong way.

Right. Extension nodes are complicated. In the end, we would probably need to import a full schedule tree to describe their positions correctly. However, for the first tests it's enough to just assume all new statements are inserted at the very top of the schedule tree. Your actual transformation will insert them somewhere else, but that's how it is.

I'll try to implement it.

There is also a problem related to exporting CopyStmts. We use ScopStmt::getScheduleStr() to export a schedule of a statement. It calls ScopStmt::getSchedule that calls Scop::getSchedule, which calls isl_schedule_get_map that causes:

/home/roman/Documents/polly/llvm/tools/polly/lib/External/isl/isl_schedule_tree.c:1820: cannot construct subtree schedule of tree with extension nodes

For the same reason we can't use ScopInfo's to check the work of the IslScheduleOptimizer pass at the polyhedral level in this case (that's why I temporary use the previous variant of the test)

We could make ScopStmt::getScheduleStr() return an empty string in case a schedule tree has extension nodes. It doesn't solve a problem related to export of CopyStmts. However, it could probably help to build a test case.

Yes, we can have it return an empty string. There are a couple of cases where a schedule tree with extension nodes cannot be moveled with a flat schedule. We probably need to handle them conservatively. (IslAst also uses getSchedule. In this case, we can probably replace it with getScheduleTree)

I've tried to implement it in this version of a patch.

[gareevroman]

Fix misprints.

[grosser]

Hi Roman,

besides some minor comments, this now looks good to me. Thank you for your work.

Best,
Tobias

include/polly/ScopInfo.h

2324 ↗

(On Diff #69482)

Unnecessary line break.

2360 ↗

(On Diff #69482)

containsExtensionNodes

'Ext' is not a commonly used abbreviation, so people will have difficulties to expand them in their mind.

lib/Analysis/DependenceInfo.cpp

168 ↗

(On Diff #69480)

require

169 ↗

(On Diff #69480)

require

606 ↗

(On Diff #69480)

require

lib/Analysis/PolyhedralInfo.cpp

138 ↗

(On Diff #69482)

require

lib/Analysis/ScopInfo.cpp

1473 ↗

(On Diff #69482)

Could it happen that this conflicts with a Statement that we generate for a basic block with the name "Copy"? If this is the case, maybe name it "CopyStmt_..."?

Also, could you add a test case that covers this situation?

lib/Exchange/JSONExporter.cpp

293 ↗

(On Diff #69482)

require

lib/Transform/DeadCodeElimination.cpp

96 ↗

(On Diff #69482)

require

lib/Transform/ScheduleOptimizer.cpp

1023 ↗

(On Diff #69482)

that make

[gareevroman]

A new version updated according to the comments.

[gareevroman]

Hi Tobias,

thanks for the comments and review!

lib/Analysis/ScopInfo.cpp

1463 ↗

(On Diff #71162)

Could it happen that this conflicts with a Statement that we generate for a basic block with the name "Copy"? If this is the case, maybe name it "CopyStmt_..."?

Yes, I think it's possible in case, for example, a basic block has a name "Copy_0".

Also, could you add a test case that covers this situation?

Could we change the name of a basic block from an existing test case to do it? I've implemented it in the last version of patch.

[grosser]

Hi Roman,

yes this looks good!

Best,
Tobias

polly/trunk/include/polly/CodeGen/IslExprBuilder.h

public:
 
   /// Return the current overflow status or nullptr if it is not tracked.
   ///
   /// @return A nullptr if tracking is disabled or otherwise an i1 that has the
   ///         value of "0" if and only if no overflow happened since tracking
   ///         was enabled.
   llvm::Value *getOverflowState() const;
 
+  /// Create LLVM-IR that computes the memory location of an access expression.
+  ///
+  /// For a given isl_ast_expr[ession] of type isl_ast_op_access this function
+  /// creates IR that computes the address the access expression refers to.
+  ///
+  /// @param Expr The ast expression of type isl_ast_op_access
+  ///             for which we generate LLVM-IR.
+  ///
+  /// @return The llvm::Value* containing the result of the computation.
+  llvm::Value *createAccessAddress(__isl_take isl_ast_expr *Expr);
+
 private:
   Scop &S;
 
   /// Flag that will be set if an overflow occurred at runtime.
   ///
   /// Note that this flag is by default a nullptr and if it is a nullptr
   /// we will not record overflows but simply perform the computations.
   /// The intended usage is as follows:
private:
   llvm::Value *createOpNAry(__isl_take isl_ast_expr *Expr);
   llvm::Value *createOpSelect(__isl_take isl_ast_expr *Expr);
   llvm::Value *createOpICmp(__isl_take isl_ast_expr *Expr);
   llvm::Value *createOpBoolean(__isl_take isl_ast_expr *Expr);
   llvm::Value *createOpBooleanConditional(__isl_take isl_ast_expr *Expr);
   llvm::Value *createId(__isl_take isl_ast_expr *Expr);
   llvm::Value *createInt(__isl_take isl_ast_expr *Expr);
   llvm::Value *createOpAddressOf(__isl_take isl_ast_expr *Expr);
-  llvm::Value *createAccessAddress(__isl_take isl_ast_expr *Expr);
 
   /// Create a binary operation @p Opc and track overflows if requested.
   ///
   /// @param OpC  The binary operation that should be performed [Add/Sub/Mul].
   /// @param LHS  The left operand.
   /// @param RHS  The right operand.
   /// @param Name The (base) name of the new IR operations.
   ///

polly/trunk/include/polly/CodeGen/IslNodeBuilder.h

protected:
   ///
   /// @param Node The node we want to obtain the schedule for.
   /// @return Return an isl_union_map that maps from the statements executed
   ///         below this ast node to the scheduling vectors used to enumerate
   ///         them.
   ///
   virtual __isl_give isl_union_map *
   getScheduleForAstNode(__isl_take isl_ast_node *Node);
+
+private:
+  /// Create code for a copy statement.
+  ///
+  /// A copy statement is expected to have one read memory access and one write
+  /// memory access (in this very order). Data is loaded from the location
+  /// described by the read memory access and written to the location described
+  /// by the write memory access. @p NewAccesses contains for each access
+  /// the isl ast expression that describes the location accessed.
+  ///
+  /// @param Stmt The copy statement that contains the accesses.
+  /// @param NewAccesses The hash table that contains remappings from memory
+  ///                    ids to new access expressions.
+  void generateCopyStmt(ScopStmt *Stmt,
+                        __isl_keep isl_id_to_ast_expr *NewAccesses);
 };
 
 #endif

polly/trunk/include/polly/ScheduleOptimizer.h

public:
 
   /// Decide if the @p NewSchedule is profitable for @p S.
   ///
   /// @param S           The SCoP we optimize.
   /// @param NewSchedule The new schedule we computed.
   ///
   /// @return True, if we believe @p NewSchedule is an improvement for @p S.
   static bool isProfitableSchedule(polly::Scop &S,
-                                   __isl_keep isl_union_map *NewSchedule);
+                                   __isl_keep isl_schedule *NewSchedule);
 
   /// Isolate a set of partial tile prefixes.
   ///
   /// This set should ensure that it contains only partial tile prefixes that
   /// have exactly VectorWidth iterations.
   ///
   /// @param Node A schedule node band, which is a parent of a band node,
   ///             that contains a vector loop.

polly/trunk/include/polly/ScopInfo.h

public:
   /// @param Subscripts Subscipt expressions
   /// @param Sizes      Dimension lengths of the accessed array.
   /// @param BaseName   Name of the acessed array.
   MemoryAccess(ScopStmt *Stmt, Instruction *AccessInst, AccessType AccType,
                Value *BaseAddress, Type *ElemType, bool Affine,
                ArrayRef<const SCEV *> Subscripts, ArrayRef<const SCEV *> Sizes,
                Value *AccessValue, ScopArrayInfo::MemoryKind Kind,
                StringRef BaseName);
+
+  /// Create a new MemoryAccess that corresponds to @p AccRel.
+  ///
+  /// Along with @p Stmt and @p AccType it uses information about dimension
+  /// lengths of the accessed array, the type of the accessed array elements,
+  /// the name of the accessed array that is derived from the object accessible
+  /// via @p AccRel.
+  ///
+  /// @param Stmt       The parent statement.
+  /// @param AccType    Whether read or write access.
+  /// @param AccRel     The access relation that describes the memory access.
+  MemoryAccess(ScopStmt *Stmt, AccessType AccType, __isl_take isl_map *AccRel);
+
   ~MemoryAccess();
 
   /// Add a new incoming block/value pairs for this PHI/ExitPHI access.
   ///
   /// @param IncomingBlock The PHI's incoming block.
   /// @param IncomingValue The value when reacing the PHI from the @p
   ///                      IncomingBlock.
   void addIncoming(BasicBlock *IncomingBlock, Value *IncomingValue) {
public:
   const ScopStmt &operator=(const ScopStmt &) = delete;
 
   /// Create the ScopStmt from a BasicBlock.
   ScopStmt(Scop &parent, BasicBlock &bb);
 
   /// Create an overapproximating ScopStmt for the region @p R.
   ScopStmt(Scop &parent, Region &R);
 
+  /// Create a copy statement.
+  ///
+  /// @param Stmt       The parent statement.
+  /// @param SourceRel  The source location.
+  /// @param TargetRel  The target location.
+  /// @param Domain     The original domain under which copy statement whould
+  ///                   be executed.
+  ScopStmt(Scop &parent, __isl_take isl_map *SourceRel,
+           __isl_take isl_map *TargetRel, __isl_take isl_set *Domain);
+
   /// Initialize members after all MemoryAccesses have been added.
   void init(LoopInfo &LI);
 
 private:
   /// Polyhedral description
   //@{
 
   /// The Scop containing this ScopStmt
public:
   /// @return The id of the iteration domain space
   __isl_give isl_id *getDomainId() const;
 
   /// Get an isl string representing this domain.
   std::string getDomainStr() const;
 
   /// Get the schedule function of this ScopStmt.
   ///
-  /// @return The schedule function of this ScopStmt.
+  /// @return The schedule function of this ScopStmt, if it does not contain
+  /// extension nodes, and nullptr, otherwise.
   __isl_give isl_map *getSchedule() const;
 
   /// Get an isl string representing this schedule.
+  ///
+  /// @return An isl string representing this schedule, if it does not contain
+  /// extension nodes, and an empty string, otherwise.
   std::string getScheduleStr() const;
 
   /// Get the invalid domain for this statement.
   __isl_give isl_set *getInvalidDomain() const {
     return isl_set_copy(InvalidDomain);
   }
 
   /// Get the invalid context for this statement.
   __isl_give isl_set *getInvalidContext() const {
     return isl_set_params(getInvalidDomain());
   }
 
   /// Set the invalid context for this statement to @p ID.
   void setInvalidDomain(__isl_take isl_set *ID);
 
   /// Get the BasicBlock represented by this ScopStmt (if any).
   ///
   /// @return The BasicBlock represented by this ScopStmt, or null if the
   ///         statement represents a region.
   BasicBlock *getBasicBlock() const { return BB; }
 
   /// Return true if this statement represents a single basic block.
   bool isBlockStmt() const { return BB != nullptr; }
 
+  /// Return true if this is a copy statement.
+  bool isCopyStmt() const { return BB == nullptr && R == nullptr; }
+
   /// Get the region represented by this ScopStmt (if any).
   ///
   /// @return The region represented by this ScopStmt, or null if the statement
   ///         represents a basic block.
   Region *getRegion() const { return R; }
 
   /// Return true if this statement represents a whole region.
   bool isRegionStmt() const { return R != nullptr; }
private:
   bool HasSingleExitEdge;
 
   /// Flag to remember if the SCoP contained an error block or not.
   bool HasErrorBlock;
 
   /// Max loop depth.
   unsigned MaxLoopDepth;
 
+  /// Number of copy statements.
+  unsigned CopyStmtsNum;
+
   typedef std::list<ScopStmt> StmtSet;
   /// The statements in this Scop.
   StmtSet Stmts;
 
   /// Parameters of this Scop
   ParameterSetTy Parameters;
 
   /// Mapping from parameters to their ids.
private:
 
   /// List of invariant accesses.
   InvariantEquivClassesTy InvariantEquivClasses;
 
   /// Scop constructor; invoked from ScopBuilder::buildScop.
   Scop(Region &R, ScalarEvolution &SE, LoopInfo &LI,
        ScopDetection::DetectionContext &DC);
 
-  /// Add the access function to all MemoryAccess objects of the Scop
-  ///        created in this pass.
-  void addAccessFunction(MemoryAccess *Access) {
-    AccessFunctions.emplace_back(Access);
-  }
   //@}
 
   /// Initialize this ScopBuilder.
   void init(AliasAnalysis &AA, AssumptionCache &AC, DominatorTree &DT,
             LoopInfo &LI);
 
   /// Propagate domains that are known due to graph properties.
   ///
private:
   void printAliasAssumptions(raw_ostream &OS) const;
   //@}
 
   friend class ScopBuilder;
 
 public:
   ~Scop();
 
+  /// Get the count of copy statements added to this Scop.
+  ///
+  /// @return The count of copy statements added to this Scop.
+  unsigned getCopyStmtsNum() { return CopyStmtsNum; }
+
+  /// Create a new copy statement.
+  ///
+  /// A new statement will be created and added to the statement vector.
+  ///
+  /// @param Stmt       The parent statement.
+  /// @param SourceRel  The source location.
+  /// @param TargetRel  The target location.
+  /// @param Domain     The original domain under which copy statement whould
+  ///                   be executed.
+  ScopStmt *addScopStmt(__isl_take isl_map *SourceRel,
+                        __isl_take isl_map *TargetRel,
+                        __isl_take isl_set *Domain);
+
+  /// Add the access function to all MemoryAccess objects of the Scop
+  ///        created in this pass.
+  void addAccessFunction(MemoryAccess *Access) {
+    AccessFunctions.emplace_back(Access);
+  }
+
   ScalarEvolution *getSE() const;
 
   /// Get the count of parameters used in this Scop.
   ///
   /// @return The count of parameters used in this Scop.
   size_t getNumParams() const { return Parameters.size(); }
 
   /// Take a list of parameters and add the new ones to the scop.
public:
 
   /// Get a union map of all reads performed in the SCoP.
   __isl_give isl_union_map *getReads();
 
   /// Get a union map of all memory accesses performed in the SCoP.
   __isl_give isl_union_map *getAccesses();
 
   /// Get the schedule of all the statements in the SCoP.
+  ///
+  /// @return The schedule of all the statements in the SCoP, if the schedule of
+  /// the Scop does not contain extension nodes, and nullptr, otherwise.
   __isl_give isl_union_map *getSchedule() const;
 
   /// Get a schedule tree describing the schedule of all statements.
   __isl_give isl_schedule *getScheduleTree() const;
 
   /// Update the current schedule
   ///
   /// NewSchedule The new schedule (given as a flat union-map).
public:
   ///    0 if @p L is an outermost loop in the SCoP
   ///   >0 for other loops in the SCoP
   ///   -1 if @p L is nullptr or there is no outermost loop in the SCoP
   int getRelativeLoopDepth(const Loop *L) const;
 
   /// Find the ScopArrayInfo associated with an isl Id
   ///        that has name @p Name.
   ScopArrayInfo *getArrayInfoByName(const std::string BaseName);
+
+  /// Check whether @p Schedule contains extension nodes.
+  ///
+  /// @return true if @p Schedule contains extension nodes.
+  static bool containsExtensionNode(__isl_keep isl_schedule *Schedule);
 };
 
 /// Print Scop scop to raw_ostream O.
 static inline raw_ostream &operator<<(raw_ostream &O, const Scop &scop) {
   scop.print(O);
   return O;
 }
 

polly/trunk/lib/Analysis/DependenceInfo.cpp

for (MemoryAccess *MA : Stmt) {
         //   [Stmt[i0, i1] -> MemAcc_A[i0 + i1]] -> MemAcc_A[i0 + i1]
         //
         // The original schedule looks like
         //   Stmt[i0, i1] -> [0, i0, 2, i1, 0]
         // but as we transformed the access domain we need the schedule
         // to match the new access domains, thus we need
         //   [Stmt[i0, i1] -> MemAcc_A[i0 + i1]] -> [0, i0, 2, i1, 0]
         isl_map *Schedule = Stmt.getSchedule();
+        assert(Schedule && "Schedules that contain extension nodes require "
+                           "special handling.");
         Schedule = isl_map_apply_domain(
             Schedule,
             isl_map_reverse(isl_map_domain_map(isl_map_copy(accdom))));
         accdom = isl_map_range_map(accdom);
 
         *AccessSchedule = isl_union_map_add_map(*AccessSchedule, Schedule);
       } else {
         accdom = tag(accdom, MA, Level);
         if (Level > Dependences::AL_Statement) {
-          isl_map *Schedule = tag(Stmt.getSchedule(), MA, Level);
+          auto *StmtScheduleMap = Stmt.getSchedule();
+          assert(StmtScheduleMap && "Schedules that contain extension nodes "
+                                    "require special handling.");
+          isl_map *Schedule = tag(StmtScheduleMap, MA, Level);
           *StmtSchedule = isl_union_map_add_map(*StmtSchedule, Schedule);
         }
       }
 
       if (MA->isRead())
         *Read = isl_union_map_add_map(*Read, accdom);
       else
         *Write = isl_union_map_add_map(*Write, accdom);
bool Dependences::isValidSchedule(Scop &S,
 
   for (ScopStmt &Stmt : S) {
     isl_map *StmtScat;
 
     if (NewSchedule->find(&Stmt) == NewSchedule->end())
       StmtScat = Stmt.getSchedule();
     else
       StmtScat = isl_map_copy((*NewSchedule)[&Stmt]);
+    assert(StmtScat &&
+           "Schedules that contain extension nodes require special handling.");
 
     if (!ScheduleSpace)
       ScheduleSpace = isl_space_range(isl_map_get_space(StmtScat));
 
     Schedule = isl_union_map_add_map(Schedule, StmtScat);
   }
 
   Dependences =

polly/trunk/lib/Analysis/PolyhedralInfo.cpp

__isl_give isl_union_map *PolyhedralInfo::getScheduleForLoop(const Scop *S,
   for (auto *BB : L->blocks()) {
     auto *SS = S->getStmtFor(BB);
     if (!SS)
       continue;
 
     unsigned int MaxDim = SS->getNumIterators();
     DEBUG(dbgs() << "Maximum depth of Stmt:\t" << MaxDim << "\n");
     auto *ScheduleMap = SS->getSchedule();
+    assert(ScheduleMap &&
+           "Schedules that contain extension nodes require special handling.");
 
     ScheduleMap = isl_map_project_out(ScheduleMap, isl_dim_out, CurrDim + 1,
                                       MaxDim - CurrDim - 1);
     ScheduleMap =
         isl_map_set_tuple_id(ScheduleMap, isl_dim_in, SS->getDomainId());
     Schedule =
         isl_union_map_union(Schedule, isl_union_map_from_map(ScheduleMap));
   }

polly/trunk/lib/Analysis/ScopInfo.cpp

MemoryAccess::MemoryAccess(ScopStmt *Stmt, Instruction *AccessInst,
   static const std::string TypeStrings[] = {"", "_Read", "_Write", "_MayWrite"};
   const std::string Access = TypeStrings[AccType] + utostr(Stmt->size()) + "_";
 
   std::string IdName =
       getIslCompatibleName(Stmt->getBaseName(), Access, BaseName);
   Id = isl_id_alloc(Stmt->getParent()->getIslCtx(), IdName.c_str(), this);
 }
 
+MemoryAccess::MemoryAccess(ScopStmt *Stmt, AccessType AccType,
+                           __isl_take isl_map *AccRel)
+    : Kind(ScopArrayInfo::MemoryKind::MK_Array), AccType(AccType),
+      RedType(RT_NONE), Statement(Stmt), InvalidDomain(nullptr),
+      AccessInstruction(nullptr), IsAffine(true), AccessRelation(nullptr),
+      NewAccessRelation(AccRel) {
+  auto *ArrayInfoId = isl_map_get_tuple_id(NewAccessRelation, isl_dim_out);
+  auto *SAI = ScopArrayInfo::getFromId(ArrayInfoId);
+  Sizes.push_back(nullptr);
+  for (unsigned i = 1; i < SAI->getNumberOfDimensions(); i++)
+    Sizes.push_back(SAI->getDimensionSize(i));
+  ElementType = SAI->getElementType();
+  BaseAddr = SAI->getBasePtr();
+  BaseName = SAI->getName();
+  static const std::string TypeStrings[] = {"", "_Read", "_Write", "_MayWrite"};
+  const std::string Access = TypeStrings[AccType] + utostr(Stmt->size()) + "_";
+
+  std::string IdName =
+      getIslCompatibleName(Stmt->getBaseName(), Access, BaseName);
+  Id = isl_id_alloc(Stmt->getParent()->getIslCtx(), IdName.c_str(), this);
+}
+
 void MemoryAccess::realignParams() {
   auto *Ctx = Statement->getParent()->getContext();
   InvalidDomain = isl_set_gist_params(InvalidDomain, isl_set_copy(Ctx));
   AccessRelation = isl_map_gist_params(AccessRelation, Ctx);
 }
 
 const std::string MemoryAccess::getReductionOperatorStr() const {
   return MemoryAccess::getReductionOperatorStr(getReductionType());

 __isl_give isl_map *ScopStmt::getSchedule() const {
   isl_set *Domain = getDomain();
   if (isl_set_is_empty(Domain)) {
     isl_set_free(Domain);
     return isl_map_from_aff(
         isl_aff_zero_on_domain(isl_local_space_from_space(getDomainSpace())));
   }
   auto *Schedule = getParent()->getSchedule();
+  if (!Schedule) {
+    isl_set_free(Domain);
+    return nullptr;
+  }
   Schedule = isl_union_map_intersect_domain(
       Schedule, isl_union_set_from_set(isl_set_copy(Domain)));
   if (isl_union_map_is_empty(Schedule)) {
     isl_set_free(Domain);
     isl_union_map_free(Schedule);
     return isl_map_from_aff(
         isl_aff_zero_on_domain(isl_local_space_from_space(getDomainSpace())));
   }

 
 ScopStmt::ScopStmt(Scop &parent, BasicBlock &bb)
     : Parent(parent), InvalidDomain(nullptr), Domain(nullptr), BB(&bb),
       R(nullptr), Build(nullptr) {
 
   BaseName = getIslCompatibleName("Stmt_", &bb, "");
 }
 
+ScopStmt::ScopStmt(Scop &parent, __isl_take isl_map *SourceRel,
+                   __isl_take isl_map *TargetRel, __isl_take isl_set *NewDomain)
+    : Parent(parent), InvalidDomain(nullptr), Domain(NewDomain), BB(nullptr),
+      R(nullptr), Build(nullptr) {
+  BaseName = getIslCompatibleName("CopyStmt_", "",
+                                  std::to_string(parent.getCopyStmtsNum()));
+  auto *Id = isl_id_alloc(getIslCtx(), getBaseName(), this);
+  Domain = isl_set_set_tuple_id(Domain, isl_id_copy(Id));
+  TargetRel = isl_map_set_tuple_id(TargetRel, isl_dim_in, Id);
+  auto *Access =
+      new MemoryAccess(this, MemoryAccess::AccessType::MUST_WRITE, TargetRel);
+  parent.addAccessFunction(Access);
+  addAccess(Access);
+  SourceRel = isl_map_set_tuple_id(SourceRel, isl_dim_in, isl_id_copy(Id));
+  Access = new MemoryAccess(this, MemoryAccess::AccessType::READ, SourceRel);
+  parent.addAccessFunction(Access);
+  addAccess(Access);
+}
+
 void ScopStmt::init(LoopInfo &LI) {
   assert(!Domain && "init must be called only once");
 
   buildDomain();
   collectSurroundingLoops();
   buildAccessRelations();
 
   if (DetectReductions)
for (const auto &CandidatePair : Candidates) {
     CandidatePair.second->markAsReductionLike(RT);
   }
 }
 
 std::string ScopStmt::getDomainStr() const { return stringFromIslObj(Domain); }
 
 std::string ScopStmt::getScheduleStr() const {
   auto *S = getSchedule();
+  if (!S)
+    return "";
   auto Str = stringFromIslObj(S);
   isl_map_free(S);
   return Str;
 }
 
 void ScopStmt::setInvalidDomain(__isl_take isl_set *ID) {
   isl_set_free(InvalidDomain);
   InvalidDomain = ID;
static Loop *getLoopSurroundingScop(Scop &S, LoopInfo &LI) {
 
   return L ? (S.contains(L) ? L->getParentLoop() : L) : nullptr;
 }
 
 Scop::Scop(Region &R, ScalarEvolution &ScalarEvolution, LoopInfo &LI,
            ScopDetection::DetectionContext &DC)
     : SE(&ScalarEvolution), R(R), IsOptimized(false),
       HasSingleExitEdge(R.getExitingBlock()), HasErrorBlock(false),
-      MaxLoopDepth(0), DC(DC), IslCtx(isl_ctx_alloc(), isl_ctx_free),
-      Context(nullptr), Affinator(this, LI), AssumedContext(nullptr),
-      InvalidContext(nullptr), Schedule(nullptr) {
+      MaxLoopDepth(0), CopyStmtsNum(0), DC(DC),
+      IslCtx(isl_ctx_alloc(), isl_ctx_free), Context(nullptr),
+      Affinator(this, LI), AssumedContext(nullptr), InvalidContext(nullptr),
+      Schedule(nullptr) {
   if (IslOnErrorAbort)
     isl_options_set_on_error(getIslCtx(), ISL_ON_ERROR_ABORT);
   buildContext();
 }
 
 void Scop::init(AliasAnalysis &AA, AssumptionCache &AC, DominatorTree &DT,
                 LoopInfo &LI) {
   buildInvariantEquivalenceClasses();

 __isl_give isl_union_map *Scop::getReads() {
   return getAccessesOfType([](MemoryAccess &MA) { return MA.isRead(); });
 }
 
 __isl_give isl_union_map *Scop::getAccesses() {
   return getAccessesOfType([](MemoryAccess &MA) { return true; });
 }
 
+// Check whether @p Node is an extension node.
+//
+// @return true if @p Node is an extension node.
+isl_bool isNotExtNode(__isl_keep isl_schedule_node *Node, void *User) {
+  if (isl_schedule_node_get_type(Node) == isl_schedule_node_extension)
+    return isl_bool_error;
+  else
+    return isl_bool_true;
+}
+
+bool Scop::containsExtensionNode(__isl_keep isl_schedule *Schedule) {
+  return isl_schedule_foreach_schedule_node_top_down(Schedule, isNotExtNode,
+                                                     nullptr) == isl_stat_error;
+}
+
 __isl_give isl_union_map *Scop::getSchedule() const {
   auto *Tree = getScheduleTree();
+  if (containsExtensionNode(Tree)) {
+    isl_schedule_free(Tree);
+    return nullptr;
+  }
   auto *S = isl_schedule_get_map(Tree);
   isl_schedule_free(Tree);
   return S;
 }
 
 __isl_give isl_schedule *Scop::getScheduleTree() const {
   return isl_schedule_intersect_domain(isl_schedule_copy(Schedule),
                                        getDomains());
if (BB) {
     assert(R && "Either basic block or a region expected.");
     Stmts.emplace_back(*this, *R);
     auto *Stmt = &Stmts.back();
     for (BasicBlock *BB : R->blocks())
       StmtMap[BB] = Stmt;
   }
 }
 
+ScopStmt *Scop::addScopStmt(__isl_take isl_map *SourceRel,
+                            __isl_take isl_map *TargetRel,
+                            __isl_take isl_set *Domain) {
+  Stmts.emplace_back(*this, SourceRel, TargetRel, Domain);
+  CopyStmtsNum++;
+  return &(Stmts.back());
+}
+
 void Scop::buildSchedule(LoopInfo &LI) {
   Loop *L = getLoopSurroundingScop(*this, LI);
   LoopStackTy LoopStack({LoopStackElementTy(L, nullptr, 0)});
   buildSchedule(getRegion().getNode(), LoopStack, LI);
   assert(LoopStack.size() == 1 && LoopStack.back().L == L);
   Schedule = LoopStack[0].Schedule;
 }
 

polly/trunk/lib/CodeGen/BlockGenerators.cpp

for (auto &SAI : S.arrays()) {
     MergePHI->addIncoming(OriginalValue, ExitBB);
     int Idx = PHI->getBasicBlockIndex(MergeBB);
     PHI->setIncomingValue(Idx, MergePHI);
   }
 }
 
 void BlockGenerator::invalidateScalarEvolution(Scop &S) {
   for (auto &Stmt : S)
-    if (Stmt.isBlockStmt())
+    if (Stmt.isCopyStmt())
+      continue;
+    else if (Stmt.isBlockStmt())
       for (auto &Inst : *Stmt.getBasicBlock())
         SE.forgetValue(&Inst);
     else if (Stmt.isRegionStmt())
       for (auto *BB : Stmt.getRegion()->blocks())
         for (auto &Inst : *BB)
           SE.forgetValue(&Inst);
     else
       llvm_unreachable("Unexpected statement type found");

polly/trunk/lib/CodeGen/IRBuilder.cpp

void ScopAnnotator::buildAliasScopes(Scop &S) {
   AliasScopeDomain = getID(Ctx, MDString::get(Ctx, "polly.alias.scope.domain"));
 
   AliasScopeMap.clear();
   OtherAliasScopeListMap.clear();
 
   SetVector<Value *> BasePtrs;
   for (ScopStmt &Stmt : S)
     for (MemoryAccess *MA : Stmt)
+      if (!Stmt.isCopyStmt())
         BasePtrs.insert(MA->getBaseAddr());
 
   std::string AliasScopeStr = "polly.alias.scope.";
   for (Value *BasePtr : BasePtrs)
     AliasScopeMap[BasePtr] = getID(
         Ctx, AliasScopeDomain,
         MDString::get(Ctx, (AliasScopeStr + BasePtr->getName()).str().c_str()));
 
   for (Value *BasePtr : BasePtrs) {

polly/trunk/lib/CodeGen/IslAst.cpp

void IslAstInfo::printScop(raw_ostream &OS, Scop &S) const {
   P = isl_printer_set_output_format(P, ISL_FORMAT_C);
   P = isl_printer_print_ast_expr(P, RunCondition);
   RtCStr = isl_printer_get_str(P);
   P = isl_printer_flush(P);
   P = isl_printer_indent(P, 4);
   P = isl_ast_node_print(RootNode, P, Options);
   AstStr = isl_printer_get_str(P);
 
-  isl_union_map *Schedule =
-      isl_union_map_intersect_domain(S.getSchedule(), S.getDomains());
+  auto *Schedule = S.getScheduleTree();
 
   DEBUG({
     dbgs() << S.getContextStr() << "\n";
     dbgs() << stringFromIslObj(Schedule);
   });
   OS << "\nif (" << RtCStr << ")\n\n";
   OS << AstStr << "\n";
   OS << "else\n";
   OS << "    {  /* original code */ }\n\n";
 
   free(RtCStr);
   free(AstStr);
 
   isl_ast_expr_free(RunCondition);
-  isl_union_map_free(Schedule);
+  isl_schedule_free(Schedule);
   isl_ast_node_free(RootNode);
   isl_printer_free(P);
 }
 
 void IslAstInfo::getAnalysisUsage(AnalysisUsage &AU) const {
   // Get the Common analysis usage of ScopPasses.
   ScopPass::getAnalysisUsage(AU);
   AU.addRequired<ScopInfoRegionPass>();

polly/trunk/lib/CodeGen/IslNodeBuilder.cpp

for (Value *IV : IVS) {
     i++;
   }
 
   IDToValue[IteratorID] = OldValue;
   isl_id_free(IteratorID);
   isl_ast_expr_free(Expr);
 }
 
+void IslNodeBuilder::generateCopyStmt(
+    ScopStmt *Stmt, __isl_keep isl_id_to_ast_expr *NewAccesses) {
+  assert(Stmt->size() == 2);
+  auto ReadAccess = Stmt->begin();
+  auto WriteAccess = ReadAccess++;
+  assert((*ReadAccess)->isRead() && (*WriteAccess)->isMustWrite());
+  assert((*ReadAccess)->getElementType() == (*WriteAccess)->getElementType() &&
+         "Accesses use the same data type");
+  assert((*ReadAccess)->isArrayKind() && (*WriteAccess)->isArrayKind());
+  auto *AccessExpr =
+      isl_id_to_ast_expr_get(NewAccesses, (*ReadAccess)->getId());
+  auto *LoadValue = ExprBuilder.create(AccessExpr);
+  AccessExpr = isl_id_to_ast_expr_get(NewAccesses, (*WriteAccess)->getId());
+  auto *StoreAddr = ExprBuilder.createAccessAddress(AccessExpr);
+  Builder.CreateStore(LoadValue, StoreAddr);
+}
+
 void IslNodeBuilder::createUser(__isl_take isl_ast_node *User) {
   LoopToScevMapT LTS;
   isl_id *Id;
   ScopStmt *Stmt;
 
   isl_ast_expr *Expr = isl_ast_node_user_get_expr(User);
   isl_ast_expr *StmtExpr = isl_ast_expr_get_op_arg(Expr, 0);
   Id = isl_ast_expr_get_id(StmtExpr);
   isl_ast_expr_free(StmtExpr);
 
   LTS.insert(OutsideLoopIterations.begin(), OutsideLoopIterations.end());
 
   Stmt = (ScopStmt *)isl_id_get_user(Id);
   auto *NewAccesses = createNewAccesses(Stmt, User);
+  if (Stmt->isCopyStmt()) {
+    generateCopyStmt(Stmt, NewAccesses);
+    isl_ast_expr_free(Expr);
+  } else {
     createSubstitutions(Expr, Stmt, LTS);
 
     if (Stmt->isBlockStmt())
       BlockGen.copyStmt(*Stmt, LTS, NewAccesses);
     else
       RegionGen.copyStmt(*Stmt, LTS, NewAccesses);
+  }
 
   isl_id_to_ast_expr_free(NewAccesses);
   isl_ast_node_free(User);
   isl_id_free(Id);
 }
 
 void IslNodeBuilder::createBlock(__isl_take isl_ast_node *Block) {
   isl_ast_node_list *List = isl_ast_node_block_get_children(Block);

polly/trunk/lib/Exchange/JSONExporter.cpp

 
 bool JSONImporter::importSchedule(Scop &S, Json::Value &JScop,
                                   const Dependences &D) {
   StatementToIslMapTy NewSchedule;
 
   int Index = 0;
   for (ScopStmt &Stmt : S) {
     Json::Value Schedule = JScop["statements"][Index]["schedule"];
+    assert(!Schedule.asString().empty() &&
+           "Schedules that contain extension nodes require special handling.");
     isl_map *Map = isl_map_read_from_str(S.getIslCtx(), Schedule.asCString());
     isl_space *Space = Stmt.getDomainSpace();
 
     // Copy the old tuple id. This is necessary to retain the user pointer,
     // that stores the reference to the ScopStmt this schedule belongs to.
     Map = isl_map_set_tuple_id(Map, isl_dim_in,
                                isl_space_get_tuple_id(Space, isl_dim_set));
     for (unsigned i = 0; i < isl_space_dim(Space, isl_dim_param); i++) {

polly/trunk/lib/Transform/DeadCodeElimination.cpp

 // We could be more precise by removing may-write accesses for which we know
 // that they are overwritten by a must-write after. However, at the moment the
 // only may-writes we introduce access the full (unbounded) array, such that
 // bounded write accesses can not overwrite all of the data-locations. As
 // this means may-writes are in the current situation always live, there is
 // no point in trying to remove them from the live-out set.
 __isl_give isl_union_set *DeadCodeElim::getLiveOut(Scop &S) {
   isl_union_map *Schedule = S.getSchedule();
+  assert(Schedule &&
+         "Schedules that contain extension nodes require special handling.");
   isl_union_map *WriteIterations = isl_union_map_reverse(S.getMustWrites());
   isl_union_map *WriteTimes =
       isl_union_map_apply_range(WriteIterations, isl_union_map_copy(Schedule));
 
   isl_union_map *LastWriteTimes = isl_union_map_lexmax(WriteTimes);
   isl_union_map *LastWriteIterations = isl_union_map_apply_range(
       LastWriteTimes, isl_union_map_reverse(Schedule));
 

polly/trunk/lib/Transform/ScheduleOptimizer.cpp

if (isl_map_is_equal(ExpectedAccessRelation, AccessRelation)) {
       IdentifiedAccess = Access;
     }
     isl_map_free(AccessRelation);
   }
   isl_map_free(ExpectedAccessRelation);
   return IdentifiedAccess;
 }
 
+/// Add constrains to @Dim dimension of @p ExtMap.
+///
+/// If @ExtMap has the following form [O0, O1, O2]->[I1, I2, I3],
+/// the following constraint will be added
+/// Bound * OM <= IM <= Bound * (OM + 1) - 1,
+/// where M is @p Dim and Bound is @p Bound.
+///
+/// @param ExtMap The isl map to be modified.
+/// @param Dim The output dimension to be modfied.
+/// @param Bound The value that is used to specify the constraint.
+/// @return The modified isl map
+__isl_give isl_map *
+addExtensionMapMatMulDimConstraint(__isl_take isl_map *ExtMap, unsigned Dim,
+                                   unsigned Bound) {
+  assert(Bound != 0);
+  auto *ExtMapSpace = isl_map_get_space(ExtMap);
+  auto *ConstrSpace = isl_local_space_from_space(ExtMapSpace);
+  auto *Constr =
+      isl_constraint_alloc_inequality(isl_local_space_copy(ConstrSpace));
+  Constr = isl_constraint_set_coefficient_si(Constr, isl_dim_out, Dim, 1);
+  Constr =
+      isl_constraint_set_coefficient_si(Constr, isl_dim_in, Dim, Bound * (-1));
+  ExtMap = isl_map_add_constraint(ExtMap, Constr);
+  Constr = isl_constraint_alloc_inequality(ConstrSpace);
+  Constr = isl_constraint_set_coefficient_si(Constr, isl_dim_out, Dim, -1);
+  Constr = isl_constraint_set_coefficient_si(Constr, isl_dim_in, Dim, Bound);
+  Constr = isl_constraint_set_constant_si(Constr, Bound - 1);
+  return isl_map_add_constraint(ExtMap, Constr);
+}
+
+/// Create an access relation that is specific for matrix multiplication
+/// pattern.
+///
+/// Create an access relation of the following form:
+/// { [O0, O1, O2]->[I1, I2, I3] :
+///   FirstOutputDimBound * O0 <= I1 <= FirstOutputDimBound * (O0 + 1) - 1
+///   and SecondOutputDimBound * O1 <= I2 <= SecondOutputDimBound * (O1 + 1) - 1
+///   and ThirdOutputDimBound * O2 <= I3 <= ThirdOutputDimBound * (O2 + 1) - 1}
+///   where FirstOutputDimBound is @p FirstOutputDimBound,
+///   SecondOutputDimBound is @p SecondOutputDimBound,
+///   ThirdOutputDimBound is @p ThirdOutputDimBound
+///
+/// @param Ctx The isl context.
+/// @param FirstOutputDimBound,
+///        SecondOutputDimBound,
+///        ThirdOutputDimBound The parameters of the access relation.
+/// @return The specified access relation.
+__isl_give isl_map *getMatMulExt(isl_ctx *Ctx, unsigned FirstOutputDimBound,
+                                 unsigned SecondOutputDimBound,
+                                 unsigned ThirdOutputDimBound) {
+  auto *NewRelSpace = isl_space_alloc(Ctx, 0, 3, 3);
+  auto *extensionMap = isl_map_universe(NewRelSpace);
+  if (!FirstOutputDimBound)
+    extensionMap = isl_map_fix_si(extensionMap, isl_dim_out, 0, 0);
+  else
+    extensionMap = addExtensionMapMatMulDimConstraint(extensionMap, 0,
+                                                      FirstOutputDimBound);
+  if (!SecondOutputDimBound)
+    extensionMap = isl_map_fix_si(extensionMap, isl_dim_out, 1, 0);
+  else
+    extensionMap = addExtensionMapMatMulDimConstraint(extensionMap, 1,
+                                                      SecondOutputDimBound);
+  if (!ThirdOutputDimBound)
+    extensionMap = isl_map_fix_si(extensionMap, isl_dim_out, 2, 0);
+  else
+    extensionMap = addExtensionMapMatMulDimConstraint(extensionMap, 2,
+                                                      ThirdOutputDimBound);
+  return extensionMap;
+}
+
 /// Create an access relation that is specific to the matrix
 ///        multiplication pattern.
 ///
 /// Create an access relation of the following form:
 /// Stmt[O0, O1, O2]->[OI, OJ],
 /// where I is @p I, J is @J
 ///
 /// @param Stmt The SCoP statement for which to generate the access relation.
__isl_give isl_map *getMatMulAccRel(__isl_take isl_map *MapOldIndVar,
   Constr = isl_constraint_set_coefficient_si(Constr, isl_dim_in, 5, 1);
   Constr =
       isl_constraint_set_coefficient_si(Constr, isl_dim_in, FirstDim, Coeff);
   AccessRel = isl_map_add_constraint(AccessRel, Constr);
   AccessRel = isl_map_equate(AccessRel, isl_dim_in, SecondDim, isl_dim_out, 1);
   return isl_map_apply_range(MapOldIndVar, AccessRel);
 }
 
+__isl_give isl_schedule_node *
+createExtensionNode(__isl_take isl_schedule_node *Node,
+                    __isl_take isl_map *ExtensionMap) {
+  auto *Extension = isl_union_map_from_map(ExtensionMap);
+  auto *NewNode = isl_schedule_node_from_extension(Extension);
+  return isl_schedule_node_graft_before(Node, NewNode);
+}
+
 /// Apply the packing transformation.
 ///
 /// The packing transformation can be described as a data-layout
 /// transformation that requires to introduce a new array, copy data
 /// to the array, and change memory access locations of the compute kernel
 /// to reference the array.
 ///
 /// @param Node The schedule node to be optimized.
 /// @param MapOldIndVar The relation, which maps original induction variables
 ///                     to the ones, which are produced by schedule
 ///                     transformations.
 /// @param MicroParams, MacroParams Parameters of the BLIS kernel
 ///                                 to be taken into account.
 /// @return The optimized schedule node.
-static void optimizeDataLayoutMatrMulPattern(__isl_take isl_map *MapOldIndVar,
-                                             MicroKernelParamsTy MicroParams,
-                                             MacroKernelParamsTy MacroParams) {
+static __isl_give isl_schedule_node *optimizeDataLayoutMatrMulPattern(
+    __isl_take isl_schedule_node *Node, __isl_take isl_map *MapOldIndVar,
+    MicroKernelParamsTy MicroParams, MacroKernelParamsTy MacroParams) {
   auto InputDimsId = isl_map_get_tuple_id(MapOldIndVar, isl_dim_in);
   auto *Stmt = static_cast<ScopStmt *>(isl_id_get_user(InputDimsId));
   isl_id_free(InputDimsId);
   MemoryAccess *MemAccessA = identifyAccessA(Stmt);
   MemoryAccess *MemAccessB = identifyAccessB(Stmt);
   if (!MemAccessA || !MemAccessB) {
     isl_map_free(MapOldIndVar);
-    return;
+    return Node;
   }
+  Node = isl_schedule_node_parent(isl_schedule_node_parent(Node));
+  Node = isl_schedule_node_parent(isl_schedule_node_parent(Node));
+  Node = isl_schedule_node_parent(Node);
+  Node = isl_schedule_node_child(isl_schedule_node_band_split(Node, 2), 0);
   auto *AccRel =
       getMatMulAccRel(isl_map_copy(MapOldIndVar), MacroParams.Kc, 3, 6);
   unsigned FirstDimSize = MacroParams.Mc * MacroParams.Kc / MicroParams.Mr;
   unsigned SecondDimSize = MicroParams.Mr;
   auto *SAI = Stmt->getParent()->createScopArrayInfo(
       MemAccessA->getElementType(), "Packed_A", {FirstDimSize, SecondDimSize});
   AccRel = isl_map_set_tuple_id(AccRel, isl_dim_out, SAI->getBasePtrId());
+  auto *OldAcc = MemAccessA->getAccessRelation();
   MemAccessA->setNewAccessRelation(AccRel);
+  auto *ExtMap =
+      getMatMulExt(Stmt->getIslCtx(), MacroParams.Mc, 0, MacroParams.Kc);
+  ExtMap = isl_map_project_out(ExtMap, isl_dim_in, 1, 1);
+  auto *Domain = Stmt->getDomain();
+  auto *NewStmt = Stmt->getParent()->addScopStmt(
+      OldAcc, MemAccessA->getAccessRelation(), isl_set_copy(Domain));
+  ExtMap = isl_map_set_tuple_id(ExtMap, isl_dim_out, NewStmt->getDomainId());
+  Node = createExtensionNode(Node, ExtMap);
+  Node = isl_schedule_node_child(Node, 0);
   AccRel = getMatMulAccRel(MapOldIndVar, MacroParams.Kc, 4, 7);
   FirstDimSize = MacroParams.Nc * MacroParams.Kc / MicroParams.Nr;
   SecondDimSize = MicroParams.Nr;
   SAI = Stmt->getParent()->createScopArrayInfo(
       MemAccessB->getElementType(), "Packed_B", {FirstDimSize, SecondDimSize});
   AccRel = isl_map_set_tuple_id(AccRel, isl_dim_out, SAI->getBasePtrId());
+  OldAcc = MemAccessB->getAccessRelation();
   MemAccessB->setNewAccessRelation(AccRel);
+  ExtMap = getMatMulExt(Stmt->getIslCtx(), 0, MacroParams.Nc, MacroParams.Kc);
+  isl_map_move_dims(ExtMap, isl_dim_out, 0, isl_dim_in, 1, 1);
+  isl_map_move_dims(ExtMap, isl_dim_in, 2, isl_dim_out, 0, 1);
+  NewStmt = Stmt->getParent()->addScopStmt(
+      OldAcc, MemAccessB->getAccessRelation(), Domain);
+  ExtMap = isl_map_set_tuple_id(ExtMap, isl_dim_out, NewStmt->getDomainId());
+  Node = createExtensionNode(Node, ExtMap);
+  Node = isl_schedule_node_child(isl_schedule_node_child(Node, 0), 0);
+  return isl_schedule_node_child(isl_schedule_node_child(Node, 0), 0);
 }
 
 /// Get a relation mapping induction variables produced by schedule
 /// transformations to the original ones.
 ///
 /// @param Node The schedule node produced as the result of creation
 ///        of the BLIS kernels.
 /// @param MicroKernelParams, MacroKernelParams Parameters of the BLIS kernel
__isl_give isl_schedule_node *ScheduleTreeOptimizer::optimizeMatMulPattern(
   Node = createMicroKernel(Node, MicroKernelParams);
   if (MacroKernelParams.Mc == 1 || MacroKernelParams.Nc == 1 ||
       MacroKernelParams.Kc == 1)
     return Node;
   auto *MapOldIndVar = getInductionVariablesSubstitution(
       Node, MicroKernelParams, MacroKernelParams);
   if (!MapOldIndVar)
     return Node;
-  optimizeDataLayoutMatrMulPattern(MapOldIndVar, MicroKernelParams,
+  return optimizeDataLayoutMatrMulPattern(Node, MapOldIndVar, MicroKernelParams,
                                           MacroKernelParams);
-  return Node;
 }
 
 bool ScheduleTreeOptimizer::isMatrMultPattern(
     __isl_keep isl_schedule_node *Node) {
   auto *PartialSchedule =
       isl_schedule_node_band_get_partial_schedule_union_map(Node);
   if (isl_schedule_node_band_n_member(Node) != 3 ||
       isl_union_map_n_map(PartialSchedule) != 1) {

 __isl_give isl_schedule_node *ScheduleTreeOptimizer::optimizeScheduleNode(
     __isl_take isl_schedule_node *Node, const llvm::TargetTransformInfo *TTI) {
   Node = isl_schedule_node_map_descendant_bottom_up(
       Node, optimizeBand, const_cast<void *>(static_cast<const void *>(TTI)));
   return Node;
 }
 
 bool ScheduleTreeOptimizer::isProfitableSchedule(
-    Scop &S, __isl_keep isl_union_map *NewSchedule) {
+    Scop &S, __isl_keep isl_schedule *NewSchedule) {
   // To understand if the schedule has been optimized we check if the schedule
   // has changed at all.
   // TODO: We can improve this by tracking if any necessarily beneficial
   // transformations have been performed. This can e.g. be tiling, loop
   // interchange, or ...) We can track this either at the place where the
   // transformation has been performed or, in case of automatic ILP based
   // optimizations, by comparing (yet to be defined) performance metrics
   // before/after the scheduling optimizer
   // (e.g., #stride-one accesses)
+  if (S.containsExtensionNode(NewSchedule))
+    return true;
+  auto *NewScheduleMap = isl_schedule_get_map(NewSchedule);
   isl_union_map *OldSchedule = S.getSchedule();
-  bool changed = !isl_union_map_is_equal(OldSchedule, NewSchedule);
+  assert(OldSchedule && "Only IslScheduleOptimizer can insert extension nodes "
+                        "that make Scop::getSchedule() return nullptr.");
+  bool changed = !isl_union_map_is_equal(OldSchedule, NewScheduleMap);
   isl_union_map_free(OldSchedule);
+  isl_union_map_free(NewScheduleMap);
   return changed;
 }
 
 namespace {
 class IslScheduleOptimizer : public ScopPass {
 public:
   static char ID;
   explicit IslScheduleOptimizer() : ScopPass(ID) { LastSchedule = nullptr; }
DEBUG({
     dbgs() << "NewScheduleTree: \n" << isl_printer_get_str(P) << "\n";
     isl_printer_free(P);
   });
 
   Function &F = S.getFunction();
   auto *TTI = &getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
   isl_schedule *NewSchedule =
       ScheduleTreeOptimizer::optimizeSchedule(Schedule, TTI);
-  isl_union_map *NewScheduleMap = isl_schedule_get_map(NewSchedule);
 
-  if (!ScheduleTreeOptimizer::isProfitableSchedule(S, NewScheduleMap)) {
-    isl_union_map_free(NewScheduleMap);
+  if (!ScheduleTreeOptimizer::isProfitableSchedule(S, NewSchedule)) {
     isl_schedule_free(NewSchedule);
     return false;
   }
 
   S.setScheduleTree(NewSchedule);
   S.markAsOptimized();
 
   if (OptimizedScops)
     S.dump();
 
-  isl_union_map_free(NewScheduleMap);
   return false;
 }
 
 void IslScheduleOptimizer::printScop(raw_ostream &OS, Scop &) const {
   isl_printer *p;
   char *ScheduleStr;
 
   OS << "Calculated schedule:\n";

polly/trunk/test/ScheduleOptimizer/mat_mul_pattern_data_layout.ll

 ; RUN: opt %loadPolly -polly-opt-isl -polly-pattern-matching-based-opts=true -polly-target-througput-vector-fma=1 -polly-target-latency-vector-fma=8 -polly-target-cache-level-associativity=8,8 -polly-target-cache-level-sizes=32768,262144 -polly-optimized-scops < %s 2>&1 | FileCheck %s
 ;
 ;    /* C := alpha*A*B + beta*C */
 ;    for (i = 0; i < _PB_NI; i++)
 ;      for (j = 0; j < _PB_NJ; j++)
 ;        {
 ;    C[i][j] *= beta;
 ;    for (k = 0; k < _PB_NK; ++k)
 ;      C[i][j] += alpha * A[i][k] * B[k][j];
 ;        }
 ;
 ; CHECK:        double Packed_A[ { [] -> [(1024)] } ][ { [] -> [(4)] } ]; // Element size 8
 ; CHECK:        double Packed_B[ { [] -> [(3072)] } ][ { [] -> [(8)] } ]; // Element size 8
 ;
-; CHECK:                { Stmt_bb14[i0, i1, i2] -> MemRef_arg6[i0, i2] };
-; CHECK:           new: { Stmt_bb14[i0, i1, i2] -> Packed_A[o0, o1] : 256*floor((-i2 + o0)/256) = -i2 + o0 and 4*floor((-i0 + o1)/4) = -i0 + o1 and 0 <= o1 <= 3 and -3 + i0 - 16*floor((i0)/16) <= 4*floor((o0)/256) <= i0 - 16*floor((i0)/16) };
+; CHECK:                { Stmt_Copy_0[i0, i1, i2] -> MemRef_arg6[i0, i2] };
+; CHECK:           new: { Stmt_Copy_0[i0, i1, i2] -> Packed_A[o0, o1] : 256*floor((-i2 + o0)/256) = -i2 + o0 and 4*floor((-i0 + o1)/4) = -i0 + o1 and 0 <= o1 <= 3 and -3 + i0 - 16*floor((i0)/16) <= 4*floor((o0)/256) <= i0 - 16*floor((i0)/16) };
 ;
-; CHECK:                { Stmt_bb14[i0, i1, i2] -> MemRef_arg7[i2, i1] };
-; CHECK:           new: { Stmt_bb14[i0, i1, i2] -> Packed_B[o0, o1] : 256*floor((-i2 + o0)/256) = -i2 + o0 and 8*floor((-i1 + o1)/8) = -i1 + o1 and 0 <= o1 <= 7 and -7 + i1 - 96*floor((i1)/96) <= 8*floor((o0)/256) <= i1 - 96*floor((i1)/96) };
+; CHECK:                { Stmt_Copy_0[i0, i1, i2] -> MemRef_arg7[i2, i1] };
+; CHECK:           new: { Stmt_Copy_0[i0, i1, i2] -> Packed_B[o0, o1] : 256*floor((-i2 + o0)/256) = -i2 + o0 and 8*floor((-i1 + o1)/8) = -i1 + o1 and 0 <= o1 <= 7 and -7 + i1 - 96*floor((i1)/96) <= 8*floor((o0)/256) <= i1 - 96*floor((i1)/96) };
+;
+; CHECK:      CopyStmt_0
+; CHECK:            Domain :=
+; CHECK:                { CopyStmt_0[i0, i1, i2] : 0 <= i0 <= 1055 and 0 <= i1 <= 1055 and 0 <= i2 <= 1023 };
+; CHECK:            Schedule :=
+; CHECK:                ;
+; CHECK:            MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 0]
+; CHECK:                null;
+; CHECK:           new: { CopyStmt_0[i0, i1, i2] -> Packed_A[o0, o1] : 256*floor((-i2 + o0)/256) = -i2 + o0 and 4*floor((-i0 + o1)/4) = -i0 + o1 and 0 <= o1 <= 3 and -3 + i0 - 16*floor((i0)/16) <= 4*floor((o0)/256) <= i0 - 16*floor((i0)/16) };
+; CHECK:            ReadAccess := [Reduction Type: NONE] [Scalar: 0]
+; CHECK:                null;
+; CHECK:           new: { CopyStmt_0[i0, i1, i2] -> MemRef_arg6[i0, i2] };
+; CHECK:      CopyStmt_1
+; CHECK:            Domain :=
+; CHECK:                { CopyStmt_1[i0, i1, i2] : 0 <= i0 <= 1055 and 0 <= i1 <= 1055 and 0 <= i2 <= 1023 };
+; CHECK:            Schedule :=
+; CHECK:                ;
+; CHECK:            MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 0]
+; CHECK:                null;
+; CHECK:           new: { CopyStmt_1[i0, i1, i2] -> Packed_B[o0, o1] : 256*floor((-i2 + o0)/256) = -i2 + o0 and 8*floor((-i1 + o1)/8) = -i1 + o1 and 0 <= o1 <= 7 and -7 + i1 - 96*floor((i1)/96) <= 8*floor((o0)/256) <= i1 - 96*floor((i1)/96) };
+; CHECK:            ReadAccess := [Reduction Type: NONE] [Scalar: 0]
+; CHECK:                null;
+; CHECK:           new: { CopyStmt_1[i0, i1, i2] -> MemRef_arg7[i2, i1] };
 ;
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 target triple = "x86_64-unknown-unknown"
 
 define internal void @kernel_gemm(i32 %arg, i32 %arg1, i32 %arg2, double %arg3, double %arg4, [1056 x double]* %arg5, [1024 x double]* %arg6, [1056 x double]* %arg7) #0 {
 bb:
   br label %bb8
 
 bb8:                                              ; preds = %bb29, %bb
   %tmp = phi i64 [ 0, %bb ], [ %tmp30, %bb29 ]
   br label %bb9
 
 bb9:                                              ; preds = %bb26, %bb8
   %tmp10 = phi i64 [ 0, %bb8 ], [ %tmp27, %bb26 ]
   %tmp11 = getelementptr inbounds [1056 x double], [1056 x double]* %arg5, i64 %tmp, i64 %tmp10
   %tmp12 = load double, double* %tmp11, align 8
   %tmp13 = fmul double %tmp12, %arg4
   store double %tmp13, double* %tmp11, align 8
-  br label %bb14
+  br label %Copy_0
 
-bb14:                                             ; preds = %bb14, %bb9
-  %tmp15 = phi i64 [ 0, %bb9 ], [ %tmp24, %bb14 ]
+Copy_0:                                             ; preds = %Copy_0, %bb9
+  %tmp15 = phi i64 [ 0, %bb9 ], [ %tmp24, %Copy_0 ]
   %tmp16 = getelementptr inbounds [1024 x double], [1024 x double]* %arg6, i64 %tmp, i64 %tmp15
   %tmp17 = load double, double* %tmp16, align 8
   %tmp18 = fmul double %tmp17, %arg3
   %tmp19 = getelementptr inbounds [1056 x double], [1056 x double]* %arg7, i64 %tmp15, i64 %tmp10
   %tmp20 = load double, double* %tmp19, align 8
   %tmp21 = fmul double %tmp18, %tmp20
   %tmp22 = load double, double* %tmp11, align 8
   %tmp23 = fadd double %tmp22, %tmp21
   store double %tmp23, double* %tmp11, align 8
   %tmp24 = add nuw nsw i64 %tmp15, 1
   %tmp25 = icmp ne i64 %tmp24, 1024
-  br i1 %tmp25, label %bb14, label %bb26
+  br i1 %tmp25, label %Copy_0, label %bb26
 
-bb26:                                             ; preds = %bb14
+bb26:                                             ; preds = %Copy_0
   %tmp27 = add nuw nsw i64 %tmp10, 1
   %tmp28 = icmp ne i64 %tmp27, 1056
   br i1 %tmp28, label %bb9, label %bb29
 
 bb29:                                             ; preds = %bb26
   %tmp30 = add nuw nsw i64 %tmp, 1
   %tmp31 = icmp ne i64 %tmp30, 1056
   br i1 %tmp31, label %bb8, label %bb32
 
 bb32:                                             ; preds = %bb29
   ret void
 }
 
 attributes #0 = { nounwind uwtable "target-cpu"="x86-64" "target-features"="+aes,+avx,+cmov,+cx16,+fxsr,+mmx,+pclmul,+popcnt,+sse,+sse2,+sse3,+sse4.1,+sse4.2,+ssse3,+x87,+xsave,+xsaveopt" }