8000 Peephole: Signed division simplification case B. by ltfish · Pull Request #5530 · angr/angr · GitHub
[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to content

Peephole: Signed division simplification case B. #5530

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Merged
merged 3 commits into from
Jun 13, 2025
+315 −95
Merged

Peephole: Signed division simplification case B. #5530

Show file tree
Hide file tree
Changes from all commits
Commits
Show all changes
3 commits
Select commit Hold shift + click to select a range
0d28d7c
Peephole: Signed division simplification case B.
ltfish Jun 13, 2025
8723cab
Add more simplifications and a test case.
ltfish Jun 13, 2025
cd4b618
Lint and type check.
ltfish Jun 13, 2025
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
8 changes: 4 additions & 4 deletions angr/analyses/decompiler/peephole_optimizations/__init__.py
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -4,14 +4,14 @@
from .a_mul_const_div_shr_const import AMulConstDivShrConst
from .a_shl_const_sub_a import AShlConstSubA
from .a_sub_a_div import ASubADiv
from .a_sub_a_div_const_mul_const import ASubADivConstMulConst
from .modulo_simplifier import ModuloSimplifier
from .a_sub_a_shr_const_shr_const import ASubAShrConstShrConst
from .arm_cmpf import ARMCmpF
from .bswap import Bswap
from .cas_intrinsics import CASIntrinsics
from .coalesce_same_cascading_ifs import CoalesceSameCascadingIfs
from .constant_derefs import ConstantDereferences
from .const_mull_a_shift import ConstMullAShift
from .optimized_div_simplifier import OptimizedDivisionSimplifier
from .extended_byte_and_mask import ExtendedByteAndMask
from .remove_empty_if_body import RemoveEmptyIfBody
from .remove_redundant_ite_branch import RemoveRedundantITEBranches
Expand Down Expand Up @@ -61,14 +61,14 @@
AShlConstSubA,
AMulConstSubA,
ASubADiv,
ASubADivConstMulConst,
ModuloSimplifier,
ASubAShrConstShrConst,
ARMCmpF,
Bswap,
CASIntrinsics,
CoalesceSameCascadingIfs,
ConstantDereferences,
ConstMullAShift,
OptimizedDivisionSimplifier,
ExtendedByteAndMask,
RemoveEmptyIfBody,
RemoveRedundantITEBranches,
Expand Down
57 changes: 0 additions & 57 deletions angr/analyses/decompiler/peephole_optimizations/a_sub_a_div_const_mul_const.py
View file
Open in desktop

This file was deleted.

53 changes: 53 additions & 0 deletions angr/analyses/decompiler/peephole_optimizations/eager_eval.py
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -170,6 +170,10 @@ def _optimize_binaryop(expr: BinaryOp):
if isinstance(expr.operands[0], Const) and expr.operands[0].value == 0:
return UnaryOp(expr.idx, "Neg", expr.operands[1], **expr.tags)

r = EagerEvaluation._combine_like_terms(expr)
if r is not None:
return r

if isinstance(expr.operands[0], StackBaseOffset) and isinstance(expr.operands[1], StackBaseOffset):
assert isinstance(expr.operands[0].offset, int) and isinstance(expr.operands[1].offset, int)
return Const(expr.idx, None, expr.operands[0].offset - expr.operands[1].offset, expr.bits, **expr.tags)
Expand Down Expand Up @@ -354,6 +358,55 @@ def _optimize_binaryop(expr: BinaryOp):

return None

@staticmethod
def _combine_like_terms(expr: BinaryOp) -> BinaryOp | None:
"""
Combine like terms for binary operations.
"""

op = expr.op
assert op in {"Add", "Sub"}

expr0, expr1 = expr.operands

conv = None
if isinstance(expr0, Convert) and expr0.from_bits < expr0.to_bits:
conv = expr0.from_bits, expr0.to_bits, expr0.is_signed
expr0 = expr0.operand

if isinstance(expr0, BinaryOp) and expr0.op == "Mul" and isinstance(expr0.operands[1], Const):
n = expr0.operands[0]

if isinstance(n, Convert) and n.from_bits > n.to_bits:
if conv is not None and (n.to_bits, n.from_bits, n.is_signed) != conv:
return None
n = n.operand

if n.likes(expr1):
# (n * C) - n ==> (C - 1) * n
coeff_0 = expr0.operands[1]
coeff = Const(coeff_0.idx, None, coeff_0.value - 1, expr.bits, **coeff_0.tags)
return BinaryOp(
expr.idx, "Mul", [n, coeff], expr.signed, variable=expr.variable, bits=expr.bits, **expr.tags
)
if isinstance(expr1, BinaryOp) and expr1.op == "Mul" and isinstance(expr.operands[1].operands[1], Const):
n1 = expr.operands[1].operands[0]
if n.likes(n1):
# (n * C) - (n1 * C1) ==> n * (C - C1)
coeff_0 = expr0.operands[1]
coeff_1 = expr1.operands[1]
coeff = Const(coeff_0.idx, None, coeff_0.value - coeff_1.value, expr.bits, **coeff_0.tags)
return BinaryOp(
expr.idx,
"Mul",
[n, coeff],
expr.signed,
variable=expr.variable,
bits=expr.bits,
**expr.tags,
)
return None

@staticmethod
def _optimize_unaryop(expr: UnaryOp):
if expr.op == "Neg" and isinstance(expr.operand, Const) and isinstance(expr.operand.value, int):
Expand Down
89 changes: 89 additions & 0 deletions angr/analyses/decompiler/peephole_optimizations/modulo_simplifier.py
View file
Open in desktop
Original file line number Diff line number Diff line change
@@ -0,0 +1,89 @@
# pylint:disable=too-many-boolean-expressions
from __future__ import annotations
from angr.ailment.expression import BinaryOp, Const, Convert

from .base import PeepholeOptimizationExprBase


class ModuloSimplifier(PeepholeOptimizationExprBase):
"""
Simplify division and multiplication expressions that can be reduced to a modulo operation.
"""

__slots__ = ()

NAME = "a - (a / N) * N => a % N"
expr_classes = (BinaryOp,)

def optimize( # pylint:disable=unused-argument
self, expr: BinaryOp, stmt_idx: int | None = None, block=None, **kwargs
):
if expr.op == "Sub" and len(expr.operands) == 2:
sub0, sub1 = expr.operands
# unpack Conversions
outer_conv_expr = None
if (
isinstance(sub0, Convert)
and isinstance(sub1, Convert)
and sub0.to_bits == sub1.to_bits
and sub0.from_bits == sub1.from_bits
and sub0.to_bits > sub0.from_bits
and sub0.is_signed == sub1.is_signed
):
# Convert(a) - Convert(a / N * N) ==> Convert(a % N)
outer_conv_expr = sub0
sub0 = sub0.operand
sub1 = sub1.operand

if isinstance(sub1, BinaryOp) and sub1.op == "Mul" and isinstance(sub1.operands[1], Const):
a0, op1 = sub0, sub1
op1_left = op1.operands[0]
mul_const = sub1.operands[1]

if (
isinstance(op1_left, Convert)
and isinstance(a0, Convert)
and op1_left.to_bits == a0.to_bits
and op1_left.from_bits == a0.from_bits
):
# Convert(a) - (Convert(a / N)) * N ==> Convert(a) % N
inner_conv_expr = a0
a0 = a0.operand
op1_left = op1_left.operand
else:
inner_conv_expr = None

if isinstance(op1_left, BinaryOp) and op1_left.op == "Div" and isinstance(op1_left.operands[1], Const):
# a - (a / N) * N ==> a % N
a1 = op1_left.operands[0]
div_const = op1_left.operands[1]

if a0.likes(a1) and mul_const.value == div_const.value:
operands = [a0, div_const]
mod = BinaryOp(expr.idx, "Mod", operands, False, bits=a0.bits, **expr.tags)
if inner_conv_expr is not None:
conv_from_bits = inner_conv_expr.from_bits
conv_to_bits = (
inner_conv_expr.to_bits if outer_conv_expr is None else outer_conv_expr.to_bits
)
conv_signed = inner_conv_expr.is_signed
conv_expr = inner_conv_expr
elif outer_conv_expr is not None:
conv_from_bits = outer_conv_expr.from_bits
conv_to_bits = outer_conv_expr.to_bits
conv_signed = outer_conv_expr.is_signed
conv_expr = outer_conv_expr
else:
# no conversion necessary
return mod

return Convert(
conv_expr.idx,
conv_from_bits,
conv_to_bits,
conv_signed,
mod,
**conv_expr.tags,
)

return None
Loading
0