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