Failure to decompile MIPS ("Instruction does not dominate all uses!")

[speachy]

This happens using the latest retdec git code (d57764ab as I write this).

Executable itself:

Input file               : /tmp/hiby_player
File format              : ELF
File class               : 32-bit
File type                : Executable file
Architecture             : MIPS (MIPS I Architecture)
Endianness               : Little endian
Entry point address      : 0x414e30
Entry point offset       : 0x14e30
Entry point section name : .text
Entry point section index: 13
Bytes on entry point     : 72001c3c602b9c2721f800004100043c804d84240000a58f0400a627f8ff012424e8a103e0ffbd276500073ce072e7246500
Detected tool            : GCC (4.7.2) (compiler), .comment section heuristic
Detected tool            : GCC (4.6) (compiler), .comment section heuristic
Detected tool            : GCC (4.5.4) (compiler), 60 from 183 significant nibbles (32.7869%)

Here's where it barfs:

Running phase: Initialization ( 0.01s )
Running phase: LLVM ( 0.02s )
Running phase: Providers initialization ( 0.02s )
Running phase: Input binary to LLVM IR decoding ( 0.13s )
Running phase: LLVM ( 8.82s )
Instruction does not dominate all uses!
  %191 = icmp eq i32 %189, %190
  br i1 %191, label %dec_label_pc_42c578, label %dec_label_pc_42c3c8
LLVM ERROR: Broken function found, compilation aborted!
Error: Decompilation to LLVM IR failed

The executable targets an Ingenic X1000 (mips32r2 presumably with their Xburst instructions). I can supply the executable or whatever intermediate info is needed; just let me know.

[s3rvac]

Thank you for the report. Can you please attach the input executable that you are trying to decompile so we can try to reproduce the issue?

[speachy]

hiby_player_mips_elf.zip

Here you go.

[s3rvac]

Thanks! I can confirm that retdec-bin2llvmir fails with the reported error when decompiling the attached executable. @PeterMatula, can you investigate this? It seems that we generate an invalid LLVM IR during decoding as this error is produced by the -verify pass after -decoder. The issue seems to be in dec_label_pc_42c3c4, which contains the following instruction:

br i1 %191, label %dec_label_pc_42c578, label %dec_label_pc_42c3c8

However, it seems that you can get to that instruction without going through a definition of %191.

[nihilus]

Xburst is not to be confused with mips32, since it is "compatible" but afaik it also has got some homebrewed instructions.

[speachy]

xburst is stock mips32r1 (or mips32r2) plus proprietary DSP/SIMD extensions. I do not know if the executable in question utilizes anything that isn't bog-standard mips32.

But be that as it may, one would think if retdec ran into an unknown (ie xburst-specific) instruction it would fail to decode the instruction and complain loudly at that point, rather than silently generate illegal LLVM IR? Either way, it's a bug..

[PeterMatula]

Delay slots - of course, what else would it be? This is a real example of a theoretical flaw in the way we handle delay slots. I knew this could happen, but hoped it won't - and so far it did not. I will try to find a more robust solution, but who knows what else will break - those things (delay slots) are a real pain in the backside.

[nihilus]

Yupp, they are tricky to reconstruct. Look at the snowman code and how it does handle them.

[PeterMatula]

Some time ago I designed this solution to MIPS delay slots, but then nearly lost it and stopped working on it. Uploading the picture here for future reference:

[seviezhou]

The bug in this issue is caused by the fact that the delay slot is the jump target of later instructions. We should insert delay slot just after AsmInstruction instead of before branchCall. For typical delay slot, I think we can copy the delay slot instruction before and after the branch instruction.

Something like this:

void Decoder::handleDelaySlotTypical(
        common::Address& addr,
        capstone2llvmir::Capstone2LlvmIrTranslator::TranslationResultOne& res,
        ByteData& bytes,
        llvm::IRBuilder<>& irb)
{
    if (!_c2l->hasDelaySlotTypical(res.capstoneInsn->id))
    {
        return;
    }

    if (!res.branchCall)
    {
        return;
    }

    assert(res.branchCall);
    assert(_c2l->getDelaySlot(res.capstoneInsn->id));
    assert(_c2l->getDelaySlot(res.capstoneInsn->id) == 1);

    AsmInstruction ai(res.branchCall);
    if (ai.isInvalid())
    {
        return;
    }

    auto oldAddr = addr;
    ByteData oldBd = bytes;
    auto* oldIp = res.branchCall->getParent()->getTerminator();
    irb.SetInsertPoint(ai.getLlvmToAsmInstruction());

    std::size_t sz = _c2l->getDelaySlot(res.capstoneInsn->id);
    for (std::size_t i = 0; i < sz; ++i)
    {
        auto r = translate(bytes, addr, irb);
        if (r.failed() || r.llvmInsn == nullptr)
        {
            break;
        }

        _llvm2capstone->emplace(r.llvmInsn, r.capstoneInsn);
    }

    // restore
    addr = oldAddr;
    bytes = oldBd;
    irb.SetInsertPoint(oldIp);
}

This might result in many blocks without predecessors, because the delay slot in the original place is not executed after the branchCall. I think this is safer to do this, because there are two situations:

1. The delay slot is not the jump target of any other instructions. Then we have a copied delay slot before the branchCall, and optimization after decoding can eliminate such dead code.
2. The delay slot is the jump target of other instructions. Then the original delay slot has one predecessor and works as it is.