Skip to content

Commit 7b16443

Browse files
zznopzznop
committed
Coalesce Thumb IT blocks with trailing conditional branches
1 parent f5ebdef commit 7b16443

2 files changed

Lines changed: 222 additions & 72 deletions

File tree

‎arch/armv7/test_lift.py‎

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -766,6 +766,8 @@ def vmlal_expected(size, unsigned):
766766
info_test_cases = [
767767
# ldm.w r0!, {r1, pc}
768768
('T', b'\xb0\xe8\x02\x80', 4, [('UnresolvedBranch', 0)], True),
769+
# it eq; bleq 0x8; beq 0xc -- the call may clobber flags, so do not coalesce the following branch
770+
('T', b'\x08\xbf\x00\xf0\x04\xf8\x06\xd0', 6, [('CallDestination', 14)], False),
769771
]
770772

771773
import re

‎arch/armv7/thumb2_disasm/arch_thumb2.cpp‎

Lines changed: 220 additions & 72 deletions
Original file line numberDiff line numberDiff line change
@@ -20,6 +20,55 @@ using namespace std;
2020
#define snprintf _snprintf
2121
#endif
2222

23+
static bool IsConditionalBranch(const decomp_result& decomp)
24+
{
25+
return (decomp.mnem == ARMV7_B) && (decomp.format->operationFlags & INSTR_FORMAT_FLAG_CONDITIONAL)
26+
&& (decomp.fields[FIELD_cond] != COND_AL);
27+
}
28+
29+
static bool IsSameOrInvertedCondition(uint32_t lhs, uint32_t rhs)
30+
{
31+
return (lhs == rhs) || ((lhs < COND_AL) && (rhs < COND_AL) && ((lhs ^ 1) == rhs));
32+
}
33+
34+
static bool ThumbITInstructionWritesAPSR(const decomp_result& decomp)
35+
{
36+
switch (decomp.mnem)
37+
{
38+
case ARMV7_CMN:
39+
case ARMV7_CMP:
40+
case ARMV7_TEQ:
41+
case ARMV7_TST:
42+
return true;
43+
default:
44+
return false;
45+
}
46+
}
47+
48+
static uint32_t GetConditionalBranchTarget(const decomp_result& decomp)
49+
{
50+
return decomp.pc + decomp.fields[decomp.format->operands[0].field0];
51+
}
52+
53+
static void EmitDirectThumbJump(Architecture* arch, LowLevelILFunction& il, uint32_t target)
54+
{
55+
BNLowLevelILLabel* label = il.GetLabelForAddress(arch, target);
56+
if (label)
57+
il.AddInstruction(il.Goto(*label));
58+
else
59+
il.AddInstruction(il.Jump(il.ConstPointer(4, target)));
60+
}
61+
62+
struct ThumbITSlot
63+
{
64+
uint32_t addr = 0;
65+
decomp_result decomp = {};
66+
bool thenSlot = false;
67+
bool lift = false;
68+
bool directBranch = false;
69+
uint32_t branchTarget = 0;
70+
};
71+
2372
static Ref<Enumeration> get_msr_op_enum()
2473
{
2574
EnumerationBuilder builder;
@@ -167,7 +216,9 @@ class Thumb2Architecture: public ArmCommonArchitecture
167216

168217
virtual size_t GetMaxInstructionLength() const override
169218
{
170-
return 18; // IT blocks can have up to four following associated instructions
219+
// IT blocks can have up to four following associated instructions, and
220+
// may be coalesced with a following conditional branch.
221+
return 22;
171222
}
172223

173224
virtual size_t GetInstructionAlignment() const override
@@ -232,6 +283,8 @@ class Thumb2Architecture: public ArmCommonArchitecture
232283
bool falseBranched = false;
233284
bool trueReturned = false;
234285
bool falseReturned = false;
286+
bool trueWroteFlags = false;
287+
bool falseWroteFlags = false;
235288

236289
uint64_t trueBranchTargetAddr = 0;
237290
uint64_t falseBranchTargetAddr = 0;
@@ -240,56 +293,96 @@ class Thumb2Architecture: public ArmCommonArchitecture
240293
{
241294
bool isTrue = (i == 0) || (((mask >> (4 - i)) & 1) == (cond & 1));
242295

243-
InstructionInfo innerResult;
244-
if (!GetInstructionInfo(data + offset, addr + offset, maxLen - offset, innerResult))
296+
if (offset >= maxLen || (maxLen - offset) < 2)
297+
break;
298+
299+
decomp_result innerDecomp;
300+
size_t remainingLen = maxLen - offset;
301+
bool decoded = populateDecomposeRequest(&request, data + offset, remainingLen, addr + offset,
302+
IFTHEN_YES, ((i + 1) >= instrCount) ? IFTHENLAST_YES : IFTHENLAST_NO)
303+
&& (thumb_decompose(&request, &innerDecomp) == STATUS_OK)
304+
&& !(innerDecomp.status & STATUS_UNDEFINED) && innerDecomp.format;
305+
if (!decoded)
245306
break;
246-
if ((offset + innerResult.length) > maxLen)
307+
size_t innerLen = innerDecomp.instrSize / 8;
308+
if ((innerLen == 0) || (innerLen > remainingLen))
247309
break;
248310

249311
bool& terminated = isTrue ? trueTerminated : falseTerminated;
250312
bool& branched = isTrue ? trueBranched : falseBranched;
251313
bool& returned = isTrue ? trueReturned : falseReturned;
314+
bool& wroteFlags = isTrue ? trueWroteFlags : falseWroteFlags;
252315
uint64_t& branchTarget = isTrue ? trueBranchTargetAddr : falseBranchTargetAddr;
253316

254317
// Only process if the conditional branch we're following isn't terminated
255318
// Otherwise, just track if the arch is switching and the offset
256319
if (!terminated)
257320
{
258-
for (size_t j = 0; j < innerResult.branchCount; j++)
321+
wroteFlags |= ThumbITInstructionWritesAPSR(innerDecomp);
322+
323+
InstructionInfo innerResult;
324+
if (GetInstructionInfo(data + offset, addr + offset, remainingLen, innerResult))
259325
{
260-
switch (innerResult.branchType[j])
326+
for (size_t j = 0; j < innerResult.branchCount; j++)
261327
{
262-
case UnconditionalBranch:
263-
case TrueBranch:
264-
case FalseBranch:
265-
branched = true;
266-
terminated = true;
267-
branchTarget = innerResult.branchTarget[j];
268-
break;
269-
case FunctionReturn:
270-
returned = true;
271-
terminated = true;
272-
break;
273-
case CallDestination:
274-
result.AddBranch(CallDestination, innerResult.branchTarget[j],
275-
innerResult.branchArch[j] ? m_armArch : this);
276-
break;
277-
case UnresolvedBranch:
278-
case IndirectBranch:
279-
case ExceptionBranch:
280-
// We don't know the branch target so just set terminated
281-
terminated = true;
282-
break;
283-
default:
284-
break;
328+
switch (innerResult.branchType[j])
329+
{
330+
case UnconditionalBranch:
331+
case TrueBranch:
332+
case FalseBranch:
333+
branched = true;
334+
terminated = true;
335+
branchTarget = innerResult.branchTarget[j];
336+
break;
337+
case FunctionReturn:
338+
returned = true;
339+
terminated = true;
340+
break;
341+
case CallDestination:
342+
result.AddBranch(CallDestination, innerResult.branchTarget[j],
343+
innerResult.branchArch[j] ? m_armArch : this);
344+
wroteFlags = true;
345+
break;
346+
case UnresolvedBranch:
347+
case IndirectBranch:
348+
case ExceptionBranch:
349+
// We don't know the branch target so just set terminated
350+
terminated = true;
351+
break;
352+
default:
353+
break;
354+
}
285355
}
356+
357+
if (innerResult.archTransitionByTargetAddr)
358+
result.archTransitionByTargetAddr = true;
286359
}
287360
}
288361

289-
if (innerResult.archTransitionByTargetAddr)
290-
result.archTransitionByTargetAddr = true;
362+
offset += innerLen;
363+
}
364+
365+
decomp_result branchDecomp;
366+
if ((offset < maxLen) && ((maxLen - offset) >= 2)
367+
&& populateDecomposeRequest(&request, data + offset, maxLen - offset, addr + offset, IFTHEN_NO, IFTHENLAST_NO)
368+
&& (thumb_decompose(&request, &branchDecomp) == STATUS_OK)
369+
&& ((offset + (branchDecomp.instrSize / 8)) <= maxLen)
370+
&& !(branchDecomp.status & STATUS_UNDEFINED) && branchDecomp.format && IsConditionalBranch(branchDecomp)
371+
&& IsSameOrInvertedCondition(branchDecomp.fields[FIELD_cond], cond))
372+
{
373+
bool branchOnTrue = branchDecomp.fields[FIELD_cond] == cond;
374+
bool& terminated = branchOnTrue ? trueTerminated : falseTerminated;
375+
bool& branched = branchOnTrue ? trueBranched : falseBranched;
376+
bool& wroteFlags = branchOnTrue ? trueWroteFlags : falseWroteFlags;
377+
uint64_t& branchTarget = branchOnTrue ? trueBranchTargetAddr : falseBranchTargetAddr;
291378

292-
offset += innerResult.length;
379+
if (!terminated && !wroteFlags)
380+
{
381+
branched = true;
382+
terminated = true;
383+
branchTarget = GetConditionalBranchTarget(branchDecomp);
384+
offset += branchDecomp.instrSize / 8;
385+
}
293386
}
294387

295388
result.length = offset;
@@ -2787,82 +2880,137 @@ class Thumb2Architecture: public ArmCommonArchitecture
27872880
uint32_t mask = decomp.fields[FIELD_mask];
27882881
uint32_t cond = decomp.fields[FIELD_firstcond];
27892882

2790-
// Calculate number of instructions
27912883
size_t instrCount;
2792-
if (decomp.fields[FIELD_mask] & 1)
2884+
if (mask & 1)
27932885
instrCount = 4;
2794-
else if (decomp.fields[FIELD_mask] & 2)
2886+
else if (mask & 2)
27952887
instrCount = 3;
2796-
else if (decomp.fields[FIELD_mask] & 4)
2888+
else if (mask & 4)
27972889
instrCount = 2;
27982890
else
27992891
instrCount = 1;
28002892

2801-
// decompose all instructions in the if-then block
2802-
vector<uint32_t> addrsTrue, addrsFalse;
2803-
vector<decomp_result> decompsTrue, decompsFalse;
2893+
// Decompose all instructions in the IT block and keep their original
2894+
// mask slot. A path may skip later slots once it has branched/returned.
2895+
vector<ThumbITSlot> slots;
2896+
bool pathTerminated[2] = {false, false};
2897+
bool pathHasBody[2] = {false, false};
2898+
bool pathWroteFlags[2] = {false, false};
28042899

28052900
for (size_t i = 0; i < instrCount; i++)
28062901
{
28072902
if (offset >= len || (len - offset) < 2)
28082903
return false;
28092904

2810-
bool isTrue = (i == 0) || (((mask >> (4 - i)) & 1) == (cond & 1));
2905+
bool thenSlot = (i == 0) || (((mask >> (4 - i)) & 1) == (cond & 1));
2906+
size_t stateIdx = thenSlot ? 0 : 1;
28112907
size_t remainingLen = len - offset;
28122908

2813-
if (!populateDecomposeRequest(&request, data+offset, remainingLen, addr+offset,
2814-
IFTHEN_YES, ((i + 1) >= instrCount) ? IFTHENLAST_YES : IFTHENLAST_NO))
2815-
return false;
2816-
2817-
if (thumb_decompose(&request, &decomp) != STATUS_OK)
2909+
bool decoded = populateDecomposeRequest(&request, data + offset, remainingLen, addr + offset,
2910+
IFTHEN_YES, ((i + 1) >= instrCount) ? IFTHENLAST_YES : IFTHENLAST_NO)
2911+
&& (thumb_decompose(&request, &decomp) == STATUS_OK)
2912+
&& !(decomp.status & STATUS_UNDEFINED) && decomp.format;
2913+
if (!decoded)
28182914
return false;
28192915
if ((decomp.instrSize / 8) > remainingLen)
28202916
return false;
2821-
if ((decomp.status & STATUS_UNDEFINED) || (!decomp.format))
2822-
return false;
28232917

2824-
if (isTrue) {
2825-
addrsTrue.push_back(request.addr);
2826-
decompsTrue.push_back(decomp);
2827-
}
2828-
else {
2829-
addrsFalse.push_back(request.addr);
2830-
decompsFalse.push_back(decomp);
2918+
ThumbITSlot slot;
2919+
slot.addr = request.addr;
2920+
slot.decomp = decomp;
2921+
slot.thenSlot = thenSlot;
2922+
slot.lift = !pathTerminated[stateIdx];
2923+
slots.push_back(slot);
2924+
pathHasBody[stateIdx] |= slot.lift;
2925+
2926+
if (slot.lift)
2927+
{
2928+
pathWroteFlags[stateIdx] |= ThumbITInstructionWritesAPSR(decomp);
2929+
2930+
InstructionInfo innerResult;
2931+
if (GetInstructionInfo(data + offset, addr + offset, remainingLen, innerResult))
2932+
{
2933+
for (size_t j = 0; j < innerResult.branchCount; j++)
2934+
{
2935+
switch (innerResult.branchType[j])
2936+
{
2937+
case UnconditionalBranch:
2938+
case TrueBranch:
2939+
case FalseBranch:
2940+
case FunctionReturn:
2941+
case UnresolvedBranch:
2942+
case IndirectBranch:
2943+
case ExceptionBranch:
2944+
pathTerminated[stateIdx] = true;
2945+
break;
2946+
default:
2947+
break;
2948+
}
2949+
}
2950+
}
28312951
}
28322952

28332953
offset += decomp.instrSize / 8;
28342954
}
28352955

2956+
decomp_result branchDecomp;
2957+
2958+
if ((offset < len) && ((len - offset) >= 2)
2959+
&& populateDecomposeRequest(&request, data + offset, len - offset, addr + offset, IFTHEN_NO, IFTHENLAST_NO)
2960+
&& (thumb_decompose(&request, &branchDecomp) == STATUS_OK)
2961+
&& ((offset + (branchDecomp.instrSize / 8)) <= len)
2962+
&& !(branchDecomp.status & STATUS_UNDEFINED) && branchDecomp.format && IsConditionalBranch(branchDecomp)
2963+
&& IsSameOrInvertedCondition(branchDecomp.fields[FIELD_cond], cond))
2964+
{
2965+
bool branchOnTrue = branchDecomp.fields[FIELD_cond] == cond;
2966+
size_t stateIdx = branchOnTrue ? 0 : 1;
2967+
if (!pathTerminated[stateIdx] && !pathWroteFlags[stateIdx])
2968+
{
2969+
ThumbITSlot slot;
2970+
slot.addr = request.addr;
2971+
slot.thenSlot = branchOnTrue;
2972+
slot.lift = true;
2973+
slot.directBranch = true;
2974+
slot.branchTarget = GetConditionalBranchTarget(branchDecomp);
2975+
slots.push_back(slot);
2976+
pathHasBody[stateIdx] = true;
2977+
pathTerminated[stateIdx] = true;
2978+
offset += branchDecomp.instrSize / 8;
2979+
}
2980+
}
2981+
28362982
// generate IL
28372983
LowLevelILLabel labelTrue, labelFalse, labelDone;
28382984

28392985
il.AddInstruction(il.If(GetCondition(il, cond), labelTrue, labelFalse));
28402986

2841-
// generate IL for "true" if-else members
2842-
il.MarkLabel(labelTrue);
2843-
2844-
for (size_t i = 0; i < decompsTrue.size(); i++)
2987+
auto liftPath = [&](bool thenPath, LowLevelILLabel& label)
28452988
{
2846-
il.SetCurrentAddress(this, addrsTrue[i]);
2847-
GetLowLevelILForThumbInstruction(this, il, &(decompsTrue[i]), true);
2848-
}
2989+
size_t stateIdx = thenPath ? 0 : 1;
28492990

2850-
if (decompsFalse.empty()) {
2851-
il.MarkLabel(labelFalse);
2852-
}
2853-
else {
2854-
il.AddInstruction(il.Goto(labelDone));
2855-
il.MarkLabel(labelFalse);
2991+
il.MarkLabel(label);
28562992

2857-
// generate IL for "false" if-else members
2858-
for (int i = 0; i < decompsFalse.size(); i++)
2993+
for (auto& slot : slots)
28592994
{
2860-
il.SetCurrentAddress(this, addrsFalse[i]);
2861-
GetLowLevelILForThumbInstruction(this, il, &(decompsFalse[i]), true);
2995+
if (!slot.lift || (slot.thenSlot != thenPath))
2996+
continue;
2997+
2998+
il.SetCurrentAddress(this, slot.addr);
2999+
if (slot.directBranch)
3000+
EmitDirectThumbJump(this, il, slot.branchTarget);
3001+
else
3002+
GetLowLevelILForThumbInstruction(this, il, &slot.decomp, true);
28623003
}
28633004

3005+
if (thenPath && pathHasBody[1] && !pathTerminated[stateIdx])
3006+
il.AddInstruction(il.Goto(labelDone));
3007+
};
3008+
3009+
liftPath(true, labelTrue);
3010+
liftPath(false, labelFalse);
3011+
3012+
if (pathHasBody[1])
28643013
il.MarkLabel(labelDone);
2865-
}
28663014

28673015
len = offset;
28683016
return true;

0 commit comments

Comments
 (0)