12.90/4.67 MAYBE 12.90/4.68 proof of /export/starexec/sandbox/benchmark/theBenchmark.c 12.90/4.68 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 12.90/4.68 12.90/4.68 12.90/4.68 Termination of the given C Problem could not be shown: 12.90/4.68 12.90/4.68 (0) C Problem 12.90/4.68 (1) CToLLVMProof [EQUIVALENT, 165 ms] 12.90/4.68 (2) LLVM problem 12.90/4.68 12.90/4.68 12.90/4.68 ---------------------------------------- 12.90/4.68 12.90/4.68 (0) 12.90/4.68 Obligation: 12.90/4.68 c file /export/starexec/sandbox/benchmark/theBenchmark.c 12.90/4.68 ---------------------------------------- 12.90/4.68 12.90/4.68 (1) CToLLVMProof (EQUIVALENT) 12.90/4.68 Compiled c-file /export/starexec/sandbox/benchmark/theBenchmark.c to LLVM. 12.90/4.68 ---------------------------------------- 12.90/4.68 12.90/4.68 (2) 12.90/4.68 Obligation: 12.90/4.68 LLVM Problem 12.90/4.68 12.90/4.68 Aliases: 12.90/4.68 12.90/4.68 Data layout: 12.90/4.68 12.90/4.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" 12.90/4.68 12.90/4.68 Machine: 12.90/4.68 12.90/4.68 "x86_64-pc-linux-gnu" 12.90/4.68 12.90/4.68 Type definitions: 12.90/4.68 12.90/4.68 struct.sl_item --> BasicStructureType(elementType: *struct.sl_item, elementType: *struct.sl_item, elementType: *struct.sl_item) 12.90/4.68 12.90/4.68 struct.sl --> BasicStructureType(elementType: *struct.sl_item, elementType: *struct.sl_item) 12.90/4.68 12.90/4.68 Global variables: 12.90/4.68 12.90/4.68 Function declarations and definitions: 12.90/4.68 12.90/4.68 *BasicFunctionTypename: "malloc" returnParam: *i8 noalias parameters: (i64) variableLength: false visibilityType: DEFAULT callingConvention: ccc 12.90/4.68 *BasicFunctionTypename: "__VERIFIER_nondet_int" returnParam: i32 parameters: () variableLength: true visibilityType: DEFAULT callingConvention: ccc 12.90/4.68 *BasicFunctionTypename: "free" returnParam: BasicVoidType parameters: (*i8) variableLength: false visibilityType: DEFAULT callingConvention: ccc 12.90/4.68 *BasicFunctionTypename: "alloc_or_die" linkageType: EXTERNALLY_VISIBLE returnParam: *BasicTypeName typeName: struct.sl_itemBasicStructureType(elementType: *struct.sl_item, elementType: *struct.sl_item, elementType: *struct.sl_item) parameters: () variableLength: false visibilityType: DEFAULT callingConvention: ccc 12.90/4.68 0: 12.90/4.68 %pi = alloca *BasicTypeName typeName: struct.sl_itemBasicStructureType(elementType: *struct.sl_item, elementType: *struct.sl_item, elementType: *struct.sl_item), align 8 12.90/4.68 %1 = call noalias *i8 @malloc(i64 24) nounwind 12.90/4.68 %2 = bitcast *i8 %1 to *BasicTypeName typeName: struct.sl_itemBasicStructureType(elementType: *struct.sl_item, elementType: *struct.sl_item, elementType: *struct.sl_item) 12.90/4.68 store %2, %pi 12.90/4.68 %3 = load %pi 12.90/4.68 ret %3 12.90/4.68 12.90/4.68 *BasicFunctionTypename: "create_sl_with_head_and_tail" linkageType: EXTERNALLY_VISIBLE returnParam: *BasicTypeName typeName: struct.slBasicStructureType(elementType: *struct.sl_item, elementType: *struct.sl_item) parameters: () variableLength: false visibilityType: DEFAULT callingConvention: ccc 12.90/4.68 0: 12.90/4.68 %sl = alloca *BasicTypeName typeName: struct.slBasicStructureType(elementType: *struct.sl_item, elementType: *struct.sl_item), align 8 12.90/4.68 %1 = call noalias *i8 @malloc(i64 16) nounwind 12.90/4.68 %2 = bitcast *i8 %1 to *BasicTypeName typeName: struct.slBasicStructureType(elementType: *struct.sl_item, elementType: *struct.sl_item) 12.90/4.68 store %2, %sl 12.90/4.68 %3 = call noalias *i8 @malloc(i64 24) nounwind 12.90/4.68 %4 = bitcast *i8 %3 to *BasicTypeName typeName: struct.sl_itemBasicStructureType(elementType: *struct.sl_item, elementType: *struct.sl_item, elementType: *struct.sl_item) 12.90/4.68 %5 = load %sl 12.90/4.68 %6 = getelementptr %5, 0, 0 12.90/4.68 store %4, %6 12.90/4.68 %7 = call noalias *i8 @malloc(i64 24) nounwind 12.90/4.68 %8 = bitcast *i8 %7 to *BasicTypeName typeName: struct.sl_itemBasicStructureType(elementType: *struct.sl_item, elementType: *struct.sl_item, elementType: *struct.sl_item) 12.90/4.68 %9 = load %sl 12.90/4.68 %10 = getelementptr %9, 0, 1 12.90/4.68 store %8, %10 12.90/4.68 %11 = load %sl 12.90/4.68 %12 = getelementptr %11, 0, 1 12.90/4.68 %13 = load %12 12.90/4.68 %14 = load %sl 12.90/4.68 %15 = getelementptr %14, 0, 0 12.90/4.68 %16 = load %15 12.90/4.68 %17 = getelementptr %16, 0, 0 12.90/4.68 store %13, %17 12.90/4.68 %18 = load %sl 12.90/4.68 %19 = getelementptr %18, 0, 0 12.90/4.68 %20 = load %19 12.90/4.68 %21 = getelementptr %20, 0, 1 12.90/4.68 store %13, %21 12.90/4.68 %22 = load %sl 12.90/4.68 %23 = getelementptr %22, 0, 0 12.90/4.68 %24 = load %23 12.90/4.68 %25 = getelementptr %24, 0, 2 12.90/4.68 store %13, %25 12.90/4.68 %26 = load %sl 12.90/4.68 %27 = getelementptr %26, 0, 1 12.90/4.68 %28 = load %27 12.90/4.68 %29 = getelementptr %28, 0, 0 12.90/4.68 store null, %29 12.90/4.68 %30 = load %sl 12.90/4.68 %31 = getelementptr %30, 0, 1 12.90/4.68 %32 = load %31 12.90/4.68 %33 = getelementptr %32, 0, 1 12.90/4.68 store null, %33 12.90/4.68 %34 = load %sl 12.90/4.68 %35 = getelementptr %34, 0, 1 12.90/4.68 %36 = load %35 12.90/4.68 %37 = getelementptr %36, 0, 2 12.90/4.68 store null, %37 12.90/4.68 %38 = load %sl 12.90/4.68 ret %38 12.90/4.68 12.90/4.68 *BasicFunctionTypename: "sl_random_insert" linkageType: EXTERNALLY_VISIBLE returnParam: BasicVoidType parameters: (sl *BasicTypeName typeName: struct.slBasicStructureType(elementType: *struct.sl_item, elementType: *struct.sl_item)) variableLength: false visibilityType: DEFAULT callingConvention: ccc 12.90/4.68 0: 12.90/4.68 %1 = alloca *BasicTypeName typeName: struct.slBasicStructureType(elementType: *struct.sl_item, elementType: *struct.sl_item), align 8 12.90/4.68 %a1 = alloca *BasicTypeName typeName: struct.sl_itemBasicStructureType(elementType: *struct.sl_item, elementType: *struct.sl_item, elementType: *struct.sl_item), align 8 12.90/4.68 %a2 = alloca *BasicTypeName typeName: struct.sl_itemBasicStructureType(elementType: *struct.sl_item, elementType: *struct.sl_item, elementType: *struct.sl_item), align 8 12.90/4.68 %a3 = alloca *BasicTypeName typeName: struct.sl_itemBasicStructureType(elementType: *struct.sl_item, elementType: *struct.sl_item, elementType: *struct.sl_item), align 8 12.90/4.68 %new = alloca *BasicTypeName typeName: struct.sl_itemBasicStructureType(elementType: *struct.sl_item, elementType: *struct.sl_item, elementType: *struct.sl_item), align 8 12.90/4.68 store %sl, %1 12.90/4.68 %2 = load %1 12.90/4.68 %3 = getelementptr %2, 0, 0 12.90/4.68 %4 = load %3 12.90/4.68 store %4, %a3 12.90/4.68 br %5 12.90/4.68 5: 12.90/4.68 %6 = load %a3 12.90/4.68 %7 = getelementptr %6, 0, 2 12.90/4.68 %8 = load %7 12.90/4.68 %9 = load %1 12.90/4.68 %10 = getelementptr %9, 0, 1 12.90/4.68 %11 = load %10 12.90/4.68 %12 = icmp ne %8 %11 12.90/4.68 br %12, %13, %16 12.90/4.68 13: 12.90/4.68 %14 = call i32 (...)* @__VERIFIER_nondet_int() 12.90/4.68 %15 = icmp ne %14 0 12.90/4.68 br %16 12.90/4.68 16: 12.90/4.68 %17 = phi [0, %5], [%15, %13] 12.90/4.68 br %17, %18, %22 12.90/4.68 18: 12.90/4.68 %19 = load %a3 12.90/4.68 %20 = getelementptr %19, 0, 2 12.90/4.68 %21 = load %20 12.90/4.68 store %21, %a3 12.90/4.68 br %5 12.90/4.68 22: 12.90/4.68 %23 = load %a3 12.90/4.68 store %23, %a2 12.90/4.68 br %24 12.90/4.68 24: 12.90/4.68 %25 = load %a2 12.90/4.68 %26 = getelementptr %25, 0, 1 12.90/4.68 %27 = load %26 12.90/4.68 %28 = load %a3 12.90/4.68 %29 = getelementptr %28, 0, 2 12.90/4.68 %30 = load %29 12.90/4.68 %31 = icmp ne %27 %30 12.90/4.68 br %31, %32, %35 12.90/4.68 32: 12.90/4.68 %33 = call i32 (...)* @__VERIFIER_nondet_int() 12.90/4.68 %34 = icmp ne %33 0 12.90/4.68 br %35 12.90/4.68 35: 12.90/4.68 %36 = phi [0, %24], [%34, %32] 12.90/4.68 br %36, %37, %41 12.90/4.68 37: 12.90/4.68 %38 = load %a2 12.90/4.68 %39 = getelementptr %38, 0, 1 12.90/4.68 %40 = load %39 12.90/4.68 store %40, %a2 12.90/4.68 br %24 12.90/4.68 41: 12.90/4.68 %42 = load %a2 12.90/4.68 store %42, %a1 12.90/4.68 br %43 12.90/4.68 43: 12.90/4.68 %44 = load %a1 12.90/4.68 %45 = getelementptr %44, 0, 0 12.90/4.68 %46 = load %45 12.90/4.68 %47 = load %a2 12.90/4.68 %48 = getelementptr %47, 0, 1 12.90/4.68 %49 = load %48 12.90/4.68 %50 = icmp ne %46 %49 12.90/4.68 br %50, %51, %54 12.90/4.68 51: 12.90/4.68 %52 = call i32 (...)* @__VERIFIER_nondet_int() 12.90/4.68 %53 = icmp ne %52 0 12.90/4.68 br %54 12.90/4.68 54: 12.90/4.68 %55 = phi [0, %43], [%53, %51] 12.90/4.68 br %55, %56, %60 12.90/4.68 56: 12.90/4.68 %57 = load %a1 12.90/4.68 %58 = getelementptr %57, 0, 0 12.90/4.68 %59 = load %58 12.90/4.68 store %59, %a1 12.90/4.68 br %43 12.90/4.68 60: 12.90/4.68 %61 = call noalias *i8 @malloc(i64 24) nounwind 12.90/4.68 %62 = bitcast *i8 %61 to *BasicTypeName typeName: struct.sl_itemBasicStructureType(elementType: *struct.sl_item, elementType: *struct.sl_item, elementType: *struct.sl_item) 12.90/4.68 store %62, %new 12.90/4.68 %63 = load %a1 12.90/4.68 %64 = getelementptr %63, 0, 0 12.90/4.68 %65 = load %64 12.90/4.68 %66 = load %new 12.90/4.68 %67 = getelementptr %66, 0, 0 12.90/4.68 store %65, %67 12.90/4.68 %68 = load %new 12.90/4.68 %69 = load %a1 12.90/4.68 %70 = getelementptr %69, 0, 0 12.90/4.68 store %68, %70 12.90/4.68 %71 = call i32 (...)* @__VERIFIER_nondet_int() 12.90/4.68 %72 = icmp ne %71 0 12.90/4.68 br %72, %73, %94 12.90/4.68 73: 12.90/4.68 %74 = load %a2 12.90/4.68 %75 = getelementptr %74, 0, 1 12.90/4.68 %76 = load %75 12.90/4.68 %77 = load %new 12.90/4.68 %78 = getelementptr %77, 0, 1 12.90/4.68 store %76, %78 12.90/4.68 %79 = load %new 12.90/4.68 %80 = load %a2 12.90/4.68 %81 = getelementptr %80, 0, 1 12.90/4.68 store %79, %81 12.90/4.68 %82 = call i32 (...)* @__VERIFIER_nondet_int() 12.90/4.68 %83 = icmp ne %82 0 12.90/4.68 br %83, %84, %93 12.90/4.68 84: 12.90/4.68 %85 = load %a3 12.90/4.68 %86 = getelementptr %85, 0, 2 12.90/4.68 %87 = load %86 12.90/4.68 %88 = load %new 12.90/4.68 %89 = getelementptr %88, 0, 2 12.90/4.68 store %87, %89 12.90/4.68 %90 = load %new 12.90/4.68 %91 = load %a3 12.90/4.68 %92 = getelementptr %91, 0, 2 12.90/4.68 store %90, %92 12.90/4.68 br %93 12.90/4.68 93: 12.90/4.68 br %94 12.90/4.68 94: 12.90/4.68 ret void 12.90/4.68 12.90/4.68 *BasicFunctionTypename: "destroy_sl" linkageType: EXTERNALLY_VISIBLE returnParam: BasicVoidType parameters: (sl *BasicTypeName typeName: struct.slBasicStructureType(elementType: *struct.sl_item, elementType: *struct.sl_item)) variableLength: false visibilityType: DEFAULT callingConvention: ccc 12.90/4.68 0: 12.90/4.68 %1 = alloca *BasicTypeName typeName: struct.slBasicStructureType(elementType: *struct.sl_item, elementType: *struct.sl_item), align 8 12.90/4.68 %tmp = alloca *BasicTypeName typeName: struct.sl_itemBasicStructureType(elementType: *struct.sl_item, elementType: *struct.sl_item, elementType: *struct.sl_item), align 8 12.90/4.68 store %sl, %1 12.90/4.68 br %2 12.90/4.68 2: 12.90/4.68 %3 = load %1 12.90/4.68 %4 = getelementptr %3, 0, 0 12.90/4.68 %5 = load %4 12.90/4.68 %6 = icmp ne %5 null 12.90/4.68 br %6, %7, %20 12.90/4.68 7: 12.90/4.68 %8 = load %1 12.90/4.68 %9 = getelementptr %8, 0, 0 12.90/4.68 %10 = load %9 12.90/4.68 store %10, %tmp 12.90/4.68 %11 = load %1 12.90/4.68 %12 = getelementptr %11, 0, 0 12.90/4.68 %13 = load %12 12.90/4.68 %14 = getelementptr %13, 0, 0 12.90/4.68 %15 = load %14 12.90/4.68 %16 = load %1 12.90/4.68 %17 = getelementptr %16, 0, 0 12.90/4.68 store %15, %17 12.90/4.68 %18 = load %tmp 12.90/4.68 %19 = bitcast *BasicTypeName typeName: struct.sl_itemBasicStructureType(elementType: *struct.sl_item, elementType: *struct.sl_item, elementType: *struct.sl_item) %18 to *i8 12.90/4.68 Unnamed Call-Instruction = call BasicVoidType @free(*i8 %19) nounwind 12.90/4.68 br %2 12.90/4.68 20: 12.90/4.68 %21 = load %1 12.90/4.68 %22 = bitcast *BasicTypeName typeName: struct.slBasicStructureType(elementType: *struct.sl_item, elementType: *struct.sl_item) %21 to *i8 12.90/4.68 Unnamed Call-Instruction = call BasicVoidType @free(*i8 %22) nounwind 12.90/4.68 ret void 12.90/4.68 12.90/4.68 *BasicFunctionTypename: "main" linkageType: EXTERNALLY_VISIBLE returnParam: i32 parameters: () variableLength: false visibilityType: DEFAULT callingConvention: ccc 12.90/4.68 0: 12.90/4.68 %1 = alloca i32, align 4 12.90/4.68 %sl = alloca *BasicTypeName typeName: struct.slBasicStructureType(elementType: *struct.sl_item, elementType: *struct.sl_item), align 8 12.90/4.68 store 0, %1 12.90/4.68 %2 = call *BasicTypeName typeName: struct.slBasicStructureType(elementType: *struct.sl_item, elementType: *struct.sl_item) @create_sl_with_head_and_tail() 12.90/4.68 store %2, %sl 12.90/4.68 br %3 12.90/4.68 3: 12.90/4.68 %4 = call i32 (...)* @__VERIFIER_nondet_int() 12.90/4.68 %5 = icmp ne %4 0 12.90/4.68 br %5, %6, %8 12.90/4.68 6: 12.90/4.68 %7 = load %sl 12.90/4.68 Unnamed Call-Instruction = call BasicVoidType @sl_random_insert(*BasicTypeName typeName: struct.slBasicStructureType(elementType: *struct.sl_item, elementType: *struct.sl_item) %7) 12.90/4.68 br %3 12.90/4.68 8: 12.90/4.68 %9 = load %sl 12.90/4.68 Unnamed Call-Instruction = call BasicVoidType @destroy_sl(*BasicTypeName typeName: struct.slBasicStructureType(elementType: *struct.sl_item, elementType: *struct.sl_item) %9) 12.90/4.68 ret 0 12.90/4.68 12.90/4.68 12.90/4.68 Analyze Termination of all function calls matching the pattern: 12.90/4.68 main() 12.90/4.72 EOF