Subversion Repositories QNX 8.QNX8 LLVM/Clang compiler suite

Rev

Blame | Last modification | View Log | Download | RSS feed

  1. //===- CFGUpdate.h - Encode a CFG Edge Update. ------------------*- C++ -*-===//
  2. //
  3. // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
  4. // See https://llvm.org/LICENSE.txt for license information.
  5. // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
  6. //
  7. //===----------------------------------------------------------------------===//
  8. //
  9. // This file defines a CFG Edge Update: Insert or Delete, and two Nodes as the
  10. // Edge ends.
  11. //
  12. //===----------------------------------------------------------------------===//
  13.  
  14. #ifndef LLVM_SUPPORT_CFGUPDATE_H
  15. #define LLVM_SUPPORT_CFGUPDATE_H
  16.  
  17. #include "llvm/ADT/ArrayRef.h"
  18. #include "llvm/ADT/DenseMap.h"
  19. #include "llvm/ADT/PointerIntPair.h"
  20. #include "llvm/Support/Compiler.h"
  21. #include "llvm/Support/Debug.h"
  22. #include "llvm/Support/raw_ostream.h"
  23.  
  24. namespace llvm {
  25. namespace cfg {
  26. enum class UpdateKind : unsigned char { Insert, Delete };
  27.  
  28. template <typename NodePtr> class Update {
  29.   using NodeKindPair = PointerIntPair<NodePtr, 1, UpdateKind>;
  30.   NodePtr From;
  31.   NodeKindPair ToAndKind;
  32.  
  33. public:
  34.   Update(UpdateKind Kind, NodePtr From, NodePtr To)
  35.       : From(From), ToAndKind(To, Kind) {}
  36.  
  37.   UpdateKind getKind() const { return ToAndKind.getInt(); }
  38.   NodePtr getFrom() const { return From; }
  39.   NodePtr getTo() const { return ToAndKind.getPointer(); }
  40.   bool operator==(const Update &RHS) const {
  41.     return From == RHS.From && ToAndKind == RHS.ToAndKind;
  42.   }
  43.  
  44.   void print(raw_ostream &OS) const {
  45.     OS << (getKind() == UpdateKind::Insert ? "Insert " : "Delete ");
  46.     getFrom()->printAsOperand(OS, false);
  47.     OS << " -> ";
  48.     getTo()->printAsOperand(OS, false);
  49.   }
  50.  
  51. #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
  52.   LLVM_DUMP_METHOD void dump() const { print(dbgs()); }
  53. #endif
  54. };
  55.  
  56. // LegalizeUpdates function simplifies updates assuming a graph structure.
  57. // This function serves double purpose:
  58. // a) It removes redundant updates, which makes it easier to reverse-apply
  59. //    them when traversing CFG.
  60. // b) It optimizes away updates that cancel each other out, as the end result
  61. //    is the same.
  62. template <typename NodePtr>
  63. void LegalizeUpdates(ArrayRef<Update<NodePtr>> AllUpdates,
  64.                      SmallVectorImpl<Update<NodePtr>> &Result,
  65.                      bool InverseGraph, bool ReverseResultOrder = false) {
  66.   // Count the total number of inserions of each edge.
  67.   // Each insertion adds 1 and deletion subtracts 1. The end number should be
  68.   // one of {-1 (deletion), 0 (NOP), +1 (insertion)}. Otherwise, the sequence
  69.   // of updates contains multiple updates of the same kind and we assert for
  70.   // that case.
  71.   SmallDenseMap<std::pair<NodePtr, NodePtr>, int, 4> Operations;
  72.   Operations.reserve(AllUpdates.size());
  73.  
  74.   for (const auto &U : AllUpdates) {
  75.     NodePtr From = U.getFrom();
  76.     NodePtr To = U.getTo();
  77.     if (InverseGraph)
  78.       std::swap(From, To); // Reverse edge for postdominators.
  79.  
  80.     Operations[{From, To}] += (U.getKind() == UpdateKind::Insert ? 1 : -1);
  81.   }
  82.  
  83.   Result.clear();
  84.   Result.reserve(Operations.size());
  85.   for (auto &Op : Operations) {
  86.     const int NumInsertions = Op.second;
  87.     assert(std::abs(NumInsertions) <= 1 && "Unbalanced operations!");
  88.     if (NumInsertions == 0)
  89.       continue;
  90.     const UpdateKind UK =
  91.         NumInsertions > 0 ? UpdateKind::Insert : UpdateKind::Delete;
  92.     Result.push_back({UK, Op.first.first, Op.first.second});
  93.   }
  94.  
  95.   // Make the order consistent by not relying on pointer values within the
  96.   // set. Reuse the old Operations map.
  97.   // In the future, we should sort by something else to minimize the amount
  98.   // of work needed to perform the series of updates.
  99.   for (size_t i = 0, e = AllUpdates.size(); i != e; ++i) {
  100.     const auto &U = AllUpdates[i];
  101.     if (!InverseGraph)
  102.       Operations[{U.getFrom(), U.getTo()}] = int(i);
  103.     else
  104.       Operations[{U.getTo(), U.getFrom()}] = int(i);
  105.   }
  106.  
  107.   llvm::sort(Result, [&](const Update<NodePtr> &A, const Update<NodePtr> &B) {
  108.     const auto &OpA = Operations[{A.getFrom(), A.getTo()}];
  109.     const auto &OpB = Operations[{B.getFrom(), B.getTo()}];
  110.     return ReverseResultOrder ? OpA < OpB : OpA > OpB;
  111.   });
  112. }
  113.  
  114. } // end namespace cfg
  115. } // end namespace llvm
  116.  
  117. #endif // LLVM_SUPPORT_CFGUPDATE_H
  118.