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/DenseMapInfo.h"
  33 #include "llvm/ADT/STLExtras.h"
  34 #include "llvm/ADT/SetVector.h"
  35 #include "llvm/ADT/SmallSet.h"
  36 #include "llvm/Analysis/IVDescriptors.h"
  37 #include "llvm/Analysis/LoopAnalysisManager.h"
  38 #include "llvm/Analysis/LoopInfo.h"
  39 #include "llvm/Analysis/LoopPass.h"
  40 #include "llvm/Analysis/ScalarEvolution.h"
  41 #include "llvm/Analysis/ValueTracking.h"
  42 #include "llvm/IR/Dominators.h"
  43 #include "llvm/InitializePasses.h"
  44 #include "llvm/Pass.h"
  45 #include "llvm/Support/Debug.h"
  46 #include "llvm/Transforms/Utils.h"
  47
  48 using namespace llvm;
  49
  50 #define DEBUG_TYPE "canon-freeze"
  51
  52 namespace {
  53
  54 class CanonicalizeFreezeInLoops : public LoopPass {
  55 public:
  56   static char ID;
  57
  58   CanonicalizeFreezeInLoops();
  59
  60 private:
  61   bool runOnLoop(Loop *L, LPPassManager &LPM) override;
  62   void getAnalysisUsage(AnalysisUsage &AU) const override;
  63 };
  64
  65 class CanonicalizeFreezeInLoopsImpl {
  66   Loop *L;
  67   ScalarEvolution &SE;
  68   DominatorTree &DT;
  69
  70   // Can freeze instruction be pushed into operands of I?
  71   // In order to do this, I should not create a poison after I's flags are
  72   // stripped.
  73   bool canHandleInst(const Instruction *I) {
  74     auto Opc = I->getOpcode();
  75     // If add/sub/mul, drop nsw/nuw flags.
  76     return Opc == Instruction::Add || Opc == Instruction::Sub ||
  77            Opc == Instruction::Mul;
  78   }
  79
  80   void InsertFreezeAndForgetFromSCEV(Use &U);
  81
  82 public:
  83   CanonicalizeFreezeInLoopsImpl(Loop *L, ScalarEvolution &SE, DominatorTree &DT)
  84       : L(L), SE(SE), DT(DT) {}
  85   bool run();
  86 };
  87
  88 } // anonymous namespace
  89
  90 namespace llvm {
  91
  92 struct FrozenIndPHIInfo {
  93   // A freeze instruction that uses an induction phi
  94   FreezeInst *FI = nullptr;
  95   // The induction phi, step instruction, the operand idx of StepInst which is
  96   // a step value
  97   PHINode *PHI;
  98   BinaryOperator *StepInst;
  99   unsigned StepValIdx = 0;
 100
 101   FrozenIndPHIInfo(PHINode *PHI, BinaryOperator *StepInst)
 102       : PHI(PHI), StepInst(StepInst) {}
 103
 104   bool operator==(const FrozenIndPHIInfo &Other) { return FI == Other.FI; }
 105 };
 106
 107 template <> struct DenseMapInfo<FrozenIndPHIInfo> {
 108   static inline FrozenIndPHIInfo getEmptyKey() {
 109     return FrozenIndPHIInfo(DenseMapInfo<PHINode *>::getEmptyKey(),
 110                             DenseMapInfo<BinaryOperator *>::getEmptyKey());
 111   }
 112
 113   static inline FrozenIndPHIInfo getTombstoneKey() {
 114     return FrozenIndPHIInfo(DenseMapInfo<PHINode *>::getTombstoneKey(),
 115                             DenseMapInfo<BinaryOperator *>::getTombstoneKey());
 116   }
 117
 118   static unsigned getHashValue(const FrozenIndPHIInfo &Val) {
 119     return DenseMapInfo<FreezeInst *>::getHashValue(Val.FI);
 120   };
 121
 122   static bool isEqual(const FrozenIndPHIInfo &LHS,
 123                       const FrozenIndPHIInfo &RHS) {
 124     return LHS.FI == RHS.FI;
 125   };
 126 };
 127
 128 } // end namespace llvm
 129
 130 // Given U = (value, user), replace value with freeze(value), and let
 131 // SCEV forget user. The inserted freeze is placed in the preheader.
 132 void CanonicalizeFreezeInLoopsImpl::InsertFreezeAndForgetFromSCEV(Use &U) {
 133   auto *PH = L->getLoopPreheader();
 134
 135   auto *UserI = cast<Instruction>(U.getUser());
 136   auto *ValueToFr = U.get();
 137   assert(L->contains(UserI->getParent()) &&
 138          "Should not process an instruction that isn't inside the loop");
 139   if (isGuaranteedNotToBeUndefOrPoison(ValueToFr, nullptr, UserI, &DT))
 140     return;
 141
 142   LLVM_DEBUG(dbgs() << "canonfr: inserting freeze:\n");
 143   LLVM_DEBUG(dbgs() << "\tUser: " << *U.getUser() << "\n");
 144   LLVM_DEBUG(dbgs() << "\tOperand: " << *U.get() << "\n");
 145
 146   U.set(new FreezeInst(ValueToFr, ValueToFr->getName() + ".frozen",
 147                        PH->getTerminator()));
 148
 149   SE.forgetValue(UserI);
 150 }
 151
 152 bool CanonicalizeFreezeInLoopsImpl::run() {
 153   // The loop should be in LoopSimplify form.
 154   if (!L->isLoopSimplifyForm())
 155     return false;
 156
 157   SmallSetVector<FrozenIndPHIInfo, 4> Candidates;
 158
 159   for (auto &PHI : L->getHeader()->phis()) {
 160     InductionDescriptor ID;
 161     if (!InductionDescriptor::isInductionPHI(&PHI, L, &SE, ID))
 162       continue;
 163
 164     LLVM_DEBUG(dbgs() << "canonfr: PHI: " << PHI << "\n");
 165     FrozenIndPHIInfo Info(&PHI, ID.getInductionBinOp());
 166     if (!Info.StepInst || !canHandleInst(Info.StepInst)) {
 167       // The stepping instruction has unknown form.
 168       // Ignore this PHI.
 169       continue;
 170     }
 171
 172     Info.StepValIdx = Info.StepInst->getOperand(0) == &PHI;
 173     Value *StepV = Info.StepInst->getOperand(Info.StepValIdx);
 174     if (auto *StepI = dyn_cast<Instruction>(StepV)) {
 175       if (L->contains(StepI->getParent())) {
 176         // The step value is inside the loop. Freezing step value will introduce
 177         // another freeze into the loop, so skip this PHI.
 178         continue;
 179       }
 180     }
 181
 182     auto Visit = [&](User *U) {
 183       if (auto *FI = dyn_cast<FreezeInst>(U)) {
 184         LLVM_DEBUG(dbgs() << "canonfr: found: " << *FI << "\n");
 185         Info.FI = FI;
 186         Candidates.insert(Info);
 187       }
 188     };
 189     for_each(PHI.users(), Visit);
 190     for_each(Info.StepInst->users(), Visit);
 191   }
 192
 193   if (Candidates.empty())
 194     return false;
 195
 196   SmallSet<PHINode *, 8> ProcessedPHIs;
 197   for (const auto &Info : Candidates) {
 198     PHINode *PHI = Info.PHI;
 199     if (!ProcessedPHIs.insert(Info.PHI).second)
 200       continue;
 201
 202     BinaryOperator *StepI = Info.StepInst;
 203     assert(StepI && "Step instruction should have been found");
 204
 205     // Drop flags from the step instruction.
 206     if (!isGuaranteedNotToBeUndefOrPoison(StepI, nullptr, StepI, &DT)) {
 207       LLVM_DEBUG(dbgs() << "canonfr: drop flags: " << *StepI << "\n");
 208       StepI->dropPoisonGeneratingFlags();
 209       SE.forgetValue(StepI);
 210     }
 211
 212     InsertFreezeAndForgetFromSCEV(StepI->getOperandUse(Info.StepValIdx));
 213
 214     unsigned OperandIdx =
 215         PHI->getOperandNumForIncomingValue(PHI->getIncomingValue(0) == StepI);
 216     InsertFreezeAndForgetFromSCEV(PHI->getOperandUse(OperandIdx));
 217   }
 218
 219   // Finally, remove the old freeze instructions.
 220   for (const auto &Item : Candidates) {
 221     auto *FI = Item.FI;
 222     LLVM_DEBUG(dbgs() << "canonfr: removing " << *FI << "\n");
 223     SE.forgetValue(FI);
 224     FI->replaceAllUsesWith(FI->getOperand(0));
 225     FI->eraseFromParent();
 226   }
 227
 228   return true;
 229 }
 230
 231 CanonicalizeFreezeInLoops::CanonicalizeFreezeInLoops() : LoopPass(ID) {
 232   initializeCanonicalizeFreezeInLoopsPass(*PassRegistry::getPassRegistry());
 233 }
 234
 235 void CanonicalizeFreezeInLoops::getAnalysisUsage(AnalysisUsage &AU) const {
 236   AU.addPreservedID(LoopSimplifyID);
 237   AU.addRequired<LoopInfoWrapperPass>();
 238   AU.addPreserved<LoopInfoWrapperPass>();
 239   AU.addRequiredID(LoopSimplifyID);
 240   AU.addRequired<ScalarEvolutionWrapperPass>();
 241   AU.addPreserved<ScalarEvolutionWrapperPass>();
 242   AU.addRequired<DominatorTreeWrapperPass>();
 243   AU.addPreserved<DominatorTreeWrapperPass>();
 244 }
 245
 246 bool CanonicalizeFreezeInLoops::runOnLoop(Loop *L, LPPassManager &) {
 247   if (skipLoop(L))
 248     return false;
 249
 250   auto &SE = getAnalysis<ScalarEvolutionWrapperPass>().getSE();
 251   auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
 252   return CanonicalizeFreezeInLoopsImpl(L, SE, DT).run();
 253 }
 254
 255 PreservedAnalyses
 256 CanonicalizeFreezeInLoopsPass::run(Loop &L, LoopAnalysisManager &AM,
 257                                    LoopStandardAnalysisResults &AR,
 258                                    LPMUpdater &U) {
 259   if (!CanonicalizeFreezeInLoopsImpl(&L, AR.SE, AR.DT).run())
 260     return PreservedAnalyses::all();
 261
 262   return getLoopPassPreservedAnalyses();
 263 }
 264
 265 INITIALIZE_PASS_BEGIN(CanonicalizeFreezeInLoops, "canon-freeze",
 266                       "Canonicalize Freeze Instructions in Loops", false, false)
 267 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
 268 INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass)
 269 INITIALIZE_PASS_DEPENDENCY(LoopSimplify)
 270 INITIALIZE_PASS_END(CanonicalizeFreezeInLoops, "canon-freeze",
 271                     "Canonicalize Freeze Instructions in Loops", false, false)
 272
 273 Pass *llvm::createCanonicalizeFreezeInLoopsPass() {
 274   return new CanonicalizeFreezeInLoops();
 275 }
 276
 277 char CanonicalizeFreezeInLoops::ID = 0;