Skip to content

Loop invariant code motion

loop_invariant_code_motion

This pass hoists operation that are invariant to the loops.

Similar to MLIR's loop invariant code motion: see external documentation.

An operation is loop-invariant if it depends only of values defined outside of the loop. LICM moves these operations out of the loop body so that they are not computed more than once.

LoopInvariantCodeMotion

Bases: RewritePattern

Source code in xdsl/transforms/loop_invariant_code_motion.py 
86
87
88
89
class LoopInvariantCodeMotion(RewritePattern):
    @op_type_rewrite_pattern
    def match_and_rewrite(self, op: scf.ForOp, rewriter: PatternRewriter) -> None:
        move_loop_invariant_code(op)

match_and_rewrite(op: scf.ForOp, rewriter: PatternRewriter) -> None

Source code in xdsl/transforms/loop_invariant_code_motion.py 
87
88
89
@op_type_rewrite_pattern
def match_and_rewrite(self, op: scf.ForOp, rewriter: PatternRewriter) -> None:
    move_loop_invariant_code(op)

LoopInvariantCodeMotionPass dataclass

Bases: ModulePass

Moves operations without side effects out of loops, provided they do not depend on values defined in the loops.

Source code in xdsl/transforms/loop_invariant_code_motion.py 
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
class LoopInvariantCodeMotionPass(ModulePass):
    """
    Moves operations without side effects out of loops, provided they do not depend on
    values defined in the loops.
    """

    name = "licm"

    def apply(self, ctx: Context, op: builtin.ModuleOp) -> None:
        PatternRewriteWalker(
            LoopInvariantCodeMotion(),
            apply_recursively=False,
            walk_regions_first=True,
        ).rewrite_module(op)

name = 'licm' class-attribute instance-attribute

apply(ctx: Context, op: builtin.ModuleOp) -> None

Source code in xdsl/transforms/loop_invariant_code_motion.py 
100
101
102
103
104
105
def apply(self, ctx: Context, op: builtin.ModuleOp) -> None:
    PatternRewriteWalker(
        LoopInvariantCodeMotion(),
        apply_recursively=False,
        walk_regions_first=True,
    ).rewrite_module(op)

can_be_hoisted(op: Operation, target_region: Region) -> bool | None

Checks whether the given op can be hoisted by checking that - the op and none of its contained operations depend on values inside of the loop.

Source code in xdsl/transforms/loop_invariant_code_motion.py 
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
def can_be_hoisted(op: Operation, target_region: Region) -> bool | None:
    """
    Checks whether the given op can be hoisted by checking that
    - the op and none of its contained operations depend on values inside of the
     loop.
    """
    #  Do not move terminators.
    if op.has_trait(IsTerminator):
        return False

    # Walk the nested operations and check that all used values are either
    # defined outside of the loop or in a nested region, but not at the level of
    # the loop body.
    for child in op.walk():
        for operand in child.operands:
            operand_owner = operand.owner
            if op.is_ancestor(operand_owner):
                continue
            if target_region.is_ancestor(operand_owner):
                return False
    return True

move_loop_invariant_code(loop: scf.ForOp)

Source code in xdsl/transforms/loop_invariant_code_motion.py 
81
82
83
def move_loop_invariant_code(loop: scf.ForOp):
    builder = Builder(InsertPoint.before(loop))
    _move_loop_invariant_code(loop.body, builder)