/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, 175 ms] (2) LLVM problem (3) LLVMToTerminationGraphProof [EQUIVALENT, 4987 ms] (4) LLVM Symbolic Execution Graph (5) SymbolicExecutionGraphToSCCProof [SOUND, 0 ms] (6) LLVM Symbolic Execution SCC (7) SCC2IRS [SOUND, 143 ms] (8) IntTRS (9) IntTRSCompressionProof [EQUIVALENT, 0 ms] (10) IntTRS (11) PolynomialOrderProcessor [EQUIVALENT, 12 ms] (12) 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 1 br %17, %18, %24 18: %19 = load %x_ref %20 = load %19 %21 = load %y_ref %22 = load %21 %23 = icmp slt %20 %22 br %24 24: %25 = phi [0, %14], [%23, %18] br %25, %26, %37 26: %27 = load %x_ref %28 = load %27 %29 = load %x_ref %30 = load %29 %31 = mul %28 %30 %32 = load %x_ref store %31, %32 %33 = load %c %34 = load %33 %35 = add %34 1 %36 = load %c store %35, %36 br %14 37: %38 = load %c %39 = load %38 ret %39 *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 1 SCC. ---------------------------------------- (6) Obligation: SCC ---------------------------------------- (7) SCC2IRS (SOUND) Transformed LLVM symbolic execution graph SCC into a rewrite problem. Log: Generated rules. Obtained 27 rulesP rules: f_498(v954, v955, v956, v957, v958, v959, v960, v961, v962, v963, v964, 1, v966, v967, v968, v969, v970, v971, v972, v973, v974, v975, v976, v977, v978, 0, 3, 7, 2, 4, 8) -> f_499(v954, v955, v956, v957, v958, v959, v960, v961, v962, v963, v966, 1, v964, v967, v968, v969, v970, v971, v972, v973, v974, v975, v976, v977, v978, 0, 3, 7, 2, 4, 8) :|: 0 = 0 f_499(v954, v955, v956, v957, v958, v959, v960, v961, v962, v963, v966, 1, v964, v967, v968, v969, v970, v971, v972, v973, v974, v975, v976, v977, v978, 0, 3, 7, 2, 4, 8) -> f_500(v954, v955, v956, v957, v958, v959, v960, v961, v962, v963, v966, 1, v964, v967, v968, v969, v970, v971, v972, v973, v974, v975, v976, v977, v978, 0, 3, 7, 2, 4, 8) :|: 1 < v966 f_500(v954, v955, v956, v957, v958, v959, v960, v961, v962, v963, v966, 1, v964, v967, v968, v969, v970, v971, v972, v973, v974, v975, v976, v977, v978, 0, 3, 7, 2, 4, 8) -> f_502(v954, v955, v956, v957, v958, v959, v960, v961, v962, v963, v966, 1, v964, v967, v968, v969, v970, v971, v972, v973, v974, v975, v976, v977, v978, 0, 3, 7, 2, 4, 8) :|: 0 = 0 f_502(v954, v955, v956, v957, v958, v959, v960, v961, v962, v963, v966, 1, v964, v967, v968, v969, v970, v971, v972, v973, v974, v975, v976, v977, v978, 0, 3, 7, 2, 4, 8) -> f_504(v954, v955, v956, v957, v958, v959, v960, v961, v962, v963, v966, 1, v964, v967, v968, v969, v970, v971, v972, v973, v974, v975, v976, v977, v978, 0, 3, 7, 2, 4, 8) :|: TRUE f_504(v954, v955, v956, v957, v958, v959, v960, v961, v962, v963, v966, 1, v964, v967, v968, v969, v970, v971, v972, v973, v974, v975, v976, v977, v978, 0, 3, 7, 2, 4, 8) -> f_506(v954, v955, v956, v957, v958, v959, v960, v961, v962, v963, v966, 1, v964, v967, v968, v969, v970, v971, v972, v973, v974, v975, v976, v977, v978, 0, 3, 7, 2, 4, 8) :|: 0 = 0 f_506(v954, v955, v956, v957, v958, v959, v960, v961, v962, v963, v966, 1, v964, v967, v968, v969, v970, v971, v972, v973, v974, v975, v976, v977, v978, 0, 3, 7, 2, 4, 8) -> f_508(v954, v955, v956, v957, v958, v959, v960, v961, v962, v963, v966, 1, v964, v967, v968, v969, v970, v971, v972, v973, v974, v975, v976, v977, v978, 0, 3, 7, 2, 4, 8) :|: 0 = 0 f_508(v954, v955, v956, v957, v958, v959, v960, v961, v962, v963, v966, 1, v964, v967, v968, v969, v970, v971, v972, v973, v974, v975, v976, v977, v978, 0, 3, 7, 2, 4, 8) -> f_510(v954, v955, v956, v957, v958, v959, v960, v961, v962, v963, v966, 1, v964, v967, v968, v969, v970, v971, v972, v973, v974, v975, v976, v977, v978, 0, 3, 7, 2, 4, 8) :|: 0 = 0 f_510(v954, v955, v956, v957, v958, v959, v960, v961, v962, v963, v966, 1, v964, v967, v968, v969, v970, v971, v972, v973, v974, v975, v976, v977, v978, 0, 3, 7, 2, 4, 8) -> f_512(v954, v955, v956, v957, v958, v959, v960, v961, v962, v963, v966, 1, v964, v967, v968, v969, v970, v971, v972, v973, v974, v975, v976, v977, v978, 0, 3, 7, 2, 4, 8) :|: 0 = 0 f_512(v954, v955, v956, v957, v958, v959, v960, v961, v962, v963, v966, 1, v964, v967, v968, v969, v970, v971, v972, v973, v974, v975, v976, v977, v978, 0, 3, 7, 2, 4, 8) -> f_514(v954, v955, v956, v957, v958, v959, v960, v961, v962, v963, v966, 1, v964, v967, v968, v969, v970, v971, v972, v973, v974, v975, v976, v977, v978, 0, 3, 7, 2, 4, 8) :|: v966 < v955 f_514(v954, v955, v956, v957, v958, v959, v960, v961, v962, v963, v966, 1, v964, v967, v968, v969, v970, v971, v972, v973, v974, v975, v976, v977, v978, 0, 3, 7, 2, 4, 8) -> f_516(v954, v955, v956, v957, v958, v959, v960, v961, v962, v963, v966, 1, v964, v967, v968, v969, v970, v971, v972, v973, v974, v975, v976, v977, v978, 0, 3, 7, 2, 4, 8) :|: 0 = 0 f_516(v954, v955, v956, v957, v958, v959, v960, v961, v962, v963, v966, 1, v964, v967, v968, v969, v970, v971, v972, v973, v974, v975, v976, v977, v978, 0, 3, 7, 2, 4, 8) -> f_518(v954, v955, v956, v957, v958, v959, v960, v961, v962, v963, v966, 1, v964, v967, v968, v969, v970, v971, v972, v973, v974, v975, v976, v977, v978, 0, 3, 7, 2, 4, 8) :|: 0 = 0 f_518(v954, v955, v956, v957, v958, v959, v960, v961, v962, v963, v966, 1, v964, v967, v968, v969, v970, v971, v972, v973, v974, v975, v976, v977, v978, 0, 3, 7, 2, 4, 8) -> f_520(v954, v955, v956, v957, v958, v959, v960, v961, v962, v963, v966, 1, v964, v967, v968, v969, v970, v971, v972, v973, v974, v975, v976, v977, v978, 0, 3, 7, 2, 4, 8) :|: TRUE f_520(v954, v955, v956, v957, v958, v959, v960, v961, v962, v963, v966, 1, v964, v967, v968, v969, v970, v971, v972, v973, v974, v975, v976, v977, v978, 0, 3, 7, 2, 4, 8) -> f_522(v954, v955, v956, v957, v958, v959, v960, v961, v962, v963, v966, 1, v964, v967, v968, v969, v970, v971, v972, v973, v974, v975, v976, v977, v978, 0, 3, 7, 2, 4, 8) :|: 0 = 0 f_522(v954, v955, v956, v957, v958, v959, v960, v961, v962, v963, v966, 1, v964, v967, v968, v969, v970, v971, v972, v973, v974, v975, v976, v977, v978, 0, 3, 7, 2, 4, 8) -> f_524(v954, v955, v956, v957, v958, v959, v960, v961, v962, v963, v966, 1, v964, v967, v968, v969, v970, v971, v972, v973, v974, v975, v976, v977, v978, 0, 3, 7, 2, 4, 8) :|: 0 = 0 f_524(v954, v955, v956, v957, v958, v959, v960, v961, v962, v963, v966, 1, v964, v967, v968, v969, v970, v971, v972, v973, v974, v975, v976, v977, v978, 0, 3, 7, 2, 4, 8) -> f_526(v954, v955, v956, v957, v958, v959, v960, v961, v962, v963, v966, 1, v964, v967, v968, v969, v970, v971, v972, v973, v974, v975, v976, v977, v978, 0, 3, 7, 2, 4, 8) :|: 0 = 0 f_526(v954, v955, v956, v957, v958, v959, v960, v961, v962, v963, v966, 1, v964, v967, v968, v969, v970, v971, v972, v973, v974, v975, v976, v977, v978, 0, 3, 7, 2, 4, 8) -> f_528(v954, v955, v956, v957, v958, v959, v960, v961, v962, v963, v966, 1, v967, v968, v969, v970, v971, v972, v973, v974, v975, v976, v977, v978, 0, 3, 7, 2, 4, 8) :|: 0 = 0 f_528(v954, v955, v956, v957, v958, v959, v960, v961, v962, v963, v966, 1, v967, v968, v969, v970, v971, v972, v973, v974, v975, v976, v977, v978, 0, 3, 7, 2, 4, 8) -> f_529(v954, v955, v956, v957, v958, v959, v960, v961, v962, v963, v966, 1, v1107, v967, v968, v969, v970, v971, v972, v973, v974, v975, v976, v977, v978, 0, 3, 7, 2, 4, 8) :|: v1107 = v966 * v966 f_529(v954, v955, v956, v957, v958, v959, v960, v961, v962, v963, v966, 1, v1107, v967, v968, v969, v970, v971, v972, v973, v974, v975, v976, v977, v978, 0, 3, 7, 2, 4, 8) -> f_530(v954, v955, v956, v957, v958, v959, v960, v961, v962, v963, v966, 1, v1107, v967, v968, v969, v970, v971, v972, v973, v974, v975, v976, v977, v978, 0, 3, 7, 2, 4, 8) :|: 0 = 0 f_530(v954, v955, v956, v957, v958, v959, v960, v961, v962, v963, v966, 1, v1107, v967, v968, v969, v970, v971, v972, v973, v974, v975, v976, v977, v978, 0, 3, 7, 2, 4, 8) -> f_531(v954, v955, v956, v957, v958, v959, v960, v961, v962, v963, v966, 1, v1107, v967, v968, v969, v970, v971, v972, v973, v974, v975, v976, v977, v978, 0, 3, 7, 2, 4, 8) :|: TRUE f_531(v954, v955, v956, v957, v958, v959, v960, v961, v962, v963, v966, 1, v1107, v967, v968, v969, v970, v971, v972, v973, v974, v975, v976, v977, v978, 0, 3, 7, 2, 4, 8) -> f_532(v954, v955, v956, v957, v958, v959, v960, v961, v962, v963, v966, 1, v1107, v967, v968, v969, v970, v971, v972, v973, v974, v975, v976, v977, v978, 0, 3, 7, 2, 4, 8) :|: 0 = 0 f_532(v954, v955, v956, v957, v958, v959, v960, v961, v962, v963, v966, 1, v1107, v967, v968, v969, v970, v971, v972, v973, v974, v975, v976, v977, v978, 0, 3, 7, 2, 4, 8) -> f_533(v954, v955, v956, v957, v958, v959, v960, v961, v962, v963, v966, 1, v1107, v968, v969, v970, v971, v972, v973, v974, v975, v976, v977, v978, 0, 3, 7, 2, 4, 8) :|: 0 = 0 f_533(v954, v955, v956, v957, v958, v959, v960, v961, v962, v963, v966, 1, v1107, v968, v969, v970, v971, v972, v973, v974, v975, v976, v977, v978, 0, 3, 7, 2, 4, 8) -> f_534(v954, v955, v956, v957, v958, v959, v960, v961, v962, v963, v966, 1, v1107, v968, v1109, v969, v970, v971, v972, v973, v974, v975, v976, v977, v978, 0, 3, 7, 2, 4, 8) :|: v1109 = 1 + v968 && 2 <= v1109 f_534(v954, v955, v956, v957, v958, v959, v960, v961, v962, v963, v966, 1, v1107, v968, v1109, v969, v970, v971, v972, v973, v974, v975, v976, v977, v978, 0, 3, 7, 2, 4, 8) -> f_535(v954, v955, v956, v957, v958, v959, v960, v961, v962, v963, v966, 1, v1107, v968, v1109, v969, v970, v971, v972, v973, v974, v975, v976, v977, v978, 0, 3, 7, 2, 4, 8) :|: 0 = 0 f_535(v954, v955, v956, v957, v958, v959, v960, v961, v962, v963, v966, 1, v1107, v968, v1109, v969, v970, v971, v972, v973, v974, v975, v976, v977, v978, 0, 3, 7, 2, 4, 8) -> f_536(v954, v955, v956, v957, v958, v959, v960, v961, v962, v963, v966, 1, v1107, v968, v1109, v969, v970, v971, v972, v973, v974, v975, v976, v977, v978, 0, 3, 7, 2, 4, 8) :|: TRUE f_536(v954, v955, v956, v957, v958, v959, v960, v961, v962, v963, v966, 1, v1107, v968, v1109, v969, v970, v971, v972, v973, v974, v975, v976, v977, v978, 0, 3, 7, 2, 4, 8) -> f_537(v954, v955, v956, v957, v958, v959, v960, v961, v962, v963, v966, 1, v1107, v968, v1109, v969, v970, v971, v972, v973, v974, v975, v976, v977, v978, 0, 3, 7, 2, 4, 8) :|: TRUE f_537(v954, v955, v956, v957, v958, v959, v960, v961, v962, v963, v966, 1, v1107, v968, v1109, v969, v970, v971, v972, v973, v974, v975, v976, v977, v978, 0, 3, 7, 2, 4, 8) -> f_497(v954, v955, v956, v957, v958, v959, v960, v961, v962, v963, v966, 1, v1107, v968, v1109, v969, v970, v971, v972, v973, v974, v975, v976, v977, v978, 0, 3, 7, 2, 4, 8) :|: TRUE f_497(v954, v955, v956, v957, v958, v959, v960, v961, v962, v963, v964, 1, v966, v967, v968, v969, v970, v971, v972, v973, v974, v975, v976, v977, v978, 0, 3, 7, 2, 4, 8) -> f_498(v954, v955, v956, v957, v958, v959, v960, v961, v962, v963, v964, 1, v966, v967, v968, v969, v970, v971, v972, v973, v974, v975, v976, v977, v978, 0, 3, 7, 2, 4, 8) :|: 0 = 0 Combined rules. Obtained 1 rulesP rules: f_498(v954:0, v955:0, v956:0, v957:0, v958:0, v959:0, v960:0, v961:0, v962:0, v963:0, v964:0, 1, v966:0, v967:0, v968:0, v969:0, v970:0, v971:0, v972:0, v973:0, v974:0, v975:0, v976:0, v977:0, v978:0, 0, 3, 7, 2, 4, 8) -> f_498(v954:0, v955:0, v956:0, v957:0, v958:0, v959:0, v960:0, v961:0, v962:0, v963:0, v966:0, 1, v966:0 * v966:0, v968:0, 1 + v968:0, v969:0, v970:0, v971:0, v972:0, v973:0, v974:0, v975:0, v976:0, v977:0, v978:0, 0, 3, 7, 2, 4, 8) :|: v966:0 > 1 && v968:0 > 0 && v966:0 < v955:0 Filtered unneeded arguments: f_498(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) -> f_498(x2, x13, x15) Removed division, modulo operations, cleaned up constraints. Obtained 1 rules.P rules: f_498(v955:0, v966:0, v968:0) -> f_498(v955:0, v966:0 * v966:0, 1 + v968:0) :|: v968:0 > 0 && v966:0 < v955:0 && v966:0 > 1 ---------------------------------------- (8) Obligation: Rules: f_498(v955:0, v966:0, v968:0) -> f_498(v955:0, v966:0 * v966:0, 1 + v968:0) :|: v968:0 > 0 && v966:0 < v955:0 && v966:0 > 1 ---------------------------------------- (9) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (10) Obligation: Rules: f_498(v955:0:0, v966:0:0, v968:0:0) -> f_498(v955:0:0, v966:0:0 * v966:0:0, 1 + v968:0:0) :|: v968:0:0 > 0 && v966:0:0 < v955:0:0 && v966:0:0 > 1 ---------------------------------------- (11) PolynomialOrderProcessor (EQUIVALENT) Found the following polynomial interpretation: [f_498(x, x1, x2)] = -2 + x - x1 + x2 The following rules are decreasing: f_498(v955:0:0, v966:0:0, v968:0:0) -> f_498(v955:0:0, v966:0:0 * v966:0:0, 1 + v968:0:0) :|: v968:0:0 > 0 && v966:0:0 < v955:0:0 && v966:0:0 > 1 The following rules are bounded: f_498(v955:0:0, v966:0:0, v968:0:0) -> f_498(v955:0:0, v966:0:0 * v966:0:0, 1 + v968:0:0) :|: v968:0:0 > 0 && v966:0:0 < v955:0:0 && v966:0:0 > 1 ---------------------------------------- (12) YES