YES proof of /export/starexec/sandbox2/benchmark/theBenchmark.c # AProVE Commit ID: 794c25de1cacf0d048858bcd21c9a779e1221865 marcel 20200619 unpublished dirty Termination of the given C Problem could be proven: (0) C Problem (1) CToLLVMProof [EQUIVALENT, 156 ms] (2) LLVM problem (3) LLVMToTerminationGraphProof [EQUIVALENT, 656 ms] (4) LLVM Symbolic Execution Graph (5) SymbolicExecutionGraphToSCCProof [SOUND, 0 ms] (6) LLVM Symbolic Execution SCC (7) SCC2IRS [SOUND, 2 ms] (8) IntTRS (9) IntTRSCompressionProof [EQUIVALENT, 0 ms] (10) IntTRS (11) RankingReductionPairProof [EQUIVALENT, 8 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: "main" linkageType: EXTERNALLY_VISIBLE returnParam: i32 parameters: () variableLength: false visibilityType: DEFAULT callingConvention: ccc 0: %1 = alloca i32, align 4 %x = alloca i32, align 4 %M = alloca i32, align 4 store 0, %1 %2 = call i32 @__VERIFIER_nondet_int() store %2, %x %3 = call i32 @__VERIFIER_nondet_int() store %3, %M %4 = load %M %5 = icmp sgt %4 0 br %5, %6, %21 6: br %7 7: %8 = load %x %9 = load %M %10 = icmp ne %8 %9 br %10, %11, %20 11: %12 = load %x %13 = load %M %14 = icmp sgt %12 %13 br %14, %15, %16 15: store 0, %x br %19 16: %17 = load %x %18 = add %17 1 store %18, %x br %19 19: br %7 20: br %21 21: ret 0 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 16 rulesP rules: f_180(v103, v104, v105, v106, v107, 1, v111, v109, 0, v112, v113, v114, 3, 4) -> f_181(v103, v104, v105, v106, v107, 1, v111, v109, 0, v112, v113, v114, 3, 4) :|: 0 = 0 f_181(v103, v104, v105, v106, v107, 1, v111, v109, 0, v112, v113, v114, 3, 4) -> f_182(v103, v104, v105, v106, v107, 1, v111, v109, 0, v112, v113, v114, 3, 4) :|: v111 != v107 f_182(v103, v104, v105, v106, v107, 1, v111, v109, 0, v112, v113, v114, 3, 4) -> f_184(v103, v104, v105, v106, v107, 1, v111, v109, 0, v112, v113, v114, 3, 4) :|: 0 = 0 f_184(v103, v104, v105, v106, v107, 1, v111, v109, 0, v112, v113, v114, 3, 4) -> f_186(v103, v104, v105, v106, v107, 1, v111, v109, 0, v112, v113, v114, 3, 4) :|: TRUE f_186(v103, v104, v105, v106, v107, 1, v111, v109, 0, v112, v113, v114, 3, 4) -> f_188(v103, v104, v105, v106, v107, 1, v111, 0, v109, v112, v113, v114, 3, 4) :|: 0 = 0 f_188(v103, v104, v105, v106, v107, 1, v111, 0, v109, v112, v113, v114, 3, 4) -> f_190(v103, v104, v105, v106, v107, 1, v111, 0, v109, v112, v113, v114, 3, 4) :|: 0 = 0 f_190(v103, v104, v105, v106, v107, 1, v111, 0, v109, v112, v113, v114, 3, 4) -> f_191(v103, v104, v105, v106, v107, 1, v111, 0, v109, v112, v113, v114, 3, 4) :|: 0 = 0 f_191(v103, v104, v105, v106, v107, 1, v111, 0, v109, v112, v113, v114, 3, 4) -> f_192(v103, v104, v105, v106, v107, 1, v111, 0, v109, v112, v113, v114, 3, 4) :|: TRUE f_192(v103, v104, v105, v106, v107, 1, v111, 0, v109, v112, v113, v114, 3, 4) -> f_193(v103, v104, v105, v106, v107, 1, v111, 0, v112, v113, v114, 3, 4) :|: 0 = 0 f_193(v103, v104, v105, v106, v107, 1, v111, 0, v112, v113, v114, 3, 4) -> f_194(v103, v104, v105, v106, v107, 1, v111, 0, v124, v112, v113, v114, 3, 4) :|: v124 = 1 + v111 f_194(v103, v104, v105, v106, v107, 1, v111, 0, v124, v112, v113, v114, 3, 4) -> f_195(v103, v104, v105, v106, v107, 1, v111, 0, v124, v112, v113, v114, 3, 4) :|: TRUE f_195(v103, v104, v105, v106, v107, 1, v111, 0, v124, v112, v113, v114, 3, 4) -> f_196(v103, v104, v105, v106, v107, 1, v111, 0, v124, v112, v113, v114, 3, 4) :|: TRUE f_196(v103, v104, v105, v106, v107, 1, v111, 0, v124, v112, v113, v114, 3, 4) -> f_197(v103, v104, v105, v106, v107, 1, v111, 0, v124, v112, v113, v114, 3, 4) :|: v111 < v107 && 1 <= v103 && 1 <= v104 && 1 <= v105 && 1 <= v107 && 4 <= v112 && 4 <= v113 && 4 <= v114 && v103 <= v112 && v104 <= v113 && v105 <= v114 f_197(v138, v139, v140, v141, v142, 1, v144, 0, v146, v147, v148, v149, 3, 4) -> f_198(v138, v139, v140, v141, v142, 1, v144, 0, v146, v147, v148, v149, 3, 4) :|: TRUE f_198(v138, v139, v140, v141, v142, 1, v144, 0, v146, v147, v148, v149, 3, 4) -> f_179(v138, v139, v140, v141, v142, 1, v144, 0, v146, v147, v148, v149, 3, 4) :|: v144 < v142 && 1 <= v138 && 1 <= v139 && 1 <= v140 && 1 <= v142 && 4 <= v147 && 4 <= v148 && 4 <= v149 && v138 <= v147 && v139 <= v148 && v140 <= v149 f_179(v103, v104, v105, v106, v107, 1, v109, 0, v111, v112, v113, v114, 3, 4) -> f_180(v103, v104, v105, v106, v107, 1, v111, v109, 0, v112, v113, v114, 3, 4) :|: 0 = 0 Combined rules. Obtained 1 rulesP rules: f_180(v103:0, v104:0, v105:0, v106:0, v107:0, 1, v111:0, v109:0, 0, v112:0, v113:0, v114:0, 3, 4) -> f_180(v103:0, v104:0, v105:0, v106:0, v107:0, 1, 1 + v111:0, v111:0, 0, v112:0, v113:0, v114:0, 3, 4) :|: v111:0 < v107:0 && v103:0 > 0 && v104:0 > 0 && v105:0 > 0 && v107:0 > 0 && v112:0 > 3 && v113:0 > 3 && v114:0 > 3 && v112:0 >= v103:0 && v113:0 >= v104:0 && v114:0 >= v105:0 Filtered unneeded arguments: f_180(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14) -> f_180(x1, x2, x3, x5, x7, x10, x11, x12) Removed division, modulo operations, cleaned up constraints. Obtained 1 rules.P rules: f_180(v103:0, v104:0, v105:0, v107:0, v111:0, v112:0, v113:0, v114:0) -> f_180(v103:0, v104:0, v105:0, v107:0, 1 + v111:0, v112:0, v113:0, v114:0) :|: v103:0 > 0 && v111:0 < v107:0 && v104:0 > 0 && v105:0 > 0 && v107:0 > 0 && v112:0 > 3 && v113:0 > 3 && v114:0 > 3 && v112:0 >= v103:0 && v114:0 >= v105:0 && v113:0 >= v104:0 ---------------------------------------- (8) Obligation: Rules: f_180(v103:0, v104:0, v105:0, v107:0, v111:0, v112:0, v113:0, v114:0) -> f_180(v103:0, v104:0, v105:0, v107:0, 1 + v111:0, v112:0, v113:0, v114:0) :|: v103:0 > 0 && v111:0 < v107:0 && v104:0 > 0 && v105:0 > 0 && v107:0 > 0 && v112:0 > 3 && v113:0 > 3 && v114:0 > 3 && v112:0 >= v103:0 && v114:0 >= v105:0 && v113:0 >= v104:0 ---------------------------------------- (9) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (10) Obligation: Rules: f_180(v103:0:0, v104:0:0, v105:0:0, v107:0:0, v111:0:0, v112:0:0, v113:0:0, v114:0:0) -> f_180(v103:0:0, v104:0:0, v105:0:0, v107:0:0, 1 + v111:0:0, v112:0:0, v113:0:0, v114:0:0) :|: v114:0:0 >= v105:0:0 && v113:0:0 >= v104:0:0 && v112:0:0 >= v103:0:0 && v114:0:0 > 3 && v113:0:0 > 3 && v112:0:0 > 3 && v107:0:0 > 0 && v105:0:0 > 0 && v104:0:0 > 0 && v111:0:0 < v107:0:0 && v103:0:0 > 0 ---------------------------------------- (11) RankingReductionPairProof (EQUIVALENT) Interpretation: [ f_180 ] = f_180_4 + -1*f_180_5 The following rules are decreasing: f_180(v103:0:0, v104:0:0, v105:0:0, v107:0:0, v111:0:0, v112:0:0, v113:0:0, v114:0:0) -> f_180(v103:0:0, v104:0:0, v105:0:0, v107:0:0, 1 + v111:0:0, v112:0:0, v113:0:0, v114:0:0) :|: v114:0:0 >= v105:0:0 && v113:0:0 >= v104:0:0 && v112:0:0 >= v103:0:0 && v114:0:0 > 3 && v113:0:0 > 3 && v112:0:0 > 3 && v107:0:0 > 0 && v105:0:0 > 0 && v104:0:0 > 0 && v111:0:0 < v107:0:0 && v103:0:0 > 0 The following rules are bounded: f_180(v103:0:0, v104:0:0, v105:0:0, v107:0:0, v111:0:0, v112:0:0, v113:0:0, v114:0:0) -> f_180(v103:0:0, v104:0:0, v105:0:0, v107:0:0, 1 + v111:0:0, v112:0:0, v113:0:0, v114:0:0) :|: v114:0:0 >= v105:0:0 && v113:0:0 >= v104:0:0 && v112:0:0 >= v103:0:0 && v114:0:0 > 3 && v113:0:0 > 3 && v112:0:0 > 3 && v107:0:0 > 0 && v105:0:0 > 0 && v104:0:0 > 0 && v111:0:0 < v107:0:0 && v103:0:0 > 0 ---------------------------------------- (12) YES