Skip to content

Post order

post_order

PostOrderIterator dataclass

Bases: Iterator[Block]

Iterates through blocks in a region by a depth first search in post order. Each block's successors are processed before the block itself (unless they have already been encounted).

Blocks that are not reachable from the starting block will not appear in the iteration.

Source code in xdsl/ir/post_order.py 
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
@dataclass(init=False)
class PostOrderIterator(Iterator[Block]):
    """
    Iterates through blocks in a region by a depth first search in post order.
    Each block's successors are processed before the block itself (unless they
    have already been encounted).

    Blocks that are not reachable from the starting block will not appear in the
    iteration.
    """

    stack: list[tuple[Block, bool]]
    seen: set[Block]

    def __init__(self, block: Block) -> None:
        self.stack = [(block, False)]
        self.seen = {block}

    def __iter__(self) -> Self:
        return self

    def __next__(self) -> Block:
        if not self.stack:
            raise StopIteration
        (block, visited) = self.stack.pop()
        while not visited:
            self.stack.append((block, True))
            term = block.last_op
            if isinstance(term, Operation) and term.has_trait(IsTerminator()):
                self.stack.extend(
                    (x, False) for x in reversed(term.successors) if x not in self.seen
                )
                self.seen.update(term.successors)
            # stack cannot be empty here
            (block, visited) = self.stack.pop()
        return block

stack: list[tuple[Block, bool]] = [(block, False)] instance-attribute

seen: set[Block] = {block} instance-attribute

__init__(block: Block) -> None

Source code in xdsl/ir/post_order.py 
24
25
26
def __init__(self, block: Block) -> None:
    self.stack = [(block, False)]
    self.seen = {block}

__iter__() -> Self

Source code in xdsl/ir/post_order.py 
28
29
def __iter__(self) -> Self:
    return self

__next__() -> Block

Source code in xdsl/ir/post_order.py 
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
def __next__(self) -> Block:
    if not self.stack:
        raise StopIteration
    (block, visited) = self.stack.pop()
    while not visited:
        self.stack.append((block, True))
        term = block.last_op
        if isinstance(term, Operation) and term.has_trait(IsTerminator()):
            self.stack.extend(
                (x, False) for x in reversed(term.successors) if x not in self.seen
            )
            self.seen.update(term.successors)
        # stack cannot be empty here
        (block, visited) = self.stack.pop()
    return block