File Manager

003 File Manager

Current Path: /usr/src/contrib/llvm-project/llvm/lib/Analysis

usr / src / contrib / llvm-project / llvm / lib / Analysis /

📁 ..
📄 AliasAnalysis.cpp(33.55 KB)
📄 AliasAnalysisEvaluator.cpp(15.64 KB)
📄 AliasAnalysisSummary.cpp(3.49 KB)
📄 AliasAnalysisSummary.h(10.17 KB)
📄 AliasSetTracker.cpp(25.86 KB)
📄 Analysis.cpp(5.29 KB)
📄 AssumeBundleQueries.cpp(7.96 KB)
📄 AssumptionCache.cpp(10.94 KB)
📄 BasicAliasAnalysis.cpp(85.81 KB)
📄 BlockFrequencyInfo.cpp(12.39 KB)
📄 BlockFrequencyInfoImpl.cpp(28.6 KB)
📄 BranchProbabilityInfo.cpp(43.48 KB)
📄 CFG.cpp(9.9 KB)
📄 CFGPrinter.cpp(11.2 KB)
📄 CFLAndersAliasAnalysis.cpp(33.01 KB)
📄 CFLGraph.h(21.23 KB)
📄 CFLSteensAliasAnalysis.cpp(13.24 KB)
📄 CGSCCPassManager.cpp(31.2 KB)
📄 CallGraph.cpp(12.86 KB)
📄 CallGraphSCCPass.cpp(26.31 KB)
📄 CallPrinter.cpp(9.48 KB)
📄 CaptureTracking.cpp(15.38 KB)
📄 CmpInstAnalysis.cpp(4.63 KB)
📄 CodeMetrics.cpp(6.99 KB)
📄 ConstantFolding.cpp(105.15 KB)
📄 CostModel.cpp(3.87 KB)
📄 DDG.cpp(11.29 KB)
📄 Delinearization.cpp(4.49 KB)
📄 DemandedBits.cpp(16.27 KB)
📄 DependenceAnalysis.cpp(150.78 KB)
📄 DependenceGraphBuilder.cpp(19.24 KB)
📄 DivergenceAnalysis.cpp(15.59 KB)
📄 DomPrinter.cpp(9.67 KB)
📄 DomTreeUpdater.cpp(15.21 KB)
📄 DominanceFrontier.cpp(3.2 KB)
📄 EHPersonalities.cpp(5.89 KB)
📄 GlobalsModRef.cpp(41 KB)
📄 GuardUtils.cpp(3.27 KB)
📄 HeatUtils.cpp(2.85 KB)
📄 IVDescriptors.cpp(42.28 KB)
📄 IVUsers.cpp(16.12 KB)
📄 IndirectCallPromotionAnalysis.cpp(4.33 KB)
📄 InlineAdvisor.cpp(15.28 KB)
📄 InlineCost.cpp(99.47 KB)
📄 InlineFeaturesAnalysis.cpp(1.59 KB)
📄 InlineSizeEstimatorAnalysis.cpp(10.95 KB)
📄 InstCount.cpp(2.45 KB)
📄 InstructionPrecedenceTracking.cpp(4.8 KB)
📄 InstructionSimplify.cpp(216.91 KB)
📄 Interval.cpp(1.78 KB)
📄 IntervalPartition.cpp(4.5 KB)
📄 LazyBlockFrequencyInfo.cpp(2.81 KB)
📄 LazyBranchProbabilityInfo.cpp(2.96 KB)
📄 LazyCallGraph.cpp(67.33 KB)
📄 LazyValueInfo.cpp(76.38 KB)
📄 LegacyDivergenceAnalysis.cpp(14.82 KB)
📄 Lint.cpp(29.07 KB)
📄 Loads.cpp(20.6 KB)
📄 LoopAccessAnalysis.cpp(88.02 KB)
📄 LoopAnalysisManager.cpp(6.6 KB)
📄 LoopCacheAnalysis.cpp(23.53 KB)
📄 LoopInfo.cpp(37.15 KB)
📄 LoopNestAnalysis.cpp(10.62 KB)
📄 LoopPass.cpp(12.89 KB)
📄 LoopUnrollAnalyzer.cpp(7.26 KB)
📄 MLInlineAdvisor.cpp(11.36 KB)
📄 MemDepPrinter.cpp(5.13 KB)
📄 MemDerefPrinter.cpp(2.53 KB)
📄 MemoryBuiltins.cpp(41.14 KB)
📄 MemoryDependenceAnalysis.cpp(69.89 KB)
📄 MemoryLocation.cpp(7.92 KB)
📄 MemorySSA.cpp(90.16 KB)
📄 MemorySSAUpdater.cpp(57.9 KB)
📄 ModuleDebugInfoPrinter.cpp(4.02 KB)
📄 ModuleSummaryAnalysis.cpp(38.13 KB)
📄 MustExecute.cpp(31.18 KB)
📄 ObjCARCAliasAnalysis.cpp(5.81 KB)
📄 ObjCARCAnalysisUtils.cpp(1.07 KB)
📄 ObjCARCInstKind.cpp(23.15 KB)
📄 OptimizationRemarkEmitter.cpp(4.23 KB)
📄 PHITransAddr.cpp(16.05 KB)
📄 PhiValues.cpp(8.4 KB)
📄 PostDominators.cpp(3.59 KB)
📄 ProfileSummaryInfo.cpp(18.07 KB)
📄 PtrUseVisitor.cpp(1.28 KB)
📄 RegionInfo.cpp(6.5 KB)
📄 RegionPass.cpp(9.23 KB)
📄 RegionPrinter.cpp(8.61 KB)
📄 ReleaseModeModelRunner.cpp(2.83 KB)
📄 ScalarEvolution.cpp(475.26 KB)
📄 ScalarEvolutionAliasAnalysis.cpp(5.96 KB)
📄 ScalarEvolutionDivision.cpp(7.51 KB)
📄 ScalarEvolutionNormalization.cpp(4.59 KB)
📄 ScopedNoAliasAA.cpp(7.38 KB)
📄 StackLifetime.cpp(12.22 KB)
📄 StackSafetyAnalysis.cpp(31.81 KB)
📄 StratifiedSets.h(18.67 KB)
📄 SyncDependenceAnalysis.cpp(12.97 KB)
📄 SyntheticCountsUtils.cpp(3.81 KB)
📄 TFUtils.cpp(8.99 KB)
📄 TargetLibraryInfo.cpp(58.98 KB)
📄 TargetTransformInfo.cpp(48.15 KB)
📄 Trace.cpp(1.8 KB)
📄 TypeBasedAliasAnalysis.cpp(26.04 KB)
📄 TypeMetadataUtils.cpp(5.93 KB)
📄 VFABIDemangling.cpp(16.46 KB)
📄 ValueLattice.cpp(1.19 KB)
📄 ValueLatticeUtils.cpp(1.53 KB)
📄 ValueTracking.cpp(243.08 KB)
📄 VectorUtils.cpp(48.57 KB)
📁 models

Editing: ScalarEvolutionDivision.cpp

//===- ScalarEvolutionDivision.h - See below --------------------*- 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 file defines the class that knows how to divide SCEV's.
//
//===----------------------------------------------------------------------===//

#include "llvm/Analysis/ScalarEvolutionDivision.h"
#include "llvm/ADT/APInt.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/Analysis/ScalarEvolution.h"
#include "llvm/IR/Constants.h"
#include "llvm/Support/Casting.h"
#include "llvm/Support/ErrorHandling.h"
#include <cassert>
#include <cstdint>

namespace llvm {
class Type;
}

using namespace llvm;

namespace {

static inline int sizeOfSCEV(const SCEV *S) {
  struct FindSCEVSize {
    int Size = 0;

FindSCEVSize() = default;

bool follow(const SCEV *S) {
      ++Size;
      // Keep looking at all operands of S.
      return true;
    }

bool isDone() const { return false; }
  };

FindSCEVSize F;
  SCEVTraversal<FindSCEVSize> ST(F);
  ST.visitAll(S);
  return F.Size;
}

} // namespace

// Computes the Quotient and Remainder of the division of Numerator by
// Denominator.
void SCEVDivision::divide(ScalarEvolution &SE, const SCEV *Numerator,
                          const SCEV *Denominator, const SCEV **Quotient,
                          const SCEV **Remainder) {
  assert(Numerator && Denominator && "Uninitialized SCEV");

SCEVDivision D(SE, Numerator, Denominator);

// Check for the trivial case here to avoid having to check for it in the
  // rest of the code.
  if (Numerator == Denominator) {
    *Quotient = D.One;
    *Remainder = D.Zero;
    return;
  }

if (Numerator->isZero()) {
    *Quotient = D.Zero;
    *Remainder = D.Zero;
    return;
  }

// A simple case when N/1. The quotient is N.
  if (Denominator->isOne()) {
    *Quotient = Numerator;
    *Remainder = D.Zero;
    return;
  }

// Split the Denominator when it is a product.
  if (const SCEVMulExpr *T = dyn_cast<SCEVMulExpr>(Denominator)) {
    const SCEV *Q, *R;
    *Quotient = Numerator;
    for (const SCEV *Op : T->operands()) {
      divide(SE, *Quotient, Op, &Q, &R);
      *Quotient = Q;

// Bail out when the Numerator is not divisible by one of the terms of
      // the Denominator.
      if (!R->isZero()) {
        *Quotient = D.Zero;
        *Remainder = Numerator;
        return;
      }
    }
    *Remainder = D.Zero;
    return;
  }

D.visit(Numerator);
  *Quotient = D.Quotient;
  *Remainder = D.Remainder;
}

void SCEVDivision::visitConstant(const SCEVConstant *Numerator) {
  if (const SCEVConstant *D = dyn_cast<SCEVConstant>(Denominator)) {
    APInt NumeratorVal = Numerator->getAPInt();
    APInt DenominatorVal = D->getAPInt();
    uint32_t NumeratorBW = NumeratorVal.getBitWidth();
    uint32_t DenominatorBW = DenominatorVal.getBitWidth();

if (NumeratorBW > DenominatorBW)
      DenominatorVal = DenominatorVal.sext(NumeratorBW);
    else if (NumeratorBW < DenominatorBW)
      NumeratorVal = NumeratorVal.sext(DenominatorBW);

APInt QuotientVal(NumeratorVal.getBitWidth(), 0);
    APInt RemainderVal(NumeratorVal.getBitWidth(), 0);
    APInt::sdivrem(NumeratorVal, DenominatorVal, QuotientVal, RemainderVal);
    Quotient = SE.getConstant(QuotientVal);
    Remainder = SE.getConstant(RemainderVal);
    return;
  }
}

void SCEVDivision::visitAddRecExpr(const SCEVAddRecExpr *Numerator) {
  const SCEV *StartQ, *StartR, *StepQ, *StepR;
  if (!Numerator->isAffine())
    return cannotDivide(Numerator);
  divide(SE, Numerator->getStart(), Denominator, &StartQ, &StartR);
  divide(SE, Numerator->getStepRecurrence(SE), Denominator, &StepQ, &StepR);
  // Bail out if the types do not match.
  Type *Ty = Denominator->getType();
  if (Ty != StartQ->getType() || Ty != StartR->getType() ||
      Ty != StepQ->getType() || Ty != StepR->getType())
    return cannotDivide(Numerator);
  Quotient = SE.getAddRecExpr(StartQ, StepQ, Numerator->getLoop(),
                              Numerator->getNoWrapFlags());
  Remainder = SE.getAddRecExpr(StartR, StepR, Numerator->getLoop(),
                               Numerator->getNoWrapFlags());
}

void SCEVDivision::visitAddExpr(const SCEVAddExpr *Numerator) {
  SmallVector<const SCEV *, 2> Qs, Rs;
  Type *Ty = Denominator->getType();

for (const SCEV *Op : Numerator->operands()) {
    const SCEV *Q, *R;
    divide(SE, Op, Denominator, &Q, &R);

// Bail out if types do not match.
    if (Ty != Q->getType() || Ty != R->getType())
      return cannotDivide(Numerator);

Qs.push_back(Q);
    Rs.push_back(R);
  }

if (Qs.size() == 1) {
    Quotient = Qs[0];
    Remainder = Rs[0];
    return;
  }

Quotient = SE.getAddExpr(Qs);
  Remainder = SE.getAddExpr(Rs);
}

void SCEVDivision::visitMulExpr(const SCEVMulExpr *Numerator) {
  SmallVector<const SCEV *, 2> Qs;
  Type *Ty = Denominator->getType();

bool FoundDenominatorTerm = false;
  for (const SCEV *Op : Numerator->operands()) {
    // Bail out if types do not match.
    if (Ty != Op->getType())
      return cannotDivide(Numerator);

if (FoundDenominatorTerm) {
      Qs.push_back(Op);
      continue;
    }

// Check whether Denominator divides one of the product operands.
    const SCEV *Q, *R;
    divide(SE, Op, Denominator, &Q, &R);
    if (!R->isZero()) {
      Qs.push_back(Op);
      continue;
    }

// Bail out if types do not match.
    if (Ty != Q->getType())
      return cannotDivide(Numerator);

FoundDenominatorTerm = true;
    Qs.push_back(Q);
  }

if (FoundDenominatorTerm) {
    Remainder = Zero;
    if (Qs.size() == 1)
      Quotient = Qs[0];
    else
      Quotient = SE.getMulExpr(Qs);
    return;
  }

if (!isa<SCEVUnknown>(Denominator))
    return cannotDivide(Numerator);

// The Remainder is obtained by replacing Denominator by 0 in Numerator.
  ValueToValueMap RewriteMap;
  RewriteMap[cast<SCEVUnknown>(Denominator)->getValue()] =
      cast<SCEVConstant>(Zero)->getValue();
  Remainder = SCEVParameterRewriter::rewrite(Numerator, SE, RewriteMap, true);

if (Remainder->isZero()) {
    // The Quotient is obtained by replacing Denominator by 1 in Numerator.
    RewriteMap[cast<SCEVUnknown>(Denominator)->getValue()] =
        cast<SCEVConstant>(One)->getValue();
    Quotient = SCEVParameterRewriter::rewrite(Numerator, SE, RewriteMap, true);
    return;
  }

// Quotient is (Numerator - Remainder) divided by Denominator.
  const SCEV *Q, *R;
  const SCEV *Diff = SE.getMinusSCEV(Numerator, Remainder);
  // This SCEV does not seem to simplify: fail the division here.
  if (sizeOfSCEV(Diff) > sizeOfSCEV(Numerator))
    return cannotDivide(Numerator);
  divide(SE, Diff, Denominator, &Q, &R);
  if (R != Zero)
    return cannotDivide(Numerator);
  Quotient = Q;
}

SCEVDivision::SCEVDivision(ScalarEvolution &S, const SCEV *Numerator,
                           const SCEV *Denominator)
    : SE(S), Denominator(Denominator) {
  Zero = SE.getZero(Denominator->getType());
  One = SE.getOne(Denominator->getType());

// We generally do not know how to divide Expr by Denominator. We initialize
  // the division to a "cannot divide" state to simplify the rest of the code.
  cannotDivide(Numerator);
}

// Convenience function for giving up on the division. We set the quotient to
// be equal to zero and the remainder to be equal to the numerator.
void SCEVDivision::cannotDivide(const SCEV *Numerator) {
  Quotient = Zero;
  Remainder = Numerator;
}

003 File Manager

Editing: ScalarEvolutionDivision.cpp

Upload File

Create Folder