/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, 174 ms] (2) LLVM problem (3) LLVMToTerminationGraphProof [EQUIVALENT, 2590 ms] (4) LLVM Symbolic Execution Graph (5) SymbolicExecutionGraphToSCCProof [SOUND, 0 ms] (6) AND (7) LLVM Symbolic Execution SCC (8) SCC2IRS [SOUND, 51 ms] (9) IntTRS (10) IntTRSCompressionProof [EQUIVALENT, 0 ms] (11) IntTRS (12) RankingReductionPairProof [EQUIVALENT, 30 ms] (13) YES (14) LLVM Symbolic Execution SCC (15) SCC2IRS [SOUND, 51 ms] (16) IntTRS (17) IntTRSCompressionProof [EQUIVALENT, 0 ms] (18) IntTRS (19) RankingReductionPairProof [EQUIVALENT, 2 ms] (20) YES (21) LLVM Symbolic Execution SCC (22) SCC2IRS [SOUND, 79 ms] (23) IntTRS (24) IntTRSCompressionProof [EQUIVALENT, 0 ms] (25) IntTRS (26) RankingReductionPairProof [EQUIVALENT, 0 ms] (27) 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 %c = alloca i32, align 4 store %x, %1 store %y, %2 store 0, %c br %3 3: %4 = load %1 %5 = icmp sgt %4 0 br %5, %9, %6 6: %7 = load %2 %8 = icmp sgt %7 0 br %9 9: %10 = phi [1, %3], [%8, %6] br %10, %11, %28 11: %12 = load %1 %13 = icmp sgt %12 0 br %13, %14, %17 14: %15 = load %1 %16 = sub %15 1 store %16, %1 br %25 17: %18 = load %2 %19 = icmp sgt %18 0 br %19, %20, %23 20: %21 = load %2 %22 = sub %21 1 store %22, %2 br %24 23: br %24 24: br %25 25: %26 = load %c %27 = add %26 1 store %27, %c br %3 28: %29 = load %c ret %29 *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 3 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 24 rulesP rules: f_654(v908, v909, v910, v911, v912, 0, 1, v915, v916, v917, v918, v919, v920, v921, v922, v923, 3, 4) -> f_656(v908, v909, v910, v911, v912, 0, 1, v916, v917, v918, v919, v920, v921, v922, v923, 3, 4) :|: 0 = 0 f_656(v908, v909, v910, v911, v912, 0, 1, v916, v917, v918, v919, v920, v921, v922, v923, 3, 4) -> f_657(v908, v909, v910, v911, v912, 0, 1, v916, v953, v917, v918, v919, v920, v921, v922, v923, 3, 4, 2) :|: v953 = 1 + v916 && 2 <= v953 f_657(v908, v909, v910, v911, v912, 0, 1, v916, v953, v917, v918, v919, v920, v921, v922, v923, 3, 4, 2) -> f_658(v908, v909, v910, v911, v912, 0, 1, v916, v953, v917, v918, v919, v920, v921, v922, v923, 3, 4, 2) :|: TRUE f_658(v908, v909, v910, v911, v912, 0, 1, v916, v953, v917, v918, v919, v920, v921, v922, v923, 3, 4, 2) -> f_659(v908, v909, v910, v911, v912, 0, 1, v916, v953, v917, v918, v919, v920, v921, v922, v923, 3, 4, 2) :|: TRUE f_659(v908, v909, v910, v911, v912, 0, 1, v916, v953, v917, v918, v919, v920, v921, v922, v923, 3, 4, 2) -> f_660(v908, v909, v910, v911, v912, 0, 1, v916, v953, v917, v918, v919, v920, v921, v922, v923, 3, 4, 2) :|: 0 = 0 f_660(v908, v909, v910, v911, v912, 0, 1, v916, v953, v917, v918, v919, v920, v921, v922, v923, 3, 4, 2) -> f_661(v908, v909, v910, v911, v912, 0, 1, v916, v953, v917, v918, v919, v920, v921, v922, v923, 3, 4, 2) :|: 0 = 0 f_661(v908, v909, v910, v911, v912, 0, 1, v916, v953, v917, v918, v919, v920, v921, v922, v923, 3, 4, 2) -> f_662(v908, v909, v910, v911, v912, 0, 1, v916, v953, v917, v918, v919, v920, v921, v922, v923, 3, 4, 2) :|: TRUE f_662(v908, v909, v910, v911, v912, 0, 1, v916, v953, v917, v918, v919, v920, v921, v922, v923, 3, 4, 2) -> f_663(v908, v909, v910, v911, v912, 0, 1, v916, v953, v918, v917, v919, v920, v921, v922, v923, 3, 4, 2) :|: 0 = 0 f_663(v908, v909, v910, v911, v912, 0, 1, v916, v953, v918, v917, v919, v920, v921, v922, v923, 3, 4, 2) -> f_664(v908, v909, v910, v911, v912, 0, 1, v916, v953, v918, v917, v919, v920, v921, v922, v923, 3, 2, 4) :|: 0 < v918 && 2 <= v917 && 2 <= v909 f_664(v908, v909, v910, v911, v912, 0, 1, v916, v953, v918, v917, v919, v920, v921, v922, v923, 3, 2, 4) -> f_666(v908, v909, v910, v911, v912, 0, 1, v916, v953, v918, v917, v919, v920, v921, v922, v923, 3, 2, 4) :|: 0 = 0 f_666(v908, v909, v910, v911, v912, 0, 1, v916, v953, v918, v917, v919, v920, v921, v922, v923, 3, 2, 4) -> f_668(v908, v909, v910, v911, v912, 0, 1, v916, v953, v918, v917, v919, v920, v921, v922, v923, 3, 2, 4) :|: 0 = 0 f_668(v908, v909, v910, v911, v912, 0, 1, v916, v953, v918, v917, v919, v920, v921, v922, v923, 3, 2, 4) -> f_670(v908, v909, v910, v911, v912, 0, 1, v916, v953, v918, v917, v919, v920, v921, v922, v923, 3, 2, 4) :|: TRUE f_670(v908, v909, v910, v911, v912, 0, 1, v916, v953, v918, v917, v919, v920, v921, v922, v923, 3, 2, 4) -> f_672(v908, v909, v910, v911, v912, 0, 1, v916, v953, v918, v917, v919, v920, v921, v922, v923, 3, 2, 4) :|: 0 = 0 f_672(v908, v909, v910, v911, v912, 0, 1, v916, v953, v918, v917, v919, v920, v921, v922, v923, 3, 2, 4) -> f_674(v908, v909, v910, v911, v912, 0, 1, v916, v953, v918, v917, v919, v920, v921, v922, v923, 3, 2, 4) :|: 0 = 0 f_674(v908, v909, v910, v911, v912, 0, 1, v916, v953, v918, v917, v919, v920, v921, v922, v923, 3, 2, 4) -> f_676(v908, v909, v910, v911, v912, 0, 1, v916, v953, v918, v917, v919, v920, v921, v922, v923, 3, 2, 4) :|: TRUE f_676(v908, v909, v910, v911, v912, 0, 1, v916, v953, v918, v917, v919, v920, v921, v922, v923, 3, 2, 4) -> f_677(v908, v909, v910, v911, v912, 0, 1, v916, v953, v918, v917, v919, v920, v921, v922, v923, 3, 2, 4) :|: 0 = 0 f_677(v908, v909, v910, v911, v912, 0, 1, v916, v953, v918, v917, v919, v920, v921, v922, v923, 3, 2, 4) -> f_678(v908, v909, v910, v911, v912, 0, 1, v916, v953, v918, v917, v919, v920, v921, v922, v923, 3, 2, 4) :|: 0 = 0 f_678(v908, v909, v910, v911, v912, 0, 1, v916, v953, v918, v917, v919, v920, v921, v922, v923, 3, 2, 4) -> f_679(v908, v909, v910, v911, v912, 0, 1, v916, v953, v918, v917, v919, v920, v921, v922, v923, 3, 2, 4) :|: TRUE f_679(v908, v909, v910, v911, v912, 0, 1, v916, v953, v918, v917, v919, v920, v921, v922, v923, 3, 2, 4) -> f_680(v908, v909, v910, v911, v912, 0, 1, v916, v953, v918, v919, v920, v921, v922, v923, 3, 2, 4) :|: 0 = 0 f_680(v908, v909, v910, v911, v912, 0, 1, v916, v953, v918, v919, v920, v921, v922, v923, 3, 2, 4) -> f_681(v908, v909, v910, v911, v912, 0, 1, v916, v953, v918, v1011, v919, v920, v921, v922, v923, 3, 2, 4) :|: 1 + v1011 = v918 && 0 <= v1011 f_681(v908, v909, v910, v911, v912, 0, 1, v916, v953, v918, v1011, v919, v920, v921, v922, v923, 3, 2, 4) -> f_682(v908, v909, v910, v911, v912, 0, 1, v916, v953, v918, v1011, v919, v920, v921, v922, v923, 3, 2, 4) :|: TRUE f_682(v908, v909, v910, v911, v912, 0, 1, v916, v953, v918, v1011, v919, v920, v921, v922, v923, 3, 2, 4) -> f_683(v908, v909, v910, v911, v912, 0, 1, v916, v953, v918, v1011, v919, v920, v921, v922, v923, 3, 2, 4) :|: TRUE f_683(v908, v909, v910, v911, v912, 0, 1, v916, v953, v918, v1011, v919, v920, v921, v922, v923, 3, 2, 4) -> f_652(v908, v909, v910, v911, v912, 0, 1, v916, v953, v918, v1011, v919, v920, v921, v922, v923, 3, 4) :|: TRUE f_652(v908, v909, v910, v911, v912, 0, 1, v915, v916, v917, v918, v919, v920, v921, v922, v923, 3, 4) -> f_654(v908, v909, v910, v911, v912, 0, 1, v915, v916, v917, v918, v919, v920, v921, v922, v923, 3, 4) :|: TRUE Combined rules. Obtained 1 rulesP rules: f_654(v908:0, v909:0, v910:0, v911:0, v912:0, 0, 1, v915:0, v916:0, v917:0, 1 + v1011:0, v919:0, v920:0, v921:0, v922:0, v923:0, 3, 4) -> f_654(v908:0, v909:0, v910:0, v911:0, v912:0, 0, 1, v916:0, 1 + v916:0, 1 + v1011:0, v1011:0, v919:0, v920:0, v921:0, v922:0, v923:0, 3, 4) :|: v916:0 > 0 && v917:0 > 1 && v1011:0 > -1 && v909:0 > 1 Filtered unneeded arguments: f_654(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18) -> f_654(x2, x9, x10, x11) Removed division, modulo operations, cleaned up constraints. Obtained 1 rules.P rules: f_654(v909:0, v916:0, v917:0, sum~cons_1~v1011:0) -> f_654(v909:0, 1 + v916:0, 1 + v1011:0, v1011:0) :|: v917:0 > 1 && v916:0 > 0 && v909:0 > 1 && v1011:0 > -1 && sum~cons_1~v1011:0 = 1 + v1011:0 ---------------------------------------- (9) Obligation: Rules: f_654(v909:0, v916:0, v917:0, sum~cons_1~v1011:0) -> f_654(v909:0, 1 + v916:0, 1 + v1011:0, v1011:0) :|: v917:0 > 1 && v916:0 > 0 && v909:0 > 1 && v1011:0 > -1 && sum~cons_1~v1011:0 = 1 + v1011:0 ---------------------------------------- (10) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (11) Obligation: Rules: f_654(v909:0:0, v916:0:0, v917:0:0, sum~cons_1~v1011:0:0) -> f_654(v909:0:0, 1 + v916:0:0, 1 + v1011:0:0, v1011:0:0) :|: v909:0:0 > 1 && v1011:0:0 > -1 && v916:0:0 > 0 && v917:0:0 > 1 && sum~cons_1~v1011:0:0 = 1 + v1011:0:0 ---------------------------------------- (12) RankingReductionPairProof (EQUIVALENT) Interpretation: [ f_654 ] = f_654_4 The following rules are decreasing: f_654(v909:0:0, v916:0:0, v917:0:0, sum~cons_1~v1011:0:0) -> f_654(v909:0:0, 1 + v916:0:0, 1 + v1011:0:0, v1011:0:0) :|: v909:0:0 > 1 && v1011:0:0 > -1 && v916:0:0 > 0 && v917:0:0 > 1 && sum~cons_1~v1011:0:0 = 1 + v1011:0:0 The following rules are bounded: f_654(v909:0:0, v916:0:0, v917:0:0, sum~cons_1~v1011:0:0) -> f_654(v909:0:0, 1 + v916:0:0, 1 + v1011:0:0, v1011:0:0) :|: v909:0:0 > 1 && v1011:0:0 > -1 && v916:0:0 > 0 && v917:0:0 > 1 && sum~cons_1~v1011:0:0 = 1 + v1011:0:0 ---------------------------------------- (13) YES ---------------------------------------- (14) Obligation: SCC ---------------------------------------- (15) SCC2IRS (SOUND) Transformed LLVM symbolic execution graph SCC into a rewrite problem. Log: Generated rules. Obtained 24 rulesP rules: f_598(v799, v800, v801, v802, v803, 0, v805, 1, v807, v808, v809, v810, v811, v812, v813, v814, 3, 4) -> f_600(v799, v800, v801, v802, v803, 0, v805, 1, v807, v808, v809, v810, v811, v812, v813, v814, 3, 4) :|: 0 = 0 f_600(v799, v800, v801, v802, v803, 0, v805, 1, v807, v808, v809, v810, v811, v812, v813, v814, 3, 4) -> f_602(v799, v800, v801, v802, v803, 0, v805, 1, v807, v808, v809, v810, v811, v812, v813, v814, 3, 4) :|: TRUE f_602(v799, v800, v801, v802, v803, 0, v805, 1, v807, v808, v809, v810, v811, v812, v813, v814, 3, 4) -> f_604(v799, v800, v801, v802, v803, 0, v807, 1, v805, v808, v809, v810, v811, v812, v813, v814, 3, 4) :|: 0 = 0 f_604(v799, v800, v801, v802, v803, 0, v807, 1, v805, v808, v809, v810, v811, v812, v813, v814, 3, 4) -> f_606(v799, v800, v801, v802, v803, 0, v807, 1, v805, v808, v809, v810, v811, v812, v813, v814, 3, 2, 4) :|: 0 < v807 && 2 <= v805 && 2 <= v800 f_606(v799, v800, v801, v802, v803, 0, v807, 1, v805, v808, v809, v810, v811, v812, v813, v814, 3, 2, 4) -> f_609(v799, v800, v801, v802, v803, 0, v807, 1, v805, v808, v809, v810, v811, v812, v813, v814, 3, 2, 4) :|: 0 = 0 f_609(v799, v800, v801, v802, v803, 0, v807, 1, v805, v808, v809, v810, v811, v812, v813, v814, 3, 2, 4) -> f_612(v799, v800, v801, v802, v803, 0, v807, 1, v805, v808, v809, v810, v811, v812, v813, v814, 3, 2, 4) :|: 0 = 0 f_612(v799, v800, v801, v802, v803, 0, v807, 1, v805, v808, v809, v810, v811, v812, v813, v814, 3, 2, 4) -> f_615(v799, v800, v801, v802, v803, 0, v807, 1, v805, v808, v809, v810, v811, v812, v813, v814, 3, 2, 4) :|: TRUE f_615(v799, v800, v801, v802, v803, 0, v807, 1, v805, v808, v809, v810, v811, v812, v813, v814, 3, 2, 4) -> f_619(v799, v800, v801, v802, v803, 0, v807, 1, v805, v808, v809, v810, v811, v812, v813, v814, 3, 2, 4) :|: 0 = 0 f_619(v799, v800, v801, v802, v803, 0, v807, 1, v805, v808, v809, v810, v811, v812, v813, v814, 3, 2, 4) -> f_623(v799, v800, v801, v802, v803, 0, v807, 1, v805, v808, v809, v810, v811, v812, v813, v814, 3, 2, 4) :|: 0 = 0 f_623(v799, v800, v801, v802, v803, 0, v807, 1, v805, v808, v809, v810, v811, v812, v813, v814, 3, 2, 4) -> f_627(v799, v800, v801, v802, v803, 0, v807, 1, v805, v808, v809, v810, v811, v812, v813, v814, 3, 2, 4) :|: TRUE f_627(v799, v800, v801, v802, v803, 0, v807, 1, v805, v808, v809, v810, v811, v812, v813, v814, 3, 2, 4) -> f_630(v799, v800, v801, v802, v803, 0, v807, 1, v805, v808, v809, v810, v811, v812, v813, v814, 3, 2, 4) :|: 0 = 0 f_630(v799, v800, v801, v802, v803, 0, v807, 1, v805, v808, v809, v810, v811, v812, v813, v814, 3, 2, 4) -> f_633(v799, v800, v801, v802, v803, 0, v807, 1, v805, v808, v809, v810, v811, v812, v813, v814, 3, 2, 4) :|: 0 = 0 f_633(v799, v800, v801, v802, v803, 0, v807, 1, v805, v808, v809, v810, v811, v812, v813, v814, 3, 2, 4) -> f_636(v799, v800, v801, v802, v803, 0, v807, 1, v805, v808, v809, v810, v811, v812, v813, v814, 3, 2, 4) :|: TRUE f_636(v799, v800, v801, v802, v803, 0, v807, 1, v805, v808, v809, v810, v811, v812, v813, v814, 3, 2, 4) -> f_638(v799, v800, v801, v802, v803, 0, v807, 1, v808, v809, v810, v811, v812, v813, v814, 3, 2, 4) :|: 0 = 0 f_638(v799, v800, v801, v802, v803, 0, v807, 1, v808, v809, v810, v811, v812, v813, v814, 3, 2, 4) -> f_640(v799, v800, v801, v802, v803, 0, v807, 1, v886, v808, v809, v810, v811, v812, v813, v814, 3, 2, 4) :|: 1 + v886 = v807 && 0 <= v886 f_640(v799, v800, v801, v802, v803, 0, v807, 1, v886, v808, v809, v810, v811, v812, v813, v814, 3, 2, 4) -> f_642(v799, v800, v801, v802, v803, 0, v807, 1, v886, v808, v809, v810, v811, v812, v813, v814, 3, 2, 4) :|: TRUE f_642(v799, v800, v801, v802, v803, 0, v807, 1, v886, v808, v809, v810, v811, v812, v813, v814, 3, 2, 4) -> f_644(v799, v800, v801, v802, v803, 0, v807, 1, v886, v808, v809, v810, v811, v812, v813, v814, 3, 2, 4) :|: TRUE f_644(v799, v800, v801, v802, v803, 0, v807, 1, v886, v808, v809, v810, v811, v812, v813, v814, 3, 2, 4) -> f_646(v799, v800, v801, v802, v803, 0, v807, 1, v886, v808, v809, v810, v811, v812, v813, v814, 3, 2, 4) :|: TRUE f_646(v799, v800, v801, v802, v803, 0, v807, 1, v886, v808, v809, v810, v811, v812, v813, v814, 3, 2, 4) -> f_648(v799, v800, v801, v802, v803, 0, v807, 1, v886, v809, v810, v811, v812, v813, v814, 3, 2, 4) :|: 0 = 0 f_648(v799, v800, v801, v802, v803, 0, v807, 1, v886, v809, v810, v811, v812, v813, v814, 3, 2, 4) -> f_650(v799, v800, v801, v802, v803, 0, v807, 1, v886, v809, v907, v810, v811, v812, v813, v814, 3, 2, 4) :|: v907 = 1 + v809 && 2 <= v907 f_650(v799, v800, v801, v802, v803, 0, v807, 1, v886, v809, v907, v810, v811, v812, v813, v814, 3, 2, 4) -> f_653(v799, v800, v801, v802, v803, 0, v807, 1, v886, v809, v907, v810, v811, v812, v813, v814, 3, 2, 4) :|: TRUE f_653(v799, v800, v801, v802, v803, 0, v807, 1, v886, v809, v907, v810, v811, v812, v813, v814, 3, 2, 4) -> f_655(v799, v800, v801, v802, v803, 0, v807, 1, v886, v809, v907, v810, v811, v812, v813, v814, 3, 2, 4) :|: TRUE f_655(v799, v800, v801, v802, v803, 0, v807, 1, v886, v809, v907, v810, v811, v812, v813, v814, 3, 2, 4) -> f_596(v799, v800, v801, v802, v803, 0, v807, 1, v886, v809, v907, v810, v811, v812, v813, v814, 3, 4) :|: TRUE f_596(v799, v800, v801, v802, v803, 0, v805, 1, v807, v808, v809, v810, v811, v812, v813, v814, 3, 4) -> f_598(v799, v800, v801, v802, v803, 0, v805, 1, v807, v808, v809, v810, v811, v812, v813, v814, 3, 4) :|: 0 = 0 Combined rules. Obtained 1 rulesP rules: f_598(v799:0, v800:0, v801:0, v802:0, v803:0, 0, v805:0, 1, 1 + v886:0, v808:0, v809:0, v810:0, v811:0, v812:0, v813:0, v814:0, 3, 4) -> f_598(v799:0, v800:0, v801:0, v802:0, v803:0, 0, 1 + v886:0, 1, v886:0, v809:0, 1 + v809:0, v810:0, v811:0, v812:0, v813:0, v814:0, 3, 4) :|: v805:0 > 1 && v886:0 > -1 && v800:0 > 1 && v809:0 > 0 Filtered unneeded arguments: f_598(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18) -> f_598(x2, x7, x9, x11) Removed division, modulo operations, cleaned up constraints. Obtained 1 rules.P rules: f_598(v800:0, v805:0, sum~cons_1~v886:0, v809:0) -> f_598(v800:0, 1 + v886:0, v886:0, 1 + v809:0) :|: v886:0 > -1 && v805:0 > 1 && v809:0 > 0 && v800:0 > 1 && sum~cons_1~v886:0 = 1 + v886:0 ---------------------------------------- (16) Obligation: Rules: f_598(v800:0, v805:0, sum~cons_1~v886:0, v809:0) -> f_598(v800:0, 1 + v886:0, v886:0, 1 + v809:0) :|: v886:0 > -1 && v805:0 > 1 && v809:0 > 0 && v800:0 > 1 && sum~cons_1~v886:0 = 1 + v886:0 ---------------------------------------- (17) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (18) Obligation: Rules: f_598(v800:0:0, v805:0:0, sum~cons_1~v886:0:0, v809:0:0) -> f_598(v800:0:0, 1 + v886:0:0, v886:0:0, 1 + v809:0:0) :|: v809:0:0 > 0 && v800:0:0 > 1 && v805:0:0 > 1 && v886:0:0 > -1 && sum~cons_1~v886:0:0 = 1 + v886:0:0 ---------------------------------------- (19) RankingReductionPairProof (EQUIVALENT) Interpretation: [ f_598 ] = f_598_3 The following rules are decreasing: f_598(v800:0:0, v805:0:0, sum~cons_1~v886:0:0, v809:0:0) -> f_598(v800:0:0, 1 + v886:0:0, v886:0:0, 1 + v809:0:0) :|: v809:0:0 > 0 && v800:0:0 > 1 && v805:0:0 > 1 && v886:0:0 > -1 && sum~cons_1~v886:0:0 = 1 + v886:0:0 The following rules are bounded: f_598(v800:0:0, v805:0:0, sum~cons_1~v886:0:0, v809:0:0) -> f_598(v800:0:0, 1 + v886:0:0, v886:0:0, 1 + v809:0:0) :|: v809:0:0 > 0 && v800:0:0 > 1 && v805:0:0 > 1 && v886:0:0 > -1 && sum~cons_1~v886:0:0 = 1 + v886:0:0 ---------------------------------------- (20) YES ---------------------------------------- (21) Obligation: SCC ---------------------------------------- (22) SCC2IRS (SOUND) Transformed LLVM symbolic execution graph SCC into a rewrite problem. Log: Generated rules. Obtained 17 rulesP rules: f_469(v359, v360, v361, v362, v363, v366, 1, v364, v367, v368, v369, v370, v371, v372, v373, 0, 3, 4) -> f_471(v359, v360, v361, v362, v363, v366, 1, v364, v367, v368, v369, v370, v371, v372, v373, 0, 3, 2, 4) :|: 0 < v366 && 2 <= v364 && 2 <= v359 f_471(v359, v360, v361, v362, v363, v366, 1, v364, v367, v368, v369, v370, v371, v372, v373, 0, 3, 2, 4) -> f_475(v359, v360, v361, v362, v363, v366, 1, v364, v367, v368, v369, v370, v371, v372, v373, 0, 3, 2, 4) :|: 0 = 0 f_475(v359, v360, v361, v362, v363, v366, 1, v364, v367, v368, v369, v370, v371, v372, v373, 0, 3, 2, 4) -> f_479(v359, v360, v361, v362, v363, v366, 1, v364, v367, v368, v369, v370, v371, v372, v373, 0, 3, 2, 4) :|: 0 = 0 f_479(v359, v360, v361, v362, v363, v366, 1, v364, v367, v368, v369, v370, v371, v372, v373, 0, 3, 2, 4) -> f_483(v359, v360, v361, v362, v363, v366, 1, v364, v367, v368, v369, v370, v371, v372, v373, 0, 3, 2, 4) :|: TRUE f_483(v359, v360, v361, v362, v363, v366, 1, v364, v367, v368, v369, v370, v371, v372, v373, 0, 3, 2, 4) -> f_487(v359, v360, v361, v362, v363, v366, 1, v364, v367, v368, v369, v370, v371, v372, v373, 0, 3, 2, 4) :|: 0 = 0 f_487(v359, v360, v361, v362, v363, v366, 1, v364, v367, v368, v369, v370, v371, v372, v373, 0, 3, 2, 4) -> f_492(v359, v360, v361, v362, v363, v366, 1, v364, v367, v368, v369, v370, v371, v372, v373, 0, 3, 2, 4) :|: 0 = 0 f_492(v359, v360, v361, v362, v363, v366, 1, v364, v367, v368, v369, v370, v371, v372, v373, 0, 3, 2, 4) -> f_497(v359, v360, v361, v362, v363, v366, 1, v364, v367, v368, v369, v370, v371, v372, v373, 0, 3, 2, 4) :|: TRUE f_497(v359, v360, v361, v362, v363, v366, 1, v364, v367, v368, v369, v370, v371, v372, v373, 0, 3, 2, 4) -> f_501(v359, v360, v361, v362, v363, v366, 1, v367, v368, v369, v370, v371, v372, v373, 0, 3, 2, 4) :|: 0 = 0 f_501(v359, v360, v361, v362, v363, v366, 1, v367, v368, v369, v370, v371, v372, v373, 0, 3, 2, 4) -> f_505(v359, v360, v361, v362, v363, v366, 1, v405, v367, v368, v369, v370, v371, v372, v373, 0, 3, 2, 4) :|: 1 + v405 = v366 && 0 <= v405 f_505(v359, v360, v361, v362, v363, v366, 1, v405, v367, v368, v369, v370, v371, v372, v373, 0, 3, 2, 4) -> f_509(v359, v360, v361, v362, v363, v366, 1, v405, v367, v368, v369, v370, v371, v372, v373, 0, 3, 2, 4) :|: TRUE f_509(v359, v360, v361, v362, v363, v366, 1, v405, v367, v368, v369, v370, v371, v372, v373, 0, 3, 2, 4) -> f_513(v359, v360, v361, v362, v363, v366, 1, v405, v367, v368, v369, v370, v371, v372, v373, 0, 3, 2, 4) :|: TRUE f_513(v359, v360, v361, v362, v363, v366, 1, v405, v367, v368, v369, v370, v371, v372, v373, 0, 3, 2, 4) -> f_516(v359, v360, v361, v362, v363, v366, 1, v405, v368, v369, v370, v371, v372, v373, 0, 3, 2, 4) :|: 0 = 0 f_516(v359, v360, v361, v362, v363, v366, 1, v405, v368, v369, v370, v371, v372, v373, 0, 3, 2, 4) -> f_519(v359, v360, v361, v362, v363, v366, 1, v405, v368, v408, v369, v370, v371, v372, v373, 0, 3, 2, 4) :|: v408 = 1 + v368 && 2 <= v408 f_519(v359, v360, v361, v362, v363, v366, 1, v405, v368, v408, v369, v370, v371, v372, v373, 0, 3, 2, 4) -> f_522(v359, v360, v361, v362, v363, v366, 1, v405, v368, v408, v369, v370, v371, v372, v373, 0, 3, 2, 4) :|: TRUE f_522(v359, v360, v361, v362, v363, v366, 1, v405, v368, v408, v369, v370, v371, v372, v373, 0, 3, 2, 4) -> f_525(v359, v360, v361, v362, v363, v366, 1, v405, v368, v408, v369, v370, v371, v372, v373, 0, 3, 2, 4) :|: TRUE f_525(v359, v360, v361, v362, v363, v366, 1, v405, v368, v408, v369, v370, v371, v372, v373, 0, 3, 2, 4) -> f_467(v359, v360, v361, v362, v363, v366, 1, v405, v368, v408, v369, v370, v371, v372, v373, 0, 3, 4) :|: TRUE f_467(v359, v360, v361, v362, v363, v364, 1, v366, v367, v368, v369, v370, v371, v372, v373, 0, 3, 4) -> f_469(v359, v360, v361, v362, v363, v366, 1, v364, v367, v368, v369, v370, v371, v372, v373, 0, 3, 4) :|: 0 = 0 Combined rules. Obtained 1 rulesP rules: f_469(v359:0, v360:0, v361:0, v362:0, v363:0, 1 + v405:0, 1, v364:0, v367:0, v368:0, v369:0, v370:0, v371:0, v372:0, v373:0, 0, 3, 4) -> f_469(v359:0, v360:0, v361:0, v362:0, v363:0, v405:0, 1, 1 + v405:0, v368:0, 1 + v368:0, v369:0, v370:0, v371:0, v372:0, v373:0, 0, 3, 4) :|: v364:0 > 1 && v405:0 > -1 && v359:0 > 1 && v368:0 > 0 Filtered unneeded arguments: f_469(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18) -> f_469(x1, x6, x8, x10) Removed division, modulo operations, cleaned up constraints. Obtained 1 rules.P rules: f_469(v359:0, sum~cons_1~v405:0, v364:0, v368:0) -> f_469(v359:0, v405:0, 1 + v405:0, 1 + v368:0) :|: v405:0 > -1 && v364:0 > 1 && v368:0 > 0 && v359:0 > 1 && sum~cons_1~v405:0 = 1 + v405:0 ---------------------------------------- (23) Obligation: Rules: f_469(v359:0, sum~cons_1~v405:0, v364:0, v368:0) -> f_469(v359:0, v405:0, 1 + v405:0, 1 + v368:0) :|: v405:0 > -1 && v364:0 > 1 && v368:0 > 0 && v359:0 > 1 && sum~cons_1~v405:0 = 1 + v405:0 ---------------------------------------- (24) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (25) Obligation: Rules: f_469(v359:0:0, sum~cons_1~v405:0:0, v364:0:0, v368:0:0) -> f_469(v359:0:0, v405:0:0, 1 + v405:0:0, 1 + v368:0:0) :|: v368:0:0 > 0 && v359:0:0 > 1 && v364:0:0 > 1 && v405:0:0 > -1 && sum~cons_1~v405:0:0 = 1 + v405:0:0 ---------------------------------------- (26) RankingReductionPairProof (EQUIVALENT) Interpretation: [ f_469 ] = f_469_2 The following rules are decreasing: f_469(v359:0:0, sum~cons_1~v405:0:0, v364:0:0, v368:0:0) -> f_469(v359:0:0, v405:0:0, 1 + v405:0:0, 1 + v368:0:0) :|: v368:0:0 > 0 && v359:0:0 > 1 && v364:0:0 > 1 && v405:0:0 > -1 && sum~cons_1~v405:0:0 = 1 + v405:0:0 The following rules are bounded: f_469(v359:0:0, sum~cons_1~v405:0:0, v364:0:0, v368:0:0) -> f_469(v359:0:0, v405:0:0, 1 + v405:0:0, 1 + v368:0:0) :|: v368:0:0 > 0 && v359:0:0 > 1 && v364:0:0 > 1 && v405:0:0 > -1 && sum~cons_1~v405:0:0 = 1 + v405:0:0 ---------------------------------------- (27) YES