File Manager

003 File Manager

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

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

📁 ..
📄 ADCE.cpp(24.71 KB)
📄 AlignmentFromAssumptions.cpp(15.9 KB)
📄 BDCE.cpp(7.42 KB)
📄 CallSiteSplitting.cpp(21.43 KB)
📄 ConstantHoisting.cpp(38.95 KB)
📄 ConstantProp.cpp(4.13 KB)
📄 CorrelatedValuePropagation.cpp(32.36 KB)
📄 DCE.cpp(6.84 KB)
📄 DeadStoreElimination.cpp(91.51 KB)
📄 DivRemPairs.cpp(15.01 KB)
📄 EarlyCSE.cpp(57.05 KB)
📄 FlattenCFGPass.cpp(2.74 KB)
📄 Float2Int.cpp(18.19 KB)
📄 GVN.cpp(100.11 KB)
📄 GVNHoist.cpp(44.85 KB)
📄 GVNSink.cpp(29.97 KB)
📄 GuardWidening.cpp(32.36 KB)
📄 IVUsersPrinter.cpp(839 B)
📄 IndVarSimplify.cpp(113.49 KB)
📄 InductiveRangeCheckElimination.cpp(72.96 KB)
📄 InferAddressSpaces.cpp(44.22 KB)
📄 InstSimplifyPass.cpp(5.39 KB)
📄 JumpThreading.cpp(115.06 KB)
📄 LICM.cpp(92.71 KB)
📄 LoopAccessAnalysisPrinter.cpp(977 B)
📄 LoopDataPrefetch.cpp(14.54 KB)
📄 LoopDeletion.cpp(11.37 KB)
📄 LoopDistribute.cpp(40.25 KB)
📄 LoopFuse.cpp(68.6 KB)
📄 LoopIdiomRecognize.cpp(69.09 KB)
📄 LoopInstSimplify.cpp(9.38 KB)
📄 LoopInterchange.cpp(60.65 KB)
📄 LoopLoadElimination.cpp(26.71 KB)
📄 LoopPassManager.cpp(4.02 KB)
📄 LoopPredication.cpp(49.21 KB)
📄 LoopRerollPass.cpp(58.54 KB)
📄 LoopRotation.cpp(4.79 KB)
📄 LoopSimplifyCFG.cpp(28.59 KB)
📄 LoopSink.cpp(14.93 KB)
📄 LoopStrengthReduce.cpp(216.88 KB)
📄 LoopUnrollAndJamPass.cpp(21.07 KB)
📄 LoopUnrollPass.cpp(60.73 KB)
📄 LoopUnswitch.cpp(64.17 KB)
📄 LoopVersioningLICM.cpp(23.65 KB)
📄 LowerAtomic.cpp(5.12 KB)
📄 LowerConstantIntrinsics.cpp(5.8 KB)
📄 LowerExpectIntrinsic.cpp(15 KB)
📄 LowerGuardIntrinsic.cpp(2.82 KB)
📄 LowerMatrixIntrinsics.cpp(73.36 KB)
📄 LowerWidenableCondition.cpp(2.75 KB)
📄 MakeGuardsExplicit.cpp(3.83 KB)
📄 MemCpyOptimizer.cpp(52.16 KB)
📄 MergeICmps.cpp(35.61 KB)
📄 MergedLoadStoreMotion.cpp(15.18 KB)
📄 NaryReassociate.cpp(19.86 KB)
📄 NewGVN.cpp(170.95 KB)
📄 PartiallyInlineLibCalls.cpp(6.22 KB)
📄 PlaceSafepoints.cpp(27.5 KB)
📄 Reassociate.cpp(95.61 KB)
📄 Reg2Mem.cpp(4.34 KB)
📄 RewriteStatepointsForGC.cpp(116.35 KB)
📄 SCCP.cpp(76.12 KB)
📄 SROA.cpp(183.83 KB)
📄 Scalar.cpp(10.08 KB)
📄 Scalarizer.cpp(32.93 KB)
📄 SeparateConstOffsetFromGEP.cpp(52.99 KB)
📄 SimpleLoopUnswitch.cpp(124.57 KB)
📄 SimplifyCFGPass.cpp(12.31 KB)
📄 Sink.cpp(10.81 KB)
📄 SpeculateAroundPHIs.cpp(35.69 KB)
📄 SpeculativeExecution.cpp(11.54 KB)
📄 StraightLineStrengthReduce.cpp(28.92 KB)
📄 StructurizeCFG.cpp(32.49 KB)
📄 TailRecursionElimination.cpp(34.9 KB)
📄 WarnMissedTransforms.cpp(6.14 KB)

Editing: LoopInstSimplify.cpp

//===- LoopInstSimplify.cpp - Loop Instruction Simplification Pass --------===//
//
// 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 performs lightweight instruction simplification on loop bodies.
//
//===----------------------------------------------------------------------===//

#include "llvm/Transforms/Scalar/LoopInstSimplify.h"
#include "llvm/ADT/PointerIntPair.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Analysis/AssumptionCache.h"
#include "llvm/Analysis/InstructionSimplify.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/LoopIterator.h"
#include "llvm/Analysis/LoopPass.h"
#include "llvm/Analysis/MemorySSA.h"
#include "llvm/Analysis/MemorySSAUpdater.h"
#include "llvm/Analysis/TargetLibraryInfo.h"
#include "llvm/IR/BasicBlock.h"
#include "llvm/IR/CFG.h"
#include "llvm/IR/DataLayout.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/Instruction.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/Module.h"
#include "llvm/IR/PassManager.h"
#include "llvm/IR/User.h"
#include "llvm/InitializePasses.h"
#include "llvm/Pass.h"
#include "llvm/Support/Casting.h"
#include "llvm/Transforms/Scalar.h"
#include "llvm/Transforms/Utils/Local.h"
#include "llvm/Transforms/Utils/LoopUtils.h"
#include <algorithm>
#include <utility>

using namespace llvm;

#define DEBUG_TYPE "loop-instsimplify"

STATISTIC(NumSimplified, "Number of redundant instructions simplified");

static bool simplifyLoopInst(Loop &L, DominatorTree &DT, LoopInfo &LI,
                             AssumptionCache &AC, const TargetLibraryInfo &TLI,
                             MemorySSAUpdater *MSSAU) {
  const DataLayout &DL = L.getHeader()->getModule()->getDataLayout();
  SimplifyQuery SQ(DL, &TLI, &DT, &AC);

// On the first pass over the loop body we try to simplify every instruction.
  // On subsequent passes, we can restrict this to only simplifying instructions
  // where the inputs have been updated. We end up needing two sets: one
  // containing the instructions we are simplifying in *this* pass, and one for
  // the instructions we will want to simplify in the *next* pass. We use
  // pointers so we can swap between two stably allocated sets.
  SmallPtrSet<const Instruction *, 8> S1, S2, *ToSimplify = &S1, *Next = &S2;

// Track the PHI nodes that have already been visited during each iteration so
  // that we can identify when it is necessary to iterate.
  SmallPtrSet<PHINode *, 4> VisitedPHIs;

// While simplifying we may discover dead code or cause code to become dead.
  // Keep track of all such instructions and we will delete them at the end.
  SmallVector<WeakTrackingVH, 8> DeadInsts;

// First we want to create an RPO traversal of the loop body. By processing in
  // RPO we can ensure that definitions are processed prior to uses (for non PHI
  // uses) in all cases. This ensures we maximize the simplifications in each
  // iteration over the loop and minimizes the possible causes for continuing to
  // iterate.
  LoopBlocksRPO RPOT(&L);
  RPOT.perform(&LI);
  MemorySSA *MSSA = MSSAU ? MSSAU->getMemorySSA() : nullptr;

bool Changed = false;
  for (;;) {
    if (MSSAU && VerifyMemorySSA)
      MSSA->verifyMemorySSA();
    for (BasicBlock *BB : RPOT) {
      for (Instruction &I : *BB) {
        if (auto *PI = dyn_cast<PHINode>(&I))
          VisitedPHIs.insert(PI);

if (I.use_empty()) {
          if (isInstructionTriviallyDead(&I, &TLI))
            DeadInsts.push_back(&I);
          continue;
        }

// We special case the first iteration which we can detect due to the
        // empty `ToSimplify` set.
        bool IsFirstIteration = ToSimplify->empty();

if (!IsFirstIteration && !ToSimplify->count(&I))
          continue;

Value *V = SimplifyInstruction(&I, SQ.getWithInstruction(&I));
        if (!V || !LI.replacementPreservesLCSSAForm(&I, V))
          continue;

for (Value::use_iterator UI = I.use_begin(), UE = I.use_end();
             UI != UE;) {
          Use &U = *UI++;
          auto *UserI = cast<Instruction>(U.getUser());
          U.set(V);

// If the instruction is used by a PHI node we have already processed
          // we'll need to iterate on the loop body to converge, so add it to
          // the next set.
          if (auto *UserPI = dyn_cast<PHINode>(UserI))
            if (VisitedPHIs.count(UserPI)) {
              Next->insert(UserPI);
              continue;
            }

// If we are only simplifying targeted instructions and the user is an
          // instruction in the loop body, add it to our set of targeted
          // instructions. Because we process defs before uses (outside of PHIs)
          // we won't have visited it yet.
          //
          // We also skip any uses outside of the loop being simplified. Those
          // should always be PHI nodes due to LCSSA form, and we don't want to
          // try to simplify those away.
          assert((L.contains(UserI) || isa<PHINode>(UserI)) &&
                 "Uses outside the loop should be PHI nodes due to LCSSA!");
          if (!IsFirstIteration && L.contains(UserI))
            ToSimplify->insert(UserI);
        }

if (MSSAU)
          if (Instruction *SimpleI = dyn_cast_or_null<Instruction>(V))
            if (MemoryAccess *MA = MSSA->getMemoryAccess(&I))
              if (MemoryAccess *ReplacementMA = MSSA->getMemoryAccess(SimpleI))
                MA->replaceAllUsesWith(ReplacementMA);

assert(I.use_empty() && "Should always have replaced all uses!");
        if (isInstructionTriviallyDead(&I, &TLI))
          DeadInsts.push_back(&I);
        ++NumSimplified;
        Changed = true;
      }
    }

// Delete any dead instructions found thus far now that we've finished an
    // iteration over all instructions in all the loop blocks.
    if (!DeadInsts.empty()) {
      Changed = true;
      RecursivelyDeleteTriviallyDeadInstructions(DeadInsts, &TLI, MSSAU);
    }

if (MSSAU && VerifyMemorySSA)
      MSSA->verifyMemorySSA();

// If we never found a PHI that needs to be simplified in the next
    // iteration, we're done.
    if (Next->empty())
      break;

// Otherwise, put the next set in place for the next iteration and reset it
    // and the visited PHIs for that iteration.
    std::swap(Next, ToSimplify);
    Next->clear();
    VisitedPHIs.clear();
    DeadInsts.clear();
  }

return Changed;
}

namespace {

class LoopInstSimplifyLegacyPass : public LoopPass {
public:
  static char ID; // Pass ID, replacement for typeid

LoopInstSimplifyLegacyPass() : LoopPass(ID) {
    initializeLoopInstSimplifyLegacyPassPass(*PassRegistry::getPassRegistry());
  }

bool runOnLoop(Loop *L, LPPassManager &LPM) override {
    if (skipLoop(L))
      return false;
    DominatorTree &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
    LoopInfo &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
    AssumptionCache &AC =
        getAnalysis<AssumptionCacheTracker>().getAssumptionCache(
            *L->getHeader()->getParent());
    const TargetLibraryInfo &TLI =
        getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(
            *L->getHeader()->getParent());
    MemorySSA *MSSA = nullptr;
    Optional<MemorySSAUpdater> MSSAU;
    if (EnableMSSALoopDependency) {
      MSSA = &getAnalysis<MemorySSAWrapperPass>().getMSSA();
      MSSAU = MemorySSAUpdater(MSSA);
    }

return simplifyLoopInst(*L, DT, LI, AC, TLI,
                            MSSAU.hasValue() ? MSSAU.getPointer() : nullptr);
  }

void getAnalysisUsage(AnalysisUsage &AU) const override {
    AU.addRequired<AssumptionCacheTracker>();
    AU.addRequired<DominatorTreeWrapperPass>();
    AU.addRequired<TargetLibraryInfoWrapperPass>();
    AU.setPreservesCFG();
    if (EnableMSSALoopDependency) {
      AU.addRequired<MemorySSAWrapperPass>();
      AU.addPreserved<MemorySSAWrapperPass>();
    }
    getLoopAnalysisUsage(AU);
  }
};

} // end anonymous namespace

PreservedAnalyses LoopInstSimplifyPass::run(Loop &L, LoopAnalysisManager &AM,
                                            LoopStandardAnalysisResults &AR,
                                            LPMUpdater &) {
  Optional<MemorySSAUpdater> MSSAU;
  if (AR.MSSA) {
    MSSAU = MemorySSAUpdater(AR.MSSA);
    if (VerifyMemorySSA)
      AR.MSSA->verifyMemorySSA();
  }
  if (!simplifyLoopInst(L, AR.DT, AR.LI, AR.AC, AR.TLI,
                        MSSAU.hasValue() ? MSSAU.getPointer() : nullptr))
    return PreservedAnalyses::all();

auto PA = getLoopPassPreservedAnalyses();
  PA.preserveSet<CFGAnalyses>();
  if (AR.MSSA)
    PA.preserve<MemorySSAAnalysis>();
  return PA;
}

char LoopInstSimplifyLegacyPass::ID = 0;

INITIALIZE_PASS_BEGIN(LoopInstSimplifyLegacyPass, "loop-instsimplify",
                      "Simplify instructions in loops", false, false)
INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
INITIALIZE_PASS_DEPENDENCY(LoopPass)
INITIALIZE_PASS_DEPENDENCY(MemorySSAWrapperPass)
INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
INITIALIZE_PASS_END(LoopInstSimplifyLegacyPass, "loop-instsimplify",
                    "Simplify instructions in loops", false, false)

Pass *llvm::createLoopInstSimplifyPass() {
  return new LoopInstSimplifyLegacyPass();
}

003 File Manager

Editing: LoopInstSimplify.cpp

Upload File

Create Folder