0.92/0.92 WORST_CASE(?,O(n^2)) 0.92/0.92 0.92/0.92 Preprocessing Cost Relations 0.92/0.92 ===================================== 0.92/0.92 0.92/0.92 #### Computed strongly connected components 0.92/0.92 0. recursive : [lbl101/13] 0.92/0.92 1. recursive : [lbl101_loop_cont/14,lbl121/13] 0.92/0.92 2. non_recursive : [exit_location/1] 0.92/0.92 3. non_recursive : [stop/7] 0.92/0.92 4. non_recursive : [lbl121_loop_cont/8] 0.92/0.92 5. non_recursive : [start/7] 0.92/0.92 6. non_recursive : [start0/7] 0.92/0.92 0.92/0.92 #### Obtained direct recursion through partial evaluation 0.92/0.92 0. SCC is partially evaluated into lbl101/13 0.92/0.92 1. SCC is partially evaluated into lbl121/13 0.92/0.92 2. SCC is completely evaluated into other SCCs 0.92/0.92 3. SCC is completely evaluated into other SCCs 0.92/0.92 4. SCC is partially evaluated into lbl121_loop_cont/8 0.92/0.92 5. SCC is partially evaluated into start/7 0.92/0.92 6. SCC is partially evaluated into start0/7 0.92/0.92 0.92/0.92 Control-Flow Refinement of Cost Relations 0.92/0.92 ===================================== 0.92/0.92 0.92/0.92 ### Specialization of cost equations lbl101/13 0.92/0.92 * CE 8 is refined into CE [16] 0.92/0.92 * CE 7 is refined into CE [17] 0.92/0.92 * CE 6 is refined into CE [18] 0.92/0.92 0.92/0.92 0.92/0.92 ### Cost equations --> "Loop" of lbl101/13 0.92/0.92 * CEs [18] --> Loop 15 0.92/0.92 * CEs [16] --> Loop 16 0.92/0.92 * CEs [17] --> Loop 17 0.92/0.92 0.92/0.92 ### Ranking functions of CR lbl101(A,B,C,D,E,F,G,H,I,J,K,L,M) 0.92/0.92 * RF of phase [15]: [A-B,-B+D,-B+F] 0.92/0.92 0.92/0.92 #### Partial ranking functions of CR lbl101(A,B,C,D,E,F,G,H,I,J,K,L,M) 0.92/0.92 * Partial RF of phase [15]: 0.92/0.92 - RF of loop [15:1]: 0.92/0.92 A-B 0.92/0.92 -B+D 0.92/0.92 -B+F 0.92/0.92 0.92/0.92 0.92/0.92 ### Specialization of cost equations lbl121/13 0.92/0.92 * CE 11 is refined into CE [19,20] 0.92/0.92 * CE 15 is refined into CE [21] 0.92/0.92 * CE 13 is refined into CE [22] 0.92/0.92 * CE 12 is refined into CE [23,24] 0.92/0.92 * CE 14 is refined into CE [25] 0.92/0.92 0.92/0.92 0.92/0.92 ### Cost equations --> "Loop" of lbl121/13 0.92/0.92 * CEs [24] --> Loop 18 0.92/0.92 * CEs [25] --> Loop 19 0.92/0.92 * CEs [23] --> Loop 20 0.92/0.92 * CEs [20] --> Loop 21 0.92/0.92 * CEs [19] --> Loop 22 0.92/0.92 * CEs [21] --> Loop 23 0.92/0.92 * CEs [22] --> Loop 24 0.92/0.92 0.92/0.92 ### Ranking functions of CR lbl121(A,B,C,D,E,F,G,H,I,J,K,L,M) 0.92/0.92 * RF of phase [18]: [D-2] 0.92/0.92 * RF of phase [19]: [D+1] 0.92/0.92 0.92/0.92 #### Partial ranking functions of CR lbl121(A,B,C,D,E,F,G,H,I,J,K,L,M) 0.92/0.92 * Partial RF of phase [18]: 0.92/0.92 - RF of loop [18:1]: 0.92/0.92 D-2 0.92/0.92 * Partial RF of phase [19]: 0.92/0.92 - RF of loop [19:1]: 0.92/0.92 D+1 0.92/0.92 0.92/0.92 0.92/0.92 ### Specialization of cost equations lbl121_loop_cont/8 0.92/0.92 * CE 9 is refined into CE [26] 0.92/0.92 * CE 10 is refined into CE [27] 0.92/0.92 0.92/0.92 0.92/0.92 ### Cost equations --> "Loop" of lbl121_loop_cont/8 0.92/0.92 * CEs [26] --> Loop 25 0.92/0.92 * CEs [27] --> Loop 26 0.92/0.92 0.92/0.92 ### Ranking functions of CR lbl121_loop_cont(A,B,C,D,E,F,G,H) 0.92/0.92 0.92/0.92 #### Partial ranking functions of CR lbl121_loop_cont(A,B,C,D,E,F,G,H) 0.92/0.92 0.92/0.92 0.92/0.92 ### Specialization of cost equations start/7 0.92/0.92 * CE 2 is refined into CE [28,29] 0.92/0.92 * CE 3 is refined into CE [30,31,32,33,34,35,36,37,38,39] 0.92/0.92 * CE 4 is refined into CE [40] 0.92/0.92 * CE 5 is refined into CE [41,42,43,44] 0.92/0.92 0.92/0.92 0.92/0.92 ### Cost equations --> "Loop" of start/7 0.92/0.92 * CEs [38] --> Loop 27 0.92/0.92 * CEs [37,39] --> Loop 28 0.92/0.92 * CEs [29,35,36] --> Loop 29 0.92/0.92 * CEs [28] --> Loop 30 0.92/0.92 * CEs [40] --> Loop 31 0.92/0.92 * CEs [42] --> Loop 32 0.92/0.92 * CEs [33,34] --> Loop 33 0.92/0.92 * CEs [30,31,32] --> Loop 34 0.92/0.92 * CEs [43,44] --> Loop 35 0.92/0.92 * CEs [41] --> Loop 36 0.92/0.92 0.92/0.92 ### Ranking functions of CR start(A,B,C,D,E,F,G) 0.92/0.92 0.92/0.92 #### Partial ranking functions of CR start(A,B,C,D,E,F,G) 0.92/0.92 0.92/0.92 0.92/0.92 ### Specialization of cost equations start0/7 0.92/0.92 * CE 1 is refined into CE [45,46,47,48,49,50,51,52,53,54] 0.92/0.92 0.92/0.92 0.92/0.92 ### Cost equations --> "Loop" of start0/7 0.92/0.92 * CEs [54] --> Loop 37 0.92/0.92 * CEs [53] --> Loop 38 0.92/0.92 * CEs [52] --> Loop 39 0.92/0.92 * CEs [51] --> Loop 40 0.92/0.92 * CEs [50] --> Loop 41 0.92/0.92 * CEs [49] --> Loop 42 0.92/0.92 * CEs [48] --> Loop 43 0.92/0.92 * CEs [47] --> Loop 44 0.92/0.92 * CEs [46] --> Loop 45 0.92/0.92 * CEs [45] --> Loop 46 0.92/0.92 0.92/0.92 ### Ranking functions of CR start0(A,B,C,D,E,F,G) 0.92/0.92 0.92/0.92 #### Partial ranking functions of CR start0(A,B,C,D,E,F,G) 0.92/0.92 0.92/0.92 0.92/0.92 Computing Bounds 0.92/0.92 ===================================== 0.92/0.92 0.92/0.92 #### Cost of chains of lbl101(A,B,C,D,E,F,G,H,I,J,K,L,M): 0.92/0.92 * Chain [[15],17]: 1*it(15)+0 0.92/0.92 Such that:it(15) =< -B+K+1 0.92/0.92 0.92/0.92 with precondition: [G=2,A=F,A=H,C=J,D=K+1,E=L,A=M,B>=2,I>=2*B,A>=D,I>=D,2*D>=I+2] 0.92/0.92 0.92/0.92 * Chain [[15],16]: 1*it(15)+0 0.92/0.92 Such that:it(15) =< -B+D 0.92/0.92 0.92/0.92 with precondition: [G=3,A=F,B>=2,D>=B+1,A>=D] 0.92/0.92 0.92/0.92 * Chain [17]: 0 0.92/0.92 with precondition: [G=2,F=A,J=C,L=E,F=H,B=I,D=K+1,F=M,2*D>=B+2,B>=D,F>=D] 0.92/0.92 0.92/0.92 * Chain [16]: 0 0.92/0.92 with precondition: [G=3,F=A,B>=2,2*D>=B+2,F>=D] 0.92/0.92 0.92/0.92 0.92/0.92 #### Cost of chains of lbl121(A,B,C,D,E,F,G,H,I,J,K,L,M): 0.92/0.92 * Chain [[19],24]: 1*it(19)+0 0.92/0.92 Such that:it(19) =< D+1 0.92/0.92 0.92/0.92 with precondition: [G=4,I=1,K+1=0,A=F,A=H,C=J,E=L,A=M,1>=D,D>=0,A>=D+1,B>=D+1] 0.92/0.92 0.92/0.92 * Chain [[19],23]: 1*it(19)+0 0.92/0.92 Such that:it(19) =< D+1 0.92/0.92 0.92/0.92 with precondition: [G=3,A=F,1>=D,D>=0,A>=D+1,B>=D+1] 0.92/0.92 0.92/0.92 * Chain [[18],23]: 1*it(18)+1*s(3)+0 0.92/0.92 Such that:aux(1) =< F 0.92/0.92 aux(3) =< D 0.92/0.92 it(18) =< aux(3) 0.92/0.92 aux(1) =< aux(3) 0.92/0.92 s(3) =< it(18)*aux(1) 0.92/0.92 0.92/0.92 with precondition: [G=3,A=F,D>=3,A>=D+1,B>=D+1] 0.92/0.92 0.92/0.92 * Chain [[18],22]: 1*it(18)+1*s(3)+0 0.92/0.92 Such that:aux(1) =< F 0.92/0.92 aux(4) =< D 0.92/0.92 it(18) =< aux(4) 0.92/0.92 aux(1) =< aux(4) 0.92/0.92 s(3) =< it(18)*aux(1) 0.92/0.92 0.92/0.92 with precondition: [G=3,A=F,D>=3,A>=D+1,B>=D+1] 0.92/0.92 0.92/0.92 * Chain [[18],21]: 2*it(18)+1*s(3)+0 0.92/0.92 Such that:aux(1) =< F 0.92/0.92 aux(5) =< D 0.92/0.92 it(18) =< aux(5) 0.92/0.92 aux(1) =< aux(5) 0.92/0.92 s(3) =< it(18)*aux(1) 0.92/0.92 0.92/0.92 with precondition: [G=3,A=F,D>=4,A>=D+1,B>=D+1] 0.92/0.92 0.92/0.92 * Chain [[18],20,[19],24]: 1*it(18)+1*it(19)+1*s(3)+1 0.92/0.92 Such that:it(19) =< 2 0.92/0.92 aux(1) =< H 0.92/0.92 aux(6) =< D 0.92/0.92 it(18) =< aux(6) 0.92/0.92 aux(1) =< aux(6) 0.92/0.92 s(3) =< it(18)*aux(1) 0.92/0.92 0.92/0.92 with precondition: [G=4,I=1,K+1=0,A=F,A=H,C=J,E=L,A=M,D>=3,A>=D+1,B>=D+1] 0.92/0.92 0.92/0.92 * Chain [[18],20,[19],23]: 1*it(18)+1*it(19)+1*s(3)+1 0.92/0.92 Such that:it(19) =< 2 0.92/0.92 aux(1) =< F 0.92/0.92 aux(7) =< D 0.92/0.92 it(18) =< aux(7) 0.92/0.92 aux(1) =< aux(7) 0.92/0.92 s(3) =< it(18)*aux(1) 0.92/0.92 0.92/0.92 with precondition: [G=3,A=F,D>=3,A>=D+1,B>=D+1] 0.92/0.92 0.92/0.92 * Chain [[18],20,23]: 1*it(18)+1*s(3)+1 0.92/0.92 Such that:aux(1) =< F 0.92/0.92 aux(8) =< D 0.92/0.92 it(18) =< aux(8) 0.92/0.92 aux(1) =< aux(8) 0.92/0.92 s(3) =< it(18)*aux(1) 0.92/0.92 0.92/0.92 with precondition: [G=3,A=F,D>=3,A>=D+1,B>=D+1] 0.92/0.92 0.92/0.92 * Chain [24]: 0 0.92/0.92 with precondition: [D+1=0,G=4,K+1=0,J=C,L=E,A=F,A=H,B=I,A=M,A>=0,B>=1] 0.92/0.92 0.92/0.92 * Chain [23]: 0 0.92/0.92 with precondition: [G=3] 0.92/0.92 0.92/0.92 * Chain [22]: 0 0.92/0.92 with precondition: [G=3,A=F,D>=2,A>=D+1,B>=D+1] 0.92/0.92 0.92/0.92 * Chain [21]: 1*s(4)+0 0.92/0.92 Such that:s(4) =< D 0.92/0.92 0.92/0.92 with precondition: [G=3,A=F,D>=3,A>=D+1,B>=D+1] 0.92/0.92 0.92/0.92 * Chain [20,[19],24]: 1*it(19)+1 0.92/0.92 Such that:it(19) =< 2 0.92/0.92 0.92/0.92 with precondition: [D=2,G=4,I=1,K+1=0,A=F,A=H,C=J,E=L,A=M,A>=3,B>=3] 0.92/0.92 0.92/0.92 * Chain [20,[19],23]: 1*it(19)+1 0.92/0.92 Such that:it(19) =< 2 0.92/0.92 0.92/0.92 with precondition: [D=2,G=3,A=F,A>=3,B>=3] 0.92/0.92 0.92/0.92 * Chain [20,23]: 1 0.92/0.92 with precondition: [D=2,G=3,A=F,A>=3,B>=3] 0.92/0.92 0.92/0.92 0.92/0.92 #### Cost of chains of lbl121_loop_cont(A,B,C,D,E,F,G,H): 0.92/0.92 * Chain [26]: 0 0.92/0.92 with precondition: [A=3] 0.92/0.92 0.92/0.92 * Chain [25]: 0 0.92/0.92 with precondition: [A=4] 0.92/0.92 0.92/0.92 0.92/0.92 #### Cost of chains of start(A,B,C,D,E,F,G): 0.92/0.92 * Chain [36]: 0 0.92/0.92 with precondition: [A=0,F=0,C=B,E=D] 0.92/0.92 0.92/0.92 * Chain [35]: 2 0.92/0.92 with precondition: [A=1,F=1,C=B,E=D] 0.92/0.92 0.92/0.92 * Chain [34]: 5 0.92/0.92 with precondition: [A=2,F=2,C=B,E=D] 0.92/0.92 0.92/0.92 * Chain [33]: 8 0.92/0.92 with precondition: [A=3,F=3,C=B,E=D] 0.92/0.92 0.92/0.92 * Chain [32]: 0 0.92/0.92 with precondition: [F=A,C=B,E=D,1>=F,F>=0] 0.92/0.92 0.92/0.92 * Chain [31]: 0 0.92/0.92 with precondition: [F=A,C=B,E=D,0>=F+1] 0.92/0.92 0.92/0.92 * Chain [30]: 0 0.92/0.92 with precondition: [F=A,C=B,E=D,F>=2] 0.92/0.92 0.92/0.92 * Chain [29]: 3*s(31)+1 0.92/0.92 Such that:aux(14) =< F 0.92/0.92 s(31) =< aux(14) 0.92/0.92 0.92/0.92 with precondition: [F=A,C=B,E=D,F>=3] 0.92/0.92 0.92/0.92 * Chain [28]: 8*s(34)+2*s(35)+5*s(40)+2 0.92/0.92 Such that:aux(17) =< 2 0.92/0.92 aux(18) =< F 0.92/0.92 s(35) =< aux(17) 0.92/0.92 s(34) =< aux(18) 0.92/0.92 s(40) =< s(34)*aux(18) 0.92/0.92 0.92/0.92 with precondition: [F=A,C=B,E=D,F>=4] 0.92/0.92 0.92/0.92 * Chain [27]: 3*s(47)+1*s(51)+1 0.92/0.92 Such that:aux(19) =< F 0.92/0.92 s(47) =< aux(19) 0.92/0.92 s(51) =< s(47)*aux(19) 0.92/0.92 0.92/0.92 with precondition: [F=A,C=B,E=D,F>=5] 0.92/0.92 0.92/0.92 0.92/0.92 #### Cost of chains of start0(A,B,C,D,E,F,G): 0.92/0.92 * Chain [46]: 0 0.92/0.92 with precondition: [A=0] 0.92/0.92 0.92/0.92 * Chain [45]: 2 0.92/0.92 with precondition: [A=1] 0.92/0.92 0.92/0.92 * Chain [44]: 5 0.92/0.92 with precondition: [A=2] 0.92/0.92 0.92/0.92 * Chain [43]: 8 0.92/0.92 with precondition: [A=3] 0.92/0.92 0.92/0.92 * Chain [42]: 0 0.92/0.92 with precondition: [1>=A,A>=0] 0.92/0.92 0.92/0.92 * Chain [41]: 0 0.92/0.92 with precondition: [0>=A+1] 0.92/0.92 0.92/0.92 * Chain [40]: 0 0.92/0.92 with precondition: [A>=2] 0.92/0.92 0.92/0.92 * Chain [39]: 3*s(53)+1 0.92/0.92 Such that:s(52) =< A 0.92/0.92 s(53) =< s(52) 0.92/0.92 0.92/0.92 with precondition: [A>=3] 0.92/0.92 0.92/0.92 * Chain [38]: 2*s(56)+8*s(57)+5*s(58)+2 0.92/0.92 Such that:s(54) =< 2 0.92/0.92 s(55) =< A 0.92/0.92 s(56) =< s(54) 0.92/0.92 s(57) =< s(55) 0.92/0.92 s(58) =< s(57)*s(55) 0.92/0.92 0.92/0.92 with precondition: [A>=4] 0.92/0.92 0.92/0.92 * Chain [37]: 3*s(60)+1*s(61)+1 0.92/0.92 Such that:s(59) =< A 0.92/0.92 s(60) =< s(59) 0.92/0.92 s(61) =< s(60)*s(59) 0.92/0.92 0.92/0.92 with precondition: [A>=5] 0.92/0.92 0.92/0.92 0.92/0.92 Closed-form bounds of start0(A,B,C,D,E,F,G): 0.92/0.92 ------------------------------------- 0.92/0.92 * Chain [46] with precondition: [A=0] 0.92/0.92 - Upper bound: 0 0.92/0.92 - Complexity: constant 0.92/0.92 * Chain [45] with precondition: [A=1] 0.92/0.92 - Upper bound: 2 0.92/0.92 - Complexity: constant 0.92/0.92 * Chain [44] with precondition: [A=2] 0.92/0.92 - Upper bound: 5 0.92/0.92 - Complexity: constant 0.92/0.92 * Chain [43] with precondition: [A=3] 0.92/0.92 - Upper bound: 8 0.92/0.92 - Complexity: constant 0.92/0.92 * Chain [42] with precondition: [1>=A,A>=0] 0.92/0.92 - Upper bound: 0 0.92/0.92 - Complexity: constant 0.92/0.92 * Chain [41] with precondition: [0>=A+1] 0.92/0.92 - Upper bound: 0 0.92/0.92 - Complexity: constant 0.92/0.92 * Chain [40] with precondition: [A>=2] 0.92/0.92 - Upper bound: 0 0.92/0.92 - Complexity: constant 0.92/0.92 * Chain [39] with precondition: [A>=3] 0.92/0.92 - Upper bound: 3*A+1 0.92/0.92 - Complexity: n 0.92/0.92 * Chain [38] with precondition: [A>=4] 0.92/0.92 - Upper bound: 8*A+6+5*A*A 0.92/0.92 - Complexity: n^2 0.92/0.92 * Chain [37] with precondition: [A>=5] 0.92/0.92 - Upper bound: 3*A+1+A*A 0.92/0.92 - Complexity: n^2 0.92/0.92 0.92/0.92 ### Maximum cost of start0(A,B,C,D,E,F,G): max([8,nat(A)*5+5+nat(A)*4*nat(A)+nat(A)*nat(A)+(nat(A)*3+1)]) 0.92/0.92 Asymptotic class: n^2 0.92/0.92 * Total analysis performed in 814 ms. 0.92/0.92 0.92/1.02 EOF