[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

887–897

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.

920

Is this removed on purpose?

[protze.joachim]

Implement @Hahnfeld 's suggested changes

openmp/tools/archer/ompt-tsan.cpp

887–897

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.

920

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

else
       owner->returnData(static_cast<T *>(this));
   }
 
   virtual void Reset() = 0;
 
   PoolData(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 : PoolData<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 PoolData<DependencyData>::New();
+  }
+
+  DependencyData(DataPool<DependencyData> *dp) : PoolData<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 : PoolData<ParallelData> {
 
   // Parallel fork is just another barrier, use Barrier[1]
 
   /// Two addresses for relationships with barriers.
   ompt_tsan_clockid Barrier[2];
 
   const void *codePtr;
 
   void *GetParallelPtr() { return &(Barrier[1]); }
 
   void *GetBarrierPtr(unsigned Index) { return &(Barrier[Index]); }
 
   ParallelData *Init(const void *codeptr) { codePtr = codeptr; return this; }
 
   void Reset() {}
 
   static ParallelData *New(const void *codeptr) {
     return PoolData<ParallelData>::New()->Init(codeptr);
struct TaskData final : PoolData<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; }
   bool isMerged() { return TaskType & ompt_task_merged; }
 
   bool isExplicit() { return TaskType & ompt_task_explicit; }
   bool isImplicit() { return TaskType & ompt_task_implicit; }
   bool isInitial() { return TaskType & ompt_task_initial; }
   bool isTarget() { return TaskType & ompt_task_target; }
 
   void *GetTaskPtr() { return &Task; }
 
   void *GetTaskwaitPtr() { return &Taskwait; }
 
   TaskData *Init(TaskData *parent, int taskType) {
     TaskType = taskType;
     Parent = parent;
     Team = Parent->Team;
     if (Parent != nullptr) {
       Parent->RefCount++;
       // Copy over pointer to taskgroup. This task may set up its own stack
       // but for now belongs to its parent's taskgroup.
       TaskGroup = Parent->TaskGroup;
     }
     return this;
   }
 
   TaskData *Init(ParallelData *team, int taskType) {
     TaskType = taskType;
     execution = 1;
     ImplicitTask = this;
     Team = team;
     return this;
   }
 
   void Reset() {
     InBarrier = false;
     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 PoolData<TaskData>::New()->Init(parent, taskType);
   }
 
   static TaskData *New(ParallelData *team, int taskType) {
     return PoolData<TaskData>::New()->Init(team, taskType);
   }
 
   TaskData(DataPool<TaskData> *dp) : PoolData<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) {
     TsanHappensBefore(Data->GetTaskPtr());
     ToTaskData(parent_task_data)->execution++;
   }
 }
 
 static void __ompt_tsan_release_task(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 __ompt_tsan_release_dependencies(TaskData *task) {
+  for (unsigned i = 0; i < task->DependencyCount; i++) {
+    task->Dependencies[i].AnnotateEnd();
+  }
+}
+
+static void __ompt_tsan_acquire_dependencies(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,
   //     -> ignored
   //
   //    ompt_task_late_fulfill  = 6,
   //     -> first completed, first freed, second ignored
   //
   //    ompt_task_complete      = 1,
   //    ompt_task_cancel        = 3,
   //     -> first completed, first freed, second starts
   //
   //    ompt_task_detach        = 4,
   //    ompt_task_yield         = 2,
   //    ompt_task_switch        = 7
   //     -> first suspended, second starts
   //
 
   if (prior_task_status == ompt_task_early_fulfill)
     return;
 
   TaskData *FromTask = ToTaskData(first_task_data);
 
   // Legacy handling for missing reduction callback
   if (hasReductionCallback < ompt_set_always && FromTask->InBarrier) {
     // We want to ignore writes in the runtime code during barriers,
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);
-      }
-    }
+    __ompt_tsan_release_dependencies(FromTask);
     // free the previously running task
     __ompt_tsan_release_task(FromTask);
   }
 
   // For late fulfill of detached task, there is no task to schedule to
   if (prior_task_status == ompt_task_late_fulfill) {
     return;
   }
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));
-      }
-    }
+    __ompt_tsan_acquire_dependencies(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,
                                      const void *codeptr_ra) {
 
   // Acquire our own lock to make sure that
   // 1. the previous release has finished.
   // 2. the next acquire doesn't start before we have finished our release.
   LocksMutex.lock();
   std::mutex &Lock = Locks[wait_id];
   LocksMutex.unlock();
 
   Lock.lock();
   TsanHappensAfter(&Lock);
 }
 
 static void ompt_tsan_mutex_released(ompt_mutex_t kind, ompt_wait_id_t wait_id,
                                      const void *codeptr_ra) {
   LocksMutex.lock();
   std::mutex &Lock = Locks[wait_id];
   LocksMutex.unlock();
   TsanHappensBefore(&Lock);
 
   Lock.unlock();
 }
 
 // callback , signature , variable to store result , required support level
 #define SET_OPTIONAL_CALLBACK_T(event, type, result, level)                    \
   do {                                                                         \