[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

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

include/polly/CodeGen/IslNodeBuilder.h

380–381

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

1465–1499

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.

1490

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

783

Why does this delete Stmt?

801

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

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

include/polly/CodeGen/IslNodeBuilder.h

380–381

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

1465–1499

OK.

1490

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

783

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.

801

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

[Meinersbur]

include/polly/CodeGen/IslExprBuilder.h

169

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

lib/Analysis/ScopInfo.cpp

1490

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

783

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(); 
}

801

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

lib/Transform/ScheduleOptimizer.cpp

658

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

688

@brief

697

@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

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

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

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

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

@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

@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

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

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

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

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

where

1202

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

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

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

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

1202

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

Drop the 'of'

175

that has -> of

lib/Transform/ScheduleOptimizer.cpp

1202

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

2309

Unnecessary line break.

2341

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

1469

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

1014

that make

[gareevroman]

A new version updated according to the comments.

[gareevroman]

Hi Tobias,

thanks for the comments and review!

lib/Analysis/ScopInfo.cpp

1469

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

include/polly/CodeGen/IslExprBuilder.h

public:
 
   /// @brief 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;
 
+  /// @brief Create LLVM-IR for an isl_ast_expr[ession] that has type
+  ///        isl_ast_op_access.
+  ///
+  /// @param Expr The ast expression that has 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;
 
   /// @brief 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);
 
   /// @brief 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.
   ///

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:
+  /// @brief Read a value specified by the read access and store into a location
+  /// specified by the write access.
+  ///
+  /// @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

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);
+
+  /// @brief 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();
 
   /// @brief 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);
 
+  /// @brief 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 BasicBlock represented by this ScopStmt, or null if the
   ///         statement represents a region.
   BasicBlock *getBasicBlock() const { return BB; }
 
   /// @brief Return true if this statement represents a single basic block.
   bool isBlockStmt() const { return BB != nullptr; }
 
+  /// @brief Return true if this is a copy statement.
+  bool isCopyStmt() const { return BB == nullptr && R == nullptr; }
+
   /// @brief 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; }
 
   /// @brief Return true if this statement represents a whole region.
   bool isRegionStmt() const { return R != nullptr; }
private:
   ValueToValueMap InvEquivClassVMap;
 
   /// @brief List of invariant accesses.
   InvariantEquivClassesTy InvariantEquivClasses;
 
   /// @brief Scop constructor; invoked from ScopBuilder::buildScop.
   Scop(Region &R, ScalarEvolution &SE, LoopInfo &LI,
        ScopDetection::DetectionContext &DC);
-
-  /// @brief Get or create the access function set in a BasicBlock
-  AccFuncSetType &getOrCreateAccessFunctions(const BasicBlock *BB) {
-    return AccFuncMap[BB];
-  }
   //@}
 
   /// @brief Initialize this ScopBuilder.
   void init(AliasAnalysis &AA, AssumptionCache &AC, DominatorTree &DT,
             LoopInfo &LI);
 
   /// @brief Propagate domains that are known due to graph properties.
   ///
private:
   void printAliasAssumptions(raw_ostream &OS) const;
   //@}
 
   friend class ScopBuilder;
 
 public:
   ~Scop();
 
+  /// @brief Get or create the access function set in a BasicBlock
+  AccFuncSetType &getOrCreateAccessFunctions(const BasicBlock *BB) {
+    return AccFuncMap[BB];
+  }
+
   /// @brief Get all access functions in a BasicBlock
   ///
   /// @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);
public:
 
   /// @brief Get a union map of all memory accesses performed in the SCoP.
   __isl_give isl_union_map *getAccesses();
 
   /// @brief Get the schedule of all the statements in the SCoP.
   __isl_give isl_union_map *getSchedule() const;
 
   /// @brief Get a schedule tree describing the schedule of all statements.
   __isl_give isl_schedule *getScheduleTree() const;
 
   /// @brief Update the current schedule
   ///
   /// @brief NewSchedule The new schedule (given as a flat union-map).
   void setSchedule(__isl_take isl_union_map *NewSchedule);
 
   /// @brief Update the current schedule
   ///
public:
 
   /// @brief Find the ScopArrayInfo associated with an isl Id
   ///        that has name @p Name.
   ScopArrayInfo *getArrayInfoByName(const std::string BaseName);
 };
 
 /// @brief Print Scop scop to raw_ostream O.
 static inline raw_ostream &operator<<(raw_ostream &O, const Scop &scop) {
   scop.print(O);
   return O;
 }
 
 /// @brief The legacy pass manager's analysis pass to compute scop information
 ///        for a region.
 class ScopInfoRegionPass : public RegionPass {
   /// @brief The Scop pointer which is used to construct a Scop.
   std::unique_ptr<Scop> S;

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());

 
 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("Stmt_Copy", "", "");
+  auto *Id = isl_id_alloc(getIslCtx(), getBaseName(), this);
+  Domain = isl_set_set_tuple_id(Domain, isl_id_copy(Id));
+  SourceRel = isl_map_set_tuple_id(SourceRel, isl_dim_in, isl_id_copy(Id));
+  AccFuncSetType &AccList = parent.getOrCreateAccessFunctions(nullptr);
+  AccList.emplace_back(this, MemoryAccess::AccessType::READ, SourceRel);
+  addAccess(&AccList.back());
+  TargetRel = isl_map_set_tuple_id(TargetRel, isl_dim_in, Id);
+  AccList.emplace_back(this, MemoryAccess::AccessType::MUST_WRITE, TargetRel);
+  addAccess(&AccList.back());
+}
+
 void ScopStmt::init(LoopInfo &LI) {
   assert(!Domain && "init must be called only once");
 
   buildDomain();
   collectSurroundingLoops();
   buildAccessRelations();
 
   deriveAssumptions(LI);
 
   if (DetectReductions)
     checkForReductions();
 }
 
 /// @brief Collect loads which might form a reduction chain with @p StoreMA
 ///
 /// Check if the stored value for @p StoreMA is a binary operator with one or
 /// two loads as operands. If the binary operand is commutative & associative,
 /// used only once (by @p StoreMA) and its load operands are also used only
 /// once, we have found a possible reduction chain. It starts at an operand
 /// load and includes the binary operator and @p StoreMA.
 ///
 /// Note: We allow only one use to ensure the load and binary operator cannot
 ///       escape this block or into any other store except @p StoreMA.
 void ScopStmt::collectCandiateReductionLoads(
     MemoryAccess *StoreMA, SmallVectorImpl<MemoryAccess *> &Loads) {
   auto *Store = dyn_cast<StoreInst>(StoreMA->getAccessInstruction());
   if (!Store)

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) {
+  Value *LoadValue;
+  Value *StoreAddr;
+  for (auto *MemA : *Stmt) {
+    isl_ast_expr *AccessExpr =
+        isl_id_to_ast_expr_get(NewAccesses, MemA->getId());
+    if (MemA->isRead())
+      LoadValue = ExprBuilder.create(AccessExpr);
+    else
+      StoreAddr = ExprBuilder.createAccessAddress(AccessExpr);
+  }
+  Builder.CreateStore(LoadValue, StoreAddr);
+  delete Stmt;
+}
+
 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);

lib/Transform/ScheduleOptimizer.cpp

if (isl_map_is_equal(ExpectedAccessRelation, AccessRelation)) {
       IdentifiedAccess = Access;
     }
     isl_map_free(AccessRelation);
   }
   isl_map_free(ExpectedAccessRelation);
   return IdentifiedAccess;
 }
 
 /// @brief 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.
 /// @param I The index of the input dimension that is mapped to the first output

 
 /// @brief Identify the memory access that corresponds to the access
 ///        to the second operand of the matrix multiplication.
 ///
 /// Identify the memory access that corresponds to the access
 /// to the matrix B of the matrix multiplication C = A x B.
 ///
 /// @param Stmt The SCoP statement that contains the memory accesses
 ///             under consideration.
 /// @return The memory access of @p Stmt that corresponds to the access
 ///         to the second operand of the matrix multiplication.
 MemoryAccess *identifyAccessA(ScopStmt *Stmt) {
   auto *OriginalRel = getMatMulPatternOriginalAccessRelation(Stmt, 0, 2);
   return identifyAccessByAccessRelation(Stmt, OriginalRel);
 }
 
 /// @brief Identify the memory access that corresponds to the access
 ///        to the first operand of the matrix multiplication.
 ///
 /// Identify the memory access that corresponds to the access
 /// to the matrix A of the matrix multiplication C = A x B.
 ///
 /// @param Stmt The SCoP statement that contains the memory accesses
 ///             under consideration.
 /// @return The memory access of @p Stmt that corresponds to the access
 ///         to the first operand of the matrix multiplication.
 MemoryAccess *identifyAccessB(ScopStmt *Stmt) {
   auto *OriginalRel = getMatMulPatternOriginalAccessRelation(Stmt, 2, 1);
   return identifyAccessByAccessRelation(Stmt, OriginalRel);
 }
 
+/// @brief 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,
+/// wehere 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);
+}
+
+/// @brief  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;
+}
+
 /// @brief Create an access relation that is specific to
 ///        the matrix multiplication pattern.
 ///
 /// Create an access relation of the following form:
 /// [O0, O1, O2, O3, O4, O5, O6, O7, O8] -> [0, O5 + K * OI, OJ],
 /// where K is @p Coeff, I is @p FirstDim, J is @p SecondDim.
 ///
 /// It can be used, for example, to create relations that helps to consequently
__isl_give isl_map *getMatMulAccRel(__isl_take isl_map *MapOldIndVar,
   Constr =
       isl_constraint_set_coefficient_si(Constr, isl_dim_in, FirstDim, Coeff);
   AccessRel = isl_map_add_constraint(AccessRel, Constr);
   AccessRel = isl_map_fix_si(AccessRel, isl_dim_out, 0, 0);
   AccessRel = isl_map_equate(AccessRel, isl_dim_in, SecondDim, isl_dim_out, 2);
   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);
+}
+
 /// @brief 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 =
+      new ScopStmt(*(Stmt->getParent()), 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 = new ScopStmt(*(Stmt->getParent()), 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);
 }
 
 /// @brief 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) {
bool ScheduleTreeOptimizer::isProfitableSchedule(
   // 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)
   isl_union_map *OldSchedule = S.getSchedule();
   bool changed = !isl_union_map_is_equal(OldSchedule, NewSchedule);
   isl_union_map_free(OldSchedule);
   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);
+  /* isl_union_map *NewScheduleMap = isl_schedule_get_map(NewSchedule);
 
   if (!ScheduleTreeOptimizer::isProfitableSchedule(S, NewScheduleMap)) {
     isl_union_map_free(NewScheduleMap);
     isl_schedule_free(NewSchedule);
     return false;
-  }
+  } */
 
   S.setScheduleTree(NewSchedule);
   S.markAsOptimized();
 
-  isl_union_map_free(NewScheduleMap);
+  // isl_union_map_free(NewScheduleMap);
   return false;
 }
 
 void IslScheduleOptimizer::printScop(raw_ostream &OS, Scop &) const {
   isl_printer *p;
   char *ScheduleStr;
 
   OS << "Calculated schedule:\n";

test/Isl/CodeGen/MemAccess/mat_mul_pattern_data_layout.ll

 ;
 ; CHECK: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 {
 ; CHECK:bb:
 ; CHECK:  %arg3.s2a = alloca double
 ; CHECK:  %arg4.s2a = alloca double
 ; CHECK:  %Packed_A = alloca [1024 x [4 x double]]
 ; CHECK:  %Packed_B = alloca [3072 x [8 x double]]
 ; CHECK:  br label %polly.split_new_and_old
 ;
-; CHECK:polly.stmt.bb14398:                               ; preds = %polly.stmt.bb14379
-; CHECK:  %arg3.s2a.reload399 = load double, double* %arg3.s2a
-; CHECK:  %polly.access.cast.Packed_A400 = bitcast [1024 x [4 x double]]* %Packed_A to double*
-; CHECK:  %243 = mul nsw i64 256, %polly.indvar95
-; CHECK:  %244 = add nsw i64 %243, %polly.indvar107
-; CHECK:  %polly.access.add.Packed_A401 = add nsw i64 0, %244
-; CHECK:  %polly.access.mul.Packed_A402 = mul nsw i64 %polly.access.add.Packed_A401, 4
-; CHECK:  %polly.access.add.Packed_A403 = add nsw i64 %polly.access.mul.Packed_A402, 2
-; CHECK:  %polly.access.Packed_A404 = getelementptr double, double* %polly.access.cast.Packed_A400, i64 %polly.access.add.Packed_A403
-; CHECK:  %tmp17_p_scalar_405 = load double, double* %polly.access.Packed_A404, align 8
-; CHECK:  %p_tmp18406 = fmul double %tmp17_p_scalar_405, %arg3.s2a.reload399
-; CHECK:  %polly.access.cast.Packed_B407 = bitcast [3072 x [8 x double]]* %Packed_B to double*
-; CHECK  %245 = mul nsw i64 256, %polly.indvar101
-; CHECK  %246 = add nsw i64 %245, %polly.indvar107
-; CHECK  %polly.access.add.Packed_B408 = add nsw i64 0, %246
-; CHECK  %polly.access.mul.Packed_B409 = mul nsw i64 %polly.access.add.Packed_B408, 8
-; CHECK  %polly.access.add.Packed_B410 = add nsw i64 %polly.access.mul.Packed_B409, 0
+; CHECK:  %polly.access.cast.arg6101 = bitcast [1024 x double]* %arg6 to double*
+; CHECK:  %polly.access.mul.arg6102 = mul nsw i64 %polly.indvar89, 1024
+; CHECK:  %polly.access.add.arg6103 = add nsw i64 %polly.access.mul.arg6102, %polly.indvar97
+; CHECK:  %polly.access.arg6104 = getelementptr double, double* %polly.access.cast.arg6101, i64 %polly.access.add.arg6103
+; CHECK:  %polly.access.arg6104.load = load double, double* %polly.access.arg6104
+; CHECK:  %polly.access.cast.Packed_A = bitcast [1024 x [4 x double]]* %Packed_A to double*
+; CHECK:  %26 = add nsw i64 %polly.indvar89, 4
+; CHECK:  %pexp.pdiv_r = urem i64 %26, 4
+; CHECK:  %27 = mul nsw i64 64, %pexp.pdiv_r
+; CHECK:  %28 = sub nsw i64 0, %27
+; CHECK:  %29 = mul nsw i64 1024, %polly.indvar77
+; CHECK:  %30 = sub nsw i64 %28, %29
+; CHECK:  %31 = mul nsw i64 256, %polly.indvar83
+; CHECK:  %32 = sub nsw i64 %30, %31
+; CHECK:  %33 = mul nsw i64 64, %polly.indvar89
+; CHECK:  %34 = add nsw i64 %32, %33
+; CHECK:  %35 = add nsw i64 %34, %polly.indvar97
+; CHECK:  %polly.access.add.Packed_A = add nsw i64 0, %35
+; CHECK:  %polly.access.mul.Packed_A = mul nsw i64 %polly.access.add.Packed_A, 4
+; CHECK:  %36 = add nsw i64 %polly.indvar89, 4
+; CHECK:  %pexp.pdiv_r105 = urem i64 %36, 4
+; CHECK:  %polly.access.add.Packed_A106 = add nsw i64 %polly.access.mul.Packed_A, %pexp.pdiv_r105
+; CHECK:  %polly.access.Packed_A = getelementptr double, double* %polly.access.cast.Packed_A, i64 %polly.access.add.Packed_A106
+; CHECK:  store double %polly.access.arg6104.load, double* %polly.access.Packed_A
+;
+; CHECK:polly.stmt.bb14:                                  ; preds = %polly.loop_header150
+; CHECK  %arg3.s2a.reload = load double, double* %arg3.s2a
+; CHECK  %polly.access.cast.Packed_A156 = bitcast [1024 x [4 x double]]* %Packed_A to double*
+; CHECK  %62 = mul nsw i64 256, %polly.indvar141
+; CHECK  %63 = add nsw i64 %62, %polly.indvar153
+; CHECK  %polly.access.add.Packed_A157 = add nsw i64 0, %63
+; CHECK  %polly.access.mul.Packed_A158 = mul nsw i64 %polly.access.add.Packed_A157, 4
+; CHECK  %polly.access.add.Packed_A159 = add nsw i64 %polly.access.mul.Packed_A158, 0
+; CHECK  %polly.access.Packed_A160 = getelementptr double, double* %polly.access.cast.Packed_A156, i64 %polly.access.add.Packed_A159
+; CHECK  %tmp17_p_scalar_ = load double, double* %polly.access.Packed_A160, align 8
+; CHECK  %p_tmp18 = fmul double %tmp17_p_scalar_, %arg3.s2a.reload
+; CHECK  %polly.access.cast.Packed_B161 = bitcast [3072 x [8 x double]]* %Packed_B to double*
+; CHECK  %64 = mul nsw i64 256, %polly.indvar147
+; CHECK  %65 = add nsw i64 %64, %polly.indvar153
+; CHECK  %polly.access.add.Packed_B162 = add nsw i64 0, %65
+; CHECK  %polly.access.mul.Packed_B163 = mul nsw i64 %polly.access.add.Packed_B162, 8
+; CHECK  %polly.access.add.Packed_B164 = add nsw i64 %polly.access.mul.Packed_B163, 0
 ;
 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