lib/Transforms/Scalar/CodeGenLICM.cpp

   1 //===- CodeGenLICM.cpp - LICM a function for code generation --------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This function performs late LICM, hoisting constants out of loops that
  11 // are not valid immediates. It should not be followed by instcombine,
  12 // because instcombine would quickly stuff the constants back into the loop.
  13 //
  14 //===----------------------------------------------------------------------===//
  15
  16 #define DEBUG_TYPE "codegen-licm"
  17 #include "llvm/Transforms/Scalar.h"
  18 #include "llvm/Constants.h"
  19 #include "llvm/DerivedTypes.h"
  20 #include "llvm/Instructions.h"
  21 #include "llvm/IntrinsicInst.h"
  22 #include "llvm/LLVMContext.h"
  23 #include "llvm/Analysis/LoopPass.h"
  24 #include "llvm/Analysis/AliasAnalysis.h"
  25 #include "llvm/Analysis/ScalarEvolution.h"
  26 #include "llvm/Analysis/IVUsers.h"
  27 #include "llvm/ADT/DenseMap.h"
  28 using namespace llvm;
  29
  30 namespace {
  31   class CodeGenLICM : public LoopPass {
  32     virtual bool runOnLoop(Loop *L, LPPassManager &LPM);
  33     virtual void getAnalysisUsage(AnalysisUsage &AU) const;
  34   public:
  35     static char ID; // Pass identification, replacement for typeid
  36     explicit CodeGenLICM() : LoopPass(&ID) {}
  37   };
  38 }
  39
  40 char CodeGenLICM::ID = 0;
  41 static RegisterPass<CodeGenLICM> X("codegen-licm",
  42                                    "hoist constants out of loops");
  43
  44 Pass *llvm::createCodeGenLICMPass() {
  45   return new CodeGenLICM();
  46 }
  47
  48 bool CodeGenLICM::runOnLoop(Loop *L, LPPassManager &) {
  49   bool Changed = false;
  50
  51   // Only visit outermost loops.
  52   if (L->getParentLoop()) return Changed;
  53
  54   Instruction *PreheaderTerm = L->getLoopPreheader()->getTerminator();
  55   DenseMap<Constant *, BitCastInst *> HoistedConstants;
  56
  57   for (Loop::block_iterator I = L->block_begin(), E = L->block_end();
  58        I != E; ++I) {
  59     BasicBlock *BB = *I;
  60     for (BasicBlock::iterator BBI = BB->begin(), BBE = BB->end();
  61          BBI != BBE; ++BBI) {
  62       Instruction *I = BBI;
  63       // Don't bother hoisting constants out of loop-header phi nodes.
  64       if (BB == L->getHeader() && isa<PHINode>(I))
  65         continue;
  66       // TODO: For now, skip all intrinsic instructions, because some of them
  67       // can require their operands to be constants, and we don't want to
  68       // break that.
  69       if (isa<IntrinsicInst>(I))
  70         continue;
  71       // LLVM represents fneg as -0.0-x; don't hoist the -0.0 out.
  72       if (BinaryOperator::isFNeg(I) ||
  73           BinaryOperator::isNeg(I) ||
  74           BinaryOperator::isNot(I))
  75         continue;
  76       for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) {
  77         // Don't hoist out switch case constants.
  78         if (isa<SwitchInst>(I) && i == 1)
  79           break;
  80         // Don't hoist out shuffle masks.
  81         if (isa<ShuffleVectorInst>(I) && i == 2)
  82           break;
  83         Value *Op = I->getOperand(i);
  84         Constant *C = dyn_cast<Constant>(Op);
  85         if (!C) continue;
  86         // TODO: Ask the target which constants are legal. This would allow
  87         // us to add support for hoisting ConstantInts and GlobalValues too.
  88         if (isa<ConstantFP>(C) ||
  89             isa<ConstantVector>(C) ||
  90             isa<ConstantAggregateZero>(C)) {
  91           BitCastInst *&BC = HoistedConstants[C];
  92           if (!BC)
  93             BC = new BitCastInst(C, C->getType(), "hoist", PreheaderTerm);
  94           I->setOperand(i, BC);
  95           Changed = true;
  96         }
  97       }
  98     }
  99   }
 100
 101   return Changed;
 102 }
 103
 104 void CodeGenLICM::getAnalysisUsage(AnalysisUsage &AU) const {
 105   // This pass preserves just about everything. List some popular things here.
 106   AU.setPreservesCFG();
 107   AU.addPreservedID(LoopSimplifyID);
 108   AU.addPreserved<LoopInfo>();
 109   AU.addPreserved<AliasAnalysis>();
 110   AU.addPreserved<DominanceFrontier>();
 111   AU.addPreserved<DominatorTree>();
 112   AU.addPreserved<ScalarEvolution>();
 113   AU.addPreserved<IVUsers>();
 114
 115   // Hoisting requires a loop preheader.
 116   AU.addRequiredID(LoopSimplifyID);
 117 }