This is an archive of the discontinued LLVM Phabricator instance.

[Evaluator] Walk initial elements when handling load through bitcast
ClosedPublic

Authored by rob.lougher on Apr 16 2019, 1:07 PM.

Details

Summary

On x86-64, if the following program is compiled at -O1 or above, the value 0 will be incorrectly printed.

#include <stdio.h>

union A {
  A(long long ll) : l(ll) {}
  void *p;
  long long l;
} u(12345);

long long l = u.l;

int main() {
  printf("%lld\n", l);
}

This is caused by the incorrect evaluation of the load from "u.l".

On input to the evaluator we have a store instruction, storing 12345 into "u", and a load reading the value to initialize "l". Both of these instructions are through a bitcast:

define linkonce_odr dso_local void @_ZN1AC2Ex(%union.A* %this, i64 %ll) unnamed_addr comdat align 2 {
  %l = bitcast %union.A* %this to i64*
  store i64 %ll, i64* %l, align 8
  ret void
...
define internal void @__cxx_global_var_init.1() section ".text.startup" {
  %1 = load i64, i64* bitcast (%union.A* @u to i64*), align 8
  store i64 %1, i64* @l, align 8
  ret void
}

When evaluating a store through a bitcast, the evaluator tries to move the bitcast from the pointer onto the stored value. So in this case we will go from:

store i64 %ll, i64* bitcast (%union.A* %this to i64*), align 8

to:

store %union.A bitcast (i64 %ll to %union.A), %union.A* %this, align 8

However, as the cast is invalid, it tries to "introspect" the type to get a valid cast by obtaining a pointer to the initial element. This ends up storing into the mutated memory an inttoptr of "12345", to an i8* pointer (a GEP).

This is so far OK. However, when evaluating the load, we first try to lookup the bitcast in the mutated memory (which doesn't exist). We then try to lookup the bitcast "from" pointer which also doesn't exist. But the "from" pointer is a global variable with a definitive initializer, so we end up folding the load to zero.

What is missing is equivalent logic to the store to introspect the type (in this case to obtain an i8* GEP, which does exist in the mutated memory, the inttoptr value obviously being castable to i64).

Note, when developing the patch I was unhappy with adding similar logic directly to the load case as it could get out of step again (e..g. given the comment in the code regarding arrays). Instead, I have abstracted the "introspection" into a helper function, with the specifics being handled by a passed-in lambda function. I have also taken the opportunity to replace the "getInitializer" helper function with a lambda. This is a non-functional change, and can be done separately if preferred.

Diff Detail

Event Timeline

rob.lougher created this revision.Apr 16 2019, 1:07 PM
Herald added a project: Restricted Project. · View Herald TranscriptApr 16 2019, 1:07 PM
rob.lougher edited the summary of this revision. (Show Details)Apr 16 2019, 1:09 PM

I wonder if it's possible to stop using MutatedMemory for checks in ComputeLoadResult and instead start using separate map which can also be filled
in EvaluateBlock. In this new map you can use bitcast (or even first operand of bitcast) as a key.

Also please strip your patch from unrelated changes for now to make it easier to read.

lib/Transforms/Utils/Evaluator.cpp
236

This seems to be an unrelated change

375

May be use [&] ?

test/Transforms/GlobalOpt/evaluate-bitcast-2.ll
7

You should also check value of @u, I think

Addressed review comments.

I wonder if it's possible to stop using MutatedMemory for checks in ComputeLoadResult and instead start using separate map which can also be filled
in EvaluateBlock. In this new map you can use bitcast (or even first operand of bitcast) as a key.

"MutatedMemory" is only used to hold evaluated store values. Using the bitcast as a key would be dangerous because we could then get different values for the same memory location (via different pointer types). Currently, the code ensures that there is only one value for each location, which is the most recent.

Also please strip your patch from unrelated changes for now to make it easier to read.

Done (see revised patch). Thanks for the review.

rob.lougher marked 3 inline comments as done.Apr 17 2019, 8:44 AM

"MutatedMemory" is only used to hold evaluated store values

It is also used to patch initializers - see BatchCommitValueTo

Using the bitcast as a key would be dangerous

There is no straightforward way to do this in MutatedMemory because GEP is a special key type (see BatchCommitValueTo)
That's why I suggested using another map.

we could then get different values for the same memory location

How?

"MutatedMemory" is only used to hold evaluated store values

It is also used to patch initializers - see BatchCommitValueTo

With values from evaluated stores.

Using the bitcast as a key would be dangerous

There is no straightforward way to do this in MutatedMemory because GEP is a special key type (see BatchCommitValueTo)
That's why I suggested using another map.

we could then get different values for the same memory location

How?

union A {
  float f;
  int i;
};

void s1(union A *u) {
  u->i = 123;
}

void s2(union A *u) {
  u->f = 1.23;
}

int foo() {
  union A u;
  s1(&u);
  s2(&u);
  return u.i;
}

int i = foo();

Input to Global Var Opt:

define dso_local void @_Z2s1P1A(%union.A* %u) #0 {
  %i = bitcast %union.A* %u to i32*
  store i32 123, i32* %i, align 4, !tbaa !2
  ret void
}

define dso_local void @_Z2s2P1A(%union.A* %u) #0 {
  %f = bitcast %union.A* %u to float*
  store float 0x3FF3AE1480000000, float* %f, align 4, !tbaa !2
  ret void
}

define dso_local i32 @_Z3foov() #0 {
  %u = alloca %union.A, align 4
  %0 = bitcast %union.A* %u to i8*
  call void @llvm.lifetime.start.p0i8(i64 4, i8* %0) #3
  call void @_Z2s1P1A(%union.A* %u)
  call void @_Z2s2P1A(%union.A* %u)
  %i = bitcast %union.A* %u to i32*
  %1 = load i32, i32* %i, align 4, !tbaa !2
  call void @llvm.lifetime.end.p0i8(i64 4, i8* %0) #3
  ret i32 %1
}

Currently both store bitcasts will be replaced by a GEP to the first element, which means the load will get the correct value.

Can't operand 0 of bitcast (%union.A* %u) be used as a key?

Can't operand 0 of bitcast (%union.A* %u) be used as a key?

Currently the (possibly casted) stored value is of the type of the key. This means the pointer lookup at the start of ComputeLoadResult() will return a value of the correct type. I guess, my question is what's wrong with keeping it like it is?

what's wrong with keeping it like it is?

Well, if it were possible to avoid the same computation for load I'd like to avoid it. However your patch seems to also handle cases when store is using GEP and load is using bitcast:

define linkonce_odr dso_local void @_ZN1AC2Ex(%union.A* %this, i64 %ll) unnamed_addr comdat align 2 {
  %l = inttoptr i64 %ll to i8*
  %p = getelementptr inbounds %union.A, %union.A* %this, i64 0, i32 0
  store i8* %l, i8** %p
  ret void
}

define internal void @__cxx_global_var_init.1() section ".text.startup" {
  %1 = load i64, i64* bitcast (%union.A* @u to i64*), align 8
  store i64 %1, i64* @l, align 8
  ret void
}

So let's stick with current approach. I'd probably include the example above as a test case.

what's wrong with keeping it like it is?

Well, if it were possible to avoid the same computation for load I'd like to avoid it. However your patch seems to also handle cases when store is using GEP and load is using bitcast:

So let's stick with current approach. I'd probably include the example above as a test case.

Yes. I will add it as an extra test (after Easter, as I am now on vacation).

Added additional test from review comments.

evgeny777 accepted this revision.Apr 25 2019, 8:02 AM

LGTM, thanks. I suggest waiting for 1-2 days in case @tejohnson has something to say.

This revision is now accepted and ready to land.Apr 25 2019, 8:02 AM

I am not familiar with this code, so happy with @evgeny777 's review.

This revision was automatically updated to reflect the committed changes.

Hi, we encountered this issue https://bugs.llvm.org/show_bug.cgi?id=48055 which reverting this patch seems to make it go away.

Can you take a look into it?

Thanks.

I have a miscompile that seems to stem from sharing the same logic between loads and stores.

In the store case, allowing evaluateBitcastFromPtr to narrow the operation to apply only to the struct's 0th element means we lose the writes to the other struct elements whenever constant folding is unable to fold an integer literal bitcast into a struct:

https://llvm.godbolt.org/z/8sYdYv5rh