Cấu trúc dữ liệu và Giải thuật Bài 129: Cây thống trị (Dominator Tree - Thuật toán Lengauer-Tarjan) - Phân tích cấu trúc kiểm soát luồng thực thi trong trình biên dịch.

Trong kỹ thuật xây dựng trình biên dịch hiện đại (như LLVM, GCC hay Go compiler), mã nguồn sau khi phân tích cú pháp sẽ được hạ cấp thành biểu diễn trung gian (IR) dưới dạng Đồ thị dòng điều khiển (Control Flow Graph - CFG). Mỗi nút trong CFG là một khối lệnh cơ bản (Basic Block), và các cạnh có hướng thể hiện các bước rẽ nhánh điều kiện hoặc vòng lặp.

Để thực hiện các kỹ thuật tối ưu hóa mã máy then chốt như:

Xây dựng dạng gán đơn tĩnh Static Single Assignment (SSA form) bằng cách đặt các hàm $\phi$ (phi-nodes).
Phát hiện và tối ưu hóa vòng lặp tự nhiên (Natural Loops / Loop Invariant Code Motion).
Loại bỏ mã chết (Dead Code Elimination).

Trình biên dịch bắt buộc phải trả lời câu hỏi: "Khối lệnh nào chắc chắn phải được thực thi trước khi luồng chương trình chạm tới khối lệnh $v$ ?" Cấu trúc giải quyết bài toán này là Cây thống trị (Dominator Tree), và phương pháp tính toán tối ưu nhất là Thuật toán Lengauer-Tarjan với độ phức tạp gần như tuyến tính $O(E \alpha(V, E))$ hoặc $O(E \log V)$ .

1. Bản chất của Khái niệm Thống trị (Dominance) trong Đồ thị có hướng

Cho một đồ thị có hướng $G = (V, E)$ với một đỉnh gốc cố định $r$ (điểm bắt đầu thực thi của hàm/chương trình):

Thống trị (Dominates): Đỉnh $u$ được gọi là thống trị đỉnh $v$ (ký hiệu $u \text{ dom } v$ ) nếu mọi đường đi có hướng từ gốc $r$ đến $v$ đều phải đi qua $u$ . Theo định nghĩa, mỗi đỉnh luôn tự thống trị chính nó ( $u \text{ dom } u$ ).
Thống trị thực sự (Strictly Dominates): $u$ thống trị thực sự $v$ nếu $u \text{ dom } v$ và $u \neq v$ .
Thống trị trực tiếp (Immediate Dominator - $\text{idom}$ ): Đỉnh $u$ là đỉnh thống trị trực tiếp của $v$ (ký hiệu $u = \text{idom}(v)$ ) nếu:
- $u$ thống trị thực sự $v$ .
- Mọi đỉnh $w$ khác thống trị thực sự $v$ đều thống trị $u$ .
- Mỗi đỉnh $v \neq r$ có thể tiếp cận được từ $r$ đều có duy nhất một đỉnh thống trị trực tiếp.
Cây thống trị (Dominator Tree): Nếu ta tạo các cạnh có hướng $(\text{idom}(v), v)$ cho mọi $v \in V \setminus \{r\}$ , ta thu được một cây có gốc tại $r$ . Trong cây này, quan hệ tổ tiên - con cháu phản ánh quan hệ thống trị trong đồ thị gốc: $u$ thống trị $v$ khi và chỉ khi $u$ là tổ tiên của $v$ trên Dominator Tree.

       CFG (Đồ thị điều khiển)                Dominator Tree
                 (1)                               (1)
                /   \                             / | \
              (2)   (3)                         (2)(3)(4)
                \   /                                  |
                 (4)                                  (5)
                  |
                 (5)
    (Đường đi tới 4 có thể qua 2 hoặc 3, 
     nên idom(4) = 1 chứ không phải 2 hay 3)

2. Nút bán thống trị (Semidominator) và Định lý Lengauer-Tarjan

Nếu kiểm tra quan hệ thống trị bằng cách xóa từng đỉnh $u$ rồi chạy BFS/DFS kiểm tra tính liên thông đến $v$ , chi phí sẽ là $O(V \cdot E)$ — quá chậm đối với các hàm có hàng nghìn khối lệnh.

Thomas Lengauer và Robert Tarjan (1979) đã phát minh ra khái niệm Nút bán thống trị (Semidominator - $\text{sdom}$ ) đóng vai trò cầu nối trung gian:

Thứ tự thăm DFS (DFN)

Thực hiện duyệt DFS trên $G$ xuất phát từ $r$ , gán cho mỗi đỉnh $u$ một chỉ số thời gian $\text{dfn}[u]$ .

Nếu $\text{dfn}[u] < \text{dfn}[v]$ , $u$ được thăm trước $v$ .

Định nghĩa Semidominator ( $\text{sdom}(v)$ )

$\text{sdom}(v)$ là đỉnh $u$ có $\text{dfn}[u]$ nhỏ nhất sao cho tồn tại một đường đi $u = v_0, v_1, \dots, v_k = v$ thỏa mãn:

$\forall 1 \le i < k: \quad \text{dfn}[v_i] > \text{dfn}[v]$

Nói cách khác, $\text{sdom}(v)$ là điểm xuất phát cao nhất có thể "đi vòng qua" các đỉnh chưa hoàn thành của cây DFS để chạm tới $v$ .

Định lý Then chốt Lengauer-Tarjan

Với mỗi đỉnh $w \neq r$ :

$\text{sdom}(w)$ luôn là một tổ tiên của $w$ trên cây DFS.
$\text{idom}(w)$ luôn là một tổ tiên của $\text{sdom}(w)$ (hoặc chính là $\text{sdom}(w)$ ).
Xét tất cả các đỉnh $u$ nằm trên đường đi từ $\text{sdom}(w)$ xuống $w$ trên cây DFS (không bao gồm $\text{sdom}(w)$ ). Gọi $u_{\min}$ là đỉnh có $\text{dfn}[\text{sdom}(u)]$ nhỏ nhất:
- Trường hợp 1: Nếu $\text{sdom}(u_{\min}) = \text{sdom}(w)$ , thì:
  
  $\text{idom}(w) = \text{sdom}(w)$
- Trường hợp 2: Nếu $\text{sdom}(u_{\min}) \neq \text{sdom}(w)$ , thì:
  
  $\text{idom}(w) = \text{idom}(u_{\min})$

3. Quy trình 3 giai đoạn của Thuật toán Lengauer-Tarjan

Thuật toán kết hợp cấu trúc Disjoint Set Union (DSU) có nén đường đi (Path Compression) để duy trì thông tin giá trị $\text{sdom}$ nhỏ nhất trên chuỗi tổ tiên:

Giai đoạn 1 (DFS Tree Construction):
- Duyệt DFS từ gốc $r$ , gán nhãn $\text{dfn}$ , lưu mảng ánh xạ ngược rev[dfn] = u, và xác định nút cha $\text{parent}[u]$ trên cây DFS.
Giai đoạn 2 (Tính $\text{sdom}$ và $\text{idom}$ thô theo thứ tự DFN giảm dần):
- Duyệt các đỉnh từ $\text{dfn} = N$ lùi về $2$ :
  - Xét mọi cạnh ngược $(v, w) \in E$ : tính $\text{sdom}(w)$ dựa trên $\text{dfn}[v]$ (nếu $v$ thăm trước $w$ ) hoặc $\text{sdom}(\text{eval}(v))$ (nếu $v$ thăm sau $w$ ).
  - Đưa $w$ vào danh sách chờ $\text{bucket}[\text{sdom}(w)]$ .
  - Nối $\text{parent}[w]$ vào tập hợp DSU của $w$ .
  - Duyệt qua tất cả các đỉnh $v \in \text{bucket}[\text{parent}[w]]$ : dùng hàm eval của DSU để kiểm tra $u_{\min}$ . Áp dụng định lý Lengauer-Tarjan để gán $\text{idom}(v) = \text{sdom}(v)$ hoặc tạm thời gán $\text{idom}(v) = u_{\min}$ .
Giai đoạn 3 (Hoàn thiện $\text{idom}$ theo thứ tự DFN tăng dần):
- Duyệt các đỉnh từ $\text{dfn} = 2$ đến $N$ :
  - Nếu $\text{idom}(w) \neq \text{sdom}(w)$ , hoàn thiện bằng cách gán $\text{idom}(w) = \text{idom}[\text{idom}(w)]$ .

4. Hiện thực hóa Thuật toán Lengauer-Tarjan bằng Golang

Đoạn mã Golang dưới đây cài đặt hoàn chỉnh thuật toán Lengauer-Tarjan để xây dựng Dominator Tree cho một đồ thị có hướng bất kỳ:

package main

import (
	"bufio"
	"fmt"
	"os"
)

type DominatorTree struct {
	n     int
	adj   [][]int // Danh sách kề xuôi
	radj  [][]int // Danh sách kề ngược

	dfn    []int
	rev    []int
	timer  int
	parent []int

	sdom []int
	idom []int

	// Cấu trúc DSU hỗ trợ nén đường đi và tìm min-sdom
	dsuParent []int
	dsuMin    []int

	bucket [][]int // Chứa danh sách các đỉnh có cùng sdom
	domAdj [][]int // Danh sách kề của Dominator Tree kết quả
}

func NewDominatorTree(n int) *DominatorTree {
	dt := &DominatorTree{
		n:         n,
		adj:       make([][]int, n+1),
		radj:      make([][]int, n+1),
		dfn:       make([]int, n+1),
		rev:       make([]int, n+1),
		parent:    make([]int, n+1),
		sdom:      make([]int, n+1),
		idom:      make([]int, n+1),
		dsuParent: make([]int, n+1),
		dsuMin:    make([]int, n+1),
		bucket:    make([][]int, n+1),
		domAdj:    make([][]int, n+1),
	}
	for i := 1; i <= n; i++ {
		dt.sdom[i] = i
		dt.dsuParent[i] = i
		dt.dsuMin[i] = i
	}
	return dt
}

func (dt *DominatorTree) AddEdge(u, v int) {
	dt.adj[u] = append(dt.adj[u], v)
	dt.radj[v] = append(dt.radj[v], u)
}

// Giai đoạn 1: DFS đánh số DFN và xác định cây khung DFS
func (dt *DominatorTree) dfs(u int) {
	dt.timer++
	dt.dfn[u] = dt.timer
	dt.rev[dt.timer] = u

	for _, v := range dt.adj[u] {
		if dt.dfn[v] == 0 {
			dt.parent[v] = u
			dt.dfs(v)
		}
	}
}

// DSU Find kết hợp Path Compression và duy trì đỉnh có sdom nhỏ nhất
func (dt *DominatorTree) find(u int) int {
	if dt.dsuParent[u] == u {
		return u
	}
	root := dt.find(dt.dsuParent[u])
	if dt.dfn[dt.sdom[dt.dsuMin[dt.dsuParent[u]]]] < dt.dfn[dt.sdom[dt.dsuMin[u]]] {
		dt.dsuMin[u] = dt.dsuMin[dt.dsuParent[u]]
	}
	dt.dsuParent[u] = root
	return root
}

func (dt *DominatorTree) eval(u int) int {
	dt.find(u)
	return dt.dsuMin[u]
}

// Xây dựng Dominator Tree xuất phát từ gốc root: O(E log V)
func (dt *DominatorTree) Build(root int) {
	dt.timer = 0
	dt.dfs(root)

	// Giai đoạn 2: Tính toán sdom và xử lý bucket theo thứ tự DFN giảm dần
	for i := dt.timer; i >= 2; i-- {
		w := dt.rev[i]

		// 1. Tính sdom(w) từ các cạnh ngược đi vào w
		for _, v := range dt.radj[w] {
			if dt.dfn[v] == 0 {
				continue // Đỉnh không chạm tới được từ root
			}
			var candidate int
			if dt.dfn[v] < dt.dfn[w] {
				candidate = v
			} else {
				uMin := dt.eval(v)
				candidate = dt.sdom[uMin]
			}
			if dt.dfn[candidate] < dt.dfn[dt.sdom[w]] {
				dt.sdom[w] = candidate
			}
		}

		dt.bucket[dt.sdom[w]] = append(dt.bucket[dt.sdom[w]], w)
		p := dt.parent[w]
		dt.dsuParent[w] = p

		// 2. Xử lý các đỉnh đang chờ tại bucket của p
		for _, v := range dt.bucket[p] {
			uMin := dt.eval(v)
			if dt.sdom[uMin] == dt.sdom[v] {
				dt.idom[v] = dt.sdom[v]
			} else {
				dt.idom[v] = uMin // Trì hoãn xử lý sang Giai đoạn 3
			}
		}
		dt.bucket[p] = dt.bucket[p][:0]
	}

	// Giai đoạn 3: Hoàn thiện idom theo thứ tự DFN tăng dần
	for i := 2; i <= dt.timer; i++ {
		w := dt.rev[i]
		if dt.idom[w] != dt.sdom[w] {
			dt.idom[w] = dt.idom[dt.idom[w]]
		}
		// Thêm cạnh vào Dominator Tree kết quả
		dt.domAdj[dt.idom[w]] = append(dt.domAdj[dt.idom[w]], w)
	}
}

func main() {
	// Giả lập Đồ thị dòng điều khiển (CFG) gồm 6 khối lệnh (1 đến 6)
	// Gốc bắt đầu chương trình: khối 1
	n := 6
	root := 1
	dt := NewDominatorTree(n)

	// Cấu trúc phân nhánh điều kiện và vòng lặp:
	// 1 -> 2, 1 -> 3
	// 2 -> 4, 3 -> 4
	// 4 -> 5, 5 -> 4 (vòng lặp giữa 4 và 5)
	// 4 -> 6
	dt.AddEdge(1, 2)
	dt.AddEdge(1, 3)
	dt.AddEdge(2, 4)
	dt.AddEdge(3, 4)
	dt.AddEdge(4, 5)
	dt.AddEdge(5, 4)
	dt.AddEdge(4, 6)

	dt.Build(root)

	writer := bufio.NewWriter(os.Stdout)
	defer writer.Flush()

	fmt.Fprintln(writer, "Kết quả Dominator Tree (idom của từng đỉnh):")
	for i := 1; i <= n; i++ {
		if i == root {
			fmt.Fprintf(writer, "Đỉnh %d (Gốc CFG): Không có idom\n", i)
		} else if dt.dfn[i] != 0 {
			fmt.Fprintf(writer, "Đỉnh %d: idom = %d\n", i, dt.idom[i])
		} else {
			fmt.Fprintf(writer, "Đỉnh %d: Không tiếp cận được từ gốc\n", i)
		}
	}

	fmt.Fprintln(writer, "\nCấu trúc cây thống trị (Cha -> Các con trực tiếp):")
	for i := 1; i <= n; i++ {
		if len(dt.domAdj[i]) > 0 {
			fmt.Fprintf(writer, "Nút %d thống trị trực tiếp: %v\n", i, dt.domAdj[i])
		}
	}
}

5. Phân tích độ phức tạp thuật toán

Thành phần	Độ phức tạp thời gian	Ghi chú
DFS Tree Traversal	$O(V + E)$	Thăm mỗi đỉnh và cạnh đúng 1 lần
Tính toán $\text{sdom}$ & Thao tác DSU	$O(E \log V)$	Mỗi cạnh ngược được duyệt 1 lần; DSU nén đường đi tốn $O(\log V)$
Hoàn thiện $\text{idom}$ (Giai đoạn 3)	$O(V)$	Duyệt tuyến tính qua mảng DFN
Tổng thể thuật toán	$O(E \log V)$	Cài đặt chuẩn mực, ngắn gọn và tối ưu cache
Bộ nhớ phụ trợ	$O(V + E)$	Mảng phẳng lưu trữ DFN, DSU và danh sách kề ngược

Nếu áp dụng kỹ thuật cân bằng DSU nâng cao kết hợp hàm Ackermann ngược ( $\alpha$ ), độ phức tạp lý thuyết có thể đạt $O(E \alpha(V, E))$ , tuy nhiên trong thực tế cài đặt trên trình biên dịch, phiên bản $O(E \log V)$ sử dụng mảng phẳng có hằng số ẩn nhỏ hơn và chạy nhanh hơn đáng kể.

6. Ứng dụng thực tế trong Trình biên dịch & Hệ thống

Xây dựng Dạng gán đơn tĩnh (SSA Construction via Dominance Frontier): Biên giới thống trị (Dominance Frontier) của một nút $u$ được tính toán trực tiếp dựa trên Dominator Tree, giúp trình biên dịch xác định vị trí tối thiểu cần chèn các hàm $\phi$ khi quản lý các phiên bản biến số.
Nhận diện Vòng lặp tự nhiên (Natural Loop Detection): Một cạnh ngược $(u, v)$ trong CFG tạo thành một vòng lặp tự nhiên khi và chỉ khi $v \text{ dom } u$ . Đỉnh $v$ được xác định là Loop Header duy nhất của vòng lặp.
Phân tích Điểm yếu mạng lưới (Network Single-Point-of-Failure): Trong đồ thị định tuyến có hướng, mọi đỉnh nằm trên đường đi từ gốc đến $v$ trên Dominator Tree đều là các điểm thắt cổ chai bắt buộc. Nếu bất kỳ nút nào trong chuỗi này bị sập, nút $v$ sẽ mất kết nối hoàn toàn khỏi mạng.

cấu trúc dữ liệu