지배자 노드와 도미노 트리 란 무엇입니까?

Question

Dominator (그래프 이론) 에 대한 Wikipedia 읽기를 시도했습니다. 도미노 노드의 다음 정의 :

노드 D는 엔트리 노드의 모든 경로가 n으로 n이면 노드 n을 지배합니다. d를 밟아야합니다.

Dominator 노드의 개념을 이해해야하지만 그래프로 깊이 들어갈 필요가 없으므로 이러한 정의를 이해하려고 노력하고 있습니다. 나는 기사에서 이미지를 보려고 노력하고 있습니다 :

이것은 그래프입니다 :

>>

위의 그래프를위한 도미터 트리 여야합니다.

>>

위의 정의에 따라, 나는 생각한다

노드 2는 노드 3을 지배합니다. 3의 모든 경로가 2. 왜? 왜? 3에서 자체로 가야합니다. 2.이란이 이유는 도미노 트리에서 3로 간다.

나는 옳다고 생각하고 있니?

이 이유가 컴파일러에서 유용한 이유를 알 수 있습니까?

Answer 1

주는 이유는 정확히 옳지 않습니다. Dominator 노드의 정의는 예제에서 시작 노드 ( $ 1 $ )에서 작동합니다. $ 3 $ 에서 $ 1 $ 에 도달하는 유일한 방법은 $ 2 $ 주어진 그래프에서 $ 1 $ 의 유일한 후속 노드이기 때문에. 따라서 $ 2 $ 은 $ 3 $ 을 지배합니다. 같은 이유로, 노드 $ 4 $ 을 통해 $ 6 $ 은 $ 2 $ $ 2 $ 은 이러한 노드의 즉각적인 도미터입니다 ( $ 1 $ 은 $ 2 $ 을 지배하며,이 노드는 $ 1 $ 및 $ 2 $ :

• $ 3, 4 $ 및 $ 6 $ 은 $ 1 $ $ 2 $
$ 2 $ $ 5 $ 에 도달 할 수 있습니다. > $ 3 $ 또는 $ 4 $ 과 $ 5 $ 에 대한 유일한 공통 노드 $ 1 $ 및 $ 2 $

이러한 개념을 컴파일러에 적용하기 위해 프로그램의 블록 레벨 제어 흐름 그래프 (또는 BRG 용 CFG)를 고려하십시오. 일부 블록 $ b $ 은 CFG에서 블록 $ b '$ 을 지배합니다. "수학 용기"> $ B $ 은 프로그램이 $ b '$ 에 도달 할 때까지 실행되어야합니다. 이 지식은 중복 코드를 제거하는 데 사용할 수 있습니다. 프로그램을 고려하십시오

a = (something)
b = True

if a == True:
   b = True
else:
   b = False
   

.

여기서, 처음 두 줄로 구성된 블록은 if-block뿐만 아니라 다른 블록을 지배합니다. 따라서 우리는 B를 true로 설정하는 if-block으로 이동할 때, 그것은 이미 주먹 블록에 의해 true로 설정되어 있으므로 컴파일러가 if-block에서 할당을 삭제하여 코드를 최적화 할 수 있습니다.

CFG가 $ B '\ ~ b $ $ b $ $ b '$ 을 지배합니다. 이러한 경로는 $ b $ 이 루프 헤더를 나타내는 루프의 존재를 나타냅니다. $ b '$ 은 (마지막) 루프 본문 부분입니다.