7.20/7.21 MAYBE 7.20/7.21 7.20/7.21 Preprocessing Cost Relations 7.20/7.21 ===================================== 7.20/7.21 7.20/7.21 #### Computed strongly connected components 7.20/7.21 0. recursive : [f20/19,f32/19,f9/19] 7.20/7.21 1. non_recursive : [exit_location/1] 7.20/7.21 2. non_recursive : [f38/10] 7.20/7.21 3. non_recursive : [f9_loop_cont/11] 7.20/7.21 4. non_recursive : [f0/10] 7.20/7.21 7.20/7.21 #### Obtained direct recursion through partial evaluation 7.20/7.21 0. SCC is partially evaluated into f9/19 7.20/7.21 1. SCC is completely evaluated into other SCCs 7.20/7.21 2. SCC is completely evaluated into other SCCs 7.20/7.21 3. SCC is partially evaluated into f9_loop_cont/11 7.20/7.21 4. SCC is partially evaluated into f0/10 7.20/7.21 7.20/7.21 Control-Flow Refinement of Cost Relations 7.20/7.21 ===================================== 7.20/7.21 7.20/7.21 ### Specialization of cost equations f9/19 7.20/7.21 * CE 44 is refined into CE [47] 7.20/7.21 * CE 43 is refined into CE [48] 7.20/7.21 * CE 42 is refined into CE [49] 7.20/7.21 * CE 2 is refined into CE [50] 7.20/7.21 * CE 7 is refined into CE [51] 7.20/7.21 * CE 15 is refined into CE [52] 7.20/7.21 * CE 19 is refined into CE [53] 7.20/7.21 * CE 3 is discarded (unfeasible) 7.20/7.21 * CE 8 is discarded (unfeasible) 7.20/7.21 * CE 16 is discarded (unfeasible) 7.20/7.21 * CE 20 is discarded (unfeasible) 7.20/7.21 * CE 27 is refined into CE [54] 7.20/7.21 * CE 32 is refined into CE [55] 7.20/7.21 * CE 28 is discarded (unfeasible) 7.20/7.21 * CE 33 is discarded (unfeasible) 7.20/7.21 * CE 11 is refined into CE [56] 7.20/7.21 * CE 23 is refined into CE [57] 7.20/7.21 * CE 12 is discarded (unfeasible) 7.20/7.21 * CE 24 is discarded (unfeasible) 7.20/7.21 * CE 37 is refined into CE [58] 7.20/7.21 * CE 38 is discarded (unfeasible) 7.20/7.21 * CE 4 is refined into CE [59] 7.20/7.21 * CE 9 is refined into CE [60] 7.20/7.21 * CE 17 is refined into CE [61] 7.20/7.21 * CE 21 is refined into CE [62] 7.20/7.21 * CE 6 is discarded (unfeasible) 7.20/7.21 * CE 36 is discarded (unfeasible) 7.20/7.21 * CE 31 is refined into CE [63] 7.20/7.21 * CE 5 is discarded (unfeasible) 7.20/7.21 * CE 10 is discarded (unfeasible) 7.20/7.21 * CE 18 is discarded (unfeasible) 7.20/7.21 * CE 22 is discarded (unfeasible) 7.20/7.21 * CE 13 is discarded (unfeasible) 7.20/7.21 * CE 25 is discarded (unfeasible) 7.20/7.21 * CE 14 is discarded (unfeasible) 7.20/7.21 * CE 26 is discarded (unfeasible) 7.20/7.21 * CE 29 is discarded (unfeasible) 7.20/7.21 * CE 34 is discarded (unfeasible) 7.20/7.21 * CE 30 is discarded (unfeasible) 7.20/7.21 * CE 35 is discarded (unfeasible) 7.20/7.21 * CE 39 is refined into CE [64] 7.20/7.21 * CE 40 is discarded (unfeasible) 7.20/7.21 * CE 41 is refined into CE [65] 7.20/7.21 7.20/7.21 7.20/7.21 ### Cost equations --> "Loop" of f9/19 7.20/7.21 * CEs [50] --> Loop 47 7.20/7.21 * CEs [51] --> Loop 48 7.20/7.21 * CEs [52] --> Loop 49 7.20/7.21 * CEs [53] --> Loop 50 7.20/7.21 * CEs [54] --> Loop 51 7.20/7.21 * CEs [55] --> Loop 52 7.20/7.21 * CEs [56] --> Loop 53 7.20/7.21 * CEs [57] --> Loop 54 7.20/7.21 * CEs [58] --> Loop 55 7.20/7.21 * CEs [63] --> Loop 56 7.20/7.21 * CEs [65] --> Loop 57 7.20/7.21 * CEs [59] --> Loop 58 7.20/7.21 * CEs [60] --> Loop 59 7.20/7.21 * CEs [61] --> Loop 60 7.20/7.21 * CEs [62] --> Loop 61 7.20/7.21 * CEs [64] --> Loop 62 7.20/7.21 * CEs [47] --> Loop 63 7.20/7.21 * CEs [48] --> Loop 64 7.20/7.21 * CEs [49] --> Loop 65 7.20/7.21 7.20/7.21 ### Ranking functions of CR f9(A,B,C,D,E,F,G,H,I,L,M,N,O,P,Q,R,S,T,U) 7.20/7.21 7.20/7.21 #### Partial ranking functions of CR f9(A,B,C,D,E,F,G,H,I,L,M,N,O,P,Q,R,S,T,U) 7.20/7.21 * Partial RF of phase [47,48,49,50,55,57,58,59,60,61,62]: 7.20/7.21 - RF of loop [47:1,48:1,49:1,50:1,55:1]: 7.20/7.21 F depends on loops [58:1,59:1,60:1,61:1,62:1] 7.20/7.21 - RF of loop [57:1]: 7.20/7.21 C depends on loops [58:1,59:1,60:1,61:1,62:1] 7.20/7.21 - RF of loop [58:1,59:1,60:1,61:1,62:1]: 7.20/7.21 -A+1 7.20/7.21 -B+2 7.20/7.21 -C/2+1/2 depends on loops [57:1] 7.20/7.21 -F+1 depends on loops [47:1,48:1,49:1,50:1,55:1] 7.20/7.21 7.20/7.21 7.20/7.21 ### Specialization of cost equations f9_loop_cont/11 7.20/7.21 * CE 46 is refined into CE [66] 7.20/7.21 * CE 45 is refined into CE [67] 7.20/7.21 7.20/7.21 7.20/7.21 ### Cost equations --> "Loop" of f9_loop_cont/11 7.20/7.21 * CEs [66] --> Loop 66 7.20/7.21 * CEs [67] --> Loop 67 7.20/7.21 7.20/7.21 ### Ranking functions of CR f9_loop_cont(A,B,C,D,E,F,G,H,I,J,K) 7.20/7.21 7.20/7.21 #### Partial ranking functions of CR f9_loop_cont(A,B,C,D,E,F,G,H,I,J,K) 7.20/7.21 7.20/7.21 7.20/7.21 ### Specialization of cost equations f0/10 7.20/7.21 * CE 1 is refined into CE [68,69,70,71,72,73,74,75,76,77,78,79,80] 7.20/7.21 7.20/7.21 7.20/7.21 ### Cost equations --> "Loop" of f0/10 7.20/7.21 * CEs [68,69,70,71,72,73,74,75,76,77,78,79,80] --> Loop 68 7.20/7.21 7.20/7.21 ### Ranking functions of CR f0(A,B,C,D,E,F,G,H,I,L) 7.20/7.21 7.20/7.21 #### Partial ranking functions of CR f0(A,B,C,D,E,F,G,H,I,L) 7.20/7.21 7.20/7.21 7.20/7.21 Computing Bounds 7.20/7.21 ===================================== 7.20/7.21 7.20/7.21 #### Cost of chains of f9(A,B,C,D,E,F,G,H,I,L,M,N,O,P,Q,R,S,T,U): 7.20/7.21 * Chain [[47,48,49,50,55,57,58,59,60,61,62],63]: 5*it(47)+1*it(57)+5*it(58)+0 7.20/7.21 Such that:aux(2) =< -6*B+3*C+2*F+4 7.20/7.21 aux(2) =< -2*B+C+2 7.20/7.21 aux(1) =< C 7.20/7.21 aux(31) =< -B+2 7.20/7.21 it(58) =< aux(31) 7.20/7.21 it(57) =< it(58)*2+it(58)*2+it(58)*2+it(58)*2+it(58)*2+aux(2) 7.20/7.21 it(57) =< it(58)*2+it(58)*2+it(58)*2+it(58)*2+it(58)*2+aux(1) 7.20/7.21 7.20/7.21 with precondition: [L=3,B=A+1,D=E,1>=D,B>=1,D>=0,C+2>=2*B,F+1>=B,B>=C] 7.20/7.21 7.20/7.21 * Chain [[47,48,49,50,55,57,58,59,60,61,62],56,64]: 5*it(47)+1*it(57)+5*it(58)+1 7.20/7.21 Such that:aux(2) =< A 7.20/7.21 aux(32) =< -A+1 7.20/7.21 aux(33) =< C 7.20/7.21 aux(2) =< aux(33) 7.20/7.21 it(58) =< aux(32) 7.20/7.21 it(57) =< it(58)*2+it(58)*2+it(58)*2+it(58)*2+it(58)*2+aux(2) 7.20/7.21 it(57) =< it(58)*2+it(58)*2+it(58)*2+it(58)*2+it(58)*2+aux(33) 7.20/7.21 7.20/7.21 with precondition: [L=2,M=1,N=2,O=1,P=1,Q=0,R=0,S=1,T=0,U=1,B=A+1,D=E,1>=D,B>=1,D>=0,C+2>=2*B,F+1>=B,B>=C] 7.20/7.21 7.20/7.21 * Chain [[47,48,49,50,55,57,58,59,60,61,62],56,63]: 5*it(47)+1*it(57)+5*it(58)+1 7.20/7.21 Such that:aux(2) =< A 7.20/7.21 aux(34) =< -B+2 7.20/7.21 aux(35) =< C 7.20/7.21 aux(2) =< aux(35) 7.20/7.21 it(58) =< aux(34) 7.20/7.21 it(57) =< it(58)*2+it(58)*2+it(58)*2+it(58)*2+it(58)*2+aux(2) 7.20/7.21 it(57) =< it(58)*2+it(58)*2+it(58)*2+it(58)*2+it(58)*2+aux(35) 7.20/7.21 7.20/7.21 with precondition: [L=3,B=A+1,D=E,1>=D,B>=1,D>=0,C+2>=2*B,F+1>=B,B>=C] 7.20/7.21 7.20/7.21 * Chain [[47,48,49,50,55,57,58,59,60,61,62],54,65]: 5*it(47)+1*it(57)+5*it(58)+1 7.20/7.21 Such that:aux(2) =< B-O 7.20/7.21 aux(1) =< C 7.20/7.21 aux(2) =< C-O 7.20/7.21 aux(36) =< -B+2 7.20/7.21 aux(37) =< -B+N 7.20/7.21 it(58) =< aux(36) 7.20/7.22 it(58) =< aux(37) 7.20/7.22 it(57) =< it(58)*2+it(58)*2+it(58)*2+it(58)*2+it(58)*2+aux(2) 7.20/7.22 it(57) =< it(58)*2+it(58)*2+it(58)*2+it(58)*2+it(58)*2+aux(1) 7.20/7.22 7.20/7.22 with precondition: [L=2,P=0,Q=1,U=0,B=A+1,D=E,M+1=N,1>=D,0>=T+1,B>=1,D>=0,R>=0,O>=2*M,M+1>=O,F+2*M>=2*B,C+2*M+2>=2*B+O,B+O>=C+M+1] 7.20/7.22 7.20/7.22 * Chain [[47,48,49,50,55,57,58,59,60,61,62],54,63]: 5*it(47)+1*it(57)+5*it(58)+1 7.20/7.22 Such that:aux(2) =< -6*B+3*C+2*F+4 7.20/7.22 aux(2) =< -2*B+C+2 7.20/7.22 aux(1) =< C 7.20/7.22 aux(38) =< -B+2 7.20/7.22 it(58) =< aux(38) 7.20/7.22 it(57) =< it(58)*2+it(58)*2+it(58)*2+it(58)*2+it(58)*2+aux(2) 7.20/7.22 it(57) =< it(58)*2+it(58)*2+it(58)*2+it(58)*2+it(58)*2+aux(1) 7.20/7.22 7.20/7.22 with precondition: [L=3,B=A+1,D=E,1>=D,B>=1,D>=0,C+2>=2*B,F+2>=2*B,B>=C] 7.20/7.22 7.20/7.22 * Chain [[47,48,49,50,55,57,58,59,60,61,62],53,65]: 5*it(47)+1*it(57)+5*it(58)+1 7.20/7.22 Such that:aux(2) =< B-O 7.20/7.22 aux(1) =< C 7.20/7.22 aux(2) =< C-O 7.20/7.22 aux(39) =< -B+2 7.20/7.22 aux(40) =< -B+N 7.20/7.22 it(58) =< aux(39) 7.20/7.22 it(58) =< aux(40) 7.20/7.22 it(57) =< it(58)*2+it(58)*2+it(58)*2+it(58)*2+it(58)*2+aux(2) 7.20/7.22 it(57) =< it(58)*2+it(58)*2+it(58)*2+it(58)*2+it(58)*2+aux(1) 7.20/7.22 7.20/7.22 with precondition: [L=2,P=0,Q=1,U=0,B=A+1,D=E,M+1=N,1>=D,B>=1,D>=0,R>=0,T>=1,O>=2*M,M+1>=O,F+2*M>=2*B,C+2*M+2>=2*B+O,B+O>=C+M+1] 7.20/7.22 7.20/7.22 * Chain [[47,48,49,50,55,57,58,59,60,61,62],53,63]: 5*it(47)+1*it(57)+5*it(58)+1 7.20/7.22 Such that:aux(2) =< -6*B+3*C+2*F+4 7.20/7.22 aux(2) =< -2*B+C+2 7.20/7.22 aux(1) =< C 7.20/7.22 aux(41) =< -B+2 7.20/7.22 it(58) =< aux(41) 7.20/7.22 it(57) =< it(58)*2+it(58)*2+it(58)*2+it(58)*2+it(58)*2+aux(2) 7.20/7.22 it(57) =< it(58)*2+it(58)*2+it(58)*2+it(58)*2+it(58)*2+aux(1) 7.20/7.22 7.20/7.22 with precondition: [L=3,B=A+1,D=E,1>=D,B>=1,D>=0,C+2>=2*B,F+2>=2*B,B>=C] 7.20/7.22 7.20/7.22 * Chain [[47,48,49,50,55,57,58,59,60,61,62],52,64]: 5*it(47)+1*it(57)+5*it(58)+1 7.20/7.22 Such that:aux(2) =< B-O 7.20/7.22 aux(1) =< C 7.20/7.22 aux(2) =< C-O 7.20/7.22 aux(42) =< -B+2 7.20/7.22 aux(43) =< -B+N 7.20/7.22 it(58) =< aux(42) 7.20/7.22 it(58) =< aux(43) 7.20/7.22 it(57) =< it(58)*2+it(58)*2+it(58)*2+it(58)*2+it(58)*2+aux(2) 7.20/7.22 it(57) =< it(58)*2+it(58)*2+it(58)*2+it(58)*2+it(58)*2+aux(1) 7.20/7.22 7.20/7.22 with precondition: [L=2,P=1,Q=0,T=0,B=A+1,D=E,M+1=N,1>=D,0>=U+1,B>=1,D>=0,R>=0,O>=2*M,M+1>=O,F+2*M>=2*B,C+2*M+2>=2*B+O,B+O>=C+M+1] 7.20/7.22 7.20/7.22 * Chain [[47,48,49,50,55,57,58,59,60,61,62],52,63]: 5*it(47)+1*it(57)+5*it(58)+1 7.20/7.22 Such that:aux(2) =< -6*B+3*C+2*F+4 7.20/7.22 aux(2) =< -2*B+C+2 7.20/7.22 aux(1) =< C 7.20/7.22 aux(44) =< -B+2 7.20/7.22 it(58) =< aux(44) 7.20/7.22 it(57) =< it(58)*2+it(58)*2+it(58)*2+it(58)*2+it(58)*2+aux(2) 7.20/7.22 it(57) =< it(58)*2+it(58)*2+it(58)*2+it(58)*2+it(58)*2+aux(1) 7.20/7.22 7.20/7.22 with precondition: [L=3,B=A+1,D=E,1>=D,B>=1,D>=0,C+2>=2*B,F+2>=2*B,B>=C] 7.20/7.22 7.20/7.22 * Chain [[47,48,49,50,55,57,58,59,60,61,62],51,64]: 5*it(47)+1*it(57)+5*it(58)+1 7.20/7.22 Such that:aux(2) =< B-O 7.20/7.22 aux(1) =< C 7.20/7.22 aux(2) =< C-O 7.20/7.22 aux(45) =< -B+2 7.20/7.22 aux(46) =< -B+N 7.20/7.22 it(58) =< aux(45) 7.20/7.22 it(58) =< aux(46) 7.20/7.22 it(57) =< it(58)*2+it(58)*2+it(58)*2+it(58)*2+it(58)*2+aux(2) 7.20/7.22 it(57) =< it(58)*2+it(58)*2+it(58)*2+it(58)*2+it(58)*2+aux(1) 7.20/7.22 7.20/7.22 with precondition: [L=2,P=1,Q=0,T=0,B=A+1,D=E,M+1=N,1>=D,B>=1,D>=0,R>=0,U>=1,O>=2*M,M+1>=O,F+2*M>=2*B,C+2*M+2>=2*B+O,B+O>=C+M+1] 7.20/7.22 7.20/7.22 * Chain [[47,48,49,50,55,57,58,59,60,61,62],51,63]: 5*it(47)+1*it(57)+5*it(58)+1 7.20/7.22 Such that:aux(2) =< -6*B+3*C+2*F+4 7.20/7.22 aux(2) =< -2*B+C+2 7.20/7.22 aux(1) =< C 7.20/7.22 aux(47) =< -B+2 7.20/7.22 it(58) =< aux(47) 7.20/7.22 it(57) =< it(58)*2+it(58)*2+it(58)*2+it(58)*2+it(58)*2+aux(2) 7.20/7.22 it(57) =< it(58)*2+it(58)*2+it(58)*2+it(58)*2+it(58)*2+aux(1) 7.20/7.22 7.20/7.22 with precondition: [L=3,B=A+1,D=E,1>=D,B>=1,D>=0,C+2>=2*B,F+2>=2*B,B>=C] 7.20/7.22 7.20/7.22 * Chain [63]: 0 7.20/7.22 with precondition: [L=3,B=A+1,2>=B,1>=D,1>=E,B>=1,D>=0,E>=0,C+1>=B,B>=C,C+3>=2*B+E,C+D+2>=2*B] 7.20/7.22 7.20/7.22 * Chain [54,65]: 1 7.20/7.22 with precondition: [L=2,P=0,Q=1,U=0,M=A,M+1=B,D=E,R+1=F,M+1=N,C=O,G=S,1>=D,0>=T+1,D>=0,M>=0,R>=0,C>=2*M,M+1>=C] 7.20/7.22 7.20/7.22 * Chain [54,63]: 1 7.20/7.22 with precondition: [L=3,B=A+1,D=E,1>=D,B>=1,D>=0,F>=1,C+2>=2*B,B>=C] 7.20/7.22 7.20/7.22 * Chain [53,65]: 1 7.20/7.22 with precondition: [L=2,P=0,Q=1,U=0,M=A,M+1=B,D=E,R+1=F,M+1=N,C=O,G=S,1>=D,D>=0,M>=0,R>=0,T>=1,C>=2*M,M+1>=C] 7.20/7.22 7.20/7.22 * Chain [53,63]: 1 7.20/7.22 with precondition: [L=3,B=A+1,D=E,1>=D,B>=1,D>=0,F>=1,C+2>=2*B,B>=C] 7.20/7.22 7.20/7.22 * Chain [52,64]: 1 7.20/7.22 with precondition: [L=2,P=1,Q=0,T=0,M=A,M+1=B,D=E,R+1=F,M+1=N,C=O,G=S,1>=D,0>=U+1,D>=0,M>=0,R>=0,C>=2*M,M+1>=C] 7.20/7.22 7.20/7.22 * Chain [52,63]: 1 7.20/7.22 with precondition: [L=3,B=A+1,D=E,1>=D,B>=1,D>=0,F>=1,C+2>=2*B,B>=C] 7.20/7.22 7.20/7.22 * Chain [51,64]: 1 7.20/7.22 with precondition: [L=2,P=1,Q=0,T=0,M=A,M+1=B,D=E,R+1=F,M+1=N,C=O,G=S,1>=D,D>=0,M>=0,R>=0,U>=1,C>=2*M,M+1>=C] 7.20/7.22 7.20/7.22 * Chain [51,63]: 1 7.20/7.22 with precondition: [L=3,B=A+1,D=E,1>=D,B>=1,D>=0,F>=1,C+2>=2*B,B>=C] 7.20/7.22 7.20/7.22 7.20/7.22 #### Cost of chains of f9_loop_cont(A,B,C,D,E,F,G,H,I,J,K): 7.20/7.22 * Chain [67]: 0 7.20/7.22 with precondition: [A=2] 7.20/7.22 7.20/7.22 * Chain [66]: 0 7.20/7.22 with precondition: [A=3] 7.20/7.22 7.20/7.22 7.20/7.22 #### Cost of chains of f0(A,B,C,D,E,F,G,H,I,L): 7.20/7.22 * Chain [68]: 1*aux(62)+0 7.20/7.22 with precondition: [] 7.20/7.22 7.20/7.22 7.20/7.22 Closed-form bounds of f0(A,B,C,D,E,F,G,H,I,L): 7.20/7.22 ------------------------------------- 7.20/7.22 * Chain [68] with precondition: [] 7.20/7.22 - Upper bound: inf 7.20/7.22 - Complexity: infinity 7.20/7.22 7.20/7.22 ### Maximum cost of f0(A,B,C,D,E,F,G,H,I,L): inf 7.20/7.22 Asymptotic class: infinity 7.20/7.22 * Total analysis performed in 6921 ms. 7.20/7.22 7.22/7.32 EOF