0.55/0.54 WORST_CASE(?,O(n^2)) 0.55/0.54 0.55/0.54 Preprocessing Cost Relations 0.55/0.54 ===================================== 0.55/0.54 0.55/0.54 #### Computed strongly connected components 0.55/0.54 0. recursive : [eval_nestedLoop_6/7,eval_nestedLoop_7/8,eval_nestedLoop_bb4_in/7,eval_nestedLoop_bb5_in/8] 0.55/0.54 1. recursive : [eval_nestedLoop_2/8,eval_nestedLoop_3/9,eval_nestedLoop_bb2_in/8,eval_nestedLoop_bb3_in/9,eval_nestedLoop_bb4_in_loop_cont/9] 0.55/0.54 2. recursive : [eval_nestedLoop_0/5,eval_nestedLoop_1/6,eval_nestedLoop_bb1_in/5,eval_nestedLoop_bb2_in_loop_cont/10,eval_nestedLoop_bb6_in/9] 0.55/0.54 3. non_recursive : [eval_nestedLoop_stop/1] 0.55/0.54 4. non_recursive : [eval_nestedLoop_bb7_in/1] 0.55/0.54 5. non_recursive : [eval_nestedLoop_bb1_in_loop_cont/2] 0.55/0.54 6. non_recursive : [eval_nestedLoop_bb0_in/4] 0.55/0.54 7. non_recursive : [eval_nestedLoop_start/4] 0.55/0.54 0.55/0.54 #### Obtained direct recursion through partial evaluation 0.55/0.54 0. SCC is partially evaluated into eval_nestedLoop_bb4_in/7 0.55/0.54 1. SCC is partially evaluated into eval_nestedLoop_bb2_in/8 0.55/0.54 2. SCC is partially evaluated into eval_nestedLoop_bb1_in/5 0.55/0.54 3. SCC is completely evaluated into other SCCs 0.55/0.54 4. SCC is completely evaluated into other SCCs 0.55/0.54 5. SCC is completely evaluated into other SCCs 0.55/0.54 6. SCC is partially evaluated into eval_nestedLoop_bb0_in/4 0.55/0.54 7. SCC is partially evaluated into eval_nestedLoop_start/4 0.55/0.54 0.55/0.54 Control-Flow Refinement of Cost Relations 0.55/0.54 ===================================== 0.55/0.54 0.55/0.54 ### Specialization of cost equations eval_nestedLoop_bb4_in/7 0.55/0.54 * CE 12 is refined into CE [13] 0.55/0.54 * CE 11 is refined into CE [14] 0.55/0.54 0.55/0.54 0.55/0.54 ### Cost equations --> "Loop" of eval_nestedLoop_bb4_in/7 0.55/0.54 * CEs [14] --> Loop 13 0.55/0.54 * CEs [13] --> Loop 14 0.55/0.54 0.55/0.54 ### Ranking functions of CR eval_nestedLoop_bb4_in(V_N,V_j_0,V_i_1,V_6,V_k_0,B,C) 0.55/0.54 * RF of phase [14]: [V_N-V_k_0] 0.55/0.54 0.55/0.54 #### Partial ranking functions of CR eval_nestedLoop_bb4_in(V_N,V_j_0,V_i_1,V_6,V_k_0,B,C) 0.55/0.54 * Partial RF of phase [14]: 0.55/0.54 - RF of loop [14:1]: 0.55/0.54 V_N-V_k_0 0.55/0.54 0.55/0.54 0.55/0.54 ### Specialization of cost equations eval_nestedLoop_bb2_in/8 0.55/0.54 * CE 10 is refined into CE [15,16] 0.55/0.54 * CE 8 is refined into CE [17] 0.55/0.54 * CE 9 is refined into CE [18] 0.55/0.54 0.55/0.54 0.55/0.54 ### Cost equations --> "Loop" of eval_nestedLoop_bb2_in/8 0.55/0.54 * CEs [18] --> Loop 15 0.55/0.54 * CEs [17] --> Loop 16 0.55/0.54 * CEs [16] --> Loop 17 0.55/0.54 * CEs [15] --> Loop 18 0.55/0.54 0.55/0.54 ### Ranking functions of CR eval_nestedLoop_bb2_in(V_m,V_N,V_j_0,V_i_1,B,C,D,E) 0.55/0.54 * RF of phase [17,18]: [V_m-V_j_0] 0.55/0.54 0.55/0.54 #### Partial ranking functions of CR eval_nestedLoop_bb2_in(V_m,V_N,V_j_0,V_i_1,B,C,D,E) 0.55/0.54 * Partial RF of phase [17,18]: 0.55/0.54 - RF of loop [17:1]: 0.55/0.54 V_N-V_i_1 0.55/0.54 - RF of loop [17:1,18:1]: 0.55/0.54 V_m-V_j_0 0.55/0.54 0.55/0.54 0.55/0.54 ### Specialization of cost equations eval_nestedLoop_bb1_in/5 0.55/0.54 * CE 7 is refined into CE [19,20,21,22] 0.55/0.54 * CE 6 is refined into CE [23] 0.55/0.54 0.55/0.54 0.55/0.54 ### Cost equations --> "Loop" of eval_nestedLoop_bb1_in/5 0.55/0.54 * CEs [23] --> Loop 19 0.55/0.54 * CEs [21,22] --> Loop 20 0.55/0.54 * CEs [20] --> Loop 21 0.55/0.54 * CEs [19] --> Loop 22 0.55/0.54 0.55/0.54 ### Ranking functions of CR eval_nestedLoop_bb1_in(V_n,V_m,V_N,V_i_0,B) 0.55/0.54 * RF of phase [20,21,22]: [V_n-V_i_0] 0.55/0.54 0.55/0.54 #### Partial ranking functions of CR eval_nestedLoop_bb1_in(V_n,V_m,V_N,V_i_0,B) 0.55/0.54 * Partial RF of phase [20,21,22]: 0.55/0.54 - RF of loop [20:1,21:1,22:1]: 0.55/0.54 V_n-V_i_0 0.55/0.54 0.55/0.54 0.55/0.54 ### Specialization of cost equations eval_nestedLoop_bb0_in/4 0.55/0.54 * CE 5 is refined into CE [24,25] 0.55/0.54 * CE 4 is refined into CE [26] 0.55/0.54 * CE 3 is refined into CE [27] 0.55/0.54 * CE 2 is refined into CE [28] 0.55/0.54 0.55/0.54 0.55/0.54 ### Cost equations --> "Loop" of eval_nestedLoop_bb0_in/4 0.55/0.54 * CEs [25] --> Loop 23 0.55/0.54 * CEs [24] --> Loop 24 0.55/0.54 * CEs [26] --> Loop 25 0.55/0.54 * CEs [27] --> Loop 26 0.55/0.54 * CEs [28] --> Loop 27 0.55/0.54 0.55/0.54 ### Ranking functions of CR eval_nestedLoop_bb0_in(V_n,V_m,V_N,B) 0.55/0.54 0.55/0.54 #### Partial ranking functions of CR eval_nestedLoop_bb0_in(V_n,V_m,V_N,B) 0.55/0.54 0.55/0.54 0.55/0.54 ### Specialization of cost equations eval_nestedLoop_start/4 0.55/0.54 * CE 1 is refined into CE [29,30,31,32,33] 0.55/0.54 0.55/0.54 0.55/0.54 ### Cost equations --> "Loop" of eval_nestedLoop_start/4 0.55/0.54 * CEs [33] --> Loop 28 0.55/0.54 * CEs [32] --> Loop 29 0.55/0.54 * CEs [31] --> Loop 30 0.55/0.54 * CEs [30] --> Loop 31 0.55/0.54 * CEs [29] --> Loop 32 0.55/0.54 0.55/0.54 ### Ranking functions of CR eval_nestedLoop_start(V_n,V_m,V_N,B) 0.55/0.54 0.55/0.54 #### Partial ranking functions of CR eval_nestedLoop_start(V_n,V_m,V_N,B) 0.55/0.54 0.55/0.54 0.55/0.54 Computing Bounds 0.55/0.54 ===================================== 0.55/0.54 0.55/0.54 #### Cost of chains of eval_nestedLoop_bb4_in(V_N,V_j_0,V_i_1,V_6,V_k_0,B,C): 0.55/0.54 * Chain [[14],13]: 1*it(14)+0 0.55/0.54 Such that:it(14) =< -V_k_0+C 0.55/0.54 0.55/0.54 with precondition: [B=2,V_N>=0,V_j_0>=0,V_6>=1,V_k_0>=V_i_1,C>=V_k_0+1,V_N>=C] 0.55/0.54 0.55/0.54 * Chain [13]: 0 0.55/0.54 with precondition: [B=2,V_k_0=C,V_N>=0,V_j_0>=0,V_6>=1,V_k_0>=V_i_1] 0.55/0.54 0.55/0.54 0.55/0.54 #### Cost of chains of eval_nestedLoop_bb2_in(V_m,V_N,V_j_0,V_i_1,B,C,D,E): 0.55/0.54 * Chain [[17,18],16]: 1*it(17)+1*it(18)+1*s(3)+0 0.55/0.54 Such that:aux(3) =< V_N-V_i_1 0.55/0.54 aux(4) =< -V_i_1+D 0.55/0.54 aux(5) =< -V_j_0+C 0.55/0.54 it(17) =< aux(5) 0.55/0.54 it(18) =< aux(5) 0.55/0.54 it(17) =< aux(3) 0.55/0.54 s(3) =< aux(3) 0.55/0.54 it(17) =< aux(4) 0.55/0.54 s(3) =< aux(4) 0.55/0.54 0.55/0.54 with precondition: [B=3,V_m=C,V_N>=0,V_j_0>=0,V_m>=V_j_0+1,D>=V_i_1] 0.55/0.54 0.55/0.54 * Chain [[17,18],15]: 1*it(17)+1*it(18)+1*s(3)+0 0.55/0.54 Such that:aux(1) =< V_m-V_j_0 0.55/0.54 aux(3) =< V_N-V_i_1 0.55/0.54 aux(2) =< -V_j_0+C 0.55/0.54 aux(4) =< -V_i_1+D 0.55/0.54 it(17) =< aux(1) 0.55/0.54 it(18) =< aux(1) 0.55/0.54 it(17) =< aux(2) 0.55/0.54 it(18) =< aux(2) 0.55/0.54 it(17) =< aux(3) 0.55/0.54 s(3) =< aux(3) 0.55/0.54 it(17) =< aux(4) 0.55/0.54 s(3) =< aux(4) 0.55/0.54 0.55/0.54 with precondition: [B=3,0>=E,V_N>=0,V_j_0>=0,C>=V_j_0+1,D>=V_i_1,V_m>=C] 0.55/0.54 0.55/0.54 * Chain [16]: 0 0.55/0.54 with precondition: [B=3,V_j_0=V_m,D=V_i_1,V_j_0=C,V_N>=0,V_j_0>=0] 0.55/0.54 0.55/0.54 * Chain [15]: 0 0.55/0.54 with precondition: [B=3,D=V_i_1,V_j_0=C,0>=E,V_N>=0,V_j_0>=0,V_m>=V_j_0] 0.55/0.54 0.55/0.54 0.55/0.54 #### Cost of chains of eval_nestedLoop_bb1_in(V_n,V_m,V_N,V_i_0,B): 0.55/0.54 * Chain [[20,21,22],19]: 3*it(20)+1*s(28)+1*s(29)+2*s(30)+1*s(31)+1*s(32)+0 0.55/0.54 Such that:aux(15) =< V_n-V_i_0 0.55/0.54 aux(10) =< V_m 0.55/0.54 aux(14) =< V_N 0.55/0.54 aux(11) =< V_N-V_i_0 0.55/0.54 it(20) =< aux(15) 0.55/0.54 aux(13) =< aux(10) 0.55/0.54 s(37) =< it(20)*aux(14) 0.55/0.54 s(38) =< it(20)*aux(11) 0.55/0.54 s(35) =< it(20)*aux(10) 0.55/0.54 s(36) =< it(20)*aux(13) 0.55/0.54 s(34) =< s(38) 0.55/0.54 s(34) =< s(37) 0.55/0.54 s(28) =< s(36) 0.55/0.54 s(29) =< s(36) 0.55/0.54 s(28) =< s(34) 0.55/0.54 s(30) =< s(34) 0.55/0.54 s(31) =< s(35) 0.55/0.54 s(32) =< s(35) 0.55/0.54 s(31) =< s(34) 0.55/0.54 0.55/0.54 with precondition: [B=4,V_m>=0,V_N>=0,V_i_0>=0,V_n>=V_i_0+1] 0.55/0.54 0.55/0.54 * Chain [19]: 0 0.55/0.54 with precondition: [B=4,V_n>=0,V_m>=0,V_N>=0,V_i_0>=0] 0.55/0.54 0.55/0.54 0.55/0.54 #### Cost of chains of eval_nestedLoop_bb0_in(V_n,V_m,V_N,B): 0.55/0.54 * Chain [27]: 0 0.55/0.54 with precondition: [0>=V_n+1] 0.55/0.54 0.55/0.54 * Chain [26]: 0 0.55/0.54 with precondition: [0>=V_m+1] 0.55/0.54 0.55/0.54 * Chain [25]: 0 0.55/0.54 with precondition: [0>=V_N+1] 0.55/0.54 0.55/0.54 * Chain [24]: 0 0.55/0.54 with precondition: [V_n>=0,V_m>=0,V_N>=0] 0.55/0.54 0.55/0.54 * Chain [23]: 3*s(43)+1*s(50)+1*s(51)+2*s(52)+1*s(53)+1*s(54)+0 0.55/0.54 Such that:s(39) =< V_n 0.55/0.54 s(40) =< V_m 0.55/0.54 aux(17) =< V_N 0.55/0.54 s(43) =< s(39) 0.55/0.54 s(44) =< s(40) 0.55/0.54 s(45) =< s(43)*aux(17) 0.55/0.54 s(47) =< s(43)*s(40) 0.55/0.54 s(48) =< s(43)*s(44) 0.55/0.54 s(50) =< s(48) 0.55/0.54 s(51) =< s(48) 0.55/0.54 s(50) =< s(45) 0.55/0.54 s(52) =< s(45) 0.55/0.54 s(53) =< s(47) 0.55/0.54 s(54) =< s(47) 0.55/0.54 s(53) =< s(45) 0.55/0.54 0.55/0.54 with precondition: [V_n>=1,V_m>=0,V_N>=0] 0.55/0.54 0.55/0.54 0.55/0.54 #### Cost of chains of eval_nestedLoop_start(V_n,V_m,V_N,B): 0.55/0.54 * Chain [32]: 0 0.55/0.54 with precondition: [0>=V_n+1] 0.55/0.54 0.55/0.54 * Chain [31]: 0 0.55/0.54 with precondition: [0>=V_m+1] 0.55/0.54 0.55/0.54 * Chain [30]: 0 0.55/0.54 with precondition: [0>=V_N+1] 0.55/0.54 0.55/0.54 * Chain [29]: 0 0.55/0.54 with precondition: [V_n>=0,V_m>=0,V_N>=0] 0.55/0.54 0.55/0.54 * Chain [28]: 3*s(58)+1*s(63)+1*s(64)+2*s(65)+1*s(66)+1*s(67)+0 0.55/0.54 Such that:s(55) =< V_n 0.55/0.54 s(56) =< V_m 0.55/0.54 s(57) =< V_N 0.55/0.54 s(58) =< s(55) 0.55/0.54 s(59) =< s(56) 0.55/0.54 s(60) =< s(58)*s(57) 0.55/0.54 s(61) =< s(58)*s(56) 0.55/0.54 s(62) =< s(58)*s(59) 0.55/0.54 s(63) =< s(62) 0.55/0.54 s(64) =< s(62) 0.55/0.54 s(63) =< s(60) 0.55/0.54 s(65) =< s(60) 0.55/0.54 s(66) =< s(61) 0.55/0.54 s(67) =< s(61) 0.55/0.54 s(66) =< s(60) 0.55/0.54 0.55/0.54 with precondition: [V_n>=1,V_m>=0,V_N>=0] 0.55/0.54 0.55/0.54 0.55/0.54 Closed-form bounds of eval_nestedLoop_start(V_n,V_m,V_N,B): 0.55/0.54 ------------------------------------- 0.55/0.54 * Chain [32] with precondition: [0>=V_n+1] 0.55/0.54 - Upper bound: 0 0.55/0.54 - Complexity: constant 0.55/0.54 * Chain [31] with precondition: [0>=V_m+1] 0.55/0.54 - Upper bound: 0 0.55/0.54 - Complexity: constant 0.55/0.54 * Chain [30] with precondition: [0>=V_N+1] 0.55/0.54 - Upper bound: 0 0.55/0.54 - Complexity: constant 0.55/0.54 * Chain [29] with precondition: [V_n>=0,V_m>=0,V_N>=0] 0.55/0.54 - Upper bound: 0 0.55/0.54 - Complexity: constant 0.55/0.54 * Chain [28] with precondition: [V_n>=1,V_m>=0,V_N>=0] 0.55/0.54 - Upper bound: 4*V_n*V_m+3*V_n+2*V_n*V_N 0.55/0.54 - Complexity: n^2 0.55/0.54 0.55/0.54 ### Maximum cost of eval_nestedLoop_start(V_n,V_m,V_N,B): nat(V_n)*4*nat(V_m)+nat(V_n)*3+nat(V_n)*2*nat(V_N) 0.55/0.54 Asymptotic class: n^2 0.55/0.54 * Total analysis performed in 415 ms. 0.55/0.54 0.56/0.64 EOF