50.68/17.66 YES 50.68/17.68 proof of /export/starexec/sandbox/benchmark/theBenchmark.c 50.68/17.68 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 50.68/17.68 50.68/17.68 50.68/17.68 Termination of the given C Problem could be proven: 50.68/17.68 50.68/17.68 (0) C Problem 50.68/17.68 (1) CToLLVMProof [EQUIVALENT, 170 ms] 50.68/17.68 (2) LLVM problem 50.68/17.68 (3) LLVMToTerminationGraphProof [EQUIVALENT, 13.3 s] 50.68/17.68 (4) LLVM Symbolic Execution Graph 50.68/17.68 (5) SymbolicExecutionGraphToSCCProof [SOUND, 0 ms] 50.68/17.68 (6) AND 50.68/17.68 (7) LLVM Symbolic Execution SCC 50.68/17.68 (8) SCC2IRS [SOUND, 82 ms] 50.68/17.68 (9) IntTRS 50.68/17.68 (10) IntTRSCompressionProof [EQUIVALENT, 0 ms] 50.68/17.68 (11) IntTRS 50.68/17.68 (12) PolynomialOrderProcessor [EQUIVALENT, 12 ms] 50.68/17.68 (13) YES 50.68/17.68 (14) LLVM Symbolic Execution SCC 50.68/17.68 (15) SCC2IRS [SOUND, 134 ms] 50.68/17.68 (16) IntTRS 50.68/17.68 (17) IntTRSCompressionProof [EQUIVALENT, 0 ms] 50.68/17.68 (18) IntTRS 50.68/17.68 (19) RankingReductionPairProof [EQUIVALENT, 11 ms] 50.68/17.68 (20) YES 50.68/17.68 50.68/17.68 50.68/17.68 ---------------------------------------- 50.68/17.68 50.68/17.68 (0) 50.68/17.68 Obligation: 50.68/17.68 c file /export/starexec/sandbox/benchmark/theBenchmark.c 50.68/17.68 ---------------------------------------- 50.68/17.68 50.68/17.68 (1) CToLLVMProof (EQUIVALENT) 50.68/17.68 Compiled c-file /export/starexec/sandbox/benchmark/theBenchmark.c to LLVM. 50.68/17.68 ---------------------------------------- 50.68/17.68 50.68/17.68 (2) 50.68/17.68 Obligation: 50.68/17.68 LLVM Problem 50.68/17.68 50.68/17.68 Aliases: 50.68/17.68 50.68/17.68 Data layout: 50.68/17.68 50.68/17.68 "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" 50.68/17.68 50.68/17.68 Machine: 50.68/17.68 50.68/17.68 "x86_64-pc-linux-gnu" 50.68/17.68 50.68/17.68 Type definitions: 50.68/17.68 50.68/17.68 Global variables: 50.68/17.68 50.68/17.68 Function declarations and definitions: 50.68/17.68 50.68/17.68 *BasicFunctionTypename: "__VERIFIER_nondet_int" returnParam: i32 parameters: () variableLength: false visibilityType: DEFAULT callingConvention: ccc 50.68/17.68 *BasicFunctionTypename: "subxy" linkageType: EXTERNALLY_VISIBLE returnParam: i32 parameters: (x i32, y i32) variableLength: false visibilityType: DEFAULT callingConvention: ccc 50.68/17.68 0: 50.68/17.68 %1 = alloca i32, align 4 50.68/17.68 %2 = alloca i32, align 4 50.68/17.68 %3 = alloca i32, align 4 50.68/17.68 %x_ref = alloca *i32, align 8 50.68/17.68 %y_ref = alloca *i32, align 8 50.68/17.68 %z = alloca *i32, align 8 50.68/17.68 %i = alloca *i32, align 8 50.68/17.68 store %x, %2 50.68/17.68 store %y, %3 50.68/17.68 %4 = alloca i8, numElementsLit: 4 50.68/17.68 %5 = bitcast *i8 %4 to *i32 50.68/17.68 store %5, %x_ref 50.68/17.68 %6 = alloca i8, numElementsLit: 4 50.68/17.68 %7 = bitcast *i8 %6 to *i32 50.68/17.68 store %7, %y_ref 50.68/17.68 %8 = alloca i8, numElementsLit: 4 50.68/17.68 %9 = bitcast *i8 %8 to *i32 50.68/17.68 store %9, %z 50.68/17.68 %10 = alloca i8, numElementsLit: 4 50.68/17.68 %11 = bitcast *i8 %10 to *i32 50.68/17.68 store %11, %i 50.68/17.68 %12 = load %2 50.68/17.68 %13 = load %x_ref 50.68/17.68 store %12, %13 50.68/17.68 %14 = load %3 50.68/17.68 %15 = load %y_ref 50.68/17.68 store %14, %15 50.68/17.68 %16 = load %z 50.68/17.68 store 0, %16 50.68/17.68 %17 = load %x_ref 50.68/17.68 %18 = load %17 50.68/17.68 %19 = load %i 50.68/17.68 store %18, %19 50.68/17.68 %20 = load %y_ref 50.68/17.68 %21 = load %20 50.68/17.68 %22 = icmp sle %21 0 50.68/17.68 br %22, %27, %23 50.68/17.68 23: 50.68/17.68 %24 = load %x_ref 50.68/17.68 %25 = load %24 50.68/17.68 %26 = icmp sle %25 0 50.68/17.68 br %26, %27, %28 50.68/17.68 27: 50.68/17.68 store 0, %1 50.68/17.68 br %57 50.68/17.68 28: 50.68/17.68 br %29 50.68/17.68 29: 50.68/17.68 %30 = load %i 50.68/17.68 %31 = load %30 50.68/17.68 %32 = icmp sgt %31 0 50.68/17.68 br %32, %33, %40 50.68/17.68 33: 50.68/17.68 %34 = load %i 50.68/17.68 %35 = load %34 50.68/17.68 %36 = add %35 -1 50.68/17.68 store %36, %34 50.68/17.68 %37 = load %z 50.68/17.68 %38 = load %37 50.68/17.68 %39 = add %38 1 50.68/17.68 store %39, %37 50.68/17.68 br %29 50.68/17.68 40: 50.68/17.68 br %41 50.68/17.68 41: 50.68/17.68 %42 = load %i 50.68/17.68 %43 = load %42 50.68/17.68 %44 = load %y_ref 50.68/17.68 %45 = load %44 50.68/17.68 %46 = icmp slt %43 %45 50.68/17.68 br %46, %47, %54 50.68/17.68 47: 50.68/17.68 %48 = load %i 50.68/17.68 %49 = load %48 50.68/17.68 %50 = add %49 1 50.68/17.68 store %50, %48 50.68/17.68 %51 = load %z 50.68/17.68 %52 = load %51 50.68/17.68 %53 = add %52 -1 50.68/17.68 store %53, %51 50.68/17.68 br %41 50.68/17.68 54: 50.68/17.68 %55 = load %z 50.68/17.68 %56 = load %55 50.68/17.68 store %56, %1 50.68/17.68 br %57 50.68/17.68 57: 50.68/17.68 %58 = load %1 50.68/17.68 ret %58 50.68/17.68 50.68/17.68 *BasicFunctionTypename: "main" linkageType: EXTERNALLY_VISIBLE returnParam: i32 parameters: () variableLength: false visibilityType: DEFAULT callingConvention: ccc 50.68/17.68 0: 50.68/17.68 %1 = alloca i32, align 4 50.68/17.68 %x = alloca i32, align 4 50.68/17.68 %y = alloca i32, align 4 50.68/17.68 store 0, %1 50.68/17.68 %2 = call i32 @__VERIFIER_nondet_int() 50.68/17.68 store %2, %x 50.68/17.68 %3 = call i32 @__VERIFIER_nondet_int() 50.68/17.68 store %3, %y 50.68/17.68 %4 = load %x 50.68/17.68 %5 = load %y 50.68/17.68 %6 = call i32 @subxy(i32 %4, i32 %5) 50.68/17.68 ret 0 50.68/17.68 50.68/17.68 50.68/17.68 Analyze Termination of all function calls matching the pattern: 50.68/17.68 main() 50.68/17.68 ---------------------------------------- 50.68/17.68 50.68/17.68 (3) LLVMToTerminationGraphProof (EQUIVALENT) 50.68/17.68 Constructed symbolic execution graph for LLVM program and proved memory safety. 50.68/17.68 ---------------------------------------- 50.68/17.68 50.68/17.68 (4) 50.68/17.68 Obligation: 50.68/17.68 SE Graph 50.68/17.68 ---------------------------------------- 50.68/17.68 50.68/17.68 (5) SymbolicExecutionGraphToSCCProof (SOUND) 50.68/17.68 Splitted symbolic execution graph to 2 SCCs. 50.68/17.68 ---------------------------------------- 50.68/17.68 50.68/17.68 (6) 50.68/17.68 Complex Obligation (AND) 50.68/17.68 50.68/17.68 ---------------------------------------- 50.68/17.68 50.68/17.68 (7) 50.68/17.68 Obligation: 50.68/17.68 SCC 50.68/17.68 ---------------------------------------- 50.68/17.68 50.68/17.68 (8) SCC2IRS (SOUND) 50.68/17.68 Transformed LLVM symbolic execution graph SCC into a rewrite problem. Log: 50.68/17.68 Generated rules. Obtained 17 rulesP rules: 50.68/17.68 f_705(v763, v764, v765, v766, v767, v768, v769, v770, v771, v772, v773, v774, v775, 0, 1, v778, v779, v780, v781, v782, v783, v784, v787, v785, v788, v786, v789, v790, v791, v792, v793, v794, v795, v796, v797, v798, v799, v800, 3, 7, 4, 8) -> f_706(v763, v764, v765, v766, v767, v768, v769, v770, v771, v772, v773, v774, v775, 0, 1, v778, v779, v781, v780, v782, v783, v784, v787, v785, v788, v786, v789, v790, v791, v792, v793, v794, v795, v796, v797, v798, v799, v800, 3, 7, 4, 8) :|: 0 = 0 50.68/17.68 f_706(v763, v764, v765, v766, v767, v768, v769, v770, v771, v772, v773, v774, v775, 0, 1, v778, v779, v781, v780, v782, v783, v784, v787, v785, v788, v786, v789, v790, v791, v792, v793, v794, v795, v796, v797, v798, v799, v800, 3, 7, 4, 8) -> f_707(v763, v764, v765, v766, v767, v768, v769, v770, v771, v772, v773, v774, v775, 0, 1, v778, v779, v781, v780, v782, v783, v784, v787, v785, v788, v786, v789, v790, v791, v792, v793, v794, v795, v796, v797, v798, v799, v800, 3, 7, 4, 8) :|: 0 = 0 50.68/17.68 f_707(v763, v764, v765, v766, v767, v768, v769, v770, v771, v772, v773, v774, v775, 0, 1, v778, v779, v781, v780, v782, v783, v784, v787, v785, v788, v786, v789, v790, v791, v792, v793, v794, v795, v796, v797, v798, v799, v800, 3, 7, 4, 8) -> f_708(v763, v764, v765, v766, v767, v768, v769, v770, v771, v772, v773, v774, v775, 0, 1, v778, v779, v781, v780, v782, v783, v784, v787, v785, v788, v786, v789, v790, v791, v792, v793, v794, v795, v796, v797, v798, v799, v800, 3, 7, 4, 8) :|: 0 = 0 50.68/17.68 f_708(v763, v764, v765, v766, v767, v768, v769, v770, v771, v772, v773, v774, v775, 0, 1, v778, v779, v781, v780, v782, v783, v784, v787, v785, v788, v786, v789, v790, v791, v792, v793, v794, v795, v796, v797, v798, v799, v800, 3, 7, 4, 8) -> f_709(v763, v764, v765, v766, v767, v768, v769, v770, v771, v772, v773, v774, v775, 0, 1, v778, v779, v781, v780, v782, v783, v784, v787, v785, v788, v786, v789, v790, v791, v792, v793, v794, v795, v796, v797, v798, v799, v800, 3, 7, 2, 4, 8) :|: v781 < v764 && 2 <= v764 50.68/17.68 f_709(v763, v764, v765, v766, v767, v768, v769, v770, v771, v772, v773, v774, v775, 0, 1, v778, v779, v781, v780, v782, v783, v784, v787, v785, v788, v786, v789, v790, v791, v792, v793, v794, v795, v796, v797, v798, v799, v800, 3, 7, 2, 4, 8) -> f_711(v763, v764, v765, v766, v767, v768, v769, v770, v771, v772, v773, v774, v775, 0, 1, v778, v779, v781, v780, v782, v783, v784, v787, v785, v788, v786, v789, v790, v791, v792, v793, v794, v795, v796, v797, v798, v799, v800, 3, 7, 2, 4, 8) :|: 0 = 0 50.68/17.68 f_711(v763, v764, v765, v766, v767, v768, v769, v770, v771, v772, v773, v774, v775, 0, 1, v778, v779, v781, v780, v782, v783, v784, v787, v785, v788, v786, v789, v790, v791, v792, v793, v794, v795, v796, v797, v798, v799, v800, 3, 7, 2, 4, 8) -> f_713(v763, v764, v765, v766, v767, v768, v769, v770, v771, v772, v773, v774, v775, 0, 1, v778, v779, v781, v780, v782, v783, v784, v787, v785, v788, v786, v789, v790, v791, v792, v793, v794, v795, v796, v797, v798, v799, v800, 3, 7, 2, 4, 8) :|: TRUE 50.68/17.68 f_713(v763, v764, v765, v766, v767, v768, v769, v770, v771, v772, v773, v774, v775, 0, 1, v778, v779, v781, v780, v782, v783, v784, v787, v785, v788, v786, v789, v790, v791, v792, v793, v794, v795, v796, v797, v798, v799, v800, 3, 7, 2, 4, 8) -> f_715(v763, v764, v765, v766, v767, v768, v769, v770, v771, v772, v773, v774, v775, 0, 1, v778, v779, v781, v780, v782, v783, v784, v787, v785, v788, v786, v789, v790, v791, v792, v793, v794, v795, v796, v797, v798, v799, v800, 3, 7, 2, 4, 8) :|: 0 = 0 50.68/17.68 f_715(v763, v764, v765, v766, v767, v768, v769, v770, v771, v772, v773, v774, v775, 0, 1, v778, v779, v781, v780, v782, v783, v784, v787, v785, v788, v786, v789, v790, v791, v792, v793, v794, v795, v796, v797, v798, v799, v800, 3, 7, 2, 4, 8) -> f_717(v763, v764, v765, v766, v767, v768, v769, v770, v771, v772, v773, v774, v775, 0, 1, v778, v779, v781, v782, v783, v784, v787, v785, v788, v786, v789, v790, v791, v792, v793, v794, v795, v796, v797, v798, v799, v800, 3, 7, 2, 4, 8) :|: 0 = 0 50.68/17.68 f_717(v763, v764, v765, v766, v767, v768, v769, v770, v771, v772, v773, v774, v775, 0, 1, v778, v779, v781, v782, v783, v784, v787, v785, v788, v786, v789, v790, v791, v792, v793, v794, v795, v796, v797, v798, v799, v800, 3, 7, 2, 4, 8) -> f_719(v763, v764, v765, v766, v767, v768, v769, v770, v771, v772, v773, v774, v775, 0, 1, v778, v779, v781, v818, v782, v783, v784, v787, v785, v788, v786, v789, v790, v791, v792, v793, v794, v795, v796, v797, v798, v799, v800, 3, 7, 2, 4, 8) :|: v818 = 1 + v781 && 2 <= v818 50.68/17.68 f_719(v763, v764, v765, v766, v767, v768, v769, v770, v771, v772, v773, v774, v775, 0, 1, v778, v779, v781, v818, v782, v783, v784, v787, v785, v788, v786, v789, v790, v791, v792, v793, v794, v795, v796, v797, v798, v799, v800, 3, 7, 2, 4, 8) -> f_721(v763, v764, v765, v766, v767, v768, v769, v770, v771, v772, v773, v774, v775, 0, 1, v778, v779, v781, v818, v782, v783, v784, v787, v785, v788, v786, v789, v790, v791, v792, v793, v794, v795, v796, v797, v798, v799, v800, 3, 7, 2, 4, 8) :|: TRUE 50.68/17.68 f_721(v763, v764, v765, v766, v767, v768, v769, v770, v771, v772, v773, v774, v775, 0, 1, v778, v779, v781, v818, v782, v783, v784, v787, v785, v788, v786, v789, v790, v791, v792, v793, v794, v795, v796, v797, v798, v799, v800, 3, 7, 2, 4, 8) -> f_723(v763, v764, v765, v766, v767, v768, v769, v770, v771, v772, v773, v774, v775, 0, 1, v778, v779, v781, v818, v782, v783, v784, v787, v785, v788, v786, v789, v790, v791, v792, v793, v794, v795, v796, v797, v798, v799, v800, 3, 7, 2, 4, 8) :|: 0 = 0 50.68/17.68 f_723(v763, v764, v765, v766, v767, v768, v769, v770, v771, v772, v773, v774, v775, 0, 1, v778, v779, v781, v818, v782, v783, v784, v787, v785, v788, v786, v789, v790, v791, v792, v793, v794, v795, v796, v797, v798, v799, v800, 3, 7, 2, 4, 8) -> f_725(v763, v764, v765, v766, v767, v768, v769, v770, v771, v772, v773, v774, v775, 0, 1, v778, v779, v781, v818, v783, v784, v787, v785, v788, v786, v789, v790, v791, v792, v793, v794, v795, v796, v797, v798, v799, v800, 3, 7, 2, 4, 8) :|: 0 = 0 50.68/17.68 f_725(v763, v764, v765, v766, v767, v768, v769, v770, v771, v772, v773, v774, v775, 0, 1, v778, v779, v781, v818, v783, v784, v787, v785, v788, v786, v789, v790, v791, v792, v793, v794, v795, v796, v797, v798, v799, v800, 3, 7, 2, 4, 8) -> f_727(v763, v764, v765, v766, v767, v768, v769, v770, v771, v772, v773, v774, v775, 0, 1, v778, v779, v781, v818, v783, v821, v784, v787, v785, v788, v786, v789, v790, v791, v792, v793, v794, v795, v796, v797, v798, v799, v800, 3, 7, 2, 4, 8) :|: 1 + v821 = v783 50.68/17.68 f_727(v763, v764, v765, v766, v767, v768, v769, v770, v771, v772, v773, v774, v775, 0, 1, v778, v779, v781, v818, v783, v821, v784, v787, v785, v788, v786, v789, v790, v791, v792, v793, v794, v795, v796, v797, v798, v799, v800, 3, 7, 2, 4, 8) -> f_728(v763, v764, v765, v766, v767, v768, v769, v770, v771, v772, v773, v774, v775, 0, 1, v778, v779, v781, v818, v783, v821, v784, v787, v785, v788, v786, v789, v790, v791, v792, v793, v794, v795, v796, v797, v798, v799, v800, 3, 7, 2, 4, 8) :|: TRUE 50.68/17.68 f_728(v763, v764, v765, v766, v767, v768, v769, v770, v771, v772, v773, v774, v775, 0, 1, v778, v779, v781, v818, v783, v821, v784, v787, v785, v788, v786, v789, v790, v791, v792, v793, v794, v795, v796, v797, v798, v799, v800, 3, 7, 2, 4, 8) -> f_729(v763, v764, v765, v766, v767, v768, v769, v770, v771, v772, v773, v774, v775, 0, 1, v778, v779, v781, v818, v783, v821, v784, v787, v785, v788, v786, v789, v790, v791, v792, v793, v794, v795, v796, v797, v798, v799, v800, 3, 7, 2, 4, 8) :|: TRUE 50.68/17.68 f_729(v763, v764, v765, v766, v767, v768, v769, v770, v771, v772, v773, v774, v775, 0, 1, v778, v779, v781, v818, v783, v821, v784, v787, v785, v788, v786, v789, v790, v791, v792, v793, v794, v795, v796, v797, v798, v799, v800, 3, 7, 2, 4, 8) -> f_704(v763, v764, v765, v766, v767, v768, v769, v770, v771, v772, v773, v774, v775, 0, 1, v778, v779, v781, v818, v783, v821, v784, v787, v785, v788, v786, v789, v790, v791, v792, v793, v794, v795, v796, v797, v798, v799, v800, 3, 7, 4, 8) :|: TRUE 50.68/17.68 f_704(v763, v764, v765, v766, v767, v768, v769, v770, v771, v772, v773, v774, v775, 0, 1, v778, v779, v780, v781, v782, v783, v784, v787, v785, v788, v786, v789, v790, v791, v792, v793, v794, v795, v796, v797, v798, v799, v800, 3, 7, 4, 8) -> f_705(v763, v764, v765, v766, v767, v768, v769, v770, v771, v772, v773, v774, v775, 0, 1, v778, v779, v780, v781, v782, v783, v784, v787, v785, v788, v786, v789, v790, v791, v792, v793, v794, v795, v796, v797, v798, v799, v800, 3, 7, 4, 8) :|: 0 = 0 50.68/17.68 Combined rules. Obtained 1 rulesP rules: 50.68/17.68 f_705(v763:0, v764:0, v765:0, v766:0, v767:0, v768:0, v769:0, v770:0, v771:0, v772:0, v773:0, v774:0, v775:0, 0, 1, v778:0, v779:0, v780:0, v781:0, v782:0, 1 + v821:0, v784:0, v787:0, v785:0, v788:0, v786:0, v789:0, v790:0, v791:0, v792:0, v793:0, v794:0, v795:0, v796:0, v797:0, v798:0, v799:0, v800:0, 3, 7, 4, 8) -> f_705(v763:0, v764:0, v765:0, v766:0, v767:0, v768:0, v769:0, v770:0, v771:0, v772:0, v773:0, v774:0, v775:0, 0, 1, v778:0, v779:0, v781:0, 1 + v781:0, 1 + v821:0, v821:0, v784:0, v787:0, v785:0, v788:0, v786:0, v789:0, v790:0, v791:0, v792:0, v793:0, v794:0, v795:0, v796:0, v797:0, v798:0, v799:0, v800:0, 3, 7, 4, 8) :|: v764:0 > 1 && v781:0 > 0 && v781:0 < v764:0 50.68/17.68 Filtered unneeded arguments: 50.68/17.68 f_705(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, x35, x36, x37, x38, x39, x40, x41, x42) -> f_705(x2, x19, x21) 50.68/17.68 Removed division, modulo operations, cleaned up constraints. Obtained 1 rules.P rules: 50.68/17.68 f_705(v764:0, v781:0, sum~cons_1~v821:0) -> f_705(v764:0, 1 + v781:0, v821:0) :|: v781:0 > 0 && v781:0 < v764:0 && v764:0 > 1 && sum~cons_1~v821:0 = 1 + v821:0 50.68/17.68 50.68/17.68 ---------------------------------------- 50.68/17.68 50.68/17.68 (9) 50.68/17.68 Obligation: 50.68/17.68 Rules: 50.68/17.68 f_705(v764:0, v781:0, sum~cons_1~v821:0) -> f_705(v764:0, 1 + v781:0, v821:0) :|: v781:0 > 0 && v781:0 < v764:0 && v764:0 > 1 && sum~cons_1~v821:0 = 1 + v821:0 50.68/17.68 50.68/17.68 ---------------------------------------- 50.68/17.68 50.68/17.68 (10) IntTRSCompressionProof (EQUIVALENT) 50.68/17.68 Compressed rules. 50.68/17.68 ---------------------------------------- 50.68/17.68 50.68/17.68 (11) 50.68/17.68 Obligation: 50.68/17.68 Rules: 50.68/17.68 f_705(v764:0:0, v781:0:0, sum~cons_1~v821:0:0) -> f_705(v764:0:0, 1 + v781:0:0, v821:0:0) :|: v781:0:0 > 0 && v781:0:0 < v764:0:0 && v764:0:0 > 1 && sum~cons_1~v821:0:0 = 1 + v821:0:0 50.68/17.68 50.68/17.68 ---------------------------------------- 50.68/17.68 50.68/17.68 (12) PolynomialOrderProcessor (EQUIVALENT) 50.68/17.68 Found the following polynomial interpretation: 50.68/17.68 [f_705(x, x1, x2)] = x - x1 50.68/17.68 50.68/17.68 The following rules are decreasing: 50.68/17.68 f_705(v764:0:0, v781:0:0, sum~cons_1~v821:0:0) -> f_705(v764:0:0, 1 + v781:0:0, v821:0:0) :|: v781:0:0 > 0 && v781:0:0 < v764:0:0 && v764:0:0 > 1 && sum~cons_1~v821:0:0 = 1 + v821:0:0 50.68/17.68 The following rules are bounded: 50.68/17.68 f_705(v764:0:0, v781:0:0, sum~cons_1~v821:0:0) -> f_705(v764:0:0, 1 + v781:0:0, v821:0:0) :|: v781:0:0 > 0 && v781:0:0 < v764:0:0 && v764:0:0 > 1 && sum~cons_1~v821:0:0 = 1 + v821:0:0 50.68/17.68 50.68/17.68 ---------------------------------------- 50.68/17.68 50.68/17.68 (13) 50.68/17.68 YES 50.68/17.68 50.68/17.68 ---------------------------------------- 50.68/17.68 50.68/17.68 (14) 50.68/17.68 Obligation: 50.68/17.68 SCC 50.68/17.68 ---------------------------------------- 50.68/17.68 50.68/17.68 (15) SCC2IRS (SOUND) 50.68/17.68 Transformed LLVM symbolic execution graph SCC into a rewrite problem. Log: 50.68/17.68 Generated rules. Obtained 15 rulesP rules: 50.68/17.68 f_516(v246, v247, v248, v249, v250, v251, v252, v253, v254, v255, v256, v257, v258, 0, v260, 1, v262, v263, v264, v265, v268, v266, v269, v267, v270, v271, v272, v273, v274, v275, v276, v277, v278, v279, v280, v281, 3, 7, 4, 8) -> f_517(v246, v247, v248, v249, v250, v251, v252, v253, v254, v255, v256, v257, v258, 0, v262, 1, v260, v263, v264, v265, v268, v266, v269, v267, v270, v271, v272, v273, v274, v275, v276, v277, v278, v279, v280, v281, 3, 7, 4, 8) :|: 0 = 0 50.68/17.68 f_517(v246, v247, v248, v249, v250, v251, v252, v253, v254, v255, v256, v257, v258, 0, v262, 1, v260, v263, v264, v265, v268, v266, v269, v267, v270, v271, v272, v273, v274, v275, v276, v277, v278, v279, v280, v281, 3, 7, 4, 8) -> f_518(v246, v247, v248, v249, v250, v251, v252, v253, v254, v255, v256, v257, v258, 0, v262, 1, v260, v263, v264, v265, v268, v266, v269, v267, v270, v271, v272, v273, v274, v275, v276, v277, v278, v279, v280, v281, 3, 7, 2, 4, 8) :|: 0 < v262 && 2 <= v260 && 2 <= v246 50.68/17.68 f_518(v246, v247, v248, v249, v250, v251, v252, v253, v254, v255, v256, v257, v258, 0, v262, 1, v260, v263, v264, v265, v268, v266, v269, v267, v270, v271, v272, v273, v274, v275, v276, v277, v278, v279, v280, v281, 3, 7, 2, 4, 8) -> f_520(v246, v247, v248, v249, v250, v251, v252, v253, v254, v255, v256, v257, v258, 0, v262, 1, v260, v263, v264, v265, v268, v266, v269, v267, v270, v271, v272, v273, v274, v275, v276, v277, v278, v279, v280, v281, 3, 7, 2, 4, 8) :|: 0 = 0 50.68/17.68 f_520(v246, v247, v248, v249, v250, v251, v252, v253, v254, v255, v256, v257, v258, 0, v262, 1, v260, v263, v264, v265, v268, v266, v269, v267, v270, v271, v272, v273, v274, v275, v276, v277, v278, v279, v280, v281, 3, 7, 2, 4, 8) -> f_522(v246, v247, v248, v249, v250, v251, v252, v253, v254, v255, v256, v257, v258, 0, v262, 1, v260, v263, v264, v265, v268, v266, v269, v267, v270, v271, v272, v273, v274, v275, v276, v277, v278, v279, v280, v281, 3, 7, 2, 4, 8) :|: TRUE 50.68/17.68 f_522(v246, v247, v248, v249, v250, v251, v252, v253, v254, v255, v256, v257, v258, 0, v262, 1, v260, v263, v264, v265, v268, v266, v269, v267, v270, v271, v272, v273, v274, v275, v276, v277, v278, v279, v280, v281, 3, 7, 2, 4, 8) -> f_524(v246, v247, v248, v249, v250, v251, v252, v253, v254, v255, v256, v257, v258, 0, v262, 1, v260, v263, v264, v265, v268, v266, v269, v267, v270, v271, v272, v273, v274, v275, v276, v277, v278, v279, v280, v281, 3, 7, 2, 4, 8) :|: 0 = 0 50.68/17.68 f_524(v246, v247, v248, v249, v250, v251, v252, v253, v254, v255, v256, v257, v258, 0, v262, 1, v260, v263, v264, v265, v268, v266, v269, v267, v270, v271, v272, v273, v274, v275, v276, v277, v278, v279, v280, v281, 3, 7, 2, 4, 8) -> f_526(v246, v247, v248, v249, v250, v251, v252, v253, v254, v255, v256, v257, v258, 0, v262, 1, v263, v264, v265, v268, v266, v269, v267, v270, v271, v272, v273, v274, v275, v276, v277, v278, v279, v280, v281, 3, 7, 2, 4, 8) :|: 0 = 0 50.68/17.68 f_526(v246, v247, v248, v249, v250, v251, v252, v253, v254, v255, v256, v257, v258, 0, v262, 1, v263, v264, v265, v268, v266, v269, v267, v270, v271, v272, v273, v274, v275, v276, v277, v278, v279, v280, v281, 3, 7, 2, 4, 8) -> f_528(v246, v247, v248, v249, v250, v251, v252, v253, v254, v255, v256, v257, v258, 0, v262, 1, v282, v263, v264, v265, v268, v266, v269, v267, v270, v271, v272, v273, v274, v275, v276, v277, v278, v279, v280, v281, 3, 7, 2, 4, 8) :|: 1 + v282 = v262 && 0 <= v282 50.68/17.68 f_528(v246, v247, v248, v249, v250, v251, v252, v253, v254, v255, v256, v257, v258, 0, v262, 1, v282, v263, v264, v265, v268, v266, v269, v267, v270, v271, v272, v273, v274, v275, v276, v277, v278, v279, v280, v281, 3, 7, 2, 4, 8) -> f_530(v246, v247, v248, v249, v250, v251, v252, v253, v254, v255, v256, v257, v258, 0, v262, 1, v282, v263, v264, v265, v268, v266, v269, v267, v270, v271, v272, v273, v274, v275, v276, v277, v278, v279, v280, v281, 3, 7, 2, 4, 8) :|: TRUE 50.68/17.68 f_530(v246, v247, v248, v249, v250, v251, v252, v253, v254, v255, v256, v257, v258, 0, v262, 1, v282, v263, v264, v265, v268, v266, v269, v267, v270, v271, v272, v273, v274, v275, v276, v277, v278, v279, v280, v281, 3, 7, 2, 4, 8) -> f_532(v246, v247, v248, v249, v250, v251, v252, v253, v254, v255, v256, v257, v258, 0, v262, 1, v282, v263, v264, v265, v268, v266, v269, v267, v270, v271, v272, v273, v274, v275, v276, v277, v278, v279, v280, v281, 3, 7, 2, 4, 8) :|: 0 = 0 50.68/17.68 f_532(v246, v247, v248, v249, v250, v251, v252, v253, v254, v255, v256, v257, v258, 0, v262, 1, v282, v263, v264, v265, v268, v266, v269, v267, v270, v271, v272, v273, v274, v275, v276, v277, v278, v279, v280, v281, 3, 7, 2, 4, 8) -> f_534(v246, v247, v248, v249, v250, v251, v252, v253, v254, v255, v256, v257, v258, 0, v262, 1, v282, v264, v265, v268, v266, v269, v267, v270, v271, v272, v273, v274, v275, v276, v277, v278, v279, v280, v281, 3, 7, 2, 4, 8) :|: 0 = 0 50.68/17.68 f_534(v246, v247, v248, v249, v250, v251, v252, v253, v254, v255, v256, v257, v258, 0, v262, 1, v282, v264, v265, v268, v266, v269, v267, v270, v271, v272, v273, v274, v275, v276, v277, v278, v279, v280, v281, 3, 7, 2, 4, 8) -> f_536(v246, v247, v248, v249, v250, v251, v252, v253, v254, v255, v256, v257, v258, 0, v262, 1, v282, v264, v284, v265, v268, v266, v269, v267, v270, v271, v272, v273, v274, v275, v276, v277, v278, v279, v280, v281, 3, 7, 2, 4, 8) :|: v284 = 1 + v264 && 2 <= v284 50.68/17.68 f_536(v246, v247, v248, v249, v250, v251, v252, v253, v254, v255, v256, v257, v258, 0, v262, 1, v282, v264, v284, v265, v268, v266, v269, v267, v270, v271, v272, v273, v274, v275, v276, v277, v278, v279, v280, v281, 3, 7, 2, 4, 8) -> f_538(v246, v247, v248, v249, v250, v251, v252, v253, v254, v255, v256, v257, v258, 0, v262, 1, v282, v264, v284, v265, v268, v266, v269, v267, v270, v271, v272, v273, v274, v275, v276, v277, v278, v279, v280, v281, 3, 7, 2, 4, 8) :|: TRUE 50.68/17.68 f_538(v246, v247, v248, v249, v250, v251, v252, v253, v254, v255, v256, v257, v258, 0, v262, 1, v282, v264, v284, v265, v268, v266, v269, v267, v270, v271, v272, v273, v274, v275, v276, v277, v278, v279, v280, v281, 3, 7, 2, 4, 8) -> f_540(v246, v247, v248, v249, v250, v251, v252, v253, v254, v255, v256, v257, v258, 0, v262, 1, v282, v264, v284, v265, v268, v266, v269, v267, v270, v271, v272, v273, v274, v275, v276, v277, v278, v279, v280, v281, 3, 7, 2, 4, 8) :|: TRUE 50.68/17.68 f_540(v246, v247, v248, v249, v250, v251, v252, v253, v254, v255, v256, v257, v258, 0, v262, 1, v282, v264, v284, v265, v268, v266, v269, v267, v270, v271, v272, v273, v274, v275, v276, v277, v278, v279, v280, v281, 3, 7, 2, 4, 8) -> f_515(v246, v247, v248, v249, v250, v251, v252, v253, v254, v255, v256, v257, v258, 0, v262, 1, v282, v264, v284, v265, v268, v266, v269, v267, v270, v271, v272, v273, v274, v275, v276, v277, v278, v279, v280, v281, 3, 7, 4, 8) :|: TRUE 50.68/17.68 f_515(v246, v247, v248, v249, v250, v251, v252, v253, v254, v255, v256, v257, v258, 0, v260, 1, v262, v263, v264, v265, v268, v266, v269, v267, v270, v271, v272, v273, v274, v275, v276, v277, v278, v279, v280, v281, 3, 7, 4, 8) -> f_516(v246, v247, v248, v249, v250, v251, v252, v253, v254, v255, v256, v257, v258, 0, v260, 1, v262, v263, v264, v265, v268, v266, v269, v267, v270, v271, v272, v273, v274, v275, v276, v277, v278, v279, v280, v281, 3, 7, 4, 8) :|: 0 = 0 50.68/17.68 Combined rules. Obtained 1 rulesP rules: 50.68/17.68 f_516(v246:0, v247:0, v248:0, v249:0, v250:0, v251:0, v252:0, v253:0, v254:0, v255:0, v256:0, v257:0, v258:0, 0, v260:0, 1, 1 + v282:0, v263:0, v264:0, v265:0, v268:0, v266:0, v269:0, v267:0, v270:0, v271:0, v272:0, v273:0, v274:0, v275:0, v276:0, v277:0, v278:0, v279:0, v280:0, v281:0, 3, 7, 4, 8) -> f_516(v246:0, v247:0, v248:0, v249:0, v250:0, v251:0, v252:0, v253:0, v254:0, v255:0, v256:0, v257:0, v258:0, 0, 1 + v282:0, 1, v282:0, v264:0, 1 + v264:0, v265:0, v268:0, v266:0, v269:0, v267:0, v270:0, v271:0, v272:0, v273:0, v274:0, v275:0, v276:0, v277:0, v278:0, v279:0, v280:0, v281:0, 3, 7, 4, 8) :|: v260:0 > 1 && v282:0 > -1 && v246:0 > 1 && v264:0 > 0 50.68/17.68 Filtered unneeded arguments: 50.68/17.68 f_516(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, x35, x36, x37, x38, x39, x40) -> f_516(x1, x15, x17, x19) 50.68/17.68 Removed division, modulo operations, cleaned up constraints. Obtained 1 rules.P rules: 50.68/17.68 f_516(v246:0, v260:0, sum~cons_1~v282:0, v264:0) -> f_516(v246:0, 1 + v282:0, v282:0, 1 + v264:0) :|: v282:0 > -1 && v260:0 > 1 && v264:0 > 0 && v246:0 > 1 && sum~cons_1~v282:0 = 1 + v282:0 50.68/17.68 50.68/17.68 ---------------------------------------- 50.68/17.68 50.68/17.68 (16) 50.68/17.68 Obligation: 50.68/17.68 Rules: 50.68/17.68 f_516(v246:0, v260:0, sum~cons_1~v282:0, v264:0) -> f_516(v246:0, 1 + v282:0, v282:0, 1 + v264:0) :|: v282:0 > -1 && v260:0 > 1 && v264:0 > 0 && v246:0 > 1 && sum~cons_1~v282:0 = 1 + v282:0 50.68/17.68 50.68/17.68 ---------------------------------------- 50.68/17.68 50.68/17.68 (17) IntTRSCompressionProof (EQUIVALENT) 50.68/17.68 Compressed rules. 50.68/17.68 ---------------------------------------- 50.68/17.68 50.68/17.68 (18) 50.68/17.68 Obligation: 50.68/17.68 Rules: 50.68/17.68 f_516(v246:0:0, v260:0:0, sum~cons_1~v282:0:0, v264:0:0) -> f_516(v246:0:0, 1 + v282:0:0, v282:0:0, 1 + v264:0:0) :|: v264:0:0 > 0 && v246:0:0 > 1 && v260:0:0 > 1 && v282:0:0 > -1 && sum~cons_1~v282:0:0 = 1 + v282:0:0 50.68/17.68 50.68/17.68 ---------------------------------------- 50.68/17.68 50.68/17.68 (19) RankingReductionPairProof (EQUIVALENT) 50.68/17.68 Interpretation: 50.68/17.68 [ f_516 ] = f_516_3 50.68/17.68 50.68/17.68 The following rules are decreasing: 50.68/17.68 f_516(v246:0:0, v260:0:0, sum~cons_1~v282:0:0, v264:0:0) -> f_516(v246:0:0, 1 + v282:0:0, v282:0:0, 1 + v264:0:0) :|: v264:0:0 > 0 && v246:0:0 > 1 && v260:0:0 > 1 && v282:0:0 > -1 && sum~cons_1~v282:0:0 = 1 + v282:0:0 50.68/17.68 50.68/17.68 The following rules are bounded: 50.68/17.68 f_516(v246:0:0, v260:0:0, sum~cons_1~v282:0:0, v264:0:0) -> f_516(v246:0:0, 1 + v282:0:0, v282:0:0, 1 + v264:0:0) :|: v264:0:0 > 0 && v246:0:0 > 1 && v260:0:0 > 1 && v282:0:0 > -1 && sum~cons_1~v282:0:0 = 1 + v282:0:0 50.68/17.68 50.68/17.68 50.68/17.68 ---------------------------------------- 50.68/17.68 50.68/17.68 (20) 50.68/17.68 YES 51.46/17.73 EOF