19.16/6.22 YES 19.16/6.23 proof of /export/starexec/sandbox/benchmark/theBenchmark.c 19.16/6.23 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 19.16/6.23 19.16/6.23 19.16/6.23 Termination of the given C Problem could be proven: 19.16/6.23 19.16/6.23 (0) C Problem 19.16/6.23 (1) CToLLVMProof [EQUIVALENT, 171 ms] 19.16/6.23 (2) LLVM problem 19.16/6.23 (3) LLVMToTerminationGraphProof [EQUIVALENT, 2737 ms] 19.16/6.23 (4) LLVM Symbolic Execution Graph 19.16/6.23 (5) SymbolicExecutionGraphToSCCProof [SOUND, 0 ms] 19.16/6.23 (6) LLVM Symbolic Execution SCC 19.16/6.23 (7) SCC2IRS [SOUND, 95 ms] 19.16/6.23 (8) IntTRS 19.16/6.23 (9) IntTRSCompressionProof [EQUIVALENT, 0 ms] 19.16/6.23 (10) IntTRS 19.16/6.23 (11) PolynomialOrderProcessor [EQUIVALENT, 7 ms] 19.16/6.23 (12) IntTRS 19.16/6.23 (13) IntTRSCompressionProof [EQUIVALENT, 0 ms] 19.16/6.23 (14) IntTRS 19.16/6.23 (15) RankingReductionPairProof [EQUIVALENT, 4 ms] 19.16/6.23 (16) YES 19.16/6.23 19.16/6.23 19.16/6.23 ---------------------------------------- 19.16/6.23 19.16/6.23 (0) 19.16/6.23 Obligation: 19.16/6.23 c file /export/starexec/sandbox/benchmark/theBenchmark.c 19.16/6.23 ---------------------------------------- 19.16/6.23 19.16/6.23 (1) CToLLVMProof (EQUIVALENT) 19.16/6.23 Compiled c-file /export/starexec/sandbox/benchmark/theBenchmark.c to LLVM. 19.16/6.23 ---------------------------------------- 19.16/6.23 19.16/6.23 (2) 19.16/6.23 Obligation: 19.16/6.23 LLVM Problem 19.16/6.23 19.16/6.23 Aliases: 19.16/6.23 19.16/6.23 Data layout: 19.16/6.23 19.16/6.23 "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" 19.16/6.23 19.16/6.23 Machine: 19.16/6.23 19.16/6.23 "x86_64-pc-linux-gnu" 19.16/6.23 19.16/6.23 Type definitions: 19.16/6.23 19.16/6.23 Global variables: 19.16/6.23 19.16/6.23 Function declarations and definitions: 19.16/6.23 19.16/6.23 *BasicFunctionTypename: "__VERIFIER_nondet_int" returnParam: i32 parameters: () variableLength: false visibilityType: DEFAULT callingConvention: ccc 19.16/6.23 *BasicFunctionTypename: "mult" linkageType: EXTERNALLY_VISIBLE returnParam: i32 parameters: (n i32, m i32) variableLength: false visibilityType: DEFAULT callingConvention: ccc 19.16/6.23 0: 19.16/6.23 %1 = alloca i32, align 4 19.16/6.23 %2 = alloca i32, align 4 19.16/6.23 %3 = alloca i32, align 4 19.16/6.23 store %n, %2 19.16/6.23 store %m, %3 19.16/6.23 %4 = load %3 19.16/6.23 %5 = icmp slt %4 0 19.16/6.23 br %5, %6, %12 19.16/6.23 6: 19.16/6.23 %7 = load %2 19.16/6.23 %8 = load %3 19.16/6.23 %9 = sub 0 %8 19.16/6.23 %10 = call i32 @mult(i32 %7, i32 %9) 19.16/6.23 %11 = mul -1 %10 19.16/6.23 store %11, %1 19.16/6.23 br %23 19.16/6.23 12: 19.16/6.23 %13 = load %3 19.16/6.23 %14 = icmp eq %13 0 19.16/6.23 br %14, %15, %16 19.16/6.23 15: 19.16/6.23 store 0, %1 19.16/6.23 br %23 19.16/6.23 16: 19.16/6.23 %17 = load %2 19.16/6.23 %18 = load %2 19.16/6.23 %19 = load %3 19.16/6.23 %20 = sub %19 1 19.16/6.23 %21 = call i32 @mult(i32 %18, i32 %20) 19.16/6.23 %22 = add %17 %21 19.16/6.23 store %22, %1 19.16/6.23 br %23 19.16/6.23 23: 19.16/6.23 %24 = load %1 19.16/6.23 ret %24 19.16/6.23 19.16/6.23 *BasicFunctionTypename: "main" linkageType: EXTERNALLY_VISIBLE returnParam: i32 parameters: () variableLength: false visibilityType: DEFAULT callingConvention: ccc 19.16/6.23 0: 19.16/6.23 %1 = alloca i32, align 4 19.16/6.23 %m = alloca i32, align 4 19.16/6.23 %n = alloca i32, align 4 19.16/6.23 %res = alloca i32, align 4 19.16/6.23 store 0, %1 19.16/6.23 %2 = call i32 @__VERIFIER_nondet_int() 19.16/6.23 store %2, %m 19.16/6.23 %3 = call i32 @__VERIFIER_nondet_int() 19.16/6.23 store %3, %n 19.16/6.23 %4 = load %m 19.16/6.23 %5 = load %n 19.16/6.23 %6 = call i32 @mult(i32 %4, i32 %5) 19.16/6.23 store %6, %res 19.16/6.23 ret 0 19.16/6.23 19.16/6.23 19.16/6.23 Analyze Termination of all function calls matching the pattern: 19.16/6.23 main() 19.16/6.23 ---------------------------------------- 19.16/6.23 19.16/6.23 (3) LLVMToTerminationGraphProof (EQUIVALENT) 19.16/6.23 Constructed symbolic execution graph for LLVM program and proved memory safety. 19.16/6.23 ---------------------------------------- 19.16/6.23 19.16/6.23 (4) 19.16/6.23 Obligation: 19.16/6.23 SE Graph 19.16/6.23 ---------------------------------------- 19.16/6.23 19.16/6.23 (5) SymbolicExecutionGraphToSCCProof (SOUND) 19.16/6.23 Splitted symbolic execution graph to 1 SCC. 19.16/6.23 ---------------------------------------- 19.16/6.23 19.16/6.23 (6) 19.16/6.23 Obligation: 19.16/6.23 SCC 19.16/6.23 ---------------------------------------- 19.16/6.23 19.16/6.23 (7) SCC2IRS (SOUND) 19.16/6.23 Transformed LLVM symbolic execution graph SCC into a rewrite problem. Log: 19.16/6.23 Generated rules. Obtained 29 rulesP rules: 19.16/6.23 f_179(v22, v23, v34, v24, v25, v26, v27, v28, v29, v30, v31, v35, 0, v33, 3, 1, 4) -> f_180(v22, v23, v34, v36, v24, v25, v26, v27, v28, v29, v30, v31, v35, v37, 0, v33, 3, 1, 4) :|: 1 <= v36 && v37 = 3 + v36 && 4 <= v37 19.16/6.23 f_180(v22, v23, v34, v36, v24, v25, v26, v27, v28, v29, v30, v31, v35, v37, 0, v33, 3, 1, 4) -> f_181(v22, v23, v34, v36, v38, v24, v25, v26, v27, v28, v29, v30, v31, v35, v37, v39, 0, v33, 3, 1, 4) :|: 1 <= v38 && v39 = 3 + v38 && 4 <= v39 19.16/6.23 f_181(v22, v23, v34, v36, v38, v24, v25, v26, v27, v28, v29, v30, v31, v35, v37, v39, 0, v33, 3, 1, 4) -> f_182(v22, v23, v34, v36, v38, v24, v25, v26, v27, v28, v29, v30, v31, v35, v37, v39, 0, v33, 3, 1, 4) :|: TRUE 19.16/6.23 f_182(v22, v23, v34, v36, v38, v24, v25, v26, v27, v28, v29, v30, v31, v35, v37, v39, 0, v33, 3, 1, 4) -> f_183(v22, v23, v34, v36, v38, v24, v25, v26, v27, v28, v29, v30, v31, v35, v37, v39, 0, v33, 3, 1, 4) :|: TRUE 19.16/6.23 f_183(v22, v23, v34, v36, v38, v24, v25, v26, v27, v28, v29, v30, v31, v35, v37, v39, 0, v33, 3, 1, 4) -> f_184(v22, v23, v34, v36, v38, v24, v25, v26, v27, v28, v29, v30, v31, v35, v37, v39, 0, v33, 3, 1, 4) :|: 0 = 0 19.16/6.23 f_184(v22, v23, v34, v36, v38, v24, v25, v26, v27, v28, v29, v30, v31, v35, v37, v39, 0, v33, 3, 1, 4) -> f_185(v22, v23, v34, v36, v38, v24, v25, v26, v27, v28, v29, v30, v31, v35, v37, v39, 0, v33, 3, 1, 4) :|: v23 < 0 19.16/6.23 f_184(v22, v23, v34, v36, v38, v24, v25, v26, v27, v28, v29, v30, v31, v35, v37, v39, 0, v33, 3, 1, 4) -> f_186(v22, v23, v34, v36, v38, v24, v25, v26, v27, v28, v29, v30, v31, v35, v37, v39, 0, v33, 3, 1, 4) :|: 0 <= v23 19.16/6.23 f_185(v22, v23, v34, v36, v38, v24, v25, v26, v27, v28, v29, v30, v31, v35, v37, v39, 0, v33, 3, 1, 4) -> f_187(v22, v23, v34, v36, v38, 1, v24, v25, v26, v27, v28, v29, v30, v31, v35, v37, v39, 0, v33, 3, 4) :|: 0 = 0 19.16/6.23 f_187(v22, v23, v34, v36, v38, 1, v24, v25, v26, v27, v28, v29, v30, v31, v35, v37, v39, 0, v33, 3, 4) -> f_189(v22, v23, v34, v36, v38, 1, v24, v25, v26, v27, v28, v29, v30, v31, v35, v37, v39, 0, v33, 3, 4) :|: TRUE 19.16/6.23 f_189(v22, v23, v34, v36, v38, 1, v24, v25, v26, v27, v28, v29, v30, v31, v35, v37, v39, 0, v33, 3, 4) -> f_191(v22, v23, v34, v36, v38, 1, v24, v25, v26, v27, v28, v29, v30, v31, v35, v37, v39, 0, v33, 3, 4) :|: 0 = 0 19.16/6.23 f_191(v22, v23, v34, v36, v38, 1, v24, v25, v26, v27, v28, v29, v30, v31, v35, v37, v39, 0, v33, 3, 4) -> f_193(v22, v23, v34, v36, v38, 1, v24, v25, v26, v27, v28, v29, v30, v31, v35, v37, v39, 0, v33, 3, 4) :|: 0 = 0 19.16/6.23 f_193(v22, v23, v34, v36, v38, 1, v24, v25, v26, v27, v28, v29, v30, v31, v35, v37, v39, 0, v33, 3, 4) -> f_196(v22, v23, v34, v36, v38, 1, v42, v24, v25, v26, v27, v28, v29, v30, v31, v35, v37, v39, 0, v33, 3, 4) :|: v42 + v23 = 0 && 1 <= v42 19.16/6.23 f_196(v22, v23, v34, v36, v38, 1, v42, v24, v25, v26, v27, v28, v29, v30, v31, v35, v37, v39, 0, v33, 3, 4) -> f_199(v22, v42, v24, v25, v26, v27, v28, v29, v30, v31, v34, v35, v36, v37, v38, v39, 0, v33, v23, 1, 3, 4) :|: 0 = 0 19.16/6.23 f_199(v22, v42, v24, v25, v26, v27, v28, v29, v30, v31, v34, v35, v36, v37, v38, v39, 0, v33, v23, 1, 3, 4) -> f_202(v22, v42, v24, v25, v26, v27, v28, v29, v30, v31, v34, v35, v36, v37, v38, v39, 0, v33, v23, 3, 1, 4) :|: TRUE 19.16/6.23 f_202(v22, v42, v24, v25, v26, v27, v28, v29, v30, v31, v34, v35, v36, v37, v38, v39, 0, v33, v23, 3, 1, 4) -> f_176(v22, v42, v24, v25, v26, v27, v28, v29, v30, v31, 0, v33, 3, 1, 4) :|: TRUE 19.16/6.23 f_176(v22, v23, v24, v25, v26, v27, v28, v29, v30, v31, 0, v33, 3, 1, 4) -> f_179(v22, v23, v34, v24, v25, v26, v27, v28, v29, v30, v31, v35, 0, v33, 3, 1, 4) :|: 1 <= v34 && v35 = 3 + v34 && 4 <= v35 19.16/6.23 f_186(v22, v23, v34, v36, v38, v24, v25, v26, v27, v28, v29, v30, v31, v35, v37, v39, 0, v33, 3, 1, 4) -> f_188(v22, v23, v34, v36, v38, 0, v24, v25, v26, v27, v28, v29, v30, v31, v35, v37, v39, v33, 3, 1, 4) :|: 0 = 0 19.16/6.23 f_188(v22, v23, v34, v36, v38, 0, v24, v25, v26, v27, v28, v29, v30, v31, v35, v37, v39, v33, 3, 1, 4) -> f_190(v22, v23, v34, v36, v38, 0, v24, v25, v26, v27, v28, v29, v30, v31, v35, v37, v39, v33, 3, 1, 4) :|: TRUE 19.16/6.23 f_190(v22, v23, v34, v36, v38, 0, v24, v25, v26, v27, v28, v29, v30, v31, v35, v37, v39, v33, 3, 1, 4) -> f_192(v22, v23, v34, v36, v38, 0, v24, v25, v26, v27, v28, v29, v30, v31, v35, v37, v39, v33, 3, 1, 4) :|: 0 = 0 19.16/6.23 f_192(v22, v23, v34, v36, v38, 0, v24, v25, v26, v27, v28, v29, v30, v31, v35, v37, v39, v33, 3, 1, 4) -> f_195(v22, v23, v34, v36, v38, 0, v24, v25, v26, v27, v28, v29, v30, v31, v35, v37, v39, v33, 3, 1, 4) :|: v23 != 0 19.16/6.23 f_195(v22, v23, v34, v36, v38, 0, v24, v25, v26, v27, v28, v29, v30, v31, v35, v37, v39, v33, 3, 1, 4) -> f_198(v22, v23, v34, v36, v38, 0, v24, v25, v26, v27, v28, v29, v30, v31, v35, v37, v39, v33, 3, 1, 4) :|: 0 = 0 19.16/6.23 f_198(v22, v23, v34, v36, v38, 0, v24, v25, v26, v27, v28, v29, v30, v31, v35, v37, v39, v33, 3, 1, 4) -> f_201(v22, v23, v34, v36, v38, 0, v24, v25, v26, v27, v28, v29, v30, v31, v35, v37, v39, v33, 3, 1, 4) :|: TRUE 19.16/6.23 f_201(v22, v23, v34, v36, v38, 0, v24, v25, v26, v27, v28, v29, v30, v31, v35, v37, v39, v33, 3, 1, 4) -> f_204(v22, v23, v34, v36, v38, 0, v24, v25, v26, v27, v28, v29, v30, v31, v35, v37, v39, v33, 3, 1, 4) :|: 0 = 0 19.16/6.23 f_204(v22, v23, v34, v36, v38, 0, v24, v25, v26, v27, v28, v29, v30, v31, v35, v37, v39, v33, 3, 1, 4) -> f_206(v22, v23, v34, v36, v38, 0, v24, v25, v26, v27, v28, v29, v30, v31, v35, v37, v39, v33, 3, 1, 4) :|: 0 = 0 19.16/6.23 f_206(v22, v23, v34, v36, v38, 0, v24, v25, v26, v27, v28, v29, v30, v31, v35, v37, v39, v33, 3, 1, 4) -> f_208(v22, v23, v34, v36, v38, 0, v24, v25, v26, v27, v28, v29, v30, v31, v35, v37, v39, v33, 3, 1, 4) :|: 0 = 0 19.16/6.23 f_208(v22, v23, v34, v36, v38, 0, v24, v25, v26, v27, v28, v29, v30, v31, v35, v37, v39, v33, 3, 1, 4) -> f_211(v22, v23, v34, v36, v38, 0, v87, v24, v25, v26, v27, v28, v29, v30, v31, v35, v37, v39, v33, 3, 1, 4) :|: 1 + v87 = v23 && 0 <= v87 19.16/6.23 f_211(v22, v23, v34, v36, v38, 0, v87, v24, v25, v26, v27, v28, v29, v30, v31, v35, v37, v39, v33, 3, 1, 4) -> f_213(v22, v87, v24, v25, v26, v27, v28, v29, v30, v31, v34, v35, v36, v37, v38, v39, 0, v33, v23, 3, 1, 4) :|: 0 = 0 19.16/6.23 f_213(v22, v87, v24, v25, v26, v27, v28, v29, v30, v31, v34, v35, v36, v37, v38, v39, 0, v33, v23, 3, 1, 4) -> f_215(v22, v87, v24, v25, v26, v27, v28, v29, v30, v31, v34, v35, v36, v37, v38, v39, 0, v33, v23, 3, 1, 4) :|: TRUE 19.16/6.23 f_215(v22, v87, v24, v25, v26, v27, v28, v29, v30, v31, v34, v35, v36, v37, v38, v39, 0, v33, v23, 3, 1, 4) -> f_176(v22, v87, v24, v25, v26, v27, v28, v29, v30, v31, 0, v33, 3, 1, 4) :|: TRUE 19.16/6.23 Combined rules. Obtained 2 rulesP rules: 19.16/6.23 f_179(v22:0, 1 + v87:0, v34:0, v24:0, v25:0, v26:0, v27:0, v28:0, v29:0, v30:0, v31:0, v35:0, 0, v33:0, 3, 1, 4) -> f_179(v22:0, v87:0, v34:1, v24:0, v25:0, v26:0, v27:0, v28:0, v29:0, v30:0, v31:0, 3 + v34:1, 0, v33:0, 3, 1, 4) :|: v87:0 > -1 && v38:0 > 0 && v36:0 > 0 && v34:1 > 0 19.16/6.23 f_179(v22:0, v23:0, v34:0, v24:0, v25:0, v26:0, v27:0, v28:0, v29:0, v30:0, v31:0, v35:0, 0, v33:0, 3, 1, 4) -> f_179(v22:0, v42:0, v34:1, v24:0, v25:0, v26:0, v27:0, v28:0, v29:0, v30:0, v31:0, 3 + v34:1, 0, v33:0, 3, 1, 4) :|: v38:0 > 0 && v36:0 > 0 && v23:0 < 0 && v42:0 > 0 && v42:0 + v23:0 = 0 && v34:1 > 0 19.16/6.23 Filtered unneeded arguments: 19.16/6.23 f_179(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17) -> f_179(x2) 19.16/6.23 Removed division, modulo operations, cleaned up constraints. Obtained 2 rules.P rules: 19.16/6.23 f_179(sum~cons_1~v87:0) -> f_179(v87:0) :|: v87:0 > -1 && sum~cons_1~v87:0 = 1 + v87:0 19.16/6.23 f_179(v23:0) -> f_179(v42:0) :|: v42:0 > 0 && v42:0 + v23:0 = 0 && v23:0 < 0 19.16/6.23 19.16/6.23 ---------------------------------------- 19.16/6.23 19.16/6.23 (8) 19.16/6.23 Obligation: 19.16/6.23 Rules: 19.16/6.23 f_179(sum~cons_1~v87:0) -> f_179(v87:0) :|: v87:0 > -1 && sum~cons_1~v87:0 = 1 + v87:0 19.16/6.23 f_179(v23:0) -> f_179(v42:0) :|: v42:0 > 0 && v42:0 + v23:0 = 0 && v23:0 < 0 19.16/6.23 19.16/6.23 ---------------------------------------- 19.16/6.23 19.16/6.23 (9) IntTRSCompressionProof (EQUIVALENT) 19.16/6.23 Compressed rules. 19.16/6.23 ---------------------------------------- 19.16/6.23 19.16/6.23 (10) 19.16/6.23 Obligation: 19.16/6.23 Rules: 19.16/6.23 f_179(v23:0:0) -> f_179(v42:0:0) :|: v42:0:0 > 0 && v42:0:0 + v23:0:0 = 0 && v23:0:0 < 0 19.16/6.23 f_179(sum~cons_1~v87:0:0) -> f_179(v87:0:0) :|: v87:0:0 > -1 && sum~cons_1~v87:0:0 = 1 + v87:0:0 19.16/6.23 19.16/6.23 ---------------------------------------- 19.16/6.23 19.16/6.23 (11) PolynomialOrderProcessor (EQUIVALENT) 19.16/6.23 Found the following polynomial interpretation: 19.16/6.23 [f_179(x)] = -x + x^2 19.16/6.23 19.16/6.23 The following rules are decreasing: 19.16/6.23 f_179(v23:0:0) -> f_179(v42:0:0) :|: v42:0:0 > 0 && v42:0:0 + v23:0:0 = 0 && v23:0:0 < 0 19.16/6.23 The following rules are bounded: 19.16/6.23 f_179(v23:0:0) -> f_179(v42:0:0) :|: v42:0:0 > 0 && v42:0:0 + v23:0:0 = 0 && v23:0:0 < 0 19.16/6.23 f_179(sum~cons_1~v87:0:0) -> f_179(v87:0:0) :|: v87:0:0 > -1 && sum~cons_1~v87:0:0 = 1 + v87:0:0 19.16/6.23 19.16/6.23 ---------------------------------------- 19.16/6.23 19.16/6.23 (12) 19.16/6.23 Obligation: 19.16/6.23 Rules: 19.16/6.23 f_179(sum~cons_1~v87:0:0) -> f_179(v87:0:0) :|: v87:0:0 > -1 && sum~cons_1~v87:0:0 = 1 + v87:0:0 19.16/6.23 19.16/6.23 ---------------------------------------- 19.16/6.23 19.16/6.23 (13) IntTRSCompressionProof (EQUIVALENT) 19.16/6.23 Compressed rules. 19.16/6.23 ---------------------------------------- 19.16/6.23 19.16/6.23 (14) 19.16/6.23 Obligation: 19.16/6.23 Rules: 19.16/6.23 f_179(sum~cons_1~v87:0:0:0) -> f_179(v87:0:0:0) :|: v87:0:0:0 > -1 && sum~cons_1~v87:0:0:0 = 1 + v87:0:0:0 19.16/6.23 19.16/6.23 ---------------------------------------- 19.16/6.23 19.16/6.23 (15) RankingReductionPairProof (EQUIVALENT) 19.16/6.23 Interpretation: 19.16/6.23 [ f_179 ] = f_179_1 19.16/6.23 19.16/6.23 The following rules are decreasing: 19.16/6.23 f_179(sum~cons_1~v87:0:0:0) -> f_179(v87:0:0:0) :|: v87:0:0:0 > -1 && sum~cons_1~v87:0:0:0 = 1 + v87:0:0:0 19.16/6.23 19.16/6.23 The following rules are bounded: 19.16/6.23 f_179(sum~cons_1~v87:0:0:0) -> f_179(v87:0:0:0) :|: v87:0:0:0 > -1 && sum~cons_1~v87:0:0:0 = 1 + v87:0:0:0 19.16/6.23 19.16/6.23 19.16/6.23 ---------------------------------------- 19.16/6.23 19.16/6.23 (16) 19.16/6.23 YES 19.30/6.29 EOF