Propagate the temporary registers between instructions and remove them if
    necessary.
    We process the nodes of the graph in reverse post order. For each
    instruction in the node, we look at the variables that it uses. For each of
    these variables we look where it is defined and if we can replace it with
    its definition.
    We have to be careful to the side effects some instructions may have.
    To do the propagation, we use the computed DU and UD chains.

def register_propagation(graph, du, ud):
    """
    Propagate the temporary registers between instructions and remove them if
    necessary.
    We process the nodes of the graph in reverse post order. For each
    instruction in the node, we look at the variables that it uses. For each of
    these variables we look where it is defined and if we can replace it with
    its definition.
    We have to be careful to the side effects some instructions may have.
    To do the propagation, we use the computed DU and UD chains.
    """
    change = True
    while change:
        change = False
        for node in graph.rpo:
            for i, ins in node.get_loc_with_ins():
                logger.debug('Treating instruction %d: %s', i, ins)
                logger.debug('  Used vars: %s', ins.get_used_vars())
                for var in ins.get_used_vars():
                    # Get the list of locations this variable is defined at.
                    locs = ud[var, i]
                    logger.debug('    var %s defined in lines %s', var, locs)
                    # If the variable is uniquely defined for this instruction
                    # it may be eligible for propagation.
                    if len(locs) != 1:
                        continue

                    loc = locs[0]
                    # Methods parameters are defined with a location < 0.
                    if loc < 0:
                        continue
                    orig_ins = graph.get_ins_from_loc(loc)
                    logger.debug('     -> %s', orig_ins)
                    logger.debug('     -> DU(%s, %s) = %s', var, loc,
                                 du[var, loc])

                    # We defined some instructions as not propagable.
                    # Actually this is the case only for array creation
                    # (new foo[x])
                    if not orig_ins.is_propagable():
                        logger.debug('    %s not propagable...', orig_ins)
                        continue

                    if not orig_ins.get_rhs().is_const():
                        # We only try to propagate constants and definition
                        # points which are used at only one location.
                        if len(du[var, loc]) > 1:
                            logger.debug('       => variable has multiple uses'
                                         ' and is not const => skip')
                            continue

                        # We check that the propagation is safe for all the
                        # variables that are used in the instruction.
                        # The propagation is not safe if there is a side effect
                        # along the path from the definition of the variable
                        # to its use in the instruction, or if the variable may
                        # be redifined along this path.
                        safe = True
                        orig_ins_used_vars = orig_ins.get_used_vars()
                        logger.debug('    variables used by the original '
                                     'instruction: %s', orig_ins_used_vars)
                        for var2 in orig_ins_used_vars:
                            # loc is the location of the defined variable
                            # i is the location of the current instruction
                            if not clear_path(graph, var2, loc, i):
                                safe = False
                                break
                        if not safe:
                            logger.debug('Propagation NOT SAFE')
                            continue

                    # We also check that the instruction itself is
                    # propagable. If the instruction has a side effect it
                    # cannot be propagated if there is another side effect
                    # along the path
                    if orig_ins.has_side_effect():
                        if not clear_path(graph, None, loc, i):
                            logger.debug('        %s has side effect and the '
                                         'path is not clear !', orig_ins)
                            continue

                    logger.debug('     => Modification of the instruction!')
                    logger.debug('      - BEFORE: %s', ins)
                    ins.replace(var, orig_ins.get_rhs())
                    logger.debug('      -> AFTER: %s', ins)
                    logger.debug('\t UD(%s, %s) : %s', var, i, ud[var, i])
                    ud[var, i].remove(loc)
                    logger.debug('\t    -> %s', ud[var, i])
                    if len(ud[var, i]) == 0:
                        ud.pop((var, i))
                    for var2 in orig_ins.get_used_vars():
                        # We update the UD chain of the variables we
                        # propagate. We also have to take the
                        # definition points of all the variables used
                        # by the instruction and update the DU chain
                        # with this information.
                        old_ud = ud.get((var2, loc))
                        logger.debug('\t  ud(%s, %s) = %s', var2, loc, old_ud)
                        # If the instruction use the same variable
                        # multiple times, the second+ time the ud chain
                        # will be None because already treated.
                        if old_ud is None:
                            continue
                        ud[var2, i].extend(old_ud)
                        logger.debug('\t  - ud(%s, %s) = %s', var2, i,
                                     ud[var2, i])
                        ud.pop((var2, loc))

                        for def_loc in old_ud:
                            du[var2, def_loc].remove(loc)
                            du[var2, def_loc].append(i)

                    new_du = du[var, loc]
                    logger.debug('\t new_du(%s, %s): %s', var, loc, new_du)
                    new_du.remove(i)
                    logger.debug('\t    -> %s', new_du)
                    if not new_du:
                        logger.debug('\t  REMOVING INS %d', loc)
                        du.pop((var, loc))
                        graph.remove_ins(loc)
                        change = True