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

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)
                    )