Subversion Repositories QNX 8.QNX8 LLVM/Clang compiler suite

Rev

Blame | Last modification | View Log | Download | RSS feed

  1. //===- llvm/Analysis/LoopUnrollAnalyzer.h - Loop Unroll Analyzer-*- 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 implements UnrolledInstAnalyzer class. It's used for predicting
  10. // potential effects that loop unrolling might have, such as enabling constant
  11. // propagation and other optimizations.
  12. //
  13. //===----------------------------------------------------------------------===//
  14.  
  15. #ifndef LLVM_ANALYSIS_LOOPUNROLLANALYZER_H
  16. #define LLVM_ANALYSIS_LOOPUNROLLANALYZER_H
  17.  
  18. #include "llvm/ADT/APInt.h"
  19. #include "llvm/ADT/DenseMap.h"
  20. #include "llvm/Analysis/ScalarEvolution.h"
  21. #include "llvm/IR/InstVisitor.h"
  22.  
  23. // This class is used to get an estimate of the optimization effects that we
  24. // could get from complete loop unrolling. It comes from the fact that some
  25. // loads might be replaced with concrete constant values and that could trigger
  26. // a chain of instruction simplifications.
  27. //
  28. // E.g. we might have:
  29. //   int a[] = {0, 1, 0};
  30. //   v = 0;
  31. //   for (i = 0; i < 3; i ++)
  32. //     v += b[i]*a[i];
  33. // If we completely unroll the loop, we would get:
  34. //   v = b[0]*a[0] + b[1]*a[1] + b[2]*a[2]
  35. // Which then will be simplified to:
  36. //   v = b[0]* 0 + b[1]* 1 + b[2]* 0
  37. // And finally:
  38. //   v = b[1]
  39. namespace llvm {
  40. class Instruction;
  41.  
  42. class UnrolledInstAnalyzer : private InstVisitor<UnrolledInstAnalyzer, bool> {
  43.   typedef InstVisitor<UnrolledInstAnalyzer, bool> Base;
  44.   friend class InstVisitor<UnrolledInstAnalyzer, bool>;
  45.   struct SimplifiedAddress {
  46.     Value *Base = nullptr;
  47.     ConstantInt *Offset = nullptr;
  48.   };
  49.  
  50. public:
  51.   UnrolledInstAnalyzer(unsigned Iteration,
  52.                        DenseMap<Value *, Value *> &SimplifiedValues,
  53.                        ScalarEvolution &SE, const Loop *L)
  54.       : SimplifiedValues(SimplifiedValues), SE(SE), L(L) {
  55.       IterationNumber = SE.getConstant(APInt(64, Iteration));
  56.   }
  57.  
  58.   // Allow access to the initial visit method.
  59.   using Base::visit;
  60.  
  61. private:
  62.   /// A cache of pointer bases and constant-folded offsets corresponding
  63.   /// to GEP (or derived from GEP) instructions.
  64.   ///
  65.   /// In order to find the base pointer one needs to perform non-trivial
  66.   /// traversal of the corresponding SCEV expression, so it's good to have the
  67.   /// results saved.
  68.   DenseMap<Value *, SimplifiedAddress> SimplifiedAddresses;
  69.  
  70.   /// SCEV expression corresponding to number of currently simulated
  71.   /// iteration.
  72.   const SCEV *IterationNumber;
  73.  
  74.   /// While we walk the loop instructions, we build up and maintain a mapping
  75.   /// of simplified values specific to this iteration.  The idea is to propagate
  76.   /// any special information we have about loads that can be replaced with
  77.   /// constants after complete unrolling, and account for likely simplifications
  78.   /// post-unrolling.
  79.   DenseMap<Value *, Value *> &SimplifiedValues;
  80.  
  81.   ScalarEvolution &SE;
  82.   const Loop *L;
  83.  
  84.   bool simplifyInstWithSCEV(Instruction *I);
  85.  
  86.   bool visitInstruction(Instruction &I);
  87.   bool visitBinaryOperator(BinaryOperator &I);
  88.   bool visitLoad(LoadInst &I);
  89.   bool visitCastInst(CastInst &I);
  90.   bool visitCmpInst(CmpInst &I);
  91.   bool visitPHINode(PHINode &PN);
  92. };
  93. }
  94. #endif
  95.