Week 2: GSoC Project Progress

Hours this week: 21

Total hours: 37

At the end of the first week, I had the following tasks to work upon:

First, to figure out the ASR dialect for the LFortran compiler.
Second, to figure the alternative for MachO backend, for x86_64 architecture.

Continuing from here, this week, I focused on the first task, to figure out the ASR dialect for the LFortran compiler. This week, I focused on the right syntax for the ASR dialect. This report contains the details of the implementation, my approach and reasoning behind it, and current status of the implementation. Since this task is very important for the project, I have spent a lot of time on it, and have tried multiple approaches to get the right syntax for the ASR dialect. Few of the important approaches, which summarize my key learnings are discussed here.

The mlir-new backend targets the following pipeline:

flowchart TB A["Initial ASR"] --> B["asr.* dialect"] B --> C["func / memref / arith / cf"] C --> D["LLVM dialect"] D --> E["LLVM IR"]

The ASR dialect shall act as a boundary between LFortran’s semantic ASR and the generic high-level MLIR that eventually lowers to LLVM. That boundary exists so that ASR and MLIR ecosystem can be separate. Any individual ASR node changes result in changes only ASR to ASR dialect conversion, without affecting the later MLIR lowering stages.

The approaches I tried, and the reasoning and learnings from them are as follows:

Approach 1: Lowering ASR nodes to FIR and HLFIR.

FIR and HLFIR are two fortran specific dialects that are used by the Flang compiler. FIR is a low-level dialect that is used by the Flang compiler to represent the fortran language. HLFIR is a high-level dialect that is used by the Flang compiler to represent the fortran language. Since these dialects are fortran specific, my begining approach was to try to lower the ASR nodes to these dialects.

Here, I tried lowering the ASR nodes to these dialects, and then using certik/mlir dialects to lower further. However, I quickly encountered the following issues:

When lowering ASR nodes to FIR, I observed that FIR is a relatively lower-level dialect. While FIR is designed to support a broad range of Fortran constructs, support for some high-level constructs like do loops may not be direct or may require prior transformation (for example, by lowering them into control flow primitives or other FIR constructs). Thus, certain Fortran features, such as do loops, might not be represented explicitly in FIR but rather as a sequence of more primitive operations. Once we lower into these form, we lose the ability to represent the ASR tree in a way that is easy to understand and debug. Also, our ASR has a property that it can be converted back to a valid fortran program, and this property is lost when we lower to FIR. Hence, this approach is not suitable for our use case.
Next, HLFIR is a high level dialect, which was developed by Flang as lowering from fortran to FIR was a very big jump, in terms of alot of decisions to make in 1 step. However, HLFIR also had few issues with LFortran ASR. HLFIR is made for Flang’s syntax of handling Fortran after parsing and analysis, but LFortran’s ASR is different. ASR has its own node types, type system, symbol tables, and rules. Many ASR nodes like ArrayPhysicalCast do not have a direct mapping in HLFIR. So, lowering ASR to HLFIR would need many extra translation steps. This makes things complicated and makes it difficult to keep the dialect close to ASR and easy to debug or convert back. Hence, this approach is not suitable for our use case.

Approach-2 & Approach-3: Alternate designs for ASR dialect

Based on this branch, the initial ASR dialect implementation follows these foundational principles for syntax:

Consider the following example:

program print_01
  implicit none
  integer(kind=4) :: x, i 
  integer :: a(3)
  a = [1, 2, 3]
  do i = 1, 10
    x = i + 5
  end do
  print *, x
  print *, a
end program

When translating this program directly from ASR to ASR Dialect, without any changes, the approach would be as follows:

$ LFORTRAN_ASR_DIALECT_DUMP=debug lfortran a.f90 --show-mlir-asr-dialect
module() {
^bb0:
    "asr.translation_unit"() {asr.op_kind = 246, asr.f.symtab = 0, asr.f.items = -421973552}
    "asr.program"() {asr.op_kind = 215, asr.f.symtab = 0, asr.f.name = "print_01", asr.f.dependencies = -1923627856, asr.f.body = 0, asr.f.start_name = 0, asr.f.end_name = 0}
    "asr.variable"() {asr.op_kind = 221, asr.f.parent_symtab = 0, asr.f.name = "a", asr.f.dependencies = -1923627856, asr.f.intent = 0, asr.f.symbolic_value = 0, asr.f.value = 0, asr.f.storage = 0, asr.f.type = memref<3xi4>, asr.f.type_declaration = "", asr.f.abi = 0, asr.f.access = 0, asr.f.presence = 0, asr.f.value_attr = false, asr.f.target_attr = false, asr.f.contiguous_attr = false, asr.f.bindc_name = "", asr.f.is_volatile = false, asr.f.is_protected = false, asr.f.pass_attr = 0, asr.f.self_argument = "", asr.f.codims = 0, asr.f.array_len = 3}
    "asr.variable"() {asr.op_kind = 221, asr.f.parent_symtab = 0, asr.f.name = "i", asr.f.dependencies = -1923627856, asr.f.intent = 0, asr.f.symbolic_value = 0, asr.f.value = 0, asr.f.storage = 0, asr.f.type = i4, asr.f.type_declaration = "", asr.f.abi = 0, asr.f.access = 0, asr.f.presence = 0, asr.f.value_attr = false, asr.f.target_attr = false, asr.f.contiguous_attr = false, asr.f.bindc_name = "", asr.f.is_volatile = false, asr.f.is_protected = false, asr.f.pass_attr = 0, asr.f.self_argument = "", asr.f.codims = 0}
    "asr.variable"() {asr.op_kind = 221, asr.f.parent_symtab = 0, asr.f.name = "x", asr.f.dependencies = -1923627856, asr.f.intent = 0, asr.f.symbolic_value = 0, asr.f.value = 0, asr.f.storage = 0, asr.f.type = i4, asr.f.type_declaration = "", asr.f.abi = 0, asr.f.access = 0, asr.f.presence = 0, asr.f.value_attr = false, asr.f.target_attr = false, asr.f.contiguous_attr = false, asr.f.bindc_name = "", asr.f.is_volatile = false, asr.f.is_protected = false, asr.f.pass_attr = 0, asr.f.self_argument = "", asr.f.codims = 0}
    "asr.assignment"() {asr.op_kind = 150, asr.f.target = -1802851888, asr.f.value = -1803494624, asr.f.overloaded = 0, asr.f.realloc_lhs = false, asr.f.move_allocation = false}
    "asr.do_loop"() {asr.op_kind = 160, asr.f.name = "", asr.f.head = -1802840544, asr.f.body = 979635568, asr.f.orelse = 0}
    "asr.print"() {asr.op_kind = 190, asr.f.text = -1802839072}
    "asr.print"() {asr.op_kind = 190, asr.f.text = -1802833808}
    "asr.return"() {asr.op_kind = 192}
}

Here, we can see that the syntax is not very readable. We reveal a lot of internal implementation details, and numeric IDs, which are not very useful for the user. All of the imeplemtation gets buried in the internal IDs, and the users have no way to understand the code. Majority of the fields have no important information for the end user as well. Hence, we need a clear syntax, which can be readable for the user.

Working on the above points, more cleaner ASR dialect syntax for this program would be as follows:

$ LFORTRAN_ASR_DIALECT_DUMP=compact lfortran a.f90 --show-mlir-asr-dialect
module {
  asr.translation_unit {
    asr.program @print_01 {
      asr.variable @a : i32[3]
        type_declaration = ""
      asr.variable @i : i32
        type_declaration = ""
      asr.variable @x : i32
        type_declaration = ""
      asr.assign @a = [1, 2, 3]
      asr.do_loop @i = 1 to 10 {
        asr.assign @x = @i + 5 : i32
      }
      asr.print @x
      asr.print @a
      asr.return
    }
  }
}

However, both of these approaches have a few issues: Here, the code is readable for the user, but we drop crucial ASR information, which might be required for the further lowering. ASR Fields such as kind, intent, ABI might be required for the further lowering, and these fields are not present here in the syntax. So, based on the two approaches, we face a dilemna. Our ASR has a lot of fields, like Intent, ABI etc, which might not be needed for every variable, but when we need them, they must be present at LLVM lowering for proper handling. So, this made designing trickier, as there are two challenges:

Identifying the important fields in current ASR Nodes will be trickier, since we need to be prepared to handle all edge cases, combinations which might pop up. For example, Intent might be irrelevant for normal programs, but when a variable is inside a function, Intent is important.
Having all fields for all ASR Nodes for ASR Dialect, made readability worse.

So, here there needs to be a trade-off, regarding when a particular value is different from some default state, which I found was very tricky to determine, espeically it shall depend on runtime.

So, we need to find a way to pass all of the information to the lowering, without compromising on the readability of the code. This forms the basis for my next approach

This codebase is hosted here: https://github.com/YashNagda17/lfortran/tree/mlir4

Approach 3: Regioned approach for the ASR Dialect.

In this approach, we divide the ASR Dialect into three different regions:

The SymTab region, which will contain the declarations of the variables.
The Metadata region, which will contain the metadata of the program. Any additional information, for example, few Write nodes might need to store additional information, like IOMSG, IOSTAT, etc, can be stored here.
The Body region, which will contain the actual execution logic.

This approach is similar to the SymTab approach, but with the addition of the Metadata and Body regions. This helps us to keep the logic readable, and pass the extra information to the lowering, without losing any information. Fortran has a @symbol syntax, which tells an user to go to the reference of @symbol, to get additional information here (I like to think of it as citations in any paper). So, we can use this syntax to refer to the SymTab & Metadata regions, and dump all the bigger information there, while keeping only the logical flow in the body region. This helps us to keep logic readable, and pass the extra information to the lowering, without losing any information. Based on this approach, the above code is lowered in ASR dialect as follows:


$ lfortran a.f90 --show-mlir-asr-dialect --backend=mlir-new
module {
  asr.translation_unit {
    asr.program @print_01 {
      asr.symtab {
        asr.variable @a : !asr.array<!asr.integer<4>, 3> {
          dependencies = [],
            intent = #asr.intent<local>,
            symbolic_value = null,
            value = null,
            storage = #asr.storage<default>,
            type_declaration = null,
            abi = #asr.abi<source>,
            access = #asr.access<public>,
            presence = #asr.presence<required>,
            value_attr = false,
            target_attr = false,
            contiguous_attr = false,
            bindc_name = "",
            is_volatile = false,
            is_protected = false,
            pass_attr = #asr.pass_attr<not_method>,
            self_argument = "",
          codims = [],
        }
        asr.variable @i : !asr.integer<4> {
          dependencies = [],
            intent = #asr.intent<local>,
            symbolic_value = null,
            value = null,
            storage = #asr.storage<default>,
            type_declaration = null,
            abi = #asr.abi<source>,
            access = #asr.access<public>,
            presence = #asr.presence<required>,
            value_attr = false,
            target_attr = false,
            contiguous_attr = false,
            bindc_name = "",
            is_volatile = false,
            is_protected = false,
            pass_attr = #asr.pass_attr<not_method>,
            self_argument = "",
          codims = [],
        }
        asr.variable @x : !asr.integer<4> {
          dependencies = [],
            intent = #asr.intent<local>,
            symbolic_value = null,
            value = null,
            storage = #asr.storage<default>,
            type_declaration = null,
            abi = #asr.abi<source>,
            access = #asr.access<public>,
            presence = #asr.presence<required>,
            value_attr = false,
            target_attr = false,
            contiguous_attr = false,
            bindc_name = "",
            is_volatile = false,
            is_protected = false,
            pass_attr = #asr.pass_attr<not_method>,
            self_argument = "",
          codims = [],
        }
      }
      asr.metadata {
      }
      asr.body {
        asr.assign [1, 2, 3] to @a : !asr.array<!asr.integer<4>, 3>
        asr.do_loop @i = 1 to 10 {
          asr.assign @i + 5 to @x : !asr.integer<4>
        }
        asr.print @x
        asr.print @a
        asr.return
      }
    }
  }
}

This approach has several advantages: Since each region is independent, users can easily navigate to the relevant region to get the information they need. We can dump all the bigger information in the SymTab & Metadata regions, while keeping the logic readable in the Body region. If needed, we can add a compact flag in the future, which can only print the Body region, without the SymTab & Metadata regions. So, this approach has a good balance between readability and information passing.

Approach 3: Code implementation

Code implementation is hosted here: https://github.com/YashNagda17/lfortran/tree/mlir6

While implementing this approach, I followed a few basic principles:

Keep ASR Dialect generation close to ASR.asdl, so each ASR constructor can map to one asr.* operation as much as possible.
Keep ASR Dialect printing separate from ASR Dialect lowering. The printed dialect should help debugging, while lowering can still use the full stored information.
Keep declarations, metadata, and executable logic separate using asr.symtab, asr.metadata, and asr.body. This keeps the body readable without losing information needed later.
Avoid exposing internal handles in the normal output. Users should see symbols like @x and structured regions, not pointer-like IDs.
Lowering APIs are auto-generated from ASR.asdl, so we can easily add new lowering handlers for new ASR nodes.
Leveraging the existing certik/mlir repository for high level dialects & llvm dialects.

The main pipeline is:

Initial ASR -> ASR Dialect -> high-level MLIR -> LLVM Dialect -> LLVM IR

I used the following flags to test each stage:

# Show only the ASR dialect syntax
lfortran a.f90 --backend=mlir-new --show-mlir-asr-dialect

# Show the high-level MLIR after ASR dialect lowering
lfortran a.f90 --backend=mlir-new --show-mlir-high-dialect

# Show the LLVM dialect generated from high-level MLIR
lfortran a.f90 --backend=mlir-new --show-mlir-llvm-dialect

These flags helped verify that the new ASR dialect is not just a pretty dump, but an actual intermediate stage in the mlir-new backend.

Currently, high level dialects & llvm dialects are implemented from the certik/mlir repository. Once the LLVM IR is implemented, we execute it using the existing lfortran pipeline for implentation, which is used by original mlir backend. Also, currently, lowering support from ASR dialect to other mlir dialects is very limited, which will be expanded in coming weeks, once ASR dialect is stable.

Next Steps

Working on current approach, I am working on clean implementation of the ASR dialect, code cleanups and hosting a stable branch for others to test and give feedbacks for the same.
Meanwhile, I shall begin to work on the second task, to figure the alternative for MachO backend, for x86_64 architecture.

Acknowledgments

A huge thanks to my mentors, Ondřej Čertík, Pranav Goswami, Harshita Kalani & other contributors for helping me to work on this project.