[SoftwareV&V] 06. Data Dependency & Data Flow Models

[원문링크]

https://adorable-aspen-d23.notion.site/SoftwareV-V_06_Data-Dependency-Data-Flow-Models-8da94a504059437885c1a1e502d6f001

SoftwareV&V_06_Data Dependency & Data Flow Models

[2021 - 1학기 수강한 Software V&V 강의 정리본입니다.]

(Software Verification & Validation)

 

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 찾기

1. 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

• Dominator
  1. Pre-dominator : 이전
  2. Post-dominator :이후
  3. immediate (pre/post) dominator : 가장 가까운 애
• : 특정 노드를 실행하기 위해 무조건 거쳐야 하는 Node

• control dependence의 정의를 더 정확히 하기 위해서 post-dominator를 사용한다.다음을 만족하는 노드 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 path는 지나지 않는 노드 N이 있을 때,
• 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한다
• 장점 : 반복적인 알고리즘을 생성 가능하다