SSA dead code elimination

[mrphrazer]

Hi!

In IRCFGSimplifierSSA, the propagations seem to work fine. However, the results of do_dead_simp_ssa seem strange to me.

Given the following code, the remaining graph in after_dead_code.dot is a small basic block.

from miasm.analysis.machine import Machine
from miasm.analysis.simplifier import IRCFGSimplifierSSA

def write_graph(output_file, ira_cfg):
    open(output_file, "wb").write(ira_cfg.dot())

code = "554889e5897dfc8975f88b55fc8b45f801d03d390500007507B801000000EB05B8000000005dc3".decode("hex")

architecture = "x86_64"
m = Machine(architecture)
mdis = m.dis_engine(code)
ira = m.ira(mdis.loc_db)
asm_cfg = mdis.dis_multiblock(0)
ira_cfg = ira.new_ircfg_from_asmcfg(asm_cfg)
head = mdis.loc_db.get_offset_location(0)

simplifier = IRCFGSimplifierSSA(ira)
ssa = simplifier.ircfg_to_ssa(ira_cfg, head)

write_graph("before_simp.dot", ira_cfg)

modified = True
while modified:
    modified = False
    modified |= simplifier.simplify_ssa(ssa, head)
    modified |= simplifier.do_propagate_int(ssa, head)
    modified |= simplifier.do_propagate_mem(ssa, head)
    modified |= simplifier.do_propagate_expr(ssa, head)

write_graph("after_propagation.dot", ira_cfg)

modified |= simplifier.do_dead_simp_ssa(ssa, head)

write_graph("after_dead_code.dot", ira_cfg)

Do you have any idea what's going on?

[serpilliere]

Hi @mrphrazer !

Yep here is the exaplaination:

• first of all, dead_simp knows which reg is to keep by using the 'abi' in the ir_arch object using get_out_regs, which is call on each leaf block of the ir_cfg
• when you do SSA transformation, the last RAX is (for example) translated in RAX.12
• So when you do dead_simp_ssa, the get_out_regs does not recognize RAX.12 as a register to keep
• it's deleted
• so the phi ancestor are deleted
• the test and conditional jump branches are useless, so removed.
• we obtain the given graph.

In full.py here is the steps which are done:

• first, we have to be sure that the registers of get_out_regs are assigned in the leaves blocks.this is done with:

    # Add dummy dependency to uncover out regs assignment
    for loc in ircfg_a.leaves():
        irblock = ircfg_a.blocks.get(loc)
        if irblock is None:
            continue
        regs = {}
        for reg in ir_arch_a.get_out_regs(irblock):
            regs[reg] = reg
        assignblks = list(irblock)
        new_assiblk = AssignBlock(regs, assignblks[-1].instr)
        assignblks.append(new_assiblk)
        new_irblock = IRBlock(irblock.loc_key, assignblks)
        ircfg_a.blocks[loc] = new_irblock

Now we are sure that we have at the leaves blocks, something like:

...
RAX = RAX
RSP = RSP

Now, when we will translate in SSA, this gives something as:

...
RAX.12 = RAX.11
RSP.20 = RSP.19

Now, we have to use a modified ir_arch_a class, as we have to recognize new registers in get_out_regs. This is done in full.py as:

    class IRAOutRegs(ira):
        def get_out_regs(self, block):
            regs_todo = super(self.__class__, self).get_out_regs(block)
            out = {}
            for assignblk in block:
                for dst in assignblk:
                    reg = self.ssa_var.get(dst, None)
                    if reg is None:
                        continue
                    if reg in regs_todo:
                        out[reg] = dst
            return set(viewvalues(out))

Here, we keep classical registers, plus ssa registers linked to original registers found in the original get_out_regs

So dead_simp_ssa will be ok!

So your come becomes:

from miasm.analysis.machine import Machine
from miasm.analysis.simplifier import IRCFGSimplifierSSA
from miasm.ir.ir import AssignBlock, IRBlock
from pdb import pm

def write_graph(output_file, ira_cfg):
    open(output_file, "wb").write(ira_cfg.dot())

code = "554889e5897dfc8975f88b55fc8b45f801d03d390500007507B801000000EB05B8000000005dc3".decode("hex")

architecture = "x86_64"
m = Machine(architecture)
mdis = m.dis_engine(code)

ira_orig = m.ira(mdis.loc_db)

class IRAOutRegs(m.ira):
    def get_out_regs(self, block):
        regs_todo = super(self.__class__, self).get_out_regs(block)
        out = {}
        for assignblk in block:
            for dst in assignblk:
                reg = self.ssa_var.get(dst, None)
                if reg is None:
                    continue
                if reg in regs_todo:
                    out[reg] = dst
        return set(out.values())




ira = IRAOutRegs(mdis.loc_db)
asm_cfg = mdis.dis_multiblock(0)
ira_cfg = ira.new_ircfg_from_asmcfg(asm_cfg)


# Add dummy dependency to uncover out regs assignment
for loc in ira_cfg.leaves():
    irblock = ira_cfg.blocks.get(loc)
    if irblock is None:
        continue
    regs = {}
    for reg in ira_orig.get_out_regs(irblock):
        regs[reg] = reg
    assignblks = list(irblock)
    new_assiblk = AssignBlock(regs, assignblks[-1].instr)
    assignblks.append(new_assiblk)
    new_irblock = IRBlock(irblock.loc_key, assignblks)
    ira_cfg.blocks[loc] = new_irblock



head = mdis.loc_db.get_offset_location(0)


write_graph("before_simp.dot", ira_cfg)

simplifier = IRCFGSimplifierSSA(ira)
simplifier.simplify(ira_cfg, head)
write_graph("after_dead_code.dot", ira_cfg)

which gives:

Ok. after reading my own explanations, I think I must include all those mechanism by default somewhere.

Maybe in the simplifier ?

Does it answer to your questions @mrphrazer ?

[mrphrazer]

Hi @serpilliere!

Yeah, this absolutely makes sense. Thanks! I also think that it is reasonable to include it somewhere around the simplifier (or, at least make it optional).

[su-vikas]

@serpilliere I would also recommend to include some explanation in full.py on why you are using the code for get_out_regs . Else, it feels some magic code, which probably is not needed in a given use case, and in the end omitted :).

[commial]

Hi @mrphrazer, nice to hear from you again =]

Another way to do the trick is to ask to ira.get_out_regs the registers to save, and then add at leaves bottom:

@[SAVE_EAX] = EAX
@[SAVE_ESP] = ESP
...

You can then perform Miasm simplifications / optimizations, as a memory access should never be removed (or just for very special cases). Then, when done (in SSA form or after out-of-ssa), you can replace back @[SAVE_EAX] = Y by EAX = Y.

I agree with you, we should add a mechanism to perform one of this method somewhere, as it appears with the time that we often needed it.

[serpilliere]

Yep @su-vikas : you are definitely right guys. We will try doing something easy to use and configurable here (and documented :smile: )

[dwuid]

Regarding https://github.com/cea-sec/miasm/issues/1000#issuecomment-471745354: Note that this propagates program semantics (RSP + 8) into the spurious (fake) assignments added earlier (formerly, RSP.3 = RSP.2).

I am not sure if this is intended? The computation now lies beyond the assignment to IRDst, and I am not sure whether there's an invariant in miasm that assumes the assignment to IRDst always being the last statement in a block.

In any case, I opened a related issue #1019 and would love to get some input! :)

[serpilliere]

@dwuid: no, Miasm does not assume the IRDst is in the last assignment block of the IR block. One example is the Mips architecture. The IRDst is here in the before last assignment block of the IR block. Most algorithms get the IRDst value of an IRBlock using irblock.dst which is the "prefered" way to do this. I don't say every implemented algorithms are ok, but if you have a counter example, feel free to open an issue about this: it has to be fixed!

[mrphrazer]

I don't say every implemented algorithms are ok, but if you have a counter example, feel free to open an issue about this: it has to be fixed!

Just to be sure: Isn't exactly this issue a counter example? Since, in the last block, IRDst is set before the return value is stored in RAX?

[serpilliere]

Ok I was not clear here, let me rephrase: If you found an algorithm currently implemented in Miasm which makes the assumption that IRDst is always at the last AssignBlock of the IRBlock, we must open an issue!

Note: I have updated the PR #1025 which is still not finished. I will work also on adding regressions tests because the simplifier becomes bigger and bigger. Some are based on #954 and #955, others are inspired from discussions with a lot of you (@MapleLeaf-X, @su-vikas , @hax0kartik, @dwuid, @commial , and I surely have forgotten a lot ...). I will try to reflect each case we discuss but it may take some time :smile:

[commial]

As a side note: assigning to IRDst doesn't immediately modify the control flow (unlike it could be when assigning on PC, EIP, ...). The IRDst value is used at the end of the IRBlock.

So assigning to IRDst then to RAX is completely right. It could even be switch, if IRDst doesn't depend on RAX.

[serpilliere]

The PR #1025 will not be merged, as it has been replaced by #1168