Subversion Repositories QNX 8.QNX8 LLVM/Clang compiler suite

//===- llvm/Analysis/DominanceFrontier.h - Dominator Frontiers --*- C++ -*-===//

//

// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.

// See https://llvm.org/LICENSE.txt for license information.

// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception

//

//===----------------------------------------------------------------------===//

//

// This is the generic implementation of the DominanceFrontier class, which

// calculate and holds the dominance frontier for a function for.

//

// This should be considered deprecated, don't add any more uses of this data

// structure.

//

//===----------------------------------------------------------------------===//

#ifndef LLVM_ANALYSIS_DOMINANCEFRONTIERIMPL_H

#define LLVM_ANALYSIS_DOMINANCEFRONTIERIMPL_H

#include "llvm/ADT/SmallPtrSet.h"

#include "llvm/Analysis/DominanceFrontier.h"

#include "llvm/Config/llvm-config.h"

#include "llvm/Support/Debug.h"

#include "llvm/Support/GenericDomTree.h"

#include "llvm/Support/raw_ostream.h"

#include <cassert>

#include <set>

#include <utility>

#include <vector>

namespace llvm {

template <class BlockT>

class DFCalculateWorkObject {

public:

  using DomTreeNodeT = DomTreeNodeBase<BlockT>;

  DFCalculateWorkObject(BlockT *B, BlockT *P, const DomTreeNodeT *N,

                        const DomTreeNodeT *PN)

      : currentBB(B), parentBB(P), Node(N), parentNode(PN) {}

  BlockT *currentBB;

  BlockT *parentBB;

  const DomTreeNodeT *Node;

  const DomTreeNodeT *parentNode;

};

template <class BlockT, bool IsPostDom>

void DominanceFrontierBase<BlockT, IsPostDom>::removeBlock(BlockT *BB) {

  assert(find(BB) != end() && "Block is not in DominanceFrontier!");

  for (iterator I = begin(), E = end(); I != E; ++I)

    I->second.erase(BB);

  Frontiers.erase(BB);

}

template <class BlockT, bool IsPostDom>

void DominanceFrontierBase<BlockT, IsPostDom>::addToFrontier(iterator I,

                                                             BlockT *Node) {

  assert(I != end() && "BB is not in DominanceFrontier!");

  assert(I->second.count(Node) && "Node is not in DominanceFrontier of BB");

  I->second.erase(Node);

}

template <class BlockT, bool IsPostDom>

void DominanceFrontierBase<BlockT, IsPostDom>::removeFromFrontier(

    iterator I, BlockT *Node) {

  assert(I != end() && "BB is not in DominanceFrontier!");

  assert(I->second.count(Node) && "Node is not in DominanceFrontier of BB");

  I->second.erase(Node);

}

template <class BlockT, bool IsPostDom>

bool DominanceFrontierBase<BlockT, IsPostDom>::compareDomSet(

    DomSetType &DS1, const DomSetType &DS2) const {

  std::set<BlockT *> tmpSet;

  for (BlockT *BB : DS2)

    tmpSet.insert(BB);

  for (typename DomSetType::const_iterator I = DS1.begin(), E = DS1.end();

       I != E;) {

    BlockT *Node = *I++;

    if (tmpSet.erase(Node) == 0)

      // Node is in DS1 but tnot in DS2.

      return true;

  }

  if (!tmpSet.empty()) {

    // There are nodes that are in DS2 but not in DS1.

    return true;

  }

  // DS1 and DS2 matches.

  return false;

}

template <class BlockT, bool IsPostDom>

bool DominanceFrontierBase<BlockT, IsPostDom>::compare(

    DominanceFrontierBase<BlockT, IsPostDom> &Other) const {

  DomSetMapType tmpFrontiers;

  for (typename DomSetMapType::const_iterator I = Other.begin(),

                                              E = Other.end();

       I != E; ++I)

    tmpFrontiers.insert(std::make_pair(I->first, I->second));

  for (typename DomSetMapType::iterator I = tmpFrontiers.begin(),

                                        E = tmpFrontiers.end();

       I != E;) {

    BlockT *Node = I->first;

    const_iterator DFI = find(Node);

    if (DFI == end())

      return true;

    if (compareDomSet(I->second, DFI->second))

      return true;

    ++I;

    tmpFrontiers.erase(Node);

  }

  if (!tmpFrontiers.empty())

    return true;

  return false;

}

template <class BlockT, bool IsPostDom>

void DominanceFrontierBase<BlockT, IsPostDom>::print(raw_ostream &OS) const {

  for (const_iterator I = begin(), E = end(); I != E; ++I) {

    OS << "  DomFrontier for BB ";

    if (I->first)

      I->first->printAsOperand(OS, false);

    else

      OS << " <<exit node>>";

    OS << " is:\t";

    const std::set<BlockT *> &BBs = I->second;

    for (const BlockT *BB : BBs) {

      OS << ' ';

      if (BB)

        BB->printAsOperand(OS, false);

      else

        OS << "<<exit node>>";

    }

    OS << '\n';

  }

}

#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)

template <class BlockT, bool IsPostDom>

void DominanceFrontierBase<BlockT, IsPostDom>::dump() const {

  print(dbgs());

}

#endif

template <class BlockT>

const typename ForwardDominanceFrontierBase<BlockT>::DomSetType &

ForwardDominanceFrontierBase<BlockT>::calculate(const DomTreeT &DT,

                                                const DomTreeNodeT *Node) {

  BlockT *BB = Node->getBlock();

  DomSetType *Result = nullptr;

  std::vector<DFCalculateWorkObject<BlockT>> workList;

  SmallPtrSet<BlockT *, 32> visited;

  workList.push_back(DFCalculateWorkObject<BlockT>(BB, nullptr, Node, nullptr));

  do {

    DFCalculateWorkObject<BlockT> *currentW = &workList.back();

    assert(currentW && "Missing work object.");

    BlockT *currentBB = currentW->currentBB;

    BlockT *parentBB = currentW->parentBB;

    const DomTreeNodeT *currentNode = currentW->Node;

    const DomTreeNodeT *parentNode = currentW->parentNode;

    assert(currentBB && "Invalid work object. Missing current Basic Block");

    assert(currentNode && "Invalid work object. Missing current Node");

    DomSetType &S = this->Frontiers[currentBB];

    // Visit each block only once.

    if (visited.insert(currentBB).second) {

      // Loop over CFG successors to calculate DFlocal[currentNode]

      for (const auto Succ : children<BlockT *>(currentBB)) {

        // Does Node immediately dominate this successor?

        if (DT[Succ]->getIDom() != currentNode)

          S.insert(Succ);

      }

    }

    // At this point, S is DFlocal.  Now we union in DFup's of our children...

    // Loop through and visit the nodes that Node immediately dominates (Node's

    // children in the IDomTree)

    bool visitChild = false;

    for (typename DomTreeNodeT::const_iterator NI = currentNode->begin(),

                                               NE = currentNode->end();

         NI != NE; ++NI) {

      DomTreeNodeT *IDominee = *NI;

      BlockT *childBB = IDominee->getBlock();

      if (visited.count(childBB) == 0) {

        workList.push_back(DFCalculateWorkObject<BlockT>(

            childBB, currentBB, IDominee, currentNode));

        visitChild = true;

      }

    }

    // If all children are visited or there is any child then pop this block

    // from the workList.

    if (!visitChild) {

      if (!parentBB) {

        Result = &S;

        break;

      }

      typename DomSetType::const_iterator CDFI = S.begin(), CDFE = S.end();

      DomSetType &parentSet = this->Frontiers[parentBB];

      for (; CDFI != CDFE; ++CDFI) {

        if (!DT.properlyDominates(parentNode, DT[*CDFI]))

          parentSet.insert(*CDFI);

      }

      workList.pop_back();

    }

  } while (!workList.empty());

  return *Result;

}

} // end namespace llvm

#endif // LLVM_ANALYSIS_DOMINANCEFRONTIERIMPL_H