[OpenMP][Tools] Fix Archer handling of task dependencies

[protze.joachim]

Summary

The current handling of dependencies in Archer has two flaws:

• annotation of dependency synchronization is not limited to sibling tasks
• annotation of in/out dependencies is based on the assumption, that dependency variables will rarely be byte-sized variables.

This patch introduces a map in the generating task to manage the dependency variables for the child tasks. The map is only accesses from the generating task, so no locking is necessary. This limits the dependency-based synchronization to sibling tasks.
This patch also introduces proper handling for new dependency types such as mutexinoutset and inoutset.

[Hahnfeld]

I think at least this patch needs a clang-format, maybe also applies to the other recent patches.

openmp/tools/archer/ompt-tsan.cpp

886–896

Can we name internal functions without double underscores, which are actually not allowed by the standard? (__ompt_tsan_release_task should be renamed eventually) Also I understand release + acquire semantics, but "release" is actually a bit confusing because it's not about actually releasing the memory AFAICT. I understand it already was confusing before, but if somebody has a better proposal for naming (I don't right now) that would be great.

921

Is this removed on purpose?

[protze.joachim]

Implement @Hahnfeld 's suggested changes

openmp/tools/archer/ompt-tsan.cpp

886–896

Since we a mid-term goal should be to refactor towards LLVM coding style, I changed the function names to use camelCase as required for function names.

I could live with renaming the task memory release function (__ompt_tsan_release_task) to freeTask.
The acquire/release refers to the similar semantics of locks.

921

Good catch! I missed this intermediate change in separating the changes into multiple patches.

[protze.joachim]

Applied a more recent version of clang-format

[Hahnfeld]

LGTM, thanks

openmp/tools/archer/ompt-tsan.cpp

if (owner == DataPool<T>::ThreadDataPool)
       owner->returnOwnData(static_cast<T *>(this));
     else
       owner->returnData(static_cast<T *>(this));
   }
 
   DataPoolEntry(DataPool<T> *dp) : owner(dp) {}
 };
 
+struct DependencyData;
+typedef DataPool<DependencyData> DependencyDataPool;
+template <>
+__thread DependencyDataPool *DependencyDataPool::ThreadDataPool = nullptr;
+
+/// Data structure to store additional information for task dependency.
+struct DependencyData final : DataPoolEntry<DependencyData> {
+  ompt_tsan_clockid in;
+  ompt_tsan_clockid out;
+  ompt_tsan_clockid inoutset;
+  void *GetInPtr() { return &in; }
+  void *GetOutPtr() { return &out; }
+  void *GetInoutsetPtr() { return &inoutset; }
+
+  void Reset() {}
+
+  static DependencyData *New() { return DataPoolEntry<DependencyData>::New(); }
+
+  DependencyData(DataPool<DependencyData> *dp)
+      : DataPoolEntry<DependencyData>(dp) {}
+};
+
+struct TaskDependency {
+  void *inPtr;
+  void *outPtr;
+  void *inoutsetPtr;
+  ompt_dependence_type_t type;
+  TaskDependency(DependencyData *depData, ompt_dependence_type_t type)
+      : inPtr(depData->GetInPtr()), outPtr(depData->GetOutPtr()),
+        inoutsetPtr(depData->GetInoutsetPtr()), type(type) {}
+  void AnnotateBegin() {
+    if (type == ompt_dependence_type_out ||
+        type == ompt_dependence_type_inout ||
+        type == ompt_dependence_type_mutexinoutset) {
+      TsanHappensAfter(inPtr);
+      TsanHappensAfter(outPtr);
+      TsanHappensAfter(inoutsetPtr);
+    } else if (type == ompt_dependence_type_in) {
+      TsanHappensAfter(outPtr);
+      TsanHappensAfter(inoutsetPtr);
+    } else if (type == ompt_dependence_type_inoutset) {
+      TsanHappensAfter(inPtr);
+      TsanHappensAfter(outPtr);
+    }
+  }
+  void AnnotateEnd() {
+    if (type == ompt_dependence_type_out ||
+        type == ompt_dependence_type_inout ||
+        type == ompt_dependence_type_mutexinoutset) {
+      TsanHappensBefore(outPtr);
+    } else if (type == ompt_dependence_type_in) {
+      TsanHappensBefore(inPtr);
+    } else if (type == ompt_dependence_type_inoutset) {
+      TsanHappensBefore(inoutsetPtr);
+    }
+  }
+};
+
 struct ParallelData;
 typedef DataPool<ParallelData> ParallelDataPool;
 template <>
 __thread ParallelDataPool *ParallelDataPool::ThreadDataPool = nullptr;
 
 /// Data structure to store additional information for parallel regions.
 struct ParallelData final : DataPoolEntry<ParallelData> {
 
struct TaskData final : DataPoolEntry<TaskData> {
   /// Reference to the team of this task.
   ParallelData *Team{nullptr};
 
   /// Reference to the current taskgroup that this task either belongs to or
   /// that it just created.
   Taskgroup *TaskGroup{nullptr};
 
   /// Dependency information for this task.
-  ompt_dependence_t *Dependencies{nullptr};
+  TaskDependency *Dependencies{nullptr};
 
   /// Number of dependency entries.
   unsigned DependencyCount{0};
 
+  // The dependency-map stores DependencyData objects representing
+  // the dependency variables used on the sibling tasks created from
+  // this task
+  // We expect a rare need for the dependency-map, so alloc on demand
+  std::unordered_map<void *, DependencyData *> *DependencyMap{nullptr};
+
 #ifdef DEBUG
   int freed{0};
 #endif
 
   bool isIncluded() { return TaskType & ompt_task_undeferred; }
   bool isUntied() { return TaskType & ompt_task_untied; }
   bool isFinal() { return TaskType & ompt_task_final; }
   bool isMergable() { return TaskType & ompt_task_mergeable; }
void Reset() {
     TaskType = 0;
     execution = 0;
     BarrierIndex = 0;
     RefCount = 1;
     Parent = nullptr;
     ImplicitTask = nullptr;
     Team = nullptr;
     TaskGroup = nullptr;
+    if (DependencyMap) {
+      for (auto i : *DependencyMap)
+        i.second->Delete();
+      delete DependencyMap;
+    }
+    DependencyMap = nullptr;
+    if (Dependencies)
+      free(Dependencies);
     Dependencies = nullptr;
     DependencyCount = 0;
 #ifdef DEBUG
     freed = 0;
 #endif
   }
 
   static TaskData *New(TaskData *parent, int taskType) {
     return DataPoolEntry<TaskData>::New()->Init(parent, taskType);
   }
 
   static TaskData *New(ParallelData *team, int taskType) {
     return DataPoolEntry<TaskData>::New()->Init(team, taskType);
   }
 
   TaskData(DataPool<TaskData> *dp) : DataPoolEntry<TaskData>(dp) {}
 };
 
 static inline TaskData *ToTaskData(ompt_data_t *task_data) {
   return reinterpret_cast<TaskData *>(task_data->ptr);
 }
 
-static inline void *ToInAddr(void *OutAddr) {
-  // FIXME: This will give false negatives when a second variable lays directly
-  //        behind a variable that only has a width of 1 byte.
-  //        Another approach would be to "negate" the address or to flip the
-  //        first bit...
-  return reinterpret_cast<char *>(OutAddr) + 1;
-}
-
 /// Store a mutex for each wait_id to resolve race condition with callbacks.
 std::unordered_map<ompt_wait_id_t, std::mutex> Locks;
 std::mutex LocksMutex;
 
 static void ompt_tsan_thread_begin(ompt_thread_t thread_type,
                                    ompt_data_t *thread_data) {
   ParallelDataPool::ThreadDataPool = new ParallelDataPool;
   TsanNewMemory(ParallelDataPool::ThreadDataPool,
                 sizeof(ParallelDataPool::ThreadDataPool));
   TaskgroupPool::ThreadDataPool = new TaskgroupPool;
   TsanNewMemory(TaskgroupPool::ThreadDataPool,
                 sizeof(TaskgroupPool::ThreadDataPool));
   TaskDataPool::ThreadDataPool = new TaskDataPool;
   TsanNewMemory(TaskDataPool::ThreadDataPool,
                 sizeof(TaskDataPool::ThreadDataPool));
+  DependencyDataPool::ThreadDataPool = new DependencyDataPool;
+  TsanNewMemory(DependencyDataPool::ThreadDataPool,
+                sizeof(DependencyDataPool::ThreadDataPool));
   thread_data->value = my_next_id();
 }
 
 static void ompt_tsan_thread_end(ompt_data_t *thread_data) {
+  TsanIgnoreWritesBegin();
   delete ParallelDataPool::ThreadDataPool;
   delete TaskgroupPool::ThreadDataPool;
   delete TaskDataPool::ThreadDataPool;
+  delete DependencyDataPool::ThreadDataPool;
+  TsanIgnoreWritesEnd();
 }
 
 /// OMPT event callbacks for handling parallel regions.
 
 static void ompt_tsan_parallel_begin(ompt_data_t *parent_task_data,
                                      const ompt_frame_t *parent_task_frame,
                                      ompt_data_t *parallel_data,
                                      uint32_t requested_team_size, int flag,
if (type & ompt_task_initial) {
     // Use the newly created address. We cannot use a single address from the
     // parent because that would declare wrong relationships with other
     // sibling tasks that may be created before this task is started!
     TsanHappensBefore(Data->GetTaskPtr());
     ToTaskData(parent_task_data)->execution++;
   }
 }
 
-static void __ompt_tsan_release_task(TaskData *task) {
+static void freeTask(TaskData *task) {
   while (task != nullptr && --task->RefCount == 0) {
     TaskData *Parent = task->Parent;
-    if (task->DependencyCount > 0) {
-      delete[] task->Dependencies;
-    }
     task->Delete();
     task = Parent;
   }
 }
 
+static void releaseDependencies(TaskData *task) {
+  for (unsigned i = 0; i < task->DependencyCount; i++) {
+    task->Dependencies[i].AnnotateEnd();
+  }
+}
+
+static void acquireDependencies(TaskData *task) {
+  for (unsigned i = 0; i < task->DependencyCount; i++) {
+    task->Dependencies[i].AnnotateBegin();
+  }
+}
+
 static void ompt_tsan_task_schedule(ompt_data_t *first_task_data,
                                     ompt_task_status_t prior_task_status,
                                     ompt_data_t *second_task_data) {
 
   //
   //  The necessary action depends on prior_task_status:
   //
   //    ompt_task_early_fulfill = 5,
if (!FromTask->isIncluded()) {
       if (FromTask->TaskGroup != nullptr) {
         // This task is part of a taskgroup, so it will finish before the
         // corresponding taskgroup_end.
         TsanHappensBefore(FromTask->TaskGroup->GetPtr());
       }
     }
 
     // release dependencies
-    for (unsigned i = 0; i < FromTask->DependencyCount; i++) {
-      ompt_dependence_t *Dependency = &FromTask->Dependencies[i];
-
-      // in dependencies block following inout and out dependencies!
-      TsanHappensBefore(ToInAddr(Dependency->variable.ptr));
-      if (Dependency->dependence_type == ompt_dependence_type_out ||
-          Dependency->dependence_type == ompt_dependence_type_inout) {
-        TsanHappensBefore(Dependency->variable.ptr);
-      }
-    }
+    releaseDependencies(FromTask);
     // free the previously running task
-    __ompt_tsan_release_task(FromTask);
+    freeTask(FromTask);
   }
 
   // For late fulfill of detached task, there is no task to schedule to
   if (prior_task_status == ompt_task_late_fulfill) {
     return;
   }
 
   TaskData *ToTask = ToTaskData(second_task_data);
if (prior_task_status == ompt_task_switch ||
     TsanHappensBefore(FromTask->GetTaskPtr());
     ToTask->ImplicitTask = FromTask->ImplicitTask;
     assert(ToTask->ImplicitTask != NULL &&
            "A task belongs to a team and has an implicit task on the stack");
   }
 
   // Handle dependencies on first execution of the task
   if (ToTask->execution == 0) {
     ToTask->execution++;
-    for (unsigned i = 0; i < ToTask->DependencyCount; i++) {
-      ompt_dependence_t *Dependency = &ToTask->Dependencies[i];
-
-      TsanHappensAfter(Dependency->variable.ptr);
-      // in and inout dependencies are also blocked by prior in dependencies!
-      if (Dependency->dependence_type == ompt_dependence_type_out ||
-          Dependency->dependence_type == ompt_dependence_type_inout) {
-        TsanHappensAfter(ToInAddr(Dependency->variable.ptr));
-      }
-    }
+    acquireDependencies(ToTask);
   }
   // 1. Task will begin execution after it has been created.
   // 2. Task will resume after it has been switched away.
   TsanHappensAfter(ToTask->GetTaskPtr());
 }
 
 static void ompt_tsan_dependences(ompt_data_t *task_data,
                                   const ompt_dependence_t *deps, int ndeps) {
   if (ndeps > 0) {
     // Copy the data to use it in task_switch and task_end.
     TaskData *Data = ToTaskData(task_data);
-    Data->Dependencies = new ompt_dependence_t[ndeps];
-    std::memcpy(Data->Dependencies, deps, sizeof(ompt_dependence_t) * ndeps);
+    if (!Data->Parent->DependencyMap)
+      Data->Parent->DependencyMap =
+          new std::unordered_map<void *, DependencyData *>();
+    Data->Dependencies =
+        (TaskDependency *)malloc(sizeof(TaskDependency) * ndeps);
     Data->DependencyCount = ndeps;
+    for (int i = 0; i < ndeps; i++) {
+      auto ret = Data->Parent->DependencyMap->insert(
+          std::make_pair(deps[i].variable.ptr, nullptr));
+      if (ret.second) {
+        ret.first->second = DependencyData::New();
+      }
+      new ((void *)(Data->Dependencies + i))
+          TaskDependency(ret.first->second, deps[i].dependence_type);
+    }
 
     // This callback is executed before this task is first started.
     TsanHappensBefore(Data->GetTaskPtr());
   }
 }
 
 /// OMPT event callbacks for handling locking.
 static void ompt_tsan_mutex_acquired(ompt_mutex_t kind, ompt_wait_id_t wait_id,