0.05/0.36 WORST_CASE(?,O(n^2)) 0.05/0.36 0.05/0.36 Preprocessing Cost Relations 0.05/0.36 ===================================== 0.05/0.36 0.05/0.36 #### Computed strongly connected components 0.05/0.36 0. recursive : [eval_set_color_ht_extracted_bb4_in/3] 0.05/0.36 1. recursive : [eval_set_color_ht_extracted_bb2_in/3,eval_set_color_ht_extracted_bb3_in/3,eval_set_color_ht_extracted_bb4_in_loop_cont/4] 0.05/0.36 2. recursive : [eval_set_color_ht_extracted_bb1_in/3,eval_set_color_ht_extracted_bb2_in_loop_cont/6,eval_set_color_ht_extracted_bb5_in/5] 0.05/0.36 3. non_recursive : [eval_set_color_ht_extracted_stop/1] 0.05/0.36 4. non_recursive : [eval_set_color_ht_extracted_bb6_in/1] 0.05/0.36 5. non_recursive : [eval_set_color_ht_extracted_bb1_in_loop_cont/2] 0.05/0.36 6. non_recursive : [eval_set_color_ht_extracted_bb0_in/3] 0.05/0.36 7. non_recursive : [eval_set_color_ht_extracted_start/3] 0.05/0.36 0.05/0.36 #### Obtained direct recursion through partial evaluation 0.05/0.36 0. SCC is partially evaluated into eval_set_color_ht_extracted_bb4_in/3 0.05/0.36 1. SCC is partially evaluated into eval_set_color_ht_extracted_bb2_in/3 0.05/0.36 2. SCC is partially evaluated into eval_set_color_ht_extracted_bb1_in/3 0.05/0.36 3. SCC is completely evaluated into other SCCs 0.05/0.36 4. SCC is completely evaluated into other SCCs 0.05/0.36 5. SCC is completely evaluated into other SCCs 0.05/0.36 6. SCC is partially evaluated into eval_set_color_ht_extracted_bb0_in/3 0.05/0.36 7. SCC is partially evaluated into eval_set_color_ht_extracted_start/3 0.05/0.36 0.05/0.36 Control-Flow Refinement of Cost Relations 0.05/0.36 ===================================== 0.05/0.36 0.05/0.36 ### Specialization of cost equations eval_set_color_ht_extracted_bb4_in/3 0.05/0.36 * CE 9 is refined into CE [10] 0.05/0.36 * CE 8 is refined into CE [11] 0.05/0.36 0.05/0.36 0.05/0.36 ### Cost equations --> "Loop" of eval_set_color_ht_extracted_bb4_in/3 0.05/0.36 * CEs [11] --> Loop 10 0.05/0.36 * CEs [10] --> Loop 11 0.05/0.36 0.05/0.36 ### Ranking functions of CR eval_set_color_ht_extracted_bb4_in(V_x_0,V_i_0,B) 0.05/0.36 * RF of phase [10]: [V_i_0] 0.05/0.36 0.05/0.36 #### Partial ranking functions of CR eval_set_color_ht_extracted_bb4_in(V_x_0,V_i_0,B) 0.05/0.36 * Partial RF of phase [10]: 0.05/0.36 - RF of loop [10:1]: 0.05/0.36 V_i_0 0.05/0.36 0.05/0.36 0.05/0.36 ### Specialization of cost equations eval_set_color_ht_extracted_bb2_in/3 0.05/0.36 * CE 7 is refined into CE [12] 0.05/0.36 * CE 6 is refined into CE [13] 0.05/0.36 * CE 5 is refined into CE [14] 0.05/0.36 0.05/0.36 0.05/0.36 ### Cost equations --> "Loop" of eval_set_color_ht_extracted_bb2_in/3 0.05/0.36 * CEs [13] --> Loop 12 0.05/0.36 * CEs [14] --> Loop 13 0.05/0.36 * CEs [12] --> Loop 14 0.05/0.36 0.05/0.36 ### Ranking functions of CR eval_set_color_ht_extracted_bb2_in(V_x_0,B,C) 0.05/0.36 * RF of phase [12]: [V_x_0-7] 0.05/0.36 0.05/0.36 #### Partial ranking functions of CR eval_set_color_ht_extracted_bb2_in(V_x_0,B,C) 0.05/0.36 * Partial RF of phase [12]: 0.05/0.36 - RF of loop [12:1]: 0.05/0.36 V_x_0-7 0.05/0.36 0.05/0.36 0.05/0.36 ### Specialization of cost equations eval_set_color_ht_extracted_bb1_in/3 0.05/0.36 * CE 4 is refined into CE [15,16,17,18] 0.05/0.36 * CE 3 is refined into CE [19,20,21,22] 0.05/0.36 0.05/0.36 0.05/0.36 ### Cost equations --> "Loop" of eval_set_color_ht_extracted_bb1_in/3 0.05/0.36 * CEs [21] --> Loop 15 0.05/0.36 * CEs [20] --> Loop 16 0.05/0.36 * CEs [22] --> Loop 17 0.05/0.36 * CEs [19] --> Loop 18 0.05/0.36 * CEs [17] --> Loop 19 0.05/0.36 * CEs [16] --> Loop 20 0.05/0.36 * CEs [18] --> Loop 21 0.05/0.36 * CEs [15] --> Loop 22 0.05/0.36 0.05/0.36 ### Ranking functions of CR eval_set_color_ht_extracted_bb1_in(V_w,V_y_0,B) 0.05/0.36 * RF of phase [15,16]: [V_y_0-1] 0.05/0.36 * RF of phase [17]: [V_y_0-1] 0.05/0.36 * RF of phase [18]: [V_y_0-1] 0.05/0.36 0.05/0.36 #### Partial ranking functions of CR eval_set_color_ht_extracted_bb1_in(V_w,V_y_0,B) 0.05/0.36 * Partial RF of phase [15,16]: 0.05/0.36 - RF of loop [15:1,16:1]: 0.05/0.36 V_y_0-1 0.05/0.36 * Partial RF of phase [17]: 0.05/0.36 - RF of loop [17:1]: 0.05/0.36 V_y_0-1 0.05/0.36 * Partial RF of phase [18]: 0.05/0.36 - RF of loop [18:1]: 0.05/0.36 V_y_0-1 0.05/0.36 0.05/0.36 0.05/0.36 ### Specialization of cost equations eval_set_color_ht_extracted_bb0_in/3 0.05/0.36 * CE 2 is refined into CE [23,24,25,26,27,28,29,30] 0.05/0.36 0.05/0.36 0.05/0.36 ### Cost equations --> "Loop" of eval_set_color_ht_extracted_bb0_in/3 0.05/0.36 * CEs [30] --> Loop 23 0.05/0.36 * CEs [29] --> Loop 24 0.05/0.36 * CEs [26] --> Loop 25 0.05/0.36 * CEs [24] --> Loop 26 0.05/0.36 * CEs [28] --> Loop 27 0.05/0.36 * CEs [27] --> Loop 28 0.05/0.36 * CEs [25] --> Loop 29 0.05/0.36 * CEs [23] --> Loop 30 0.05/0.36 0.05/0.36 ### Ranking functions of CR eval_set_color_ht_extracted_bb0_in(V_h,V_w,B) 0.05/0.36 0.05/0.36 #### Partial ranking functions of CR eval_set_color_ht_extracted_bb0_in(V_h,V_w,B) 0.05/0.36 0.05/0.36 0.05/0.36 ### Specialization of cost equations eval_set_color_ht_extracted_start/3 0.05/0.36 * CE 1 is refined into CE [31,32,33,34,35,36,37,38] 0.05/0.36 0.05/0.36 0.05/0.36 ### Cost equations --> "Loop" of eval_set_color_ht_extracted_start/3 0.05/0.36 * CEs [38] --> Loop 31 0.05/0.36 * CEs [37] --> Loop 32 0.05/0.36 * CEs [36] --> Loop 33 0.05/0.36 * CEs [35] --> Loop 34 0.05/0.36 * CEs [34] --> Loop 35 0.05/0.36 * CEs [33] --> Loop 36 0.05/0.36 * CEs [32] --> Loop 37 0.05/0.36 * CEs [31] --> Loop 38 0.05/0.36 0.05/0.36 ### Ranking functions of CR eval_set_color_ht_extracted_start(V_h,V_w,B) 0.05/0.36 0.05/0.36 #### Partial ranking functions of CR eval_set_color_ht_extracted_start(V_h,V_w,B) 0.05/0.36 0.05/0.36 0.05/0.36 Computing Bounds 0.05/0.36 ===================================== 0.05/0.36 0.05/0.36 #### Cost of chains of eval_set_color_ht_extracted_bb4_in(V_x_0,V_i_0,B): 0.05/0.36 * Chain [[10],11]: 1*it(10)+0 0.05/0.36 Such that:it(10) =< V_i_0 0.05/0.36 0.05/0.36 with precondition: [B=2,8>=V_i_0,V_i_0>=1,V_x_0>=V_i_0] 0.05/0.36 0.05/0.36 0.05/0.36 #### Cost of chains of eval_set_color_ht_extracted_bb2_in(V_x_0,B,C): 0.05/0.36 * Chain [[12],14]: 1*it(12)+1*s(3)+0 0.05/0.36 Such that:aux(4) =< V_x_0 0.05/0.36 it(12) =< aux(4) 0.05/0.36 s(3) =< aux(4)*8 0.05/0.36 0.05/0.36 with precondition: [B=3,C=0,V_x_0>=8] 0.05/0.36 0.05/0.36 * Chain [[12],13,14]: 1*it(12)+1*s(3)+1*s(4)+1 0.05/0.36 Such that:s(4) =< 7 0.05/0.36 aux(5) =< V_x_0 0.05/0.36 s(4) =< aux(5) 0.05/0.36 it(12) =< aux(5) 0.05/0.36 s(3) =< aux(5)*8 0.05/0.36 0.05/0.36 with precondition: [B=3,C=0,V_x_0>=9] 0.05/0.36 0.05/0.36 * Chain [14]: 0 0.05/0.36 with precondition: [B=3,V_x_0=C,0>=V_x_0] 0.05/0.36 0.05/0.36 * Chain [13,14]: 1*s(4)+1 0.05/0.36 Such that:s(4) =< V_x_0 0.05/0.36 0.05/0.36 with precondition: [B=3,C=0,7>=V_x_0,V_x_0>=1] 0.05/0.36 0.05/0.36 0.05/0.36 #### Cost of chains of eval_set_color_ht_extracted_bb1_in(V_w,V_y_0,B): 0.05/0.36 * Chain [[18],22]: 2*it(18)+1*s(5)+1*s(8)+1 0.05/0.36 Such that:s(5) =< V_w 0.05/0.36 it(18) =< V_y_0 0.05/0.36 s(8) =< 7*V_y_0 0.05/0.36 0.05/0.36 with precondition: [B=4,7>=V_w,V_w>=1,V_y_0>=2] 0.05/0.36 0.05/0.36 * Chain [[17],21]: 1*it(17)+0 0.05/0.36 Such that:it(17) =< V_y_0 0.05/0.36 0.05/0.36 with precondition: [B=4,0>=V_w,V_y_0>=2] 0.05/0.36 0.05/0.36 * Chain [[15,16],20]: 3*it(15)+1*s(10)+1*s(11)+1*s(26)+1*s(27)+1*s(28)+1*s(30)+1*s(31)+0 0.05/0.36 Such that:aux(11) =< V_w 0.05/0.36 aux(12) =< V_y_0 0.05/0.36 s(10) =< aux(11) 0.05/0.36 s(11) =< aux(11)*8 0.05/0.36 it(15) =< aux(12) 0.05/0.36 aux(8) =< aux(11) 0.05/0.36 s(29) =< it(15)*aux(11) 0.05/0.36 s(26) =< aux(12)*7 0.05/0.36 s(32) =< it(15)*aux(8) 0.05/0.36 s(30) =< s(32) 0.05/0.36 s(31) =< s(32)*8 0.05/0.36 s(26) =< s(29) 0.05/0.36 s(27) =< s(29) 0.05/0.36 s(28) =< s(29)*8 0.05/0.36 0.05/0.36 with precondition: [B=4,V_w>=8,V_y_0>=2] 0.05/0.36 0.05/0.36 * Chain [[15,16],19]: 3*it(15)+1*s(26)+1*s(27)+1*s(28)+1*s(30)+1*s(31)+1*s(33)+1*s(35)+1*s(36)+1 0.05/0.36 Such that:s(33) =< 7 0.05/0.36 aux(13) =< V_w 0.05/0.36 aux(14) =< V_y_0 0.05/0.36 s(33) =< aux(13) 0.05/0.36 s(35) =< aux(13) 0.05/0.36 s(36) =< aux(13)*8 0.05/0.36 it(15) =< aux(14) 0.05/0.36 aux(8) =< aux(13) 0.05/0.36 s(29) =< it(15)*aux(13) 0.05/0.36 s(26) =< aux(14)*7 0.05/0.36 s(32) =< it(15)*aux(8) 0.05/0.36 s(30) =< s(32) 0.05/0.36 s(31) =< s(32)*8 0.05/0.36 s(26) =< s(29) 0.05/0.36 s(27) =< s(29) 0.05/0.36 s(28) =< s(29)*8 0.05/0.36 0.05/0.36 with precondition: [B=4,V_w>=9,V_y_0>=2] 0.05/0.36 0.05/0.36 * Chain [22]: 1*s(5)+1 0.05/0.36 Such that:s(5) =< V_w 0.05/0.36 0.05/0.36 with precondition: [B=4,7>=V_w,1>=V_y_0,V_w>=1] 0.05/0.36 0.05/0.36 * Chain [21]: 0 0.05/0.36 with precondition: [B=4,0>=V_w,1>=V_y_0] 0.05/0.36 0.05/0.36 * Chain [20]: 1*s(10)+1*s(11)+0 0.05/0.36 Such that:s(9) =< V_w 0.05/0.36 s(10) =< s(9) 0.05/0.36 s(11) =< s(9)*8 0.05/0.36 0.05/0.36 with precondition: [B=4,1>=V_y_0,V_w>=8] 0.05/0.36 0.05/0.36 * Chain [19]: 1*s(33)+1*s(35)+1*s(36)+1 0.05/0.36 Such that:s(33) =< 7 0.05/0.36 s(34) =< V_w 0.05/0.36 s(33) =< s(34) 0.05/0.36 s(35) =< s(34) 0.05/0.36 s(36) =< s(34)*8 0.05/0.36 0.05/0.36 with precondition: [B=4,1>=V_y_0,V_w>=9] 0.05/0.36 0.05/0.36 0.05/0.36 #### Cost of chains of eval_set_color_ht_extracted_bb0_in(V_h,V_w,B): 0.05/0.36 * Chain [30]: 1*s(37)+1 0.05/0.36 Such that:s(37) =< V_w 0.05/0.36 0.05/0.36 with precondition: [1>=V_h,7>=V_w,V_w>=1] 0.05/0.36 0.05/0.36 * Chain [29]: 0 0.05/0.36 with precondition: [1>=V_h,0>=V_w] 0.05/0.36 0.05/0.36 * Chain [28]: 1*s(39)+1*s(40)+0 0.05/0.36 Such that:s(38) =< V_w 0.05/0.36 s(39) =< s(38) 0.05/0.36 s(40) =< s(38)*8 0.05/0.36 0.05/0.36 with precondition: [1>=V_h,V_w>=8] 0.05/0.36 0.05/0.36 * Chain [27]: 1*s(41)+1*s(43)+1*s(44)+1 0.05/0.36 Such that:s(41) =< 7 0.05/0.36 s(42) =< V_w 0.05/0.36 s(41) =< s(42) 0.05/0.36 s(43) =< s(42) 0.05/0.36 s(44) =< s(42)*8 0.05/0.36 0.05/0.36 with precondition: [1>=V_h,V_w>=9] 0.05/0.36 0.05/0.36 * Chain [26]: 1*s(45)+2*s(46)+1*s(47)+1 0.05/0.36 Such that:s(46) =< V_h 0.05/0.36 s(47) =< 7*V_h 0.05/0.36 s(45) =< V_w 0.05/0.36 0.05/0.36 with precondition: [7>=V_w,V_h>=2,V_w>=1] 0.05/0.36 0.05/0.36 * Chain [25]: 1*s(48)+0 0.05/0.36 Such that:s(48) =< V_h 0.05/0.36 0.05/0.36 with precondition: [0>=V_w,V_h>=2] 0.05/0.36 0.05/0.36 * Chain [24]: 1*s(51)+1*s(52)+3*s(53)+1*s(56)+1*s(58)+1*s(59)+1*s(60)+1*s(61)+0 0.05/0.36 Such that:s(50) =< V_h 0.05/0.36 s(49) =< V_w 0.05/0.36 s(51) =< s(49) 0.05/0.36 s(52) =< s(49)*8 0.05/0.36 s(53) =< s(50) 0.05/0.36 s(54) =< s(49) 0.05/0.36 s(55) =< s(53)*s(49) 0.05/0.36 s(56) =< s(50)*7 0.05/0.36 s(57) =< s(53)*s(54) 0.05/0.36 s(58) =< s(57) 0.05/0.36 s(59) =< s(57)*8 0.05/0.36 s(56) =< s(55) 0.05/0.36 s(60) =< s(55) 0.05/0.36 s(61) =< s(55)*8 0.05/0.36 0.05/0.36 with precondition: [V_h>=2,V_w>=8] 0.05/0.36 0.05/0.36 * Chain [23]: 1*s(62)+1*s(65)+1*s(66)+3*s(67)+1*s(70)+1*s(72)+1*s(73)+1*s(74)+1*s(75)+1 0.05/0.36 Such that:s(62) =< 7 0.05/0.36 s(64) =< V_h 0.05/0.36 s(63) =< V_w 0.05/0.36 s(62) =< s(63) 0.05/0.36 s(65) =< s(63) 0.05/0.36 s(66) =< s(63)*8 0.05/0.36 s(67) =< s(64) 0.05/0.36 s(68) =< s(63) 0.05/0.36 s(69) =< s(67)*s(63) 0.05/0.36 s(70) =< s(64)*7 0.05/0.36 s(71) =< s(67)*s(68) 0.05/0.36 s(72) =< s(71) 0.05/0.36 s(73) =< s(71)*8 0.05/0.36 s(70) =< s(69) 0.05/0.36 s(74) =< s(69) 0.05/0.36 s(75) =< s(69)*8 0.05/0.36 0.05/0.36 with precondition: [V_h>=2,V_w>=9] 0.05/0.36 0.05/0.36 0.05/0.36 #### Cost of chains of eval_set_color_ht_extracted_start(V_h,V_w,B): 0.05/0.36 * Chain [38]: 1*s(76)+1 0.05/0.36 Such that:s(76) =< V_w 0.05/0.36 0.05/0.36 with precondition: [1>=V_h,7>=V_w,V_w>=1] 0.05/0.36 0.05/0.36 * Chain [37]: 0 0.05/0.36 with precondition: [1>=V_h,0>=V_w] 0.05/0.36 0.05/0.36 * Chain [36]: 1*s(78)+1*s(79)+0 0.05/0.36 Such that:s(77) =< V_w 0.05/0.36 s(78) =< s(77) 0.05/0.36 s(79) =< s(77)*8 0.05/0.36 0.05/0.36 with precondition: [1>=V_h,V_w>=8] 0.05/0.36 0.05/0.36 * Chain [35]: 1*s(80)+1*s(82)+1*s(83)+1 0.05/0.36 Such that:s(80) =< 7 0.05/0.36 s(81) =< V_w 0.05/0.36 s(80) =< s(81) 0.05/0.36 s(82) =< s(81) 0.05/0.36 s(83) =< s(81)*8 0.05/0.36 0.05/0.36 with precondition: [1>=V_h,V_w>=9] 0.05/0.36 0.05/0.36 * Chain [34]: 2*s(84)+1*s(85)+1*s(86)+1 0.05/0.36 Such that:s(84) =< V_h 0.05/0.36 s(85) =< 7*V_h 0.05/0.36 s(86) =< V_w 0.05/0.36 0.05/0.36 with precondition: [7>=V_w,V_h>=2,V_w>=1] 0.05/0.36 0.05/0.36 * Chain [33]: 1*s(87)+0 0.05/0.36 Such that:s(87) =< V_h 0.05/0.36 0.05/0.36 with precondition: [0>=V_w,V_h>=2] 0.05/0.36 0.05/0.36 * Chain [32]: 1*s(90)+1*s(91)+3*s(92)+1*s(95)+1*s(97)+1*s(98)+1*s(99)+1*s(100)+0 0.05/0.36 Such that:s(88) =< V_h 0.05/0.36 s(89) =< V_w 0.05/0.36 s(90) =< s(89) 0.05/0.36 s(91) =< s(89)*8 0.05/0.36 s(92) =< s(88) 0.05/0.36 s(93) =< s(89) 0.05/0.36 s(94) =< s(92)*s(89) 0.05/0.36 s(95) =< s(88)*7 0.05/0.36 s(96) =< s(92)*s(93) 0.05/0.36 s(97) =< s(96) 0.05/0.36 s(98) =< s(96)*8 0.05/0.36 s(95) =< s(94) 0.05/0.36 s(99) =< s(94) 0.05/0.36 s(100) =< s(94)*8 0.05/0.36 0.05/0.36 with precondition: [V_h>=2,V_w>=8] 0.05/0.36 0.05/0.36 * Chain [31]: 1*s(101)+1*s(104)+1*s(105)+3*s(106)+1*s(109)+1*s(111)+1*s(112)+1*s(113)+1*s(114)+1 0.05/0.36 Such that:s(101) =< 7 0.05/0.36 s(102) =< V_h 0.05/0.36 s(103) =< V_w 0.05/0.36 s(101) =< s(103) 0.05/0.36 s(104) =< s(103) 0.05/0.36 s(105) =< s(103)*8 0.05/0.36 s(106) =< s(102) 0.05/0.36 s(107) =< s(103) 0.05/0.36 s(108) =< s(106)*s(103) 0.05/0.36 s(109) =< s(102)*7 0.05/0.36 s(110) =< s(106)*s(107) 0.05/0.36 s(111) =< s(110) 0.05/0.36 s(112) =< s(110)*8 0.05/0.36 s(109) =< s(108) 0.05/0.36 s(113) =< s(108) 0.05/0.36 s(114) =< s(108)*8 0.05/0.36 0.05/0.36 with precondition: [V_h>=2,V_w>=9] 0.05/0.36 0.05/0.36 0.05/0.36 Closed-form bounds of eval_set_color_ht_extracted_start(V_h,V_w,B): 0.05/0.36 ------------------------------------- 0.05/0.36 * Chain [38] with precondition: [1>=V_h,7>=V_w,V_w>=1] 0.05/0.36 - Upper bound: V_w+1 0.05/0.36 - Complexity: n 0.05/0.36 * Chain [37] with precondition: [1>=V_h,0>=V_w] 0.05/0.36 - Upper bound: 0 0.05/0.36 - Complexity: constant 0.05/0.36 * Chain [36] with precondition: [1>=V_h,V_w>=8] 0.05/0.36 - Upper bound: 9*V_w 0.05/0.36 - Complexity: n 0.05/0.36 * Chain [35] with precondition: [1>=V_h,V_w>=9] 0.05/0.36 - Upper bound: 9*V_w+8 0.05/0.36 - Complexity: n 0.05/0.36 * Chain [34] with precondition: [7>=V_w,V_h>=2,V_w>=1] 0.05/0.36 - Upper bound: 9*V_h+V_w+1 0.05/0.36 - Complexity: n 0.05/0.36 * Chain [33] with precondition: [0>=V_w,V_h>=2] 0.05/0.36 - Upper bound: V_h 0.05/0.36 - Complexity: n 0.05/0.36 * Chain [32] with precondition: [V_h>=2,V_w>=8] 0.05/0.36 - Upper bound: 18*V_h*V_w+10*V_h+9*V_w 0.05/0.36 - Complexity: n^2 0.05/0.36 * Chain [31] with precondition: [V_h>=2,V_w>=9] 0.05/0.36 - Upper bound: 10*V_h+8+18*V_h*V_w+9*V_w 0.05/0.36 - Complexity: n^2 0.05/0.36 0.05/0.36 ### Maximum cost of eval_set_color_ht_extracted_start(V_h,V_w,B): max([nat(V_h),nat(V_w)+1+max([nat(V_h)*2+nat(7*V_h),nat(V_h)*18*nat(V_w)+nat(V_h)*10+(nat(V_w)*8+7)])]) 0.05/0.36 Asymptotic class: n^2 0.05/0.36 * Total analysis performed in 272 ms. 0.05/0.36 0.05/0.46 EOF