Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(20)

Unified Diff: include/llvm/Bitcode/NaCl/AbbrevTrieNode.h

Issue 939073008: Rebased PNaCl localmods in LLVM to 223109 (Closed)
Patch Set: undo localmod Created 5 years, 10 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View side-by-side diff with in-line comments
Download patch
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
« no previous file with comments | « include/llvm/Analysis/NaCl/PNaClAllowedIntrinsics.h ('k') | include/llvm/Bitcode/NaCl/NaClAnalyzerBlockDist.h » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698