[PPCG PATCH 1/2] gpu_group_references: check for overlapping writes again after merge

[skim...@kotnet.org]

From: Sven Verdoolaege <sk...@kotnet.org>

gpu_group_references calls group_writes (twice) for merging
reference groups that overlap, where two groups are considered
to overlap if they access the same elements and if at least one
of the two involves a write. However, the merged reference group
replaces one of the two groups and is only compared against groups
that this original group has not been compared against yet.
If, say, a read is first compared against another read and then
against a write, then it is combined with the write, but not with
the read, while this second read may very well overlap with the write,
resulting in incorrect code.
To avoid this problem, check for overlaps again as soon as
any other group was merged into the current group.

It is tricky to construct a test case that would fail without this fix
because the writes usually appear first in the list of references.
Reads can be moved ahead of writes to fill a hole left when merging
two other groups, but if this happens inside group_overlapping_writes,
then the read will likely still get merged in inside
group_depth_overlapping_writes.

Signed-off-by: Sven Verdoolaege <sk...@kotnet.org>
---
gpu_group.c | 10 +++++++++-
1 file changed, 9 insertions(+), 1 deletion(-)

diff --git a/gpu_group.c b/gpu_group.c
index 7b869b9..96df6af 100644
--- a/gpu_group.c
+++ b/gpu_group.c
@@ -1215,6 +1215,11 @@ static int compute_group_bounds(struct ppcg_kernel *kernel,
* then merge the two groups into one.
* If "compute_bounds" is set, then call compute_group_bounds
* on the merged groups.
+ * If any group is merged into the current group, then its access
+ * relation may have changed or it may have been turned into a write.
+ * The combined group might therefore overlap with groups that
+ * the original group did not overlap with. The groups therefore
+ * need to be checked again.
*
* Return the updated number of groups.
* Return -1 on error.
@@ -1226,8 +1231,10 @@ static int group_writes(struct ppcg_kernel *kernel,
struct gpu_group_data *data)
{
int i, j;
+ int any_merge;

- for (i = 0; i < n; ++i) {
+ for (i = 0; i < n; i += !any_merge) {
+ any_merge = 0;
for (j = n - 1; j > i; --j) {
if (!groups[i]->write && !groups[j]->write)
continue;
@@ -1235,6 +1242,7 @@ static int group_writes(struct ppcg_kernel *kernel,
if (!overlap(groups[i], groups[j]))
continue;

+ any_merge = 1;
groups[i] = join_groups_and_free(groups[i], groups[j]);
if (j != n - 1)
groups[j] = groups[n - 1];
--
2.7.4