Navigation Menu

Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

LICM introduces load in writeonly function (UB) #51248

Open
nunoplopes opened this issue Sep 19, 2021 · 4 comments
Open

LICM introduces load in writeonly function (UB) #51248

nunoplopes opened this issue Sep 19, 2021 · 4 comments
Labels

Comments

@nunoplopes
Copy link
Member

nunoplopes commented Sep 19, 2021

Bugzilla Link 51906
Version trunk
OS All
CC @aeubanks,@alinas,@fhahn,@nikic,@Kojoley,@regehr,@Vsevolod-Livinskij,@whitneywhtsang

Extended Description

LICM transforms this:

for (i=0; i < 4; i += 4)
  store @glb, some-expr
=>
tmp = load @lgb
compute some-expr
for (i=0; i < 4; i += 4)
  tmp = expr
store @glb, tmp

For functions that are writeonly this introduces UB as the original function had no load and the optimized now has a load from global memory.
The second issue is the store introduction. I didn't check if the store is introduced for loops that are not guaranteed to execute, but if that's the case that may violate C++'s memory model (where I believe you cannot introduce stores).

@glb = external global i8, align 1

define void @test(i8 %var) writeonly {
entry:
  br label %for.cond

for.cond:
  %i = phi i64 [ 0, %entry ], [ %add, %cond.end ]
  %cmp = icmp ult i64 %i, 4
  br i1 %cmp, label %for.body39, label %for.end

for.body39:
  %div = sdiv i8 %var, 3
  %cmp2 = icmp slt i8 %div, 0
  br i1 %cmp2, label %cond.true, label %cond.false

cond.true:
  br label %cond.end

cond.false:
  br label %cond.end

cond.end:
  %merge = phi i8 [ %div, %cond.true ], [ 0, %cond.false ]
  store i8 %merge, i8* @glb, align 1
  %add = add i64 %i, 4
  br label %for.cond

for.end:
  ret void
}

After LICM:

define void @test(i8 %var) writeonly {
entry:
  %div = sdiv i8 %var, 3
  %cmp2 = icmp slt i8 %div, 0
  %glb.promoted = load i8, i8* @glb, align 1
  br label %for.cond

for.cond:                                         ; preds = %cond.end, %entry
  %merge1 = phi i8 [ %glb.promoted, %entry ], [ %merge, %cond.end ]
  %i = phi i64 [ 0, %entry ], [ %add, %cond.end ]
  %cmp = icmp ult i64 %i, 4
  br i1 %cmp, label %for.body39, label %for.end

for.body39:                                       ; preds = %for.cond
  br i1 %cmp2, label %cond.true, label %cond.false

cond.true:                                        ; preds = %for.body39
  br label %cond.end

cond.false:                                       ; preds = %for.body39
  br label %cond.end

cond.end:                                         ; preds = %cond.false, %cond.true
  %merge = phi i8 [ %div, %cond.true ], [ 0, %cond.false ]
  %add = add i64 %i, 4
  br label %for.cond

for.end:                                          ; preds = %for.cond
  %merge1.lcssa = phi i8 [ %merge1, %for.cond ]
  store i8 %merge1.lcssa, i8* @glb, align 1
  ret void
}

Reduced test case from John Regehr & Vsevolod Livinskii.

@nikic
Copy link
Contributor

nikic commented Sep 19, 2021

This is debatable. Generally attributes like writeonly only refer to caller accessible memory, e.g. it's okay to load from an alloca in a writeonly function. The situation here is similar in that the load is spurious -- the loaded value doesn't actually matter. From the perspective of the caller, while the implementation is not actually writeonly, it behaves as if it were.

I didn't check if the store is introduced for loops that are not guaranteed to execute, but if that's the case that may violate C++'s memory model (where I believe you cannot introduce stores).

The transform is only performed if the store is guaranteed to execute or to an allocation that does not escape before/during the loop.

@nunoplopes
Copy link
Member Author

The transform is only performed if the store is guaranteed to execute or to
an allocation that does not escape before/during the loop.

If that's the case, then there's no point in doing the load in the first place. The phi can be initialized with poison, as you know you'll never see then 0-iteration value.
Problem solved and doesn't requiring arguing about whether a load impacts the execution or not w.r.t. to the writeonly attribute. That would be a non-trivial semantics (possible ofc, but would be nice to avoid).

@Kojoley
Copy link
Contributor

Kojoley commented Sep 19, 2021

This is debatable. Generally attributes like writeonly only refer to caller
accessible memory

And a global is accessible in caller.

Langref says:

If a writeonly function reads memory visible to the program, or has other side-effects, the behavior is undefined.

So the load could be replaced with unreachable, what means that the code:

define void @test(i8 %var) #0 {
entry:
  %div = sdiv i8 %var, 3
  %cmp2 = icmp slt i8 %div, 0
  %glb.promoted = load i8, i8* @glb, align 1

could be transformed to:

define void @test(i8 %var) #0 {
  unreachable

@llvmbot llvmbot transferred this issue from llvm/llvm-bugzilla-archive Dec 11, 2021
fhahn added a commit that referenced this issue Apr 10, 2022
Test for #51248. LICM introduces an unused load in a writeonly function.
@fhahn
Copy link
Contributor

fhahn commented Apr 10, 2022

Candidate patch: https://reviews.llvm.org/D123473

@fhahn fhahn closed this as completed in 42229b9 Apr 11, 2022
@nunoplopes nunoplopes reopened this May 4, 2022
fhahn added a commit that referenced this issue May 29, 2022
…doesn't exec."

This reverts the revert commit ad95255.

The updated version also creates a load when the store may not execute.
In those cases, we still need to introduce a load in a function where
there may not have been one before, so this doesn't completely resolve
issue #51248.

Original message:

    When only a store is sunk, there is no need to create a load in the
    pre-header, as the result of the load will never get used.

    The dead load can can introduce UB, if the function is marked as
    writeonly.

    Reviewed By: nikic

    Differential Revision: https://reviews.llvm.org/D123473
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
Projects
None yet
Development

No branches or pull requests

5 participants