25.46/8.28 YES 25.46/8.29 proof of /export/starexec/sandbox/benchmark/theBenchmark.c 25.46/8.29 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 25.46/8.29 25.46/8.29 25.46/8.29 Termination of the given C Problem could be proven: 25.46/8.29 25.46/8.29 (0) C Problem 25.46/8.29 (1) CToLLVMProof [EQUIVALENT, 175 ms] 25.46/8.29 (2) LLVM problem 25.46/8.29 (3) LLVMToTerminationGraphProof [EQUIVALENT, 3992 ms] 25.46/8.29 (4) LLVM Symbolic Execution Graph 25.46/8.29 (5) SymbolicExecutionGraphToSCCProof [SOUND, 0 ms] 25.46/8.29 (6) AND 25.46/8.29 (7) LLVM Symbolic Execution SCC 25.46/8.29 (8) SCC2IRS [SOUND, 117 ms] 25.46/8.29 (9) IntTRS 25.46/8.29 (10) IRS2T2 [EQUIVALENT, 0 ms] 25.46/8.29 (11) T2IntSys 25.46/8.29 (12) T2 [EQUIVALENT, 1344 ms] 25.46/8.29 (13) YES 25.46/8.29 (14) LLVM Symbolic Execution SCC 25.46/8.29 (15) SCC2IRS [SOUND, 58 ms] 25.46/8.29 (16) IntTRS 25.46/8.29 (17) IRS2T2 [EQUIVALENT, 0 ms] 25.46/8.29 (18) T2IntSys 25.46/8.29 (19) T2 [EQUIVALENT, 1103 ms] 25.46/8.29 (20) YES 25.46/8.29 25.46/8.29 25.46/8.29 ---------------------------------------- 25.46/8.29 25.46/8.29 (0) 25.46/8.29 Obligation: 25.46/8.29 c file /export/starexec/sandbox/benchmark/theBenchmark.c 25.46/8.29 ---------------------------------------- 25.46/8.29 25.46/8.29 (1) CToLLVMProof (EQUIVALENT) 25.46/8.29 Compiled c-file /export/starexec/sandbox/benchmark/theBenchmark.c to LLVM. 25.46/8.29 ---------------------------------------- 25.46/8.29 25.46/8.29 (2) 25.46/8.29 Obligation: 25.46/8.29 LLVM Problem 25.46/8.29 25.46/8.29 Aliases: 25.46/8.29 25.46/8.29 Data layout: 25.46/8.29 25.46/8.29 "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" 25.46/8.29 25.46/8.29 Machine: 25.46/8.29 25.46/8.29 "x86_64-pc-linux-gnu" 25.46/8.29 25.46/8.29 Type definitions: 25.46/8.29 25.46/8.29 Global variables: 25.46/8.29 25.46/8.29 Function declarations and definitions: 25.46/8.29 25.46/8.29 *BasicFunctionTypename: "__VERIFIER_nondet_int" returnParam: i32 parameters: () variableLength: false visibilityType: DEFAULT callingConvention: ccc 25.46/8.29 *BasicFunctionTypename: "test_fun" linkageType: EXTERNALLY_VISIBLE returnParam: i32 parameters: (x i32, y i32) variableLength: false visibilityType: DEFAULT callingConvention: ccc 25.46/8.29 0: 25.46/8.29 %1 = alloca i32, align 4 25.46/8.29 %2 = alloca i32, align 4 25.46/8.29 %c = alloca i32, align 4 25.46/8.29 store %x, %1 25.46/8.29 store %y, %2 25.46/8.29 store 0, %c 25.46/8.29 br %3 25.46/8.29 3: 25.46/8.29 %4 = load %1 25.46/8.29 %5 = icmp sge %4 0 25.46/8.29 br %5, %6, %21 25.46/8.29 6: 25.46/8.29 %7 = load %1 25.46/8.29 %8 = add %7 1 25.46/8.29 store %8, %1 25.46/8.29 store 1, %2 25.46/8.29 br %9 25.46/8.29 9: 25.46/8.29 %10 = load %1 25.46/8.29 %11 = load %2 25.46/8.29 %12 = icmp sgt %10 %11 25.46/8.29 br %12, %13, %18 25.46/8.29 13: 25.46/8.29 %14 = load %2 25.46/8.29 %15 = add %14 1 25.46/8.29 store %15, %2 25.46/8.29 %16 = load %c 25.46/8.29 %17 = add %16 1 25.46/8.29 store %17, %c 25.46/8.29 br %9 25.46/8.29 18: 25.46/8.29 %19 = load %1 25.46/8.29 %20 = sub %19 2 25.46/8.29 store %20, %1 25.46/8.29 br %3 25.46/8.29 21: 25.46/8.29 %22 = load %c 25.46/8.29 ret %22 25.46/8.29 25.46/8.29 *BasicFunctionTypename: "main" linkageType: EXTERNALLY_VISIBLE returnParam: i32 parameters: () variableLength: false visibilityType: DEFAULT callingConvention: ccc 25.46/8.29 0: 25.46/8.29 %1 = alloca i32, align 4 25.46/8.29 store 0, %1 25.46/8.29 %2 = call i32 @__VERIFIER_nondet_int() 25.46/8.29 %3 = call i32 @__VERIFIER_nondet_int() 25.46/8.29 %4 = call i32 @test_fun(i32 %2, i32 %3) 25.46/8.29 ret %4 25.46/8.29 25.46/8.29 25.46/8.29 Analyze Termination of all function calls matching the pattern: 25.46/8.29 main() 25.46/8.29 ---------------------------------------- 25.46/8.29 25.46/8.29 (3) LLVMToTerminationGraphProof (EQUIVALENT) 25.46/8.29 Constructed symbolic execution graph for LLVM program and proved memory safety. 25.46/8.29 ---------------------------------------- 25.46/8.29 25.46/8.29 (4) 25.46/8.29 Obligation: 25.46/8.29 SE Graph 25.46/8.29 ---------------------------------------- 25.46/8.29 25.46/8.29 (5) SymbolicExecutionGraphToSCCProof (SOUND) 25.46/8.29 Splitted symbolic execution graph to 2 SCCs. 25.46/8.29 ---------------------------------------- 25.46/8.29 25.46/8.29 (6) 25.46/8.29 Complex Obligation (AND) 25.46/8.29 25.46/8.29 ---------------------------------------- 25.46/8.29 25.46/8.29 (7) 25.46/8.29 Obligation: 25.46/8.29 SCC 25.46/8.29 ---------------------------------------- 25.46/8.29 25.46/8.29 (8) SCC2IRS (SOUND) 25.46/8.29 Transformed LLVM symbolic execution graph SCC into a rewrite problem. Log: 25.46/8.29 Generated rules. Obtained 54 rulesP rules: 25.46/8.29 f_446(v612, v613, v614, v615, v616, v617, 1, v619, 0, v621, v622, v623, v624, v626, v627, v628, v629, v630, 3, 2, 4) -> f_447(v612, v613, v614, v615, v616, v617, 1, v619, 0, v621, v622, v623, v624, v631, v626, v627, v628, v629, v630, 3, 2, 4) :|: 2 + v631 = v619 && 0 <= 1 + v631 25.46/8.29 f_447(v612, v613, v614, v615, v616, v617, 1, v619, 0, v621, v622, v623, v624, v631, v626, v627, v628, v629, v630, 3, 2, 4) -> f_448(v612, v613, v614, v615, v616, v617, 1, v619, 0, v621, v622, v623, v624, v631, v626, v627, v628, v629, v630, 3, 2, 4) :|: TRUE 25.46/8.29 f_448(v612, v613, v614, v615, v616, v617, 1, v619, 0, v621, v622, v623, v624, v631, v626, v627, v628, v629, v630, 3, 2, 4) -> f_449(v612, v613, v614, v615, v616, v617, 1, v619, 0, v621, v622, v623, v624, v631, v626, v627, v628, v629, v630, 3, 2, 4) :|: TRUE 25.46/8.29 f_449(v612, v613, v614, v615, v616, v617, 1, v619, 0, v621, v622, v623, v624, v631, v626, v627, v628, v629, v630, 3, 2, 4) -> f_450(v612, v613, v614, v615, v616, v631, 1, v617, v619, 0, v621, v622, v623, v624, v626, v627, v628, v629, v630, 3, 2, 4) :|: 0 = 0 25.46/8.29 f_450(v612, v613, v614, v615, v616, v631, 1, v617, v619, 0, v621, v622, v623, v624, v626, v627, v628, v629, v630, 3, 2, 4) -> f_451(v612, v613, v614, v615, v616, v631, 1, v617, v619, 0, v621, v622, v623, v624, v626, v627, v628, v629, v630, 3, 2, 4) :|: 0 <= v631 && 2 <= v619 && 1 <= v617 && 2 <= v612 && 1 <= v623 && 2 <= v624 25.46/8.29 f_451(v612, v613, v614, v615, v616, v631, 1, v617, v619, 0, v621, v622, v623, v624, v626, v627, v628, v629, v630, 3, 2, 4) -> f_453(v612, v613, v614, v615, v616, v631, 1, v617, v619, 0, v621, v622, v623, v624, v626, v627, v628, v629, v630, 3, 2, 4) :|: 0 = 0 25.46/8.29 f_453(v612, v613, v614, v615, v616, v631, 1, v617, v619, 0, v621, v622, v623, v624, v626, v627, v628, v629, v630, 3, 2, 4) -> f_455(v612, v613, v614, v615, v616, v631, 1, v617, v619, 0, v621, v622, v623, v624, v626, v627, v628, v629, v630, 3, 2, 4) :|: TRUE 25.46/8.29 f_455(v612, v613, v614, v615, v616, v631, 1, v617, v619, 0, v621, v622, v623, v624, v626, v627, v628, v629, v630, 3, 2, 4) -> f_457(v612, v613, v614, v615, v616, v631, 1, v619, 0, v621, v622, v623, v624, v626, v627, v628, v629, v630, 3, 2, 4) :|: 0 = 0 25.46/8.29 f_457(v612, v613, v614, v615, v616, v631, 1, v619, 0, v621, v622, v623, v624, v626, v627, v628, v629, v630, 3, 2, 4) -> f_459(v612, v613, v614, v615, v616, v631, 1, v663, v619, 0, v621, v622, v623, v624, v626, v627, v628, v629, v630, 3, 2, 4) :|: v663 = 1 + v631 && 1 <= v663 25.46/8.29 f_459(v612, v613, v614, v615, v616, v631, 1, v663, v619, 0, v621, v622, v623, v624, v626, v627, v628, v629, v630, 3, 2, 4) -> f_461(v612, v613, v614, v615, v616, v631, 1, v663, v619, 0, v621, v622, v623, v624, v626, v627, v628, v629, v630, 3, 2, 4) :|: TRUE 25.46/8.29 f_461(v612, v613, v614, v615, v616, v631, 1, v663, v619, 0, v621, v622, v623, v624, v626, v627, v628, v629, v630, 3, 2, 4) -> f_462(v612, v613, v614, v615, v616, v631, 1, v663, v619, 0, v621, v622, v623, v624, v626, v627, v628, v629, v630, 3, 2, 4) :|: TRUE 25.46/8.29 f_462(v612, v613, v614, v615, v616, v631, 1, v663, v619, 0, v621, v622, v623, v624, v626, v627, v628, v629, v630, 3, 2, 4) -> f_463(v612, v613, v614, v615, v616, v631, 1, v663, v619, 0, v621, v622, v623, v624, v626, v627, v628, v629, v630, 3, 2, 4) :|: TRUE 25.46/8.29 f_463(v612, v613, v614, v615, v616, v631, 1, v663, v619, 0, v621, v622, v623, v624, v626, v627, v628, v629, v630, 3, 2, 4) -> f_464(v612, v613, v614, v615, v616, v631, 1, v663, v619, 0, v621, v622, v623, v624, v626, v627, v628, v629, v630, 3, 2, 4) :|: TRUE 25.46/8.29 f_464(v685, v686, v687, v688, v689, v690, 1, v692, v693, 0, v695, v696, v697, v698, v699, v700, v701, v702, v703, 3, 2, 4) -> f_465(v685, v686, v687, v688, v689, v690, 1, v692, v693, 0, v695, v696, v697, v698, v699, v700, v701, v702, v703, 3, 2, 4) :|: 0 = 0 25.46/8.29 f_465(v685, v686, v687, v688, v689, v690, 1, v692, v693, 0, v695, v696, v697, v698, v699, v700, v701, v702, v703, 3, 2, 4) -> f_466(v685, v686, v687, v688, v689, v690, 1, v692, 0, v695, v696, v697, v698, v693, v699, v700, v701, v702, v703, 3, 2, 4) :|: 0 = 0 25.46/8.29 f_466(v685, v686, v687, v688, v689, v690, 1, v692, 0, v695, v696, v697, v698, v693, v699, v700, v701, v702, v703, 3, 2, 4) -> f_467(v685, v686, v687, v688, v689, v690, 1, v692, 0, v695, v696, v697, v698, v693, v699, v700, v701, v702, v703, 3, 2, 4) :|: 1 < v692 && 1 <= v690 && 3 <= v693 && 3 <= v696 && 2 <= v695 && 2 <= v685 25.46/8.29 f_466(v685, v686, v687, v688, v689, v690, 1, v692, 0, v695, v696, v697, v698, v693, v699, v700, v701, v702, v703, 3, 2, 4) -> f_468(v685, v686, v687, v688, v689, 0, 1, v695, v696, v697, v698, 2, v699, v700, v701, v702, v703, 3, 4) :|: v692 <= 1 && v690 = 0 && v692 = 1 && 0 = 0 && v693 = 2 25.46/8.29 f_467(v685, v686, v687, v688, v689, v690, 1, v692, 0, v695, v696, v697, v698, v693, v699, v700, v701, v702, v703, 3, 2, 4) -> f_469(v685, v686, v687, v688, v689, v690, 1, v692, v695, v696, v697, v698, v693, v699, v700, v701, v702, v703, 0, 3, 2, 4) :|: 0 = 0 25.46/8.29 f_469(v685, v686, v687, v688, v689, v690, 1, v692, v695, v696, v697, v698, v693, v699, v700, v701, v702, v703, 0, 3, 2, 4) -> f_471(v685, v686, v687, v688, v689, v690, 1, v692, v695, v696, v697, v698, v693, v699, v700, v701, v702, v703, 0, 3, 2, 4) :|: TRUE 25.46/8.29 f_471(v685, v686, v687, v688, v689, v690, 1, v692, v695, v696, v697, v698, v693, v699, v700, v701, v702, v703, 0, 3, 2, 4) -> f_488(v685, v686, v687, v688, v689, v690, 1, v692, 1, v695, v696, v697, v698, v693, v699, v700, v701, v702, v703, 0, 3, 2, 4) :|: TRUE 25.46/8.29 f_488(v807, v808, v809, v810, v811, v812, 1, v814, v815, v816, v817, v818, v819, v820, v821, v822, v823, v824, v825, 0, 3, 2, 4) -> f_490(v807, v808, v809, v810, v811, v812, 1, v814, v815, v817, v818, v819, v820, v821, v822, v823, v824, v825, 0, 3, 2, 4) :|: 0 = 0 25.46/8.29 f_490(v807, v808, v809, v810, v811, v812, 1, v814, v815, v817, v818, v819, v820, v821, v822, v823, v824, v825, 0, 3, 2, 4) -> f_491(v807, v808, v809, v810, v811, v812, 1, v814, v815, v852, v818, v819, v820, v821, v822, v823, v824, v825, 0, 3, 2, 4) :|: v852 = 1 + v815 && 2 <= v852 25.46/8.29 f_491(v807, v808, v809, v810, v811, v812, 1, v814, v815, v852, v818, v819, v820, v821, v822, v823, v824, v825, 0, 3, 2, 4) -> f_492(v807, v808, v809, v810, v811, v812, 1, v814, v815, v852, v818, v819, v820, v821, v822, v823, v824, v825, 0, 3, 2, 4) :|: TRUE 25.46/8.29 f_492(v807, v808, v809, v810, v811, v812, 1, v814, v815, v852, v818, v819, v820, v821, v822, v823, v824, v825, 0, 3, 2, 4) -> f_493(v807, v808, v809, v810, v811, v812, 1, v814, v815, v852, v819, v820, v821, v822, v823, v824, v825, 0, 3, 2, 4) :|: 0 = 0 25.46/8.29 f_493(v807, v808, v809, v810, v811, v812, 1, v814, v815, v852, v819, v820, v821, v822, v823, v824, v825, 0, 3, 2, 4) -> f_494(v807, v808, v809, v810, v811, v812, 1, v814, v815, v852, v819, v854, v820, v821, v822, v823, v824, v825, 0, 3, 2, 4) :|: v854 = 1 + v819 && 2 <= v854 25.46/8.29 f_494(v807, v808, v809, v810, v811, v812, 1, v814, v815, v852, v819, v854, v820, v821, v822, v823, v824, v825, 0, 3, 2, 4) -> f_495(v807, v808, v809, v810, v811, v812, 1, v814, v815, v852, v819, v854, v820, v821, v822, v823, v824, v825, 0, 3, 2, 4) :|: TRUE 25.46/8.29 f_495(v807, v808, v809, v810, v811, v812, 1, v814, v815, v852, v819, v854, v820, v821, v822, v823, v824, v825, 0, 3, 2, 4) -> f_496(v807, v808, v809, v810, v811, v812, 1, v814, v815, v852, v819, v854, v820, v821, v822, v823, v824, v825, 0, 3, 2, 4) :|: TRUE 25.46/8.29 f_496(v807, v808, v809, v810, v811, v812, 1, v814, v815, v852, v819, v854, v820, v821, v822, v823, v824, v825, 0, 3, 2, 4) -> f_497(v807, v808, v809, v810, v811, v812, 1, v814, v815, v852, v819, v854, v820, v821, v822, v823, v824, v825, 0, 3, 2, 4) :|: TRUE 25.46/8.29 f_497(v878, v879, v880, v881, v882, v883, 1, v885, v886, v887, v888, v889, v890, v891, v892, v893, v894, v895, 0, 3, 2, 4) -> f_498(v878, v879, v880, v881, v882, v883, 1, v885, v886, v887, v888, v889, v890, v891, v892, v893, v894, v895, 0, 3, 2, 4) :|: 0 = 0 25.46/8.29 f_498(v878, v879, v880, v881, v882, v883, 1, v885, v886, v887, v888, v889, v890, v891, v892, v893, v894, v895, 0, 3, 2, 4) -> f_499(v878, v879, v880, v881, v882, v883, 1, v885, v887, v886, v888, v889, v890, v891, v892, v893, v894, v895, 0, 3, 2, 4) :|: 0 = 0 25.46/8.29 f_499(v878, v879, v880, v881, v882, v883, 1, v885, v887, v886, v888, v889, v890, v891, v892, v893, v894, v895, 0, 3, 2, 4) -> f_500(v878, v879, v880, v881, v882, v883, 1, v885, v887, v886, v888, v889, v890, v891, v892, v893, v894, v895, 0, 3, 2, 4) :|: v887 < v885 && 3 <= v885 && 2 <= v883 && 4 <= v890 && 3 <= v878 25.46/8.29 f_499(v878, v879, v880, v881, v882, v883, 1, v885, v887, v886, v888, v889, v890, v891, v892, v893, v894, v895, 0, 3, 2, 4) -> f_501(v878, v879, v880, v881, v882, v886, 1, v887, v888, v889, v890, v891, v892, v893, v894, v895, 0, 3, 2, 4) :|: v885 <= v887 && v885 = v887 && v883 = v886 25.46/8.29 f_500(v878, v879, v880, v881, v882, v883, 1, v885, v887, v886, v888, v889, v890, v891, v892, v893, v894, v895, 0, 3, 2, 4) -> f_502(v878, v879, v880, v881, v882, v883, 1, v885, v887, v886, v888, v889, v890, v891, v892, v893, v894, v895, 0, 3, 2, 4) :|: 0 = 0 25.46/8.29 f_502(v878, v879, v880, v881, v882, v883, 1, v885, v887, v886, v888, v889, v890, v891, v892, v893, v894, v895, 0, 3, 2, 4) -> f_504(v878, v879, v880, v881, v882, v883, 1, v885, v887, v886, v888, v889, v890, v891, v892, v893, v894, v895, 0, 3, 2, 4) :|: TRUE 25.46/8.29 f_504(v878, v879, v880, v881, v882, v883, 1, v885, v887, v886, v888, v889, v890, v891, v892, v893, v894, v895, 0, 3, 2, 4) -> f_488(v878, v879, v880, v881, v882, v883, 1, v885, v887, v886, v887, v888, v889, v890, v891, v892, v893, v894, v895, 0, 3, 2, 4) :|: TRUE 25.46/8.29 f_501(v878, v879, v880, v881, v882, v886, 1, v887, v888, v889, v890, v891, v892, v893, v894, v895, 0, 3, 2, 4) -> f_503(v878, v879, v880, v881, v882, v886, 1, v887, 0, v888, v889, v890, v891, v892, v893, v894, v895, 3, 2, 4) :|: 0 = 0 25.46/8.29 f_503(v878, v879, v880, v881, v882, v886, 1, v887, 0, v888, v889, v890, v891, v892, v893, v894, v895, 3, 2, 4) -> f_505(v878, v879, v880, v881, v882, v886, 1, v887, 0, v888, v889, v890, v891, v892, v893, v894, v895, 3, 2, 4) :|: TRUE 25.46/8.29 f_505(v878, v879, v880, v881, v882, v886, 1, v887, 0, v888, v889, v890, v891, v892, v893, v894, v895, 3, 2, 4) -> f_506(v878, v879, v880, v881, v882, v886, 1, v887, 0, v888, v889, v891, v892, v893, v894, v895, 3, 2, 4) :|: 0 = 0 25.46/8.29 f_506(v878, v879, v880, v881, v882, v886, 1, v887, 0, v888, v889, v891, v892, v893, v894, v895, 3, 2, 4) -> f_507(v878, v879, v880, v881, v882, v886, 1, v887, 0, v888, v889, v954, v891, v892, v893, v894, v895, 3, 2, 4) :|: 2 + v954 = v887 && 0 <= v954 25.46/8.29 f_507(v878, v879, v880, v881, v882, v886, 1, v887, 0, v888, v889, v954, v891, v892, v893, v894, v895, 3, 2, 4) -> f_508(v878, v879, v880, v881, v882, v886, 1, v887, 0, v888, v889, v954, v891, v892, v893, v894, v895, 3, 2, 4) :|: TRUE 25.46/8.29 f_508(v878, v879, v880, v881, v882, v886, 1, v887, 0, v888, v889, v954, v891, v892, v893, v894, v895, 3, 2, 4) -> f_509(v878, v879, v880, v881, v882, v886, 1, v887, 0, v888, v889, v954, v891, v892, v893, v894, v895, 3, 2, 4) :|: TRUE 25.46/8.29 f_509(v878, v879, v880, v881, v882, v886, 1, v887, 0, v888, v889, v954, v891, v892, v893, v894, v895, 3, 2, 4) -> f_510(v878, v879, v880, v881, v882, v954, 1, v886, v887, 0, v888, v889, v891, v892, v893, v894, v895, 3, 2, 4) :|: 0 = 0 25.46/8.29 f_510(v878, v879, v880, v881, v882, v954, 1, v886, v887, 0, v888, v889, v891, v892, v893, v894, v895, 3, 2, 4) -> f_511(v878, v879, v880, v881, v882, v954, 1, v886, v887, 0, v888, v889, v891, v892, v893, v894, v895, 3, 2, 4) :|: 0 = 0 25.46/8.29 f_511(v878, v879, v880, v881, v882, v954, 1, v886, v887, 0, v888, v889, v891, v892, v893, v894, v895, 3, 2, 4) -> f_512(v878, v879, v880, v881, v882, v954, 1, v886, v887, 0, v888, v889, v891, v892, v893, v894, v895, 3, 2, 4) :|: TRUE 25.46/8.29 f_512(v878, v879, v880, v881, v882, v954, 1, v886, v887, 0, v888, v889, v891, v892, v893, v894, v895, 3, 2, 4) -> f_513(v878, v879, v880, v881, v882, v954, 1, v887, 0, v886, v888, v889, v891, v892, v893, v894, v895, 3, 2, 4) :|: 0 = 0 25.46/8.29 f_513(v878, v879, v880, v881, v882, v954, 1, v887, 0, v886, v888, v889, v891, v892, v893, v894, v895, 3, 2, 4) -> f_514(v878, v879, v880, v881, v882, v954, 1, v886, v887, 0, v888, v889, v891, v892, v893, v894, v895, 3, 2, 4) :|: v886 = 1 + v954 25.46/8.29 f_514(v878, v879, v880, v881, v882, v954, 1, v886, v887, 0, v888, v889, v891, v892, v893, v894, v895, 3, 2, 4) -> f_515(v878, v879, v880, v881, v882, v954, 1, v886, v887, 0, v888, v889, v891, v892, v893, v894, v895, 3, 2, 4) :|: TRUE 25.46/8.29 f_515(v878, v879, v880, v881, v882, v954, 1, v886, v887, 0, v888, v889, v891, v892, v893, v894, v895, 3, 2, 4) -> f_516(v878, v879, v880, v881, v882, v954, 1, v886, v887, 0, v888, v889, v891, v892, v893, v894, v895, 3, 2, 4) :|: TRUE 25.46/8.29 f_516(v878, v879, v880, v881, v882, v954, 1, v886, v887, 0, v888, v889, v891, v892, v893, v894, v895, 3, 2, 4) -> f_517(v878, v879, v880, v881, v882, v954, 1, v886, v887, 0, v888, v889, v891, v892, v893, v894, v895, 3, 2, 4) :|: TRUE 25.46/8.29 f_517(v878, v879, v880, v881, v882, v954, 1, v886, v887, 0, v888, v889, v891, v892, v893, v894, v895, 3, 2, 4) -> f_464(v878, v879, v880, v881, v882, v954, 1, v886, v887, 0, v886, v887, v888, v889, v891, v892, v893, v894, v895, 3, 2, 4) :|: TRUE 25.46/8.29 f_468(v685, v686, v687, v688, v689, 0, 1, v695, v696, v697, v698, 2, v699, v700, v701, v702, v703, 3, 4) -> f_470(v685, v686, v687, v688, v689, 0, 1, v695, v696, v697, v698, 2, v699, v700, v701, v702, v703, 3, 4) :|: 0 = 0 25.46/8.29 f_470(v685, v686, v687, v688, v689, 0, 1, v695, v696, v697, v698, 2, v699, v700, v701, v702, v703, 3, 4) -> f_472(v685, v686, v687, v688, v689, 0, 1, v695, v696, v697, v698, 2, v699, v700, v701, v702, v703, 3, 4) :|: TRUE 25.46/8.29 f_472(v685, v686, v687, v688, v689, 0, 1, v695, v696, v697, v698, 2, v699, v700, v701, v702, v703, 3, 4) -> f_445(v685, v686, v687, v688, v689, 0, 1, 1, 0, v695, v696, v697, v698, 2, v699, v700, v701, v702, v703, 3, 2, 4) :|: TRUE 25.46/8.29 f_445(v612, v613, v614, v615, v616, v617, 1, v619, 0, v621, v622, v623, v624, v625, v626, v627, v628, v629, v630, 3, 2, 4) -> f_446(v612, v613, v614, v615, v616, v617, 1, v619, 0, v621, v622, v623, v624, v626, v627, v628, v629, v630, 3, 2, 4) :|: 0 = 0 25.46/8.29 Combined rules. Obtained 3 rulesP rules: 25.46/8.29 f_499(v878:0, v879:0, v880:0, v881:0, v882:0, v883:0, 1, v885:0, v887:0, v886:0, v888:0, v889:0, v890:0, v891:0, v892:0, v893:0, v894:0, v895:0, 0, 3, 2, 4) -> f_499(v878:0, v879:0, v880:0, v881:0, v882:0, v883:0, 1, v885:0, 1 + v887:0, v887:0, v889:0, 1 + v889:0, v890:0, v891:0, v892:0, v893:0, v894:0, v895:0, 0, 3, 2, 4) :|: v887:0 > 0 && v889:0 > 0 && v885:0 > 2 && v887:0 < v885:0 && v883:0 > 1 && v878:0 > 2 && v890:0 > 3 25.46/8.29 f_466(v685:0, v686:0, v687:0, v688:0, v689:0, v690:0, 1, v692:0, 0, v695:0, v696:0, v697:0, v698:0, v693:0, v699:0, v700:0, v701:0, v702:0, v703:0, 3, 2, 4) -> f_499(v685:0, v686:0, v687:0, v688:0, v689:0, v690:0, 1, v692:0, 2, 1, v698:0, 1 + v698:0, v693:0, v699:0, v700:0, v701:0, v702:0, v703:0, 0, 3, 2, 4) :|: v690:0 > 0 && v692:0 > 1 && v693:0 > 2 && v696:0 > 2 && v695:0 > 1 && v698:0 > 0 && v685:0 > 1 25.46/8.29 f_499(v878:0, v879:0, v880:0, v881:0, v882:0, 1 + v954:0, 1, 2 + v954:0, 2 + v954:0, 1 + v954:0, v888:0, v889:0, v890:0, v891:0, v892:0, v893:0, v894:0, v895:0, 0, 3, 2, 4) -> f_466(v878:0, v879:0, v880:0, v881:0, v882:0, v954:0, 1, 1 + v954:0, 0, 1 + v954:0, 2 + v954:0, v888:0, v889:0, 2 + v954:0, v891:0, v892:0, v893:0, v894:0, v895:0, 3, 2, 4) :|: v954:0 > -1 25.46/8.29 Filtered unneeded arguments: 25.46/8.29 f_499(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18, x19, x20, x21, x22) -> f_499(x1, x6, x8, x9, x10, x12, x13) 25.46/8.29 f_466(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18, x19, x20, x21, x22) -> f_466(x1, x6, x8, x10, x11, x13, x14) 25.46/8.29 Removed division, modulo operations, cleaned up constraints. Obtained 3 rules.P rules: 25.46/8.29 f_499(v878:0, v883:0, v885:0, v887:0, v886:0, v889:0, v890:0) -> f_499(v878:0, v883:0, v885:0, 1 + v887:0, v887:0, 1 + v889:0, v890:0) :|: v889:0 > 0 && v887:0 > 0 && v885:0 > 2 && v887:0 < v885:0 && v883:0 > 1 && v890:0 > 3 && v878:0 > 2 25.46/8.29 f_466(v685:0, v690:0, v692:0, v695:0, v696:0, v698:0, v693:0) -> f_499(v685:0, v690:0, v692:0, 2, 1, 1 + v698:0, v693:0) :|: v692:0 > 1 && v690:0 > 0 && v693:0 > 2 && v696:0 > 2 && v695:0 > 1 && v685:0 > 1 && v698:0 > 0 25.46/8.29 f_499(v878:0, sum~cons_1~v954:0, sum~cons_2~v954:0, sum~cons_2~v954:01, sum~cons_1~v954:01, v889:0, v890:0) -> f_466(v878:0, v954:0, 1 + v954:0, 1 + v954:0, 2 + v954:0, v889:0, 2 + v954:0) :|: v954:0 > -1 && sum~cons_1~v954:0 = 1 + v954:0 && sum~cons_2~v954:0 = 2 + v954:0 && sum~cons_2~v954:01 = 2 + v954:0 && sum~cons_1~v954:01 = 1 + v954:0 25.46/8.29 25.46/8.29 ---------------------------------------- 25.46/8.29 25.46/8.29 (9) 25.46/8.29 Obligation: 25.46/8.29 Rules: 25.46/8.29 f_499(v878:0, v883:0, v885:0, v887:0, v886:0, v889:0, v890:0) -> f_499(v878:0, v883:0, v885:0, 1 + v887:0, v887:0, 1 + v889:0, v890:0) :|: v889:0 > 0 && v887:0 > 0 && v885:0 > 2 && v887:0 < v885:0 && v883:0 > 1 && v890:0 > 3 && v878:0 > 2 25.46/8.29 f_466(v685:0, v690:0, v692:0, v695:0, v696:0, v698:0, v693:0) -> f_499(v685:0, v690:0, v692:0, 2, 1, 1 + v698:0, v693:0) :|: v692:0 > 1 && v690:0 > 0 && v693:0 > 2 && v696:0 > 2 && v695:0 > 1 && v685:0 > 1 && v698:0 > 0 25.46/8.29 f_499(x, x1, x2, x3, x4, x5, x6) -> f_466(x, x7, 1 + x7, 1 + x7, 2 + x7, x5, 2 + x7) :|: x7 > -1 && x1 = 1 + x7 && x2 = 2 + x7 && x3 = 2 + x7 && x4 = 1 + x7 25.46/8.29 25.46/8.29 ---------------------------------------- 25.46/8.29 25.46/8.29 (10) IRS2T2 (EQUIVALENT) 25.46/8.29 Transformed input IRS into an integer transition system.Used the following mapping from defined symbols to location IDs: 25.46/8.29 25.46/8.29 (f_499_7,1) 25.46/8.29 (f_466_7,2) 25.46/8.29 25.46/8.29 ---------------------------------------- 25.46/8.29 25.46/8.29 (11) 25.46/8.29 Obligation: 25.46/8.29 START: 0; 25.46/8.29 25.46/8.29 FROM: 0; 25.46/8.29 TO: 1; 25.46/8.29 25.46/8.29 FROM: 0; 25.46/8.29 TO: 2; 25.46/8.29 25.46/8.29 FROM: 1; 25.46/8.29 oldX0 := x0; 25.46/8.29 oldX1 := x1; 25.46/8.29 oldX2 := x2; 25.46/8.29 oldX3 := x3; 25.46/8.29 oldX4 := x4; 25.46/8.29 oldX5 := x5; 25.46/8.29 oldX6 := x6; 25.46/8.29 assume(oldX5 > 0 && oldX3 > 0 && oldX2 > 2 && oldX3 < oldX2 && oldX1 > 1 && oldX6 > 3 && oldX0 > 2); 25.46/8.29 x0 := oldX0; 25.46/8.29 x1 := oldX1; 25.46/8.29 x2 := oldX2; 25.46/8.29 x3 := 1 + oldX3; 25.46/8.29 x4 := oldX3; 25.46/8.29 x5 := 1 + oldX5; 25.46/8.29 x6 := oldX6; 25.46/8.29 TO: 1; 25.46/8.29 25.46/8.29 FROM: 2; 25.46/8.29 oldX0 := x0; 25.46/8.29 oldX1 := x1; 25.46/8.29 oldX2 := x2; 25.46/8.29 oldX3 := x3; 25.46/8.29 oldX4 := x4; 25.46/8.29 oldX5 := x5; 25.46/8.29 oldX6 := x6; 25.46/8.29 assume(oldX2 > 1 && oldX1 > 0 && oldX6 > 2 && oldX4 > 2 && oldX3 > 1 && oldX0 > 1 && oldX5 > 0); 25.46/8.29 x0 := oldX0; 25.46/8.29 x1 := oldX1; 25.46/8.29 x2 := oldX2; 25.46/8.29 x3 := 2; 25.46/8.29 x4 := 1; 25.46/8.29 x5 := 1 + oldX5; 25.46/8.29 x6 := oldX6; 25.46/8.29 TO: 1; 25.46/8.29 25.46/8.29 FROM: 1; 25.46/8.29 oldX0 := x0; 25.46/8.29 oldX1 := x1; 25.46/8.29 oldX2 := x2; 25.46/8.29 oldX3 := x3; 25.46/8.29 oldX4 := x4; 25.46/8.29 oldX5 := x5; 25.46/8.29 oldX6 := x6; 25.46/8.29 oldX7 := oldX1 - 1; 25.46/8.29 assume(oldX7 > -1 && oldX1 = 1 + oldX7 && oldX2 = 2 + oldX7 && oldX3 = 2 + oldX7 && oldX4 = 1 + oldX7); 25.46/8.29 x0 := oldX0; 25.46/8.29 x1 := oldX1 - 1; 25.46/8.29 x2 := 1 + oldX7; 25.46/8.29 x3 := 1 + oldX7; 25.46/8.29 x4 := 2 + oldX7; 25.46/8.29 x5 := oldX5; 25.46/8.29 x6 := 2 + oldX7; 25.46/8.29 TO: 2; 25.46/8.29 25.46/8.29 25.46/8.29 ---------------------------------------- 25.46/8.29 25.46/8.29 (12) T2 (EQUIVALENT) 25.46/8.29 Initially, performed program simplifications using lexicographic rank functions: 25.46/8.29 * Removed transitions 2, 5, 6, 14, 16, 17 using the following rank functions: 25.46/8.29 - Rank function 1: 25.46/8.29 RF for loc. 6: x1 25.46/8.29 RF for loc. 8: x1 25.46/8.29 RF for loc. 12: 1+x1 25.46/8.29 Bound for (chained) transitions 16: 2 25.46/8.29 - Rank function 2: 25.46/8.29 RF for loc. 6: 2*x1 25.46/8.29 RF for loc. 8: 2*x1 25.46/8.29 RF for loc. 12: 1+2*x1 25.46/8.29 Bound for (chained) transitions 6, 14: 2 25.46/8.29 - Rank function 3: 25.46/8.29 RF for loc. 6: -x3-x5 25.46/8.29 RF for loc. 8: -1-x3-x5 25.46/8.29 RF for loc. 12: 0 25.46/8.29 Bound for (chained) transitions 17: 0 25.46/8.29 - Rank function 4: 25.46/8.29 RF for loc. 6: x2-x3 25.46/8.29 RF for loc. 8: x2-x3 25.46/8.29 Bound for (chained) transitions 5: 1 25.46/8.29 - Rank function 5: 25.46/8.29 RF for loc. 6: 0 25.46/8.29 RF for loc. 8: -1 25.46/8.29 Bound for (chained) transitions 2: 0 25.46/8.29 25.46/8.29 ---------------------------------------- 25.46/8.29 25.46/8.29 (13) 25.46/8.29 YES 25.46/8.29 25.46/8.29 ---------------------------------------- 25.46/8.29 25.46/8.29 (14) 25.46/8.29 Obligation: 25.46/8.29 SCC 25.46/8.29 ---------------------------------------- 25.46/8.29 25.46/8.29 (15) SCC2IRS (SOUND) 25.46/8.29 Transformed LLVM symbolic execution graph SCC into a rewrite problem. Log: 25.46/8.29 Generated rules. Obtained 13 rulesP rules: 25.46/8.29 f_279(v95, v96, v97, v98, v99, 1, v101, v102, v103, v104, v105, v106, v107, v108, v109, 0, 3, 2, 4) -> f_280(v95, v96, v97, v98, v99, 1, v101, v103, v102, v104, v105, v106, v107, v108, v109, 0, 3, 2, 4) :|: 0 = 0 25.46/8.29 f_280(v95, v96, v97, v98, v99, 1, v101, v103, v102, v104, v105, v106, v107, v108, v109, 0, 3, 2, 4) -> f_281(v95, v96, v97, v98, v99, 1, v101, v103, v102, v104, v105, v106, v107, v108, v109, 0, 3, 2, 4) :|: v103 < v101 && 3 <= v101 && 2 <= v95 25.46/8.29 f_281(v95, v96, v97, v98, v99, 1, v101, v103, v102, v104, v105, v106, v107, v108, v109, 0, 3, 2, 4) -> f_283(v95, v96, v97, v98, v99, 1, v101, v103, v102, v104, v105, v106, v107, v108, v109, 0, 3, 2, 4) :|: 0 = 0 25.46/8.29 f_283(v95, v96, v97, v98, v99, 1, v101, v103, v102, v104, v105, v106, v107, v108, v109, 0, 3, 2, 4) -> f_285(v95, v96, v97, v98, v99, 1, v101, v103, v102, v104, v105, v106, v107, v108, v109, 0, 3, 2, 4) :|: TRUE 25.46/8.29 f_285(v95, v96, v97, v98, v99, 1, v101, v103, v102, v104, v105, v106, v107, v108, v109, 0, 3, 2, 4) -> f_287(v95, v96, v97, v98, v99, 1, v101, v103, v104, v102, v105, v106, v107, v108, v109, 0, 3, 2, 4) :|: 0 = 0 25.46/8.29 f_287(v95, v96, v97, v98, v99, 1, v101, v103, v104, v102, v105, v106, v107, v108, v109, 0, 3, 2, 4) -> f_289(v95, v96, v97, v98, v99, 1, v101, v103, v111, v104, v102, v105, v106, v107, v108, v109, 0, 3, 2, 4) :|: v111 = 1 + v103 && 3 <= v111 25.46/8.29 f_289(v95, v96, v97, v98, v99, 1, v101, v103, v111, v104, v102, v105, v106, v107, v108, v109, 0, 3, 2, 4) -> f_291(v95, v96, v97, v98, v99, 1, v101, v103, v111, v104, v102, v105, v106, v107, v108, v109, 0, 3, 2, 4) :|: TRUE 25.46/8.29 f_291(v95, v96, v97, v98, v99, 1, v101, v103, v111, v104, v102, v105, v106, v107, v108, v109, 0, 3, 2, 4) -> f_293(v95, v96, v97, v98, v99, 1, v101, v103, v111, v102, v105, v106, v107, v108, v109, 0, 3, 2, 4) :|: 0 = 0 25.46/8.29 f_293(v95, v96, v97, v98, v99, 1, v101, v103, v111, v102, v105, v106, v107, v108, v109, 0, 3, 2, 4) -> f_295(v95, v96, v97, v98, v99, 1, v101, v103, v111, v102, v105, v106, v107, v108, v109, 0, 3, 2, 4) :|: v103 = 1 + v102 25.46/8.29 f_295(v95, v96, v97, v98, v99, 1, v101, v103, v111, v102, v105, v106, v107, v108, v109, 0, 3, 2, 4) -> f_297(v95, v96, v97, v98, v99, 1, v101, v103, v111, v102, v105, v106, v107, v108, v109, 0, 3, 2, 4) :|: TRUE 25.46/8.29 f_297(v95, v96, v97, v98, v99, 1, v101, v103, v111, v102, v105, v106, v107, v108, v109, 0, 3, 2, 4) -> f_299(v95, v96, v97, v98, v99, 1, v101, v103, v111, v102, v105, v106, v107, v108, v109, 0, 3, 2, 4) :|: TRUE 25.46/8.29 f_299(v95, v96, v97, v98, v99, 1, v101, v103, v111, v102, v105, v106, v107, v108, v109, 0, 3, 2, 4) -> f_278(v95, v96, v97, v98, v99, 1, v101, v103, v111, v102, v105, v106, v107, v108, v109, 0, 3, 2, 4) :|: TRUE 25.46/8.29 f_278(v95, v96, v97, v98, v99, 1, v101, v102, v103, v104, v105, v106, v107, v108, v109, 0, 3, 2, 4) -> f_279(v95, v96, v97, v98, v99, 1, v101, v102, v103, v104, v105, v106, v107, v108, v109, 0, 3, 2, 4) :|: 0 = 0 25.46/8.29 Combined rules. Obtained 1 rulesP rules: 25.46/8.29 f_279(v95:0, v96:0, v97:0, v98:0, v99:0, 1, v101:0, v102:0, 1 + v102:0, v104:0, v105:0, v106:0, v107:0, v108:0, v109:0, 0, 3, 2, 4) -> f_279(v95:0, v96:0, v97:0, v98:0, v99:0, 1, v101:0, 1 + v102:0, 1 + (1 + v102:0), v102:0, v105:0, v106:0, v107:0, v108:0, v109:0, 0, 3, 2, 4) :|: v101:0 > 2 && v101:0 > 1 + v102:0 && v102:0 > 0 && v95:0 > 1 25.46/8.29 Filtered unneeded arguments: 25.46/8.29 f_279(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18, x19) -> f_279(x1, x7, x8, x9) 25.46/8.29 Removed division, modulo operations, cleaned up constraints. Obtained 1 rules.P rules: 25.46/8.29 f_279(v95:0, v101:0, v102:0, sum~cons_1~v102:0) -> f_279(v95:0, v101:0, 1 + v102:0, 1 + (1 + v102:0)) :|: v101:0 > 1 + v102:0 && v101:0 > 2 && v95:0 > 1 && v102:0 > 0 && sum~cons_1~v102:0 = 1 + v102:0 25.46/8.29 25.46/8.29 ---------------------------------------- 25.46/8.29 25.46/8.29 (16) 25.46/8.29 Obligation: 25.46/8.29 Rules: 25.46/8.29 f_279(v95:0, v101:0, v102:0, sum~cons_1~v102:0) -> f_279(v95:0, v101:0, 1 + v102:0, 1 + (1 + v102:0)) :|: v101:0 > 1 + v102:0 && v101:0 > 2 && v95:0 > 1 && v102:0 > 0 && sum~cons_1~v102:0 = 1 + v102:0 25.46/8.29 25.46/8.29 ---------------------------------------- 25.46/8.29 25.46/8.29 (17) IRS2T2 (EQUIVALENT) 25.46/8.29 Transformed input IRS into an integer transition system.Used the following mapping from defined symbols to location IDs: 25.46/8.29 25.46/8.29 (f_279_4,1) 25.46/8.29 25.46/8.29 ---------------------------------------- 25.46/8.29 25.46/8.29 (18) 25.46/8.29 Obligation: 25.46/8.29 START: 0; 25.46/8.29 25.46/8.29 FROM: 0; 25.46/8.29 TO: 1; 25.46/8.29 25.46/8.29 FROM: 1; 25.46/8.29 oldX0 := x0; 25.46/8.29 oldX1 := x1; 25.46/8.29 oldX2 := x2; 25.46/8.29 oldX3 := x3; 25.46/8.29 assume(oldX1 > 1 + oldX2 && oldX1 > 2 && oldX0 > 1 && oldX2 > 0 && oldX3 = 1 + oldX2); 25.46/8.29 x0 := oldX0; 25.46/8.29 x1 := oldX1; 25.46/8.29 x2 := 1 + oldX2; 25.46/8.29 x3 := 1 + (1 + oldX2); 25.46/8.29 TO: 1; 25.46/8.29 25.46/8.29 25.46/8.29 ---------------------------------------- 25.46/8.29 25.46/8.29 (19) T2 (EQUIVALENT) 25.46/8.29 Initially, performed program simplifications using lexicographic rank functions: 25.46/8.29 * Removed transitions 1, 3, 4 using the following rank functions: 25.46/8.29 - Rank function 1: 25.46/8.29 RF for loc. 5: 2*x1-x2-x3 25.46/8.29 RF for loc. 6: -1+2*x1-x2-x3 25.46/8.29 Bound for (chained) transitions 3: 2 25.46/8.29 Bound for (chained) transitions 4: 2 25.46/8.29 - Rank function 2: 25.46/8.29 RF for loc. 5: 0 25.46/8.29 RF for loc. 6: -1 25.46/8.29 Bound for (chained) transitions 1: 0 25.46/8.29 25.46/8.29 ---------------------------------------- 25.46/8.29 25.46/8.29 (20) 25.46/8.29 YES 25.78/9.76 EOF