llvm/lib/Analysis/ScalarEvolutionDivision.cpp

   1 //===- ScalarEvolutionDivision.h - See below --------------------*- 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 file defines the class that knows how to divide SCEV's.
  10 //
  11 //===----------------------------------------------------------------------===//
  12
  13 #include "llvm/Analysis/ScalarEvolutionDivision.h"
  14 #include "llvm/ADT/APInt.h"
  15 #include "llvm/ADT/DenseMap.h"
  16 #include "llvm/ADT/SmallVector.h"
  17 #include "llvm/Analysis/ScalarEvolution.h"
  18 #include "llvm/Support/Casting.h"
  19 #include <cassert>
  20 #include <cstdint>
  21
  22 namespace llvm {
  23 class Type;
  24 }
  25
  26 using namespace llvm;
  27
  28 namespace {
  29
  30 static inline int sizeOfSCEV(const SCEV *S) {
  31   struct FindSCEVSize {
  32     int Size = 0;
  33
  34     FindSCEVSize() = default;
  35
  36     bool follow(const SCEV *S) {
  37       ++Size;
  38       // Keep looking at all operands of S.
  39       return true;
  40     }
  41
  42     bool isDone() const { return false; }
  43   };
  44
  45   FindSCEVSize F;
  46   SCEVTraversal<FindSCEVSize> ST(F);
  47   ST.visitAll(S);
  48   return F.Size;
  49 }
  50
  51 } // namespace
  52
  53 // Computes the Quotient and Remainder of the division of Numerator by
  54 // Denominator.
  55 void SCEVDivision::divide(ScalarEvolution &SE, const SCEV *Numerator,
  56                           const SCEV *Denominator, const SCEV **Quotient,
  57                           const SCEV **Remainder) {
  58   assert(Numerator && Denominator && "Uninitialized SCEV");
  59
  60   SCEVDivision D(SE, Numerator, Denominator);
  61
  62   // Check for the trivial case here to avoid having to check for it in the
  63   // rest of the code.
  64   if (Numerator == Denominator) {
  65     *Quotient = D.One;
  66     *Remainder = D.Zero;
  67     return;
  68   }
  69
  70   if (Numerator->isZero()) {
  71     *Quotient = D.Zero;
  72     *Remainder = D.Zero;
  73     return;
  74   }
  75
  76   // A simple case when N/1. The quotient is N.
  77   if (Denominator->isOne()) {
  78     *Quotient = Numerator;
  79     *Remainder = D.Zero;
  80     return;
  81   }
  82
  83   // Split the Denominator when it is a product.
  84   if (const SCEVMulExpr *T = dyn_cast<SCEVMulExpr>(Denominator)) {
  85     const SCEV *Q, *R;
  86     *Quotient = Numerator;
  87     for (const SCEV *Op : T->operands()) {
  88       divide(SE, *Quotient, Op, &Q, &R);
  89       *Quotient = Q;
  90
  91       // Bail out when the Numerator is not divisible by one of the terms of
  92       // the Denominator.
  93       if (!R->isZero()) {
  94         *Quotient = D.Zero;
  95         *Remainder = Numerator;
  96         return;
  97       }
  98     }
  99     *Remainder = D.Zero;
 100     return;
 101   }
 102
 103   D.visit(Numerator);
 104   *Quotient = D.Quotient;
 105   *Remainder = D.Remainder;
 106 }
 107
 108 void SCEVDivision::visitConstant(const SCEVConstant *Numerator) {
 109   if (const SCEVConstant *D = dyn_cast<SCEVConstant>(Denominator)) {
 110     APInt NumeratorVal = Numerator->getAPInt();
 111     APInt DenominatorVal = D->getAPInt();
 112     uint32_t NumeratorBW = NumeratorVal.getBitWidth();
 113     uint32_t DenominatorBW = DenominatorVal.getBitWidth();
 114
 115     if (NumeratorBW > DenominatorBW)
 116       DenominatorVal = DenominatorVal.sext(NumeratorBW);
 117     else if (NumeratorBW < DenominatorBW)
 118       NumeratorVal = NumeratorVal.sext(DenominatorBW);
 119
 120     APInt QuotientVal(NumeratorVal.getBitWidth(), 0);
 121     APInt RemainderVal(NumeratorVal.getBitWidth(), 0);
 122     APInt::sdivrem(NumeratorVal, DenominatorVal, QuotientVal, RemainderVal);
 123     Quotient = SE.getConstant(QuotientVal);
 124     Remainder = SE.getConstant(RemainderVal);
 125     return;
 126   }
 127 }
 128
 129 void SCEVDivision::visitVScale(const SCEVVScale *Numerator) {
 130   return cannotDivide(Numerator);
 131 }
 132
 133 void SCEVDivision::visitAddRecExpr(const SCEVAddRecExpr *Numerator) {
 134   const SCEV *StartQ, *StartR, *StepQ, *StepR;
 135   if (!Numerator->isAffine())
 136     return cannotDivide(Numerator);
 137   divide(SE, Numerator->getStart(), Denominator, &StartQ, &StartR);
 138   divide(SE, Numerator->getStepRecurrence(SE), Denominator, &StepQ, &StepR);
 139   // Bail out if the types do not match.
 140   Type *Ty = Denominator->getType();
 141   if (Ty != StartQ->getType() || Ty != StartR->getType() ||
 142       Ty != StepQ->getType() || Ty != StepR->getType())
 143     return cannotDivide(Numerator);
 144   Quotient = SE.getAddRecExpr(StartQ, StepQ, Numerator->getLoop(),
 145                               Numerator->getNoWrapFlags());
 146   Remainder = SE.getAddRecExpr(StartR, StepR, Numerator->getLoop(),
 147                                Numerator->getNoWrapFlags());
 148 }
 149
 150 void SCEVDivision::visitAddExpr(const SCEVAddExpr *Numerator) {
 151   SmallVector<const SCEV *, 2> Qs, Rs;
 152   Type *Ty = Denominator->getType();
 153
 154   for (const SCEV *Op : Numerator->operands()) {
 155     const SCEV *Q, *R;
 156     divide(SE, Op, Denominator, &Q, &R);
 157
 158     // Bail out if types do not match.
 159     if (Ty != Q->getType() || Ty != R->getType())
 160       return cannotDivide(Numerator);
 161
 162     Qs.push_back(Q);
 163     Rs.push_back(R);
 164   }
 165
 166   if (Qs.size() == 1) {
 167     Quotient = Qs[0];
 168     Remainder = Rs[0];
 169     return;
 170   }
 171
 172   Quotient = SE.getAddExpr(Qs);
 173   Remainder = SE.getAddExpr(Rs);
 174 }
 175
 176 void SCEVDivision::visitMulExpr(const SCEVMulExpr *Numerator) {
 177   SmallVector<const SCEV *, 2> Qs;
 178   Type *Ty = Denominator->getType();
 179
 180   bool FoundDenominatorTerm = false;
 181   for (const SCEV *Op : Numerator->operands()) {
 182     // Bail out if types do not match.
 183     if (Ty != Op->getType())
 184       return cannotDivide(Numerator);
 185
 186     if (FoundDenominatorTerm) {
 187       Qs.push_back(Op);
 188       continue;
 189     }
 190
 191     // Check whether Denominator divides one of the product operands.
 192     const SCEV *Q, *R;
 193     divide(SE, Op, Denominator, &Q, &R);
 194     if (!R->isZero()) {
 195       Qs.push_back(Op);
 196       continue;
 197     }
 198
 199     // Bail out if types do not match.
 200     if (Ty != Q->getType())
 201       return cannotDivide(Numerator);
 202
 203     FoundDenominatorTerm = true;
 204     Qs.push_back(Q);
 205   }
 206
 207   if (FoundDenominatorTerm) {
 208     Remainder = Zero;
 209     if (Qs.size() == 1)
 210       Quotient = Qs[0];
 211     else
 212       Quotient = SE.getMulExpr(Qs);
 213     return;
 214   }
 215
 216   if (!isa<SCEVUnknown>(Denominator))
 217     return cannotDivide(Numerator);
 218
 219   // The Remainder is obtained by replacing Denominator by 0 in Numerator.
 220   ValueToSCEVMapTy RewriteMap;
 221   RewriteMap[cast<SCEVUnknown>(Denominator)->getValue()] = Zero;
 222   Remainder = SCEVParameterRewriter::rewrite(Numerator, SE, RewriteMap);
 223
 224   if (Remainder->isZero()) {
 225     // The Quotient is obtained by replacing Denominator by 1 in Numerator.
 226     RewriteMap[cast<SCEVUnknown>(Denominator)->getValue()] = One;
 227     Quotient = SCEVParameterRewriter::rewrite(Numerator, SE, RewriteMap);
 228     return;
 229   }
 230
 231   // Quotient is (Numerator - Remainder) divided by Denominator.
 232   const SCEV *Q, *R;
 233   const SCEV *Diff = SE.getMinusSCEV(Numerator, Remainder);
 234   // This SCEV does not seem to simplify: fail the division here.
 235   if (sizeOfSCEV(Diff) > sizeOfSCEV(Numerator))
 236     return cannotDivide(Numerator);
 237   divide(SE, Diff, Denominator, &Q, &R);
 238   if (R != Zero)
 239     return cannotDivide(Numerator);
 240   Quotient = Q;
 241 }
 242
 243 SCEVDivision::SCEVDivision(ScalarEvolution &S, const SCEV *Numerator,
 244                            const SCEV *Denominator)
 245     : SE(S), Denominator(Denominator) {
 246   Zero = SE.getZero(Denominator->getType());
 247   One = SE.getOne(Denominator->getType());
 248
 249   // We generally do not know how to divide Expr by Denominator. We initialize
 250   // the division to a "cannot divide" state to simplify the rest of the code.
 251   cannotDivide(Numerator);
 252 }
 253
 254 // Convenience function for giving up on the division. We set the quotient to
 255 // be equal to zero and the remainder to be equal to the numerator.
 256 void SCEVDivision::cannotDivide(const SCEV *Numerator) {
 257   Quotient = Zero;
 258   Remainder = Numerator;
 259 }