/export/starexec/sandbox2/solver/bin/starexec_run_c /export/starexec/sandbox2/benchmark/theBenchmark.c /export/starexec/sandbox2/output/output_files -------------------------------------------------------------------------------- YES proof of /export/starexec/sandbox2/benchmark/theBenchmark.c # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty Termination of the given C Problem could be proven: (0) C Problem (1) CToLLVMProof [EQUIVALENT, 176 ms] (2) LLVM problem (3) LLVMToTerminationGraphProof [EQUIVALENT, 8588 ms] (4) LLVM Symbolic Execution Graph (5) SymbolicExecutionGraphToSCCProof [SOUND, 0 ms] (6) LLVM Symbolic Execution SCC (7) SCC2IRS [SOUND, 119 ms] (8) IntTRS (9) IntTRSCompressionProof [EQUIVALENT, 0 ms] (10) IntTRS (11) PolynomialOrderProcessor [EQUIVALENT, 11 ms] (12) YES ---------------------------------------- (0) Obligation: c file /export/starexec/sandbox2/benchmark/theBenchmark.c ---------------------------------------- (1) CToLLVMProof (EQUIVALENT) Compiled c-file /export/starexec/sandbox2/benchmark/theBenchmark.c to LLVM. ---------------------------------------- (2) Obligation: LLVM Problem Aliases: Data layout: "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" Machine: "x86_64-pc-linux-gnu" Type definitions: Global variables: Function declarations and definitions: *BasicFunctionTypename: "__VERIFIER_nondet_int" returnParam: i32 parameters: () variableLength: false visibilityType: DEFAULT callingConvention: ccc *BasicFunctionTypename: "sumOfThirdBytes" linkageType: EXTERNALLY_VISIBLE returnParam: i32 parameters: (numbers *i32, array_size i32) variableLength: false visibilityType: DEFAULT callingConvention: ccc 0: %1 = alloca *i32, align 8 %2 = alloca i32, align 4 %i = alloca i32, align 4 %sum = alloca i32, align 4 %p = alloca *i8, align 8 store %numbers, %1 store %array_size, %2 store 0, %sum store 0, %i br %3 3: %4 = load %i %5 = load %2 %6 = icmp slt %4 %5 br %6, %7, %23 7: %8 = load %i %9 = sext i32 %8 to i64 %10 = load %1 %11 = getelementptr %10, %9 %12 = bitcast *i32 %11 to *i8 store %12, %p %13 = load %p %14 = getelementptr %13, 2 store %14, %p %15 = load %sum %16 = load %p %17 = load %16 %18 = sext i8 %17 to i32 %19 = add %15 %18 store %19, %sum br %20 20: %21 = load %i %22 = add %21 1 store %22, %i br %3 23: %24 = load %sum ret %24 *BasicFunctionTypename: "main" linkageType: EXTERNALLY_VISIBLE returnParam: i32 parameters: () variableLength: false visibilityType: DEFAULT callingConvention: ccc 0: %1 = alloca i32, align 4 %array_size = alloca i32, align 4 %numbers = alloca *i32, align 8 store 0, %1 %2 = call i32 @__VERIFIER_nondet_int() store %2, %array_size %3 = load %array_size %4 = icmp slt %3 1 br %4, %5, %6 5: store 1, %array_size br %6 6: %7 = load %array_size %8 = sext i32 %7 to i64 %9 = mul %8 4 %10 = alloca i8, numElementsLit: %9 %11 = bitcast *i8 %10 to *i32 store %11, %numbers %12 = load %numbers %13 = load %array_size %14 = call i32 @sumOfThirdBytes(*i32 %12, i32 %13) ret %14 Analyze Termination of all function calls matching the pattern: main() ---------------------------------------- (3) LLVMToTerminationGraphProof (EQUIVALENT) Constructed symbolic execution graph for LLVM program and proved memory safety. ---------------------------------------- (4) Obligation: SE Graph ---------------------------------------- (5) SymbolicExecutionGraphToSCCProof (SOUND) Splitted symbolic execution graph to 1 SCC. ---------------------------------------- (6) Obligation: SCC ---------------------------------------- (7) SCC2IRS (SOUND) Transformed LLVM symbolic execution graph SCC into a rewrite problem. Log: Generated rules. Obtained 26 rulesP rules: f_515(v416, v417, v418, v419, v420, v421, v422, v423, 1, v425, v426, v427, v428, v429, v430, v431, v437, v432, v438, v433, v439, v440, v441, v442, v443, v444, v445, 0, v446, v448, v434, v435, v436, 3, 7, 2, 4, 8) -> f_516(v416, v417, v418, v419, v420, v421, v422, v423, 1, v426, v427, v428, v429, v430, v425, v431, v437, v432, v438, v433, v439, v440, v441, v442, v443, v444, v445, 0, v446, v448, v434, v435, v436, 3, 7, 2, 4, 8) :|: 0 = 0 f_516(v416, v417, v418, v419, v420, v421, v422, v423, 1, v426, v427, v428, v429, v430, v425, v431, v437, v432, v438, v433, v439, v440, v441, v442, v443, v444, v445, 0, v446, v448, v434, v435, v436, 3, 7, 2, 4, 8) -> f_517(v416, v417, v418, v419, v420, v421, v422, v423, 1, v426, v427, v428, v429, v430, v425, v431, v437, v432, v438, v433, v439, v440, v441, v442, v443, v444, v445, 0, v446, v448, v434, v435, v436, 3, 7, 2, 4, 8) :|: 0 = 0 f_517(v416, v417, v418, v419, v420, v421, v422, v423, 1, v426, v427, v428, v429, v430, v425, v431, v437, v432, v438, v433, v439, v440, v441, v442, v443, v444, v445, 0, v446, v448, v434, v435, v436, 3, 7, 2, 4, 8) -> f_518(v416, v417, v418, v419, v420, v421, v422, v423, 1, v449, v426, v427, v428, v429, v430, v425, v431, v437, v432, v438, v433, v439, v440, v441, v442, v443, v444, v445, 0, v446, v448, v434, v435, v436, 3, 7, 2, 4, 8, 5) :|: v449 = v416 + 4 * v423 && 5 <= v449 f_518(v416, v417, v418, v419, v420, v421, v422, v423, 1, v449, v426, v427, v428, v429, v430, v425, v431, v437, v432, v438, v433, v439, v440, v441, v442, v443, v444, v445, 0, v446, v448, v434, v435, v436, 3, 7, 2, 4, 8, 5) -> f_519(v416, v417, v418, v419, v420, v421, v422, v423, 1, v449, v426, v427, v428, v429, v430, v425, v431, v437, v432, v438, v433, v439, v440, v441, v442, v443, v444, v445, 0, v446, v448, v434, v435, v436, 3, 7, 2, 4, 8, 5) :|: 0 = 0 f_519(v416, v417, v418, v419, v420, v421, v422, v423, 1, v449, v426, v427, v428, v429, v430, v425, v431, v437, v432, v438, v433, v439, v440, v441, v442, v443, v444, v445, 0, v446, v448, v434, v435, v436, 3, 7, 2, 4, 8, 5) -> f_520(v416, v417, v418, v419, v420, v421, v422, v423, 1, v449, v426, v427, v428, v429, v430, v425, v431, v437, v432, v438, v433, v439, v440, v441, v442, v443, v444, v445, 0, v446, v448, v434, v435, v436, 3, 7, 2, 4, 8, 5) :|: TRUE f_520(v416, v417, v418, v419, v420, v421, v422, v423, 1, v449, v426, v427, v428, v429, v430, v425, v431, v437, v432, v438, v433, v439, v440, v441, v442, v443, v444, v445, 0, v446, v448, v434, v435, v436, 3, 7, 2, 4, 8, 5) -> f_521(v416, v417, v418, v419, v420, v421, v422, v423, 1, v449, v427, v428, v429, v430, v425, v431, v437, v432, v438, v433, v439, v440, v441, v442, v443, v444, v445, 0, v446, v448, v434, v435, v436, 3, 7, 2, 4, 8, 5) :|: 0 = 0 f_521(v416, v417, v418, v419, v420, v421, v422, v423, 1, v449, v427, v428, v429, v430, v425, v431, v437, v432, v438, v433, v439, v440, v441, v442, v443, v444, v445, 0, v446, v448, v434, v435, v436, 3, 7, 2, 4, 8, 5) -> f_522(v416, v417, v418, v419, v420, v421, v422, v423, 1, v449, v451, v428, v427, v429, v430, v425, v431, v437, v432, v438, v433, v439, v440, v441, v442, v443, v444, v445, 0, v446, v448, v434, v435, v436, 3, 7, 2, 4, 8, 5) :|: v451 = 2 + v449 && 7 <= v451 f_522(v416, v417, v418, v419, v420, v421, v422, v423, 1, v449, v451, v428, v427, v429, v430, v425, v431, v437, v432, v438, v433, v439, v440, v441, v442, v443, v444, v445, 0, v446, v448, v434, v435, v436, 3, 7, 2, 4, 8, 5) -> f_523(v416, v417, v418, v419, v420, v421, v422, v423, 1, v449, v451, v428, v427, v429, v430, v425, v431, v437, v432, v438, v433, v439, v440, v441, v442, v443, v444, v445, 0, v446, v448, v434, v435, v436, 3, 7, 2, 4, 8, 5) :|: TRUE f_523(v416, v417, v418, v419, v420, v421, v422, v423, 1, v449, v451, v428, v427, v429, v430, v425, v431, v437, v432, v438, v433, v439, v440, v441, v442, v443, v444, v445, 0, v446, v448, v434, v435, v436, 3, 7, 2, 4, 8, 5) -> f_524(v416, v417, v418, v419, v420, v421, v422, v423, 1, v449, v451, v430, v427, v429, v425, v431, v437, v432, v438, v433, v439, v440, v441, v442, v443, v444, v445, 0, v446, v448, v434, v435, v436, 3, 7, 2, 4, 8, 5) :|: 0 = 0 f_524(v416, v417, v418, v419, v420, v421, v422, v423, 1, v449, v451, v430, v427, v429, v425, v431, v437, v432, v438, v433, v439, v440, v441, v442, v443, v444, v445, 0, v446, v448, v434, v435, v436, 3, 7, 2, 4, 8, 5) -> f_525(v416, v417, v418, v419, v420, v421, v422, v423, 1, v449, v451, v430, v429, v425, v431, v437, v432, v438, v433, v439, v440, v441, v442, v443, v444, v445, v427, 0, v446, v448, v434, v435, v436, 3, 7, 2, 4, 8, 5) :|: 0 = 0 f_525(v416, v417, v418, v419, v420, v421, v422, v423, 1, v449, v451, v430, v429, v425, v431, v437, v432, v438, v433, v439, v440, v441, v442, v443, v444, v445, v427, 0, v446, v448, v434, v435, v436, 3, 7, 2, 4, 8, 5) -> f_526(v416, v417, v418, v419, v420, v421, v422, v423, 1, v449, v451, v430, v453, v429, v425, v431, v437, v432, v438, v433, v439, v440, v441, v442, v443, v444, v445, v427, 0, v446, v448, v434, v435, v436, 3, 7, 2, 4, 8, 5) :|: TRUE f_526(v416, v417, v418, v419, v420, v421, v422, v423, 1, v449, v451, v430, v453, v429, v425, v431, v437, v432, v438, v433, v439, v440, v441, v442, v443, v444, v445, v427, 0, v446, v448, v434, v435, v436, 3, 7, 2, 4, 8, 5) -> f_527(v416, v417, v418, v419, v420, v421, v422, v423, 1, v449, v451, v430, v453, v425, v431, v437, v432, v438, v433, v439, v440, v441, v442, v443, v444, v445, v427, v429, 0, v446, v448, v434, v435, v436, 3, 7, 2, 4, 8, 5) :|: 0 = 0 f_527(v416, v417, v418, v419, v420, v421, v422, v423, 1, v449, v451, v430, v453, v425, v431, v437, v432, v438, v433, v439, v440, v441, v442, v443, v444, v445, v427, v429, 0, v446, v448, v434, v435, v436, 3, 7, 2, 4, 8, 5) -> f_528(v416, v417, v418, v419, v420, v421, v422, v423, 1, v449, v451, v430, v453, v455, v425, v431, v437, v432, v438, v433, v439, v440, v441, v442, v443, v444, v445, v427, v429, 0, v446, v448, v434, v435, v436, 3, 7, 2, 4, 8, 5) :|: v455 = v430 + v453 f_528(v416, v417, v418, v419, v420, v421, v422, v423, 1, v449, v451, v430, v453, v455, v425, v431, v437, v432, v438, v433, v439, v440, v441, v442, v443, v444, v445, v427, v429, 0, v446, v448, v434, v435, v436, 3, 7, 2, 4, 8, 5) -> f_529(v416, v417, v418, v419, v420, v421, v422, v423, 1, v449, v451, v430, v453, v455, v425, v431, v437, v432, v438, v433, v439, v440, v441, v442, v443, v444, v445, v427, v429, 0, v446, v448, v434, v435, v436, 3, 7, 2, 4, 8, 5) :|: TRUE f_529(v416, v417, v418, v419, v420, v421, v422, v423, 1, v449, v451, v430, v453, v455, v425, v431, v437, v432, v438, v433, v439, v440, v441, v442, v443, v444, v445, v427, v429, 0, v446, v448, v434, v435, v436, 3, 7, 2, 4, 8, 5) -> f_530(v416, v417, v418, v419, v420, v421, v422, v423, 1, v449, v451, v430, v453, v455, v425, v431, v437, v432, v438, v433, v439, v440, v441, v442, v443, v444, v445, v427, v429, 0, v446, v448, v434, v435, v436, 3, 7, 2, 4, 8, 5) :|: TRUE f_530(v416, v417, v418, v419, v420, v421, v422, v423, 1, v449, v451, v430, v453, v455, v425, v431, v437, v432, v438, v433, v439, v440, v441, v442, v443, v444, v445, v427, v429, 0, v446, v448, v434, v435, v436, 3, 7, 2, 4, 8, 5) -> f_531(v416, v417, v418, v419, v420, v421, v422, v423, 1, v449, v451, v430, v453, v455, v431, v437, v432, v438, v433, v439, v440, v441, v442, v443, v444, v445, v427, v429, 0, v446, v448, v434, v435, v436, 3, 7, 2, 4, 8, 5) :|: 0 = 0 f_531(v416, v417, v418, v419, v420, v421, v422, v423, 1, v449, v451, v430, v453, v455, v431, v437, v432, v438, v433, v439, v440, v441, v442, v443, v444, v445, v427, v429, 0, v446, v448, v434, v435, v436, 3, 7, 2, 4, 8, 5) -> f_532(v416, v417, v418, v419, v420, v421, v422, v423, 1, v449, v451, v430, v453, v455, v458, v431, v437, v432, v438, v433, v439, v440, v441, v442, v443, v444, v445, v427, v429, 0, v446, v448, v434, v435, v436, 3, 7, 2, 4, 8, 5) :|: v458 = 1 + v423 && 2 <= v458 f_532(v416, v417, v418, v419, v420, v421, v422, v423, 1, v449, v451, v430, v453, v455, v458, v431, v437, v432, v438, v433, v439, v440, v441, v442, v443, v444, v445, v427, v429, 0, v446, v448, v434, v435, v436, 3, 7, 2, 4, 8, 5) -> f_533(v416, v417, v418, v419, v420, v421, v422, v423, 1, v449, v451, v430, v453, v455, v458, v431, v437, v432, v438, v433, v439, v440, v441, v442, v443, v444, v445, v427, v429, 0, v446, v448, v434, v435, v436, 3, 7, 2, 4, 8, 5) :|: TRUE f_533(v416, v417, v418, v419, v420, v421, v422, v423, 1, v449, v451, v430, v453, v455, v458, v431, v437, v432, v438, v433, v439, v440, v441, v442, v443, v444, v445, v427, v429, 0, v446, v448, v434, v435, v436, 3, 7, 2, 4, 8, 5) -> f_534(v416, v417, v418, v419, v420, v421, v422, v423, 1, v449, v451, v430, v453, v455, v458, v431, v437, v432, v438, v433, v439, v440, v441, v442, v443, v444, v445, v427, v429, 0, v446, v448, v434, v435, v436, 3, 7, 2, 4, 8, 5) :|: TRUE f_534(v416, v417, v418, v419, v420, v421, v422, v423, 1, v449, v451, v430, v453, v455, v458, v431, v437, v432, v438, v433, v439, v440, v441, v442, v443, v444, v445, v427, v429, 0, v446, v448, v434, v435, v436, 3, 7, 2, 4, 8, 5) -> f_535(v416, v417, v418, v419, v420, v421, v422, v458, 1, v423, v449, v451, v430, v453, v455, v431, v437, v432, v438, v433, v439, v440, v441, v442, v443, v444, v445, v427, v429, 0, v446, v448, v434, v435, v436, 3, 7, 2, 4, 8, 5) :|: 0 = 0 f_535(v416, v417, v418, v419, v420, v421, v422, v458, 1, v423, v449, v451, v430, v453, v455, v431, v437, v432, v438, v433, v439, v440, v441, v442, v443, v444, v445, v427, v429, 0, v446, v448, v434, v435, v436, 3, 7, 2, 4, 8, 5) -> f_536(v416, v417, v418, v419, v420, v421, v422, v458, 1, v423, v449, v451, v430, v453, v455, v431, v437, v432, v438, v433, v439, v440, v441, v442, v443, v444, v445, v427, v429, 0, v446, v448, v434, v435, v436, 3, 7, 2, 4, 8, 5) :|: 0 = 0 f_536(v416, v417, v418, v419, v420, v421, v422, v458, 1, v423, v449, v451, v430, v453, v455, v431, v437, v432, v438, v433, v439, v440, v441, v442, v443, v444, v445, v427, v429, 0, v446, v448, v434, v435, v436, 3, 7, 2, 4, 8, 5) -> f_537(v416, v417, v418, v419, v420, v421, v422, v458, 1, v423, v449, v451, v430, v453, v455, v431, v437, v432, v438, v433, v439, v440, v441, v442, v443, v444, v445, v427, v429, 0, v446, v448, v434, v435, v436, 3, 7, 2, 4, 8, 12, 5) :|: v458 < v417 && 3 <= v417 && 12 <= v440 f_537(v416, v417, v418, v419, v420, v421, v422, v458, 1, v423, v449, v451, v430, v453, v455, v431, v437, v432, v438, v433, v439, v440, v441, v442, v443, v444, v445, v427, v429, 0, v446, v448, v434, v435, v436, 3, 7, 2, 4, 8, 12, 5) -> f_539(v416, v417, v418, v419, v420, v421, v422, v458, 1, v423, v449, v451, v430, v453, v455, v431, v437, v432, v438, v433, v439, v440, v441, v442, v443, v444, v445, v427, v429, 0, v446, v448, v434, v435, v436, 3, 7, 2, 4, 8, 12, 5) :|: 0 = 0 f_539(v416, v417, v418, v419, v420, v421, v422, v458, 1, v423, v449, v451, v430, v453, v455, v431, v437, v432, v438, v433, v439, v440, v441, v442, v443, v444, v445, v427, v429, 0, v446, v448, v434, v435, v436, 3, 7, 2, 4, 8, 12, 5) -> f_541(v416, v417, v418, v419, v420, v421, v422, v458, 1, v423, v449, v451, v430, v453, v455, v431, v437, v432, v438, v433, v439, v440, v441, v442, v443, v444, v445, v427, v429, 0, v446, v448, v434, v435, v436, 3, 7, 2, 4, 8, 12, 5) :|: TRUE f_541(v416, v417, v418, v419, v420, v421, v422, v458, 1, v423, v449, v451, v430, v453, v455, v431, v437, v432, v438, v433, v439, v440, v441, v442, v443, v444, v445, v427, v429, 0, v446, v448, v434, v435, v436, 3, 7, 2, 4, 8, 12, 5) -> f_514(v416, v417, v418, v419, v420, v421, v422, v458, 1, v423, v449, v451, v430, v453, v455, v431, v437, v432, v438, v433, v439, v440, v441, v442, v443, v444, v445, 0, v446, v448, v434, v435, v436, 3, 7, 2, 4, 8) :|: TRUE f_514(v416, v417, v418, v419, v420, v421, v422, v423, 1, v425, v426, v427, v428, v429, v430, v431, v437, v432, v438, v433, v439, v440, v441, v442, v443, v444, v445, 0, v446, v448, v434, v435, v436, 3, 7, 2, 4, 8) -> f_515(v416, v417, v418, v419, v420, v421, v422, v423, 1, v425, v426, v427, v428, v429, v430, v431, v437, v432, v438, v433, v439, v440, v441, v442, v443, v444, v445, 0, v446, v448, v434, v435, v436, 3, 7, 2, 4, 8) :|: 0 = 0 Combined rules. Obtained 1 rulesP rules: f_515(v416:0, v417:0, v418:0, v419:0, v420:0, v421:0, v422:0, v423:0, 1, v425:0, v426:0, v427:0, v428:0, v429:0, v430:0, v431:0, v437:0, v432:0, v438:0, v433:0, v439:0, v440:0, v441:0, v442:0, v443:0, v444:0, v445:0, 0, v446:0, v448:0, v434:0, v435:0, v436:0, 3, 7, 2, 4, 8) -> f_515(v416:0, v417:0, v418:0, v419:0, v420:0, v421:0, v422:0, 1 + v423:0, 1, v423:0, v416:0 + 4 * v423:0, 2 + (v416:0 + 4 * v423:0), v430:0, v453:0, v430:0 + v453:0, v431:0, v437:0, v432:0, v438:0, v433:0, v439:0, v440:0, v441:0, v442:0, v443:0, v444:0, v445:0, 0, v446:0, v448:0, v434:0, v435:0, v436:0, 3, 7, 2, 4, 8) :|: v416:0 + 4 * v423:0 > 4 && v423:0 > 0 && v417:0 > 2 && v440:0 > 11 && v417:0 > 1 + v423:0 Filtered unneeded arguments: f_515(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18, x19, x20, x21, x22, x23, x24, x25, x26, x27, x28, x29, x30, x31, x32, x33, x34, x35, x36, x37, x38) -> f_515(x1, x2, x8, x22) Removed division, modulo operations, cleaned up constraints. Obtained 1 rules.P rules: f_515(v416:0, v417:0, v423:0, v440:0) -> f_515(v416:0, v417:0, 1 + v423:0, v440:0) :|: v423:0 > 0 && v416:0 + 4 * v423:0 > 4 && v417:0 > 2 && v417:0 > 1 + v423:0 && v440:0 > 11 ---------------------------------------- (8) Obligation: Rules: f_515(v416:0, v417:0, v423:0, v440:0) -> f_515(v416:0, v417:0, 1 + v423:0, v440:0) :|: v423:0 > 0 && v416:0 + 4 * v423:0 > 4 && v417:0 > 2 && v417:0 > 1 + v423:0 && v440:0 > 11 ---------------------------------------- (9) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (10) Obligation: Rules: f_515(v416:0:0, v417:0:0, v423:0:0, v440:0:0) -> f_515(v416:0:0, v417:0:0, 1 + v423:0:0, v440:0:0) :|: v417:0:0 > 1 + v423:0:0 && v440:0:0 > 11 && v417:0:0 > 2 && v416:0:0 + 4 * v423:0:0 > 4 && v423:0:0 > 0 ---------------------------------------- (11) PolynomialOrderProcessor (EQUIVALENT) Found the following polynomial interpretation: [f_515(x, x1, x2, x3)] = -2 + x1 - x2 The following rules are decreasing: f_515(v416:0:0, v417:0:0, v423:0:0, v440:0:0) -> f_515(v416:0:0, v417:0:0, 1 + v423:0:0, v440:0:0) :|: v417:0:0 > 1 + v423:0:0 && v440:0:0 > 11 && v417:0:0 > 2 && v416:0:0 + 4 * v423:0:0 > 4 && v423:0:0 > 0 The following rules are bounded: f_515(v416:0:0, v417:0:0, v423:0:0, v440:0:0) -> f_515(v416:0:0, v417:0:0, 1 + v423:0:0, v440:0:0) :|: v417:0:0 > 1 + v423:0:0 && v440:0:0 > 11 && v417:0:0 > 2 && v416:0:0 + 4 * v423:0:0 > 4 && v423:0:0 > 0 ---------------------------------------- (12) YES