【GCC編譯器】計算支配樹信息 Part1 – 求CFG的深度為主搜索樹

• 2021 年 8 月 7 日
• 筆記

• 深度為主生成樹：將圖中所有的結點和那些構成深度為主次序的邊表示為樹的形式，並將其他的邊(這些邊不是深度為主次序的一部分)用一種有別於樹的方式來表示(我們用虛線而不是實線表示它們)
  • 屬於深度為主生成樹的邊稱為樹邊（tree edge）
  • 不屬於深度為主生成樹的那些邊分為三類:
    • 前向邊（forward edge）：從一個結點到一個直接後裔並且不是樹邊的邊（用F標識），主編號由小到大
    • 後向邊（back edge）：從一個結點到樹中它的一個祖先的邊（用B標識），主編號由大到小
    • 橫向邊（cross edge）：連接兩個在樹中互不是祖先的結點的邊（用C標識），主編號由大到小

• GCC在計算深度為主搜索樹時，使用的是非遞歸算法。利用stack先入後出的特點，完成樹的深度優先遍歷。為了使得代碼邏輯更清晰，刪除了CDI_POST_DOMINATORS模式相關的代碼。
•  遍歷過程中一共生成3張映射表：
  • bb的index –> bb的深度為主編號：保存在映射表m_dfs_order
  • bb的深度為主編號 –> bb的index：保存在映射表m_dfs_to_bb
  • bb的深度為主編號 –> 在深度為主生成樹中，bb的父節點的深度為主編號：保存在m_dfs_parent

/* The nonrecursive variant of creating a DFS tree.  BB is the starting basic
   block for this tree and m_reverse is true, if predecessors should be visited
   instead of successors of a node.  After this is done all nodes reachable
   from BB were visited, have assigned their dfs number and are linked together
   to form a tree.  */

void
dom_info::calc_dfs_tree_nonrec (basic_block bb)
{
  edge_iterator *stack = new edge_iterator[m_n_basic_blocks + 1];
  int sp = 0;
  unsigned d_i = dom_convert_dir_to_idx (CDI_DOMINATORS);

  /* Initialize the first edge.  */
  edge_iterator ei = ei_start (bb->succs);

  /* When the stack is empty we break out of this loop.  */
  while (1)
    {
      basic_block bn;
      edge_iterator einext;

      /* This loop traverses edges e in depth first manner, and fills the
         stack.  */
      while (!ei_end_p (ei))
        {
          edge e = ei_edge (ei);

	      /* Deduce from E the current and the next block (BB and BN), and the
	         next edge.  */
          bb = e->src;
          bn = e->dest;
          /* 三種情況下跳過當前節點：
             1. BN是end block，對於CDI_DOMINATORS模式來說，即exit block.
             2. 沒有給BN分配保存dominance information的空間.
             3. 已經被訪問過的節點. */
          if (bn == m_end_block || bn->dom[d_i] == NULL
              || m_dfs_order[bn->index])
            {
              ei_next (&ei);
              continue;
            }

          /* 深度優先，遍歷BN的後繼節點. */
          einext = ei_start (bn->succs);
          
          gcc_assert (bn != m_start_block);
	      /* Fill the DFS tree info calculatable _before_ recursing.  */
          /* my_i    是BB的深度為主編號.
             child_i 是BN的深度為主編號. */
          TBB my_i;
          if (bb != m_start_block)
            my_i = m_dfs_order[bb->index];
          else
            my_i = *m_dfs_last;
          /* 將BN和child_i的映射關係存入表m_dfs_order. */
          TBB child_i = m_dfs_order[bn->index] = m_dfsnum++;
          /* 將child_i和BN的映射關係存入表m_dfs_to_bb. */
          m_dfs_to_bb[child_i] = bn;
          /* 將BB和BN的父子節點關係寫入表m_dfs_parent. */
          m_dfs_parent[child_i] = my_i;

	      /* Save the current point in the CFG on the stack, and recurse.  */
          stack[sp++] = ei;
          ei = einext;
        }

      if (!sp)
        break;
      ei = stack[--sp];

      /* OK.  The edge-list was exhausted, meaning normally we would
         end the recursion.  After returning from the recursive call,
         there were (may be) other statements which were run after a
         child node was completely considered by DFS.  Here is the
         point to do it in the non-recursive variant.
         E.g. The block just completed is in e->dest for forward DFS,
         the block not yet completed (the parent of the one above)
         in e->src.  This could be used e.g. for computing the number of
         descendants or the tree depth.  */
      ei_next (&ei);
    }
  delete[] stack;
}