Page MenuHomePhabricator

[LICM] Allow movement of non-aliasing calls that at most only write to memory
Needs ReviewPublic

Authored by ddcc on May 20 2020, 1:49 PM.

Details

Summary

This patch allows readnone/writeonly calls that at most only write to non-aliasing memory to be moved.

Diff Detail

Event Timeline

ddcc created this revision.May 20 2020, 1:49 PM
Herald added a project: Restricted Project. · View Herald TranscriptMay 20 2020, 1:49 PM
asbirlea requested changes to this revision.May 20 2020, 5:21 PM

Please check failing tests.

The idea does not seem right. If a call can only write and not read, it cannot necessarily be moved.

Your test2() example looks incorrect. If foo2b writes to str and foo2c reads from it and writes to it, then foo2c should read the value written inside the loop, which can be overwritten on different iterations.

Example:

  • foo2b writes value 2 to str.
  • foo2c reads value from str, increments by 1 and writes back.
  • loop runs 3 times.

With foo2b inside the loop, final value in str is 3.
With foo2b outside the loop, final value in str is 5.

I did not look at test1().

llvm/lib/Transforms/Scalar/LICM.cpp
1167

No reason to add the else when the if returns.

This revision now requires changes to proceed.May 20 2020, 5:21 PM
ddcc updated this revision to Diff 265421.May 20 2020, 10:31 PM

Check aliasing on arguments, update tests

ddcc added a comment.May 20 2020, 10:33 PM

The idea does not seem right. If a call can only write and not read, it cannot necessarily be moved.

Your test2() example looks incorrect. If foo2b writes to str and foo2c reads from it and writes to it, then foo2c should read the value written inside the loop, which can be overwritten on different iterations.

Example:

  • foo2b writes value 2 to str.
  • foo2c reads value from str, increments by 1 and writes back.
  • loop runs 3 times.

With foo2b inside the loop, final value in str is 3.
With foo2b outside the loop, final value in str is 5.

The intention is that given a function which only writes the values of its inputs elsewhere in memory without aliasing, calls to that function can be hoisted because they will still execute at least once. But, I was missing some noalias checks on the arguments, which are now fixed, because not reading through the argument doesn't mean that the underlying memory can't be otherwise accessed.

In this testcase, foo2c (now foo2d) may only write to str because of the writeonly attribute, but it can't be hoisted because it may read elsewhere from memory.

ddcc marked an inline comment as done.May 20 2020, 10:33 PM
ddcc updated this revision to Diff 265426.May 20 2020, 10:46 PM

Drop ineffective loop aliasing check

ddcc retitled this revision from [LICM] Allow movement of calls that at most only write to memory to [LICM] Allow movement of non-aliasing calls that at most only write to memory.May 20 2020, 10:51 PM
ddcc edited the summary of this revision. (Show Details)

Let's take the examples below, same scenario.

If @foo2e writes 2 to str, and @foo2f reads, increments by 1 and writes back, and the loop runs 3 times.
Code below gives result 3. When @foo2e is hoisted, the result is 5.
At the very least you need to check pointerInvalidatedByLoop for all call args.

declare void @foo2e(i8*) argmemonly writeonly nounwind
declare void @foo2f(i8*) nounwind

entry:
  %mem = call noalias i8* @malloc()
  %str = getelementptr inbounds [4 x i8], [4 x i8]* @str, i64 0, i64 0
  br label %loop
loop:
  call void @foo2e(i8* %mem)
  call void @foo2f(i8* %mem)
  br i1 %c, label %loop, label %out
out:
  ret void

For inaccessible memory, if two of the calls inside the loop write to that same inaccessible memory location, and one meets the condition to hoist, while the other also reads, then it's legal to hoist one of them?
@foo2e always writes 2 to that location.
@foo2f reads that location, increments by 1 and writes it back.
With an iteration count of 3, the original code will hold 3 at that location. After hoisting it will hold 5.

declare void @foo2e() inaccessiblemem writeonly nounwind
declare void @foo2f() nounwind

entry:
  %mem = call noalias i8* @malloc()
  %str = getelementptr inbounds [4 x i8], [4 x i8]* @str, i64 0, i64 0
  br label %loop
loop:
  call void @foo2e()
  call void @foo2f()
  br i1 %c, label %loop, label %out
out:
  ret void
ddcc added a comment.May 21 2020, 6:09 PM

Thanks for the feedback!

If @foo2e writes 2 to str, and @foo2f reads, increments by 1 and writes back, and the loop runs 3 times.
Code below gives result 3. When @foo2e is hoisted, the result is 5.
At the very least you need to check pointerInvalidatedByLoop for all call args.

I am missing a check on noalias arguments, but wouldn't it need to be for reference instead of modification (as implemented by pointerInvalidatedByLoop*)? For example, if the increment call (foo2f) occurred before the write call (foo2e), then it is no longer correct to hoist out the write either. I'm also not sure what to do with the MemorySSA variant when the AliasSetTracker is not available; MemorySSA seems to generate only a single MemoryDef for a call, which doesn't distinguish between definitions of arguments or other memory.

Instead, perhaps it'd be easier if I just limited this case to inaccessiblememonly calls with readnone arguments? That is my primary use case, anyway.

For inaccessible memory, if two of the calls inside the loop write to that same inaccessible memory location, and one meets the condition to hoist, while the other also reads, then it's legal to hoist one of them?
@foo2e always writes 2 to that location.
@foo2f reads that location, increments by 1 and writes it back.
With an iteration count of 3, the original code will hold 3 at that location. After hoisting it will hold 5.

That's a good point. The inaccessible memory that I'm interested in is memory-mapped from a hardware peripheral, so I know it doesn't alias, but I don't see a good way to express that with the existing function attributes. Even with LTO, there's no guarantee that an inaccessiblememonly function can't alias against another regular external function. The closest relevant attribute would be noalias, but that only applies to memory derived from input arguments, which would mean nothing on a readnone argument. I suppose what I'm looking for is some sort of exclusive attribute, which would indicate that the inaccessible memory can't be accessed in any other way.

Another potential issue is whether writeonly must be deterministic? readonly is guaranteed to be pure, but writeonly is only guaranteed to not read from memory or have other side-effects. For example, can a writeonly function access the timestamp counter and write only if the result is even?

ddcc added a comment.May 21 2020, 9:02 PM

Thanks for mentioning it; yeah, I think restrict support would be useful for functions that do access arguments, but it wouldn't cover aliasing in the second case between external functions with attributes that don't access arguments.

MSxDOS added a subscriber: MSxDOS.May 23 2020, 3:57 PM