[llvm-extract] Add -dag option.

[Bigcheese]

Summary

The -dag option informs llvm-extract to keep all global values that were
explicitly listed and that are reachable from those listed. This is useful for
extracting sub-graphs of a program.

[chandlerc]

The name "dag" doesn't make sense to me here. We should be calling it something like "globals". All of the extract stuff works by extracting the entire sub-graph needed.

tools/llvm-extract/llvm-extract.cpp

 //===- llvm-extract.cpp - LLVM function extraction utility ----------------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 // This utility changes the input module to only contain a single function,
 // which is primarily used for debugging transformations.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/ADT/SetVector.h"
 #include "llvm/ADT/SmallPtrSet.h"
+#include "llvm/ADT/STLExtras.h"
 #include "llvm/Bitcode/BitcodeWriterPass.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/IRPrintingPasses.h"
 #include "llvm/IR/LLVMContext.h"
 #include "llvm/IR/Module.h"
 #include "llvm/IRReader/IRReader.h"
 #include "llvm/PassManager.h"
 #include "llvm/Support/CommandLine.h"

 ExtractRegExpGlobals("rglob", cl::desc("Specify global(s) to extract using a "
                                        "regular expression"),
                      cl::ZeroOrMore, cl::value_desc("rglobal"));
 
 static cl::opt<bool>
 OutputAssembly("S",
                cl::desc("Write output as LLVM assembly"), cl::Hidden);
 
+static cl::opt<bool>
+ExtractDAG("dag", cl::desc("Extract all globals and functions referenced by "
+                           "the selected global values."));
+
+SmallPtrSet<Constant *, 8> SeenConstants;
+
+void MarkUsed(Constant *C, SetVector<GlobalValue *> &GVs);
+
+/// \brief Mark the specific global value as used, and recursively mark anything
+///   that it uses as also used.
+void MarkUsed(GlobalValue *G, SetVector<GlobalValue *> &GVs) {
+  // If the global is already in the set, no need to reprocess it.
+  if (!GVs.insert(G))
+    return;
+  
+  if (GlobalVariable *GV = dyn_cast<GlobalVariable>(G)) {
+    // If this is a global variable, we must make sure to add any global values
+    // referenced by the initializer to the alive set.
+    if (GV->hasInitializer())
+      MarkUsed(GV->getInitializer(), GVs);
+  } else if (GlobalAlias *GA = dyn_cast<GlobalAlias>(G)) {
+    // The target of a global alias is needed.
+    MarkUsed(GA->getAliasee(), GVs);
+  } else {
+    // Otherwise this must be a function object.  We have to scan the body of
+    // the function looking for constants and global values which are used as
+    // operands.  Any operands of these types must be processed to ensure that
+    // any globals used will be marked as needed.
+    Function *F = cast<Function>(G);
+
+    if (F->hasPrefixData())
+      MarkUsed(F->getPrefixData(), GVs);
+
+    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))
+            MarkUsed(GV, GVs);
+          else if (Constant *C = dyn_cast<Constant>(*U))
+            MarkUsed(C, GVs);
+  }
+}
+
+void MarkUsed(Constant *C, SetVector<GlobalValue *> &GVs) {
+  if (GlobalValue *GV = dyn_cast<GlobalValue>(C))
+    return MarkUsed(GV, GVs);
+
+  // Loop over all of the operands of the constant, adding any globals they
+  // use to the list of needed globals.
+  for (User::op_iterator I = C->op_begin(), E = C->op_end(); I != E; ++I) {
+    // If we've already processed this constant there's no need to do it again.
+    Constant *Op = dyn_cast<Constant>(*I);
+    if (Op && SeenConstants.insert(Op))
+      MarkUsed(Op, GVs);
+  }
+}
+
 int main(int argc, char **argv) {
   // Print a stack trace if we signal out.
   sys::PrintStackTraceOnErrorSignal();
   PrettyStackTraceProgram X(argc, argv);
 
   LLVMContext &Context = getGlobalContext();
   llvm_shutdown_obj Y;  // Call llvm_shutdown() on exit.
   cl::ParseCommandLineOptions(argc, argv, "llvm extractor\n");
for (size_t i = 0, e = ExtractRegExpFuncs.size(); i != e; ++i) {
     }
     if (!match) {
       errs() << argv[0] << ": program doesn't contain global named '"
              << ExtractRegExpFuncs[i] << "'!\n";
       return 1;
     }
   }
 
+  // Add all referenced GVs.
+  if (ExtractDAG) {
+    SetVector<GlobalValue *> NewGVs;
+    for (size_t i = 0; i < GVs.size(); ++i) {
+      GlobalValue *GV = GVs[i];
+      if (GV->isMaterializable()) {
+        std::string ErrInfo;
+        if (GV->Materialize(&ErrInfo)) {
+          errs() << argv[0] << ": error reading input: " << ErrInfo << "\n";
+          return 1;
+        }
+      }
+      MarkUsed(GV, NewGVs);
+    }
+    GVs = NewGVs;
+  }
+
   // Materialize requisite global values.
   if (!DeleteFn)
     for (size_t i = 0, e = GVs.size(); i != e; ++i) {
       GlobalValue *GV = GVs[i];
       if (GV->isMaterializable()) {
         std::string ErrInfo;
         if (GV->Materialize(&ErrInfo)) {
           errs() << argv[0] << ": error reading input: " << ErrInfo << "\n";