1package interp 2 3// This file implements the core interpretation routines, interpreting single 4// functions. 5 6import ( 7 "errors" 8 "strings" 9 10 "tinygo.org/x/go-llvm" 11) 12 13type frame struct { 14 *evalPackage 15 fn llvm.Value 16 locals map[llvm.Value]Value 17} 18 19// evalBasicBlock evaluates a single basic block, returning the return value (if 20// ending with a ret instruction), a list of outgoing basic blocks (if not 21// ending with a ret instruction), or an error on failure. 22// Most of it works at compile time. Some calls get translated into calls to be 23// executed at runtime: calls to functions with side effects, external calls, 24// and operations on the result of such instructions. 25func (fr *frame) evalBasicBlock(bb, incoming llvm.BasicBlock, indent string) (retval Value, outgoing []llvm.Value, err *Error) { 26 for inst := bb.FirstInstruction(); !inst.IsNil(); inst = llvm.NextInstruction(inst) { 27 if fr.Debug { 28 print(indent) 29 inst.Dump() 30 println() 31 } 32 switch { 33 case !inst.IsABinaryOperator().IsNil(): 34 lhs := fr.getLocal(inst.Operand(0)).(*LocalValue).Underlying 35 rhs := fr.getLocal(inst.Operand(1)).(*LocalValue).Underlying 36 37 switch inst.InstructionOpcode() { 38 // Standard binary operators 39 case llvm.Add: 40 fr.locals[inst] = &LocalValue{fr.Eval, fr.builder.CreateAdd(lhs, rhs, "")} 41 case llvm.FAdd: 42 fr.locals[inst] = &LocalValue{fr.Eval, fr.builder.CreateFAdd(lhs, rhs, "")} 43 case llvm.Sub: 44 fr.locals[inst] = &LocalValue{fr.Eval, fr.builder.CreateSub(lhs, rhs, "")} 45 case llvm.FSub: 46 fr.locals[inst] = &LocalValue{fr.Eval, fr.builder.CreateFSub(lhs, rhs, "")} 47 case llvm.Mul: 48 fr.locals[inst] = &LocalValue{fr.Eval, fr.builder.CreateMul(lhs, rhs, "")} 49 case llvm.FMul: 50 fr.locals[inst] = &LocalValue{fr.Eval, fr.builder.CreateFMul(lhs, rhs, "")} 51 case llvm.UDiv: 52 fr.locals[inst] = &LocalValue{fr.Eval, fr.builder.CreateUDiv(lhs, rhs, "")} 53 case llvm.SDiv: 54 fr.locals[inst] = &LocalValue{fr.Eval, fr.builder.CreateSDiv(lhs, rhs, "")} 55 case llvm.FDiv: 56 fr.locals[inst] = &LocalValue{fr.Eval, fr.builder.CreateFDiv(lhs, rhs, "")} 57 case llvm.URem: 58 fr.locals[inst] = &LocalValue{fr.Eval, fr.builder.CreateURem(lhs, rhs, "")} 59 case llvm.SRem: 60 fr.locals[inst] = &LocalValue{fr.Eval, fr.builder.CreateSRem(lhs, rhs, "")} 61 case llvm.FRem: 62 fr.locals[inst] = &LocalValue{fr.Eval, fr.builder.CreateFRem(lhs, rhs, "")} 63 64 // Logical operators 65 case llvm.Shl: 66 fr.locals[inst] = &LocalValue{fr.Eval, fr.builder.CreateShl(lhs, rhs, "")} 67 case llvm.LShr: 68 fr.locals[inst] = &LocalValue{fr.Eval, fr.builder.CreateLShr(lhs, rhs, "")} 69 case llvm.AShr: 70 fr.locals[inst] = &LocalValue{fr.Eval, fr.builder.CreateAShr(lhs, rhs, "")} 71 case llvm.And: 72 fr.locals[inst] = &LocalValue{fr.Eval, fr.builder.CreateAnd(lhs, rhs, "")} 73 case llvm.Or: 74 fr.locals[inst] = &LocalValue{fr.Eval, fr.builder.CreateOr(lhs, rhs, "")} 75 case llvm.Xor: 76 fr.locals[inst] = &LocalValue{fr.Eval, fr.builder.CreateXor(lhs, rhs, "")} 77 78 default: 79 return nil, nil, fr.unsupportedInstructionError(inst) 80 } 81 82 // Memory operators 83 case !inst.IsAAllocaInst().IsNil(): 84 allocType := inst.Type().ElementType() 85 alloca := llvm.AddGlobal(fr.Mod, allocType, fr.packagePath+"$alloca") 86 alloca.SetInitializer(llvm.ConstNull(allocType)) 87 alloca.SetLinkage(llvm.InternalLinkage) 88 fr.locals[inst] = &LocalValue{ 89 Underlying: alloca, 90 Eval: fr.Eval, 91 } 92 case !inst.IsALoadInst().IsNil(): 93 operand := fr.getLocal(inst.Operand(0)).(*LocalValue) 94 var value llvm.Value 95 if !operand.IsConstant() || inst.IsVolatile() || (!operand.Underlying.IsAConstantExpr().IsNil() && operand.Underlying.Opcode() == llvm.BitCast) { 96 value = fr.builder.CreateLoad(operand.Value(), inst.Name()) 97 } else { 98 value = operand.Load() 99 } 100 if value.Type() != inst.Type() { 101 return nil, nil, fr.errorAt(inst, errors.New("interp: load: type does not match")) 102 } 103 fr.locals[inst] = fr.getValue(value) 104 case !inst.IsAStoreInst().IsNil(): 105 value := fr.getLocal(inst.Operand(0)) 106 ptr := fr.getLocal(inst.Operand(1)) 107 if inst.IsVolatile() { 108 fr.builder.CreateStore(value.Value(), ptr.Value()) 109 } else { 110 ptr.Store(value.Value()) 111 } 112 case !inst.IsAGetElementPtrInst().IsNil(): 113 value := fr.getLocal(inst.Operand(0)) 114 llvmIndices := make([]llvm.Value, inst.OperandsCount()-1) 115 for i := range llvmIndices { 116 llvmIndices[i] = inst.Operand(i + 1) 117 } 118 indices := make([]uint32, len(llvmIndices)) 119 for i, llvmIndex := range llvmIndices { 120 operand := fr.getLocal(llvmIndex) 121 if !operand.IsConstant() { 122 // Not a constant operation. 123 // This should be detected by the scanner, but isn't at the 124 // moment. 125 return nil, nil, fr.errorAt(inst, errors.New("todo: non-const gep")) 126 } 127 indices[i] = uint32(operand.Value().ZExtValue()) 128 } 129 result, err := value.GetElementPtr(indices) 130 if err != nil { 131 return nil, nil, fr.errorAt(inst, err) 132 } 133 if result.Type() != inst.Type() { 134 return nil, nil, fr.errorAt(inst, errors.New("interp: gep: type does not match")) 135 } 136 fr.locals[inst] = result 137 138 // Cast operators 139 case !inst.IsATruncInst().IsNil(): 140 value := fr.getLocal(inst.Operand(0)) 141 fr.locals[inst] = &LocalValue{fr.Eval, fr.builder.CreateTrunc(value.(*LocalValue).Value(), inst.Type(), "")} 142 case !inst.IsAZExtInst().IsNil(): 143 value := fr.getLocal(inst.Operand(0)) 144 fr.locals[inst] = &LocalValue{fr.Eval, fr.builder.CreateZExt(value.(*LocalValue).Value(), inst.Type(), "")} 145 case !inst.IsASExtInst().IsNil(): 146 value := fr.getLocal(inst.Operand(0)) 147 fr.locals[inst] = &LocalValue{fr.Eval, fr.builder.CreateSExt(value.(*LocalValue).Value(), inst.Type(), "")} 148 case !inst.IsAFPToUIInst().IsNil(): 149 value := fr.getLocal(inst.Operand(0)) 150 fr.locals[inst] = &LocalValue{fr.Eval, fr.builder.CreateFPToUI(value.(*LocalValue).Value(), inst.Type(), "")} 151 case !inst.IsAFPToSIInst().IsNil(): 152 value := fr.getLocal(inst.Operand(0)) 153 fr.locals[inst] = &LocalValue{fr.Eval, fr.builder.CreateFPToSI(value.(*LocalValue).Value(), inst.Type(), "")} 154 case !inst.IsAUIToFPInst().IsNil(): 155 value := fr.getLocal(inst.Operand(0)) 156 fr.locals[inst] = &LocalValue{fr.Eval, fr.builder.CreateUIToFP(value.(*LocalValue).Value(), inst.Type(), "")} 157 case !inst.IsASIToFPInst().IsNil(): 158 value := fr.getLocal(inst.Operand(0)) 159 fr.locals[inst] = &LocalValue{fr.Eval, fr.builder.CreateSIToFP(value.(*LocalValue).Value(), inst.Type(), "")} 160 case !inst.IsAFPTruncInst().IsNil(): 161 value := fr.getLocal(inst.Operand(0)) 162 fr.locals[inst] = &LocalValue{fr.Eval, fr.builder.CreateFPTrunc(value.(*LocalValue).Value(), inst.Type(), "")} 163 case !inst.IsAFPExtInst().IsNil(): 164 value := fr.getLocal(inst.Operand(0)) 165 fr.locals[inst] = &LocalValue{fr.Eval, fr.builder.CreateFPExt(value.(*LocalValue).Value(), inst.Type(), "")} 166 case !inst.IsAPtrToIntInst().IsNil(): 167 value := fr.getLocal(inst.Operand(0)) 168 fr.locals[inst] = &LocalValue{fr.Eval, fr.builder.CreatePtrToInt(value.Value(), inst.Type(), "")} 169 case !inst.IsABitCastInst().IsNil() && inst.Type().TypeKind() == llvm.PointerTypeKind: 170 operand := inst.Operand(0) 171 if !operand.IsACallInst().IsNil() { 172 fn := operand.CalledValue() 173 if !fn.IsAFunction().IsNil() && fn.Name() == "runtime.alloc" { 174 continue // special case: bitcast of alloc 175 } 176 } 177 if _, ok := fr.getLocal(operand).(*MapValue); ok { 178 // Special case for runtime.trackPointer calls. 179 // Note: this might not be entirely sound in some rare cases 180 // where the map is stored in a dirty global. 181 uses := getUses(inst) 182 if len(uses) == 1 { 183 use := uses[0] 184 if !use.IsACallInst().IsNil() && !use.CalledValue().IsAFunction().IsNil() && use.CalledValue().Name() == "runtime.trackPointer" { 185 continue 186 } 187 } 188 // It is not possible in Go to bitcast a map value to a pointer. 189 return nil, nil, fr.errorAt(inst, errors.New("unimplemented: bitcast of map")) 190 } 191 value := fr.getLocal(operand).(*LocalValue) 192 fr.locals[inst] = &LocalValue{fr.Eval, fr.builder.CreateBitCast(value.Value(), inst.Type(), "")} 193 194 // Other operators 195 case !inst.IsAICmpInst().IsNil(): 196 lhs := fr.getLocal(inst.Operand(0)).(*LocalValue).Underlying 197 rhs := fr.getLocal(inst.Operand(1)).(*LocalValue).Underlying 198 predicate := inst.IntPredicate() 199 if predicate == llvm.IntEQ { 200 var lhsZero, rhsZero bool 201 var ok1, ok2 bool 202 if lhs.Type().TypeKind() == llvm.PointerTypeKind { 203 // Unfortunately, the const propagation in the IR builder 204 // doesn't handle pointer compares of inttoptr values. So we 205 // implement it manually here. 206 lhsZero, ok1 = isPointerNil(lhs) 207 rhsZero, ok2 = isPointerNil(rhs) 208 } 209 if lhs.Type().TypeKind() == llvm.IntegerTypeKind { 210 lhsZero, ok1 = isZero(lhs) 211 rhsZero, ok2 = isZero(rhs) 212 } 213 if ok1 && ok2 { 214 if lhsZero && rhsZero { 215 // Both are zero, so this icmp is always evaluated to true. 216 fr.locals[inst] = &LocalValue{fr.Eval, llvm.ConstInt(fr.Mod.Context().Int1Type(), 1, false)} 217 continue 218 } 219 if lhsZero != rhsZero { 220 // Only one of them is zero, so this comparison must return false. 221 fr.locals[inst] = &LocalValue{fr.Eval, llvm.ConstInt(fr.Mod.Context().Int1Type(), 0, false)} 222 continue 223 } 224 } 225 } 226 fr.locals[inst] = &LocalValue{fr.Eval, fr.builder.CreateICmp(predicate, lhs, rhs, "")} 227 case !inst.IsAFCmpInst().IsNil(): 228 lhs := fr.getLocal(inst.Operand(0)).(*LocalValue).Underlying 229 rhs := fr.getLocal(inst.Operand(1)).(*LocalValue).Underlying 230 predicate := inst.FloatPredicate() 231 fr.locals[inst] = &LocalValue{fr.Eval, fr.builder.CreateFCmp(predicate, lhs, rhs, "")} 232 case !inst.IsAPHINode().IsNil(): 233 for i := 0; i < inst.IncomingCount(); i++ { 234 if inst.IncomingBlock(i) == incoming { 235 fr.locals[inst] = fr.getLocal(inst.IncomingValue(i)) 236 } 237 } 238 case !inst.IsACallInst().IsNil(): 239 callee := inst.CalledValue() 240 switch { 241 case callee.Name() == "runtime.alloc": 242 // heap allocation 243 users := getUses(inst) 244 var resultInst = inst 245 if len(users) == 1 && !users[0].IsABitCastInst().IsNil() { 246 // happens when allocating something other than i8* 247 resultInst = users[0] 248 } 249 size := fr.getLocal(inst.Operand(0)).(*LocalValue).Underlying.ZExtValue() 250 allocType := resultInst.Type().ElementType() 251 typeSize := fr.TargetData.TypeAllocSize(allocType) 252 elementCount := 1 253 if size != typeSize { 254 // allocate an array 255 if size%typeSize != 0 { 256 return nil, nil, fr.unsupportedInstructionError(inst) 257 } 258 elementCount = int(size / typeSize) 259 allocType = llvm.ArrayType(allocType, elementCount) 260 } 261 alloc := llvm.AddGlobal(fr.Mod, allocType, fr.packagePath+"$alloc") 262 alloc.SetInitializer(llvm.ConstNull(allocType)) 263 alloc.SetLinkage(llvm.InternalLinkage) 264 result := &LocalValue{ 265 Underlying: alloc, 266 Eval: fr.Eval, 267 } 268 if elementCount == 1 { 269 fr.locals[resultInst] = result 270 } else { 271 result, err := result.GetElementPtr([]uint32{0, 0}) 272 if err != nil { 273 return nil, nil, fr.errorAt(inst, err) 274 } 275 fr.locals[resultInst] = result 276 } 277 case callee.Name() == "runtime.hashmapMake": 278 // create a map 279 keySize := inst.Operand(0).ZExtValue() 280 valueSize := inst.Operand(1).ZExtValue() 281 fr.locals[inst] = &MapValue{ 282 Eval: fr.Eval, 283 PkgName: fr.packagePath, 284 KeySize: int(keySize), 285 ValueSize: int(valueSize), 286 } 287 case callee.Name() == "runtime.hashmapStringSet": 288 // set a string key in the map 289 keyBuf := fr.getLocal(inst.Operand(1)).(*LocalValue) 290 keyLen := fr.getLocal(inst.Operand(2)).(*LocalValue) 291 valPtr := fr.getLocal(inst.Operand(3)).(*LocalValue) 292 m, ok := fr.getLocal(inst.Operand(0)).(*MapValue) 293 if !ok || !keyBuf.IsConstant() || !keyLen.IsConstant() || !valPtr.IsConstant() { 294 // The mapassign operation could not be done at compile 295 // time. Do it at runtime instead. 296 m := fr.getLocal(inst.Operand(0)).Value() 297 fr.markDirty(m) 298 llvmParams := []llvm.Value{ 299 m, // *runtime.hashmap 300 fr.getLocal(inst.Operand(1)).Value(), // key.ptr 301 fr.getLocal(inst.Operand(2)).Value(), // key.len 302 fr.getLocal(inst.Operand(3)).Value(), // value (unsafe.Pointer) 303 fr.getLocal(inst.Operand(4)).Value(), // context 304 fr.getLocal(inst.Operand(5)).Value(), // parentHandle 305 } 306 fr.builder.CreateCall(callee, llvmParams, "") 307 continue 308 } 309 // "key" is a Go string value, which in the TinyGo calling convention is split up 310 // into separate pointer and length parameters. 311 m.PutString(keyBuf, keyLen, valPtr) 312 case callee.Name() == "runtime.hashmapBinarySet": 313 // set a binary (int etc.) key in the map 314 keyBuf := fr.getLocal(inst.Operand(1)).(*LocalValue) 315 valPtr := fr.getLocal(inst.Operand(2)).(*LocalValue) 316 m, ok := fr.getLocal(inst.Operand(0)).(*MapValue) 317 if !ok || !keyBuf.IsConstant() || !valPtr.IsConstant() { 318 // The mapassign operation could not be done at compile 319 // time. Do it at runtime instead. 320 m := fr.getLocal(inst.Operand(0)).Value() 321 fr.markDirty(m) 322 llvmParams := []llvm.Value{ 323 m, // *runtime.hashmap 324 fr.getLocal(inst.Operand(1)).Value(), // key 325 fr.getLocal(inst.Operand(2)).Value(), // value 326 fr.getLocal(inst.Operand(3)).Value(), // context 327 fr.getLocal(inst.Operand(4)).Value(), // parentHandle 328 } 329 fr.builder.CreateCall(callee, llvmParams, "") 330 continue 331 } 332 m.PutBinary(keyBuf, valPtr) 333 case callee.Name() == "runtime.stringConcat": 334 // adding two strings together 335 buf1Ptr := fr.getLocal(inst.Operand(0)) 336 buf1Len := fr.getLocal(inst.Operand(1)) 337 buf2Ptr := fr.getLocal(inst.Operand(2)) 338 buf2Len := fr.getLocal(inst.Operand(3)) 339 buf1 := getStringBytes(buf1Ptr, buf1Len.Value()) 340 buf2 := getStringBytes(buf2Ptr, buf2Len.Value()) 341 result := []byte(string(buf1) + string(buf2)) 342 vals := make([]llvm.Value, len(result)) 343 for i := range vals { 344 vals[i] = llvm.ConstInt(fr.Mod.Context().Int8Type(), uint64(result[i]), false) 345 } 346 globalType := llvm.ArrayType(fr.Mod.Context().Int8Type(), len(result)) 347 globalValue := llvm.ConstArray(fr.Mod.Context().Int8Type(), vals) 348 global := llvm.AddGlobal(fr.Mod, globalType, fr.packagePath+"$stringconcat") 349 global.SetInitializer(globalValue) 350 global.SetLinkage(llvm.InternalLinkage) 351 global.SetGlobalConstant(true) 352 global.SetUnnamedAddr(true) 353 stringType := fr.Mod.GetTypeByName("runtime._string") 354 retPtr := llvm.ConstGEP(global, getLLVMIndices(fr.Mod.Context().Int32Type(), []uint32{0, 0})) 355 retLen := llvm.ConstInt(stringType.StructElementTypes()[1], uint64(len(result)), false) 356 ret := llvm.ConstNull(stringType) 357 ret = llvm.ConstInsertValue(ret, retPtr, []uint32{0}) 358 ret = llvm.ConstInsertValue(ret, retLen, []uint32{1}) 359 fr.locals[inst] = &LocalValue{fr.Eval, ret} 360 case callee.Name() == "runtime.sliceCopy": 361 elementSize := fr.getLocal(inst.Operand(4)).(*LocalValue).Value().ZExtValue() 362 dstArray := fr.getLocal(inst.Operand(0)).(*LocalValue).stripPointerCasts() 363 srcArray := fr.getLocal(inst.Operand(1)).(*LocalValue).stripPointerCasts() 364 dstLen := fr.getLocal(inst.Operand(2)).(*LocalValue) 365 srcLen := fr.getLocal(inst.Operand(3)).(*LocalValue) 366 if elementSize != 1 && dstArray.Type().ElementType().TypeKind() == llvm.ArrayTypeKind && srcArray.Type().ElementType().TypeKind() == llvm.ArrayTypeKind { 367 // Slice data pointers are created by adding a global array 368 // and getting the address of the first element using a GEP. 369 // However, before the compiler can pass it to 370 // runtime.sliceCopy, it has to perform a bitcast to a *i8, 371 // to make it a unsafe.Pointer. Now, when the IR builder 372 // sees a bitcast of a GEP with zero indices, it will make 373 // a bitcast of the original array instead of the GEP, 374 // which breaks our assumptions. 375 // Re-add this GEP, in the hope that it it is then of the correct type... 376 dstArrayValue, err := dstArray.GetElementPtr([]uint32{0, 0}) 377 if err != nil { 378 return nil, nil, fr.errorAt(inst, err) 379 } 380 dstArray = dstArrayValue.(*LocalValue) 381 srcArrayValue, err := srcArray.GetElementPtr([]uint32{0, 0}) 382 if err != nil { 383 return nil, nil, fr.errorAt(inst, err) 384 } 385 srcArray = srcArrayValue.(*LocalValue) 386 } 387 if fr.Eval.TargetData.TypeAllocSize(dstArray.Type().ElementType()) != elementSize { 388 return nil, nil, fr.errorAt(inst, errors.New("interp: slice dst element size does not match pointer type")) 389 } 390 if fr.Eval.TargetData.TypeAllocSize(srcArray.Type().ElementType()) != elementSize { 391 return nil, nil, fr.errorAt(inst, errors.New("interp: slice src element size does not match pointer type")) 392 } 393 if dstArray.Type() != srcArray.Type() { 394 return nil, nil, fr.errorAt(inst, errors.New("interp: slice element types don't match")) 395 } 396 length := dstLen.Value().SExtValue() 397 if srcLength := srcLen.Value().SExtValue(); srcLength < length { 398 length = srcLength 399 } 400 if length < 0 { 401 return nil, nil, fr.errorAt(inst, errors.New("interp: trying to copy a slice with negative length?")) 402 } 403 for i := int64(0); i < length; i++ { 404 var err error 405 // *dst = *src 406 dstArray.Store(srcArray.Load()) 407 // dst++ 408 dstArrayValue, err := dstArray.GetElementPtr([]uint32{1}) 409 if err != nil { 410 return nil, nil, fr.errorAt(inst, err) 411 } 412 dstArray = dstArrayValue.(*LocalValue) 413 // src++ 414 srcArrayValue, err := srcArray.GetElementPtr([]uint32{1}) 415 if err != nil { 416 return nil, nil, fr.errorAt(inst, err) 417 } 418 srcArray = srcArrayValue.(*LocalValue) 419 } 420 case callee.Name() == "runtime.stringToBytes": 421 // convert a string to a []byte 422 bufPtr := fr.getLocal(inst.Operand(0)) 423 bufLen := fr.getLocal(inst.Operand(1)) 424 result := getStringBytes(bufPtr, bufLen.Value()) 425 vals := make([]llvm.Value, len(result)) 426 for i := range vals { 427 vals[i] = llvm.ConstInt(fr.Mod.Context().Int8Type(), uint64(result[i]), false) 428 } 429 globalType := llvm.ArrayType(fr.Mod.Context().Int8Type(), len(result)) 430 globalValue := llvm.ConstArray(fr.Mod.Context().Int8Type(), vals) 431 global := llvm.AddGlobal(fr.Mod, globalType, fr.packagePath+"$bytes") 432 global.SetInitializer(globalValue) 433 global.SetLinkage(llvm.InternalLinkage) 434 global.SetGlobalConstant(true) 435 global.SetUnnamedAddr(true) 436 sliceType := inst.Type() 437 retPtr := llvm.ConstGEP(global, getLLVMIndices(fr.Mod.Context().Int32Type(), []uint32{0, 0})) 438 retLen := llvm.ConstInt(sliceType.StructElementTypes()[1], uint64(len(result)), false) 439 ret := llvm.ConstNull(sliceType) 440 ret = llvm.ConstInsertValue(ret, retPtr, []uint32{0}) // ptr 441 ret = llvm.ConstInsertValue(ret, retLen, []uint32{1}) // len 442 ret = llvm.ConstInsertValue(ret, retLen, []uint32{2}) // cap 443 fr.locals[inst] = &LocalValue{fr.Eval, ret} 444 case callee.Name() == "runtime.typeAssert": 445 actualTypeInt := fr.getLocal(inst.Operand(0)).(*LocalValue).Underlying 446 assertedType := fr.getLocal(inst.Operand(1)).(*LocalValue).Underlying 447 if actualTypeInt.IsAConstantExpr().IsNil() || actualTypeInt.Opcode() != llvm.PtrToInt { 448 return nil, nil, fr.errorAt(inst, errors.New("interp: expected typecode in runtime.typeAssert to be a ptrtoint")) 449 } 450 actualType := actualTypeInt.Operand(0) 451 if actualType.IsAConstant().IsNil() || assertedType.IsAConstant().IsNil() { 452 return nil, nil, fr.errorAt(inst, errors.New("interp: unimplemented: type assert with non-constant interface value")) 453 } 454 assertOk := uint64(0) 455 if llvm.ConstExtractValue(actualType.Initializer(), []uint32{0}) == assertedType { 456 assertOk = 1 457 } 458 fr.locals[inst] = &LocalValue{fr.Eval, llvm.ConstInt(fr.Mod.Context().Int1Type(), assertOk, false)} 459 case callee.Name() == "runtime.interfaceImplements": 460 typecode := fr.getLocal(inst.Operand(0)).(*LocalValue).Underlying 461 interfaceMethodSet := fr.getLocal(inst.Operand(1)).(*LocalValue).Underlying 462 if typecode.IsAConstantExpr().IsNil() || typecode.Opcode() != llvm.PtrToInt { 463 return nil, nil, fr.errorAt(inst, errors.New("interp: expected typecode to be a ptrtoint")) 464 } 465 typecode = typecode.Operand(0) 466 if interfaceMethodSet.IsAConstantExpr().IsNil() || interfaceMethodSet.Opcode() != llvm.GetElementPtr { 467 return nil, nil, fr.errorAt(inst, errors.New("interp: expected method set in runtime.interfaceImplements to be a constant gep")) 468 } 469 interfaceMethodSet = interfaceMethodSet.Operand(0).Initializer() 470 methodSet := llvm.ConstExtractValue(typecode.Initializer(), []uint32{1}) 471 if methodSet.IsAConstantExpr().IsNil() || methodSet.Opcode() != llvm.GetElementPtr { 472 return nil, nil, fr.errorAt(inst, errors.New("interp: expected method set to be a constant gep")) 473 } 474 methodSet = methodSet.Operand(0).Initializer() 475 476 // Make a set of all the methods on the concrete type, for 477 // easier checking in the next step. 478 definedMethods := map[string]struct{}{} 479 for i := 0; i < methodSet.Type().ArrayLength(); i++ { 480 methodInfo := llvm.ConstExtractValue(methodSet, []uint32{uint32(i)}) 481 name := llvm.ConstExtractValue(methodInfo, []uint32{0}).Name() 482 definedMethods[name] = struct{}{} 483 } 484 // Check whether all interface methods are also in the list 485 // of defined methods calculated above. 486 implements := uint64(1) // i1 true 487 for i := 0; i < interfaceMethodSet.Type().ArrayLength(); i++ { 488 name := llvm.ConstExtractValue(interfaceMethodSet, []uint32{uint32(i)}).Name() 489 if _, ok := definedMethods[name]; !ok { 490 // There is a method on the interface that is not 491 // implemented by the type. 492 implements = 0 // i1 false 493 break 494 } 495 } 496 fr.locals[inst] = &LocalValue{fr.Eval, llvm.ConstInt(fr.Mod.Context().Int1Type(), implements, false)} 497 case callee.Name() == "runtime.nanotime": 498 fr.locals[inst] = &LocalValue{fr.Eval, llvm.ConstInt(fr.Mod.Context().Int64Type(), 0, false)} 499 case callee.Name() == "llvm.dbg.value": 500 // do nothing 501 case strings.HasPrefix(callee.Name(), "llvm.lifetime."): 502 // do nothing 503 case callee.Name() == "runtime.trackPointer": 504 // do nothing 505 case strings.HasPrefix(callee.Name(), "runtime.print") || callee.Name() == "runtime._panic": 506 // This are all print instructions, which necessarily have side 507 // effects but no results. 508 // TODO: print an error when executing runtime._panic (with the 509 // exact error message it would print at runtime). 510 var params []llvm.Value 511 for i := 0; i < inst.OperandsCount()-1; i++ { 512 operand := fr.getLocal(inst.Operand(i)).Value() 513 fr.markDirty(operand) 514 params = append(params, operand) 515 } 516 // TODO: accurate debug info, including call chain 517 fr.builder.CreateCall(callee, params, inst.Name()) 518 case !callee.IsAFunction().IsNil() && callee.IsDeclaration(): 519 // external functions 520 var params []llvm.Value 521 for i := 0; i < inst.OperandsCount()-1; i++ { 522 operand := fr.getLocal(inst.Operand(i)).Value() 523 fr.markDirty(operand) 524 params = append(params, operand) 525 } 526 // TODO: accurate debug info, including call chain 527 result := fr.builder.CreateCall(callee, params, inst.Name()) 528 if inst.Type().TypeKind() != llvm.VoidTypeKind { 529 fr.markDirty(result) 530 fr.locals[inst] = &LocalValue{fr.Eval, result} 531 } 532 case !callee.IsAFunction().IsNil(): 533 // regular function 534 var params []Value 535 dirtyParams := false 536 for i := 0; i < inst.OperandsCount()-1; i++ { 537 local := fr.getLocal(inst.Operand(i)) 538 if !local.IsConstant() { 539 dirtyParams = true 540 } 541 params = append(params, local) 542 } 543 var ret Value 544 scanResult, err := fr.hasSideEffects(callee) 545 if err != nil { 546 return nil, nil, err 547 } 548 if scanResult.severity == sideEffectLimited || dirtyParams && scanResult.severity != sideEffectAll { 549 // Side effect is bounded. This means the operation invokes 550 // side effects (like calling an external function) but it 551 // is known at compile time which side effects it invokes. 552 // This means the function can be called at runtime and the 553 // affected globals can be marked dirty at compile time. 554 llvmParams := make([]llvm.Value, len(params)) 555 for i, param := range params { 556 llvmParams[i] = param.Value() 557 } 558 result := fr.builder.CreateCall(callee, llvmParams, inst.Name()) 559 ret = &LocalValue{fr.Eval, result} 560 // mark all mentioned globals as dirty 561 for global := range scanResult.mentionsGlobals { 562 fr.markDirty(global) 563 } 564 } else { 565 // Side effect is one of: 566 // * None: no side effects, can be fully interpreted at 567 // compile time. 568 // * Unbounded: cannot call at runtime so we'll try to 569 // interpret anyway and hope for the best. 570 ret, err = fr.function(callee, params, indent+" ") 571 if err != nil { 572 // Record this function call in the backtrace. 573 err.Traceback = append(err.Traceback, ErrorLine{ 574 Pos: getPosition(inst), 575 Inst: inst, 576 }) 577 return nil, nil, err 578 } 579 } 580 if inst.Type().TypeKind() != llvm.VoidTypeKind { 581 fr.locals[inst] = ret 582 } 583 default: 584 // function pointers, etc. 585 return nil, nil, fr.unsupportedInstructionError(inst) 586 } 587 case !inst.IsAExtractValueInst().IsNil(): 588 agg := fr.getLocal(inst.Operand(0)).(*LocalValue) // must be constant 589 indices := inst.Indices() 590 if agg.Underlying.IsConstant() { 591 newValue := llvm.ConstExtractValue(agg.Underlying, indices) 592 fr.locals[inst] = fr.getValue(newValue) 593 } else { 594 if len(indices) != 1 { 595 return nil, nil, fr.errorAt(inst, errors.New("interp: cannot handle extractvalue with not exactly 1 index")) 596 } 597 fr.locals[inst] = &LocalValue{fr.Eval, fr.builder.CreateExtractValue(agg.Underlying, int(indices[0]), inst.Name())} 598 } 599 case !inst.IsAInsertValueInst().IsNil(): 600 agg := fr.getLocal(inst.Operand(0)).(*LocalValue) // must be constant 601 val := fr.getLocal(inst.Operand(1)) 602 indices := inst.Indices() 603 if agg.IsConstant() && val.IsConstant() { 604 newValue := llvm.ConstInsertValue(agg.Underlying, val.Value(), indices) 605 fr.locals[inst] = &LocalValue{fr.Eval, newValue} 606 } else { 607 if len(indices) != 1 { 608 return nil, nil, fr.errorAt(inst, errors.New("interp: cannot handle insertvalue with not exactly 1 index")) 609 } 610 fr.locals[inst] = &LocalValue{fr.Eval, fr.builder.CreateInsertValue(agg.Underlying, val.Value(), int(indices[0]), inst.Name())} 611 } 612 case !inst.IsASelectInst().IsNil(): 613 // var result T 614 // if cond { 615 // result = x 616 // } else { 617 // result = y 618 // } 619 // return result 620 cond := fr.getLocal(inst.Operand(0)).(*LocalValue).Underlying 621 x := fr.getLocal(inst.Operand(1)).(*LocalValue).Underlying 622 y := fr.getLocal(inst.Operand(2)).(*LocalValue).Underlying 623 fr.locals[inst] = &LocalValue{fr.Eval, fr.builder.CreateSelect(cond, x, y, "")} 624 625 case !inst.IsAReturnInst().IsNil() && inst.OperandsCount() == 0: 626 return nil, nil, nil // ret void 627 case !inst.IsAReturnInst().IsNil() && inst.OperandsCount() == 1: 628 return fr.getLocal(inst.Operand(0)), nil, nil 629 case !inst.IsABranchInst().IsNil() && inst.OperandsCount() == 3: 630 // conditional branch (if/then/else) 631 cond := fr.getLocal(inst.Operand(0)).Value() 632 if cond.Type() != fr.Mod.Context().Int1Type() { 633 return nil, nil, fr.errorAt(inst, errors.New("expected an i1 in a branch instruction")) 634 } 635 thenBB := inst.Operand(1) 636 elseBB := inst.Operand(2) 637 if !cond.IsAInstruction().IsNil() { 638 return nil, nil, fr.errorAt(inst, errors.New("interp: branch on a non-constant")) 639 } 640 if !cond.IsAConstantExpr().IsNil() { 641 // This may happen when the instruction builder could not 642 // const-fold some instructions. 643 return nil, nil, fr.errorAt(inst, errors.New("interp: branch on a non-const-propagated constant expression")) 644 } 645 switch cond { 646 case llvm.ConstInt(fr.Mod.Context().Int1Type(), 0, false): // false 647 return nil, []llvm.Value{thenBB}, nil // then 648 case llvm.ConstInt(fr.Mod.Context().Int1Type(), 1, false): // true 649 return nil, []llvm.Value{elseBB}, nil // else 650 default: 651 return nil, nil, fr.errorAt(inst, errors.New("branch was not true or false")) 652 } 653 case !inst.IsABranchInst().IsNil() && inst.OperandsCount() == 1: 654 // unconditional branch (goto) 655 return nil, []llvm.Value{inst.Operand(0)}, nil 656 case !inst.IsAUnreachableInst().IsNil(): 657 // Unreachable was reached (e.g. after a call to panic()). 658 // Report this as an error, as it is not supposed to happen. 659 // This is a sentinel error value. 660 return nil, nil, errUnreachable 661 662 default: 663 return nil, nil, fr.unsupportedInstructionError(inst) 664 } 665 } 666 667 panic("interp: reached end of basic block without terminator") 668} 669 670// Get the Value for an operand, which is a constant value of some sort. 671func (fr *frame) getLocal(v llvm.Value) Value { 672 if ret, ok := fr.locals[v]; ok { 673 return ret 674 } else if value := fr.getValue(v); value != nil { 675 return value 676 } else { 677 // This should not happen under normal circumstances. 678 panic("cannot find value") 679 } 680} 681