(self, function, data_graph)
Find unused registers throughout the function, and use those registers to replace stack variables.

        Only functions that satisfy the following criteria can be optimized in this way:
        - The function does not call any other function.
        - The function does not use esp to index any stack variable.
        - Prologue and epilogue of the function is identifiable.
        - At least one register is not used in the entire function.

        :param angr.knowledge.Function function:
        :param networkx.MultiDiGraph data_graph:
        :return: None
Find unused registers throughout the function, and use those registers to replace stack variables.
Find unused registers throughout the function and use those registers to replace stack variables .
def _register_reallocation(self, function, data_graph):
        """
        Find unused registers throughout the function, and use those registers to replace stack variables.

        Only functions that satisfy the following criteria can be optimized in this way:
        - The function does not call any other function.
        - The function does not use esp to index any stack variable.
        - Prologue and epilogue of the function is identifiable.
        - At least one register is not used in the entire function.

        :param angr.knowledge.Function function:
        :param networkx.MultiDiGraph data_graph:
        :return: None
        """

        # make sure this function does not call other functions
        if function.callout_sites:
            return

        if len(function.endpoints) != 1:
            return

        # identify function prologue and epilogue
        startpoint_block = self.project.factory.block(function.startpoint.addr).capstone
        startpoint_insns = startpoint_block.insns

        # supported function prologues:
        #
        # push  ebp
        # mov   ebp, esp
        # sub   esp, [0-9a-f]+h
        #
        # push  ebp
        # mov   ebp, esp
        # push  eax

        if len(startpoint_insns) < 3:
            return

        insn0, insn1, insn2 = startpoint_insns[:3]

        if not (insn0.mnemonic == 'push' and insn0.op_str == 'ebp'):
            return
        if not (insn1.mnemonic == 'mov' and insn1.op_str == 'ebp, esp'):
            return
        if not (insn2.mnemonic == 'sub' and re.match(r"esp, [0-9a-fx]+", insn2.op_str)) and \
                not (insn2.mnemonic == 'push' and insn2.op_str == 'eax'):
            return


        endpoint_block = self.project.factory.block(function.endpoints[0].addr).capstone
        endpoint_insns = endpoint_block.insns

        # supported function epilogues:
        #
        # add   esp, [0-9a-f]+h
        # pop   ebp
        # ret

        if len(endpoint_insns) < 3:
            return

        insn3, insn4, insn5 = endpoint_insns[-3:]

        if not (insn3.mnemonic == 'add' and re.match(r"esp, [0-9a-fx]+", insn3.op_str)):
            return
        if not (insn4.mnemonic == 'pop' and insn4.op_str == 'ebp'):
            return
        if not insn5.mnemonic == 'ret':
            return

        # make sure esp is not used anywhere else - all stack variables must be indexed using ebp
        esp_offset = self.project.arch.registers['esp'][0]
        ebp_offset = self.project.arch.registers['ebp'][0]
        esp_variables = [ ]
        for n in data_graph.nodes():
            if isinstance(n.variable, SimRegisterVariable) and n.variable.reg == esp_offset:
                esp_variables.append(n)

        # find out all call instructions
        call_insns = set()
        for src, dst, data in function.transition_graph.edges(data=True):
            if 'type' in data and data['type'] == 'call':
                src_block = function._get_block(src.addr)
                call_insns.add(src_block.instruction_addrs[-1])

        # there should be six esp variables + all call sites
        # push ebp (insn0 - read, insn0 - write) ; sub esp, 0xXX (insn2) ;
        # add esp, 0xXX (insn3) ; pop ebp (insn4) ; ret (insn5)

        esp_insns = set( n.location.ins_addr for n in esp_variables )
        if esp_insns != { insn0.address, insn2.address, insn3.address, insn4.address, insn5.address } | call_insns:
            return

        prologue_addr = insn0.address
        prologue_size = insn0.size + insn1.size + insn2.size
        epilogue_addr = insn3.address
        epilogue_size = insn3.size + insn4.size + insn5.size

        # look at consumer of those esp variables. no other instruction should be consuming them
        # esp_consumer_insns = { insn0.address, insn1.address, insn2.address, insn3.address, insn4.address,
        #                        insn5.address} | esp_insns
        # for esp_variable in esp_variables:  # type: angr.analyses.ddg.ProgramVariable
        #     consumers = data_graph.successors(esp_variable)
        #     if any([ consumer.location.ins_addr not in esp_consumer_insns for consumer in consumers ]):
        #         return

        # make sure we never gets the address of those stack variables into any register
        # say, lea edx, [ebp-0x4] is forbidden
        # check all edges in data graph
        for src, dst, data in data_graph.edges(data=True):
            if isinstance(dst.variable, SimRegisterVariable) and \
                    dst.variable.reg != ebp_offset and \
                    dst.variable.reg < 40:
                #to a register other than ebp
                if isinstance(src.variable, SimRegisterVariable) and \
                        src.variable.reg == ebp_offset:
                    # from ebp
                    l.debug("Found a lea operation from ebp at %#x. Function %s cannot be optimized.",
                            dst.location.ins_addr,
                            repr(function),
                            )
                    return

        # we definitely don't want to mess with fp or sse operations
        for node in data_graph.nodes():
            if isinstance(node.variable, SimRegisterVariable) and \
                    72 <= node.variable.reg < 288:  # offset(mm0) <= node.variable.reg < offset(cs)
                l.debug('Found a float-point/SSE register access at %#x. Function %s cannot be optimized.',
                        node.location.ins_addr,
                        repr(function)
                        )
                return

        l.debug("RegisterReallocation: function %s satisfies the criteria.", repr(function))

        # nice. let's see if we can optimize this function
        # do we have free registers?

        used_general_registers = set()
        for n in data_graph.nodes():
            if isinstance(n.variable, SimRegisterVariable):
                if n.variable.reg < 40:  # this is a hardcoded limit - we only care about general registers
                    used_general_registers.add(n.variable.reg)
        registers = self.project.arch.registers
        all_general_registers = { #registers['eax'][0], registers['ecx'][0], registers['edx'][0],
                                  registers['ebx'][0], registers['edi'][0], registers['esi'][0],
                                  registers['esp'][0], registers['ebp'][0]
                                  }
        unused_general_registers = all_general_registers - used_general_registers

        if not unused_general_registers:
            l.debug("RegisterReallocation: function %s does not have any free register.", repr(function))
            return
        l.debug("RegisterReallocation: function %s has %d free register(s): %s",
                repr(function),
                len(unused_general_registers),
                ", ".join([self.project.arch.register_names[u] for u in unused_general_registers ])
                )

        # find local stack variables of size 4
        stack_variables = set()
        for n in data_graph.nodes():
            if isinstance(n.variable, SimStackVariable) and \
                    n.variable.base == 'bp' and \
                    n.variable.size == 4 and \
                    n.variable.offset < 0:
                stack_variables.add(n)

        # alright, now we need to make sure that stack variables are never accessed by indexes
        # in other words, they must be accessed directly in forms of 'dword ptr [ebp+x]'
        # it's easy to do this: we get mem_addr predecessors of each stack variable, and make sure there are only two of
        # them: one is ebp, the other one is a constant
        #
        # ah, also, since we do not want to mess with crazy fp registers, we further require none of the stack variable
        # sources and consumers is a FP register.

        filtered_stack_variables = set()
        for stack_variable in stack_variables:

            failed = False

            # check how they are accessed
            in_edges = data_graph.in_edges(stack_variable, data=True)
            for src, _, data in in_edges:
                if 'type' in data and data['type'] == 'mem_addr':
                    if isinstance(src.variable, SimRegisterVariable) and src.variable.reg == ebp_offset:
                        # ebp
                        pass
                    elif isinstance(src.variable, SimConstantVariable):
                        # the constant
                        pass
                    else:
                        # ouch
                        failed = True
                        break

                if isinstance(src.variable, SimRegisterVariable) and src.variable.reg >= 72:
                    # it comes from a FP register
                    failed = True
                    break

            if failed:
                continue

            # check consumers
            out_edges = data_graph.out_edges(stack_variable, data=True)
            for _, dst, data in out_edges:
                if 'type' in data and data['type'] == 'kill':
                    continue
                if isinstance(dst.variable, SimRegisterVariable) and dst.variable.reg >= 72:
                    # an FP register is the consumer
                    failed = True
                    break

            if failed:
                continue

            filtered_stack_variables.add(stack_variable)

        # order the stack variables by the sum of their in and out degrees.
        stack_variable_to_degree = defaultdict(int)
        stack_variable_sources = defaultdict(list)
        for sv in filtered_stack_variables:
            stack_variable_to_degree[sv.variable] += data_graph.in_degree(sv)
            stack_variable_to_degree[sv.variable] += data_graph.out_degree(sv)
            stack_variable_sources[sv.variable].append(sv)

        sorted_stack_variables = sorted(stack_variable_to_degree.keys(),
                                       key=lambda sv: stack_variable_to_degree[sv],
                                       reverse=True
                                       )

        # aha these are the ones that we can replace!
        for reg, sv in zip(unused_general_registers, sorted_stack_variables):

            non_initial_sources = [src for src in stack_variable_sources[sv] if not src.initial]

            if not non_initial_sources:
                # we failed to find any source for it, which indicates a failure in our dependence analysis
                # skip
                continue

            # get consumers
            consumers = set()
            for src in stack_variable_sources[sv]:
                out_edges = data_graph.out_edges(src, data=True)
                for _, dst, data in out_edges:
                    if 'type' not in data or data['type'] != 'kill':
                        consumers.add(dst)

            rr = RegisterReallocation(sv, SimRegisterVariable(reg, 4), non_initial_sources,
                                      list(consumers), prologue_addr, prologue_size, epilogue_addr, epilogue_size
                                      )
            self.register_reallocations.append(rr)

            l.debug("RegisterReallocation: %s will replace %s in function %s.",
                    rr.register_variable,
                    rr.stack_variable,
                    repr(function)
                    )
def _register_reallocation ( self , function , data_graph ) : # make sure this function does not call other functions if function . callout_sites : return if len ( function . endpoints ) != 1 : return # identify function prologue and epilogue startpoint_block = self . project . factory . block ( function . startpoint . addr ) . capstone startpoint_insns = startpoint_block . insns # supported function prologues: # # push  ebp # mov   ebp, esp # sub   esp, [0-9a-f]+h # # push  ebp # mov   ebp, esp # push  eax if len ( startpoint_insns ) < 3 : return insn0 , insn1 , insn2 = startpoint_insns [ : 3 ] if not ( insn0 . mnemonic == 'push' and insn0 . op_str == 'ebp' ) : return if not ( insn1 . mnemonic == 'mov' and insn1 . op_str == 'ebp, esp' ) : return if not ( insn2 . mnemonic == 'sub' and re . match ( r"esp, [0-9a-fx]+" , insn2 . op_str ) ) and not ( insn2 . mnemonic == 'push' and insn2 . op_str == 'eax' ) : return endpoint_block = self . project . factory . block ( function . endpoints [ 0 ] . addr ) . capstone endpoint_insns = endpoint_block . insns # supported function epilogues: # # add   esp, [0-9a-f]+h # pop   ebp # ret if len ( endpoint_insns ) < 3 : return insn3 , insn4 , insn5 = endpoint_insns [ - 3 : ] if not ( insn3 . mnemonic == 'add' and re . match ( r"esp, [0-9a-fx]+" , insn3 . op_str ) ) : return if not ( insn4 . mnemonic == 'pop' and insn4 . op_str == 'ebp' ) : return if not insn5 . mnemonic == 'ret' : return # make sure esp is not used anywhere else - all stack variables must be indexed using ebp esp_offset = self . project . arch . registers [ 'esp' ] [ 0 ] ebp_offset = self . project . arch . registers [ 'ebp' ] [ 0 ] esp_variables = [ ] for n in data_graph . nodes ( ) : if isinstance ( n . variable , SimRegisterVariable ) and n . variable . reg == esp_offset : esp_variables . append ( n ) # find out all call instructions call_insns = set ( ) for src , dst , data in function . transition_graph . edges ( data = True ) : if 'type' in data and data [ 'type' ] == 'call' : src_block = function . _get_block ( src . addr ) call_insns . add ( src_block . instruction_addrs [ - 1 ] ) # there should be six esp variables + all call sites # push ebp (insn0 - read, insn0 - write) ; sub esp, 0xXX (insn2) ; # add esp, 0xXX (insn3) ; pop ebp (insn4) ; ret (insn5) esp_insns = set ( n . location . ins_addr for n in esp_variables ) if esp_insns != { insn0 . address , insn2 . address , insn3 . address , insn4 . address , insn5 . address } | call_insns : return prologue_addr = insn0 . address prologue_size = insn0 . size + insn1 . size + insn2 . size epilogue_addr = insn3 . address epilogue_size = insn3 . size + insn4 . size + insn5 . size # look at consumer of those esp variables. no other instruction should be consuming them # esp_consumer_insns = { insn0.address, insn1.address, insn2.address, insn3.address, insn4.address, #                        insn5.address} | esp_insns # for esp_variable in esp_variables:  # type: angr.analyses.ddg.ProgramVariable #     consumers = data_graph.successors(esp_variable) #     if any([ consumer.location.ins_addr not in esp_consumer_insns for consumer in consumers ]): #         return # make sure we never gets the address of those stack variables into any register # say, lea edx, [ebp-0x4] is forbidden # check all edges in data graph for src , dst , data in data_graph . edges ( data = True ) : if isinstance ( dst . variable , SimRegisterVariable ) and dst . variable . reg != ebp_offset and dst . variable . reg < 40 : #to a register other than ebp if isinstance ( src . variable , SimRegisterVariable ) and src . variable . reg == ebp_offset : # from ebp l . debug ( "Found a lea operation from ebp at %#x. Function %s cannot be optimized." , dst . location . ins_addr , repr ( function ) , ) return # we definitely don't want to mess with fp or sse operations for node in data_graph . nodes ( ) : if isinstance ( node . variable , SimRegisterVariable ) and 72 <= node . variable . reg < 288 : # offset(mm0) <= node.variable.reg < offset(cs) l . debug ( 'Found a float-point/SSE register access at %#x. Function %s cannot be optimized.' , node . location . ins_addr , repr ( function ) ) return l . debug ( "RegisterReallocation: function %s satisfies the criteria." , repr ( function ) ) # nice. let's see if we can optimize this function # do we have free registers? used_general_registers = set ( ) for n in data_graph . nodes ( ) : if isinstance ( n . variable , SimRegisterVariable ) : if n . variable . reg < 40 : # this is a hardcoded limit - we only care about general registers used_general_registers . add ( n . variable . reg ) registers = self . project . arch . registers all_general_registers = { #registers['eax'][0], registers['ecx'][0], registers['edx'][0], registers [ 'ebx' ] [ 0 ] , registers [ 'edi' ] [ 0 ] , registers [ 'esi' ] [ 0 ] , registers [ 'esp' ] [ 0 ] , registers [ 'ebp' ] [ 0 ] } unused_general_registers = all_general_registers - used_general_registers if not unused_general_registers : l . debug ( "RegisterReallocation: function %s does not have any free register." , repr ( function ) ) return l . debug ( "RegisterReallocation: function %s has %d free register(s): %s" , repr ( function ) , len ( unused_general_registers ) , ", " . join ( [ self . project . arch . register_names [ u ] for u in unused_general_registers ] ) ) # find local stack variables of size 4 stack_variables = set ( ) for n in data_graph . nodes ( ) : if isinstance ( n . variable , SimStackVariable ) and n . variable . base == 'bp' and n . variable . size == 4 and n . variable . offset < 0 : stack_variables . add ( n ) # alright, now we need to make sure that stack variables are never accessed by indexes # in other words, they must be accessed directly in forms of 'dword ptr [ebp+x]' # it's easy to do this: we get mem_addr predecessors of each stack variable, and make sure there are only two of # them: one is ebp, the other one is a constant # # ah, also, since we do not want to mess with crazy fp registers, we further require none of the stack variable # sources and consumers is a FP register. filtered_stack_variables = set ( ) for stack_variable in stack_variables : failed = False # check how they are accessed in_edges = data_graph . in_edges ( stack_variable , data = True ) for src , _ , data in in_edges : if 'type' in data and data [ 'type' ] == 'mem_addr' : if isinstance ( src . variable , SimRegisterVariable ) and src . variable . reg == ebp_offset : # ebp pass elif isinstance ( src . variable , SimConstantVariable ) : # the constant pass else : # ouch failed = True break if isinstance ( src . variable , SimRegisterVariable ) and src . variable . reg >= 72 : # it comes from a FP register failed = True break if failed : continue # check consumers out_edges = data_graph . out_edges ( stack_variable , data = True ) for _ , dst , data in out_edges : if 'type' in data and data [ 'type' ] == 'kill' : continue if isinstance ( dst . variable , SimRegisterVariable ) and dst . variable . reg >= 72 : # an FP register is the consumer failed = True break if failed : continue filtered_stack_variables . add ( stack_variable ) # order the stack variables by the sum of their in and out degrees. stack_variable_to_degree = defaultdict ( int ) stack_variable_sources = defaultdict ( list ) for sv in filtered_stack_variables : stack_variable_to_degree [ sv . variable ] += data_graph . in_degree ( sv ) stack_variable_to_degree [ sv . variable ] += data_graph . out_degree ( sv ) stack_variable_sources [ sv . variable ] . append ( sv ) sorted_stack_variables = sorted ( stack_variable_to_degree . keys ( ) , key = lambda sv : stack_variable_to_degree [ sv ] , reverse = True ) # aha these are the ones that we can replace! for reg , sv in zip ( unused_general_registers , sorted_stack_variables ) : non_initial_sources = [ src for src in stack_variable_sources [ sv ] if not src . initial ] if not non_initial_sources : # we failed to find any source for it, which indicates a failure in our dependence analysis # skip continue # get consumers consumers = set ( ) for src in stack_variable_sources [ sv ] : out_edges = data_graph . out_edges ( src , data = True ) for _ , dst , data in out_edges : if 'type' not in data or data [ 'type' ] != 'kill' : consumers . add ( dst ) rr = RegisterReallocation ( sv , SimRegisterVariable ( reg , 4 ) , non_initial_sources , list ( consumers ) , prologue_addr , prologue_size , epilogue_addr , epilogue_size ) self . register_reallocations . append ( rr ) l . debug ( "RegisterReallocation: %s will replace %s in function %s." , rr . register_variable , rr . stack_variable , repr ( function ) )