1 //===- SymbolRewriter.cpp - Symbol Rewriter ---------------------*- C++ -*-===//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // SymbolRewriter is a LLVM pass which can rewrite symbols transparently within
11 // existing code.  It is implemented as a compiler pass and is configured via a
12 // YAML configuration file.
13 //
14 // The YAML configuration file format is as follows:
15 //
16 // RewriteMapFile := RewriteDescriptors
17 // RewriteDescriptors := RewriteDescriptor | RewriteDescriptors
18 // RewriteDescriptor := RewriteDescriptorType ':' '{' RewriteDescriptorFields '}'
19 // RewriteDescriptorFields := RewriteDescriptorField | RewriteDescriptorFields
20 // RewriteDescriptorField := FieldIdentifier ':' FieldValue ','
21 // RewriteDescriptorType := Identifier
22 // FieldIdentifier := Identifier
23 // FieldValue := Identifier
24 // Identifier := [0-9a-zA-Z]+
25 //
26 // Currently, the following descriptor types are supported:
27 //
28 // - function:          (function rewriting)
29 //      + Source        (original name of the function)
30 //      + Target        (explicit transformation)
31 //      + Transform     (pattern transformation)
32 //      + Naked         (boolean, whether the function is undecorated)
33 // - global variable:   (external linkage global variable rewriting)
34 //      + Source        (original name of externally visible variable)
35 //      + Target        (explicit transformation)
36 //      + Transform     (pattern transformation)
37 // - global alias:      (global alias rewriting)
38 //      + Source        (original name of the aliased name)
39 //      + Target        (explicit transformation)
40 //      + Transform     (pattern transformation)
41 //
42 // Note that source and exactly one of [Target, Transform] must be provided
43 //
44 // New rewrite descriptors can be created.  Addding a new rewrite descriptor
45 // involves:
46 //
47 //  a) extended the rewrite descriptor kind enumeration
48 //     (<anonymous>::RewriteDescriptor::RewriteDescriptorType)
49 //  b) implementing the new descriptor
50 //     (c.f. <anonymous>::ExplicitRewriteFunctionDescriptor)
51 //  c) extending the rewrite map parser
52 //     (<anonymous>::RewriteMapParser::parseEntry)
53 //
54 //  Specify to rewrite the symbols using the `-rewrite-symbols` option, and
55 //  specify the map file to use for the rewriting via the `-rewrite-map-file`
56 //  option.
57 //
58 //===----------------------------------------------------------------------===//
59 
60 #define DEBUG_TYPE "symbol-rewriter"
61 #include "llvm/Transforms/Utils/SymbolRewriter.h"
62 #include "llvm/Pass.h"
63 #include "llvm/ADT/SmallString.h"
64 #include "llvm/IR/LegacyPassManager.h"
65 #include "llvm/Support/CommandLine.h"
66 #include "llvm/Support/Debug.h"
67 #include "llvm/Support/MemoryBuffer.h"
68 #include "llvm/Support/Regex.h"
69 #include "llvm/Support/SourceMgr.h"
70 #include "llvm/Support/YAMLParser.h"
71 #include "llvm/Support/raw_ostream.h"
72 
73 using namespace llvm;
74 using namespace SymbolRewriter;
75 
76 static cl::list<std::string> RewriteMapFiles("rewrite-map-file",
77                                              cl::desc("Symbol Rewrite Map"),
78                                              cl::value_desc("filename"));
79 
80 static void rewriteComdat(Module &M, GlobalObject *GO,
81                           const std::string &Source,
82                           const std::string &Target) {
83   if (Comdat *CD = GO->getComdat()) {
84     auto &Comdats = M.getComdatSymbolTable();
85 
86     Comdat *C = M.getOrInsertComdat(Target);
87     C->setSelectionKind(CD->getSelectionKind());
88     GO->setComdat(C);
89 
90     Comdats.erase(Comdats.find(Source));
91   }
92 }
93 
94 namespace {
95 template <RewriteDescriptor::Type DT, typename ValueType,
96           ValueType *(llvm::Module::*Get)(StringRef) const>
97 class ExplicitRewriteDescriptor : public RewriteDescriptor {
98 public:
99   const std::string Source;
100   const std::string Target;
101 
102   ExplicitRewriteDescriptor(StringRef S, StringRef T, const bool Naked)
103       : RewriteDescriptor(DT), Source(Naked ? StringRef("\01" + S.str()) : S),
104         Target(T) {}
105 
106   bool performOnModule(Module &M) override;
107 
108   static bool classof(const RewriteDescriptor *RD) {
109     return RD->getType() == DT;
110   }
111 };
112 
113 template <RewriteDescriptor::Type DT, typename ValueType,
114           ValueType *(llvm::Module::*Get)(StringRef) const>
115 bool ExplicitRewriteDescriptor<DT, ValueType, Get>::performOnModule(Module &M) {
116   bool Changed = false;
117   if (ValueType *S = (M.*Get)(Source)) {
118     if (GlobalObject *GO = dyn_cast<GlobalObject>(S))
119       rewriteComdat(M, GO, Source, Target);
120 
121     if (Value *T = (M.*Get)(Target))
122       S->setValueName(T->getValueName());
123     else
124       S->setName(Target);
125 
126     Changed = true;
127   }
128   return Changed;
129 }
130 
131 template <RewriteDescriptor::Type DT, typename ValueType,
132           ValueType *(llvm::Module::*Get)(StringRef) const,
133           iterator_range<typename iplist<ValueType>::iterator>
134           (llvm::Module::*Iterator)()>
135 class PatternRewriteDescriptor : public RewriteDescriptor {
136 public:
137   const std::string Pattern;
138   const std::string Transform;
139 
140   PatternRewriteDescriptor(StringRef P, StringRef T)
141     : RewriteDescriptor(DT), Pattern(P), Transform(T) { }
142 
143   bool performOnModule(Module &M) override;
144 
145   static bool classof(const RewriteDescriptor *RD) {
146     return RD->getType() == DT;
147   }
148 };
149 
150 template <RewriteDescriptor::Type DT, typename ValueType,
151           ValueType *(llvm::Module::*Get)(StringRef) const,
152           iterator_range<typename iplist<ValueType>::iterator>
153           (llvm::Module::*Iterator)()>
154 bool PatternRewriteDescriptor<DT, ValueType, Get, Iterator>::
155 performOnModule(Module &M) {
156   bool Changed = false;
157   for (auto &C : (M.*Iterator)()) {
158     std::string Error;
159 
160     std::string Name = Regex(Pattern).sub(Transform, C.getName(), &Error);
161     if (!Error.empty())
162       report_fatal_error("unable to transforn " + C.getName() + " in " +
163                          M.getModuleIdentifier() + ": " + Error);
164 
165     if (C.getName() == Name)
166       continue;
167 
168     if (GlobalObject *GO = dyn_cast<GlobalObject>(&C))
169       rewriteComdat(M, GO, C.getName(), Name);
170 
171     if (Value *V = (M.*Get)(Name))
172       C.setValueName(V->getValueName());
173     else
174       C.setName(Name);
175 
176     Changed = true;
177   }
178   return Changed;
179 }
180 
181 /// Represents a rewrite for an explicitly named (function) symbol.  Both the
182 /// source function name and target function name of the transformation are
183 /// explicitly spelt out.
184 typedef ExplicitRewriteDescriptor<RewriteDescriptor::Type::Function,
185                                   llvm::Function, &llvm::Module::getFunction>
186     ExplicitRewriteFunctionDescriptor;
187 
188 /// Represents a rewrite for an explicitly named (global variable) symbol.  Both
189 /// the source variable name and target variable name are spelt out.  This
190 /// applies only to module level variables.
191 typedef ExplicitRewriteDescriptor<RewriteDescriptor::Type::GlobalVariable,
192                                   llvm::GlobalVariable,
193                                   &llvm::Module::getGlobalVariable>
194     ExplicitRewriteGlobalVariableDescriptor;
195 
196 /// Represents a rewrite for an explicitly named global alias.  Both the source
197 /// and target name are explicitly spelt out.
198 typedef ExplicitRewriteDescriptor<RewriteDescriptor::Type::NamedAlias,
199                                   llvm::GlobalAlias,
200                                   &llvm::Module::getNamedAlias>
201     ExplicitRewriteNamedAliasDescriptor;
202 
203 /// Represents a rewrite for a regular expression based pattern for functions.
204 /// A pattern for the function name is provided and a transformation for that
205 /// pattern to determine the target function name create the rewrite rule.
206 typedef PatternRewriteDescriptor<RewriteDescriptor::Type::Function,
207                                  llvm::Function, &llvm::Module::getFunction,
208                                  &llvm::Module::functions>
209     PatternRewriteFunctionDescriptor;
210 
211 /// Represents a rewrite for a global variable based upon a matching pattern.
212 /// Each global variable matching the provided pattern will be transformed as
213 /// described in the transformation pattern for the target.  Applies only to
214 /// module level variables.
215 typedef PatternRewriteDescriptor<RewriteDescriptor::Type::GlobalVariable,
216                                  llvm::GlobalVariable,
217                                  &llvm::Module::getGlobalVariable,
218                                  &llvm::Module::globals>
219     PatternRewriteGlobalVariableDescriptor;
220 
221 /// PatternRewriteNamedAliasDescriptor - represents a rewrite for global
222 /// aliases which match a given pattern.  The provided transformation will be
223 /// applied to each of the matching names.
224 typedef PatternRewriteDescriptor<RewriteDescriptor::Type::NamedAlias,
225                                  llvm::GlobalAlias,
226                                  &llvm::Module::getNamedAlias,
227                                  &llvm::Module::aliases>
228     PatternRewriteNamedAliasDescriptor;
229 } // namespace
230 
231 bool RewriteMapParser::parse(const std::string &MapFile,
232                              RewriteDescriptorList *DL) {
233   ErrorOr<std::unique_ptr<MemoryBuffer>> Mapping =
234       MemoryBuffer::getFile(MapFile);
235 
236   if (!Mapping)
237     report_fatal_error("unable to read rewrite map '" + MapFile + "': " +
238                        Mapping.getError().message());
239 
240   if (!parse(*Mapping, DL))
241     report_fatal_error("unable to parse rewrite map '" + MapFile + "'");
242 
243   return true;
244 }
245 
246 bool RewriteMapParser::parse(std::unique_ptr<MemoryBuffer> &MapFile,
247                              RewriteDescriptorList *DL) {
248   SourceMgr SM;
249   yaml::Stream YS(MapFile->getBuffer(), SM);
250 
251   for (auto &Document : YS) {
252     yaml::MappingNode *DescriptorList;
253 
254     // ignore empty documents
255     if (isa<yaml::NullNode>(Document.getRoot()))
256       continue;
257 
258     DescriptorList = dyn_cast<yaml::MappingNode>(Document.getRoot());
259     if (!DescriptorList) {
260       YS.printError(Document.getRoot(), "DescriptorList node must be a map");
261       return false;
262     }
263 
264     for (auto &Descriptor : *DescriptorList)
265       if (!parseEntry(YS, Descriptor, DL))
266         return false;
267   }
268 
269   return true;
270 }
271 
272 bool RewriteMapParser::parseEntry(yaml::Stream &YS, yaml::KeyValueNode &Entry,
273                                   RewriteDescriptorList *DL) {
274   yaml::ScalarNode *Key;
275   yaml::MappingNode *Value;
276   SmallString<32> KeyStorage;
277   StringRef RewriteType;
278 
279   Key = dyn_cast<yaml::ScalarNode>(Entry.getKey());
280   if (!Key) {
281     YS.printError(Entry.getKey(), "rewrite type must be a scalar");
282     return false;
283   }
284 
285   Value = dyn_cast<yaml::MappingNode>(Entry.getValue());
286   if (!Value) {
287     YS.printError(Entry.getValue(), "rewrite descriptor must be a map");
288     return false;
289   }
290 
291   RewriteType = Key->getValue(KeyStorage);
292   if (RewriteType.equals("function"))
293     return parseRewriteFunctionDescriptor(YS, Key, Value, DL);
294   else if (RewriteType.equals("global variable"))
295     return parseRewriteGlobalVariableDescriptor(YS, Key, Value, DL);
296   else if (RewriteType.equals("global alias"))
297     return parseRewriteGlobalAliasDescriptor(YS, Key, Value, DL);
298 
299   YS.printError(Entry.getKey(), "unknown rewrite type");
300   return false;
301 }
302 
303 bool RewriteMapParser::
304 parseRewriteFunctionDescriptor(yaml::Stream &YS, yaml::ScalarNode *K,
305                                yaml::MappingNode *Descriptor,
306                                RewriteDescriptorList *DL) {
307   bool Naked = false;
308   std::string Source;
309   std::string Target;
310   std::string Transform;
311 
312   for (auto &Field : *Descriptor) {
313     yaml::ScalarNode *Key;
314     yaml::ScalarNode *Value;
315     SmallString<32> KeyStorage;
316     SmallString<32> ValueStorage;
317     StringRef KeyValue;
318 
319     Key = dyn_cast<yaml::ScalarNode>(Field.getKey());
320     if (!Key) {
321       YS.printError(Field.getKey(), "descriptor key must be a scalar");
322       return false;
323     }
324 
325     Value = dyn_cast<yaml::ScalarNode>(Field.getValue());
326     if (!Value) {
327       YS.printError(Field.getValue(), "descriptor value must be a scalar");
328       return false;
329     }
330 
331     KeyValue = Key->getValue(KeyStorage);
332     if (KeyValue.equals("source")) {
333       std::string Error;
334 
335       Source = Value->getValue(ValueStorage);
336       if (!Regex(Source).isValid(Error)) {
337         YS.printError(Field.getKey(), "invalid regex: " + Error);
338         return false;
339       }
340     } else if (KeyValue.equals("target")) {
341       Target = Value->getValue(ValueStorage);
342     } else if (KeyValue.equals("transform")) {
343       Transform = Value->getValue(ValueStorage);
344     } else if (KeyValue.equals("naked")) {
345       std::string Undecorated;
346 
347       Undecorated = Value->getValue(ValueStorage);
348       Naked = StringRef(Undecorated).lower() == "true" || Undecorated == "1";
349     } else {
350       YS.printError(Field.getKey(), "unknown key for function");
351       return false;
352     }
353   }
354 
355   if (Transform.empty() == Target.empty()) {
356     YS.printError(Descriptor,
357                   "exactly one of transform or target must be specified");
358     return false;
359   }
360 
361   // TODO see if there is a more elegant solution to selecting the rewrite
362   // descriptor type
363   if (!Target.empty())
364     DL->push_back(llvm::make_unique<ExplicitRewriteFunctionDescriptor>(
365         Source, Target, Naked));
366   else
367     DL->push_back(
368         llvm::make_unique<PatternRewriteFunctionDescriptor>(Source, Transform));
369 
370   return true;
371 }
372 
373 bool RewriteMapParser::
374 parseRewriteGlobalVariableDescriptor(yaml::Stream &YS, yaml::ScalarNode *K,
375                                      yaml::MappingNode *Descriptor,
376                                      RewriteDescriptorList *DL) {
377   std::string Source;
378   std::string Target;
379   std::string Transform;
380 
381   for (auto &Field : *Descriptor) {
382     yaml::ScalarNode *Key;
383     yaml::ScalarNode *Value;
384     SmallString<32> KeyStorage;
385     SmallString<32> ValueStorage;
386     StringRef KeyValue;
387 
388     Key = dyn_cast<yaml::ScalarNode>(Field.getKey());
389     if (!Key) {
390       YS.printError(Field.getKey(), "descriptor Key must be a scalar");
391       return false;
392     }
393 
394     Value = dyn_cast<yaml::ScalarNode>(Field.getValue());
395     if (!Value) {
396       YS.printError(Field.getValue(), "descriptor value must be a scalar");
397       return false;
398     }
399 
400     KeyValue = Key->getValue(KeyStorage);
401     if (KeyValue.equals("source")) {
402       std::string Error;
403 
404       Source = Value->getValue(ValueStorage);
405       if (!Regex(Source).isValid(Error)) {
406         YS.printError(Field.getKey(), "invalid regex: " + Error);
407         return false;
408       }
409     } else if (KeyValue.equals("target")) {
410       Target = Value->getValue(ValueStorage);
411     } else if (KeyValue.equals("transform")) {
412       Transform = Value->getValue(ValueStorage);
413     } else {
414       YS.printError(Field.getKey(), "unknown Key for Global Variable");
415       return false;
416     }
417   }
418 
419   if (Transform.empty() == Target.empty()) {
420     YS.printError(Descriptor,
421                   "exactly one of transform or target must be specified");
422     return false;
423   }
424 
425   if (!Target.empty())
426     DL->push_back(llvm::make_unique<ExplicitRewriteGlobalVariableDescriptor>(
427         Source, Target,
428         /*Naked*/ false));
429   else
430     DL->push_back(llvm::make_unique<PatternRewriteGlobalVariableDescriptor>(
431         Source, Transform));
432 
433   return true;
434 }
435 
436 bool RewriteMapParser::
437 parseRewriteGlobalAliasDescriptor(yaml::Stream &YS, yaml::ScalarNode *K,
438                                   yaml::MappingNode *Descriptor,
439                                   RewriteDescriptorList *DL) {
440   std::string Source;
441   std::string Target;
442   std::string Transform;
443 
444   for (auto &Field : *Descriptor) {
445     yaml::ScalarNode *Key;
446     yaml::ScalarNode *Value;
447     SmallString<32> KeyStorage;
448     SmallString<32> ValueStorage;
449     StringRef KeyValue;
450 
451     Key = dyn_cast<yaml::ScalarNode>(Field.getKey());
452     if (!Key) {
453       YS.printError(Field.getKey(), "descriptor key must be a scalar");
454       return false;
455     }
456 
457     Value = dyn_cast<yaml::ScalarNode>(Field.getValue());
458     if (!Value) {
459       YS.printError(Field.getValue(), "descriptor value must be a scalar");
460       return false;
461     }
462 
463     KeyValue = Key->getValue(KeyStorage);
464     if (KeyValue.equals("source")) {
465       std::string Error;
466 
467       Source = Value->getValue(ValueStorage);
468       if (!Regex(Source).isValid(Error)) {
469         YS.printError(Field.getKey(), "invalid regex: " + Error);
470         return false;
471       }
472     } else if (KeyValue.equals("target")) {
473       Target = Value->getValue(ValueStorage);
474     } else if (KeyValue.equals("transform")) {
475       Transform = Value->getValue(ValueStorage);
476     } else {
477       YS.printError(Field.getKey(), "unknown key for Global Alias");
478       return false;
479     }
480   }
481 
482   if (Transform.empty() == Target.empty()) {
483     YS.printError(Descriptor,
484                   "exactly one of transform or target must be specified");
485     return false;
486   }
487 
488   if (!Target.empty())
489     DL->push_back(llvm::make_unique<ExplicitRewriteNamedAliasDescriptor>(
490         Source, Target,
491         /*Naked*/ false));
492   else
493     DL->push_back(llvm::make_unique<PatternRewriteNamedAliasDescriptor>(
494         Source, Transform));
495 
496   return true;
497 }
498 
499 namespace {
500 class RewriteSymbolsLegacyPass : public ModulePass {
501 public:
502   static char ID; // Pass identification, replacement for typeid
503 
504   RewriteSymbolsLegacyPass();
505   RewriteSymbolsLegacyPass(SymbolRewriter::RewriteDescriptorList &DL);
506 
507   bool runOnModule(Module &M) override;
508 
509 private:
510   RewriteSymbolPass Impl;
511 };
512 
513 char RewriteSymbolsLegacyPass::ID = 0;
514 
515 RewriteSymbolsLegacyPass::RewriteSymbolsLegacyPass() : ModulePass(ID), Impl() {
516   initializeRewriteSymbolsLegacyPassPass(*PassRegistry::getPassRegistry());
517 }
518 
519 RewriteSymbolsLegacyPass::RewriteSymbolsLegacyPass(
520     SymbolRewriter::RewriteDescriptorList &DL)
521     : ModulePass(ID), Impl(DL) {}
522 
523 bool RewriteSymbolsLegacyPass::runOnModule(Module &M) {
524   return Impl.runImpl(M);
525 }
526 }
527 
528 namespace llvm {
529 PreservedAnalyses RewriteSymbolPass::run(Module &M, ModuleAnalysisManager &AM) {
530   if (!runImpl(M))
531     return PreservedAnalyses::all();
532 
533   return PreservedAnalyses::none();
534 }
535 
536 bool RewriteSymbolPass::runImpl(Module &M) {
537   bool Changed;
538 
539   Changed = false;
540   for (auto &Descriptor : Descriptors)
541     Changed |= Descriptor->performOnModule(M);
542 
543   return Changed;
544 }
545 
546 void RewriteSymbolPass::loadAndParseMapFiles() {
547   const std::vector<std::string> MapFiles(RewriteMapFiles);
548   SymbolRewriter::RewriteMapParser Parser;
549 
550   for (const auto &MapFile : MapFiles)
551     Parser.parse(MapFile, &Descriptors);
552 }
553 }
554 
555 INITIALIZE_PASS(RewriteSymbolsLegacyPass, "rewrite-symbols", "Rewrite Symbols",
556                 false, false)
557 
558 ModulePass *llvm::createRewriteSymbolsPass() {
559   return new RewriteSymbolsLegacyPass();
560 }
561 
562 ModulePass *
563 llvm::createRewriteSymbolsPass(SymbolRewriter::RewriteDescriptorList &DL) {
564   return new RewriteSymbolsLegacyPass(DL);
565 }
566