/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: 794c25de1cacf0d048858bcd21c9a779e1221865 marcel 20200619 unpublished dirty Termination of the given C Problem could be proven: (0) C Problem (1) CToLLVMProof [EQUIVALENT, 176 ms] (2) LLVM problem (3) LLVMToTerminationGraphProof [EQUIVALENT, 8203 ms] (4) LLVM Symbolic Execution Graph (5) SymbolicExecutionGraphToSCCProof [SOUND, 1 ms] (6) AND (7) LLVM Symbolic Execution SCC (8) SCC2IRS [SOUND, 97 ms] (9) IntTRS (10) IntTRSCompressionProof [EQUIVALENT, 0 ms] (11) IntTRS (12) RankingReductionPairProof [EQUIVALENT, 0 ms] (13) IntTRS (14) IntTRSCompressionProof [EQUIVALENT, 1 ms] (15) IntTRS (16) PolynomialOrderProcessor [EQUIVALENT, 0 ms] (17) YES (18) LLVM Symbolic Execution SCC (19) SCC2IRS [SOUND, 109 ms] (20) IntTRS (21) IntTRSCompressionProof [EQUIVALENT, 0 ms] (22) IntTRS (23) PolynomialOrderProcessor [EQUIVALENT, 9 ms] (24) 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) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (11) Obligation: Rules: f_661(x:0, sum~cons_1~x2:0, x2:0, x3:0, x4:0) -> f_661(x:0, x2:0, 0, 1 + x3:0, 1 + x2:0) :|: x3:0 > 1 && x:0 > 2 && x2:0 > 0 && sum~cons_1~x2:0 = 1 + x2:0 f_661(v786:0:0, v796:0:0, v798:0:0, v802:0:0, v803:0:0) -> f_661(v786:0:0, v796:0:0, 1 + v798:0:0, 1 + v802:0:0, v803:0:0) :|: v803:0:0 > 2 && v786:0:0 > 2 && v796:0:0 > 1 + v798:0:0 && v796:0:0 > 1 && v798:0:0 > -1 && v802:0:0 > 1 ---------------------------------------- (12) RankingReductionPairProof (EQUIVALENT) Interpretation: [ f_661 ] = f_661_2 The following rules are decreasing: f_661(x:0, sum~cons_1~x2:0, x2:0, x3:0, x4:0) -> f_661(x:0, x2:0, 0, 1 + x3:0, 1 + x2:0) :|: x3:0 > 1 && x:0 > 2 && x2:0 > 0 && sum~cons_1~x2:0 = 1 + x2:0 The following rules are bounded: f_661(x:0, sum~cons_1~x2:0, x2:0, x3:0, x4:0) -> f_661(x:0, x2:0, 0, 1 + x3:0, 1 + x2:0) :|: x3:0 > 1 && x:0 > 2 && x2:0 > 0 && sum~cons_1~x2:0 = 1 + x2:0 f_661(v786:0:0, v796:0:0, v798:0:0, v802:0:0, v803:0:0) -> f_661(v786:0:0, v796:0:0, 1 + v798:0:0, 1 + v802:0:0, v803:0:0) :|: v803:0:0 > 2 && v786:0:0 > 2 && v796:0:0 > 1 + v798:0:0 && v796:0:0 > 1 && v798:0:0 > -1 && v802:0:0 > 1 ---------------------------------------- (13) Obligation: Rules: f_661(v786:0:0, v796:0:0, v798:0:0, v802:0:0, v803:0:0) -> f_661(v786:0:0, v796:0:0, 1 + v798:0:0, 1 + v802:0:0, v803:0:0) :|: v803:0:0 > 2 && v786:0:0 > 2 && v796:0:0 > 1 + v798:0:0 && v796:0:0 > 1 && v798:0:0 > -1 && v802:0:0 > 1 ---------------------------------------- (14) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (15) Obligation: Rules: f_661(v786:0:0:0, v796:0:0:0, v798:0:0:0, v802:0:0:0, v803:0:0:0) -> f_661(v786:0:0:0, v796:0:0:0, 1 + v798:0:0:0, 1 + v802:0:0:0, v803:0:0:0) :|: v798:0:0:0 > -1 && v802:0:0:0 > 1 && v796:0:0:0 > 1 && v796:0:0:0 > 1 + v798:0:0:0 && v786:0:0:0 > 2 && v803:0:0:0 > 2 ---------------------------------------- (16) PolynomialOrderProcessor (EQUIVALENT) Found the following polynomial interpretation: [f_661(x, x1, x2, x3, x4)] = x1 - x2 The following rules are decreasing: f_661(v786:0:0:0, v796:0:0:0, v798:0:0:0, v802:0:0:0, v803:0:0:0) -> f_661(v786:0:0:0, v796:0:0:0, 1 + v798:0:0:0, 1 + v802:0:0:0, v803:0:0:0) :|: v798:0:0:0 > -1 && v802:0:0:0 > 1 && v796:0:0:0 > 1 && v796:0:0:0 > 1 + v798:0:0:0 && v786:0:0:0 > 2 && v803:0:0:0 > 2 The following rules are bounded: f_661(v786:0:0:0, v796:0:0:0, v798:0:0:0, v802:0:0:0, v803:0:0:0) -> f_661(v786:0:0:0, v796:0:0:0, 1 + v798:0:0:0, 1 + v802:0:0:0, v803:0:0:0) :|: v798:0:0:0 > -1 && v802:0:0:0 > 1 && v796:0:0:0 > 1 && v796:0:0:0 > 1 + v798:0:0:0 && v786:0:0:0 > 2 && v803:0:0:0 > 2 ---------------------------------------- (17) YES ---------------------------------------- (18) Obligation: SCC ---------------------------------------- (19) 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 ---------------------------------------- (20) 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 ---------------------------------------- (21) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (22) 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 ---------------------------------------- (23) PolynomialOrderProcessor (EQUIVALENT) Found the following polynomial interpretation: [f_460(x, x1)] = x - x1 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 ---------------------------------------- (24) YES