GVN.cpp

      MD.removeInstruction(L);
      
      L->replaceAllUsesWith(last);
      toErase.push_back(L);
      deletedLoad = true;
      NumGVNLoad++;
      break;
    } else {
      dep = MD.getDependencyFrom(L, DepInst, DepInst->getParent());
    }
  }

  // If this load really doesn't depend on anything, then we must be loading an
  // undef value.  This can happen when loading for a fresh allocation with no
  // intervening stores, for example.
  if (dep.isNone()) {
    // If this load depends directly on an allocation, there isn't
    // anything stored there; therefore, we can optimize this load
    // to undef.
    MD.removeInstruction(L);
    L->replaceAllUsesWith(UndefValue::get(L->getType()));
    toErase.push_back(L);
    deletedLoad = true;
    NumGVNLoad++;
  }

  if (!deletedLoad)
    last = L;
  
  return deletedLoad;
}

Value* GVN::lookupNumber(BasicBlock* BB, uint32_t num) {
  DenseMap<BasicBlock*, ValueNumberScope*>::iterator I = localAvail.find(BB);
  if (I == localAvail.end())
    return 0;
  
  ValueNumberScope* locals = I->second;
  
  while (locals) {
    DenseMap<uint32_t, Value*>::iterator I = locals->table.find(num);
    if (I != locals->table.end())
      return I->second;
    else
      locals = locals->parent;
  }
  
  return 0;
}

/// processInstruction - When calculating availability, handle an instruction
/// by inserting it into the appropriate sets
bool GVN::processInstruction(Instruction *I,
                             DenseMap<Value*, LoadInst*> &lastSeenLoad,
                             SmallVectorImpl<Instruction*> &toErase) {
  if (LoadInst* L = dyn_cast<LoadInst>(I)) {
    bool changed = processLoad(L, lastSeenLoad, toErase);
    
    if (!changed) {
      unsigned num = VN.lookup_or_add(L);
      localAvail[I->getParent()]->table.insert(std::make_pair(num, L));
    }
    
    return changed;
  }
  
  uint32_t nextNum = VN.getNextUnusedValueNumber();
  unsigned num = VN.lookup_or_add(I);
  
  // Allocations are always uniquely numbered, so we can save time and memory
  // by fast failing them.
  if (isa<AllocationInst>(I) || isa<TerminatorInst>(I)) {
    localAvail[I->getParent()]->table.insert(std::make_pair(num, I));
    return false;
  }
  
  // Collapse PHI nodes
  if (PHINode* p = dyn_cast<PHINode>(I)) {
    Value* constVal = CollapsePhi(p);
    
    if (constVal) {
      for (PhiMapType::iterator PI = phiMap.begin(), PE = phiMap.end();
           PI != PE; ++PI)
        if (PI->second.count(p))
          PI->second.erase(p);
        
      p->replaceAllUsesWith(constVal);
      toErase.push_back(p);
    } else {
      localAvail[I->getParent()]->table.insert(std::make_pair(num, I));
    }
  
  // If the number we were assigned was a brand new VN, then we don't
  // need to do a lookup to see if the number already exists
  // somewhere in the domtree: it can't!
  } else if (num == nextNum) {
    localAvail[I->getParent()]->table.insert(std::make_pair(num, I));
    
  // Perform value-number based elimination
  } else if (Value* repl = lookupNumber(I->getParent(), num)) {
    // Remove it!
    MemoryDependenceAnalysis& MD = getAnalysis<MemoryDependenceAnalysis>();
    MD.removeInstruction(I);
    
    VN.erase(I);
    I->replaceAllUsesWith(repl);
    toErase.push_back(I);
    return true;
  } else {
    localAvail[I->getParent()]->table.insert(std::make_pair(num, I));
  }
  
  return false;
}

// GVN::runOnFunction - This is the main transformation entry point for a
// function.
//
bool GVN::runOnFunction(Function& F) {
  VN.setAliasAnalysis(&getAnalysis<AliasAnalysis>());
  VN.setMemDep(&getAnalysis<MemoryDependenceAnalysis>());
  VN.setDomTree(&getAnalysis<DominatorTree>());
  
  bool changed = false;
  bool shouldContinue = true;
  
  // Merge unconditional branches, allowing PRE to catch more
  // optimization opportunities.
  for (Function::iterator FI = F.begin(), FE = F.end(); FI != FE; ) {
    BasicBlock* BB = FI;
    ++FI;
    bool removedBlock = MergeBlockIntoPredecessor(BB, this);
    if (removedBlock) NumGVNBlocks++;
    
    changed |= removedBlock;
  }
  
  while (shouldContinue) {
    shouldContinue = iterateOnFunction(F);
    changed |= shouldContinue;
  }
  
  if (EnablePRE) {
    bool PREChanged = true;
    while (PREChanged) {
      PREChanged = performPRE(F);
      changed |= PREChanged;
    }
  }

  cleanupGlobalSets();

  return changed;
}


bool GVN::processBlock(DomTreeNode* DTN) {
  BasicBlock* BB = DTN->getBlock();

  SmallVector<Instruction*, 8> toErase;
  DenseMap<Value*, LoadInst*> lastSeenLoad;
  bool changed_function = false;
  
  if (DTN->getIDom())
    localAvail[BB] =
                  new ValueNumberScope(localAvail[DTN->getIDom()->getBlock()]);
  else
    localAvail[BB] = new ValueNumberScope(0);
  
  for (BasicBlock::iterator BI = BB->begin(), BE = BB->end();
       BI != BE;) {
    changed_function |= processInstruction(BI, lastSeenLoad, toErase);
    if (toErase.empty()) {
      ++BI;
      continue;
    }
    
    // If we need some instructions deleted, do it now.
    NumGVNInstr += toErase.size();
    
    // Avoid iterator invalidation.
    bool AtStart = BI == BB->begin();
    if (!AtStart)
      --BI;

    for (SmallVector<Instruction*, 4>::iterator I = toErase.begin(),
         E = toErase.end(); I != E; ++I)
      (*I)->eraseFromParent();

    if (AtStart)
      BI = BB->begin();
    else
      ++BI;
    
    toErase.clear();
  }
  
  return changed_function;
}

/// performPRE - Perform a purely local form of PRE that looks for diamond
/// control flow patterns and attempts to perform simple PRE at the join point.
bool GVN::performPRE(Function& F) {
  bool changed = false;
  SmallVector<std::pair<TerminatorInst*, unsigned>, 4> toSplit;
  for (df_iterator<BasicBlock*> DI = df_begin(&F.getEntryBlock()),
       DE = df_end(&F.getEntryBlock()); DI != DE; ++DI) {
    BasicBlock* CurrentBlock = *DI;
    
    // Nothing to PRE in the entry block.
    if (CurrentBlock == &F.getEntryBlock()) continue;
    
    for (BasicBlock::iterator BI = CurrentBlock->begin(),
         BE = CurrentBlock->end(); BI != BE; ) {
      if (isa<AllocationInst>(BI) || isa<TerminatorInst>(BI) ||
          isa<PHINode>(BI) || BI->mayReadFromMemory() ||
          BI->mayWriteToMemory()) {
        BI++;
        continue;
      }
      
      uint32_t valno = VN.lookup(BI);
      
      // Look for the predecessors for PRE opportunities.  We're
      // only trying to solve the basic diamond case, where
      // a value is computed in the successor and one predecessor,
      // but not the other.  We also explicitly disallow cases
      // where the successor is its own predecessor, because they're
      // more complicated to get right.
      unsigned numWith = 0;
      unsigned numWithout = 0;
      BasicBlock* PREPred = 0;
      DenseMap<BasicBlock*, Value*> predMap;
      for (pred_iterator PI = pred_begin(CurrentBlock),
           PE = pred_end(CurrentBlock); PI != PE; ++PI) {
        // We're not interested in PRE where the block is its
        // own predecessor, on in blocks with predecessors
        // that are not reachable.
        if (*PI == CurrentBlock) {
          numWithout = 2;
          break;
        } else if (!localAvail.count(*PI))  {
          numWithout = 2;
          break;
        }
        
        DenseMap<uint32_t, Value*>::iterator predV = 
                                            localAvail[*PI]->table.find(valno);
        if (predV == localAvail[*PI]->table.end()) {
          PREPred = *PI;
          numWithout++;
        } else if (predV->second == BI) {
          numWithout = 2;
        } else {
          predMap[*PI] = predV->second;
          numWith++;
        }
      }
      
      // Don't do PRE when it might increase code size, i.e. when
      // we would need to insert instructions in more than one pred.
      if (numWithout != 1 || numWith == 0) {
        BI++;
        continue;
      }
      
      // We can't do PRE safely on a critical edge, so instead we schedule
      // the edge to be split and perform the PRE the next time we iterate
      // on the function.
      unsigned succNum = 0;
      for (unsigned i = 0, e = PREPred->getTerminator()->getNumSuccessors();
           i != e; ++i)
        if (PREPred->getTerminator()->getSuccessor(i) == CurrentBlock) {
          succNum = i;
          break;
        }
        
      if (isCriticalEdge(PREPred->getTerminator(), succNum)) {
        toSplit.push_back(std::make_pair(PREPred->getTerminator(), succNum));
        changed = true;
        BI++;
        continue;
      }
      
      // Instantiate the expression the in predecessor that lacked it.
      // Because we are going top-down through the block, all value numbers
      // will be available in the predecessor by the time we need them.  Any
      // that weren't original present will have been instantiated earlier
      // in this loop.
      Instruction* PREInstr = BI->clone();
      bool success = true;
      for (unsigned i = 0; i < BI->getNumOperands(); ++i) {
        Value* op = BI->getOperand(i);
        if (isa<Argument>(op) || isa<Constant>(op) || isa<GlobalValue>(op))
          PREInstr->setOperand(i, op);
        else {
          Value* V = lookupNumber(PREPred, VN.lookup(op));
          if (!V) {
            success = false;
            break;
          } else
            PREInstr->setOperand(i, V);
        }
      }
      
      // Fail out if we encounter an operand that is not available in
      // the PRE predecessor.  This is typically because of loads which 
      // are not value numbered precisely.
      if (!success) {
        delete PREInstr;
        BI++;
        continue;
      }
      
      PREInstr->insertBefore(PREPred->getTerminator());
      PREInstr->setName(BI->getName() + ".pre");
      predMap[PREPred] = PREInstr;
      VN.add(PREInstr, valno);
      NumGVNPRE++;
      
      // Update the availability map to include the new instruction.
      localAvail[PREPred]->table.insert(std::make_pair(valno, PREInstr));
      
      // Create a PHI to make the value available in this block.
      PHINode* Phi = PHINode::Create(BI->getType(),
                                     BI->getName() + ".pre-phi",
                                     CurrentBlock->begin());
      for (pred_iterator PI = pred_begin(CurrentBlock),
           PE = pred_end(CurrentBlock); PI != PE; ++PI)
        Phi->addIncoming(predMap[*PI], *PI);
      
      VN.add(Phi, valno);
      localAvail[CurrentBlock]->table[valno] = Phi;
      
      BI->replaceAllUsesWith(Phi);
      VN.erase(BI);
      
      Instruction* erase = BI;
      BI++;
      erase->eraseFromParent();
      
      changed = true;
    }
  }
  
  for (SmallVector<std::pair<TerminatorInst*, unsigned>, 4>::iterator
       I = toSplit.begin(), E = toSplit.end(); I != E; ++I)
    SplitCriticalEdge(I->first, I->second, this);
  
  return changed || toSplit.size();
}

// iterateOnFunction - Executes one iteration of GVN
bool GVN::iterateOnFunction(Function &F) {
  DominatorTree &DT = getAnalysis<DominatorTree>();

  cleanupGlobalSets();

  // Top-down walk of the dominator tree
  bool changed = false;
  for (df_iterator<DomTreeNode*> DI = df_begin(DT.getRootNode()),
       DE = df_end(DT.getRootNode()); DI != DE; ++DI)
    changed |= processBlock(*DI);
  
  return changed;
}

void GVN::cleanupGlobalSets() {
  VN.clear();
  phiMap.clear();

  for (DenseMap<BasicBlock*, ValueNumberScope*>::iterator
       I = localAvail.begin(), E = localAvail.end(); I != E; ++I)
    delete I->second;
  localAvail.clear();
}