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