[LLDB] Added support for PHI nodes to IR interpreter

[cameron314]

Summary

This allows expressions such as 'i == 1 || i == 2` to be executed using the IR interpreter.

[zturner]

I'll let Sean comment on the content of the patch, but please add a test
that runs such an expression and demonstrates the correct output.

[cameron314]

Ah, that's a bit tricky at the moment. The LLVM tip no longer compiles with VS2015 (specifically lib\Support\SourceMgr.cpp), and my Python setup for VS2013 is all wonky.
This will have to wait a bit.

[zturner]

http://lab.llvm.org:8011/builders/lldb-x86-windows-msvc2015

My build bot which uses MSVC 2015 is workign fine. What kind of error are
you seeing?

[cameron314]

Whoops, my fault. I was accidentally using the VS2013 command prompt with the 2015 cmake files. Compiling happily as we speak, test coming up soon after.

[cameron314]

I've added a test for this patch.

[cameron314]

I'd appreciate if someone could take a look at this when they have a moment.

[zturner]

This is going to have to be Sean, but his delay can be unpredictable. Keep
pinging every so often until you get a response

[cameron314]

All right, no worries :-) I didn't want to bother anyone.

[cameron314]

@spyffe, do you have time to look at this sometime this week? It's a very simple patch (the test code took longer to write than the patch itself). Thanks!

[spyffe]

Ah… you know me too well.
Looking at this now.

[spyffe]

This patch is fine. I especially appreciate the time you took making the IRInterpreter properly testable. I will use this myself.

source/Commands/CommandObjectExpression.cpp

67

This is a great feature which I will use in test cases.

source/Expression/IRInterpreter.cpp

1102

Looks all right to me. Thank you!

[cameron314]

Excellent, thank you!

[ovyalov]

Looks like this CL broke CMake build bot - http://lab.llvm.org:8011/builders/lldb-x86_64-ubuntu-14.04-cmake/builds/14634, could you take a look?

packages/Python/lldbsuite/test/expression_command/ir-interpreter/Makefile

+LEVEL = ../../make
+
+CXX_SOURCES := main.cpp
+
+include $(LEVEL)/Makefile.rules
 No newline at end of file

packages/Python/lldbsuite/test/expression_command/ir-interpreter/TestIRInterpreter.py

+"""
+Test certain parts of the IR interpreter.
+"""
+
+import os, os.path
+
+import lldb
+from lldbsuite.test.lldbtest import *
+import lldbsuite.test.lldbutil as lldbutil
+
+class IRInterpreterTestCase(TestBase):
+    mydir = TestBase.compute_mydir(__file__)
+
+    def test_phi_node_support(self):
+        """Test support for PHI nodes in the IR interpreter."""
+        
+        self.build()
+        exe = os.path.join(os.getcwd(), 'a.out')
+        self.runCmd('file ' + exe, CURRENT_EXECUTABLE_SET)
+        
+        # Break on the first assignment to i
+        line = line_number('main.cpp', 'i = 5')
+        lldbutil.run_break_set_by_file_and_line(self, 'main.cpp', line, num_expected_locations=1, loc_exact=True)
+        
+        self.runCmd('run', RUN_SUCCEEDED)
+        
+        # The stop reason of the thread should be breakpoint
+        self.expect('thread list', STOPPED_DUE_TO_BREAKPOINT,
+            substrs = ['stopped', 'stop reason = breakpoint'])
+        
+        self.runCmd('s')
+        
+        # The logical 'or' causes a PHI node to be generated. Execute without JIT
+        # to test that the interpreter can handle this
+        self.expect('expr -j 0 -- i == 3 || i == 5', substrs=['true'])
+        
+        self.runCmd('s')
+        self.expect('expr -j 0 -- i == 3 || i == 5', substrs=['false'])
+        self.runCmd('s')
+        self.expect('expr -j 0 -- i == 3 || i == 5', substrs=['true'])

packages/Python/lldbsuite/test/expression_command/ir-interpreter/main.cpp

+//===-- main.cpp ------------------------------------------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+int main()
+{
+    int i;
+    i = 5;
+    i = 2;
+    i = 3;
+    return 0;
+}

source/Commands/CommandObjectExpression.h

public:
         OptionParsingStarting(CommandInterpreter &interpreter) override;
 
         // Options table: Required for subclasses of Options.
 
         static OptionDefinition g_option_table[];
         bool        top_level;
         bool        unwind_on_error;
         bool        ignore_breakpoints;
+        bool        allow_jit;
         bool        show_types;
         bool        show_summary;
         bool        debug;
         uint32_t    timeout;
         bool        try_all_threads;
         lldb::LanguageType language;
         LanguageRuntimeDescriptionDisplayVerbosity m_verbosity;
         LazyBool        auto_apply_fixits;

source/Commands/CommandObjectExpression.cpp

CommandObjectExpression::CommandOptions::g_option_table[] =
     { LLDB_OPT_SET_1 | LLDB_OPT_SET_2, false, "all-threads",        'a', OptionParser::eRequiredArgument, nullptr, nullptr, 0, eArgTypeBoolean,    "Should we run all threads if the execution doesn't complete on one thread."},
     { LLDB_OPT_SET_1 | LLDB_OPT_SET_2, false, "ignore-breakpoints", 'i', OptionParser::eRequiredArgument, nullptr, nullptr, 0, eArgTypeBoolean,    "Ignore breakpoint hits while running expressions"},
     { LLDB_OPT_SET_1 | LLDB_OPT_SET_2, false, "timeout",            't', OptionParser::eRequiredArgument, nullptr, nullptr, 0, eArgTypeUnsignedInteger,  "Timeout value (in microseconds) for running the expression."},
     { LLDB_OPT_SET_1 | LLDB_OPT_SET_2, false, "unwind-on-error",    'u', OptionParser::eRequiredArgument, nullptr, nullptr, 0, eArgTypeBoolean,    "Clean up program state if the expression causes a crash, or raises a signal.  Note, unlike gdb hitting a breakpoint is controlled by another option (-i)."},
     { LLDB_OPT_SET_1 | LLDB_OPT_SET_2, false, "debug",              'g', OptionParser::eNoArgument      , nullptr, nullptr, 0, eArgTypeNone,       "When specified, debug the JIT code by setting a breakpoint on the first instruction and forcing breakpoints to not be ignored (-i0) and no unwinding to happen on error (-u0)."},
     { LLDB_OPT_SET_1 | LLDB_OPT_SET_2, false, "language",           'l', OptionParser::eRequiredArgument, nullptr, nullptr, 0, eArgTypeLanguage,   "Specifies the Language to use when parsing the expression.  If not set the target.language setting is used." },
     { LLDB_OPT_SET_1 | LLDB_OPT_SET_2, false, "apply-fixits",       'X', OptionParser::eRequiredArgument, nullptr, nullptr, 0, eArgTypeLanguage,   "If true, simple FixIt hints will be automatically applied to the expression." },
     { LLDB_OPT_SET_1, false, "description-verbosity", 'v', OptionParser::eOptionalArgument, nullptr, g_description_verbosity_type, 0, eArgTypeDescriptionVerbosity,        "How verbose should the output of this expression be, if the object description is asked for."},
-    { LLDB_OPT_SET_1 | LLDB_OPT_SET_2, false, "top-level",          'p', OptionParser::eNoArgument      , NULL, NULL, 0, eArgTypeNone,       "Interpret the expression as top-level definitions rather than code to be immediately executed."}
+    { LLDB_OPT_SET_1 | LLDB_OPT_SET_2, false, "top-level",          'p', OptionParser::eNoArgument      , NULL, NULL, 0, eArgTypeNone,       "Interpret the expression as top-level definitions rather than code to be immediately executed."},
+    { LLDB_OPT_SET_1 | LLDB_OPT_SET_2, false, "allow-jit",          'j', OptionParser::eRequiredArgument, nullptr, nullptr, 0, eArgTypeBoolean,    "Controls whether the expression can fall back to being JITted if it's not supported by the interpreter (defaults to true)."}
 };
 
 uint32_t
 CommandObjectExpression::CommandOptions::GetNumDefinitions ()
 {
     return llvm::array_lengthof(g_option_table);
 }
 
case 'i':
             bool success;
             bool tmp_value = Args::StringToBoolean(option_arg, true, &success);
             if (success)
                 ignore_breakpoints = tmp_value;
             else
                 error.SetErrorStringWithFormat("could not convert \"%s\" to a boolean value.", option_arg);
             break;
         }
+
+    case 'j':
+        {
+            bool success;
+            bool tmp_value = Args::StringToBoolean(option_arg, true, &success);
+            if (success)
+                allow_jit = tmp_value;
+            else
+                error.SetErrorStringWithFormat("could not convert \"%s\" to a boolean value.", option_arg);
+            break;
+        }
+
     case 't':
         {
             bool success;
             uint32_t result;
             result = StringConvert::ToUInt32(option_arg, 0, 0, &success);
             if (success)
                 timeout = result;
             else
CommandObjectExpression::CommandOptions::OptionParsingStarting (CommandInterpreter &interpreter)
     show_summary = true;
     try_all_threads = true;
     timeout = 0;
     debug = false;
     language = eLanguageTypeUnknown;
     m_verbosity = eLanguageRuntimeDescriptionDisplayVerbosityCompact;
     auto_apply_fixits = eLazyBoolCalculate;
     top_level = false;
+    allow_jit = true;
 }
 
 const OptionDefinition*
 CommandObjectExpression::CommandOptions::GetDefinitions ()
 {
     return g_option_table;
 }
 
if (target)
         options.SetCoerceToId(m_varobj_options.use_objc);
         options.SetUnwindOnError(m_command_options.unwind_on_error);
         options.SetIgnoreBreakpoints (m_command_options.ignore_breakpoints);
         options.SetKeepInMemory(keep_in_memory);
         options.SetUseDynamic(m_varobj_options.use_dynamic);
         options.SetTryAllThreads(m_command_options.try_all_threads);
         options.SetDebug(m_command_options.debug);
         options.SetLanguage(m_command_options.language);
+        options.SetExecutionPolicy(m_command_options.allow_jit ?
+            EvaluateExpressionOptions::default_execution_policy :
+            lldb_private::eExecutionPolicyNever);
         
         bool auto_apply_fixits;
         if (m_command_options.auto_apply_fixits == eLazyBoolCalculate)
             auto_apply_fixits = target->GetEnableAutoApplyFixIts();
         else
             auto_apply_fixits = m_command_options.auto_apply_fixits == eLazyBoolYes ? true : false;
         
         options.SetAutoApplyFixIts(auto_apply_fixits);

source/Expression/IRInterpreter.cpp

 {
 public:
     typedef std::map <const Value*, lldb::addr_t> ValueMap;
 
     ValueMap                                m_values;
     DataLayout                             &m_target_data;
     lldb_private::IRExecutionUnit          &m_execution_unit;
     const BasicBlock                       *m_bb;
+    const BasicBlock                       *m_prev_bb;
     BasicBlock::const_iterator              m_ii;
     BasicBlock::const_iterator              m_ie;
 
     lldb::addr_t                            m_frame_process_address;
     size_t                                  m_frame_size;
     lldb::addr_t                            m_stack_pointer;
 
     lldb::ByteOrder                         m_byte_order;
     size_t                                  m_addr_byte_size;
 
     InterpreterStackFrame (DataLayout &target_data,
                            lldb_private::IRExecutionUnit &execution_unit,
                            lldb::addr_t stack_frame_bottom,
                            lldb::addr_t stack_frame_top) :
         m_target_data (target_data),
-        m_execution_unit (execution_unit)
+        m_execution_unit (execution_unit),
+        m_bb (nullptr),
+        m_prev_bb (nullptr)
     {
         m_byte_order = (target_data.isLittleEndian() ? lldb::eByteOrderLittle : lldb::eByteOrderBig);
         m_addr_byte_size = (target_data.getPointerSize(0));
 
         m_frame_process_address = stack_frame_bottom;
         m_frame_size = stack_frame_top - stack_frame_bottom;
         m_stack_pointer = stack_frame_top;
     }
 
     ~InterpreterStackFrame ()
     {
     }
 
     void Jump (const BasicBlock *bb)
     {
+        m_prev_bb = m_bb;
         m_bb = bb;
         m_ii = m_bb->begin();
         m_ie = m_bb->end();
     }
 
     std::string SummarizeValue (const Value *value)
     {
         lldb_private::StreamString ss;
for (Function::iterator bbi = function.begin(), bbe = function.end();
                     error.SetErrorToGenericError();
                     error.SetErrorString(unsupported_opcode_error);
                     return false;
                 }
             case Instruction::Add:
             case Instruction::Alloca:
             case Instruction::BitCast:
             case Instruction::Br:
+            case Instruction::PHI:
                 break;
             case Instruction::Call:
                 {
                     CallInst *call_inst = dyn_cast<CallInst>(ii);
 
                     if (!call_inst)
                     {
                         error.SetErrorToGenericError();
while (frame.m_ii != frame.m_ie && (++num_insts < 4096))
 
                     if (log)
                     {
                         log->Printf("Interpreted a BrInst with no condition");
                     }
                 }
             }
                 continue;
+            case Instruction::PHI:
+            {
+                const PHINode *phi_inst = dyn_cast<PHINode>(inst);
+
+                if (!phi_inst)
+                {
+                    if (log)
+                        log->Printf("getOpcode() returns PHI, but instruction is not a PHINode");
+                    error.SetErrorToGenericError();
+                    error.SetErrorString(interpreter_internal_error);
+                    return false;
+                }
+                if (!frame.m_prev_bb)
+                {
+                    if (log)
+                        log->Printf("Encountered PHI node without having jumped from another basic block");
+                    error.SetErrorToGenericError();
+                    error.SetErrorString(interpreter_internal_error);
+                    return false;
+                }
+
+                Value* value = phi_inst->getIncomingValueForBlock(frame.m_prev_bb);
+                lldb_private::Scalar result;
+                if (!frame.EvaluateValue(result, value, module))
+                {
+                    if (log)
+                        log->Printf("Couldn't evaluate %s", PrintValue(value).c_str());
+                    error.SetErrorToGenericError();
+                    error.SetErrorString(bad_value_error);
+                    return false;
+                }
+                frame.AssignValue(inst, result, module);
+
+                if (log)
+                {
+                    log->Printf("Interpreted a %s", inst->getOpcodeName());
+                    log->Printf("  Incoming value : %s", frame.SummarizeValue(value).c_str());
+                }
+            }
+            break;
             case Instruction::GetElementPtr:
             {
                 const GetElementPtrInst *gep_inst = dyn_cast<GetElementPtrInst>(inst);
 
                 if (!gep_inst)
                 {
                     if (log)
                         log->Printf("getOpcode() returns GetElementPtr, but instruction is not a GetElementPtrInst");