File Manager

003 File Manager

Current Path: /usr/src/contrib/llvm-project/llvm/lib/Transforms/Utils

usr / src / contrib / llvm-project / llvm / lib / Transforms / Utils /

📁 ..
📄 AMDGPUEmitPrintf.cpp(8.57 KB)
📄 ASanStackFrameLayout.cpp(5.75 KB)
📄 AddDiscriminators.cpp(10.78 KB)
📄 AssumeBundleBuilder.cpp(21.46 KB)
📄 BasicBlockUtils.cpp(51.81 KB)
📄 BreakCriticalEdges.cpp(19.03 KB)
📄 BuildLibCalls.cpp(43.9 KB)
📄 BypassSlowDivision.cpp(17.95 KB)
📄 CallGraphUpdater.cpp(5.76 KB)
📄 CallPromotionUtils.cpp(22.18 KB)
📄 CanonicalizeAliases.cpp(3.18 KB)
📄 CanonicalizeFreezeInLoops.cpp(7.93 KB)
📄 CloneFunction.cpp(34.49 KB)
📄 CloneModule.cpp(7.93 KB)
📄 CodeExtractor.cpp(65.69 KB)
📄 CodeMoverUtils.cpp(15.82 KB)
📄 CtorUtils.cpp(5.1 KB)
📄 Debugify.cpp(17.78 KB)
📄 DemoteRegToStack.cpp(6.1 KB)
📄 EntryExitInstrumenter.cpp(5.83 KB)
📄 EscapeEnumerator.cpp(2.96 KB)
📄 Evaluator.cpp(27.98 KB)
📄 FixIrreducible.cpp(12.68 KB)
📄 FlattenCFG.cpp(16.99 KB)
📄 FunctionComparator.cpp(34.36 KB)
📄 FunctionImportUtils.cpp(13.8 KB)
📄 GlobalStatus.cpp(7.23 KB)
📄 GuardUtils.cpp(4.76 KB)
📄 ImportedFunctionsInliningStatistics.cpp(7.67 KB)
📄 InjectTLIMappings.cpp(6.62 KB)
📄 InlineFunction.cpp(103.28 KB)
📄 InstructionNamer.cpp(1.98 KB)
📄 IntegerDivision.cpp(26.17 KB)
📄 LCSSA.cpp(18.72 KB)
📄 LibCallsShrinkWrap.cpp(18.68 KB)
📄 Local.cpp(114.96 KB)
📄 LoopRotationUtils.cpp(29.47 KB)
📄 LoopSimplify.cpp(36.13 KB)
📄 LoopUnroll.cpp(38.07 KB)
📄 LoopUnrollAndJam.cpp(37.71 KB)
📄 LoopUnrollPeel.cpp(31.88 KB)
📄 LoopUnrollRuntime.cpp(40.17 KB)
📄 LoopUtils.cpp(65.03 KB)
📄 LoopVersioning.cpp(12.42 KB)
📄 LowerInvoke.cpp(3.3 KB)
📄 LowerMemIntrinsics.cpp(20.41 KB)
📄 LowerSwitch.cpp(23.46 KB)
📄 Mem2Reg.cpp(3.71 KB)
📄 MetaRenamer.cpp(5.29 KB)
📄 MisExpect.cpp(6.97 KB)
📄 ModuleUtils.cpp(10.99 KB)
📄 NameAnonGlobals.cpp(3.33 KB)
📄 PredicateInfo.cpp(36.79 KB)
📄 PromoteMemoryToRegister.cpp(37.26 KB)
📄 SSAUpdater.cpp(16.72 KB)
📄 SSAUpdaterBulk.cpp(7.46 KB)
📄 SanitizerStats.cpp(4.08 KB)
📄 ScalarEvolutionExpander.cpp(101.25 KB)
📄 SimplifyCFG.cpp(238.13 KB)
📄 SimplifyIndVar.cpp(34.53 KB)
📄 SimplifyLibCalls.cpp(122.25 KB)
📄 SizeOpts.cpp(5.08 KB)
📄 SplitModule.cpp(9.67 KB)
📄 StripGCRelocates.cpp(2.86 KB)
📄 StripNonLineTableDebugInfo.cpp(1.4 KB)
📄 SymbolRewriter.cpp(18.82 KB)
📄 UnifyFunctionExitNodes.cpp(4.42 KB)
📄 UnifyLoopExits.cpp(8.16 KB)
📄 UniqueInternalLinkageNames.cpp(2.91 KB)
📄 Utils.cpp(2.53 KB)
📄 VNCoercion.cpp(25.89 KB)
📄 ValueMapper.cpp(38.06 KB)

Editing: CanonicalizeFreezeInLoops.cpp

//==- 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 by pushing them out to
// the preheader.
//
//   loop:
//     i = phi init, i.next
//     i.next = add nsw i, 1
//     i.next.fr = freeze i.next // push this out of this loop
//     use(i.next.fr)
//     br i1 (i.next <= N), loop, exit
//   =>
//     init.fr = freeze init
//   loop:
//     i = phi init.fr, i.next
//     i.next = add i, 1         // nsw is dropped here
//     use(i.next)
//     br i1 (i.next <= N), loop, exit
//
// Removing freezes from these chains help scalar evolution successfully analyze
// expressions.
//
//===----------------------------------------------------------------------===//

#include "llvm/Transforms/Utils/CanonicalizeFreezeInLoops.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/Analysis/IVDescriptors.h"
#include "llvm/Analysis/IVUsers.h"
#include "llvm/Analysis/LoopAnalysisManager.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/LoopPass.h"
#include "llvm/Analysis/ScalarEvolution.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/IR/Dominators.h"
#include "llvm/InitializePasses.h"
#include "llvm/Pass.h"
#include "llvm/Support/Debug.h"
#include "llvm/Transforms/Utils.h"

using namespace llvm;

#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;
};

class CanonicalizeFreezeInLoopsImpl {
  Loop *L;
  ScalarEvolution &SE;
  DominatorTree &DT;

struct FrozenIndPHIInfo {
    // A freeze instruction that uses an induction phi
    FreezeInst *FI = nullptr;
    // The induction phi, step instruction, the operand idx of StepInst which is
    // a step value
    PHINode *PHI;
    BinaryOperator *StepInst;
    unsigned StepValIdx = 0;

FrozenIndPHIInfo(PHINode *PHI, BinaryOperator *StepInst)
        : PHI(PHI), StepInst(StepInst) {}
  };

// Can freeze instruction be pushed into operands of I?
  // In order to do this, I should not create a poison after I's flags are
  // stripped.
  bool canHandleInst(const Instruction *I) {
    auto Opc = I->getOpcode();
    // If add/sub/mul, drop nsw/nuw flags.
    return Opc == Instruction::Add || Opc == Instruction::Sub ||
           Opc == Instruction::Mul;
  }

void InsertFreezeAndForgetFromSCEV(Use &U);

public:
  CanonicalizeFreezeInLoopsImpl(Loop *L, ScalarEvolution &SE, DominatorTree &DT)
      : L(L), SE(SE), DT(DT) {}
  bool run();
};

} // anonymous namespace

// Given U = (value, user), replace value with freeze(value), and let
// SCEV forget user. The inserted freeze is placed in the preheader.
void CanonicalizeFreezeInLoopsImpl::InsertFreezeAndForgetFromSCEV(Use &U) {
  auto *PH = L->getLoopPreheader();

auto *UserI = cast<Instruction>(U.getUser());
  auto *ValueToFr = U.get();
  assert(L->contains(UserI->getParent()) &&
         "Should not process an instruction that isn't inside the loop");
  if (isGuaranteedNotToBeUndefOrPoison(ValueToFr, UserI, &DT))
    return;

LLVM_DEBUG(dbgs() << "canonfr: inserting freeze:\n");
  LLVM_DEBUG(dbgs() << "\tUser: " << *U.getUser() << "\n");
  LLVM_DEBUG(dbgs() << "\tOperand: " << *U.get() << "\n");

U.set(new FreezeInst(ValueToFr, ValueToFr->getName() + ".frozen",
                       PH->getTerminator()));

SE.forgetValue(UserI);
}

bool CanonicalizeFreezeInLoopsImpl::run() {
  // The loop should be in LoopSimplify form.
  if (!L->isLoopSimplifyForm())
    return false;

SmallVector<FrozenIndPHIInfo, 4> Candidates;

for (auto &PHI : L->getHeader()->phis()) {
    InductionDescriptor ID;
    if (!InductionDescriptor::isInductionPHI(&PHI, L, &SE, ID))
      continue;

LLVM_DEBUG(dbgs() << "canonfr: PHI: " << PHI << "\n");
    FrozenIndPHIInfo Info(&PHI, ID.getInductionBinOp());
    if (!Info.StepInst || !canHandleInst(Info.StepInst)) {
      // The stepping instruction has unknown form.
      // Ignore this PHI.
      continue;
    }

Info.StepValIdx = Info.StepInst->getOperand(0) == &PHI;
    Value *StepV = Info.StepInst->getOperand(Info.StepValIdx);
    if (auto *StepI = dyn_cast<Instruction>(StepV)) {
      if (L->contains(StepI->getParent())) {
        // The step value is inside the loop. Freezing step value will introduce
        // another freeze into the loop, so skip this PHI.
        continue;
      }
    }

auto Visit = [&](User *U) {
      if (auto *FI = dyn_cast<FreezeInst>(U)) {
        LLVM_DEBUG(dbgs() << "canonfr: found: " << *FI << "\n");
        Info.FI = FI;
        Candidates.push_back(Info);
      }
    };
    for_each(PHI.users(), Visit);
    for_each(Info.StepInst->users(), Visit);
  }

if (Candidates.empty())
    return false;

SmallSet<PHINode *, 8> ProcessedPHIs;
  for (const auto &Info : Candidates) {
    PHINode *PHI = Info.PHI;
    if (!ProcessedPHIs.insert(Info.PHI).second)
      continue;

BinaryOperator *StepI = Info.StepInst;
    assert(StepI && "Step instruction should have been found");

// Drop flags from the step instruction.
    if (!isGuaranteedNotToBeUndefOrPoison(StepI, StepI, &DT)) {
      LLVM_DEBUG(dbgs() << "canonfr: drop flags: " << *StepI << "\n");
      StepI->dropPoisonGeneratingFlags();
      SE.forgetValue(StepI);
    }

InsertFreezeAndForgetFromSCEV(StepI->getOperandUse(Info.StepValIdx));

unsigned OperandIdx =
        PHI->getOperandNumForIncomingValue(PHI->getIncomingValue(0) == StepI);
    InsertFreezeAndForgetFromSCEV(PHI->getOperandUse(OperandIdx));
  }

// Finally, remove the old freeze instructions.
  for (const auto &Item : Candidates) {
    auto *FI = Item.FI;
    LLVM_DEBUG(dbgs() << "canonfr: removing " << *FI << "\n");
    SE.forgetValue(FI);
    FI->replaceAllUsesWith(FI->getOperand(0));
    FI->eraseFromParent();
  }

return true;
}

CanonicalizeFreezeInLoops::CanonicalizeFreezeInLoops() : LoopPass(ID) {
  initializeCanonicalizeFreezeInLoopsPass(*PassRegistry::getPassRegistry());
}

void CanonicalizeFreezeInLoops::getAnalysisUsage(AnalysisUsage &AU) const {
  AU.addPreservedID(LoopSimplifyID);
  AU.addRequired<LoopInfoWrapperPass>();
  AU.addPreserved<LoopInfoWrapperPass>();
  AU.addRequiredID(LoopSimplifyID);
  AU.addRequired<ScalarEvolutionWrapperPass>();
  AU.addPreserved<ScalarEvolutionWrapperPass>();
  AU.addRequired<DominatorTreeWrapperPass>();
  AU.addPreserved<DominatorTreeWrapperPass>();
}

bool CanonicalizeFreezeInLoops::runOnLoop(Loop *L, LPPassManager &) {
  if (skipLoop(L))
    return false;

auto &SE = getAnalysis<ScalarEvolutionWrapperPass>().getSE();
  auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
  return CanonicalizeFreezeInLoopsImpl(L, SE, DT).run();
}

PreservedAnalyses
CanonicalizeFreezeInLoopsPass::run(Loop &L, LoopAnalysisManager &AM,
                                   LoopStandardAnalysisResults &AR,
                                   LPMUpdater &U) {
  if (!CanonicalizeFreezeInLoopsImpl(&L, AR.SE, AR.DT).run())
    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(LoopSimplify)
INITIALIZE_PASS_END(CanonicalizeFreezeInLoops, "canon-freeze",
                    "Canonicalize Freeze Instructions in Loops", false, false)

Pass *llvm::createCanonicalizeFreezeInLoopsPass() {
  return new CanonicalizeFreezeInLoops();
}

char CanonicalizeFreezeInLoops::ID = 0;

003 File Manager

Editing: CanonicalizeFreezeInLoops.cpp

Upload File

Create Folder