llvm/Analysis/LoopUnrollAnalyzer.h

0001 //===- llvm/Analysis/LoopUnrollAnalyzer.h - Loop Unroll Analyzer-*- C++ -*-===//
0002 //
0003 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
0004 // See https://llvm.org/LICENSE.txt for license information.
0005 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
0006 //
0007 //===----------------------------------------------------------------------===//
0008 //
0009 // This file implements UnrolledInstAnalyzer class. It's used for predicting
0010 // potential effects that loop unrolling might have, such as enabling constant
0011 // propagation and other optimizations.
0012 //
0013 //===----------------------------------------------------------------------===//
0014
0015 #ifndef LLVM_ANALYSIS_LOOPUNROLLANALYZER_H
0016 #define LLVM_ANALYSIS_LOOPUNROLLANALYZER_H
0017
0018 #include "llvm/ADT/APInt.h"
0019 #include "llvm/ADT/DenseMap.h"
0020 #include "llvm/Analysis/ScalarEvolution.h"
0021 #include "llvm/IR/InstVisitor.h"
0022
0023 // This class is used to get an estimate of the optimization effects that we
0024 // could get from complete loop unrolling. It comes from the fact that some
0025 // loads might be replaced with concrete constant values and that could trigger
0026 // a chain of instruction simplifications.
0027 //
0028 // E.g. we might have:
0029 //   int a[] = {0, 1, 0};
0030 //   v = 0;
0031 //   for (i = 0; i < 3; i ++)
0032 //     v += b[i]*a[i];
0033 // If we completely unroll the loop, we would get:
0034 //   v = b[0]*a[0] + b[1]*a[1] + b[2]*a[2]
0035 // Which then will be simplified to:
0036 //   v = b[0]* 0 + b[1]* 1 + b[2]* 0
0037 // And finally:
0038 //   v = b[1]
0039 namespace llvm {
0040 class Instruction;
0041
0042 class UnrolledInstAnalyzer : private InstVisitor<UnrolledInstAnalyzer, bool> {
0043   typedef InstVisitor<UnrolledInstAnalyzer, bool> Base;
0044   friend class InstVisitor<UnrolledInstAnalyzer, bool>;
0045   struct SimplifiedAddress {
0046     Value *Base = nullptr;
0047     APInt Offset;
0048   };
0049
0050 public:
0051   UnrolledInstAnalyzer(unsigned Iteration,
0052                        DenseMap<Value *, Value *> &SimplifiedValues,
0053                        ScalarEvolution &SE, const Loop *L)
0054       : SimplifiedValues(SimplifiedValues), SE(SE), L(L) {
0055       IterationNumber = SE.getConstant(APInt(64, Iteration));
0056   }
0057
0058   // Allow access to the initial visit method.
0059   using Base::visit;
0060
0061 private:
0062   /// A cache of pointer bases and constant-folded offsets corresponding
0063   /// to GEP (or derived from GEP) instructions.
0064   ///
0065   /// In order to find the base pointer one needs to perform non-trivial
0066   /// traversal of the corresponding SCEV expression, so it's good to have the
0067   /// results saved.
0068   DenseMap<Value *, SimplifiedAddress> SimplifiedAddresses;
0069
0070   /// SCEV expression corresponding to number of currently simulated
0071   /// iteration.
0072   const SCEV *IterationNumber;
0073
0074   /// While we walk the loop instructions, we build up and maintain a mapping
0075   /// of simplified values specific to this iteration.  The idea is to propagate
0076   /// any special information we have about loads that can be replaced with
0077   /// constants after complete unrolling, and account for likely simplifications
0078   /// post-unrolling.
0079   DenseMap<Value *, Value *> &SimplifiedValues;
0080
0081   ScalarEvolution &SE;
0082   const Loop *L;
0083
0084   bool simplifyInstWithSCEV(Instruction *I);
0085
0086   bool visitInstruction(Instruction &I);
0087   bool visitBinaryOperator(BinaryOperator &I);
0088   bool visitLoad(LoadInst &I);
0089   bool visitCastInst(CastInst &I);
0090   bool visitCmpInst(CmpInst &I);
0091   bool visitPHINode(PHINode &PN);
0092 };
0093 }
0094 #endif