[DependenceInfo] Remove access to WAW and WAR: Expose both as False [NFC]

[bollu]

Summary

This patch sets the stage for rework of the WAW and WAR dependences. The
migration is to store both the WAW and the WAR together in a single map
called as "False" (the false dependences). The motivation for this
change is explained below.

Motivation #1: semantics of isl_union_flow_get_{must|may}_dependence:

Code snippet for reference:

DependenceInfo.cpp:374-377

Flow = buildFlow(MustWrite, MustWrite, Read, Schedule);

WAW = isl_union_flow_get_must_dependence(Flow);

WAR = isl_union_flow_get_may_dependence(Flow);

isl_union_flow_get_may_dependence will return:

1. all dependences that start from a May source
2. dependences that start form a Must source but connect to a May source before reaching the Sink. In particular, something like: Sink <- ... <- May source <- ... <- Must source is counted as a *May* dependence.

1. isl_union_flow_get_must_dependence only returns dependences are of the form: Sink <- .. <No may source> .. <- Must source

Hence, in our case, we get too many WAR dependences, since something of
the form:

MustWrite <- Read <- MustWrite

is counted as WAR (may dependence).
Similary, we will have too little WAW (must) dependences.
Both our WAW and WAR computation will be incorrect due to the incorrect
call to buildFlow. This needs to be fixed later on.

However, to generate WAW and WAR dependences correctly, we will need 2
calls to buildFlow() - one for WAW and one for WAR, which is very expensive.
If we combine WAR and WAW into one map (False), we need only one call to
buildFlow() to build False.

There is only one place in Polly where we care about the
difference between a WAR and WAW:

lib/Transform/ScheduleOptimizer.cpp:containsOnlyMatMulDep()

This patch changes the function to not care about WAW dependence
exclusively. Now, there is effectively *no* place in polly where we ask
for WAW or WAR sepearately. So, combining them into a single map has no
functional difference in Polly.

We can migrate from storing WAW and WAR separately to storing them together as
False.

Motivation #2: take May writes into account, build TC_RED with alternate

strategy:

Currently, we are only considering MustWrite when building WAW and WAR.
We wish to also consider May-writes when building WAW and WAR.

1. This helps with correctness of WAW and WAR we track.
2. If we treat Reduction-like memory accesses as May-writes, we are able to compute TC_RED without actually incurring a call to the expensive isl_union_map_transitive_closure.

[grosser]

This looks good to me. As this is a rather large change, I would like to get an explicit OK from Michael and Roman.

include/polly/DependenceInfo.h

89

Why do you put this between TYPE_RED and TYPE_TC_RED. I would expect this to come before TYPE_RED.

[bollu]

Changed ordering of FALSE and RED in dependences type enum.

[gareevroman]

Hi Siddharth,

thanks for the patch!

However, to generate WAW and WAR dependences correctly, we will need 2
calls to buildFlow() - one for WAW and one for WAR, which is very expensive.

It would be great, if you could attach the results of the LLVM test-suite compile-time evaluation to show it.

There is only one place in Polly where we care about the
difference between a WAR and WAW:

lib/Transform/ScheduleOptimizer.cpp:containsOnlyMatMulDep()

This patch changes the function to not care about WAW dependence
exclusively.

Please see inline comments.

Also, please, prefix titles with "[Polly]".

include/polly/DependenceInfo.h

179

I'm not sure whether it's good to use variable names that are almost similar to reserved keywords. Could you rename it to, for example, FalseDep?

lib/CodeGen/IslAst.cpp

186

Why do you store the union of all dependences in Dep? We planned to check only RAW dependences here. Furthermore, we intended to check that there are no WAR dependences.

include/polly/DependenceInfo.h

struct Dependences {
   /// in which the reduction statements are executed does not matter. However,
   /// if they are executed in parallel we need to take additional measures
   /// (e.g, privatization) to ensure a correct result. The (reverse) transitive
   /// closure of the reduction dependences are used to check for parallel
   /// executed reduction statements during code generation. These dependences
   /// connect all instances of a reduction with each other, they are therefore
   /// cyclic and possibly "reversed".
   enum Type {
-    // Write after read
-    TYPE_WAR = 1 << 0,
-
     // Read after write
-    TYPE_RAW = 1 << 1,
+    TYPE_RAW = 1 << 0,
 
-    // Write after write
-    TYPE_WAW = 1 << 2,
+    // False dependences (write after write / write after read)
+    TYPE_FALSE = 1 << 2,
 
     // Reduction dependences
-    TYPE_RED = 1 << 3,
+    TYPE_RED = 1 << 1,
 
     // Transitive closure of the reduction dependences (& the reverse)
-    TYPE_TC_RED = 1 << 4,
+    TYPE_TC_RED = 1 << 3,
   };
 
   /// Get the dependences of type @p Kinds.
   ///
   /// @param Kinds This integer defines the different kinds of dependences
   ///              that will be returned. To return more than one kind, the
   ///              different kinds are 'ored' together.
   __isl_give isl_union_map *getDependences(int Kinds) const;
struct Dependences {
 
   /// Destructor that will free internal objects.
   ~Dependences() { releaseMemory(); }
 
 private:
   /// Create an empty dependences struct.
   explicit Dependences(const std::shared_ptr<isl_ctx> &IslCtx,
                        AnalysisLevel Level)
-      : RAW(nullptr), WAR(nullptr), WAW(nullptr), RED(nullptr), TC_RED(nullptr),
-        IslCtx(IslCtx), Level(Level) {}
+      : RAW(nullptr), WAR(nullptr), WAW(nullptr), False(nullptr), RED(nullptr),
+        TC_RED(nullptr), IslCtx(IslCtx), Level(Level) {}
 
   /// Calculate and add at the privatization dependences.
   void addPrivatizationDependences();
 
   /// Calculate the dependences for a certain SCoP @p S.
   void calculateDependences(Scop &S);
 
   /// Set the reduction dependences for @p MA to @p Deps.
   void setReductionDependences(MemoryAccess *MA, __isl_take isl_map *Deps);
 
   /// Free the objects associated with this Dependences struct.
   ///
   /// The Dependences struct will again be "empty" afterwards.
   void releaseMemory();
 
   /// The different basic kinds of dependences we calculate.
   isl_union_map *RAW;
   isl_union_map *WAR;
   isl_union_map *WAW;
+  isl_union_map *False;
 
   /// The special reduction dependences.
   isl_union_map *RED;
 
   /// The (reverse) transitive closure of reduction dependences.
   isl_union_map *TC_RED;
 
   /// Mapping from memory accesses to their reduction dependences.

lib/Analysis/DependenceInfo.cpp

DEBUG(dbgs() << "Read: " << Read << "\n";
 
     // End of max_operations scope.
   }
 
   if (isl_ctx_last_error(IslCtx.get()) == isl_error_quota) {
     isl_union_map_free(RAW);
     isl_union_map_free(WAW);
     isl_union_map_free(WAR);
-    RAW = WAW = WAR = nullptr;
+    RAW = WAW = WAR = False = nullptr;
     isl_ctx_reset_error(IslCtx.get());
   }
 
   // Drop out early, as the remaining computations are only needed for
   // reduction dependences or dependences that are finer than statement
   // level dependences.
   if (!HasReductions && Level == AL_Statement) {
     RED = isl_union_map_empty(isl_union_map_get_space(RAW));
     TC_RED = isl_union_map_empty(isl_union_set_get_space(TaggedStmtDomain));
     isl_union_set_free(TaggedStmtDomain);
+    False =
+        isl_union_map_union(isl_union_map_copy(WAW), isl_union_map_copy(WAR));
     return;
   }
 
   isl_union_map *STMT_RAW, *STMT_WAW, *STMT_WAR;
   STMT_RAW = isl_union_map_intersect_domain(
       isl_union_map_copy(RAW), isl_union_set_copy(TaggedStmtDomain));
   STMT_WAW = isl_union_map_intersect_domain(
       isl_union_map_copy(WAW), isl_union_set_copy(TaggedStmtDomain));
void Dependences::calculateDependences(Scop &S) {
   WAW = isl_union_map_union(WAW, STMT_WAW);
   WAR = isl_union_map_union(WAR, STMT_WAR);
 
   RAW = isl_union_map_coalesce(RAW);
   WAW = isl_union_map_coalesce(WAW);
   WAR = isl_union_map_coalesce(WAR);
   RED = isl_union_map_coalesce(RED);
   TC_RED = isl_union_map_coalesce(TC_RED);
+  False = isl_union_map_union(isl_union_map_copy(WAW), isl_union_map_copy(WAR));
 
   DEBUG(dump());
 }
 
 bool Dependences::isValidSchedule(Scop &S,
                                   StatementToIslMapTy *NewSchedule) const {
   if (LegalityCheckDisabled)
     return true;
 
-  isl_union_map *Dependences = getDependences(TYPE_RAW | TYPE_WAW | TYPE_WAR);
+  isl_union_map *Dependences = getDependences(TYPE_RAW | TYPE_FALSE);
   isl_space *Space = S.getParamSpace();
   isl_union_map *Schedule = isl_union_map_empty(Space);
 
   isl_space *ScheduleSpace = nullptr;
 
   for (ScopStmt &Stmt : S) {
     isl_map *StmtScat;
 
void Dependences::print(raw_ostream &OS) const {
   OS << "\tWAR dependences:\n\t\t";
   printDependencyMap(OS, WAR);
   OS << "\tWAW dependences:\n\t\t";
   printDependencyMap(OS, WAW);
   OS << "\tReduction dependences:\n\t\t";
   printDependencyMap(OS, RED);
   OS << "\tTransitive closure of reduction dependences:\n\t\t";
   printDependencyMap(OS, TC_RED);
+  OS << "\tFalse dependences:\n\t\t";
+  printDependencyMap(OS, False);
 }
 
 void Dependences::dump() const { print(dbgs()); }
 
 void Dependences::releaseMemory() {
   isl_union_map_free(RAW);
   isl_union_map_free(WAR);
   isl_union_map_free(WAW);
+  isl_union_map_free(False);
   isl_union_map_free(RED);
   isl_union_map_free(TC_RED);
 
-  RED = RAW = WAR = WAW = TC_RED = nullptr;
+  RED = RAW = WAR = WAW = TC_RED = False = nullptr;
 
   for (auto &ReductionDeps : ReductionDependences)
     isl_map_free(ReductionDeps.second);
   ReductionDependences.clear();
 }
 
 __isl_give isl_union_map *Dependences::getDependences(int Kinds) const {
   assert(hasValidDependences() && "No valid dependences available");
   isl_space *Space = isl_union_map_get_space(RAW);
   isl_union_map *Deps = isl_union_map_empty(Space);
 
   if (Kinds & TYPE_RAW)
     Deps = isl_union_map_union(Deps, isl_union_map_copy(RAW));
 
-  if (Kinds & TYPE_WAR)
-    Deps = isl_union_map_union(Deps, isl_union_map_copy(WAR));
-
-  if (Kinds & TYPE_WAW)
-    Deps = isl_union_map_union(Deps, isl_union_map_copy(WAW));
+  if (Kinds & TYPE_FALSE) {
+    Deps = isl_union_map_union(Deps, isl_union_map_copy(False));
+  }
 
   if (Kinds & TYPE_RED)
     Deps = isl_union_map_union(Deps, isl_union_map_copy(RED));
 
   if (Kinds & TYPE_TC_RED)
     Deps = isl_union_map_union(Deps, isl_union_map_copy(TC_RED));
 
   Deps = isl_union_map_coalesce(Deps);

lib/Analysis/PolyhedralInfo.cpp

bool PolyhedralInfo::checkParallel(Loop *L, isl_pw_aff **MinDepDistPtr) const {
   if (!S)
     return false;
   const Dependences &D =
       DI->getDependences(const_cast<Scop *>(S), Dependences::AL_Access);
   if (!D.hasValidDependences())
     return false;
   DEBUG(dbgs() << "Loop :\t" << L->getHeader()->getName() << ":\n");
 
-  isl_union_map *Deps =
-      D.getDependences(Dependences::TYPE_RAW | Dependences::TYPE_WAW |
-                       Dependences::TYPE_WAR | Dependences::TYPE_RED);
+  isl_union_map *Deps = D.getDependences(
+      Dependences::TYPE_RAW | Dependences::TYPE_FALSE | Dependences::TYPE_RED);
   DEBUG(dbgs() << "Dependences :\t" << stringFromIslObj(Deps) << "\n");
 
   isl_union_map *Schedule = getScheduleForLoop(S, L);
   DEBUG(dbgs() << "Schedule: \t" << stringFromIslObj(Schedule) << "\n");
 
   IsParallel = D.isParallel(Schedule, Deps, MinDepDistPtr);
   isl_union_map_free(Schedule);
   return IsParallel;

lib/CodeGen/IslAst.cpp

 /// (or non-zero) dependence distance on the dimension in question.
 static bool astScheduleDimIsParallel(__isl_keep isl_ast_build *Build,
                                      const Dependences *D,
                                      IslAstUserPayload *NodeInfo) {
   if (!D->hasValidDependences())
     return false;
 
   isl_union_map *Schedule = isl_ast_build_get_schedule(Build);
-  isl_union_map *Deps = D->getDependences(
-      Dependences::TYPE_RAW | Dependences::TYPE_WAW | Dependences::TYPE_WAR);
+  isl_union_map *Deps =
+      D->getDependences(Dependences::TYPE_RAW | Dependences::TYPE_FALSE);
 
   if (!D->isParallel(Schedule, Deps, &NodeInfo->MinimalDependenceDistance) &&
       !isl_union_map_free(Schedule))
     return false;
 
   isl_union_map *RedDeps = D->getDependences(Dependences::TYPE_TC_RED);
   if (!D->isParallel(Schedule, RedDeps))
     NodeInfo->IsReductionParallel = true;

lib/Transform/ScheduleOptimizer.cpp

 /// @param  D The SCoP dependencies.
 /// @param  Pos The parameter to desribe an acceptable true dependence.
 ///             In case it has a negative value, try to determine its
 ///             acceptable value.
 /// @return True in case dependencies correspond to the matrix multiplication
 ///         and false, otherwise.
 static bool containsOnlyMatMulDep(__isl_keep isl_map *Schedule,
                                   const Dependences *D, int &Pos) {
-  auto *WAR = D->getDependences(Dependences::TYPE_WAR);
-  if (!isl_union_map_is_empty(WAR)) {
-    isl_union_map_free(WAR);
-    return false;
-  }
-  isl_union_map_free(WAR);
-  auto *Dep = D->getDependences(Dependences::TYPE_RAW);
+
+  auto *Dep =
+      D->getDependences(Dependences::TYPE_RAW | Dependences::TYPE_FALSE);
   auto *Red = D->getDependences(Dependences::TYPE_RED);
   if (Red)
     Dep = isl_union_map_union(Dep, Red);
   auto *DomainSpace = isl_space_domain(isl_map_get_space(Schedule));
   auto *Space = isl_space_map_from_domain_and_range(isl_space_copy(DomainSpace),
                                                     DomainSpace);
   auto *Deltas = isl_map_deltas(isl_union_map_extract_map(Dep, Space));
   isl_union_map_free(Dep);
bool IslScheduleOptimizer::runOnScop(Scop &S) {
 
   if (!D.hasValidDependences())
     return false;
 
   isl_schedule_free(LastSchedule);
   LastSchedule = nullptr;
 
   // Build input data.
-  int ValidityKinds =
-      Dependences::TYPE_RAW | Dependences::TYPE_WAR | Dependences::TYPE_WAW;
+  int ValidityKinds = Dependences::TYPE_RAW | Dependences::TYPE_FALSE;
   int ProximityKinds;
 
   if (OptimizeDeps == "all")
-    ProximityKinds =
-        Dependences::TYPE_RAW | Dependences::TYPE_WAR | Dependences::TYPE_WAW;
+    ProximityKinds = Dependences::TYPE_RAW | Dependences::TYPE_FALSE;
   else if (OptimizeDeps == "raw")
     ProximityKinds = Dependences::TYPE_RAW;
   else {
     errs() << "Do not know how to optimize for '" << OptimizeDeps << "'"
            << " Falling back to optimizing all dependences.\n";
-    ProximityKinds =
-        Dependences::TYPE_RAW | Dependences::TYPE_WAR | Dependences::TYPE_WAW;
+    ProximityKinds = Dependences::TYPE_RAW | Dependences::TYPE_FALSE;
   }
 
   isl_union_set *Domain = S.getDomains();
 
   if (!Domain)
     return false;
 
   isl_union_map *Validity = D.getDependences(ValidityKinds);