[ARM] Miscompilation on arrays promoted to constant pools

[iid_iunknown]

Summary

This addresses the ARM miscompilation issue described in PR32780.

Problem
When a constant array is promoted to a constant pool, the constant islands pass can create several constpool entries with inlined copies of that array. If the array elements are accessed via multiple pointers, it might happen that the pointers would point to different array copies, thereby making all the operations on these pointers (such as comparison, subtraction, etc) invalid.

Solution
This patch restricts promotion to arrays having one use only, which guarantees that address of a promoted array can be taken only once.
As an extra small benefit, the patch merges similar allUsersAreInFunction and allUsersAreInFunctions functions into a single function to reduce code duplication and, possibly, make it a bit faster.

[efriedma]

lib/Target/ARM/ARMISelLowering.cpp

2972

IsCDAInit seems a bit dubious; for example, you could have a struct which contains an array, or use a scalar as a one-element array, or type-pun a scalar into an array. Or you could even end up comparing the address of a constant against itself.

One use in the IR could lead to more than one use in the actual generated code; for example, consider the case where the only use is a GEP, which feeds into multiple instructions. I think we can solve this, though: since ISel doesn't work across basic blocks, all the uses of the address of the global will be replaced with the return value of promoteToConstantPool. We just need to prevent later passes from trying to rematerialize it, so we have only one instruction which references the constant pool entry by the time we get to the constant islands pass.

[yinma]

Hi, I am facing the same issue. In my case, I disable the rematerialization of all instructions that referring contant pool. I think only t2LEApcrel is rematerializable right now. Because
the safety assumption of ContantIslandPass is that the reference to an constant pool entry should be one use. ARM common subexpression elimination will make single reference to one constant pool, the
rest reference should be copy. I believe the only re-introduction of referencing instruction is the rematerialization in register allocation pass. If we disable rematerialization. the assumption of one use should hold
until constant island pass in general. So in constant island, we can simply check if the CPE->RefCount is not greater than 1, if is greater than 1, no cloning. How do you think?

[yinma]

I tried this patch, I think it is a little bit too restrictive. If something like
define i8* @foo() {
entry:

store i8* getelementptr inbounds ([5 x i8], [5 x i8]* @.str, i32 0, i32 0), i8** @b, align 4
ret i8* getelementptr inbounds ([5 x i8], [5 x i8]* @.str, i32 0, i32 0)

}

this is a write->read back to back case. I don't think it will cause any issue when it is promoted to constant pool.

[iid_iunknown]

As this patch has not been accepted and 4.0.1 is apporaching, and taking into account the severity level of the problem, another patch is suggested to temporarily disable globals promotion:

https://reviews.llvm.org/D33446

lib/Target/ARM/ARMISelLowering.cpp

case TLSModel::LocalDynamic:
       return LowerToTLSGeneralDynamicModel(GA, DAG);
     case TLSModel::InitialExec:
     case TLSModel::LocalExec:
       return LowerToTLSExecModels(GA, DAG, model);
   }
   llvm_unreachable("bogus TLS model");
 }
 
-/// Return true if all users of V are within function F, looking through
-/// ConstantExprs.
-static bool allUsersAreInFunction(const Value *V, const Function *F) {
-  SmallVector<const User*,4> Worklist;
+// Tells if users of V do not prevent it from being promoted to constant pool,
+// looking through ConstantExprs.
+// This means:
+//  - all users of V are within function F;
+//  - all users of V are within some (any) function but it no larger than a pointer;
+//  - if V is constant array, it only has one use.
+static bool usersAllowConstantPromotion(const Value *V, const Function *F,
+                                      bool IsCDAInit, unsigned InitSize) {
+  unsigned UsersCount = 0;
+  SmallVector<const User*, 4> Worklist;
   for (auto *U : V->users())
     Worklist.push_back(U);
   while (!Worklist.empty()) {
     auto *U = Worklist.pop_back_val();
     if (isa<ConstantExpr>(U)) {
       for (auto *UU : U->users())
         Worklist.push_back(UU);
       continue;
     }
 
-    auto *I = dyn_cast<Instruction>(U);
-    if (!I || I->getParent()->getParent() != F)
+    if (isa<Instruction>(U)) {
+      auto *I = cast<Instruction>(U);
+      if (I->getParent()->getParent() != F && InitSize > 4)
+        return false;
+      ++UsersCount;
+      if (IsCDAInit && UsersCount > 1)
         return false;
     }
-  return true;
-}
-
-/// Return true if all users of V are within some (any) function, looking through
-/// ConstantExprs. In other words, are there any global constant users?
-static bool allUsersAreInFunctions(const Value *V) {
-  SmallVector<const User*,4> Worklist;
-  for (auto *U : V->users())
-    Worklist.push_back(U);
-  while (!Worklist.empty()) {
-    auto *U = Worklist.pop_back_val();
-    if (isa<ConstantExpr>(U)) {
-      for (auto *UU : U->users())
-        Worklist.push_back(UU);
-      continue;
-    }
-
-    if (!isa<Instruction>(U))
+    else
       return false;
   }
   return true;
 }
 
 // Return true if T is an integer, float or an array/vector of either.
 static bool isSimpleType(Type *T) {
   if (T->isIntegerTy() || T->isFloatingPointTy())
static SDValue promoteToConstantPool(const GlobalValue *GV, SelectionDAG &DAG,
   // multiple uses), and promoting it would increase the constant pool size (Sz
   // > 4), ensure we have space to do so up to MaxTotal.
   if (!AFI->getGlobalsPromotedToConstantPool().count(GVar) && Size > 4)
     if (AFI->getPromotedConstpoolIncrease() + PaddedSize - 4 >=
         ConstpoolPromotionMaxTotal)
       return SDValue();
 
   // This is only valid if all users are in a single function OR it has users
-  // in multiple functions but it no larger than a pointer. We also check if
-  // GVar has constant (non-ConstantExpr) users. If so, it essentially has its
-  // address taken.
-  if (!allUsersAreInFunction(GVar, F) &&
-      !(Size <= 4 && allUsersAreInFunctions(GVar)))
+  // in multiple functions but it no larger than a pointer. 
+  // Constant arrays has an extra check to restrict promotion to arrays that
+  // only have one use. This prevents possible pointer accesses to different
+  // CP copies of the same promoted array, which may result in misbehaving
+  // code when such pointers are compared, substructed, etc.
+  // We also check if GVar has constant (non-ConstantExpr) users. If so, it
+  // essentially has its address taken.
+  if (!usersAllowConstantPromotion(GVar, F, CDAInit != nullptr, Size))
     return SDValue();
 
   // We're going to inline this global. Pad it out if needed.
   if (RequiredPadding != 4) {
     StringRef S = CDAInit->getAsString();
 
     SmallVector<uint8_t,16> V(S.size());
     std::copy(S.bytes_begin(), S.bytes_end(), V.begin());

test/CodeGen/ARM/constantpool-promote-dbg.ll

 ; RUN: llc -relocation-model=static < %s | FileCheck %s
 
 target datalayout = "e-m:e-p:32:32-i64:64-v128:64:128-a:0:32-n32-S64"
 target triple = "thumbv7m--linux-gnu"
 
-@.str = private unnamed_addr constant [4 x i8] c"abc\00", align 1
+@.int = private unnamed_addr constant i32 777, align 4
 
 ; CHECK-LABEL: fn1
-; CHECK: .str:
+; CHECK: .int:
 define arm_aapcscc i8* @fn1() local_unnamed_addr #0 !dbg !8 {
 entry:
-  ret i8* getelementptr inbounds ([4 x i8], [4 x i8]* @.str, i32 0, i32 0), !dbg !14
+  ret i8* bitcast (i32* @.int to i8*), !dbg !14
 }
 
 ; CHECK-LABEL: fn2
-; CHECK-NOT: .str:
-define arm_aapcscc i8* @fn2() local_unnamed_addr #0 !dbg !15 {
+; CHECK-NOT: .int:
+define arm_aapcscc i16* @fn2() local_unnamed_addr #0 !dbg !15 {
 entry:
-  ret i8* getelementptr inbounds ([4 x i8], [4 x i8]* @.str, i32 0, i32 1), !dbg !16
+  ret i16* bitcast (i32* @.int to i16*), !dbg !16
 }
 
 attributes #0 = { minsize norecurse nounwind optsize readnone "disable-tail-calls"="false" "less-precise-fpmad"="false" "no-frame-pointer-elim"="true" "no-frame-pointer-elim-non-leaf" "no-infs-fp-math"="false" "no-jump-tables"="false" "no-nans-fp-math"="false" "stack-protector-buffer-size"="8" "target-cpu"="cortex-m3" "target-features"="+hwdiv,+soft-float,-crypto,-neon" "unsafe-fp-math"="false" "use-soft-float"="true" }
 
 !llvm.dbg.cu = !{!0}
 !llvm.module.flags = !{!3, !4, !5, !6}
 !llvm.ident = !{!7}
 

test/CodeGen/ARM/constantpool-promote.ll

-; RUN: llc -mtriple armv7--linux-gnueabihf -relocation-model=static < %s | FileCheck %s --check-prefixes=CHECK,CHECK-V7,CHECK-V7ARM
-; RUN: llc -mtriple armv7--linux-gnueabihf -relocation-model=pic < %s | FileCheck %s --check-prefixes=CHECK,CHECK-V7,CHECK-V7ARM
+; RUN: llc -mtriple armv7--linux-gnueabihf -relocation-model=static < %s | FileCheck %s --check-prefixes=CHECK,CHECK-V7,CHECK-V7ARM,CHECK-STATIC
+; RUN: llc -mtriple armv7--linux-gnueabihf -relocation-model=pic < %s | FileCheck %s --check-prefixes=CHECK,CHECK-V7,CHECK-V7ARM,CHECK-PIC
 ; RUN: llc -mtriple armv7--linux-gnueabihf -relocation-model=ropi < %s | FileCheck %s --check-prefixes=CHECK,CHECK-V7,CHECK-V7ARM
 ; RUN: llc -mtriple armv7--linux-gnueabihf -relocation-model=rwpi < %s | FileCheck %s --check-prefixes=CHECK,CHECK-V7,CHECK-V7ARM
 ; RUN: llc -mtriple thumbv7--linux-gnueabihf -relocation-model=static < %s | FileCheck %s --check-prefixes=CHECK,CHECK-V7,CHECK-V7THUMB
 ; RUN: llc -mtriple thumbv7--linux-gnueabihf -relocation-model=pic < %s | FileCheck %s --check-prefixes=CHECK,CHECK-V7,CHECK-V7THUMB
 ; RUN: llc -mtriple thumbv7--linux-gnueabihf -relocation-model=ropi < %s | FileCheck %s --check-prefixes=CHECK,CHECK-V7,CHECK-V7THUMB
 ; RUN: llc -mtriple thumbv7--linux-gnueabihf -relocation-model=rwpi < %s | FileCheck %s --check-prefixes=CHECK,CHECK-V7,CHECK-V7THUMB
 ; RUN: llc -mtriple thumbv6m--linux-gnueabihf -relocation-model=static < %s | FileCheck %s --check-prefixes=CHECK,CHECK-V6M
 ; RUN: llc -mtriple thumbv6m--linux-gnueabihf -relocation-model=pic < %s | FileCheck %s --check-prefixes=CHECK,CHECK-V6M
 ; RUN: llc -mtriple thumbv6m--linux-gnueabihf -relocation-model=ropi < %s | FileCheck %s --check-prefixes=CHECK,CHECK-V6M
 ; RUN: llc -mtriple thumbv6m--linux-gnueabihf -relocation-model=rwpi < %s | FileCheck %s --check-prefixes=CHECK,CHECK-V6M
 
 @.str = private unnamed_addr constant [2 x i8] c"s\00", align 1
 @.str1 = private unnamed_addr constant [69 x i8] c"this string is far too long to fit in a literal pool by far and away\00", align 1
 @.str2 = private unnamed_addr constant [27 x i8] c"this string is just right!\00", align 1
 @.str3 = private unnamed_addr constant [26 x i8] c"this string is used twice\00", align 1
 @.str4 = private unnamed_addr constant [29 x i8] c"same string in two functions\00", align 1
+@.str5 = private unnamed_addr constant [2 x i8] c"s\00", align 1
 @.arr1 = private unnamed_addr constant [2 x i16] [i16 3, i16 4], align 2
 @.arr2 = private unnamed_addr constant [2 x i16] [i16 7, i16 8], align 2
 @.arr3 = private unnamed_addr constant [2 x i16*] [i16* null, i16* null], align 4
 @.ptr = private unnamed_addr constant [2 x i16*] [i16* getelementptr inbounds ([2 x i16], [2 x i16]* @.arr2, i32 0, i32 0), i16* null], align 2
 @.arr4 = private unnamed_addr constant [2 x i16] [i16 3, i16 4], align 16
+@.arr5 = private unnamed_addr constant [2 x i16] [i16 3, i16 4], align 2
+@.arr6 = private unnamed_addr constant [2 x i16] [i16 3, i16 4], align 2
 @.zerosize = private unnamed_addr constant [0 x i16] zeroinitializer, align 4
 
 ; CHECK-LABEL: @test1
 ; CHECK: adr r0, [[x:.*]]
 ; CHECK: [[x]]:
 ; CHECK: .asciz "s\000\000"
 define void @test1() #0 {
   tail call void @a(i8* getelementptr inbounds ([2 x i8], [2 x i8]* @.str, i32 0, i32 0)) #2

 ; CHECK: .asciz "this string is just right!\000"
 define void @test3() #0 {
   tail call void @a(i8* getelementptr inbounds ([27 x i8], [27 x i8]* @.str2, i32 0, i32 0)) #2
   ret void
 }
 
 
 ; CHECK-LABEL: @test4
-; CHECK: adr r{{.*}}, [[x:.*]]
-; CHECK: [[x]]:
-; CHECK: .asciz "this string is used twice\000\000"
+; CHECK-STATIC: movw [[r:.*]], :lower16:[[x:.*]]
+; CHECK-STATIC: movt [[r]], :upper16:[[x]]
+; CHECK-PIC: ldr [[r1:.*]], [[x:.*]]
+; CHECK-PIC: add [[r2:.*]], pc, [[r1]]
+; CHECK-PIC: [[x]]:
+; CHECK-NOT: adr r{{.*}}, [[x:.*]]
+; CHECK-NOT: [[x]]:
+; CHECK-NOT: .asciz "this string is used twice\000\000"
 define void @test4() #0 {
   tail call void @a(i8* getelementptr inbounds ([26 x i8], [26 x i8]* @.str3, i32 0, i32 0)) #2
   tail call void @a(i8* getelementptr inbounds ([26 x i8], [26 x i8]* @.str3, i32 0, i32 0)) #2
   ret void
 }
 
 ; CHECK-LABEL: @test5a
 ; CHECK-NOT: adr

 }
 
 ; CHECK-LABEL: @test6b
 ; CHECK: adr r0, [[x:.*]]
 ; CHECK: [[x]]:
 ; CHECK: .short 3
 ; CHECK: .short 4
 define void @test6b() #0 {
-  tail call void @c(i16* getelementptr inbounds ([2 x i16], [2 x i16]* @.arr1, i32 0, i32 0)) #2
+  tail call void @c(i16* getelementptr inbounds ([2 x i16], [2 x i16]* @.arr6, i32 0, i32 0)) #2
   ret void
 }
 
 ; This shouldn't be promoted, as the string is used by another global.
 ; CHECK-LABEL: @test7
 ; CHECK-NOT: adr
 define void @test7() #0 {
   tail call void @c(i16* getelementptr inbounds ([2 x i16], [2 x i16]* @.arr2, i32 0, i32 0)) #2

 ; CHECK-LABEL: @test10
 ; CHECK-V6M: adr r{{[0-9]*}}, [[x:.*]]
 ; CHECK-V6M: [[x]]:
 ; CHECK-V6M: .asciz "s\000\000"
 ; CHECK-V7: ldrb{{(.w)?}} r{{[0-9]*}}, [[x:.*]]
 ; CHECK-V7: [[x]]:
 ; CHECK-V7: .asciz "s\000\000"
 define void @test10(i8* %a) local_unnamed_addr #0 {
-  call void @llvm.memmove.p0i8.p0i8.i32(i8* %a, i8* getelementptr inbounds ([2 x i8], [2 x i8]* @.str, i32 0, i32 0), i32 1, i32 1, i1 false)
+  call void @llvm.memmove.p0i8.p0i8.i32(i8* %a, i8* getelementptr inbounds ([2 x i8], [2 x i8]* @.str5, i32 0, i32 0), i32 1, i32 1, i1 false)
   ret void
 }
 
 ; CHECK-LABEL: @test11
 ; CHECK-V6M: adr r{{[0-9]*}}, [[x:.*]]
 ; CHECK-V6M: [[x]]:
 ; CHECK-V6M: .short 3
 ; CHECK-V6M: .short 4
 ; CHECK-V7THUMB: ldrh{{(.w)?}} r{{[0-9]*}}, [[x:.*]]
 ; CHECK-V7THUMB: [[x]]:
 ; CHECK-V7THUMB: .short 3
 ; CHECK-V7THUMB: .short 4
 ; CHECK-V7ARM: adr r{{[0-9]*}}, [[x:.*]]
 ; CHECK-V7ARM: [[x]]:
 ; CHECK-V7ARM: .short 3
 ; CHECK-V7ARM: .short 4
 define void @test11(i16* %a) local_unnamed_addr #0 {
-  call void @llvm.memmove.p0i16.p0i16.i32(i16* %a, i16* getelementptr inbounds ([2 x i16], [2 x i16]* @.arr1, i32 0, i32 0), i32 2, i32 2, i1 false)
+  call void @llvm.memmove.p0i16.p0i16.i32(i16* %a, i16* getelementptr inbounds ([2 x i16], [2 x i16]* @.arr5, i32 0, i32 0), i32 2, i32 2, i1 false)
   ret void
 }
 
 
 declare void @b(i8*) #1
 declare void @c(i16*) #1
 declare void @llvm.memcpy.p0i8.p0i8.i32(i8* nocapture writeonly, i8* nocapture readonly, i32, i32, i1)
 declare void @llvm.memmove.p0i8.p0i8.i32(i8*, i8*, i32, i32, i1) local_unnamed_addr