0.04/0.46 WORST_CASE(?,O(n^2)) 0.04/0.46 0.04/0.46 Preprocessing Cost Relations 0.04/0.46 ===================================== 0.04/0.46 0.04/0.46 #### Computed strongly connected components 0.04/0.46 0. recursive : [evalrsdbb1in/6,evalrsdbb2in/6,evalrsdbb3in/6,evalrsdbb4in/6] 0.04/0.46 1. non_recursive : [evalrsdstop/4] 0.04/0.46 2. non_recursive : [evalrsdreturnin/4] 0.04/0.46 3. non_recursive : [exit_location/1] 0.04/0.46 4. non_recursive : [evalrsdbb4in_loop_cont/5] 0.04/0.46 5. non_recursive : [evalrsdbbin/4] 0.04/0.46 6. non_recursive : [evalrsdentryin/4] 0.04/0.46 7. non_recursive : [evalrsdstart/4] 0.04/0.46 0.04/0.46 #### Obtained direct recursion through partial evaluation 0.04/0.46 0. SCC is partially evaluated into evalrsdbb4in/6 0.04/0.46 1. SCC is completely evaluated into other SCCs 0.04/0.46 2. SCC is completely evaluated into other SCCs 0.04/0.46 3. SCC is completely evaluated into other SCCs 0.04/0.46 4. SCC is partially evaluated into evalrsdbb4in_loop_cont/5 0.04/0.46 5. SCC is partially evaluated into evalrsdbbin/4 0.04/0.46 6. SCC is partially evaluated into evalrsdentryin/4 0.04/0.46 7. SCC is partially evaluated into evalrsdstart/4 0.04/0.46 0.04/0.46 Control-Flow Refinement of Cost Relations 0.04/0.46 ===================================== 0.04/0.46 0.04/0.46 ### Specialization of cost equations evalrsdbb4in/6 0.04/0.46 * CE 8 is refined into CE [11] 0.04/0.46 * CE 7 is refined into CE [12] 0.04/0.46 * CE 6 is refined into CE [13] 0.04/0.46 * CE 5 is refined into CE [14] 0.04/0.46 0.04/0.46 0.04/0.46 ### Cost equations --> "Loop" of evalrsdbb4in/6 0.04/0.46 * CEs [13] --> Loop 11 0.04/0.46 * CEs [14] --> Loop 12 0.04/0.46 * CEs [11] --> Loop 13 0.04/0.46 * CEs [12] --> Loop 14 0.04/0.46 0.04/0.46 ### Ranking functions of CR evalrsdbb4in(A,B,C,E,F,G) 0.04/0.46 0.04/0.46 #### Partial ranking functions of CR evalrsdbb4in(A,B,C,E,F,G) 0.04/0.46 * Partial RF of phase [11,12]: 0.04/0.46 - RF of loop [11:1]: 0.04/0.46 -A+B+1 0.04/0.46 B+1 0.04/0.46 - RF of loop [12:1]: 0.04/0.46 -A+C+1 depends on loops [11:1] 0.04/0.46 -B/2+C+1/2 depends on loops [11:1] 0.04/0.46 C+1 depends on loops [11:1] 0.04/0.46 0.04/0.46 0.04/0.46 ### Specialization of cost equations evalrsdbb4in_loop_cont/5 0.04/0.46 * CE 10 is refined into CE [15] 0.04/0.46 * CE 9 is refined into CE [16] 0.04/0.46 0.04/0.46 0.04/0.46 ### Cost equations --> "Loop" of evalrsdbb4in_loop_cont/5 0.04/0.46 * CEs [15] --> Loop 15 0.04/0.46 * CEs [16] --> Loop 16 0.04/0.46 0.04/0.46 ### Ranking functions of CR evalrsdbb4in_loop_cont(A,B,C,D,E) 0.04/0.46 0.04/0.46 #### Partial ranking functions of CR evalrsdbb4in_loop_cont(A,B,C,D,E) 0.04/0.46 0.04/0.46 0.04/0.46 ### Specialization of cost equations evalrsdbbin/4 0.04/0.46 * CE 4 is refined into CE [17,18,19] 0.04/0.46 0.04/0.46 0.04/0.46 ### Cost equations --> "Loop" of evalrsdbbin/4 0.04/0.46 * CEs [17,18,19] --> Loop 17 0.04/0.46 0.04/0.46 ### Ranking functions of CR evalrsdbbin(A,B,C,E) 0.04/0.46 0.04/0.46 #### Partial ranking functions of CR evalrsdbbin(A,B,C,E) 0.04/0.46 0.04/0.46 0.04/0.46 ### Specialization of cost equations evalrsdentryin/4 0.04/0.46 * CE 2 is refined into CE [20] 0.04/0.46 * CE 3 is refined into CE [21] 0.04/0.46 0.04/0.46 0.04/0.46 ### Cost equations --> "Loop" of evalrsdentryin/4 0.04/0.46 * CEs [20] --> Loop 18 0.04/0.46 * CEs [21] --> Loop 19 0.04/0.46 0.04/0.46 ### Ranking functions of CR evalrsdentryin(A,B,C,E) 0.04/0.46 0.04/0.46 #### Partial ranking functions of CR evalrsdentryin(A,B,C,E) 0.04/0.46 0.04/0.46 0.04/0.46 ### Specialization of cost equations evalrsdstart/4 0.04/0.46 * CE 1 is refined into CE [22,23] 0.04/0.46 0.04/0.46 0.04/0.46 ### Cost equations --> "Loop" of evalrsdstart/4 0.04/0.46 * CEs [23] --> Loop 20 0.04/0.46 * CEs [22] --> Loop 21 0.04/0.46 0.04/0.46 ### Ranking functions of CR evalrsdstart(A,B,C,E) 0.04/0.46 0.04/0.46 #### Partial ranking functions of CR evalrsdstart(A,B,C,E) 0.04/0.46 0.04/0.46 0.04/0.46 Computing Bounds 0.04/0.46 ===================================== 0.04/0.46 0.04/0.46 #### Cost of chains of evalrsdbb4in(A,B,C,E,F,G): 0.04/0.46 * Chain [[11,12],14]: 1*it(11)+1*it(12)+0 0.04/0.46 Such that:aux(21) =< B 0.04/0.46 it(11) =< B-F 0.04/0.46 aux(13) =< B-G 0.04/0.46 aux(6) =< -B/2+C+1/2 0.04/0.46 aux(12) =< -B/2+C+F/2-G 0.04/0.46 aux(15) =< C 0.04/0.46 aux(2) =< C+1 0.04/0.46 aux(25) =< G+1 0.04/0.46 aux(26) =< C-G 0.04/0.46 aux(12) =< aux(26) 0.04/0.46 aux(13) =< aux(25) 0.04/0.46 aux(15) =< aux(25) 0.04/0.46 aux(23) =< aux(13) 0.04/0.46 aux(23) =< aux(15)-1/2 0.04/0.46 aux(21) =< aux(15) 0.04/0.46 aux(17) =< aux(13) 0.04/0.46 aux(16) =< it(11)*aux(15) 0.04/0.46 aux(5) =< it(11)*aux(15) 0.04/0.46 aux(14) =< it(11)*aux(13) 0.04/0.46 aux(1) =< it(11)*aux(13) 0.04/0.46 aux(24) =< it(11)*aux(23) 0.04/0.46 aux(3) =< it(11)*aux(23) 0.04/0.46 aux(22) =< it(11)*aux(21) 0.04/0.46 aux(5) =< it(11)*aux(21) 0.04/0.46 aux(18) =< it(11)*aux(17) 0.04/0.46 aux(1) =< it(11)*aux(17) 0.04/0.46 aux(3) =< it(11)*aux(17) 0.04/0.46 aux(11) =< aux(16) 0.04/0.46 aux(7) =< aux(14) 0.04/0.46 aux(9) =< aux(24) 0.04/0.46 aux(11) =< aux(22) 0.04/0.46 aux(7) =< aux(18) 0.04/0.46 aux(9) =< aux(18) 0.04/0.46 it(12) =< aux(5)+aux(6) 0.04/0.46 it(12) =< aux(3)+aux(26) 0.04/0.46 it(12) =< aux(1)+aux(2) 0.04/0.46 it(12) =< aux(11)+aux(12) 0.04/0.46 it(12) =< aux(9)+aux(26) 0.04/0.46 it(12) =< aux(7)+aux(26) 0.04/0.46 0.04/0.46 with precondition: [E=2,A=G+1,C>=A,F+1>=A,2*A>=B,B>=C,B>=F] 0.04/0.46 0.04/0.46 * Chain [[11,12],13]: 1*it(11)+1*it(12)+0 0.04/0.46 Such that:aux(13) =< -A+B 0.04/0.46 it(11) =< -A+B+1 0.04/0.46 aux(25) =< A 0.04/0.46 aux(21) =< B 0.04/0.46 aux(6) =< -B/2+C+1/2 0.04/0.46 aux(15) =< C 0.04/0.46 aux(2) =< C+1 0.04/0.46 aux(27) =< -A+C+1 0.04/0.46 aux(28) =< -B/2+C+1 0.04/0.46 aux(8) =< aux(27) 0.04/0.46 aux(8) =< aux(28) 0.04/0.46 aux(13) =< aux(25) 0.04/0.46 aux(15) =< aux(25) 0.04/0.46 aux(23) =< aux(13) 0.04/0.46 aux(23) =< aux(15)-1/2 0.04/0.46 aux(21) =< aux(15) 0.04/0.46 aux(17) =< aux(13) 0.04/0.46 aux(16) =< it(11)*aux(15) 0.04/0.46 aux(5) =< it(11)*aux(15) 0.04/0.46 aux(14) =< it(11)*aux(13) 0.04/0.46 aux(1) =< it(11)*aux(13) 0.04/0.46 aux(24) =< it(11)*aux(23) 0.04/0.46 aux(3) =< it(11)*aux(23) 0.04/0.46 aux(22) =< it(11)*aux(21) 0.04/0.46 aux(5) =< it(11)*aux(21) 0.04/0.46 aux(18) =< it(11)*aux(17) 0.04/0.46 aux(1) =< it(11)*aux(17) 0.04/0.46 aux(3) =< it(11)*aux(17) 0.04/0.46 aux(11) =< aux(16) 0.04/0.46 aux(7) =< aux(14) 0.04/0.46 aux(9) =< aux(24) 0.04/0.46 aux(11) =< aux(22) 0.04/0.46 aux(7) =< aux(18) 0.04/0.46 aux(9) =< aux(18) 0.04/0.46 it(12) =< aux(5)+aux(6) 0.04/0.46 it(12) =< aux(3)+aux(27) 0.04/0.46 it(12) =< aux(1)+aux(2) 0.04/0.46 it(12) =< aux(11)+aux(8) 0.04/0.46 it(12) =< aux(9)+aux(8) 0.04/0.46 it(12) =< aux(7)+aux(8) 0.04/0.46 0.04/0.46 with precondition: [E=3,C>=A,2*A>=B,B>=C] 0.04/0.46 0.04/0.46 * Chain [13]: 0 0.04/0.46 with precondition: [E=3,A>=0,2*A>=B,B>=C] 0.04/0.46 0.04/0.46 0.04/0.47 #### Cost of chains of evalrsdbb4in_loop_cont(A,B,C,D,E): 0.04/0.47 * Chain [16]: 0 0.04/0.47 with precondition: [A=2,B>=0] 0.04/0.47 0.04/0.47 * Chain [15]: 0 0.04/0.47 with precondition: [A=3,B>=0] 0.04/0.47 0.04/0.47 0.04/0.47 #### Cost of chains of evalrsdbbin(A,B,C,E): 0.04/0.47 * Chain [17]: 1*s(2)+1*s(23)+1*s(25)+1*s(47)+0 0.04/0.47 Such that:aux(31) =< 2*A+2 0.04/0.47 aux(35) =< A 0.04/0.47 aux(36) =< A+1 0.04/0.47 aux(37) =< A+1/2 0.04/0.47 aux(38) =< 2*A 0.04/0.47 aux(39) =< 2*A+1 0.04/0.47 s(2) =< aux(36) 0.04/0.47 s(3) =< aux(36) 0.04/0.47 s(5) =< aux(36) 0.04/0.47 s(1) =< aux(38) 0.04/0.47 s(6) =< aux(38) 0.04/0.47 s(2) =< aux(31) 0.04/0.47 s(5) =< aux(31) 0.04/0.47 s(3) =< aux(35) 0.04/0.47 s(6) =< aux(35) 0.04/0.47 s(10) =< s(3) 0.04/0.47 s(10) =< s(6)-1/2 0.04/0.47 s(1) =< s(6) 0.04/0.47 s(11) =< s(3) 0.04/0.47 s(12) =< s(2)*s(6) 0.04/0.47 s(13) =< s(2)*s(6) 0.04/0.47 s(14) =< s(2)*s(3) 0.04/0.47 s(15) =< s(2)*s(3) 0.04/0.47 s(16) =< s(2)*s(10) 0.04/0.47 s(17) =< s(2)*s(10) 0.04/0.47 s(18) =< s(2)*s(1) 0.04/0.47 s(13) =< s(2)*s(1) 0.04/0.47 s(19) =< s(2)*s(11) 0.04/0.47 s(15) =< s(2)*s(11) 0.04/0.47 s(17) =< s(2)*s(11) 0.04/0.47 s(20) =< s(12) 0.04/0.47 s(21) =< s(14) 0.04/0.47 s(22) =< s(16) 0.04/0.47 s(20) =< s(18) 0.04/0.47 s(21) =< s(19) 0.04/0.47 s(22) =< s(19) 0.04/0.47 s(23) =< s(13)+aux(37) 0.04/0.47 s(23) =< s(17)+aux(36) 0.04/0.47 s(23) =< s(15)+aux(39) 0.04/0.47 s(23) =< s(20)+s(5) 0.04/0.47 s(23) =< s(22)+aux(36) 0.04/0.47 s(23) =< s(21)+aux(36) 0.04/0.47 s(25) =< aux(36) 0.04/0.47 s(34) =< aux(35) 0.04/0.47 s(34) =< s(6)-1/2 0.04/0.47 s(35) =< aux(35) 0.04/0.47 s(36) =< s(25)*s(6) 0.04/0.47 s(37) =< s(25)*s(6) 0.04/0.47 s(38) =< s(25)*aux(35) 0.04/0.47 s(39) =< s(25)*aux(35) 0.04/0.47 s(40) =< s(25)*s(34) 0.04/0.47 s(41) =< s(25)*s(34) 0.04/0.47 s(42) =< s(25)*s(1) 0.04/0.47 s(37) =< s(25)*s(1) 0.04/0.47 s(43) =< s(25)*s(35) 0.04/0.47 s(39) =< s(25)*s(35) 0.04/0.47 s(41) =< s(25)*s(35) 0.04/0.47 s(44) =< s(36) 0.04/0.47 s(45) =< s(38) 0.04/0.47 s(46) =< s(40) 0.04/0.47 s(44) =< s(42) 0.04/0.47 s(45) =< s(43) 0.04/0.47 s(46) =< s(43) 0.04/0.47 s(47) =< s(37)+aux(37) 0.04/0.47 s(47) =< s(41)+aux(36) 0.04/0.47 s(47) =< s(39)+aux(39) 0.04/0.47 s(47) =< s(44)+aux(36) 0.04/0.47 s(47) =< s(46)+aux(36) 0.04/0.47 s(47) =< s(45)+aux(36) 0.04/0.47 0.04/0.47 with precondition: [A>=0] 0.04/0.47 0.04/0.47 0.04/0.47 #### Cost of chains of evalrsdentryin(A,B,C,E): 0.04/0.47 * Chain [19]: 0 0.04/0.47 with precondition: [0>=A+1] 0.04/0.47 0.04/0.47 * Chain [18]: 1*s(54)+1*s(72)+1*s(73)+1*s(87)+0 0.04/0.47 Such that:s(49) =< A 0.04/0.47 s(50) =< A+1 0.04/0.47 s(51) =< A+1/2 0.04/0.47 s(52) =< 2*A 0.04/0.47 s(53) =< 2*A+1 0.04/0.47 s(48) =< 2*A+2 0.04/0.47 s(54) =< s(50) 0.04/0.47 s(55) =< s(50) 0.04/0.47 s(56) =< s(50) 0.04/0.47 s(57) =< s(52) 0.04/0.47 s(58) =< s(52) 0.04/0.47 s(54) =< s(48) 0.04/0.47 s(56) =< s(48) 0.04/0.47 s(55) =< s(49) 0.04/0.47 s(58) =< s(49) 0.04/0.47 s(59) =< s(55) 0.04/0.47 s(59) =< s(58)-1/2 0.04/0.47 s(57) =< s(58) 0.04/0.47 s(60) =< s(55) 0.04/0.47 s(61) =< s(54)*s(58) 0.04/0.47 s(62) =< s(54)*s(58) 0.04/0.47 s(63) =< s(54)*s(55) 0.04/0.47 s(64) =< s(54)*s(55) 0.04/0.47 s(65) =< s(54)*s(59) 0.04/0.47 s(66) =< s(54)*s(59) 0.04/0.47 s(67) =< s(54)*s(57) 0.04/0.47 s(62) =< s(54)*s(57) 0.04/0.47 s(68) =< s(54)*s(60) 0.04/0.47 s(64) =< s(54)*s(60) 0.04/0.47 s(66) =< s(54)*s(60) 0.04/0.47 s(69) =< s(61) 0.04/0.47 s(70) =< s(63) 0.04/0.47 s(71) =< s(65) 0.04/0.47 s(69) =< s(67) 0.04/0.47 s(70) =< s(68) 0.04/0.47 s(71) =< s(68) 0.04/0.47 s(72) =< s(62)+s(51) 0.04/0.47 s(72) =< s(66)+s(50) 0.04/0.47 s(72) =< s(64)+s(53) 0.04/0.47 s(72) =< s(69)+s(56) 0.04/0.47 s(72) =< s(71)+s(50) 0.04/0.47 s(72) =< s(70)+s(50) 0.04/0.47 s(73) =< s(50) 0.04/0.47 s(74) =< s(49) 0.04/0.47 s(74) =< s(58)-1/2 0.04/0.47 s(75) =< s(49) 0.04/0.47 s(76) =< s(73)*s(58) 0.04/0.47 s(77) =< s(73)*s(58) 0.04/0.47 s(78) =< s(73)*s(49) 0.04/0.47 s(79) =< s(73)*s(49) 0.04/0.47 s(80) =< s(73)*s(74) 0.04/0.47 s(81) =< s(73)*s(74) 0.04/0.47 s(82) =< s(73)*s(57) 0.04/0.47 s(77) =< s(73)*s(57) 0.04/0.47 s(83) =< s(73)*s(75) 0.04/0.47 s(79) =< s(73)*s(75) 0.04/0.47 s(81) =< s(73)*s(75) 0.04/0.47 s(84) =< s(76) 0.04/0.47 s(85) =< s(78) 0.04/0.47 s(86) =< s(80) 0.04/0.47 s(84) =< s(82) 0.04/0.47 s(85) =< s(83) 0.04/0.47 s(86) =< s(83) 0.04/0.47 s(87) =< s(77)+s(51) 0.04/0.47 s(87) =< s(81)+s(50) 0.04/0.47 s(87) =< s(79)+s(53) 0.04/0.47 s(87) =< s(84)+s(50) 0.04/0.47 s(87) =< s(86)+s(50) 0.04/0.47 s(87) =< s(85)+s(50) 0.04/0.47 0.04/0.47 with precondition: [A>=0] 0.04/0.47 0.04/0.47 0.04/0.47 #### Cost of chains of evalrsdstart(A,B,C,E): 0.04/0.47 * Chain [21]: 0 0.04/0.47 with precondition: [0>=A+1] 0.04/0.47 0.04/0.47 * Chain [20]: 1*s(94)+1*s(112)+1*s(113)+1*s(127)+0 0.04/0.47 Such that:s(88) =< A 0.04/0.47 s(89) =< A+1 0.04/0.47 s(90) =< A+1/2 0.04/0.47 s(91) =< 2*A 0.04/0.47 s(92) =< 2*A+1 0.04/0.47 s(93) =< 2*A+2 0.04/0.47 s(94) =< s(89) 0.04/0.47 s(95) =< s(89) 0.04/0.47 s(96) =< s(89) 0.04/0.47 s(97) =< s(91) 0.04/0.47 s(98) =< s(91) 0.04/0.47 s(94) =< s(93) 0.04/0.47 s(96) =< s(93) 0.04/0.47 s(95) =< s(88) 0.04/0.47 s(98) =< s(88) 0.04/0.47 s(99) =< s(95) 0.04/0.47 s(99) =< s(98)-1/2 0.04/0.47 s(97) =< s(98) 0.04/0.47 s(100) =< s(95) 0.04/0.47 s(101) =< s(94)*s(98) 0.04/0.47 s(102) =< s(94)*s(98) 0.04/0.47 s(103) =< s(94)*s(95) 0.04/0.47 s(104) =< s(94)*s(95) 0.04/0.47 s(105) =< s(94)*s(99) 0.04/0.47 s(106) =< s(94)*s(99) 0.04/0.47 s(107) =< s(94)*s(97) 0.04/0.47 s(102) =< s(94)*s(97) 0.04/0.47 s(108) =< s(94)*s(100) 0.04/0.47 s(104) =< s(94)*s(100) 0.04/0.47 s(106) =< s(94)*s(100) 0.04/0.47 s(109) =< s(101) 0.04/0.47 s(110) =< s(103) 0.04/0.47 s(111) =< s(105) 0.04/0.47 s(109) =< s(107) 0.04/0.47 s(110) =< s(108) 0.04/0.47 s(111) =< s(108) 0.04/0.47 s(112) =< s(102)+s(90) 0.04/0.47 s(112) =< s(106)+s(89) 0.04/0.47 s(112) =< s(104)+s(92) 0.04/0.47 s(112) =< s(109)+s(96) 0.04/0.47 s(112) =< s(111)+s(89) 0.04/0.47 s(112) =< s(110)+s(89) 0.04/0.47 s(113) =< s(89) 0.04/0.47 s(114) =< s(88) 0.04/0.47 s(114) =< s(98)-1/2 0.04/0.47 s(115) =< s(88) 0.04/0.47 s(116) =< s(113)*s(98) 0.04/0.47 s(117) =< s(113)*s(98) 0.04/0.47 s(118) =< s(113)*s(88) 0.04/0.47 s(119) =< s(113)*s(88) 0.04/0.47 s(120) =< s(113)*s(114) 0.04/0.47 s(121) =< s(113)*s(114) 0.04/0.47 s(122) =< s(113)*s(97) 0.04/0.47 s(117) =< s(113)*s(97) 0.04/0.47 s(123) =< s(113)*s(115) 0.04/0.47 s(119) =< s(113)*s(115) 0.04/0.47 s(121) =< s(113)*s(115) 0.04/0.47 s(124) =< s(116) 0.04/0.47 s(125) =< s(118) 0.04/0.47 s(126) =< s(120) 0.04/0.47 s(124) =< s(122) 0.04/0.47 s(125) =< s(123) 0.04/0.47 s(126) =< s(123) 0.04/0.47 s(127) =< s(117)+s(90) 0.04/0.47 s(127) =< s(121)+s(89) 0.04/0.47 s(127) =< s(119)+s(92) 0.04/0.47 s(127) =< s(124)+s(89) 0.04/0.47 s(127) =< s(126)+s(89) 0.04/0.47 s(127) =< s(125)+s(89) 0.04/0.47 0.04/0.47 with precondition: [A>=0] 0.04/0.47 0.04/0.47 0.04/0.47 Closed-form bounds of evalrsdstart(A,B,C,E): 0.04/0.47 ------------------------------------- 0.04/0.47 * Chain [21] with precondition: [0>=A+1] 0.04/0.47 - Upper bound: 0 0.04/0.47 - Complexity: constant 0.04/0.47 * Chain [20] with precondition: [A>=0] 0.04/0.47 - Upper bound: 2*A+2+(A+1)*(4*A)+(2*A+1) 0.04/0.47 - Complexity: n^2 0.04/0.47 0.04/0.47 ### Maximum cost of evalrsdstart(A,B,C,E): nat(2*A)*2*nat(A+1)+nat(A+1)*2+nat(A+1/2)*2 0.04/0.47 Asymptotic class: n^2 0.04/0.47 * Total analysis performed in 366 ms. 0.04/0.47 0.48/0.57 EOF