Page MenuHomePhabricator

[DDG] Data Dependence Graph - Ordinals
ClosedPublic

Authored by bmahjour on Dec 3 2019, 2:03 PM.

Details

Summary

This patch associates ordinal numbers to the DDG Nodes allowing the builder to order nodes within a pi-block in program order. The algorithm works by simply assuming the order in which the BBList is fed into the builder. The builder already relies on the blocks being in program order so that it can compute the dependencies correctly. Similarly the order of instructions in their parent basic blocks determine their program order.

Diff Detail

Event Timeline

bmahjour created this revision.Dec 3 2019, 2:03 PM

I do not understand why the ordinals are necessary. For deterministic behavior, the deterministic iteration order over blocks and instructions should already ensure that (unless you are iterating over DenseMaps, which does not seem the case and is easily fixed). If for correctness, do you have an illustrative example when this would be critical?

llvm/lib/Analysis/DependenceGraphBuilder.cpp
56

Did you consider string the node ordinal in the Node directly instead of using a lookup table?

bmahjour marked 2 inline comments as done.EditedDec 5 2019, 1:40 PM

I do not understand why the ordinals are necessary. For deterministic behavior, the deterministic iteration order over blocks and instructions should already ensure that (unless you are iterating over DenseMaps, which does not seem the case and is easily fixed). If for correctness, do you have an illustrative example when this would be critical?

The nodes in a pi-block cannot be topologically sorted since they form a cycle. The ordinals help us put them in their original program order so as to preserve correctness. For example consider this case:

for (int i = 0; i < n-1; i++) {
  A[i] = B[i];
  B[i+1] = A[i];
}

There will be a pi-block consisting of all load and stores in the loop, and they cannot be sorted in the order of data dependence. We do not want to inadvertently change it to:

for (int i = 0; i < n-1; i++) {
  B[i+1] = A[i];
  A[i] = B[i];
}
llvm/lib/Analysis/DependenceGraphBuilder.cpp
56

Ordinal numbers take up space and are only needed during construction of the graph. The users of DDG don't need the ordinal, so I decided to save space and use the maps instead. The maps get cleared as soon as we are done with pi-block creation.

bmahjour marked an inline comment as done.Dec 12 2019, 9:58 AM

ping

The nodes in a pi-block cannot be topologically sorted since they form a cycle. The ordinals help us put them in their original program order so as to preserve correctness. For example consider this case:

for (int i = 0; i < n-1; i++) {
  A[i] = B[i];
  B[i+1] = A[i];
}

There will be a pi-block consisting of all load and stores in the loop, and they cannot be sorted in the order of data dependence. We do not want to inadvertently change it to:

for (int i = 0; i < n-1; i++) {
  B[i+1] = A[i];
  A[i] = B[i];
}

What would cause the order of nodes in a pi-node to change? As it's not topologically sorted, wouldn't the order stay the order in which they were added to NodeList?

What would cause the order of nodes in a pi-node to change? As it's not topologically sorted, wouldn't the order stay the order in which they were added to NodeList?

The order is at the mercy of SCCIterator. For example if you look at the first pi-block node in basic-a.ll, you'll notice that prior to this change the %inc = add i64 %i.02, 1 was placed ahead of %i.02 = phi .

Meinersbur accepted this revision.Dec 18 2019, 1:36 PM

The order is at the mercy of SCCIterator. For example if you look at the first pi-block node in basic-a.ll, you'll notice that prior to this change the %inc = add i64 %i.02, 1 was placed ahead of %i.02 = phi .

I see. Could you add that as a comment to either computeInstructionOrdinals and/or the invocation of llvm::sort.

LGTM

This revision is now accepted and ready to land.Dec 18 2019, 1:36 PM

The order is at the mercy of SCCIterator. For example if you look at the first pi-block node in basic-a.ll, you'll notice that prior to this change the %inc = add i64 %i.02, 1 was placed ahead of %i.02 = phi .

I see. Could you add that as a comment to either computeInstructionOrdinals and/or the invocation of llvm::sort.

Done.

This revision was automatically updated to reflect the committed changes.