10.83/3.95 MAYBE 10.83/3.96 proof of /export/starexec/sandbox2/benchmark/theBenchmark.c 10.83/3.96 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 10.83/3.96 10.83/3.96 10.83/3.96 Termination of the given C Problem could not be shown: 10.83/3.96 10.83/3.96 (0) C Problem 10.83/3.96 (1) CToLLVMProof [EQUIVALENT, 167 ms] 10.83/3.96 (2) LLVM problem 10.83/3.96 10.83/3.96 10.83/3.96 ---------------------------------------- 10.83/3.96 10.83/3.96 (0) 10.83/3.96 Obligation: 10.83/3.96 c file /export/starexec/sandbox2/benchmark/theBenchmark.c 10.83/3.96 ---------------------------------------- 10.83/3.96 10.83/3.96 (1) CToLLVMProof (EQUIVALENT) 10.83/3.96 Compiled c-file /export/starexec/sandbox2/benchmark/theBenchmark.c to LLVM. 10.83/3.96 ---------------------------------------- 10.83/3.96 10.83/3.96 (2) 10.83/3.96 Obligation: 10.83/3.96 LLVM Problem 10.83/3.96 10.83/3.96 Aliases: 10.83/3.96 10.83/3.96 Data layout: 10.83/3.96 10.83/3.96 "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" 10.83/3.96 10.83/3.96 Machine: 10.83/3.96 10.83/3.96 "x86_64-pc-linux-gnu" 10.83/3.96 10.83/3.96 Type definitions: 10.83/3.96 10.83/3.96 struct.TLItem --> BasicStructureType(elementType: *struct.TLItem, elementType: *struct.DItem) 10.83/3.96 10.83/3.96 struct.DItem --> BasicStructureType(elementType: *struct.DItem, elementType: i32) 10.83/3.96 10.83/3.96 Global variables: 10.83/3.96 10.83/3.96 Function declarations and definitions: 10.83/3.96 10.83/3.96 *BasicFunctionTypename: "__VERIFIER_nondet_int" returnParam: i32 parameters: () variableLength: false visibilityType: DEFAULT callingConvention: ccc 10.83/3.96 *BasicFunctionTypename: "malloc" returnParam: *i8 noalias parameters: (i64) variableLength: false visibilityType: DEFAULT callingConvention: ccc 10.83/3.96 *BasicFunctionTypename: "abort" returnParam: BasicVoidType parameters: () variableLength: false visibilityType: DEFAULT callingConvention: ccc 10.83/3.96 *BasicFunctionTypename: "free" returnParam: BasicVoidType parameters: (*i8) variableLength: false visibilityType: DEFAULT callingConvention: ccc 10.83/3.96 *BasicFunctionTypename: "main" linkageType: EXTERNALLY_VISIBLE returnParam: i32 parameters: () variableLength: false visibilityType: DEFAULT callingConvention: ccc 10.83/3.96 0: 10.83/3.96 %1 = alloca i32, align 4 10.83/3.96 %data = alloca *BasicTypeName typeName: struct.TLItemBasicStructureType(elementType: *struct.TLItem, elementType: *struct.DItem), align 8 10.83/3.96 %item = alloca *BasicTypeName typeName: struct.DItemBasicStructureType(elementType: *struct.DItem, elementType: i32), align 8 10.83/3.96 %item2 = alloca *BasicTypeName typeName: struct.DItemBasicStructureType(elementType: *struct.DItem, elementType: i32), align 8 10.83/3.96 %lItem = alloca *BasicTypeName typeName: struct.TLItemBasicStructureType(elementType: *struct.TLItem, elementType: *struct.DItem), align 8 10.83/3.96 %c1 = alloca i32, align 4 10.83/3.96 %dst = alloca **BasicTypeName typeName: struct.DItemBasicStructureType(elementType: *struct.DItem, elementType: i32), align 8 10.83/3.96 store 0, %1 10.83/3.96 store null, %data 10.83/3.96 store 0, %c1 10.83/3.96 br %2 10.83/3.96 2: 10.83/3.96 %3 = load %c1 10.83/3.96 %4 = icmp slt %3 5 10.83/3.96 br %4, %5, %8 10.83/3.96 5: 10.83/3.96 %6 = call i32 @__VERIFIER_nondet_int() 10.83/3.96 %7 = icmp ne %6 0 10.83/3.96 br %8 10.83/3.96 8: 10.83/3.96 %9 = phi [0, %2], [%7, %5] 10.83/3.96 br %9, %10, %66 10.83/3.96 10: 10.83/3.96 %11 = load %c1 10.83/3.96 %12 = add %11 1 10.83/3.96 store %12, %c1 10.83/3.96 %13 = call noalias *i8 @malloc(i64 16) nounwind 10.83/3.96 %14 = bitcast *i8 %13 to *BasicTypeName typeName: struct.DItemBasicStructureType(elementType: *struct.DItem, elementType: i32) 10.83/3.96 store %14, %item 10.83/3.96 %15 = load %item 10.83/3.96 %16 = icmp ne %15 null 10.83/3.96 br %16, %18, %17 10.83/3.96 17: 10.83/3.96 Unnamed Call-Instruction = call BasicVoidType @abort() noreturn nounwind 10.83/3.96 unreachable 10.83/3.96 18: 10.83/3.96 %19 = load %item 10.83/3.96 %20 = getelementptr %19, 0, 0 10.83/3.96 store null, %20 10.83/3.96 %21 = load %c1 10.83/3.96 %22 = icmp slt %21 2 10.83/3.96 br %22, %23, %26 10.83/3.96 23: 10.83/3.96 %24 = load %item 10.83/3.96 %25 = getelementptr %24, 0, 1 10.83/3.96 store 2, %25 10.83/3.96 br %26 10.83/3.96 26: 10.83/3.96 %27 = load %c1 10.83/3.96 %28 = icmp slt %27 4 10.83/3.96 br %28, %29, %34 10.83/3.96 29: 10.83/3.96 %30 = load %c1 10.83/3.96 %31 = add %30 2 10.83/3.96 %32 = load %item 10.83/3.96 %33 = getelementptr %32, 0, 1 10.83/3.96 store %31, %33 10.83/3.96 br %34 10.83/3.96 34: 10.83/3.96 %35 = load %c1 10.83/3.96 %36 = icmp slt %35 6 10.83/3.96 br %36, %37, %43 10.83/3.96 37: 10.83/3.96 %38 = load %c1 10.83/3.96 %39 = mul 2 %38 10.83/3.96 %40 = add %39 4 10.83/3.96 %41 = load %item 10.83/3.96 %42 = getelementptr %41, 0, 1 10.83/3.96 store %40, %42 10.83/3.96 br %43 10.83/3.96 43: 10.83/3.96 %44 = call noalias *i8 @malloc(i64 16) nounwind 10.83/3.96 %45 = bitcast *i8 %44 to *BasicTypeName typeName: struct.TLItemBasicStructureType(elementType: *struct.TLItem, elementType: *struct.DItem) 10.83/3.96 store %45, %lItem 10.83/3.96 %46 = load %data 10.83/3.96 %47 = icmp ne %46 null 10.83/3.96 br %47, %48, %57 10.83/3.96 48: 10.83/3.96 %49 = load %data 10.83/3.96 %50 = getelementptr %49, 0, 0 10.83/3.96 %51 = load %50 10.83/3.96 %52 = load %lItem 10.83/3.96 %53 = getelementptr %52, 0, 0 10.83/3.96 store %51, %53 10.83/3.96 %54 = load %lItem 10.83/3.96 %55 = load %data 10.83/3.96 %56 = getelementptr %55, 0, 0 10.83/3.96 store %54, %56 10.83/3.96 br %62 10.83/3.96 57: 10.83/3.96 %58 = load %lItem 10.83/3.96 %59 = load %lItem 10.83/3.96 %60 = getelementptr %59, 0, 0 10.83/3.96 store %58, %60 10.83/3.96 %61 = load %lItem 10.83/3.96 store %61, %data 10.83/3.96 br %62 10.83/3.96 62: 10.83/3.96 %63 = load %item 10.83/3.96 %64 = load %lItem 10.83/3.96 %65 = getelementptr %64, 0, 1 10.83/3.96 store %63, %65 10.83/3.96 store null, %item 10.83/3.96 store null, %lItem 10.83/3.96 br %2 10.83/3.96 66: 10.83/3.96 %67 = load %data 10.83/3.96 %68 = icmp ne %67 null 10.83/3.96 br %68, %70, %69 10.83/3.96 69: 10.83/3.96 store 0, %1 10.83/3.96 br %175 10.83/3.96 70: 10.83/3.96 br %71 10.83/3.96 71: 10.83/3.96 %72 = load %data 10.83/3.96 %73 = getelementptr %72, 0, 0 10.83/3.96 %74 = load %73 10.83/3.96 %75 = load %data 10.83/3.96 %76 = icmp ne %74 %75 10.83/3.96 br %76, %77, %147 10.83/3.96 77: 10.83/3.96 %78 = load %data 10.83/3.96 %79 = getelementptr %78, 0, 1 10.83/3.96 %80 = load %79 10.83/3.96 store %80, %item 10.83/3.96 %81 = load %data 10.83/3.96 %82 = getelementptr %81, 0, 0 10.83/3.96 %83 = load %82 10.83/3.96 %84 = getelementptr %83, 0, 1 10.83/3.96 %85 = load %84 10.83/3.96 store %85, %item2 10.83/3.96 %86 = load %data 10.83/3.96 %87 = getelementptr %86, 0, 0 10.83/3.96 %88 = load %87 10.83/3.96 store %88, %lItem 10.83/3.96 %89 = load %lItem 10.83/3.96 %90 = getelementptr %89, 0, 0 10.83/3.96 %91 = load %90 10.83/3.96 %92 = load %data 10.83/3.96 %93 = getelementptr %92, 0, 0 10.83/3.96 store %91, %93 10.83/3.96 %94 = load %lItem 10.83/3.96 %95 = bitcast *BasicTypeName typeName: struct.TLItemBasicStructureType(elementType: *struct.TLItem, elementType: *struct.DItem) %94 to *i8 10.83/3.96 Unnamed Call-Instruction = call BasicVoidType @free(*i8 %95) nounwind 10.83/3.96 %96 = load %data 10.83/3.96 %97 = getelementptr %96, 0, 1 10.83/3.96 store %97, %dst 10.83/3.96 br %98 10.83/3.96 98: 10.83/3.96 %99 = load %item 10.83/3.96 %100 = icmp ne %99 null 10.83/3.96 br %100, %101, %104 10.83/3.96 101: 10.83/3.96 %102 = load %item2 10.83/3.96 %103 = icmp ne %102 null 10.83/3.96 br %104 10.83/3.96 104: 10.83/3.96 %105 = phi [0, %98], [%103, %101] 10.83/3.96 br %105, %106, %130 10.83/3.96 106: 10.83/3.96 %107 = load %item 10.83/3.96 %108 = getelementptr %107, 0, 1 10.83/3.96 %109 = load %108 10.83/3.96 %110 = load %item2 10.83/3.96 %111 = getelementptr %110, 0, 1 10.83/3.96 %112 = load %111 10.83/3.96 %113 = icmp sgt %109 %112 10.83/3.96 br %113, %114, %120 10.83/3.96 114: 10.83/3.96 %115 = load %item 10.83/3.96 %116 = load %dst 10.83/3.96 store %115, %116 10.83/3.96 %117 = load %item 10.83/3.96 %118 = getelementptr %117, 0, 0 10.83/3.96 %119 = load %118 10.83/3.96 store %119, %item 10.83/3.96 br %126 10.83/3.96 120: 10.83/3.96 %121 = load %item2 10.83/3.96 %122 = load %dst 10.83/3.96 store %121, %122 10.83/3.96 %123 = load %item2 10.83/3.96 %124 = getelementptr %123, 0, 0 10.83/3.96 %125 = load %124 10.83/3.96 store %125, %item2 10.83/3.96 br %126 10.83/3.96 126: 10.83/3.96 %127 = load %dst 10.83/3.96 %128 = load %127 10.83/3.96 %129 = getelementptr %128, 0, 0 10.83/3.96 store %129, %dst 10.83/3.96 br %98 10.83/3.96 130: 10.83/3.96 %131 = load %item 10.83/3.96 %132 = icmp ne %131 null 10.83/3.96 br %132, %133, %136 10.83/3.96 133: 10.83/3.96 %134 = load %item 10.83/3.96 %135 = load %dst 10.83/3.96 store %134, %135 10.83/3.96 store null, %item 10.83/3.96 br %143 10.83/3.96 136: 10.83/3.96 %137 = load %item2 10.83/3.96 %138 = icmp ne %137 null 10.83/3.96 br %138, %139, %142 10.83/3.96 139: 10.83/3.96 %140 = load %item2 10.83/3.96 %141 = load %dst 10.83/3.96 store %140, %141 10.83/3.96 store null, %item2 10.83/3.96 br %142 10.83/3.96 142: 10.83/3.96 br %143 10.83/3.96 143: 10.83/3.96 store null, %dst 10.83/3.96 %144 = load %data 10.83/3.96 %145 = getelementptr %144, 0, 0 10.83/3.96 %146 = load %145 10.83/3.96 store %146, %data 10.83/3.96 br %71 10.83/3.96 147: 10.83/3.96 %148 = load %data 10.83/3.96 %149 = getelementptr %148, 0, 1 10.83/3.96 %150 = load %149 10.83/3.96 store %150, %item 10.83/3.96 %151 = load %data 10.83/3.96 %152 = bitcast *BasicTypeName typeName: struct.TLItemBasicStructureType(elementType: *struct.TLItem, elementType: *struct.DItem) %151 to *i8 10.83/3.96 Unnamed Call-Instruction = call BasicVoidType @free(*i8 %152) nounwind 10.83/3.96 br %153 10.83/3.96 153: 10.83/3.96 %154 = load %item 10.83/3.96 %155 = icmp ne %154 null 10.83/3.96 br %155, %156, %174 10.83/3.96 156: 10.83/3.96 %157 = load %item 10.83/3.96 store %157, %item2 10.83/3.96 %158 = load %item 10.83/3.96 %159 = getelementptr %158, 0, 0 10.83/3.96 %160 = load %159 10.83/3.96 store %160, %item 10.83/3.96 %161 = load %item2 10.83/3.96 %162 = getelementptr %161, 0, 1 10.83/3.96 %163 = load %162 10.83/3.96 %164 = icmp sgt %163 1 10.83/3.96 br %164, %165, %173 10.83/3.96 165: 10.83/3.96 %166 = load %item2 10.83/3.96 %167 = getelementptr %166, 0, 1 10.83/3.96 %168 = load %167 10.83/3.96 %169 = icmp slt %168 15 10.83/3.96 br %169, %170, %173 10.83/3.96 170: 10.83/3.96 %171 = load %item2 10.83/3.96 %172 = bitcast *BasicTypeName typeName: struct.DItemBasicStructureType(elementType: *struct.DItem, elementType: i32) %171 to *i8 10.83/3.96 Unnamed Call-Instruction = call BasicVoidType @free(*i8 %172) nounwind 10.83/3.96 br %173 10.83/3.96 173: 10.83/3.96 br %153 10.83/3.96 174: 10.83/3.96 store 0, %1 10.83/3.96 br %175 10.83/3.96 175: 10.83/3.96 %176 = load %1 10.83/3.96 ret %176 10.83/3.96 10.83/3.96 10.83/3.96 Analyze Termination of all function calls matching the pattern: 10.83/3.96 main() 10.97/4.00 EOF