Page MenuHomePhabricator

More detailed memory dependence checking between volatile and non-volatile accesses
ClosedPublic

Authored by kparzysz on Feb 3 2016, 8:34 AM.

Details

Summary

Don't automatically assume depedency if only one of the memory accesses in question is volatile. Defer the final determination of dependency to the alias analysis.
The (very simple) motivating example is added as a lit test.

Diff Detail

Repository
rL LLVM

Event Timeline

kparzysz updated this revision to Diff 46793.Feb 3 2016, 8:34 AM
kparzysz retitled this revision from to More detailed memory dependence checking between volatile and non-volatile accesses.
kparzysz updated this object.
kparzysz added a reviewer: dberlin.
kparzysz set the repository for this revision to rL LLVM.
kparzysz added a subscriber: llvm-commits.
dberlin edited edge metadata.Feb 4 2016, 4:04 PM

This looks correct to me, but nick and philip understand the ordering guarantees a lot better than I do :)

Philip, Nick---could you please review this?

reames edited edge metadata.Feb 22 2016, 10:24 AM

Minor code comments inline. Once addressed should be good to go after quick round of review.

The following is mostly to record my though process... no response needed and no action required.

The key issue here is one of semantics. We've been a bit unclear in the past as to whether volatile applied to *memory locations* or *memory accesses*. At first, it looks like your change is dependent on the location model, but it's not. You're simply allowing the non-ordered accessed to fall down into the generic may-alias handling below. This works with both models, but is optional for volatile-locations and required for volatile-access.

If we were going to move towards the volatile-locations model, that's something we'd need to discuss widely on llvm-dev. I'm mildly in favour of a volatile-access model, but don't know the C++ spec well enough to know what's actually required here. I'm also of the opinion that if we're going to treat a volatile as applying to *locations* we should consider teaching AA about this fact.

lib/Analysis/MemoryDependenceAnalysis.cpp
648 ↗(On Diff #46793)

This isn't quite right. You can't be less precise when lacking information about the querying instruction.

This needs to be:
if (SI->isVolatile()) {

if (!QueryInst)
  return a clobber;
if (!isSimple(QueryInst))
 return a clobber;

}

649 ↗(On Diff #46793)

Given we've got this same pattern in several places, please pull out a helper function along the lines of "bool isSimple(Instruction* I)". Could be a lambda, or a static function.

test/Transforms/GVN/volatile-nonvolatile.ll
3 ↗(On Diff #46793)

Stylistic suggestion: put the check lines immediate next to the function, add a CHECK-LABEL: @foo.

16 ↗(On Diff #46793)

Please add a couple of negative tests as well.

kparzysz updated this revision to Diff 48725.Feb 22 2016, 1:59 PM
kparzysz edited edge metadata.

Addressed Philip's comments.

reames accepted this revision.Feb 22 2016, 2:20 PM
reames edited edge metadata.

LGTM w/comment addressed.

lib/Analysis/MemoryDependenceAnalysis.cpp
654 ↗(On Diff #48725)

Huh, there's actually another bug here I hadn't noticed. We should be checking to see if the query instruction is another (potentially volatile) memory access. Simple reusing the isOtherMemoryAccess helper function would fix this.

(To be clear, this is not a new bug, but since we'll be exercising the code more, we should fix it here. Please add a test case as well.)

This revision is now accepted and ready to land.Feb 22 2016, 2:20 PM
This revision was automatically updated to reflect the committed changes.

Added the call to isOtherMemAccess.

I couldn't create a testcase. It seems like all cases of non-trivial memory accessing instructions (i.e. other than loads and stores) are handled in other parts of the code.

To clarify last comment: I tried creating a testcase using GVN and DSE, and in both cases, either the non-load-or-store instruction was handled by the optimization itself, or the "getDependence" function did not follow the desired path within the memory dependence analysis.

nicholas edited edge metadata.Feb 22 2016, 10:08 PM
nicholas added a subscriber: nicholas.

Krzysztof Parzyszek wrote:

kparzysz added a comment.

Philip, Nick---could you please review this?

It looks correct to me, but please wait for Philip.

I wish there were a testcase which demonstrated that two non-aliasing
volatile accesses were dependent, but I don't see any way to write that
test (maybe you can add more debug print statements to MemDep).

Nick

Hi,

in Chromium we have this snippet to force a heap overflow (to test asan instrumentation):

62	void AsanHeapOverflow() {
63	  scoped_ptr<int[]> array(new int[kArraySize]);
64	  // Declares the dummy value as volatile to make sure it doesn't get optimized
65	  // away.
66	  int volatile dummy = 0;
67	  dummy = array[kArraySize];
68	  base::debug::Alias(const_cast<int*>(&dummy));
69	}

This now no longer does an invalid write. I'm guessing this is an expected consequence of this change – what's the new way to express this?

I'm not sure that I understand this code---where is the invalid write? There is an out-of-bounds load, but I can't see any questionable stores.

Sorry, I meant "invalid read", not "invalid write".

GVN removes the load and replaces the uses of it with "undef". I guess the only certain way to keep the load is to make the array volatile:

void AsanHeapOverflow() {
  scoped_ptr<volatile int[]> array(new int[kArraySize]);
  int dummy = array[kArraySize];
}

I'm not sure what the last line does so my example does not include it.