[GlobalDCE] Don't add dependency via icmp against inbouds pointer

[aykevl]

Summary

This patch optimizes the following case:

static int x;
bool foo(int *n) {
    return &x == n;
}

To remove the static global that isn't otherwise used:

bool foo(int *n) {
    return false;
}

This is not a valid optimization in C. However, there are cases where
this can be valid in other language if the pointer parameter n is known
to point into a valid object (either via the dereferenceable_or_null
attribute or an inbouds gep). The logic here is the same as for
https://reviews.llvm.org/D60047.

The motivator for this is runtime type information in TinyGo. There are
two ways type information globals are referenced: either by storing it
in an interface value, or by comparing the interface type against the
type information global. It is this second use (the comparison) that
leads to a significant code size increase of double digit percents in
some cases.

We currently work around this using a hack, but I'd like this to be
supported natively in LLVM so we can simplify the compiler and make use
of a normal LTO pipeline instead of our homegrown LTO variant.

[aykevl]

llvm/lib/Transforms/IPO/GlobalDCE.cpp

70

Note this function is basically a copy of https://github.com/llvm/llvm-project/blob/main/llvm/lib/Analysis/CaptureTracking.cpp#L60. I guess this could be generalized, perhaps making it a method on Value?

[StephenFan]

llvm/lib/Transforms/IPO/GlobalDCE.cpp

102

Your isDereferenceableOrNull function can handle the GetElementPtr instruction, but isLocalGlobal can not handle GetElementPtr. Maybe we need to call stripInBoundsOffsets on Op0 and Op1?

[khei4]

Drive-by comments: Although I'm not sure about dereferenceable and noalias semantics, in this case, is it appropriate to use noalias instead of dereferenceable, if you want to know the pointers (in)equality? And use getUnderlyingObject for GEPs? I think dereferenceable GV aliases seem normal.
langref for parameter attributes

Edit: also these changes seem better to be placed on InstSimplify rather than GlobalDCE, because they are not dead code.

llvm/test/Transforms/GlobalDCE/icmp.ll

1–3

It might be better to use update_test_checks.py for maintainability. And if this is target independent test, you shouldn't hard code target info.

[khei4]

https://github.com/khei4/llvm-project/blob/main/llvm/lib/Analysis/InstructionSimplify.cpp#L2700~L2727
seems like noalias only itself is not sufficient to judge pointer inequality.

[jdoerfert]

This patch is all over the place. We have different other places where we simplify globals or comparisons, this should go there instead.

llvm/lib/Analysis/TypeMetadataUtils.cpp

272

Why is this code in this file?

llvm/lib/Transforms/IPO/GlobalDCE.cpp

64–67

84

We should not copy code.

107

This code doesn't belong here. No other such logic is used in this traversal.

llvm/include/llvm/Analysis/TypeMetadataUtils.h

 //===- TypeMetadataUtils.h - Utilities related to type metadata --*- C++ -*-==//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 // This file contains functions that make it easier to manipulate type metadata
 // for devirtualization.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_ANALYSIS_TYPEMETADATAUTILS_H
 #define LLVM_ANALYSIS_TYPEMETADATAUTILS_H
 
+#include "llvm/IR/GlobalVariable.h"
 #include <cstdint>
 
 namespace llvm {
 
 template <typename T> class SmallVectorImpl;
 class CallBase;
 class CallInst;
 class Constant;

 /// For such (sub-)expressions, getPointerAtOffset returns the @target pointer.
 Constant *getPointerAtOffset(Constant *I, uint64_t Offset, Module &M,
                              Constant *TopLevelGlobal = nullptr);
 
 /// Finds the same "relative pointer" pattern as described above, where the
 /// target is `C`, and replaces the entire pattern with a constant zero.
 void replaceRelativePointerUsersWithZero(Constant *C);
 
+// Remove the icmp instructions that use this global with a constant result
+// (false or true).
+void replaceICmpUsersWithFalse(GlobalVariable *GV);
+
 } // namespace llvm
 
 #endif

llvm/lib/Analysis/TypeMetadataUtils.cpp

 void llvm::replaceRelativePointerUsersWithZero(Constant *C) {
   for (auto *U : C->users()) {
     if (auto *Equiv = dyn_cast<DSOLocalEquivalent>(U))
       replaceRelativePointerUsersWithZero(Equiv);
     else
       replaceRelativePointerUserWithZero(U);
   }
 }
+
+void llvm::replaceICmpUsersWithFalse(GlobalVariable *GV) {
+  // Find all the icmp instructions that use this global variable.
+  SmallPtrSet<ICmpInst *, 8> Compares;
+  for (auto *U : GV->users()) {
+    if (auto *I = dyn_cast<ICmpInst>(U)) {
+      Compares.insert(I);
+    }
+  }
+
+  // Replace them all with a constant.
+  for (auto *I : Compares) {
+    assert(I->isEquality() && "expected only equality comparisons!");
+    auto *Op0 = I->getOperand(0);
+    auto *Op1 = I->getOperand(1);
+    uint64_t Result;
+    if (Op0 == Op1) {
+      // Comparisons against itself are always true.
+      Result = 1;
+    } else if (Op0 == GV || Op1 == GV) {
+      // Comparisons against another pointer are always false.
+      Result = 0;
+    } else {
+      llvm_unreachable(
+          "expected one of the operands to be the global variable!");
+    }
+    if (I->getPredicate() == CmpInst::Predicate::ICMP_NE) {
+      Result = !Result;
+    }
+    auto *V = ConstantInt::get(Type::getInt1Ty(I->getContext()), Result);
+    I->replaceAllUsesWith(V);
+    I->eraseFromParent();
+  }
+}

llvm/lib/Transforms/IPO/GlobalDCE.cpp

if (I.isDebugOrPseudoInst())
       continue;
     if (auto *RI = dyn_cast<ReturnInst>(&I))
       return !RI->getReturnValue();
     break;
   }
   return false;
 }
 
+// Returns true when V is a global with local (internal or private) linkage.
+static bool isLocalGlobal(Value *V) {
+  auto *GV = dyn_cast<GlobalVariable>(V);
+  if (GV && GV->hasLocalLinkage()) {
+    return true;
+  }
+  return false;
+}
+
+static bool isDereferenceableOrNull(Value *O, const DataLayout &DL) {
+  // An inbounds GEP can either be a valid pointer (pointing into
+  // or to the end of an allocation), or be null in the default
+  // address space. So for an inbounds GEP there is no way to let
+  // the pointer escape using clever GEP hacking because doing so
+  // would make the pointer point outside of the allocated object
+  // and thus make the GEP result a poison value. Similarly, other
+  // dereferenceable pointers cannot be manipulated without producing
+  // poison.
+  if (auto *GEP = dyn_cast<GetElementPtrInst>(O))
+    if (GEP->isInBounds())
+      return true;
+  bool CanBeNull, CanBeFreed;
+  return O->getPointerDereferenceableBytes(DL, CanBeNull, CanBeFreed);
+}
+
 /// Compute the set of GlobalValue that depends from V.
 /// The recursion stops as soon as a GlobalValue is met.
 void GlobalDCEPass::ComputeDependencies(Value *V,
                                         SmallPtrSetImpl<GlobalValue *> &Deps) {
   if (auto *I = dyn_cast<Instruction>(V)) {
     Function *Parent = I->getParent()->getParent();
+    if (auto *ICmp = dyn_cast<ICmpInst>(I)) {
+      // Check for icmp eq/ne against a local global variable.
+      // The icmp won't keep the global alive if the pointer it compares against
+      // is dereferenceable_or_null: there is no way it could have been captured
+      // in any other way.
+      if (ICmp->isEquality() && !Parent->nullPointerIsDefined()) {
+        auto *Op0 = ICmp->getOperand(0);
+        auto *Op1 = ICmp->getOperand(1);
+        const DataLayout &DL = I->getModule()->getDataLayout();
+        if (Op0->getType()->isPointerTy() &&
+            (isLocalGlobal(Op0) || isLocalGlobal(Op1)) &&
+            isDereferenceableOrNull(Op0, DL) &&
+            isDereferenceableOrNull(Op1, DL))
+          return;
+      }
+    }
     Deps.insert(Parent);
   } else if (auto *GV = dyn_cast<GlobalValue>(V)) {
     Deps.insert(GV);
   } else if (auto *CE = dyn_cast<Constant>(V)) {
     // Avoid walking the whole tree of a big ConstantExprs multiple times.
     auto Where = ConstantDependenciesCache.find(CE);
     if (Where != ConstantDependenciesCache.end()) {
       auto const &K = Where->second;
if (!F->use_empty()) {
       replaceRelativePointerUsersWithZero(F);
 
       F->replaceNonMetadataUsesWith(ConstantPointerNull::get(F->getType()));
     }
     EraseUnusedGlobalValue(F);
   }
 
   NumVariables += DeadGlobalVars.size();
-  for (GlobalVariable *GV : DeadGlobalVars)
+  for (GlobalVariable *GV : DeadGlobalVars) {
+    if (!GV->use_empty()) {
+      // Local global variables might still be referenced from an icmp, after
+      // we've proven that the global variable isn't captured anywhere.
+      // Replace icmp eq against these globals with false, and icmp ne with
+      // true.
+      replaceICmpUsersWithFalse(GV);
+    }
     EraseUnusedGlobalValue(GV);
+  }
 
   NumAliases += DeadAliases.size();
   for (GlobalAlias *GA : DeadAliases)
     EraseUnusedGlobalValue(GA);
 
   NumIFuncs += DeadIFuncs.size();
   for (GlobalIFunc *GIF : DeadIFuncs)
     EraseUnusedGlobalValue(GIF);

llvm/test/Transforms/GlobalDCE/icmp.ll

+; RUN: opt -S -passes=globaldce < %s | FileCheck %s
+target datalayout = "e-m:e-i8:8:32-i16:16:32-i64:64-i128:128-n32:64-S128"
+target triple = "aarch64-unknown-linux-gnu"
+
+@local = internal global i32 0
+@local2 = internal global i32 0
+@local3 = internal global i32 0
+@local4 = internal global i32 0
+@nonlocal = global i32 0
+
+; CHECK-LABEL: @cmplocal(
+; CHECK: ret i1 false
+define i1 @cmplocal(ptr dereferenceable_or_null(4) %other) {
+  ; The typical case.
+  %result = icmp eq ptr %other, @local
+  ret i1 %result
+}
+
+; CHECK-LABEL: @cmplocalne(
+; CHECK: ret i1 true
+define i1 @cmplocalne(ptr dereferenceable_or_null(4) %other) {
+  ; When the check is reversed, the result is true (not false).
+  %result = icmp ne ptr %other, @local
+  ret i1 %result
+}
+
+; CHECK-LABEL: @cmplocalrev(
+; CHECK: ret i1 false
+define i1 @cmplocalrev(ptr dereferenceable_or_null(4) %other) {
+  ; Check that it also works with the operands reversed.
+  %result = icmp eq ptr @local, %other
+  ret i1 %result
+}
+
+; CHECK-LABEL: @cmplocalself(
+; CHECK: ret i1 true
+define i1 @cmplocalself(ptr dereferenceable_or_null(4) %other) {
+  ; A comparison against itself won't make the global escape, but will always be
+  ; true. (This is probably also optimized by instcombine, but checking to be
+  ; sure).
+  %result = icmp eq ptr @local, @local
+  ret i1 %result
+}
+
+; CHECK-LABEL: @cmpnonlocal(
+; CHECK: ret i1 %result
+define i1 @cmpnonlocal(ptr dereferenceable_or_null(4) %other) {
+  ; The optimization doesn't apply to external globals.
+  %result = icmp eq ptr %other, @nonlocal
+  ret i1 %result
+}
+
+; CHECK-LABEL: @cmplocal2(
+; CHECK: ret i1 %result
+define i1 @cmplocal2(ptr %other) {
+  ; The optimization doesn't work without dereferenceable_or_null because then
+  ; we might use pointer tricks to obtain the value of @local anyway.
+  %result = icmp eq ptr %other, @local2
+  ret i1 %result
+}
+
+; CHECK-LABEL: @cmplocal3(
+; CHECK: ret i1 false
+define i1 @cmplocal3(ptr %other) {
+  ; ...but the optimization _does_ work with an inbouds gep, which provides the
+  ; same guarantee.
+  %gep = getelementptr inbounds i32, ptr %other, i64 1
+  %result = icmp eq ptr %gep, @local3
+  ret i1 %result
+}
+
+; CHECK-LABEL: @cmplocal4(
+; CHECK: ret i1 %result
+define i1 @cmplocal4(ptr dereferenceable_or_null(4) %other) {
+  ; TODO: we might want to optimize this case.
+  %gep = getelementptr i32, ptr %other, i64 0
+  %result = icmp eq ptr %gep, @local4
+  ret i1 %result
+}