Index: include/llvm/Bitcode/NaCl/AbbrevTrieNode.h |
diff --git a/include/llvm/Bitcode/NaCl/AbbrevTrieNode.h b/include/llvm/Bitcode/NaCl/AbbrevTrieNode.h |
new file mode 100644 |
index 0000000000000000000000000000000000000000..e3a6ee4ba88e45631479579170de9f8fd8a9a073 |
--- /dev/null |
+++ b/include/llvm/Bitcode/NaCl/AbbrevTrieNode.h |
@@ -0,0 +1,135 @@ |
+//===- AbbrevTrieNode.h - Abbreviation lookup tries ----*- C++ -*-===// |
+// |
+// The LLVM Compiler Infrastructure |
+// |
+// This file is distributed under the University of Illinois Open Source |
+// License. See LICENSE.TXT for details. |
+// |
+//===----------------------------------------------------------------------===// |
+// |
+// This header file defines class AbbrevTrieNode that implement abbreviation |
+// lookup tries. These tries reduce the set of abbreviations that need to |
+// be tested for best fit to a pnacl bitcode record, by sorting abbreviations |
+// on literal constants that may appear in the abbreviations. By doing this, |
+// we can reduce hundreds of possible abbreviations down to a small number |
+// of possibly applicable abbreviations. |
+// |
+// The tries separate abbreviations based on constant size, and constants |
+// that appear in the abbreviations. The trie is used to capture constants |
+// that appear at any index, and use these constants to decide if a trie |
+// node applies to the record. |
+// |
+//===----------------------------------------------------------------------===// |
+ |
+#ifndef LLVM_BITCODE_NACL_ABBREV_TRIE_NODE_H |
+#define LLVM_BITCODE_NACL_ABBREV_TRIE_NODE_H |
+ |
+#include "llvm/Bitcode/NaCl/NaClBitcodeParser.h" |
+#include <map> |
+#include <set> |
+ |
+namespace llvm { |
+ |
+// Models the association of an abbreviation index with the |
+// corresponding abbreviation associated with that index. |
+typedef std::pair<size_t, NaClBitCodeAbbrev*> AbbrevIndexPair; |
+ |
+// Models a trie of abbreviation matches that can be used to reduce |
+// the number of applicable abbreviations. This is done by moving |
+// abbreviations that require literals to appear in them, to be in |
+// successor nodes. Abbreviations without literals are stored |
+// in this node. |
+class AbbrevTrieNode { |
+ // For faster lookup, we could model the successor map as |
+ // std::map<std::pair<size_t, uint64_t>, AbbrevTrieNode*>. However, |
+ // we split up the pair into a nested map. This allows us to reduce |
+ // the size of the domain of the map considerably, as well as |
+ // avoiding much value (i.e. std::pair<size_t, uint64_t>) |
+ // copying. These modifications result in considerable better time |
+ // performance. |
+ // |
+ // We also do this representation because the trie is sparse, |
+ // with respect to where constants can appear. Hence, we don't |
+ // built a possible successor for all possible indicies, but only |
+ // for those that can contain constants in some abbreviation. |
+ typedef std::map<uint64_t, AbbrevTrieNode*> SuccessorValueMap; |
+ typedef std::map<size_t, SuccessorValueMap*> SuccessorMap; |
+ |
+public: |
+ // Models the list of successor labels defined for a node. |
+ typedef std::vector< std::pair<size_t, uint64_t> > SuccessorLabels; |
+ |
+ // Creates an entry node into the trie. |
+ AbbrevTrieNode() {} |
+ |
+ ~AbbrevTrieNode(); |
+ |
+ // Print out the trie to the given stream, indenting the given |
+ // amount. If LocalOnly is true, no successor information is |
+ // printed. |
+ void Print(raw_ostream &Stream, |
+ const std::string &Indent, |
+ bool LocalOnly=false) const; |
+ |
+ // Adds matching constants, defined in Abbreviation, to the trie. |
+ // Returns true if any nodes were added to the trie to add the given |
+ // abbreviation. Note: This method only creates nodes, Abbreviations |
+ // must be aded in a separate pass using method Insert. Note: If |
+ // you call NaClBuildAbbrevLookupMap, it will construct the |
+ // (complete) abbrevation trie, calling Add and Insert in the |
+ // appropriate order. |
+ bool Add(NaClBitCodeAbbrev *Abbrev) { |
+ return Add(Abbrev, 0, 0); |
+ } |
+ |
+ // Inserts the given abbreviation (pair) in all trie nodes that |
+ // might match the given abbreviation. Should not be called until |
+ // all trie nodes are built using Add. |
+ void Insert(AbbrevIndexPair &AbbrevPair); |
+ |
+ // Returns the successor trie node matching the given Index/Value pair. |
+ AbbrevTrieNode* GetSuccessor(size_t Index, uint64_t Value) const; |
+ |
+ // Collects the set of successor (edge) labels defined for the node. |
+ void GetSuccessorLabels(SuccessorLabels &labels) const; |
+ |
+ // Returns a trie node (in the trie) that defines all possible |
+ // abbreviations that may apply to the given record. |
+ const AbbrevTrieNode *MatchRecord(const NaClBitcodeRecordData &Record) const; |
+ |
+ // Returns the abbreviations associated with the node. |
+ const std::set<AbbrevIndexPair> &GetAbbreviations() const { |
+ return Abbreviations; |
+ } |
+ |
+private: |
+ // Adds matching constants, defined in Abbreviation, to the trie. |
+ // Returns true if any nodes were added to the trie to add the given |
+ // abbreviation. Index is the positition (within the abbreviation) |
+ // where search should begin for the next available |
+ // literal. SkipIndex is the smallest skipped index used to find the |
+ // next available literal. |
+ bool Add(NaClBitCodeAbbrev *Abbrev, |
+ size_t Index, |
+ size_t SkipIndex); |
+ |
+ // The set of possible successor trie nodes defined for this node. |
+ SuccessorMap Successors; |
+ |
+ // The set of abbreviations that apply if one can't match a pnacl |
+ // bitcode record against any of the successors. |
+ std::set<AbbrevIndexPair> Abbreviations; |
+}; |
+ |
+// A map from record sizes, to the corresponding trie one should use |
+// to find abbreviations for records of that size. |
+typedef std::map<size_t, AbbrevTrieNode*> AbbrevLookupSizeMap; |
+ |
+// Builds abbreviation lookup trie for abbreviations |
+void NaClBuildAbbrevLookupMap(AbbrevLookupSizeMap &LookupMap, |
+ const SmallVectorImpl<NaClBitCodeAbbrev*> &Abbrevs, |
+ size_t InitialIndex = 0); |
+ |
+} |
+ |
+#endif |