0.67/0.69 WORST_CASE(?,O(n^2)) 0.67/0.69 0.67/0.69 Preprocessing Cost Relations 0.67/0.69 ===================================== 0.67/0.69 0.67/0.69 #### Computed strongly connected components 0.67/0.69 0. recursive : [eval_terminatorbubble_10/9,eval_terminatorbubble_9/9,eval_terminatorbubble_bb2_in/9,eval_terminatorbubble_bb3_in/9,eval_terminatorbubble_bb4_in/9,eval_terminatorbubble_bb5_in/9] 0.67/0.69 1. recursive : [eval_terminatorbubble_bb1_in/11,eval_terminatorbubble_bb2_in_loop_cont/12,eval_terminatorbubble_bb6_in/11] 0.67/0.69 2. non_recursive : [eval_terminatorbubble_stop/6] 0.67/0.69 3. non_recursive : [eval_terminatorbubble_bb7_in/6] 0.67/0.69 4. non_recursive : [exit_location/1] 0.67/0.69 5. non_recursive : [eval_terminatorbubble_bb1_in_loop_cont/7] 0.67/0.69 6. non_recursive : [eval_terminatorbubble_3/6] 0.67/0.69 7. non_recursive : [eval_terminatorbubble_2/6] 0.67/0.69 8. non_recursive : [eval_terminatorbubble_1/6] 0.67/0.69 9. non_recursive : [eval_terminatorbubble_0/6] 0.67/0.69 10. non_recursive : [eval_terminatorbubble_bb0_in/6] 0.67/0.69 11. non_recursive : [eval_terminatorbubble_start/6] 0.67/0.69 0.67/0.69 #### Obtained direct recursion through partial evaluation 0.67/0.69 0. SCC is partially evaluated into eval_terminatorbubble_bb2_in/9 0.67/0.69 1. SCC is partially evaluated into eval_terminatorbubble_bb1_in/11 0.67/0.69 2. SCC is completely evaluated into other SCCs 0.67/0.69 3. SCC is completely evaluated into other SCCs 0.67/0.69 4. SCC is completely evaluated into other SCCs 0.67/0.69 5. SCC is partially evaluated into eval_terminatorbubble_bb1_in_loop_cont/7 0.67/0.69 6. SCC is partially evaluated into eval_terminatorbubble_3/6 0.67/0.69 7. SCC is completely evaluated into other SCCs 0.67/0.69 8. SCC is completely evaluated into other SCCs 0.67/0.69 9. SCC is completely evaluated into other SCCs 0.67/0.69 10. SCC is completely evaluated into other SCCs 0.67/0.69 11. SCC is partially evaluated into eval_terminatorbubble_start/6 0.67/0.69 0.67/0.69 Control-Flow Refinement of Cost Relations 0.67/0.69 ===================================== 0.67/0.69 0.67/0.69 ### Specialization of cost equations eval_terminatorbubble_bb2_in/9 0.67/0.69 * CE 17 is discarded (unfeasible) 0.67/0.69 * CE 18 is discarded (unfeasible) 0.67/0.69 * CE 14 is discarded (unfeasible) 0.67/0.69 * CE 20 is refined into CE [21] 0.67/0.69 * CE 19 is refined into CE [22] 0.67/0.69 * CE 16 is refined into CE [23] 0.67/0.69 * CE 15 is refined into CE [24] 0.67/0.69 0.67/0.69 0.67/0.69 ### Cost equations --> "Loop" of eval_terminatorbubble_bb2_in/9 0.67/0.69 * CEs [23] --> Loop 21 0.67/0.69 * CEs [24] --> Loop 22 0.67/0.69 * CEs [21] --> Loop 23 0.67/0.69 * CEs [22] --> Loop 24 0.67/0.69 0.67/0.69 ### Ranking functions of CR eval_terminatorbubble_bb2_in(V_11,V_b_0,V_j_0,V_size,V_t_0,B,C,D,E) 0.67/0.69 * RF of phase [21,22]: [V_b_0-V_j_0,-V_j_0+V_size] 0.67/0.69 0.67/0.69 #### Partial ranking functions of CR eval_terminatorbubble_bb2_in(V_11,V_b_0,V_j_0,V_size,V_t_0,B,C,D,E) 0.67/0.69 * Partial RF of phase [21,22]: 0.67/0.69 - RF of loop [21:1,22:1]: 0.67/0.69 V_b_0-V_j_0 0.67/0.69 -V_j_0+V_size 0.67/0.69 - RF of loop [22:1]: 0.67/0.69 V_b_0-V_t_0-1 0.67/0.69 V_size-V_t_0-1 0.67/0.69 0.67/0.69 0.67/0.69 ### Specialization of cost equations eval_terminatorbubble_bb1_in/11 0.67/0.69 * CE 5 is discarded (unfeasible) 0.67/0.69 * CE 7 is discarded (unfeasible) 0.67/0.69 * CE 6 is refined into CE [25,26] 0.67/0.69 * CE 10 is discarded (unfeasible) 0.67/0.69 * CE 9 is discarded (unfeasible) 0.67/0.69 * CE 8 is refined into CE [27,28] 0.67/0.69 * CE 11 is refined into CE [29] 0.67/0.69 * CE 4 is refined into CE [30] 0.67/0.69 0.67/0.69 0.67/0.69 ### Cost equations --> "Loop" of eval_terminatorbubble_bb1_in/11 0.67/0.69 * CEs [30] --> Loop 25 0.67/0.69 * CEs [26] --> Loop 26 0.67/0.69 * CEs [28] --> Loop 27 0.67/0.69 * CEs [27,29] --> Loop 28 0.67/0.69 * CEs [25] --> Loop 29 0.67/0.69 0.67/0.69 ### Ranking functions of CR eval_terminatorbubble_bb1_in(V_11,V_b_0,V_j_0,V_size,V_t_0,B,C,D,E,F,G) 0.67/0.69 * RF of phase [25]: [V_b_0-1] 0.67/0.69 0.67/0.69 #### Partial ranking functions of CR eval_terminatorbubble_bb1_in(V_11,V_b_0,V_j_0,V_size,V_t_0,B,C,D,E,F,G) 0.67/0.69 * Partial RF of phase [25]: 0.67/0.69 - RF of loop [25:1]: 0.67/0.69 V_b_0-1 0.67/0.69 0.67/0.69 0.67/0.69 ### Specialization of cost equations eval_terminatorbubble_bb1_in_loop_cont/7 0.67/0.69 * CE 12 is refined into CE [31] 0.67/0.69 * CE 13 is refined into CE [32] 0.67/0.69 0.67/0.69 0.67/0.69 ### Cost equations --> "Loop" of eval_terminatorbubble_bb1_in_loop_cont/7 0.67/0.69 * CEs [31] --> Loop 30 0.67/0.69 * CEs [32] --> Loop 31 0.67/0.69 0.67/0.69 ### Ranking functions of CR eval_terminatorbubble_bb1_in_loop_cont(A,B,C,D,E,F,G) 0.67/0.69 0.67/0.69 #### Partial ranking functions of CR eval_terminatorbubble_bb1_in_loop_cont(A,B,C,D,E,F,G) 0.67/0.69 0.67/0.69 0.67/0.69 ### Specialization of cost equations eval_terminatorbubble_3/6 0.67/0.69 * CE 3 is refined into CE [33,34,35,36,37,38,39] 0.67/0.69 * CE 2 is refined into CE [40] 0.67/0.69 0.67/0.69 0.67/0.69 ### Cost equations --> "Loop" of eval_terminatorbubble_3/6 0.67/0.69 * CEs [36,39] --> Loop 32 0.67/0.69 * CEs [35,37,38] --> Loop 33 0.67/0.69 * CEs [34] --> Loop 34 0.67/0.69 * CEs [40] --> Loop 35 0.67/0.69 * CEs [33] --> Loop 36 0.67/0.69 0.67/0.69 ### Ranking functions of CR eval_terminatorbubble_3(V_11,V_b_0,V_j_0,V_size,V_t_0,B) 0.67/0.69 0.67/0.69 #### Partial ranking functions of CR eval_terminatorbubble_3(V_11,V_b_0,V_j_0,V_size,V_t_0,B) 0.67/0.69 0.67/0.69 0.67/0.69 ### Specialization of cost equations eval_terminatorbubble_start/6 0.67/0.69 * CE 1 is refined into CE [41,42,43,44,45] 0.67/0.69 0.67/0.69 0.67/0.69 ### Cost equations --> "Loop" of eval_terminatorbubble_start/6 0.67/0.69 * CEs [45] --> Loop 37 0.67/0.69 * CEs [44] --> Loop 38 0.67/0.69 * CEs [43] --> Loop 39 0.67/0.69 * CEs [42] --> Loop 40 0.67/0.69 * CEs [41] --> Loop 41 0.67/0.69 0.67/0.69 ### Ranking functions of CR eval_terminatorbubble_start(V_11,V_b_0,V_j_0,V_size,V_t_0,B) 0.67/0.69 0.67/0.69 #### Partial ranking functions of CR eval_terminatorbubble_start(V_11,V_b_0,V_j_0,V_size,V_t_0,B) 0.67/0.69 0.67/0.69 0.67/0.69 Computing Bounds 0.67/0.69 ===================================== 0.67/0.69 0.67/0.69 #### Cost of chains of eval_terminatorbubble_bb2_in(V_11,V_b_0,V_j_0,V_size,V_t_0,B,C,D,E): 0.67/0.69 * Chain [[21,22],24]: 1*it(21)+1*it(22)+0 0.67/0.69 Such that:aux(3) =< -V_j_0+V_size 0.67/0.69 it(22) =< -V_t_0+E 0.67/0.69 aux(5) =< -V_j_0+D 0.67/0.69 it(21) =< aux(5) 0.67/0.69 it(22) =< aux(5) 0.67/0.69 it(21) =< aux(3) 0.67/0.69 it(22) =< aux(3) 0.67/0.69 0.67/0.69 with precondition: [B=2,V_b_0=D,V_t_0>=0,V_size>=V_b_0,V_b_0>=V_j_0+1,V_j_0>=V_t_0+1,E>=V_t_0,V_b_0>=E+1] 0.67/0.69 0.67/0.69 * Chain [[21,22],23]: 1*it(21)+1*it(22)+0 0.67/0.69 Such that:it(22) =< V_b_0-V_t_0 0.67/0.69 aux(3) =< -V_j_0+V_size 0.67/0.69 aux(6) =< V_b_0-V_j_0 0.67/0.69 it(21) =< aux(6) 0.67/0.69 it(22) =< aux(6) 0.67/0.69 it(21) =< aux(3) 0.67/0.69 it(22) =< aux(3) 0.67/0.69 0.67/0.69 with precondition: [B=3,V_t_0>=0,V_size>=V_b_0,V_b_0>=V_j_0+1,V_j_0>=V_t_0+1] 0.67/0.69 0.67/0.69 * Chain [24]: 0 0.67/0.69 with precondition: [B=2,C=V_11,V_j_0=V_b_0,V_j_0=D,V_t_0=E,V_t_0>=0,V_size>=V_j_0,V_j_0>=V_t_0+1] 0.67/0.69 0.67/0.69 * Chain [23]: 0 0.67/0.69 with precondition: [B=3,V_t_0>=0,V_size>=V_b_0,V_b_0>=V_j_0,V_j_0>=V_t_0+1] 0.67/0.69 0.67/0.69 0.67/0.69 #### Cost of chains of eval_terminatorbubble_bb1_in(V_11,V_b_0,V_j_0,V_size,V_t_0,B,C,D,E,F,G): 0.67/0.69 * Chain [[25],29]: 1*it(25)+1*s(9)+1*s(10)+0 0.67/0.69 Such that:aux(7) =< F 0.67/0.69 aux(11) =< V_b_0 0.67/0.69 it(25) =< aux(11) 0.67/0.69 aux(7) =< aux(11) 0.67/0.69 aux(9) =< aux(7)-1 0.67/0.69 aux(8) =< aux(7) 0.67/0.69 s(12) =< it(25)*aux(7) 0.67/0.69 s(9) =< it(25)*aux(9) 0.67/0.69 s(11) =< it(25)*aux(8) 0.67/0.69 s(10) =< s(12) 0.67/0.69 s(9) =< s(12) 0.67/0.69 s(10) =< s(11) 0.67/0.69 s(9) =< s(11) 0.67/0.69 0.67/0.69 with precondition: [B=4,D=1,E=1,G=0,V_size=F,V_b_0>=2,V_size>=V_b_0] 0.67/0.69 0.67/0.69 * Chain [[25],28]: 1*it(25)+1*s(9)+1*s(10)+0 0.67/0.69 Such that:aux(7) =< V_size 0.67/0.69 aux(12) =< V_b_0 0.67/0.69 it(25) =< aux(12) 0.67/0.69 aux(7) =< aux(12) 0.67/0.69 aux(9) =< aux(7)-1 0.67/0.69 aux(8) =< aux(7) 0.67/0.69 s(12) =< it(25)*aux(7) 0.67/0.69 s(9) =< it(25)*aux(9) 0.67/0.69 s(11) =< it(25)*aux(8) 0.67/0.69 s(10) =< s(12) 0.67/0.69 s(9) =< s(12) 0.67/0.69 s(10) =< s(11) 0.67/0.69 s(9) =< s(11) 0.67/0.69 0.67/0.69 with precondition: [B=3,V_b_0>=2,V_size>=V_b_0] 0.67/0.69 0.67/0.69 * Chain [[25],27]: 1*it(25)+1*s(9)+1*s(10)+2*s(13)+0 0.67/0.69 Such that:aux(14) =< V_b_0 0.67/0.69 aux(15) =< V_size 0.67/0.69 it(25) =< aux(14) 0.67/0.69 aux(7) =< aux(15) 0.67/0.69 s(13) =< aux(14) 0.67/0.69 s(13) =< aux(15) 0.67/0.69 aux(7) =< aux(14) 0.67/0.69 aux(9) =< aux(7)-1 0.67/0.69 aux(8) =< aux(7) 0.67/0.69 s(12) =< it(25)*aux(7) 0.67/0.69 s(9) =< it(25)*aux(9) 0.67/0.69 s(11) =< it(25)*aux(8) 0.67/0.69 s(10) =< s(12) 0.67/0.69 s(9) =< s(12) 0.67/0.69 s(10) =< s(11) 0.67/0.69 s(9) =< s(11) 0.67/0.69 0.67/0.69 with precondition: [B=3,V_b_0>=3,V_size>=V_b_0] 0.67/0.69 0.67/0.69 * Chain [[25],26]: 1*it(25)+1*s(9)+1*s(10)+1*s(20)+0 0.67/0.69 Such that:aux(10) =< V_b_0 0.67/0.69 it(25) =< V_b_0-D 0.67/0.69 s(19) =< D 0.67/0.69 aux(16) =< F 0.67/0.69 aux(7) =< aux(16) 0.67/0.69 s(20) =< s(19) 0.67/0.69 s(20) =< aux(16) 0.67/0.69 aux(7) =< aux(10) 0.67/0.69 it(25) =< aux(10) 0.67/0.69 aux(9) =< aux(7)-1 0.67/0.69 aux(8) =< aux(7) 0.67/0.69 s(12) =< it(25)*aux(7) 0.67/0.69 s(9) =< it(25)*aux(9) 0.67/0.69 s(11) =< it(25)*aux(8) 0.67/0.69 s(10) =< s(12) 0.67/0.69 s(9) =< s(12) 0.67/0.69 s(10) =< s(11) 0.67/0.69 s(9) =< s(11) 0.67/0.69 0.67/0.69 with precondition: [B=4,G=0,D=E,V_size=F,D>=2,V_size>=V_b_0,V_b_0>=D+1] 0.67/0.69 0.67/0.69 * Chain [29]: 0 0.67/0.69 with precondition: [V_b_0=1,B=4,D=1,E=1,G=0,C=V_11,V_size=F,V_size>=1] 0.67/0.69 0.67/0.69 * Chain [28]: 0 0.67/0.69 with precondition: [B=3,V_b_0>=1,V_size>=V_b_0] 0.67/0.69 0.67/0.69 * Chain [27]: 2*s(13)+0 0.67/0.69 Such that:s(14) =< V_size 0.67/0.69 aux(13) =< V_b_0 0.67/0.69 s(13) =< aux(13) 0.67/0.69 s(13) =< s(14) 0.67/0.69 0.67/0.69 with precondition: [B=3,V_b_0>=2,V_size>=V_b_0] 0.67/0.69 0.67/0.69 * Chain [26]: 1*s(20)+0 0.67/0.69 Such that:s(19) =< V_b_0 0.67/0.69 s(17) =< V_size 0.67/0.69 s(20) =< s(19) 0.67/0.69 s(20) =< s(17) 0.67/0.69 0.67/0.69 with precondition: [B=4,G=0,V_b_0=D,V_b_0=E,V_size=F,V_b_0>=2,V_size>=V_b_0] 0.67/0.69 0.67/0.69 0.67/0.69 #### Cost of chains of eval_terminatorbubble_bb1_in_loop_cont(A,B,C,D,E,F,G): 0.67/0.69 * Chain [31]: 0 0.67/0.69 with precondition: [A=3] 0.67/0.69 0.67/0.69 * Chain [30]: 0 0.67/0.69 with precondition: [A=4] 0.67/0.69 0.67/0.69 0.67/0.69 #### Cost of chains of eval_terminatorbubble_3(V_11,V_b_0,V_j_0,V_size,V_t_0,B): 0.67/0.69 * Chain [36]: 0 0.67/0.69 with precondition: [V_size=1] 0.67/0.69 0.67/0.69 * Chain [35]: 0 0.67/0.69 with precondition: [0>=V_size] 0.67/0.69 0.67/0.69 * Chain [34]: 0 0.67/0.69 with precondition: [V_size>=1] 0.67/0.69 0.67/0.69 * Chain [33]: 5*s(36)+2*s(41)+2*s(43)+0 0.67/0.69 Such that:aux(22) =< V_size 0.67/0.69 s(36) =< aux(22) 0.67/0.69 s(38) =< aux(22)-1 0.67/0.69 s(39) =< aux(22) 0.67/0.69 s(40) =< s(36)*aux(22) 0.67/0.69 s(41) =< s(36)*s(38) 0.67/0.69 s(42) =< s(36)*s(39) 0.67/0.69 s(43) =< s(40) 0.67/0.69 s(41) =< s(40) 0.67/0.69 s(43) =< s(42) 0.67/0.69 s(41) =< s(42) 0.67/0.69 0.67/0.69 with precondition: [V_size>=2] 0.67/0.69 0.67/0.69 * Chain [32]: 5*s(58)+2*s(64)+2*s(66)+0 0.67/0.69 Such that:aux(25) =< V_size 0.67/0.69 s(58) =< aux(25) 0.67/0.69 s(61) =< aux(25)-1 0.67/0.69 s(62) =< aux(25) 0.67/0.69 s(63) =< s(58)*aux(25) 0.67/0.69 s(64) =< s(58)*s(61) 0.67/0.69 s(65) =< s(58)*s(62) 0.67/0.69 s(66) =< s(63) 0.67/0.69 s(64) =< s(63) 0.67/0.69 s(66) =< s(65) 0.67/0.69 s(64) =< s(65) 0.67/0.69 0.67/0.69 with precondition: [V_size>=3] 0.67/0.69 0.67/0.69 0.67/0.69 #### Cost of chains of eval_terminatorbubble_start(V_11,V_b_0,V_j_0,V_size,V_t_0,B): 0.67/0.69 * Chain [41]: 0 0.67/0.69 with precondition: [V_size=1] 0.67/0.69 0.67/0.69 * Chain [40]: 0 0.67/0.69 with precondition: [0>=V_size] 0.67/0.69 0.67/0.69 * Chain [39]: 0 0.67/0.69 with precondition: [V_size>=1] 0.67/0.69 0.67/0.69 * Chain [38]: 5*s(80)+2*s(84)+2*s(86)+0 0.67/0.69 Such that:s(79) =< V_size 0.67/0.69 s(80) =< s(79) 0.67/0.69 s(81) =< s(79)-1 0.67/0.69 s(82) =< s(79) 0.67/0.69 s(83) =< s(80)*s(79) 0.67/0.69 s(84) =< s(80)*s(81) 0.67/0.69 s(85) =< s(80)*s(82) 0.67/0.69 s(86) =< s(83) 0.67/0.69 s(84) =< s(83) 0.67/0.69 s(86) =< s(85) 0.67/0.69 s(84) =< s(85) 0.67/0.69 0.67/0.69 with precondition: [V_size>=2] 0.67/0.69 0.67/0.69 * Chain [37]: 5*s(88)+2*s(92)+2*s(94)+0 0.67/0.69 Such that:s(87) =< V_size 0.67/0.69 s(88) =< s(87) 0.67/0.69 s(89) =< s(87)-1 0.67/0.69 s(90) =< s(87) 0.67/0.69 s(91) =< s(88)*s(87) 0.67/0.69 s(92) =< s(88)*s(89) 0.67/0.69 s(93) =< s(88)*s(90) 0.67/0.69 s(94) =< s(91) 0.67/0.69 s(92) =< s(91) 0.67/0.69 s(94) =< s(93) 0.67/0.69 s(92) =< s(93) 0.67/0.69 0.67/0.69 with precondition: [V_size>=3] 0.67/0.69 0.67/0.69 0.67/0.69 Closed-form bounds of eval_terminatorbubble_start(V_11,V_b_0,V_j_0,V_size,V_t_0,B): 0.67/0.69 ------------------------------------- 0.67/0.69 * Chain [41] with precondition: [V_size=1] 0.67/0.69 - Upper bound: 0 0.67/0.69 - Complexity: constant 0.67/0.69 * Chain [40] with precondition: [0>=V_size] 0.67/0.69 - Upper bound: 0 0.67/0.69 - Complexity: constant 0.67/0.69 * Chain [39] with precondition: [V_size>=1] 0.67/0.69 - Upper bound: 0 0.67/0.69 - Complexity: constant 0.67/0.69 * Chain [38] with precondition: [V_size>=2] 0.67/0.69 - Upper bound: 2*V_size*V_size+5*V_size+(V_size-1)*(2*V_size) 0.67/0.69 - Complexity: n^2 0.67/0.69 * Chain [37] with precondition: [V_size>=3] 0.67/0.69 - Upper bound: 2*V_size*V_size+5*V_size+(V_size-1)*(2*V_size) 0.67/0.69 - Complexity: n^2 0.67/0.69 0.67/0.69 ### Maximum cost of eval_terminatorbubble_start(V_11,V_b_0,V_j_0,V_size,V_t_0,B): nat(V_size)*2*nat(V_size)+nat(V_size)*5+nat(V_size)*2*nat(nat(V_size)+ -1) 0.67/0.69 Asymptotic class: n^2 0.67/0.69 * Total analysis performed in 571 ms. 0.67/0.69 0.70/0.79 EOF