diff --git a/llvm/include/llvm/InitializePasses.h b/llvm/include/llvm/InitializePasses.h --- a/llvm/include/llvm/InitializePasses.h +++ b/llvm/include/llvm/InitializePasses.h @@ -90,6 +90,7 @@ void initializeBreakCriticalEdgesPass(PassRegistry&); void initializeBreakFalseDepsPass(PassRegistry&); void initializeCanonicalizeAliasesLegacyPassPass(PassRegistry &); +void initializeCanonicalizeFreezeInLoopsPass(PassRegistry&); void initializeCFGOnlyPrinterLegacyPassPass(PassRegistry&); void initializeCFGOnlyViewerLegacyPassPass(PassRegistry&); void initializeCFGPrinterLegacyPassPass(PassRegistry&); diff --git a/llvm/include/llvm/Transforms/Utils.h b/llvm/include/llvm/Transforms/Utils.h --- a/llvm/include/llvm/Transforms/Utils.h +++ b/llvm/include/llvm/Transforms/Utils.h @@ -134,6 +134,14 @@ // exit blocks. // FunctionPass *createUnifyLoopExitsPass(); + +//===----------------------------------------------------------------------===// +// +// CanonicalizeFreezeInLoops - Canonicalize freeze instructions in loops so they +// don't block SCEV. +// +Pass *createCanonicalizeFreezeInLoopsPass(); + } #endif diff --git a/llvm/include/llvm/Transforms/Utils/CanonicalizeFreezeInLoops.h b/llvm/include/llvm/Transforms/Utils/CanonicalizeFreezeInLoops.h new file mode 100644 --- /dev/null +++ b/llvm/include/llvm/Transforms/Utils/CanonicalizeFreezeInLoops.h @@ -0,0 +1,32 @@ +//==- CanonicalizeFreezeInLoop.h - Canonicalize freezes in a loop-*- C++ -*-==// +// +// 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 +// +//===----------------------------------------------------------------------===// +// +// This file canonicalizes freeze instructions in a loop. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_UTILS_CANONICALIZE_FREEZES_IN_LOOPS_H +#define LLVM_TRANSFORMS_UTILS_CANONICALIZE_FREEZES_IN_LOOPS_H + +#include "llvm/Analysis/LoopInfo.h" +#include "llvm/IR/PassManager.h" +#include "llvm/Transforms/Scalar/LoopPassManager.h" + +namespace llvm { + +/// A pass that canonicalizes freeze instructions in a loop. +class CanonicalizeFreezeInLoopsPass + : public PassInfoMixin { +public: + PreservedAnalyses run(Loop &L, LoopAnalysisManager &AM, + LoopStandardAnalysisResults &AR, LPMUpdater &U); +}; + +} // end namespace llvm + +#endif // LLVM_TRANSFORMS_UTILS_CANONICALIZE_FREEZES_IN_LOOPS_H diff --git a/llvm/lib/Passes/PassBuilder.cpp b/llvm/lib/Passes/PassBuilder.cpp --- a/llvm/lib/Passes/PassBuilder.cpp +++ b/llvm/lib/Passes/PassBuilder.cpp @@ -178,6 +178,7 @@ #include "llvm/Transforms/Utils/AssumeBundleBuilder.h" #include "llvm/Transforms/Utils/BreakCriticalEdges.h" #include "llvm/Transforms/Utils/CanonicalizeAliases.h" +#include "llvm/Transforms/Utils/CanonicalizeFreezeInLoops.h" #include "llvm/Transforms/Utils/EntryExitInstrumenter.h" #include "llvm/Transforms/Utils/InjectTLIMappings.h" #include "llvm/Transforms/Utils/LCSSA.h" diff --git a/llvm/lib/Passes/PassRegistry.def b/llvm/lib/Passes/PassRegistry.def --- a/llvm/lib/Passes/PassRegistry.def +++ b/llvm/lib/Passes/PassRegistry.def @@ -311,6 +311,7 @@ #ifndef LOOP_PASS #define LOOP_PASS(NAME, CREATE_PASS) #endif +LOOP_PASS("canon-freeze", CanonicalizeFreezeInLoopsPass()) LOOP_PASS("invalidate", InvalidateAllAnalysesPass()) LOOP_PASS("licm", LICMPass()) LOOP_PASS("loop-idiom", LoopIdiomRecognizePass()) diff --git a/llvm/lib/Transforms/Utils/CMakeLists.txt b/llvm/lib/Transforms/Utils/CMakeLists.txt --- a/llvm/lib/Transforms/Utils/CMakeLists.txt +++ b/llvm/lib/Transforms/Utils/CMakeLists.txt @@ -10,6 +10,7 @@ CallPromotionUtils.cpp CallGraphUpdater.cpp CanonicalizeAliases.cpp + CanonicalizeFreezeInLoops.cpp CloneFunction.cpp CloneModule.cpp CodeExtractor.cpp diff --git a/llvm/lib/Transforms/Utils/CanonicalizeFreezeInLoops.cpp b/llvm/lib/Transforms/Utils/CanonicalizeFreezeInLoops.cpp new file mode 100644 --- /dev/null +++ b/llvm/lib/Transforms/Utils/CanonicalizeFreezeInLoops.cpp @@ -0,0 +1,241 @@ +//==- CanonicalizeFreezeInLoops - Canonicalize freezes in a loop-*- C++ -*-===// +// +// 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 +// +//===----------------------------------------------------------------------===// +// +// This pass canonicalizes freeze instructions in a loop. +// Freeze instructions that use induction variables are pushed out of the loop. +// This helps scalar evolution not be blocked by frozen variables. +// +// +// loop: +// i = phi init, i.next +// i.next = add nsw i, 1 +// i.next.fr = freeze i.next // push this out of this loop +// cond = icmp i.next.fr, N +// br i1 cond, loop, exit +// => +// +// init.fr = freeze init +// loop: +// i = phi init.fr, i.next +// i.next = add i, 1 +// cond = icmp i.next, N +// br i1 cond, loop, exit +// +//===----------------------------------------------------------------------===// + +#include "llvm/Transforms/Utils/CanonicalizeFreezeInLoops.h" +#include "llvm/ADT/SmallVector.h" +#include "llvm/Analysis/IVUsers.h" +#include "llvm/Analysis/LoopAnalysisManager.h" +#include "llvm/Analysis/LoopInfo.h" +#include "llvm/Analysis/LoopPass.h" +#include "llvm/Analysis/ValueTracking.h" +#include "llvm/IR/PatternMatch.h" +#include "llvm/InitializePasses.h" +#include "llvm/Pass.h" +#include "llvm/Support/Debug.h" +#include "llvm/Transforms/Utils.h" + +using namespace llvm; +using namespace PatternMatch; + +#define DEBUG_TYPE "canon-freeze" + +namespace { + +class CanonicalizeFreezeInLoops : public LoopPass { +public: + static char ID; + + CanonicalizeFreezeInLoops(); + +private: + bool runOnLoop(Loop *L, LPPassManager &LPM) override; + void getAnalysisUsage(AnalysisUsage &AU) const override; +}; + +/// A class that describes induction variable / frozen value / step values +/// which is a candidate for canonicalization. +struct Candidate { + FreezeInst *FI; + PHINode *IndVar; + BinaryOperator *SteppingInst; + Value *Step; + + Candidate(FreezeInst *FI, PHINode *Ind, BinaryOperator *StepInst, Value *Step) + : FI(FI), IndVar(Ind), SteppingInst(StepInst), Step(Step) {} +}; + +} // anonymous namespace + +static bool CanonicalizeFreezes(Loop *L, ScalarEvolution &SE, LoopInfo &LI, + DominatorTree &DT) { + // Assumes that the loop is in LoopSimplify form, having only single backedge. + if (!L->isLoopSimplifyForm()) + return false; + + SmallVector Candidates; + + for (auto *BB : L->blocks()) { + for (auto &I : *BB) { + auto *FI = dyn_cast(&I); + if (!FI) + continue; + if (FI->user_empty()) { + // Dead instruction. Remove this + SE.forgetValue(FI); + FI->eraseFromParent(); + continue; + } + + PHINode *PN = nullptr; + BinaryOperator *SteppingInst = nullptr; + BasicBlock *Latch = L->getLoopLatch(); + + // Consider freeze instructions on induction variables only (auxiliary + // induction variables allowed) + if ((PN = dyn_cast(FI->getOperand(0)))) { + if (!L->isAuxiliaryInductionVariable(*PN, SE)) + continue; + + auto *I = PN->getIncomingValueForBlock(Latch); + SteppingInst = dyn_cast(I); + } else if ((SteppingInst = dyn_cast(FI->getOperand(0)))) { + auto IsAuxiliaryIndVar = [&](unsigned OpIdx, PHINode *&ResPN) -> bool { + PHINode *I = dyn_cast(SteppingInst->getOperand(OpIdx)); + if (I && L->isAuxiliaryInductionVariable(*I, SE)) { + ResPN = I; + return true; + } + return false; + }; + + if (!IsAuxiliaryIndVar(0, PN) && !IsAuxiliaryIndVar(1, PN)) + continue; + assert(SteppingInst == PN->getIncomingValueForBlock(Latch)); + } else + continue; + + assert(PN && "Induction variable isn't found!"); + assert(SteppingInst && "Increment operation isn't found!"); + assert((SteppingInst->getOpcode() == Instruction::Add || + SteppingInst->getOpcode() == Instruction::Sub) && + "Unknown opcode"); + + // If it isn't beneficial to freeze the step, skip this + Value *Step = SteppingInst->getOperand(SteppingInst->getOperand(0) == PN); + if (auto *StepI = dyn_cast(Step)) { + BasicBlock *StepBB = StepI->getParent(); + if (L->contains(StepBB)) { + // Step instruction is in the body. Freezing this can possibly block + // SCEV. + continue; + } + } + Candidates.emplace_back(FI, PN, SteppingInst, Step); + } + } + + for (auto &Candidate : Candidates) { + PHINode *PN = Candidate.IndVar; + BinaryOperator *SteppingInst = Candidate.SteppingInst; + BasicBlock *PH = L->getLoopPreheader(); + FreezeInst *FI = Candidate.FI; + + LLVM_DEBUG(dbgs() << "CanonFr: PN: " << *PN << "\n" + << "CanonFr: " << *SteppingInst << "\n" + << "CanonFr: " << *FI << "\n"); + + if (!isGuaranteedNotToBeUndefOrPoison(SteppingInst, SteppingInst, &DT)) { + // Drop any flag on the stepping instruction. + SteppingInst->dropPoisonGeneratingFlags(); + SE.forgetValue(SteppingInst); + } + + // Freeze the step value. + Value *StepValue = Candidate.Step; + if (!isGuaranteedNotToBeUndefOrPoison(StepValue, PN, &DT)) { + unsigned OpIdx = SteppingInst->getOperand(1) == StepValue; + SteppingInst->setOperand( + OpIdx, new FreezeInst(StepValue, StepValue->getName() + ".frozen", + PH->getTerminator())); + + auto *StepI = dyn_cast(StepValue); + if (StepI && StepI->user_empty()) { + if (L->contains(StepI->getParent())) + SE.forgetValue(StepI); + StepI->eraseFromParent(); + } + } + + // Freeze the initial value. + Value *InitialValue = PN->getIncomingValueForBlock(PH); + if (!isGuaranteedNotToBeUndefOrPoison(InitialValue, PN, &DT)) { + PN->setIncomingValueForBlock( + PH, new FreezeInst(InitialValue, InitialValue->getName() + ".frozen", + PH->getTerminator())); + SE.forgetValue(PN); + } + + // Replace uses of the original frozen value with its operand. + SE.forgetValue(FI); + FI->replaceAllUsesWith(FI->getOperand(0)); + FI->eraseFromParent(); + } + return Candidates.size() > 0; +} + +CanonicalizeFreezeInLoops::CanonicalizeFreezeInLoops() : LoopPass(ID) { + initializeCanonicalizeFreezeInLoopsPass(*PassRegistry::getPassRegistry()); +} + +void CanonicalizeFreezeInLoops::getAnalysisUsage(AnalysisUsage &AU) const { + AU.addPreservedID(LoopSimplifyID); + AU.addRequired(); + AU.addPreserved(); + AU.addRequiredID(LoopSimplifyID); + AU.addRequired(); + AU.addPreserved(); + AU.addRequired(); + AU.addPreserved(); +} + +bool CanonicalizeFreezeInLoops::runOnLoop(Loop *L, LPPassManager &) { + if (skipLoop(L)) + return false; + + auto &SE = getAnalysis().getSE(); + auto &LI = getAnalysis().getLoopInfo(); + auto &DT = getAnalysis().getDomTree(); + return CanonicalizeFreezes(L, SE, LI, DT); +} + +PreservedAnalyses +CanonicalizeFreezeInLoopsPass::run(Loop &L, LoopAnalysisManager &AM, + LoopStandardAnalysisResults &AR, + LPMUpdater &U) { + if (!CanonicalizeFreezes(&L, AR.SE, AR.LI, AR.DT)) + return PreservedAnalyses::all(); + + return getLoopPassPreservedAnalyses(); +} + +INITIALIZE_PASS_BEGIN(CanonicalizeFreezeInLoops, "canon-freeze", + "Canonicalize Freeze Instructions in Loops", false, false) +INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) +INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass) +INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass) +INITIALIZE_PASS_DEPENDENCY(LoopSimplify) +INITIALIZE_PASS_END(CanonicalizeFreezeInLoops, "canon-freeze", + "Canonicalize Freeze Instructions in Loops", false, false) + +Pass *llvm::createCanonicalizeFreezeInLoopsPass() { + return new CanonicalizeFreezeInLoops(); +} + +char CanonicalizeFreezeInLoops::ID = 0; \ No newline at end of file diff --git a/llvm/lib/Transforms/Utils/Utils.cpp b/llvm/lib/Transforms/Utils/Utils.cpp --- a/llvm/lib/Transforms/Utils/Utils.cpp +++ b/llvm/lib/Transforms/Utils/Utils.cpp @@ -26,6 +26,7 @@ initializeAddDiscriminatorsLegacyPassPass(Registry); initializeBreakCriticalEdgesPass(Registry); initializeCanonicalizeAliasesLegacyPassPass(Registry); + initializeCanonicalizeFreezeInLoopsPass(Registry); initializeInstNamerPass(Registry); initializeLCSSAWrapperPassPass(Registry); initializeLibCallsShrinkWrapLegacyPassPass(Registry); diff --git a/llvm/test/Transforms/CanonicalizeFreezeInLoops/simple.ll b/llvm/test/Transforms/CanonicalizeFreezeInLoops/simple.ll new file mode 100644 --- /dev/null +++ b/llvm/test/Transforms/CanonicalizeFreezeInLoops/simple.ll @@ -0,0 +1,336 @@ +; NOTE: Assertions have been autogenerated by utils/update_test_checks.py +; RUN: opt < %s -canon-freeze -S | FileCheck %s +target triple = "aarch64-unknown-linux-gnu" +declare void @call(i32) +declare i32 @get_step() + +define void @add(i32 %init, i32 %n) { +; CHECK-LABEL: @add( +; CHECK-NEXT: entry: +; CHECK-NEXT: [[INIT_FROZEN:%.*]] = freeze i32 [[INIT:%.*]] +; CHECK-NEXT: br label [[LOOP:%.*]] +; CHECK: loop: +; CHECK-NEXT: [[I:%.*]] = phi i32 [ [[INIT_FROZEN]], [[ENTRY:%.*]] ], [ [[I_NEXT:%.*]], [[LOOP]] ] +; CHECK-NEXT: [[I_NEXT]] = add i32 [[I]], 1 +; CHECK-NEXT: call void @call(i32 [[I]]) +; CHECK-NEXT: [[COND:%.*]] = icmp eq i32 [[I_NEXT]], [[N:%.*]] +; CHECK-NEXT: br i1 [[COND]], label [[LOOP]], label [[EXIT:%.*]] +; CHECK: exit: +; CHECK-NEXT: ret void +; +entry: + br label %loop +loop: + %i = phi i32 [%init, %entry], [%i.next, %loop] + %i.fr = freeze i32 %i + %i.next = add i32 %i, 1 + call void @call(i32 %i.fr) + %cond = icmp eq i32 %i.next, %n + br i1 %cond, label %loop, label %exit +exit: + ret void +} + +define void @add2(i32 %init, i32 %n) { +; CHECK-LABEL: @add2( +; CHECK-NEXT: entry: +; CHECK-NEXT: [[INIT_FROZEN:%.*]] = freeze i32 [[INIT:%.*]] +; CHECK-NEXT: br label [[LOOP:%.*]] +; CHECK: loop: +; CHECK-NEXT: [[I:%.*]] = phi i32 [ [[INIT_FROZEN]], [[ENTRY:%.*]] ], [ [[I_NEXT:%.*]], [[LOOP]] ] +; CHECK-NEXT: [[I_NEXT]] = add i32 1, [[I]] +; CHECK-NEXT: call void @call(i32 [[I]]) +; CHECK-NEXT: [[COND:%.*]] = icmp eq i32 [[I_NEXT]], [[N:%.*]] +; CHECK-NEXT: br i1 [[COND]], label [[LOOP]], label [[EXIT:%.*]] +; CHECK: exit: +; CHECK-NEXT: ret void +; +entry: + br label %loop +loop: + %i = phi i32 [%init, %entry], [%i.next, %loop] + %i.fr = freeze i32 %i + %i.next = add i32 1, %i + call void @call(i32 %i.fr) + %cond = icmp eq i32 %i.next, %n + br i1 %cond, label %loop, label %exit +exit: + ret void +} + +define void @add3(i32 %init, i32 %n) { +; CHECK-LABEL: @add3( +; CHECK-NEXT: entry: +; CHECK-NEXT: [[INIT_FROZEN:%.*]] = freeze i32 [[INIT:%.*]] +; CHECK-NEXT: br label [[LOOP:%.*]] +; CHECK: loop: +; CHECK-NEXT: [[I:%.*]] = phi i32 [ [[INIT_FROZEN]], [[ENTRY:%.*]] ], [ [[I_NEXT:%.*]], [[LOOP]] ] +; CHECK-NEXT: [[I_NEXT]] = add i32 1, [[I]] +; CHECK-NEXT: call void @call(i32 [[I_NEXT]]) +; CHECK-NEXT: [[COND:%.*]] = icmp eq i32 [[I_NEXT]], [[N:%.*]] +; CHECK-NEXT: br i1 [[COND]], label [[LOOP]], label [[EXIT:%.*]] +; CHECK: exit: +; CHECK-NEXT: ret void +; +entry: + br label %loop +loop: + %i = phi i32 [%init, %entry], [%i.next, %loop] + %i.next = add i32 1, %i + %i.next.fr = freeze i32 %i.next + call void @call(i32 %i.next.fr) + %cond = icmp eq i32 %i.next, %n + br i1 %cond, label %loop, label %exit +exit: + ret void +} + +define void @add_nooverflow(i32 %init, i32 %n) { +; CHECK-LABEL: @add_nooverflow( +; CHECK-NEXT: entry: +; CHECK-NEXT: [[INIT_FROZEN:%.*]] = freeze i32 [[INIT:%.*]] +; CHECK-NEXT: br label [[LOOP:%.*]] +; CHECK: loop: +; CHECK-NEXT: [[I:%.*]] = phi i32 [ [[INIT_FROZEN]], [[ENTRY:%.*]] ], [ [[I_NEXT:%.*]], [[LOOP]] ] +; CHECK-NEXT: [[I_NEXT]] = add i32 [[I]], 1 +; CHECK-NEXT: call void @call(i32 [[I]]) +; CHECK-NEXT: [[COND:%.*]] = icmp eq i32 [[I_NEXT]], [[N:%.*]] +; CHECK-NEXT: br i1 [[COND]], label [[LOOP]], label [[EXIT:%.*]] +; CHECK: exit: +; CHECK-NEXT: ret void +; +entry: + br label %loop +loop: + %i = phi i32 [%init, %entry], [%i.next, %loop] + %i.fr = freeze i32 %i + %i.next = add nsw nuw i32 %i, 1 + call void @call(i32 %i.fr) + %cond = icmp eq i32 %i.next, %n + br i1 %cond, label %loop, label %exit +exit: + ret void +} + +define void @sub(i32 %init, i32 %n) { +; CHECK-LABEL: @sub( +; CHECK-NEXT: entry: +; CHECK-NEXT: [[INIT_FROZEN:%.*]] = freeze i32 [[INIT:%.*]] +; CHECK-NEXT: br label [[LOOP:%.*]] +; CHECK: loop: +; CHECK-NEXT: [[I:%.*]] = phi i32 [ [[INIT_FROZEN]], [[ENTRY:%.*]] ], [ [[I_NEXT:%.*]], [[LOOP]] ] +; CHECK-NEXT: [[I_NEXT]] = sub i32 [[I]], 1 +; CHECK-NEXT: call void @call(i32 [[I]]) +; CHECK-NEXT: [[COND:%.*]] = icmp eq i32 [[I_NEXT]], [[N:%.*]] +; CHECK-NEXT: br i1 [[COND]], label [[LOOP]], label [[EXIT:%.*]] +; CHECK: exit: +; CHECK-NEXT: ret void +; +entry: + br label %loop +loop: + %i = phi i32 [%init, %entry], [%i.next, %loop] + %i.fr = freeze i32 %i + %i.next = sub i32 %i, 1 + call void @call(i32 %i.fr) + %cond = icmp eq i32 %i.next, %n + br i1 %cond, label %loop, label %exit +exit: + ret void +} + +define void @sub_nooverflow(i32 %init, i32 %n) { +; CHECK-LABEL: @sub_nooverflow( +; CHECK-NEXT: entry: +; CHECK-NEXT: [[INIT_FROZEN:%.*]] = freeze i32 [[INIT:%.*]] +; CHECK-NEXT: br label [[LOOP:%.*]] +; CHECK: loop: +; CHECK-NEXT: [[I:%.*]] = phi i32 [ [[INIT_FROZEN]], [[ENTRY:%.*]] ], [ [[I_NEXT:%.*]], [[LOOP]] ] +; CHECK-NEXT: [[I_NEXT]] = sub i32 [[I]], 1 +; CHECK-NEXT: call void @call(i32 [[I]]) +; CHECK-NEXT: [[COND:%.*]] = icmp eq i32 [[I_NEXT]], [[N:%.*]] +; CHECK-NEXT: br i1 [[COND]], label [[LOOP]], label [[EXIT:%.*]] +; CHECK: exit: +; CHECK-NEXT: ret void +; +entry: + br label %loop +loop: + %i = phi i32 [%init, %entry], [%i.next, %loop] + %i.fr = freeze i32 %i + %i.next = sub nsw nuw i32 %i, 1 + call void @call(i32 %i.fr) + %cond = icmp eq i32 %i.next, %n + br i1 %cond, label %loop, label %exit +exit: + ret void +} + +define void @next_frozen(i32 %init, i32 %n) { +; CHECK-LABEL: @next_frozen( +; CHECK-NEXT: entry: +; CHECK-NEXT: [[INIT_FROZEN:%.*]] = freeze i32 [[INIT:%.*]] +; CHECK-NEXT: br label [[LOOP:%.*]] +; CHECK: loop: +; CHECK-NEXT: [[I:%.*]] = phi i32 [ [[INIT_FROZEN]], [[ENTRY:%.*]] ], [ [[I_NEXT:%.*]], [[LOOP]] ] +; CHECK-NEXT: [[I_NEXT]] = add i32 [[I]], 1 +; CHECK-NEXT: call void @call(i32 [[I_NEXT]]) +; CHECK-NEXT: [[COND:%.*]] = icmp eq i32 [[I_NEXT]], [[N:%.*]] +; CHECK-NEXT: br i1 [[COND]], label [[LOOP]], label [[EXIT:%.*]] +; CHECK: exit: +; CHECK-NEXT: ret void +; +entry: + br label %loop +loop: + %i = phi i32 [%init, %entry], [%i.next, %loop] + %i.next = add nsw nuw i32 %i, 1 + %i.next.fr = freeze i32 %i.next + call void @call(i32 %i.next.fr) + %cond = icmp eq i32 %i.next, %n + br i1 %cond, label %loop, label %exit +exit: + ret void +} + +define void @init_const(i32 %n) { +; CHECK-LABEL: @init_const( +; CHECK-NEXT: entry: +; CHECK-NEXT: br label [[LOOP:%.*]] +; CHECK: loop: +; CHECK-NEXT: [[I:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[I_NEXT:%.*]], [[LOOP]] ] +; CHECK-NEXT: [[I_NEXT]] = add i32 [[I]], 1 +; CHECK-NEXT: call void @call(i32 [[I_NEXT]]) +; CHECK-NEXT: [[COND:%.*]] = icmp eq i32 [[I_NEXT]], [[N:%.*]] +; CHECK-NEXT: br i1 [[COND]], label [[LOOP]], label [[EXIT:%.*]] +; CHECK: exit: +; CHECK-NEXT: ret void +; +entry: + br label %loop +loop: + %i = phi i32 [0, %entry], [%i.next, %loop] + %i.next = add nsw nuw i32 %i, 1 + %i.next.fr = freeze i32 %i.next + call void @call(i32 %i.next.fr) + %cond = icmp eq i32 %i.next, %n + br i1 %cond, label %loop, label %exit +exit: + ret void +} + +define void @step(i32 %init, i32 %n, i32 %step) { +; CHECK-LABEL: @step( +; CHECK-NEXT: entry: +; CHECK-NEXT: [[STEP_FROZEN:%.*]] = freeze i32 [[STEP:%.*]] +; CHECK-NEXT: [[INIT_FROZEN:%.*]] = freeze i32 [[INIT:%.*]] +; CHECK-NEXT: br label [[LOOP:%.*]] +; CHECK: loop: +; CHECK-NEXT: [[I:%.*]] = phi i32 [ [[INIT_FROZEN]], [[ENTRY:%.*]] ], [ [[I_NEXT:%.*]], [[LOOP]] ] +; CHECK-NEXT: [[I_NEXT]] = add i32 [[I]], [[STEP_FROZEN]] +; CHECK-NEXT: call void @call(i32 [[I_NEXT]]) +; CHECK-NEXT: [[COND:%.*]] = icmp eq i32 [[I_NEXT]], [[N:%.*]] +; CHECK-NEXT: br i1 [[COND]], label [[LOOP]], label [[EXIT:%.*]] +; CHECK: exit: +; CHECK-NEXT: ret void +; +entry: + br label %loop +loop: + %i = phi i32 [%init, %entry], [%i.next, %loop] + %i.next = add nsw nuw i32 %i, %step + %i.next.fr = freeze i32 %i.next + call void @call(i32 %i.next.fr) + %cond = icmp eq i32 %i.next, %n + br i1 %cond, label %loop, label %exit +exit: + ret void +} + +define void @step_inst_preheader(i32 %init, i32 %n) { +; CHECK-LABEL: @step_inst_preheader( +; CHECK-NEXT: entry: +; CHECK-NEXT: [[STEP:%.*]] = call i32 @get_step() +; CHECK-NEXT: [[STEP_FROZEN:%.*]] = freeze i32 [[STEP]] +; CHECK-NEXT: [[INIT_FROZEN:%.*]] = freeze i32 [[INIT:%.*]] +; CHECK-NEXT: br label [[LOOP:%.*]] +; CHECK: loop: +; CHECK-NEXT: [[I:%.*]] = phi i32 [ [[INIT_FROZEN]], [[ENTRY:%.*]] ], [ [[I_NEXT:%.*]], [[LOOP]] ] +; CHECK-NEXT: [[I_NEXT]] = add i32 [[I]], [[STEP_FROZEN]] +; CHECK-NEXT: call void @call(i32 [[I_NEXT]]) +; CHECK-NEXT: [[COND:%.*]] = icmp eq i32 [[I_NEXT]], [[N:%.*]] +; CHECK-NEXT: br i1 [[COND]], label [[LOOP]], label [[EXIT:%.*]] +; CHECK: exit: +; CHECK-NEXT: ret void +; +entry: + %step = call i32 @get_step() + br label %loop +loop: + %i = phi i32 [%init, %entry], [%i.next, %loop] + %i.next = add nsw nuw i32 %i, %step + %i.next.fr = freeze i32 %i.next + call void @call(i32 %i.next.fr) + %cond = icmp eq i32 %i.next, %n + br i1 %cond, label %loop, label %exit +exit: + ret void +} + +; negative test +define void @step_inst(i32 %init, i32 %n) { +; CHECK-LABEL: @step_inst( +; CHECK-NEXT: entry: +; CHECK-NEXT: br label [[LOOP:%.*]] +; CHECK: loop: +; CHECK-NEXT: [[I:%.*]] = phi i32 [ [[INIT:%.*]], [[ENTRY:%.*]] ], [ [[I_NEXT:%.*]], [[LOOP]] ] +; CHECK-NEXT: [[I_NEXT]] = add nuw nsw i32 [[I]], [[I]] +; CHECK-NEXT: [[I_NEXT_FR:%.*]] = freeze i32 [[I_NEXT]] +; CHECK-NEXT: call void @call(i32 [[I_NEXT_FR]]) +; CHECK-NEXT: [[COND:%.*]] = icmp eq i32 [[I_NEXT]], [[N:%.*]] +; CHECK-NEXT: br i1 [[COND]], label [[LOOP]], label [[EXIT:%.*]] +; CHECK: exit: +; CHECK-NEXT: ret void +; +entry: + br label %loop +loop: + %i = phi i32 [%init, %entry], [%i.next, %loop] + %i.next = add nsw nuw i32 %i, %i + %i.next.fr = freeze i32 %i.next + call void @call(i32 %i.next.fr) + %cond = icmp eq i32 %i.next, %n + br i1 %cond, label %loop, label %exit +exit: + ret void +} + +; negative test +define void @freeze_non_indvar(i32 %init, i32 %n) { +; CHECK-LABEL: @freeze_non_indvar( +; CHECK-NEXT: entry: +; CHECK-NEXT: br label [[LOOP:%.*]] +; CHECK: loop: +; CHECK-NEXT: [[I:%.*]] = phi i32 [ [[INIT:%.*]], [[ENTRY:%.*]] ], [ [[I_NEXT:%.*]], [[LOOP]] ] +; CHECK-NEXT: [[I_NEXT]] = add nuw nsw i32 [[I]], 1 +; CHECK-NEXT: [[J:%.*]] = udiv i32 [[I_NEXT]], 2 +; CHECK-NEXT: [[J_FR:%.*]] = freeze i32 [[J]] +; CHECK-NEXT: call void @call(i32 [[J_FR]]) +; CHECK-NEXT: [[COND:%.*]] = icmp eq i32 [[I_NEXT]], [[N:%.*]] +; CHECK-NEXT: br i1 [[COND]], label [[LOOP]], label [[EXIT:%.*]] +; CHECK: exit: +; CHECK-NEXT: ret void +; +entry: + br label %loop +loop: + %i = phi i32 [%init, %entry], [%i.next, %loop] + %i.next = add nsw nuw i32 %i, 1 + %j = udiv i32 %i.next, 2 + %j.fr = freeze i32 %j + call void @call(i32 %j.fr) + %cond = icmp eq i32 %i.next, %n + br i1 %cond, label %loop, label %exit +exit: + ret void +}