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 STATISTIC(NumDeadCases, "Number of switch cases removed");
     32 
     33 namespace {
     34   class CorrelatedValuePropagation : public FunctionPass {
     35     LazyValueInfo *LVI;
     36 
     37     bool processSelect(SelectInst *SI);
     38     bool processPHI(PHINode *P);
     39     bool processMemAccess(Instruction *I);
     40     bool processCmp(CmpInst *C);
     41     bool processSwitch(SwitchInst *SI);
     42 
     43   public:
     44     static char ID;
     45     CorrelatedValuePropagation(): FunctionPass(ID) {
     46      initializeCorrelatedValuePropagationPass(*PassRegistry::getPassRegistry());
     47     }
     48 
     49     bool runOnFunction(Function &F);
     50 
     51     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
     52       AU.addRequired<LazyValueInfo>();
     53     }
     54   };
     55 }
     56 
     57 char CorrelatedValuePropagation::ID = 0;
     58 INITIALIZE_PASS_BEGIN(CorrelatedValuePropagation, "correlated-propagation",
     59                 "Value Propagation", false, false)
     60 INITIALIZE_PASS_DEPENDENCY(LazyValueInfo)
     61 INITIALIZE_PASS_END(CorrelatedValuePropagation, "correlated-propagation",
     62                 "Value Propagation", false, false)
     63 
     64 // Public interface to the Value Propagation pass
     65 Pass *llvm::createCorrelatedValuePropagationPass() {
     66   return new CorrelatedValuePropagation();
     67 }
     68 
     69 bool CorrelatedValuePropagation::processSelect(SelectInst *S) {
     70   if (S->getType()->isVectorTy()) return false;
     71   if (isa<Constant>(S->getOperand(0))) return false;
     72 
     73   Constant *C = LVI->getConstant(S->getOperand(0), S->getParent());
     74   if (!C) return false;
     75 
     76   ConstantInt *CI = dyn_cast<ConstantInt>(C);
     77   if (!CI) return false;
     78 
     79   Value *ReplaceWith = S->getOperand(1);
     80   Value *Other = S->getOperand(2);
     81   if (!CI->isOne()) std::swap(ReplaceWith, Other);
     82   if (ReplaceWith == S) ReplaceWith = UndefValue::get(S->getType());
     83 
     84   S->replaceAllUsesWith(ReplaceWith);
     85   S->eraseFromParent();
     86 
     87   ++NumSelects;
     88 
     89   return true;
     90 }
     91 
     92 bool CorrelatedValuePropagation::processPHI(PHINode *P) {
     93   bool Changed = false;
     94 
     95   BasicBlock *BB = P->getParent();
     96   for (unsigned i = 0, e = P->getNumIncomingValues(); i < e; ++i) {
     97     Value *Incoming = P->getIncomingValue(i);
     98     if (isa<Constant>(Incoming)) continue;
     99 
    100     Constant *C = LVI->getConstantOnEdge(P->getIncomingValue(i),
    101                                          P->getIncomingBlock(i),
    102                                          BB);
    103     if (!C) continue;
    104 
    105     P->setIncomingValue(i, C);
    106     Changed = true;
    107   }
    108 
    109   if (Value *V = SimplifyInstruction(P)) {
    110     P->replaceAllUsesWith(V);
    111     P->eraseFromParent();
    112     Changed = true;
    113   }
    114 
    115   if (Changed)
    116     ++NumPhis;
    117 
    118   return Changed;
    119 }
    120 
    121 bool CorrelatedValuePropagation::processMemAccess(Instruction *I) {
    122   Value *Pointer = 0;
    123   if (LoadInst *L = dyn_cast<LoadInst>(I))
    124     Pointer = L->getPointerOperand();
    125   else
    126     Pointer = cast<StoreInst>(I)->getPointerOperand();
    127 
    128   if (isa<Constant>(Pointer)) return false;
    129 
    130   Constant *C = LVI->getConstant(Pointer, I->getParent());
    131   if (!C) return false;
    132 
    133   ++NumMemAccess;
    134   I->replaceUsesOfWith(Pointer, C);
    135   return true;
    136 }
    137 
    138 /// processCmp - If the value of this comparison could be determined locally,
    139 /// constant propagation would already have figured it out.  Instead, walk
    140 /// the predecessors and statically evaluate the comparison based on information
    141 /// available on that edge.  If a given static evaluation is true on ALL
    142 /// incoming edges, then it's true universally and we can simplify the compare.
    143 bool CorrelatedValuePropagation::processCmp(CmpInst *C) {
    144   Value *Op0 = C->getOperand(0);
    145   if (isa<Instruction>(Op0) &&
    146       cast<Instruction>(Op0)->getParent() == C->getParent())
    147     return false;
    148 
    149   Constant *Op1 = dyn_cast<Constant>(C->getOperand(1));
    150   if (!Op1) return false;
    151 
    152   pred_iterator PI = pred_begin(C->getParent()), PE = pred_end(C->getParent());
    153   if (PI == PE) return false;
    154 
    155   LazyValueInfo::Tristate Result = LVI->getPredicateOnEdge(C->getPredicate(),
    156                                     C->getOperand(0), Op1, *PI, C->getParent());
    157   if (Result == LazyValueInfo::Unknown) return false;
    158 
    159   ++PI;
    160   while (PI != PE) {
    161     LazyValueInfo::Tristate Res = LVI->getPredicateOnEdge(C->getPredicate(),
    162                                     C->getOperand(0), Op1, *PI, C->getParent());
    163     if (Res != Result) return false;
    164     ++PI;
    165   }
    166 
    167   ++NumCmps;
    168 
    169   if (Result == LazyValueInfo::True)
    170     C->replaceAllUsesWith(ConstantInt::getTrue(C->getContext()));
    171   else
    172     C->replaceAllUsesWith(ConstantInt::getFalse(C->getContext()));
    173 
    174   C->eraseFromParent();
    175 
    176   return true;
    177 }
    178 
    179 /// processSwitch - Simplify a switch instruction by removing cases which can
    180 /// never fire.  If the uselessness of a case could be determined locally then
    181 /// constant propagation would already have figured it out.  Instead, walk the
    182 /// predecessors and statically evaluate cases based on information available
    183 /// on that edge.  Cases that cannot fire no matter what the incoming edge can
    184 /// safely be removed.  If a case fires on every incoming edge then the entire
    185 /// switch can be removed and replaced with a branch to the case destination.
    186 bool CorrelatedValuePropagation::processSwitch(SwitchInst *SI) {
    187   Value *Cond = SI->getCondition();
    188   BasicBlock *BB = SI->getParent();
    189 
    190   // If the condition was defined in same block as the switch then LazyValueInfo
    191   // currently won't say anything useful about it, though in theory it could.
    192   if (isa<Instruction>(Cond) && cast<Instruction>(Cond)->getParent() == BB)
    193     return false;
    194 
    195   // If the switch is unreachable then trying to improve it is a waste of time.
    196   pred_iterator PB = pred_begin(BB), PE = pred_end(BB);
    197   if (PB == PE) return false;
    198 
    199   // Analyse each switch case in turn.  This is done in reverse order so that
    200   // removing a case doesn't cause trouble for the iteration.
    201   bool Changed = false;
    202   for (SwitchInst::CaseIt CI = SI->case_end(), CE = SI->case_begin(); CI-- != CE;
    203        ) {
    204     ConstantInt *Case = CI.getCaseValue();
    205 
    206     // Check to see if the switch condition is equal to/not equal to the case
    207     // value on every incoming edge, equal/not equal being the same each time.
    208     LazyValueInfo::Tristate State = LazyValueInfo::Unknown;
    209     for (pred_iterator PI = PB; PI != PE; ++PI) {
    210       // Is the switch condition equal to the case value?
    211       LazyValueInfo::Tristate Value = LVI->getPredicateOnEdge(CmpInst::ICMP_EQ,
    212                                                               Cond, Case, *PI, BB);
    213       // Give up on this case if nothing is known.
    214       if (Value == LazyValueInfo::Unknown) {
    215         State = LazyValueInfo::Unknown;
    216         break;
    217       }
    218 
    219       // If this was the first edge to be visited, record that all other edges
    220       // need to give the same result.
    221       if (PI == PB) {
    222         State = Value;
    223         continue;
    224       }
    225 
    226       // If this case is known to fire for some edges and known not to fire for
    227       // others then there is nothing we can do - give up.
    228       if (Value != State) {
    229         State = LazyValueInfo::Unknown;
    230         break;
    231       }
    232     }
    233 
    234     if (State == LazyValueInfo::False) {
    235       // This case never fires - remove it.
    236       CI.getCaseSuccessor()->removePredecessor(BB);
    237       SI->removeCase(CI); // Does not invalidate the iterator.
    238       ++NumDeadCases;
    239       Changed = true;
    240     } else if (State == LazyValueInfo::True) {
    241       // This case always fires.  Arrange for the switch to be turned into an
    242       // unconditional branch by replacing the switch condition with the case
    243       // value.
    244       SI->setCondition(Case);
    245       NumDeadCases += SI->getNumCases();
    246       Changed = true;
    247       break;
    248     }
    249   }
    250 
    251   if (Changed)
    252     // If the switch has been simplified to the point where it can be replaced
    253     // by a branch then do so now.
    254     ConstantFoldTerminator(BB);
    255 
    256   return Changed;
    257 }
    258 
    259 bool CorrelatedValuePropagation::runOnFunction(Function &F) {
    260   LVI = &getAnalysis<LazyValueInfo>();
    261 
    262   bool FnChanged = false;
    263 
    264   for (Function::iterator FI = F.begin(), FE = F.end(); FI != FE; ++FI) {
    265     bool BBChanged = false;
    266     for (BasicBlock::iterator BI = FI->begin(), BE = FI->end(); BI != BE; ) {
    267       Instruction *II = BI++;
    268       switch (II->getOpcode()) {
    269       case Instruction::Select:
    270         BBChanged |= processSelect(cast<SelectInst>(II));
    271         break;
    272       case Instruction::PHI:
    273         BBChanged |= processPHI(cast<PHINode>(II));
    274         break;
    275       case Instruction::ICmp:
    276       case Instruction::FCmp:
    277         BBChanged |= processCmp(cast<CmpInst>(II));
    278         break;
    279       case Instruction::Load:
    280       case Instruction::Store:
    281         BBChanged |= processMemAccess(II);
    282         break;
    283       }
    284     }
    285 
    286     Instruction *Term = FI->getTerminator();
    287     switch (Term->getOpcode()) {
    288     case Instruction::Switch:
    289       BBChanged |= processSwitch(cast<SwitchInst>(Term));
    290       break;
    291     }
    292 
    293     FnChanged |= BBChanged;
    294   }
    295 
    296   return FnChanged;
    297 }
    298