[Polly][DeLICM] Known knowledge.

[Meinersbur]

Summary

Extend the Knowledge class to store information about the contents of array elements and which values are written. Two knowledges do not conflict the known content is the same. The content information if computed from writes to and loads from the array elements, and represented by "ValInst": isl spaces that compare equal if the value represented is the same.

This patch contains changes that I try to commit independently (introduction of distributeDomain/removal of AllElements, VirtualUse(?)).

[Meinersbur]

• Rebase to r298543
• Add switch to disable known information

[Meinersbur]

• Rebase to r298546
• Removed/activate commented code.

[Meinersbur]

• Remove spurious semicolon

[grosser]

Hi Michael,

thank you for pushing this forward. This is again a pretty large patch, even though the kind of different changes are now a lot smaller. Still, for proper and timely review, it would really help to get these patches smaller and upstream as much as possible independently. I did a first round over this patch, and trying to understand which parts are needed to get the tests working that you contributed. It seems indeed that e.g. VirtualUse is not really needed and to my surprise also the computeKnownFromWrite / computeKnownFromRead functions do not seem to be needed. At least all test cases pass even when I just return an empty known set. Did I make some wrong assumptions or is this functionality not tested and can be added later together with the corresponding test cases. (I stop now my review, to get first some feedback from you).

Best,
Tobias

include/polly/ScopInfo.h

1334

This can probably be committed separately and directly be used and tested in RegionGenerator::addOperandToPHI. No further review needed for this.

include/polly/Support/VirtualInstruction.h

38

An -> A

lib/Transform/DeLICM.cpp

391

This move also not seem to be needed without VirtualUse.

859

Not needed without VirtualUse?

896

Not needed without virtual use?

1204

Grammar: "look get"

1207

I prefer comments to be aligned to the start of the first line (otherwise they mix with the parameters).

1231

The only case currently tested seems to be VirtualUse::Constant. If I add a "break" at the beginning of each other case, all tests still pass as expected. Maybe we can first introduce the constant case, without virtual use and then look again at the virtual use?

1233

on the

1932

If I revert this change and use the original getInputAccessOf function, all tests still pass. This and the use where we check for Val to be a constant are the only uses of VirtualUse. If we drop them, this patch would become more targeted.

2008–2050

If I add return makeEmptyUnionMap(); all tests still pass.

2021

If I add return makeEmptyUnionMap(); all tests still pass.

2108

Not needed without virtual Statement.

2241

Not needed without VirtualStmt.

2261

Not needed without VirtualStmt.

unittests/DeLICM/DeLICMTest.cpp

127

I assume we do not need this commented code to be committed.

[Meinersbur]

In D31247#708641, @grosser wrote:

thank you for pushing this forward. This is again a pretty large patch, even though the kind of different changes are now a lot smaller. Still, for proper and timely review, it would really help to get these patches smaller and upstream as much as possible independently. I did a first round over this patch, and trying to understand which parts are needed to get the tests working that you contributed. It seems indeed that e.g. VirtualUse is not really needed

See inline comment.

and to my surprise also the computeKnownFromWrite / computeKnownFromRead functions do not seem to be needed.

That was my laziness by making minimal changes to the reduction.ll test case to make it work. By doing this, only a particular kind of conflict occurs, namely conflicts with previously mapped values. This is not typical for GVE PRE-optimized code. I'll come up with better ones with the next update.

Michael

include/polly/Support/VirtualInstruction.h

38

It is pronounced "El El Vee Em", hence the article is correct.

Also compare
https://www.google.com/search?q="An+LLVM"
vs
https://www.google.com/search?q="A+LLVM"

lib/Transform/DeLICM.cpp

1231

You may have missed that the "VirtualUse::InterValue" case breaks as well because it is the longest and "main" case, to avoid handling it in a switch case. All other cases return, that is, for the two test cases we need to distinguish at least these two and if its none of them (to return "value unknown"), makes three cases.

The other cases are not that interesting, so no test case for those yet. It doesn't come up because the test cases were crafted that way. For instance, VirtualUse::IntraValue never occurs because there are never two instructions depending on each other in a single basic block. The same computational pattern is employed with only one instruction, so the test case uses the smaller one.

[Meinersbur]

• Not all synthesizable values are affine (e.g. undef)
• Not all affine values are synthezizable (e.g. load-hoisted values)
• Addresses some of Tobias' comments.
• More test cases.
• Remove computeKnownFromRead, seems not to be useful here.

Note this currently miscompiles External\SPEC\CINT2006\401.bzip2, looking into it.

[Meinersbur]

401.bzip2 fails even without its patch, look similar to http://llvm.org/PR32251 .

[grosser]

Hi Michael,

thanks for upstreaming already so much of this patch. I believe after this patch is rebased onto trunk, the diff should be small enough to review it as a whole.

Best,
Tobias

include/polly/Support/VirtualInstruction.h

38

You are right

[Meinersbur]

Rebase to r302234

[grosser]

Hi Michael,

this looks good to me. I just have a couple of minor typos. I also tried this of some of the polybench kernels, but it seems not yet enough to make them really faster. The one thing we need for a simple gemm kernel is -polly-delicm-overapproximate-writes=true, the second is an option to remove redundant writes. I assume these will be handled in later changes, so no need to block this patch.

Best,
Tobias

lib/Transform/DeLICM.cpp

119

A synthesizable

1361

uses.

1394

no need for comma here.

test/DeLICM/reduction_looprotate.ll

13 ↗

(On Diff #97972)

to DO in

[Meinersbur]

In D31247#747634, @grosser wrote:

Hi Michael,

this looks good to me. I just have a couple of minor typos. I also tried this of some of the polybench kernels, but it seems not yet enough to make them really faster. The one thing we need for a simple gemm kernel is -polly-delicm-overapproximate-writes=true, the second is an option to remove redundant writes. I assume these will be handled in later changes, so no need to block this patch.

For really being effective, we also need partial writes (MemoryAccesses that do not write in an entire's statement domain). This makes -polly-delicm-overapproximate-writes=true kind of redundant.

Depending on the benchmark, an extension determining that a PHINode is identical to one of their incoming values could be useful as well.

About the redundant writes, I still have to think about to do it correctly. the PHINode extension could be helpful.

[grosser]

Cool. Maybe let's pull out this discussion from the review thread to the ML. This seems to be go beyond what this patch coveres.

include/polly/DeLICM.h

 namespace polly {
 /// Create a new DeLICM pass instance.
 llvm::Pass *createDeLICMPass();
 
 /// Determine whether two lifetimes are conflicting.
 ///
 /// Used by unittesting.
 bool isConflicting(isl::union_set ExistingOccupied,
-                   isl::union_set ExistingUnused, isl::union_set ExistingWrites,
+                   isl::union_set ExistingUnused, isl::union_map ExistingKnown,
+                   isl::union_map ExistingWrites,
                    isl::union_set ProposedOccupied,
-                   isl::union_set ProposedUnused, isl::union_set ProposedWrites,
+                   isl::union_set ProposedUnused, isl::union_map ProposedKnown,
+                   isl::union_map ProposedWrites,
                    llvm::raw_ostream *OS = nullptr, unsigned Indent = 0);
 } // namespace polly
 
 namespace llvm {
 void initializeDeLICMPass(llvm::PassRegistry &);
 } // namespace llvm
 
 #endif /* POLLY_DELICM_H */

include/polly/ScopInfo.h

public:
   bool contains(const Loop *L) const {
     // Block statements never contain loops.
     if (isBlockStmt())
       return false;
 
     return getRegion()->contains(L);
   }
 
+  /// Return whether this statement contains @p BB.
+  bool contains(BasicBlock *BB) const {
+    if (isCopyStmt())
+      return false;
+    if (isBlockStmt())
+      return BB == getBasicBlock();
+    return getRegion()->contains(BB);
+  }
+
   /// Return the closest innermost loop that contains this statement, but is not
   /// contained in it.
   ///
   /// For block statement, this is just the loop that contains the block. Region
   /// statements can contain boxed loops, so getting the loop of one of the
   /// region's BBs might return such an inner loop. For instance, the region's
   /// entry could be a header of a loop, but the region might extend to BBs
   /// after the loop exit. Similarly, the region might only contain parts of the

include/polly/Support/ISLTools.h

 /// @param Amount The offset to add to the specified dimension.
 ///
 /// @return The modified set.
 isl::set shiftDim(isl::set Set, int Pos, int Amount);
 
 /// Piecewise shiftDim(isl::set,int,int).
 isl::union_set shiftDim(isl::union_set USet, int Pos, int Amount);
 
+/// Add a constant to one dimension of a map.
+///
+/// @param Map    The map to shift a dimension in.
+/// @param Type   A tuple of @p Map which contains the dimension to shift.
+/// @param Pos    The dimension to shift. If negative, the dimensions are
+/// counted from the end instead from the beginning. Eg. -1 is the last
+/// dimension in the tuple.
+/// @param Amount The offset to add to the specified dimension.
+///
+/// @return The modified map.
+isl::map shiftDim(isl::map Map, isl::dim Dim, int Pos, int Amount);
+
+/// Add a constant to one dimension of a each map in a union map.
+///
+/// @param UMap   The maps to shift a dimension in.
+/// @param Type   The tuple which contains the dimension to shift.
+/// @param Pos    The dimension to shift. If negative, the dimensions are
+///               counted from the ends of each map of union instead from their
+///               beginning. E.g. -1 is the last dimension of any map.
+/// @param Amount The offset to add to the specified dimension.
+///
+/// @return The union of all modified maps.
+isl::union_map shiftDim(isl::union_map UMap, isl::dim Dim, int Pos, int Amount);
+
 /// Simplify a set inplace.
 void simplify(isl::set &Set);
 
 /// Simplify a union set inplace.
 void simplify(isl::union_set &USet);
 
 /// Simplify a map inplace.
 void simplify(isl::map &Map);

 ///
 /// @param Zone      { Zone[] }
 /// @param InclStart Include timepoints adjacent to the beginning of a zone.
 /// @param InclEnd   Include timepoints adjacent to the ending of a zone.
 ///
 /// @return { Scatter[] }
 isl::union_set convertZoneToTimepoints(isl::union_set Zone, bool InclStart,
                                        bool InclEnd);
+
+/// Like convertZoneToTimepoints(isl::union_set,InclStart,InclEnd), but convert
+/// either the domain or the range of a map.
+isl::union_map convertZoneToTimepoints(isl::union_map Zone, isl::dim Dim,
+                                       bool InclStart, bool InclEnd);
+
+/// Distribute the domain to the tuples of a wrapped range map.
+///
+/// @param Map { Domain[] -> [Range1[] -> Range2[]] }
+///
+/// @return { [Domain[] -> Range1[]] -> [Domain[] -> Range2[]] }
+isl::map distributeDomain(isl::map Map);
+
+/// Apply distributeDomain(isl::map) to each map in the union.
+isl::union_map distributeDomain(isl::union_map UMap);
+
+/// Prepend a space to the tuples of a map.
+///
+/// @param UMap   { Domain[] -> Range[] }
+/// @param Factor { Factor[] }
+///
+/// @return { [Factor[] -> Domain[]] -> [Factor[] -> Range[]] }
+isl::union_map liftDomains(isl::union_map UMap, isl::union_set Factor);
+
+/// Apply a map to the 'middle' of another relation.
+///
+/// @param UMap { [DomainDomain[] -> DomainRange[]] -> Range[] }
+/// @param Func { DomainRange[] -> NewDomainRange[] }
+///
+/// @return { [DomainDomain[] -> NewDomainRange[]] -> Range[] }
+isl::union_map applyDomainRange(isl::union_map UMap, isl::union_map Func);
 } // namespace polly
 
 #endif /* POLLY_ISLTOOLS_H */

include/polly/Support/VirtualInstruction.h

+//===------ VirtualInstruction.cpp ------------------------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// Tools for determining which instructions are within a statement and the
+// nature of their operands.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef POLLY_SUPPORT_VIRTUALINSTRUCTION_H
+#define POLLY_SUPPORT_VIRTUALINSTRUCTION_H
+
+#include "polly/ScopInfo.h"
+
+namespace polly {
+
+/// Determine the nature of a value's use within a statement.
+///
+/// These are not always representable by llvm::Use. For instance, scalar write
+/// MemoryAccesses do use a value, but are not associated to an instruction's
+/// argument.
+///
+/// Despite its name it is not tied to virtual instructions (although it works
+/// fine with them), but to promote consistent handling of values used in
+/// statements.
+class VirtualUse {
+public:
+  /// The different types of uses. Handling usually differentiates a lot between
+  /// these; one can use a switch to handle each case (and get warned by the
+  /// compiler if one is not handled).
+  enum UseType {
+    // An llvm::Constant.
+    Constant,
+
+    // Parameters, induction variables and affine expressions of those.
+    Synthesizable,
+
+    // Definition before the SCoP and not synthesizable. Can be an instruction
+    // outside the SCoP, a function argument or a global value. Whether there is
+    // a scalar MemoryAccess in this statement for reading it depends on the
+    // -polly-analyze-read-only-scalars switch.
+    ReadOnly,
+
+    // Definition within this statement. No MemoryAccess between them necessary.
+    IntraValue,
+
+    // Definition in another statement. There is a scalar MemoryAccess that
+    // makes it available in this statement.
+    InterValue
+  };
+
+private:
+  /// The statement where a value is used.
+  ScopStmt *User;
+
+  /// The value that is used.
+  Value *Val;
+
+  /// The type of value use.
+  UseType Ty;
+
+  /// If this is an inter-statement (or read-only) use, contains the
+  /// MemoryAccess that makes the value available in this statement. In case of
+  /// intra-statement uses, can contain an MemoryKind::Array access. In all
+  /// other cases, it is a nullptr.
+  MemoryAccess *InputMA;
+
+  VirtualUse(ScopStmt *User, Value *Val, UseType Ty, MemoryAccess *InputMA)
+      : User(User), Val(Val), Ty(Ty), InputMA(InputMA) {}
+
+public:
+  /// Get a VirtualUse for an llvm::Use.
+  ///
+  /// @param S  The Scop object.
+  /// @param U  The llvm::Use the get information for.
+  /// @param LI The LoopInfo analysis. Needed to determine whether the value us
+  /// synthesizable.
+  ///
+  /// @return The VirtualUse representing the same use as @p U.
+  static VirtualUse create(Scop *S, Use &U, LoopInfo *LI);
+
+  /// Get a VirtualUse for an llvm::Use. Prefer this constructor if the user
+  /// statement is already known.
+  static VirtualUse create(ScopStmt *UserStmt, Use &U, LoopInfo *LI);
+
+  /// Get a VirtualUse for any kind use of a value within a statement.
+  ///
+  /// @param UserStmt       The statement in which @p Val is used.
+  /// @param IsEntryPHIUser Whether the user is a PHINode in the statement's
+  /// entry block. If True, this use can only be an intra-statement use if @p
+  /// UserStmt is a region statement. Block statements do not include a
+  /// loop-backedge, such that it will use the value of a previous iteration,
+  /// not the value of the current iteration.
+  /// @param UserScope      Loop scope in which the value is used. Needed to
+  /// determine whether the value us synthesizable.
+  /// @param Val            The value being used.
+  ///
+  /// @return A VirtualUse object that gives information about @p Val's use in
+  /// @p UserStmt.
+  static VirtualUse create(ScopStmt *UserStmt, bool IsEntryPHIUser,
+                           Loop *UserScope, Value *Val);
+
+  bool isConstant() const { return Ty == Constant; }
+  bool isSynthesizable() const { return Ty == Synthesizable; }
+  bool isReadOnly() const { return Ty == ReadOnly; }
+  bool isIntra() const { return Ty == IntraValue; }
+  bool isInter() const { return Ty == InterValue; }
+
+  /// Return user statement.
+  ScopStmt *getUser() const { return User; }
+
+  /// Return the used value.
+  llvm::Value *getValue() const { return Val; }
+
+  /// Return the type of use.
+  UseType getType() const { return Ty; }
+
+  /// Return the MemoryAccess that makes the value available in this statement,
+  /// if any.
+  MemoryAccess *getMemAccess() const { return InputMA; }
+
+  void print(raw_ostream &OS) const;
+#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
+  void dump() const;
+#endif
+};
+
+} // namespace polly
+
+#endif /* POLLY_SUPPORT_VIRTUALINSTRUCTION_H */

lib/CMakeLists.txt

add_polly_library(Polly
   Transform/Canonicalization.cpp
   Transform/CodePreparation.cpp
   Transform/DeadCodeElimination.cpp
   Transform/ScheduleOptimizer.cpp
   Transform/FlattenSchedule.cpp
   Transform/FlattenAlgo.cpp
   Transform/DeLICM.cpp
   Transform/Simplify.cpp
+  Support/VirtualInstruction.cpp
   ${POLLY_HEADER_FILES}
   )
 
 if (GPU_CODEGEN)
   target_link_libraries(Polly PollyPPCG)
 endif (GPU_CODEGEN)
 
 target_link_libraries(Polly ${ISL_TARGET})

lib/Support/GICHelper.cpp

static void replace(std::string &str, const std::string &find,
   }
 }
 
 static void makeIslCompatible(std::string &str) {
   replace(str, ".", "_");
   replace(str, "\"", "_");
   replace(str, " ", "__");
   replace(str, "=>", "TO");
+  replace(str, "+", "_");
 }
 
 std::string polly::getIslCompatibleName(const std::string &Prefix,
                                         const std::string &Middle,
                                         const std::string &Suffix) {
   std::string S = Prefix + Middle + Suffix;
   makeIslCompatible(S);
   return S;

lib/Support/ISLTools.cpp

isl::union_set polly::shiftDim(isl::union_set USet, int Pos, int Amount) {
   auto Result = give(isl_union_set_empty(isl_union_set_get_space(USet.keep())));
   foreachElt(USet, [=, &Result](isl::set Set) {
     auto Shifted = shiftDim(Set, Pos, Amount);
     Result = give(isl_union_set_add_set(Result.take(), Shifted.take()));
   });
   return Result;
 }
 
+isl::map polly::shiftDim(isl::map Map, isl::dim Dim, int Pos, int Amount) {
+  int NumDims = Map.dim(Dim);
+  if (Pos < 0)
+    Pos = NumDims + Pos;
+  assert(Pos < NumDims && "Dimension index must be in range");
+  auto Space = give(isl_map_get_space(Map.keep()));
+  switch (Dim) {
+  case isl::dim::in:
+    Space = std::move(Space).domain();
+    break;
+  case isl::dim::out:
+    Space = give(isl_space_range(Space.take()));
+    break;
+  default:
+    llvm_unreachable("Unsupported value for 'dim'");
+  }
+  Space = give(isl_space_map_from_domain_and_range(Space.copy(), Space.copy()));
+  auto Translator = makeShiftDimAff(std::move(Space), Pos, Amount);
+  auto TranslatorMap = give(isl_map_from_multi_aff(Translator.take()));
+  switch (Dim) {
+  case isl::dim::in:
+    return Map.apply_domain(TranslatorMap);
+  case isl::dim::out:
+    return Map.apply_range(TranslatorMap);
+  default:
+    llvm_unreachable("Unsupported value for 'dim'");
+  }
+}
+
+isl::union_map polly::shiftDim(isl::union_map UMap, isl::dim Dim, int Pos,
+                               int Amount) {
+  auto Result = isl::union_map::empty(UMap.get_space());
+
+  foreachElt(UMap, [=, &Result](isl::map Map) {
+    auto Shifted = shiftDim(Map, Dim, Pos, Amount);
+    Result = std::move(Result).add_map(Shifted);
+  });
+  return Result;
+}
 void polly::simplify(isl::set &Set) {
   Set = give(isl_set_compute_divs(Set.take()));
   Set = give(isl_set_detect_equalities(Set.take()));
   Set = give(isl_set_coalesce(Set.take()));
 }
 
 void polly::simplify(isl::union_set &USet) {
   USet = give(isl_union_set_compute_divs(USet.take()));
isl::union_set polly::convertZoneToTimepoints(isl::union_set Zone,
   if (InclStart && !InclEnd)
     return ShiftedZone;
   else if (!InclStart && !InclEnd)
     return give(isl_union_set_intersect(Zone.take(), ShiftedZone.take()));
 
   assert(InclStart && InclEnd);
   return give(isl_union_set_union(Zone.take(), ShiftedZone.take()));
 }
+
+isl::union_map polly::convertZoneToTimepoints(isl::union_map Zone, isl::dim Dim,
+                                              bool InclStart, bool InclEnd) {
+  if (!InclStart && InclEnd)
+    return Zone;
+
+  auto ShiftedZone = shiftDim(Zone, Dim, -1, -1);
+  if (InclStart && !InclEnd)
+    return ShiftedZone;
+  else if (!InclStart && !InclEnd)
+    return give(isl_union_map_intersect(Zone.take(), ShiftedZone.take()));
+
+  assert(InclStart && InclEnd);
+  return give(isl_union_map_union(Zone.take(), ShiftedZone.take()));
+}
+
+isl::map polly::distributeDomain(isl::map Map) {
+  // Note that we cannot take Map apart into { Domain[] -> Range1[] } and {
+  // Domain[] -> Range2[] } and combine again. We would loose any relation
+  // between Range1[] and Range2[] that is not also a constraint to Domain[].
+
+  auto Space = give(isl_map_get_space(Map.keep()));
+  auto DomainSpace = give(isl_space_domain(Space.copy()));
+  assert(DomainSpace);
+  auto DomainDims = isl_space_dim(DomainSpace.keep(), isl_dim_set);
+  auto RangeSpace = give(isl_space_unwrap(isl_space_range(Space.copy())));
+  auto Range1Space = give(isl_space_domain(RangeSpace.copy()));
+  assert(Range1Space);
+  auto Range1Dims = isl_space_dim(Range1Space.keep(), isl_dim_set);
+  auto Range2Space = give(isl_space_range(RangeSpace.copy()));
+  assert(Range2Space);
+  auto Range2Dims = isl_space_dim(Range2Space.keep(), isl_dim_set);
+
+  auto OutputSpace = give(isl_space_map_from_domain_and_range(
+      isl_space_wrap(isl_space_map_from_domain_and_range(DomainSpace.copy(),
+                                                         Range1Space.copy())),
+      isl_space_wrap(isl_space_map_from_domain_and_range(DomainSpace.copy(),
+                                                         Range2Space.copy()))));
+
+  auto Translator =
+      give(isl_basic_map_universe(isl_space_map_from_domain_and_range(
+          isl_space_wrap(Space.copy()), isl_space_wrap(OutputSpace.copy()))));
+
+  for (unsigned i = 0; i < DomainDims; i += 1) {
+    Translator = give(
+        isl_basic_map_equate(Translator.take(), isl_dim_in, i, isl_dim_out, i));
+    Translator =
+        give(isl_basic_map_equate(Translator.take(), isl_dim_in, i, isl_dim_out,
+                                  DomainDims + Range1Dims + i));
+  }
+  for (unsigned i = 0; i < Range1Dims; i += 1) {
+    Translator =
+        give(isl_basic_map_equate(Translator.take(), isl_dim_in, DomainDims + i,
+                                  isl_dim_out, DomainDims + i));
+  }
+  for (unsigned i = 0; i < Range2Dims; i += 1) {
+    Translator = give(isl_basic_map_equate(
+        Translator.take(), isl_dim_in, DomainDims + Range1Dims + i, isl_dim_out,
+        DomainDims + Range1Dims + DomainDims + i));
+  }
+
+  return give(isl_set_unwrap(isl_set_apply(
+      isl_map_wrap(Map.copy()), isl_map_from_basic_map(Translator.copy()))));
+}
+
+isl::union_map polly::distributeDomain(isl::union_map UMap) {
+  auto Result = give(isl_union_map_empty(isl_union_map_get_space(UMap.keep())));
+  foreachElt(UMap, [=, &Result](isl::map Map) {
+    auto Distributed = distributeDomain(Map);
+    Result = give(isl_union_map_add_map(Result.take(), Distributed.copy()));
+  });
+  return Result;
+}
+
+isl::union_map polly::liftDomains(isl::union_map UMap, isl::union_set Factor) {
+
+  // { Factor[] -> Factor[] }
+  auto Factors = makeIdentityMap(std::move(Factor), true);
+
+  return std::move(Factors).product(std::move(UMap));
+}
+
+isl::union_map polly::applyDomainRange(isl::union_map UMap,
+                                       isl::union_map Func) {
+  // This implementation creates unnecessary cross products of the
+  // DomainDomain[] and Func. An alternative implementation could reverse
+  // domain+uncurry,apply Func to what now is the domain, then undo the
+  // preparing transformation. Another alternative implementation could create a
+  // translator map for each piece.
+
+  // { DomainDomain[] }
+  auto DomainDomain = UMap.domain().unwrap().domain();
+
+  // { [DomainDomain[] -> DomainRange[]] -> [DomainDomain[] -> NewDomainRange[]]
+  // }
+  auto LifetedFunc = liftDomains(std::move(Func), DomainDomain);
+
+  return std::move(UMap).apply_domain(std::move(LifetedFunc));
+}

lib/Support/VirtualInstruction.cpp

+//===------ VirtualInstruction.cpp ------------------------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// Tools for determining which instructions are within a statement and the
+// nature of their operands.
+//
+//===----------------------------------------------------------------------===//
+
+#include "polly/Support/VirtualInstruction.h"
+
+using namespace polly;
+using namespace llvm;
+
+namespace {
+/// Is @p Val defined in @p Stmt?
+bool isDefinedInStmt(Value *Val, ScopStmt *Stmt) {
+  auto *Inst = dyn_cast<Instruction>(Val);
+  if (!Inst)
+    return false;
+  return Stmt->contains(Inst->getParent());
+}
+
+/// If InputVal is not defined in the stmt itself, return the MemoryAccess that
+/// reads the scalar. Return nullptr otherwise (if the value is defined in the
+/// scop, or is synthesizable)
+MemoryAccess *getInputAccessOf(Value *InputVal, ScopStmt *UserStmt,
+                               bool IsEntryPHIUser) {
+  // Stmt may have a backedge to itself.
+  // In this case prefer to use definition of the value itself.
+  // Using the input MemoryAccess is only allowed if the user instruction is a
+  // PHI that handles the backedge.
+  if (!IsEntryPHIUser && UserStmt->isBlockStmt() &&
+      isDefinedInStmt(InputVal, UserStmt))
+    return nullptr;
+
+  for (auto *MA : *UserStmt) {
+    if (!MA->isRead())
+      continue;
+    // if (!(MA->isOriginalScalarKind() ||
+    ////      (AllowArrayLoads && MA->isOriginalArrayKind())))
+    // continue;
+    if (!MA->isOriginalScalarKind())
+      continue;
+
+    if (MA->getAccessValue() == InputVal)
+      return MA;
+  }
+  return nullptr;
+}
+}; // namespace
+
+VirtualUse VirtualUse ::create(Scop *S, Use &U, LoopInfo *LI) {
+  return create(S->getStmtFor(cast<Instruction>(U.getUser())), U, LI);
+}
+
+VirtualUse VirtualUse ::create(ScopStmt *UserStmt, Use &U, LoopInfo *LI) {
+  auto *Val = U.get();
+  auto *UserInst = U.getUser();
+  auto IsEntryPHIUser =
+      isa<PHINode>(UserInst) &&
+      cast<PHINode>(UserInst)->getParent() == UserStmt->getEntryBlock();
+  return create(UserStmt, IsEntryPHIUser, LI->getLoopFor(getUseBlock(U)), Val);
+}
+
+VirtualUse VirtualUse::create(ScopStmt *UserStmt, bool IsEntryPHIUser,
+                              Loop *UserScope, Value *Val) {
+  if (isa<llvm::Constant>(Val) || isa<llvm::BasicBlock>(Val))
+    return VirtualUse(UserStmt, Val, Constant, nullptr);
+
+  auto *S = UserStmt->getParent();
+  auto *SE = S->getSE();
+
+  if (canSynthesize(Val, *UserStmt->getParent(), SE, UserScope))
+    return VirtualUse(UserStmt, Val, Synthesizable, nullptr);
+
+  auto *InputMA = getInputAccessOf(Val, UserStmt, IsEntryPHIUser);
+
+  if (isa<Argument>(Val))
+    return VirtualUse(UserStmt, Val, ReadOnly, InputMA);
+
+  auto Inst = cast<Instruction>(Val);
+  if (!S->contains(Inst))
+    return VirtualUse(UserStmt, Val, ReadOnly, InputMA);
+
+  if (isa<PHINode>(Inst) && Inst->getParent() == UserStmt->getEntryBlock())
+    return VirtualUse(UserStmt, Val, IntraValue, nullptr);
+
+  if (InputMA)
+    return VirtualUse(UserStmt, Val, InterValue, InputMA);
+
+  return VirtualUse(UserStmt, Val, IntraValue, nullptr);
+}
+
+void VirtualUse::print(raw_ostream &OS) const {
+  OS << "User: [" << User->getBaseName() << "] ";
+  switch (Ty) {
+  case polly::VirtualUse::Constant:
+    OS << "Constant Op:";
+    break;
+  case polly::VirtualUse::ReadOnly:
+    OS << "Read-Only Op:";
+    break;
+  case polly::VirtualUse::Synthesizable:
+    OS << "Synthesizable Op:";
+    break;
+  case polly::VirtualUse::IntraValue:
+    OS << "Intra Op:";
+    break;
+  case polly::VirtualUse::InterValue:
+    OS << "Inter Op:";
+    break;
+  }
+  if (Val) {
+    OS << ' ';
+    Val->print(errs(), true);
+  }
+  if (InputMA)
+    OS << ' ' << InputMA;
+}
+
+#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
+void VirtualUse::dump() const {
+  print(errs());
+  errs() << '\n';
+}
+#endif

lib/Transform/DeLICM.cpp

 //     isl_id_get_user: Pointer to ScopArrayInfo
 //
 // * Scatter[] - Scatter space or space of timepoints
 //     Has no tuple id
 //
 // * Zone[] - Range between timepoints as described above
 //     Has no tuple id
 //
+// * ValInst[] - An llvm::Value as defined at a specific timepoint.
+//
+//     A ValInst[] itself can be structured as one of:
+//
+//     * [] - An unknown value.
+//         Always zero dimensions
+//         Has no tuple id
+//
+//     * Value[] - An llvm::Value that is read-only in the Scop, i.e. its
+//                 runtime content does not depend on the timepoint.
+//         Always zero dimensions
+//         isl_id_get_name: Val_<NameOfValue>
+//         isl_id_get_user: A pointer to an llvm::Value
+//
+//     * [Expression] - An evaluated expression.
+//         The value was synthesizable in a given scope, and this is the result.
+//         This typically is a parameter, an induction variable or an affine
+//         expression of these.
+//
+//     * [Domain[] -> Value[]] - An llvm::Value that may change during the
+//                               Scop's execution.
+//         The tuple itself has no id, but it wraps a map space holding a
+//         statement instance which defines the llvm::Value as the map's domain
+//         and llvm::Value itself as range.
+//
+// @see makeValInst()
+//
 // An annotation "{ Domain[] -> Scatter[] }" therefore means: A map from a
 // statement instance to a timepoint, aka a schedule. There is only one scatter
 // space, but most of the time multiple statements are processed in one set.
 // This is why most of the time isl_union_map has to be used.
 //
 // The basic algorithm works as follows:
 // At first we verify that the SCoP is compatible with this technique. For
 // instance, two writes cannot write to the same location at the same statement

 //
 //===----------------------------------------------------------------------===//
 
 #include "polly/DeLICM.h"
 #include "polly/Options.h"
 #include "polly/ScopInfo.h"
 #include "polly/ScopPass.h"
 #include "polly/Support/ISLTools.h"
+#include "polly/Support/VirtualInstruction.h"
 #include "llvm/ADT/Statistic.h"
 #define DEBUG_TYPE "polly-delicm"
 
 using namespace polly;
 using namespace llvm;
 
 namespace {
 
auto UMap = computeScalarReachingDefinition(
       Schedule, give(isl_union_set_from_set(Writes.take())), InclDef,
       InclRedef);
 
   auto ResultSpace = give(isl_space_map_from_domain_and_range(
       ScatterSpace.take(), DomainSpace.take()));
   return singleton(UMap, ResultSpace);
 }
 
-/// If InputVal is not defined in the stmt itself, return the MemoryAccess that
-/// reads the scalar. Return nullptr otherwise (if the value is defined in the
-/// scop, or is synthesizable).
-MemoryAccess *getInputAccessOf(Value *InputVal, ScopStmt *Stmt) {
-  for (auto *MA : *Stmt) {
-    if (!MA->isRead())
-      continue;
-    if (!MA->isLatestScalarKind())
-      continue;
+/// Create a domain-to-unknown value mapping.
+///
+/// @param Domain { Domain[] }
+///
+/// @return { Domain[] -> ValInst[] }
+isl::map makeUnknownForDomain(isl::set Domain) {
+  return give(isl_map_from_domain(Domain.take()));
+}
 
-    assert(MA->getAccessValue() == MA->getBaseAddr());
-    if (MA->getAccessValue() == InputVal)
-      return MA;
-  }
-  return nullptr;
+/// Create a domain-to-unknown value mapping.
+///
+/// @param Domain { Domain[] }
+///
+/// @return { Domain[] -> ValInst[] }
+isl::union_map makeUnknownForDomain(isl::union_set Domain) {
+  return give(isl_union_map_from_domain(Domain.take()));
+
+/// Return whether @p Map maps to an unknown value.
+///
+/// @param { [] -> ValInst[] }
+bool isMapToUnknown(const isl::map &Map) {
+  auto Space = give(isl_space_range(isl_map_get_space(Map.keep())));
+  return !isl_map_has_tuple_id(Map.keep(), isl_dim_set) &&
+         !isl_space_is_wrapping(Space.keep()) &&
+         isl_map_dim(Map.keep(), isl_dim_out) == 0;
+}
+
+/// Return only the mappings that map to known values.
+///
+/// @param UMap { [] -> ValInst[] }
+///
+/// @return { [] -> ValInst[] }
+isl::union_map filterKnownValInst(const isl::union_map &UMap) {
+  auto Result = give(isl_union_map_empty(isl_union_map_get_space(UMap.keep())));
+  foreachElt(UMap, [=, &Result](isl::map Map) {
+    if (!isMapToUnknown(Map))
+      Result = give(isl_union_map_add_map(Result.take(), Map.take()));
+  });
+  return Result;
 }
 
 /// Try to find a 'natural' extension of a mapped to elements outside its
 /// domain.
 ///
 /// @param Relevant The map with mapping that may not be modified.
 /// @param Universe The domain to which @p Relevant needs to be extended.
 ///
private:
   isl::union_set Occupied;
 
   /// { [Element[] -> Zone[]] }
   /// Set of array elements when they are not alive, i.e. their memory can be
   /// used for other purposed. Can contain a nullptr; in this case the set is
   /// implicitly defined as the complement of #Occupied.
   isl::union_set Unused;
 
-  /// { [Element[] -> Scatter[]] }
+  /// { [Element[] -> Zone[]] -> ValInst[] }
+  /// Maps to the known content for each array element at any interval.
+  ///
+  /// Any element/interval can map to multiple known elements. This is due to
+  /// multiple llvm::Value referring to the same content. Examples are
+  ///
+  /// - A value stored and loaded again. The LoadInst represents the same value
+  /// as the StoreInst's value operand.
+  ///
+  /// - A PHINode is equal to any one of the incoming values. In case of
+  /// LCSSA-form, it is always equal to its single incoming value.
+  ///
+  /// Two Knowledges are considered not conflicting if at least one of the known
+  /// values match. Not known values are not stored as an unnamed tuple (as
+  /// #Written does), but maps to nothing.
+  ///
+  ///  Known values are usually just defined for #Occupied elements. Knowing
+  ///  #Unused contents has no advantage as it can be overwritten.
+  isl::union_map Known;
+
+  /// { [Element[] -> Scatter[]] -> ValInst[] }
   /// The write actions currently in the scop or that would be added when
-  /// mapping a scalar.
-  isl::union_set Written;
+  /// mapping a scalar. Maps to the value that is written.
+  ///
+  /// Written values that cannot be identified are represented by an unknown
+  /// ValInst[] (an unnamed tuple of 0 dimension). It conflicts with itself.
+  isl::union_map Written;
 
   /// Check whether this Knowledge object is well-formed.
   void checkConsistency() const {
 #ifndef NDEBUG
     // Default-initialized object
-    if (!Occupied && !Unused && !Written)
+    if (!Occupied && !Unused && !Known && !Written)
       return;
 
     assert(Occupied || Unused);
+    assert(Known);
     assert(Written);
 
+    assert(filterKnownValInst(Known).is_equal(Known) &&
+           "Known must only contain known elements");
+
     // If not all fields are defined, we cannot derived the universe.
     if (!Occupied || !Unused)
       return;
 
-    assert(isl_union_set_is_disjoint(Occupied.keep(), Unused.keep()) ==
-           isl_bool_true);
+    assert(isl_union_set_is_disjoint(Occupied.keep(), Unused.keep()) !=
+           isl_bool_false);
     auto Universe = give(isl_union_set_union(Occupied.copy(), Unused.copy()));
-    assert(isl_union_set_is_subset(Written.keep(), Universe.keep()) ==
-           isl_bool_true);
+
+    assert(Written.domain().is_subset(Universe).is_true_or_error());
+    assert(Known.domain().is_subset(Universe).is_true_or_error());
 #endif
   }
 
 public:
   /// Initialize a nullptr-Knowledge. This is only provided for convenience; do
   /// not use such an object.
   Knowledge() {}
 
   /// Create a new object with the given members.
   Knowledge(isl::union_set Occupied, isl::union_set Unused,
-            isl::union_set Written)
+            isl::union_map Known, isl::union_map Written)
       : Occupied(std::move(Occupied)), Unused(std::move(Unused)),
-        Written(std::move(Written)) {
+        Known(std::move(Known)), Written(std::move(Written)) {
     checkConsistency();
   }
 
-  /// Alternative constructor taking isl_sets instead isl_union_sets.
-  Knowledge(isl::set Occupied, isl::set Unused, isl::set Written)
-      : Knowledge(give(isl_union_set_from_set(Occupied.take())),
-                  give(isl_union_set_from_set(Unused.take())),
-                  give(isl_union_set_from_set(Written.take()))) {}
-
   /// Return whether this object was not default-constructed.
-  bool isUsable() const { return (Occupied || Unused) && Written; }
+  bool isUsable() const { return (Occupied || Unused) && Known && Written; }
 
   /// Print the content of this object to @p OS.
   void print(llvm::raw_ostream &OS, unsigned Indent = 0) const {
     if (isUsable()) {
       if (Occupied)
         OS.indent(Indent) << "Occupied: " << Occupied << "\n";
       else
         OS.indent(Indent) << "Occupied: <Everything else not in Unused>\n";
       if (Unused)
         OS.indent(Indent) << "Unused:   " << Unused << "\n";
       else
         OS.indent(Indent) << "Unused:   <Everything else not in Occupied>\n";
+      OS.indent(Indent) << "Known:    " << Known << "\n";
       OS.indent(Indent) << "Written : " << Written << '\n';
     } else {
       OS.indent(Indent) << "Invalid knowledge\n";
     }
   }
 
   /// Combine two knowledges, this and @p That.
   void learnFrom(Knowledge That) {
     assert(!isConflicting(*this, That));
     assert(Unused && That.Occupied);
     assert(
         !That.Unused &&
         "This function is only prepared to learn occupied elements from That");
     assert(!Occupied && "This function does not implement "
                         "`this->Occupied = "
                         "give(isl_union_set_union(this->Occupied.take(), "
                         "That.Occupied.copy()));`");
 
     Unused = give(isl_union_set_subtract(Unused.take(), That.Occupied.copy()));
-    Written = give(isl_union_set_union(Written.take(), That.Written.take()));
+    Known = give(isl_union_map_union(Known.take(), That.Known.copy()));
+    Written = give(isl_union_map_union(Written.take(), That.Written.take()));
 
     checkConsistency();
   }
 
   /// Determine whether two Knowledges conflict with each other.
   ///
   /// In theory @p Existing and @p Proposed are symmetric, but the
   /// implementation is constrained by the implicit interpretation. That is, @p
if (Existing.Occupied && Proposed.Unused) {
       auto ProposedUniverse = give(isl_union_set_union(Proposed.Occupied.copy(),
                                                        Proposed.Unused.copy()));
       assert(isl_union_set_is_equal(ExistingUniverse.keep(),
                                     ProposedUniverse.keep()) == isl_bool_true &&
              "Both inputs' Knowledges must be over the same universe");
     }
 #endif
 
-    // Are the new lifetimes required for Proposed unused in Existing?
-    if (isl_union_set_is_subset(Proposed.Occupied.keep(),
-                                Existing.Unused.keep()) != isl_bool_true) {
+    // Do the Existing and Proposed lifetimes conflicting?
+    // In order to not conflict, one of the following conditions must apply for
+    // each element/lifetime interval:
+    //
+    // 1. If occupied in one of the knowledges, it is unused in the other.
+    //
+    // - or -
+    //
+    // 2. Both contain the same value.
+    //
+    // Instead of partitioning the lifetimes into a part occupied by both and
+    // checking the conditions separately, we check only the second conditions
+    // and ensure that it will also apply when then first condition is true.
+    // This is done by adding another "the value occupying Proposed" to
+    // Proposed.Known and to Existing.Unused such that these match while looking
+    // for a common known value. Note that we use "unknown value" for this
+    // purpose such that we can re-use Existing.Unused to also match unknown
+    // values in Proposed.Written in a later check.
+    auto ProposedOccupiedAnyVal = makeUnknownForDomain(Proposed.Occupied);
+    auto ProposedValues = Proposed.Known.unite(ProposedOccupiedAnyVal);
+
+    auto ExistingUnusedAnyVal = makeUnknownForDomain(Existing.Unused);
+    auto ExistingValues = Existing.Known.unite(ExistingUnusedAnyVal);
+
+    auto SomeVal = ExistingValues.intersect(ProposedValues);
+    auto SomeValDomain = SomeVal.domain();
+
+    if (!Proposed.Occupied.is_subset(SomeValDomain)) {
       if (OS) {
-        auto ConflictingLifetimes = give(isl_union_set_subtract(
-            Proposed.Occupied.copy(), Existing.Unused.copy()));
-        OS->indent(Indent) << "Proposed lifetimes are not unused in existing\n";
-        OS->indent(Indent) << "Conflicting lifetimes: " << ConflictingLifetimes
-                           << "\n";
+        auto Conflicting = Proposed.Occupied.subtract(SomeValDomain);
+        auto ExistingConflictingKnown =
+            Existing.Known.intersect_domain(Conflicting);
+        auto ProposedConflictingKnown =
+            Proposed.Known.intersect_domain(Conflicting);
+
+        OS->indent(Indent) << "Proposed lifetime conflicting with Existing's\n";
+        OS->indent(Indent) << "Conflicting occupied: " << Conflicting << "\n";
+        if (!ExistingConflictingKnown.is_empty())
+          OS->indent(Indent)
+              << "Existing Known:       " << ExistingConflictingKnown << "\n";
+        if (!ProposedConflictingKnown.is_empty())
+          OS->indent(Indent)
+              << "Proposed Known:       " << ProposedConflictingKnown << "\n";
       }
       return true;
     }
 
-    // Do the writes in Existing only overwrite unused values in Proposed?
+    // Do the writes in Existing conflict with occupied values in Proposed?
+    // In order to not conflict, it must either write to unused lifetime or
+    // write the same value. To check, we remove the writes that write into
+    // Proposed.Unused (they never conflict) and then see whether the written
+    // value is already in Proposed.Known.
+    //
     // We convert here the set of lifetimes to actual timepoints. A lifetime is
     // in conflict with a set of write timepoints, if either a live timepoint is
     // clearly within the lifetime or if a write happens at the beginning of the
     // lifetime (where it would conflict with the value that actually writes the
     // value alive). There is no conflict at the end of a lifetime, as the alive
     // value will always be read, before it is overwritten again. The last
     // property holds in Polly for all scalar values and we expect all users of
     // Knowledge to check this property also for accesses to MemoryKind::Array.
     auto ProposedFixedDefs =
         convertZoneToTimepoints(Proposed.Occupied, true, false);
-    if (isl_union_set_is_disjoint(Existing.Written.keep(),
-                                  ProposedFixedDefs.keep()) != isl_bool_true) {
+    auto ProposedFixedKnown =
+        convertZoneToTimepoints(Proposed.Known, isl::dim::in, true, false);
+
+    auto ExistingConflictingWrites =
+        Existing.Written.intersect_domain(ProposedFixedDefs);
+    auto ExistingConflictingWritesDomain = ExistingConflictingWrites.domain();
+
+    auto SomeWrittenVal =
+        ProposedFixedKnown.intersect(ExistingConflictingWrites);
+    auto SomeWrittenValDomain = SomeWrittenVal.domain();
+
+    if (!ExistingConflictingWritesDomain.is_subset(SomeWrittenValDomain)) {
       if (OS) {
-        auto ConflictingWrites = give(isl_union_set_intersect(
-            Existing.Written.copy(), ProposedFixedDefs.copy()));
-        OS->indent(Indent) << "Proposed writes into range used by existing\n";
-        OS->indent(Indent) << "Conflicting writes: " << ConflictingWrites
-                           << "\n";
+        auto ExistingConflictingWritten =
+            ExistingConflictingWrites.subtract_domain(SomeWrittenValDomain);
+        auto ProposedConflictingKnown = ProposedFixedKnown.subtract_domain(
+            ExistingConflictingWritten.domain());
+
+        OS->indent(Indent)
+            << "Proposed a lifetime where there is an Existing write into it\n";
+        OS->indent(Indent) << "Existing conflicting writes: "
+                           << ExistingConflictingWritten << "\n";
+        if (!ProposedConflictingKnown.is_empty())
+          OS->indent(Indent)
+              << "Proposed conflicting known:  " << ProposedConflictingKnown
       }
       return true;
     }
 
-    // Do the new writes in Proposed only overwrite unused values in Existing?
-    auto ExistingAvailableDefs =
-        convertZoneToTimepoints(Existing.Unused, true, false);
-    if (isl_union_set_is_subset(Proposed.Written.keep(),
-                                ExistingAvailableDefs.keep()) !=
-        isl_bool_true) {
+    // Do the writes in Proposed conflict with occupied values in Existing?
+    // We use the same trick with unknown values to save a subtract operation.
+    auto ExistingValuesFixedDefs =
+        convertZoneToTimepoints(ExistingValues, isl::dim::in, true, false);
+
+    auto ProposedWrittenDomain = Proposed.Written.domain();
+    auto ProposedWrittenAnyVal =
+        Proposed.Written.unite(makeUnknownForDomain(ProposedWrittenDomain));
+    auto ProposedWrittenSomeVal =
+        ProposedWrittenAnyVal.intersect(ExistingValuesFixedDefs);
+    auto ProposedWrittenSomeValDomain = ProposedWrittenSomeVal.domain();
+
+    if (!ProposedWrittenDomain.is_subset(ProposedWrittenSomeValDomain)) {
       if (OS) {
-        auto ConflictingWrites = give(isl_union_set_subtract(
-            Proposed.Written.copy(), ExistingAvailableDefs.copy()));
+        auto Conflicting =
+            ProposedWrittenDomain.subtract(ProposedWrittenSomeValDomain);
+        auto ExistingConflictingKnown =
+            ExistingValuesFixedDefs.intersect_domain(Conflicting);
+        auto ProposedConflictingWritten =
+            Proposed.Written.intersect_domain(Conflicting);
+
+        OS->indent(Indent) << "Proposed writes into range used by Existing\n";
+        OS->indent(Indent) << "Proposed conflicting writes: "
+                           << ProposedConflictingWritten << "\n";
+        if (!ExistingConflictingKnown.is_empty())
           OS->indent(Indent)
-            << "Proposed a lifetime where there is an Existing write into it\n";
-        OS->indent(Indent) << "Conflicting writes: " << ConflictingWrites
-                           << "\n";
+              << "Existing conflicting known: " << ExistingConflictingKnown
       }
       return true;
     }
 
     // Does Proposed write at the same time as Existing already does (order of
-    // writes is undefined)?
-    if (isl_union_set_is_disjoint(Existing.Written.keep(),
-                                  Proposed.Written.keep()) != isl_bool_true) {
+    // writes is undefined)? Writing the same value is permitted.
+    auto BothWritten =
+        Existing.Written.domain().intersect(Proposed.Written.domain());
+    auto CommonWritten = filterKnownValInst(Existing.Written)
+                             .intersect(filterKnownValInst(Proposed.Written))
+                             .domain();
+
+    if (!BothWritten.is_subset(CommonWritten)) {
       if (OS) {
-        auto ConflictingWrites = give(isl_union_set_intersect(
-            Existing.Written.copy(), Proposed.Written.copy()));
+        auto Conflicting = BothWritten.subtract(CommonWritten);
+        auto ExistingConflictingWritten =
+            Existing.Written.intersect_domain(Conflicting);
+        auto ProposedConflictingWritten =
+            Proposed.Written.intersect_domain(Conflicting);
+
         OS->indent(Indent) << "Proposed writes at the same time as an already "
                               "Existing write\n";
-        OS->indent(Indent) << "Conflicting writes: " << ConflictingWrites
-                           << "\n";
+        OS->indent(Indent) << "Conflicting writes: " << Conflicting << "\n";
+        if (!ExistingConflictingWritten.is_empty())
+          OS->indent(Indent)
+              << "Exiting write:      " << ExistingConflictingWritten << "\n";
+        if (!ProposedConflictingWritten.is_empty())
+          OS->indent(Indent)
+              << "Proposed write:     " << ProposedConflictingWritten << "\n";
       }
       return true;
     }
 
     return false;
   }
 };
 
protected:
   /// Cached reaching definitions for each ScopStmt.
   ///
   /// Use getScalarReachingDefinition() to get its contents.
   DenseMap<ScopStmt *, isl::map> ScalarReachDefZone;
 
   /// The analyzed Scop.
   Scop *S;
 
+  /// LoopInfo analysis used to determine whether values are synthesizable.
+  LoopInfo *LI;
+
   /// Parameter space that does not need realignment.
   isl::space ParamSpace;
 
   /// Space the schedule maps to.
   isl::space ScatterSpace;
 
   /// Cached version of the schedule and domains.
   isl::union_map Schedule;
 
-  /// Set of all referenced elements.
-  /// { Element[] -> Element[] }
-  isl::union_set AllElements;
-
   /// Combined access relations of all MemoryKind::Array READ accesses.
   /// { DomainRead[] -> Element[] }
   isl::union_map AllReads;
 
   /// Combined access relations of all MemoryKind::Array, MAY_WRITE accesses.
   /// { DomainMayWrite[] -> Element[] }
   isl::union_map AllMayWrites;
 
   /// Combined access relations of all MemoryKind::Array, MUST_WRITE accesses.
   /// { DomainMustWrite[] -> Element[] }
   isl::union_map AllMustWrites;
 
+  /// The value instances written to array elements of all write accesses.
+  /// { [Element[] -> DomainWrite[]] -> ValInst[] }
+  isl::union_map AllWriteValInst;
+
+  // { [Element[] -> DomainRead[]] -> ValInst[] }
+  isl::union_map AllReadValInst;
+
+  /// All reaching definitions for  MemoryKind::Array writes.
+  /// { [Element[] -> Zone[]] -> DomainWrite[] }
+  isl::union_map WriteReachDefZone;
+
   /// Prepare the object before computing the zones of @p S.
-  ZoneAlgorithm(Scop *S)
-      : IslCtx(S->getSharedIslCtx()), S(S), Schedule(give(S->getSchedule())) {
+  ZoneAlgorithm(Scop *S, LoopInfo *LI)
+      : IslCtx(S->getSharedIslCtx()), S(S), LI(LI),
+        Schedule(give(S->getSchedule())) {
 
     auto Domains = give(S->getDomains());
 
     Schedule =
         give(isl_union_map_intersect_domain(Schedule.take(), Domains.take()));
     ParamSpace = give(isl_union_map_get_space(Schedule.keep()));
     ScatterSpace = getScatterSpace(Schedule);
   }
bool isCompatibleStmt(ScopStmt *Stmt) {
     }
 
     return true;
   }
 
   void addArrayReadAccess(MemoryAccess *MA) {
     assert(MA->isLatestArrayKind());
     assert(MA->isRead());
+    auto *Stmt = MA->getStatement();
 
     // { DomainRead[] -> Element[] }
     auto AccRel = getAccessRelationFor(MA);
     AllReads = give(isl_union_map_add_map(AllReads.take(), AccRel.copy()));
+
+    if (auto *Load = dyn_cast_or_null<LoadInst>(MA->getAccessValue())) {
+      // { DomainRead[] -> ValInst[] }
+      auto LoadValInst =
+          makeValInst(Load, Stmt, false, LI->getLoopFor(Load->getParent()),
+                      Stmt->isBlockStmt());
+
+      // { DomainRead[] -> [Element[] -> DomainRead[]] }
+      auto IncludeElement =
+          give(isl_map_curry(isl_map_domain_map(AccRel.take())));
+
+      // { [Element[] -> DomainRead[]] -> ValInst[] }
+      auto EltLoadValInst =
+          give(isl_map_apply_domain(LoadValInst.take(), IncludeElement.take()));
+
+      AllReadValInst = give(
+          isl_union_map_add_map(AllReadValInst.take(), EltLoadValInst.take()));
+    }
   }
 
   void addArrayWriteAccess(MemoryAccess *MA) {
     assert(MA->isLatestArrayKind());
     assert(MA->isWrite());
+    auto *Stmt = MA->getStatement();
 
     // { Domain[] -> Element[] }
     auto AccRel = getAccessRelationFor(MA);
 
     if (MA->isMustWrite())
       AllMustWrites =
           give(isl_union_map_add_map(AllMustWrites.take(), AccRel.copy()));
 
     if (MA->isMayWrite())
       AllMayWrites =
           give(isl_union_map_add_map(AllMayWrites.take(), AccRel.copy()));
+
+    // { Domain[] -> ValInst[] }
+    auto WriteValInstance =
+        makeValInst(MA->getAccessValue(), Stmt, false,
+                    LI->getLoopFor(MA->getAccessInstruction()->getParent()),
+                    MA->isMustWrite());
+
+    // { Domain[] -> [Element[] -> Domain[]] }
+    auto IncludeElement =
+        give(isl_map_curry(isl_map_domain_map(AccRel.copy())));
+
+    // { [Element[] -> DomainWrite[]] -> ValInst[] }
+    auto EltWriteValInst = give(
+        isl_map_apply_domain(WriteValInstance.take(), IncludeElement.take()));
+
+    AllWriteValInst = give(
+        isl_union_map_add_map(AllWriteValInst.take(), EltWriteValInst.take()));
   }
 
 protected:
   isl::union_set makeEmptyUnionSet() {
     return give(isl_union_set_empty(ParamSpace.copy()));
   }
 
   isl::union_map makeEmptyUnionMap() {
protected:
 
   /// Get the schedule for the statement instances of @p Domain.
   isl::map getScatterFor(isl::set Domain) const {
     auto ResultSpace = give(isl_space_map_from_domain_and_range(
         isl_set_get_space(Domain.keep()), ScatterSpace.copy()));
     auto UDomain = give(isl_union_set_from_set(Domain.copy()));
     auto UResult = getScatterFor(std::move(UDomain));
     auto Result = singleton(std::move(UResult), std::move(ResultSpace));
-    assert(isl_set_is_equal(give(isl_map_domain(Result.copy())).keep(),
+    assert(!Result ||
+           isl_set_is_equal(give(isl_map_domain(Result.copy())).keep(),
                             Domain.keep()) == isl_bool_true);
     return Result;
   }
 
   /// Get the domain of @p Stmt.
   isl::set getDomainFor(ScopStmt *Stmt) const {
     return give(Stmt->getDomain());
   }
isl::map getScalarReachingDefinition(ScopStmt *Stmt) {
     auto &Result = ScalarReachDefZone[Stmt];
     if (Result)
       return Result;
 
     auto Domain = getDomainFor(Stmt);
     Result = computeScalarReachingDefinition(Schedule, Domain, false, true);
     simplify(Result);
 
-    assert(Result);
+    return Result;
+  }
+
+  /// Get the reaching definition of a scalar defined in @p DefDomain.
+  ///
+  /// @param DomainDef { DomainDef[] }
+  ///              The write statements to get the reaching definition for.
+  ///
+  /// @return { Scatter[] -> DomainDef[] }
+  isl::map getScalarReachingDefinition(isl::set DomainDef) {
+    auto DomId = give(isl_set_get_tuple_id(DomainDef.keep()));
+    auto *Stmt = static_cast<ScopStmt *>(isl_id_get_user(DomId.keep()));
+
+    auto StmtResult = getScalarReachingDefinition(Stmt);
+
+    return give(isl_map_intersect_range(StmtResult.take(), DomainDef.take()));
+  }
+
+  /// Create a statement-to-unknown value mapping.
+  ///
+  /// @param Stmt The statement whose instances are mapped to unknown.
+  ///
+  /// @return { Domain[] -> ValInst[] }
+  isl::map makeUnknownForDomain(ScopStmt *Stmt) const {
+    return ::makeUnknownForDomain(getDomainFor(Stmt));
+  }
+
+  /// Create an isl_id that represents @p V.
+  isl::id makeValueId(Value *V) const {
+    if (!V)
+      return nullptr;
+
+    auto Name = getIslCompatibleName("Val_", V, std::string());
+    return give(isl_id_alloc(IslCtx.get(), Name.c_str(), V));
+  }
+
+  /// Create the space for an llvm::Value that is available everywhere.
+  isl::space makeValueSpace(Value *V) const {
+    auto Result = give(isl_space_set_from_params(ParamSpace.copy()));
+    return give(isl_space_set_tuple_id(Result.take(), isl_dim_set,
+                                       makeValueId(V).take()));
+  }
+
+  /// Create a set with the llvm::Value @p V which is available everywhere.
+  isl::set makeValueSet(Value *V) const {
+    auto Space = makeValueSpace(V);
+    return give(isl_set_universe(Space.take()));
+  }
+
+  /// Create a mapping from a statement instance to the instance of an
+  /// llvm::Value that can be used in there.
+  ///
+  /// Although LLVM IR used single static assignment, llvm::Values can have
+  /// different contents in loops, when they get redefined in the last
+  /// iteration. This function tries to get the statement instance of the
+  /// previous definition, relative to a user.
+  ///
+  /// Example:
+  /// for (int i = 0; i < N; i += 1) {
+  /// DEF:
+  ///    int v = A[i];
+  /// USE:
+  ///    use(v);
+  ///  }
+  ///
+  /// The value instance used by statement instance USE[i] is DEF[i]. Hence,
+  /// makeValInst returns:
+  ///
+  /// { USE[i] -> [DEF[i] -> v[]] : 0 <= i < N }
+  ///
+  /// @param Val            The value to look get the instance of.
+  /// @param UserStmt       The statement that uses @p Val. Can be nullptr.
+  /// @param IsEntryPHIUser Whether the user is a PHINode in the statement's
+  /// entry block.
+  /// @param Scope          Loop the using instruction resides in.
+  /// @param IsCertain      Pass true if the definition of @p Val is a
+  /// MUST_WRITE or
+  ///                       false if the write is conditional.
+  ///
+  /// @return { DomainUse[] -> ValInst[] }
+  isl::map makeValInst(Value *Val, ScopStmt *UserStmt, bool IsEntryPHIUser,
+                       Loop *Scope, bool IsCertain = true) {
+
+    // If the definition/write is conditional, the previous write may "shine
+    // through" on conditions we cannot determine. Return the unknown value.
+    if (!IsCertain)
+      return makeUnknownForDomain(UserStmt);
+
+    auto DomainUse = getDomainFor(UserStmt);
+    auto *SE = S->getSE();
+
+    auto VUse = VirtualUse::create(UserStmt, IsEntryPHIUser, Scope, Val);
+    switch (VUse.getType()) {
+    case VirtualUse::Constant:
+    case VirtualUse::ReadOnly: {
+      // The definition does not depend the statement which uses it.
+      auto ValSet = makeValueSet(Val);
+      return give(
+          isl_map_from_domain_and_range(DomainUse.take(), ValSet.take()));
+    }
+
+    case VirtualUse::Synthesizable: {
+      // With the induction variables fixed, we can evaluate this expression.
+      auto *SCEV = SE->getSCEVAtScope(Val, Scope);
+
+      // { UserDomain[] -> [Expression] }
+      auto Aff = give(UserStmt->getPwAff(SCEV));
+      auto Result = give(isl_map_from_pw_aff(Aff.take()));
+
+      simplify(Result);
+      return Result;
+    }
+
+    case VirtualUse::IntraValue: {
+      // Definition and use is in the same statement. We do not need to compute
+      // a reaching definition.
+
+      // { llvm::Value }
+      auto ValSet = makeValueSet(Val);
+
+      // {  UserDomain[] -> llvm::Value }
+      auto ValInstSet =
+          give(isl_map_from_domain_and_range(DomainUse.take(), ValSet.take()));
+
+      // { UserDomain[] -> [UserDomain[] - >llvm::Value] }
+      auto Result =
+          give(isl_map_reverse(isl_map_domain_map(ValInstSet.take())));
+      simplify(Result);
+      return Result;
+    }
+
+    case VirtualUse::InterValue:
+      // The value is defined in a different statement.
+      break;
+    }
+
+    auto *Inst = cast<Instruction>(Val);
+    auto *ValStmt = S->getStmtFor(Inst);
+
+    // If the llvm::Value is defined in a removed Stmt, we cannot derive its
+    // domain. We could use an arbitrary statement, but this could result in
+    // different ValInst[] for the same llvm::Value.
+    if (!ValStmt)
+      return ::makeUnknownForDomain(DomainUse);
+
+    // { DomainDef[] }
+    auto DomainDef = getDomainFor(ValStmt);
+
+    // { Scatter[] -> DomainDef[] }
+    auto ReachDef = getScalarReachingDefinition(DomainDef);
+
+    // { DomainUse[] -> Scatter[] }
+    auto UserSched = getScatterFor(DomainUse);
+
+    // { DomainUse[] -> DomainDef[] }
+    auto UsedInstance =
+        give(isl_map_apply_range(UserSched.take(), ReachDef.take()));
+
+    // { llvm::Value }
+    auto ValSet = makeValueSet(Val);
+
+    // { DomainUse[] -> llvm::Value[] }
+    auto ValInstSet =
+        give(isl_map_from_domain_and_range(DomainUse.take(), ValSet.take()));
+
+    // { DomainUse[] -> [DomainDef[] -> llvm::Value]  }
+    auto Result =
+        give(isl_map_range_product(UsedInstance.take(), ValInstSet.take()));
+
+    simplify(Result);
     return Result;
   }
 
   /// Compute the different zones.
   void computeCommon() {
     AllReads = makeEmptyUnionMap();
     AllMayWrites = makeEmptyUnionMap();
     AllMustWrites = makeEmptyUnionMap();
+    AllWriteValInst = makeEmptyUnionMap();
+    AllReadValInst = makeEmptyUnionMap();
 
     for (auto &Stmt : *S) {
       for (auto *MA : Stmt) {
         if (!MA->isLatestArrayKind())
           continue;
 
         if (MA->isRead())
           addArrayReadAccess(MA);
 
         if (MA->isWrite())
           addArrayWriteAccess(MA);
       }
     }
 
     // { DomainWrite[] -> Element[] }
     auto AllWrites =
         give(isl_union_map_union(AllMustWrites.copy(), AllMayWrites.copy()));
 
-    // { Element[] }
-    AllElements = makeEmptyUnionSet();
-    foreachElt(AllWrites, [this](isl::map Write) {
-      auto Space = give(isl_map_get_space(Write.keep()));
-      auto EltSpace = give(isl_space_range(Space.take()));
-      auto EltUniv = give(isl_set_universe(EltSpace.take()));
-      AllElements =
-          give(isl_union_set_add_set(AllElements.take(), EltUniv.take()));
-    });
+    // { [Element[] -> Zone[]] -> DomainWrite[] }
+    WriteReachDefZone =
+        computeReachingDefinition(Schedule, AllWrites, false, true);
+    simplify(WriteReachDefZone);
   }
 
   /// Print the current state of all MemoryAccesses to @p.
   void printAccesses(llvm::raw_ostream &OS, int Indent = 0) const {
     OS.indent(Indent) << "After accesses {\n";
     for (auto &Stmt : *S) {
       OS.indent(Indent + 4) << Stmt.getBaseName() << "\n";
       for (auto *MA : Stmt)

 
 /// Implementation of the DeLICM/DePRE transformation.
 class DeLICMImpl : public ZoneAlgorithm {
 private:
   /// Knowledge before any transformation took place.
   Knowledge OriginalZone;
 
   /// Current knowledge of the SCoP including all already applied
   /// transformations.
   Knowledge Zone;
 
   /// For getting the MemoryAccesses that write or read a given scalar.
   ScalarDefUseChains DefUse;
 
   /// Number of StoreInsts something can be mapped to.
   int NumberOfCompatibleTargets = 0;
 
bool isConflicting(const Knowledge &Proposed) {
     return Knowledge::isConflicting(Zone, Proposed, OS, 4);
   }
 
   /// Determine whether @p SAI is a scalar that can be mapped to an array
   /// element.
   bool isMappable(const ScopArrayInfo *SAI) {
     assert(SAI);
 
     if (SAI->isValueKind()) {
       auto *MA = DefUse.getValueDef(SAI);
       if (!MA) {
         DEBUG(dbgs()
               << "    Reject because value is read-only within the scop\n");
         return false;
       }
 
       // Mapping if value is used after scop is not supported. The code
private:
   ///
   /// @return true if the scalar was successfully mapped.
   bool tryMapValue(const ScopArrayInfo *SAI, isl::map TargetElt) {
     assert(SAI->isValueKind());
 
     auto *DefMA = DefUse.getValueDef(SAI);
     assert(DefMA->isValueKind());
     assert(DefMA->isMustWrite());
+    auto *V = DefMA->getAccessValue();
+    auto *DefInst = DefMA->getAccessInstruction();
 
     // Stop if the scalar has already been mapped.
     if (!DefMA->getLatestScopArrayInfo()->isValueKind())
       return false;
 
     // { DomainDef[] -> Scatter[] }
     auto DefSched = getScatterFor(DefMA);
 
bool tryMapValue(const ScopArrayInfo *SAI, isl::map TargetElt) {
     std::tie(DefUses, Lifetime) = computeValueUses(SAI);
     DEBUG(dbgs() << "    Lifetime: " << Lifetime << '\n');
 
     /// { [Element[] -> Zone[]] }
     auto EltZone = give(
         isl_map_wrap(isl_map_apply_domain(Lifetime.copy(), DefTarget.copy())));
     simplify(EltZone);
 
-    // { [Element[] -> Scatter[]] }
-    auto DefEltSched = give(isl_map_wrap(isl_map_reverse(
-        isl_map_apply_domain(DefTarget.copy(), DefSched.copy()))));
+    // { DomainDef[] -> ValInst[] }
+    auto ValInst = makeValInst(V, DefMA->getStatement(), false,
+                               LI->getLoopFor(DefInst->getParent()), true);
+
+    // { DomainDef[] -> [Element[] -> Zone[]] }
+    auto EltKnownTranslator =
+        give(isl_map_range_product(DefTarget.copy(), Lifetime.copy()));
+
+    // { [Element[] -> Zone[]] -> ValInst[] }
+    auto EltKnown =
+        give(isl_map_apply_domain(ValInst.copy(), EltKnownTranslator.take()));
+    simplify(EltKnown);
+
+    // { DomainDef[] -> [Element[] -> Scatter[]] }
+    auto WrittenTranslator =
+        give(isl_map_range_product(DefTarget.copy(), DefSched.take()));
+
+    // { [Element[] -> Scatter[]] -> ValInst[] }
+    auto DefEltSched =
+        give(isl_map_apply_domain(ValInst.copy(), WrittenTranslator.take()));
     simplify(DefEltSched);
 
-    Knowledge Proposed(EltZone, nullptr, DefEltSched);
+    Knowledge Proposed(EltZone, nullptr, filterKnownValInst(EltKnown),
+                       DefEltSched);
     if (isConflicting(Proposed))
       return false;
 
     // { DomainUse[] -> Element[] }
     auto UseTarget = give(
         isl_union_map_apply_range(isl_union_map_reverse(DefUses.take()),
                                   isl_union_map_from_map(DefTarget.copy())));
 
void mapValue(const ScopArrayInfo *SAI, isl::map DefTarget,
     auto *WA = DefUse.getValueDef(SAI);
     WA->setNewAccessRelation(DefTarget.copy());
     applyLifetime(Proposed);
 
     MappedValueScalars++;
     NumberOfMappedValueScalars += 1;
   }
 
+  /// Express the incoming values of a PHI for each incoming statement in an
+  /// isl::union_map.
+  ///
+  /// @param SAI The PHI scalar represented by a ScopArrayInfo.
+  ///
+  /// @return { PHIWriteDomain[] -> ValInst[] }
+  isl::union_map determinePHIWrittenValues(const ScopArrayInfo *SAI) {
+    auto Result = makeEmptyUnionMap();
+
+    // Collect the incoming values.
+    for (auto *MA : DefUse.getPHIIncomings(SAI)) {
+      // { DomainWrite[] -> ValInst[] }
+      isl::union_map ValInst;
+      auto *WriteStmt = MA->getStatement();
+
+      auto Incoming = MA->getIncoming();
+      assert(!Incoming.empty());
+      if (Incoming.size() == 1) {
+        ValInst = makeValInst(Incoming[0].second, WriteStmt, false,
+                              LI->getLoopFor(Incoming[0].first), true);
+      } else {
+        // If the PHI is in a subregion's exit node it can have multiple
+        // incoming values (+ maybe another incoming edge from an unrelated
+        // block). We cannot directly represent it as a single llvm::Value.
+        // We currently model it as unknown value, but modeling as the PHIInst
+        // itself could be OK, too.
+        ValInst = makeUnknownForDomain(WriteStmt);
+      }
+
+      Result = give(isl_union_map_union(Result.take(), ValInst.take()));
+    }
+
+    assert(isl_union_map_is_single_valued(Result.keep()) == isl_bool_true &&
+           "Cannot have multiple incoming values for same incoming statement");
+    return Result;
+  }
+
   /// Try to map a MemoryKind::PHI scalar to a given array element.
   ///
   /// @param SAI       Representation of the scalar's memory to map.
   /// @param TargetElt { Scatter[] -> Element[] }
   ///                  Suggestion where to map the scalar to when at a
   ///                  timepoint.
   ///
   /// @return true if the PHI scalar has been mapped.
bool tryMapPHI(const ScopArrayInfo *SAI, isl::map TargetElt) {
     auto Lifetime = betweenScatter(PerPHIWriteScatter, PHISched, false, true);
     simplify(Lifetime);
     DEBUG(dbgs() << "    Lifetime: " << Lifetime << "\n");
 
     // { DomainWrite[] -> Zone[] }
     auto WriteLifetime = give(isl_union_map_apply_domain(
         isl_union_map_from_map(Lifetime.copy()), PerPHIWrites.copy()));
 
+    // { DomainWrite[] -> ValInst[] }
+    auto WrittenValue = determinePHIWrittenValues(SAI);
+
     // { DomainWrite[] -> [Element[] -> Scatter[]] }
     auto WrittenTranslator =
         give(isl_union_map_range_product(WritesTarget.copy(), Schedule.copy()));
 
-    // { [Element[] -> Scatter[]] }
-    auto Written = give(isl_union_map_range(WrittenTranslator.copy()));
+    // { [Element[] -> Scatter[]] -> ValInst[] }
+    auto Written = give(isl_union_map_apply_domain(WrittenValue.copy(),
+                                                   WrittenTranslator.copy()));
     simplify(Written);
 
     // { DomainWrite[] -> [Element[] -> Zone[]] }
     auto LifetimeTranslator = give(
-        isl_union_map_range_product(WritesTarget.copy(), WriteLifetime.take()));
+        isl_union_map_range_product(WritesTarget.copy(), WriteLifetime.copy()));
+
+    // { DomainWrite[] -> ValInst[] }
+    auto WrittenKnownValue = filterKnownValInst(WrittenValue);
+
+    // { [Element[] -> Zone[]] -> ValInst[] }
+    auto EltLifetimeInst = give(isl_union_map_apply_domain(
+        WrittenKnownValue.copy(), LifetimeTranslator.copy()));
+    simplify(EltLifetimeInst);
 
     // { [Element[] -> Zone[] }
     auto Occupied = give(isl_union_map_range(LifetimeTranslator.copy()));
     simplify(Occupied);
 
-    Knowledge Proposed(Occupied, nullptr, Written);
+    Knowledge Proposed(Occupied, nullptr, EltLifetimeInst, Written);
     if (isConflicting(Proposed))
       return false;
 
     mapPHI(SAI, std::move(PHITarget), std::move(WritesTarget),
            std::move(Lifetime), std::move(Proposed));
     return true;
   }
 
auto ProcessAllIncoming = [&](ScopStmt *Stmt) {
           continue;
 
         Worklist.push_back(MA);
       }
     };
 
     // Add initial scalar. Either the value written by the store, or all inputs
     // of its statement.
-    auto WrittenVal = TargetStoreMA->getAccessValue();
-    if (auto InputAcc = getInputAccessOf(WrittenVal, TargetStmt))
-      Worklist.push_back(InputAcc);
+    auto WrittenValUse = VirtualUse::create(
+        TargetStmt, TargetStoreMA->getAccessInstruction()->getOperandUse(0),
+        LI);
+    if (WrittenValUse.isInter())
+      Worklist.push_back(WrittenValUse.getMemAccess());
     else
       ProcessAllIncoming(TargetStmt);
 
     auto AnyMapped = false;
     auto &DL =
         S->getRegion().getEntry()->getParent()->getParent()->getDataLayout();
     auto StoreSize =
         DL.getTypeAllocSize(TargetStoreMA->getAccessValue()->getType());
auto ArrayUnused = computeArrayUnused(Schedule, AllMustWrites, AllReads,
                                           false, false, true);
 
     auto Result = give(isl_union_map_wrap(ArrayUnused.copy()));
 
     simplify(Result);
     return Result;
   }
 
-  /// Determine when an array element is written to.
+  isl::union_map computeKnownFromWrite() const {
+
+    // { [Element[] -> Zone[]] -> [Element[] -> DomainWrite[]]  }
+    auto EltReachdDef =
+        distributeDomain(give(isl_union_map_uncurry(WriteReachDefZone.copy())));
+
+    // { [Element[] -> DomainWrite[]] -> ValInst[] }
+    auto AllKnownWriteValInst = filterKnownValInst(AllWriteValInst);
+
+    // { [Element[] -> Zone[]] -> ValInst[] }
+    return EltReachdDef.apply_range(AllKnownWriteValInst);
+  }
+
+  isl::union_map computeKnownFromRead() const {
+    // { [Element[] -> Scatter[]] -> DomainWrite[] }
+    auto EltScatterWrite =
+        convertZoneToTimepoints(WriteReachDefZone, isl::dim::in, false, true);
+
+    // { [Element[] -> Zone[]] -> [Element[] -> DomainWrite[]] }
+    auto ZoneToWrite =
+        distributeDomain(give(isl_union_map_curry(WriteReachDefZone.copy())));
+
+    // { [Element[] -> DomainWrite[]] -> [Element[] -> Scatter[]] }
+    auto WriteToScatter =
+        distributeDomain(give(isl_union_map_curry(EltScatterWrite.copy())))
+            .reverse();
+
+    // { [DomainRead[] -> Scatter[]] -> Element[] }
+    auto ReadScatterElt = Schedule.domain_map().apply_range(AllReads);
+
+    // { [Element[] -> Scatter[]] -> [Element[] -> DomainRead[] }
+    auto ScatterToRead = distributeDomain(ReadScatterElt.reverse()).reverse();
+
+    // { [Element[] -> DomainRead[]] -> ValInst[] }
+    auto AllKnownReadValInst = filterKnownValInst(AllReadValInst);
+
+    // { [Element[] -> Zone[]] -> ValInst[] }
+    return ZoneToWrite.apply_range(WriteToScatter)
+        .apply_range(ScatterToRead)
+        .apply_range(AllKnownReadValInst);
+  }
+
+  /// Compute which value an array element stores at every instant.
   ///
-  /// @return { [Element[] -> Scatter[]] }
-  isl::union_set computeWritten() const {
-    // { WriteDomain[] -> Element[] }
-    auto AllWrites =
-        give(isl_union_map_union(AllMustWrites.copy(), AllMayWrites.copy()));
+  /// @return { [Element[] -> Zone[]] -> ValInst[] }
+  isl::union_map computeKnown() const {
+    auto KnownFromWrite = computeKnownFromWrite();
+    auto KnownFromRead = computeKnownFromRead();
 
-    // { Scatter[] -> Element[] }
-    auto WriteTimepoints =
-        give(isl_union_map_apply_domain(AllWrites.copy(), Schedule.copy()));
+    auto Known = KnownFromWrite.unite(KnownFromRead);
+    simplify(Known);
 
-    auto Result =
-        give(isl_union_map_wrap(isl_union_map_reverse(WriteTimepoints.copy())));
+    return Known;
+  }
 
-    simplify(Result);
-    return Result;
+  /// Determine when an array element is written to, and which value instance is
+  /// written.
+  ///
+  /// @return { [Element[] -> Scatter[]] -> ValInst[] }
+  isl::union_map computeWritten() const {
+    // { [Element[] -> Scatter[]] -> ValInst[] }
+    auto EltWritten = applyDomainRange(AllWriteValInst, Schedule);
+
+    simplify(EltWritten);
+    return EltWritten;
   }
 
   /// Determine whether an access touches at most one element.
   ///
   /// The accessed element could be a scalar or accessing an array with constant
   /// subscript, such that all instances access only that element.
   ///
   /// @param MA The access to test.
OS.indent(Indent + 4) << "PHI scalars mapped:    "
                           << NumberOfMappedPHIScalars << '\n';
     OS.indent(Indent) << "}\n";
   }
 
   /// Return whether at least one transformation been applied.
   bool isModified() const { return NumberOfTargetsMapped > 0; }
 
 public:
-  DeLICMImpl(Scop *S) : ZoneAlgorithm(S) {}
+  DeLICMImpl(Scop *S, LoopInfo *LI) : ZoneAlgorithm(S, LI) {}
 
   /// Calculate the lifetime (definition to last use) of every array element.
   ///
   /// @return True if the computed lifetimes (#Zone) is usable.
   bool computeZone() {
     // Check that nothing strange occurs.
     if (!isCompatibleScop()) {
       DeLICMIncompatible++;
       return false;
     }
 
     DefUse.compute(S);
-    isl::union_set EltUnused, EltWritten;
+    isl::union_set EltUnused;
+    isl::union_map EltKnown, EltWritten;
 
     {
       IslMaxOperationsGuard MaxOpGuard(IslCtx.get(), DelicmMaxOps);
 
       computeCommon();
 
       EltUnused = computeLifetime();
+      EltKnown = computeKnown();
       EltWritten = computeWritten();
     }
     DeLICMAnalyzed++;
 
-    if (!EltUnused || !EltWritten) {
+    if (!EltUnused || !EltKnown || !EltWritten) {
       assert(isl_ctx_last_error(IslCtx.get()) == isl_error_quota &&
              "The only reason that these things have not been computed should "
              "be if the max-operations limit hit");
       DeLICMOutOfQuota++;
       DEBUG(dbgs() << "DeLICM analysis exceeded max_operations\n");
       DebugLoc Begin, End;
       getDebugLocations(getBBPairForRegion(&S->getRegion()), Begin, End);
       OptimizationRemarkAnalysis R(DEBUG_TYPE, "OutOfQuota", Begin,
                                    S->getEntry());
       R << "maximal number of operations exceeded during zone analysis";
       S->getFunction().getContext().diagnose(R);
       return false;
     }
 
-    Zone = OriginalZone = Knowledge(nullptr, EltUnused, EltWritten);
+    Zone = OriginalZone = Knowledge(nullptr, EltUnused, EltKnown, EltWritten);
     DEBUG(dbgs() << "Computed Zone:\n"; OriginalZone.print(dbgs(), 4));
 
     assert(Zone.isUsable() && OriginalZone.isUsable());
     return true;
   }
 
   /// Try to map as many scalars to unused array elements as possible.
   ///

 private:
   DeLICM(const DeLICM &) = delete;
   const DeLICM &operator=(const DeLICM &) = delete;
 
   /// The pass implementation, also holding per-scop data.
   std::unique_ptr<DeLICMImpl> Impl;
 
   void collapseToUnused(Scop &S) {
-    Impl = make_unique<DeLICMImpl>(&S);
+    Impl = make_unique<DeLICMImpl>(
+        &S, &getAnalysis<LoopInfoWrapperPass>().getLoopInfo());
 
     if (!Impl->computeZone()) {
       DEBUG(dbgs() << "Abort because cannot reliably compute lifetimes\n");
       return;
     }
 
     DEBUG(dbgs() << "Collapsing scalars to unused array elements...\n");
     Impl->greedyCollapse();
 
     DEBUG(dbgs() << "\nFinal Scop:\n");
     DEBUG(S.print(dbgs()));
   }
 
 public:
   static char ID;
   explicit DeLICM() : ScopPass(ID) {}
 
   virtual void getAnalysisUsage(AnalysisUsage &AU) const override {
     AU.addRequiredTransitive<ScopInfoRegionPass>();
+    AU.addRequired<LoopInfoWrapperPass>();
     AU.setPreservesAll();
   }
 
   virtual bool runOnScop(Scop &S) override {
     // Free resources for previous scop's computation, if not yet done.
     releaseMemory();
 
     collapseToUnused(S);

 char DeLICM::ID;
 } // anonymous namespace
 
 Pass *polly::createDeLICMPass() { return new DeLICM(); }
 
 INITIALIZE_PASS_BEGIN(DeLICM, "polly-delicm", "Polly - DeLICM/DePRE", false,
                       false)
 INITIALIZE_PASS_DEPENDENCY(ScopInfoWrapperPass)
+INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
 INITIALIZE_PASS_END(DeLICM, "polly-delicm", "Polly - DeLICM/DePRE", false,
                     false)
 
-bool polly::isConflicting(isl::union_set ExistingOccupied,
-                          isl::union_set ExistingUnused,
-                          isl::union_set ExistingWrites,
-                          isl::union_set ProposedOccupied,
-                          isl::union_set ProposedUnused,
-                          isl::union_set ProposedWrites, llvm::raw_ostream *OS,
-                          unsigned Indent) {
+bool polly::isConflicting(
+    isl::union_set ExistingOccupied, isl::union_set ExistingUnused,
+    isl::union_map ExistingKnown, isl::union_map ExistingWrites,
+    isl::union_set ProposedOccupied, isl::union_set ProposedUnused,
+    isl::union_map ProposedKnown, isl::union_map ProposedWrites,
+    llvm::raw_ostream *OS, unsigned Indent) {
   Knowledge Existing(std::move(ExistingOccupied), std::move(ExistingUnused),
-                     std::move(ExistingWrites));
+                     std::move(ExistingKnown), std::move(ExistingWrites));
   Knowledge Proposed(std::move(ProposedOccupied), std::move(ProposedUnused),
-                     std::move(ProposedWrites));
+                     std::move(ProposedKnown), std::move(ProposedWrites));
 
   return Knowledge::isConflicting(Existing, Proposed, OS, Indent);
 }

test/DeLICM/reduction_known.ll

+; RUN: opt %loadPolly -polly-flatten-schedule -polly-delicm -analyze < %s | FileCheck %s
+;
+;    void func(double *A) {
+;      for (int j = 0; j < 2; j += 1) { /* outer */
+;        double phi = 0.0;
+;        for (int i = 0; i < 4; i += 1) /* reduction */
+;          phi += 4.2;
+;        A[j] = phi;
+;      }
+;    }
+;
+define void @func(double* noalias nonnull %A) {
+entry:
+  br label %outer.preheader
+
+outer.preheader:
+  br label %outer.for
+
+outer.for:
+  %j = phi i32 [0, %outer.preheader], [%j.inc, %outer.inc]
+  %j.cmp = icmp slt i32 %j, 2
+  br i1 %j.cmp, label %reduction.preheader, label %outer.exit
+
+
+    reduction.preheader:
+      br label %reduction.for
+
+    reduction.for:
+      %i = phi i32 [0, %reduction.preheader], [%i.inc, %reduction.inc]
+      %phi = phi double [0.0, %reduction.preheader], [%add, %reduction.inc]
+      %i.cmp = icmp slt i32 %i, 4
+      %A_idx = getelementptr inbounds double, double* %A, i32 %j
+      br i1 %i.cmp, label %body, label %reduction.exit
+
+
+
+        body:
+          %add = fadd double %phi, 4.2
+          store double %add, double* %A_idx
+          br label %reduction.inc
+
+
+
+    reduction.inc:
+      %i.inc = add nuw nsw i32 %i, 1
+      br label %reduction.for
+
+    reduction.exit:
+      store double %phi, double* %A_idx
+      br label %outer.inc
+
+
+
+outer.inc:
+  %j.inc = add nuw nsw i32 %j, 1
+  br label %outer.for
+
+outer.exit:
+  br label %return
+
+return:
+  ret void
+}
+
+
+; CHECK:      After accesses {
+; CHECK-NEXT:     Stmt_reduction_preheader
+; CHECK-NEXT:             MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 { Stmt_reduction_preheader[i0] -> MemRef_phi__phi[] };
+; CHECK-NEXT:            new: { Stmt_reduction_preheader[i0] -> MemRef_A[i0] : 0 <= i0 <= 1 };
+; CHECK-NEXT:     Stmt_reduction_for
+; CHECK-NEXT:             ReadAccess :=       [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 { Stmt_reduction_for[i0, i1] -> MemRef_phi__phi[] };
+; CHECK-NEXT:            new: { Stmt_reduction_for[i0, i1] -> MemRef_A[i0] : 0 <= i0 <= 1 and 0 <= i1 <= 4 };
+; CHECK-NEXT:             MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 { Stmt_reduction_for[i0, i1] -> MemRef_phi[] };
+; CHECK-NEXT:            new: { Stmt_reduction_for[i0, i1] -> MemRef_A[i0] : 0 <= i0 <= 1 and 0 <= i1 <= 4 };
+; CHECK-NEXT:     Stmt_body
+; CHECK-NEXT:             MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 { Stmt_body[i0, i1] -> MemRef_add[] };
+; CHECK-NEXT:            new: { Stmt_body[i0, i1] -> MemRef_A[i0] : 0 <= i0 <= 1 and 0 <= i1 <= 3 };
+; CHECK-NEXT:             ReadAccess :=       [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 { Stmt_body[i0, i1] -> MemRef_phi[] };
+; CHECK-NEXT:            new: { Stmt_body[i0, i1] -> MemRef_A[i0] : 0 <= i0 <= 1 and i1 >= 0 and -5i0 <= i1 <= 8 - 5i0 and i1 <= 3 };
+; CHECK-NEXT:             MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:                 { Stmt_body[i0, i1] -> MemRef_A[i0] };
+; CHECK-NEXT:     Stmt_reduction_inc
+; CHECK-NEXT:             ReadAccess :=       [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 { Stmt_reduction_inc[i0, i1] -> MemRef_add[] };
+; CHECK-NEXT:            new: { Stmt_reduction_inc[i0, i1] -> MemRef_A[i0] : i1 >= 0 and -5i0 <= i1 <= 7 - 5i0 and i1 <= 3; Stmt_reduction_inc[1, 3] -> MemRef_A[1] };
+; CHECK-NEXT:             MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 { Stmt_reduction_inc[i0, i1] -> MemRef_phi__phi[] };
+; CHECK-NEXT:            new: { Stmt_reduction_inc[i0, i1] -> MemRef_A[i0] : 0 <= i0 <= 1 and i1 >= 0 and -5i0 <= i1 <= 3 };
+; CHECK-NEXT:     Stmt_reduction_exit
+; CHECK-NEXT:             MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:                 { Stmt_reduction_exit[i0] -> MemRef_A[i0] };
+; CHECK-NEXT:             ReadAccess :=       [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 { Stmt_reduction_exit[i0] -> MemRef_phi[] };
+; CHECK-NEXT:            new: { Stmt_reduction_exit[i0] -> MemRef_A[i0] : 0 <= i0 <= 1 };
+; CHECK-NEXT: }

test/DeLICM/reduction_overapproximate.ll

 
 outer.exit:
   br label %return
 
 return:
   ret void
 }
 
-; TODO: MemRef_phi__phi[] should be mapped to A[j-1] as as well, but it is
-;       occupied by %add. It is actually the same value but DeLICM currently
-;       does not known without the "Known"-extension.
 
 ; APPROX:      After accesses {
 ; APPROX-NEXT:     Stmt_reduction_checkloop
 ; APPROX-NEXT:             MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
 ; APPROX-NEXT:                 { Stmt_reduction_checkloop[i0] -> MemRef_val__phi[] };
 ; APPROX-NEXT:            new: { Stmt_reduction_checkloop[i0] -> MemRef_A[-1 + i0] : 0 <= i0 <= 3 };
 ; APPROX-NEXT:     Stmt_reduction_preheader
 ; APPROX-NEXT:             MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
 ; APPROX-NEXT:                 { Stmt_reduction_preheader[i0] -> MemRef_phi__phi[] };
+; APPROX-NEXT:            new: { Stmt_reduction_preheader[i0] -> MemRef_A[-1 + i0] : 2 <= i0 <= 3 };
 ; APPROX-NEXT:     Stmt_reduction_for
 ; APPROX-NEXT:             ReadAccess :=       [Reduction Type: NONE] [Scalar: 1]
 ; APPROX-NEXT:                 { Stmt_reduction_for[i0, i1] -> MemRef_phi__phi[] };
+; APPROX-NEXT:            new: { Stmt_reduction_for[i0, i1] -> MemRef_A[-1 + i0] : i0 <= 3 and i1 >= 0 and 2 - 3i0 <= i1 <= 11 - 3i0 and i1 <= 2 and i1 <= -2 + i0 };
 ; APPROX-NEXT:             MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
 ; APPROX-NEXT:                 { Stmt_reduction_for[i0, i1] -> MemRef_phi[] };
 ; APPROX-NEXT:            new: { Stmt_reduction_for[i0, i1] -> MemRef_A[-1 + i0] : i0 <= 3 and i1 >= 0 and 2 - 3i0 <= i1 <= 11 - 3i0 and i1 <= 2 and i1 <= -2 + i0 };
 ; APPROX-NEXT:     Stmt_body
 ; APPROX-NEXT:            MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
 ; APPROX-NEXT:                { Stmt_body[i0, i1] -> MemRef_add[] };
 ; APPROX-NEXT:           new: { Stmt_body[i0, i1] -> MemRef_A[-1 + i0] : i0 <= 3 and i1 >= 0 and 2 - 3i0 <= i1 <= 10 - 3i0 and i1 <= 1 and i1 <= -2 + i0 };
 ; APPROX-NEXT:            ReadAccess :=       [Reduction Type: NONE] [Scalar: 1]
 ; APPROX-NEXT:                { Stmt_body[i0, i1] -> MemRef_phi[] };
 ; APPROX-NEXT:           new: { Stmt_body[i0, i1] -> MemRef_A[-1 + i0] : i0 <= 3 and 0 <= i1 <= -2 + i0 };
 ; APPROX-NEXT:     Stmt_reduction_inc
 ; APPROX-NEXT:             ReadAccess :=       [Reduction Type: NONE] [Scalar: 1]
 ; APPROX-NEXT:                 { Stmt_reduction_inc[i0, i1] -> MemRef_add[] };
 ; APPROX-NEXT:            new: { Stmt_reduction_inc[i0, i1] -> MemRef_A[-1 + i0] : i0 <= 3 and 0 <= i1 <= -2 + i0 };
 ; APPROX-NEXT:             MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
 ; APPROX-NEXT:                 { Stmt_reduction_inc[i0, i1] -> MemRef_phi__phi[] };
+; APPROX-NEXT:            new: { Stmt_reduction_inc[i0, i1] -> MemRef_A[2] : i0 <= 3 and 0 <= i1 <= -2 + i0 };
 ; APPROX-NEXT:             MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
 ; APPROX-NEXT:                 { Stmt_reduction_inc[i0, i1] -> MemRef_val__phi[] };
 ; APPROX-NEXT:            new: { Stmt_reduction_inc[i0, i1] -> MemRef_A[-1 + i0] : 2 <= i0 <= 3 and 0 <= i1 <= -2 + i0 };
 ; APPROX-NEXT:     Stmt_reduction_exit
 ; APPROX-NEXT:             ReadAccess :=       [Reduction Type: NONE] [Scalar: 1]
 ; APPROX-NEXT:                 { Stmt_reduction_exit[i0] -> MemRef_val__phi[] };
 ; APPROX-NEXT:            new: { Stmt_reduction_exit[i0] -> MemRef_A[-1 + i0] : 0 <= i0 <= 3 };
 ; APPROX-NEXT:             MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 0]
 ; APPROX-NEXT:                 { Stmt_reduction_exit[i0] -> MemRef_A[-1 + i0] };
 ; APPROX-NEXT: }
 
 
 ; EXACT: No modification has been made

unittests/DeLICM/DeLICMTest.cpp

 //===- DeLICMTest.cpp ----------------------------------------------------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #include "polly/DeLICM.h"
+#include "llvm/Support/Debug.h"
 #include "gtest/gtest.h"
 #include <isl/map.h>
 #include <isl/set.h>
 #include <isl/stream.h>
 #include <isl/union_map.h>
 #include <isl/union_set.h>
 #include <memory>
 
 using namespace llvm;
 using namespace polly;
 
 namespace {
 
 /// Get the universes of all spaces in @p USet.
 isl::union_set unionSpace(const isl::union_set &USet) {
   auto Result = give(isl_union_set_empty(isl_union_set_get_space(USet.keep())));
   foreachElt(USet, [=, &Result](isl::set Set) {
     auto Space = give(isl_set_get_space(Set.keep()));
     auto Universe = give(isl_set_universe(Space.take()));
     Result = give(isl_union_set_add_set(Result.take(), Universe.take()));
   });
   return Result;
 }
 
-void completeLifetime(isl::union_set Universe, isl::union_set &Unknown,
+void completeLifetime(isl::union_set Universe, isl::union_map OccupiedAndKnown,
+                      isl::union_set &Occupied, isl::union_map &Known,
                       isl::union_set &Undef) {
-  if (!Unknown) {
+  auto ParamSpace = give(isl_union_set_get_space(Universe.keep()));
+
+  if (OccupiedAndKnown) {
+    assert(!Occupied);
+    assert(!Known);
+
+    Known = isl::union_map::empty(ParamSpace);
+    Occupied = OccupiedAndKnown.domain();
+    foreachElt(OccupiedAndKnown, [&Known](isl::map Map) {
+      if (isl_map_has_tuple_name(Map.keep(), isl_dim_out) != isl_bool_true)
+        return;
+      Known = give(isl_union_map_add_map(Known.take(), Map.take()));
+    });
+  }
+
+  if (!Occupied) {
     assert(Undef);
-    Unknown = give(isl_union_set_subtract(Universe.copy(), Undef.copy()));
+    Occupied = give(isl_union_set_subtract(Universe.copy(), Undef.copy()));
   }
 
   if (!Undef) {
-    assert(Unknown);
-    Undef = give(isl_union_set_subtract(Universe.copy(), Unknown.copy()));
+    assert(Occupied);
+    Undef = give(isl_union_set_subtract(Universe.copy(), Occupied.copy()));
+  }
+
+  if (!Known) { // By default, nothin is known.
+    Known = isl::union_map::empty(ParamSpace);
   }
 }
 
 typedef struct {
   const char *OccupiedStr;
   const char *UndefStr;
   const char *WrittenStr;
-} Knowledge;
+} KnowledgeStr;
 
 isl::union_set parseSetOrNull(isl_ctx *Ctx, const char *Str) {
   if (!Str)
     return nullptr;
   return isl::union_set(Ctx, Str);
 }
 
-bool checkIsConflictingNonsymmetric(Knowledge Existing, Knowledge Proposed) {
+isl::union_map parseMapOrNull(isl_ctx *Ctx, const char *Str) {
+  if (!Str)
+    return nullptr;
+  return isl::union_map(Ctx, Str);
+}
+
+bool checkIsConflictingNonsymmetric(KnowledgeStr Existing,
+                                    KnowledgeStr Proposed) {
   std::unique_ptr<isl_ctx, decltype(&isl_ctx_free)> Ctx(isl_ctx_alloc(),
                                                         &isl_ctx_free);
 
   // Parse knowledge.
-  auto ExistingOccupied = parseSetOrNull(Ctx.get(), Existing.OccupiedStr);
+  auto ExistingOccupiedAndKnown =
+      parseMapOrNull(Ctx.get(), Existing.OccupiedStr);
   auto ExistingUnused = parseSetOrNull(Ctx.get(), Existing.UndefStr);
-  auto ExistingWritten = parseSetOrNull(Ctx.get(), Existing.WrittenStr);
+  auto ExistingWritten = parseMapOrNull(Ctx.get(), Existing.WrittenStr);
 
-  auto ProposedOccupied = parseSetOrNull(Ctx.get(), Proposed.OccupiedStr);
+  auto ProposedOccupiedAndKnown =
+      parseMapOrNull(Ctx.get(), Proposed.OccupiedStr);
   auto ProposedUnused = parseSetOrNull(Ctx.get(), Proposed.UndefStr);
-  auto ProposedWritten = parseSetOrNull(Ctx.get(), Proposed.WrittenStr);
+  auto ProposedWritten = parseMapOrNull(Ctx.get(), Proposed.WrittenStr);
 
   // Determine universe (set of all possible domains).
   auto Universe =
       give(isl_union_set_empty(isl_space_params_alloc(Ctx.get(), 0)));
-  if (ExistingOccupied)
-    Universe =
-        give(isl_union_set_union(Universe.take(), ExistingOccupied.copy()));
+  if (ExistingOccupiedAndKnown)
+    Universe = give(isl_union_set_union(
+        Universe.take(), ExistingOccupiedAndKnown.domain().take()));
   if (ExistingUnused)
     Universe =
         give(isl_union_set_union(Universe.take(), ExistingUnused.copy()));
   if (ExistingWritten)
-    Universe =
-        give(isl_union_set_union(Universe.take(), ExistingWritten.copy()));
-  if (ProposedOccupied)
-    Universe =
-        give(isl_union_set_union(Universe.take(), ProposedOccupied.copy()));
+    Universe = give(
+        isl_union_set_union(Universe.take(), ExistingWritten.domain().take()));
+  if (ProposedOccupiedAndKnown)
+    Universe = give(isl_union_set_union(
+        Universe.take(), ProposedOccupiedAndKnown.domain().take()));
   if (ProposedUnused)
     Universe =
         give(isl_union_set_union(Universe.take(), ProposedUnused.copy()));
   if (ProposedWritten)
-    Universe =
-        give(isl_union_set_union(Universe.take(), ProposedWritten.copy()));
+    Universe = give(
+        isl_union_set_union(Universe.take(), ProposedWritten.domain().take()));
+
+  // isl::id OtherId =  give( isl_id_alloc( Ctx.get(), "other", &OtherId));
+  // auto OtherSpace = give( isl_set_universe(  isl_space_set_tuple_id(
+  // isl_space_set_alloc(Ctx.get(), 0, 0 ), isl_dim_set, OtherId.copy())) );
+
   Universe = unionSpace(Universe);
 
   // Add a space the universe that does not occur anywhere else to ensure
   // robustness. Use &NewId to ensure that this Id is unique.
   isl::id NewId = give(isl_id_alloc(Ctx.get(), "Unrelated", &NewId));
   // The space must contains at least one dimension to allow order
   // modifications.
   auto NewSpace = give(isl_space_set_alloc(Ctx.get(), 0, 1));
   NewSpace =
       give(isl_space_set_tuple_id(NewSpace.take(), isl_dim_set, NewId.copy()));
   auto NewSet = give(isl_set_universe(NewSpace.take()));
   Universe = give(isl_union_set_add_set(Universe.take(), NewSet.take()));
 
   // Using the universe, fill missing data.
-  completeLifetime(Universe, ExistingOccupied, ExistingUnused);
-  completeLifetime(Universe, ProposedOccupied, ProposedUnused);
-
-  auto Result =
-      isConflicting(ExistingOccupied, ExistingUnused, ExistingWritten,
-                    ProposedOccupied, ProposedUnused, ProposedWritten);
+  isl::union_set ExistingOccupied;
+  isl::union_map ExistingKnown;
+  completeLifetime(Universe, ExistingOccupiedAndKnown, ExistingOccupied,
+                   ExistingKnown, ExistingUnused);
+
+  isl::union_set ProposedOccupied;
+  isl::union_map ProposedKnown;
+  completeLifetime(Universe, ProposedOccupiedAndKnown, ProposedOccupied,
+                   ProposedKnown, ProposedUnused);
+
+  auto Result = isConflicting(ExistingOccupied, ExistingUnused, ExistingKnown,
+                              ExistingWritten, ProposedOccupied, ProposedUnused,
+                              ProposedKnown, ProposedWritten, &llvm::dbgs());
 
+#if 0
   // isConflicting does not require ExistingOccupied nor ProposedUnused and are
   // implicitly assumed to be the remainder elements. Test the implicitness as
   // well.
   EXPECT_EQ(Result,
-            isConflicting(ExistingOccupied, ExistingUnused, ExistingWritten,
-                          ProposedOccupied, {}, ProposedWritten));
+            isConflicting(ExistingOccupied, ExistingUnused, ExistingKnown, ExistingWritten,
+                          ProposedOccupied,  {}, ProposedKnown, ProposedWritten));
   EXPECT_EQ(Result,
-            isConflicting({}, ExistingUnused, ExistingWritten, ProposedOccupied,
-                          ProposedUnused, ProposedWritten));
-  EXPECT_EQ(Result, isConflicting({}, ExistingUnused, ExistingWritten,
-                                  ProposedOccupied, {}, ProposedWritten));
+            isConflicting({}, ExistingUnused, ExistingKnown,ExistingWritten, ProposedOccupied,
+                          ProposedUnused,ProposedKnown, ProposedWritten));
+  EXPECT_EQ(Result, isConflicting({}, ExistingUnused, ExistingKnown,ExistingWritten,
+                                  ProposedOccupied, {},ProposedKnown, ProposedWritten));
+#endif
 
   return Result;
 }
 
-bool checkIsConflicting(Knowledge Existing, Knowledge Proposed) {
+bool checkIsConflicting(KnowledgeStr Existing, KnowledgeStr Proposed) {
   auto Forward = checkIsConflictingNonsymmetric(Existing, Proposed);
   auto Backward = checkIsConflictingNonsymmetric(Proposed, Existing);
 
   // isConflicting should be symmetric.
   EXPECT_EQ(Forward, Backward);
 
   return Forward || Backward;
 }
 
 TEST(DeLICM, isConflicting) {
 
   // Check occupied vs. occupied.
-  EXPECT_TRUE(
-      checkIsConflicting({"{ Dom[i] }", nullptr, "{}"}, {nullptr, "{}", "{}"}));
-  EXPECT_TRUE(checkIsConflicting({"{ Dom[i] }", nullptr, "{}"},
-                                 {"{ Dom[i] }", nullptr, "{}"}));
-  EXPECT_FALSE(checkIsConflicting({"{ Dom[0] }", nullptr, "{}"},
+  EXPECT_TRUE(checkIsConflicting({"{ Dom[i] -> [] }", nullptr, "{}"},
+                                 {nullptr, "{}", "{}"}));
+  EXPECT_TRUE(checkIsConflicting({"{ Dom[i] -> [] }", nullptr, "{}"},
+                                 {"{ Dom[i] -> [] }", nullptr, "{}"}));
+  EXPECT_FALSE(checkIsConflicting({"{ Dom[0] -> [] }", nullptr, "{}"},
+                                  {nullptr, "{ Dom[0] }", "{}"}));
+  EXPECT_FALSE(checkIsConflicting({"{ Dom[i] -> [] : i != 0 }", nullptr, "{}"},
+                                  {"{ Dom[0] -> [] }", nullptr, "{}"}));
+
+  // Check occupied vs. occupied with known values.
+  EXPECT_FALSE(checkIsConflicting({"{ Dom[i] -> Val[] }", nullptr, "{}"},
+                                  {"{ Dom[i] -> Val[] }", nullptr, "{}"}));
+  EXPECT_TRUE(checkIsConflicting({"{ Dom[i] -> ValA[] }", nullptr, "{}"},
+                                 {"{ Dom[i] -> ValB[] }", nullptr, "{}"}));
+  EXPECT_TRUE(checkIsConflicting({"{ Dom[i] -> Val[] }", nullptr, "{}"},
+                                 {"{ Dom[i] -> [] }", nullptr, "{}"}));
+  EXPECT_FALSE(checkIsConflicting({"{ Dom[0] -> Val[] }", nullptr, "{}"},
                                   {nullptr, "{ Dom[0] }", "{}"}));
-  EXPECT_FALSE(checkIsConflicting({"{ Dom[i] : i != 0 }", nullptr, "{}"},
-                                  {"{ Dom[0] }", nullptr, "{}"}));
 
   // Check occupied vs. written.
-  EXPECT_TRUE(
-      checkIsConflicting({nullptr, "{}", "{}"}, {"{}", nullptr, "{ Dom[0] }"}));
-  EXPECT_FALSE(
-      checkIsConflicting({"{}", nullptr, "{}"}, {"{}", nullptr, "{ Dom[0] }"}));
-
-  EXPECT_TRUE(checkIsConflicting({"{ Dom[i] }", nullptr, "{}"},
-                                 {"{}", nullptr, "{ Dom[0] }"}));
-  EXPECT_FALSE(checkIsConflicting({"{ DomA[i] }", nullptr, "{}"},
-                                  {"{}", nullptr, "{ DomB[0] }"}));
+  EXPECT_TRUE(checkIsConflicting({nullptr, "{}", "{}"},
+                                 {"{}", nullptr, "{ Dom[0] -> [] }"}));
+  EXPECT_FALSE(checkIsConflicting({"{}", nullptr, "{}"},
+                                  {"{}", nullptr, "{ Dom[0] -> [] }"}));
+  EXPECT_TRUE(checkIsConflicting({"{ Dom[i] -> [] }", nullptr, "{}"},
+                                 {"{}", nullptr, "{ Dom[0] -> [] }"}));
+  EXPECT_FALSE(checkIsConflicting({"{ DomA[i] -> [] }", nullptr, "{}"},
+                                  {"{}", nullptr, "{ DomB[0] -> [] }"}));
 
   // Dom[1] represents the time between 0 and 1. Now Proposed writes at timestep
   // 0 such that will have a different value between 0 and 1. Hence it is
   // conflicting with Existing.
-  EXPECT_TRUE(checkIsConflicting({"{ Dom[1] }", nullptr, "{}"},
-                                 {"{}", nullptr, "{ Dom[0] }"}));
-  EXPECT_FALSE(checkIsConflicting({"{ Dom[i] : i != 1 }", nullptr, "{}"},
-                                  {"{}", nullptr, "{ Dom[0] }"}));
+  EXPECT_TRUE(checkIsConflicting({"{ Dom[1] -> [] }", nullptr, "{}"},
+                                 {"{}", nullptr, "{ Dom[0] -> [] }"}));
+  EXPECT_FALSE(checkIsConflicting({"{ Dom[i] -> [] : i != 1 }", nullptr, "{}"},
+                                  {"{}", nullptr, "{ Dom[0] -> [] }"}));
+
+  // Check occupied vs. written with known values.
+  EXPECT_FALSE(checkIsConflicting({"{ Dom[i] -> Val[] }", nullptr, "{}"},
+                                  {"{}", nullptr, "{ Dom[0] -> Val[] }"}));
+  EXPECT_TRUE(checkIsConflicting({"{ Dom[i] -> ValA[] }", nullptr, "{}"},
+                                 {"{}", nullptr, "{ Dom[0] -> ValB[] }"}));
+  EXPECT_TRUE(checkIsConflicting({"{ Dom[i] -> Val[] }", nullptr, "{}"},
+                                 {"{}", nullptr, "{ Dom[0] -> [] }"}));
+  EXPECT_TRUE(checkIsConflicting({"{ Dom[i] -> [] }", nullptr, "{}"},
+                                 {"{}", nullptr, "{ Dom[0] -> Val[] }"}));
 
   // Check written vs. written.
-  EXPECT_TRUE(checkIsConflicting({"{}", nullptr, "{ Dom[0] }"},
-                                 {"{}", nullptr, "{ Dom[0] }"}));
-  EXPECT_FALSE(checkIsConflicting({"{}", nullptr, "{ Dom[-1] }"},
-                                  {"{}", nullptr, "{ Dom[0] }"}));
-  EXPECT_FALSE(checkIsConflicting({"{}", nullptr, "{ Dom[1] }"},
-                                  {"{}", nullptr, "{ Dom[0] }"}));
+  EXPECT_TRUE(checkIsConflicting({"{}", nullptr, "{ Dom[0] -> [] }"},
+                                 {"{}", nullptr, "{ Dom[0] -> [] }"}));
+  EXPECT_FALSE(checkIsConflicting({"{}", nullptr, "{ Dom[-1] -> [] }"},
+                                  {"{}", nullptr, "{ Dom[0] -> [] }"}));
+  EXPECT_FALSE(checkIsConflicting({"{}", nullptr, "{ Dom[1] -> [] }"},
+                                  {"{}", nullptr, "{ Dom[0] -> [] }"}));
+
+  // Check written vs. written with known values.
+  EXPECT_FALSE(checkIsConflicting({"{}", nullptr, "{ Dom[0] -> Val[] }"},
+                                  {"{}", nullptr, "{ Dom[0] -> Val[] }"}));
+  EXPECT_TRUE(checkIsConflicting({"{}", nullptr, "{ Dom[0] -> ValA[] }"},
+                                 {"{}", nullptr, "{ Dom[0] -> ValB[] }"}));
+  EXPECT_TRUE(checkIsConflicting({"{}", nullptr, "{ Dom[0] -> Val[] }"},
+                                 {"{}", nullptr, "{ Dom[0] -> [] }"}));
 }
 } // anonymous namespace

unittests/Isl/IslTest.cpp

TEST(DeLICM, convertZoneToTimepoints) {
   EXPECT_EQ(USET("{}"),
             convertZoneToTimepoints(USET("{ [0,1] }"), false, false));
   EXPECT_EQ(USET("{ [0,0] }"),
             convertZoneToTimepoints(USET("{ [0,1] }"), true, false));
   EXPECT_EQ(USET("{ [0,1] }"),
             convertZoneToTimepoints(USET("{ [0,1] }"), false, true));
   EXPECT_EQ(USET("{ [0,0]; [0,1] }"),
             convertZoneToTimepoints(USET("{ [0,1] }"), true, true));
+
+  // Map domains
+  EXPECT_EQ(UMAP("{}"), convertZoneToTimepoints(UMAP("{ [1] -> [] }"),
+                                                isl::dim::in, false, false));
+  EXPECT_EQ(UMAP("{ [0] -> [] }"),
+            convertZoneToTimepoints(UMAP("{ [1] -> [] }"), isl::dim::in, true,
+                                    false));
+  EXPECT_EQ(UMAP("{ [1] -> [] }"),
+            convertZoneToTimepoints(UMAP("{ [1] -> [] }"), isl::dim::in, false,
+                                    true));
+  EXPECT_EQ(
+      UMAP("{ [0] -> []; [1] -> [] }"),
+      convertZoneToTimepoints(UMAP("{ [1] -> [] }"), isl::dim::in, true, true));
+
+  // Map ranges
+  EXPECT_EQ(UMAP("{}"), convertZoneToTimepoints(UMAP("{ [] -> [1] }"),
+                                                isl::dim::out, false, false));
+  EXPECT_EQ(UMAP("{ [] -> [0] }"),
+            convertZoneToTimepoints(UMAP("{ [] -> [1] }"), isl::dim::out, true,
+                                    false));
+  EXPECT_EQ(UMAP("{ [] -> [1] }"),
+            convertZoneToTimepoints(UMAP("{ [] -> [1] }"), isl::dim::out, false,
+                                    true));
+  EXPECT_EQ(UMAP("{ [] -> [0]; [] -> [1] }"),
+            convertZoneToTimepoints(UMAP("{ [] -> [1] }"), isl::dim::out, true,
+                                    true));
+}
+
+TEST(DeLICM, distribute) {
+  std::unique_ptr<isl_ctx, decltype(&isl_ctx_free)> Ctx(isl_ctx_alloc(),
+                                                        &isl_ctx_free);
+
+  // Basic usage
+  EXPECT_EQ(MAP("{ [Domain[] -> Range1[]] -> [Domain[] -> Range2[]] }"),
+            distributeDomain(MAP("{ Domain[] -> [Range1[] -> Range2[]] }")));
+  EXPECT_EQ(
+      MAP("{ [Domain[i,j] -> Range1[i,k]] -> [Domain[i,j] -> Range2[j,k]] }"),
+      distributeDomain(MAP("{ Domain[i,j] -> [Range1[i,k] -> Range2[j,k]] }")));
+
+  // Union maps
+  EXPECT_EQ(
+      UMAP(
+          "{ [DomainA[i,j] -> RangeA1[i,k]] -> [DomainA[i,j] -> RangeA2[j,k]];"
+          "[DomainB[i,j] -> RangeB1[i,k]] -> [DomainB[i,j] -> RangeB2[j,k]] }"),
+      distributeDomain(
+          UMAP("{ DomainA[i,j] -> [RangeA1[i,k] -> RangeA2[j,k]];"
+               "DomainB[i,j] -> [RangeB1[i,k] -> RangeB2[j,k]] }")));
+}
+
+TEST(DeLICM, lift) {
+  std::unique_ptr<isl_ctx, decltype(&isl_ctx_free)> Ctx(isl_ctx_alloc(),
+                                                        &isl_ctx_free);
+
+  // Basic usage
+  EXPECT_EQ(UMAP("{ [Factor[] -> Domain[]] -> [Factor[] -> Range[]] }"),
+            liftDomains(UMAP("{ Domain[] -> Range[] }"), USET("{ Factor[] }")));
+  EXPECT_EQ(UMAP("{ [Factor[l] -> Domain[i,k]] -> [Factor[l] -> Range[j,k]] }"),
+            liftDomains(UMAP("{ Domain[i,k] -> Range[j,k] }"),
+                        USET("{ Factor[l] }")));
+
+  // Multiple maps in union
+  EXPECT_EQ(
+      UMAP("{ [FactorA[] -> DomainA[]] -> [FactorA[] -> RangeA[]];"
+           "[FactorB[] -> DomainA[]] -> [FactorB[] -> RangeA[]];"
+           "[FactorA[] -> DomainB[]] -> [FactorA[] -> RangeB[]];"
+           "[FactorB[] -> DomainB[]] -> [FactorB[] -> RangeB[]] }"),
+      liftDomains(UMAP("{ DomainA[] -> RangeA[]; DomainB[] -> RangeB[] }"),
+                  USET("{ FactorA[]; FactorB[] }")));
+}
+
+TEST(DeLICM, apply) {
+  std::unique_ptr<isl_ctx, decltype(&isl_ctx_free)> Ctx(isl_ctx_alloc(),
+                                                        &isl_ctx_free);
+
+  // Basic usage
+  EXPECT_EQ(
+      UMAP("{ [DomainDomain[] -> NewDomainRange[]] -> Range[] }"),
+      applyDomainRange(UMAP("{ [DomainDomain[] -> DomainRange[]] -> Range[] }"),
+                       UMAP("{ DomainRange[] -> NewDomainRange[] }")));
+  EXPECT_EQ(
+      UMAP("{ [DomainDomain[i,k] -> NewDomainRange[j,k,l]] -> Range[i,j] }"),
+      applyDomainRange(
+          UMAP("{ [DomainDomain[i,k] -> DomainRange[j,k]] -> Range[i,j] }"),
+          UMAP("{ DomainRange[j,k] -> NewDomainRange[j,k,l] }")));
+
+  // Multiple maps in union
+  EXPECT_EQ(UMAP("{ [DomainDomainA[] -> NewDomainRangeA[]] -> RangeA[];"
+                 "[DomainDomainB[] -> NewDomainRangeB[]] -> RangeB[] }"),
+            applyDomainRange(
+                UMAP("{ [DomainDomainA[] -> DomainRangeA[]] -> RangeA[];"
+                     "[DomainDomainB[] -> DomainRangeB[]] -> RangeB[] }"),
+                UMAP("{ DomainRangeA[] -> NewDomainRangeA[];"
+                     "DomainRangeB[] -> NewDomainRangeB[] }")));
 }
 
 } // anonymous namespace