11.73/4.13 NO 11.73/4.14 proof of /export/starexec/sandbox/benchmark/theBenchmark.c 11.73/4.14 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 11.73/4.14 11.73/4.14 11.73/4.14 Termination of the given C Problem could be disproven: 11.73/4.14 11.73/4.14 (0) C Problem 11.73/4.14 (1) CToLLVMProof [EQUIVALENT, 173 ms] 11.73/4.14 (2) LLVM problem 11.73/4.14 (3) LLVMToTerminationGraphProof [EQUIVALENT, 485 ms] 11.73/4.14 (4) LLVM Symbolic Execution Graph 11.73/4.14 (5) SymbolicExecutionGraphToLassoProof [EQUIVALENT, 0 ms] 11.73/4.14 (6) LLVM Symbolic Execution Lasso 11.73/4.14 (7) Lasso2IRS [EQUIVALENT, 47 ms] 11.73/4.14 (8) IntTRS 11.73/4.14 (9) IRS2T2 [EQUIVALENT, 0 ms] 11.73/4.14 (10) T2IntSys 11.73/4.14 (11) T2 [COMPLETE, 1222 ms] 11.73/4.14 (12) NO 11.73/4.14 11.73/4.14 11.73/4.14 ---------------------------------------- 11.73/4.14 11.73/4.14 (0) 11.73/4.14 Obligation: 11.73/4.14 c file /export/starexec/sandbox/benchmark/theBenchmark.c 11.73/4.14 ---------------------------------------- 11.73/4.14 11.73/4.14 (1) CToLLVMProof (EQUIVALENT) 11.73/4.14 Compiled c-file /export/starexec/sandbox/benchmark/theBenchmark.c to LLVM. 11.73/4.14 ---------------------------------------- 11.73/4.14 11.73/4.14 (2) 11.73/4.14 Obligation: 11.73/4.14 LLVM Problem 11.73/4.14 11.73/4.14 Aliases: 11.73/4.14 11.73/4.14 Data layout: 11.73/4.14 11.73/4.14 "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" 11.73/4.14 11.73/4.14 Machine: 11.73/4.14 11.73/4.14 "x86_64-pc-linux-gnu" 11.73/4.14 11.73/4.14 Type definitions: 11.73/4.14 11.73/4.14 Global variables: 11.73/4.14 11.73/4.14 Function declarations and definitions: 11.73/4.14 11.73/4.14 *BasicFunctionTypename: "__VERIFIER_nondet_int" returnParam: i32 parameters: () variableLength: true visibilityType: DEFAULT callingConvention: ccc 11.73/4.14 *BasicFunctionTypename: "main" linkageType: EXTERNALLY_VISIBLE returnParam: i32 parameters: () variableLength: false visibilityType: DEFAULT callingConvention: ccc 11.73/4.14 0: 11.73/4.14 %1 = alloca i32, align 4 11.73/4.14 %c = alloca i32, align 4 11.73/4.14 %x = alloca i32, align 4 11.73/4.14 store 0, %1 11.73/4.14 %2 = call i32 (...)* @__VERIFIER_nondet_int() 11.73/4.14 store %2, %c 11.73/4.14 %3 = call i32 (...)* @__VERIFIER_nondet_int() 11.73/4.14 store %3, %x 11.73/4.14 br %4 11.73/4.14 4: 11.73/4.14 %5 = load %x 11.73/4.14 %6 = icmp sge %5 0 11.73/4.14 br %6, %7, %11 11.73/4.14 7: 11.73/4.14 %8 = load %c 11.73/4.14 %9 = load %x 11.73/4.14 %10 = add %9 %8 11.73/4.14 store %10, %x 11.73/4.14 br %4 11.73/4.14 11: 11.73/4.14 %12 = load %1 11.73/4.14 ret %12 11.73/4.14 11.73/4.14 11.73/4.14 Analyze Termination of all function calls matching the pattern: 11.73/4.14 main() 11.73/4.14 ---------------------------------------- 11.73/4.14 11.73/4.14 (3) LLVMToTerminationGraphProof (EQUIVALENT) 11.73/4.14 Constructed symbolic execution graph for LLVM program and proved memory safety. 11.73/4.14 ---------------------------------------- 11.73/4.14 11.73/4.14 (4) 11.73/4.14 Obligation: 11.73/4.14 SE Graph 11.73/4.14 ---------------------------------------- 11.73/4.14 11.73/4.14 (5) SymbolicExecutionGraphToLassoProof (EQUIVALENT) 11.73/4.14 Converted SEGraph to 1 independent lasso. 11.73/4.14 ---------------------------------------- 11.73/4.14 11.73/4.14 (6) 11.73/4.14 Obligation: 11.73/4.14 Lasso 11.73/4.14 ---------------------------------------- 11.73/4.14 11.73/4.14 (7) Lasso2IRS (EQUIVALENT) 11.73/4.14 Transformed LLVM symbolic execution graph SCC into a rewrite problem. Log: 11.73/4.14 Generated rules. Obtained 29 rulesP rules: 11.73/4.14 f_97(v15, v16, v17, v18, v19, v22, 1, v20, v23, v24, v25, 0, 3, 4) -> f_98(v15, v16, v17, v18, v19, v22, 1, v20, v23, v24, v25, 0, 3, 4) :|: 0 <= v22 11.73/4.14 f_98(v15, v16, v17, v18, v19, v22, 1, v20, v23, v24, v25, 0, 3, 4) -> f_100(v15, v16, v17, v18, v19, v22, 1, v20, v23, v24, v25, 0, 3, 4) :|: 0 = 0 11.73/4.14 f_100(v15, v16, v17, v18, v19, v22, 1, v20, v23, v24, v25, 0, 3, 4) -> f_102(v15, v16, v17, v18, v19, v22, 1, v20, v23, v24, v25, 0, 3, 4) :|: TRUE 11.73/4.14 f_102(v15, v16, v17, v18, v19, v22, 1, v20, v23, v24, v25, 0, 3, 4) -> f_104(v15, v16, v17, v18, v19, v22, 1, v20, v23, v24, v25, 0, 3, 4) :|: 0 = 0 11.73/4.14 f_104(v15, v16, v17, v18, v19, v22, 1, v20, v23, v24, v25, 0, 3, 4) -> f_106(v15, v16, v17, v18, v19, v22, 1, v23, v24, v25, 0, 3, 4) :|: 0 = 0 11.73/4.14 f_106(v15, v16, v17, v18, v19, v22, 1, v23, v24, v25, 0, 3, 4) -> f_107(v15, v16, v17, v18, v19, v22, 1, v27, v23, v24, v25, 0, 3, 4) :|: v27 = v22 + v18 11.73/4.14 f_107(v15, v16, v17, v18, v19, v22, 1, v27, v23, v24, v25, 0, 3, 4) -> f_108(v15, v16, v17, v18, v19, v22, 1, v27, v23, v24, v25, 0, 3, 4) :|: TRUE 11.73/4.14 f_108(v15, v16, v17, v18, v19, v22, 1, v27, v23, v24, v25, 0, 3, 4) -> f_109(v15, v16, v17, v18, v19, v22, 1, v27, v23, v24, v25, 0, 3, 4) :|: TRUE 11.73/4.14 f_109(v15, v16, v17, v18, v19, v22, 1, v27, v23, v24, v25, 0, 3, 4) -> f_96(v15, v16, v17, v18, v19, v22, 1, v27, v23, v24, v25, 0, 3, 4) :|: TRUE 11.73/4.14 f_96(v15, v16, v17, v18, v19, v20, 1, v22, v23, v24, v25, 0, 3, 4) -> f_97(v15, v16, v17, v18, v19, v22, 1, v20, v23, v24, v25, 0, 3, 4) :|: 0 = 0 11.73/4.14 f_60 -> f_61(v1, v2, 3, 1, 4) :|: 1 <= v1 && v2 = 3 + v1 && 4 <= v2 11.73/4.14 f_61(v1, v2, 3, 1, 4) -> f_62(v1, v3, v2, v4, 3, 1, 4) :|: 1 <= v3 && v4 = 3 + v3 && 4 <= v4 11.73/4.14 f_62(v1, v3, v2, v4, 3, 1, 4) -> f_63(v1, v3, v5, v2, v4, v6, 3, 1, 4) :|: 1 <= v5 && v6 = 3 + v5 && 4 <= v6 11.73/4.14 f_63(v1, v3, v5, v2, v4, v6, 3, 1, 4) -> f_64(v1, v3, v5, v2, v4, v6, 0, 3, 1, 4) :|: TRUE 11.73/4.14 f_64(v1, v3, v5, v2, v4, v6, 0, 3, 1, 4) -> f_65(v1, v3, v5, v7, v2, v4, v6, 0, 3, 1, 4) :|: TRUE 11.73/4.14 f_65(v1, v3, v5, v7, v2, v4, v6, 0, 3, 1, 4) -> f_66(v1, v3, v5, v7, v2, v4, v6, 0, 3, 1, 4) :|: TRUE 11.73/4.14 f_66(v1, v3, v5, v7, v2, v4, v6, 0, 3, 1, 4) -> f_67(v1, v3, v5, v7, v9, v2, v4, v6, 0, 3, 1, 4) :|: TRUE 11.73/4.14 f_67(v1, v3, v5, v7, v9, v2, v4, v6, 0, 3, 1, 4) -> f_68(v1, v3, v5, v7, v9, v2, v4, v6, 0, 3, 1, 4) :|: TRUE 11.73/4.14 f_68(v1, v3, v5, v7, v9, v2, v4, v6, 0, 3, 1, 4) -> f_69(v1, v3, v5, v7, v9, v2, v4, v6, 0, 3, 1, 4) :|: TRUE 11.73/4.14 f_69(v1, v3, v5, v7, v9, v2, v4, v6, 0, 3, 1, 4) -> f_70(v1, v3, v5, v7, v9, v2, v4, v6, 0, 3, 1, 4) :|: 0 = 0 11.73/4.14 f_70(v1, v3, v5, v7, v9, v2, v4, v6, 0, 3, 1, 4) -> f_71(v1, v3, v5, v7, v9, v2, v4, v6, 0, 3, 1, 4) :|: 0 <= v9 11.73/4.14 f_71(v1, v3, v5, v7, v9, v2, v4, v6, 0, 3, 1, 4) -> f_73(v1, v3, v5, v7, v9, 1, v2, v4, v6, 0, 3, 4) :|: 0 = 0 11.73/4.14 f_73(v1, v3, v5, v7, v9, 1, v2, v4, v6, 0, 3, 4) -> f_75(v1, v3, v5, v7, v9, 1, v2, v4, v6, 0, 3, 4) :|: TRUE 11.73/4.14 f_75(v1, v3, v5, v7, v9, 1, v2, v4, v6, 0, 3, 4) -> f_77(v1, v3, v5, v7, v9, 1, v2, v4, v6, 0, 3, 4) :|: 0 = 0 11.73/4.14 f_77(v1, v3, v5, v7, v9, 1, v2, v4, v6, 0, 3, 4) -> f_79(v1, v3, v5, v7, v9, 1, v2, v4, v6, 0, 3, 4) :|: 0 = 0 11.73/4.14 f_79(v1, v3, v5, v7, v9, 1, v2, v4, v6, 0, 3, 4) -> f_80(v1, v3, v5, v7, v9, 1, v11, v2, v4, v6, 0, 3, 4) :|: v11 = v9 + v7 11.73/4.14 f_80(v1, v3, v5, v7, v9, 1, v11, v2, v4, v6, 0, 3, 4) -> f_81(v1, v3, v5, v7, v9, 1, v11, v2, v4, v6, 0, 3, 4) :|: TRUE 11.73/4.14 f_81(v1, v3, v5, v7, v9, 1, v11, v2, v4, v6, 0, 3, 4) -> f_82(v1, v3, v5, v7, v9, 1, v11, v2, v4, v6, 0, 3, 4) :|: TRUE 11.73/4.14 f_82(v1, v3, v5, v7, v9, 1, v11, v2, v4, v6, 0, 3, 4) -> f_96(v1, v3, v5, v7, v9, v9, 1, v11, v2, v4, v6, 0, 3, 4) :|: TRUE 11.73/4.14 Combined rules. Obtained 2 rulesP rules: 11.73/4.14 f_60 -> f_97(v1:0, v3:0, v5:0, v7:0, v9:0, v9:0 + v7:0, 1, v9:0, 3 + v1:0, 3 + v3:0, 3 + v5:0, 0, 3, 4) :|: v3:0 > 0 && v1:0 > 0 && v5:0 > 0 && v9:0 > -1 11.73/4.14 f_97(v15:0, v16:0, v17:0, v18:0, v19:0, v22:0, 1, v20:0, v23:0, v24:0, v25:0, 0, 3, 4) -> f_97(v15:0, v16:0, v17:0, v18:0, v19:0, v22:0 + v18:0, 1, v22:0, v23:0, v24:0, v25:0, 0, 3, 4) :|: v22:0 > -1 11.73/4.14 Filtered unneeded arguments: 11.73/4.14 f_97(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14) -> f_97(x4, x6) 11.73/4.14 Removed division, modulo operations, cleaned up constraints. Obtained 2 rules.P rules: 11.73/4.14 f_60 -> f_97(v7:0, v9:0 + v7:0) :|: v9:0 > -1 11.73/4.14 f_97(v18:0, v22:0) -> f_97(v18:0, v22:0 + v18:0) :|: v22:0 > -1 11.73/4.14 11.73/4.14 ---------------------------------------- 11.73/4.14 11.73/4.14 (8) 11.73/4.14 Obligation: 11.73/4.14 Rules: 11.73/4.14 f_60 -> f_97(v7:0, v9:0 + v7:0) :|: v9:0 > -1 11.73/4.14 f_97(v18:0, v22:0) -> f_97(v18:0, v22:0 + v18:0) :|: v22:0 > -1 11.73/4.14 Start term: f_60 11.73/4.14 11.73/4.14 ---------------------------------------- 11.73/4.14 11.73/4.14 (9) IRS2T2 (EQUIVALENT) 11.73/4.14 Transformed input IRS into an integer transition system.Used the following mapping from defined symbols to location IDs: 11.73/4.14 11.73/4.14 (f_60_2,1) 11.73/4.14 (f_97_2,2) 11.73/4.14 11.73/4.14 ---------------------------------------- 11.73/4.14 11.73/4.14 (10) 11.73/4.14 Obligation: 11.73/4.14 START: 1; 11.73/4.14 11.73/4.14 FROM: 1; 11.73/4.14 oldX0 := x0; 11.73/4.14 oldX1 := x1; 11.73/4.14 oldX2 := nondet(); 11.73/4.14 oldX3 := nondet(); 11.73/4.14 assume(oldX3 > -1); 11.73/4.14 x0 := oldX2; 11.73/4.14 x1 := oldX3 + oldX2; 11.73/4.14 TO: 2; 11.73/4.14 11.73/4.14 FROM: 2; 11.73/4.14 oldX0 := x0; 11.73/4.14 oldX1 := x1; 11.73/4.14 assume(oldX1 > -1); 11.73/4.14 x0 := oldX0; 11.73/4.14 x1 := oldX1 + oldX0; 11.73/4.14 TO: 2; 11.73/4.14 11.73/4.14 11.73/4.14 ---------------------------------------- 11.73/4.14 11.73/4.14 (11) T2 (COMPLETE) 11.73/4.14 Found this recurrent set for cutpoint 5: oldX0 == 0 and oldX2 == 0 and oldX3 == 0 and x0 == 0 and x1 == 0 11.73/4.14 11.73/4.14 ---------------------------------------- 11.73/4.14 11.73/4.14 (12) 11.73/4.14 NO 11.80/4.18 EOF