Transform: add SymbolRewriter pass

This introduces the symbol rewriter. This is an IR->IR transformation that is
implemented as a CodeGenPrepare pass. This allows for the transparent
adjustment of the symbols during compilation.

It provides a clean, simple, elegant solution for symbol inter-positioning. This
technique is often used, such as in the various sanitizers and performance
analysis.

The control of this is via a custom YAML syntax map file that indicates source
to destination mapping, so as to avoid having the compiler to know the exact
details of the source to destination transformations.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@221548 91177308-0d34-0410-b5e6-96231b3b80d8

10 files changed, 822 insertions, 2 deletions

diff --git a/include/llvm/IR/Module.h b/include/llvm/IR/Module.h
index 23bdde56c71..7fff80ae24b 100644
--- a/include/llvm/IR/Module.h
+++ b/include/llvm/IR/Module.h
@@ -371,8 +371,11 @@ public:
   /// does not exist, return null. If AllowInternal is set to true, this
   /// function will return types that have InternalLinkage. By default, these
   /// types are not returned.
-  const GlobalVariable *getGlobalVariable(StringRef Name,
-                                          bool AllowInternal = false) const {
+  GlobalVariable *getGlobalVariable(StringRef Name) const {
+    return getGlobalVariable(Name, false);
+  }
+
+  GlobalVariable *getGlobalVariable(StringRef Name, bool AllowInternal) const {
     return const_cast<Module *>(this)->getGlobalVariable(Name, AllowInternal);
   }
 
@@ -564,6 +567,13 @@ public:
   size_t                  size() const  { return FunctionList.size(); }
   bool                    empty() const { return FunctionList.empty(); }
 
+  iterator_range<iterator> functions() {
+    return iterator_range<iterator>(begin(), end());
+  }
+  iterator_range<const_iterator> functions() const {
+    return iterator_range<const_iterator>(begin(), end());
+  }
+
 /// @}
 /// @name Alias Iteration
 /// @{
diff --git a/include/llvm/InitializePasses.h b/include/llvm/InitializePasses.h
index 2964798e071..c6440f6e241 100644
--- a/include/llvm/InitializePasses.h
+++ b/include/llvm/InitializePasses.h
@@ -284,6 +284,7 @@ void initializeMachineFunctionPrinterPassPass(PassRegistry&);
 void initializeStackMapLivenessPass(PassRegistry&);
 void initializeMachineCombinerPass(PassRegistry &);
 void initializeLoadCombinePass(PassRegistry&);
+void initializeRewriteSymbolsPass(PassRegistry&);
 }
 
 #endif
diff --git a/include/llvm/LinkAllPasses.h b/include/llvm/LinkAllPasses.h
index b17e673be09..ef354f9cf50 100644
--- a/include/llvm/LinkAllPasses.h
+++ b/include/llvm/LinkAllPasses.h
@@ -34,6 +34,7 @@
 #include "llvm/Transforms/ObjCARC.h"
 #include "llvm/Transforms/Scalar.h"
 #include "llvm/Transforms/Utils/UnifyFunctionExitNodes.h"
+#include "llvm/Transforms/Utils/SymbolRewriter.h"
 #include "llvm/Transforms/Vectorize.h"
 #include <cstdlib>
 
@@ -163,6 +164,7 @@ namespace {
       (void) llvm::createPartiallyInlineLibCallsPass();
       (void) llvm::createScalarizerPass();
       (void) llvm::createSeparateConstOffsetFromGEPPass();
+      (void) llvm::createRewriteSymbolsPass();
 
       (void)new llvm::IntervalPartition();
       (void)new llvm::FindUsedTypes();
diff --git a/include/llvm/Transforms/Utils/SymbolRewriter.h b/include/llvm/Transforms/Utils/SymbolRewriter.h
new file mode 100644
index 00000000000..af793726579
--- /dev/null
+++ b/include/llvm/Transforms/Utils/SymbolRewriter.h
@@ -0,0 +1,155 @@
+//===-- SymbolRewriter.h - Symbol Rewriting Pass ----------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file provides the prototypes and definitions related to the Symbol
+// Rewriter pass.
+//
+// The Symbol Rewriter pass takes a set of rewrite descriptors which define
+// transformations for symbol names.  These can be either single name to name
+// trnsformation or more broad regular expression based transformations.
+//
+// All the functions are re-written at the IR level.  The Symbol Rewriter itself
+// is exposed as a module level pass.  All symbols at the module level are
+// iterated.  For any matching symbol, the requested transformation is applied,
+// updating references to it as well (a la RAUW).  The resulting binary will
+// only contain the rewritten symbols.
+//
+// By performing this operation in the compiler, we are able to catch symbols
+// that would otherwise not be possible to catch (e.g. inlined symbols).
+//
+// This makes it possible to cleanly transform symbols without resorting to
+// overly-complex macro tricks and the pre-processor.  An example of where this
+// is useful is the sanitizers where we would like to intercept a well-defined
+// set of functions across the module.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_TRANSFORMS_UTILS_SYMBOL_REWRITER_H
+#define LLVM_TRANSFORMS_UTILS_SYMBOL_REWRITER_H
+
+#include "llvm/ADT/ilist.h"
+#include "llvm/ADT/ilist_node.h"
+#include "llvm/IR/Module.h"
+
+namespace llvm {
+class MemoryBuffer;
+
+namespace yaml {
+class KeyValueNode;
+class MappingNode;
+class ScalarNode;
+class Stream;
+}
+
+namespace SymbolRewriter {
+/// The basic entity representing a rewrite operation.  It serves as the base
+/// class for any rewrite descriptor.  It has a certain set of specializations
+/// which describe a particular rewrite.
+///
+/// The RewriteMapParser can be used to parse a mapping file that provides the
+/// mapping for rewriting the symbols.  The descriptors individually describe
+/// whether to rewrite a function, global variable, or global alias.  Each of
+/// these can be selected either by explicitly providing a name for the ones to
+/// be rewritten or providing a (posix compatible) regular expression that will
+/// select the symbols to rewrite.  This descriptor list is passed to the
+/// SymbolRewriter pass.
+class RewriteDescriptor : public ilist_node<RewriteDescriptor> {
+  RewriteDescriptor(const RewriteDescriptor &) LLVM_DELETED_FUNCTION;
+
+  const RewriteDescriptor &
+  operator=(const RewriteDescriptor &) LLVM_DELETED_FUNCTION;
+
+public:
+  enum class Type {
+    Invalid,        /// invalid
+    Function,       /// function - descriptor rewrites a function
+    GlobalVariable, /// global variable - descriptor rewrites a global variable
+    NamedAlias,     /// named alias - descriptor rewrites a global alias
+  };
+
+  virtual ~RewriteDescriptor() {}
+
+  Type getType() const { return Kind; }
+
+  virtual bool performOnModule(Module &M) = 0;
+
+protected:
+  explicit RewriteDescriptor(Type T) : Kind(T) {}
+
+private:
+  const Type Kind;
+};
+
+typedef iplist<RewriteDescriptor> RewriteDescriptorList;
+
+class RewriteMapParser {
+public:
+  RewriteMapParser() {}
+  ~RewriteMapParser() {}
+
+  bool parse(const std::string &MapFile, RewriteDescriptorList *Descriptors);
+
+private:
+  bool parse(std::unique_ptr<MemoryBuffer> &MapFile, RewriteDescriptorList *DL);
+  bool parseEntry(yaml::Stream &Stream, yaml::KeyValueNode &Entry,
+                  RewriteDescriptorList *DL);
+  bool parseRewriteFunctionDescriptor(yaml::Stream &Stream,
+                                      yaml::ScalarNode *Key,
+                                      yaml::MappingNode *Value,
+                                      RewriteDescriptorList *DL);
+  bool parseRewriteGlobalVariableDescriptor(yaml::Stream &Stream,
+                                            yaml::ScalarNode *Key,
+                                            yaml::MappingNode *Value,
+                                            RewriteDescriptorList *DL);
+  bool parseRewriteGlobalAliasDescriptor(yaml::Stream &YS, yaml::ScalarNode *K,
+                                         yaml::MappingNode *V,
+                                         RewriteDescriptorList *DL);
+};
+}
+
+template <>
+struct ilist_traits<SymbolRewriter::RewriteDescriptor>
+    : public ilist_default_traits<SymbolRewriter::RewriteDescriptor> {
+  mutable ilist_half_node<SymbolRewriter::RewriteDescriptor> Sentinel;
+
+public:
+  // createSentinel is used to get a reference to a node marking the end of
+  // the list.  Because the sentinel is relative to this instance, use a
+  // non-static method.
+  SymbolRewriter::RewriteDescriptor *createSentinel() const {
+    // since i[p] lists always publicly derive from the corresponding
+    // traits, placing a data member in this class will augment the
+    // i[p]list.  Since the NodeTy is expected to publicly derive from
+    // ilist_node<NodeTy>, there is a legal viable downcast from it to
+    // NodeTy.  We use this trick to superpose i[p]list with a "ghostly"
+    // NodeTy, which becomes the sentinel.  Dereferencing the sentinel is
+    // forbidden (save the ilist_node<NodeTy>) so no one will ever notice
+    // the superposition.
+    return static_cast<SymbolRewriter::RewriteDescriptor *>(&Sentinel);
+  }
+  void destroySentinel(SymbolRewriter::RewriteDescriptor *) {}
+
+  SymbolRewriter::RewriteDescriptor *provideInitialHead() const {
+    return createSentinel();
+  }
+
+  SymbolRewriter::RewriteDescriptor *
+  ensureHead(SymbolRewriter::RewriteDescriptor *&) const {
+    return createSentinel();
+  }
+
+  static void noteHead(SymbolRewriter::RewriteDescriptor *,
+                       SymbolRewriter::RewriteDescriptor *) {}
+};
+
+ModulePass *createRewriteSymbolsPass();
+ModulePass *createRewriteSymbolsPass(SymbolRewriter::RewriteDescriptorList &);
+}
+
+#endif
diff --git a/lib/CodeGen/Passes.cpp b/lib/CodeGen/Passes.cpp
index 4762116a656..3053f7f6b3f 100644
--- a/lib/CodeGen/Passes.cpp
+++ b/lib/CodeGen/Passes.cpp
@@ -27,6 +27,7 @@
 #include "llvm/Target/TargetLowering.h"
 #include "llvm/Target/TargetSubtargetInfo.h"
 #include "llvm/Transforms/Scalar.h"
+#include "llvm/Transforms/Utils/SymbolRewriter.h"
 
 using namespace llvm;
 
@@ -445,6 +446,7 @@ void TargetPassConfig::addPassesToHandleExceptions() {
 void TargetPassConfig::addCodeGenPrepare() {
   if (getOptLevel() != CodeGenOpt::None && !DisableCGP)
     addPass(createCodeGenPreparePass(TM));
+  addPass(llvm::createRewriteSymbolsPass());
 }
 
 /// Add common passes that perform LLVM IR to IR transforms in preparation for
diff --git a/lib/Transforms/Utils/CMakeLists.txt b/lib/Transforms/Utils/CMakeLists.txt
index fcf548f97c5..5c370233f6d 100644
--- a/lib/Transforms/Utils/CMakeLists.txt
+++ b/lib/Transforms/Utils/CMakeLists.txt
@@ -36,6 +36,7 @@ add_llvm_library(LLVMTransformUtils
   UnifyFunctionExitNodes.cpp
   Utils.cpp
   ValueMapper.cpp
+  SymbolRewriter.cpp
   )
 
 add_dependencies(LLVMTransformUtils intrinsics_gen)
diff --git a/lib/Transforms/Utils/SymbolRewriter.cpp b/lib/Transforms/Utils/SymbolRewriter.cpp
new file mode 100644
index 00000000000..9afdff1d66c
--- /dev/null
+++ b/lib/Transforms/Utils/SymbolRewriter.cpp
@@ -0,0 +1,543 @@
+//===- SymbolRewriter.cpp - Symbol Rewriter ---------------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// SymbolRewriter is a LLVM pass which can rewrite symbols transparently within
+// existing code.  It is implemented as a compiler pass and is configured via a
+// YAML configuration file.
+//
+// The YAML configuration file format is as follows:
+//
+// RewriteMapFile := RewriteDescriptors
+// RewriteDescriptors := RewriteDescriptor | RewriteDescriptors
+// RewriteDescriptor := RewriteDescriptorType ':' '{' RewriteDescriptorFields '}'
+// RewriteDescriptorFields := RewriteDescriptorField | RewriteDescriptorFields
+// RewriteDescriptorField := FieldIdentifier ':' FieldValue ','
+// RewriteDescriptorType := Identifier
+// FieldIdentifier := Identifier
+// FieldValue := Identifier
+// Identifier := [0-9a-zA-Z]+
+//
+// Currently, the following descriptor types are supported:
+//
+// - function:          (function rewriting)
+//      + Source        (original name of the function)
+//      + Target        (explicit transformation)
+//      + Transform     (pattern transformation)
+//      + Naked         (boolean, whether the function is undecorated)
+// - global variable:   (external linkage global variable rewriting)
+//      + Source        (original name of externally visible variable)
+//      + Target        (explicit transformation)
+//      + Transform     (pattern transformation)
+// - global alias:      (global alias rewriting)
+//      + Source        (original name of the aliased name)
+//      + Target        (explicit transformation)
+//      + Transform     (pattern transformation)
+//
+// Note that source and exactly one of [Target, Transform] must be provided
+//
+// New rewrite descriptors can be created.  Addding a new rewrite descriptor
+// involves:
+//
+//  a) extended the rewrite descriptor kind enumeration
+//     (<anonymous>::RewriteDescriptor::RewriteDescriptorType)
+//  b) implementing the new descriptor
+//     (c.f. <anonymous>::ExplicitRewriteFunctionDescriptor)
+//  c) extending the rewrite map parser
+//     (<anonymous>::RewriteMapParser::parseEntry)
+//
+//  Specify to rewrite the symbols using the `-rewrite-symbols` option, and
+//  specify the map file to use for the rewriting via the `-rewrite-map-file`
+//  option.
+//
+//===----------------------------------------------------------------------===//
+
+#define DEBUG_TYPE "symbol-rewriter"
+#include "llvm/CodeGen/Passes.h"
+#include "llvm/Pass.h"
+#include "llvm/PassManager.h"
+#include "llvm/Support/CommandLine.h"
+#include "llvm/Support/Debug.h"
+#include "llvm/Support/MemoryBuffer.h"
+#include "llvm/Support/Regex.h"
+#include "llvm/Support/SourceMgr.h"
+#include "llvm/Support/YAMLParser.h"
+#include "llvm/Support/raw_ostream.h"
+#include "llvm/Transforms/IPO/PassManagerBuilder.h"
+#include "llvm/Transforms/Utils/SymbolRewriter.h"
+
+using namespace llvm;
+
+static cl::list<std::string> RewriteMapFiles("rewrite-map-file",
+                                             cl::desc("Symbol Rewrite Map"),
+                                             cl::value_desc("filename"));
+
+namespace llvm {
+namespace SymbolRewriter {
+template <RewriteDescriptor::Type DT, typename ValueType,
+          ValueType *(llvm::Module::*Get)(StringRef) const>
+class ExplicitRewriteDescriptor : public RewriteDescriptor {
+public:
+  const std::string Source;
+  const std::string Target;
+
+  ExplicitRewriteDescriptor(StringRef S, StringRef T, const bool Naked)
+      : RewriteDescriptor(DT), Source(Naked ? StringRef("\01" + S.str()) : S),
+        Target(T) {}
+
+  bool performOnModule(Module &M) override;
+
+  static bool classof(const RewriteDescriptor *RD) {
+    return RD->getType() == DT;
+  }
+};
+
+template <RewriteDescriptor::Type DT, typename ValueType,
+          ValueType *(llvm::Module::*Get)(StringRef) const>
+bool ExplicitRewriteDescriptor<DT, ValueType, Get>::performOnModule(Module &M) {
+  bool Changed = false;
+  if (ValueType *S = (M.*Get)(Source)) {
+    if (Value *T = (M.*Get)(Target))
+      S->setValueName(T->getValueName());
+    else
+      S->setName(Target);
+    Changed = true;
+  }
+  return Changed;
+}
+
+template <RewriteDescriptor::Type DT, typename ValueType,
+          ValueType *(llvm::Module::*Get)(StringRef) const,
+          iterator_range<typename iplist<ValueType>::iterator> (llvm::Module::*Iterator)()>
+class PatternRewriteDescriptor : public RewriteDescriptor {
+public:
+  const std::string Pattern;
+  const std::string Transform;
+
+  PatternRewriteDescriptor(StringRef P, StringRef T)
+    : RewriteDescriptor(DT), Pattern(P), Transform(T) { }
+
+  bool performOnModule(Module &M) override;
+
+  static bool classof(const RewriteDescriptor *RD) {
+    return RD->getType() == DT;
+  }
+};
+
+template <RewriteDescriptor::Type DT, typename ValueType,
+          ValueType *(llvm::Module::*Get)(StringRef) const,
+          iterator_range<typename iplist<ValueType>::iterator> (llvm::Module::*Iterator)()>
+bool PatternRewriteDescriptor<DT, ValueType, Get, Iterator>::
+performOnModule(Module &M) {
+  bool Changed = false;
+  for (auto &C : (M.*Iterator)()) {
+    std::string Error;
+
+    std::string Name = Regex(Pattern).sub(Transform, C.getName(), &Error);
+    if (!Error.empty())
+      report_fatal_error("unable to transforn " + C.getName() + " in " +
+                         M.getModuleIdentifier() + ": " + Error);
+
+    if (Value *V = (M.*Get)(Name))
+      C.setValueName(V->getValueName());
+    else
+      C.setName(Name);
+
+    Changed = true;
+  }
+  return Changed;
+}
+
+/// Represents a rewrite for an explicitly named (function) symbol.  Both the
+/// source function name and target function name of the transformation are
+/// explicitly spelt out.
+using ExplicitRewriteFunctionDescriptor =
+    ExplicitRewriteDescriptor<RewriteDescriptor::Type::Function, llvm::Function,
+                              &llvm::Module::getFunction>;
+
+/// Represents a rewrite for an explicitly named (global variable) symbol.  Both
+/// the source variable name and target variable name are spelt out.  This
+/// applies only to module level variables.
+using ExplicitRewriteGlobalVariableDescriptor =
+    ExplicitRewriteDescriptor<RewriteDescriptor::Type::GlobalVariable,
+                              llvm::GlobalVariable,
+                              &llvm::Module::getGlobalVariable>;
+
+/// Represents a rewrite for an explicitly named global alias.  Both the source
+/// and target name are explicitly spelt out.
+using ExplicitRewriteNamedAliasDescriptor =
+    ExplicitRewriteDescriptor<RewriteDescriptor::Type::NamedAlias,
+                              llvm::GlobalAlias, &llvm::Module::getNamedAlias>;
+
+/// Represents a rewrite for a regular expression based pattern for functions.
+/// A pattern for the function name is provided and a transformation for that
+/// pattern to determine the target function name create the rewrite rule.
+using PatternRewriteFunctionDescriptor =
+    PatternRewriteDescriptor<RewriteDescriptor::Type::Function, llvm::Function,
+                             &llvm::Module::getFunction,
+                             &llvm::Module::functions>;
+
+
+/// Represents a rewrite for a global variable based upon a matching pattern.
+/// Each global variable matching the provided pattern will be transformed as
+/// described in the transformation pattern for the target.  Applies only to
+/// module level variables.
+using PatternRewriteGlobalVariableDescriptor =
+    PatternRewriteDescriptor<RewriteDescriptor::Type::GlobalVariable,
+                             llvm::GlobalVariable,
+                             &llvm::Module::getGlobalVariable,
+                             &llvm::Module::globals>;
+
+/// PatternRewriteNamedAliasDescriptor - represents a rewrite for global
+/// aliases which match a given pattern.  The provided transformation will be
+/// applied to each of the matching names.
+using PatternRewriteNamedAliasDescriptor =
+    PatternRewriteDescriptor<RewriteDescriptor::Type::NamedAlias,
+                             llvm::GlobalAlias,
+                             &llvm::Module::getNamedAlias,
+                             &llvm::Module::aliases>;
+
+
+bool RewriteMapParser::parse(const std::string &MapFile,
+                             RewriteDescriptorList *DL) {
+  ErrorOr<std::unique_ptr<MemoryBuffer>> Mapping =
+      MemoryBuffer::getFile(MapFile);
+
+  if (!Mapping)
+    report_fatal_error("unable to read rewrite map '" + MapFile + "': " +
+                       Mapping.getError().message());
+
+  if (!parse(*Mapping, DL))
+    report_fatal_error("unable to parse rewrite map '" + MapFile + "'");
+
+  return true;
+}
+
+bool RewriteMapParser::parse(std::unique_ptr<MemoryBuffer> &MapFile,
+                             RewriteDescriptorList *DL) {
+  SourceMgr SM;
+  yaml::Stream YS(MapFile->getBuffer(), SM);
+
+  for (auto &Document : YS) {
+    yaml::MappingNode *DescriptorList;
+
+    // ignore empty documents
+    if (isa<yaml::NullNode>(Document.getRoot()))
+      continue;
+
+    DescriptorList = dyn_cast<yaml::MappingNode>(Document.getRoot());
+    if (!DescriptorList) {
+      YS.printError(Document.getRoot(), "DescriptorList node must be a map");
+      return false;
+    }
+
+    for (auto &Descriptor : *DescriptorList)
+      if (!parseEntry(YS, Descriptor, DL))
+        return false;
+  }
+
+  return true;
+}
+
+bool RewriteMapParser::parseEntry(yaml::Stream &YS, yaml::KeyValueNode &Entry,
+                                  RewriteDescriptorList *DL) {
+  const std::string kRewriteTypeFunction = "function";
+  const std::string kRewriteTypeGlobalVariable = "global variable";
+  const std::string kRewriteTypeGlobalAlias = "global alias";
+
+  yaml::ScalarNode *Key;
+  yaml::MappingNode *Value;
+  SmallString<32> KeyStorage;
+  StringRef RewriteType;
+
+  Key = dyn_cast<yaml::ScalarNode>(Entry.getKey());
+  if (!Key) {
+    YS.printError(Entry.getKey(), "rewrite type must be a scalar");
+    return false;
+  }
+
+  Value = dyn_cast<yaml::MappingNode>(Entry.getValue());
+  if (!Value) {
+    YS.printError(Entry.getValue(), "rewrite descriptor must be a map");
+    return false;
+  }
+
+  RewriteType = Key->getValue(KeyStorage);
+  if (RewriteType == kRewriteTypeFunction)
+    return parseRewriteFunctionDescriptor(YS, Key, Value, DL);
+  else if (RewriteType == kRewriteTypeGlobalVariable)
+    return parseRewriteGlobalVariableDescriptor(YS, Key, Value, DL);
+  else if (RewriteType == kRewriteTypeGlobalAlias)
+    return parseRewriteGlobalAliasDescriptor(YS, Key, Value, DL);
+
+  YS.printError(Entry.getKey(), "unknown rewrite type");
+  return false;
+}
+
+bool RewriteMapParser::
+parseRewriteFunctionDescriptor(yaml::Stream &YS, yaml::ScalarNode *K,
+                               yaml::MappingNode *Descriptor,
+                               RewriteDescriptorList *DL) {
+  const std::string kDescriptorFieldSource = "source";
+  const std::string kDescriptorFieldTarget = "target";
+  const std::string kDescriptorFieldTransform = "transform";
+  const std::string kDescriptorFieldNaked = "naked";
+
+  bool Naked = false;
+  std::string Source;
+  std::string Target;
+  std::string Transform;
+
+  for (auto &Field : *Descriptor) {
+    yaml::ScalarNode *Key;
+    yaml::ScalarNode *Value;
+    SmallString<32> KeyStorage;
+    SmallString<32> ValueStorage;
+    StringRef KeyValue;
+
+    Key = dyn_cast<yaml::ScalarNode>(Field.getKey());
+    if (!Key) {
+      YS.printError(Field.getKey(), "descriptor key must be a scalar");
+      return false;
+    }
+
+    Value = dyn_cast<yaml::ScalarNode>(Field.getValue());
+    if (!Value) {
+      YS.printError(Field.getValue(), "descriptor value must be a scalar");
+      return false;
+    }
+
+    KeyValue = Key->getValue(KeyStorage);
+    if (KeyValue == kDescriptorFieldSource) {
+      std::string Error;
+
+      Source = Value->getValue(ValueStorage);
+      if (!Regex(Source).isValid(Error)) {
+        YS.printError(Field.getKey(), "invalid regex: " + Error);
+        return false;
+      }
+    } else if (KeyValue == kDescriptorFieldTarget) {
+      Target = Value->getValue(ValueStorage);
+    } else if (KeyValue == kDescriptorFieldTransform) {
+      Transform = Value->getValue(ValueStorage);
+    } else if (KeyValue == kDescriptorFieldNaked) {
+      std::string Undecorated;
+
+      Undecorated = Value->getValue(ValueStorage);
+      Naked = StringRef(Undecorated).lower() == "true" || Undecorated == "1";
+    } else {
+      YS.printError(Field.getKey(), "unknown key for function");
+      return false;
+    }
+  }
+
+  if (Transform.empty() == Target.empty()) {
+    YS.printError(Descriptor,
+                  "exactly one of transform or target must be specified");
+    return false;
+  }
+
+  // TODO see if there is a more elegant solution to selecting the rewrite
+  // descriptor type
+  if (!Target.empty())
+    DL->push_back(new ExplicitRewriteFunctionDescriptor(Source, Target, Naked));
+  else
+    DL->push_back(new PatternRewriteFunctionDescriptor(Source, Transform));
+
+  return true;
+}
+
+bool RewriteMapParser::
+parseRewriteGlobalVariableDescriptor(yaml::Stream &YS, yaml::ScalarNode *K,
+                                     yaml::MappingNode *Descriptor,
+                                     RewriteDescriptorList *DL) {
+  const std::string kDescriptorFieldSource = "source";
+  const std::string kDescriptorFieldTarget = "target";
+  const std::string kDescriptorFieldTransform = "transform";
+
+  std::string Source;
+  std::string Target;
+  std::string Transform;
+
+  for (auto &Field : *Descriptor) {
+    yaml::ScalarNode *Key;
+    yaml::ScalarNode *Value;
+    SmallString<32> KeyStorage;
+    SmallString<32> ValueStorage;
+    StringRef KeyValue;
+
+    Key = dyn_cast<yaml::ScalarNode>(Field.getKey());
+    if (!Key) {
+      YS.printError(Field.getKey(), "descriptor Key must be a scalar");
+      return false;
+    }
+
+    Value = dyn_cast<yaml::ScalarNode>(Field.getValue());
+    if (!Value) {
+      YS.printError(Field.getValue(), "descriptor value must be a scalar");
+      return false;
+    }
+
+    KeyValue = Key->getValue(KeyStorage);
+    if (KeyValue == kDescriptorFieldSource) {
+      std::string Error;
+
+      Source = Value->getValue(ValueStorage);
+      if (!Regex(Source).isValid(Error)) {
+        YS.printError(Field.getKey(), "invalid regex: " + Error);
+        return false;
+      }
+    } else if (KeyValue == kDescriptorFieldTarget) {
+      Target = Value->getValue(ValueStorage);
+    } else if (KeyValue == kDescriptorFieldTransform) {
+      Transform = Value->getValue(ValueStorage);
+    } else {
+      YS.printError(Field.getKey(), "unknown Key for Global Variable");
+      return false;
+    }
+  }
+
+  if (Transform.empty() == Target.empty()) {
+    YS.printError(Descriptor,
+                  "exactly one of transform or target must be specified");
+    return false;
+  }
+
+  if (!Target.empty())
+    DL->push_back(new ExplicitRewriteGlobalVariableDescriptor(Source, Target,
+                                                              /*Naked*/false));
+  else
+    DL->push_back(new PatternRewriteGlobalVariableDescriptor(Source,
+                                                             Transform));
+
+  return true;
+}
+
+bool RewriteMapParser::
+parseRewriteGlobalAliasDescriptor(yaml::Stream &YS, yaml::ScalarNode *K,
+                                  yaml::MappingNode *Descriptor,
+                                  RewriteDescriptorList *DL) {
+  const std::string kDescriptorFieldSource = "source";
+  const std::string kDescriptorFieldTarget = "target";
+  const std::string kDescriptorFieldTransform = "transform";
+
+  std::string Source;
+  std::string Target;
+  std::string Transform;
+
+  for (auto &Field : *Descriptor) {
+    yaml::ScalarNode *Key;
+    yaml::ScalarNode *Value;
+    SmallString<32> KeyStorage;
+    SmallString<32> ValueStorage;
+    StringRef KeyValue;
+
+    Key = dyn_cast<yaml::ScalarNode>(Field.getKey());
+    if (!Key) {
+      YS.printError(Field.getKey(), "descriptor key must be a scalar");
+      return false;
+    }
+
+    Value = dyn_cast<yaml::ScalarNode>(Field.getValue());
+    if (!Value) {
+      YS.printError(Field.getValue(), "descriptor value must be a scalar");
+      return false;
+    }
+
+    KeyValue = Key->getValue(KeyStorage);
+    if (KeyValue == kDescriptorFieldSource) {
+      std::string Error;
+
+      Source = Value->getValue(ValueStorage);
+      if (!Regex(Source).isValid(Error)) {
+        YS.printError(Field.getKey(), "invalid regex: " + Error);
+        return false;
+      }
+    } else if (KeyValue == kDescriptorFieldTarget) {
+      Target = Value->getValue(ValueStorage);
+    } else if (KeyValue == kDescriptorFieldTransform) {
+      Transform = Value->getValue(ValueStorage);
+    } else {
+      YS.printError(Field.getKey(), "unknown key for Global Alias");
+      return false;
+    }
+  }
+
+  if (Transform.empty() == Target.empty()) {
+    YS.printError(Descriptor,
+                  "exactly one of transform or target must be specified");
+    return false;
+  }
+
+  if (!Target.empty())
+    DL->push_back(new ExplicitRewriteNamedAliasDescriptor(Source, Target,
+                                                          /*Naked*/false));
+  else
+    DL->push_back(new PatternRewriteNamedAliasDescriptor(Source, Transform));
+
+  return true;
+}
+}
+}
+
+namespace {
+class RewriteSymbols : public ModulePass {
+public:
+  static char ID; // Pass identification, replacement for typeid
+
+  RewriteSymbols();
+  RewriteSymbols(SymbolRewriter::RewriteDescriptorList &DL);
+
+  virtual bool runOnModule(Module &M) override;
+
+private:
+  void loadAndParseMapFiles();
+
+  SymbolRewriter::RewriteDescriptorList Descriptors;
+};
+
+char RewriteSymbols::ID = 0;
+
+RewriteSymbols::RewriteSymbols() : ModulePass(ID) {
+  initializeRewriteSymbolsPass(*PassRegistry::getPassRegistry());
+  loadAndParseMapFiles();
+}
+
+RewriteSymbols::RewriteSymbols(SymbolRewriter::RewriteDescriptorList &DL)
+    : ModulePass(ID) {
+  std::swap(Descriptors, DL);
+}
+
+bool RewriteSymbols::runOnModule(Module &M) {
+  bool Changed;
+
+  Changed = false;
+  for (auto &Descriptor : Descriptors)
+    Changed |= Descriptor.performOnModule(M);
+
+  return Changed;
+}
+
+void RewriteSymbols::loadAndParseMapFiles() {
+  const std::vector<std::string> MapFiles(RewriteMapFiles);
+  SymbolRewriter::RewriteMapParser parser;
+
+  for (const auto &MapFile : MapFiles)
+    parser.parse(MapFile, &Descriptors);
+}
+}
+
+INITIALIZE_PASS(RewriteSymbols, "rewrite-symbols", "Rewrite Symbols", false,
+                false);
+
+ModulePass *llvm::createRewriteSymbolsPass() { return new RewriteSymbols(); }
+
+ModulePass *
+llvm::createRewriteSymbolsPass(SymbolRewriter::RewriteDescriptorList &DL) {
+  return new RewriteSymbols(DL);
+}
diff --git a/test/SymbolRewriter/rewrite.ll b/test/SymbolRewriter/rewrite.ll
new file mode 100644
index 00000000000..716fff9f284
--- /dev/null
+++ b/test/SymbolRewriter/rewrite.ll
@@ -0,0 +1,59 @@
+; RUN: opt -mtriple i686-win32 -rewrite-symbols -rewrite-map-file %p/rewrite.map \
+; RUN:   %s -o - | llvm-dis | FileCheck %s
+
+declare void @source_function()
+@source_variable = external global i32
+declare void @source_function_pattern_function()
+declare void @source_function_pattern_multiple_function_matches()
+@source_variable_pattern_variable = external global i32
+@source_variable_pattern_multiple_variable_matches = external global i32
+declare void @"\01naked_source_function"()
+declare void @"\01__imp_missing_global_leader_prefix"()
+
+declare i32 @first_callee()
+declare i32 @second_callee()
+define i32 @caller() {
+  %rhs = call i32 @first_callee()
+  %lhs = call i32 @second_callee()
+  %res = add i32 %rhs, %lhs
+  ret i32 %res
+}
+
+%struct.S = type { i8 }
+@_ZN1SC1Ev = alias void (%struct.S*)* @_ZN1SC2Ev
+define void @_ZN1SC2Ev(%struct.S* %this) unnamed_addr align 2 {
+entry:
+  %this.addr = alloca %struct.S*, align 4
+  store %struct.S* %this, %struct.S** %this.addr, align 4
+  ret void
+}
+
+; CHECK: @target_variable = external global i32
+; CHECK-NOT: @source_variable = external global i32
+; CHECK: @target_pattern_variable = external global i32
+; CHECK-NOT: @source_pattern_variable = external global i32
+; CHECK: @target_pattern_multiple_variable_matches = external global i32
+; CHECK-NOT: @source_pattern_multiple_variable_matches = external global i32
+; CHECK: declare void @target_function()
+; CHECK-NOT: declare void @source_function()
+; CHECK: declare void @target_pattern_function()
+; CHECK-NOT: declare void @source_function_pattern_function()
+; CHECK: declare void @target_pattern_multiple_function_matches()
+; CHECK-NOT: declare void @source_function_pattern_multiple_function_matches()
+; CHECK: declare void @naked_target_function()
+; CHECK-NOT: declare void @"\01naked_source_function"()
+; CHECK-NOT: declare void @"\01__imp__imported_function"()
+; CHECK: declare void @"\01__imp_missing_global_leader_prefix"()
+; CHECK-NOT: declare void @"\01__imp_DO_NOT_REWRITE"()
+
+; CHECK: declare i32 @renamed_callee()
+; CHECK-NOT: declare i32 @first_callee()
+; CHECK: declare i32 @second_callee()
+; CHECK: define i32 @caller() {
+; CHECK:   %rhs = call i32 @renamed_callee()
+; CHECK-NOT: %rhs = call i32 @first_callee()
+; CHECK:   %lhs = call i32 @second_callee()
+; CHECK:   %res = add i32 %rhs, %lhs
+; CHECK:   ret i32 %res
+; CHECK: }
+
diff --git a/test/SymbolRewriter/rewrite.map b/test/SymbolRewriter/rewrite.map
new file mode 100644
index 00000000000..ef6dfc8ca2b
--- /dev/null
+++ b/test/SymbolRewriter/rewrite.map
@@ -0,0 +1,46 @@
+function: {
+  source: source_function,
+  target: target_function,
+}
+
+global variable: {
+  source: source_variable,
+  target: target_variable,
+}
+
+function: {
+  source: source_function_(.*),
+  transform: target_\1,
+}
+
+global variable: {
+  source: source_variable_(.*),
+  transform: target_\1,
+}
+
+function: {
+  source: naked_source_function,
+  target: naked_target_function,
+  naked: true,
+}
+
+function: {
+  source: imported_function,
+  target: exported_function,
+}
+
+function: {
+  source: missing_global_leader_prefix,
+  target: DO_NOT_REWRITE,
+}
+
+function: {
+  source: first_callee,
+  target: renamed_callee,
+}
+
+global alias: {
+  source: _ZN1SC1Ev,
+  target: _ZN1SD1Ev,
+}
+
diff --git a/tools/opt/opt.cpp b/tools/opt/opt.cpp
index 8a3362912c7..cdd22e48c0c 100644
--- a/tools/opt/opt.cpp
+++ b/tools/opt/opt.cpp
@@ -322,6 +322,7 @@ int main(int argc, char **argv) {
   // supported.
   initializeCodeGenPreparePass(Registry);
   initializeAtomicExpandPass(Registry);
+  initializeRewriteSymbolsPass(Registry);
 
 #ifdef LINK_POLLY_INTO_TOOLS
   polly::initializePollyPasses(Registry);