search

arcana-lab / noelle

NOELLE Offers Empowering LLVM Extensions
MIT License
72 stars 35 forks source link

Fix call to call FDG generation bug #69

Closed vgene closed 1 year ago

vgene commented 1 year ago

Serious bug when generating function DG!

NOELLE does not construct most RAW memory dependences function call A to function call B in function DG. For now, I'm guessing the WAR deps stop mis-transformation from happening. But this has significant implications once full privatization support rolls out.

yiansu commented 1 year ago

The current code logic is actually not a bug but being bold in determining the dependence result between two calls. Below is the reason.

According to the definition of getModRefInfo from LLVM here. getModRefInfo returns Mod if call A writes to a memory location read or written by call B. Therefore, assuming the original result is sound, from call B's perspective, there are only three cases

  1. call B reads a memory location written by call A -> getModRefInfo(call B, call A) should return Ref result
  2. call B writes a memory location written by call A -> getModRefInfo(call B, call A) should return Mod result
  3. call B reads and writes a memory location written by call A -> getModRefInfo(call B, call A) should return ModRef result

However, if getModRefInfo(call B, call A) returns NoModRef result, this contradicts the above three cases and the only reason to that is because of the original Mod result is incorrect. As one should always being bold in interpreting the alias analysis result, there should be no dependence between these two calls.

Let me know if you're seeing a missing dependence between two calls due to this logic and I'd be happy to take a look.

vgene commented 1 year ago

The last branch on line 611 is MakeModRefEdge not NoModRef. Just think what happens if callA modref callB and callB modref callA. There should be all deps between them. In the current logic, there won't be a RAW edge.

vgene commented 1 year ago

Any NoModRef in any direction will remove all deps, which is handled earlier.

yiansu commented 1 year ago

Can we have a testable example highlighting the significance of this missing RAW dependence with the existence of both WAR and WAW dependence between two calls? From what I can tell, the existence of WAR and WAW dependencies are stronger restrictions that are already blocking most of the transformations (including privatization).

vgene commented 1 year ago

It depends on the client and CPF currently discards all false dependences in planning with the assumption of privatization.

PDG is supposed to be conservative. Any missing dependence at this level is a problem.

scampanoni commented 1 year ago

This has been fixed by last Yian's pull request.