/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, 178 ms] (2) LLVM problem (3) LLVMToTerminationGraphProof [EQUIVALENT, 2991 ms] (4) LLVM Symbolic Execution Graph (5) SymbolicExecutionGraphToSCCProof [SOUND, 0 ms] (6) AND (7) LLVM Symbolic Execution SCC (8) SCC2IRS [SOUND, 117 ms] (9) IntTRS (10) IRS2T2 [EQUIVALENT, 0 ms] (11) T2IntSys (12) T2 [EQUIVALENT, 573 ms] (13) YES (14) LLVM Symbolic Execution SCC (15) SCC2IRS [SOUND, 127 ms] (16) IntTRS (17) IntTRSCompressionProof [EQUIVALENT, 0 ms] (18) IntTRS (19) RankingReductionPairProof [EQUIVALENT, 13 ms] (20) YES ---------------------------------------- (0) Obligation: c file /export/starexec/sandbox/benchmark/theBenchmark.c ---------------------------------------- (1) CToLLVMProof (EQUIVALENT) Compiled c-file /export/starexec/sandbox/benchmark/theBenchmark.c to LLVM. ---------------------------------------- (2) Obligation: LLVM Problem Aliases: Data layout: "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64-S128" Machine: "x86_64-pc-linux-gnu" Type definitions: Global variables: Function declarations and definitions: *BasicFunctionTypename: "__VERIFIER_nondet_int" returnParam: i32 parameters: () variableLength: false visibilityType: DEFAULT callingConvention: ccc *BasicFunctionTypename: "main" linkageType: EXTERNALLY_VISIBLE returnParam: i32 parameters: () variableLength: false visibilityType: DEFAULT callingConvention: ccc 0: %1 = alloca i32, align 4 %x = alloca *i32, align 8 %y = alloca *i32, align 8 %z = alloca *i32, align 8 %m = alloca *i32, align 8 %n = alloca *i32, align 8 store 0, %1 %2 = alloca i8, numElementsLit: 4 %3 = bitcast *i8 %2 to *i32 store %3, %x %4 = alloca i8, numElementsLit: 4 %5 = bitcast *i8 %4 to *i32 store %5, %y %6 = alloca i8, numElementsLit: 4 %7 = bitcast *i8 %6 to *i32 store %7, %z %8 = alloca i8, numElementsLit: 4 %9 = bitcast *i8 %8 to *i32 store %9, %m %10 = alloca i8, numElementsLit: 4 %11 = bitcast *i8 %10 to *i32 store %11, %n %12 = call i32 @__VERIFIER_nondet_int() %13 = icmp ne %12 0 br %13, %14, %16 14: %15 = load %x store 1, %15 br %18 16: %17 = load %x store -1, %17 br %18 18: %19 = load %x %20 = load %19 %21 = icmp sgt %20 0 br %21, %22, %26 22: %23 = load %x %24 = load %23 %25 = add %24 1 store %25, %23 br %30 26: %27 = load %x %28 = load %27 %29 = add %28 -1 store %29, %27 br %30 30: %31 = load %x %32 = load %31 %33 = icmp sgt %32 0 br %33, %34, %38 34: %35 = load %x %36 = load %35 %37 = add %36 1 store %37, %35 br %42 38: %39 = load %x %40 = load %39 %41 = add %40 -1 store %41, %39 br %42 42: %43 = load %x %44 = load %43 %45 = icmp sgt %44 0 br %45, %46, %50 46: %47 = load %x %48 = load %47 %49 = add %48 1 store %49, %47 br %54 50: %51 = load %x %52 = load %51 %53 = add %52 -1 store %53, %51 br %54 54: %55 = load %x %56 = load %55 %57 = icmp sgt %56 0 br %57, %58, %62 58: %59 = load %x %60 = load %59 %61 = add %60 1 store %61, %59 br %66 62: %63 = load %x %64 = load %63 %65 = add %64 -1 store %65, %63 br %66 66: %67 = load %x %68 = load %67 %69 = icmp sgt %68 0 br %69, %70, %74 70: %71 = load %x %72 = load %71 %73 = add %72 1 store %73, %71 br %78 74: %75 = load %x %76 = load %75 %77 = add %76 -1 store %77, %75 br %78 78: %79 = load %x %80 = load %79 %81 = icmp sgt %80 0 br %81, %82, %86 82: %83 = load %x %84 = load %83 %85 = add %84 1 store %85, %83 br %90 86: %87 = load %x %88 = load %87 %89 = add %88 -1 store %89, %87 br %90 90: %91 = load %x %92 = load %91 %93 = icmp sgt %92 0 br %93, %94, %98 94: %95 = load %x %96 = load %95 %97 = add %96 1 store %97, %95 br %102 98: %99 = load %x %100 = load %99 %101 = add %100 -1 store %101, %99 br %102 102: %103 = load %x %104 = load %103 %105 = icmp sgt %104 0 br %105, %106, %110 106: %107 = load %x %108 = load %107 %109 = add %108 1 store %109, %107 br %114 110: %111 = load %x %112 = load %111 %113 = add %112 -1 store %113, %111 br %114 114: br %115 115: %116 = load %y %117 = load %116 %118 = icmp slt %117 100 br %118, %119, %123 119: %120 = load %z %121 = load %120 %122 = icmp slt %121 100 br %123 123: %124 = phi [0, %115], [%122, %119] br %124, %125, %138 125: %126 = load %y %127 = load %126 %128 = load %x %129 = load %128 %130 = add %127 %129 %131 = load %y store %130, %131 %132 = load %z %133 = load %132 %134 = load %x %135 = load %134 %136 = sub %133 %135 %137 = load %z store %136, %137 br %115 138: ret 0 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 26 rulesP rules: f_764(v1, v3, v5, v7, v9, v11, v13, v16, v19, v22, v25, 0, -1, -2, -3, -4, -5, -6, -7, -8, -9, v31, 1, v35, v234, v238, v2, v4, v6, v8, v10, v12, v14, v17, v20, v23, v26, 3, 7, 9, 4, 8, 99, 90, 108) -> f_766(v1, v3, v5, v7, v9, v11, v13, v16, v19, v22, v25, 0, -1, -2, -3, -4, -5, -6, -7, -8, -9, v234, 1, v35, v31, v238, v2, v4, v6, v8, v10, v12, v14, v17, v20, v23, v26, 3, 7, 9, 4, 8, 99, 90, 108) :|: 0 = 0 f_766(v1, v3, v5, v7, v9, v11, v13, v16, v19, v22, v25, 0, -1, -2, -3, -4, -5, -6, -7, -8, -9, v234, 1, v35, v31, v238, v2, v4, v6, v8, v10, v12, v14, v17, v20, v23, v26, 3, 7, 9, 4, 8, 99, 90, 108) -> f_769(v1, v3, v5, v7, v9, v11, v13, v16, v19, v22, v25, 0, -1, -2, -3, -4, -5, -6, -7, -8, -9, v234, 1, v35, v31, v238, v2, v4, v6, v8, v10, v12, v14, v17, v20, v23, v26, 3, 7, 9, 4, 8, 99, 90, 108) :|: 0 = 0 f_769(v1, v3, v5, v7, v9, v11, v13, v16, v19, v22, v25, 0, -1, -2, -3, -4, -5, -6, -7, -8, -9, v234, 1, v35, v31, v238, v2, v4, v6, v8, v10, v12, v14, v17, v20, v23, v26, 3, 7, 9, 4, 8, 99, 90, 108) -> f_772(v1, v3, v5, v7, v9, v11, v13, v16, v19, v22, v25, 0, -1, -2, -3, -4, -5, -6, -7, -8, -9, v234, 1, v35, v31, v238, v2, v4, v6, v8, v10, v12, v14, v17, v20, v23, v26, 3, 7, 9, 4, 8, 99, 90, 108) :|: TRUE f_772(v1, v3, v5, v7, v9, v11, v13, v16, v19, v22, v25, 0, -1, -2, -3, -4, -5, -6, -7, -8, -9, v234, 1, v35, v31, v238, v2, v4, v6, v8, v10, v12, v14, v17, v20, v23, v26, 3, 7, 9, 4, 8, 99, 90, 108) -> f_775(v1, v3, v5, v7, v9, v11, v13, v16, v19, v22, v25, 0, -1, -2, -3, -4, -5, -6, -7, -8, -9, v234, 1, v35, v31, v238, v2, v4, v6, v8, v10, v12, v14, v17, v20, v23, v26, 3, 7, 9, 4, 8, 99, 90, 108) :|: 0 = 0 f_775(v1, v3, v5, v7, v9, v11, v13, v16, v19, v22, v25, 0, -1, -2, -3, -4, -5, -6, -7, -8, -9, v234, 1, v35, v31, v238, v2, v4, v6, v8, v10, v12, v14, v17, v20, v23, v26, 3, 7, 9, 4, 8, 99, 90, 108) -> f_778(v1, v3, v5, v7, v9, v11, v13, v16, v19, v22, v25, 0, -1, -2, -3, -4, -5, -6, -7, -8, -9, v234, 1, v238, v31, v35, v2, v4, v6, v8, v10, v12, v14, v17, v20, v23, v26, 3, 7, 9, 4, 8, 99, 90, 108) :|: 0 = 0 f_778(v1, v3, v5, v7, v9, v11, v13, v16, v19, v22, v25, 0, -1, -2, -3, -4, -5, -6, -7, -8, -9, v234, 1, v238, v31, v35, v2, v4, v6, v8, v10, v12, v14, v17, v20, v23, v26, 3, 7, 9, 4, 8, 99, 90, 108) -> f_780(v1, v3, v5, v7, v9, v11, v13, v16, v19, v22, v25, 0, -1, -2, -3, -4, -5, -6, -7, -8, -9, v234, 1, v238, v31, v35, v2, v4, v6, v8, v10, v12, v14, v17, v20, v23, v26, 3, 7, 9, 4, 8, 99, 90) :|: v238 < 100 && v35 <= 90 f_780(v1, v3, v5, v7, v9, v11, v13, v16, v19, v22, v25, 0, -1, -2, -3, -4, -5, -6, -7, -8, -9, v234, 1, v238, v31, v35, v2, v4, v6, v8, v10, v12, v14, v17, v20, v23, v26, 3, 7, 9, 4, 8, 99, 90) -> f_783(v1, v3, v5, v7, v9, v11, v13, v16, v19, v22, v25, 0, -1, -2, -3, -4, -5, -6, -7, -8, -9, v234, 1, v238, v31, v35, v2, v4, v6, v8, v10, v12, v14, v17, v20, v23, v26, 3, 7, 9, 4, 8, 99, 90) :|: 0 = 0 f_783(v1, v3, v5, v7, v9, v11, v13, v16, v19, v22, v25, 0, -1, -2, -3, -4, -5, -6, -7, -8, -9, v234, 1, v238, v31, v35, v2, v4, v6, v8, v10, v12, v14, v17, v20, v23, v26, 3, 7, 9, 4, 8, 99, 90) -> f_786(v1, v3, v5, v7, v9, v11, v13, v16, v19, v22, v25, 0, -1, -2, -3, -4, -5, -6, -7, -8, -9, v234, 1, v238, v31, v35, v2, v4, v6, v8, v10, v12, v14, v17, v20, v23, v26, 3, 7, 9, 4, 8, 99, 90) :|: 0 = 0 f_786(v1, v3, v5, v7, v9, v11, v13, v16, v19, v22, v25, 0, -1, -2, -3, -4, -5, -6, -7, -8, -9, v234, 1, v238, v31, v35, v2, v4, v6, v8, v10, v12, v14, v17, v20, v23, v26, 3, 7, 9, 4, 8, 99, 90) -> f_789(v1, v3, v5, v7, v9, v11, v13, v16, v19, v22, v25, 0, -1, -2, -3, -4, -5, -6, -7, -8, -9, v234, 1, v238, v31, v35, v2, v4, v6, v8, v10, v12, v14, v17, v20, v23, v26, 3, 7, 9, 4, 8, 99, 90) :|: TRUE f_789(v1, v3, v5, v7, v9, v11, v13, v16, v19, v22, v25, 0, -1, -2, -3, -4, -5, -6, -7, -8, -9, v234, 1, v238, v31, v35, v2, v4, v6, v8, v10, v12, v14, v17, v20, v23, v26, 3, 7, 9, 4, 8, 99, 90) -> f_792(v1, v3, v5, v7, v9, v11, v13, v16, v19, v22, v25, 0, -1, -2, -3, -4, -5, -6, -7, -8, -9, v234, 1, v238, v31, v35, v2, v4, v6, v8, v10, v12, v14, v17, v20, v23, v26, 3, 7, 9, 4, 8, 99, 90) :|: 0 = 0 f_792(v1, v3, v5, v7, v9, v11, v13, v16, v19, v22, v25, 0, -1, -2, -3, -4, -5, -6, -7, -8, -9, v234, 1, v238, v31, v35, v2, v4, v6, v8, v10, v12, v14, v17, v20, v23, v26, 3, 7, 9, 4, 8, 99, 90) -> f_794(v1, v3, v5, v7, v9, v11, v13, v16, v19, v22, v25, 0, -1, -2, -3, -4, -5, -6, -7, -8, -9, v234, 1, v238, v35, v2, v4, v6, v8, v10, v12, v14, v17, v20, v23, v26, 3, 7, 9, 4, 8, 90, 99) :|: 0 = 0 f_794(v1, v3, v5, v7, v9, v11, v13, v16, v19, v22, v25, 0, -1, -2, -3, -4, -5, -6, -7, -8, -9, v234, 1, v238, v35, v2, v4, v6, v8, v10, v12, v14, v17, v20, v23, v26, 3, 7, 9, 4, 8, 90, 99) -> f_796(v1, v3, v5, v7, v9, v11, v13, v16, v19, v22, v25, 0, -1, -2, -3, -4, -5, -6, -7, -8, -9, v234, 1, v238, v35, v2, v4, v6, v8, v10, v12, v14, v17, v20, v23, v26, 3, 7, 9, 4, 8, 90, 99) :|: 0 = 0 f_796(v1, v3, v5, v7, v9, v11, v13, v16, v19, v22, v25, 0, -1, -2, -3, -4, -5, -6, -7, -8, -9, v234, 1, v238, v35, v2, v4, v6, v8, v10, v12, v14, v17, v20, v23, v26, 3, 7, 9, 4, 8, 90, 99) -> f_798(v1, v3, v5, v7, v9, v11, v13, v16, v19, v22, v25, 0, -1, -2, -3, -4, -5, -6, -7, -8, -9, v234, 1, v238, v35, v2, v4, v6, v8, v10, v12, v14, v17, v20, v23, v26, 3, 7, 9, 4, 8, 90, 99) :|: 0 = 0 f_798(v1, v3, v5, v7, v9, v11, v13, v16, v19, v22, v25, 0, -1, -2, -3, -4, -5, -6, -7, -8, -9, v234, 1, v238, v35, v2, v4, v6, v8, v10, v12, v14, v17, v20, v23, v26, 3, 7, 9, 4, 8, 90, 99) -> f_800(v1, v3, v5, v7, v9, v11, v13, v16, v19, v22, v25, 0, -1, -2, -3, -4, -5, -6, -7, -8, -9, v234, 1, v238, v932, v35, v2, v4, v6, v8, v10, v12, v14, v17, v20, v23, v26, 3, 7, 9, 4, 8, 90, 99, 81) :|: 9 + v932 = v234 && v932 <= 81 f_800(v1, v3, v5, v7, v9, v11, v13, v16, v19, v22, v25, 0, -1, -2, -3, -4, -5, -6, -7, -8, -9, v234, 1, v238, v932, v35, v2, v4, v6, v8, v10, v12, v14, v17, v20, v23, v26, 3, 7, 9, 4, 8, 90, 99, 81) -> f_802(v1, v3, v5, v7, v9, v11, v13, v16, v19, v22, v25, 0, -1, -2, -3, -4, -5, -6, -7, -8, -9, v234, 1, v238, v932, v35, v2, v4, v6, v8, v10, v12, v14, v17, v20, v23, v26, 3, 7, 9, 4, 8, 90, 99, 81) :|: 0 = 0 f_802(v1, v3, v5, v7, v9, v11, v13, v16, v19, v22, v25, 0, -1, -2, -3, -4, -5, -6, -7, -8, -9, v234, 1, v238, v932, v35, v2, v4, v6, v8, v10, v12, v14, v17, v20, v23, v26, 3, 7, 9, 4, 8, 90, 99, 81) -> f_804(v1, v3, v5, v7, v9, v11, v13, v16, v19, v22, v25, 0, -1, -2, -3, -4, -5, -6, -7, -8, -9, v234, 1, v238, v932, v35, v2, v4, v6, v8, v10, v12, v14, v17, v20, v23, v26, 3, 7, 9, 4, 8, 90, 99, 81) :|: TRUE f_804(v1, v3, v5, v7, v9, v11, v13, v16, v19, v22, v25, 0, -1, -2, -3, -4, -5, -6, -7, -8, -9, v234, 1, v238, v932, v35, v2, v4, v6, v8, v10, v12, v14, v17, v20, v23, v26, 3, 7, 9, 4, 8, 90, 99, 81) -> f_806(v1, v3, v5, v7, v9, v11, v13, v16, v19, v22, v25, 0, -1, -2, -3, -4, -5, -6, -7, -8, -9, v234, 1, v238, v932, v35, v2, v4, v6, v8, v10, v12, v14, v17, v20, v23, v26, 3, 7, 9, 4, 8, 90, 99, 81) :|: 0 = 0 f_806(v1, v3, v5, v7, v9, v11, v13, v16, v19, v22, v25, 0, -1, -2, -3, -4, -5, -6, -7, -8, -9, v234, 1, v238, v932, v35, v2, v4, v6, v8, v10, v12, v14, v17, v20, v23, v26, 3, 7, 9, 4, 8, 90, 99, 81) -> f_808(v1, v3, v5, v7, v9, v11, v13, v16, v19, v22, v25, 0, -1, -2, -3, -4, -5, -6, -7, -8, -9, v234, 1, v238, v932, v2, v4, v6, v8, v10, v12, v14, v17, v20, v23, v26, 3, 7, 9, 4, 8, 90, 99, 81) :|: 0 = 0 f_808(v1, v3, v5, v7, v9, v11, v13, v16, v19, v22, v25, 0, -1, -2, -3, -4, -5, -6, -7, -8, -9, v234, 1, v238, v932, v2, v4, v6, v8, v10, v12, v14, v17, v20, v23, v26, 3, 7, 9, 4, 8, 90, 99, 81) -> f_810(v1, v3, v5, v7, v9, v11, v13, v16, v19, v22, v25, 0, -1, -2, -3, -4, -5, -6, -7, -8, -9, v234, 1, v238, v932, v2, v4, v6, v8, v10, v12, v14, v17, v20, v23, v26, 3, 7, 9, 4, 8, 90, 99, 81) :|: 0 = 0 f_810(v1, v3, v5, v7, v9, v11, v13, v16, v19, v22, v25, 0, -1, -2, -3, -4, -5, -6, -7, -8, -9, v234, 1, v238, v932, v2, v4, v6, v8, v10, v12, v14, v17, v20, v23, v26, 3, 7, 9, 4, 8, 90, 99, 81) -> f_812(v1, v3, v5, v7, v9, v11, v13, v16, v19, v22, v25, 0, -1, -2, -3, -4, -5, -6, -7, -8, -9, v234, 1, v238, v932, v2, v4, v6, v8, v10, v12, v14, v17, v20, v23, v26, 3, 7, 9, 4, 8, 90, 99, 81) :|: 0 = 0 f_812(v1, v3, v5, v7, v9, v11, v13, v16, v19, v22, v25, 0, -1, -2, -3, -4, -5, -6, -7, -8, -9, v234, 1, v238, v932, v2, v4, v6, v8, v10, v12, v14, v17, v20, v23, v26, 3, 7, 9, 4, 8, 90, 99, 81) -> f_814(v1, v3, v5, v7, v9, v11, v13, v16, v19, v22, v25, 0, -1, -2, -3, -4, -5, -6, -7, -8, -9, v234, 1, v238, v932, v936, v2, v4, v6, v8, v10, v12, v14, v17, v20, v23, v26, 3, 7, 9, 4, 8, 90, 99, 81, 108) :|: v936 = 9 + v238 && v936 <= 108 f_814(v1, v3, v5, v7, v9, v11, v13, v16, v19, v22, v25, 0, -1, -2, -3, -4, -5, -6, -7, -8, -9, v234, 1, v238, v932, v936, v2, v4, v6, v8, v10, v12, v14, v17, v20, v23, v26, 3, 7, 9, 4, 8, 90, 99, 81, 108) -> f_816(v1, v3, v5, v7, v9, v11, v13, v16, v19, v22, v25, 0, -1, -2, -3, -4, -5, -6, -7, -8, -9, v234, 1, v238, v932, v936, v2, v4, v6, v8, v10, v12, v14, v17, v20, v23, v26, 3, 7, 9, 4, 8, 90, 99, 81, 108) :|: 0 = 0 f_816(v1, v3, v5, v7, v9, v11, v13, v16, v19, v22, v25, 0, -1, -2, -3, -4, -5, -6, -7, -8, -9, v234, 1, v238, v932, v936, v2, v4, v6, v8, v10, v12, v14, v17, v20, v23, v26, 3, 7, 9, 4, 8, 90, 99, 81, 108) -> f_818(v1, v3, v5, v7, v9, v11, v13, v16, v19, v22, v25, 0, -1, -2, -3, -4, -5, -6, -7, -8, -9, v234, 1, v238, v932, v936, v2, v4, v6, v8, v10, v12, v14, v17, v20, v23, v26, 3, 7, 9, 4, 8, 90, 99, 81, 108) :|: TRUE f_818(v1, v3, v5, v7, v9, v11, v13, v16, v19, v22, v25, 0, -1, -2, -3, -4, -5, -6, -7, -8, -9, v234, 1, v238, v932, v936, v2, v4, v6, v8, v10, v12, v14, v17, v20, v23, v26, 3, 7, 9, 4, 8, 90, 99, 81, 108) -> f_820(v1, v3, v5, v7, v9, v11, v13, v16, v19, v22, v25, 0, -1, -2, -3, -4, -5, -6, -7, -8, -9, v234, 1, v238, v932, v936, v2, v4, v6, v8, v10, v12, v14, v17, v20, v23, v26, 3, 7, 9, 4, 8, 90, 99, 81, 108) :|: TRUE f_820(v1, v3, v5, v7, v9, v11, v13, v16, v19, v22, v25, 0, -1, -2, -3, -4, -5, -6, -7, -8, -9, v234, 1, v238, v932, v936, v2, v4, v6, v8, v10, v12, v14, v17, v20, v23, v26, 3, 7, 9, 4, 8, 90, 99, 81, 108) -> f_762(v1, v3, v5, v7, v9, v11, v13, v16, v19, v22, v25, 0, -1, -2, -3, -4, -5, -6, -7, -8, -9, v234, 1, v238, v932, v936, v2, v4, v6, v8, v10, v12, v14, v17, v20, v23, v26, 3, 7, 9, 4, 8, 99, 90, 108) :|: TRUE f_762(v1, v3, v5, v7, v9, v11, v13, v16, v19, v22, v25, 0, -1, -2, -3, -4, -5, -6, -7, -8, -9, v31, 1, v35, v234, v238, v2, v4, v6, v8, v10, v12, v14, v17, v20, v23, v26, 3, 7, 9, 4, 8, 99, 90, 108) -> f_764(v1, v3, v5, v7, v9, v11, v13, v16, v19, v22, v25, 0, -1, -2, -3, -4, -5, -6, -7, -8, -9, v31, 1, v35, v234, v238, v2, v4, v6, v8, v10, v12, v14, v17, v20, v23, v26, 3, 7, 9, 4, 8, 99, 90, 108) :|: 0 = 0 Combined rules. Obtained 1 rulesP rules: f_764(v1:0, v3:0, v5:0, v7:0, v9:0, v11:0, v13:0, v16:0, v19:0, v22:0, v25:0, 0, -1, -2, -3, -4, -5, -6, -7, -8, -9, v31:0, 1, v35:0, 9 + v932:0, v238:0, v2:0, v4:0, v6:0, v8:0, v10:0, v12:0, v14:0, v17:0, v20:0, v23:0, v26:0, 3, 7, 9, 4, 8, 99, 90, 108) -> f_764(v1:0, v3:0, v5:0, v7:0, v9:0, v11:0, v13:0, v16:0, v19:0, v22:0, v25:0, 0, -1, -2, -3, -4, -5, -6, -7, -8, -9, 9 + v932:0, 1, v238:0, v932:0, 9 + v238:0, v2:0, v4:0, v6:0, v8:0, v10:0, v12:0, v14:0, v17:0, v20:0, v23:0, v26:0, 3, 7, 9, 4, 8, 99, 90, 108) :|: v35:0 < 91 && v238:0 < 100 && v932:0 < 82 Filtered unneeded arguments: f_764(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, x43, x44, x45) -> f_764(x24, x25, x26) Removed division, modulo operations, cleaned up constraints. Obtained 1 rules.P rules: f_764(v35:0, sum~cons_9~v932:0, v238:0) -> f_764(v238:0, v932:0, 9 + v238:0) :|: v238:0 < 100 && v932:0 < 82 && v35:0 < 91 && sum~cons_9~v932:0 = 9 + v932:0 ---------------------------------------- (9) Obligation: Rules: f_764(v35:0, sum~cons_9~v932:0, v238:0) -> f_764(v238:0, v932:0, 9 + v238:0) :|: v238:0 < 100 && v932:0 < 82 && v35:0 < 91 && sum~cons_9~v932:0 = 9 + v932:0 ---------------------------------------- (10) IRS2T2 (EQUIVALENT) Transformed input IRS into an integer transition system.Used the following mapping from defined symbols to location IDs: (f_764_3,1) ---------------------------------------- (11) Obligation: START: 0; FROM: 0; TO: 1; FROM: 1; oldX0 := x0; oldX1 := x1; oldX2 := x2; oldX3 := oldX1 - 9; assume(oldX2 < 100 && oldX3 < 82 && oldX0 < 91 && oldX1 = 9 + oldX3); x0 := oldX2; x1 := oldX1 - 9; x2 := 9 + oldX2; TO: 1; ---------------------------------------- (12) T2 (EQUIVALENT) Initially, performed program simplifications using lexicographic rank functions: * Removed transitions 1, 3, 4 using the following rank functions: - Rank function 1: RF for loc. 5: 9-2*x2 RF for loc. 6: -2*x2 Bound for (chained) transitions 4: -198 - Rank function 2: RF for loc. 5: -2*x2 RF for loc. 6: -9-2*x2 Bound for (chained) transitions 3: -207 - Rank function 3: RF for loc. 5: 0 RF for loc. 6: -1 Bound for (chained) transitions 1: 0 ---------------------------------------- (13) YES ---------------------------------------- (14) Obligation: SCC ---------------------------------------- (15) SCC2IRS (SOUND) Transformed LLVM symbolic execution graph SCC into a rewrite problem. Log: Generated rules. Obtained 26 rulesP rules: f_763(v1, v3, v5, v7, v9, v11, v13, v16, v19, v22, v25, v28, 1, 2, 3, 4, 5, 6, 7, 8, 9, v29, v33, v233, v237, v2, v4, v6, v8, v10, v12, v14, v17, v20, v23, v26, 0, 99, 108, 90) -> f_765(v1, v3, v5, v7, v9, v11, v13, v16, v19, v22, v25, v28, 1, 2, 3, 4, 5, 6, 7, 8, 9, v233, v33, v29, v237, v2, v4, v6, v8, v10, v12, v14, v17, v20, v23, v26, 0, 99, 108, 90) :|: 0 = 0 f_765(v1, v3, v5, v7, v9, v11, v13, v16, v19, v22, v25, v28, 1, 2, 3, 4, 5, 6, 7, 8, 9, v233, v33, v29, v237, v2, v4, v6, v8, v10, v12, v14, v17, v20, v23, v26, 0, 99, 108, 90) -> f_767(v1, v3, v5, v7, v9, v11, v13, v16, v19, v22, v25, v28, 1, 2, 3, 4, 5, 6, 7, 8, 9, v233, v33, v29, v237, v2, v4, v6, v8, v10, v12, v14, v17, v20, v23, v26, 0, 90, 99) :|: v233 < 100 && v29 <= 90 f_767(v1, v3, v5, v7, v9, v11, v13, v16, v19, v22, v25, v28, 1, 2, 3, 4, 5, 6, 7, 8, 9, v233, v33, v29, v237, v2, v4, v6, v8, v10, v12, v14, v17, v20, v23, v26, 0, 90, 99) -> f_770(v1, v3, v5, v7, v9, v11, v13, v16, v19, v22, v25, v28, 1, 2, 3, 4, 5, 6, 7, 8, 9, v233, v33, v29, v237, v2, v4, v6, v8, v10, v12, v14, v17, v20, v23, v26, 0, 90, 99) :|: 0 = 0 f_770(v1, v3, v5, v7, v9, v11, v13, v16, v19, v22, v25, v28, 1, 2, 3, 4, 5, 6, 7, 8, 9, v233, v33, v29, v237, v2, v4, v6, v8, v10, v12, v14, v17, v20, v23, v26, 0, 90, 99) -> f_773(v1, v3, v5, v7, v9, v11, v13, v16, v19, v22, v25, v28, 1, 2, 3, 4, 5, 6, 7, 8, 9, v233, v33, v29, v237, v2, v4, v6, v8, v10, v12, v14, v17, v20, v23, v26, 0, 90, 99) :|: TRUE f_773(v1, v3, v5, v7, v9, v11, v13, v16, v19, v22, v25, v28, 1, 2, 3, 4, 5, 6, 7, 8, 9, v233, v33, v29, v237, v2, v4, v6, v8, v10, v12, v14, v17, v20, v23, v26, 0, 90, 99) -> f_776(v1, v3, v5, v7, v9, v11, v13, v16, v19, v22, v25, v28, 1, 2, 3, 4, 5, 6, 7, 8, 9, v233, v33, v29, v237, v2, v4, v6, v8, v10, v12, v14, v17, v20, v23, v26, 0, 90, 99) :|: 0 = 0 f_776(v1, v3, v5, v7, v9, v11, v13, v16, v19, v22, v25, v28, 1, 2, 3, 4, 5, 6, 7, 8, 9, v233, v33, v29, v237, v2, v4, v6, v8, v10, v12, v14, v17, v20, v23, v26, 0, 90, 99) -> f_779(v1, v3, v5, v7, v9, v11, v13, v16, v19, v22, v25, v28, 1, 2, 3, 4, 5, 6, 7, 8, 9, v233, v237, v29, v33, v2, v4, v6, v8, v10, v12, v14, v17, v20, v23, v26, 0, 90, 99) :|: 0 = 0 f_779(v1, v3, v5, v7, v9, v11, v13, v16, v19, v22, v25, v28, 1, 2, 3, 4, 5, 6, 7, 8, 9, v233, v237, v29, v33, v2, v4, v6, v8, v10, v12, v14, v17, v20, v23, v26, 0, 90, 99) -> f_782(v1, v3, v5, v7, v9, v11, v13, v16, v19, v22, v25, v28, 1, 2, 3, 4, 5, 6, 7, 8, 9, v233, v237, v29, v33, v2, v4, v6, v8, v10, v12, v14, v17, v20, v23, v26, 0, 90, 99) :|: 0 = 0 f_782(v1, v3, v5, v7, v9, v11, v13, v16, v19, v22, v25, v28, 1, 2, 3, 4, 5, 6, 7, 8, 9, v233, v237, v29, v33, v2, v4, v6, v8, v10, v12, v14, v17, v20, v23, v26, 0, 90, 99) -> f_785(v1, v3, v5, v7, v9, v11, v13, v16, v19, v22, v25, v28, 1, 2, 3, 4, 5, 6, 7, 8, 9, v233, v237, v29, v33, v2, v4, v6, v8, v10, v12, v14, v17, v20, v23, v26, 0, 90, 99) :|: 0 = 0 f_785(v1, v3, v5, v7, v9, v11, v13, v16, v19, v22, v25, v28, 1, 2, 3, 4, 5, 6, 7, 8, 9, v233, v237, v29, v33, v2, v4, v6, v8, v10, v12, v14, v17, v20, v23, v26, 0, 90, 99) -> f_788(v1, v3, v5, v7, v9, v11, v13, v16, v19, v22, v25, v28, 1, 2, 3, 4, 5, 6, 7, 8, 9, v233, v237, v29, v33, v2, v4, v6, v8, v10, v12, v14, v17, v20, v23, v26, 0, 90, 99) :|: TRUE f_788(v1, v3, v5, v7, v9, v11, v13, v16, v19, v22, v25, v28, 1, 2, 3, 4, 5, 6, 7, 8, 9, v233, v237, v29, v33, v2, v4, v6, v8, v10, v12, v14, v17, v20, v23, v26, 0, 90, 99) -> f_791(v1, v3, v5, v7, v9, v11, v13, v16, v19, v22, v25, v28, 1, 2, 3, 4, 5, 6, 7, 8, 9, v233, v237, v29, v33, v2, v4, v6, v8, v10, v12, v14, v17, v20, v23, v26, 0, 90, 99) :|: 0 = 0 f_791(v1, v3, v5, v7, v9, v11, v13, v16, v19, v22, v25, v28, 1, 2, 3, 4, 5, 6, 7, 8, 9, v233, v237, v29, v33, v2, v4, v6, v8, v10, v12, v14, v17, v20, v23, v26, 0, 90, 99) -> f_793(v1, v3, v5, v7, v9, v11, v13, v16, v19, v22, v25, v28, 1, 2, 3, 4, 5, 6, 7, 8, 9, v233, v237, v33, v2, v4, v6, v8, v10, v12, v14, v17, v20, v23, v26, 0, 99, 90) :|: 0 = 0 f_793(v1, v3, v5, v7, v9, v11, v13, v16, v19, v22, v25, v28, 1, 2, 3, 4, 5, 6, 7, 8, 9, v233, v237, v33, v2, v4, v6, v8, v10, v12, v14, v17, v20, v23, v26, 0, 99, 90) -> f_795(v1, v3, v5, v7, v9, v11, v13, v16, v19, v22, v25, v28, 1, 2, 3, 4, 5, 6, 7, 8, 9, v233, v237, v33, v2, v4, v6, v8, v10, v12, v14, v17, v20, v23, v26, 0, 99, 90) :|: 0 = 0 f_795(v1, v3, v5, v7, v9, v11, v13, v16, v19, v22, v25, v28, 1, 2, 3, 4, 5, 6, 7, 8, 9, v233, v237, v33, v2, v4, v6, v8, v10, v12, v14, v17, v20, v23, v26, 0, 99, 90) -> f_797(v1, v3, v5, v7, v9, v11, v13, v16, v19, v22, v25, v28, 1, 2, 3, 4, 5, 6, 7, 8, 9, v233, v237, v33, v2, v4, v6, v8, v10, v12, v14, v17, v20, v23, v26, 0, 99, 90) :|: 0 = 0 f_797(v1, v3, v5, v7, v9, v11, v13, v16, v19, v22, v25, v28, 1, 2, 3, 4, 5, 6, 7, 8, 9, v233, v237, v33, v2, v4, v6, v8, v10, v12, v14, v17, v20, v23, v26, 0, 99, 90) -> f_799(v1, v3, v5, v7, v9, v11, v13, v16, v19, v22, v25, v28, 1, 2, 3, 4, 5, 6, 7, 8, 9, v233, v237, v931, v33, v2, v4, v6, v8, v10, v12, v14, v17, v20, v23, v26, 0, 99, 90, 108) :|: v931 = 9 + v233 && v931 <= 108 f_799(v1, v3, v5, v7, v9, v11, v13, v16, v19, v22, v25, v28, 1, 2, 3, 4, 5, 6, 7, 8, 9, v233, v237, v931, v33, v2, v4, v6, v8, v10, v12, v14, v17, v20, v23, v26, 0, 99, 90, 108) -> f_801(v1, v3, v5, v7, v9, v11, v13, v16, v19, v22, v25, v28, 1, 2, 3, 4, 5, 6, 7, 8, 9, v233, v237, v931, v33, v2, v4, v6, v8, v10, v12, v14, v17, v20, v23, v26, 0, 99, 90, 108) :|: 0 = 0 f_801(v1, v3, v5, v7, v9, v11, v13, v16, v19, v22, v25, v28, 1, 2, 3, 4, 5, 6, 7, 8, 9, v233, v237, v931, v33, v2, v4, v6, v8, v10, v12, v14, v17, v20, v23, v26, 0, 99, 90, 108) -> f_803(v1, v3, v5, v7, v9, v11, v13, v16, v19, v22, v25, v28, 1, 2, 3, 4, 5, 6, 7, 8, 9, v233, v237, v931, v33, v2, v4, v6, v8, v10, v12, v14, v17, v20, v23, v26, 0, 99, 90, 108) :|: TRUE f_803(v1, v3, v5, v7, v9, v11, v13, v16, v19, v22, v25, v28, 1, 2, 3, 4, 5, 6, 7, 8, 9, v233, v237, v931, v33, v2, v4, v6, v8, v10, v12, v14, v17, v20, v23, v26, 0, 99, 90, 108) -> f_805(v1, v3, v5, v7, v9, v11, v13, v16, v19, v22, v25, v28, 1, 2, 3, 4, 5, 6, 7, 8, 9, v233, v237, v931, v33, v2, v4, v6, v8, v10, v12, v14, v17, v20, v23, v26, 0, 99, 90, 108) :|: 0 = 0 f_805(v1, v3, v5, v7, v9, v11, v13, v16, v19, v22, v25, v28, 1, 2, 3, 4, 5, 6, 7, 8, 9, v233, v237, v931, v33, v2, v4, v6, v8, v10, v12, v14, v17, v20, v23, v26, 0, 99, 90, 108) -> f_807(v1, v3, v5, v7, v9, v11, v13, v16, v19, v22, v25, v28, 1, 2, 3, 4, 5, 6, 7, 8, 9, v233, v237, v931, v2, v4, v6, v8, v10, v12, v14, v17, v20, v23, v26, 0, 99, 90, 108) :|: 0 = 0 f_807(v1, v3, v5, v7, v9, v11, v13, v16, v19, v22, v25, v28, 1, 2, 3, 4, 5, 6, 7, 8, 9, v233, v237, v931, v2, v4, v6, v8, v10, v12, v14, v17, v20, v23, v26, 0, 99, 90, 108) -> f_809(v1, v3, v5, v7, v9, v11, v13, v16, v19, v22, v25, v28, 1, 2, 3, 4, 5, 6, 7, 8, 9, v233, v237, v931, v2, v4, v6, v8, v10, v12, v14, v17, v20, v23, v26, 0, 99, 90, 108) :|: 0 = 0 f_809(v1, v3, v5, v7, v9, v11, v13, v16, v19, v22, v25, v28, 1, 2, 3, 4, 5, 6, 7, 8, 9, v233, v237, v931, v2, v4, v6, v8, v10, v12, v14, v17, v20, v23, v26, 0, 99, 90, 108) -> f_811(v1, v3, v5, v7, v9, v11, v13, v16, v19, v22, v25, v28, 1, 2, 3, 4, 5, 6, 7, 8, 9, v233, v237, v931, v2, v4, v6, v8, v10, v12, v14, v17, v20, v23, v26, 0, 99, 90, 108) :|: 0 = 0 f_811(v1, v3, v5, v7, v9, v11, v13, v16, v19, v22, v25, v28, 1, 2, 3, 4, 5, 6, 7, 8, 9, v233, v237, v931, v2, v4, v6, v8, v10, v12, v14, v17, v20, v23, v26, 0, 99, 90, 108) -> f_813(v1, v3, v5, v7, v9, v11, v13, v16, v19, v22, v25, v28, 1, 2, 3, 4, 5, 6, 7, 8, 9, v233, v237, v931, v935, v2, v4, v6, v8, v10, v12, v14, v17, v20, v23, v26, 0, 99, 90, 108, 81) :|: 9 + v935 = v237 && v935 <= 81 f_813(v1, v3, v5, v7, v9, v11, v13, v16, v19, v22, v25, v28, 1, 2, 3, 4, 5, 6, 7, 8, 9, v233, v237, v931, v935, v2, v4, v6, v8, v10, v12, v14, v17, v20, v23, v26, 0, 99, 90, 108, 81) -> f_815(v1, v3, v5, v7, v9, v11, v13, v16, v19, v22, v25, v28, 1, 2, 3, 4, 5, 6, 7, 8, 9, v233, v237, v931, v935, v2, v4, v6, v8, v10, v12, v14, v17, v20, v23, v26, 0, 99, 90, 108, 81) :|: 0 = 0 f_815(v1, v3, v5, v7, v9, v11, v13, v16, v19, v22, v25, v28, 1, 2, 3, 4, 5, 6, 7, 8, 9, v233, v237, v931, v935, v2, v4, v6, v8, v10, v12, v14, v17, v20, v23, v26, 0, 99, 90, 108, 81) -> f_817(v1, v3, v5, v7, v9, v11, v13, v16, v19, v22, v25, v28, 1, 2, 3, 4, 5, 6, 7, 8, 9, v233, v237, v931, v935, v2, v4, v6, v8, v10, v12, v14, v17, v20, v23, v26, 0, 99, 90, 108, 81) :|: TRUE f_817(v1, v3, v5, v7, v9, v11, v13, v16, v19, v22, v25, v28, 1, 2, 3, 4, 5, 6, 7, 8, 9, v233, v237, v931, v935, v2, v4, v6, v8, v10, v12, v14, v17, v20, v23, v26, 0, 99, 90, 108, 81) -> f_819(v1, v3, v5, v7, v9, v11, v13, v16, v19, v22, v25, v28, 1, 2, 3, 4, 5, 6, 7, 8, 9, v233, v237, v931, v935, v2, v4, v6, v8, v10, v12, v14, v17, v20, v23, v26, 0, 99, 90, 108, 81) :|: TRUE f_819(v1, v3, v5, v7, v9, v11, v13, v16, v19, v22, v25, v28, 1, 2, 3, 4, 5, 6, 7, 8, 9, v233, v237, v931, v935, v2, v4, v6, v8, v10, v12, v14, v17, v20, v23, v26, 0, 99, 90, 108, 81) -> f_761(v1, v3, v5, v7, v9, v11, v13, v16, v19, v22, v25, v28, 1, 2, 3, 4, 5, 6, 7, 8, 9, v233, v237, v931, v935, v2, v4, v6, v8, v10, v12, v14, v17, v20, v23, v26, 0, 99, 108, 90) :|: TRUE f_761(v1, v3, v5, v7, v9, v11, v13, v16, v19, v22, v25, v28, 1, 2, 3, 4, 5, 6, 7, 8, 9, v29, v33, v233, v237, v2, v4, v6, v8, v10, v12, v14, v17, v20, v23, v26, 0, 99, 108, 90) -> f_763(v1, v3, v5, v7, v9, v11, v13, v16, v19, v22, v25, v28, 1, 2, 3, 4, 5, 6, 7, 8, 9, v29, v33, v233, v237, v2, v4, v6, v8, v10, v12, v14, v17, v20, v23, v26, 0, 99, 108, 90) :|: 0 = 0 Combined rules. Obtained 1 rulesP rules: f_763(v1:0, v3:0, v5:0, v7:0, v9:0, v11:0, v13:0, v16:0, v19:0, v22:0, v25:0, v28:0, 1, 2, 3, 4, 5, 6, 7, 8, 9, v29:0, v33:0, v233:0, 9 + v935:0, v2:0, v4:0, v6:0, v8:0, v10:0, v12:0, v14:0, v17:0, v20:0, v23:0, v26:0, 0, 99, 108, 90) -> f_763(v1:0, v3:0, v5:0, v7:0, v9:0, v11:0, v13:0, v16:0, v19:0, v22:0, v25:0, v28:0, 1, 2, 3, 4, 5, 6, 7, 8, 9, v233:0, 9 + v935:0, 9 + v233:0, v935:0, v2:0, v4:0, v6:0, v8:0, v10:0, v12:0, v14:0, v17:0, v20:0, v23:0, v26:0, 0, 99, 108, 90) :|: v29:0 < 91 && v233:0 < 100 && v935:0 < 82 Filtered unneeded arguments: f_763(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_763(x22, x24, x25) Removed division, modulo operations, cleaned up constraints. Obtained 1 rules.P rules: f_763(v29:0, v233:0, sum~cons_9~v935:0) -> f_763(v233:0, 9 + v233:0, v935:0) :|: v233:0 < 100 && v935:0 < 82 && v29:0 < 91 && sum~cons_9~v935:0 = 9 + v935:0 ---------------------------------------- (16) Obligation: Rules: f_763(v29:0, v233:0, sum~cons_9~v935:0) -> f_763(v233:0, 9 + v233:0, v935:0) :|: v233:0 < 100 && v935:0 < 82 && v29:0 < 91 && sum~cons_9~v935:0 = 9 + v935:0 ---------------------------------------- (17) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (18) Obligation: Rules: f_763(v29:0:0, v233:0:0, sum~cons_9~v935:0:0) -> f_763(v233:0:0, 9 + v233:0:0, v935:0:0) :|: v233:0:0 < 100 && v935:0:0 < 82 && v29:0:0 < 91 && sum~cons_9~v935:0:0 = 9 + v935:0:0 ---------------------------------------- (19) RankingReductionPairProof (EQUIVALENT) Interpretation: [ f_763 ] = -1/9*f_763_2 The following rules are decreasing: f_763(v29:0:0, v233:0:0, sum~cons_9~v935:0:0) -> f_763(v233:0:0, 9 + v233:0:0, v935:0:0) :|: v233:0:0 < 100 && v935:0:0 < 82 && v29:0:0 < 91 && sum~cons_9~v935:0:0 = 9 + v935:0:0 The following rules are bounded: f_763(v29:0:0, v233:0:0, sum~cons_9~v935:0:0) -> f_763(v233:0:0, 9 + v233:0:0, v935:0:0) :|: v233:0:0 < 100 && v935:0:0 < 82 && v29:0:0 < 91 && sum~cons_9~v935:0:0 = 9 + v935:0:0 ---------------------------------------- (20) YES