/*
- * Copyright (C) 2011 Apple Inc. All rights reserved.
+ * Copyright (C) 2011, 2014 Apple Inc. All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
#include "DFGAnalysis.h"
#include "DFGBasicBlock.h"
+#include "DFGBlockMap.h"
+#include "DFGBlockSet.h"
#include "DFGCommon.h"
-#include <wtf/FastBitVector.h>
namespace JSC { namespace DFG {
void compute(Graph&);
- bool dominates(BlockIndex from, BlockIndex to) const
+ bool strictlyDominates(BasicBlock* from, BasicBlock* to) const
{
ASSERT(isValid());
- return m_results[to].get(from);
+ return m_data[to].preNumber > m_data[from].preNumber
+ && m_data[to].postNumber < m_data[from].postNumber;
}
bool dominates(BasicBlock* from, BasicBlock* to) const
{
- return dominates(from->index, to->index);
+ return from == to || strictlyDominates(from, to);
}
- void dump(Graph&, PrintStream&) const;
+ BasicBlock* immediateDominatorOf(BasicBlock* block) const
+ {
+ return m_data[block].idomParent;
+ }
+
+ template<typename Functor>
+ void forAllStrictDominatorsOf(BasicBlock* to, const Functor& functor) const
+ {
+ for (BasicBlock* block = m_data[to].idomParent; block; block = m_data[block].idomParent)
+ functor(block);
+ }
+
+ template<typename Functor>
+ void forAllDominatorsOf(BasicBlock* to, const Functor& functor) const
+ {
+ for (BasicBlock* block = to; block; block = m_data[block].idomParent)
+ functor(block);
+ }
+
+ template<typename Functor>
+ void forAllBlocksStrictlyDominatedBy(BasicBlock* from, const Functor& functor) const
+ {
+ Vector<BasicBlock*, 16> worklist;
+ worklist.appendVector(m_data[from].idomKids);
+ while (!worklist.isEmpty()) {
+ BasicBlock* block = worklist.takeLast();
+ functor(block);
+ worklist.appendVector(m_data[block].idomKids);
+ }
+ }
+
+ template<typename Functor>
+ void forAllBlocksDominatedBy(BasicBlock* from, const Functor& functor) const
+ {
+ Vector<BasicBlock*, 16> worklist;
+ worklist.append(from);
+ while (!worklist.isEmpty()) {
+ BasicBlock* block = worklist.takeLast();
+ functor(block);
+ worklist.appendVector(m_data[block].idomKids);
+ }
+ }
+
+ BlockSet strictDominatorsOf(BasicBlock* to) const;
+ BlockSet dominatorsOf(BasicBlock* to) const;
+ BlockSet blocksStrictlyDominatedBy(BasicBlock* from) const;
+ BlockSet blocksDominatedBy(BasicBlock* from) const;
+
+ template<typename Functor>
+ void forAllBlocksInDominanceFrontierOf(
+ BasicBlock* from, const Functor& functor) const
+ {
+ BlockSet set;
+ forAllBlocksInDominanceFrontierOfImpl(
+ from,
+ [&] (BasicBlock* block) {
+ if (set.add(block))
+ functor(block);
+ });
+ }
+
+ BlockSet dominanceFrontierOf(BasicBlock* from) const;
+
+ template<typename Functor>
+ void forAllBlocksInIteratedDominanceFrontierOf(
+ const BlockList& from, const Functor& functor)
+ {
+ forAllBlocksInPrunedIteratedDominanceFrontierOf(
+ from,
+ [&] (BasicBlock* block) -> bool {
+ functor(block);
+ return true;
+ });
+ }
+
+ // This is a close relative of forAllBlocksInIteratedDominanceFrontierOf(), which allows the
+ // given functor to return false to indicate that we don't wish to consider the given block.
+ // Useful for computing pruned SSA form.
+ template<typename Functor>
+ void forAllBlocksInPrunedIteratedDominanceFrontierOf(
+ const BlockList& from, const Functor& functor)
+ {
+ BlockSet set;
+ forAllBlocksInIteratedDominanceFrontierOfImpl(
+ from,
+ [&] (BasicBlock* block) -> bool {
+ if (!set.add(block))
+ return false;
+ return functor(block);
+ });
+ }
+
+ BlockSet iteratedDominanceFrontierOf(const BlockList& from) const;
+
+ void dump(PrintStream&) const;
private:
- bool pruneDominators(Graph&, BlockIndex);
+ bool naiveDominates(BasicBlock* from, BasicBlock* to) const;
+
+ template<typename Functor>
+ void forAllBlocksInDominanceFrontierOfImpl(
+ BasicBlock* from, const Functor& functor) const
+ {
+ // Paraphrasing from http://en.wikipedia.org/wiki/Dominator_(graph_theory):
+ // "The dominance frontier of a block 'from' is the set of all blocks 'to' such that
+ // 'from' dominates an immediate predecessor of 'to', but 'from' does not strictly
+ // dominate 'to'."
+ //
+ // A useful corner case to remember: a block may be in its own dominance frontier if it has
+ // a loop edge to itself, since it dominates itself and so it dominates its own immediate
+ // predecessor, and a block never strictly dominates itself.
+
+ forAllBlocksDominatedBy(
+ from,
+ [&] (BasicBlock* block) {
+ for (unsigned successorIndex = block->numSuccessors(); successorIndex--;) {
+ BasicBlock* to = block->successor(successorIndex);
+ if (!strictlyDominates(from, to))
+ functor(to);
+ }
+ });
+ }
+
+ template<typename Functor>
+ void forAllBlocksInIteratedDominanceFrontierOfImpl(
+ const BlockList& from, const Functor& functor) const
+ {
+ BlockList worklist = from;
+ while (!worklist.isEmpty()) {
+ BasicBlock* block = worklist.takeLast();
+ forAllBlocksInDominanceFrontierOfImpl(
+ block,
+ [&] (BasicBlock* otherBlock) {
+ if (functor(otherBlock))
+ worklist.append(otherBlock);
+ });
+ }
+ }
+
+ struct BlockData {
+ BlockData()
+ : idomParent(nullptr)
+ , preNumber(UINT_MAX)
+ , postNumber(UINT_MAX)
+ {
+ }
+
+ Vector<BasicBlock*> idomKids;
+ BasicBlock* idomParent;
+
+ unsigned preNumber;
+ unsigned postNumber;
+ };
- Vector<FastBitVector> m_results; // For each block, the bitvector of blocks that dominate it.
- FastBitVector m_scratch; // A temporary bitvector with bit for each block. We recycle this to save new/deletes.
+ BlockMap<BlockData> m_data;
};
} } // namespace JSC::DFG
projects / apple / javascriptcore.git / blobdiff