Bug 20788 - bugpoint does not respect the "Alias must point to a definition"

[npjdesres]

Summary

Fix bug 20788.

GlobalAliases may reference function definitions, but not function declarations.

bugpoint would sometimes create invalid IR by deleting a function's body (thus mutating a function definition into a declaration) without first 'fixing' any GlobalAliases that reference that function definition.

This patch iteratively prevents that issue. Before deleting a function's body, it scans the module for GlobalAliases which reference that function. When found, it eliminates them using replaceAllUsesWith.

[hfinkel]

This generally looks good, thanks!; you seem unfamiliar with our general coding conventions, so I've made a number of style comments.

tools/bugpoint/ExtractFunction.cpp

217

declaration -> definition

219

space after for

223

space after for

223

i -> I

224

space after if, no spaced around expression
(same below)

229

General convention would be to use 'e' instead of 'N' here.

230

No spaces around parameter expression.

[npjdesres]

LLVM style guidelines

[npjdesres]

How should I recruit an appropriate reviewer?

[• dberlin]

So, once the issues are fixed, i actually think this is pretty
obviously correct.
I have a bunch of code i will try it on that currently does not work
with bugpoint for this very reason.

[npjdesres]

I thought my updated diff #25062 fixed the all issues. Are there other issues?

[• dberlin]

I have a .bc file (old, admittedly, but passes opt -verify), on which
bugpoint does not work, even with this patch.

After a bunch of cutdowns, it gets:
Checking for crash with only these blocks: .lr.ph .loopexit
_ZN4llvm11SmallVectorIPN5clang6driver6ActionELj3EED1Ev.exit: Alias
must point to a definition
void (%"class.clang::DiagnosticNoteRenderer"*)*
@_ZN5clang22DiagnosticNoteRendererD1Ev
Alias must point to a definition
void (%"class.clang::DiagnosticNoteRenderer"*)*
@_ZN5clang22DiagnosticNoteRendererD2Ev
Alias must point to a definition
void (%"class.llvm::ReturnInst"*)* @_ZN4llvm10ReturnInstD1Ev
Alias must point to a definition

...
etc

I've put it here:
https://drive.google.com/file/d/0BzaAhp8ViDJ6elZEWXF4TVgydU0/view?usp=sharing

(I just made a pass crash if F.size() < 50, and ran it to get bugpoint
to start going :P)

[npjdesres]

@dberlin: your testcase demonstrates that a GlobalAlias may refer to any kind of ConstantExpr, whereas my previous patch incorrectly assumed that the aliasee must be an llvm::Function.

Consequently, the test on line 194 needs a ->stripPointerCasts(). My latest patch handles that testcase correctly.

@dberlin: you mentioned you have many test cases. Would you be so kind as to run this latest patch on them? Thanks,

[• dberlin]

I still get the same crash on bugpoint with this patch, though
slightly further along

Checking for crash with only these blocks: ._crit_edge
_ZN12_GLOBAL__N_111StmtPrinter9PrintExprEPN5clang4ExprE.exit ... <25
total>: Alias must point to a definition
void (%"class.clang::DiagnosticNoteRenderer"*)*
@_ZN5clang22DiagnosticNoteRendererD1Ev
Alias must point to a definition
void (%"class.clang::DiagnosticNoteRenderer"*)*
@_ZN5clang22DiagnosticNoteRendererD2Ev
Alias must point to a definition
void (%"class.llvm::ReturnInst"*)* @_ZN4llvm10ReturnInstD1Ev
Alias must point to a definition
void (%"class.llvm::ReturnInst"*)* @_ZN4llvm10ReturnInstD2Ev
Alias must point to a definition
void (%"class.llvm::AllocaInst"*)* @_ZN4llvm10AllocaInstD1Ev
Alias must point to a definition
void (%"class.llvm::AllocaInst"*)* @_ZN4llvm10AllocaInstD2Ev
Alias must point to a definition
void (%"class.llvm::ModulePass"*)* @_ZN4llvm10ModulePassD1Ev
Alias must point to a definition
void (%"class.llvm::ModulePass"*)* @_ZN4llvm10ModulePassD2Ev
Alias must point to a definition
void (%"class.llvm::ImmutablePass"*)* @_ZN4llvm13ImmutablePassD1Ev
Alias must point to a definition
void (%"class.llvm::ImmutablePass"*)* @_ZN4llvm13ImmutablePassD2Ev
Alias must point to a definition
void (%"class.llvm::raw_null_ostream"*)* @_ZN4llvm16raw_null_ostreamD1Ev
Alias must point to a definition
void (%"class.llvm::raw_null_ostream"*)* @_ZN4llvm16raw_null_ostreamD2Ev
./opt: bugpoint-input-b1bae24.bc: error: input module is broken!
simplifycfg failed!

[npjdesres]

@dberlin: I'm unable to recreate your crash. However, I have a hunch that it pertains to aliases to global variables, rather than aliases to functions.

The new patch (attached) eliminates aliases before calls to GV->setInitializer(nullptr).

[• dberlin]

This one works properly for me on that file.

So LGTM.

[npjdesres]

Sorry, I had forgotten about this diff.

LGTM too. I do not have commit privs.

[hfinkel]

Rebased, and committed: r254171.

tools/bugpoint/BugDriver.h

 /// PrintFunctionList - prints out list of problematic functions
 ///
 void PrintFunctionList(const std::vector<Function*> &Funcs);
 
 /// PrintGlobalVariableList - prints out list of problematic global variables
 ///
 void PrintGlobalVariableList(const std::vector<GlobalVariable*> &GVs);
 
+// DeleteGlobalInitializer - "Remove" the global variable by deleting its
+// initializer, making it external.
+//
+void DeleteGlobalInitializer(GlobalVariable *GV);
+
 // DeleteFunctionBody - "Remove" the function by deleting all of it's basic
 // blocks, making it external.
 //
 void DeleteFunctionBody(Function *F);
 
 /// SplitFunctionsOutOfModule - Given a module and a list of functions in the
 /// module, split the functions OUT of the specified module, and place them in
 /// the new module.
 Module *SplitFunctionsOutOfModule(Module *M, const std::vector<Function*> &F,
                                   ValueToValueMapTy &VMap);
 
 } // End llvm namespace
 
 #endif

tools/bugpoint/CrashDebugger.cpp

ReduceCrashingGlobalVariables::TestGlobalVariables(
   PrintGlobalVariableList(GVs);
   outs() << ": ";
 
   // Loop over and delete any global variables which we aren't supposed to be
   // playing with...
   for (Module::global_iterator I = M->global_begin(), E = M->global_end();
        I != E; ++I)
     if (I->hasInitializer() && !GVSet.count(I)) {
-      I->setInitializer(nullptr);
+      DeleteGlobalInitializer(I);
       I->setLinkage(GlobalValue::ExternalLinkage);
     }
 
   // Try running the hacked up program...
   if (TestFn(BD, M)) {
     BD.setNewProgram(M);        // It crashed, keep the trimmed version...
 
     // Make sure to use global variable pointers that point into the now-current
if (!NoGlobalRM &&
     // Now try to reduce the number of global variable initializers in the
     // module to something small.
     Module *M = CloneModule(BD.getProgram());
     bool DeletedInit = false;
 
     for (Module::global_iterator I = M->global_begin(), E = M->global_end();
          I != E; ++I)
       if (I->hasInitializer()) {
-        I->setInitializer(nullptr);
+        DeleteGlobalInitializer(I);
         I->setLinkage(GlobalValue::ExternalLinkage);
         DeletedInit = true;
       }
 
     if (!DeletedInit) {
       delete M;  // No change made...
     } else {
       // See if the program still causes a crash...

tools/bugpoint/ExtractFunction.cpp

if (M->size() == NewM->size() || --NumExtracted == 0) {
     Module::iterator MI = NewM->begin();
     for (unsigned i = 0, e = M->size(); i != e; ++i)
       ++MI;
   }
 
   return NewM;
 }
 
+static void eliminateAliases(GlobalValue *GV) {
+  // First, check whether a GlobalAlias references this definition.
+  // GlobalAlias MAY NOT reference declarations.
+  for (;;) {
+    // 1. Find aliases
+    SmallVector<GlobalAlias*,1> aliases;
+    Module *M = GV->getParent();
+    for (Module::alias_iterator I=M->alias_begin(), E=M->alias_end(); I!=E; ++I)
+      if (I->getAliasee()->stripPointerCasts() == GV)
+        aliases.push_back(&*I);
+    if (aliases.empty())
+      break;
+    // 2. Resolve aliases
+    for (unsigned i=0, e=aliases.size(); i<e; ++i) {
+      aliases[i]->replaceAllUsesWith(aliases[i]->getAliasee());
+      aliases[i]->eraseFromParent();
+    }
+    // 3. Repeat until no more aliases found; there might
+    // be an alias to an alias...
+  }
+}
+
+//
+// DeleteGlobalInitializer - "Remove" the global variable by deleting its initializer,
+// making it external.
+//
+void llvm::DeleteGlobalInitializer(GlobalVariable *GV) {
+  eliminateAliases(GV);
+  GV->setInitializer(nullptr);
+}
 
 // DeleteFunctionBody - "Remove" the function by deleting all of its basic
 // blocks, making it external.
 //
 void llvm::DeleteFunctionBody(Function *F) {
+  eliminateAliases(F);
+
   // delete the body of the function...
   F->deleteBody();
   assert(F->isDeclaration() && "This didn't make the function external!");
 }
 
 /// GetTorInit - Given a list of entries for static ctors/dtors, return them
 /// as a constant array.
 static Constant *GetTorInit(std::vector<std::pair<Function*, int> > &TorList) {
   assert(!TorList.empty() && "Don't create empty tor list!");
   std::vector<Constant*> ArrayElts;
   Type *Int32Ty = Type::getInt32Ty(TorList[0].first->getContext());
 
   StructType *STy =
       StructType::get(Int32Ty, TorList[0].first->getType(), nullptr);
   for (unsigned i = 0, e = TorList.size(); i != e; ++i) {
     Constant *Elts[] = {
       ConstantInt::get(Int32Ty, TorList[i].second),
       TorList[i].first
     };
     ArrayElts.push_back(ConstantStruct::get(STy, Elts));
if (Function *TestFn = globalInitUsesExternalBA(I)) {
         errs() << "*** Error: when reducing functions, encountered "
                   "the global '";
         GV->printAsOperand(errs(), false);
         errs() << "' with an initializer that references blockaddresses "
                   "from safe function '" << SafeFn->getName()
                << "' and from test function '" << TestFn->getName() << "'.\n";
         exit(1);
       }
-      I->setInitializer(nullptr);  // Delete the initializer to make it external
+      DeleteGlobalInitializer(I); // Delete the initializer to make it external
     } else {
       // If we keep it in the safe module, then delete it in the test module
-      GV->setInitializer(nullptr);
+      DeleteGlobalInitializer(GV);
     }
   }
 
   // Make sure that there is a global ctor/dtor array in both halves of the
   // module if they both have static ctor/dtor functions.
   SplitStaticCtorDtor("llvm.global_ctors", M, New, NewVMap);
   SplitStaticCtorDtor("llvm.global_dtors", M, New, NewVMap);