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: UnifyLoopExits.cpp

//===- UnifyLoopExits.cpp - Redirect exiting edges to one block -*- 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
//
//===----------------------------------------------------------------------===//
//
// For each natural loop with multiple exit blocks, this pass creates a new
// block N such that all exiting blocks now branch to N, and then control flow
// is redistributed to all the original exit blocks.
//
// Limitation: This assumes that all terminators in the CFG are direct branches
//             (the "br" instruction). The presence of any other control flow
//             such as indirectbr, switch or callbr will cause an assert.
//
//===----------------------------------------------------------------------===//

#include "llvm/Analysis/LoopInfo.h"
#include "llvm/IR/Dominators.h"
#include "llvm/InitializePasses.h"
#include "llvm/Transforms/Utils.h"
#include "llvm/Transforms/Utils/BasicBlockUtils.h"

#define DEBUG_TYPE "unify-loop-exits"

using namespace llvm;

namespace {
struct UnifyLoopExits : public FunctionPass {
  static char ID;
  UnifyLoopExits() : FunctionPass(ID) {
    initializeUnifyLoopExitsPass(*PassRegistry::getPassRegistry());
  }

void getAnalysisUsage(AnalysisUsage &AU) const override {
    AU.addRequiredID(LowerSwitchID);
    AU.addRequired<LoopInfoWrapperPass>();
    AU.addRequired<DominatorTreeWrapperPass>();
    AU.addPreservedID(LowerSwitchID);
    AU.addPreserved<LoopInfoWrapperPass>();
    AU.addPreserved<DominatorTreeWrapperPass>();
  }

bool runOnFunction(Function &F) override;
};
} // namespace

char UnifyLoopExits::ID = 0;

FunctionPass *llvm::createUnifyLoopExitsPass() { return new UnifyLoopExits(); }

INITIALIZE_PASS_BEGIN(UnifyLoopExits, "unify-loop-exits",
                      "Fixup each natural loop to have a single exit block",
                      false /* Only looks at CFG */, false /* Analysis Pass */)
INITIALIZE_PASS_DEPENDENCY(LowerSwitch)
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
INITIALIZE_PASS_END(UnifyLoopExits, "unify-loop-exits",
                    "Fixup each natural loop to have a single exit block",
                    false /* Only looks at CFG */, false /* Analysis Pass */)

// The current transform introduces new control flow paths which may break the
// SSA requirement that every def must dominate all its uses. For example,
// consider a value D defined inside the loop that is used by some instruction
// U outside the loop. It follows that D dominates U, since the original
// program has valid SSA form. After merging the exits, all paths from D to U
// now flow through the unified exit block. In addition, there may be other
// paths that do not pass through D, but now reach the unified exit
// block. Thus, D no longer dominates U.
//
// Restore the dominance by creating a phi for each such D at the new unified
// loop exit. But when doing this, ignore any uses U that are in the new unified
// loop exit, since those were introduced specially when the block was created.
//
// The use of SSAUpdater seems like overkill for this operation. The location
// for creating the new PHI is well-known, and also the set of incoming blocks
// to the new PHI.
static void restoreSSA(const DominatorTree &DT, const Loop *L,
                       const SetVector<BasicBlock *> &Incoming,
                       BasicBlock *LoopExitBlock) {
  using InstVector = SmallVector<Instruction *, 8>;
  using IIMap = DenseMap<Instruction *, InstVector>;
  IIMap ExternalUsers;
  for (auto BB : L->blocks()) {
    for (auto &I : *BB) {
      for (auto &U : I.uses()) {
        auto UserInst = cast<Instruction>(U.getUser());
        auto UserBlock = UserInst->getParent();
        if (UserBlock == LoopExitBlock)
          continue;
        if (L->contains(UserBlock))
          continue;
        LLVM_DEBUG(dbgs() << "added ext use for " << I.getName() << "("
                          << BB->getName() << ")"
                          << ": " << UserInst->getName() << "("
                          << UserBlock->getName() << ")"
                          << "\n");
        ExternalUsers[&I].push_back(UserInst);
      }
    }
  }

for (auto II : ExternalUsers) {
    // For each Def used outside the loop, create NewPhi in
    // LoopExitBlock. NewPhi receives Def only along exiting blocks that
    // dominate it, while the remaining values are undefined since those paths
    // didn't exist in the original CFG.
    auto Def = II.first;
    LLVM_DEBUG(dbgs() << "externally used: " << Def->getName() << "\n");
    auto NewPhi = PHINode::Create(Def->getType(), Incoming.size(),
                                  Def->getName() + ".moved",
                                  LoopExitBlock->getTerminator());
    for (auto In : Incoming) {
      LLVM_DEBUG(dbgs() << "predecessor " << In->getName() << ": ");
      if (Def->getParent() == In || DT.dominates(Def, In)) {
        LLVM_DEBUG(dbgs() << "dominated\n");
        NewPhi->addIncoming(Def, In);
      } else {
        LLVM_DEBUG(dbgs() << "not dominated\n");
        NewPhi->addIncoming(UndefValue::get(Def->getType()), In);
      }
    }

LLVM_DEBUG(dbgs() << "external users:");
    for (auto U : II.second) {
      LLVM_DEBUG(dbgs() << " " << U->getName());
      U->replaceUsesOfWith(Def, NewPhi);
    }
    LLVM_DEBUG(dbgs() << "\n");
  }
}

static bool unifyLoopExits(DominatorTree &DT, LoopInfo &LI, Loop *L) {
  // To unify the loop exits, we need a list of the exiting blocks as
  // well as exit blocks. The functions for locating these lists both
  // traverse the entire loop body. It is more efficient to first
  // locate the exiting blocks and then examine their successors to
  // locate the exit blocks.
  SetVector<BasicBlock *> ExitingBlocks;
  SetVector<BasicBlock *> Exits;

// We need SetVectors, but the Loop API takes a vector, so we use a temporary.
  SmallVector<BasicBlock *, 8> Temp;
  L->getExitingBlocks(Temp);
  for (auto BB : Temp) {
    ExitingBlocks.insert(BB);
    for (auto S : successors(BB)) {
      auto SL = LI.getLoopFor(S);
      // A successor is not an exit if it is directly or indirectly in the
      // current loop.
      if (SL == L || L->contains(SL))
        continue;
      Exits.insert(S);
    }
  }

LLVM_DEBUG(
      dbgs() << "Found exit blocks:";
      for (auto Exit : Exits) {
        dbgs() << " " << Exit->getName();
      }
      dbgs() << "\n";

dbgs() << "Found exiting blocks:";
      for (auto EB : ExitingBlocks) {
        dbgs() << " " << EB->getName();
      }
      dbgs() << "\n";);

if (Exits.size() <= 1) {
    LLVM_DEBUG(dbgs() << "loop does not have multiple exits; nothing to do\n");
    return false;
  }

SmallVector<BasicBlock *, 8> GuardBlocks;
  DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Eager);
  auto LoopExitBlock = CreateControlFlowHub(&DTU, GuardBlocks, ExitingBlocks,
                                            Exits, "loop.exit");

restoreSSA(DT, L, ExitingBlocks, LoopExitBlock);

#if defined(EXPENSIVE_CHECKS)
  assert(DT.verify(DominatorTree::VerificationLevel::Full));
#else
  assert(DT.verify(DominatorTree::VerificationLevel::Fast));
#endif // EXPENSIVE_CHECKS
  L->verifyLoop();

// The guard blocks were created outside the loop, so they need to become
  // members of the parent loop.
  if (auto ParentLoop = L->getParentLoop()) {
    for (auto G : GuardBlocks) {
      ParentLoop->addBasicBlockToLoop(G, LI);
    }
    ParentLoop->verifyLoop();
  }

#if defined(EXPENSIVE_CHECKS)
  LI.verify(DT);
#endif // EXPENSIVE_CHECKS

return true;
}

bool UnifyLoopExits::runOnFunction(Function &F) {
  LLVM_DEBUG(dbgs() << "===== Unifying loop exits in function " << F.getName()
                    << "\n");
  auto &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
  auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();

bool Changed = false;
  auto Loops = LI.getLoopsInPreorder();
  for (auto L : Loops) {
    LLVM_DEBUG(dbgs() << "Loop: " << L->getHeader()->getName() << " (depth: "
                      << LI.getLoopDepth(L->getHeader()) << ")\n");
    Changed |= unifyLoopExits(DT, LI, L);
  }
  return Changed;
}

003 File Manager

Editing: UnifyLoopExits.cpp

Upload File

Create Folder