# Efficient algorithm for generating data dependency DAG from lists of memory ranges and access modes

Assume you are given:

1. A list of N (not necessarily distinct) memory ranges of the form [x,y], where x and y are non-negative integers representing the lower and upper bounds of the range, and
2. A list of N memory access modes (read or write),

where the $i^{th}$ entry in the memory range list is accessed (either read from or written to) according to the $i^{th}$ entry in the data access modes list.

How do you efficiently generate a data dependency DAG representing the dependencies between subsequent accesses to possibly overlapping memory ranges?

The DAG should not have redundant dependencies. And ideally the algorithm should have running time quadratic in N (or better, if possible).

UPDATE: To clarify, a dependency between two memory accesses exists if

1. The two memory ranges being accessed overlap (i.e., have at least one byte in common), and
2. At least one of the access modes is a write (concurrent reads from the same memory range are ok).

Each update to the tree can be done in $O(\log N)$ time. Also, the overlap check can be done in $O(k + \log N)$ where $k$ is the number of intervals that overlap for that particular query.
The running time will depend on the size of the resulting dependency graph, but if that graph has $M$ edges, then the total running time will be $O(M + N \log N)$. In particular, since this DAG can have at most $O(N^2)$ edges, the algorithm certainly runs in $O(N^2)$ time -- and possibly much faster, if the resulting dependency DAG is sparse.