Skip to content

Warning

This page is under construction. The content may be incomplete or incorrect. Submit an issue on GitHub if you need help or want to contribute.

The Control Flow Dialect

The control flow dialect provides the most generic control flow semantics via cf.Branch and cf.ConditionalBranch.

cf.Branch

the cf.Branch statement is used to mark how basic block branches to another basic block without condition. This represents an edge on the control flow graph (CFG).

^1(%2):
  │   %y = py.constant.constant 1 : !py.int
  │        cf.br ^3(%y)
  ^2(%3):
  │ %y_1 = py.constant.constant 2 : !py.int
  │        cf.br ^3(%y_1)
  ^3(%y_2):
  │        func.return %y_2

Definition the cf.Branch statement takes a successor block and its argument. The cf.Branch is a terminator thus it should always be the last statement of a block.

Note

ir.Statement does not own any ir.Block, the ir.Region owns blocks. The ir.Statement will only own ir.Region. In Kirin, we use similar design as LLVM/MLIR where the phi nodes in SSA form are replaced by block arguments.

cf.ConditionalBranch

The cf.ConditionalBranch statement represents a conditional branching statement that looks like following (the cf.cond_br statement):

^0(%main_self, %x):
│   %0 = py.constant.constant 1 : !py.int
│   %1 = py.cmp.gt(lhs=%x, rhs=%0) : !py.bool
│        cf.cond_br %1 goto ^1(%1) else ^2(%1)

Definition, cf.ConditionalBranch takes a boolean condition cond of type ir.SSAValue and:

  • then successor and its argument
  • else successor and its argument

this statement is also a terminator, which means it must be the last statement of a block.

Combining together - lowering from Python

Now combining these two statemente together, we can represent most of the Python control flows, e.g if-else and for-loops. These two statement basically just provides a basic way describing the edges on a control flow graph (CFG) by assuming the node only has one or two outgoing edges.

As an example, the following Python program:

from kirin.prelude import basic_no_opt

@basic_no_opt
def main(x):
    if x > 1:
        y = 1
    else:
        y = 2
    return y

will be lowered to the following SSA form in cf dialect:

func.func main(!Any) -> !Any {
  ^0(%main_self, %x):
  │   %0 = py.constant.constant 1 : !py.int
  │   %1 = py.cmp.gt(lhs=%x, rhs=%0) : !py.bool
  │        cf.cond_br %1 goto ^1(%1) else ^2(%1)
  ^1(%2):
  │   %y = py.constant.constant 1 : !py.int
  │        cf.br ^3(%y)
  ^2(%3):
  │ %y_1 = py.constant.constant 2 : !py.int
  │        cf.br ^3(%y_1)
  ^3(%y_2):
  │        func.return %y_2
} // func.func main

And similarly, we can lower a for-loop into the cf dialect:

@basic_no_opt
def main(x):
    for i in range(5):
        x = x + i
    return x

will be lowered into the following SSA form:

func.func main(!Any) -> !Any {
  ^0(%main_self, %x_1):
  │ %0 = py.constant.constant 0 : !py.int
  │ %1 = py.constant.constant 5 : !py.int
  │ %2 = py.constant.constant 1 : !py.int
  │ %3 = py.range.range(start=%0, stop=%1, step=%2) : !py.range
  │ %4 = py.iterable.iter(value=%3) : !Any
  │ %5 = py.constant.constant None : !py.NoneType
  │ %6 = py.iterable.next(iter=%4) : !Any
  │ %7 = py.cmp.is(lhs=%6, rhs=%5) : !py.bool
  │      cf.cond_br %7 goto ^2(%x_1) else ^1(%6, %x_1)
  ^1(%i, %x_2):
  │ %x = py.binop.add(%x_2, %i) : ~T
  │ %8 = py.iterable.next(iter=%4) : !Any
  │ %9 = py.cmp.is(lhs=%8, rhs=%5) : !py.bool
  │      cf.cond_br %9 goto ^2(%x) else ^1(%8, %x)
  ^2(%x_3):
  │      func.return %x_3
} // func.func main

However, as you may already notice, lowering from Python directly to cf dialect will lose some of the high-level information such as the control flow is actually a for-loop. This information can be useful when one wants to perform some optimization. This is why we are taking the same route as MLIR with a structural IR (via ir.Regions). For the interested readers, please proceed to Structural Control Flow for further reading.

API Reference

Branch dataclass 

Branch(
    *,
    args: Sequence[SSAValue] = (),
    regions: Sequence[Region] = (),
    successors: Sequence[Block] = (),
    attributes: Mapping[str, Attribute] = {},
    results: Sequence[ResultValue] = (),
    result_types: Sequence[TypeAttribute] = (),
    args_slice: Mapping[str, int | slice] = {},
    source: SourceInfo | None = None
)

Bases: Statement


              flowchart TD
              kirin.dialects.cf.stmts.Branch[Branch]
              kirin.ir.nodes.stmt.Statement[Statement]
              kirin.ir.nodes.base.IRNode[IRNode]
              kirin.print.printable.Printable[Printable]

                              kirin.ir.nodes.stmt.Statement --> kirin.dialects.cf.stmts.Branch
                                kirin.ir.nodes.base.IRNode --> kirin.ir.nodes.stmt.Statement
                                kirin.print.printable.Printable --> kirin.ir.nodes.base.IRNode
                




              click kirin.dialects.cf.stmts.Branch href "" "kirin.dialects.cf.stmts.Branch"
              click kirin.ir.nodes.stmt.Statement href "" "kirin.ir.nodes.stmt.Statement"
              click kirin.ir.nodes.base.IRNode href "" "kirin.ir.nodes.base.IRNode"
              click kirin.print.printable.Printable href "" "kirin.print.printable.Printable"
Source code in src/kirin/ir/nodes/stmt.py 
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
def __init__(
    self,
    *,
    args: Sequence[SSAValue] = (),
    regions: Sequence[Region] = (),
    successors: Sequence[Block] = (),
    attributes: Mapping[str, Attribute] = {},
    results: Sequence[ResultValue] = (),
    result_types: Sequence[TypeAttribute] = (),
    args_slice: Mapping[str, int | slice] = {},
    source: SourceInfo | None = None,
) -> None:
    super().__init__()
    """Initialize the Statement.

    Args:
        arsg (Sequence[SSAValue], optional): The arguments of the Statement. Defaults to ().
        regions (Sequence[Region], optional): The regions where the Statement belong to. Defaults to ().
        successors (Sequence[Block], optional): The successors of the Statement. Defaults to ().
        attributes (Mapping[str, Attribute], optional): The attributes of the Statement. Defaults to {}.
        results (Sequence[ResultValue], optional): The result values of the Statement. Defaults to ().
        result_types (Sequence[TypeAttribute], optional): The result types of the Statement. Defaults to ().
        args_slice (Mapping[str, int | slice], optional): The arguments slice of the Statement. Defaults to {}.
        source (SourceInfo | None, optional): The source information of the Statement for debugging/stacktracing. Defaults to None.

    """
    self._args = ()
    self._regions = []
    self._name_args_slice = dict(args_slice)
    self.source = source
    self.args = args

    if results:
        self._results = list(results)
        assert (
            len(result_types) == 0
        ), "expect either results or result_types specified, got both"

    if result_types:
        self._results = [
            ResultValue(self, idx, type=type)
            for idx, type in enumerate(result_types)
        ]

    if not results and not result_types:
        self._results = list(results)

    self.successors = list(successors)
    self.attributes = dict(attributes)
    self.regions = list(regions)

    self.parent = None
    self._next_stmt = None
    self._prev_stmt = None
    self.__post_init__()

arguments instance-attribute 

arguments: tuple[SSAValue, ...]

name class-attribute instance-attribute 

name = 'br'

successor class-attribute instance-attribute 

successor: Block = block()

traits class-attribute instance-attribute 

traits = frozenset({IsTerminator()})

print_impl 

print_impl(printer: Printer) -> None
Source code in src/kirin/dialects/cf/stmts.py 
18
19
20
21
22
23
24
25
26
27
28
29
def print_impl(self, printer: Printer) -> None:
    with printer.rich(style="keyword"):
        printer.print_name(self)

    printer.plain_print(" ")
    printer.plain_print(printer.state.block_id[self.successor])
    printer.print_seq(
        self.arguments,
        delim=", ",
        prefix="(",
        suffix=")",
    )

verify 

verify() -> None

run mandatory validation checks. This is not same as verify_type, which may be optional.

Source code in src/kirin/dialects/cf/stmts.py 
15
16
def verify(self) -> None:
    return

ConditionalBranch dataclass 

ConditionalBranch(
    *,
    args: Sequence[SSAValue] = (),
    regions: Sequence[Region] = (),
    successors: Sequence[Block] = (),
    attributes: Mapping[str, Attribute] = {},
    results: Sequence[ResultValue] = (),
    result_types: Sequence[TypeAttribute] = (),
    args_slice: Mapping[str, int | slice] = {},
    source: SourceInfo | None = None
)

Bases: Statement


              flowchart TD
              kirin.dialects.cf.stmts.ConditionalBranch[ConditionalBranch]
              kirin.ir.nodes.stmt.Statement[Statement]
              kirin.ir.nodes.base.IRNode[IRNode]
              kirin.print.printable.Printable[Printable]

                              kirin.ir.nodes.stmt.Statement --> kirin.dialects.cf.stmts.ConditionalBranch
                                kirin.ir.nodes.base.IRNode --> kirin.ir.nodes.stmt.Statement
                                kirin.print.printable.Printable --> kirin.ir.nodes.base.IRNode
                




              click kirin.dialects.cf.stmts.ConditionalBranch href "" "kirin.dialects.cf.stmts.ConditionalBranch"
              click kirin.ir.nodes.stmt.Statement href "" "kirin.ir.nodes.stmt.Statement"
              click kirin.ir.nodes.base.IRNode href "" "kirin.ir.nodes.base.IRNode"
              click kirin.print.printable.Printable href "" "kirin.print.printable.Printable"
Source code in src/kirin/ir/nodes/stmt.py 
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
def __init__(
    self,
    *,
    args: Sequence[SSAValue] = (),
    regions: Sequence[Region] = (),
    successors: Sequence[Block] = (),
    attributes: Mapping[str, Attribute] = {},
    results: Sequence[ResultValue] = (),
    result_types: Sequence[TypeAttribute] = (),
    args_slice: Mapping[str, int | slice] = {},
    source: SourceInfo | None = None,
) -> None:
    super().__init__()
    """Initialize the Statement.

    Args:
        arsg (Sequence[SSAValue], optional): The arguments of the Statement. Defaults to ().
        regions (Sequence[Region], optional): The regions where the Statement belong to. Defaults to ().
        successors (Sequence[Block], optional): The successors of the Statement. Defaults to ().
        attributes (Mapping[str, Attribute], optional): The attributes of the Statement. Defaults to {}.
        results (Sequence[ResultValue], optional): The result values of the Statement. Defaults to ().
        result_types (Sequence[TypeAttribute], optional): The result types of the Statement. Defaults to ().
        args_slice (Mapping[str, int | slice], optional): The arguments slice of the Statement. Defaults to {}.
        source (SourceInfo | None, optional): The source information of the Statement for debugging/stacktracing. Defaults to None.

    """
    self._args = ()
    self._regions = []
    self._name_args_slice = dict(args_slice)
    self.source = source
    self.args = args

    if results:
        self._results = list(results)
        assert (
            len(result_types) == 0
        ), "expect either results or result_types specified, got both"

    if result_types:
        self._results = [
            ResultValue(self, idx, type=type)
            for idx, type in enumerate(result_types)
        ]

    if not results and not result_types:
        self._results = list(results)

    self.successors = list(successors)
    self.attributes = dict(attributes)
    self.regions = list(regions)

    self.parent = None
    self._next_stmt = None
    self._prev_stmt = None
    self.__post_init__()

cond class-attribute instance-attribute 

cond: SSAValue = argument(Bool)

else_arguments instance-attribute 

else_arguments: tuple[SSAValue, ...]

else_successor class-attribute instance-attribute 

else_successor: Block = block()

name class-attribute instance-attribute 

name = 'cond_br'

then_arguments instance-attribute 

then_arguments: tuple[SSAValue, ...]

then_successor class-attribute instance-attribute 

then_successor: Block = block()

traits class-attribute instance-attribute 

traits = frozenset({IsTerminator()})

print_impl 

print_impl(printer: Printer) -> None
Source code in src/kirin/dialects/cf/stmts.py 
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
def print_impl(self, printer: Printer) -> None:
    with printer.rich(style="keyword"):
        printer.print_name(self)

    printer.plain_print(" ")
    printer.print(self.cond)

    with printer.rich(style="keyword"):
        printer.plain_print(" goto ")

    printer.plain_print(printer.state.block_id[self.then_successor])
    printer.plain_print("(")
    printer.print_seq(self.then_arguments, delim=", ")
    printer.plain_print(")")

    with printer.rich(style="keyword"):
        printer.plain_print(" else ")

    printer.plain_print(printer.state.block_id[self.else_successor])
    printer.plain_print("(")
    printer.print_seq(self.else_arguments, delim=", ")
    printer.plain_print(")")

verify 

verify() -> None

run mandatory validation checks. This is not same as verify_type, which may be optional.

Source code in src/kirin/dialects/cf/stmts.py 
67
68
def verify(self) -> None:
    return