Question? Leave a message!




Program Analysis and Optimization

Program Analysis and Optimization
Dr.MasonHanks Profile Pic
Dr.MasonHanks,Germany,Teacher
Published Date:23-07-2017
Website URL
Comment
Spring Spring 2009 2009 Lecture Lecture 9: 9: Introduction Introduction to to Program Analysis and Optimization OptimizationOutline • Introduction Introduction • Basic Blocks • Common Subexpression Elimination • CC opy PP ropagatiti on •Dead ead C Code ode Eliminat atio on • Algebraic Simplification • Summary Prog g ram Analy y sis • Compile-time reasoning about run-time behavior of program – Can discover things that are always true: • “ “ x ii s all ways 1 1 ii n thth e stt att ement t y = x + z” ” • “the pointer p always points into array a” • “the statement return 5 can never execute” – Can infer things that are likely to be true: • “the reference r usually refers to an object of class C” • • “the the statement statement a a=b+c = b + c appears appears t to o e execute xecute more more frequently frequently than the statement x = y + z” – Distinction between data and control-flow properties Saman Amarasinghe 3 6.035 ©MIT Fall 1998 Transformations • Use analysis results to transform program • Overall goal: improve some aspect of program • Traditional goals: – Rd Reduce numbb er off executed d ii nstructiions – Reduce overall code size • • Other Other goals goals emerge emerge as as space space becomes becomes more more complex complex – Reduce number of cycles • Use vector or DSP instructions • Improve instruction or data cache hit rate – Reduce power consumption – Reduce Reduce memory memory usage usage Saman Amarasinghe 4 6.035 ©MIT Fall 1998 Outline • Introduction Introduction • Basic Blocks • Common Subexpression Elimination • CC opy PP ropagatiti on •Dead ead C Code ode Eliminat atio on • Algebraic Simplification • Summary Control Flow Grap ph • Nodes Rep p resent Comp p utation – Each Node is a Basic Block –Ba asic Blo ock is a a Sequ q uence o of Instru uctio ons with • No Branches Out Of Middle of Basic Block • No Branches Into Middle of Basic Block • Basic Blocks should be maximal – Execution of basic block starts with first instruction – Includes all instructions in basic block •Edges Represent Control Flow Saman Amarasinghe 6 6.035 ©MIT Fall 1998 s = 0; Control Flow Grap p h a = 4; i = 0; into add(n, k) k k == 0 0 s = 0; a = 4; i = 0; if (k == 0) b b = 1 1 ; b = 2; b = 1; else b= b = 2; 2; i n while (i n) s = s + ab; ; s = s ++ abb ; i = i + 1; return s; i = i + 1; return s; Saman Amarasinghe 7 6.035 ©MIT Fall 1998 Basic Block Construction • Start with instruction control-flow ggp raph • Visit all edges in graph • • Merge Merge a adjacent djacent nodes nodes if if – Only one edge from first node – Only Only one one edge edge into into second second node node s = 0; s = 0; a = 4; a = 4; Saman Amarasinghe 8 6.035 ©MIT Fall 1998 s = 0; s = 0; a = 4; a = 4; i = 0; k= k==0 =0 b = 2; b = 1; i n s = s + ab; return s; ii i =i+1+1;; Saman Amarasinghe 9 6.035 ©MIT Fall 2006s = 0; s = 0; a = 4; a = 4; i = 0; i = 0; k= k==0 =0 b = 2; b = 1; i n s = s + ab; return s; ii i =i+1+1;; Saman Amarasinghe 10 6.035 ©MIT Fall 2006s = 0; s = 0; a = 4; a = 4; i = 0; k= k==0 =0 i = 0; k= k==0 =0 b = 2; b = 1; i n s = s + ab; return s; iii =i+1+1;; Saman Amarasinghe 11 6.035 ©MIT Fall 2006s = 0; s=0 s=0;; a = 4; i = 0; a = 4; k= k==0 =0 i = 0; k= k==0 =0 b = 2; b = 2; b = 1; i n s = s + ab; return s; iii =i+1+1;; Saman Amarasinghe 12 6.035 ©MIT Fall 2006s = 0; s=0 s=0;; a = 4; i = 0; a = 4; k= k==0 =0 i = 0; k= k==0 =0 b = 2; b = 2; b = 1; i n i n s = s + ab; return s; iii =i+1+1;; Saman Amarasinghe 13 6.035 ©MIT Fall 2006s = 0; s=0 s=0;; a = 4; i = 0; a = 4; k= k==0 =0 i = 0; k= k==0 =0 b = 2; b = 2; b = 1; i n i n s = s + ab; s = s + ab; return s; iii =i+1+1;; Saman Amarasinghe 14 6.035 ©MIT Fall 2006s = 0; s=0 s=0;; a = 4; i = 0; a = 4; k= k==0 =0 i = 0; k= k==0 =0 b = 2; b = 2; b = 1; i n i n s = s + ab; s = s + ab; return s; i = i + 1; i = i + 1; Saman Amarasinghe 15 6.035 ©MIT Fall 2006s = 0; s=0 s=0;; a = 4; i = 0; a = 4; k= k==0 =0 i = 0; k= k==0 =0 b = 2; b = 2; b = 1; i n i n s = s + ab; s = s + ab; return s; i = i + 1; iii =i+1+1;; Saman Amarasinghe 16 6.035 ©MIT Fall 2006s = 0; s=0 s=0;; a = 4; i = 0; a = 4; k= k==0 =0 i = 0; k= k==0 =0 b = 2; b = 2; b = 1; i n i n s = s + ab; s = s + ab; return s; return s; i = i + 1; ii i =i+1+1;; Saman Amarasinghe 17 6.035 ©MIT Fall 2006s = 0; s=0 s=0;; a = 4; i = 0; a = 4; k= k==0 =0 i = 0; k= k==0 =0 b = 2; b = 1; b = 2; b = 1; i n i n s = s + ab; s = s + ab; return s; return s; i = i + 1; ii i =i+1+1;; Saman Amarasinghe 18 6.035 ©MIT Fall 2006s = 0; s=0 s=0;; a = 4; i = 0; a = 4; k= k==0 =0 i = 0; k= k==0 =0 b = 2; b = 1; b = 2; b = 1; i n i n s = s + ab; s = s + ab; return s; return s; i = i + 1; ii i =i+1+1;; Saman Amarasinghe 19 6.035 ©MIT Fall 2006s = 0; s=0 s=0;; a = 4; i = 0; a = 4; k= k==0 =0 i = 0; k= k==0 =0 b = 2; b = 1; b = 2; b = 1; i n i n s = s + ab; s = s + ab; return s; return s; i = i + 1; ii i =i+1+1;; Saman Amarasinghe 20 6.035 ©MIT Fall 2006