Data dependency and Data flow Models

Learning Objectives

• Data Flow Model 이해하기
• Data Flow Model를 이용하는 analysis 이해하기
• Data flow 모델링 할 때의 trade-off 알아보기 (시간,돈,false alarm)

1. 왜 Data Flow Model?

• Control Flow Model (CFG,CG,FSM)은 프로그램의 실행 순서를 따라 그린 것이다.

• But, Data dependence, Control dependence 에 대해 생각해 봐야 한다.

  -x의 값이 어디로부터 왔는지?

  -무엇이 바뀌게 하였는지?

• CFM과 DFM을 섞어서 사용한다.

2. 기본 용어

1. Definition Use Pairs

: 특정 variable이 어디서 정의되고 어디서 사용되는지 나타냄

x:(15L, 17L) // x가 15라인에서 정의되고 17라인에서 사용됨

• Code → CFG → DU pair 찾기

2. Definition clear path

: definition과 usage 사이에 어떤 다른 것도 없는 것. (가장 최신 definition을 살려두고 이전 것은 kill한다.)

3. (Direct) Data Dependence Graph

: 이 value가 어디로부터 왔니?

• Nodes : CFG 꺼

• Edges : def-use(du) pairs , 변수 이름으로 라벨 된 것

• Code → CFG → DU pair 찾기 → DU path 찾기 → DU clear path 찾기 → DDG

4. Control Dependence Graph

: 어떤 statement가 실행 여부를 결정하니?

• Nodes : CFG꺼
• Edges : unlabelled

C,D,E는 B에 dependent하고 / B,F는 A에 dependent 하다.

• Dominator

  : 특정 노드를 실행하기 위해 무조건 거쳐야 하는 Node

  1. Pre-dominator : 이전

  2. Post-dominator :이후

  3. immediate (pre/post) dominator : 가장 가까운 애

• ex) B의 post-dominator는 G이다. (C,E 아님)

• control dependence의 정의를 더 정확히 하기 위해서 post-dominator를 사용한다.

  : 모든 execution path는 지나지 않는 노드 N이 있을 때,

  다음을 만족하는 노드 C가 존재한다.

  • 적어도 두 개의 후손을 가지고 있고
  • C는 N에 의해 post-dominated되지 않는다. (C는 N의 pre-dominator가 아니다)
  • C의 후손 중에 N에 의해 post-dominated되는 노드가 있다. (C의 후손 중에 N의 pre-dominator가 있다.)

  ex) Node C = B , Node N = F

• Execution of F is not inevitable(피할 수 있는, 선택적인) at B

• Execution of F is inevitable(피할 수 없는, 필수적인) at E

• ⇒ F is control-dependent on B ( F의 execution을 결정하는 노드 중 가장 가까운 포인트는 B이다.)

5. Data Flow Analysis

Summary

• Data Flow Model은 CFG의 패턴을 detect한다.

• Data Dependence information

  장점 : 반복적인 알고리즘을 생성 가능하다

   : widley applicable하다. (data flow 속성 외에도 다 가능)
  

  단점 : feasible path와 infeasible path의 구별이 불가하다

   : 전체 프로그램에 걸친 analysis 는 Precision과 computational cost를 trade-off한다