def remove_dead_exceptions(graph):
    """Exceptions can be removed if they are unreachable"""

    clastexc = c_last_exception

    def issubclassofmember(cls, seq):
        for member in seq:
            if member and issubclass(cls, member):
                return True
        return False

    def visit(block):
        if not (isinstance(block, Block) and block.exitswitch == clastexc):
            return
        exits = []
        seen = []
        for link in block.exits:
            case = link.exitcase
            # check whether exceptions are shadowed
            if issubclassofmember(case, seen):
                continue
            # see if the previous case can be merged
            while len(exits) > 1:
                prev = exits[-1]
                if not (issubclass(prev.exitcase, link.exitcase) and
                    prev.target is link.target and prev.args == link.args):
                    break
                exits.pop()
            exits.append(link)
            seen.append(case)
        block.recloseblock(*exits)

    traverse(visit, graph)

 def test_jump_target_specialization(self):
     x = self.codetest(self.jump_target_specialization)
     def visitor(node):
         if isinstance(node, Block):
             for op in node.operations:
                 assert op.opname != 'mul', "mul should have disappeared"
     traverse(visitor, x)

def remove_assertion_errors(graph):
    """Remove branches that go directly to raising an AssertionError,
    assuming that AssertionError shouldn't occur at run-time.  Note that
    this is how implicit exceptions are removed (see _implicit_ in
    flowcontext.py).
    """
    def visit(block):
        if isinstance(block, Block):
            for i in range(len(block.exits)-1, -1, -1):
                exit = block.exits[i]
                if not (exit.target is graph.exceptblock and
                        exit.args[0] == Constant(AssertionError)):
                    continue
                # can we remove this exit without breaking the graph?
                if len(block.exits) < 2:
                    break
                if block.exitswitch == c_last_exception:
                    if exit.exitcase is None:
                        break
                    if len(block.exits) == 2:
                        # removing the last non-exceptional exit
                        block.exitswitch = None
                        exit.exitcase = None
                # remove this exit
                lst = list(block.exits)
                del lst[i]
                block.recloseblock(*lst)
    traverse(visit, graph)

def eliminate_empty_blocks(graph):
    """Eliminate basic blocks that do not contain any operations.
    When this happens, we need to replace the preceeding link with the
    following link.  Arguments of the links should be updated."""
    def visit(link):
        if isinstance(link, Link):
            while not link.target.operations:
                block1 = link.target
                if block1.exitswitch is not None:
                    break
                if not block1.exits:
                    break
                exit = block1.exits[0]
                assert block1 is not exit.target, (
                    "the graph contains an empty infinite loop")
                outputargs = []
                for v in exit.args:
                    if isinstance(v, Variable):
                        # this variable is valid in the context of block1
                        # but it must come from 'link'
                        i = block1.inputargs.index(v)
                        v = link.args[i]
                    outputargs.append(v)
                link.args = outputargs
                link.target = exit.target
                # the while loop above will simplify recursively the new link
    traverse(visit, graph)

 def test_implicitAttributeError(self):
     x = self.codetest(self.implicitAttributeError)
     simplify_graph(x)
     self.show(x)
     def cannot_reach_exceptblock(link):
         if isinstance(link, Link):
             assert link.target is not x.exceptblock
     traverse(cannot_reach_exceptblock, x)

 def all_operations(self, graph):
     result = {}
     def visit(node):
         if isinstance(node, Block):
             for op in node.operations:
                 result.setdefault(op.opname, 0)
                 result[op.opname] += 1
     traverse(visit, graph)
     return result

 def test_reraiseTypeError(self):
     x = self.codetest(self.reraiseTypeError)
     simplify_graph(x)
     self.show(x)
     found = []
     def can_reach_exceptblock(link):
         if isinstance(link, Link):
             if link.target is x.exceptblock:
                 found.append(link)                
     traverse(can_reach_exceptblock, x)
     assert found

 def test_reraiseAnything(self):
     x = self.codetest(self.reraiseAnything)
     simplify_graph(x)
     self.show(x)
     found = {}
     def find_exceptions(link):
         if isinstance(link, Link):
             if link.target is x.exceptblock:
                 assert isinstance(link.args[0], Constant)
                 found[link.args[0].value] = True
     traverse(find_exceptions, x)
     assert found == {ValueError: True, ZeroDivisionError: True, OverflowError: True}

 def test_reraiseAttributeError(self):
     x = self.codetest(self.reraiseAttributeError)
     simplify_graph(x)
     self.show(x)
     found_AttributeError = []
     def only_raise_AttributeError(link):
         if isinstance(link, Link):
             if link.target is x.exceptblock:
                 assert link.args[0] == Constant(AttributeError)
                 found_AttributeError.append(link)
     traverse(only_raise_AttributeError, x)
     assert found_AttributeError

 def test_const_star_call(self):
     def g(a=1,b=2,c=3):
         pass
     def f():
         return g(1,*(2,3))
     graph = self.codetest(f)
     call_args = []
     def visit(block):
         if isinstance(block, Block):
             for op in block.operations:
                 if op.opname == "call_args":
                     call_args.append(op)
     traverse(visit, graph)
     assert not call_args

 def test_reraiseAnythingDicCase(self):
     x = self.codetest(self.reraiseAnythingDicCase)
     simplify_graph(x)
     self.show(x)
     found = {}
     def find_exceptions(link):
         if isinstance(link, Link):
             if link.target is x.exceptblock:
                 if isinstance(link.args[0], Constant):
                     found[link.args[0].value] = True
                 else:
                     found[link.exitcase] = None
     traverse(find_exceptions, x)
     assert found == {IndexError: True, KeyError: True, Exception: None}

 def test_reraiseTypeError(self):
     x = self.codetest(self.reraiseTypeError)
     simplify_graph(x)
     self.show(x)
     excfound = []
     def check(link):
         if isinstance(link, Link):
             if link.target is x.exceptblock:
                 excfound.append(link.exitcase)
     traverse(check, x)
     assert len(excfound) == 2
     excfound.sort()
     expected = [Exception, TypeError]
     expected.sort()
     assert excfound == expected

 def patch_graphs(self):
     def patch_consts(args):
         for arg in args:
             if isinstance(arg, Constant) and arg in self.constants:
                 arg.value = self.constants[arg]
     def visit(obj):
         if isinstance(obj, Link):
             patch_consts(obj.args)
             if (hasattr(obj, "llexitcase") and
                 Constant(obj.llexitcase) in self.constants):
                 obj.llexitcase = self.constants[Constant(obj.llexitcase)]
         elif isinstance(obj, Block):
             for op in obj.operations:
                 patch_consts(op.args)
     for graph in self.graphs:
         traverse(visit, graph)

def graph_footprint(graph):
    class Counter:
        blocks = 0
        links = 0
        ops = 0

    count = Counter()

    def visit(block):
        if isinstance(block, flowmodel.Block):
            count.blocks += 1
            count.ops += len(block.operations)
        elif isinstance(block, flowmodel.Link):
            count.links += 1

    flowmodel.traverse(visit, graph)
    return count.blocks, count.links, count.ops

def ordered_blocks(graph):
    # collect all blocks
    allblocks = []
    def visit(block):
        if isinstance(block, Block):
            # first we order by offset in the code string
            if block.operations:
                ofs = block.operations[0].offset
            else:
                ofs = sys.maxint
            # then we order by input variable name or value
            if block.inputargs:
                txt = str(block.inputargs[0])
            else:
                txt = "dummy"
            allblocks.append((ofs, txt, block))
    traverse(visit, graph)
    allblocks.sort()
    #for ofs, txt, block in allblocks:
    #    print ofs, txt, block
    return [block for ofs, txt, block in allblocks]

    def compute_lifetimes(self, graph):
        """Compute the static data flow of the graph: returns a list of LifeTime
        instances, each of which corresponds to a set of Variables from the graph.
        The variables are grouped in the same LifeTime if a value can pass from
        one to the other by following the links.  Each LifeTime also records all
        places where a Variable in the set is used (read) or build (created).
        """
        lifetimes = UnionFind(LifeTime)

        def set_creation_point(block, var, *cp):
            _, _, info = lifetimes.find((block, var))
            info.creationpoints[cp] = True

        def set_use_point(block, var, *up):
            _, _, info = lifetimes.find((block, var))
            info.usepoints[up] = True

        def union(block1, var1, block2, var2):
            if isinstance(var1, Variable):
                lifetimes.union((block1, var1), (block2, var2))
            elif isinstance(var1, Constant):
                set_creation_point(block2, var2, "constant", var1)
            else:
                raise TypeError(var1)

        for var in graph.startblock.inputargs:
            set_creation_point(graph.startblock, var, "inputargs")
        set_use_point(graph.returnblock, graph.returnblock.inputargs[0], "return")
        set_use_point(graph.exceptblock, graph.exceptblock.inputargs[0], "except")
        set_use_point(graph.exceptblock, graph.exceptblock.inputargs[1], "except")

        def visit(node):
            if isinstance(node, Block):
                for op in node.operations:
                    if op.opname in self.IDENTITY_OPS:
                        # special-case these operations to identify their input
                        # and output variables
                        union(node, op.args[0], node, op.result)
                        continue
                    if op.opname in self.SUBSTRUCT_OPS:
                        if self.visit_substruct_op(node, union, op):
                            continue
                    for i in range(len(op.args)):
                        if isinstance(op.args[i], Variable):
                            set_use_point(node, op.args[i], "op", node, op, i)
                    set_creation_point(node, op.result, "op", node, op)
                if isinstance(node.exitswitch, Variable):
                    set_use_point(node, node.exitswitch, "exitswitch", node)

            if isinstance(node, Link):
                if isinstance(node.last_exception, Variable):
                    set_creation_point(node.prevblock, node.last_exception,
                                       "last_exception")
                if isinstance(node.last_exc_value, Variable):
                    set_creation_point(node.prevblock, node.last_exc_value,
                                       "last_exc_value")
                d = {}
                for i, arg in enumerate(node.args):
                    union(node.prevblock, arg,
                          node.target, node.target.inputargs[i])
                    if isinstance(arg, Variable):
                        if arg in d:
                            # same variable present several times in link.args
                            # consider it as a 'use' of the variable, which
                            # will disable malloc optimization (aliasing problems)
                            set_use_point(node.prevblock, arg, "dup", node, i)
                        else:
                            d[arg] = True

        traverse(visit, graph)
        return lifetimes.infos()

def sanity_check(t):
    # look for missing '.concretetype'
    for graph in t.graphs:
        checkgraph(graph)
        traverse(no_missing_concretetype, graph)

def simplify_exceptions(graph):
    """The exception handling caused by non-implicit exceptions
    starts with an exitswitch on Exception, followed by a lengthy
    chain of is_/issubtype tests. We collapse them all into
    the block's single list of exits.
    """
    clastexc = c_last_exception
    renaming = {}
    def rename(v):
        return renaming.get(v, v)

    def visit(block):
        if not (isinstance(block, Block)
                and block.exitswitch == clastexc
                and block.exits[-1].exitcase is Exception):
            return
        covered = [link.exitcase for link in block.exits[1:-1]]
        seen = []
        preserve = list(block.exits[:-1])
        exc = block.exits[-1]
        last_exception = exc.last_exception
        last_exc_value = exc.last_exc_value
        query = exc.target
        switches = []
        # collect the targets
        while len(query.exits) == 2:
            newrenaming = {}
            for lprev, ltarg in zip(exc.args, query.inputargs):
                newrenaming[ltarg] = rename(lprev)
            op = query.operations[0]
            if not (op.opname in ("is_", "issubtype") and
                    newrenaming.get(op.args[0]) == last_exception):
                break
            renaming.update(newrenaming)
            case = query.operations[0].args[-1].value
            assert issubclass(case, py.builtin.BaseException)
            lno, lyes = query.exits
            assert lno.exitcase == False and lyes.exitcase == True
            if case not in seen:
                is_covered = False
                for cov in covered:
                    if issubclass(case, cov):
                        is_covered = True
                        break
                if not is_covered:
                    switches.append( (case, lyes) )
                seen.append(case)
            exc = lno
            query = exc.target
        if Exception not in seen:
            switches.append( (Exception, exc) )
        # construct the block's new exits
        exits = []
        for case, oldlink in switches:
            link = oldlink.copy(rename)
            assert case is not None
            link.last_exception = last_exception
            link.last_exc_value = last_exc_value
            # make the above two variables unique
            renaming2 = {}
            def rename2(v):
                return renaming2.get(v, v)
            for v in link.getextravars():
                renaming2[v] = Variable(v)
            link = link.copy(rename2)
            link.exitcase = case
            link.prevblock = block
            exits.append(link)
        block.recloseblock(*(preserve + exits))

    traverse(visit, graph)