llvm/lib/Transforms/Utils/CanonicalizeFreezeInLoops.cpp

   1 //==- CanonicalizeFreezeInLoops - Canonicalize freezes in a loop-*- C++ -*-===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 //
   9 // This pass canonicalizes freeze instructions in a loop by pushing them out to
  10 // the preheader.
  11 //
  12 //   loop:
  13 //     i = phi init, i.next
  14 //     i.next = add nsw i, 1
  15 //     i.next.fr = freeze i.next // push this out of this loop
  16 //     use(i.next.fr)
  17 //     br i1 (i.next <= N), loop, exit
  18 //   =>
  19 //     init.fr = freeze init
  20 //   loop:
  21 //     i = phi init.fr, i.next
  22 //     i.next = add i, 1         // nsw is dropped here
  23 //     use(i.next)
  24 //     br i1 (i.next <= N), loop, exit
  25 //
  26 // Removing freezes from these chains help scalar evolution successfully analyze
  27 // expressions.
  28 //
  29 //===----------------------------------------------------------------------===//
  30
  31 #include "llvm/Transforms/Utils/CanonicalizeFreezeInLoops.h"
  32 #include "llvm/ADT/STLExtras.h"
  33 #include "llvm/ADT/SmallVector.h"
  34 #include "llvm/Analysis/IVDescriptors.h"
  35 #include "llvm/Analysis/LoopAnalysisManager.h"
  36 #include "llvm/Analysis/LoopInfo.h"
  37 #include "llvm/Analysis/LoopPass.h"
  38 #include "llvm/Analysis/ScalarEvolution.h"
  39 #include "llvm/Analysis/ValueTracking.h"
  40 #include "llvm/IR/Dominators.h"
  41 #include "llvm/InitializePasses.h"
  42 #include "llvm/Pass.h"
  43 #include "llvm/Support/Debug.h"
  44 #include "llvm/Transforms/Utils.h"
  45
  46 using namespace llvm;
  47
  48 #define DEBUG_TYPE "canon-freeze"
  49
  50 namespace {
  51
  52 class CanonicalizeFreezeInLoops : public LoopPass {
  53 public:
  54   static char ID;
  55
  56   CanonicalizeFreezeInLoops();
  57
  58 private:
  59   bool runOnLoop(Loop *L, LPPassManager &LPM) override;
  60   void getAnalysisUsage(AnalysisUsage &AU) const override;
  61 };
  62
  63 class CanonicalizeFreezeInLoopsImpl {
  64   Loop *L;
  65   ScalarEvolution &SE;
  66   DominatorTree &DT;
  67
  68   struct FrozenIndPHIInfo {
  69     // A freeze instruction that uses an induction phi
  70     FreezeInst *FI = nullptr;
  71     // The induction phi, step instruction, the operand idx of StepInst which is
  72     // a step value
  73     PHINode *PHI;
  74     BinaryOperator *StepInst;
  75     unsigned StepValIdx = 0;
  76
  77     FrozenIndPHIInfo(PHINode *PHI, BinaryOperator *StepInst)
  78         : PHI(PHI), StepInst(StepInst) {}
  79   };
  80
  81   // Can freeze instruction be pushed into operands of I?
  82   // In order to do this, I should not create a poison after I's flags are
  83   // stripped.
  84   bool canHandleInst(const Instruction *I) {
  85     auto Opc = I->getOpcode();
  86     // If add/sub/mul, drop nsw/nuw flags.
  87     return Opc == Instruction::Add || Opc == Instruction::Sub ||
  88            Opc == Instruction::Mul;
  89   }
  90
  91   void InsertFreezeAndForgetFromSCEV(Use &U);
  92
  93 public:
  94   CanonicalizeFreezeInLoopsImpl(Loop *L, ScalarEvolution &SE, DominatorTree &DT)
  95       : L(L), SE(SE), DT(DT) {}
  96   bool run();
  97 };
  98
  99 } // anonymous namespace
 100
 101 // Given U = (value, user), replace value with freeze(value), and let
 102 // SCEV forget user. The inserted freeze is placed in the preheader.
 103 void CanonicalizeFreezeInLoopsImpl::InsertFreezeAndForgetFromSCEV(Use &U) {
 104   auto *PH = L->getLoopPreheader();
 105
 106   auto *UserI = cast<Instruction>(U.getUser());
 107   auto *ValueToFr = U.get();
 108   assert(L->contains(UserI->getParent()) &&
 109          "Should not process an instruction that isn't inside the loop");
 110   if (isGuaranteedNotToBeUndefOrPoison(ValueToFr, nullptr, UserI, &DT))
 111     return;
 112
 113   LLVM_DEBUG(dbgs() << "canonfr: inserting freeze:\n");
 114   LLVM_DEBUG(dbgs() << "\tUser: " << *U.getUser() << "\n");
 115   LLVM_DEBUG(dbgs() << "\tOperand: " << *U.get() << "\n");
 116
 117   U.set(new FreezeInst(ValueToFr, ValueToFr->getName() + ".frozen",
 118                        PH->getTerminator()));
 119
 120   SE.forgetValue(UserI);
 121 }
 122
 123 bool CanonicalizeFreezeInLoopsImpl::run() {
 124   // The loop should be in LoopSimplify form.
 125   if (!L->isLoopSimplifyForm())
 126     return false;
 127
 128   SmallVector<FrozenIndPHIInfo, 4> Candidates;
 129
 130   for (auto &PHI : L->getHeader()->phis()) {
 131     InductionDescriptor ID;
 132     if (!InductionDescriptor::isInductionPHI(&PHI, L, &SE, ID))
 133       continue;
 134
 135     LLVM_DEBUG(dbgs() << "canonfr: PHI: " << PHI << "\n");
 136     FrozenIndPHIInfo Info(&PHI, ID.getInductionBinOp());
 137     if (!Info.StepInst || !canHandleInst(Info.StepInst)) {
 138       // The stepping instruction has unknown form.
 139       // Ignore this PHI.
 140       continue;
 141     }
 142
 143     Info.StepValIdx = Info.StepInst->getOperand(0) == &PHI;
 144     Value *StepV = Info.StepInst->getOperand(Info.StepValIdx);
 145     if (auto *StepI = dyn_cast<Instruction>(StepV)) {
 146       if (L->contains(StepI->getParent())) {
 147         // The step value is inside the loop. Freezing step value will introduce
 148         // another freeze into the loop, so skip this PHI.
 149         continue;
 150       }
 151     }
 152
 153     auto Visit = [&](User *U) {
 154       if (auto *FI = dyn_cast<FreezeInst>(U)) {
 155         LLVM_DEBUG(dbgs() << "canonfr: found: " << *FI << "\n");
 156         Info.FI = FI;
 157         Candidates.push_back(Info);
 158       }
 159     };
 160     for_each(PHI.users(), Visit);
 161     for_each(Info.StepInst->users(), Visit);
 162   }
 163
 164   if (Candidates.empty())
 165     return false;
 166
 167   SmallSet<PHINode *, 8> ProcessedPHIs;
 168   for (const auto &Info : Candidates) {
 169     PHINode *PHI = Info.PHI;
 170     if (!ProcessedPHIs.insert(Info.PHI).second)
 171       continue;
 172
 173     BinaryOperator *StepI = Info.StepInst;
 174     assert(StepI && "Step instruction should have been found");
 175
 176     // Drop flags from the step instruction.
 177     if (!isGuaranteedNotToBeUndefOrPoison(StepI, nullptr, StepI, &DT)) {
 178       LLVM_DEBUG(dbgs() << "canonfr: drop flags: " << *StepI << "\n");
 179       StepI->dropPoisonGeneratingFlags();
 180       SE.forgetValue(StepI);
 181     }
 182
 183     InsertFreezeAndForgetFromSCEV(StepI->getOperandUse(Info.StepValIdx));
 184
 185     unsigned OperandIdx =
 186         PHI->getOperandNumForIncomingValue(PHI->getIncomingValue(0) == StepI);
 187     InsertFreezeAndForgetFromSCEV(PHI->getOperandUse(OperandIdx));
 188   }
 189
 190   // Finally, remove the old freeze instructions.
 191   for (const auto &Item : Candidates) {
 192     auto *FI = Item.FI;
 193     LLVM_DEBUG(dbgs() << "canonfr: removing " << *FI << "\n");
 194     SE.forgetValue(FI);
 195     FI->replaceAllUsesWith(FI->getOperand(0));
 196     FI->eraseFromParent();
 197   }
 198
 199   return true;
 200 }
 201
 202 CanonicalizeFreezeInLoops::CanonicalizeFreezeInLoops() : LoopPass(ID) {
 203   initializeCanonicalizeFreezeInLoopsPass(*PassRegistry::getPassRegistry());
 204 }
 205
 206 void CanonicalizeFreezeInLoops::getAnalysisUsage(AnalysisUsage &AU) const {
 207   AU.addPreservedID(LoopSimplifyID);
 208   AU.addRequired<LoopInfoWrapperPass>();
 209   AU.addPreserved<LoopInfoWrapperPass>();
 210   AU.addRequiredID(LoopSimplifyID);
 211   AU.addRequired<ScalarEvolutionWrapperPass>();
 212   AU.addPreserved<ScalarEvolutionWrapperPass>();
 213   AU.addRequired<DominatorTreeWrapperPass>();
 214   AU.addPreserved<DominatorTreeWrapperPass>();
 215 }
 216
 217 bool CanonicalizeFreezeInLoops::runOnLoop(Loop *L, LPPassManager &) {
 218   if (skipLoop(L))
 219     return false;
 220
 221   auto &SE = getAnalysis<ScalarEvolutionWrapperPass>().getSE();
 222   auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
 223   return CanonicalizeFreezeInLoopsImpl(L, SE, DT).run();
 224 }
 225
 226 PreservedAnalyses
 227 CanonicalizeFreezeInLoopsPass::run(Loop &L, LoopAnalysisManager &AM,
 228                                    LoopStandardAnalysisResults &AR,
 229                                    LPMUpdater &U) {
 230   if (!CanonicalizeFreezeInLoopsImpl(&L, AR.SE, AR.DT).run())
 231     return PreservedAnalyses::all();
 232
 233   return getLoopPassPreservedAnalyses();
 234 }
 235
 236 INITIALIZE_PASS_BEGIN(CanonicalizeFreezeInLoops, "canon-freeze",
 237                       "Canonicalize Freeze Instructions in Loops", false, false)
 238 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
 239 INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass)
 240 INITIALIZE_PASS_DEPENDENCY(LoopSimplify)
 241 INITIALIZE_PASS_END(CanonicalizeFreezeInLoops, "canon-freeze",
 242                     "Canonicalize Freeze Instructions in Loops", false, false)
 243
 244 Pass *llvm::createCanonicalizeFreezeInLoopsPass() {
 245   return new CanonicalizeFreezeInLoops();
 246 }
 247
 248 char CanonicalizeFreezeInLoops::ID = 0;