ACM Transactions on Software Engineering and Methodology (to appear). Interprocedural Contr

procedure Mbegin M

read i,j sum = 0 while i < 10 do call B endwhile call B print sumend M

9101112131415

procedure Bbegin B call C

if j >= 0 then sum = sum + j read j endif

i = i + 1end B

16171819

procedure Cbegin C

if sum > 100 then halt endifend C

alternative version of 18:

print(\"error\")18’

1. enter M9. enter B2. read i,j9. enter B10a. call C16. enter C10b. return C11. if j >= 0 thenTF12. sum = sum + j13. read j6a. call B19. exit C14. i = i + 16b. return B7. print sum15. exit B8. exit M13. read j14. i = i + 13. sum = 010a. call C4. while i < 10 doFT5a. call B5b. return B11. if j >= 0 thenTF12. sum = sum + j19. exit C10b. return C16. enter C17. if sum > 100 thenFT18. halt17. if sum > 100 thenFT18. halt15. exit Bexit60IIFG nodes / CFG nodes504030201006050403020100armeplaymazejavflespadidempegnetunzipnuuerffcex1. enter M1. enter M2. read i,j2. read i,j3. sum = 03. sum = 0RP5b4. while i < 10 doFT5a. call B4. while i < 10 doFRP6bT5a. call BTF5b. return BF6a. call BT6a. call B5b. return B6b. return B6b. return B7. print sum7. print sum8. exit M8. exit Msuper exit1. enter MTT2. read i,j3. sum = 04. while i < 10 doT5a. call BF6a. call B8. exit M7. print sumT5b. return BT6b. return BTT1. enter M2. read i,j3. sum = 04. while i < 10 doFT5a. call B5b. return B13. read j6a. call B14. i = i + 16b. return B7. print sum8. exit M15. exit B11. if j >= 0 thenTF12. sum = sum + j9. enter B16. enter C10a. call C10b. return C17. if sum > 100 thenFT18. halt19. exit C1. enter MTTT9. enter BT5b. return BT10a. call C6b. return BT8. exit M7. print sumT15. exit BTT10b. return CT16. enter CT17. if sum > 100 thenF19. exit CT18. halt2. read i,j3. sum = 04. while i < 10 doT5a. call BF11. if j >= 0 thenTT14. i = i + 16a. call B13. read j12. sum = sum + jcontrol dependence on predicatecontrol dependence on placeholderinterprocedural control flow10079083485182736794681458556682038100

8080

Nodes whose partialcontrol dependencesinclude a placeholder

6060

4040

Nodes whose partialcontrol dependences

include only predicates

2020

00

armenudejavumpegplayernetmazespaceunzipdiffflexPercentage of ICDG nodes and edgestraversed on average1.01.00.80.71%0.80.60.47%0.40.40%0.29%0.20.17%0.24%0.13%0.60.40.22%0.200nuvuerexffeemejadiflayazacardeplmpegnetmspunzip100784133051794355244954403545319100

8080

Nodes whose intraproceduraland interprocedural controldependences differed

6060

Nodes whose intraproceduraland interprocedural controldependences were the same

4040

2020

Statically unreachable nodes

00

armenudejavumpegplayernetmazespaceunzipdiffflex1004558341402576804491885853109403328100100373828112150455745174571291168100

80808080

60606060

40404040

20202020

0000

unzipdejavuarmenumpegplayerarmenudejavumpegplayernetmazespacenetmazeInterprocedural control dependences thatwere missed by the intraproceduralcontrol-dependence computation

Interprocedural control dependences thatwere computed also by the intraproceduralcontrol-dependence computation

Interprocedural control dependences thatwere computed only by the interproceduralcontrol-dependence computation along:

a control-dependence edge

an unbalanced-left control-dependence pathan unbalanced-right control-dependence pathan unbalanced-right-left control-dependence path

spaceunzipflexdiffdiffflex1001118636502162434552175043572124961001002076338707134617749351910336100

80808080

60606060

40404040

20202020

0000

unzipdejavuarmenumpegplayernetmazearmenudejavumpegplayerspaceIntraprocedural control dependences thatwere computed only in the intraproceduralcontext

Intraprocedural control dependences thatwere computed also in the interproceduralcontext

Intraprocedural control dependences thatwere computed only in the intraproceduralcontext:

spurious control dependencesincomplete control dependences

netmazespaceunzipflexdiffdiffflex1. enter MTTT9. enter BT5b. return BT10a. call C6b. return BT8. exit M7. print sumT15. exit BTT10b. return CT16. enter CT17. if sum > 100 thenF19. exit CT18. halt2. read i,j3. sum = 04. while i < 10 doT5a. call BF11. if j >= 0 thenTT14. i = i + 16a. call B13. read j12. sum = sum + jcontrol dependence on predicatecontrol dependence on placeholderinterprocedural control flow