Home | History | Annotate | Download | only in Scalar 
      1 //===- CorrelatedValuePropagation.cpp - Propagate CFG-derived info --------===//
      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 file implements the Correlated Value Propagation pass.
     11 //
     12 //===----------------------------------------------------------------------===//
     13 
     14 #define DEBUG_TYPE "correlated-value-propagation"
     15 #include "llvm/Transforms/Scalar.h"
     16 #include "llvm/Constants.h"
     17 #include "llvm/Function.h"
     18 #include "llvm/Instructions.h"
     19 #include "llvm/Pass.h"
     20 #include "llvm/Analysis/InstructionSimplify.h"
     21 #include "llvm/Analysis/LazyValueInfo.h"
     22 #include "llvm/Support/CFG.h"
     23 #include "llvm/Transforms/Utils/Local.h"
     24 #include "llvm/ADT/Statistic.h"
     25 using namespace llvm;
     26 
     27 STATISTIC(NumPhis,      "Number of phis propagated");
     28 STATISTIC(NumSelects,   "Number of selects propagated");
     29 STATISTIC(NumMemAccess, "Number of memory access targets propagated");
     30 STATISTIC(NumCmps,      "Number of comparisons propagated");
     31 
     32 namespace {
     33   class CorrelatedValuePropagation : public FunctionPass {
     34     LazyValueInfo *LVI;
     35 
     36     bool processSelect(SelectInst *SI);
     37     bool processPHI(PHINode *P);
     38     bool processMemAccess(Instruction *I);
     39     bool processCmp(CmpInst *C);
     40 
     41   public:
     42     static char ID;
     43     CorrelatedValuePropagation(): FunctionPass(ID) {
     44      initializeCorrelatedValuePropagationPass(*PassRegistry::getPassRegistry());
     45     }
     46 
     47     bool runOnFunction(Function &F);
     48 
     49     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
     50       AU.addRequired<LazyValueInfo>();
     51     }
     52   };
     53 }
     54 
     55 char CorrelatedValuePropagation::ID = 0;
     56 INITIALIZE_PASS_BEGIN(CorrelatedValuePropagation, "correlated-propagation",
     57                 "Value Propagation", false, false)
     58 INITIALIZE_PASS_DEPENDENCY(LazyValueInfo)
     59 INITIALIZE_PASS_END(CorrelatedValuePropagation, "correlated-propagation",
     60                 "Value Propagation", false, false)
     61 
     62 // Public interface to the Value Propagation pass
     63 Pass *llvm::createCorrelatedValuePropagationPass() {
     64   return new CorrelatedValuePropagation();
     65 }
     66 
     67 bool CorrelatedValuePropagation::processSelect(SelectInst *S) {
     68   if (S->getType()->isVectorTy()) return false;
     69   if (isa<Constant>(S->getOperand(0))) return false;
     70 
     71   Constant *C = LVI->getConstant(S->getOperand(0), S->getParent());
     72   if (!C) return false;
     73 
     74   ConstantInt *CI = dyn_cast<ConstantInt>(C);
     75   if (!CI) return false;
     76 
     77   Value *ReplaceWith = S->getOperand(1);
     78   Value *Other = S->getOperand(2);
     79   if (!CI->isOne()) std::swap(ReplaceWith, Other);
     80   if (ReplaceWith == S) ReplaceWith = UndefValue::get(S->getType());
     81 
     82   S->replaceAllUsesWith(ReplaceWith);
     83   S->eraseFromParent();
     84 
     85   ++NumSelects;
     86 
     87   return true;
     88 }
     89 
     90 bool CorrelatedValuePropagation::processPHI(PHINode *P) {
     91   bool Changed = false;
     92 
     93   BasicBlock *BB = P->getParent();
     94   for (unsigned i = 0, e = P->getNumIncomingValues(); i < e; ++i) {
     95     Value *Incoming = P->getIncomingValue(i);
     96     if (isa<Constant>(Incoming)) continue;
     97 
     98     Constant *C = LVI->getConstantOnEdge(P->getIncomingValue(i),
     99                                          P->getIncomingBlock(i),
    100                                          BB);
    101     if (!C) continue;
    102 
    103     P->setIncomingValue(i, C);
    104     Changed = true;
    105   }
    106 
    107   if (Value *V = SimplifyInstruction(P)) {
    108     P->replaceAllUsesWith(V);
    109     P->eraseFromParent();
    110     Changed = true;
    111   }
    112 
    113   ++NumPhis;
    114 
    115   return Changed;
    116 }
    117 
    118 bool CorrelatedValuePropagation::processMemAccess(Instruction *I) {
    119   Value *Pointer = 0;
    120   if (LoadInst *L = dyn_cast<LoadInst>(I))
    121     Pointer = L->getPointerOperand();
    122   else
    123     Pointer = cast<StoreInst>(I)->getPointerOperand();
    124 
    125   if (isa<Constant>(Pointer)) return false;
    126 
    127   Constant *C = LVI->getConstant(Pointer, I->getParent());
    128   if (!C) return false;
    129 
    130   ++NumMemAccess;
    131   I->replaceUsesOfWith(Pointer, C);
    132   return true;
    133 }
    134 
    135 /// processCmp - If the value of this comparison could be determined locally,
    136 /// constant propagation would already have figured it out.  Instead, walk
    137 /// the predecessors and statically evaluate the comparison based on information
    138 /// available on that edge.  If a given static evaluation is true on ALL
    139 /// incoming edges, then it's true universally and we can simplify the compare.
    140 bool CorrelatedValuePropagation::processCmp(CmpInst *C) {
    141   Value *Op0 = C->getOperand(0);
    142   if (isa<Instruction>(Op0) &&
    143       cast<Instruction>(Op0)->getParent() == C->getParent())
    144     return false;
    145 
    146   Constant *Op1 = dyn_cast<Constant>(C->getOperand(1));
    147   if (!Op1) return false;
    148 
    149   pred_iterator PI = pred_begin(C->getParent()), PE = pred_end(C->getParent());
    150   if (PI == PE) return false;
    151 
    152   LazyValueInfo::Tristate Result = LVI->getPredicateOnEdge(C->getPredicate(),
    153                                     C->getOperand(0), Op1, *PI, C->getParent());
    154   if (Result == LazyValueInfo::Unknown) return false;
    155 
    156   ++PI;
    157   while (PI != PE) {
    158     LazyValueInfo::Tristate Res = LVI->getPredicateOnEdge(C->getPredicate(),
    159                                     C->getOperand(0), Op1, *PI, C->getParent());
    160     if (Res != Result) return false;
    161     ++PI;
    162   }
    163 
    164   ++NumCmps;
    165 
    166   if (Result == LazyValueInfo::True)
    167     C->replaceAllUsesWith(ConstantInt::getTrue(C->getContext()));
    168   else
    169     C->replaceAllUsesWith(ConstantInt::getFalse(C->getContext()));
    170 
    171   C->eraseFromParent();
    172 
    173   return true;
    174 }
    175 
    176 bool CorrelatedValuePropagation::runOnFunction(Function &F) {
    177   LVI = &getAnalysis<LazyValueInfo>();
    178 
    179   bool FnChanged = false;
    180 
    181   for (Function::iterator FI = F.begin(), FE = F.end(); FI != FE; ++FI) {
    182     bool BBChanged = false;
    183     for (BasicBlock::iterator BI = FI->begin(), BE = FI->end(); BI != BE; ) {
    184       Instruction *II = BI++;
    185       switch (II->getOpcode()) {
    186       case Instruction::Select:
    187         BBChanged |= processSelect(cast<SelectInst>(II));
    188         break;
    189       case Instruction::PHI:
    190         BBChanged |= processPHI(cast<PHINode>(II));
    191         break;
    192       case Instruction::ICmp:
    193       case Instruction::FCmp:
    194         BBChanged |= processCmp(cast<CmpInst>(II));
    195         break;
    196       case Instruction::Load:
    197       case Instruction::Store:
    198         BBChanged |= processMemAccess(II);
    199         break;
    200       }
    201     }
    202 
    203     FnChanged |= BBChanged;
    204   }
    205 
    206   return FnChanged;
    207 }
    208