/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, 174 ms] (2) LLVM problem (3) LLVMToTerminationGraphProof [EQUIVALENT, 8371 ms] (4) LLVM Symbolic Execution Graph (5) SymbolicExecutionGraphToSCCProof [SOUND, 2 ms] (6) AND (7) LLVM Symbolic Execution SCC (8) SCC2IRS [SOUND, 59 ms] (9) IntTRS (10) IntTRSCompressionProof [EQUIVALENT, 0 ms] (11) IntTRS (12) PolynomialOrderProcessor [EQUIVALENT, 0 ms] (13) YES (14) LLVM Symbolic Execution SCC (15) SCC2IRS [SOUND, 83 ms] (16) IntTRS (17) IntTRSCompressionProof [EQUIVALENT, 0 ms] (18) IntTRS (19) RankingReductionPairProof [EQUIVALENT, 0 ms] (20) YES (21) LLVM Symbolic Execution SCC (22) SCC2IRS [SOUND, 111 ms] (23) IntTRS (24) IntTRSCompressionProof [EQUIVALENT, 0 ms] (25) IntTRS (26) RankingReductionPairProof [EQUIVALENT, 26 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 %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, %41 18: br %19 19: %20 = load %y_ref %21 = load %20 %22 = icmp sgt %21 0 br %22, %23, %32 23: %24 = load %y_ref %25 = load %24 %26 = sub %25 1 %27 = load %y_ref store %26, %27 %28 = load %c %29 = load %28 %30 = add %29 1 %31 = load %c store %30, %31 br %19 32: %33 = load %x_ref %34 = load %33 %35 = sub %34 1 %36 = load %x_ref store %35, %36 %37 = load %c %38 = load %37 %39 = add %38 1 %40 = load %c store %39, %40 br %14 41: %42 = load %c %43 = load %42 ret %43 *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 22 rulesP rules: f_733(v717, v718, v719, v720, v721, v722, v723, v724, v725, v726, v727, 1, 0, v730, v731, v732, v733, v734, v735, v736, v737, v738, v739, v740, v741, v742, v743, v744, 3, 7, 2, 4, 8) -> f_734(v717, v718, v719, v720, v721, v722, v723, v724, v725, v726, v732, 1, 0, v730, v731, v727, v733, v734, v735, v736, v737, v738, v739, v740, v741, v742, v743, v744, 3, 7, 2, 4, 8) :|: 0 = 0 f_734(v717, v718, v719, v720, v721, v722, v723, v724, v725, v726, v732, 1, 0, v730, v731, v727, v733, v734, v735, v736, v737, v738, v739, v740, v741, v742, v743, v744, 3, 7, 2, 4, 8) -> f_735(v717, v718, v719, v720, v721, v722, v723, v724, v725, v726, v732, 1, 0, v730, v731, v727, v733, v734, v735, v736, v737, v738, v739, v740, v741, v742, v743, v744, 3, 7, 2, 4, 8) :|: 0 < v732 && 2 <= v727 && 2 <= v717 f_735(v717, v718, v719, v720, v721, v722, v723, v724, v725, v726, v732, 1, 0, v730, v731, v727, v733, v734, v735, v736, v737, v738, v739, v740, v741, v742, v743, v744, 3, 7, 2, 4, 8) -> f_737(v717, v718, v719, v720, v721, v722, v723, v724, v725, v726, v732, 1, 0, v730, v731, v727, v733, v734, v735, v736, v737, v738, v739, v740, v741, v742, v743, v744, 3, 7, 2, 4, 8) :|: 0 = 0 f_737(v717, v718, v719, v720, v721, v722, v723, v724, v725, v726, v732, 1, 0, v730, v731, v727, v733, v734, v735, v736, v737, v738, v739, v740, v741, v742, v743, v744, 3, 7, 2, 4, 8) -> f_739(v717, v718, v719, v720, v721, v722, v723, v724, v725, v726, v732, 1, 0, v730, v731, v727, v733, v734, v735, v736, v737, v738, v739, v740, v741, v742, v743, v744, 3, 7, 2, 4, 8) :|: TRUE f_739(v717, v718, v719, v720, v721, v722, v723, v724, v725, v726, v732, 1, 0, v730, v731, v727, v733, v734, v735, v736, v737, v738, v739, v740, v741, v742, v743, v744, 3, 7, 2, 4, 8) -> f_741(v717, v718, v719, v720, v721, v722, v723, v724, v725, v726, v732, 1, 0, v730, v731, v727, v733, v734, v735, v736, v737, v738, v739, v740, v741, v742, v743, v744, 3, 7, 2, 4, 8) :|: TRUE f_741(v717, v718, v719, v720, v721, v722, v723, v724, v725, v726, v732, 1, 0, v730, v731, v727, v733, v734, v735, v736, v737, v738, v739, v740, v741, v742, v743, v744, 3, 7, 2, 4, 8) -> f_743(v717, v718, v719, v720, v721, v722, v723, v724, v725, v726, v732, 1, 0, v730, v731, v727, v733, v734, v735, v736, v737, v738, v739, v740, v741, v742, v743, v744, 3, 7, 2, 4, 8) :|: 0 = 0 f_743(v717, v718, v719, v720, v721, v722, v723, v724, v725, v726, v732, 1, 0, v730, v731, v727, v733, v734, v735, v736, v737, v738, v739, v740, v741, v742, v743, v744, 3, 7, 2, 4, 8) -> f_745(v717, v718, v719, v720, v721, v722, v723, v724, v725, v726, v732, 1, 0, v730, v731, v727, v733, v734, v735, v736, v737, v738, v739, v740, v741, v742, v743, v744, 3, 7, 2, 4, 8) :|: 0 = 0 f_745(v717, v718, v719, v720, v721, v722, v723, v724, v725, v726, v732, 1, 0, v730, v731, v727, v733, v734, v735, v736, v737, v738, v739, v740, v741, v742, v743, v744, 3, 7, 2, 4, 8) -> f_747(v717, v718, v719, v720, v721, v722, v723, v724, v725, v726, v732, 1, 0, v730, v731, v727, v733, v734, v735, v736, v737, v738, v739, v740, v741, v742, v743, v744, 3, 7, 2, 4, 8) :|: 0 = 0 f_747(v717, v718, v719, v720, v721, v722, v723, v724, v725, v726, v732, 1, 0, v730, v731, v727, v733, v734, v735, v736, v737, v738, v739, v740, v741, v742, v743, v744, 3, 7, 2, 4, 8) -> f_748(v717, v718, v719, v720, v721, v722, v723, v724, v725, v726, v732, 1, 0, v730, v731, v727, v733, v734, v735, v736, v737, v738, v739, v740, v741, v742, v743, v744, 3, 7, 2, 4, 8) :|: TRUE f_748(v717, v718, v719, v720, v721, v722, v723, v724, v725, v726, v732, 1, 0, v730, v731, v727, v733, v734, v735, v736, v737, v738, v739, v740, v741, v742, v743, v744, 3, 7, 2, 4, 8) -> f_749(v717, v718, v719, v720, v721, v722, v723, v724, v725, v726, v732, 1, 0, v730, v731, v727, v733, v734, v735, v736, v737, v738, v739, v740, v741, v742, v743, v744, 3, 7, 2, 4, 8) :|: 0 = 0 f_749(v717, v718, v719, v720, v721, v722, v723, v724, v725, v726, v732, 1, 0, v730, v731, v727, v733, v734, v735, v736, v737, v738, v739, v740, v741, v742, v743, v744, 3, 7, 2, 4, 8) -> f_750(v717, v718, v719, v720, v721, v722, v723, v724, v725, v726, v732, 1, 0, v730, v731, v733, v734, v735, v736, v737, v738, v739, v740, v741, v742, v743, v744, 3, 7, 2, 4, 8) :|: 0 = 0 f_750(v717, v718, v719, v720, v721, v722, v723, v724, v725, v726, v732, 1, 0, v730, v731, v733, v734, v735, v736, v737, v738, v739, v740, v741, v742, v743, v744, 3, 7, 2, 4, 8) -> f_751(v717, v718, v719, v720, v721, v722, v723, v724, v725, v726, v732, 1, 0, v730, v731, v771, v733, v734, v735, v736, v737, v738, v739, v740, v741, v742, v743, v744, 3, 7, 2, 4, 8) :|: 1 + v771 = v732 && 0 <= v771 f_751(v717, v718, v719, v720, v721, v722, v723, v724, v725, v726, v732, 1, 0, v730, v731, v771, v733, v734, v735, v736, v737, v738, v739, v740, v741, v742, v743, v744, 3, 7, 2, 4, 8) -> f_752(v717, v718, v719, v720, v721, v722, v723, v724, v725, v726, v732, 1, 0, v730, v731, v771, v733, v734, v735, v736, v737, v738, v739, v740, v741, v742, v743, v744, 3, 7, 2, 4, 8) :|: 0 = 0 f_752(v717, v718, v719, v720, v721, v722, v723, v724, v725, v726, v732, 1, 0, v730, v731, v771, v733, v734, v735, v736, v737, v738, v739, v740, v741, v742, v743, v744, 3, 7, 2, 4, 8) -> f_753(v717, v718, v719, v720, v721, v722, v723, v724, v725, v726, v732, 1, 0, v730, v731, v771, v733, v734, v735, v736, v737, v738, v739, v740, v741, v742, v743, v744, 3, 7, 2, 4, 8) :|: TRUE f_753(v717, v718, v719, v720, v721, v722, v723, v724, v725, v726, v732, 1, 0, v730, v731, v771, v733, v734, v735, v736, v737, v738, v739, v740, v741, v742, v743, v744, 3, 7, 2, 4, 8) -> f_754(v717, v718, v719, v720, v721, v722, v723, v724, v725, v726, v732, 1, 0, v730, v731, v771, v733, v734, v735, v736, v737, v738, v739, v740, v741, v742, v743, v744, 3, 7, 2, 4, 8) :|: 0 = 0 f_754(v717, v718, v719, v720, v721, v722, v723, v724, v725, v726, v732, 1, 0, v730, v731, v771, v733, v734, v735, v736, v737, v738, v739, v740, v741, v742, v743, v744, 3, 7, 2, 4, 8) -> f_755(v717, v718, v719, v720, v721, v722, v723, v724, v725, v726, v732, 1, 0, v730, v731, v771, v734, v735, v736, v737, v738, v739, v740, v741, v742, v743, v744, 3, 7, 2, 4, 8) :|: 0 = 0 f_755(v717, v718, v719, v720, v721, v722, v723, v724, v725, v726, v732, 1, 0, v730, v731, v771, v734, v735, v736, v737, v738, v739, v740, v741, v742, v743, v744, 3, 7, 2, 4, 8) -> f_756(v717, v718, v719, v720, v721, v722, v723, v724, v725, v726, v732, 1, 0, v730, v731, v771, v734, v773, v735, v736, v737, v738, v739, v740, v741, v742, v743, v744, 3, 7, 2, 4, 8) :|: v773 = 1 + v734 && 3 <= v773 f_756(v717, v718, v719, v720, v721, v722, v723, v724, v725, v726, v732, 1, 0, v730, v731, v771, v734, v773, v735, v736, v737, v738, v739, v740, v741, v742, v743, v744, 3, 7, 2, 4, 8) -> f_757(v717, v718, v719, v720, v721, v722, v723, v724, v725, v726, v732, 1, 0, v730, v731, v771, v734, v773, v735, v736, v737, v738, v739, v740, v741, v742, v743, v744, 3, 7, 2, 4, 8) :|: 0 = 0 f_757(v717, v718, v719, v720, v721, v722, v723, v724, v725, v726, v732, 1, 0, v730, v731, v771, v734, v773, v735, v736, v737, v738, v739, v740, v741, v742, v743, v744, 3, 7, 2, 4, 8) -> f_758(v717, v718, v719, v720, v721, v722, v723, v724, v725, v726, v732, 1, 0, v730, v731, v771, v734, v773, v735, v736, v737, v738, v739, v740, v741, v742, v743, v744, 3, 7, 2, 4, 8) :|: TRUE f_758(v717, v718, v719, v720, v721, v722, v723, v724, v725, v726, v732, 1, 0, v730, v731, v771, v734, v773, v735, v736, v737, v738, v739, v740, v741, v742, v743, v744, 3, 7, 2, 4, 8) -> f_759(v717, v718, v719, v720, v721, v722, v723, v724, v725, v726, v732, 1, 0, v730, v731, v771, v734, v773, v735, v736, v737, v738, v739, v740, v741, v742, v743, v744, 3, 7, 2, 4, 8) :|: TRUE f_759(v717, v718, v719, v720, v721, v722, v723, v724, v725, v726, v732, 1, 0, v730, v731, v771, v734, v773, v735, v736, v737, v738, v739, v740, v741, v742, v743, v744, 3, 7, 2, 4, 8) -> f_732(v717, v718, v719, v720, v721, v722, v723, v724, v725, v726, v732, 1, 0, v730, v731, v771, v734, v773, v735, v736, v737, v738, v739, v740, v741, v742, v743, v744, 3, 7, 2, 4, 8) :|: TRUE f_732(v717, v718, v719, v720, v721, v722, v723, v724, v725, v726, v727, 1, 0, v730, v731, v732, v733, v734, v735, v736, v737, v738, v739, v740, v741, v742, v743, v744, 3, 7, 2, 4, 8) -> f_733(v717, v718, v719, v720, v721, v722, v723, v724, v725, v726, v727, 1, 0, v730, v731, v732, v733, v734, v735, v736, v737, v738, v739, v740, v741, v742, v743, v744, 3, 7, 2, 4, 8) :|: 0 = 0 Combined rules. Obtained 1 rulesP rules: f_733(v717:0, v718:0, v719:0, v720:0, v721:0, v722:0, v723:0, v724:0, v725:0, v726:0, v727:0, 1, 0, v730:0, v731:0, 1 + v771:0, v733:0, v734:0, v735:0, v736:0, v737:0, v738:0, v739:0, v740:0, v741:0, v742:0, v743:0, v744:0, 3, 7, 2, 4, 8) -> f_733(v717:0, v718:0, v719:0, v720:0, v721:0, v722:0, v723:0, v724:0, v725:0, v726:0, 1 + v771:0, 1, 0, v730:0, v731:0, v771:0, v734:0, 1 + v734:0, v735:0, v736:0, v737:0, v738:0, v739:0, v740:0, v741:0, v742:0, v743:0, v744:0, 3, 7, 2, 4, 8) :|: v727:0 > 1 && v771:0 > -1 && v717:0 > 1 && v734:0 > 1 Filtered unneeded arguments: f_733(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) -> f_733(x1, x11, x16, x18) Removed division, modulo operations, cleaned up constraints. Obtained 1 rules.P rules: f_733(v717:0, v727:0, sum~cons_1~v771:0, v734:0) -> f_733(v717:0, 1 + v771:0, v771:0, 1 + v734:0) :|: v771:0 > -1 && v727:0 > 1 && v734:0 > 1 && v717:0 > 1 && sum~cons_1~v771:0 = 1 + v771:0 ---------------------------------------- (9) Obligation: Rules: f_733(v717:0, v727:0, sum~cons_1~v771:0, v734:0) -> f_733(v717:0, 1 + v771:0, v771:0, 1 + v734:0) :|: v771:0 > -1 && v727:0 > 1 && v734:0 > 1 && v717:0 > 1 && sum~cons_1~v771:0 = 1 + v771:0 ---------------------------------------- (10) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (11) Obligation: Rules: f_733(v717:0:0, v727:0:0, sum~cons_1~v771:0:0, v734:0:0) -> f_733(v717:0:0, 1 + v771:0:0, v771:0:0, 1 + v734:0:0) :|: v734:0:0 > 1 && v717:0:0 > 1 && v727:0:0 > 1 && v771:0:0 > -1 && sum~cons_1~v771:0:0 = 1 + v771:0:0 ---------------------------------------- (12) PolynomialOrderProcessor (EQUIVALENT) Found the following polynomial interpretation: [f_733(x, x1, x2, x3)] = x2 The following rules are decreasing: f_733(v717:0:0, v727:0:0, sum~cons_1~v771:0:0, v734:0:0) -> f_733(v717:0:0, 1 + v771:0:0, v771:0:0, 1 + v734:0:0) :|: v734:0:0 > 1 && v717:0:0 > 1 && v727:0:0 > 1 && v771:0:0 > -1 && sum~cons_1~v771:0:0 = 1 + v771:0:0 The following rules are bounded: f_733(v717:0:0, v727:0:0, sum~cons_1~v771:0:0, v734:0:0) -> f_733(v717:0:0, 1 + v771:0:0, v771:0:0, 1 + v734:0:0) :|: v734:0:0 > 1 && v717:0:0 > 1 && v727:0:0 > 1 && v771:0:0 > -1 && sum~cons_1~v771:0:0 = 1 + v771:0:0 ---------------------------------------- (13) YES ---------------------------------------- (14) Obligation: SCC ---------------------------------------- (15) SCC2IRS (SOUND) Transformed LLVM symbolic execution graph SCC into a rewrite problem. Log: Generated rules. Obtained 22 rulesP rules: f_671(v547, v548, v549, v550, v551, v552, v553, v554, v555, v556, v557, 1, 0, v560, v561, v562, v563, v564, v565, v566, v567, v568, v569, v570, v571, v572, 3, 7, 4, 8) -> f_673(v547, v548, v549, v550, v551, v552, v553, v554, v555, v556, v560, 1, 0, v557, v561, v562, v563, v564, v565, v566, v567, v568, v569, v570, v571, v572, 3, 7, 4, 8) :|: 0 = 0 f_673(v547, v548, v549, v550, v551, v552, v553, v554, v555, v556, v560, 1, 0, v557, v561, v562, v563, v564, v565, v566, v567, v568, v569, v570, v571, v572, 3, 7, 4, 8) -> f_675(v547, v548, v549, v550, v551, v552, v553, v554, v555, v556, v560, 1, 0, v557, v561, v562, v563, v564, v565, v566, v567, v568, v569, v570, v571, v572, 3, 7, 2, 4, 8) :|: 0 < v560 && 2 <= v557 && 2 <= v547 f_675(v547, v548, v549, v550, v551, v552, v553, v554, v555, v556, v560, 1, 0, v557, v561, v562, v563, v564, v565, v566, v567, v568, v569, v570, v571, v572, 3, 7, 2, 4, 8) -> f_678(v547, v548, v549, v550, v551, v552, v553, v554, v555, v556, v560, 1, 0, v557, v561, v562, v563, v564, v565, v566, v567, v568, v569, v570, v571, v572, 3, 7, 2, 4, 8) :|: 0 = 0 f_678(v547, v548, v549, v550, v551, v552, v553, v554, v555, v556, v560, 1, 0, v557, v561, v562, v563, v564, v565, v566, v567, v568, v569, v570, v571, v572, 3, 7, 2, 4, 8) -> f_681(v547, v548, v549, v550, v551, v552, v553, v554, v555, v556, v560, 1, 0, v557, v561, v562, v563, v564, v565, v566, v567, v568, v569, v570, v571, v572, 3, 7, 2, 4, 8) :|: TRUE f_681(v547, v548, v549, v550, v551, v552, v553, v554, v555, v556, v560, 1, 0, v557, v561, v562, v563, v564, v565, v566, v567, v568, v569, v570, v571, v572, 3, 7, 2, 4, 8) -> f_684(v547, v548, v549, v550, v551, v552, v553, v554, v555, v556, v560, 1, 0, v557, v561, v562, v563, v564, v565, v566, v567, v568, v569, v570, v571, v572, 3, 7, 2, 4, 8) :|: TRUE f_684(v547, v548, v549, v550, v551, v552, v553, v554, v555, v556, v560, 1, 0, v557, v561, v562, v563, v564, v565, v566, v567, v568, v569, v570, v571, v572, 3, 7, 2, 4, 8) -> f_688(v547, v548, v549, v550, v551, v552, v553, v554, v555, v556, v560, 1, 0, v557, v561, v562, v563, v564, v565, v566, v567, v568, v569, v570, v571, v572, 3, 7, 2, 4, 8) :|: 0 = 0 f_688(v547, v548, v549, v550, v551, v552, v553, v554, v555, v556, v560, 1, 0, v557, v561, v562, v563, v564, v565, v566, v567, v568, v569, v570, v571, v572, 3, 7, 2, 4, 8) -> f_691(v547, v548, v549, v550, v551, v552, v553, v554, v555, v556, v560, 1, 0, v557, v561, v562, v563, v564, v565, v566, v567, v568, v569, v570, v571, v572, 3, 7, 2, 4, 8) :|: 0 = 0 f_691(v547, v548, v549, v550, v551, v552, v553, v554, v555, v556, v560, 1, 0, v557, v561, v562, v563, v564, v565, v566, v567, v568, v569, v570, v571, v572, 3, 7, 2, 4, 8) -> f_694(v547, v548, v549, v550, v551, v552, v553, v554, v555, v556, v560, 1, 0, v557, v561, v562, v563, v564, v565, v566, v567, v568, v569, v570, v571, v572, 3, 7, 2, 4, 8) :|: 0 = 0 f_694(v547, v548, v549, v550, v551, v552, v553, v554, v555, v556, v560, 1, 0, v557, v561, v562, v563, v564, v565, v566, v567, v568, v569, v570, v571, v572, 3, 7, 2, 4, 8) -> f_697(v547, v548, v549, v550, v551, v552, v553, v554, v555, v556, v560, 1, 0, v557, v561, v562, v563, v564, v565, v566, v567, v568, v569, v570, v571, v572, 3, 7, 2, 4, 8) :|: TRUE f_697(v547, v548, v549, v550, v551, v552, v553, v554, v555, v556, v560, 1, 0, v557, v561, v562, v563, v564, v565, v566, v567, v568, v569, v570, v571, v572, 3, 7, 2, 4, 8) -> f_700(v547, v548, v549, v550, v551, v552, v553, v554, v555, v556, v560, 1, 0, v557, v561, v562, v563, v564, v565, v566, v567, v568, v569, v570, v571, v572, 3, 7, 2, 4, 8) :|: 0 = 0 f_700(v547, v548, v549, v550, v551, v552, v553, v554, v555, v556, v560, 1, 0, v557, v561, v562, v563, v564, v565, v566, v567, v568, v569, v570, v571, v572, 3, 7, 2, 4, 8) -> f_703(v547, v548, v549, v550, v551, v552, v553, v554, v555, v556, v560, 1, 0, v561, v562, v563, v564, v565, v566, v567, v568, v569, v570, v571, v572, 3, 7, 2, 4, 8) :|: 0 = 0 f_703(v547, v548, v549, v550, v551, v552, v553, v554, v555, v556, v560, 1, 0, v561, v562, v563, v564, v565, v566, v567, v568, v569, v570, v571, v572, 3, 7, 2, 4, 8) -> f_706(v547, v548, v549, v550, v551, v552, v553, v554, v555, v556, v560, 1, 0, v653, v561, v562, v563, v564, v565, v566, v567, v568, v569, v570, v571, v572, 3, 7, 2, 4, 8) :|: 1 + v653 = v560 && 0 <= v653 f_706(v547, v548, v549, v550, v551, v552, v553, v554, v555, v556, v560, 1, 0, v653, v561, v562, v563, v564, v565, v566, v567, v568, v569, v570, v571, v572, 3, 7, 2, 4, 8) -> f_709(v547, v548, v549, v550, v551, v552, v553, v554, v555, v556, v560, 1, 0, v653, v561, v562, v563, v564, v565, v566, v567, v568, v569, v570, v571, v572, 3, 7, 2, 4, 8) :|: 0 = 0 f_709(v547, v548, v549, v550, v551, v552, v553, v554, v555, v556, v560, 1, 0, v653, v561, v562, v563, v564, v565, v566, v567, v568, v569, v570, v571, v572, 3, 7, 2, 4, 8) -> f_712(v547, v548, v549, v550, v551, v552, v553, v554, v555, v556, v560, 1, 0, v653, v561, v562, v563, v564, v565, v566, v567, v568, v569, v570, v571, v572, 3, 7, 2, 4, 8) :|: TRUE f_712(v547, v548, v549, v550, v551, v552, v553, v554, v555, v556, v560, 1, 0, v653, v561, v562, v563, v564, v565, v566, v567, v568, v569, v570, v571, v572, 3, 7, 2, 4, 8) -> f_714(v547, v548, v549, v550, v551, v552, v553, v554, v555, v556, v560, 1, 0, v653, v561, v562, v563, v564, v565, v566, v567, v568, v569, v570, v571, v572, 3, 7, 2, 4, 8) :|: 0 = 0 f_714(v547, v548, v549, v550, v551, v552, v553, v554, v555, v556, v560, 1, 0, v653, v561, v562, v563, v564, v565, v566, v567, v568, v569, v570, v571, v572, 3, 7, 2, 4, 8) -> f_716(v547, v548, v549, v550, v551, v552, v553, v554, v555, v556, v560, 1, 0, v653, v562, v563, v564, v565, v566, v567, v568, v569, v570, v571, v572, 3, 7, 2, 4, 8) :|: 0 = 0 f_716(v547, v548, v549, v550, v551, v552, v553, v554, v555, v556, v560, 1, 0, v653, v562, v563, v564, v565, v566, v567, v568, v569, v570, v571, v572, 3, 7, 2, 4, 8) -> f_718(v547, v548, v549, v550, v551, v552, v553, v554, v555, v556, v560, 1, 0, v653, v562, v667, v563, v564, v565, v566, v567, v568, v569, v570, v571, v572, 3, 7, 2, 4, 8) :|: v667 = 1 + v562 && 2 <= v667 f_718(v547, v548, v549, v550, v551, v552, v553, v554, v555, v556, v560, 1, 0, v653, v562, v667, v563, v564, v565, v566, v567, v568, v569, v570, v571, v572, 3, 7, 2, 4, 8) -> f_720(v547, v548, v549, v550, v551, v552, v553, v554, v555, v556, v560, 1, 0, v653, v562, v667, v563, v564, v565, v566, v567, v568, v569, v570, v571, v572, 3, 7, 2, 4, 8) :|: 0 = 0 f_720(v547, v548, v549, v550, v551, v552, v553, v554, v555, v556, v560, 1, 0, v653, v562, v667, v563, v564, v565, v566, v567, v568, v569, v570, v571, v572, 3, 7, 2, 4, 8) -> f_722(v547, v548, v549, v550, v551, v552, v553, v554, v555, v556, v560, 1, 0, v653, v562, v667, v563, v564, v565, v566, v567, v568, v569, v570, v571, v572, 3, 7, 2, 4, 8) :|: TRUE f_722(v547, v548, v549, v550, v551, v552, v553, v554, v555, v556, v560, 1, 0, v653, v562, v667, v563, v564, v565, v566, v567, v568, v569, v570, v571, v572, 3, 7, 2, 4, 8) -> f_724(v547, v548, v549, v550, v551, v552, v553, v554, v555, v556, v560, 1, 0, v653, v562, v667, v563, v564, v565, v566, v567, v568, v569, v570, v571, v572, 3, 7, 2, 4, 8) :|: TRUE f_724(v547, v548, v549, v550, v551, v552, v553, v554, v555, v556, v560, 1, 0, v653, v562, v667, v563, v564, v565, v566, v567, v568, v569, v570, v571, v572, 3, 7, 2, 4, 8) -> f_669(v547, v548, v549, v550, v551, v552, v553, v554, v555, v556, v560, 1, 0, v653, v562, v667, v563, v564, v565, v566, v567, v568, v569, v570, v571, v572, 3, 7, 4, 8) :|: TRUE f_669(v547, v548, v549, v550, v551, v552, v553, v554, v555, v556, v557, 1, 0, v560, v561, v562, v563, v564, v565, v566, v567, v568, v569, v570, v571, v572, 3, 7, 4, 8) -> f_671(v547, v548, v549, v550, v551, v552, v553, v554, v555, v556, v557, 1, 0, v560, v561, v562, v563, v564, v565, v566, v567, v568, v569, v570, v571, v572, 3, 7, 4, 8) :|: 0 = 0 Combined rules. Obtained 1 rulesP rules: f_671(v547:0, v548:0, v549:0, v550:0, v551:0, v552:0, v553:0, v554:0, v555:0, v556:0, v557:0, 1, 0, 1 + v653:0, v561:0, v562:0, v563:0, v564:0, v565:0, v566:0, v567:0, v568:0, v569:0, v570:0, v571:0, v572:0, 3, 7, 4, 8) -> f_671(v547:0, v548:0, v549:0, v550:0, v551:0, v552:0, v553:0, v554:0, v555:0, v556:0, 1 + v653:0, 1, 0, v653:0, v562:0, 1 + v562:0, v563:0, v564:0, v565:0, v566:0, v567:0, v568:0, v569:0, v570:0, v571:0, v572:0, 3, 7, 4, 8) :|: v557:0 > 1 && v653:0 > -1 && v547:0 > 1 && v562:0 > 0 Filtered unneeded arguments: f_671(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) -> f_671(x1, x11, x14, x16) Removed division, modulo operations, cleaned up constraints. Obtained 1 rules.P rules: f_671(v547:0, v557:0, sum~cons_1~v653:0, v562:0) -> f_671(v547:0, 1 + v653:0, v653:0, 1 + v562:0) :|: v653:0 > -1 && v557:0 > 1 && v562:0 > 0 && v547:0 > 1 && sum~cons_1~v653:0 = 1 + v653:0 ---------------------------------------- (16) Obligation: Rules: f_671(v547:0, v557:0, sum~cons_1~v653:0, v562:0) -> f_671(v547:0, 1 + v653:0, v653:0, 1 + v562:0) :|: v653:0 > -1 && v557:0 > 1 && v562:0 > 0 && v547:0 > 1 && sum~cons_1~v653:0 = 1 + v653:0 ---------------------------------------- (17) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (18) Obligation: Rules: f_671(v547:0:0, v557:0:0, sum~cons_1~v653:0:0, v562:0:0) -> f_671(v547:0:0, 1 + v653:0:0, v653:0:0, 1 + v562:0:0) :|: v562:0:0 > 0 && v547:0:0 > 1 && v557:0:0 > 1 && v653:0:0 > -1 && sum~cons_1~v653:0:0 = 1 + v653:0:0 ---------------------------------------- (19) RankingReductionPairProof (EQUIVALENT) Interpretation: [ f_671 ] = f_671_3 The following rules are decreasing: f_671(v547:0:0, v557:0:0, sum~cons_1~v653:0:0, v562:0:0) -> f_671(v547:0:0, 1 + v653:0:0, v653:0:0, 1 + v562:0:0) :|: v562:0:0 > 0 && v547:0:0 > 1 && v557:0:0 > 1 && v653:0:0 > -1 && sum~cons_1~v653:0:0 = 1 + v653:0:0 The following rules are bounded: f_671(v547:0:0, v557:0:0, sum~cons_1~v653:0:0, v562:0:0) -> f_671(v547:0:0, 1 + v653:0:0, v653:0:0, 1 + v562:0:0) :|: v562:0:0 > 0 && v547:0:0 > 1 && v557:0:0 > 1 && v653:0:0 > -1 && sum~cons_1~v653:0:0 = 1 + v653: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_582(v372, v373, v374, v375, v376, v377, v378, v379, v380, v381, 1, v383, v384, v385, v386, v387, v388, v389, v390, v391, v392, v393, v394, v395, v396, 0, 3, 7, 4, 8) -> f_584(v372, v373, v374, v375, v376, v377, v378, v379, v380, v381, 1, v384, v383, v385, v386, v387, v388, v389, v390, v391, v392, v393, v394, v395, v396, 0, 3, 7, 4, 8) :|: 0 = 0 f_584(v372, v373, v374, v375, v376, v377, v378, v379, v380, v381, 1, v384, v383, v385, v386, v387, v388, v389, v390, v391, v392, v393, v394, v395, v396, 0, 3, 7, 4, 8) -> f_586(v372, v373, v374, v375, v376, v377, v378, v379, v380, v381, 1, v384, v383, v385, v386, v387, v388, v389, v390, v391, v392, v393, v394, v395, v396, 0, 3, 7, 2, 4, 8) :|: 0 < v384 && 2 <= v383 && 2 <= v373 f_586(v372, v373, v374, v375, v376, v377, v378, v379, v380, v381, 1, v384, v383, v385, v386, v387, v388, v389, v390, v391, v392, v393, v394, v395, v396, 0, 3, 7, 2, 4, 8) -> f_589(v372, v373, v374, v375, v376, v377, v378, v379, v380, v381, 1, v384, v383, v385, v386, v387, v388, v389, v390, v391, v392, v393, v394, v395, v396, 0, 3, 7, 2, 4, 8) :|: 0 = 0 f_589(v372, v373, v374, v375, v376, v377, v378, v379, v380, v381, 1, v384, v383, v385, v386, v387, v388, v389, v390, v391, v392, v393, v394, v395, v396, 0, 3, 7, 2, 4, 8) -> f_592(v372, v373, v374, v375, v376, v377, v378, v379, v380, v381, 1, v384, v383, v385, v386, v387, v388, v389, v390, v391, v392, v393, v394, v395, v396, 0, 3, 7, 2, 4, 8) :|: TRUE f_592(v372, v373, v374, v375, v376, v377, v378, v379, v380, v381, 1, v384, v383, v385, v386, v387, v388, v389, v390, v391, v392, v393, v394, v395, v396, 0, 3, 7, 2, 4, 8) -> f_595(v372, v373, v374, v375, v376, v377, v378, v379, v380, v381, 1, v384, v383, v385, v386, v387, v388, v389, v390, v391, v392, v393, v394, v395, v396, 0, 3, 7, 2, 4, 8) :|: 0 = 0 f_595(v372, v373, v374, v375, v376, v377, v378, v379, v380, v381, 1, v384, v383, v385, v386, v387, v388, v389, v390, v391, v392, v393, v394, v395, v396, 0, 3, 7, 2, 4, 8) -> f_598(v372, v373, v374, v375, v376, v377, v378, v379, v380, v381, 1, v384, v385, v386, v387, v388, v389, v390, v391, v392, v393, v394, v395, v396, 0, 3, 7, 2, 4, 8) :|: 0 = 0 f_598(v372, v373, v374, v375, v376, v377, v378, v379, v380, v381, 1, v384, v385, v386, v387, v388, v389, v390, v391, v392, v393, v394, v395, v396, 0, 3, 7, 2, 4, 8) -> f_601(v372, v373, v374, v375, v376, v377, v378, v379, v380, v381, 1, v384, v414, v385, v386, v387, v388, v389, v390, v391, v392, v393, v394, v395, v396, 0, 3, 7, 2, 4, 8) :|: 1 + v414 = v384 && 0 <= v414 f_601(v372, v373, v374, v375, v376, v377, v378, v379, v380, v381, 1, v384, v414, v385, v386, v387, v388, v389, v390, v391, v392, v393, v394, v395, v396, 0, 3, 7, 2, 4, 8) -> f_604(v372, v373, v374, v375, v376, v377, v378, v379, v380, v381, 1, v384, v414, v385, v386, v387, v388, v389, v390, v391, v392, v393, v394, v395, v396, 0, 3, 7, 2, 4, 8) :|: 0 = 0 f_604(v372, v373, v374, v375, v376, v377, v378, v379, v380, v381, 1, v384, v414, v385, v386, v387, v388, v389, v390, v391, v392, v393, v394, v395, v396, 0, 3, 7, 2, 4, 8) -> f_608(v372, v373, v374, v375, v376, v377, v378, v379, v380, v381, 1, v384, v414, v385, v386, v387, v388, v389, v390, v391, v392, v393, v394, v395, v396, 0, 3, 7, 2, 4, 8) :|: TRUE f_608(v372, v373, v374, v375, v376, v377, v378, v379, v380, v381, 1, v384, v414, v385, v386, v387, v388, v389, v390, v391, v392, v393, v394, v395, v396, 0, 3, 7, 2, 4, 8) -> f_611(v372, v373, v374, v375, v376, v377, v378, v379, v380, v381, 1, v384, v414, v385, v386, v387, v388, v389, v390, v391, v392, v393, v394, v395, v396, 0, 3, 7, 2, 4, 8) :|: 0 = 0 f_611(v372, v373, v374, v375, v376, v377, v378, v379, v380, v381, 1, v384, v414, v385, v386, v387, v388, v389, v390, v391, v392, v393, v394, v395, v396, 0, 3, 7, 2, 4, 8) -> f_614(v372, v373, v374, v375, v376, v377, v378, v379, v380, v381, 1, v384, v414, v386, v387, v388, v389, v390, v391, v392, v393, v394, v395, v396, 0, 3, 7, 2, 4, 8) :|: 0 = 0 f_614(v372, v373, v374, v375, v376, v377, v378, v379, v380, v381, 1, v384, v414, v386, v387, v388, v389, v390, v391, v392, v393, v394, v395, v396, 0, 3, 7, 2, 4, 8) -> f_618(v372, v373, v374, v375, v376, v377, v378, v379, v380, v381, 1, v384, v414, v386, v445, v387, v388, v389, v390, v391, v392, v393, v394, v395, v396, 0, 3, 7, 2, 4, 8) :|: v445 = 1 + v386 && 2 <= v445 f_618(v372, v373, v374, v375, v376, v377, v378, v379, v380, v381, 1, v384, v414, v386, v445, v387, v388, v389, v390, v391, v392, v393, v394, v395, v396, 0, 3, 7, 2, 4, 8) -> f_622(v372, v373, v374, v375, v376, v377, v378, v379, v380, v381, 1, v384, v414, v386, v445, v387, v388, v389, v390, v391, v392, v393, v394, v395, v396, 0, 3, 7, 2, 4, 8) :|: 0 = 0 f_622(v372, v373, v374, v375, v376, v377, v378, v379, v380, v381, 1, v384, v414, v386, v445, v387, v388, v389, v390, v391, v392, v393, v394, v395, v396, 0, 3, 7, 2, 4, 8) -> f_626(v372, v373, v374, v375, v376, v377, v378, v379, v380, v381, 1, v384, v414, v386, v445, v387, v388, v389, v390, v391, v392, v393, v394, v395, v396, 0, 3, 7, 2, 4, 8) :|: TRUE f_626(v372, v373, v374, v375, v376, v377, v378, v379, v380, v381, 1, v384, v414, v386, v445, v387, v388, v389, v390, v391, v392, v393, v394, v395, v396, 0, 3, 7, 2, 4, 8) -> f_630(v372, v373, v374, v375, v376, v377, v378, v379, v380, v381, 1, v384, v414, v386, v445, v387, v388, v389, v390, v391, v392, v393, v394, v395, v396, 0, 3, 7, 2, 4, 8) :|: TRUE f_630(v372, v373, v374, v375, v376, v377, v378, v379, v380, v381, 1, v384, v414, v386, v445, v387, v388, v389, v390, v391, v392, v393, v394, v395, v396, 0, 3, 7, 2, 4, 8) -> f_580(v372, v373, v374, v375, v376, v377, v378, v379, v380, v381, 1, v384, v414, v386, v445, v387, v388, v389, v390, v391, v392, v393, v394, v395, v396, 0, 3, 7, 4, 8) :|: TRUE f_580(v372, v373, v374, v375, v376, v377, v378, v379, v380, v381, 1, v383, v384, v385, v386, v387, v388, v389, v390, v391, v392, v393, v394, v395, v396, 0, 3, 7, 4, 8) -> f_582(v372, v373, v374, v375, v376, v377, v378, v379, v380, v381, 1, v383, v384, v385, v386, v387, v388, v389, v390, v391, v392, v393, v394, v395, v396, 0, 3, 7, 4, 8) :|: 0 = 0 Combined rules. Obtained 1 rulesP rules: f_582(v372:0, v373:0, v374:0, v375:0, v376:0, v377:0, v378:0, v379:0, v380:0, v381:0, 1, v383:0, 1 + v414:0, v385:0, v386:0, v387:0, v388:0, v389:0, v390:0, v391:0, v392:0, v393:0, v394:0, v395:0, v396:0, 0, 3, 7, 4, 8) -> f_582(v372:0, v373:0, v374:0, v375:0, v376:0, v377:0, v378:0, v379:0, v380:0, v381:0, 1, 1 + v414:0, v414:0, v386:0, 1 + v386:0, v387:0, v388:0, v389:0, v390:0, v391:0, v392:0, v393:0, v394:0, v395:0, v396:0, 0, 3, 7, 4, 8) :|: v383:0 > 1 && v414:0 > -1 && v373:0 > 1 && v386:0 > 0 Filtered unneeded arguments: f_582(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) -> f_582(x2, x12, x13, x15) Removed division, modulo operations, cleaned up constraints. Obtained 1 rules.P rules: f_582(v373:0, v383:0, sum~cons_1~v414:0, v386:0) -> f_582(v373:0, 1 + v414:0, v414:0, 1 + v386:0) :|: v414:0 > -1 && v383:0 > 1 && v386:0 > 0 && v373:0 > 1 && sum~cons_1~v414:0 = 1 + v414:0 ---------------------------------------- (23) Obligation: Rules: f_582(v373:0, v383:0, sum~cons_1~v414:0, v386:0) -> f_582(v373:0, 1 + v414:0, v414:0, 1 + v386:0) :|: v414:0 > -1 && v383:0 > 1 && v386:0 > 0 && v373:0 > 1 && sum~cons_1~v414:0 = 1 + v414:0 ---------------------------------------- (24) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (25) Obligation: Rules: f_582(v373:0:0, v383:0:0, sum~cons_1~v414:0:0, v386:0:0) -> f_582(v373:0:0, 1 + v414:0:0, v414:0:0, 1 + v386:0:0) :|: v386:0:0 > 0 && v373:0:0 > 1 && v383:0:0 > 1 && v414:0:0 > -1 && sum~cons_1~v414:0:0 = 1 + v414:0:0 ---------------------------------------- (26) RankingReductionPairProof (EQUIVALENT) Interpretation: [ f_582 ] = f_582_3 The following rules are decreasing: f_582(v373:0:0, v383:0:0, sum~cons_1~v414:0:0, v386:0:0) -> f_582(v373:0:0, 1 + v414:0:0, v414:0:0, 1 + v386:0:0) :|: v386:0:0 > 0 && v373:0:0 > 1 && v383:0:0 > 1 && v414:0:0 > -1 && sum~cons_1~v414:0:0 = 1 + v414:0:0 The following rules are bounded: f_582(v373:0:0, v383:0:0, sum~cons_1~v414:0:0, v386:0:0) -> f_582(v373:0:0, 1 + v414:0:0, v414:0:0, 1 + v386:0:0) :|: v386:0:0 > 0 && v373:0:0 > 1 && v383:0:0 > 1 && v414:0:0 > -1 && sum~cons_1~v414:0:0 = 1 + v414:0:0 ---------------------------------------- (27) YES