[fir] Add cfg conversion pass

[clementval]

Summary

This patch upstream the cfg conversion pass. This pass
rewrite FIR loop-like operation to a CFG.

This patch is part of the upstreaming effort from fir-dev branch.

Co-authored-by: Jean Perier <[e-mail]>

Co-authored-by: Eric Schweitz <[e-mail]>
Co-authored-by: V Donaldson <[e-mail]>

[mehdi_amini]

flang/lib/Optimizer/Transforms/RewriteLoop.cpp

30

Please replace these with pass options.

297

This actually really seems like this option does not belong here: if someone wants to disable cfg-conversion in the compiler, then the proper plumbing is to have this option on the pass manager builder so that the pass does not get added to the pipeline.

[clementval]

Move always-execute-loop-body option to the TableGen file.
Remove disable-cfg-conversion option.

[clementval]

flang/lib/Optimizer/Transforms/RewriteLoop.cpp

30

Done.

297

Right it makes more sense. Just removed the option.

[mehdi_amini]

LG, thanks!

[schweitz]

flang/lib/Optimizer/Transforms/RewriteLoop.cpp

297

We'll need a way to enable and disable the passes in the test tools and without having to specify the entire pipeline.

[mehdi_amini]

flang/lib/Optimizer/Transforms/RewriteLoop.cpp

297

Which test tools? Ultimately the option will have to be pushed there (in whatever abstraction used to build the pipeline there)

[clementval]

flang/lib/Optimizer/Transforms/RewriteLoop.cpp

297

We have a test tool that is similar to mlir-translate but for FIR of course. Not upstreamed yet.

[clementval]

Rebase

flang/include/flang/Optimizer/Transforms/Passes.h

 namespace fir {
 
 //===----------------------------------------------------------------------===//
 // Passes defined in Passes.td
 //===----------------------------------------------------------------------===//
 
 std::unique_ptr<mlir::Pass> createAbstractResultOptPass();
 std::unique_ptr<mlir::Pass> createAffineDemotionPass();
+std::unique_ptr<mlir::Pass> createFirToCfgPass();
 std::unique_ptr<mlir::Pass> createCharacterConversionPass();
 std::unique_ptr<mlir::Pass> createExternalNameConversionPass();
 std::unique_ptr<mlir::Pass> createPromoteToAffinePass();
 
 /// Support for inlining on FIR.
 bool canLegallyInline(mlir::Operation *op, mlir::Region *reg,
                       mlir::BlockAndValueMapping &map);
 
 // declarative passes
 #define GEN_PASS_REGISTRATION
 #include "flang/Optimizer/Transforms/Passes.h.inc"
 
 } // namespace fir
 
 #endif // OPTIMIZER_TRANSFORMS_PASSES_H

flang/include/flang/Optimizer/Transforms/Passes.td

def CharacterConversion : Pass<"character-conversion"> {
   let options = [
     Option<"useRuntimeCalls", "use-runtime-calls",
            "std::string", /*default=*/"std::string{}",
            "Generate runtime calls to a named set of conversion routines. "
            "By default, the conversions may produce unexpected results.">
   ];
 }
 
+def CFGConversion : FunctionPass<"cfg-conversion"> {
+  let summary = "Convert FIR structured control flow ops to CFG ops.";
+  let description = [{
+    Transform the `fir.do_loop`, `fir.if`, and `fir.iterate_while` ops into
+    plain old test and branch operations. Removing the high-level control
+    structures can enable other optimizations.
+
+    This pass is required before code gen to the LLVM IR dialect.
+  }];
+  let constructor = "::fir::createFirToCfgPass()";
+  let dependentDialects = [
+    "fir::FIROpsDialect", "mlir::StandardOpsDialect"
+  ];
+  let options = [
+    Option<"forceLoopToExecuteOnce", "always-execute-loop-body", "bool",
+           /*default=*/"false",
+           "force the body of a loop to execute at least once">
+  ];
+}
+
 def ExternalNameConversion : Pass<"external-name-interop", "mlir::ModuleOp"> {
   let summary = "Convert name for external interoperability";
   let description = [{
     Demangle FIR internal name and mangle them for external interoperability.
   }];
   let constructor = "::fir::createExternalNameConversionPass()";
 }
 
 #endif // FLANG_OPTIMIZER_TRANSFORMS_PASSES

flang/lib/Optimizer/Transforms/CMakeLists.txt

 add_flang_library(FIRTransforms
   AbstractResult.cpp
   AffinePromotion.cpp
   AffineDemotion.cpp
   CharacterConversion.cpp
   Inliner.cpp
   ExternalNameConversion.cpp
+  RewriteLoop.cpp
 
   DEPENDS
   FIRDialect
   FIRSupport
   FIROptTransformsPassIncGen
   RewritePatternsIncGen
 
   LINK_LIBS
   FIRDialect
   MLIRAffineToStandard
   MLIRLLVMIR
   MLIROpenACC
   MLIROpenMP
   FIRSupport
 )

flang/lib/Optimizer/Transforms/RewriteLoop.cpp

+//===-- RewriteLoop.cpp ---------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include "PassDetail.h"
+#include "flang/Optimizer/Dialect/FIRDialect.h"
+#include "flang/Optimizer/Dialect/FIROps.h"
+#include "flang/Optimizer/Transforms/Passes.h"
+#include "mlir/Dialect/Affine/IR/AffineOps.h"
+#include "mlir/Dialect/StandardOps/IR/Ops.h"
+#include "mlir/Pass/Pass.h"
+#include "mlir/Transforms/DialectConversion.h"
+#include "llvm/Support/CommandLine.h"
+
+using namespace fir;
+
+namespace {
+
+// Conversion of fir control ops to more primitive control-flow.
+//
+// FIR loops that cannot be converted to the affine dialect will remain as
+// `fir.do_loop` operations.  These can be converted to control-flow operations.
+
+/// Convert `fir.do_loop` to CFG
+class CfgLoopConv : public mlir::OpRewritePattern<fir::DoLoopOp> {
+public:
+  using OpRewritePattern::OpRewritePattern;
+
+  CfgLoopConv(mlir::MLIRContext *ctx, bool forceLoopToExecuteOnce)
+      : mlir::OpRewritePattern<fir::DoLoopOp>(ctx),
+        forceLoopToExecuteOnce(forceLoopToExecuteOnce) {}
+
+  mlir::LogicalResult
+  matchAndRewrite(DoLoopOp loop,
+                  mlir::PatternRewriter &rewriter) const override {
+    auto loc = loop.getLoc();
+
+    // Create the start and end blocks that will wrap the DoLoopOp with an
+    // initalizer and an end point
+    auto *initBlock = rewriter.getInsertionBlock();
+    auto initPos = rewriter.getInsertionPoint();
+    auto *endBlock = rewriter.splitBlock(initBlock, initPos);
+
+    // Split the first DoLoopOp block in two parts. The part before will be the
+    // conditional block since it already has the induction variable and
+    // loop-carried values as arguments.
+    auto *conditionalBlock = &loop.region().front();
+    conditionalBlock->addArgument(rewriter.getIndexType());
+    auto *firstBlock =
+        rewriter.splitBlock(conditionalBlock, conditionalBlock->begin());
+    auto *lastBlock = &loop.region().back();
+
+    // Move the blocks from the DoLoopOp between initBlock and endBlock
+    rewriter.inlineRegionBefore(loop.region(), endBlock);
+
+    // Get loop values from the DoLoopOp
+    auto low = loop.lowerBound();
+    auto high = loop.upperBound();
+    assert(low && high && "must be a Value");
+    auto step = loop.step();
+
+    // Initalization block
+    rewriter.setInsertionPointToEnd(initBlock);
+    auto diff = rewriter.create<mlir::SubIOp>(loc, high, low);
+    auto distance = rewriter.create<mlir::AddIOp>(loc, diff, step);
+    mlir::Value iters =
+        rewriter.create<mlir::SignedDivIOp>(loc, distance, step);
+
+    if (forceLoopToExecuteOnce) {
+      auto zero = rewriter.create<mlir::ConstantIndexOp>(loc, 0);
+      auto cond =
+          rewriter.create<mlir::CmpIOp>(loc, CmpIPredicate::sle, iters, zero);
+      auto one = rewriter.create<mlir::ConstantIndexOp>(loc, 1);
+      iters = rewriter.create<mlir::SelectOp>(loc, cond, one, iters);
+    }
+
+    llvm::SmallVector<mlir::Value> loopOperands;
+    loopOperands.push_back(low);
+    auto operands = loop.getIterOperands();
+    loopOperands.append(operands.begin(), operands.end());
+    loopOperands.push_back(iters);
+
+    rewriter.create<mlir::BranchOp>(loc, conditionalBlock, loopOperands);
+
+    // Last loop block
+    auto *terminator = lastBlock->getTerminator();
+    rewriter.setInsertionPointToEnd(lastBlock);
+    auto iv = conditionalBlock->getArgument(0);
+    mlir::Value steppedIndex = rewriter.create<mlir::AddIOp>(loc, iv, step);
+    assert(steppedIndex && "must be a Value");
+    auto lastArg = conditionalBlock->getNumArguments() - 1;
+    auto itersLeft = conditionalBlock->getArgument(lastArg);
+    auto one = rewriter.create<mlir::ConstantIndexOp>(loc, 1);
+    mlir::Value itersMinusOne =
+        rewriter.create<mlir::SubIOp>(loc, itersLeft, one);
+
+    llvm::SmallVector<mlir::Value> loopCarried;
+    loopCarried.push_back(steppedIndex);
+    auto begin = loop.finalValue() ? std::next(terminator->operand_begin())
+                                   : terminator->operand_begin();
+    loopCarried.append(begin, terminator->operand_end());
+    loopCarried.push_back(itersMinusOne);
+    rewriter.create<mlir::BranchOp>(loc, conditionalBlock, loopCarried);
+    rewriter.eraseOp(terminator);
+
+    // Conditional block
+    rewriter.setInsertionPointToEnd(conditionalBlock);
+    auto zero = rewriter.create<mlir::ConstantIndexOp>(loc, 0);
+    auto comparison =
+        rewriter.create<mlir::CmpIOp>(loc, CmpIPredicate::sgt, itersLeft, zero);
+
+    rewriter.create<mlir::CondBranchOp>(loc, comparison, firstBlock,
+                                        llvm::ArrayRef<mlir::Value>(), endBlock,
+                                        llvm::ArrayRef<mlir::Value>());
+
+    // The result of the loop operation is the values of the condition block
+    // arguments except the induction variable on the last iteration.
+    auto args = loop.finalValue()
+                    ? conditionalBlock->getArguments()
+                    : conditionalBlock->getArguments().drop_front();
+    rewriter.replaceOp(loop, args.drop_back());
+    return success();
+  }
+
+private:
+  bool forceLoopToExecuteOnce;
+};
+
+/// Convert `fir.if` to control-flow
+class CfgIfConv : public mlir::OpRewritePattern<fir::IfOp> {
+public:
+  using OpRewritePattern::OpRewritePattern;
+
+  CfgIfConv(mlir::MLIRContext *ctx, bool forceLoopToExecuteOnce)
+      : mlir::OpRewritePattern<fir::IfOp>(ctx),
+        forceLoopToExecuteOnce(forceLoopToExecuteOnce) {}
+
+  mlir::LogicalResult
+  matchAndRewrite(IfOp ifOp, mlir::PatternRewriter &rewriter) const override {
+    auto loc = ifOp.getLoc();
+
+    // Split the block containing the 'fir.if' into two parts.  The part before
+    // will contain the condition, the part after will be the continuation
+    // point.
+    auto *condBlock = rewriter.getInsertionBlock();
+    auto opPosition = rewriter.getInsertionPoint();
+    auto *remainingOpsBlock = rewriter.splitBlock(condBlock, opPosition);
+    mlir::Block *continueBlock;
+    if (ifOp.getNumResults() == 0) {
+      continueBlock = remainingOpsBlock;
+    } else {
+      continueBlock =
+          rewriter.createBlock(remainingOpsBlock, ifOp.getResultTypes());
+      rewriter.create<mlir::BranchOp>(loc, remainingOpsBlock);
+    }
+
+    // Move blocks from the "then" region to the region containing 'fir.if',
+    // place it before the continuation block, and branch to it.
+    auto &ifOpRegion = ifOp.thenRegion();
+    auto *ifOpBlock = &ifOpRegion.front();
+    auto *ifOpTerminator = ifOpRegion.back().getTerminator();
+    auto ifOpTerminatorOperands = ifOpTerminator->getOperands();
+    rewriter.setInsertionPointToEnd(&ifOpRegion.back());
+    rewriter.create<mlir::BranchOp>(loc, continueBlock, ifOpTerminatorOperands);
+    rewriter.eraseOp(ifOpTerminator);
+    rewriter.inlineRegionBefore(ifOpRegion, continueBlock);
+
+    // Move blocks from the "else" region (if present) to the region containing
+    // 'fir.if', place it before the continuation block and branch to it.  It
+    // will be placed after the "then" regions.
+    auto *otherwiseBlock = continueBlock;
+    auto &otherwiseRegion = ifOp.elseRegion();
+    if (!otherwiseRegion.empty()) {
+      otherwiseBlock = &otherwiseRegion.front();
+      auto *otherwiseTerm = otherwiseRegion.back().getTerminator();
+      auto otherwiseTermOperands = otherwiseTerm->getOperands();
+      rewriter.setInsertionPointToEnd(&otherwiseRegion.back());
+      rewriter.create<mlir::BranchOp>(loc, continueBlock,
+                                      otherwiseTermOperands);
+      rewriter.eraseOp(otherwiseTerm);
+      rewriter.inlineRegionBefore(otherwiseRegion, continueBlock);
+    }
+
+    rewriter.setInsertionPointToEnd(condBlock);
+    rewriter.create<mlir::CondBranchOp>(
+        loc, ifOp.condition(), ifOpBlock, llvm::ArrayRef<mlir::Value>(),
+        otherwiseBlock, llvm::ArrayRef<mlir::Value>());
+    rewriter.replaceOp(ifOp, continueBlock->getArguments());
+    return success();
+  }
+
+private:
+  bool forceLoopToExecuteOnce;
+};
+
+/// Convert `fir.iter_while` to control-flow.
+class CfgIterWhileConv : public mlir::OpRewritePattern<fir::IterWhileOp> {
+public:
+  using OpRewritePattern::OpRewritePattern;
+
+  CfgIterWhileConv(mlir::MLIRContext *ctx, bool forceLoopToExecuteOnce)
+      : mlir::OpRewritePattern<fir::IterWhileOp>(ctx),
+        forceLoopToExecuteOnce(forceLoopToExecuteOnce) {}
+
+  mlir::LogicalResult
+  matchAndRewrite(fir::IterWhileOp whileOp,
+                  mlir::PatternRewriter &rewriter) const override {
+    auto loc = whileOp.getLoc();
+
+    // Start by splitting the block containing the 'fir.do_loop' into two parts.
+    // The part before will get the init code, the part after will be the end
+    // point.
+    auto *initBlock = rewriter.getInsertionBlock();
+    auto initPosition = rewriter.getInsertionPoint();
+    auto *endBlock = rewriter.splitBlock(initBlock, initPosition);
+
+    // Use the first block of the loop body as the condition block since it is
+    // the block that has the induction variable and loop-carried values as
+    // arguments. Split out all operations from the first block into a new
+    // block. Move all body blocks from the loop body region to the region
+    // containing the loop.
+    auto *conditionBlock = &whileOp.region().front();
+    auto *firstBodyBlock =
+        rewriter.splitBlock(conditionBlock, conditionBlock->begin());
+    auto *lastBodyBlock = &whileOp.region().back();
+    rewriter.inlineRegionBefore(whileOp.region(), endBlock);
+    auto iv = conditionBlock->getArgument(0);
+    auto iterateVar = conditionBlock->getArgument(1);
+
+    // Append the induction variable stepping logic to the last body block and
+    // branch back to the condition block. Loop-carried values are taken from
+    // operands of the loop terminator.
+    auto *terminator = lastBodyBlock->getTerminator();
+    rewriter.setInsertionPointToEnd(lastBodyBlock);
+    auto step = whileOp.step();
+    mlir::Value stepped = rewriter.create<mlir::AddIOp>(loc, iv, step);
+    assert(stepped && "must be a Value");
+
+    llvm::SmallVector<mlir::Value> loopCarried;
+    loopCarried.push_back(stepped);
+    auto begin = whileOp.finalValue() ? std::next(terminator->operand_begin())
+                                      : terminator->operand_begin();
+    loopCarried.append(begin, terminator->operand_end());
+    rewriter.create<mlir::BranchOp>(loc, conditionBlock, loopCarried);
+    rewriter.eraseOp(terminator);
+
+    // Compute loop bounds before branching to the condition.
+    rewriter.setInsertionPointToEnd(initBlock);
+    auto lowerBound = whileOp.lowerBound();
+    auto upperBound = whileOp.upperBound();
+    assert(lowerBound && upperBound && "must be a Value");
+
+    // The initial values of loop-carried values is obtained from the operands
+    // of the loop operation.
+    llvm::SmallVector<mlir::Value> destOperands;
+    destOperands.push_back(lowerBound);
+    auto iterOperands = whileOp.getIterOperands();
+    destOperands.append(iterOperands.begin(), iterOperands.end());
+    rewriter.create<mlir::BranchOp>(loc, conditionBlock, destOperands);
+
+    // With the body block done, we can fill in the condition block.
+    rewriter.setInsertionPointToEnd(conditionBlock);
+    // The comparison depends on the sign of the step value. We fully expect
+    // this expression to be folded by the optimizer or LLVM. This expression
+    // is written this way so that `step == 0` always returns `false`.
+    auto zero = rewriter.create<mlir::ConstantIndexOp>(loc, 0);
+    auto compl0 =
+        rewriter.create<mlir::CmpIOp>(loc, CmpIPredicate::slt, zero, step);
+    auto compl1 =
+        rewriter.create<mlir::CmpIOp>(loc, CmpIPredicate::sle, iv, upperBound);
+    auto compl2 =
+        rewriter.create<mlir::CmpIOp>(loc, CmpIPredicate::slt, step, zero);
+    auto compl3 =
+        rewriter.create<mlir::CmpIOp>(loc, CmpIPredicate::sle, upperBound, iv);
+    auto cmp0 = rewriter.create<mlir::AndOp>(loc, compl0, compl1);
+    auto cmp1 = rewriter.create<mlir::AndOp>(loc, compl2, compl3);
+    auto cmp2 = rewriter.create<mlir::OrOp>(loc, cmp0, cmp1);
+    // Remember to AND in the early-exit bool.
+    auto comparison = rewriter.create<mlir::AndOp>(loc, iterateVar, cmp2);
+    rewriter.create<mlir::CondBranchOp>(loc, comparison, firstBodyBlock,
+                                        llvm::ArrayRef<mlir::Value>(), endBlock,
+                                        llvm::ArrayRef<mlir::Value>());
+    // The result of the loop operation is the values of the condition block
+    // arguments except the induction variable on the last iteration.
+    auto args = whileOp.finalValue()
+                    ? conditionBlock->getArguments()
+                    : conditionBlock->getArguments().drop_front();
+    rewriter.replaceOp(whileOp, args);
+    return success();
+  }
+
+private:
+  bool forceLoopToExecuteOnce;
+};
+
+/// Convert FIR structured control flow ops to CFG ops.
+class CfgConversion : public CFGConversionBase<CfgConversion> {
+public:
+  void runOnFunction() override {
+    auto *context = &getContext();
+    mlir::OwningRewritePatternList patterns(context);
+    patterns.insert<CfgLoopConv, CfgIfConv, CfgIterWhileConv>(
+        context, forceLoopToExecuteOnce);
+    mlir::ConversionTarget target(*context);
+    target.addLegalDialect<mlir::AffineDialect, FIROpsDialect,
+                           mlir::StandardOpsDialect>();
+
+    // apply the patterns
+    target.addIllegalOp<ResultOp, DoLoopOp, IfOp, IterWhileOp>();
+    target.markUnknownOpDynamicallyLegal([](Operation *) { return true; });
+    if (mlir::failed(mlir::applyPartialConversion(getFunction(), target,
+                                                  std::move(patterns)))) {
+      mlir::emitError(mlir::UnknownLoc::get(context),
+                      "error in converting to CFG\n");
+      signalPassFailure();
+    }
+  }
+};
+} // namespace
+
+/// Convert FIR's structured control flow ops to CFG ops.  This
+/// conversion enables the `createLowerToCFGPass` to transform these to CFG
+/// form.
+std::unique_ptr<mlir::Pass> fir::createFirToCfgPass() {
+  return std::make_unique<CfgConversion>();
+}

flang/test/Fir/loop01.fir

+// RUN: fir-opt --split-input-file --cfg-conversion %s | FileCheck %s
+
+func @x(%lb : index, %ub : index, %step : index, %b : i1, %addr : !fir.ref<index>) {
+  fir.do_loop %iv = %lb to %ub step %step unordered {
+    // expect following conditional blocks to get fused
+    fir.if %b {
+      fir.store %iv to %addr : !fir.ref<index>
+    } else {
+      %zero = constant 0 : index
+      fir.store %zero to %addr : !fir.ref<index>
+    }
+  }
+  return
+}
+
+func private @f2() -> i1
+
+// CHECK:     func @x(%[[VAL_0:.*]]: index, %[[VAL_1:.*]]: index, %[[VAL_2:.*]]: index, %[[VAL_3:.*]]: i1, %[[VAL_4:.*]]: !fir.ref<index>) {
+// CHECK:       %[[VAL_5:.*]] = subi %[[VAL_1]], %[[VAL_0]] : index
+// CHECK:       %[[VAL_6:.*]] = addi %[[VAL_5]], %[[VAL_2]] : index
+// CHECK:       %[[VAL_7:.*]] = divi_signed %[[VAL_6]], %[[VAL_2]] : index
+// CHECK:       br ^bb1(%[[VAL_0]], %[[VAL_7]] : index, index)
+// CHECK:     ^bb1(%[[VAL_8:.*]]: index, %[[VAL_9:.*]]: index):
+// CHECK:       %[[VAL_10:.*]] = constant 0 : index
+// CHECK:       %[[VAL_11:.*]] = cmpi sgt, %[[VAL_9]], %[[VAL_10]] : index
+// CHECK:       cond_br %[[VAL_11]], ^bb2, ^bb6
+// CHECK:     ^bb2:
+// CHECK:       cond_br %[[VAL_3]], ^bb3, ^bb4
+// CHECK:     ^bb3:
+// CHECK:       fir.store %[[VAL_8]] to %[[VAL_4]] : !fir.ref<index>
+// CHECK:       br ^bb5
+// CHECK:     ^bb4:
+// CHECK:       %[[VAL_12:.*]] = constant 0 : index
+// CHECK:       fir.store %[[VAL_12]] to %[[VAL_4]] : !fir.ref<index>
+// CHECK:       br ^bb5
+// CHECK:     ^bb5:
+// CHECK:       %[[VAL_13:.*]] = addi %[[VAL_8]], %[[VAL_2]] : index
+// CHECK:       %[[VAL_14:.*]] = constant 1 : index
+// CHECK:       %[[VAL_15:.*]] = subi %[[VAL_9]], %[[VAL_14]] : index
+// CHECK:       br ^bb1(%[[VAL_13]], %[[VAL_15]] : index, index)
+// CHECK:     ^bb6:
+// CHECK:       return
+// CHECK:     }
+// CHECK:     func private @f2() -> i1
+
+// -----
+
+func @x2(%lo : index, %up : index, %ok : i1) {
+  %c1 = constant 1 : index
+  %unused = fir.iterate_while (%i = %lo to %up step %c1) and (%ok1 = %ok) {
+    %ok2 = fir.call @f2() : () -> i1
+    fir.result %ok2 : i1
+  }
+  return
+}
+
+func private @f3(i16)
+
+// CHECK:   func @x2(%[[VAL_0:.*]]: index, %[[VAL_1:.*]]: index, %[[VAL_2:.*]]: i1) {
+// CHECK:     %[[VAL_3:.*]] = constant 1 : index
+// CHECK:     br ^bb1(%[[VAL_0]], %[[VAL_2]] : index, i1)
+// CHECK:   ^bb1(%[[VAL_4:.*]]: index, %[[VAL_5:.*]]: i1):
+// CHECK:     %[[VAL_6:.*]] = constant 0 : index
+// CHECK:     %[[VAL_7:.*]] = cmpi slt, %[[VAL_6]], %[[VAL_3]] : index
+// CHECK:     %[[VAL_8:.*]] = cmpi sle, %[[VAL_4]], %[[VAL_1]] : index
+// CHECK:     %[[VAL_9:.*]] = cmpi slt, %[[VAL_3]], %[[VAL_6]] : index
+// CHECK:     %[[VAL_10:.*]] = cmpi sle, %[[VAL_1]], %[[VAL_4]] : index
+// CHECK:     %[[VAL_11:.*]] = and %[[VAL_7]], %[[VAL_8]] : i1
+// CHECK:     %[[VAL_12:.*]] = and %[[VAL_9]], %[[VAL_10]] : i1
+// CHECK:     %[[VAL_13:.*]] = or %[[VAL_11]], %[[VAL_12]] : i1
+// CHECK:     %[[VAL_14:.*]] = and %[[VAL_5]], %[[VAL_13]] : i1
+// CHECK:     cond_br %[[VAL_14]], ^bb2, ^bb3
+// CHECK:   ^bb2:
+// CHECK:     %[[VAL_15:.*]] = fir.call @f2() : () -> i1
+// CHECK:     %[[VAL_16:.*]] = addi %[[VAL_4]], %[[VAL_3]] : index
+// CHECK:     br ^bb1(%[[VAL_16]], %[[VAL_15]] : index, i1)
+// CHECK:   ^bb3:
+// CHECK:     return
+// CHECK:   }
+// CHECK:   func private @f3(i16)
+
+// -----
+
+// do_loop with an extra loop-carried value
+func @x3(%lo : index, %up : index) -> i1 {
+  %c1 = constant 1 : index
+  %ok1 = constant true
+  %ok2 = fir.do_loop %i = %lo to %up step %c1 iter_args(%j = %ok1) -> i1 {
+    %ok = fir.call @f2() : () -> i1
+    fir.result %ok : i1
+  }
+  return %ok2 : i1
+}
+
+// CHECK-LABEL:   func @x3(
+// CHECK-SAME:             %[[VAL_0:.*]]: index,
+// CHECK-SAME:             %[[VAL_1:.*]]: index) -> i1 {
+// CHECK:           %[[VAL_2:.*]] = constant 1 : index
+// CHECK:           %[[VAL_3:.*]] = constant true
+// CHECK:           %[[VAL_4:.*]] = subi %[[VAL_1]], %[[VAL_0]] : index
+// CHECK:           %[[VAL_5:.*]] = addi %[[VAL_4]], %[[VAL_2]] : index
+// CHECK:           %[[VAL_6:.*]] = divi_signed %[[VAL_5]], %[[VAL_2]] : index
+// CHECK:           br ^bb1(%[[VAL_0]], %[[VAL_3]], %[[VAL_6]] : index, i1, index)
+// CHECK:         ^bb1(%[[VAL_7:.*]]: index, %[[VAL_8:.*]]: i1, %[[VAL_9:.*]]: index):
+// CHECK:           %[[VAL_10:.*]] = constant 0 : index
+// CHECK:           %[[VAL_11:.*]] = cmpi sgt, %[[VAL_9]], %[[VAL_10]] : index
+// CHECK:           cond_br %[[VAL_11]], ^bb2, ^bb3
+// CHECK:         ^bb2:
+// CHECK:           %[[VAL_12:.*]] = fir.call @f2() : () -> i1
+// CHECK:           %[[VAL_13:.*]] = addi %[[VAL_7]], %[[VAL_2]] : index
+// CHECK:           %[[VAL_14:.*]] = constant 1 : index
+// CHECK:           %[[VAL_15:.*]] = subi %[[VAL_9]], %[[VAL_14]] : index
+// CHECK:           br ^bb1(%[[VAL_13]], %[[VAL_12]], %[[VAL_15]] : index, i1, index)
+// CHECK:         ^bb3:
+// CHECK:           return %[[VAL_8]] : i1
+// CHECK:         }
+
+// -----
+
+// iterate_while with an extra loop-carried value
+func @y3(%lo : index, %up : index) -> i1 {
+  %c1 = constant 1 : index
+  %ok1 = constant true
+  %ok4 = fir.call @f2() : () -> i1
+  %ok2:2 = fir.iterate_while (%i = %lo to %up step %c1) and (%ok3 = %ok1) iter_args(%j = %ok4) -> i1 {
+    %ok = fir.call @f2() : () -> i1
+    fir.result %ok3, %ok : i1, i1
+  }
+  %andok = and %ok2#0, %ok2#1 : i1
+  return %andok : i1
+}
+
+func private @f4(i32) -> i1
+
+// CHECK-LABEL:   func @y3(
+// CHECK-SAME:             %[[VAL_0:.*]]: index,
+// CHECK-SAME:             %[[VAL_1:.*]]: index) -> i1 {
+// CHECK:           %[[VAL_2:.*]] = constant 1 : index
+// CHECK:           %[[VAL_3:.*]] = constant true
+// CHECK:           %[[VAL_4:.*]] = fir.call @f2() : () -> i1
+// CHECK:           br ^bb1(%[[VAL_0]], %[[VAL_3]], %[[VAL_4]] : index, i1, i1)
+// CHECK:         ^bb1(%[[VAL_5:.*]]: index, %[[VAL_6:.*]]: i1, %[[VAL_7:.*]]: i1):
+// CHECK:           %[[VAL_8:.*]] = constant 0 : index
+// CHECK:           %[[VAL_9:.*]] = cmpi slt, %[[VAL_8]], %[[VAL_2]] : index
+// CHECK:           %[[VAL_10:.*]] = cmpi sle, %[[VAL_5]], %[[VAL_1]] : index
+// CHECK:           %[[VAL_11:.*]] = cmpi slt, %[[VAL_2]], %[[VAL_8]] : index
+// CHECK:           %[[VAL_12:.*]] = cmpi sle, %[[VAL_1]], %[[VAL_5]] : index
+// CHECK:           %[[VAL_13:.*]] = and %[[VAL_9]], %[[VAL_10]] : i1
+// CHECK:           %[[VAL_14:.*]] = and %[[VAL_11]], %[[VAL_12]] : i1
+// CHECK:           %[[VAL_15:.*]] = or %[[VAL_13]], %[[VAL_14]] : i1
+// CHECK:           %[[VAL_16:.*]] = and %[[VAL_6]], %[[VAL_15]] : i1
+// CHECK:           cond_br %[[VAL_16]], ^bb2, ^bb3
+// CHECK:         ^bb2:
+// CHECK:           %[[VAL_17:.*]] = fir.call @f2() : () -> i1
+// CHECK:           %[[VAL_18:.*]] = addi %[[VAL_5]], %[[VAL_2]] : index
+// CHECK:           br ^bb1(%[[VAL_18]], %[[VAL_6]], %[[VAL_17]] : index, i1, i1)
+// CHECK:         ^bb3:
+// CHECK:           %[[VAL_19:.*]] = and %[[VAL_6]], %[[VAL_7]] : i1
+// CHECK:           return %[[VAL_19]] : i1
+// CHECK:         }
+// CHECK:         func private @f4(i32) -> i1
+
+// -----
+
+// do_loop that returns the final value of the induction
+func @x4(%lo : index, %up : index) -> index {
+  %c1 = constant 1 : index
+  %v = fir.do_loop %i = %lo to %up step %c1 -> index {
+    %i1 = fir.convert %i : (index) -> i32
+    %ok = fir.call @f4(%i1) : (i32) -> i1
+    fir.result %i : index
+  }
+  return %v : index
+}
+
+// CHECK-LABEL:   func @x4(
+// CHECK-SAME:             %[[VAL_0:.*]]: index,
+// CHECK-SAME:             %[[VAL_1:.*]]: index) -> index {
+// CHECK:           %[[VAL_2:.*]] = constant 1 : index
+// CHECK:           %[[VAL_3:.*]] = subi %[[VAL_1]], %[[VAL_0]] : index
+// CHECK:           %[[VAL_4:.*]] = addi %[[VAL_3]], %[[VAL_2]] : index
+// CHECK:           %[[VAL_5:.*]] = divi_signed %[[VAL_4]], %[[VAL_2]] : index
+// CHECK:           br ^bb1(%[[VAL_0]], %[[VAL_5]] : index, index)
+// CHECK:         ^bb1(%[[VAL_6:.*]]: index, %[[VAL_7:.*]]: index):
+// CHECK:           %[[VAL_8:.*]] = constant 0 : index
+// CHECK:           %[[VAL_9:.*]] = cmpi sgt, %[[VAL_7]], %[[VAL_8]] : index
+// CHECK:           cond_br %[[VAL_9]], ^bb2, ^bb3
+// CHECK:         ^bb2:
+// CHECK:           %[[VAL_10:.*]] = fir.convert %[[VAL_6]] : (index) -> i32
+// CHECK:           %[[VAL_11:.*]] = fir.call @f4(%[[VAL_10]]) : (i32) -> i1
+// CHECK:           %[[VAL_12:.*]] = addi %[[VAL_6]], %[[VAL_2]] : index
+// CHECK:           %[[VAL_13:.*]] = constant 1 : index
+// CHECK:           %[[VAL_14:.*]] = subi %[[VAL_7]], %[[VAL_13]] : index
+// CHECK:           br ^bb1(%[[VAL_12]], %[[VAL_14]] : index, index)
+// CHECK:         ^bb3:
+// CHECK:           return %[[VAL_6]] : index
+// CHECK:         }
+
+// -----
+
+// iterate_while that returns the final value of both inductions
+func @y4(%lo : index, %up : index) -> index {
+  %c1 = constant 1 : index
+  %ok1 = constant true
+  %v:2 = fir.iterate_while (%i = %lo to %up step %c1) and (%ok2 = %ok1) -> (index, i1) {
+    %i1 = fir.convert %i : (index) -> i32
+    %ok = fir.call @f4(%i1) : (i32) -> i1
+    fir.result %i, %ok : index, i1
+  }
+  return %v#0 : index
+}
+
+// CHECK-LABEL:   func @y4(
+// CHECK-SAME:             %[[VAL_0:.*]]: index,
+// CHECK-SAME:             %[[VAL_1:.*]]: index) -> index {
+// CHECK:           %[[VAL_2:.*]] = constant 1 : index
+// CHECK:           %[[VAL_3:.*]] = constant true
+// CHECK:           br ^bb1(%[[VAL_0]], %[[VAL_3]] : index, i1)
+// CHECK:         ^bb1(%[[VAL_4:.*]]: index, %[[VAL_5:.*]]: i1):
+// CHECK:           %[[VAL_6:.*]] = constant 0 : index
+// CHECK:           %[[VAL_7:.*]] = cmpi slt, %[[VAL_6]], %[[VAL_2]] : index
+// CHECK:           %[[VAL_8:.*]] = cmpi sle, %[[VAL_4]], %[[VAL_1]] : index
+// CHECK:           %[[VAL_9:.*]] = cmpi slt, %[[VAL_2]], %[[VAL_6]] : index
+// CHECK:           %[[VAL_10:.*]] = cmpi sle, %[[VAL_1]], %[[VAL_4]] : index
+// CHECK:           %[[VAL_11:.*]] = and %[[VAL_7]], %[[VAL_8]] : i1
+// CHECK:           %[[VAL_12:.*]] = and %[[VAL_9]], %[[VAL_10]] : i1
+// CHECK:           %[[VAL_13:.*]] = or %[[VAL_11]], %[[VAL_12]] : i1
+// CHECK:           %[[VAL_14:.*]] = and %[[VAL_5]], %[[VAL_13]] : i1
+// CHECK:           cond_br %[[VAL_14]], ^bb2, ^bb3
+// CHECK:         ^bb2:
+// CHECK:           %[[VAL_15:.*]] = fir.convert %[[VAL_4]] : (index) -> i32
+// CHECK:           %[[VAL_16:.*]] = fir.call @f4(%[[VAL_15]]) : (i32) -> i1
+// CHECK:           %[[VAL_17:.*]] = addi %[[VAL_4]], %[[VAL_2]] : index
+// CHECK:           br ^bb1(%[[VAL_17]], %[[VAL_16]] : index, i1)
+// CHECK:         ^bb3:
+// CHECK:           return %[[VAL_4]] : index
+// CHECK:         }
+
+// -----
+
+// do_loop that returns the final induction value
+// and an extra loop-carried value
+func @x5(%lo : index, %up : index) -> index {
+  %c1 = constant 1 : index
+  %s1 = constant 42 : i16
+  %v:2 = fir.do_loop %i = %lo to %up step %c1 iter_args(%s = %s1) -> (index, i16) {
+    %ok = fir.call @f2() : () -> i1
+    %s2 = fir.convert %ok : (i1) -> i16
+    fir.result %i, %s2 : index, i16
+  }
+  fir.call @f3(%v#1) : (i16) -> ()
+  return %v#0 : index
+}
+
+// CHECK-LABEL:   func @x5(
+// CHECK-SAME:             %[[VAL_0:.*]]: index,
+// CHECK-SAME:             %[[VAL_1:.*]]: index) -> index {
+// CHECK:           %[[VAL_2:.*]] = constant 1 : index
+// CHECK:           %[[VAL_3:.*]] = constant 42 : i16
+// CHECK:           %[[VAL_4:.*]] = subi %[[VAL_1]], %[[VAL_0]] : index
+// CHECK:           %[[VAL_5:.*]] = addi %[[VAL_4]], %[[VAL_2]] : index
+// CHECK:           %[[VAL_6:.*]] = divi_signed %[[VAL_5]], %[[VAL_2]] : index
+// CHECK:           br ^bb1(%[[VAL_0]], %[[VAL_3]], %[[VAL_6]] : index, i16, index)
+// CHECK:         ^bb1(%[[VAL_7:.*]]: index, %[[VAL_8:.*]]: i16, %[[VAL_9:.*]]: index):
+// CHECK:           %[[VAL_10:.*]] = constant 0 : index
+// CHECK:           %[[VAL_11:.*]] = cmpi sgt, %[[VAL_9]], %[[VAL_10]] : index
+// CHECK:           cond_br %[[VAL_11]], ^bb2, ^bb3
+// CHECK:         ^bb2:
+// CHECK:           %[[VAL_12:.*]] = fir.call @f2() : () -> i1
+// CHECK:           %[[VAL_13:.*]] = fir.convert %[[VAL_12]] : (i1) -> i16
+// CHECK:           %[[VAL_14:.*]] = addi %[[VAL_7]], %[[VAL_2]] : index
+// CHECK:           %[[VAL_15:.*]] = constant 1 : index
+// CHECK:           %[[VAL_16:.*]] = subi %[[VAL_9]], %[[VAL_15]] : index
+// CHECK:           br ^bb1(%[[VAL_14]], %[[VAL_13]], %[[VAL_16]] : index, i16, index)
+// CHECK:         ^bb3:
+// CHECK:           fir.call @f3(%[[VAL_8]]) : (i16) -> ()
+// CHECK:           return %[[VAL_7]] : index
+// CHECK:         }
+
+// -----
+
+// iterate_while that returns the both induction values
+// and an extra loop-carried value
+func @y5(%lo : index, %up : index) -> index {
+  %c1 = constant 1 : index
+  %s1 = constant 42 : i16
+  %ok1 = constant true
+  %v:3 = fir.iterate_while (%i = %lo to %up step %c1) and (%ok2 = %ok1) iter_args(%s = %s1) -> (index, i1, i16) {
+    %ok = fir.call @f2() : () -> i1
+    %s2 = fir.convert %ok : (i1) -> i16
+    fir.result %i, %ok, %s2 : index, i1, i16
+  }
+  fir.if %v#1 {
+    %arg = constant 0 : i32
+    %ok4 = fir.call @f4(%arg) : (i32) -> i1
+  }
+  fir.call @f3(%v#2) : (i16) -> ()
+  return %v#0 : index
+}
+
+// CHECK-LABEL:   func @y5(
+// CHECK-SAME:             %[[VAL_0:.*]]: index,
+// CHECK-SAME:             %[[VAL_1:.*]]: index) -> index {
+// CHECK:           %[[VAL_2:.*]] = constant 1 : index
+// CHECK:           %[[VAL_3:.*]] = constant 42 : i16
+// CHECK:           %[[VAL_4:.*]] = constant true
+// CHECK:           br ^bb1(%[[VAL_0]], %[[VAL_4]], %[[VAL_3]] : index, i1, i16)
+// CHECK:         ^bb1(%[[VAL_5:.*]]: index, %[[VAL_6:.*]]: i1, %[[VAL_7:.*]]: i16):
+// CHECK:           %[[VAL_8:.*]] = constant 0 : index
+// CHECK:           %[[VAL_9:.*]] = cmpi slt, %[[VAL_8]], %[[VAL_2]] : index
+// CHECK:           %[[VAL_10:.*]] = cmpi sle, %[[VAL_5]], %[[VAL_1]] : index
+// CHECK:           %[[VAL_11:.*]] = cmpi slt, %[[VAL_2]], %[[VAL_8]] : index
+// CHECK:           %[[VAL_12:.*]] = cmpi sle, %[[VAL_1]], %[[VAL_5]] : index
+// CHECK:           %[[VAL_13:.*]] = and %[[VAL_9]], %[[VAL_10]] : i1
+// CHECK:           %[[VAL_14:.*]] = and %[[VAL_11]], %[[VAL_12]] : i1
+// CHECK:           %[[VAL_15:.*]] = or %[[VAL_13]], %[[VAL_14]] : i1
+// CHECK:           %[[VAL_16:.*]] = and %[[VAL_6]], %[[VAL_15]] : i1
+// CHECK:           cond_br %[[VAL_16]], ^bb2, ^bb3
+// CHECK:         ^bb2:
+// CHECK:           %[[VAL_17:.*]] = fir.call @f2() : () -> i1
+// CHECK:           %[[VAL_18:.*]] = fir.convert %[[VAL_17]] : (i1) -> i16
+// CHECK:           %[[VAL_19:.*]] = addi %[[VAL_5]], %[[VAL_2]] : index
+// CHECK:           br ^bb1(%[[VAL_19]], %[[VAL_17]], %[[VAL_18]] : index, i1, i16)
+// CHECK:         ^bb3:
+// CHECK:           cond_br %[[VAL_6]], ^bb4, ^bb5
+// CHECK:         ^bb4:
+// CHECK:           %[[VAL_20:.*]] = constant 0 : i32
+// CHECK:           %[[VAL_21:.*]] = fir.call @f4(%[[VAL_20]]) : (i32) -> i1
+// CHECK:           br ^bb5
+// CHECK:         ^bb5:
+// CHECK:           fir.call @f3(%[[VAL_7]]) : (i16) -> ()
+// CHECK:           return %[[VAL_5]] : index
+// CHECK:         }

flang/test/Fir/loop02.fir

+// RUN: fir-opt --cfg-conversion="always-execute-loop-body=true" %s | FileCheck %s
+// RUN: fir-opt --cfg-conversion %s | FileCheck %s --check-prefix=NOOPT
+
+func @x(%addr : !fir.ref<index>) {
+  %bound = constant 452 : index
+  %step = constant 1 : index
+  fir.do_loop %iv = %bound to %bound step %step {
+    fir.call @y(%addr) : (!fir.ref<index>) -> ()
+  }
+  return
+}
+
+func private @y(%addr : !fir.ref<index>)
+
+
+// CHECK-LABEL:   func @x(
+// CHECK-SAME:            %[[VAL_0:.*]]: !fir.ref<index>) {
+// CHECK:           %[[VAL_1:.*]] = constant 452 : index
+// CHECK:           %[[VAL_2:.*]] = constant 1 : index
+// CHECK:           %[[VAL_3:.*]] = subi %[[VAL_1]], %[[VAL_1]] : index
+// CHECK:           %[[VAL_4:.*]] = addi %[[VAL_3]], %[[VAL_2]] : index
+// CHECK:           %[[VAL_5:.*]] = divi_signed %[[VAL_4]], %[[VAL_2]] : index
+// CHECK:           %[[VAL_6:.*]] = constant 0 : index
+// CHECK:           %[[VAL_7:.*]] = cmpi sle, %[[VAL_5]], %[[VAL_6]] : index
+// CHECK:           %[[VAL_8:.*]] = constant 1 : index
+// CHECK:           %[[VAL_9:.*]] = select %[[VAL_7]], %[[VAL_8]], %[[VAL_5]] : index
+// CHECK:           br ^bb1(%[[VAL_1]], %[[VAL_9]] : index, index)
+// CHECK:         ^bb1(%[[VAL_10:.*]]: index, %[[VAL_11:.*]]: index):
+// CHECK:           %[[VAL_12:.*]] = constant 0 : index
+// CHECK:           %[[VAL_13:.*]] = cmpi sgt, %[[VAL_11]], %[[VAL_12]] : index
+// CHECK:           cond_br %[[VAL_13]], ^bb2, ^bb3
+// CHECK:         ^bb2:
+// CHECK:           fir.call @y(%[[VAL_0]]) : (!fir.ref<index>) -> ()
+// CHECK:           %[[VAL_14:.*]] = addi %[[VAL_10]], %[[VAL_2]] : index
+// CHECK:           %[[VAL_15:.*]] = constant 1 : index
+// CHECK:           %[[VAL_16:.*]] = subi %[[VAL_11]], %[[VAL_15]] : index
+// CHECK:           br ^bb1(%[[VAL_14]], %[[VAL_16]] : index, index)
+// CHECK:         ^bb3:
+// CHECK:           return
+// CHECK:         }
+// CHECK:         func private @y(!fir.ref<index>)
+
+// NOOPT-LABEL:   func @x(
+// NOOPT-SAME:            %[[VAL_0:.*]]: !fir.ref<index>) {
+// NOOPT:           %[[VAL_1:.*]] = constant 452 : index
+// NOOPT:           %[[VAL_2:.*]] = constant 1 : index
+// NOOPT:           %[[VAL_3:.*]] = subi %[[VAL_1]], %[[VAL_1]] : index
+// NOOPT:           %[[VAL_4:.*]] = addi %[[VAL_3]], %[[VAL_2]] : index
+// NOOPT:           %[[VAL_5:.*]] = divi_signed %[[VAL_4]], %[[VAL_2]] : index
+// NOOPT:           br ^bb1(%[[VAL_1]], %[[VAL_5]] : index, index)
+// NOOPT:         ^bb1(%[[VAL_6:.*]]: index, %[[VAL_7:.*]]: index):
+// NOOPT:           %[[VAL_8:.*]] = constant 0 : index
+// NOOPT:           %[[VAL_9:.*]] = cmpi sgt, %[[VAL_7]], %[[VAL_8]] : index
+// NOOPT:           cond_br %[[VAL_9]], ^bb2, ^bb3
+// NOOPT:         ^bb2:
+// NOOPT:           fir.call @y(%[[VAL_0]]) : (!fir.ref<index>) -> ()
+// NOOPT:           %[[VAL_10:.*]] = addi %[[VAL_6]], %[[VAL_2]] : index
+// NOOPT:           %[[VAL_11:.*]] = constant 1 : index
+// NOOPT:           %[[VAL_12:.*]] = subi %[[VAL_7]], %[[VAL_11]] : index
+// NOOPT:           br ^bb1(%[[VAL_10]], %[[VAL_12]] : index, index)
+// NOOPT:         ^bb3:
+// NOOPT:           return
+// NOOPT:         }
+// NOOPT:         func private @y(!fir.ref<index>)