0.05/0.51 WORST_CASE(?,O(n^2)) 0.05/0.51 0.05/0.51 Preprocessing Cost Relations 0.05/0.51 ===================================== 0.05/0.51 0.05/0.51 #### Computed strongly connected components 0.05/0.51 0. recursive : [eval_foo_2/4,eval_foo_3/5,eval_foo_bb3_in/4,eval_foo_bb4_in/4,eval_foo_bb5_in/5] 0.05/0.51 1. recursive : [eval_foo_0/4,eval_foo_1/5,eval_foo__critedge_in/6,eval_foo_bb1_in/4,eval_foo_bb2_in/4,eval_foo_bb3_in_loop_cont/7,eval_foo_bb6_in/7] 0.05/0.51 2. non_recursive : [eval_foo_stop/1] 0.05/0.51 3. non_recursive : [eval_foo_bb7_in/1] 0.05/0.51 4. non_recursive : [eval_foo_bb1_in_loop_cont/2] 0.05/0.51 5. non_recursive : [eval_foo_bb0_in/2] 0.05/0.51 6. non_recursive : [eval_foo_start/4] 0.05/0.51 0.05/0.51 #### Obtained direct recursion through partial evaluation 0.05/0.51 0. SCC is partially evaluated into eval_foo_bb3_in/4 0.05/0.51 1. SCC is partially evaluated into eval_foo_bb1_in/4 0.05/0.51 2. SCC is completely evaluated into other SCCs 0.05/0.51 3. SCC is completely evaluated into other SCCs 0.05/0.51 4. SCC is completely evaluated into other SCCs 0.05/0.51 5. SCC is partially evaluated into eval_foo_bb0_in/2 0.05/0.51 6. SCC is partially evaluated into eval_foo_start/4 0.05/0.51 0.05/0.51 Control-Flow Refinement of Cost Relations 0.05/0.51 ===================================== 0.05/0.51 0.05/0.51 ### Specialization of cost equations eval_foo_bb3_in/4 0.05/0.51 * CE 7 is refined into CE [10] 0.05/0.51 * CE 9 is refined into CE [11] 0.05/0.51 * CE 8 is refined into CE [12] 0.05/0.51 0.05/0.51 0.05/0.51 ### Cost equations --> "Loop" of eval_foo_bb3_in/4 0.05/0.51 * CEs [12] --> Loop 10 0.05/0.51 * CEs [10] --> Loop 11 0.05/0.51 * CEs [11] --> Loop 12 0.05/0.51 0.05/0.51 ### Ranking functions of CR eval_foo_bb3_in(V_m,V__12,B,C) 0.05/0.51 * RF of phase [10]: [V_m-V__12+1] 0.05/0.51 0.05/0.51 #### Partial ranking functions of CR eval_foo_bb3_in(V_m,V__12,B,C) 0.05/0.51 * Partial RF of phase [10]: 0.05/0.51 - RF of loop [10:1]: 0.05/0.51 V_m-V__12+1 0.05/0.51 0.05/0.51 0.05/0.51 ### Specialization of cost equations eval_foo_bb1_in/4 0.05/0.51 * CE 5 is refined into CE [13] 0.05/0.51 * CE 6 is refined into CE [14] 0.05/0.51 * CE 4 is refined into CE [15,16,17,18] 0.05/0.51 * CE 3 is refined into CE [19] 0.05/0.51 0.05/0.51 0.05/0.51 ### Cost equations --> "Loop" of eval_foo_bb1_in/4 0.05/0.51 * CEs [16] --> Loop 13 0.05/0.51 * CEs [17] --> Loop 14 0.05/0.51 * CEs [19] --> Loop 15 0.05/0.51 * CEs [18] --> Loop 16 0.05/0.51 * CEs [15] --> Loop 17 0.05/0.51 * CEs [13] --> Loop 18 0.05/0.51 * CEs [14] --> Loop 19 0.05/0.51 0.05/0.51 ### Ranking functions of CR eval_foo_bb1_in(V_m,V__01,V__0,B) 0.05/0.51 0.05/0.51 #### Partial ranking functions of CR eval_foo_bb1_in(V_m,V__01,V__0,B) 0.05/0.51 * Partial RF of phase [13,14,15,16,17]: 0.05/0.51 - RF of loop [13:1]: 0.05/0.51 V__01 depends on loops [16:1,17:1] 0.05/0.51 -V_m+V__01 depends on loops [16:1,17:1] 0.05/0.51 - RF of loop [13:1,14:1,16:1,17:1]: 0.05/0.51 V__0+1 0.05/0.51 - RF of loop [14:1,15:1]: 0.05/0.51 V__01+1 depends on loops [16:1,17:1] 0.05/0.51 0.05/0.51 0.05/0.51 ### Specialization of cost equations eval_foo_bb0_in/2 0.05/0.51 * CE 2 is refined into CE [20,21] 0.05/0.51 0.05/0.51 0.05/0.51 ### Cost equations --> "Loop" of eval_foo_bb0_in/2 0.05/0.51 * CEs [21] --> Loop 20 0.05/0.51 * CEs [20] --> Loop 21 0.05/0.51 0.05/0.51 ### Ranking functions of CR eval_foo_bb0_in(V_m,B) 0.05/0.51 0.05/0.51 #### Partial ranking functions of CR eval_foo_bb0_in(V_m,B) 0.05/0.51 0.05/0.51 0.05/0.51 ### Specialization of cost equations eval_foo_start/4 0.05/0.51 * CE 1 is refined into CE [22,23] 0.05/0.51 0.05/0.51 0.05/0.51 ### Cost equations --> "Loop" of eval_foo_start/4 0.05/0.51 * CEs [23] --> Loop 22 0.05/0.51 * CEs [22] --> Loop 23 0.05/0.51 0.05/0.51 ### Ranking functions of CR eval_foo_start(V_x,V_y,V_m,B) 0.05/0.51 0.05/0.51 #### Partial ranking functions of CR eval_foo_start(V_x,V_y,V_m,B) 0.05/0.51 0.05/0.51 0.05/0.51 Computing Bounds 0.05/0.51 ===================================== 0.05/0.51 0.05/0.51 #### Cost of chains of eval_foo_bb3_in(V_m,V__12,B,C): 0.05/0.51 * Chain [[10],12]: 1*it(10)+0 0.05/0.51 Such that:it(10) =< -V__12+C 0.05/0.51 0.05/0.51 with precondition: [B=2,V_m+1=C,V__12>=0,V_m>=V__12] 0.05/0.51 0.05/0.51 * Chain [[10],11]: 1*it(10)+0 0.05/0.51 Such that:it(10) =< -V__12+C 0.05/0.51 0.05/0.51 with precondition: [B=2,V__12>=0,C>=V__12+1,V_m>=C] 0.05/0.51 0.05/0.51 * Chain [12]: 0 0.05/0.51 with precondition: [B=2,V__12=C,V_m>=0,V__12>=V_m+1] 0.05/0.51 0.05/0.51 * Chain [11]: 0 0.05/0.51 with precondition: [B=2,V__12=C,V__12>=0,V_m>=V__12] 0.05/0.51 0.05/0.51 0.05/0.51 #### Cost of chains of eval_foo_bb1_in(V_m,V__01,V__0,B): 0.05/0.51 * Chain [[13,14,15,16,17],19]: 2*it(13)+1*it(15)+2*it(16)+1*s(5)+1*s(6)+0 0.05/0.51 Such that:aux(40) =< V_m 0.05/0.51 aux(29) =< V_m-V__01+V__0+1 0.05/0.51 aux(41) =< -V__01+V__0 0.05/0.51 aux(41) =< V__0 0.05/0.51 aux(46) =< V__01+1 0.05/0.51 aux(47) =< V__0+1 0.05/0.51 it(13) =< aux(47) 0.05/0.51 it(16) =< aux(47) 0.05/0.51 aux(31) =< aux(40)+1 0.05/0.51 aux(25) =< aux(40) 0.05/0.51 aux(22) =< it(16)*aux(40) 0.05/0.51 s(5) =< it(16)*aux(40) 0.05/0.51 aux(26) =< it(16)*aux(25) 0.05/0.51 aux(7) =< aux(22) 0.05/0.51 aux(7) =< aux(26) 0.05/0.51 aux(33) =< it(16)*aux(31) 0.05/0.51 s(6) =< it(16)*aux(31) 0.05/0.51 it(13) =< aux(33)+aux(7)+aux(46) 0.05/0.51 it(15) =< aux(33)+aux(7)+aux(46) 0.05/0.51 s(6) =< it(15)+aux(41) 0.05/0.51 s(6) =< it(15)+aux(29) 0.05/0.51 0.05/0.51 with precondition: [B=3,V__01>=0,V__0>=0,V_m>=V__0] 0.05/0.51 0.05/0.51 * Chain [[13,14,15,16,17],18]: 2*it(13)+1*it(15)+2*it(16)+1*s(5)+1*s(6)+0 0.05/0.51 Such that:aux(40) =< V_m 0.05/0.51 aux(29) =< V_m-V__01+V__0+1 0.05/0.51 aux(41) =< V_m+V__0+1 0.05/0.51 aux(48) =< V__01+1 0.05/0.51 aux(49) =< V__0+1 0.05/0.51 it(13) =< aux(49) 0.05/0.51 it(16) =< aux(49) 0.05/0.51 aux(31) =< aux(40)+1 0.05/0.51 aux(25) =< aux(40) 0.05/0.51 aux(22) =< it(16)*aux(40) 0.05/0.51 s(5) =< it(16)*aux(40) 0.05/0.51 aux(26) =< it(16)*aux(25) 0.05/0.51 aux(7) =< aux(22) 0.05/0.51 aux(7) =< aux(26) 0.05/0.51 aux(33) =< it(16)*aux(31) 0.05/0.51 s(6) =< it(16)*aux(31) 0.05/0.51 it(13) =< aux(33)+aux(7)+aux(48) 0.05/0.51 it(15) =< aux(33)+aux(7)+aux(48) 0.05/0.51 s(6) =< it(15)+aux(41) 0.05/0.51 s(6) =< it(15)+aux(29) 0.05/0.51 0.05/0.51 with precondition: [B=3,V__01>=0,V__0>=0,V_m>=V__0] 0.05/0.51 0.05/0.51 * Chain [18]: 0 0.05/0.51 with precondition: [B=3,0>=V__0+1,V__01+1>=0,V_m>=V__0] 0.05/0.51 0.05/0.51 0.05/0.51 #### Cost of chains of eval_foo_bb0_in(V_m,B): 0.05/0.51 * Chain [21]: 0 0.05/0.51 with precondition: [0>=V_m+1] 0.05/0.51 0.05/0.51 * Chain [20]: 4*s(45)+4*s(46)+2*s(50)+1*s(54)+2*s(55)+1*s(56)+0 0.05/0.51 Such that:s(43) =< 1 0.05/0.51 s(44) =< V_m+1 0.05/0.51 aux(54) =< V_m 0.05/0.51 aux(55) =< 2*V_m+1 0.05/0.51 s(45) =< s(44) 0.05/0.51 s(46) =< s(44) 0.05/0.51 s(47) =< aux(54)+1 0.05/0.51 s(48) =< aux(54) 0.05/0.51 s(49) =< s(46)*aux(54) 0.05/0.51 s(50) =< s(46)*aux(54) 0.05/0.51 s(51) =< s(46)*s(48) 0.05/0.51 s(52) =< s(49) 0.05/0.51 s(52) =< s(51) 0.05/0.51 s(53) =< s(46)*s(47) 0.05/0.51 s(54) =< s(46)*s(47) 0.05/0.51 s(45) =< s(53)+s(52)+s(43) 0.05/0.51 s(55) =< s(53)+s(52)+s(43) 0.05/0.51 s(54) =< s(55)+aux(55) 0.05/0.51 s(56) =< s(46)*s(47) 0.05/0.51 s(56) =< s(55)+aux(54) 0.05/0.51 s(56) =< s(55)+aux(55) 0.05/0.51 0.05/0.51 with precondition: [V_m>=0] 0.05/0.51 0.05/0.51 0.05/0.51 #### Cost of chains of eval_foo_start(V_x,V_y,V_m,B): 0.05/0.51 * Chain [23]: 0 0.05/0.51 with precondition: [0>=V_m+1] 0.05/0.51 0.05/0.51 * Chain [22]: 4*s(61)+4*s(62)+2*s(66)+1*s(70)+2*s(71)+1*s(72)+0 0.05/0.51 Such that:s(57) =< 1 0.05/0.51 s(59) =< V_m 0.05/0.51 s(58) =< V_m+1 0.05/0.51 s(60) =< 2*V_m+1 0.05/0.51 s(61) =< s(58) 0.05/0.51 s(62) =< s(58) 0.05/0.51 s(63) =< s(59)+1 0.05/0.51 s(64) =< s(59) 0.05/0.51 s(65) =< s(62)*s(59) 0.05/0.51 s(66) =< s(62)*s(59) 0.05/0.51 s(67) =< s(62)*s(64) 0.05/0.51 s(68) =< s(65) 0.05/0.51 s(68) =< s(67) 0.05/0.51 s(69) =< s(62)*s(63) 0.05/0.51 s(70) =< s(62)*s(63) 0.05/0.51 s(61) =< s(69)+s(68)+s(57) 0.05/0.51 s(71) =< s(69)+s(68)+s(57) 0.05/0.51 s(70) =< s(71)+s(60) 0.05/0.51 s(72) =< s(62)*s(63) 0.05/0.51 s(72) =< s(71)+s(59) 0.05/0.51 s(72) =< s(71)+s(60) 0.05/0.51 0.05/0.51 with precondition: [V_m>=0] 0.05/0.51 0.05/0.51 0.05/0.51 Closed-form bounds of eval_foo_start(V_x,V_y,V_m,B): 0.05/0.51 ------------------------------------- 0.05/0.51 * Chain [23] with precondition: [0>=V_m+1] 0.05/0.51 - Upper bound: 0 0.05/0.51 - Complexity: constant 0.05/0.51 * Chain [22] with precondition: [V_m>=0] 0.05/0.51 - Upper bound: (V_m+1)*(8*V_m)+2+(12*V_m+12) 0.05/0.51 - Complexity: n^2 0.05/0.51 0.05/0.51 ### Maximum cost of eval_foo_start(V_x,V_y,V_m,B): nat(V_m)*8*nat(V_m+1)+2+nat(V_m+1)*12 0.05/0.51 Asymptotic class: n^2 0.05/0.51 * Total analysis performed in 383 ms. 0.05/0.51 0.50/0.61 EOF