Skip instruction implementation

[astrelsky]

I've been struggling to implement skip instructions for the RL78 for quite some time now. It seems the best way to go about it is to use a similar approach to what is used for ARM. However, because any instruction can be skipped, this makes all branches, calls and returns conditional and causes the decompiler to fail 90% of the time. This is usually due to exceeding the maximum instruction count.

An alternative is to use local context and this actually works great, until it doesn't. The problem here occurs when an instruction which follows a skip instruction is branched into. Since there is a difference in instruction context disassembly "fails" and the decompiler will usually start puking BADSPACEBASE everywhere.

I think the best way, other than built in support for skip instructions, would be to use the first approach with some way to tell the flow analysis and the decompiler that a branch/call/return is only conditional if it has been proceeded by a skip instruction. Any ideas on how to do this that won't suffer from the same issues when using context?

[astrelsky]

I think I just figured out a solution. I will use pcode injection for the skip instructions because I can get the next instruction and its lenses to inject the appropriate pcode to skip it from the java api.

[astrelsky]

So I setup the pcode inject library and the injection. This is what I have.

	private String doGetCondition(char c) {
		switch (c) {
			case 'C':
				return "PSW[0,1]";
			case 'N':
				return "!";
			case 'Z':
				return "PSW[6,1]";
			case 'H':
				return "(PSW[6,1] | PSW[0,1])";
		}
		throw new AssertException();
	}

	private String getCondition(Program program, InjectContext con) {
		Instruction inst = program.getListing().getInstructionAt(con.baseAddr);
		String mnemonic = inst.getMnemonicString();
		try {
			String cond = doGetCondition(mnemonic.charAt(2));
			if (cond.equals("!")) {
				cond += doGetCondition(mnemonic.charAt(3));
			}
			return "if (" + cond + ") ";
		} catch (AssertException | IndexOutOfBoundsException e) {
			Msg.showError(this, null, mnemonic, e);
			throw e;
		}
	}

	private String getJumpTarget(Program program, InjectContext con) {
		Instruction inst = program.getListing().getInstructionAt(con.nextAddr);
		if (inst == null) {
			return "";
		}
		return "goto [inst_next+"+Integer.toString(inst.getLength())+":3];";
	}

	@Override
	public PcodeOp[] getPcode(Program program, InjectContext con) {
		SleighLanguage l = con.language;
		PcodeParser parser = new PcodeParser(l, l.getUniqueBase());
		String target = getJumpTarget(program, con);
		String cond = getCondition(program, con);
		String sourceName = getSource();
		ConstructTpl constructTpl = parser.compilePcode(cond + target, sourceName, 1);
		SleighParserContext protoContext =
			new SleighParserContext(con.baseAddr, con.nextAddr, con.refAddr, con.callAddr);
		ParserWalker walker = new ParserWalker(protoContext);
		PcodeEmitObjects emit = new PcodeEmitObjects(walker);
		try {
			emit.build(constructTpl, -1);
		} catch (Exception e) {
			throw new AssertException(e);
		}
		return emit.getPcodeOp();
	}

But this ends up resulting in the following

2022-05-12 20:09:23 ERROR (PcodeCompile) C:\Users\astre\Documents\ghidra_10.2_DEV\Ghidra\Extensions\RL78_sleigh\data\languages\rl78.cspec:1: invalid dynamic target used in goto destination  
2022-05-12 20:09:23 ERROR (DecompileCallback) Decompiling ram:01501a, pcode inject error at ram:015046: Unexpected Error: Semantics for this instruction are not implemented ghidra.util.exception.AssertException: Unexpected Error: Semantics for this instruction are not implemented

Anyone have any ideas? I don't see why this can't be done.

[astrelsky]

@caheckman or @ghidra1 any thoughts on why the following would result in Low-level Error: Bad relative branch at instruction : (ram,0x01938c)? This seems like it should be pretty trivial.

public class InjectSkipPayload extends InjectPayloadCallother {

	public InjectSkipPayload(String sourceName, SleighLanguage language) {
		super(sourceName);
	}

	@Override
	public PcodeOp[] getPcode(Program program, InjectContext con) {
		Instruction inst = program.getListing().getInstructionAt(con.nextAddr).getNext();
		Varnode[] in = {new Varnode(inst.getAddress(), 3)};
		PcodeOp[] p = {new PcodeOp(con.baseAddr, -1, PcodeOp.BRANCH, in)};
		return p;
	}

}

The decompilation dump has the following for the injection.

<injectdebug>
<inject name="SKIP" type="2">
  <addr space="ram" offset="0x1938c"/>
  <payload><![CDATA[
<inst offset="2"><op code="4"><seqnum space="ram" offset="0x1938c"/><void/><addr space="ram" offset="0x19391" size="3"/></op></inst>

]]></payload>
</inject>
</injectdebug>

The instruction containing SKIP is implemented as follows

:SKZ is opcode=0x61; opcode=0xE8 {
    if $(Z) goto <skip>;
    goto <end>;
    <skip>
    SKIP();
    <end>
}

[astrelsky]

Well, this is extremely gross but here is a work around. Having to put up with the "removing unreachable block" warnings and error bookmarks everywhere is much much better than not having it implemented at all. Luckily the bookmarks from disassembly "error" isn't a problem because the disassembly by flow to the next instruction occurs first. The pcodeop getNextInstructionLength is implemented to do exactly what it's name implies via pcode injection.

define pcodeop getNextInstructionLength;

SKIP1: loc is epsilon [ loc = inst_next + 1; ] {
    export *[ram]:3 loc;
}

SKIP2: loc is epsilon [ loc = inst_next + 2; ] {
    export *[ram]:3 loc;
}

SKIP3: loc is epsilon [ loc = inst_next + 3; ] {
    export *[ram]:3 loc;
}

#
# Table 30/30
#

# SKC
:SKC is SKIP1 & SKIP2 & SKIP3 & opcode=0x61; opcode=0xC8 {
    len:2 = getNextInstructionLength();
    if ($(CY)) goto <skip>;
    goto inst_next;
    <skip>
    if (len == 1) goto SKIP1;
    if (len == 2) goto SKIP2;
    if (len == 3) goto SKIP3;
}

[astrelsky]

I could not get it to work. Order definitely matters though as moving any :^instruction ... to the top causes every instruction to fail to be parsed. The reason it fails is it looks at possible matches, checks the first one which is :^instruction ... sees it matches, takes it, it builds instruction, repeat until maximum depth reached. No matter what order I put it in or how I tweaked it, it wouldn't cooperate.

Edit: I could probably use another bit in the context register to prevent that.

[astrelsky]

So changing it to this did work. However, it yielded the same "Multiple flows produced inconsistent instruction prototype ... possibly due to inconsistent context"

These are defined first;

# PREFIX
:^instruction is ctx1=0 & skip_check=1 & instruction [ctx1=1;] {
    if (skipflag) goto inst_next;
    build instruction;
}

# PREFIX
:^instruction is ctx1=0 & skip_check=0 & instruction [ctx1=1;] {
    build instruction;
}

These are defined later:

# SKC
:SKC is opcode=0x61; opcode=0xC8 [skip_check = 1; globalset(inst_next, skip_check);] {
    skipflag = $(CY);
}

# SKNC
:SKNC is opcode=0x61; opcode=0xD8 [skip_check = 1; globalset(inst_next, skip_check);] {
    skipflag = !$(CY);
}

# SKZ
:SKZ is opcode=0x61; opcode=0xE8 [skip_check = 1; globalset(inst_next, skip_check);] {
    skipflag = $(Z);
}

# SKNZ
:SKNZ is opcode=0x61; opcode=0xF8 [skip_check = 1; globalset(inst_next, skip_check);] {
    skipflag = !$(Z);
}

# SKH
:SKH is opcode=0x61; opcode=0xE3 [skip_check = 1; globalset(inst_next, skip_check);] {
    skipflag = ($(Z) | $(CY));
}

# SKNH
:SKNH is opcode=0x61; opcode=0xF3 [skip_check = 1; globalset(inst_next, skip_check);] {
    skipflag = (!($(Z) | $(CY)));
}

# PREFIX
:^instruction is skip_check=0 & es_prefix=0 & opcode=0x11; epsilon ... & instruction [ es_prefix=1; ] {
    build instruction;
}

# PREFIX
:^instruction is skip_check=1 & es_prefix=0 & opcode=0x11; epsilon ... & instruction [ es_prefix=1; ] {
    if (skipflag) goto inst_next;
    build instruction;
}

[GhidorahRex]

Do you have all the context bits set as noflow?

[astrelsky]

Do you have all the context bits set as noflow?

The ones in use are set as noflow.

[ghidra1]

Context definition (flow vs no-flow) is not the issue - it is the differing context for multiple flows leading to the same instruction. (see comment below)
When differing context occurs this means you are sensitive to the order of disassembly and flow processing which must be avoided since the resulting static pcode would differ. That is why you must rely on fake registers and dynamic behavior instead of static context to control skipping behavior - or rely on delay slots if they make sense, although they too have their limitations.

[ghidra1]

Have you looked at the PA-RISC approach or considered the use of delays slots (you are allowed to branch into a delay slot)? As you discovered context is dicey for this type of skipping logic and should probably be avoided due to the dynamic nature (an instruction may be skipped or not-skipped depending on flow).

[astrelsky]

I am finding some things I missed so will follow-up with another patch when done. In addition the decompiler has not yet been changed (C++), although it will probably work OK since it processes pcode and not pcode templates. I am working on the C++ code now.

I suspect the decompiler will work without a problem as long as the c++ sleigh portion is done. The condition branch target would already be computed in the pcode cbranch op once it reaches the rule portion of the decompiler. (This is super rough because I'm going off memory)

[ghidra1]

I have attached an update patch file which includes changes to C++ code. I have not tested the C++ change but it was pretty straight forward. You may notice places in the code where inst_next2 indicates "not supported" (e.g., injection, stand-alone decompiler, etc.). These will not impact your use with Ghidra and may be improved upon in the future.

inst_next2_patch2.txt

Let me know how it goes...

You will need to build both java sleigh parser and decompiler C++ code:
gradle generateGrammarSource Decompiler:buildNatives

[astrelsky]

It seems to work good. The only problem I'm seeing is that the disassembler isn't considering the flow when skipping an unconditional branch.

SKZ
BR LAB_xyz
// instructions below are not disassembled but the ones at LAB_xyz are

I do see the following error in the decompiler on occasion. I'm not sure if it is due to these changes or if it is due to the recent protocol changes.

Pcode: Decoding error: Expecting <doc> but did not scan an element

[ghidra1]

Here is an updated patch where hopefully the disassembly issue is addressed
inst_next2_patch4.txt

[astrelsky]

It looks like that did the trick.

[ghidra1]

Sleigh support for inst_next2 has been merged into master for 10.2 release.
(See ca80be4)