[GlobalOpt] Handle null check with global pointer variables

[scui]

Summary

I'm working on extending the OptimizeGlobalAddressOfMalloc to handle some more general cases. One of the cases is the null check of global pointer variables. It is disabled with https://reviews.llvm.org/rGb7cd291c1542aee12c9e9fde6c411314a163a8ea. This PR is to reenable it while fixing the original problem reported. The fix is to set the store value correctly when creating store for the new created global init bool symbol.

[efriedma]

llvm/lib/Transforms/IPO/GlobalOpt.cpp

684

Only loosely relevant to this patch, but are we really expecting anyone to call the result of malloc? Or am I misreading this?

703

Maybe explicitly note here that the rewriting code has special handling for this case.

Not sure this interacts correctly with AllUsesOfValueWillTrapIfNull recursion. It looks like the rewriting code can't handle an icmp of a bitcast/GEP/PHI of a load.

957

I think GV->hasInitializer() must be true here?

The equality comparison here makes me a little nervous, in case the way we analyze bitcasts changes in the future. SI->getValueOperand()->isNullValue() would probably be more clear anyway.

976

The code that was meant to support the icmp comparison case.

Sinking the load seems wrong; how do we know we aren't sinking it past a store?

[scui]

This to address the review comments: (1) Refine the code to handle ICmpInst when checking if AllUsesOfValueWillTrapIfNull, (2) Consider the GlobalVariable is initialized when creating StoreInst for the global init bool symbol, (3) Remove the unsafe code sinking when transforming the ICmpInst.

[scui]

llvm/lib/Transforms/IPO/GlobalOpt.cpp

684

I think we can simply return false when passing to call argument, but I'll leave the code as it is for now. I'm going to extend the code for function call argument passing and function returns later in another patch,

703

Add restriction for operand 0 as the transformation only handles this kind of code pattern.

957

That's right, GV->hasInitializer() is true here. Modify the code as you suggested.

976

I agree, the sinking is not safe. Remove the comment, and the code sinking.

[efriedma]

I'd like to see a little more test coverage, given all the different cases where the behavior of the transform changed.

llvm/lib/Transforms/IPO/GlobalOpt.cpp

957

Would !isa<Constant>(SI->getValueOperand())) work?

[scui]

In D102711#2785937, @efriedma wrote:

I'd like to see a little more test coverage, given all the different cases where the behavior of the transform changed.

Thanks for the suggestion. I'll come back to add some test cases when I get time later.

[scui]

Add two test cases - one is to test the icmp condition with non-null value, the other is to test the disablement of the sinking of load to the icmp location.

[scui]

llvm/lib/Transforms/IPO/GlobalOpt.cpp

957

Would !isa<Constant>(SI->getValueOperand())) work?

This won't work, as the "GV = malloc()" instruction has been transformed to "GV = &NewGV", and "&NewGV" is a Constant.

[efriedma]

New testcases look good.

llvm/lib/Transforms/IPO/GlobalOpt.cpp

980

Can we explicitly note here, for the signed compares, why it doesn't matter if the high bit of the global is set? The logic here isn't obvious.

990–991

UGE should fold to ConstantInt::getTrue(GV->getContext());

[scui]

llvm/lib/Transforms/IPO/GlobalOpt.cpp

980

I'm not sure what comments I can add, as I actually don't know the logic here for the folding of the signed compares. The code has been like this from 2009 (the earliest I can found). Do you have any suggestions on how to handle all these signed compares?

990–991

Right.

[efriedma]

llvm/lib/Transforms/IPO/GlobalOpt.cpp

980

We could probably just reject icmps with a signed predicate; frontends won't normally generate signed pointer comparisons anyway.

Alternatively, you could use some tortured logic here: the program doesn't actually capture the pointer, and you can't do anything useful just knowing the sign of the pointer. So just pretend the sign bit isn't set.

[scui]

llvm/lib/Transforms/IPO/GlobalOpt.cpp

980

We could probably just reject icmps with a signed predicate; frontends won't normally generate signed pointer comparisons anyway.

Thank you very much for the suggestions. I'll take the safe approach - rejecting the signed comparisons. Hopefully it won't have much impact on real programs.

[scui]

Exclude the signed null checks, and correct the handling of UGE.

[efriedma]

LGTM

llvm/lib/Transforms/IPO/GlobalOpt.cpp

for (const User *U : V->users()) {
     if (isa<LoadInst>(U)) {
       // Will trap.
     } else if (const StoreInst *SI = dyn_cast<StoreInst>(U)) {
       if (SI->getOperand(0) == V) {
         //cerr << "NONTRAPPING USE: " << *U;
         return false;  // Storing the value.
       }
     } else if (const CallInst *CI = dyn_cast<CallInst>(U)) {
       if (CI->getCalledOperand() != V) {
         //cerr << "NONTRAPPING USE: " << *U;
         return false;  // Not calling the ptr
       }
     } else if (const InvokeInst *II = dyn_cast<InvokeInst>(U)) {
       if (II->getCalledOperand() != V) {
         //cerr << "NONTRAPPING USE: " << *U;
         return false;  // Not calling the ptr
       }
     } else if (const BitCastInst *CI = dyn_cast<BitCastInst>(U)) {
       if (!AllUsesOfValueWillTrapIfNull(CI, PHIs)) return false;
     } else if (const GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(U)) {
       if (!AllUsesOfValueWillTrapIfNull(GEPI, PHIs)) return false;
     } else if (const PHINode *PN = dyn_cast<PHINode>(U)) {
       // If we've already seen this phi node, ignore it, it has already been
       // checked.
       if (PHIs.insert(PN).second && !AllUsesOfValueWillTrapIfNull(PN, PHIs))
         return false;
+    } else if (isa<ICmpInst>(U) &&
+               !ICmpInst::isSigned(cast<ICmpInst>(U)->getPredicate()) &&
+               isa<LoadInst>(U->getOperand(0)) &&
+               isa<ConstantPointerNull>(U->getOperand(1))) {
+      assert(isa<GlobalValue>(
+                 cast<LoadInst>(U->getOperand(0))->getPointerOperand()) &&
+             "Should be GlobalVariable");
+      // This and only this kind of non-signed ICmpInst is to be replaced with
+      // the comparing of the value of the created global init bool later in
+      // optimizeGlobalAddressOfMalloc for the global variable.
     } else {
       //cerr << "NONTRAPPING USE: " << *U;
       return false;
     }
   }
   return true;
 }
 
new GlobalVariable(Type::getInt1Ty(GV->getContext()), false,
                        GlobalValue::InternalLinkage,
                        ConstantInt::getFalse(GV->getContext()),
                        GV->getName()+".init", GV->getThreadLocalMode());
   bool InitBoolUsed = false;
 
   // Loop over all uses of GV, processing them in turn.
   while (!GV->use_empty()) {
     if (StoreInst *SI = dyn_cast<StoreInst>(GV->user_back())) {
-      // The global is initialized when the store to it occurs.
-      new StoreInst(ConstantInt::getTrue(GV->getContext()), InitBool, false,
-                    Align(1), SI->getOrdering(), SI->getSyncScopeID(), SI);
+      // The global is initialized when the store to it occurs. If the stored
+      // value is null value, the global bool is set to false, otherwise true.
+      new StoreInst(ConstantInt::getBool(
+                        GV->getContext(),
+                        !isa<ConstantPointerNull>(SI->getValueOperand())),
+                    InitBool, false, Align(1), SI->getOrdering(),
+                    SI->getSyncScopeID(), SI);
       SI->eraseFromParent();
       continue;
     }
 
     LoadInst *LI = cast<LoadInst>(GV->user_back());
     while (!LI->use_empty()) {
       Use &LoadUse = *LI->use_begin();
       ICmpInst *ICI = dyn_cast<ICmpInst>(LoadUse.getUser());
       if (!ICI) {
         LoadUse = RepValue;
         continue;
       }
 
       // Replace the cmp X, 0 with a use of the bool value.
-      // Sink the load to where the compare was, if atomic rules allow us to.
       Value *LV = new LoadInst(InitBool->getValueType(), InitBool,
                                InitBool->getName() + ".val", false, Align(1),
-                               LI->getOrdering(), LI->getSyncScopeID(),
-                               LI->isUnordered() ? (Instruction *)ICI : LI);
+                               LI->getOrdering(), LI->getSyncScopeID(), LI);
       InitBoolUsed = true;
       switch (ICI->getPredicate()) {
       default: llvm_unreachable("Unknown ICmp Predicate!");
-      case ICmpInst::ICMP_ULT:
-      case ICmpInst::ICMP_SLT:   // X < null -> always false
+      case ICmpInst::ICMP_ULT: // X < null -> always false
         LV = ConstantInt::getFalse(GV->getContext());
         break;
+      case ICmpInst::ICMP_UGE: // X >= null -> always true
+        LV = ConstantInt::getTrue(GV->getContext());
+        break;
       case ICmpInst::ICMP_ULE:
-      case ICmpInst::ICMP_SLE:
       case ICmpInst::ICMP_EQ:
         LV = BinaryOperator::CreateNot(LV, "notinit", ICI);
         break;
       case ICmpInst::ICMP_NE:
-      case ICmpInst::ICMP_UGE:
-      case ICmpInst::ICMP_SGE:
       case ICmpInst::ICMP_UGT:
-      case ICmpInst::ICMP_SGT:
         break;  // no change.
       }
       ICI->replaceAllUsesWith(LV);
       ICI->eraseFromParent();
     }
     LI->eraseFromParent();
   }
 

llvm/test/Transforms/GlobalOpt/malloc-promote-4.ll

+; RUN: opt -S -globalopt -o - < %s | FileCheck %s
+
+; CHECK: [[G_INIT:@.*]] = internal unnamed_addr global i1 false
+@g = internal global i32* null, align 8
+
+; CHECK-LABEL: define {{.*}} @f1(
+; CHECK-NEXT:    [[G_INIT_VAL:%.*]] = load i1, i1* [[G_INIT]], align 1
+; CHECK-NEXT:    call fastcc void @f2()
+; CHECK-NEXT:    [[NOTINIT:%.*]] = xor i1 [[G_INIT_VAL]], true
+; CHECK-NEXT:    br i1 [[NOTINIT]], label [[TMP1:%.*]], label [[TMP2:%.*]]
+;
+define internal i32 @f1() {
+  %1 = load i32*, i32** @g, align 8
+  call void @f2();
+  %2 = icmp eq i32* %1, null
+  br i1 %2, label %3, label %4
+
+3:                                          ; preds = %0
+  br label %5
+
+4:                                          ; preds = %0
+  br label %5
+
+5:                                          ; preds = %3, %4
+  %6 = phi i32 [ -1, %3 ], [ 1, %4 ]
+  ret i32 %6
+}
+
+; CHECK-LABEL: define {{.*}} @f2(
+; CHECK-NEXT:    store i1 true, i1* [[G_INIT]], align 1
+; CHECK-NEXT:    ret void
+;
+define internal void @f2() {
+  %1 = call noalias i8* @malloc(i64 4)
+  %2 = bitcast i8* %1 to i32*
+  store i32* %2, i32** @g, align 8
+  ret void
+}
+
+; CHECK-LABEL: define {{.*}} @main(
+; CHECK-NEXT:    store i1 false, i1* [[G_INIT]], align 1
+; CHECK-NEXT:    [[TMP1:%.*]] = call fastcc i32 @f1()
+; CHECK-NEXT:    ret i32 [[TMP1]]
+;
+define dso_local i32 @main() {
+  store i32* null, i32** @g, align 8
+  %1 = call i32 @f1()
+  ret i32 %1
+}
+
+declare dso_local noalias i8* @malloc(i64)

llvm/test/Transforms/GlobalOpt/null-check-is-use-pr35760.ll

 ; RUN: opt -S -globalopt -o - < %s | FileCheck %s
 
 target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
 target triple = "x86_64-unknown-linux-gnu"
 
+; CHECK: [[_ZL3G_I_INIT:@.*]] = internal unnamed_addr global i1 false
 @_ZL3g_i = internal global i32* null, align 8
 @.str = private unnamed_addr constant [2 x i8] c"0\00", align 1
 @.str.1 = private unnamed_addr constant [2 x i8] c"1\00", align 1
 
+; CHECK-LABEL: define {{.*}} @main(
+; CHECK-NEXT:    store i1 false, i1* [[_ZL3G_I_INIT]], align 1
 define dso_local i32 @main() {
   store i32* null, i32** @_ZL3g_i, align 8
   call void @_ZL13PutsSomethingv()
   ret i32 0
 }
 
 ; CHECK-LABEL: define {{.*}} @_ZL13PutsSomethingv()
-; CHECK: [[gvLoad:%.*]] = load i32*, i32** @_ZL3g_i
-; CHECK-NEXT: icmp eq i32* [[gvLoad]], null
+; CHECK-NEXT:    [[_ZL3G_I_INIT_VAL:%.*]] = load i1, i1* [[_ZL3G_I_INIT]], align 1
+; CHECK-NEXT:    [[NOTINIT:%.*]] = xor i1 [[_ZL3G_I_INIT_VAL]], true
+; CHECK-NEXT:    br i1 [[NOTINIT]], label %[[TMP1:.*]], label %[[TMP3:.*]]
+; CHECK:       [[TMP1]]:
+; CHECK-NEXT:    store i1 true, i1* [[_ZL3G_I_INIT]], align 1
 define internal void @_ZL13PutsSomethingv() {
   %1 = load i32*, i32** @_ZL3g_i, align 8
   %2 = icmp eq i32* %1, null
   br i1 %2, label %3, label %7
 
 3:                                                ; preds = %0
   %4 = call noalias i8* @malloc(i64 4) #3
   %5 = bitcast i8* %4 to i32*

llvm/test/Transforms/GlobalOpt/null-check-not-use-pr35760.ll

+; RUN: opt -S -globalopt -o - < %s | FileCheck %s
+
+; No malloc promotion with non-null check.
+
+target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+@_ZL3g_i = internal global i32* null, align 8
+@_ZL3g_j = global i32* null, align 8
+@.str = private unnamed_addr constant [2 x i8] c"0\00", align 1
+@.str.1 = private unnamed_addr constant [2 x i8] c"1\00", align 1
+
+define dso_local i32 @main() {
+  store i32* null, i32** @_ZL3g_i, align 8
+  call void @_ZL13PutsSomethingv()
+  ret i32 0
+}
+
+; CHECK-LABEL: define {{.*}} @_ZL13PutsSomethingv()
+; CHECK-NEXT:    [[TMP1:%.*]] = load i32*, i32** @_ZL3g_i, align 8
+; CHECK-NEXT:    [[TMP2:%.*]] = load i32*, i32** @_ZL3g_j, align 8
+; CHECK-NEXT:    icmp eq i32* [[TMP1]], [[TMP2]]
+define internal void @_ZL13PutsSomethingv() {
+  %1 = load i32*, i32** @_ZL3g_i, align 8
+  %2 = load i32*, i32** @_ZL3g_j, align 8
+  %cmp = icmp eq i32* %1, %2
+  br i1 %cmp, label %3, label %7
+
+3:                                                ; preds = %0
+  %4 = call noalias i8* @malloc(i64 4) #3
+  %5 = bitcast i8* %4 to i32*
+  store i32* %5, i32** @_ZL3g_i, align 8
+  %6 = call i32 @puts(i8* getelementptr inbounds ([2 x i8], [2 x i8]* @.str, i64 0, i64 0))
+  br label %9
+
+7:                                                ; preds = %0
+  %8 = call i32 @puts(i8* getelementptr inbounds ([2 x i8], [2 x i8]* @.str.1, i64 0, i64 0))
+  br label %9
+
+9:                                                ; preds = %7, %3
+  ret void
+}
+
+declare dso_local noalias i8* @malloc(i64)
+
+declare dso_local i32 @puts(i8* nocapture readonly)