Lec15.lR Translation (2) - 14주차 2강

부제: Control-Flow Graph

 

14주차 2강. 2024.12.04.

 

• three address code - 각 식이 최대 3개의 피연산자를 갖도록 함. 단순한 연산 단위로 분해해 분석과 최적화 용이하게.
• global optimization을 효과적으로 수행하기 위해 3주소 코드를 CFG로 변환함.

 

• CFG는 프로그램 제어 흐름을 그래프로 표현한 구조. 최적화와 정적 분석을 위해 사용.
• Node는 Basic Block을 나타냄. 분기 없이 연속적으로 실행되는 명령어 집합
• Edge: Basic Block 간의 Control Flow. 조건문, 반복문의 흐름에 따라 블록이 연결됨.

• basic block은 분기가 없는 명령어의 최대 연속 집합. 중간에서 흐름이 끊기지 않고 처음부터 끝까지 순차적 실행.
• basic block의 속성
  • 중간으로 점프 불가: 기본 블록의 중간에 control flow 들어올 수 없음.
  • control flow는 항상 basic block의 첫 번째 명령에서 시작
  • 끝에서만 점프 가능: 기본 블록의 마지막 명령어에서만 control flow가 빠져나올 수 있음

 

• partitioning instruction에 의해 basic block을 만들 수 있음
• basic block 사이에 control-flow를 연결

• Leader 결정
  • 각 basic block의 첫 번째 명령어
  • 조건부 또는 무조건 jump 명령어의 target 명령어는 leader가 됨
  • 조건부 또는 무조건 jump 명령어 바로 다음에 오는 명령어도 leader임. jump 이후 흐름은 새로운 basic block으로 간주됨.
• basic block 구성
  • leader부터 시작해 다음 leader 전까지 모든 명령어를 basic block으로 포함. 프로그램 끝에 도달할 때까지 반복.

 

• L1: i=1. 프로그램의 첫 번째 명령어는 항상 Leader. i=1은 독립적인 basic block 형성
• L2: j=1. 새로운 선언. 독립적인 basic block
• L3~L9: jump가 나오기 전까지 한 block
• L10~L11: jump가 나오기 전까지 한 block
• L12: 재선언. 독립적인 basic block
• L13~17: jump 나오기 전까지 한 블록

• CFG는 방향 그래프. N은 basic block으로 구성된 노드 집합. 화살표는 control flow를 나타내는 간선 집합
• edge 조건1: n1의 마지막 명령어가 조건부 또는 무조건 jump이고, 해당 jump가 n2의 시작을 가리킬 때
• edge 조건2: n1이 무조건 jump로 끝나지 않고, n2가 프로그램 내에서 n1 바로 다음에 위치할 때