PR17623 -- GlobalsModRef alias error fix

[david2050]

Summary

PR17623 exposes a bug through LTO in GlobalsModRef where the notion of a global that indirectly owns memory is only true if it is not initialized to point to some other named memory. The revision filters candidate globals by this new condition.

[nicholas]

David Callahan wrote:

Hi chandlerc,

PR17623 exposes a bug through LTO in GlobalsModRef where the notion of a global that indirectly owns memory is only true if it is not initialized to point to some other named memory. The revision filters candidate globals by this new condition.

+/// hasNullInitilaizer -- for a global variable which is non-address-taken,

(Unless it is the prevailing form in this file,) please don't repeat the
function name in the comment. Also, it has a typo.

+ // If initilazed to the null pointer, ignore it.

Typo again.

At a high level, I have some problems with globals-mod-ref-aa. It's
relying on LLVM IR types, which is a bad idea (consider a global union {
intptr_t i; char *p; }). The AnalyzeGlobals function appears to be
computing whether things have their address taken, and doesn't read nor
write unnamed_addr.

I don't understand why you didn't add the "is null" to
AnalyzeIndirectGlobalMemory. It seems to go with "non-aliased heap
memory" because heap allocators can return null. If all stores to it
store the result of malloc or a nullptr, it should be fine for it to
detect a store internally. It looks like it tries to handle a global
that always points to the result of malloc, but different malloc's in
different places.

Also, do we ever have it initialized to undef? Or do we canonicalize
those hasInitializer() == false?

Nick

REPOSITORY

rL LLVM

http://reviews.llvm.org/D7451

Files:

lib/Analysis/IPA/GlobalsModRef.cpp
test/Analysis/GlobalsModRef/pr17623.ll

EMAIL PREFERENCES

http://reviews.llvm.org/settings/panel/emailpreferences/

---

llvm-commits mailing list
[e-mail]
http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits

[david2050]

Updated based on previous comments.

[david2050]

Thanks Nick, I applied your suggested comments.

I will leave it to others to defend the analysis but at least we can fix the obvious bugs.
david

[chandlerc]

Leaving this review to Nick.

lib/Analysis/IPA/GlobalsModRef.cpp

FunctionRecord *getFunctionInfo(const Function *F) {
       return nullptr;
     }
 
     void AnalyzeGlobals(Module &M);
     void AnalyzeCallGraph(CallGraph &CG, Module &M);
     bool AnalyzeUsesOfPointer(Value *V, std::vector<Function*> &Readers,
                               std::vector<Function*> &Writers,
                               GlobalValue *OkayStoreDest = nullptr);
-    bool AnalyzeIndirectGlobalMemory(GlobalValue *GV);
+    bool hasNullInitializer(GlobalVariable *GV);
+    bool AnalyzeIndirectGlobalMemory(GlobalVariable *GV);
   };
 }
 
 char GlobalsModRef::ID = 0;
 INITIALIZE_AG_PASS_BEGIN(GlobalsModRef, AliasAnalysis,
                 "globalsmodref-aa", "Simple mod/ref analysis for globals",    
                 false, true, false)
 INITIALIZE_PASS_DEPENDENCY(CallGraphWrapperPass)
for (Use &U : V->uses()) {
     } else {
       return true;
     }
   }
 
   return false;
 }
 
+/// for a global variable which is non-address-taken,
+/// verify that if it is initialized it is initialized to null
+bool GlobalsModRef::hasNullInitializer(GlobalVariable *GV) {
+  if (!GV->hasInitializer())
+    return true;
+  // If initialized to the null pointer, ignore it.
+  Constant *init = GV->getInitializer();
+  if (isa<ConstantPointerNull>(init))
+    return true;
+  // or is undefined
+  if (isa<UndefValue>(init))
+    return true;
+  return false;
+}
+
 /// AnalyzeIndirectGlobalMemory - We found an non-address-taken global variable
 /// which holds a pointer type.  See if the global always points to non-aliased
 /// heap memory: that is, all initializers of the globals are allocations, and
 /// those allocations have no use other than initialization of the global.
 /// Further, all loads out of GV must directly use the memory, not store the
 /// pointer somewhere.  If this is true, we consider the memory pointed to by
 /// GV to be owned by GV and can disambiguate other pointers from it.
-bool GlobalsModRef::AnalyzeIndirectGlobalMemory(GlobalValue *GV) {
+bool GlobalsModRef::AnalyzeIndirectGlobalMemory(GlobalVariable *GV) {
+
+  // points to memory with another name?
+  if (!hasNullInitializer(GV))
+    return false;
+
   // Keep track of values related to the allocation of the memory, f.e. the
   // value produced by the malloc call and any casts.
   std::vector<Value*> AllocRelatedValues;
 
   // Walk the user list of the global.  If we find anything other than a direct
   // load or store, bail out.
   for (User *U : GV->users()) {
     if (LoadInst *LI = dyn_cast<LoadInst>(U)) {

test/Analysis/GlobalsModRef/pr17623.ll

+; RUN: opt < %s -tbaa -basicaa -globalsmodref-aa -print-alias-sets -disable-output 2>&1 | FileCheck %s 
+
+; This code was derived from 
+
+; static int a, b, e;
+; static int *c;
+; static int **volatile d = &c;
+; int main() {
+;   for (; a <= 0; a++) {
+;     e = 0;
+;     *d = &e;
+;     if (*c)
+;       return 1;
+;   }
+;  return 0;
+; }
+
+; Note that this code has the following points-to relationships (flow-insensitive)
+;     
+;             &e -> e
+;        &c -> c -> e
+;   &d -> d -> c
+; 
+; Which imples that (&e ,c) should be in the same alias set as should (&c, d);
+; Below %1 is "d" and "%2" is "c" so we expect 
+
+; CHECK:   may alias, Mod/Ref   Pointers: (i32* @e, 4), (i32** %1, 8), (i32** @c, 8), (i32* %2, 4)
+
+; ModuleID = 'bug17623b.bc'
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+@a = internal global i32 0, align 4
+@e = internal global i32 0, align 4
+@d = internal global i32** @c, align 8
+@c = internal global i32* null, align 8
+
+; Function Attrs: nounwind uwtable
+define i32 @main() #0 {
+entry:
+  %retval = alloca i32, align 4
+  store i32 0, i32* %retval
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.inc, %entry
+  %0 = load i32* @a, align 4
+  %cmp = icmp sle i32 %0, 0
+  br i1 %cmp, label %for.body, label %for.end
+
+for.body:                                         ; preds = %for.cond
+  store i32 0, i32* @e, align 4
+  %1 = load volatile i32*** @d, align 8
+  store i32* @e, i32** %1, align 8
+  %2 = load i32** @c, align 8
+  %3 = load i32* %2, align 4
+  %tobool = icmp ne i32 %3, 0
+  br i1 %tobool, label %if.then, label %if.end
+
+if.then:                                          ; preds = %for.body
+  store i32 1, i32* %retval
+  br label %return
+
+if.end:                                           ; preds = %for.body
+  br label %for.inc
+
+for.inc:                                          ; preds = %if.end
+  %4 = load i32* @a, align 4
+  %inc = add nsw i32 %4, 1
+  store i32 %inc, i32* @a, align 4
+  br label %for.cond
+
+for.end:                                          ; preds = %for.cond
+  store i32 0, i32* %retval
+  br label %return
+
+return:                                           ; preds = %for.end, %if.then
+  %5 = load i32* %retval
+  ret i32 %5
+}
+
+attributes #0 = { nounwind uwtable "less-precise-fpmad"="false" "no-frame-pointer-elim"="true" "no-frame-pointer-elim-non-leaf" "no-infs-fp-math"="false" "no-nans-fp-math"="false" "stack-protector-buffer-size"="8" "unsafe-fp-math"="false" "use-soft-float"="false" }
+
+!llvm.ident = !{!0}
+
+!0 = !{!"clang version 3.7.0 (http://llvm.org/git/clang.git 721f778cf06294ecc194dd76fd5d47ee903f7b07) (http://llvm.org/git/llvm.git 06eb5aad3744336cea6607280edb4491a73b6cc9)"}