+
+
+/* Compute dominance frontiers, ala Harvey, Ferrante, et al.
+
+ This algorithm can be found in Timothy Harvey's PhD thesis, at
+ http://www.cs.rice.edu/~harv/dissertation.pdf in the section on iterative
+ dominance algorithms.
+
+ First, we identify each join point, j (any node with more than one
+ incoming edge is a join point).
+
+ We then examine each predecessor, p, of j and walk up the dominator tree
+ starting at p.
+
+ We stop the walk when we reach j's immediate dominator - j is in the
+ dominance frontier of each of the nodes in the walk, except for j's
+ immediate dominator. Intuitively, all of the rest of j's dominators are
+ shared by j's predecessors as well.
+ Since they dominate j, they will not have j in their dominance frontiers.
+
+ The number of nodes touched by this algorithm is equal to the size
+ of the dominance frontiers, no more, no less.
+*/
+
+
+static void
+compute_dominance_frontiers_1 (bitmap *frontiers)
+{
+ edge p;
+ edge_iterator ei;
+ basic_block b;
+ FOR_EACH_BB (b)
+ {
+ if (EDGE_COUNT (b->preds) >= 2)
+ {
+ FOR_EACH_EDGE (p, ei, b->preds)
+ {
+ basic_block runner = p->src;
+ basic_block domsb;
+ if (runner == ENTRY_BLOCK_PTR)
+ continue;
+
+ domsb = get_immediate_dominator (CDI_DOMINATORS, b);
+ while (runner != domsb)
+ {
+ if (bitmap_bit_p (frontiers[runner->index], b->index))
+ break;
+ bitmap_set_bit (frontiers[runner->index],
+ b->index);
+ runner = get_immediate_dominator (CDI_DOMINATORS,
+ runner);
+ }
+ }
+ }
+ }
+}
+
+
+void
+compute_dominance_frontiers (bitmap *frontiers)
+{
+ timevar_push (TV_DOM_FRONTIERS);
+
+ compute_dominance_frontiers_1 (frontiers);
+
+ timevar_pop (TV_DOM_FRONTIERS);
+}
+
+/* Given a set of blocks with variable definitions (DEF_BLOCKS),
+ return a bitmap with all the blocks in the iterated dominance
+ frontier of the blocks in DEF_BLOCKS. DFS contains dominance
+ frontier information as returned by compute_dominance_frontiers.
+
+ The resulting set of blocks are the potential sites where PHI nodes
+ are needed. The caller is responsible for freeing the memory
+ allocated for the return value. */
+
+bitmap
+compute_idf (bitmap def_blocks, bitmap *dfs)
+{
+ bitmap_iterator bi;
+ unsigned bb_index, i;
+ VEC(int,heap) *work_stack;
+ bitmap phi_insertion_points;
+
+ work_stack = VEC_alloc (int, heap, n_basic_blocks);
+ phi_insertion_points = BITMAP_ALLOC (NULL);
+
+ /* Seed the work list with all the blocks in DEF_BLOCKS. We use
+ VEC_quick_push here for speed. This is safe because we know that
+ the number of definition blocks is no greater than the number of
+ basic blocks, which is the initial capacity of WORK_STACK. */
+ EXECUTE_IF_SET_IN_BITMAP (def_blocks, 0, bb_index, bi)
+ VEC_quick_push (int, work_stack, bb_index);
+
+ /* Pop a block off the worklist, add every block that appears in
+ the original block's DF that we have not already processed to
+ the worklist. Iterate until the worklist is empty. Blocks
+ which are added to the worklist are potential sites for
+ PHI nodes. */
+ while (VEC_length (int, work_stack) > 0)
+ {
+ bb_index = VEC_pop (int, work_stack);
+
+ /* Since the registration of NEW -> OLD name mappings is done
+ separately from the call to update_ssa, when updating the SSA
+ form, the basic blocks where new and/or old names are defined
+ may have disappeared by CFG cleanup calls. In this case,
+ we may pull a non-existing block from the work stack. */
+ gcc_assert (bb_index < (unsigned) last_basic_block);
+
+ EXECUTE_IF_AND_COMPL_IN_BITMAP (dfs[bb_index], phi_insertion_points,
+ 0, i, bi)
+ {
+ /* Use a safe push because if there is a definition of VAR
+ in every basic block, then WORK_STACK may eventually have
+ more than N_BASIC_BLOCK entries. */
+ VEC_safe_push (int, heap, work_stack, i);
+ bitmap_set_bit (phi_insertion_points, i);
+ }
+ }
+
+ VEC_free (int, heap, work_stack);
+
+ return phi_insertion_points;
+}
+
+