SymbolRewriter: introduce the SymbolRewriter pass

[abdulras]

Summary

To provide some additional context around this change. We (Facebook) have been using this for some internal testing and believe that this pass is generally useful and others may benefit from it. It provides a clean, flexible mechanism for symbol inter-positioning which is very useful in scenarios related to profiling. Furthermore, this pass may be directly useful in LLVM itself for the santizers which perform symbol inter-positioning for code analysis purposes. As such, we would like to merge this pass into the public LLVM repository.

---

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.

[grosbach]

There are a lot of definitions that appear to be private to the rewriter in the include/llvm/.../.h file. I suspect most of that content can move to an anonymous namespace in the .cpp file.

In general, the code needs a lot more comments. It's generally clean code, which is great for understand how things work, but comments are still useful for the "why" of things.

A few inline comments as well. Once some of this is sorted out, I may have additional feedback, but this will give us a good starting place, I hope.

include/llvm/CodeGen/Passes.h

600 ↗

(On Diff #11670)

Nothing calls the second version.

include/llvm/Transforms/Utils/SymbolRewriter.h

2

Needs file level comment header. Should include a fairly substantive description of what the pass does.

19

Why is there a SymbolRewriter namespace? The classes themselves should already provide the necessary scoping.

27

Comments on what these meen would be very helpful.

Why the RDT_ prefix? They're already namespaced inside the class.

53

const on a non-reference argument?

64

In general, these classes all need some comments explaining how they fit together.

lib/Transforms/Makefile

12 ↗

(On Diff #11670)

Why is this in its own subdirectory? The header is in Utils (which seems to make sense), so the implementation should be, too, I'd think.

lib/Transforms/SymbolRewriter/SymbolRewriter.cpp

474 ↗

(On Diff #11670)

Eh? Bitwise operator on the return values of empty()? That's a non-standard idiom. Rewriting in terms of boolean operators would make more sense.

495 ↗

(On Diff #11670)

We have a "using namespace llvm" at the top. No need for the explicit scope operator here.

544 ↗

(On Diff #11670)

Nothing calls this version of the factory function?

[abdulras]

Given that the move will simplify the diff, I've addressed the inline comments and move into Utils from its own directory. I'll see about restructuring the descriptors to private from public. If clang ever needs to generate the descriptors, we can make them public then. Better to make as many of the types opaque as possible.

include/llvm/CodeGen/Passes.h

600 ↗

(On Diff #11670)

Correct. Nothing calls it yet, the idea was to add this in this form to permit clang to read the file and provide the descriptor list to LLVM so that we do not have to read the file in the backend.

include/llvm/Transforms/Utils/SymbolRewriter.h

2

Added something to cover this. Happy to enhance it as necessary.

19

Well, this is being push up towards clang, but I don't see why it would need to be able to see the ModulePass subclass. I thought that the namespace was a good solution, but Im not tied to it. How would you prefer to handle this situation?

27

This was written way before we adopted C++11. I can use an enum class now. Comments added.

53

StringRefs shouldn't be const nor refs. Fixed.

64

Sure. Added a block comment describing them all. Let me know if you would like to enhance that in any way.

lib/Transforms/Makefile

12 ↗

(On Diff #11670)

Thought it was something that was less of a general purpose utility for the other transformations. Happily moved as it greatly simplifies the build aspect.

lib/Transforms/SymbolRewriter/SymbolRewriter.cpp

474 ↗

(On Diff #11670)

Sure. Done.

495 ↗

(On Diff #11670)

Fixed.

544 ↗

(On Diff #11670)

This is meant for the integration with clang. I figured that adding that up front would be better. Im happy to remove it for the time being.

[abdulras]

Address a number of Jim's comments.

[abdulras]

Address Jim's comments about reducing duplication and some error handling.

[grosbach]

Looking much improved. A few questions, but in general I think this is fine.

include/llvm/IR/Module.h

373

This drops the const-ness of the return value. Do we need to do that?

include/llvm/Transforms/Utils/SymbolRewriter.h

50

Since the pass factory and the parser take parameters via reference, is there any need to have the actual classes for the descriptors and such in the public header file? Those seem like implementation details which can be in the .cpp file.

[abdulras]

include/llvm/IR/Module.h

373

Yes, in order to rename the Value.

include/llvm/Transforms/Utils/SymbolRewriter.h

50

Ah, I think I see what you mean, I can remove the concrete types from the header as only the iplist type information is needed.

[abdulras]

Committed in SVN r221548 with the recommended change.

[abdulras]

Seems that I can't close the revision :-(.

include/llvm/IR/Module.h

   /// 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);
   }
 

   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
 /// @{

include/llvm/InitializePasses.h

 void initializeStackMapLivenessPass(PassRegistry&);
 void initializeMachineCombinerPass(PassRegistry &);
 void initializeLoadCombinePass(PassRegistry&);
+void initializeRewriteSymbolsPass(PassRegistry&);
 }
 
 #endif

include/llvm/LinkAllPasses.h

 #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>
 

       (void) llvm::createPartiallyInlineLibCallsPass();
       (void) llvm::createScalarizerPass();
       (void) llvm::createSeparateConstOffsetFromGEPPass();
+      (void) llvm::createRewriteSymbolsPass();
 
       (void)new llvm::IntervalPartition();
       (void)new llvm::FindUsedTypes();

include/llvm/Transforms/Utils/SymbolRewriter.h

+//===-- 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;
+
+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>;
+
+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

lib/CodeGen/Passes.cpp

 #include "llvm/Target/TargetLowering.h"
 #include "llvm/Target/TargetSubtargetInfo.h"
 #include "llvm/Transforms/Scalar.h"
+#include "llvm/Transforms/Utils/SymbolRewriter.h"
 
 using namespace llvm;
 

 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

lib/Transforms/Utils/CMakeLists.txt

   UnifyFunctionExitNodes.cpp
   Utils.cpp
   ValueMapper.cpp
+  SymbolRewriter.cpp
   )
 
 add_dependencies(LLVMTransformUtils intrinsics_gen)

lib/Transforms/Utils/SymbolRewriter.cpp

+//===- 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 {
+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);
+}

test/SymbolRewriter/rewrite.ll

+; 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: }
+

test/SymbolRewriter/rewrite.map

+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,
+}
+

tools/opt/opt.cpp

   // supported.
   initializeCodeGenPreparePass(Registry);
   initializeAtomicExpandPass(Registry);
+  initializeRewriteSymbolsPass(Registry);
 
 #ifdef LINK_POLLY_INTO_TOOLS
   polly::initializePollyPasses(Registry);