9.45/3.23 YES 9.70/3.29 proof of /export/starexec/sandbox/benchmark/theBenchmark.c 9.70/3.29 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 9.70/3.29 9.70/3.29 9.70/3.29 Termination of the given C Problem could be proven: 9.70/3.29 9.70/3.29 (0) C Problem 9.70/3.29 (1) CToLLVMProof [EQUIVALENT, 151 ms] 9.70/3.29 (2) LLVM problem 9.70/3.29 (3) LLVMToTerminationGraphProof [EQUIVALENT, 422 ms] 9.70/3.29 (4) LLVM Symbolic Execution Graph 9.70/3.29 (5) SymbolicExecutionGraphToSCCProof [SOUND, 1 ms] 9.70/3.29 (6) LLVM Symbolic Execution SCC 9.70/3.29 (7) SCC2IRS [SOUND, 0 ms] 9.70/3.29 (8) IntTRS 9.70/3.29 (9) IntTRSCompressionProof [EQUIVALENT, 0 ms] 9.70/3.29 (10) IntTRS 9.70/3.29 (11) RankingReductionPairProof [EQUIVALENT, 0 ms] 9.70/3.29 (12) YES 9.70/3.29 9.70/3.29 9.70/3.29 ---------------------------------------- 9.70/3.29 9.70/3.29 (0) 9.70/3.29 Obligation: 9.70/3.29 c file /export/starexec/sandbox/benchmark/theBenchmark.c 9.70/3.29 ---------------------------------------- 9.70/3.29 9.70/3.29 (1) CToLLVMProof (EQUIVALENT) 9.70/3.29 Compiled c-file /export/starexec/sandbox/benchmark/theBenchmark.c to LLVM. 9.70/3.29 ---------------------------------------- 9.70/3.29 9.70/3.29 (2) 9.70/3.29 Obligation: 9.70/3.29 LLVM Problem 9.70/3.29 9.70/3.29 Aliases: 9.70/3.29 9.70/3.29 Data layout: 9.70/3.29 9.70/3.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" 9.70/3.29 9.70/3.29 Machine: 9.70/3.29 9.70/3.29 "x86_64-pc-linux-gnu" 9.70/3.29 9.70/3.29 Type definitions: 9.70/3.29 9.70/3.29 Global variables: 9.70/3.29 9.70/3.29 Function declarations and definitions: 9.70/3.29 9.70/3.29 *BasicFunctionTypename: "__VERIFIER_nondet_int" returnParam: i32 parameters: () variableLength: false visibilityType: DEFAULT callingConvention: ccc 9.70/3.29 *BasicFunctionTypename: "main" linkageType: EXTERNALLY_VISIBLE returnParam: i32 parameters: () variableLength: false visibilityType: DEFAULT callingConvention: ccc 9.70/3.29 0: 9.70/3.29 %1 = alloca i32, align 4 9.70/3.29 %x = alloca i32, align 4 9.70/3.29 store 0, %1 9.70/3.29 %2 = call i32 @__VERIFIER_nondet_int() 9.70/3.29 store %2, %x 9.70/3.29 %3 = load %x 9.70/3.29 %4 = icmp sgt %3 0 9.70/3.29 br %4, %5, %13 9.70/3.29 5: 9.70/3.29 br %6 9.70/3.29 6: 9.70/3.29 %7 = load %x 9.70/3.29 %8 = icmp ne %7 0 9.70/3.29 br %8, %9, %12 9.70/3.29 9: 9.70/3.29 %10 = load %x 9.70/3.29 %11 = sub %10 1 9.70/3.29 store %11, %x 9.70/3.29 br %6 9.70/3.29 12: 9.70/3.29 br %13 9.70/3.29 13: 9.70/3.29 ret 0 9.70/3.29 9.70/3.29 9.70/3.29 Analyze Termination of all function calls matching the pattern: 9.70/3.29 main() 9.70/3.29 ---------------------------------------- 9.70/3.29 9.70/3.29 (3) LLVMToTerminationGraphProof (EQUIVALENT) 9.70/3.29 Constructed symbolic execution graph for LLVM program and proved memory safety. 9.70/3.29 ---------------------------------------- 9.70/3.29 9.70/3.29 (4) 9.70/3.29 Obligation: 9.70/3.29 SE Graph 9.70/3.29 ---------------------------------------- 9.70/3.29 9.70/3.29 (5) SymbolicExecutionGraphToSCCProof (SOUND) 9.70/3.29 Splitted symbolic execution graph to 1 SCC. 9.70/3.29 ---------------------------------------- 9.70/3.29 9.70/3.29 (6) 9.70/3.29 Obligation: 9.70/3.29 SCC 9.70/3.29 ---------------------------------------- 9.70/3.29 9.70/3.29 (7) SCC2IRS (SOUND) 9.70/3.29 Transformed LLVM symbolic execution graph SCC into a rewrite problem. Log: 9.70/3.29 Generated rules. Obtained 9 rulesP rules: 9.70/3.29 f_104(v22, v23, v24, 1, v27, v26, v28, v29, 0, 3, 4) -> f_105(v22, v23, v24, 1, v27, v26, v28, v29, 0, 3, 2, 4) :|: v27 != 0 && 2 <= v26 && 2 <= v24 9.70/3.29 f_105(v22, v23, v24, 1, v27, v26, v28, v29, 0, 3, 2, 4) -> f_107(v22, v23, v24, 1, v27, v26, v28, v29, 0, 3, 2, 4) :|: 0 = 0 9.70/3.29 f_107(v22, v23, v24, 1, v27, v26, v28, v29, 0, 3, 2, 4) -> f_109(v22, v23, v24, 1, v27, v26, v28, v29, 0, 3, 2, 4) :|: TRUE 9.70/3.29 f_109(v22, v23, v24, 1, v27, v26, v28, v29, 0, 3, 2, 4) -> f_111(v22, v23, v24, 1, v27, v28, v29, 0, 3, 2, 4) :|: 0 = 0 9.70/3.29 f_111(v22, v23, v24, 1, v27, v28, v29, 0, 3, 2, 4) -> f_113(v22, v23, v24, 1, v27, v31, v28, v29, 0, 3, 2, 4) :|: 1 + v31 = v27 && 0 <= v31 9.70/3.29 f_113(v22, v23, v24, 1, v27, v31, v28, v29, 0, 3, 2, 4) -> f_114(v22, v23, v24, 1, v27, v31, v28, v29, 0, 3, 2, 4) :|: TRUE 9.70/3.29 f_114(v22, v23, v24, 1, v27, v31, v28, v29, 0, 3, 2, 4) -> f_115(v22, v23, v24, 1, v27, v31, v28, v29, 0, 3, 2, 4) :|: TRUE 9.70/3.29 f_115(v22, v23, v24, 1, v27, v31, v28, v29, 0, 3, 2, 4) -> f_103(v22, v23, v24, 1, v27, v31, v28, v29, 0, 3, 4) :|: TRUE 9.70/3.29 f_103(v22, v23, v24, 1, v26, v27, v28, v29, 0, 3, 4) -> f_104(v22, v23, v24, 1, v27, v26, v28, v29, 0, 3, 4) :|: 0 = 0 9.70/3.29 Combined rules. Obtained 1 rulesP rules: 9.70/3.29 f_104(v22:0, v23:0, v24:0, 1, 1 + v31:0, v26:0, v28:0, v29:0, 0, 3, 4) -> f_104(v22:0, v23:0, v24:0, 1, v31:0, 1 + v31:0, v28:0, v29:0, 0, 3, 4) :|: v26:0 > 1 && v31:0 > -1 && v24:0 > 1 9.70/3.29 Filtered unneeded arguments: 9.70/3.29 f_104(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11) -> f_104(x3, x5, x6) 9.70/3.29 Removed division, modulo operations, cleaned up constraints. Obtained 1 rules.P rules: 9.70/3.29 f_104(v24:0, sum~cons_1~v31:0, v26:0) -> f_104(v24:0, v31:0, 1 + v31:0) :|: v31:0 > -1 && v24:0 > 1 && v26:0 > 1 && sum~cons_1~v31:0 = 1 + v31:0 9.70/3.29 9.70/3.29 ---------------------------------------- 9.70/3.29 9.70/3.29 (8) 9.70/3.29 Obligation: 9.70/3.29 Rules: 9.70/3.29 f_104(v24:0, sum~cons_1~v31:0, v26:0) -> f_104(v24:0, v31:0, 1 + v31:0) :|: v31:0 > -1 && v24:0 > 1 && v26:0 > 1 && sum~cons_1~v31:0 = 1 + v31:0 9.70/3.29 9.70/3.29 ---------------------------------------- 9.70/3.29 9.70/3.29 (9) IntTRSCompressionProof (EQUIVALENT) 9.70/3.29 Compressed rules. 9.70/3.29 ---------------------------------------- 9.70/3.29 9.70/3.29 (10) 9.70/3.29 Obligation: 9.70/3.29 Rules: 9.70/3.29 f_104(v24:0:0, sum~cons_1~v31:0:0, v26:0:0) -> f_104(v24:0:0, v31:0:0, 1 + v31:0:0) :|: v31:0:0 > -1 && v24:0:0 > 1 && v26:0:0 > 1 && sum~cons_1~v31:0:0 = 1 + v31:0:0 9.70/3.29 9.70/3.29 ---------------------------------------- 9.70/3.29 9.70/3.29 (11) RankingReductionPairProof (EQUIVALENT) 9.70/3.29 Interpretation: 9.70/3.29 [ f_104 ] = f_104_2 9.70/3.29 9.70/3.29 The following rules are decreasing: 9.70/3.29 f_104(v24:0:0, sum~cons_1~v31:0:0, v26:0:0) -> f_104(v24:0:0, v31:0:0, 1 + v31:0:0) :|: v31:0:0 > -1 && v24:0:0 > 1 && v26:0:0 > 1 && sum~cons_1~v31:0:0 = 1 + v31:0:0 9.70/3.29 9.70/3.29 The following rules are bounded: 9.70/3.29 f_104(v24:0:0, sum~cons_1~v31:0:0, v26:0:0) -> f_104(v24:0:0, v31:0:0, 1 + v31:0:0) :|: v31:0:0 > -1 && v24:0:0 > 1 && v26:0:0 > 1 && sum~cons_1~v31:0:0 = 1 + v31:0:0 9.70/3.29 9.70/3.29 9.70/3.29 ---------------------------------------- 9.70/3.29 9.70/3.29 (12) 9.70/3.29 YES 9.70/3.37 EOF