1 //===-- IRInterpreter.cpp ---------------------------------------*- C++ -*-===//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 
10 #include "lldb/Core/DataExtractor.h"
11 #include "lldb/Core/Error.h"
12 #include "lldb/Core/Log.h"
13 #include "lldb/Core/Scalar.h"
14 #include "lldb/Core/StreamString.h"
15 #include "lldb/Expression/IRMemoryMap.h"
16 #include "lldb/Expression/IRInterpreter.h"
17 #include "lldb/Host/Endian.h"
18 
19 #include "llvm/IR/Constants.h"
20 #include "llvm/IR/DataLayout.h"
21 #include "llvm/IR/Function.h"
22 #include "llvm/IR/Instructions.h"
23 #include "llvm/IR/Module.h"
24 #include "llvm/Support/raw_ostream.h"
25 
26 #include <map>
27 
28 using namespace llvm;
29 
30 static std::string
31 PrintValue(const Value *value, bool truncate = false)
32 {
33     std::string s;
34     raw_string_ostream rso(s);
35     value->print(rso);
36     rso.flush();
37     if (truncate)
38         s.resize(s.length() - 1);
39 
40     size_t offset;
41     while ((offset = s.find('\n')) != s.npos)
42         s.erase(offset, 1);
43     while (s[0] == ' ' || s[0] == '\t')
44         s.erase(0, 1);
45 
46     return s;
47 }
48 
49 static std::string
50 PrintType(const Type *type, bool truncate = false)
51 {
52     std::string s;
53     raw_string_ostream rso(s);
54     type->print(rso);
55     rso.flush();
56     if (truncate)
57         s.resize(s.length() - 1);
58     return s;
59 }
60 
61 class InterpreterStackFrame
62 {
63 public:
64     typedef std::map <const Value*, lldb::addr_t> ValueMap;
65 
66     ValueMap                                m_values;
67     DataLayout                             &m_target_data;
68     lldb_private::IRMemoryMap              &m_memory_map;
69     const BasicBlock                       *m_bb;
70     BasicBlock::const_iterator              m_ii;
71     BasicBlock::const_iterator              m_ie;
72 
73     lldb::addr_t                            m_frame_process_address;
74     size_t                                  m_frame_size;
75     lldb::addr_t                            m_stack_pointer;
76 
77     lldb::ByteOrder                         m_byte_order;
78     size_t                                  m_addr_byte_size;
79 
80     InterpreterStackFrame (DataLayout &target_data,
81                            lldb_private::IRMemoryMap &memory_map,
82                            lldb::addr_t stack_frame_bottom,
83                            lldb::addr_t stack_frame_top) :
84         m_target_data (target_data),
85         m_memory_map (memory_map)
86     {
87         m_byte_order = (target_data.isLittleEndian() ? lldb::eByteOrderLittle : lldb::eByteOrderBig);
88         m_addr_byte_size = (target_data.getPointerSize(0));
89 
90         m_frame_process_address = stack_frame_bottom;
91         m_frame_size = stack_frame_top - stack_frame_bottom;
92         m_stack_pointer = stack_frame_top;
93     }
94 
95     ~InterpreterStackFrame ()
96     {
97     }
98 
99     void Jump (const BasicBlock *bb)
100     {
101         m_bb = bb;
102         m_ii = m_bb->begin();
103         m_ie = m_bb->end();
104     }
105 
106     std::string SummarizeValue (const Value *value)
107     {
108         lldb_private::StreamString ss;
109 
110         ss.Printf("%s", PrintValue(value).c_str());
111 
112         ValueMap::iterator i = m_values.find(value);
113 
114         if (i != m_values.end())
115         {
116             lldb::addr_t addr = i->second;
117 
118             ss.Printf(" 0x%llx", (unsigned long long)addr);
119         }
120 
121         return ss.GetString();
122     }
123 
124     bool AssignToMatchType (lldb_private::Scalar &scalar, uint64_t u64value, Type *type)
125     {
126         size_t type_size = m_target_data.getTypeStoreSize(type);
127 
128         switch (type_size)
129         {
130         case 1:
131             scalar = (uint8_t)u64value;
132             break;
133         case 2:
134             scalar = (uint16_t)u64value;
135             break;
136         case 4:
137             scalar = (uint32_t)u64value;
138             break;
139         case 8:
140             scalar = (uint64_t)u64value;
141             break;
142         default:
143             return false;
144         }
145 
146         return true;
147     }
148 
149     bool EvaluateValue (lldb_private::Scalar &scalar, const Value *value, Module &module)
150     {
151         const Constant *constant = dyn_cast<Constant>(value);
152 
153         if (constant)
154         {
155             APInt value_apint;
156 
157             if (!ResolveConstantValue(value_apint, constant))
158                 return false;
159 
160             return AssignToMatchType(scalar, value_apint.getLimitedValue(), value->getType());
161         }
162         else
163         {
164             lldb::addr_t process_address = ResolveValue(value, module);
165             size_t value_size = m_target_data.getTypeStoreSize(value->getType());
166 
167             lldb_private::DataExtractor value_extractor;
168             lldb_private::Error extract_error;
169 
170             m_memory_map.GetMemoryData(value_extractor, process_address, value_size, extract_error);
171 
172             if (!extract_error.Success())
173                 return false;
174 
175             lldb::offset_t offset = 0;
176             if (value_size == 1 || value_size == 2 || value_size == 4 || value_size == 8)
177             {
178                 uint64_t u64value = value_extractor.GetMaxU64(&offset, value_size);
179                 return AssignToMatchType(scalar, u64value, value->getType());
180             }
181         }
182 
183         return false;
184     }
185 
186     bool AssignValue (const Value *value, lldb_private::Scalar &scalar, Module &module)
187     {
188         lldb::addr_t process_address = ResolveValue (value, module);
189 
190         if (process_address == LLDB_INVALID_ADDRESS)
191             return false;
192 
193         lldb_private::Scalar cast_scalar;
194 
195         if (!AssignToMatchType(cast_scalar, scalar.GetRawBits64(0), value->getType()))
196             return false;
197 
198         size_t value_byte_size = m_target_data.getTypeStoreSize(value->getType());
199 
200         lldb_private::DataBufferHeap buf(value_byte_size, 0);
201 
202         lldb_private::Error get_data_error;
203 
204         if (!cast_scalar.GetAsMemoryData(buf.GetBytes(), buf.GetByteSize(), m_byte_order, get_data_error))
205             return false;
206 
207         lldb_private::Error write_error;
208 
209         m_memory_map.WriteMemory(process_address, buf.GetBytes(), buf.GetByteSize(), write_error);
210 
211         return write_error.Success();
212     }
213 
214     bool ResolveConstantValue (APInt &value, const Constant *constant)
215     {
216         switch (constant->getValueID())
217         {
218         default:
219             break;
220         case Value::ConstantIntVal:
221             if (const ConstantInt *constant_int = dyn_cast<ConstantInt>(constant))
222             {
223                 value = constant_int->getValue();
224                 return true;
225             }
226             break;
227         case Value::ConstantFPVal:
228             if (const ConstantFP *constant_fp = dyn_cast<ConstantFP>(constant))
229             {
230                 value = constant_fp->getValueAPF().bitcastToAPInt();
231                 return true;
232             }
233             break;
234         case Value::ConstantExprVal:
235             if (const ConstantExpr *constant_expr = dyn_cast<ConstantExpr>(constant))
236             {
237                 switch (constant_expr->getOpcode())
238                 {
239                     default:
240                         return false;
241                     case Instruction::IntToPtr:
242                     case Instruction::PtrToInt:
243                     case Instruction::BitCast:
244                         return ResolveConstantValue(value, constant_expr->getOperand(0));
245                     case Instruction::GetElementPtr:
246                     {
247                         ConstantExpr::const_op_iterator op_cursor = constant_expr->op_begin();
248                         ConstantExpr::const_op_iterator op_end = constant_expr->op_end();
249 
250                         Constant *base = dyn_cast<Constant>(*op_cursor);
251 
252                         if (!base)
253                             return false;
254 
255                         if (!ResolveConstantValue(value, base))
256                             return false;
257 
258                         op_cursor++;
259 
260                         if (op_cursor == op_end)
261                             return true; // no offset to apply!
262 
263                         SmallVector <Value *, 8> indices (op_cursor, op_end);
264 
265                         uint64_t offset = m_target_data.getIndexedOffset(base->getType(), indices);
266 
267                         const bool is_signed = true;
268                         value += APInt(value.getBitWidth(), offset, is_signed);
269 
270                         return true;
271                     }
272                 }
273             }
274             break;
275         case Value::ConstantPointerNullVal:
276             if (isa<ConstantPointerNull>(constant))
277             {
278                 value = APInt(m_target_data.getPointerSizeInBits(), 0);
279                 return true;
280             }
281             break;
282         }
283         return false;
284     }
285 
286     bool MakeArgument(const Argument *value, uint64_t address)
287     {
288         lldb::addr_t data_address = Malloc(value->getType());
289 
290         if (data_address == LLDB_INVALID_ADDRESS)
291             return false;
292 
293         lldb_private::Error write_error;
294 
295         m_memory_map.WritePointerToMemory(data_address, address, write_error);
296 
297         if (!write_error.Success())
298         {
299             lldb_private::Error free_error;
300             m_memory_map.Free(data_address, free_error);
301             return false;
302         }
303 
304         m_values[value] = data_address;
305 
306         lldb_private::Log *log(lldb_private::GetLogIfAllCategoriesSet (LIBLLDB_LOG_EXPRESSIONS));
307 
308         if (log)
309         {
310             log->Printf("Made an allocation for argument %s", PrintValue(value).c_str());
311             log->Printf("  Data region    : %llx", (unsigned long long)address);
312             log->Printf("  Ref region     : %llx", (unsigned long long)data_address);
313         }
314 
315         return true;
316     }
317 
318     bool ResolveConstant (lldb::addr_t process_address, const Constant *constant)
319     {
320         APInt resolved_value;
321 
322         if (!ResolveConstantValue(resolved_value, constant))
323             return false;
324 
325         lldb_private::StreamString buffer (lldb_private::Stream::eBinary,
326                                            m_memory_map.GetAddressByteSize(),
327                                            m_memory_map.GetByteOrder());
328 
329         size_t constant_size = m_target_data.getTypeStoreSize(constant->getType());
330 
331         const uint64_t *raw_data = resolved_value.getRawData();
332 
333         buffer.PutRawBytes(raw_data, constant_size, lldb::endian::InlHostByteOrder());
334 
335         lldb_private::Error write_error;
336 
337         m_memory_map.WriteMemory(process_address, (const uint8_t*)buffer.GetData(), constant_size, write_error);
338 
339         return write_error.Success();
340     }
341 
342     lldb::addr_t Malloc (size_t size, uint8_t byte_alignment)
343     {
344         lldb::addr_t ret = m_stack_pointer;
345 
346         ret -= size;
347         ret -= (ret % byte_alignment);
348 
349         if (ret < m_frame_process_address)
350             return LLDB_INVALID_ADDRESS;
351 
352         m_stack_pointer = ret;
353         return ret;
354     }
355 
356     lldb::addr_t MallocPointer ()
357     {
358         return Malloc(m_target_data.getPointerSize(), m_target_data.getPointerPrefAlignment());
359     }
360 
361     lldb::addr_t Malloc (llvm::Type *type)
362     {
363         lldb_private::Error alloc_error;
364 
365         return Malloc(m_target_data.getTypeAllocSize(type), m_target_data.getPrefTypeAlignment(type));
366     }
367 
368     std::string PrintData (lldb::addr_t addr, llvm::Type *type)
369     {
370         size_t length = m_target_data.getTypeStoreSize(type);
371 
372         lldb_private::DataBufferHeap buf(length, 0);
373 
374         lldb_private::Error read_error;
375 
376         m_memory_map.ReadMemory(buf.GetBytes(), addr, length, read_error);
377 
378         if (!read_error.Success())
379             return std::string("<couldn't read data>");
380 
381         lldb_private::StreamString ss;
382 
383         for (size_t i = 0; i < length; i++)
384         {
385             if ((!(i & 0xf)) && i)
386                 ss.Printf("%02hhx - ", buf.GetBytes()[i]);
387             else
388                 ss.Printf("%02hhx ", buf.GetBytes()[i]);
389         }
390 
391         return ss.GetString();
392     }
393 
394     lldb::addr_t ResolveValue (const Value *value, Module &module)
395     {
396         ValueMap::iterator i = m_values.find(value);
397 
398         if (i != m_values.end())
399             return i->second;
400 
401         // Fall back and allocate space [allocation type Alloca]
402 
403         lldb::addr_t data_address = Malloc(value->getType());
404 
405         if (const Constant *constant = dyn_cast<Constant>(value))
406         {
407             if (!ResolveConstant (data_address, constant))
408             {
409                 lldb_private::Error free_error;
410                 m_memory_map.Free(data_address, free_error);
411                 return LLDB_INVALID_ADDRESS;
412             }
413         }
414 
415         m_values[value] = data_address;
416         return data_address;
417     }
418 };
419 
420 static const char *unsupported_opcode_error         = "Interpreter doesn't handle one of the expression's opcodes";
421 static const char *unsupported_operand_error        = "Interpreter doesn't handle one of the expression's operands";
422 //static const char *interpreter_initialization_error = "Interpreter couldn't be initialized";
423 static const char *interpreter_internal_error       = "Interpreter encountered an internal error";
424 static const char *bad_value_error                  = "Interpreter couldn't resolve a value during execution";
425 static const char *memory_allocation_error          = "Interpreter couldn't allocate memory";
426 static const char *memory_write_error               = "Interpreter couldn't write to memory";
427 static const char *memory_read_error                = "Interpreter couldn't read from memory";
428 static const char *infinite_loop_error              = "Interpreter ran for too many cycles";
429 //static const char *bad_result_error                 = "Result of expression is in bad memory";
430 
431 bool
432 IRInterpreter::CanInterpret (llvm::Module &module,
433                              llvm::Function &function,
434                              lldb_private::Error &error)
435 {
436     lldb_private::Log *log(lldb_private::GetLogIfAllCategoriesSet (LIBLLDB_LOG_EXPRESSIONS));
437 
438     bool saw_function_with_body = false;
439 
440     for (Module::iterator fi = module.begin(), fe = module.end();
441          fi != fe;
442          ++fi)
443     {
444         if (fi->begin() != fi->end())
445         {
446             if (saw_function_with_body)
447                 return false;
448             saw_function_with_body = true;
449         }
450     }
451 
452     for (Function::iterator bbi = function.begin(), bbe = function.end();
453          bbi != bbe;
454          ++bbi)
455     {
456         for (BasicBlock::iterator ii = bbi->begin(), ie = bbi->end();
457              ii != ie;
458              ++ii)
459         {
460             switch (ii->getOpcode())
461             {
462             default:
463                 {
464                     if (log)
465                         log->Printf("Unsupported instruction: %s", PrintValue(ii).c_str());
466                     error.SetErrorToGenericError();
467                     error.SetErrorString(unsupported_opcode_error);
468                     return false;
469                 }
470             case Instruction::Add:
471             case Instruction::Alloca:
472             case Instruction::BitCast:
473             case Instruction::Br:
474             case Instruction::GetElementPtr:
475                 break;
476             case Instruction::ICmp:
477                 {
478                     ICmpInst *icmp_inst = dyn_cast<ICmpInst>(ii);
479 
480                     if (!icmp_inst)
481                     {
482                         error.SetErrorToGenericError();
483                         error.SetErrorString(interpreter_internal_error);
484                         return false;
485                     }
486 
487                     switch (icmp_inst->getPredicate())
488                     {
489                     default:
490                     {
491                         if (log)
492                             log->Printf("Unsupported ICmp predicate: %s", PrintValue(ii).c_str());
493 
494                         error.SetErrorToGenericError();
495                         error.SetErrorString(unsupported_opcode_error);
496                         return false;
497                     }
498                     case CmpInst::ICMP_EQ:
499                     case CmpInst::ICMP_NE:
500                     case CmpInst::ICMP_UGT:
501                     case CmpInst::ICMP_UGE:
502                     case CmpInst::ICMP_ULT:
503                     case CmpInst::ICMP_ULE:
504                     case CmpInst::ICMP_SGT:
505                     case CmpInst::ICMP_SGE:
506                     case CmpInst::ICMP_SLT:
507                     case CmpInst::ICMP_SLE:
508                         break;
509                     }
510                 }
511                 break;
512             case Instruction::And:
513             case Instruction::AShr:
514             case Instruction::IntToPtr:
515             case Instruction::PtrToInt:
516             case Instruction::Load:
517             case Instruction::LShr:
518             case Instruction::Mul:
519             case Instruction::Or:
520             case Instruction::Ret:
521             case Instruction::SDiv:
522             case Instruction::SExt:
523             case Instruction::Shl:
524             case Instruction::SRem:
525             case Instruction::Store:
526             case Instruction::Sub:
527             case Instruction::UDiv:
528             case Instruction::URem:
529             case Instruction::Xor:
530             case Instruction::ZExt:
531                 break;
532             }
533 
534             for (int oi = 0, oe = ii->getNumOperands();
535                  oi != oe;
536                  ++oi)
537             {
538                 Value *operand = ii->getOperand(oi);
539                 Type *operand_type = operand->getType();
540 
541                 switch (operand_type->getTypeID())
542                 {
543                 default:
544                     break;
545                 case Type::VectorTyID:
546                     {
547                         if (log)
548                             log->Printf("Unsupported operand type: %s", PrintType(operand_type).c_str());
549                         error.SetErrorString(unsupported_operand_error);
550                         return false;
551                     }
552                 }
553             }
554         }
555 
556     }
557 
558     return true;}
559 
560 bool
561 IRInterpreter::Interpret (llvm::Module &module,
562                           llvm::Function &function,
563                           llvm::ArrayRef<lldb::addr_t> args,
564                           lldb_private::IRMemoryMap &memory_map,
565                           lldb_private::Error &error,
566                           lldb::addr_t stack_frame_bottom,
567                           lldb::addr_t stack_frame_top)
568 {
569     lldb_private::Log *log(lldb_private::GetLogIfAllCategoriesSet (LIBLLDB_LOG_EXPRESSIONS));
570 
571     if (log)
572     {
573         std::string s;
574         raw_string_ostream oss(s);
575 
576         module.print(oss, NULL);
577 
578         oss.flush();
579 
580         log->Printf("Module as passed in to IRInterpreter::Interpret: \n\"%s\"", s.c_str());
581     }
582 
583     DataLayout data_layout(&module);
584 
585     InterpreterStackFrame frame(data_layout, memory_map, stack_frame_bottom, stack_frame_top);
586 
587     if (frame.m_frame_process_address == LLDB_INVALID_ADDRESS)
588     {
589         error.SetErrorString("Couldn't allocate stack frame");
590     }
591 
592     int arg_index = 0;
593 
594     for (llvm::Function::arg_iterator ai = function.arg_begin(), ae = function.arg_end();
595          ai != ae;
596          ++ai, ++arg_index)
597     {
598         if (args.size() < arg_index)
599         {
600             error.SetErrorString ("Not enough arguments passed in to function");
601             return false;
602         }
603 
604         lldb::addr_t ptr = args[arg_index];
605 
606         frame.MakeArgument(ai, ptr);
607     }
608 
609     uint32_t num_insts = 0;
610 
611     frame.Jump(function.begin());
612 
613     while (frame.m_ii != frame.m_ie && (++num_insts < 4096))
614     {
615         const Instruction *inst = frame.m_ii;
616 
617         if (log)
618             log->Printf("Interpreting %s", PrintValue(inst).c_str());
619 
620         switch (inst->getOpcode())
621         {
622             default:
623                 break;
624             case Instruction::Add:
625             case Instruction::Sub:
626             case Instruction::Mul:
627             case Instruction::SDiv:
628             case Instruction::UDiv:
629             case Instruction::SRem:
630             case Instruction::URem:
631             case Instruction::Shl:
632             case Instruction::LShr:
633             case Instruction::AShr:
634             case Instruction::And:
635             case Instruction::Or:
636             case Instruction::Xor:
637             {
638                 const BinaryOperator *bin_op = dyn_cast<BinaryOperator>(inst);
639 
640                 if (!bin_op)
641                 {
642                     if (log)
643                         log->Printf("getOpcode() returns %s, but instruction is not a BinaryOperator", inst->getOpcodeName());
644                     error.SetErrorToGenericError();
645                     error.SetErrorString(interpreter_internal_error);
646                     return false;
647                 }
648 
649                 Value *lhs = inst->getOperand(0);
650                 Value *rhs = inst->getOperand(1);
651 
652                 lldb_private::Scalar L;
653                 lldb_private::Scalar R;
654 
655                 if (!frame.EvaluateValue(L, lhs, module))
656                 {
657                     if (log)
658                         log->Printf("Couldn't evaluate %s", PrintValue(lhs).c_str());
659                     error.SetErrorToGenericError();
660                     error.SetErrorString(bad_value_error);
661                     return false;
662                 }
663 
664                 if (!frame.EvaluateValue(R, rhs, module))
665                 {
666                     if (log)
667                         log->Printf("Couldn't evaluate %s", PrintValue(rhs).c_str());
668                     error.SetErrorToGenericError();
669                     error.SetErrorString(bad_value_error);
670                     return false;
671                 }
672 
673                 lldb_private::Scalar result;
674 
675                 switch (inst->getOpcode())
676                 {
677                     default:
678                         break;
679                     case Instruction::Add:
680                         result = L + R;
681                         break;
682                     case Instruction::Mul:
683                         result = L * R;
684                         break;
685                     case Instruction::Sub:
686                         result = L - R;
687                         break;
688                     case Instruction::SDiv:
689                         L.MakeSigned();
690                         R.MakeSigned();
691                         result = L / R;
692                         break;
693                     case Instruction::UDiv:
694                         result = L.GetRawBits64(0) / R.GetRawBits64(1);
695                         break;
696                     case Instruction::SRem:
697                         L.MakeSigned();
698                         R.MakeSigned();
699                         result = L % R;
700                         break;
701                     case Instruction::URem:
702                         result = L.GetRawBits64(0) % R.GetRawBits64(1);
703                         break;
704                     case Instruction::Shl:
705                         result = L << R;
706                         break;
707                     case Instruction::AShr:
708                         result = L >> R;
709                         break;
710                     case Instruction::LShr:
711                         result = L;
712                         result.ShiftRightLogical(R);
713                         break;
714                     case Instruction::And:
715                         result = L & R;
716                         break;
717                     case Instruction::Or:
718                         result = L | R;
719                         break;
720                     case Instruction::Xor:
721                         result = L ^ R;
722                         break;
723                 }
724 
725                 frame.AssignValue(inst, result, module);
726 
727                 if (log)
728                 {
729                     log->Printf("Interpreted a %s", inst->getOpcodeName());
730                     log->Printf("  L : %s", frame.SummarizeValue(lhs).c_str());
731                     log->Printf("  R : %s", frame.SummarizeValue(rhs).c_str());
732                     log->Printf("  = : %s", frame.SummarizeValue(inst).c_str());
733                 }
734             }
735                 break;
736             case Instruction::Alloca:
737             {
738                 const AllocaInst *alloca_inst = dyn_cast<AllocaInst>(inst);
739 
740                 if (!alloca_inst)
741                 {
742                     if (log)
743                         log->Printf("getOpcode() returns Alloca, but instruction is not an AllocaInst");
744                     error.SetErrorToGenericError();
745                     error.SetErrorString(interpreter_internal_error);
746                     return false;
747                 }
748 
749                 if (alloca_inst->isArrayAllocation())
750                 {
751                     if (log)
752                         log->Printf("AllocaInsts are not handled if isArrayAllocation() is true");
753                     error.SetErrorToGenericError();
754                     error.SetErrorString(unsupported_opcode_error);
755                     return false;
756                 }
757 
758                 // The semantics of Alloca are:
759                 //   Create a region R of virtual memory of type T, backed by a data buffer
760                 //   Create a region P of virtual memory of type T*, backed by a data buffer
761                 //   Write the virtual address of R into P
762 
763                 Type *T = alloca_inst->getAllocatedType();
764                 Type *Tptr = alloca_inst->getType();
765 
766                 lldb::addr_t R = frame.Malloc(T);
767 
768                 if (R == LLDB_INVALID_ADDRESS)
769                 {
770                     if (log)
771                         log->Printf("Couldn't allocate memory for an AllocaInst");
772                     error.SetErrorToGenericError();
773                     error.SetErrorString(memory_allocation_error);
774                     return false;
775                 }
776 
777                 lldb::addr_t P = frame.Malloc(Tptr);
778 
779                 if (P == LLDB_INVALID_ADDRESS)
780                 {
781                     if (log)
782                         log->Printf("Couldn't allocate the result pointer for an AllocaInst");
783                     error.SetErrorToGenericError();
784                     error.SetErrorString(memory_allocation_error);
785                     return false;
786                 }
787 
788                 lldb_private::Error write_error;
789 
790                 memory_map.WritePointerToMemory(P, R, write_error);
791 
792                 if (!write_error.Success())
793                 {
794                     if (log)
795                         log->Printf("Couldn't write the result pointer for an AllocaInst");
796                     error.SetErrorToGenericError();
797                     error.SetErrorString(memory_write_error);
798                     lldb_private::Error free_error;
799                     memory_map.Free(P, free_error);
800                     memory_map.Free(R, free_error);
801                     return false;
802                 }
803 
804                 frame.m_values[alloca_inst] = P;
805 
806                 if (log)
807                 {
808                     log->Printf("Interpreted an AllocaInst");
809                     log->Printf("  R : 0x%" PRIx64, R);
810                     log->Printf("  P : 0x%" PRIx64, P);
811                 }
812             }
813                 break;
814             case Instruction::BitCast:
815             case Instruction::ZExt:
816             {
817                 const CastInst *cast_inst = dyn_cast<CastInst>(inst);
818 
819                 if (!cast_inst)
820                 {
821                     if (log)
822                         log->Printf("getOpcode() returns %s, but instruction is not a BitCastInst", cast_inst->getOpcodeName());
823                     error.SetErrorToGenericError();
824                     error.SetErrorString(interpreter_internal_error);
825                     return false;
826                 }
827 
828                 Value *source = cast_inst->getOperand(0);
829 
830                 lldb_private::Scalar S;
831 
832                 if (!frame.EvaluateValue(S, source, module))
833                 {
834                     if (log)
835                         log->Printf("Couldn't evaluate %s", PrintValue(source).c_str());
836                     error.SetErrorToGenericError();
837                     error.SetErrorString(bad_value_error);
838                     return false;
839                 }
840 
841                 frame.AssignValue(inst, S, module);
842             }
843                 break;
844             case Instruction::SExt:
845             {
846                 const CastInst *cast_inst = dyn_cast<CastInst>(inst);
847 
848                 if (!cast_inst)
849                 {
850                     if (log)
851                         log->Printf("getOpcode() returns %s, but instruction is not a BitCastInst", cast_inst->getOpcodeName());
852                     error.SetErrorToGenericError();
853                     error.SetErrorString(interpreter_internal_error);
854                     return false;
855                 }
856 
857                 Value *source = cast_inst->getOperand(0);
858 
859                 lldb_private::Scalar S;
860 
861                 if (!frame.EvaluateValue(S, source, module))
862                 {
863                     if (log)
864                         log->Printf("Couldn't evaluate %s", PrintValue(source).c_str());
865                     error.SetErrorToGenericError();
866                     error.SetErrorString(bad_value_error);
867                     return false;
868                 }
869 
870                 S.MakeSigned();
871 
872                 lldb_private::Scalar S_signextend(S.SLongLong());
873 
874                 frame.AssignValue(inst, S_signextend, module);
875             }
876                 break;
877             case Instruction::Br:
878             {
879                 const BranchInst *br_inst = dyn_cast<BranchInst>(inst);
880 
881                 if (!br_inst)
882                 {
883                     if (log)
884                         log->Printf("getOpcode() returns Br, but instruction is not a BranchInst");
885                     error.SetErrorToGenericError();
886                     error.SetErrorString(interpreter_internal_error);
887                     return false;
888                 }
889 
890                 if (br_inst->isConditional())
891                 {
892                     Value *condition = br_inst->getCondition();
893 
894                     lldb_private::Scalar C;
895 
896                     if (!frame.EvaluateValue(C, condition, module))
897                     {
898                         if (log)
899                             log->Printf("Couldn't evaluate %s", PrintValue(condition).c_str());
900                         error.SetErrorToGenericError();
901                         error.SetErrorString(bad_value_error);
902                         return false;
903                     }
904 
905                     if (C.GetRawBits64(0))
906                         frame.Jump(br_inst->getSuccessor(0));
907                     else
908                         frame.Jump(br_inst->getSuccessor(1));
909 
910                     if (log)
911                     {
912                         log->Printf("Interpreted a BrInst with a condition");
913                         log->Printf("  cond : %s", frame.SummarizeValue(condition).c_str());
914                     }
915                 }
916                 else
917                 {
918                     frame.Jump(br_inst->getSuccessor(0));
919 
920                     if (log)
921                     {
922                         log->Printf("Interpreted a BrInst with no condition");
923                     }
924                 }
925             }
926                 continue;
927             case Instruction::GetElementPtr:
928             {
929                 const GetElementPtrInst *gep_inst = dyn_cast<GetElementPtrInst>(inst);
930 
931                 if (!gep_inst)
932                 {
933                     if (log)
934                         log->Printf("getOpcode() returns GetElementPtr, but instruction is not a GetElementPtrInst");
935                     error.SetErrorToGenericError();
936                     error.SetErrorString(interpreter_internal_error);
937                     return false;
938                 }
939 
940                 const Value *pointer_operand = gep_inst->getPointerOperand();
941                 Type *pointer_type = pointer_operand->getType();
942 
943                 lldb_private::Scalar P;
944 
945                 if (!frame.EvaluateValue(P, pointer_operand, module))
946                 {
947                     if (log)
948                         log->Printf("Couldn't evaluate %s", PrintValue(pointer_operand).c_str());
949                     error.SetErrorToGenericError();
950                     error.SetErrorString(bad_value_error);
951                     return false;
952                 }
953 
954                 typedef SmallVector <Value *, 8> IndexVector;
955                 typedef IndexVector::iterator IndexIterator;
956 
957                 SmallVector <Value *, 8> indices (gep_inst->idx_begin(),
958                                                   gep_inst->idx_end());
959 
960                 SmallVector <Value *, 8> const_indices;
961 
962                 for (IndexIterator ii = indices.begin(), ie = indices.end();
963                      ii != ie;
964                      ++ii)
965                 {
966                     ConstantInt *constant_index = dyn_cast<ConstantInt>(*ii);
967 
968                     if (!constant_index)
969                     {
970                         lldb_private::Scalar I;
971 
972                         if (!frame.EvaluateValue(I, *ii, module))
973                         {
974                             if (log)
975                                 log->Printf("Couldn't evaluate %s", PrintValue(*ii).c_str());
976                             error.SetErrorToGenericError();
977                             error.SetErrorString(bad_value_error);
978                             return false;
979                         }
980 
981                         if (log)
982                             log->Printf("Evaluated constant index %s as %llu", PrintValue(*ii).c_str(), I.ULongLong(LLDB_INVALID_ADDRESS));
983 
984                         constant_index = cast<ConstantInt>(ConstantInt::get((*ii)->getType(), I.ULongLong(LLDB_INVALID_ADDRESS)));
985                     }
986 
987                     const_indices.push_back(constant_index);
988                 }
989 
990                 uint64_t offset = data_layout.getIndexedOffset(pointer_type, const_indices);
991 
992                 lldb_private::Scalar Poffset = P + offset;
993 
994                 frame.AssignValue(inst, Poffset, module);
995 
996                 if (log)
997                 {
998                     log->Printf("Interpreted a GetElementPtrInst");
999                     log->Printf("  P       : %s", frame.SummarizeValue(pointer_operand).c_str());
1000                     log->Printf("  Poffset : %s", frame.SummarizeValue(inst).c_str());
1001                 }
1002             }
1003                 break;
1004             case Instruction::ICmp:
1005             {
1006                 const ICmpInst *icmp_inst = dyn_cast<ICmpInst>(inst);
1007 
1008                 if (!icmp_inst)
1009                 {
1010                     if (log)
1011                         log->Printf("getOpcode() returns ICmp, but instruction is not an ICmpInst");
1012                     error.SetErrorToGenericError();
1013                     error.SetErrorString(interpreter_internal_error);
1014                     return false;
1015                 }
1016 
1017                 CmpInst::Predicate predicate = icmp_inst->getPredicate();
1018 
1019                 Value *lhs = inst->getOperand(0);
1020                 Value *rhs = inst->getOperand(1);
1021 
1022                 lldb_private::Scalar L;
1023                 lldb_private::Scalar R;
1024 
1025                 if (!frame.EvaluateValue(L, lhs, module))
1026                 {
1027                     if (log)
1028                         log->Printf("Couldn't evaluate %s", PrintValue(lhs).c_str());
1029                     error.SetErrorToGenericError();
1030                     error.SetErrorString(bad_value_error);
1031                     return false;
1032                 }
1033 
1034                 if (!frame.EvaluateValue(R, rhs, module))
1035                 {
1036                     if (log)
1037                         log->Printf("Couldn't evaluate %s", PrintValue(rhs).c_str());
1038                     error.SetErrorToGenericError();
1039                     error.SetErrorString(bad_value_error);
1040                     return false;
1041                 }
1042 
1043                 lldb_private::Scalar result;
1044 
1045                 switch (predicate)
1046                 {
1047                     default:
1048                         return false;
1049                     case CmpInst::ICMP_EQ:
1050                         result = (L == R);
1051                         break;
1052                     case CmpInst::ICMP_NE:
1053                         result = (L != R);
1054                         break;
1055                     case CmpInst::ICMP_UGT:
1056                         result = (L.GetRawBits64(0) > R.GetRawBits64(0));
1057                         break;
1058                     case CmpInst::ICMP_UGE:
1059                         result = (L.GetRawBits64(0) >= R.GetRawBits64(0));
1060                         break;
1061                     case CmpInst::ICMP_ULT:
1062                         result = (L.GetRawBits64(0) < R.GetRawBits64(0));
1063                         break;
1064                     case CmpInst::ICMP_ULE:
1065                         result = (L.GetRawBits64(0) <= R.GetRawBits64(0));
1066                         break;
1067                     case CmpInst::ICMP_SGT:
1068                         L.MakeSigned();
1069                         R.MakeSigned();
1070                         result = (L > R);
1071                         break;
1072                     case CmpInst::ICMP_SGE:
1073                         L.MakeSigned();
1074                         R.MakeSigned();
1075                         result = (L >= R);
1076                         break;
1077                     case CmpInst::ICMP_SLT:
1078                         L.MakeSigned();
1079                         R.MakeSigned();
1080                         result = (L < R);
1081                         break;
1082                     case CmpInst::ICMP_SLE:
1083                         L.MakeSigned();
1084                         R.MakeSigned();
1085                         result = (L <= R);
1086                         break;
1087                 }
1088 
1089                 frame.AssignValue(inst, result, module);
1090 
1091                 if (log)
1092                 {
1093                     log->Printf("Interpreted an ICmpInst");
1094                     log->Printf("  L : %s", frame.SummarizeValue(lhs).c_str());
1095                     log->Printf("  R : %s", frame.SummarizeValue(rhs).c_str());
1096                     log->Printf("  = : %s", frame.SummarizeValue(inst).c_str());
1097                 }
1098             }
1099                 break;
1100             case Instruction::IntToPtr:
1101             {
1102                 const IntToPtrInst *int_to_ptr_inst = dyn_cast<IntToPtrInst>(inst);
1103 
1104                 if (!int_to_ptr_inst)
1105                 {
1106                     if (log)
1107                         log->Printf("getOpcode() returns IntToPtr, but instruction is not an IntToPtrInst");
1108                     error.SetErrorToGenericError();
1109                     error.SetErrorString(interpreter_internal_error);
1110                     return false;
1111                 }
1112 
1113                 Value *src_operand = int_to_ptr_inst->getOperand(0);
1114 
1115                 lldb_private::Scalar I;
1116 
1117                 if (!frame.EvaluateValue(I, src_operand, module))
1118                 {
1119                     if (log)
1120                         log->Printf("Couldn't evaluate %s", PrintValue(src_operand).c_str());
1121                     error.SetErrorToGenericError();
1122                     error.SetErrorString(bad_value_error);
1123                     return false;
1124                 }
1125 
1126                 frame.AssignValue(inst, I, module);
1127 
1128                 if (log)
1129                 {
1130                     log->Printf("Interpreted an IntToPtr");
1131                     log->Printf("  Src : %s", frame.SummarizeValue(src_operand).c_str());
1132                     log->Printf("  =   : %s", frame.SummarizeValue(inst).c_str());
1133                 }
1134             }
1135                 break;
1136             case Instruction::PtrToInt:
1137             {
1138                 const PtrToIntInst *ptr_to_int_inst = dyn_cast<PtrToIntInst>(inst);
1139 
1140                 if (!ptr_to_int_inst)
1141                 {
1142                     if (log)
1143                         log->Printf("getOpcode() returns PtrToInt, but instruction is not an PtrToIntInst");
1144                     error.SetErrorToGenericError();
1145                     error.SetErrorString(interpreter_internal_error);
1146                     return false;
1147                 }
1148 
1149                 Value *src_operand = ptr_to_int_inst->getOperand(0);
1150 
1151                 lldb_private::Scalar I;
1152 
1153                 if (!frame.EvaluateValue(I, src_operand, module))
1154                 {
1155                     if (log)
1156                         log->Printf("Couldn't evaluate %s", PrintValue(src_operand).c_str());
1157                     error.SetErrorToGenericError();
1158                     error.SetErrorString(bad_value_error);
1159                     return false;
1160                 }
1161 
1162                 frame.AssignValue(inst, I, module);
1163 
1164                 if (log)
1165                 {
1166                     log->Printf("Interpreted a PtrToInt");
1167                     log->Printf("  Src : %s", frame.SummarizeValue(src_operand).c_str());
1168                     log->Printf("  =   : %s", frame.SummarizeValue(inst).c_str());
1169                 }
1170             }
1171                 break;
1172             case Instruction::Load:
1173             {
1174                 const LoadInst *load_inst = dyn_cast<LoadInst>(inst);
1175 
1176                 if (!load_inst)
1177                 {
1178                     if (log)
1179                         log->Printf("getOpcode() returns Load, but instruction is not a LoadInst");
1180                     error.SetErrorToGenericError();
1181                     error.SetErrorString(interpreter_internal_error);
1182                     return false;
1183                 }
1184 
1185                 // The semantics of Load are:
1186                 //   Create a region D that will contain the loaded data
1187                 //   Resolve the region P containing a pointer
1188                 //   Dereference P to get the region R that the data should be loaded from
1189                 //   Transfer a unit of type type(D) from R to D
1190 
1191                 const Value *pointer_operand = load_inst->getPointerOperand();
1192 
1193                 Type *pointer_ty = pointer_operand->getType();
1194                 PointerType *pointer_ptr_ty = dyn_cast<PointerType>(pointer_ty);
1195                 if (!pointer_ptr_ty)
1196                 {
1197                     if (log)
1198                         log->Printf("getPointerOperand()->getType() is not a PointerType");
1199                     error.SetErrorToGenericError();
1200                     error.SetErrorString(interpreter_internal_error);
1201                     return false;
1202                 }
1203                 Type *target_ty = pointer_ptr_ty->getElementType();
1204 
1205                 lldb::addr_t D = frame.ResolveValue(load_inst, module);
1206                 lldb::addr_t P = frame.ResolveValue(pointer_operand, module);
1207 
1208                 if (D == LLDB_INVALID_ADDRESS)
1209                 {
1210                     if (log)
1211                         log->Printf("LoadInst's value doesn't resolve to anything");
1212                     error.SetErrorToGenericError();
1213                     error.SetErrorString(bad_value_error);
1214                     return false;
1215                 }
1216 
1217                 if (P == LLDB_INVALID_ADDRESS)
1218                 {
1219                     if (log)
1220                         log->Printf("LoadInst's pointer doesn't resolve to anything");
1221                     error.SetErrorToGenericError();
1222                     error.SetErrorString(bad_value_error);
1223                     return false;
1224                 }
1225 
1226                 lldb::addr_t R;
1227                 lldb_private::Error read_error;
1228                 memory_map.ReadPointerFromMemory(&R, P, read_error);
1229 
1230                 if (!read_error.Success())
1231                 {
1232                     if (log)
1233                         log->Printf("Couldn't read the address to be loaded for a LoadInst");
1234                     error.SetErrorToGenericError();
1235                     error.SetErrorString(memory_read_error);
1236                     return false;
1237                 }
1238 
1239                 size_t target_size = data_layout.getTypeStoreSize(target_ty);
1240                 lldb_private::DataBufferHeap buffer(target_size, 0);
1241 
1242                 read_error.Clear();
1243                 memory_map.ReadMemory(buffer.GetBytes(), R, buffer.GetByteSize(), read_error);
1244                 if (!read_error.Success())
1245                 {
1246                     if (log)
1247                         log->Printf("Couldn't read from a region on behalf of a LoadInst");
1248                     error.SetErrorToGenericError();
1249                     error.SetErrorString(memory_read_error);
1250                     return false;
1251                 }
1252 
1253                 lldb_private::Error write_error;
1254                 memory_map.WriteMemory(D, buffer.GetBytes(), buffer.GetByteSize(), write_error);
1255                 if (!write_error.Success())
1256                 {
1257                     if (log)
1258                         log->Printf("Couldn't write to a region on behalf of a LoadInst");
1259                     error.SetErrorToGenericError();
1260                     error.SetErrorString(memory_read_error);
1261                     return false;
1262                 }
1263 
1264                 if (log)
1265                 {
1266                     log->Printf("Interpreted a LoadInst");
1267                     log->Printf("  P : 0x%" PRIx64, P);
1268                     log->Printf("  R : 0x%" PRIx64, R);
1269                     log->Printf("  D : 0x%" PRIx64, D);
1270                 }
1271             }
1272                 break;
1273             case Instruction::Ret:
1274             {
1275                 return true;
1276             }
1277             case Instruction::Store:
1278             {
1279                 const StoreInst *store_inst = dyn_cast<StoreInst>(inst);
1280 
1281                 if (!store_inst)
1282                 {
1283                     if (log)
1284                         log->Printf("getOpcode() returns Store, but instruction is not a StoreInst");
1285                     error.SetErrorToGenericError();
1286                     error.SetErrorString(interpreter_internal_error);
1287                     return false;
1288                 }
1289 
1290                 // The semantics of Store are:
1291                 //   Resolve the region D containing the data to be stored
1292                 //   Resolve the region P containing a pointer
1293                 //   Dereference P to get the region R that the data should be stored in
1294                 //   Transfer a unit of type type(D) from D to R
1295 
1296                 const Value *value_operand = store_inst->getValueOperand();
1297                 const Value *pointer_operand = store_inst->getPointerOperand();
1298 
1299                 Type *pointer_ty = pointer_operand->getType();
1300                 PointerType *pointer_ptr_ty = dyn_cast<PointerType>(pointer_ty);
1301                 if (!pointer_ptr_ty)
1302                     return false;
1303                 Type *target_ty = pointer_ptr_ty->getElementType();
1304 
1305                 lldb::addr_t D = frame.ResolveValue(value_operand, module);
1306                 lldb::addr_t P = frame.ResolveValue(pointer_operand, module);
1307 
1308                 if (D == LLDB_INVALID_ADDRESS)
1309                 {
1310                     if (log)
1311                         log->Printf("StoreInst's value doesn't resolve to anything");
1312                     error.SetErrorToGenericError();
1313                     error.SetErrorString(bad_value_error);
1314                     return false;
1315                 }
1316 
1317                 if (P == LLDB_INVALID_ADDRESS)
1318                 {
1319                     if (log)
1320                         log->Printf("StoreInst's pointer doesn't resolve to anything");
1321                     error.SetErrorToGenericError();
1322                     error.SetErrorString(bad_value_error);
1323                     return false;
1324                 }
1325 
1326                 lldb::addr_t R;
1327                 lldb_private::Error read_error;
1328                 memory_map.ReadPointerFromMemory(&R, P, read_error);
1329 
1330                 if (!read_error.Success())
1331                 {
1332                     if (log)
1333                         log->Printf("Couldn't read the address to be loaded for a LoadInst");
1334                     error.SetErrorToGenericError();
1335                     error.SetErrorString(memory_read_error);
1336                     return false;
1337                 }
1338 
1339                 size_t target_size = data_layout.getTypeStoreSize(target_ty);
1340                 lldb_private::DataBufferHeap buffer(target_size, 0);
1341 
1342                 read_error.Clear();
1343                 memory_map.ReadMemory(buffer.GetBytes(), D, buffer.GetByteSize(), read_error);
1344                 if (!read_error.Success())
1345                 {
1346                     if (log)
1347                         log->Printf("Couldn't read from a region on behalf of a StoreInst");
1348                     error.SetErrorToGenericError();
1349                     error.SetErrorString(memory_read_error);
1350                     return false;
1351                 }
1352 
1353                 lldb_private::Error write_error;
1354                 memory_map.WriteMemory(R, buffer.GetBytes(), buffer.GetByteSize(), write_error);
1355                 if (!write_error.Success())
1356                 {
1357                     if (log)
1358                         log->Printf("Couldn't write to a region on behalf of a StoreInst");
1359                     error.SetErrorToGenericError();
1360                     error.SetErrorString(memory_write_error);
1361                     return false;
1362                 }
1363 
1364                 if (log)
1365                 {
1366                     log->Printf("Interpreted a StoreInst");
1367                     log->Printf("  D : 0x%" PRIx64, D);
1368                     log->Printf("  P : 0x%" PRIx64, P);
1369                     log->Printf("  R : 0x%" PRIx64, R);
1370                 }
1371             }
1372                 break;
1373         }
1374 
1375         ++frame.m_ii;
1376     }
1377 
1378     if (num_insts >= 4096)
1379     {
1380         error.SetErrorToGenericError();
1381         error.SetErrorString(infinite_loop_error);
1382         return false;
1383     }
1384 
1385     return false;
1386 }
1387