[LLVMdev] Removing AvailableExternal values in GlobalDCE (was Re: RFC: ThinLTO Impementation Plan)

[Teresa Johnson]

On Fri, May 15, 2015 at 11:20 PM, Teresa Johnson <tejohnson at google.com> wrote:
> On Fri, May 15, 2015 at 2:52 PM, David Blaikie <dblaikie at gmail.com> wrote:
>>
>>
>> On Fri, May 15, 2015 at 1:15 PM, Teresa Johnson <tejohnson at google.com>
>> wrote:
>>>
>>> On Fri, May 15, 2015 at 10:04 AM, David Blaikie <dblaikie at gmail.com>
>>> wrote:
>>> >
>>> >
>>> > On Fri, May 15, 2015 at 9:53 AM, Teresa Johnson <tejohnson at google.com>
>>> > wrote:
>>> >>
>>> >> Looking back through my GlobalDCE changes, it looks like one of the
>>> >> places I had changed (where we mark defined globals in runOnModule)
>>> >> already has a guard for !hasAvailableExternallyLinkage and
>>> >> !isDiscardableIfUnused, so my additional guard against marking
>>> >> imported functions is unnecessary. But the other place I had to change
>>> >> was in GlobalIsNeeded where it walks through the function and
>>> >> recursively marks any referenced global as needed. Here there was no
>>> >> guard against marking a global that is available externally as needed
>>> >> if it is referenced. I had added a check here to not mark imported
>>> >> functions as needed on reference unless they were discardable (i.e.
>>> >> link once). Is this a bug - should this have a guard against marking
>>> >> available externally function refs as needed?
>>> >
>>> >
>>> > Duncan's probably got a better idea of what the right answer is here. I
>>> > suspect "yes".
>>> >
>>> > The trick with available_externally is to ensure we keep these around
>>> > for
>>> > long enough that their definitions are useful (for inlining, constant
>>> > prop,
>>> > all that good stuff) but remove them before we actually do too much work
>>> > on
>>> > them, or at least before we emit them into the final object file.
>>>
>>> Yep, and that is exactly how long I want my imported functions to
>>> stick around. Currently I have the ThinLTO import pass added at the
>>> start of addLTOOptimizationPasses, just after the AA passes. So the
>>> imported functions stick around through global opt, constant merge,
>>> combining, and inlining. The call to GlobalDCE is just after inlining
>>> and a second globalopt.
>>>
>>> >
>>> > I imagine if GlobalDCE isn't removing available_externally functions
>>> > it's
>>> > because they're still useful in the optimization pipeline and something
>>> > further down the pipe removes them (because they do, ultimately, get
>>> > removed).
>>>
>>> That would be good to know, since if they are useful later on in the
>>> pipe then presumably my imported functions could be as well. But I
>>> wonder who is removing them since GlobalDCE isn't (if there are refs)?
>>
>>
>> Yep - seems no one removes them (well, probably if there are no calls to the
>> function at all they get removed as usual (eg: if all the calls are inlined
>> we probably drop the function as we would for a linkonce_odr function)). If
>> they're still around come codegen time, we just skip them:
>>
>> lib/CodeGen/MachineFunctionPass.cpp, MachineFunctionPass::runOnFunction:
>>
>> 33| bool MachineFunctionPass::runOnFunction(Function &F) {
>> 34|   // Do not codegen any 'available_externally' functions at all, they
>> have
>> 35|   // definitions outside the translation unit.
>> 36|   if (F.hasAvailableExternallyLinkage())
>> 37|     return false;
>> 38|
>> 39|   MachineFunction &MF = getAnalysis<MachineFunctionAnalysis>().getMF();
>> 40|   return runOnMachineFunction(MF);
>> 41| }
>
> Ok, thanks for digging this up. I guess that would work for the
> imported functions as well, but it seems like a waste of compile time
> if they are not useful after inlining/global opt. Is there any reason
> to keep them past GlobalDCE or should I try changing GlobalDCE so that
> it removes them?
>

I found allowing GlobalDCE to remove referenced
AvailableExternallyLinkage values earlier passes all the clang/llvm
tests (see patch below). AFAICT, it shouldn't be necessary to keep
these functions around past the first call to GlobalDCE (which is
after inlining), but let me know if I missed something. Although they
will be removed eventually by MachineFunctionPass as David pointed
out, so this is more of a compile-time improvement than anything. It
will affect ThinLTO more significantly in compile time because there
will be more functions with this linkage type, depending on how many
static functions are imported that we have to promote.

Also, what about available_externally variable
definitions/initializations? I'm not sure what source construct
currently can generate those, but are these suppressed/turned into
declarations at some point? Note that ThinLTO imported file static
variables always need to be promoted, and will be marked
available_external.

Index: lib/Transforms/IPO/GlobalDCE.cpp
===================================================================
--- lib/Transforms/IPO/GlobalDCE.cpp (revision 237590)
+++ lib/Transforms/IPO/GlobalDCE.cpp (working copy)
@@ -162,7 +162,10 @@ bool GlobalDCE::runOnModule(Module &M) {
     // themselves.
     for (unsigned i = 0, e = DeadFunctions.size(); i != e; ++i) {
       RemoveUnusedGlobalValue(*DeadFunctions[i]);
-      M.getFunctionList().erase(DeadFunctions[i]);
+      // Might have deleted the body of an available externally function that
+      // is still referenced. Leave the declaration.
+      if (DeadFunctions[i]->use_empty())
+        M.getFunctionList().erase(DeadFunctions[i]);
     }
     NumFunctions += DeadFunctions.size();
     Changed = true;
@@ -171,7 +174,10 @@ bool GlobalDCE::runOnModule(Module &M) {
   if (!DeadGlobalVars.empty()) {
     for (unsigned i = 0, e = DeadGlobalVars.size(); i != e; ++i) {
       RemoveUnusedGlobalValue(*DeadGlobalVars[i]);
-      M.getGlobalList().erase(DeadGlobalVars[i]);
+      // Might have deleted the definition of an available externally function
+      // that is still referenced. Leave the declaration.
+      if (DeadGlobalVars[i]->use_empty())
+        M.getGlobalList().erase(DeadGlobalVars[i]);
     }
     NumVariables += DeadGlobalVars.size();
     Changed = true;
@@ -231,8 +237,10 @@ void GlobalDCE::GlobalIsNeeded(GlobalValue *G) {
     for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB)
       for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I)
         for (User::op_iterator U = I->op_begin(), E = I->op_end(); U != E; ++U)
-          if (GlobalValue *GV = dyn_cast<GlobalValue>(*U))
-            GlobalIsNeeded(GV);
+          if (GlobalValue *GV = dyn_cast<GlobalValue>(*U)) {
+            if (!GV->hasAvailableExternallyLinkage())
+              GlobalIsNeeded(GV);
+          }
           else if (Constant *C = dyn_cast<Constant>(*U))
             MarkUsedGlobalsAsNeeded(C);
   }



-- 
Teresa Johnson | Software Engineer | tejohnson at google.com | 408-460-2413