Index: lib/Bitcode/NaCl/Analysis/AbbrevTrieNode.cpp |
diff --git a/lib/Bitcode/NaCl/Analysis/AbbrevTrieNode.cpp b/lib/Bitcode/NaCl/Analysis/AbbrevTrieNode.cpp |
new file mode 100644 |
index 0000000000000000000000000000000000000000..7ff3e36fea48de6d633ca95821f1b04a98596598 |
--- /dev/null |
+++ b/lib/Bitcode/NaCl/Analysis/AbbrevTrieNode.cpp |
@@ -0,0 +1,295 @@ |
+//===- AbbrevTrieNode.cpp ------------------------------------------------===// |
+// Implements abbreviation lookup tries. |
+// |
+// The LLVM Compiler Infrastructure |
+// |
+// This file is distributed under the University of Illinois Open Source |
+// License. See LICENSE.TXT for details. |
+// |
+//===----------------------------------------------------------------------===// |
+ |
+#include "llvm/Bitcode/NaCl/AbbrevTrieNode.h" |
+#include "llvm/Bitcode/NaCl/NaClBitcodeValueDist.h" |
+ |
+using namespace llvm; |
+ |
+void AbbrevTrieNode::GetSuccessorLabels(SuccessorLabels &Labels) const { |
+ for (SuccessorMap::const_iterator |
+ IndexIter = Successors.begin(), IndexIterEnd = Successors.end(); |
+ IndexIter != IndexIterEnd; ++IndexIter) { |
+ if (const SuccessorValueMap *ValueMap = IndexIter->second) { |
+ for (SuccessorValueMap::const_iterator |
+ ValueIter = ValueMap->begin(), ValueIterEnd = ValueMap->end(); |
+ ValueIter != ValueIterEnd; ++ValueIter) { |
+ Labels.push_back(std::pair<size_t, uint64_t>(IndexIter->first, |
+ ValueIter->first)); |
+ } |
+ } |
+ } |
+} |
+ |
+AbbrevTrieNode::~AbbrevTrieNode() { |
+ for (SuccessorMap::const_iterator |
+ Iter = Successors.begin(), IterEnd = Successors.end(); |
+ Iter != IterEnd; ++Iter) { |
+ if (const SuccessorValueMap *ValueMap = Iter->second) { |
+ for (SuccessorValueMap::const_iterator |
+ Iter = ValueMap->begin(), IterEnd = ValueMap->end(); |
+ Iter != IterEnd; ++Iter) { |
+ delete Iter->second; |
+ } |
+ delete ValueMap; |
+ } |
+ } |
+} |
+ |
+void AbbrevTrieNode::Print(raw_ostream &Stream, |
+ const std::string &Indent, |
+ bool LocalOnly) const { |
+ std::string IndentPlus(Indent); |
+ IndentPlus.append(" "); |
+ std::string IndentPlusPlus(IndentPlus); |
+ IndentPlusPlus.append(" "); |
+ if (! Abbreviations.empty()) { |
+ Stream << Indent << "Abbreviations:\n"; |
+ for (std::set<AbbrevIndexPair>::const_iterator |
+ Iter = Abbreviations.begin(), IterEnd = Abbreviations.end(); |
+ Iter != IterEnd; ++Iter) { |
+ Stream << IndentPlus; |
+ Iter->second->Print(Stream, /* AddNewline= */ false); |
+ Stream << " (abbrev #" << Iter->first << ")\n"; |
+ } |
+ } |
+ if (LocalOnly) return; |
+ if (!Successors.empty()) { |
+ Stream << Indent << "Successor Map:\n"; |
+ SuccessorLabels Labels; |
+ GetSuccessorLabels(Labels); |
+ for (SuccessorLabels::const_iterator |
+ Iter = Labels.begin(), IterEnd = Labels.end(); |
+ Iter != IterEnd; ++Iter) { |
+ size_t Index = Iter->first; |
+ if (Index == 0) { |
+ Stream << IndentPlus << "Record.Code = " << Iter->second << "\n"; |
+ } else { |
+ Stream << IndentPlus << "Record.Values[" << (Index-1) |
+ << "] = " << Iter->second << "\n"; |
+ } |
+ GetSuccessor(Iter->first, Iter->second)->Print(Stream, IndentPlusPlus); |
+ } |
+ } |
+} |
+ |
+AbbrevTrieNode *AbbrevTrieNode:: |
+GetSuccessor(size_t Index, uint64_t Value) const { |
+ SuccessorMap::const_iterator IndexPos = Successors.find(Index); |
+ if (IndexPos != Successors.end()) { |
+ if (SuccessorValueMap *ValueMap = IndexPos->second) { |
+ SuccessorValueMap::iterator ValuePos = ValueMap->find(Value); |
+ if (ValuePos != ValueMap->end()) |
+ return ValuePos->second; |
+ } |
+ } |
+ return 0; |
+} |
+ |
+bool AbbrevTrieNode::Add(NaClBitCodeAbbrev *Abbrev, |
+ size_t Index, size_t SkipIndex) { |
+ if (Index >= Abbrev->getNumOperandInfos()) return false; |
+ bool AddedNodes = false; |
+ |
+ // Skip over matches that may match because they don't have constants |
+ // in the index. |
+ while (SkipIndex < Index) { |
+ SuccessorMap::iterator Pos = Successors.find(SkipIndex); |
+ if (Pos != Successors.end()) { |
+ SuccessorValueMap *ValueMap = Pos->second; |
+ for (SuccessorValueMap::const_iterator |
+ Iter = ValueMap->begin(), IterEnd = ValueMap->end(); |
+ Iter != IterEnd; ++Iter) { |
+ if (AbbrevTrieNode *Successor = Iter->second) { |
+ if (Successor->Add(Abbrev, Index, SkipIndex+1)) |
+ AddedNodes = true; |
+ } |
+ } |
+ } |
+ ++SkipIndex; |
+ } |
+ |
+ // Now update successors for next matching constant in abbreviation. |
+ for (; Index < Abbrev->GetMinRecordSize(); ++Index) { |
+ const NaClBitCodeAbbrevOp &Op = Abbrev->getOperandInfo(Index); |
+ if (Op.isLiteral()) { |
+ if (Index == SkipIndex) { |
+ // No preceeding nodes to match, add here. |
+ SuccessorValueMap *ValueMap = Successors[Index]; |
+ if (ValueMap == 0) { |
+ ValueMap = new SuccessorValueMap(); |
+ Successors[Index] = ValueMap; |
+ } |
+ AbbrevTrieNode *Successor = (*ValueMap)[Op.getValue()]; |
+ if (Successor == 0) { |
+ Successor = new AbbrevTrieNode(); |
+ AddedNodes = true; |
+ (*ValueMap)[Op.getValue()] = Successor; |
+ } |
+ if (Successor->Add(Abbrev, Index+1, Index+1)) |
+ AddedNodes = true; |
+ } else { |
+ // Need to match all possible prefixes before inserting constant. |
+ if (Add(Abbrev, Index, SkipIndex)) |
+ AddedNodes = true; |
+ } |
+ return AddedNodes; |
+ } |
+ } |
+ return AddedNodes; |
+} |
+ |
+void AbbrevTrieNode::Insert(AbbrevIndexPair &AbbrevPair) { |
+ NaClBitCodeAbbrev *Abbrev = AbbrevPair.second; |
+ |
+ for (std::map<size_t, SuccessorValueMap*>::iterator |
+ Iter = Successors.begin(), IterEnd = Successors.end(); |
+ Iter != IterEnd; ++Iter) { |
+ if (SuccessorValueMap *ValueMap = Iter->second) { |
+ if (Iter->first < Abbrev->GetMinRecordSize()) { |
+ const NaClBitCodeAbbrevOp &Op = |
+ Abbrev->getOperandInfo(Iter->first); |
+ if (Op.isLiteral()) { |
+ uint64_t Value = Op.getValue(); |
+ SuccessorValueMap::iterator Pos = ValueMap->find(Value); |
+ if (Pos != ValueMap->end()) { |
+ if (AbbrevTrieNode *Next = Pos->second) { |
+ // Found constant that will be followed, update subgraph |
+ // and quit. |
+ Next->Insert(AbbrevPair); |
+ return; |
+ } |
+ } |
+ } else { |
+ // Not literal, so it may (or may not) be followed, depending |
+ // on the value in the record that will be matched against. So |
+ // add to subgraph, and here if no succeeding matching literal |
+ // constants. |
+ for (SuccessorValueMap::iterator |
+ Iter = ValueMap->begin(), IterEnd = ValueMap->end(); |
+ Iter != IterEnd; ++Iter) { |
+ if (AbbrevTrieNode *Next = Iter->second) |
+ Next->Insert(AbbrevPair); |
+ } |
+ } |
+ } else if (!Abbrev->IsFixedSize()) { |
+ // May match array element. So add to subgraph as well as here. |
+ for (SuccessorValueMap::iterator |
+ Iter = ValueMap->begin(), IterEnd = ValueMap->end(); |
+ Iter != IterEnd; ++Iter) { |
+ if (AbbrevTrieNode *Next = Iter->second) |
+ Next->Insert(AbbrevPair); |
+ } |
+ } |
+ } |
+ } |
+ |
+ // If reached, no guarantees that any edge was followed, so add |
+ // to matches of this node. |
+ Abbreviations.insert(AbbrevPair); |
+} |
+ |
+const AbbrevTrieNode *AbbrevTrieNode:: |
+MatchRecord(const NaClBitcodeRecordData &Record) const { |
+ for (std::map<size_t, SuccessorValueMap*>::const_iterator |
+ Iter = Successors.begin(), IterEnd = Successors.end(); |
+ Iter != IterEnd; ++Iter) { |
+ if (SuccessorValueMap *ValueMap = Iter->second) { |
+ if (Iter->first <= Record.Values.size()) { |
+ uint64_t Value; |
+ if (Iter->first == 0) |
+ Value = Record.Code; |
+ else |
+ Value = Record.Values[Iter->first-1]; |
+ SuccessorValueMap::iterator Pos = ValueMap->find(Value); |
+ if (Pos != ValueMap->end()) { |
+ if (AbbrevTrieNode *Next = Pos->second) { |
+ return Next->MatchRecord(Record); |
+ } |
+ } |
+ } else { |
+ // Map index too big, quit. |
+ break; |
+ } |
+ } |
+ } |
+ |
+ // If reached, no refinement found, use this node. |
+ return this; |
+} |
+ |
+static void ComputeAbbrevRange(NaClBitCodeAbbrev *Abbrev, |
+ size_t &MinIndex, size_t &MaxIndex) { |
+ // Find the range of record lengths for which the abbreviation may |
+ // apply. Note: To keep a limit on the number of copies, collapse all |
+ // records with length > NaClValueIndexCutoff into the same bucket. |
+ MinIndex = Abbrev->GetMinRecordSize(); |
+ if (MinIndex > NaClValueIndexCutoff) { |
+ MinIndex = NaClValueIndexCutoff + 1; |
+ } |
+ MaxIndex = MinIndex; |
+ if (!Abbrev->IsFixedSize()) { |
+ MaxIndex = NaClValueIndexCutoff + 1; |
+ } |
+} |
+ |
+// Once all nodes have been added (via calls to AddAbbrevToLookupMap), |
+// this function adds the given abbreviation pair to all possible |
+// matchxes in the lookup map. |
+static void AddAbbrevPairToLookupMap(AbbrevLookupSizeMap &LookupMap, |
+ AbbrevIndexPair &AbbrevPair) { |
+ size_t MinIndex, MaxIndex; |
+ ComputeAbbrevRange(AbbrevPair.second, MinIndex, MaxIndex); |
+ for (size_t Index = MinIndex; Index <= MaxIndex; ++Index) { |
+ AbbrevTrieNode *Node = LookupMap[Index]; |
+ assert(Node); |
+ Node->Insert(AbbrevPair); |
+ } |
+} |
+ |
+// Adds the given abbreviation to the corresponding lookup map, constructing |
+// the map of usable lookup tries. |
+static bool AddAbbrevToLookupMap(AbbrevLookupSizeMap &LookupMap, |
+ NaClBitCodeAbbrev *Abbrev) { |
+ bool Added = false; |
+ size_t MinIndex, MaxIndex; |
+ ComputeAbbrevRange(Abbrev, MinIndex, MaxIndex); |
+ for (size_t Index = MinIndex; Index <= MaxIndex; ++Index) { |
+ AbbrevTrieNode *Node = LookupMap[Index]; |
+ if (Node == 0) { |
+ Node = new AbbrevTrieNode(); |
+ LookupMap[Index] = Node; |
+ Added = true; |
+ } |
+ if (Node->Add(Abbrev)) Added = true; |
+ } |
+ return Added; |
+} |
+ |
+void llvm::NaClBuildAbbrevLookupMap( |
+ AbbrevLookupSizeMap &LookupMap, |
+ const SmallVectorImpl<NaClBitCodeAbbrev*> &Abbrevs, |
+ size_t InitialIndex) { |
+ // First build nodes of trie. |
+ bool FixpointFound = false; |
+ while (!FixpointFound) { |
+ FixpointFound = true; |
+ for (size_t i = InitialIndex; i < Abbrevs.size(); ++i) { |
+ if (AddAbbrevToLookupMap(LookupMap, Abbrevs[i])) |
+ FixpointFound = false; |
+ } |
+ } |
+ |
+ // Now populate with abbreviations that apply. |
+ for (size_t i = InitialIndex; i < Abbrevs.size(); ++i) { |
+ AbbrevIndexPair Pair(i, Abbrevs[i]); |
+ AddAbbrevPairToLookupMap(LookupMap, Pair); |
+ } |
+} |