+ void computeSemiDominatorsAndImplicitImmediateDominators()
+ {
+ for (unsigned currentPreNumber = m_blockByPreNumber.size(); currentPreNumber-- > 1;) {
+ BasicBlock* block = m_blockByPreNumber[currentPreNumber];
+ BlockData& blockData = m_data[block];
+
+ // Step 2:
+ for (BasicBlock* predecessorBlock : block->predecessors) {
+ BasicBlock* intermediateBlock = eval(predecessorBlock);
+ blockData.semiNumber = std::min(
+ m_data[intermediateBlock].semiNumber, blockData.semiNumber);
+ }
+ unsigned bucketPreNumber = blockData.semiNumber;
+ ASSERT(bucketPreNumber <= currentPreNumber);
+ m_data[m_blockByPreNumber[bucketPreNumber]].bucket.append(block);
+ link(blockData.parent, block);
+
+ // Step 3:
+ for (BasicBlock* semiDominee : m_data[blockData.parent].bucket) {
+ BasicBlock* possibleDominator = eval(semiDominee);
+ BlockData& semiDomineeData = m_data[semiDominee];
+ ASSERT(m_blockByPreNumber[semiDomineeData.semiNumber] == blockData.parent);
+ BlockData& possibleDominatorData = m_data[possibleDominator];
+ if (possibleDominatorData.semiNumber < semiDomineeData.semiNumber)
+ semiDomineeData.dom = possibleDominator;
+ else
+ semiDomineeData.dom = blockData.parent;
+ }
+ m_data[blockData.parent].bucket.clear();
+ }
+ }
+
+ void computeExplicitImmediateDominators()
+ {
+ for (unsigned currentPreNumber = 1; currentPreNumber < m_blockByPreNumber.size(); ++currentPreNumber) {
+ BasicBlock* block = m_blockByPreNumber[currentPreNumber];
+ BlockData& blockData = m_data[block];
+
+ if (blockData.dom != m_blockByPreNumber[blockData.semiNumber])
+ blockData.dom = m_data[blockData.dom].dom;
+ }
+ }
+
+ void link(BasicBlock* from, BasicBlock* to)
+ {
+ m_data[to].ancestor = from;
+ }
+
+ BasicBlock* eval(BasicBlock* block)
+ {
+ if (!m_data[block].ancestor)
+ return block;
+
+ compress(block);
+ return m_data[block].label;
+ }
+
+ void compress(BasicBlock* initialBlock)
+ {
+ // This was meant to be a recursive function, but we don't like recursion because we don't
+ // want to blow the stack. The original function will call compress() recursively on the
+ // ancestor of anything that has an ancestor. So, we populate our worklist with the
+ // recursive ancestors of initialBlock. Then we process the list starting from the block
+ // that is furthest up the ancestor chain.
+
+ BasicBlock* ancestor = m_data[initialBlock].ancestor;
+ ASSERT(ancestor);
+ if (!m_data[ancestor].ancestor)
+ return;
+
+ Vector<BasicBlock*, 16> stack;
+ for (BasicBlock* block = initialBlock; block; block = m_data[block].ancestor)
+ stack.append(block);
+
+ // We only care about blocks that have an ancestor that has an ancestor. The last two
+ // elements in the stack won't satisfy this property.
+ ASSERT(stack.size() >= 2);
+ ASSERT(!m_data[stack[stack.size() - 1]].ancestor);
+ ASSERT(!m_data[m_data[stack[stack.size() - 2]].ancestor].ancestor);
+
+ for (unsigned i = stack.size() - 2; i--;) {
+ BasicBlock* block = stack[i];
+ BasicBlock*& labelOfBlock = m_data[block].label;
+ BasicBlock*& ancestorOfBlock = m_data[block].ancestor;
+ ASSERT(ancestorOfBlock);
+ ASSERT(m_data[ancestorOfBlock].ancestor);
+
+ BasicBlock* labelOfAncestorOfBlock = m_data[ancestorOfBlock].label;
+
+ if (m_data[labelOfAncestorOfBlock].semiNumber < m_data[labelOfBlock].semiNumber)
+ labelOfBlock = labelOfAncestorOfBlock;
+ ancestorOfBlock = m_data[ancestorOfBlock].ancestor;
+ }