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

[Martin Storsjö via llvm-dev]

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