0.73/0.72 WORST_CASE(?,O(n^1)) 0.73/0.72 0.73/0.72 Preprocessing Cost Relations 0.73/0.72 ===================================== 0.73/0.72 0.73/0.72 #### Computed strongly connected components 0.73/0.72 0. recursive : [eval_xnu_bb3_in/8,eval_xnu_bb4_in/8] 0.73/0.72 1. recursive : [eval_xnu_1/6,eval_xnu_2/7,eval_xnu_3/8,eval_xnu_4/9,eval_xnu_7/9,eval_xnu_8/10,eval_xnu_bb1_in/5,eval_xnu_bb2_in/5,eval_xnu_bb3_in_loop_cont/6,eval_xnu_bb5_in/9] 0.73/0.72 2. non_recursive : [eval_xnu_stop/1] 0.73/0.72 3. non_recursive : [eval_xnu_bb6_in/1] 0.73/0.72 4. non_recursive : [eval_xnu_bb1_in_loop_cont/2] 0.73/0.72 5. non_recursive : [eval_xnu_bb0_in/2] 0.73/0.72 6. non_recursive : [eval_xnu_start/2] 0.73/0.72 0.73/0.72 #### Obtained direct recursion through partial evaluation 0.73/0.72 0. SCC is partially evaluated into eval_xnu_bb3_in/8 0.73/0.72 1. SCC is partially evaluated into eval_xnu_bb1_in/5 0.73/0.72 2. SCC is completely evaluated into other SCCs 0.73/0.72 3. SCC is completely evaluated into other SCCs 0.73/0.72 4. SCC is completely evaluated into other SCCs 0.73/0.72 5. SCC is partially evaluated into eval_xnu_bb0_in/2 0.73/0.72 6. SCC is partially evaluated into eval_xnu_start/2 0.73/0.72 0.73/0.72 Control-Flow Refinement of Cost Relations 0.73/0.72 ===================================== 0.73/0.72 0.73/0.72 ### Specialization of cost equations eval_xnu_bb3_in/8 0.73/0.72 * CE 14 is refined into CE [15] 0.73/0.72 * CE 13 is refined into CE [16] 0.73/0.72 0.73/0.72 0.73/0.72 ### Cost equations --> "Loop" of eval_xnu_bb3_in/8 0.73/0.72 * CEs [16] --> Loop 9 0.73/0.72 * CEs [15] --> Loop 10 0.73/0.72 0.73/0.72 ### Ranking functions of CR eval_xnu_bb3_in(V_i_0,V_end_0,V_beg_0,V_2,V__end_0,V_4,V_k_0,B) 0.73/0.72 * RF of phase [9]: [V__end_0-V_k_0,V_i_0-V_k_0+1] 0.73/0.72 0.73/0.72 #### Partial ranking functions of CR eval_xnu_bb3_in(V_i_0,V_end_0,V_beg_0,V_2,V__end_0,V_4,V_k_0,B) 0.73/0.72 * Partial RF of phase [9]: 0.73/0.72 - RF of loop [9:1]: 0.73/0.72 V__end_0-V_k_0 0.73/0.72 V_i_0-V_k_0+1 0.73/0.72 0.73/0.72 0.73/0.72 ### Specialization of cost equations eval_xnu_bb1_in/5 0.73/0.72 * CE 12 is refined into CE [17] 0.73/0.72 * CE 4 is refined into CE [18] 0.73/0.72 * CE 5 is refined into CE [19] 0.73/0.72 * CE 6 is refined into CE [20] 0.73/0.72 * CE 7 is refined into CE [21] 0.73/0.72 * CE 8 is refined into CE [22,23] 0.73/0.72 * CE 9 is refined into CE [24] 0.73/0.72 * CE 10 is refined into CE [25] 0.73/0.72 * CE 11 is refined into CE [26,27] 0.73/0.72 * CE 3 is refined into CE [28] 0.73/0.72 0.73/0.72 0.73/0.72 ### Cost equations --> "Loop" of eval_xnu_bb1_in/5 0.73/0.72 * CEs [18] --> Loop 11 0.73/0.72 * CEs [23,27] --> Loop 12 0.73/0.72 * CEs [22,26] --> Loop 13 0.73/0.72 * CEs [20,21,24,25] --> Loop 14 0.73/0.72 * CEs [19] --> Loop 15 0.73/0.72 * CEs [28] --> Loop 16 0.73/0.72 * CEs [17] --> Loop 17 0.73/0.72 0.73/0.72 ### Ranking functions of CR eval_xnu_bb1_in(V_len,V_i_0,V_end_0,V_beg_0,B) 0.73/0.72 * RF of phase [11,12,13,14,15,16]: [V_len-V_i_0] 0.73/0.72 0.73/0.72 #### Partial ranking functions of CR eval_xnu_bb1_in(V_len,V_i_0,V_end_0,V_beg_0,B) 0.73/0.72 * Partial RF of phase [11,12,13,14,15,16]: 0.73/0.72 - RF of loop [11:1,12:1,13:1,14:1,15:1,16:1]: 0.73/0.72 V_len-V_i_0 0.73/0.72 - RF of loop [12:1]: 0.73/0.72 V_end_0-V_beg_0 depends on loops [16:1] 0.73/0.72 V_i_0-V_beg_0 depends on loops [11:1,16:1] 0.73/0.72 V_len/2-V_beg_0/2-1/2 0.73/0.72 - RF of loop [12:1,13:1,14:1,15:1,16:1]: 0.73/0.72 V_len-V_end_0 0.73/0.72 - RF of loop [13:1,14:1,15:1]: 0.73/0.72 V_len-V_beg_0 0.73/0.72 0.73/0.72 0.73/0.72 ### Specialization of cost equations eval_xnu_bb0_in/2 0.73/0.72 * CE 2 is refined into CE [29,30] 0.73/0.72 0.73/0.72 0.73/0.72 ### Cost equations --> "Loop" of eval_xnu_bb0_in/2 0.73/0.72 * CEs [30] --> Loop 18 0.73/0.72 * CEs [29] --> Loop 19 0.73/0.72 0.73/0.72 ### Ranking functions of CR eval_xnu_bb0_in(V_len,B) 0.73/0.72 0.73/0.72 #### Partial ranking functions of CR eval_xnu_bb0_in(V_len,B) 0.73/0.72 0.73/0.72 0.73/0.72 ### Specialization of cost equations eval_xnu_start/2 0.73/0.72 * CE 1 is refined into CE [31,32] 0.73/0.72 0.73/0.72 0.73/0.72 ### Cost equations --> "Loop" of eval_xnu_start/2 0.73/0.72 * CEs [32] --> Loop 20 0.73/0.72 * CEs [31] --> Loop 21 0.73/0.72 0.73/0.72 ### Ranking functions of CR eval_xnu_start(V_len,B) 0.73/0.72 0.73/0.72 #### Partial ranking functions of CR eval_xnu_start(V_len,B) 0.73/0.72 0.73/0.72 0.73/0.72 Computing Bounds 0.73/0.72 ===================================== 0.73/0.72 0.73/0.72 #### Cost of chains of eval_xnu_bb3_in(V_i_0,V_end_0,V_beg_0,V_2,V__end_0,V_4,V_k_0,B): 0.73/0.72 * Chain [[9],10]: 1*it(9)+0 0.73/0.72 Such that:it(9) =< V__end_0-V_k_0 0.73/0.72 0.73/0.72 with precondition: [B=2,V_beg_0>=0,V_i_0>=V_end_0,V__end_0>=V_end_0,V_end_0>=V_beg_0,V_k_0>=V_beg_0,V_i_0+1>=V__end_0,V__end_0>=V_k_0+1] 0.73/0.72 0.73/0.72 * Chain [10]: 0 0.73/0.72 with precondition: [B=2,V_k_0=V__end_0,V_beg_0>=0,V_i_0>=V_end_0,V_k_0>=V_end_0,V_end_0>=V_beg_0,V_i_0+1>=V_k_0] 0.73/0.72 0.73/0.72 0.73/0.72 #### Cost of chains of eval_xnu_bb1_in(V_len,V_i_0,V_end_0,V_beg_0,B): 0.73/0.72 * Chain [[11,12,13,14,15,16],17]: 1*it(11)+1*it(12)+3*it(13)+1*it(16)+2*s(11)+4*s(13)+0 0.73/0.72 Such that:aux(16) =< V_len 0.73/0.72 it(12) =< V_len/2-V_beg_0/2 0.73/0.72 aux(25) =< V_len-V_i_0 0.73/0.72 aux(26) =< V_len-V_end_0 0.73/0.72 aux(27) =< V_len-V_beg_0 0.73/0.72 aux(28) =< V_i_0-V_beg_0 0.73/0.72 aux(29) =< V_end_0-V_beg_0 0.73/0.72 aux(24) =< aux(27) 0.73/0.72 aux(8) =< aux(28) 0.73/0.72 aux(24) =< aux(28) 0.73/0.72 aux(8) =< aux(29) 0.73/0.72 aux(14) =< aux(16) 0.73/0.72 it(11) =< aux(25) 0.73/0.72 it(12) =< aux(25) 0.73/0.72 it(13) =< aux(25) 0.73/0.72 it(16) =< aux(25) 0.73/0.72 it(12) =< aux(26) 0.73/0.72 it(13) =< aux(26) 0.73/0.72 it(16) =< aux(26) 0.73/0.72 it(13) =< aux(27) 0.73/0.72 s(12) =< aux(27) 0.73/0.72 aux(14) =< aux(16) 0.73/0.72 aux(13) =< it(16)*aux(16) 0.73/0.72 aux(4) =< it(16)*aux(16) 0.73/0.72 s(12) =< it(16)+it(11)+aux(24) 0.73/0.72 s(12) =< it(16)+it(11)+aux(28) 0.73/0.72 it(12) =< it(16)+it(11)+aux(24) 0.73/0.72 it(12) =< it(16)+it(11)+aux(28) 0.73/0.72 aux(15) =< it(16)*aux(14) 0.73/0.72 aux(4) =< it(16)*aux(14) 0.73/0.72 aux(7) =< aux(13) 0.73/0.72 aux(7) =< aux(15) 0.73/0.72 it(12) =< aux(4)+aux(29) 0.73/0.72 it(12) =< aux(7)+aux(8) 0.73/0.72 s(12) =< it(12)*aux(27) 0.73/0.72 s(13) =< aux(27) 0.73/0.72 s(11) =< s(12) 0.73/0.72 0.73/0.72 with precondition: [B=3,V_beg_0>=0,V_len>=V_i_0+1,V_i_0>=V_end_0,V_end_0>=V_beg_0] 0.73/0.72 0.73/0.72 * Chain [17]: 0 0.73/0.72 with precondition: [B=3,V_beg_0>=0,V_i_0>=V_len,V_i_0>=V_end_0,V_end_0>=V_beg_0] 0.73/0.72 0.73/0.72 0.73/0.72 #### Cost of chains of eval_xnu_bb0_in(V_len,B): 0.73/0.72 * Chain [19]: 0 0.73/0.72 with precondition: [0>=V_len] 0.73/0.72 0.73/0.72 * Chain [18]: 1*s(16)+9*s(25)+2*s(34)+0 0.73/0.72 Such that:s(16) =< V_len/2 0.73/0.72 aux(31) =< V_len 0.73/0.72 s(24) =< aux(31) 0.73/0.72 s(25) =< aux(31) 0.73/0.72 s(16) =< aux(31) 0.73/0.72 s(28) =< aux(31) 0.73/0.72 s(24) =< aux(31) 0.73/0.72 s(29) =< s(25)*aux(31) 0.73/0.72 s(30) =< s(25)*aux(31) 0.73/0.72 s(28) =< s(25)+s(25) 0.73/0.72 s(28) =< s(25)+s(25) 0.73/0.72 s(16) =< s(25)+s(25) 0.73/0.72 s(16) =< s(25)+s(25) 0.73/0.72 s(31) =< s(25)*s(24) 0.73/0.72 s(30) =< s(25)*s(24) 0.73/0.72 s(32) =< s(29) 0.73/0.72 s(32) =< s(31) 0.73/0.72 s(16) =< s(30) 0.73/0.72 s(16) =< s(32) 0.73/0.72 s(28) =< s(16)*aux(31) 0.73/0.72 s(34) =< s(28) 0.73/0.72 0.73/0.72 with precondition: [V_len>=1] 0.73/0.72 0.73/0.72 0.73/0.72 #### Cost of chains of eval_xnu_start(V_len,B): 0.73/0.72 * Chain [21]: 0 0.73/0.72 with precondition: [0>=V_len] 0.73/0.72 0.73/0.72 * Chain [20]: 1*s(35)+9*s(38)+2*s(44)+0 0.73/0.72 Such that:s(36) =< V_len 0.73/0.72 s(35) =< V_len/2 0.73/0.72 s(37) =< s(36) 0.73/0.72 s(38) =< s(36) 0.73/0.72 s(35) =< s(36) 0.73/0.72 s(39) =< s(36) 0.73/0.72 s(37) =< s(36) 0.73/0.72 s(40) =< s(38)*s(36) 0.73/0.72 s(41) =< s(38)*s(36) 0.73/0.72 s(39) =< s(38)+s(38) 0.73/0.72 s(39) =< s(38)+s(38) 0.73/0.72 s(35) =< s(38)+s(38) 0.73/0.72 s(35) =< s(38)+s(38) 0.73/0.72 s(42) =< s(38)*s(37) 0.73/0.72 s(41) =< s(38)*s(37) 0.73/0.72 s(43) =< s(40) 0.73/0.72 s(43) =< s(42) 0.73/0.72 s(35) =< s(41) 0.73/0.72 s(35) =< s(43) 0.73/0.72 s(39) =< s(35)*s(36) 0.73/0.72 s(44) =< s(39) 0.73/0.72 0.73/0.72 with precondition: [V_len>=1] 0.73/0.72 0.73/0.72 0.73/0.72 Closed-form bounds of eval_xnu_start(V_len,B): 0.73/0.72 ------------------------------------- 0.73/0.72 * Chain [21] with precondition: [0>=V_len] 0.73/0.72 - Upper bound: 0 0.73/0.72 - Complexity: constant 0.73/0.72 * Chain [20] with precondition: [V_len>=1] 0.73/0.72 - Upper bound: 23/2*V_len 0.73/0.72 - Complexity: n 0.73/0.72 0.73/0.72 ### Maximum cost of eval_xnu_start(V_len,B): nat(V_len)*11+nat(V_len/2) 0.73/0.72 Asymptotic class: n 0.73/0.72 * Total analysis performed in 565 ms. 0.73/0.72 0.74/0.82 EOF