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