Fix handling of the arm IT instruction in the unwinder

[tberghammer]

Summary

Fix handling of the arm IT instruction in the unwinder

The IT instruction can specify condition code for up to 4 consecutive
instruction and it is used quite often by clang in epilogues causing
an issue when trying to unwind from locations covered by the IT
instruction and for locations immediately after the IT instruction.

Changes made to fix it:

• Introduce the concept of conditional instruction block what is a list of consecutive instructions with the same condition. We update the unwind information during the conditional instruction block and when we reach the end of it (first instruction with a different condition) then we restore the unwind information we had before the condition.
• Fix a bug in the ARM instruction emulator where neither PC nor the ITSTATE was advanced when we reached an instruction what we can't decode.

After the change we have no regression on android-arm running the
regular test suit and TestStandardUnwind also passes when running it
with clang as the compiler (previously it failed on an IT instruction).

[clayborg]

It would be nice to not pick UINT32_MAX for the unconditional condition and let each emulator picks it desired values. See inlined comments. Let me know what you think.

include/lldb/Core/EmulateInstruction.h

406–410

Add:

virtual uint32_t
GetUnconditionalCondition () { return 0; };

And change GetInstructionCondition to use the above function:

virtual uint32_t
GetInstructionCondition() { return GetUnconditionalCondition (); }

See inline comments below for more info...

source/Plugins/UnwindAssembly/InstEmulation/UnwindAssemblyInstEmulation.cpp

130

Maybe require the instruction emulator to give us an unconditional value here?

const uint32_t unconditional_condition = m_inst_emulator_ap->GetUnconditionalCondition();
uint32_t last_condition = unconditional_condition;

UINT32_MAX follows the ARM way of thinking, but other chips might have their own notion where zero is the unconditional value. It would be nice to not pick any default values for all instruction emulators.

163

Change to:

if (m_inst_emulator_ap->GetInstructionCondition() != unconditional_condition &&

175

Change to:

if (last_condition != unconditional_condition)

[labath]

include/lldb/Core/EmulateInstruction.h

406–410

How about

virtual llvm::Optional<uint32_t>
GetInstructionCondition() { return llvm::NoneType; }

?

[clayborg]

I like that llvm::Optional<uint32_t> idea!

[tberghammer]

UINT32_MAX is a kind of a random value what is most likely won't be used on any architecture as a condition code (I can't imagine having so much different condition flags) and my current intention is to map the unconditional value to into it as it is already done on ARM where the unconditional value is 0b1110 and 0b1111.

I don't really like the idea of introducing a new GetUnconditionalCondition() method because I think it over complicates the API in a situation where it is not necessary. I would better prefer to create a static constant for the unconditional condition (with setting it to UINT32_MAX) so the implementation is a bit cleaner. If we really want to make a very clean interface then I would suggest to introduce a new "Condition" class with a virtual equality operator and a virtual isUnconditional function and then we can make GetInstructionCondition return a pointer to an instance so we don't restrict the storage format for the architectures to a uint32_t. I think this would be the most general API but I also feel it would be a massive over-engineering.

For llvm::Optional<T> the main issue is that (non) equality operator is intentionally not defined for llvm::Optional<T> (I don't know why) what would make UnwindAssemblyInstEmulation.cpp:161 very strange. Also debugging code containing llvm data types is generally pretty complicated.

All in all I would suggest to use a uint32_t/uint64_t for the condition code with UINT32_MAX/UINT64_MAX meaning unconditional and I propose the introduction of a new public/protected static constant on EmulateInstruction what represents the unconditional value. This way the implementation is cleaner because will be obvious when we are comparing against an unconditional condition with keeping the API simple.

What do you think?

[tberghammer]

Create a typedef for the condition type and a static const value for the unconditional condition.

[labath]

I agree that we should not over-engineer things. I'll leave the decision up to others...

[clayborg]

Yes, it was probably too complex. My main objection was the use of the UINT32_MAX as a magic number. Your UnconditionalCondition solution clears this up.

include/lldb/Core/EmulateInstruction.h

390

It is nice to tell when something is a constant (prefixed with "k"), a member variable (prefixed with "m_"), typenames are camel case, variables should be lower cased with underscores. That is our current coding convention.

I would like to see this be

static const InstructionCondition k_unconditional_condition = UINT32_MAX;

407

k_unconditional_condition

source/Plugins/Instruction/ARM/EmulateInstructionARM.cpp

13653–13655

Do you want to use UnconditionalCondition (or k_unconditional_condition) instead of UINT32_MAX here?

13654

k_unconditional_condition

source/Plugins/UnwindAssembly/InstEmulation/UnwindAssemblyInstEmulation.cpp

129

k_unconditional_condition

[tberghammer]

include/lldb/Core/EmulateInstruction.h

390

It is a public, static member variable so I think we should use CamelCase and not snake_case and I don't see where I can add a k prefix into it (KInstructionCondition?) Also as (almost) all static member is cons inside LLDB I don't think it will be confusing

[tberghammer]

Jason: Can you take at the change in the unwinding logic?

source/Plugins/Instruction/ARM/EmulateInstructionARM.cpp

13653–13655

No, here we are inside EmulateInstructionARM. CurrentCond returns UINT32_MAX as a failure value what we want to treat as unconditional (as we can't do anything better). Changing CurrentCond to return UnconditionalCondition in case of a failure won't make any sense either.

[clayborg]

Looks good.

include/lldb/Core/EmulateInstruction.h

typedef bool   (*WriteRegisterCallback) (EmulateInstruction *instruction,
                                              void *baton,
                                              const Context &context, 
                                              const RegisterInfo *reg_info,
                                              const RegisterValue &reg_value);
 
     EmulateInstruction (const ArchSpec &arch);
 
     ~EmulateInstruction() override = default;
 
     //----------------------------------------------------------------------
     // Mandatory overrides
     //----------------------------------------------------------------------    
     virtual bool
     SupportsEmulatingInstructionsOfType (InstructionType inst_type) = 0;
     
     virtual bool
     SetTargetTriple (const ArchSpec &arch) = 0;
     
     virtual bool 
     ReadInstruction () = 0;
 
     virtual bool
     EvaluateInstruction (uint32_t evaluate_options) = 0;
 
-    virtual bool
-    IsInstructionConditional() { return false; }
+    // Returns a condition code in the for of uint32_t where UINT32_MAX means that the instruction
+    // is not conditional and other values specify the condition of the instruction in an
+    // architecture specififc way.
+    virtual uint32_t
+    GetInstructionCondition() { return UINT32_MAX; }
 
     virtual bool
     TestEmulation (Stream *out_stream, ArchSpec &arch, OptionValueDictionary *test_data) = 0;
 
     virtual bool
     GetRegisterInfo (lldb::RegisterKind reg_kind, uint32_t reg_num, RegisterInfo &reg_info) = 0;
 
     //----------------------------------------------------------------------

include/lldb/Symbol/UnwindPlan.h

public:
 
     void 
     Dump (Stream& s, Thread* thread, lldb::addr_t base_addr) const;
 
     void 
     AppendRow (const RowSP& row_sp);
 
     void
-    InsertRow (const RowSP& row_sp);
+    InsertRow (const RowSP& row_sp, bool replace_existing = false);
 
     // Returns a pointer to the best row for the given offset into the function's instructions.
     // If offset is -1 it indicates that the function start is unknown - the final row in the UnwindPlan is returned.
     // In practice, the UnwindPlan for a function with no known start address will be the architectural default
     // UnwindPlan which will only have one row.
     UnwindPlan::RowSP
     GetRowForFunctionOffset (int offset) const;
 

source/Plugins/Instruction/ARM/EmulateInstructionARM.h

//    }
     ReadInstruction ()  override;
     
     bool
     SetInstruction (const Opcode &insn_opcode, const Address &inst_addr, Target *target)  override;
 
     bool
     EvaluateInstruction (uint32_t evaluate_options) override;
 
-    bool
-    IsInstructionConditional() override;
+    uint32_t
+    GetInstructionCondition() override;
 
     bool
     TestEmulation (Stream *out_stream, ArchSpec &arch, OptionValueDictionary *test_data)  override;
 
     bool
     GetRegisterInfo (lldb::RegisterKind reg_kind, uint32_t reg_num, RegisterInfo &reg_info)  override;
 
     bool

source/Plugins/Instruction/ARM/EmulateInstructionARM.cpp

 EmulateInstructionARM::EvaluateInstruction (uint32_t evaluate_options)
 {
     ARMOpcode *opcode_data = NULL;
    
     if (m_opcode_mode == eModeThumb)
         opcode_data = GetThumbOpcodeForInstruction (m_opcode.GetOpcode32(), m_arm_isa);
     else if (m_opcode_mode == eModeARM)
         opcode_data = GetARMOpcodeForInstruction (m_opcode.GetOpcode32(), m_arm_isa);
-        
-    if (opcode_data == NULL)
-        return false;
-    
     const bool auto_advance_pc = evaluate_options & eEmulateInstructionOptionAutoAdvancePC;
     m_ignore_conditions = evaluate_options & eEmulateInstructionOptionIgnoreConditions;
                  
     bool success = false;
     if (m_opcode_cpsr == 0 || m_ignore_conditions == false)
     {
         m_opcode_cpsr = ReadRegisterUnsigned (eRegisterKindDWARF, 
                                                 dwarf_cpsr, 
                                                 0,
                                                 &success);
     }
 
     // Only return false if we are unable to read the CPSR if we care about conditions
     if (success == false && m_ignore_conditions == false)
         return false;
     
     uint32_t orig_pc_value = 0;
     if (auto_advance_pc)
     {
         orig_pc_value = ReadRegisterUnsigned (eRegisterKindDWARF, dwarf_pc, 0, &success);
         if (!success)
             return false;
     }
-    
-    // Call the Emulate... function.
+    // Call the Emulate... function if we managed to decode the opcode.
+    if (opcode_data)
+    {
         success = (this->*opcode_data->callback) (m_opcode.GetOpcode32(), opcode_data->encoding);  
         if (!success)
             return false;
+    }
 
     // Advance the ITSTATE bits to their values for the next instruction if we haven't just executed
     // an IT instruction what initialized it.
     if (m_opcode_mode == eModeThumb && m_it_session.InITBlock() &&
-        opcode_data->callback != &EmulateInstructionARM::EmulateIT)
+        (opcode_data == nullptr || opcode_data->callback != &EmulateInstructionARM::EmulateIT))
         m_it_session.ITAdvance();
 
     if (auto_advance_pc)
     {
         uint32_t after_pc_value = ReadRegisterUnsigned (eRegisterKindDWARF, dwarf_pc, 0, &success);
         if (!success)
             return false;
-            
         if (auto_advance_pc && (after_pc_value == orig_pc_value))
         {
-            if (opcode_data->size == eSize32)
-                after_pc_value += 4;
-            else if (opcode_data->size == eSize16)
-                after_pc_value += 2;
-                
+            after_pc_value += m_opcode.GetByteSize();
             EmulateInstruction::Context context;
             context.type = eContextAdvancePC;
             context.SetNoArgs();
             if (!WriteRegisterUnsigned (context, eRegisterKindDWARF, dwarf_pc, after_pc_value))
                 return false;
-                
         }
     }
     return true;
 }
 
-bool
-EmulateInstructionARM::IsInstructionConditional()
+uint32_t
+EmulateInstructionARM::GetInstructionCondition()
 {
     const uint32_t cond = CurrentCond (m_opcode.GetOpcode32());
-    return cond != 0xe && cond != 0xf && cond != UINT32_MAX;
+    if (cond == 0xe || cond == 0xf || cond == UINT32_MAX)
+        return UINT32_MAX;
+    return cond;
 }
 
 bool
 EmulateInstructionARM::TestEmulation (Stream *out_stream, ArchSpec &arch, OptionValueDictionary *test_data)
 {
     if (!test_data)
     {
         out_stream->Printf ("TestEmulation: Missing test data.\n");

source/Plugins/UnwindAssembly/InstEmulation/UnwindAssemblyInstEmulation.cpp

if (range.GetByteSize() > 0 &&
                 RegisterInfo pc_reg_info;
                 m_inst_emulator_ap->GetRegisterInfo (eRegisterKindGeneric, LLDB_REGNUM_GENERIC_PC, pc_reg_info);
 
                 // cache the return address register number (in whatever register numbering this UnwindPlan uses) for
                 // quick reference during instruction parsing.
                 RegisterInfo ra_reg_info;
                 m_inst_emulator_ap->GetRegisterInfo (eRegisterKindGeneric, LLDB_REGNUM_GENERIC_RA, ra_reg_info);
 
+                // The architecture dependent condition code of the last processed instruction
+                // (UINT32_MAX means unconditional).
+                uint32_t last_condition = UINT32_MAX;
+                lldb::addr_t condition_block_start_offset = 0;
+
                 for (size_t idx=0; idx<num_instructions; ++idx)
                 {
                     m_curr_row_modified = false;
                     m_forward_branch_offset = 0;
 
                     inst = inst_list.GetInstructionAtIndex (idx).get();
                     if (inst)
                     {
                         lldb::addr_t current_offset = inst->GetAddress().GetFileAddress() - base_addr;
                         auto it = saved_unwind_states.upper_bound(current_offset);
                         assert(it != saved_unwind_states.begin() && "Unwind row for the function entry missing");
                         --it; // Move it to the row corresponding to the current offset
 
                         // If the offset of m_curr_row don't match with the offset we see in saved_unwind_states
                         // then we have to update m_curr_row and m_register_values based on the saved values. It
                         // is happenning after we processed an epilogue and a return to caller instruction.
                         if (it->second.first->GetOffset() != m_curr_row->GetOffset())
                         {
                             UnwindPlan::Row *newrow = new UnwindPlan::Row;
                             *newrow = *it->second.first;
                             m_curr_row.reset(newrow);
-                            m_register_values = it->second.second;;
+                            m_register_values = it->second.second;
+                        }
+
+                        m_inst_emulator_ap->SetInstruction (inst->GetOpcode(), 
+                                                            inst->GetAddress(), 
+                                                            exe_ctx.GetTargetPtr());
+
+                        if (last_condition != m_inst_emulator_ap->GetInstructionCondition())
+                        {
+                            if (m_inst_emulator_ap->GetInstructionCondition() != UINT32_MAX &&
+                                saved_unwind_states.count(current_offset) == 0)
+                            {
+                                // If we don't have a saved row for the current offset then save our
+                                // current state because we will have to restore it after the
+                                // conditional block.
+                                auto new_row = std::make_shared<UnwindPlan::Row>(*m_curr_row.get());
+                                saved_unwind_states.insert({current_offset, {new_row, m_register_values}});
+                            }
+
+                            // If the last instruction was conditional with a different condition
+                            // then the then current condition then restore the condition.
+                            if (last_condition != UINT32_MAX)
+                            {
+                                const auto& saved_state = saved_unwind_states.at(condition_block_start_offset);
+                                m_curr_row = std::make_shared<UnwindPlan::Row>(*saved_state.first);
+                                m_curr_row->SetOffset(current_offset);
+                                m_register_values = saved_state.second;
+                                bool replace_existing = true; // The last instruction might already
+                                                              // created a row for this offset and
+                                                              // we want to overwrite it.
+                                unwind_plan.InsertRow(std::make_shared<UnwindPlan::Row>(*m_curr_row), replace_existing);
+                            }
+
+                            // We are starting a new conditional block at the catual offset
+                            condition_block_start_offset = current_offset;
                         }
 
                         if (log && log->GetVerbose ())
                         {
                             StreamString strm;
                             lldb_private::FormatEntity::Entry format;
                             FormatEntity::Parse("${frame.pc}: ", format);
                             inst->Dump(&strm, inst_list.GetMaxOpcocdeByteSize (), show_address, show_bytes, NULL, NULL, NULL, &format, 0);
                             log->PutCString (strm.GetData());
                         }
 
-                        m_inst_emulator_ap->SetInstruction (inst->GetOpcode(), 
-                                                            inst->GetAddress(), 
-                                                            exe_ctx.GetTargetPtr());
+                        last_condition = m_inst_emulator_ap->GetInstructionCondition();
 
                         m_inst_emulator_ap->EvaluateInstruction (eEmulateInstructionOptionIgnoreConditions);
 
                         // If the current instruction is a branch forward then save the current CFI information
                         // for the offset where we are branching.
                         if (m_forward_branch_offset != 0 && range.ContainsFileAddress(inst->GetAddress().GetFileAddress() + m_forward_branch_offset))
                         {
                             auto newrow = std::make_shared<UnwindPlan::Row>(*m_curr_row.get());
if (log && log->GetVerbose ())
         StreamString strm;
         strm.Printf ("UnwindAssemblyInstEmulation::WriteRegister (name = \"%s\", value = ", reg_info->name);
         reg_value.Dump(&strm, reg_info, false, false, eFormatDefault);
         strm.PutCString (", context = ");
         context.Dump(strm, instruction);
         log->PutCString(strm.GetData());
     }
 
-    if (!instruction->IsInstructionConditional())
-        SetRegisterValue (*reg_info, reg_value);
 
     switch (context.type)
     {
         case EmulateInstruction::eContextInvalid:
         case EmulateInstruction::eContextReadOpcode:
         case EmulateInstruction::eContextImmediate:
         case EmulateInstruction::eContextAdjustBaseRegister:
         case EmulateInstruction::eContextRegisterPlusOffset:
//            }
                 {
                     m_forward_branch_offset = context.info.signed_immediate;
                 }
             }
             break;
 
         case EmulateInstruction::eContextPopRegisterOffStack:
             {
-                if (!instruction->IsInstructionConditional())
-                {
-                    const uint32_t reg_num = reg_info->kinds[m_unwind_plan_ptr->GetRegisterKind()];
-                    const uint32_t generic_regnum = reg_info->kinds[eRegisterKindGeneric];
-                    if (reg_num != LLDB_INVALID_REGNUM && generic_regnum != LLDB_REGNUM_GENERIC_SP)
-                    {
-                        switch (context.info_type)
-                        {
-                            case EmulateInstruction::eInfoTypeAddress:
-                                if (m_pushed_regs.find(reg_num) != m_pushed_regs.end() &&
-                                    context.info.address == m_pushed_regs[reg_num])
-                                {
-                                    m_curr_row->SetRegisterLocationToSame(reg_num,
-                                                                          false /*must_replace*/);
-                                    m_curr_row_modified = true;
-                                }
-                                break;
-                            case EmulateInstruction::eInfoTypeISA:
-                                assert((generic_regnum == LLDB_REGNUM_GENERIC_PC ||
-                                        generic_regnum == LLDB_REGNUM_GENERIC_FLAGS) &&
-                                       "eInfoTypeISA used for poping a register other the the PC/FLAGS");
-                                if (generic_regnum != LLDB_REGNUM_GENERIC_FLAGS)
-                                {
-                                    m_curr_row->SetRegisterLocationToSame(reg_num,
-                                                                          false /*must_replace*/);
-                                    m_curr_row_modified = true;
-                                }
-                                break;
-                            default:
-                                assert(false && "unhandled case, add code to handle this!");
-                                break;
-                        }
-                    }
-                }
-            }
             break;
 
         case EmulateInstruction::eContextSetFramePointer:
-            if (!m_fp_is_cfa && !instruction->IsInstructionConditional())
+            if (!m_fp_is_cfa)
             {
                 m_fp_is_cfa = true;
                 m_cfa_reg_info = *reg_info;
                 const uint32_t cfa_reg_num = reg_info->kinds[m_unwind_plan_ptr->GetRegisterKind()];
                 assert (cfa_reg_num != LLDB_INVALID_REGNUM);
                 m_curr_row->GetCFAValue().SetIsRegisterPlusOffset(cfa_reg_num, m_initial_sp -
                         reg_value.GetAsUInt64());
                 m_curr_row_modified = true;
             }
             break;
 
         case EmulateInstruction::eContextAdjustStackPointer:
             // If we have created a frame using the frame pointer, don't follow
             // subsequent adjustments to the stack pointer.
-            if (!m_fp_is_cfa && !instruction->IsInstructionConditional())
+            if (!m_fp_is_cfa)
             {
                 m_curr_row->GetCFAValue().SetIsRegisterPlusOffset(
                         m_curr_row->GetCFAValue().GetRegisterNumber(),
                         m_initial_sp - reg_value.GetAsUInt64());
                 m_curr_row_modified = true;
             }
             break;
     }
     return true;
 }
 
 

source/Symbol/UnwindPlan.cpp

 {
     if (m_row_list.empty() || m_row_list.back()->GetOffset() != row_sp->GetOffset())
         m_row_list.push_back(row_sp);
     else
         m_row_list.back() = row_sp;
 }
 
 void
-UnwindPlan::InsertRow (const UnwindPlan::RowSP &row_sp)
+UnwindPlan::InsertRow (const UnwindPlan::RowSP &row_sp, bool replace_existing)
 {
     collection::iterator it = m_row_list.begin();
     while (it != m_row_list.end()) {
         RowSP row = *it;
         if (row->GetOffset() >= row_sp->GetOffset())
             break;
         it++;
     }
     if (it == m_row_list.end() || (*it)->GetOffset() != row_sp->GetOffset())
         m_row_list.insert(it, row_sp);
+    else if (replace_existing)
+        *it = row_sp;
 }
 
 UnwindPlan::RowSP
 UnwindPlan::GetRowForFunctionOffset (int offset) const
 {
     RowSP row;
     if (!m_row_list.empty())
     {