0.03/0.19 WORST_CASE(?,O(n^1)) 0.03/0.19 0.03/0.19 Preprocessing Cost Relations 0.03/0.19 ===================================== 0.03/0.19 0.03/0.19 #### Computed strongly connected components 0.03/0.19 0. recursive : [eval/3] 0.03/0.19 1. non_recursive : [exit_location/1] 0.03/0.19 2. non_recursive : [eval_loop_cont/2] 0.03/0.19 3. non_recursive : [start/3] 0.03/0.19 0.03/0.19 #### Obtained direct recursion through partial evaluation 0.03/0.19 0. SCC is partially evaluated into eval/3 0.03/0.19 1. SCC is completely evaluated into other SCCs 0.03/0.19 2. SCC is completely evaluated into other SCCs 0.03/0.19 3. SCC is partially evaluated into start/3 0.03/0.19 0.03/0.19 Control-Flow Refinement of Cost Relations 0.03/0.19 ===================================== 0.03/0.19 0.03/0.19 ### Specialization of cost equations eval/3 0.03/0.19 * CE 4 is refined into CE [5] 0.03/0.19 * CE 2 is refined into CE [6] 0.03/0.19 * CE 3 is refined into CE [7] 0.03/0.19 0.03/0.19 0.03/0.19 ### Cost equations --> "Loop" of eval/3 0.03/0.19 * CEs [6] --> Loop 5 0.03/0.19 * CEs [7] --> Loop 6 0.03/0.19 * CEs [5] --> Loop 7 0.03/0.19 0.03/0.19 ### Ranking functions of CR eval(A,B,C) 0.03/0.19 * RF of phase [5,6]: [A+B-2] 0.03/0.19 0.03/0.19 #### Partial ranking functions of CR eval(A,B,C) 0.03/0.19 * Partial RF of phase [5,6]: 0.03/0.19 - RF of loop [5:1]: 0.03/0.19 A-1 0.03/0.19 A-B depends on loops [6:1] 0.03/0.19 - RF of loop [6:1]: 0.03/0.19 -A+B depends on loops [5:1] 0.03/0.19 B-1 0.03/0.19 0.03/0.19 0.03/0.19 ### Specialization of cost equations start/3 0.03/0.19 * CE 1 is refined into CE [8,9] 0.03/0.19 0.03/0.19 0.03/0.19 ### Cost equations --> "Loop" of start/3 0.03/0.19 * CEs [9] --> Loop 8 0.03/0.19 * CEs [8] --> Loop 9 0.03/0.19 0.03/0.19 ### Ranking functions of CR start(A,B,C) 0.03/0.19 0.03/0.19 #### Partial ranking functions of CR start(A,B,C) 0.03/0.19 0.03/0.19 0.03/0.19 Computing Bounds 0.03/0.19 ===================================== 0.03/0.19 0.03/0.19 #### Cost of chains of eval(A,B,C): 0.03/0.19 * Chain [[5,6],7]: 1*it(5)+1*it(6)+0 0.03/0.19 Such that:aux(4) =< -A+B 0.03/0.19 aux(2) =< A-B 0.03/0.19 aux(1) =< 2*A+B 0.03/0.19 aux(14) =< A 0.03/0.19 aux(15) =< A+B 0.03/0.19 aux(16) =< A+2*B 0.03/0.19 aux(17) =< B 0.03/0.19 aux(3) =< aux(14) 0.03/0.19 it(5) =< aux(14) 0.03/0.19 aux(1) =< aux(15) 0.03/0.19 aux(3) =< aux(15) 0.03/0.19 it(5) =< aux(15) 0.03/0.19 it(6) =< aux(15) 0.03/0.19 aux(1) =< aux(16) 0.03/0.19 aux(3) =< aux(16) 0.03/0.19 aux(1) =< aux(17) 0.03/0.19 it(6) =< aux(17) 0.03/0.19 it(6) =< aux(3)+aux(4) 0.03/0.19 aux(1) =< it(6)*aux(17) 0.03/0.19 it(5) =< aux(1)+aux(2) 0.03/0.19 0.03/0.19 with precondition: [C=2,A>=1,B>=1,A+B>=3] 0.03/0.19 0.03/0.19 * Chain [7]: 0 0.03/0.19 with precondition: [C=2] 0.03/0.19 0.03/0.19 0.03/0.19 #### Cost of chains of start(A,B,C): 0.03/0.19 * Chain [9]: 0 0.03/0.19 with precondition: [] 0.03/0.19 0.03/0.19 * Chain [8]: 1*s(9)+1*s(10)+0 0.03/0.19 Such that:s(1) =< -A+B 0.03/0.19 s(4) =< A 0.03/0.19 s(2) =< A-B 0.03/0.19 s(5) =< A+B 0.03/0.19 s(6) =< A+2*B 0.03/0.19 s(3) =< 2*A+B 0.03/0.19 aux(18) =< B 0.03/0.19 s(1) =< aux(18) 0.03/0.19 s(8) =< s(4) 0.03/0.19 s(9) =< s(4) 0.03/0.19 s(3) =< s(5) 0.03/0.19 s(8) =< s(5) 0.03/0.19 s(9) =< s(5) 0.03/0.19 s(10) =< s(5) 0.03/0.19 s(3) =< s(6) 0.03/0.19 s(8) =< s(6) 0.03/0.19 s(3) =< aux(18) 0.03/0.19 s(10) =< aux(18) 0.03/0.19 s(10) =< s(8)+s(1) 0.03/0.19 s(3) =< s(10)*aux(18) 0.03/0.19 s(9) =< s(3)+s(2) 0.03/0.19 0.03/0.19 with precondition: [A>=1,B>=1,A+B>=3] 0.03/0.19 0.03/0.19 0.03/0.19 Closed-form bounds of start(A,B,C): 0.03/0.19 ------------------------------------- 0.03/0.19 * Chain [9] with precondition: [] 0.03/0.19 - Upper bound: 0 0.03/0.19 - Complexity: constant 0.03/0.19 * Chain [8] with precondition: [A>=1,B>=1,A+B>=3] 0.03/0.19 - Upper bound: 2*A+B 0.03/0.19 - Complexity: n 0.03/0.19 0.03/0.19 ### Maximum cost of start(A,B,C): nat(A+B)+nat(A) 0.03/0.19 Asymptotic class: n 0.03/0.19 * Total analysis performed in 117 ms. 0.03/0.19 0.03/0.29 EOF