(self)
return simplified
Find variables that are definitely equivalent and then eliminate unnecessary copies.
Find variables that are definitely equivalent and then eliminate unnecessary copies.
Find variables that are definitely equivalent and then eliminate unnecessary copies .
def _unify_local_variables(self) -> bool:
        """
        Find variables that are definitely equivalent and then eliminate unnecessary copies.
        """

        simplified = False

        prop = self._compute_propagation()
        if not prop.equivalence:
            return simplified

        addr_and_idx_to_block: Dict[Tuple[int,int], Block] = { }
        for block in self.func_graph.nodes():
            addr_and_idx_to_block[(block.addr, block.idx)] = block

        equivalences: Dict[Any,Set[Equivalence]] = defaultdict(set)
        for eq in prop.equivalence:
            equivalences[eq.atom1].add(eq)

        for _, eqs in equivalences.items():
            if len(eqs) > 1:
                continue

            eq = next(iter(eqs))

            # Acceptable equivalence classes:
            #
            # stack variable == register
            # register variable == register
            # stack variable == Conv(register, M->N)
            #
            the_def = None
            if isinstance(eq.atom0, SimStackVariable):
                if isinstance(eq.atom1, Register):
                    # stack_var == register
                    reg = eq.atom1
                elif isinstance(eq.atom1, Convert) and isinstance(eq.atom1.operand, Register):
                    # stack_var == Conv(register, M->N)
                    reg = eq.atom1.operand
                else:
                    continue

            elif isinstance(eq.atom0, Register):
                if isinstance(eq.atom1, Register):
                    # register == register
                    reg = eq.atom1
                else:
                    continue

            else:
                continue

            # find the definition of this register
            rd = self._compute_reaching_definitions()
            defs = rd.all_uses.get_uses_by_location(eq.codeloc)
            if len(defs) != 1:
                # there are multiple defs for this register - we do not support replacing all of them
                continue
            for def_ in defs:
                def_: Definition
                if isinstance(def_.atom, atoms.Register) and def_.atom.reg_offset == reg.reg_offset:
                    # found it!
                    the_def = def_
                    break

            if the_def is None:
                continue

            if isinstance(the_def.codeloc, ExternalCodeLocation):
                # this is a function argument. we enter a slightly different logic and try to eliminate copies of this
                # argument if
                # (a) the on-stack copy of it has never been modified in this function
                # (b) the function argument register has never been updated.
                #     TODO: we may loosen requirement (b) once we have real register versioning in AIL.
                defs = [ def_ for def_ in rd.all_definitions if def_.codeloc == eq.codeloc ]
                all_uses_with_def = None
                to_replace, replace_with = None, None
                remove_initial_assignment = None

                if defs and len(defs) == 1:
                    stackvar_def = defs[0]
                    if isinstance(stackvar_def.atom, atoms.MemoryLocation) \
                            and isinstance(stackvar_def.atom.addr, SpOffset):
                        # found the stack variable
                        # Make sure there is no other write to this location
                        if any((def_ != stackvar_def and def_.atom == stackvar_def.atom)
                               for def_ in rd.all_definitions if isinstance(def_.atom, atoms.MemoryLocation)):
                            continue

                        # Make sure the register is never updated across this function
                        if any((def_ != the_def and def_.atom == the_def.atom)
                               for def_ in rd.all_definitions if isinstance(def_.atom, atoms.Register)):
                            continue

                        # find all its uses
                        all_stackvar_uses: Set[CodeLocation] = set(rd.all_uses.get_uses(stackvar_def))
                        all_uses_with_def = set()
                        for use in all_stackvar_uses:
                            all_uses_with_def.add((stackvar_def, use))

                        to_replace = Load(None, StackBaseOffset(None, self.project.arch.bits, eq.atom0.offset),
                                          eq.atom0.size, endness=self.project.arch.memory_endness)
                        replace_with = eq.atom1
                        remove_initial_assignment = True

                if all_uses_with_def is None:
                    continue

            else:
                # find all uses of this definition
                # we make a copy of the set since we may touch the set (uses) when replacing expressions
                all_uses: Set[CodeLocation] = set(rd.all_uses.get_uses(the_def))
                all_uses_with_def = set((the_def, use) for use in all_uses)

                remove_initial_assignment = False  # expression folding will take care of it
                if isinstance(eq.atom0, SimStackVariable):
                    # create the memory loading expression
                    to_replace = eq.atom1
                    replace_with = Load(None, StackBaseOffset(None, self.project.arch.bits, eq.atom0.offset),
                                        eq.atom0.size, endness=self.project.arch.memory_endness)
                elif isinstance(eq.atom0, Register):
                    if self.project.arch.is_artificial_register(eq.atom0.reg_offset, eq.atom0.size):
                        to_replace = eq.atom0
                        replace_with = eq.atom1
                    else:
                        to_replace = eq.atom1
                        replace_with = eq.atom0
                else:
                    raise RuntimeError("Unsupported atom0 type %s." % type(eq.atom0))

            # TODO: We can only replace all these uses with the stack variable if the stack variable isn't
            # TODO: re-assigned of a new value. Perform this check.

            # replace all uses
            all_uses_replaced = True
            for def_, u in all_uses_with_def:
                if u == eq.codeloc:
                    # skip the very initial assignment location
                    continue
                old_block = addr_and_idx_to_block.get((u.block_addr, u.block_idx), None)
                if old_block is None:
                    continue

                # if there is an updated block, use it
                the_block = self.blocks.get(old_block, old_block)
                stmt: Statement = the_block.statements[u.stmt_idx]

                r, new_block = self._replace_expr_and_update_block(the_block, u.stmt_idx, stmt, def_, u, to_replace,
                                                                   replace_with)
                if r:
                    self.blocks[old_block] = new_block
                else:
                    # failed to replace a use - we need to keep the initial assignment!
                    all_uses_replaced = False
                simplified |= r

            if all_uses_replaced and remove_initial_assignment:
                # the initial statement can be removed
                self._assignments_to_remove.add(eq.codeloc)

        # no need to clear cache at the end of this function
        return simplified
def _unify_local_variables ( self ) -> bool : simplified = False prop = self . _compute_propagation ( ) if not prop . equivalence : return simplified addr_and_idx_to_block : Dict [ Tuple [ int , int ] , Block ] = { } for block in self . func_graph . nodes ( ) : addr_and_idx_to_block [ ( block . addr , block . idx ) ] = block equivalences : Dict [ Any , Set [ Equivalence ] ] = defaultdict ( set ) for eq in prop . equivalence : equivalences [ eq . atom1 ] . add ( eq ) for _ , eqs in equivalences . items ( ) : if len ( eqs ) > 1 : continue eq = next ( iter ( eqs ) ) # Acceptable equivalence classes: # # stack variable == register # register variable == register # stack variable == Conv(register, M->N) # the_def = None if isinstance ( eq . atom0 , SimStackVariable ) : if isinstance ( eq . atom1 , Register ) : # stack_var == register reg = eq . atom1 elif isinstance ( eq . atom1 , Convert ) and isinstance ( eq . atom1 . operand , Register ) : # stack_var == Conv(register, M->N) reg = eq . atom1 . operand else : continue elif isinstance ( eq . atom0 , Register ) : if isinstance ( eq . atom1 , Register ) : # register == register reg = eq . atom1 else : continue else : continue # find the definition of this register rd = self . _compute_reaching_definitions ( ) defs = rd . all_uses . get_uses_by_location ( eq . codeloc ) if len ( defs ) != 1 : # there are multiple defs for this register - we do not support replacing all of them continue for def_ in defs : def_ : Definition if isinstance ( def_ . atom , atoms . Register ) and def_ . atom . reg_offset == reg . reg_offset : # found it! the_def = def_ break if the_def is None : continue if isinstance ( the_def . codeloc , ExternalCodeLocation ) : # this is a function argument. we enter a slightly different logic and try to eliminate copies of this # argument if # (a) the on-stack copy of it has never been modified in this function # (b) the function argument register has never been updated. #     TODO: we may loosen requirement (b) once we have real register versioning in AIL. defs = [ def_ for def_ in rd . all_definitions if def_ . codeloc == eq . codeloc ] all_uses_with_def = None to_replace , replace_with = None , None remove_initial_assignment = None if defs and len ( defs ) == 1 : stackvar_def = defs [ 0 ] if isinstance ( stackvar_def . atom , atoms . MemoryLocation ) and isinstance ( stackvar_def . atom . addr , SpOffset ) : # found the stack variable # Make sure there is no other write to this location if any ( ( def_ != stackvar_def and def_ . atom == stackvar_def . atom ) for def_ in rd . all_definitions if isinstance ( def_ . atom , atoms . MemoryLocation ) ) : continue # Make sure the register is never updated across this function if any ( ( def_ != the_def and def_ . atom == the_def . atom ) for def_ in rd . all_definitions if isinstance ( def_ . atom , atoms . Register ) ) : continue # find all its uses all_stackvar_uses : Set [ CodeLocation ] = set ( rd . all_uses . get_uses ( stackvar_def ) ) all_uses_with_def = set ( ) for use in all_stackvar_uses : all_uses_with_def . add ( ( stackvar_def , use ) ) to_replace = Load ( None , StackBaseOffset ( None , self . project . arch . bits , eq . atom0 . offset ) , eq . atom0 . size , endness = self . project . arch . memory_endness ) replace_with = eq . atom1 remove_initial_assignment = True if all_uses_with_def is None : continue else : # find all uses of this definition # we make a copy of the set since we may touch the set (uses) when replacing expressions all_uses : Set [ CodeLocation ] = set ( rd . all_uses . get_uses ( the_def ) ) all_uses_with_def = set ( ( the_def , use ) for use in all_uses ) remove_initial_assignment = False # expression folding will take care of it if isinstance ( eq . atom0 , SimStackVariable ) : # create the memory loading expression to_replace = eq . atom1 replace_with = Load ( None , StackBaseOffset ( None , self . project . arch . bits , eq . atom0 . offset ) , eq . atom0 . size , endness = self . project . arch . memory_endness ) elif isinstance ( eq . atom0 , Register ) : if self . project . arch . is_artificial_register ( eq . atom0 . reg_offset , eq . atom0 . size ) : to_replace = eq . atom0 replace_with = eq . atom1 else : to_replace = eq . atom1 replace_with = eq . atom0 else : raise RuntimeError ( "Unsupported atom0 type %s." % type ( eq . atom0 ) ) # TODO: We can only replace all these uses with the stack variable if the stack variable isn't # TODO: re-assigned of a new value. Perform this check. # replace all uses all_uses_replaced = True for def_ , u in all_uses_with_def : if u == eq . codeloc : # skip the very initial assignment location continue old_block = addr_and_idx_to_block . get ( ( u . block_addr , u . block_idx ) , None ) if old_block is None : continue # if there is an updated block, use it the_block = self . blocks . get ( old_block , old_block ) stmt : Statement = the_block . statements [ u . stmt_idx ] r , new_block = self . _replace_expr_and_update_block ( the_block , u . stmt_idx , stmt , def_ , u , to_replace , replace_with ) if r : self . blocks [ old_block ] = new_block else : # failed to replace a use - we need to keep the initial assignment! all_uses_replaced = False simplified |= r if all_uses_replaced and remove_initial_assignment : # the initial statement can be removed self . _assignments_to_remove . add ( eq . codeloc ) # no need to clear cache at the end of this function return simplified