/export/starexec/sandbox/solver/bin/starexec_run_c /export/starexec/sandbox/benchmark/theBenchmark.c /export/starexec/sandbox/output/output_files -------------------------------------------------------------------------------- YES proof of /export/starexec/sandbox/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, 177 ms] (2) LLVM problem (3) LLVMToTerminationGraphProof [EQUIVALENT, 7685 ms] (4) LLVM Symbolic Execution Graph (5) SymbolicExecutionGraphToSCCProof [SOUND, 0 ms] (6) AND (7) LLVM Symbolic Execution SCC (8) SCC2IRS [SOUND, 133 ms] (9) IntTRS (10) IRS2T2 [EQUIVALENT, 0 ms] (11) T2IntSys (12) T2 [EQUIVALENT, 843 ms] (13) YES (14) LLVM Symbolic Execution SCC (15) SCC2IRS [SOUND, 84 ms] (16) IntTRS (17) IntTRSCompressionProof [EQUIVALENT, 0 ms] (18) IntTRS (19) RankingReductionPairProof [EQUIVALENT, 23 ms] (20) YES ---------------------------------------- (0) Obligation: c file /export/starexec/sandbox/benchmark/theBenchmark.c ---------------------------------------- (1) CToLLVMProof (EQUIVALENT) Compiled c-file /export/starexec/sandbox/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: "test_fun" linkageType: EXTERNALLY_VISIBLE returnParam: i32 parameters: (x i32, y i32) variableLength: false visibilityType: DEFAULT callingConvention: ccc 0: %1 = alloca i32, align 4 %2 = alloca i32, align 4 %x_ref = alloca *i32, align 8 %y_ref = alloca *i32, align 8 %c = alloca *i32, align 8 store %x, %1 store %y, %2 %3 = alloca i8, numElementsLit: 4 %4 = bitcast *i8 %3 to *i32 store %4, %x_ref %5 = alloca i8, numElementsLit: 4 %6 = bitcast *i8 %5 to *i32 store %6, %y_ref %7 = alloca i8, numElementsLit: 4 %8 = bitcast *i8 %7 to *i32 store %8, %c %9 = load %1 %10 = load %x_ref store %9, %10 %11 = load %2 %12 = load %y_ref store %11, %12 %13 = load %c store 0, %13 br %14 14: %15 = load %x_ref %16 = load %15 %17 = icmp sgt %16 0 br %17, %18, %40 18: %19 = load %y_ref store 0, %19 br %20 20: %21 = load %y_ref %22 = load %21 %23 = load %x_ref %24 = load %23 %25 = icmp slt %22 %24 br %25, %26, %35 26: %27 = load %y_ref %28 = load %27 %29 = add %28 1 %30 = load %y_ref store %29, %30 %31 = load %c %32 = load %31 %33 = add %32 1 %34 = load %c store %33, %34 br %20 35: %36 = load %x_ref %37 = load %36 %38 = sub %37 1 %39 = load %x_ref store %38, %39 br %14 40: %41 = load %c %42 = load %41 ret %42 *BasicFunctionTypename: "main" linkageType: EXTERNALLY_VISIBLE returnParam: i32 parameters: () variableLength: false visibilityType: DEFAULT callingConvention: ccc 0: %1 = alloca i32, align 4 store 0, %1 %2 = call i32 @__VERIFIER_nondet_int() %3 = call i32 @__VERIFIER_nondet_int() %4 = call i32 @test_fun(i32 %2, i32 %3) ret %4 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 2 SCCs. ---------------------------------------- (6) Complex Obligation (AND) ---------------------------------------- (7) Obligation: SCC ---------------------------------------- (8) SCC2IRS (SOUND) Transformed LLVM symbolic execution graph SCC into a rewrite problem. Log: Generated rules. Obtained 44 rulesP rules: f_661(v786, v787, v788, v789, v790, v791, v792, v793, v794, v795, v796, 1, v798, v799, v800, v801, v802, v803, v804, v805, v806, v807, v808, v809, v810, v811, v812, v813, 0, 3, 7, 2, 4, 8) -> f_662(v786, v787, v788, v789, v790, v791, v792, v793, v794, v795, v796, 1, v798, v800, v801, v802, v803, v804, v805, v806, v807, v808, v809, v810, v811, v812, v813, 0, 3, 7, 2, 4, 8) :|: 0 = 0 f_662(v786, v787, v788, v789, v790, v791, v792, v793, v794, v795, v796, 1, v798, v800, v801, v802, v803, v804, v805, v806, v807, v808, v809, v810, v811, v812, v813, 0, 3, 7, 2, 4, 8) -> f_663(v786, v787, v788, v789, v790, v791, v792, v793, v794, v795, v796, 1, v798, v815, v801, v802, v803, v804, v805, v806, v807, v808, v809, v810, v811, v812, v813, 0, 3, 7, 2, 4, 8) :|: v815 = 1 + v798 && 1 <= v815 f_663(v786, v787, v788, v789, v790, v791, v792, v793, v794, v795, v796, 1, v798, v815, v801, v802, v803, v804, v805, v806, v807, v808, v809, v810, v811, v812, v813, 0, 3, 7, 2, 4, 8) -> f_664(v786, v787, v788, v789, v790, v791, v792, v793, v794, v795, v796, 1, v798, v815, v801, v802, v803, v804, v805, v806, v807, v808, v809, v810, v811, v812, v813, 0, 3, 7, 2, 4, 8) :|: 0 = 0 f_664(v786, v787, v788, v789, v790, v791, v792, v793, v794, v795, v796, 1, v798, v815, v801, v802, v803, v804, v805, v806, v807, v808, v809, v810, v811, v812, v813, 0, 3, 7, 2, 4, 8) -> f_665(v786, v787, v788, v789, v790, v791, v792, v793, v794, v795, v796, 1, v798, v815, v801, v802, v803, v804, v805, v806, v807, v808, v809, v810, v811, v812, v813, 0, 3, 7, 2, 4, 8) :|: TRUE f_665(v786, v787, v788, v789, v790, v791, v792, v793, v794, v795, v796, 1, v798, v815, v801, v802, v803, v804, v805, v806, v807, v808, v809, v810, v811, v812, v813, 0, 3, 7, 2, 4, 8) -> f_666(v786, v787, v788, v789, v790, v791, v792, v793, v794, v795, v796, 1, v798, v815, v801, v802, v803, v804, v805, v806, v807, v808, v809, v810, v811, v812, v813, 0, 3, 7, 2, 4, 8) :|: 0 = 0 f_666(v786, v787, v788, v789, v790, v791, v792, v793, v794, v795, v796, 1, v798, v815, v801, v802, v803, v804, v805, v806, v807, v808, v809, v810, v811, v812, v813, 0, 3, 7, 2, 4, 8) -> f_667(v786, v787, v788, v789, v790, v791, v792, v793, v794, v795, v796, 1, v798, v815, v802, v803, v804, v805, v806, v807, v808, v809, v810, v811, v812, v813, 0, 3, 7, 2, 4, 8) :|: 0 = 0 f_667(v786, v787, v788, v789, v790, v791, v792, v793, v794, v795, v796, 1, v798, v815, v802, v803, v804, v805, v806, v807, v808, v809, v810, v811, v812, v813, 0, 3, 7, 2, 4, 8) -> f_668(v786, v787, v788, v789, v790, v791, v792, v793, v794, v795, v796, 1, v798, v815, v802, v817, v803, v804, v805, v806, v807, v808, v809, v810, v811, v812, v813, 0, 3, 7, 2, 4, 8) :|: v817 = 1 + v802 && 3 <= v817 f_668(v786, v787, v788, v789, v790, v791, v792, v793, v794, v795, v796, 1, v798, v815, v802, v817, v803, v804, v805, v806, v807, v808, v809, v810, v811, v812, v813, 0, 3, 7, 2, 4, 8) -> f_669(v786, v787, v788, v789, v790, v791, v792, v793, v794, v795, v796, 1, v798, v815, v802, v817, v803, v804, v805, v806, v807, v808, v809, v810, v811, v812, v813, 0, 3, 7, 2, 4, 8) :|: 0 = 0 f_669(v786, v787, v788, v789, v790, v791, v792, v793, v794, v795, v796, 1, v798, v815, v802, v817, v803, v804, v805, v806, v807, v808, v809, v810, v811, v812, v813, 0, 3, 7, 2, 4, 8) -> f_670(v786, v787, v788, v789, v790, v791, v792, v793, v794, v795, v796, 1, v798, v815, v802, v817, v803, v804, v805, v806, v807, v808, v809, v810, v811, v812, v813, 0, 3, 7, 2, 4, 8) :|: TRUE f_670(v786, v787, v788, v789, v790, v791, v792, v793, v794, v795, v796, 1, v798, v815, v802, v817, v803, v804, v805, v806, v807, v808, v809, v810, v811, v812, v813, 0, 3, 7, 2, 4, 8) -> f_671(v786, v787, v788, v789, v790, v791, v792, v793, v794, v795, v796, 1, v798, v815, v802, v817, v803, v804, v805, v806, v807, v808, v809, v810, v811, v812, v813, 0, 3, 7, 2, 4, 8) :|: TRUE f_671(v786, v787, v788, v789, v790, v791, v792, v793, v794, v795, v796, 1, v798, v815, v802, v817, v803, v804, v805, v806, v807, v808, v809, v810, v811, v812, v813, 0, 3, 7, 2, 4, 8) -> f_672(v786, v787, v788, v789, v790, v791, v792, v793, v794, v795, v796, 1, v798, v815, v802, v817, v803, v804, v805, v806, v807, v808, v809, v810, v811, v812, v813, 0, 3, 7, 2, 4, 8) :|: 0 = 0 f_672(v786, v787, v788, v789, v790, v791, v792, v793, v794, v795, v796, 1, v798, v815, v802, v817, v803, v804, v805, v806, v807, v808, v809, v810, v811, v812, v813, 0, 3, 7, 2, 4, 8) -> f_673(v786, v787, v788, v789, v790, v791, v792, v793, v794, v795, v796, 1, v815, v798, v802, v817, v803, v804, v805, v806, v807, v808, v809, v810, v811, v812, v813, 0, 3, 7, 2, 4, 8) :|: 0 = 0 f_673(v786, v787, v788, v789, v790, v791, v792, v793, v794, v795, v796, 1, v815, v798, v802, v817, v803, v804, v805, v806, v807, v808, v809, v810, v811, v812, v813, 0, 3, 7, 2, 4, 8) -> f_674(v786, v787, v788, v789, v790, v791, v792, v793, v794, v795, v796, 1, v815, v798, v802, v817, v803, v804, v805, v806, v807, v808, v809, v810, v811, v812, v813, 0, 3, 7, 2, 4, 8) :|: 0 = 0 f_674(v786, v787, v788, v789, v790, v791, v792, v793, v794, v795, v796, 1, v815, v798, v802, v817, v803, v804, v805, v806, v807, v808, v809, v810, v811, v812, v813, 0, 3, 7, 2, 4, 8) -> f_675(v786, v787, v788, v789, v790, v791, v792, v793, v794, v795, v796, 1, v815, v798, v802, v817, v803, v804, v805, v806, v807, v808, v809, v810, v811, v812, v813, 0, 3, 7, 2, 4, 8) :|: 0 = 0 f_675(v786, v787, v788, v789, v790, v791, v792, v793, v794, v795, v796, 1, v815, v798, v802, v817, v803, v804, v805, v806, v807, v808, v809, v810, v811, v812, v813, 0, 3, 7, 2, 4, 8) -> f_676(v786, v787, v788, v789, v790, v791, v792, v793, v794, v795, v796, 1, v815, v798, v802, v817, v803, v804, v805, v806, v807, v808, v809, v810, v811, v812, v813, 0, 3, 7, 2, 4, 8) :|: v815 < v796 && 2 <= v796 && 3 <= v803 && 3 <= v786 f_675(v786, v787, v788, v789, v790, v791, v792, v793, v794, v795, v796, 1, v815, v798, v802, v817, v803, v804, v805, v806, v807, v808, v809, v810, v811, v812, v813, 0, 3, 7, 2, 4, 8) -> f_677(v786, v787, v788, v789, v790, v791, v792, v793, v794, v795, v815, 1, v798, v802, v817, v803, v804, v805, v806, v807, v808, v809, v810, v811, v812, v813, 0, 3, 7, 2, 4, 8) :|: v796 <= v815 && v796 = v815 f_676(v786, v787, v788, v789, v790, v791, v792, v793, v794, v795, v796, 1, v815, v798, v802, v817, v803, v804, v805, v806, v807, v808, v809, v810, v811, v812, v813, 0, 3, 7, 2, 4, 8) -> f_678(v786, v787, v788, v789, v790, v791, v792, v793, v794, v795, v796, 1, v815, v798, v802, v817, v803, v804, v805, v806, v807, v808, v809, v810, v811, v812, v813, 0, 3, 7, 2, 4, 8) :|: 0 = 0 f_678(v786, v787, v788, v789, v790, v791, v792, v793, v794, v795, v796, 1, v815, v798, v802, v817, v803, v804, v805, v806, v807, v808, v809, v810, v811, v812, v813, 0, 3, 7, 2, 4, 8) -> f_680(v786, v787, v788, v789, v790, v791, v792, v793, v794, v795, v796, 1, v815, v798, v802, v817, v803, v804, v805, v806, v807, v808, v809, v810, v811, v812, v813, 0, 3, 7, 2, 4, 8) :|: TRUE f_680(v786, v787, v788, v789, v790, v791, v792, v793, v794, v795, v796, 1, v815, v798, v802, v817, v803, v804, v805, v806, v807, v808, v809, v810, v811, v812, v813, 0, 3, 7, 2, 4, 8) -> f_660(v786, v787, v788, v789, v790, v791, v792, v793, v794, v795, v796, 1, v815, v798, v815, v802, v817, v803, v804, v805, v806, v807, v808, v809, v810, v811, v812, v813, 0, 3, 7, 2, 4, 8) :|: TRUE f_660(v786, v787, v788, v789, v790, v791, v792, v793, v794, v795, v796, 1, v798, v799, v800, v801, v802, v803, v804, v805, v806, v807, v808, v809, v810, v811, v812, v813, 0, 3, 7, 2, 4, 8) -> f_661(v786, v787, v788, v789, v790, v791, v792, v793, v794, v795, v796, 1, v798, v799, v800, v801, v802, v803, v804, v805, v806, v807, v808, v809, v810, v811, v812, v813, 0, 3, 7, 2, 4, 8) :|: 0 = 0 f_677(v786, v787, v788, v789, v790, v791, v792, v793, v794, v795, v815, 1, v798, v802, v817, v803, v804, v805, v806, v807, v808, v809, v810, v811, v812, v813, 0, 3, 7, 2, 4, 8) -> f_679(v786, v787, v788, v789, v790, v791, v792, v793, v794, v795, v815, 1, 0, v798, v802, v817, v803, v804, v805, v806, v807, v808, v809, v810, v811, v812, v813, 3, 7, 2, 4, 8) :|: 0 = 0 f_679(v786, v787, v788, v789, v790, v791, v792, v793, v794, v795, v815, 1, 0, v798, v802, v817, v803, v804, v805, v806, v807, v808, v809, v810, v811, v812, v813, 3, 7, 2, 4, 8) -> f_681(v786, v787, v788, v789, v790, v791, v792, v793, v794, v795, v815, 1, 0, v798, v802, v817, v803, v804, v805, v806, v807, v808, v809, v810, v811, v812, v813, 3, 7, 2, 4, 8) :|: TRUE f_681(v786, v787, v788, v789, v790, v791, v792, v793, v794, v795, v815, 1, 0, v798, v802, v817, v803, v804, v805, v806, v807, v808, v809, v810, v811, v812, v813, 3, 7, 2, 4, 8) -> f_682(v786, v787, v788, v789, v790, v791, v792, v793, v794, v795, v815, 1, 0, v798, v802, v817, v803, v804, v805, v806, v807, v808, v809, v810, v811, v812, v813, 3, 7, 2, 4, 8) :|: 0 = 0 f_682(v786, v787, v788, v789, v790, v791, v792, v793, v794, v795, v815, 1, 0, v798, v802, v817, v803, v804, v805, v806, v807, v808, v809, v810, v811, v812, v813, 3, 7, 2, 4, 8) -> f_683(v786, v787, v788, v789, v790, v791, v792, v793, v794, v795, v815, 1, 0, v798, v802, v817, v804, v805, v806, v807, v808, v809, v810, v811, v812, v813, 3, 7, 2, 4, 8) :|: 0 = 0 f_683(v786, v787, v788, v789, v790, v791, v792, v793, v794, v795, v815, 1, 0, v798, v802, v817, v804, v805, v806, v807, v808, v809, v810, v811, v812, v813, 3, 7, 2, 4, 8) -> f_684(v786, v787, v788, v789, v790, v791, v792, v793, v794, v795, v815, 1, 0, v798, v802, v817, v804, v805, v806, v807, v808, v809, v810, v811, v812, v813, 3, 7, 2, 4, 8) :|: 1 + v798 = v815 f_684(v786, v787, v788, v789, v790, v791, v792, v793, v794, v795, v815, 1, 0, v798, v802, v817, v804, v805, v806, v807, v808, v809, v810, v811, v812, v813, 3, 7, 2, 4, 8) -> f_685(v786, v787, v788, v789, v790, v791, v792, v793, v794, v795, v815, 1, 0, v798, v802, v817, v804, v805, v806, v807, v808, v809, v810, v811, v812, v813, 3, 7, 2, 4, 8) :|: 0 = 0 f_685(v786, v787, v788, v789, v790, v791, v792, v793, v794, v795, v815, 1, 0, v798, v802, v817, v804, v805, v806, v807, v808, v809, v810, v811, v812, v813, 3, 7, 2, 4, 8) -> f_686(v786, v787, v788, v789, v790, v791, v792, v793, v794, v795, v815, 1, 0, v798, v802, v817, v804, v805, v806, v807, v808, v809, v810, v811, v812, v813, 3, 7, 2, 4, 8) :|: TRUE f_686(v786, v787, v788, v789, v790, v791, v792, v793, v794, v795, v815, 1, 0, v798, v802, v817, v804, v805, v806, v807, v808, v809, v810, v811, v812, v813, 3, 7, 2, 4, 8) -> f_687(v786, v787, v788, v789, v790, v791, v792, v793, v794, v795, v815, 1, 0, v798, v802, v817, v804, v805, v806, v807, v808, v809, v810, v811, v812, v813, 3, 7, 2, 4, 8) :|: TRUE f_687(v786, v787, v788, v789, v790, v791, v792, v793, v794, v795, v815, 1, 0, v798, v802, v817, v804, v805, v806, v807, v808, v809, v810, v811, v812, v813, 3, 7, 2, 4, 8) -> f_688(v786, v787, v788, v789, v790, v791, v792, v793, v794, v795, v815, 1, 0, v798, v802, v817, v804, v805, v806, v807, v808, v809, v810, v811, v812, v813, 3, 7, 2, 4, 8) :|: 0 = 0 f_688(v786, v787, v788, v789, v790, v791, v792, v793, v794, v795, v815, 1, 0, v798, v802, v817, v804, v805, v806, v807, v808, v809, v810, v811, v812, v813, 3, 7, 2, 4, 8) -> f_689(v786, v787, v788, v789, v790, v791, v792, v793, v794, v795, v798, 1, v815, 0, v802, v817, v804, v805, v806, v807, v808, v809, v810, v811, v812, v813, 3, 7, 2, 4, 8) :|: 0 = 0 f_689(v786, v787, v788, v789, v790, v791, v792, v793, v794, v795, v798, 1, v815, 0, v802, v817, v804, v805, v806, v807, v808, v809, v810, v811, v812, v813, 3, 7, 2, 4, 8) -> f_690(v786, v787, v788, v789, v790, v791, v792, v793, v794, v795, v798, 1, v815, 0, v802, v817, v804, v805, v806, v807, v808, v809, v810, v811, v812, v813, 3, 7, 2, 4, 8) :|: 0 < v798 && 2 <= v815 && 3 <= v786 f_690(v786, v787, v788, v789, v790, v791, v792, v793, v794, v795, v798, 1, v815, 0, v802, v817, v804, v805, v806, v807, v808, v809, v810, v811, v812, v813, 3, 7, 2, 4, 8) -> f_692(v786, v787, v788, v789, v790, v791, v792, v793, v794, v795, v798, 1, v815, 0, v802, v817, v804, v805, v806, v807, v808, v809, v810, v811, v812, v813, 3, 7, 2, 4, 8) :|: 0 = 0 f_692(v786, v787, v788, v789, v790, v791, v792, v793, v794, v795, v798, 1, v815, 0, v802, v817, v804, v805, v806, v807, v808, v809, v810, v811, v812, v813, 3, 7, 2, 4, 8) -> f_694(v786, v787, v788, v789, v790, v791, v792, v793, v794, v795, v798, 1, v815, 0, v802, v817, v804, v805, v806, v807, v808, v809, v810, v811, v812, v813, 3, 7, 2, 4, 8) :|: TRUE f_694(v786, v787, v788, v789, v790, v791, v792, v793, v794, v795, v798, 1, v815, 0, v802, v817, v804, v805, v806, v807, v808, v809, v810, v811, v812, v813, 3, 7, 2, 4, 8) -> f_696(v786, v787, v788, v789, v790, v791, v792, v793, v794, v795, v798, 1, v815, 0, v802, v817, v804, v805, v806, v807, v808, v809, v810, v811, v812, v813, 3, 7, 2, 4, 8) :|: 0 = 0 f_696(v786, v787, v788, v789, v790, v791, v792, v793, v794, v795, v798, 1, v815, 0, v802, v817, v804, v805, v806, v807, v808, v809, v810, v811, v812, v813, 3, 7, 2, 4, 8) -> f_698(v786, v787, v788, v789, v790, v791, v792, v793, v794, v795, v798, 1, v815, 0, v802, v817, v804, v805, v806, v807, v808, v809, v810, v811, v812, v813, 3, 7, 2, 4, 8) :|: TRUE f_698(v786, v787, v788, v789, v790, v791, v792, v793, v794, v795, v798, 1, v815, 0, v802, v817, v804, v805, v806, v807, v808, v809, v810, v811, v812, v813, 3, 7, 2, 4, 8) -> f_700(v786, v787, v788, v789, v790, v791, v792, v793, v794, v795, v798, 1, v815, 0, v802, v817, v804, v805, v806, v807, v808, v809, v810, v811, v812, v813, 3, 7, 2, 4, 8) :|: TRUE f_700(v786, v787, v788, v789, v790, v791, v792, v793, v794, v795, v798, 1, v815, 0, v802, v817, v804, v805, v806, v807, v808, v809, v810, v811, v812, v813, 3, 7, 2, 4, 8) -> f_701(v786, v787, v788, v789, v790, v791, v792, v793, v794, v795, v798, 1, v815, 0, v802, v817, v804, v805, v806, v807, v808, v809, v810, v811, v812, v813, 3, 7, 2, 4, 8) :|: TRUE f_701(v944, v945, v946, v947, v948, v949, v950, v951, v952, v953, v954, 1, v956, 0, v958, v959, v960, v961, v962, v963, v964, v965, v966, v967, v968, v969, 3, 7, 2, 4, 8) -> f_703(v944, v945, v946, v947, v948, v949, v950, v951, v952, v953, v954, 1, v956, 0, v958, v959, v960, v961, v962, v963, v964, v965, v966, v967, v968, v969, 3, 7, 2, 4, 8) :|: 0 = 0 f_703(v944, v945, v946, v947, v948, v949, v950, v951, v952, v953, v954, 1, v956, 0, v958, v959, v960, v961, v962, v963, v964, v965, v966, v967, v968, v969, 3, 7, 2, 4, 8) -> f_704(v944, v945, v946, v947, v948, v949, v950, v951, v952, v953, v954, 1, 0, v956, v958, v959, v960, v961, v962, v963, v964, v965, v966, v967, v968, v969, 3, 7, 2, 4, 8) :|: 0 = 0 f_704(v944, v945, v946, v947, v948, v949, v950, v951, v952, v953, v954, 1, 0, v956, v958, v959, v960, v961, v962, v963, v964, v965, v966, v967, v968, v969, 3, 7, 2, 4, 8) -> f_705(v944, v945, v946, v947, v948, v949, v950, v951, v952, v953, v954, 1, 0, v956, v958, v959, v960, v961, v962, v963, v964, v965, v966, v967, v968, v969, 3, 7, 2, 4, 8) :|: 0 = 0 f_705(v944, v945, v946, v947, v948, v949, v950, v951, v952, v953, v954, 1, 0, v956, v958, v959, v960, v961, v962, v963, v964, v965, v966, v967, v968, v969, 3, 7, 2, 4, 8) -> f_706(v944, v945, v946, v947, v948, v949, v950, v951, v952, v953, v954, 1, 0, v956, v958, v959, v960, v961, v962, v963, v964, v965, v966, v967, v968, v969, 3, 7, 2, 4, 8) :|: 0 = 0 f_706(v944, v945, v946, v947, v948, v949, v950, v951, v952, v953, v954, 1, 0, v956, v958, v959, v960, v961, v962, v963, v964, v965, v966, v967, v968, v969, 3, 7, 2, 4, 8) -> f_707(v944, v945, v946, v947, v948, v949, v950, v951, v952, v953, v954, 1, 0, v956, v958, v959, v960, v961, v962, v963, v964, v965, v966, v967, v968, v969, 3, 7, 2, 4, 8) :|: 0 = 0 f_707(v944, v945, v946, v947, v948, v949, v950, v951, v952, v953, v954, 1, 0, v956, v958, v959, v960, v961, v962, v963, v964, v965, v966, v967, v968, v969, 3, 7, 2, 4, 8) -> f_708(v944, v945, v946, v947, v948, v949, v950, v951, v952, v953, v954, 1, 0, v956, v958, v959, v960, v961, v962, v963, v964, v965, v966, v967, v968, v969, 3, 7, 2, 4, 8) :|: TRUE f_708(v944, v945, v946, v947, v948, v949, v950, v951, v952, v953, v954, 1, 0, v956, v958, v959, v960, v961, v962, v963, v964, v965, v966, v967, v968, v969, 3, 7, 2, 4, 8) -> f_660(v944, v945, v946, v947, v948, v949, v950, v951, v952, v953, v954, 1, 0, v954, v956, v958, v959, v956, v960, v961, v962, v963, v964, v965, v966, v967, v968, v969, 0, 3, 7, 2, 4, 8) :|: TRUE Combined rules. Obtained 2 rulesP rules: f_661(v786:0, v787:0, v788:0, v789:0, v790:0, v791:0, v792:0, v793:0, v794:0, v795:0, v796:0, 1, v798:0, v799:0, v800:0, v801:0, v802:0, v803:0, v804:0, v805:0, v806:0, v807:0, v808:0, v809:0, v810:0, v811:0, v812:0, v813:0, 0, 3, 7, 2, 4, 8) -> f_661(v786:0, v787:0, v788:0, v789:0, v790:0, v791:0, v792:0, v793:0, v794:0, v795:0, v796:0, 1, 1 + v798:0, v798:0, 1 + v798:0, v802:0, 1 + v802:0, v803:0, v804:0, v805:0, v806:0, v807:0, v808:0, v809:0, v810:0, v811:0, v812:0, v813:0, 0, 3, 7, 2, 4, 8) :|: v798:0 > -1 && v802:0 > 1 && v796:0 > 1 && v796:0 > 1 + v798:0 && v786:0 > 2 && v803:0 > 2 f_661(v786:0, v787:0, v788:0, v789:0, v790:0, v791:0, v792:0, v793:0, v794:0, v795:0, 1 + v798:0, 1, v798:0, v799:0, v800:0, v801:0, v802:0, v803:0, v804:0, v805:0, v806:0, v807:0, v808:0, v809:0, v810:0, v811:0, v812:0, v813:0, 0, 3, 7, 2, 4, 8) -> f_661(v786:0, v787:0, v788:0, v789:0, v790:0, v791:0, v792:0, v793:0, v794:0, v795:0, v798:0, 1, 0, v798:0, 1 + v798:0, v802:0, 1 + v802:0, 1 + v798:0, v804:0, v805:0, v806:0, v807:0, v808:0, v809:0, v810:0, v811:0, v812:0, v813:0, 0, 3, 7, 2, 4, 8) :|: v798:0 > 0 && v802:0 > 1 && v786:0 > 2 Filtered unneeded arguments: f_661(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) -> f_661(x1, x11, x13, x17, x18) Removed division, modulo operations, cleaned up constraints. Obtained 2 rules.P rules: f_661(v786:0, v796:0, v798:0, v802:0, v803:0) -> f_661(v786:0, v796:0, 1 + v798:0, 1 + v802:0, v803:0) :|: v802:0 > 1 && v798:0 > -1 && v796:0 > 1 && v796:0 > 1 + v798:0 && v803:0 > 2 && v786:0 > 2 f_661(v786:0, sum~cons_1~v798:0, v798:0, v802:0, v803:0) -> f_661(v786:0, v798:0, 0, 1 + v802:0, 1 + v798:0) :|: v802:0 > 1 && v786:0 > 2 && v798:0 > 0 && sum~cons_1~v798:0 = 1 + v798:0 ---------------------------------------- (9) Obligation: Rules: f_661(v786:0, v796:0, v798:0, v802:0, v803:0) -> f_661(v786:0, v796:0, 1 + v798:0, 1 + v802:0, v803:0) :|: v802:0 > 1 && v798:0 > -1 && v796:0 > 1 && v796:0 > 1 + v798:0 && v803:0 > 2 && v786:0 > 2 f_661(x, x1, x2, x3, x4) -> f_661(x, x2, 0, 1 + x3, 1 + x2) :|: x3 > 1 && x > 2 && x2 > 0 && x1 = 1 + x2 ---------------------------------------- (10) IRS2T2 (EQUIVALENT) Transformed input IRS into an integer transition system.Used the following mapping from defined symbols to location IDs: (f_661_5,1) ---------------------------------------- (11) Obligation: START: 0; FROM: 0; TO: 1; FROM: 1; oldX0 := x0; oldX1 := x1; oldX2 := x2; oldX3 := x3; oldX4 := x4; assume(oldX3 > 1 && oldX2 > -1 && oldX1 > 1 && oldX1 > 1 + oldX2 && oldX4 > 2 && oldX0 > 2); x0 := oldX0; x1 := oldX1; x2 := 1 + oldX2; x3 := 1 + oldX3; x4 := oldX4; TO: 1; FROM: 1; oldX0 := x0; oldX1 := x1; oldX2 := x2; oldX3 := x3; oldX4 := x4; assume(oldX3 > 1 && oldX0 > 2 && oldX2 > 0 && oldX1 = 1 + oldX2); x0 := oldX0; x1 := oldX2; x2 := 0; x3 := 1 + oldX3; x4 := 1 + oldX2; TO: 1; ---------------------------------------- (12) T2 (EQUIVALENT) Initially, performed program simplifications using lexicographic rank functions: * Removed transitions 1, 4, 5 using the following rank functions: - Rank function 1: RF for loc. 5: x1 RF for loc. 6: x1 Bound for (chained) transitions 5: 2 - Rank function 2: RF for loc. 5: 1+2*x1-2*x2 RF for loc. 6: 2*x1-2*x2 Bound for (chained) transitions 4: 4 - Rank function 3: RF for loc. 5: 0 RF for loc. 6: -1 Bound for (chained) transitions 1: 0 ---------------------------------------- (13) YES ---------------------------------------- (14) Obligation: SCC ---------------------------------------- (15) SCC2IRS (SOUND) Transformed LLVM symbolic execution graph SCC into a rewrite problem. Log: Generated rules. Obtained 19 rulesP rules: f_460(v168, v169, v170, v171, v172, v173, v174, v175, v176, v177, 1, v179, v180, v181, v182, v183, v184, v185, v186, v187, v188, v189, v190, 0, 3, 7, 4, 8) -> f_461(v168, v169, v170, v171, v172, v173, v174, v175, v176, v177, 1, v180, v179, v181, v182, v183, v184, v185, v186, v187, v188, v189, v190, 0, 3, 7, 4, 8) :|: 0 = 0 f_461(v168, v169, v170, v171, v172, v173, v174, v175, v176, v177, 1, v180, v179, v181, v182, v183, v184, v185, v186, v187, v188, v189, v190, 0, 3, 7, 4, 8) -> f_462(v168, v169, v170, v171, v172, v173, v174, v175, v176, v177, 1, v180, v179, v181, v182, v183, v184, v185, v186, v187, v188, v189, v190, 0, 3, 7, 4, 8) :|: 0 = 0 f_462(v168, v169, v170, v171, v172, v173, v174, v175, v176, v177, 1, v180, v179, v181, v182, v183, v184, v185, v186, v187, v188, v189, v190, 0, 3, 7, 4, 8) -> f_463(v168, v169, v170, v171, v172, v173, v174, v175, v176, v177, 1, v180, v179, v181, v182, v183, v184, v185, v186, v187, v188, v189, v190, 0, 3, 7, 4, 8) :|: 0 = 0 f_463(v168, v169, v170, v171, v172, v173, v174, v175, v176, v177, 1, v180, v179, v181, v182, v183, v184, v185, v186, v187, v188, v189, v190, 0, 3, 7, 4, 8) -> f_464(v168, v169, v170, v171, v172, v173, v174, v175, v176, v177, 1, v180, v179, v181, v182, v183, v184, v185, v186, v187, v188, v189, v190, 0, 3, 7, 2, 4, 8) :|: v180 < v168 && 2 <= v168 f_464(v168, v169, v170, v171, v172, v173, v174, v175, v176, v177, 1, v180, v179, v181, v182, v183, v184, v185, v186, v187, v188, v189, v190, 0, 3, 7, 2, 4, 8) -> f_466(v168, v169, v170, v171, v172, v173, v174, v175, v176, v177, 1, v180, v179, v181, v182, v183, v184, v185, v186, v187, v188, v189, v190, 0, 3, 7, 2, 4, 8) :|: 0 = 0 f_466(v168, v169, v170, v171, v172, v173, v174, v175, v176, v177, 1, v180, v179, v181, v182, v183, v184, v185, v186, v187, v188, v189, v190, 0, 3, 7, 2, 4, 8) -> f_468(v168, v169, v170, v171, v172, v173, v174, v175, v176, v177, 1, v180, v179, v181, v182, v183, v184, v185, v186, v187, v188, v189, v190, 0, 3, 7, 2, 4, 8) :|: TRUE f_468(v168, v169, v170, v171, v172, v173, v174, v175, v176, v177, 1, v180, v179, v181, v182, v183, v184, v185, v186, v187, v188, v189, v190, 0, 3, 7, 2, 4, 8) -> f_470(v168, v169, v170, v171, v172, v173, v174, v175, v176, v177, 1, v180, v179, v181, v182, v183, v184, v185, v186, v187, v188, v189, v190, 0, 3, 7, 2, 4, 8) :|: 0 = 0 f_470(v168, v169, v170, v171, v172, v173, v174, v175, v176, v177, 1, v180, v179, v181, v182, v183, v184, v185, v186, v187, v188, v189, v190, 0, 3, 7, 2, 4, 8) -> f_472(v168, v169, v170, v171, v172, v173, v174, v175, v176, v177, 1, v180, v179, v181, v182, v183, v184, v185, v186, v187, v188, v189, v190, 0, 3, 7, 2, 4, 8) :|: 0 = 0 f_472(v168, v169, v170, v171, v172, v173, v174, v175, v176, v177, 1, v180, v179, v181, v182, v183, v184, v185, v186, v187, v188, v189, v190, 0, 3, 7, 2, 4, 8) -> f_474(v168, v169, v170, v171, v172, v173, v174, v175, v176, v177, 1, v180, v192, v179, v181, v182, v183, v184, v185, v186, v187, v188, v189, v190, 0, 3, 7, 2, 4, 8) :|: v192 = 1 + v180 && 2 <= v192 f_474(v168, v169, v170, v171, v172, v173, v174, v175, v176, v177, 1, v180, v192, v179, v181, v182, v183, v184, v185, v186, v187, v188, v189, v190, 0, 3, 7, 2, 4, 8) -> f_476(v168, v169, v170, v171, v172, v173, v174, v175, v176, v177, 1, v180, v192, v179, v181, v182, v183, v184, v185, v186, v187, v188, v189, v190, 0, 3, 7, 2, 4, 8) :|: 0 = 0 f_476(v168, v169, v170, v171, v172, v173, v174, v175, v176, v177, 1, v180, v192, v179, v181, v182, v183, v184, v185, v186, v187, v188, v189, v190, 0, 3, 7, 2, 4, 8) -> f_478(v168, v169, v170, v171, v172, v173, v174, v175, v176, v177, 1, v180, v192, v179, v181, v182, v183, v184, v185, v186, v187, v188, v189, v190, 0, 3, 7, 2, 4, 8) :|: TRUE f_478(v168, v169, v170, v171, v172, v173, v174, v175, v176, v177, 1, v180, v192, v179, v181, v182, v183, v184, v185, v186, v187, v188, v189, v190, 0, 3, 7, 2, 4, 8) -> f_480(v168, v169, v170, v171, v172, v173, v174, v175, v176, v177, 1, v180, v192, v179, v181, v182, v183, v184, v185, v186, v187, v188, v189, v190, 0, 3, 7, 2, 4, 8) :|: 0 = 0 f_480(v168, v169, v170, v171, v172, v173, v174, v175, v176, v177, 1, v180, v192, v179, v181, v182, v183, v184, v185, v186, v187, v188, v189, v190, 0, 3, 7, 2, 4, 8) -> f_482(v168, v169, v170, v171, v172, v173, v174, v175, v176, v177, 1, v180, v192, v181, v182, v183, v184, v185, v186, v187, v188, v189, v190, 0, 3, 7, 2, 4, 8) :|: 0 = 0 f_482(v168, v169, v170, v171, v172, v173, v174, v175, v176, v177, 1, v180, v192, v181, v182, v183, v184, v185, v186, v187, v188, v189, v190, 0, 3, 7, 2, 4, 8) -> f_484(v168, v169, v170, v171, v172, v173, v174, v175, v176, v177, 1, v180, v192, v181, v182, v183, v184, v185, v186, v187, v188, v189, v190, 0, 3, 7, 2, 4, 8) :|: v192 = 1 + v180 f_484(v168, v169, v170, v171, v172, v173, v174, v175, v176, v177, 1, v180, v192, v181, v182, v183, v184, v185, v186, v187, v188, v189, v190, 0, 3, 7, 2, 4, 8) -> f_486(v168, v169, v170, v171, v172, v173, v174, v175, v176, v177, 1, v180, v192, v181, v182, v183, v184, v185, v186, v187, v188, v189, v190, 0, 3, 7, 2, 4, 8) :|: 0 = 0 f_486(v168, v169, v170, v171, v172, v173, v174, v175, v176, v177, 1, v180, v192, v181, v182, v183, v184, v185, v186, v187, v188, v189, v190, 0, 3, 7, 2, 4, 8) -> f_489(v168, v169, v170, v171, v172, v173, v174, v175, v176, v177, 1, v180, v192, v181, v182, v183, v184, v185, v186, v187, v188, v189, v190, 0, 3, 7, 2, 4, 8) :|: TRUE f_489(v168, v169, v170, v171, v172, v173, v174, v175, v176, v177, 1, v180, v192, v181, v182, v183, v184, v185, v186, v187, v188, v189, v190, 0, 3, 7, 2, 4, 8) -> f_492(v168, v169, v170, v171, v172, v173, v174, v175, v176, v177, 1, v180, v192, v181, v182, v183, v184, v185, v186, v187, v188, v189, v190, 0, 3, 7, 2, 4, 8) :|: TRUE f_492(v168, v169, v170, v171, v172, v173, v174, v175, v176, v177, 1, v180, v192, v181, v182, v183, v184, v185, v186, v187, v188, v189, v190, 0, 3, 7, 2, 4, 8) -> f_459(v168, v169, v170, v171, v172, v173, v174, v175, v176, v177, 1, v180, v192, v181, v182, v183, v184, v185, v186, v187, v188, v189, v190, 0, 3, 7, 4, 8) :|: TRUE f_459(v168, v169, v170, v171, v172, v173, v174, v175, v176, v177, 1, v179, v180, v181, v182, v183, v184, v185, v186, v187, v188, v189, v190, 0, 3, 7, 4, 8) -> f_460(v168, v169, v170, v171, v172, v173, v174, v175, v176, v177, 1, v179, v180, v181, v182, v183, v184, v185, v186, v187, v188, v189, v190, 0, 3, 7, 4, 8) :|: 0 = 0 Combined rules. Obtained 1 rulesP rules: f_460(v168:0, v169:0, v170:0, v171:0, v172:0, v173:0, v174:0, v175:0, v176:0, v177:0, 1, v179:0, v180:0, v181:0, v182:0, v183:0, v184:0, v185:0, v186:0, v187:0, v188:0, v189:0, v190:0, 0, 3, 7, 4, 8) -> f_460(v168:0, v169:0, v170:0, v171:0, v172:0, v173:0, v174:0, v175:0, v176:0, v177:0, 1, v180:0, 1 + v180:0, v181:0, v182:0, v183:0, v184:0, v185:0, v186:0, v187:0, v188:0, v189:0, v190:0, 0, 3, 7, 4, 8) :|: v168:0 > 1 && v180:0 > 0 && v180:0 < v168:0 Filtered unneeded arguments: f_460(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) -> f_460(x1, x13) Removed division, modulo operations, cleaned up constraints. Obtained 1 rules.P rules: f_460(v168:0, v180:0) -> f_460(v168:0, 1 + v180:0) :|: v180:0 > 0 && v180:0 < v168:0 && v168:0 > 1 ---------------------------------------- (16) Obligation: Rules: f_460(v168:0, v180:0) -> f_460(v168:0, 1 + v180:0) :|: v180:0 > 0 && v180:0 < v168:0 && v168:0 > 1 ---------------------------------------- (17) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (18) Obligation: Rules: f_460(v168:0:0, v180:0:0) -> f_460(v168:0:0, 1 + v180:0:0) :|: v180:0:0 > 0 && v180:0:0 < v168:0:0 && v168:0:0 > 1 ---------------------------------------- (19) RankingReductionPairProof (EQUIVALENT) Interpretation: [ f_460 ] = -1*f_460_2 + f_460_1 The following rules are decreasing: f_460(v168:0:0, v180:0:0) -> f_460(v168:0:0, 1 + v180:0:0) :|: v180:0:0 > 0 && v180:0:0 < v168:0:0 && v168:0:0 > 1 The following rules are bounded: f_460(v168:0:0, v180:0:0) -> f_460(v168:0:0, 1 + v180:0:0) :|: v180:0:0 > 0 && v180:0:0 < v168:0:0 && v168:0:0 > 1 ---------------------------------------- (20) YES