[llvm-dev] DenseMap/ValueMap: is M[New]=M[Old] valid ?

Martin Storsjö via llvm-dev
2019-09-27T06:38:20Z

On Thu, 26 Sep 2019, David Blaikie wrote:

> I'd be surprised if Clang or GCC's behavior here varied depending
on the
> size of anything, but maybe?
>
> In any case, C++17 or so requires the RHS to be evaluated before the LHS
for
> assignments - so this is now /always/ wrong, not just unspecified (which, I
> guess, also always wrong... just sometimes accidentally right) as it was
> before.

It's not a question about when the operands are evaluated - both do
evaluate them in the same order. But evaluating the left and right hand
side leaves you with two references. Then to do the assignment, you
dereference the right hand side reference and assign it to the
dereferenced left hand side reference.

If the value type is as small as the reference itself, Clang dereferences
the right hand side reference before evaluating the left hand side.

The testcase in https://bugs.llvm.org/show_bug.cgi?id=42065 allows you to
play around with different variants of this; small or large value type,
and different forms of the assignment expression (where one form of the
expression helped for Clang but not for GCC).

The core part of the testcase is this:

void copy(void *a, void *b) {
         GlobalMap[a] = GlobalMap[b];
}

When compiled with Clang, ends up like this:

define void @_Z4copyPvS_(i8*, i8*) #1 {
   %3 = alloca i8*, align 8
   %4 = alloca i8*, align 8
   store i8* %0, i8** %3, align 8
   store i8* %1, i8** %4, align 8
   %5 = call dereferenceable(8) i8**
@_ZN4llvm12DenseMapBaseINS_8DenseMapIPvS2_NS_12DenseMapInfoIS2_EENS_6detail12DenseMapPairIS2_S2_EEEES2_S2_S4_S7_EixERKS2_(%"class.llvm::DenseMapBase"*
getelementptr inbounds (%"class.llvm::DenseMap",
%"class.llvm::DenseMap"* @GlobalMap, i32 0, i32 0), i8**
dereferenceable(8) %4)
   %6 = load i8*, i8** %5, align 8
   %7 = call dereferenceable(8) i8**
@_ZN4llvm12DenseMapBaseINS_8DenseMapIPvS2_NS_12DenseMapInfoIS2_EENS_6detail12DenseMapPairIS2_S2_EEEES2_S2_S4_S7_EixERKS2_(%"class.llvm::DenseMapBase"*
getelementptr inbounds (%"class.llvm::DenseMap",
%"class.llvm::DenseMap"* @GlobalMap, i32 0, i32 0), i8**
dereferenceable(8) %3)
   store i8* %6, i8** %7, align 8
   ret void
}

Here %6 is the value type loaded from the RHS reference %5, loaded before
evaluating the LHS.

If the value type of the map is something larger than just a pointer, the
emitted IR looks like this instead:

define void @_Z4copyPvS_(i8*, i8*) #1 {
   %3 = alloca i8*, align 8
   %4 = alloca i8*, align 8
   store i8* %0, i8** %3, align 8
   store i8* %1, i8** %4, align 8
   %5 = call dereferenceable(800) %struct.LargeValue*
@_ZN4llvm12DenseMapBaseINS_8DenseMapIPv10LargeValueNS_12DenseMapInfoIS2_EENS_6detail12DenseMapPairIS2_S3_EEEES2_S3_S5_S8_EixERKS2_(%"class.llvm::DenseMapBase"*
getelementptr inbounds (%"class.llvm::DenseMap",
%"class.llvm::DenseMap"* @GlobalMap, i32 0, i32 0), i8**
dereferenceable(8) %4)
   %6 = call dereferenceable(800) %struct.LargeValue*
@_ZN4llvm12DenseMapBaseINS_8DenseMapIPv10LargeValueNS_12DenseMapInfoIS2_EENS_6detail12DenseMapPairIS2_S3_EEEES2_S3_S5_S8_EixERKS2_(%"class.llvm::DenseMapBase"*
getelementptr inbounds (%"class.llvm::DenseMap",
%"class.llvm::DenseMap"* @GlobalMap, i32 0, i32 0), i8**
dereferenceable(8) %3)
   %7 = bitcast %struct.LargeValue* %6 to i8*
   %8 = bitcast %struct.LargeValue* %5 to i8*
   call void @llvm.memcpy.p0i8.p0i8.i64(i8* %7, i8* %8, i64 800, i32 8, i1
false)
   ret void
}

In this case, the RHS reference isn't dereferenced until both references
are available, and the value can be copied with a memcpy.

// Martin