Lecture 2: 2015-09-16

Announcements

  • Introduce TA.
  • No Midterm, the scores are distributed into HW and projects.

Control Flow Analysis

  • Basic Block.
  • Execution →\rightarrow Dynamic control flow
    • branch prediction
  • static control flow (Compiler)
    • not executing the program
  • Control flow analysis
    • Determining properties of the program branch structure

Organize structures, make smart decisions.

Basic Block (BB)

  • Defn: a sequence of consecutive operations in which flow of control enters at the beginning and leaves at the end without halt or possibility of branching except at the end.
  • If one operation is executed in a BB, they all are.

Finding BB's

  • Create a BB whenever you see a branch
  • Split if a target entered into the middle of a block

Q: dynamic branch?

  • Statically determined?
  • Programs with self-modifying code. [PAPER?]

Control Flow Graph (CFG)

  • taken (jump) / fallthrough (not jump)
  • In the assembly code it looks not the same order in the "if" statement.

Weighted CFG

  • branch only when you do the "unlikely" thing.
  • we want the fallthrough path to be the hottest path: not eliminating smaller the number of jumps, branching less dynamically (I-cache issue)

Dominated DOM

  • a node xx dominates yy, if every path from the Entry block to yy contains xx.
    • each BB dominates itself
    • If xx dominates yy and yy dominates zz then xx dominates zz.
    • If xx dominates zz and yy dominates zz then either xx dominates yy or yy dominates xx.

I think the education is a little bit behind, but now we need only to keep the concepts in the head, and do the Google if you want to find the exactly algorithm.

Donimator Tree