1.81/1.86 MAYBE 1.81/1.86 1.81/1.86 Preprocessing Cost Relations 1.81/1.86 ===================================== 1.81/1.86 1.81/1.86 #### Computed strongly connected components 1.81/1.86 0. recursive : [f2/11] 1.81/1.86 1. recursive : [f2_loop_cont/12,f4/11] 1.81/1.86 2. recursive : [f300/11,f4_loop_cont/12] 1.81/1.86 3. non_recursive : [exit_location/1] 1.81/1.86 4. non_recursive : [f1/6] 1.81/1.86 5. non_recursive : [f300_loop_cont/7] 1.81/1.86 6. non_recursive : [f5/6] 1.81/1.86 1.81/1.86 #### Obtained direct recursion through partial evaluation 1.81/1.86 0. SCC is partially evaluated into f2/11 1.81/1.86 1. SCC is partially evaluated into f4/11 1.81/1.86 2. SCC is partially evaluated into f300/11 1.81/1.86 3. SCC is completely evaluated into other SCCs 1.81/1.86 4. SCC is completely evaluated into other SCCs 1.81/1.86 5. SCC is partially evaluated into f300_loop_cont/7 1.81/1.86 6. SCC is partially evaluated into f5/6 1.81/1.86 1.81/1.86 Control-Flow Refinement of Cost Relations 1.81/1.86 ===================================== 1.81/1.86 1.81/1.86 ### Specialization of cost equations f2/11 1.81/1.86 * CE 17 is refined into CE [24] 1.81/1.86 * CE 14 is refined into CE [25] 1.81/1.86 * CE 15 is refined into CE [26] 1.81/1.86 * CE 16 is refined into CE [27] 1.81/1.86 1.81/1.86 1.81/1.86 ### Cost equations --> "Loop" of f2/11 1.81/1.86 * CEs [27] --> Loop 19 1.81/1.86 * CEs [24] --> Loop 20 1.81/1.86 * CEs [25] --> Loop 21 1.81/1.86 * CEs [26] --> Loop 22 1.81/1.86 1.81/1.86 ### Ranking functions of CR f2(A,B,C,D,E,G,H,I,J,K,L) 1.81/1.86 1.81/1.86 #### Partial ranking functions of CR f2(A,B,C,D,E,G,H,I,J,K,L) 1.81/1.86 1.81/1.86 1.81/1.86 ### Specialization of cost equations f4/11 1.81/1.86 * CE 20 is refined into CE [28] 1.81/1.86 * CE 18 is refined into CE [29,30] 1.81/1.86 * CE 23 is refined into CE [31] 1.81/1.86 * CE 19 is refined into CE [32,33,34,35,36] 1.81/1.86 * CE 21 is refined into CE [37] 1.81/1.86 * CE 22 is refined into CE [38] 1.81/1.86 1.81/1.86 1.81/1.86 ### Cost equations --> "Loop" of f4/11 1.81/1.86 * CEs [33,35,37] --> Loop 23 1.81/1.86 * CEs [32,34,38] --> Loop 24 1.81/1.86 * CEs [36] --> Loop 25 1.81/1.86 * CEs [28] --> Loop 26 1.81/1.86 * CEs [29] --> Loop 27 1.81/1.86 * CEs [31] --> Loop 28 1.81/1.86 * CEs [30] --> Loop 29 1.81/1.86 1.81/1.86 ### Ranking functions of CR f4(A,B,C,D,E,G,H,I,J,K,L) 1.81/1.86 1.81/1.86 #### Partial ranking functions of CR f4(A,B,C,D,E,G,H,I,J,K,L) 1.81/1.86 * Partial RF of phase [23,24,25]: 1.81/1.86 - RF of loop [23:1,24:1]: 1.81/1.86 -A+B depends on loops [25:1] 1.81/1.86 1.81/1.86 1.81/1.86 ### Specialization of cost equations f300/11 1.81/1.86 * CE 9 is refined into CE [39] 1.81/1.86 * CE 2 is refined into CE [40,41] 1.81/1.86 * CE 3 is refined into CE [42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61] 1.81/1.86 * CE 4 is refined into CE [62,63,64,65] 1.81/1.86 * CE 5 is refined into CE [66,67,68,69] 1.81/1.86 * CE 11 is refined into CE [70] 1.81/1.86 * CE 6 is refined into CE [71,72,73,74,75,76,77,78,79,80,81,82,83,84,85] 1.81/1.86 * CE 7 is refined into CE [86,87,88] 1.81/1.86 * CE 8 is refined into CE [89,90,91] 1.81/1.86 * CE 10 is refined into CE [92] 1.81/1.86 1.81/1.86 1.81/1.86 ### Cost equations --> "Loop" of f300/11 1.81/1.86 * CEs [72,75,78,81,87,90] --> Loop 30 1.81/1.86 * CEs [92] --> Loop 31 1.81/1.86 * CEs [74,80,89] --> Loop 32 1.81/1.86 * CEs [71,77,86] --> Loop 33 1.81/1.86 * CEs [73,76,79,82,88,91] --> Loop 34 1.81/1.86 * CEs [83,84] --> Loop 35 1.81/1.86 * CEs [85] --> Loop 36 1.81/1.86 * CEs [39] --> Loop 37 1.81/1.86 * CEs [43,47,51,55,63,67] --> Loop 38 1.81/1.86 * CEs [40,42,46,50,54,62,66] --> Loop 39 1.81/1.86 * CEs [70] --> Loop 40 1.81/1.86 * CEs [44,45,48,49,52,53,56,57,64,65,68,69] --> Loop 41 1.81/1.86 * CEs [41,58,59,60,61] --> Loop 42 1.81/1.86 1.81/1.86 ### Ranking functions of CR f300(A,B,C,D,E,G,H,I,J,K,L) 1.81/1.86 * RF of phase [31]: [A-C] 1.81/1.86 1.81/1.86 #### Partial ranking functions of CR f300(A,B,C,D,E,G,H,I,J,K,L) 1.81/1.86 * Partial RF of phase [31]: 1.81/1.86 - RF of loop [31:1]: 1.81/1.86 A-C 1.81/1.86 1.81/1.86 1.81/1.86 ### Specialization of cost equations f300_loop_cont/7 1.81/1.86 * CE 12 is refined into CE [93] 1.81/1.86 * CE 13 is refined into CE [94] 1.81/1.86 1.81/1.86 1.81/1.86 ### Cost equations --> "Loop" of f300_loop_cont/7 1.81/1.86 * CEs [93] --> Loop 43 1.81/1.86 * CEs [94] --> Loop 44 1.81/1.86 1.81/1.86 ### Ranking functions of CR f300_loop_cont(A,B,C,D,E,F,G) 1.81/1.86 1.81/1.86 #### Partial ranking functions of CR f300_loop_cont(A,B,C,D,E,F,G) 1.81/1.86 1.81/1.86 1.81/1.86 ### Specialization of cost equations f5/6 1.81/1.86 * CE 1 is refined into CE [95,96,97,98,99,100,101,102,103,104,105,106,107,108,109,110,111,112,113,114] 1.81/1.86 1.81/1.86 1.81/1.86 ### Cost equations --> "Loop" of f5/6 1.81/1.86 * CEs [112] --> Loop 45 1.81/1.86 * CEs [111,113,114] --> Loop 46 1.81/1.86 * CEs [99,103] --> Loop 47 1.81/1.86 * CEs [102] --> Loop 48 1.81/1.86 * CEs [98,107,110] --> Loop 49 1.81/1.86 * CEs [97,104,105,106,108,109] --> Loop 50 1.81/1.86 * CEs [96,100,101] --> Loop 51 1.81/1.86 * CEs [95] --> Loop 52 1.81/1.86 1.81/1.86 ### Ranking functions of CR f5(A,B,C,D,E,G) 1.81/1.86 1.81/1.86 #### Partial ranking functions of CR f5(A,B,C,D,E,G) 1.81/1.86 1.81/1.86 1.81/1.86 Computing Bounds 1.81/1.86 ===================================== 1.81/1.86 1.81/1.86 #### Cost of chains of f2(A,B,C,D,E,G,H,I,J,K,L): 1.81/1.86 * Chain [[19]]...: 1*it(19)+0 1.81/1.86 with precondition: [B>=A+1,D=0,G>=2,3>=G] 1.81/1.86 1.81/1.86 * Chain [[19],22]: 1*it(19)+0 1.81/1.86 with precondition: [D=0,G=2,A+1=H,B=I,C=J,E=L,0>=K+1,B>=A+1] 1.81/1.86 1.81/1.86 * Chain [[19],21]: 1*it(19)+0 1.81/1.86 with precondition: [D=0,G=2,A+1=H,B=I,C=J,E=L,K>=1,B>=A+1] 1.81/1.86 1.81/1.86 * Chain [[19],20]: 1*it(19)+0 1.81/1.86 with precondition: [D=0,G=3,B>=A+1] 1.81/1.86 1.81/1.86 * Chain [22]: 0 1.81/1.86 with precondition: [D=0,G=2,J=C,L=E,A+1=H,B=I,0>=K+1,B>=A+1] 1.81/1.86 1.81/1.86 * Chain [21]: 0 1.81/1.86 with precondition: [D=0,G=2,J=C,L=E,A+1=H,B=I,K>=1,B>=A+1] 1.81/1.86 1.81/1.86 * Chain [20]: 0 1.81/1.86 with precondition: [D=0,G=3,B>=A+1] 1.81/1.86 1.81/1.86 1.81/1.86 #### Cost of chains of f4(A,B,C,D,E,G,H,I,J,K,L): 1.81/1.86 * Chain [[23,24,25]]...: 4*it(25)+0 1.81/1.86 with precondition: [B>=A+1,G>=3,4>=G] 1.81/1.86 1.81/1.86 * Chain [[23,24,25],29]...: 5*it(25)+0 1.81/1.86 with precondition: [G=3,B>=A+1] 1.81/1.86 1.81/1.86 * Chain [[23,24,25],28]: 4*it(25)+0 1.81/1.86 with precondition: [G=3,B>=A+1] 1.81/1.86 1.81/1.86 * Chain [[23,24,25],27]: 5*it(25)+0 1.81/1.86 with precondition: [G=3,B>=A+1] 1.81/1.86 1.81/1.86 * Chain [[23,24,25],26]: 4*it(25)+0 1.81/1.86 with precondition: [G=4,B>=A+1,H>=I] 1.81/1.86 1.81/1.86 * Chain [29]...: 1*s(11)+0 1.81/1.86 with precondition: [G=3,B>=A+1] 1.81/1.86 1.81/1.86 * Chain [28]: 0 1.81/1.86 with precondition: [G=3] 1.81/1.86 1.81/1.86 * Chain [27]: 1*s(12)+0 1.81/1.86 with precondition: [G=3,B>=A+1] 1.81/1.86 1.81/1.86 * Chain [26]: 0 1.81/1.86 with precondition: [G=4,J=C+1,K=D,L=E,A=H,B=I,A>=B] 1.81/1.86 1.81/1.86 1.81/1.86 #### Cost of chains of f300(A,B,C,D,E,G,H,I,J,K,L): 1.81/1.86 * Chain [[34,36]]...: 8*it(36)+0 1.81/1.86 with precondition: [A>=C+1,B>=A+1] 1.81/1.86 1.81/1.86 * Chain [[34,36],[31],40]: 8*it(36)+1*s(32)+0 1.81/1.86 with precondition: [G=3,B>=A+1,A>=C+1] 1.81/1.86 1.81/1.86 * Chain [[34,36],[31],37]: 8*it(36)+1*s(33)+0 1.81/1.86 with precondition: [G=5,H=J,B>=A+1,A>=C+1,H>=I] 1.81/1.86 1.81/1.86 * Chain [[34,36],42]...: 9*aux(19)+0 1.81/1.86 with precondition: [G=3,B>=A+1,A>=C+1] 1.81/1.86 1.81/1.86 * Chain [[34,36],41]...: 9*aux(20)+0 1.81/1.86 with precondition: [G=3,B>=A+1,A>=C+1] 1.81/1.86 1.81/1.86 * Chain [[34,36],40]: 8*it(36)+0 1.81/1.86 with precondition: [G=3,B>=A+1,A>=C+1] 1.81/1.86 1.81/1.86 * Chain [[34,36],39]: 9*aux(21)+0 1.81/1.86 with precondition: [G=3,B>=A+1,A>=C+1] 1.81/1.86 1.81/1.86 * Chain [[34,36],38]: 9*aux(22)+0 1.81/1.86 with precondition: [G=3,B>=A+1,A>=C+1] 1.81/1.86 1.81/1.86 * Chain [[34,36],37]: 8*it(36)+0 1.81/1.86 with precondition: [G=5,B>=A+1,A>=C+1,J>=H] 1.81/1.86 1.81/1.86 * Chain [[34,36],35,[31],40]: 10*aux(23)+0 1.81/1.86 with precondition: [G=3,B>=A+1,A>=C+1] 1.81/1.86 1.81/1.86 * Chain [[34,36],35,[31],37]: 10*aux(23)+0 1.81/1.86 with precondition: [G=5,H=J,B>=A+1,A>=C+1,H>=I] 1.81/1.86 1.81/1.86 * Chain [[34,36],35,40]: 9*aux(23)+0 1.81/1.86 with precondition: [G=3,B>=A+1,A>=C+1] 1.81/1.86 1.81/1.86 * Chain [[34,36],35,37]: 9*aux(23)+0 1.81/1.86 with precondition: [G=5,B>=A+1,A>=C+1,J>=H,H>=I] 1.81/1.86 1.81/1.86 * Chain [[34,36],33,[31],40]: 9*it(36)+1*s(74)+0 1.81/1.86 with precondition: [G=3,B>=A+1,A>=C+1] 1.81/1.86 1.81/1.86 * Chain [[34,36],33,[31],37]: 9*it(36)+1*s(76)+0 1.81/1.86 with precondition: [G=5,H=I,H=J,0>=K+1,B>=A+1,A>=C+1] 1.81/1.86 1.81/1.86 * Chain [[34,36],33,40]: 9*aux(24)+0 1.81/1.86 with precondition: [G=3,B>=A+1,A>=C+1] 1.81/1.86 1.81/1.86 * Chain [[34,36],32,[31],40]: 9*it(36)+1*s(79)+0 1.81/1.86 with precondition: [G=3,B>=A+1,A>=C+1] 1.81/1.86 1.81/1.86 * Chain [[34,36],32,[31],37]: 9*it(36)+1*s(81)+0 1.81/1.86 with precondition: [G=5,H=I,H=J,K>=1,B>=A+1,A>=C+1] 1.81/1.86 1.81/1.86 * Chain [[34,36],32,40]: 9*aux(37)+0 1.81/1.86 with precondition: [G=3,B>=A+1,A>=C+1] 1.81/1.86 1.81/1.86 * Chain [[34,36],30,[31],40]: 10*aux(50)+0 1.81/1.86 with precondition: [G=3,B>=A+1,A>=C+1] 1.81/1.86 1.81/1.86 * Chain [[34,36],30,[31],37]: 10*aux(50)+0 1.81/1.86 with precondition: [G=5,H=J,B>=A+1,A>=C+1,H>=I] 1.81/1.86 1.81/1.86 * Chain [[34,36],30,40]: 9*aux(50)+0 1.81/1.86 with precondition: [G=3,B>=A+1,A>=C+1] 1.81/1.86 1.81/1.86 * Chain [[34,36],30,37]: 9*aux(50)+0 1.81/1.86 with precondition: [G=5,B>=A+1,A>=C+1,J>=H,H>=I] 1.81/1.86 1.81/1.86 * Chain [[31],40]: 1*it(31)+0 1.81/1.86 Such that:it(31) =< A-C 1.81/1.86 1.81/1.86 with precondition: [G=3,A>=B,A>=C+1] 1.81/1.86 1.81/1.86 * Chain [[31],37]: 1*it(31)+0 1.81/1.86 Such that:it(31) =< A-C 1.81/1.86 1.81/1.86 with precondition: [G=5,A=H,B=I,A=J,D=K,A>=B,A>=C+1] 1.81/1.86 1.81/1.86 * Chain [42]...: 1*aux(19)+0 1.81/1.86 with precondition: [G=3,B>=A+1,A>=C+1] 1.81/1.86 1.81/1.86 * Chain [41]...: 1*aux(20)+0 1.81/1.86 with precondition: [G=3,B>=A+2,A>=C+1] 1.81/1.86 1.81/1.86 * Chain [40]: 0 1.81/1.86 with precondition: [G=3] 1.81/1.86 1.81/1.86 * Chain [39]: 1*aux(21)+0 1.81/1.86 with precondition: [G=3,B>=A+1,A>=C+1] 1.81/1.86 1.81/1.86 * Chain [38]: 1*aux(22)+0 1.81/1.86 with precondition: [G=3,B>=A+2,A>=C+1] 1.81/1.86 1.81/1.86 * Chain [37]: 0 1.81/1.86 with precondition: [G=5,I=B,K=D,A=H,C=J,C>=A] 1.81/1.86 1.81/1.86 * Chain [35,[31],40]: 2*aux(23)+0 1.81/1.86 with precondition: [G=3,B>=A+1,A>=C+1] 1.81/1.86 1.81/1.86 * Chain [35,[31],37]: 2*aux(23)+0 1.81/1.86 with precondition: [G=5,H=J,B>=A+1,A>=C+1,H>=I] 1.81/1.86 1.81/1.86 * Chain [35,40]: 1*aux(23)+0 1.81/1.86 with precondition: [G=3,B>=A+1,A>=C+1] 1.81/1.86 1.81/1.86 * Chain [35,37]: 1*aux(23)+0 1.81/1.86 with precondition: [G=5,B>=A+1,A>=C+1,J>=H,H>=I] 1.81/1.86 1.81/1.86 * Chain [33,[31],40]: 1*aux(24)+1*it(31)+0 1.81/1.86 Such that:it(31) =< A-C 1.81/1.86 1.81/1.86 with precondition: [G=3,A+1=B,A>=C+1] 1.81/1.86 1.81/1.86 * Chain [33,[31],37]: 1*aux(24)+1*it(31)+0 1.81/1.86 Such that:it(31) =< A-C 1.81/1.86 1.81/1.86 with precondition: [G=5,B=A+1,B=H,B=I,B=J,0>=K+1,B>=C+2] 1.81/1.86 1.81/1.86 * Chain [33,40]: 1*aux(24)+0 1.81/1.86 with precondition: [G=3,A+1=B,A>=C+1] 1.81/1.86 1.81/1.86 * Chain [32,[31],40]: 1*aux(37)+1*it(31)+0 1.81/1.86 Such that:it(31) =< A-C 1.81/1.86 1.81/1.86 with precondition: [G=3,A+1=B,A>=C+1] 1.81/1.86 1.81/1.86 * Chain [32,[31],37]: 1*aux(37)+1*it(31)+0 1.81/1.86 Such that:it(31) =< A-C 1.81/1.86 1.81/1.86 with precondition: [G=5,B=A+1,B=H,B=I,B=J,K>=1,B>=C+2] 1.81/1.86 1.81/1.86 * Chain [32,40]: 1*aux(37)+0 1.81/1.86 with precondition: [G=3,A+1=B,A>=C+1] 1.81/1.86 1.81/1.86 * Chain [30,[31],40]: 2*aux(50)+0 1.81/1.86 with precondition: [G=3,B>=A+2,A>=C+1] 1.81/1.86 1.81/1.86 * Chain [30,[31],37]: 2*aux(50)+0 1.81/1.86 with precondition: [G=5,H=J,B>=A+2,A>=C+1,H>=I] 1.81/1.86 1.81/1.86 * Chain [30,40]: 1*aux(50)+0 1.81/1.86 with precondition: [G=3,B>=A+2,A>=C+1] 1.81/1.86 1.81/1.86 * Chain [30,37]: 1*aux(50)+0 1.81/1.86 with precondition: [G=5,B>=A+2,A>=C+1,J>=H,H>=I] 1.81/1.86 1.81/1.86 1.81/1.86 #### Cost of chains of f300_loop_cont(A,B,C,D,E,F,G): 1.81/1.86 * Chain [44]: 0 1.81/1.86 with precondition: [A=3] 1.81/1.86 1.81/1.86 * Chain [43]: 0 1.81/1.86 with precondition: [A=5] 1.81/1.86 1.81/1.86 1.81/1.86 #### Cost of chains of f5(A,B,C,D,E,G): 1.81/1.86 * Chain [52]: 0 1.81/1.86 with precondition: [] 1.81/1.86 1.81/1.86 * Chain [51]: 4*s(129)+6*s(130)+0 1.81/1.86 Such that:aux(57) =< A-C 1.81/1.86 s(129) =< aux(57) 1.81/1.86 1.81/1.86 with precondition: [A+1=B,A>=C+1] 1.81/1.86 1.81/1.86 * Chain [50]: 1*aux(58)+0 1.81/1.86 with precondition: [B>=A+1,A>=C+1] 1.81/1.86 1.81/1.86 * Chain [49]: 1*aux(59)+0 1.81/1.86 with precondition: [B>=A+2,A>=C+1] 1.81/1.86 1.81/1.86 * Chain [48]: 0 1.81/1.86 with precondition: [C>=A] 1.81/1.86 1.81/1.86 * Chain [47]: 2*s(146)+0 1.81/1.86 Such that:aux(60) =< A-C 1.81/1.86 s(146) =< aux(60) 1.81/1.86 1.81/1.86 with precondition: [A>=B,A>=C+1] 1.81/1.86 1.81/1.86 * Chain [46]...: 1*aux(61)+0 1.81/1.86 with precondition: [B>=A+1,A>=C+1] 1.81/1.86 1.81/1.86 * Chain [45]...: 1*s(151)+0 1.81/1.86 with precondition: [B>=A+2,A>=C+1] 1.81/1.86 1.81/1.86 1.81/1.86 Closed-form bounds of f5(A,B,C,D,E,G): 1.81/1.86 ------------------------------------- 1.81/1.86 * Chain [52] with precondition: [] 1.81/1.86 - Upper bound: 0 1.81/1.86 - Complexity: constant 1.81/1.86 * Chain [51] with precondition: [A+1=B,A>=C+1] 1.81/1.86 - Upper bound: inf 1.81/1.86 - Complexity: infinity 1.81/1.86 * Chain [50] with precondition: [B>=A+1,A>=C+1] 1.81/1.86 - Upper bound: inf 1.81/1.86 - Complexity: infinity 1.81/1.86 * Chain [49] with precondition: [B>=A+2,A>=C+1] 1.81/1.86 - Upper bound: inf 1.81/1.86 - Complexity: infinity 1.81/1.86 * Chain [48] with precondition: [C>=A] 1.81/1.86 - Upper bound: 0 1.81/1.86 - Complexity: constant 1.81/1.86 * Chain [47] with precondition: [A>=B,A>=C+1] 1.81/1.86 - Upper bound: 2*A-2*C 1.81/1.86 - Complexity: n 1.81/1.86 * Chain [46]... with precondition: [B>=A+1,A>=C+1] 1.81/1.86 - Upper bound: inf 1.81/1.86 - Complexity: infinity 1.81/1.86 * Chain [45]... with precondition: [B>=A+2,A>=C+1] 1.81/1.86 - Upper bound: inf 1.81/1.86 - Complexity: infinity 1.81/1.86 1.81/1.86 ### Maximum cost of f5(A,B,C,D,E,G): inf 1.81/1.86 Asymptotic class: infinity 1.81/1.86 * Total analysis performed in 1696 ms. 1.81/1.86 1.86/1.96 EOF