23.99/7.66 YES 23.99/7.67 proof of /export/starexec/sandbox/benchmark/theBenchmark.c 23.99/7.67 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 23.99/7.67 23.99/7.67 23.99/7.67 Termination of the given C Problem could be proven: 23.99/7.67 23.99/7.67 (0) C Problem 23.99/7.67 (1) CToLLVMProof [EQUIVALENT, 170 ms] 23.99/7.67 (2) LLVM problem 23.99/7.67 (3) LLVMToTerminationGraphProof [EQUIVALENT, 2575 ms] 23.99/7.67 (4) LLVM Symbolic Execution Graph 23.99/7.67 (5) SymbolicExecutionGraphToSCCProof [SOUND, 2 ms] 23.99/7.67 (6) AND 23.99/7.67 (7) LLVM Symbolic Execution SCC 23.99/7.67 (8) SCC2IRS [SOUND, 55 ms] 23.99/7.67 (9) IntTRS 23.99/7.67 (10) IRS2T2 [EQUIVALENT, 0 ms] 23.99/7.67 (11) T2IntSys 23.99/7.67 (12) T2 [EQUIVALENT, 1156 ms] 23.99/7.67 (13) YES 23.99/7.67 (14) LLVM Symbolic Execution SCC 23.99/7.67 (15) SCC2IRS [SOUND, 59 ms] 23.99/7.67 (16) IntTRS 23.99/7.67 (17) IRS2T2 [EQUIVALENT, 0 ms] 23.99/7.67 (18) T2IntSys 23.99/7.67 (19) T2 [EQUIVALENT, 1202 ms] 23.99/7.67 (20) YES 23.99/7.67 (21) LLVM Symbolic Execution SCC 23.99/7.67 (22) SCC2IRS [SOUND, 76 ms] 23.99/7.67 (23) IntTRS 23.99/7.67 (24) IRS2T2 [EQUIVALENT, 0 ms] 23.99/7.67 (25) T2IntSys 23.99/7.67 (26) T2 [EQUIVALENT, 1233 ms] 23.99/7.67 (27) YES 23.99/7.67 23.99/7.67 23.99/7.67 ---------------------------------------- 23.99/7.67 23.99/7.67 (0) 23.99/7.67 Obligation: 23.99/7.67 c file /export/starexec/sandbox/benchmark/theBenchmark.c 23.99/7.67 ---------------------------------------- 23.99/7.67 23.99/7.67 (1) CToLLVMProof (EQUIVALENT) 23.99/7.67 Compiled c-file /export/starexec/sandbox/benchmark/theBenchmark.c to LLVM. 23.99/7.67 ---------------------------------------- 23.99/7.67 23.99/7.67 (2) 23.99/7.67 Obligation: 23.99/7.67 LLVM Problem 23.99/7.67 23.99/7.67 Aliases: 23.99/7.67 23.99/7.67 Data layout: 23.99/7.67 23.99/7.67 "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64-S128" 23.99/7.67 23.99/7.67 Machine: 23.99/7.67 23.99/7.67 "x86_64-pc-linux-gnu" 23.99/7.67 23.99/7.67 Type definitions: 23.99/7.67 23.99/7.67 Global variables: 23.99/7.67 23.99/7.67 Function declarations and definitions: 23.99/7.67 23.99/7.67 *BasicFunctionTypename: "__VERIFIER_nondet_int" returnParam: i32 parameters: () variableLength: false visibilityType: DEFAULT callingConvention: ccc 23.99/7.67 *BasicFunctionTypename: "test_fun" linkageType: EXTERNALLY_VISIBLE returnParam: i32 parameters: (x i32, y i32) variableLength: false visibilityType: DEFAULT callingConvention: ccc 23.99/7.67 0: 23.99/7.67 %1 = alloca i32, align 4 23.99/7.67 %2 = alloca i32, align 4 23.99/7.67 %c = alloca i32, align 4 23.99/7.67 store %x, %1 23.99/7.67 store %y, %2 23.99/7.67 store 0, %c 23.99/7.67 br %3 23.99/7.67 3: 23.99/7.67 %4 = load %1 23.99/7.67 %5 = icmp sgt %4 0 23.99/7.67 br %5, %9, %6 23.99/7.67 6: 23.99/7.67 %7 = load %2 23.99/7.67 %8 = icmp sgt %7 0 23.99/7.67 br %9 23.99/7.67 9: 23.99/7.67 %10 = phi [1, %3], [%8, %6] 23.99/7.67 br %10, %11, %28 23.99/7.67 11: 23.99/7.67 %12 = load %1 23.99/7.67 %13 = icmp sgt %12 0 23.99/7.67 br %13, %14, %17 23.99/7.67 14: 23.99/7.67 %15 = load %1 23.99/7.67 %16 = sub %15 1 23.99/7.67 store %16, %1 23.99/7.67 br %25 23.99/7.67 17: 23.99/7.67 %18 = load %2 23.99/7.67 %19 = icmp sgt %18 0 23.99/7.67 br %19, %20, %23 23.99/7.67 20: 23.99/7.67 %21 = load %2 23.99/7.67 %22 = sub %21 1 23.99/7.67 store %22, %2 23.99/7.67 br %24 23.99/7.67 23: 23.99/7.67 br %24 23.99/7.67 24: 23.99/7.67 br %25 23.99/7.67 25: 23.99/7.67 %26 = load %c 23.99/7.67 %27 = add %26 1 23.99/7.67 store %27, %c 23.99/7.67 br %3 23.99/7.67 28: 23.99/7.67 %29 = load %c 23.99/7.67 ret %29 23.99/7.67 23.99/7.67 *BasicFunctionTypename: "main" linkageType: EXTERNALLY_VISIBLE returnParam: i32 parameters: () variableLength: false visibilityType: DEFAULT callingConvention: ccc 23.99/7.67 0: 23.99/7.67 %1 = alloca i32, align 4 23.99/7.67 store 0, %1 23.99/7.67 %2 = call i32 @__VERIFIER_nondet_int() 23.99/7.67 %3 = call i32 @__VERIFIER_nondet_int() 23.99/7.67 %4 = call i32 @test_fun(i32 %2, i32 %3) 23.99/7.67 ret %4 23.99/7.67 23.99/7.67 23.99/7.67 Analyze Termination of all function calls matching the pattern: 23.99/7.67 main() 23.99/7.67 ---------------------------------------- 23.99/7.67 23.99/7.67 (3) LLVMToTerminationGraphProof (EQUIVALENT) 23.99/7.67 Constructed symbolic execution graph for LLVM program and proved memory safety. 23.99/7.67 ---------------------------------------- 23.99/7.67 23.99/7.67 (4) 23.99/7.67 Obligation: 23.99/7.67 SE Graph 23.99/7.67 ---------------------------------------- 23.99/7.67 23.99/7.67 (5) SymbolicExecutionGraphToSCCProof (SOUND) 23.99/7.67 Splitted symbolic execution graph to 3 SCCs. 23.99/7.67 ---------------------------------------- 23.99/7.67 23.99/7.67 (6) 23.99/7.67 Complex Obligation (AND) 23.99/7.67 23.99/7.67 ---------------------------------------- 23.99/7.67 23.99/7.67 (7) 23.99/7.67 Obligation: 23.99/7.67 SCC 23.99/7.67 ---------------------------------------- 23.99/7.67 23.99/7.67 (8) SCC2IRS (SOUND) 23.99/7.67 Transformed LLVM symbolic execution graph SCC into a rewrite problem. Log: 23.99/7.67 Generated rules. Obtained 24 rulesP rules: 23.99/7.67 f_654(v908, v909, v910, v911, v912, 0, 1, v915, v916, v917, v918, v919, v920, v921, v922, v923, 3, 4) -> f_656(v908, v909, v910, v911, v912, 0, 1, v916, v917, v918, v919, v920, v921, v922, v923, 3, 4) :|: 0 = 0 23.99/7.67 f_656(v908, v909, v910, v911, v912, 0, 1, v916, v917, v918, v919, v920, v921, v922, v923, 3, 4) -> f_657(v908, v909, v910, v911, v912, 0, 1, v916, v953, v917, v918, v919, v920, v921, v922, v923, 3, 4, 2) :|: v953 = 1 + v916 && 2 <= v953 23.99/7.67 f_657(v908, v909, v910, v911, v912, 0, 1, v916, v953, v917, v918, v919, v920, v921, v922, v923, 3, 4, 2) -> f_658(v908, v909, v910, v911, v912, 0, 1, v916, v953, v917, v918, v919, v920, v921, v922, v923, 3, 4, 2) :|: TRUE 23.99/7.67 f_658(v908, v909, v910, v911, v912, 0, 1, v916, v953, v917, v918, v919, v920, v921, v922, v923, 3, 4, 2) -> f_659(v908, v909, v910, v911, v912, 0, 1, v916, v953, v917, v918, v919, v920, v921, v922, v923, 3, 4, 2) :|: TRUE 23.99/7.67 f_659(v908, v909, v910, v911, v912, 0, 1, v916, v953, v917, v918, v919, v920, v921, v922, v923, 3, 4, 2) -> f_660(v908, v909, v910, v911, v912, 0, 1, v916, v953, v917, v918, v919, v920, v921, v922, v923, 3, 4, 2) :|: 0 = 0 23.99/7.67 f_660(v908, v909, v910, v911, v912, 0, 1, v916, v953, v917, v918, v919, v920, v921, v922, v923, 3, 4, 2) -> f_661(v908, v909, v910, v911, v912, 0, 1, v916, v953, v917, v918, v919, v920, v921, v922, v923, 3, 4, 2) :|: 0 = 0 23.99/7.67 f_661(v908, v909, v910, v911, v912, 0, 1, v916, v953, v917, v918, v919, v920, v921, v922, v923, 3, 4, 2) -> f_662(v908, v909, v910, v911, v912, 0, 1, v916, v953, v917, v918, v919, v920, v921, v922, v923, 3, 4, 2) :|: TRUE 23.99/7.67 f_662(v908, v909, v910, v911, v912, 0, 1, v916, v953, v917, v918, v919, v920, v921, v922, v923, 3, 4, 2) -> f_663(v908, v909, v910, v911, v912, 0, 1, v916, v953, v918, v917, v919, v920, v921, v922, v923, 3, 4, 2) :|: 0 = 0 23.99/7.67 f_663(v908, v909, v910, v911, v912, 0, 1, v916, v953, v918, v917, v919, v920, v921, v922, v923, 3, 4, 2) -> f_664(v908, v909, v910, v911, v912, 0, 1, v916, v953, v918, v917, v919, v920, v921, v922, v923, 3, 2, 4) :|: 0 < v918 && 2 <= v917 && 2 <= v909 23.99/7.67 f_664(v908, v909, v910, v911, v912, 0, 1, v916, v953, v918, v917, v919, v920, v921, v922, v923, 3, 2, 4) -> f_666(v908, v909, v910, v911, v912, 0, 1, v916, v953, v918, v917, v919, v920, v921, v922, v923, 3, 2, 4) :|: 0 = 0 23.99/7.67 f_666(v908, v909, v910, v911, v912, 0, 1, v916, v953, v918, v917, v919, v920, v921, v922, v923, 3, 2, 4) -> f_668(v908, v909, v910, v911, v912, 0, 1, v916, v953, v918, v917, v919, v920, v921, v922, v923, 3, 2, 4) :|: 0 = 0 23.99/7.67 f_668(v908, v909, v910, v911, v912, 0, 1, v916, v953, v918, v917, v919, v920, v921, v922, v923, 3, 2, 4) -> f_670(v908, v909, v910, v911, v912, 0, 1, v916, v953, v918, v917, v919, v920, v921, v922, v923, 3, 2, 4) :|: TRUE 23.99/7.67 f_670(v908, v909, v910, v911, v912, 0, 1, v916, v953, v918, v917, v919, v920, v921, v922, v923, 3, 2, 4) -> f_672(v908, v909, v910, v911, v912, 0, 1, v916, v953, v918, v917, v919, v920, v921, v922, v923, 3, 2, 4) :|: 0 = 0 23.99/7.67 f_672(v908, v909, v910, v911, v912, 0, 1, v916, v953, v918, v917, v919, v920, v921, v922, v923, 3, 2, 4) -> f_674(v908, v909, v910, v911, v912, 0, 1, v916, v953, v918, v917, v919, v920, v921, v922, v923, 3, 2, 4) :|: 0 = 0 23.99/7.67 f_674(v908, v909, v910, v911, v912, 0, 1, v916, v953, v918, v917, v919, v920, v921, v922, v923, 3, 2, 4) -> f_676(v908, v909, v910, v911, v912, 0, 1, v916, v953, v918, v917, v919, v920, v921, v922, v923, 3, 2, 4) :|: TRUE 23.99/7.67 f_676(v908, v909, v910, v911, v912, 0, 1, v916, v953, v918, v917, v919, v920, v921, v922, v923, 3, 2, 4) -> f_677(v908, v909, v910, v911, v912, 0, 1, v916, v953, v918, v917, v919, v920, v921, v922, v923, 3, 2, 4) :|: 0 = 0 23.99/7.67 f_677(v908, v909, v910, v911, v912, 0, 1, v916, v953, v918, v917, v919, v920, v921, v922, v923, 3, 2, 4) -> f_678(v908, v909, v910, v911, v912, 0, 1, v916, v953, v918, v917, v919, v920, v921, v922, v923, 3, 2, 4) :|: 0 = 0 23.99/7.67 f_678(v908, v909, v910, v911, v912, 0, 1, v916, v953, v918, v917, v919, v920, v921, v922, v923, 3, 2, 4) -> f_679(v908, v909, v910, v911, v912, 0, 1, v916, v953, v918, v917, v919, v920, v921, v922, v923, 3, 2, 4) :|: TRUE 23.99/7.67 f_679(v908, v909, v910, v911, v912, 0, 1, v916, v953, v918, v917, v919, v920, v921, v922, v923, 3, 2, 4) -> f_680(v908, v909, v910, v911, v912, 0, 1, v916, v953, v918, v919, v920, v921, v922, v923, 3, 2, 4) :|: 0 = 0 23.99/7.67 f_680(v908, v909, v910, v911, v912, 0, 1, v916, v953, v918, v919, v920, v921, v922, v923, 3, 2, 4) -> f_681(v908, v909, v910, v911, v912, 0, 1, v916, v953, v918, v1011, v919, v920, v921, v922, v923, 3, 2, 4) :|: 1 + v1011 = v918 && 0 <= v1011 23.99/7.67 f_681(v908, v909, v910, v911, v912, 0, 1, v916, v953, v918, v1011, v919, v920, v921, v922, v923, 3, 2, 4) -> f_682(v908, v909, v910, v911, v912, 0, 1, v916, v953, v918, v1011, v919, v920, v921, v922, v923, 3, 2, 4) :|: TRUE 23.99/7.67 f_682(v908, v909, v910, v911, v912, 0, 1, v916, v953, v918, v1011, v919, v920, v921, v922, v923, 3, 2, 4) -> f_683(v908, v909, v910, v911, v912, 0, 1, v916, v953, v918, v1011, v919, v920, v921, v922, v923, 3, 2, 4) :|: TRUE 23.99/7.67 f_683(v908, v909, v910, v911, v912, 0, 1, v916, v953, v918, v1011, v919, v920, v921, v922, v923, 3, 2, 4) -> f_652(v908, v909, v910, v911, v912, 0, 1, v916, v953, v918, v1011, v919, v920, v921, v922, v923, 3, 4) :|: TRUE 23.99/7.67 f_652(v908, v909, v910, v911, v912, 0, 1, v915, v916, v917, v918, v919, v920, v921, v922, v923, 3, 4) -> f_654(v908, v909, v910, v911, v912, 0, 1, v915, v916, v917, v918, v919, v920, v921, v922, v923, 3, 4) :|: TRUE 23.99/7.67 Combined rules. Obtained 1 rulesP rules: 23.99/7.67 f_654(v908:0, v909:0, v910:0, v911:0, v912:0, 0, 1, v915:0, v916:0, v917:0, 1 + v1011:0, v919:0, v920:0, v921:0, v922:0, v923:0, 3, 4) -> f_654(v908:0, v909:0, v910:0, v911:0, v912:0, 0, 1, v916:0, 1 + v916:0, 1 + v1011:0, v1011:0, v919:0, v920:0, v921:0, v922:0, v923:0, 3, 4) :|: v916:0 > 0 && v917:0 > 1 && v1011:0 > -1 && v909:0 > 1 23.99/7.67 Filtered unneeded arguments: 23.99/7.67 f_654(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18) -> f_654(x2, x9, x10, x11) 23.99/7.67 Removed division, modulo operations, cleaned up constraints. Obtained 1 rules.P rules: 23.99/7.67 f_654(v909:0, v916:0, v917:0, sum~cons_1~v1011:0) -> f_654(v909:0, 1 + v916:0, 1 + v1011:0, v1011:0) :|: v917:0 > 1 && v916:0 > 0 && v909:0 > 1 && v1011:0 > -1 && sum~cons_1~v1011:0 = 1 + v1011:0 23.99/7.67 23.99/7.67 ---------------------------------------- 23.99/7.67 23.99/7.67 (9) 23.99/7.67 Obligation: 23.99/7.67 Rules: 23.99/7.67 f_654(v909:0, v916:0, v917:0, sum~cons_1~v1011:0) -> f_654(v909:0, 1 + v916:0, 1 + v1011:0, v1011:0) :|: v917:0 > 1 && v916:0 > 0 && v909:0 > 1 && v1011:0 > -1 && sum~cons_1~v1011:0 = 1 + v1011:0 23.99/7.67 23.99/7.67 ---------------------------------------- 23.99/7.67 23.99/7.67 (10) IRS2T2 (EQUIVALENT) 23.99/7.67 Transformed input IRS into an integer transition system.Used the following mapping from defined symbols to location IDs: 23.99/7.67 23.99/7.67 (f_654_4,1) 23.99/7.67 23.99/7.67 ---------------------------------------- 23.99/7.67 23.99/7.67 (11) 23.99/7.67 Obligation: 23.99/7.67 START: 0; 23.99/7.67 23.99/7.67 FROM: 0; 23.99/7.67 TO: 1; 23.99/7.67 23.99/7.67 FROM: 1; 23.99/7.67 oldX0 := x0; 23.99/7.67 oldX1 := x1; 23.99/7.67 oldX2 := x2; 23.99/7.67 oldX3 := x3; 23.99/7.67 oldX4 := oldX3 - 1; 23.99/7.67 assume(oldX2 > 1 && oldX1 > 0 && oldX0 > 1 && oldX4 > -1 && oldX3 = 1 + oldX4); 23.99/7.67 x0 := oldX0; 23.99/7.67 x1 := 1 + oldX1; 23.99/7.67 x2 := 1 + oldX4; 23.99/7.67 x3 := oldX3 - 1; 23.99/7.67 TO: 1; 23.99/7.67 23.99/7.67 23.99/7.67 ---------------------------------------- 23.99/7.67 23.99/7.67 (12) T2 (EQUIVALENT) 23.99/7.67 Initially, performed program simplifications using lexicographic rank functions: 23.99/7.67 * Removed transitions 1, 3, 4 using the following rank functions: 23.99/7.67 - Rank function 1: 23.99/7.67 RF for loc. 5: 1+2*x3 23.99/7.67 RF for loc. 6: 2*x3 23.99/7.67 Bound for (chained) transitions 3: 2 23.99/7.67 Bound for (chained) transitions 4: 2 23.99/7.67 - Rank function 2: 23.99/7.67 RF for loc. 5: 0 23.99/7.67 RF for loc. 6: -1 23.99/7.67 Bound for (chained) transitions 1: 0 23.99/7.67 23.99/7.67 ---------------------------------------- 23.99/7.67 23.99/7.67 (13) 23.99/7.67 YES 23.99/7.67 23.99/7.67 ---------------------------------------- 23.99/7.67 23.99/7.67 (14) 23.99/7.67 Obligation: 23.99/7.67 SCC 23.99/7.67 ---------------------------------------- 23.99/7.67 23.99/7.67 (15) SCC2IRS (SOUND) 23.99/7.67 Transformed LLVM symbolic execution graph SCC into a rewrite problem. Log: 23.99/7.67 Generated rules. Obtained 24 rulesP rules: 23.99/7.67 f_598(v799, v800, v801, v802, v803, 0, v805, 1, v807, v808, v809, v810, v811, v812, v813, v814, 3, 4) -> f_600(v799, v800, v801, v802, v803, 0, v805, 1, v807, v808, v809, v810, v811, v812, v813, v814, 3, 4) :|: 0 = 0 23.99/7.67 f_600(v799, v800, v801, v802, v803, 0, v805, 1, v807, v808, v809, v810, v811, v812, v813, v814, 3, 4) -> f_602(v799, v800, v801, v802, v803, 0, v805, 1, v807, v808, v809, v810, v811, v812, v813, v814, 3, 4) :|: TRUE 23.99/7.67 f_602(v799, v800, v801, v802, v803, 0, v805, 1, v807, v808, v809, v810, v811, v812, v813, v814, 3, 4) -> f_604(v799, v800, v801, v802, v803, 0, v807, 1, v805, v808, v809, v810, v811, v812, v813, v814, 3, 4) :|: 0 = 0 23.99/7.67 f_604(v799, v800, v801, v802, v803, 0, v807, 1, v805, v808, v809, v810, v811, v812, v813, v814, 3, 4) -> f_606(v799, v800, v801, v802, v803, 0, v807, 1, v805, v808, v809, v810, v811, v812, v813, v814, 3, 2, 4) :|: 0 < v807 && 2 <= v805 && 2 <= v800 23.99/7.67 f_606(v799, v800, v801, v802, v803, 0, v807, 1, v805, v808, v809, v810, v811, v812, v813, v814, 3, 2, 4) -> f_609(v799, v800, v801, v802, v803, 0, v807, 1, v805, v808, v809, v810, v811, v812, v813, v814, 3, 2, 4) :|: 0 = 0 23.99/7.67 f_609(v799, v800, v801, v802, v803, 0, v807, 1, v805, v808, v809, v810, v811, v812, v813, v814, 3, 2, 4) -> f_612(v799, v800, v801, v802, v803, 0, v807, 1, v805, v808, v809, v810, v811, v812, v813, v814, 3, 2, 4) :|: 0 = 0 23.99/7.67 f_612(v799, v800, v801, v802, v803, 0, v807, 1, v805, v808, v809, v810, v811, v812, v813, v814, 3, 2, 4) -> f_615(v799, v800, v801, v802, v803, 0, v807, 1, v805, v808, v809, v810, v811, v812, v813, v814, 3, 2, 4) :|: TRUE 23.99/7.67 f_615(v799, v800, v801, v802, v803, 0, v807, 1, v805, v808, v809, v810, v811, v812, v813, v814, 3, 2, 4) -> f_619(v799, v800, v801, v802, v803, 0, v807, 1, v805, v808, v809, v810, v811, v812, v813, v814, 3, 2, 4) :|: 0 = 0 23.99/7.67 f_619(v799, v800, v801, v802, v803, 0, v807, 1, v805, v808, v809, v810, v811, v812, v813, v814, 3, 2, 4) -> f_623(v799, v800, v801, v802, v803, 0, v807, 1, v805, v808, v809, v810, v811, v812, v813, v814, 3, 2, 4) :|: 0 = 0 23.99/7.67 f_623(v799, v800, v801, v802, v803, 0, v807, 1, v805, v808, v809, v810, v811, v812, v813, v814, 3, 2, 4) -> f_627(v799, v800, v801, v802, v803, 0, v807, 1, v805, v808, v809, v810, v811, v812, v813, v814, 3, 2, 4) :|: TRUE 23.99/7.67 f_627(v799, v800, v801, v802, v803, 0, v807, 1, v805, v808, v809, v810, v811, v812, v813, v814, 3, 2, 4) -> f_630(v799, v800, v801, v802, v803, 0, v807, 1, v805, v808, v809, v810, v811, v812, v813, v814, 3, 2, 4) :|: 0 = 0 23.99/7.67 f_630(v799, v800, v801, v802, v803, 0, v807, 1, v805, v808, v809, v810, v811, v812, v813, v814, 3, 2, 4) -> f_633(v799, v800, v801, v802, v803, 0, v807, 1, v805, v808, v809, v810, v811, v812, v813, v814, 3, 2, 4) :|: 0 = 0 23.99/7.67 f_633(v799, v800, v801, v802, v803, 0, v807, 1, v805, v808, v809, v810, v811, v812, v813, v814, 3, 2, 4) -> f_636(v799, v800, v801, v802, v803, 0, v807, 1, v805, v808, v809, v810, v811, v812, v813, v814, 3, 2, 4) :|: TRUE 23.99/7.67 f_636(v799, v800, v801, v802, v803, 0, v807, 1, v805, v808, v809, v810, v811, v812, v813, v814, 3, 2, 4) -> f_638(v799, v800, v801, v802, v803, 0, v807, 1, v808, v809, v810, v811, v812, v813, v814, 3, 2, 4) :|: 0 = 0 23.99/7.67 f_638(v799, v800, v801, v802, v803, 0, v807, 1, v808, v809, v810, v811, v812, v813, v814, 3, 2, 4) -> f_640(v799, v800, v801, v802, v803, 0, v807, 1, v886, v808, v809, v810, v811, v812, v813, v814, 3, 2, 4) :|: 1 + v886 = v807 && 0 <= v886 23.99/7.67 f_640(v799, v800, v801, v802, v803, 0, v807, 1, v886, v808, v809, v810, v811, v812, v813, v814, 3, 2, 4) -> f_642(v799, v800, v801, v802, v803, 0, v807, 1, v886, v808, v809, v810, v811, v812, v813, v814, 3, 2, 4) :|: TRUE 23.99/7.67 f_642(v799, v800, v801, v802, v803, 0, v807, 1, v886, v808, v809, v810, v811, v812, v813, v814, 3, 2, 4) -> f_644(v799, v800, v801, v802, v803, 0, v807, 1, v886, v808, v809, v810, v811, v812, v813, v814, 3, 2, 4) :|: TRUE 23.99/7.67 f_644(v799, v800, v801, v802, v803, 0, v807, 1, v886, v808, v809, v810, v811, v812, v813, v814, 3, 2, 4) -> f_646(v799, v800, v801, v802, v803, 0, v807, 1, v886, v808, v809, v810, v811, v812, v813, v814, 3, 2, 4) :|: TRUE 23.99/7.67 f_646(v799, v800, v801, v802, v803, 0, v807, 1, v886, v808, v809, v810, v811, v812, v813, v814, 3, 2, 4) -> f_648(v799, v800, v801, v802, v803, 0, v807, 1, v886, v809, v810, v811, v812, v813, v814, 3, 2, 4) :|: 0 = 0 23.99/7.67 f_648(v799, v800, v801, v802, v803, 0, v807, 1, v886, v809, v810, v811, v812, v813, v814, 3, 2, 4) -> f_650(v799, v800, v801, v802, v803, 0, v807, 1, v886, v809, v907, v810, v811, v812, v813, v814, 3, 2, 4) :|: v907 = 1 + v809 && 2 <= v907 23.99/7.67 f_650(v799, v800, v801, v802, v803, 0, v807, 1, v886, v809, v907, v810, v811, v812, v813, v814, 3, 2, 4) -> f_653(v799, v800, v801, v802, v803, 0, v807, 1, v886, v809, v907, v810, v811, v812, v813, v814, 3, 2, 4) :|: TRUE 23.99/7.67 f_653(v799, v800, v801, v802, v803, 0, v807, 1, v886, v809, v907, v810, v811, v812, v813, v814, 3, 2, 4) -> f_655(v799, v800, v801, v802, v803, 0, v807, 1, v886, v809, v907, v810, v811, v812, v813, v814, 3, 2, 4) :|: TRUE 23.99/7.67 f_655(v799, v800, v801, v802, v803, 0, v807, 1, v886, v809, v907, v810, v811, v812, v813, v814, 3, 2, 4) -> f_596(v799, v800, v801, v802, v803, 0, v807, 1, v886, v809, v907, v810, v811, v812, v813, v814, 3, 4) :|: TRUE 23.99/7.67 f_596(v799, v800, v801, v802, v803, 0, v805, 1, v807, v808, v809, v810, v811, v812, v813, v814, 3, 4) -> f_598(v799, v800, v801, v802, v803, 0, v805, 1, v807, v808, v809, v810, v811, v812, v813, v814, 3, 4) :|: 0 = 0 23.99/7.67 Combined rules. Obtained 1 rulesP rules: 23.99/7.67 f_598(v799:0, v800:0, v801:0, v802:0, v803:0, 0, v805:0, 1, 1 + v886:0, v808:0, v809:0, v810:0, v811:0, v812:0, v813:0, v814:0, 3, 4) -> f_598(v799:0, v800:0, v801:0, v802:0, v803:0, 0, 1 + v886:0, 1, v886:0, v809:0, 1 + v809:0, v810:0, v811:0, v812:0, v813:0, v814:0, 3, 4) :|: v805:0 > 1 && v886:0 > -1 && v800:0 > 1 && v809:0 > 0 23.99/7.67 Filtered unneeded arguments: 23.99/7.67 f_598(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18) -> f_598(x2, x7, x9, x11) 23.99/7.67 Removed division, modulo operations, cleaned up constraints. Obtained 1 rules.P rules: 23.99/7.67 f_598(v800:0, v805:0, sum~cons_1~v886:0, v809:0) -> f_598(v800:0, 1 + v886:0, v886:0, 1 + v809:0) :|: v886:0 > -1 && v805:0 > 1 && v809:0 > 0 && v800:0 > 1 && sum~cons_1~v886:0 = 1 + v886:0 23.99/7.67 23.99/7.67 ---------------------------------------- 23.99/7.67 23.99/7.67 (16) 23.99/7.67 Obligation: 23.99/7.67 Rules: 23.99/7.67 f_598(v800:0, v805:0, sum~cons_1~v886:0, v809:0) -> f_598(v800:0, 1 + v886:0, v886:0, 1 + v809:0) :|: v886:0 > -1 && v805:0 > 1 && v809:0 > 0 && v800:0 > 1 && sum~cons_1~v886:0 = 1 + v886:0 23.99/7.67 23.99/7.67 ---------------------------------------- 23.99/7.67 23.99/7.67 (17) IRS2T2 (EQUIVALENT) 23.99/7.67 Transformed input IRS into an integer transition system.Used the following mapping from defined symbols to location IDs: 23.99/7.67 23.99/7.67 (f_598_4,1) 23.99/7.67 23.99/7.67 ---------------------------------------- 23.99/7.67 23.99/7.67 (18) 23.99/7.67 Obligation: 23.99/7.67 START: 0; 23.99/7.67 23.99/7.67 FROM: 0; 23.99/7.67 TO: 1; 23.99/7.67 23.99/7.67 FROM: 1; 23.99/7.67 oldX0 := x0; 23.99/7.67 oldX1 := x1; 23.99/7.67 oldX2 := x2; 23.99/7.67 oldX3 := x3; 23.99/7.67 oldX4 := oldX2 - 1; 23.99/7.67 assume(oldX4 > -1 && oldX1 > 1 && oldX3 > 0 && oldX0 > 1 && oldX2 = 1 + oldX4); 23.99/7.67 x0 := oldX0; 23.99/7.67 x1 := 1 + oldX4; 23.99/7.67 x2 := oldX2 - 1; 23.99/7.67 x3 := 1 + oldX3; 23.99/7.67 TO: 1; 23.99/7.67 23.99/7.67 23.99/7.67 ---------------------------------------- 23.99/7.67 23.99/7.67 (19) T2 (EQUIVALENT) 23.99/7.67 Initially, performed program simplifications using lexicographic rank functions: 23.99/7.67 * Removed transitions 1, 3, 4 using the following rank functions: 23.99/7.67 - Rank function 1: 23.99/7.67 RF for loc. 5: 1+2*x2 23.99/7.67 RF for loc. 6: 2*x2 23.99/7.67 Bound for (chained) transitions 3: 2 23.99/7.67 Bound for (chained) transitions 4: 2 23.99/7.67 - Rank function 2: 23.99/7.67 RF for loc. 5: 0 23.99/7.67 RF for loc. 6: -1 23.99/7.67 Bound for (chained) transitions 1: 0 23.99/7.67 23.99/7.67 ---------------------------------------- 23.99/7.67 23.99/7.67 (20) 23.99/7.67 YES 23.99/7.67 23.99/7.67 ---------------------------------------- 23.99/7.67 23.99/7.67 (21) 23.99/7.67 Obligation: 23.99/7.67 SCC 23.99/7.67 ---------------------------------------- 23.99/7.67 23.99/7.67 (22) SCC2IRS (SOUND) 23.99/7.67 Transformed LLVM symbolic execution graph SCC into a rewrite problem. Log: 23.99/7.67 Generated rules. Obtained 17 rulesP rules: 23.99/7.67 f_469(v359, v360, v361, v362, v363, v366, 1, v364, v367, v368, v369, v370, v371, v372, v373, 0, 3, 4) -> f_471(v359, v360, v361, v362, v363, v366, 1, v364, v367, v368, v369, v370, v371, v372, v373, 0, 3, 2, 4) :|: 0 < v366 && 2 <= v364 && 2 <= v359 23.99/7.67 f_471(v359, v360, v361, v362, v363, v366, 1, v364, v367, v368, v369, v370, v371, v372, v373, 0, 3, 2, 4) -> f_475(v359, v360, v361, v362, v363, v366, 1, v364, v367, v368, v369, v370, v371, v372, v373, 0, 3, 2, 4) :|: 0 = 0 23.99/7.67 f_475(v359, v360, v361, v362, v363, v366, 1, v364, v367, v368, v369, v370, v371, v372, v373, 0, 3, 2, 4) -> f_479(v359, v360, v361, v362, v363, v366, 1, v364, v367, v368, v369, v370, v371, v372, v373, 0, 3, 2, 4) :|: 0 = 0 23.99/7.67 f_479(v359, v360, v361, v362, v363, v366, 1, v364, v367, v368, v369, v370, v371, v372, v373, 0, 3, 2, 4) -> f_483(v359, v360, v361, v362, v363, v366, 1, v364, v367, v368, v369, v370, v371, v372, v373, 0, 3, 2, 4) :|: TRUE 23.99/7.67 f_483(v359, v360, v361, v362, v363, v366, 1, v364, v367, v368, v369, v370, v371, v372, v373, 0, 3, 2, 4) -> f_487(v359, v360, v361, v362, v363, v366, 1, v364, v367, v368, v369, v370, v371, v372, v373, 0, 3, 2, 4) :|: 0 = 0 23.99/7.67 f_487(v359, v360, v361, v362, v363, v366, 1, v364, v367, v368, v369, v370, v371, v372, v373, 0, 3, 2, 4) -> f_492(v359, v360, v361, v362, v363, v366, 1, v364, v367, v368, v369, v370, v371, v372, v373, 0, 3, 2, 4) :|: 0 = 0 23.99/7.67 f_492(v359, v360, v361, v362, v363, v366, 1, v364, v367, v368, v369, v370, v371, v372, v373, 0, 3, 2, 4) -> f_497(v359, v360, v361, v362, v363, v366, 1, v364, v367, v368, v369, v370, v371, v372, v373, 0, 3, 2, 4) :|: TRUE 23.99/7.67 f_497(v359, v360, v361, v362, v363, v366, 1, v364, v367, v368, v369, v370, v371, v372, v373, 0, 3, 2, 4) -> f_501(v359, v360, v361, v362, v363, v366, 1, v367, v368, v369, v370, v371, v372, v373, 0, 3, 2, 4) :|: 0 = 0 23.99/7.67 f_501(v359, v360, v361, v362, v363, v366, 1, v367, v368, v369, v370, v371, v372, v373, 0, 3, 2, 4) -> f_505(v359, v360, v361, v362, v363, v366, 1, v405, v367, v368, v369, v370, v371, v372, v373, 0, 3, 2, 4) :|: 1 + v405 = v366 && 0 <= v405 23.99/7.67 f_505(v359, v360, v361, v362, v363, v366, 1, v405, v367, v368, v369, v370, v371, v372, v373, 0, 3, 2, 4) -> f_509(v359, v360, v361, v362, v363, v366, 1, v405, v367, v368, v369, v370, v371, v372, v373, 0, 3, 2, 4) :|: TRUE 23.99/7.67 f_509(v359, v360, v361, v362, v363, v366, 1, v405, v367, v368, v369, v370, v371, v372, v373, 0, 3, 2, 4) -> f_513(v359, v360, v361, v362, v363, v366, 1, v405, v367, v368, v369, v370, v371, v372, v373, 0, 3, 2, 4) :|: TRUE 23.99/7.67 f_513(v359, v360, v361, v362, v363, v366, 1, v405, v367, v368, v369, v370, v371, v372, v373, 0, 3, 2, 4) -> f_516(v359, v360, v361, v362, v363, v366, 1, v405, v368, v369, v370, v371, v372, v373, 0, 3, 2, 4) :|: 0 = 0 23.99/7.67 f_516(v359, v360, v361, v362, v363, v366, 1, v405, v368, v369, v370, v371, v372, v373, 0, 3, 2, 4) -> f_519(v359, v360, v361, v362, v363, v366, 1, v405, v368, v408, v369, v370, v371, v372, v373, 0, 3, 2, 4) :|: v408 = 1 + v368 && 2 <= v408 23.99/7.67 f_519(v359, v360, v361, v362, v363, v366, 1, v405, v368, v408, v369, v370, v371, v372, v373, 0, 3, 2, 4) -> f_522(v359, v360, v361, v362, v363, v366, 1, v405, v368, v408, v369, v370, v371, v372, v373, 0, 3, 2, 4) :|: TRUE 23.99/7.67 f_522(v359, v360, v361, v362, v363, v366, 1, v405, v368, v408, v369, v370, v371, v372, v373, 0, 3, 2, 4) -> f_525(v359, v360, v361, v362, v363, v366, 1, v405, v368, v408, v369, v370, v371, v372, v373, 0, 3, 2, 4) :|: TRUE 23.99/7.67 f_525(v359, v360, v361, v362, v363, v366, 1, v405, v368, v408, v369, v370, v371, v372, v373, 0, 3, 2, 4) -> f_467(v359, v360, v361, v362, v363, v366, 1, v405, v368, v408, v369, v370, v371, v372, v373, 0, 3, 4) :|: TRUE 23.99/7.67 f_467(v359, v360, v361, v362, v363, v364, 1, v366, v367, v368, v369, v370, v371, v372, v373, 0, 3, 4) -> f_469(v359, v360, v361, v362, v363, v366, 1, v364, v367, v368, v369, v370, v371, v372, v373, 0, 3, 4) :|: 0 = 0 23.99/7.67 Combined rules. Obtained 1 rulesP rules: 23.99/7.67 f_469(v359:0, v360:0, v361:0, v362:0, v363:0, 1 + v405:0, 1, v364:0, v367:0, v368:0, v369:0, v370:0, v371:0, v372:0, v373:0, 0, 3, 4) -> f_469(v359:0, v360:0, v361:0, v362:0, v363:0, v405:0, 1, 1 + v405:0, v368:0, 1 + v368:0, v369:0, v370:0, v371:0, v372:0, v373:0, 0, 3, 4) :|: v364:0 > 1 && v405:0 > -1 && v359:0 > 1 && v368:0 > 0 23.99/7.67 Filtered unneeded arguments: 23.99/7.67 f_469(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18) -> f_469(x1, x6, x8, x10) 23.99/7.67 Removed division, modulo operations, cleaned up constraints. Obtained 1 rules.P rules: 23.99/7.67 f_469(v359:0, sum~cons_1~v405:0, v364:0, v368:0) -> f_469(v359:0, v405:0, 1 + v405:0, 1 + v368:0) :|: v405:0 > -1 && v364:0 > 1 && v368:0 > 0 && v359:0 > 1 && sum~cons_1~v405:0 = 1 + v405:0 23.99/7.67 23.99/7.67 ---------------------------------------- 23.99/7.67 23.99/7.67 (23) 23.99/7.67 Obligation: 23.99/7.67 Rules: 23.99/7.67 f_469(v359:0, sum~cons_1~v405:0, v364:0, v368:0) -> f_469(v359:0, v405:0, 1 + v405:0, 1 + v368:0) :|: v405:0 > -1 && v364:0 > 1 && v368:0 > 0 && v359:0 > 1 && sum~cons_1~v405:0 = 1 + v405:0 23.99/7.67 23.99/7.67 ---------------------------------------- 23.99/7.67 23.99/7.67 (24) IRS2T2 (EQUIVALENT) 23.99/7.67 Transformed input IRS into an integer transition system.Used the following mapping from defined symbols to location IDs: 23.99/7.67 23.99/7.67 (f_469_4,1) 23.99/7.67 23.99/7.67 ---------------------------------------- 23.99/7.67 23.99/7.67 (25) 23.99/7.67 Obligation: 23.99/7.67 START: 0; 23.99/7.67 23.99/7.67 FROM: 0; 23.99/7.67 TO: 1; 23.99/7.67 23.99/7.67 FROM: 1; 23.99/7.67 oldX0 := x0; 23.99/7.67 oldX1 := x1; 23.99/7.67 oldX2 := x2; 23.99/7.67 oldX3 := x3; 23.99/7.67 oldX4 := oldX1 - 1; 23.99/7.67 assume(oldX4 > -1 && oldX2 > 1 && oldX3 > 0 && oldX0 > 1 && oldX1 = 1 + oldX4); 23.99/7.67 x0 := oldX0; 23.99/7.67 x1 := oldX1 - 1; 23.99/7.67 x2 := 1 + oldX4; 23.99/7.67 x3 := 1 + oldX3; 23.99/7.67 TO: 1; 23.99/7.67 23.99/7.67 23.99/7.67 ---------------------------------------- 23.99/7.67 23.99/7.67 (26) T2 (EQUIVALENT) 23.99/7.67 Initially, performed program simplifications using lexicographic rank functions: 23.99/7.67 * Removed transitions 1, 3, 4 using the following rank functions: 23.99/7.67 - Rank function 1: 23.99/7.67 RF for loc. 5: 1+2*x1 23.99/7.67 RF for loc. 6: 2*x1 23.99/7.67 Bound for (chained) transitions 3: 2 23.99/7.67 Bound for (chained) transitions 4: 2 23.99/7.67 - Rank function 2: 23.99/7.67 RF for loc. 5: 0 23.99/7.67 RF for loc. 6: -1 23.99/7.67 Bound for (chained) transitions 1: 0 23.99/7.67 23.99/7.67 ---------------------------------------- 23.99/7.67 23.99/7.67 (27) 23.99/7.67 YES 24.26/8.28 EOF