1.07/1.08 WORST_CASE(?,O(n^1)) 1.07/1.08 1.07/1.08 Preprocessing Cost Relations 1.07/1.08 ===================================== 1.07/1.08 1.07/1.08 #### Computed strongly connected components 1.07/1.08 0. recursive : [m1/7] 1.07/1.08 1. non_recursive : [exit_location/1] 1.07/1.08 2. non_recursive : [m1_loop_cont/2] 1.07/1.08 3. non_recursive : [start/7] 1.07/1.08 1.07/1.08 #### Obtained direct recursion through partial evaluation 1.07/1.08 0. SCC is partially evaluated into m1/7 1.07/1.08 1. SCC is completely evaluated into other SCCs 1.07/1.08 2. SCC is completely evaluated into other SCCs 1.07/1.08 3. SCC is partially evaluated into start/7 1.07/1.08 1.07/1.08 Control-Flow Refinement of Cost Relations 1.07/1.08 ===================================== 1.07/1.08 1.07/1.08 ### Specialization of cost equations m1/7 1.07/1.08 * CE 6 is refined into CE [7] 1.07/1.08 * CE 2 is refined into CE [8] 1.07/1.08 * CE 4 is refined into CE [9] 1.07/1.08 * CE 5 is refined into CE [10] 1.07/1.08 * CE 3 is refined into CE [11] 1.07/1.08 1.07/1.08 1.07/1.08 ### Cost equations --> "Loop" of m1/7 1.07/1.08 * CEs [8] --> Loop 7 1.07/1.08 * CEs [9] --> Loop 8 1.07/1.08 * CEs [10] --> Loop 9 1.07/1.08 * CEs [11] --> Loop 10 1.07/1.08 * CEs [7] --> Loop 11 1.07/1.08 1.07/1.08 ### Ranking functions of CR m1(A,B,C,D,E,F,I) 1.07/1.08 * RF of phase [7]: [-A+B-C+E+2,-A-C+3*E+4,2*A-C+1,2*A+2*C-3*F+1,2*A-F+1,B-C+1,B-F+1,-C+2*E+3,2*E-F+3] 1.07/1.08 * RF of phase [8,9]: [-A+B-C+E+1,-A+2*B-C,-A-C+3*E+3,2*A+2*C-3*F,B-F,2*E-F+2] 1.07/1.08 * RF of phase [10]: [-A+B,-A+B-C+E+2,-A+3*B-2*C+2,-A-C+3*E+4,-A+C-1,-A+E+1,2*A+2*C-3*F+1,B-F+1,C-F,2*E-F+3] 1.07/1.08 1.07/1.08 #### Partial ranking functions of CR m1(A,B,C,D,E,F,I) 1.07/1.08 * Partial RF of phase [7]: 1.07/1.08 - RF of loop [7:1]: 1.07/1.08 -A+B-C+E+2 1.07/1.08 -A-C+3*E+4 1.07/1.08 2*A-C+1 1.07/1.08 2*A+2*C-3*F+1 1.07/1.08 2*A-F+1 1.07/1.08 B-C+1 1.07/1.08 B-F+1 1.07/1.08 -C+2*E+3 1.07/1.08 2*E-F+3 1.07/1.08 * Partial RF of phase [8,9]: 1.07/1.08 - RF of loop [8:1]: 1.07/1.08 A+B-E-F 1.07/1.08 A+B/2-F+1/2 1.07/1.08 A+E-F+2 1.07/1.08 2*A+C-2*F+1 1.07/1.08 B-C+1 1.07/1.08 -C+2*E+3 1.07/1.08 - RF of loop [8:1,9:1]: 1.07/1.08 B-F 1.07/1.08 2*E-F+2 1.07/1.08 - RF of loop [9:1]: 1.07/1.08 -A+B 1.07/1.08 -A+C depends on loops [8:1] 1.07/1.08 -A+E+1 1.07/1.08 C-F 1.07/1.08 * Partial RF of phase [10]: 1.07/1.08 - RF of loop [10:1]: 1.07/1.08 -A+B 1.07/1.08 -A+B-C+E+2 1.07/1.08 -A+3*B-2*C+2 1.07/1.08 -A-C+3*E+4 1.07/1.08 -A+C-1 1.07/1.08 -A+E+1 1.07/1.08 2*A+2*C-3*F+1 1.07/1.08 B-F+1 1.07/1.08 C-F 1.07/1.08 2*E-F+3 1.07/1.08 1.07/1.08 1.07/1.08 ### Specialization of cost equations start/7 1.07/1.08 * CE 1 is refined into CE [12,13] 1.07/1.08 1.07/1.08 1.07/1.08 ### Cost equations --> "Loop" of start/7 1.07/1.08 * CEs [13] --> Loop 12 1.07/1.08 * CEs [12] --> Loop 13 1.07/1.08 1.07/1.08 ### Ranking functions of CR start(A,B,C,D,E,F,I) 1.07/1.08 1.07/1.08 #### Partial ranking functions of CR start(A,B,C,D,E,F,I) 1.07/1.08 1.07/1.08 1.07/1.08 Computing Bounds 1.07/1.08 ===================================== 1.07/1.08 1.07/1.08 #### Cost of chains of m1(A,B,C,D,E,F,I): 1.07/1.08 * Chain [[8,9],[10],11]: 1*it(8)+1*it(9)+1*it(10)+0 1.07/1.08 Such that:aux(1) =< -2*A+E+F+1 1.07/1.08 it(8) =< A+B-E-F 1.07/1.08 it(8) =< A+B/2-F+1/2 1.07/1.08 aux(2) =< -B+2*C-F 1.07/1.08 aux(5) =< 2*B-E-F 1.07/1.08 aux(15) =< -A+E 1.07/1.08 aux(16) =< -A+E+1 1.07/1.08 aux(17) =< B-F 1.07/1.08 aux(18) =< B-F+1 1.07/1.08 aux(19) =< 2*E-F+2 1.07/1.08 aux(2) =< aux(15) 1.07/1.08 it(9) =< aux(15) 1.07/1.08 it(9) =< aux(16) 1.07/1.08 it(10) =< aux(16) 1.07/1.08 aux(4) =< aux(17) 1.07/1.08 aux(4) =< aux(18) 1.07/1.08 it(10) =< aux(18) 1.07/1.08 it(8) =< aux(17) 1.07/1.08 it(9) =< aux(17) 1.07/1.08 it(8) =< aux(4) 1.07/1.08 it(9) =< aux(4) 1.07/1.08 it(8) =< aux(5) 1.07/1.08 it(9) =< aux(5) 1.07/1.08 it(8) =< aux(19) 1.07/1.08 it(9) =< aux(19) 1.07/1.08 it(9) =< it(8)+aux(2) 1.07/1.08 it(9) =< it(8)+aux(1) 1.07/1.08 1.07/1.08 with precondition: [I=2,A+C=E+F+1,D>=0,2*E+2>=B,B>=C,C>=E+1,C>=F+1,E+F+1>=C,B+F+1>=C+E] 1.07/1.08 1.07/1.08 * Chain [[8,9],[7],11]: 1*it(7)+1*it(8)+1*it(9)+0 1.07/1.08 Such that:aux(1) =< -2*A+E+F+1 1.07/1.08 aux(5) =< 2*B-E-F 1.07/1.08 aux(2) =< C-F 1.07/1.08 aux(20) =< -A+E+1 1.07/1.08 aux(21) =< A+B-E-F 1.07/1.08 aux(22) =< B-F 1.07/1.08 aux(23) =< B-F+1 1.07/1.08 aux(24) =< 2*E-F+2 1.07/1.08 aux(2) =< aux(20) 1.07/1.08 it(9) =< aux(20) 1.07/1.08 it(7) =< aux(21) 1.07/1.08 it(8) =< aux(21) 1.07/1.08 aux(4) =< aux(22) 1.07/1.08 aux(4) =< aux(23) 1.07/1.08 it(7) =< aux(23) 1.07/1.08 it(8) =< aux(22) 1.07/1.08 it(9) =< aux(22) 1.07/1.08 it(8) =< aux(4) 1.07/1.08 it(9) =< aux(4) 1.07/1.08 it(8) =< aux(5) 1.07/1.08 it(9) =< aux(5) 1.07/1.08 it(8) =< aux(24) 1.07/1.08 it(9) =< aux(24) 1.07/1.08 it(9) =< it(8)+aux(2) 1.07/1.08 it(9) =< it(8)+aux(1) 1.07/1.08 1.07/1.08 with precondition: [I=2,A+C=E+F+1,D>=0,2*E+2>=B,B>=C,C>=E+1,C>=F+1,E+F+1>=C,B+F+1>=C+E] 1.07/1.08 1.07/1.08 * Chain [[8,9],11]: 1*it(8)+1*it(9)+0 1.07/1.08 Such that:aux(1) =< -2*A+E+F+1 1.07/1.08 it(8) =< A+B/2-F+1/2 1.07/1.08 aux(5) =< 2*B-E-F 1.07/1.08 aux(2) =< C-F 1.07/1.08 aux(25) =< -A+E+1 1.07/1.08 aux(26) =< B-F 1.07/1.08 aux(27) =< 2*E-F+2 1.07/1.08 aux(2) =< aux(25) 1.07/1.08 it(9) =< aux(25) 1.07/1.08 it(8) =< aux(26) 1.07/1.08 it(9) =< aux(26) 1.07/1.08 it(8) =< aux(5) 1.07/1.08 it(9) =< aux(5) 1.07/1.08 it(8) =< aux(27) 1.07/1.08 it(9) =< aux(27) 1.07/1.08 it(9) =< it(8)+aux(2) 1.07/1.08 it(9) =< it(8)+aux(1) 1.07/1.08 1.07/1.08 with precondition: [I=2,A+C=E+F+1,D>=0,2*E+2>=B,B>=C,C>=E+1,C>=F+1,E+F+1>=C,B+F+1>=C+E] 1.07/1.08 1.07/1.08 * Chain [11]: 0 1.07/1.08 with precondition: [I=2,E+F+1=A+C,A>=0,B>=1,D>=0,F>=A,2*E+2>=B,2*B>=F,3*B>=2*E+A+2,3*B>=2*E+F+1,A+B>=2*E,A+2*B>=2*E+F+1] 1.07/1.08 1.07/1.08 1.07/1.08 #### Cost of chains of start(A,B,C,D,E,F,I): 1.07/1.08 * Chain [13]: 0 1.07/1.08 with precondition: [E+1=C,A=F,A>=0,D>=0,B>=A+1,A+B>=2*E,2*E+2>=A+B] 1.07/1.08 1.07/1.08 * Chain [12]: 1*s(44)+1*s(45)+1*s(47)+1*s(48)+1*s(49)+1*s(50)+1*s(52)+1*s(53)+0 1.07/1.08 Such that:s(34) =< -B+2*C-F 1.07/1.08 s(37) =< B-C+1 1.07/1.08 s(39) =< B-F 1.07/1.08 s(40) =< B-F+1 1.07/1.08 s(41) =< 2*B-C-F+1 1.07/1.08 s(38) =< B/2+1/2 1.07/1.08 s(43) =< 2*C-F 1.07/1.08 aux(37) =< C-F 1.07/1.08 s(44) =< s(37) 1.07/1.08 s(45) =< s(38) 1.07/1.08 s(44) =< s(38) 1.07/1.08 s(47) =< aux(37) 1.07/1.08 s(45) =< s(39) 1.07/1.08 s(47) =< s(39) 1.07/1.08 s(45) =< s(41) 1.07/1.08 s(47) =< s(41) 1.07/1.08 s(45) =< s(43) 1.07/1.08 s(47) =< s(43) 1.07/1.08 s(47) =< s(45)+aux(37) 1.07/1.08 s(48) =< aux(37) 1.07/1.08 s(49) =< s(37) 1.07/1.08 s(50) =< s(37) 1.07/1.08 s(51) =< s(39) 1.07/1.08 s(51) =< s(40) 1.07/1.08 s(49) =< s(40) 1.07/1.08 s(50) =< s(39) 1.07/1.08 s(48) =< s(39) 1.07/1.08 s(50) =< s(51) 1.07/1.08 s(48) =< s(51) 1.07/1.08 s(50) =< s(41) 1.07/1.08 s(48) =< s(41) 1.07/1.08 s(50) =< s(43) 1.07/1.08 s(48) =< s(43) 1.07/1.08 s(48) =< s(50)+aux(37) 1.07/1.08 s(34) =< aux(37) 1.07/1.08 s(52) =< aux(37) 1.07/1.08 s(53) =< aux(37) 1.07/1.08 s(53) =< s(40) 1.07/1.08 s(44) =< s(39) 1.07/1.08 s(52) =< s(39) 1.07/1.08 s(44) =< s(51) 1.07/1.08 s(52) =< s(51) 1.07/1.08 s(44) =< s(41) 1.07/1.08 s(52) =< s(41) 1.07/1.08 s(44) =< s(43) 1.07/1.08 s(52) =< s(43) 1.07/1.08 s(52) =< s(44)+s(34) 1.07/1.08 s(52) =< s(44)+aux(37) 1.07/1.08 1.07/1.08 with precondition: [E+1=C,A=F,A>=0,D>=0,E>=A,B>=E+1,A+B>=2*E,2*E+2>=A+B] 1.07/1.08 1.07/1.08 1.07/1.08 Closed-form bounds of start(A,B,C,D,E,F,I): 1.07/1.08 ------------------------------------- 1.07/1.08 * Chain [13] with precondition: [E+1=C,A=F,A>=0,D>=0,B>=A+1,A+B>=2*E,2*E+2>=A+B] 1.07/1.08 - Upper bound: 0 1.07/1.08 - Complexity: constant 1.07/1.08 * Chain [12] with precondition: [E+1=C,A=F,A>=0,D>=0,E>=A,B>=E+1,A+B>=2*E,2*E+2>=A+B] 1.07/1.08 - Upper bound: 7/2*B+C-4*F+7/2 1.07/1.08 - Complexity: n 1.07/1.08 1.07/1.08 ### Maximum cost of start(A,B,C,D,E,F,I): 7/2*B+C-4*F+7/2 1.07/1.08 Asymptotic class: n 1.07/1.08 * Total analysis performed in 993 ms. 1.07/1.08 1.08/1.18 EOF