[flang] RFC: -fstack-arrays implementation

[tblah]

Summary

From gfortran's man page:

Adding this option will make the Fortran compiler put all local arrays, even those of unknown size onto stack memory. If your program uses very large local arrays it is possible that you will have to extend your runtime limits for stack memory on some operating systems. This flag is enabled by default at optimization level -Ofast.

This RFC provides an evaluation of the scope of work required to support -fstack-arrays as a pass responsible for moving array heap allocations to the stack.

Github issue: https://github.com/llvm/llvm-project/issues/59231

The proposed design works in most cases, the exceptions are

• • Where blocks: the generated code is too complex for the pass to follow. There are multiple known bugs in the generated code so the easiest course of action is likely to be to fix this in codegen.
• Array constructors: the generated code uses realloc() because it is not always possible to tell ahead of time how large the constructed array will be. This makes it difficult to rewrite the generated code to use alloca. gfortran is able to transform this case into a stack allocation. This more complex case will be left for future work.

For more information on these two cases see the section on ConvertExpr.cpp.

[kiranchandramohan]

Thanks for posting this RFC @tblah. Could you also comment on why a general pass like MemoryAllocationOpt that converts Stack Allocation to Heap Allocation is not suitable here? Please include this in the RFC as an alternative option that was considered.

flang/docs/fstack-arrays.md

20

Could you add a FIR code example of the state now and after your change?

43

Could you expand this a bit more, particularly why stack allocation cannot be used?

[peixin]

flang/docs/fstack-arrays.md

33

Why? Is it possible to transform fir.allocmem into fir.alloca in one place when the option is enabled in codegen?

How about adding one unit attribute to fir.allocmem to label that the data object cannot be allocated on stack?

43

+1

[clementval]

In D139617#3981099, @kiranchandramohan wrote:

Could you also comment on why a general pass like MemoryAllocationOpt that converts Stack Allocation to Heap Allocation is not suitable here? Please include this in the RFC as an alternative option that was considered.

That would be good to know. Modifying the behavior in all the mentioned places sounds a bit hacky and error prone in the future. How are you going to ensure future code will follow what you propose here. I think a centralized pass is preferred even if it requires extra attributes or smth similar.

[jeanPerier]

Note that lowering is being updated and that in the future, temporaries for expressions will be created in HLFIR bufferization pass: https://github.com/llvm/llvm-project/blob/main/flang/lib/Optimizer/HLFIR/Transforms/BufferizeHLFIR.cpp.

[tblah]

Updates:

• Organize document according to the format recommended in DesignGuideline.md
• Explain why a piecemeal approach was chosen instead of a single pass performing this conversion
• Mention that most of the referenced code will be replaced by HLFIR
• Include an example of the changes to array value copy
• Provide a more detailed explanation of ConvertVariable.cpp
• Add a testing plan

[tblah]

In D139617#3981121, @clementval wrote:

In D139617#3981099, @kiranchandramohan wrote:

Could you also comment on why a general pass like MemoryAllocationOpt that converts Stack Allocation to Heap Allocation is not suitable here? Please include this in the RFC as an alternative option that was considered.

That would be good to know. Modifying the behavior in all the mentioned places sounds a bit hacky and error prone in the future. How are you going to ensure future code will follow what you propose here. I think a centralized pass is preferred even if it requires extra attributes or smth similar.

Thanks for taking a look. I have explained my reasoning in the updated version of the patch. In short, it isn't easy to match up fir.allocmem and fir.free.

In D139617#3981245, @jeanPerier wrote:

Note that lowering is being updated and that in the future, temporaries for expressions will be created in HLFIR bufferization pass: https://github.com/llvm/llvm-project/blob/main/flang/lib/Optimizer/HLFIR/Transforms/BufferizeHLFIR.cpp.

Thanks for the heads up. I've added a mention of this to the document. Would it be okay to come back to HLFIR changes in a later patch to this RFC?

[tblah]

flang/docs/fstack-arrays.md

33

Do you mean an attribute meaning something like "this is a real allocate statement not something added during code generation"?

Please see my explanation for my reasoning in the updated version of the patch.

[clementval]

In D139617#3982104, @tblah wrote:

In D139617#3981121, @clementval wrote:

In D139617#3981099, @kiranchandramohan wrote:

Could you also comment on why a general pass like MemoryAllocationOpt that converts Stack Allocation to Heap Allocation is not suitable here? Please include this in the RFC as an alternative option that was considered.

That would be good to know. Modifying the behavior in all the mentioned places sounds a bit hacky and error prone in the future. How are you going to ensure future code will follow what you propose here. I think a centralized pass is preferred even if it requires extra attributes or smth similar.

Thanks for taking a look. I have explained my reasoning in the updated version of the patch. In short, it isn't easy to match up fir.allocmem and fir.free.

Ok but it can be made easy to match if necessary. I still think a centralized way of doing is preferable.

[peixin]

flang/docs/fstack-arrays.md

4

Can you add more descriptions about what kind of arrays will be allocated on the stack? It would be good to add the description of -fstack-arrays of LLVM Flang and maintain it each time the lowering/codegen code is changed.

16

Can you give one example that it is hard to match the fir.allocmem op with associated fir.freemem?

33

No. What I mean is to add one unit attribute, maybe named mustHeapAlloc. In lowering code, you won't need to add one if-else of fir.allocmem and fir.alloca. Just add the unit attribute if fstack-arrays is enabled.

I am thinking if we can also add one unit attribute to fir.freemem, too. Then, we can make the transformation in one pass or somewhere in codegen at one time.

1. If the pattern of what can be transformed from heap allocation into stack sllocation can be captured, then no need to change anything in lowering code. Do it directly in the single-maintained place (in one pass or somewhere in codegen).
2. For special cases, add the unit attirbute in lowering code, make the transformation by checking the attribute in the single-maintained place (in one pass or somewhere in codegen).

55

Do we use git diff style to show the FIR changes in doc files? Maybe removing the unrelated FIR is more clear such as follows.

temp-arrays.fir
%1 = fir.allocmem !fir.array<5xi32>
... // other FIR code including accessing %1
fir.freemem %1 : !fir.heap<!fir.array<5xi32>>

// Maybe describe what -fstack-arrays does to generate the following?

temp-arrays-stack-allocation.fir
%1 = fir.alloca !fir.array<5xi32>
... // other FIR code including accessing %1
// No fir.freemem for stack allocated %1

[tblah]

flang/docs/fstack-arrays.md

16

The simplest example would be when the fir.freemem is in another fir.func. But these couldn't be converted to stack allocations anyway.

Another example:

subroutine example(n, arr)
  integer, intent(in) :: n
  integer, dimension(:), allocatable, intent(out) :: arr

  if (n .lt. 1) then
    return
  end if

  allocate(arr(n))

  call doSomething(arr)

  if (isFinished(arr)) then
    deallocate(arr)
  end if

! arr might still be alive here
end subroutine

Data flow analysis would be needed to determine whether arr has a lifetime which outlives the fir.func in which is was first allocated (and so could not be moved onto the stack).

[jeanPerier]

In D139617#3982104, @tblah wrote:

Thanks for the heads up. I've added a mention of this to the document. Would it be okay to come back to HLFIR changes in a later patch to this RFC?

Yes, that sounds reasonable to me.

[peixin]

flang/docs/fstack-arrays.md

16

Can -fstack-arrays be applied to allocatable arrays? I checked gfortran and classic-flang, both of which don't allocate memory on stack for this case when fstack-arrays is enabled.

[tblah]

flang/docs/fstack-arrays.md

16

Thanks for checking. My concern is that a general transformation will have to understand FIR for any situation where fir.allocmem and fir.freemem are generated and so will have to be able to distinguish, from the FIR, situations like this from those where arrays can be moved onto the stack.

If instead the codegen was modified, the context would be still available and so it would be easy to only try moving the right sort of allocations.

Another approach might to be add an attribute either saying "consider moving this heap allocation to the stack" or "never move this heap allocation to the stack". That could simplify things, but then we would have the same problem of having to modify all the right sections of code-gen, and keep that maintained going forward.

[peixin]

flang/docs/fstack-arrays.md

16

Sounds reasonable to me. Thanks.

[tschuett]

Could you have an array builder/materialiser component for creating arrays? Despite the code being spread over the lowering, there is a central component in charge of arrays?!?

[clementval]

flang/docs/fstack-arrays.md

16

That could simplify things, but then we would have the same problem of having to modify all the right sections of code-gen, and keep that maintained going forward.

You mean lowering right? If an attribute is needed I thing it's a nicer solution than having an if-else at every place we create an allocmemop/freememop.

[tblah]

Thank you everyone for the feedback so far.

Following the feedback, I have decided to change my approach and implement this as a pass responsible for moving array heap allocations to the stack.

Data flow analysis using the MLIR DFA framework will be used to find allocations where both the fir.allocmem and fir.freemem are in the same function, operating on the same SSA value, and the fir.freemem will always be executed before function return.

Suitable allocations will then be moved to the stack (if possible without introducing a fir.alloca inside of a loop).

fir.allocmem generated by an allocate statement in source code will not be converted, as the standard seems to require these remain on the heap (C.12.1.2).

[tblah]

Add a section naming a new FIR attribute to mark allocations which should never be moved to the stack: fir.must_be_heap

[tblah]

There is a WIP implementation of the RFC at https://reviews.llvm.org/D140415

[tblah]

• Added a paragraph explaining handling of fir.call operations during data flow analysis
• Added information about the two known cases where the existing analysis is insufficient (see the section on ConvertExpr.cpp)

I would like to merge what exists already for the easy cases and return to the two edge cases once HLFIR work is more complete.

[jeanPerier]

flang/docs/fstack-arrays.md

69

[peixin]

flang/docs/fstack-arrays.md

8

1. I think you are referring to Ubuntu Manpage: gfortran (https://manpages.ubuntu.com/manpages/trusty/man1/arm-linux-gnueabi-gfortran.1.html), instead of gfortran manual page (https://gcc.gnu.org/onlinedocs/gfortran/Code-Gen-Options.html).

2. Is it allowed to copy it from the GCC manual page in LLVM doc files? I don't know.

[tblah]

• Remove quote from gfortran's man page
• Fix typo

[tblah]

flang/docs/fstack-arrays.md

8

Thanks for pointing this out. I have replaced the direct quote with a rephrasing.

69

Thanks!

[tblah]

• Add mention of CFG loops, removed TODO for goto statements
• Specified the conditions under which llvm.stacksave/llvm.stackrestore intrinsics are safe to use

[tblah]

Ping for review on this. The pass implementation is now merged.

[jeanPerier]

Looks good, thanks for documenting this.

flang/docs/fstack-arrays.md

+# -fstack-arrays
+## Problem Description
+In gfortran, `-fstack-arrays` will cause all local arrays, including those of
+unknown size, to be allocated from stack memory. Gfortran enables this flag by
+default at `-Ofast`.
+
+Flang already allocates all local arrays on the stack (the
+`memory-allocation-opt` pass can move large allocations to the heap, but by
+default it will not). But there are some cases where temporary arrays are
+created on the heap by Flang. Moving these temporary arrays is the goal here.
+
+## Proposed Solution
+One approach would be to write a pass which attempts to move heap allocations to
+the stack (like the `memory-allocation-opt` pass in reverse). This approach has
+the advantage of a self-contained implementation and ensuring that newly added
+cases are covered.
+
+Another approach would be to modify each place in which arrays are allocated on
+the heap to instead generate a stack allocation. The advantage of the second
+approach is that it would be difficult to match up all `fir.allocmem` operations
+with their associated `fir.freemem`. In general, the lifetimes of heap allocated
+memory are not constrained by the current function's stack frame and so cannot
+be always converted to stack allocations. It is much easier to swap heap
+allocations for stack allocations when they are first generated because the
+lifetime information is conveniently available.
+
+For example, to rewrite the heap allocation in the `array-value-copy` pass with
+a stack allocation using the first approach would require analysis to ensure
+that the heap allocation is always freed before the function returns. This is
+much more complex than never generating a heap allocation (and free) in the
+first place (the second approach).
+
+The plan is to take the more complex first approach so that newly added changes
+to lowering code do not need to be made to support the stack arrays option. The
+general problem of determining heap allocation lifetimes can be simplified in
+this case because only those allocations which are always freed before exit from
+the same function are possible to be moved to heap allocations in that
+function's stack frame. Furthermore, the aim of this pass would be to only move
+those allocations generated by Flang, and so some of the more difficult cases
+can be avoided. Where the transformation is not possible, the existing heap
+allocation will be kept.
+
+## Implementation details overview
+In order to limit the complexity of the proposed pass, it is useful to
+understand the situations in which Flang will generate heap allocations.
+
+### Known Heap Array Allocations
+Flang allocates most arrays on the stack by default, but there are a few cases
+where temporary arrays are allocated on the heap:
+- `flang/lib/Optimizer/Transforms/ArrayValueCopy.cpp`
+- `flang/lib/Optimizer/Transforms/MemoryAllocation.cpp`
+- `flang/lib/Lower/ConvertExpr.cpp`
+- `flang/lib/Lower/IntrinsicCall.cpp`
+- `flang/lib/Lower/ConvertVariable.cpp`
+
+Lowering code is being updated and in the future, temporaries for expressions
+will be created in the HLFIR bufferization pass in
+`flang/lib/Optimizer/HLFIR/Trnasforms/BufferizeHLFIR.cpp`.
+
+#### `ArrayValueCopy.cpp`
+Memory is allocated for a temporary array in `allocateArrayTemp()`. This
+temporary array is used to ensure that assignments of one array to itself
+produce the required value. E.g.
+
+```
+integer, dimension(5), intent(inout) :: x
+x(3,4) = x(1,2)
+```
+
+#### `MemoryAllocation.cpp`
+The default options for the Memory Allocation transformation ensure that no
+array allocations, no matter how large, are moved from the stack to the heap.
+
+#### `ConvertExpr.cpp`
+`ConvertExpr.cpp` allocates many array temporaries on the heap:
+  - Passing array arguments by value or when they need re-shaping
+  - Lowering elemental array expressions
+  - Lowering mask expressions
+  - Array constructors
+
+The last two of these cases are **not** covered by the current stack arrays pass
+design.
+
+The FIR code generated for mask expressions (the WHERE construct) sets a
+boolean variable to indicate whether a heap allocation was necessary. The
+allocation is only freed if the variable indicates that the allocation was
+performed to begin with. The proposed dataflow analysis is not intelligent
+enough to statically determine that the boolean variable will always be true
+when the allocation is performed. Beyond this, the control flow in the generated
+FIR code passes the allocated memory through `fir.result`, resulting in a
+different SSA value to be allocated and freed, causing the analysis not to
+realise that the allocated memory is freed. The most convenient solution here
+would be to generate less complicated FIR code, as the existing codegen has
+known bugs: https://github.com/llvm/llvm-project/issues/56921,
+https://github.com/llvm/llvm-project/issues/59803.
+
+Code generated for array constructors uses `realloc()` to grow the allocated
+buffer because the size of the resulting array cannot always be determined
+ahead of running the constructor. This makes this temporary unsuitable
+for allocation on the stack.
+
+#### `IntrinsicCall.cpp`
+The existing design is for the runtime to do the allocation and the lowering
+code to insert `fir.freemem` to remove the allocation. It is not clear whether
+this can be replaced by adapting lowering code to do stack allocations and to
+pass these to the runtime. This would be a significant change and so is out of
+scope of `-fstack-arrays`.
+
+#### `ConvertVariable.cpp`
+See `Fortran::lower::MapSymbolAttributes`:
+
+Dummy arguments that are not declared in the current entry point require a
+skeleton definition. Most such "unused" dummies will not survive into final
+generated code, but some will. It is illegal to reference one at run time if it
+does. There are three ways these dummies can be mapped to a value:
+- a `fir::UndefOp` value: preferable but can't be used for dummies with dynamic
+  bounds or used to define another dummy.
+- A stack slot. This has intermediate-weight cost but may not be usable for
+  objects with dynamic bounds.
+- A heap box/descriptor is the heaviest weight option, only used for dynamic
+  objects.
+
+These heap allocations will be out of scope for `-fstack-arrays` because the
+existing implementation already uses stack allocations (or better) where
+possible, and most such dummy arguments will be removed from generated code.
+
+#### `BufferizeHLFIR.cpp`
+TODO
+
+### Detecting Allocations to Move
+Allocations which could be moved to the stack will be detected by performing a
+forward dense data flow analysis using `mlir::dataflow::DenseDataFlowAnalysis`.
+This analysis will search for SSA values created by a `fir.allocmem` which are
+always freed using `fir.freemem` within the same function.
+
+Tracking allocations by SSA values will miss some cases where address
+calculations are duplicated in different blocks: resulting in different SSA
+values as arguments for the allocation and the free. It is believed that simple
+tracking of SSA values is sufficient for detecting the allocations for array
+temporaries added by Flang, because these temporaries should be simple arrays:
+not nested inside of derived types or other arrays.
+
+Arrays allocated by an `allocate` statement in source code should not be moved
+to the stack. These will be identified by adding an attribute to these
+`fir.allocmem` operations when they are lowered. Intrinsics such as `allocated`
+and `move_alloc` do not need to be supported because the array temporaries moved
+to the stack will never be visible in user code.
+
+Only allocations for arrays will be considered for moving to the stack.
+
+When conducting the dense data flow analysis, the pass will assume that existing
+allocations are not freed inside called functions. This is true for the existing
+heap array temporary allocations generated by Flang. If an allocation were to be
+freed inside of a called function, the allocation would presumably not also be
+freed later in the caller function (as this would be a double-free). Therefore
+the stack arrays pass would not find where the allocation was freed and so not
+transform the allocation. It is necessary to make this assumption so that the
+stack arrays pass can transform array allocations created for pass-by-value
+function arguments.
+
+### Moving Allocations
+The `fir.allocmem` will be replaced by a `fir.alloca` with the same arguments.
+The `fir.freemem` will be removed entirely.
+
+Where possible, the `fir.alloca` should be placed in the function entry block
+(so we can be sure it only happens once). This may not be possible if the array
+has non-constant extents (causing the `fir.alloca` to have SSA values as
+operands). In this case, the `fir.alloca` will be placed immediately after the
+last operand becomes available.
+
+If this location is inside a loop (either an `mlir::LoopLikeOpInterface` or a
+cyclic CFG), the transformation should attempt to use the `llvm.stacksave`/
+`llvm.stackrestore` intrinsics to ensure that the stack does not grow on every
+loop iteration. Use of these intrinsics is considered valid when the allocation
+and deallocation occur within the same block and there are no other stack
+allocations between them. If this is not the case, the existing heap allocation
+will be preserved.
+
+### FIR attribute
+A FIR attribute will be added to distinguish `fir.allocmem` arising from
+`allocate` statements in source from `fir.allocmem` operations  added by Flang.
+The attribute will be called `"fir.must_be_heap"` and will have a boolean value:
+`true` meaning that the stack arrays pass must not move the allocation, `false`
+meaning that stack arrays may move the allocation. Not specifying the attribute
+will be equivalent to setting it to `false`.
+
+## Testing Plan
+FileCheck tests will be written to check each of the above identified sources of
+heap allocated array temporaries are detected and converted by the new pass.
+
+Another test will check that `allocate` statements in source code will not be
+moved to the stack.