Line data    Source code

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