GVN.cpp

      // 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;
      predMap.clear();

      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 == CurInst) {
          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)
        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));
        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 = CurInst->clone(CurInst->getContext());
      bool success = true;
      for (unsigned i = 0, e = CurInst->getNumOperands(); i != e; ++i) {
        Value *Op = PREInstr->getOperand(i);
        if (isa<Argument>(Op) || isa<Constant>(Op) || isa<GlobalValue>(Op))
          continue;

        if (Value *V = lookupNumber(PREPred, VN.lookup(Op))) {
          PREInstr->setOperand(i, V);
        } else {
          success = false;
          break;
        }
      }

      // 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;
        DEBUG(verifyRemoved(PREInstr));
        continue;
      }

      PREInstr->insertBefore(PREPred->getTerminator());
      PREInstr->setName(CurInst->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(CurInst->getType(),
                                     CurInst->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;

      CurInst->replaceAllUsesWith(Phi);
      if (isa<PointerType>(Phi->getType()))
        MD->invalidateCachedPointerInfo(Phi);
      VN.erase(CurInst);

      DEBUG(errs() << "GVN PRE removed: " << *CurInst << '\n');
      MD->removeInstruction(CurInst);
      CurInst->eraseFromParent();
      DEBUG(verifyRemoved(CurInst));
      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) {
  cleanupGlobalSets();

  for (df_iterator<DomTreeNode*> DI = df_begin(DT->getRootNode()),
       DE = df_end(DT->getRootNode()); DI != DE; ++DI) {
    if (DI->getIDom())
      localAvail[DI->getBlock()] =
                   new ValueNumberScope(localAvail[DI->getIDom()->getBlock()]);
    else
      localAvail[DI->getBlock()] = new ValueNumberScope(0);
  }

  // Top-down walk of the dominator tree
  bool Changed = false;
#if 0
  // Needed for value numbering with phi construction to work.
  ReversePostOrderTraversal<Function*> RPOT(&F);
  for (ReversePostOrderTraversal<Function*>::rpo_iterator RI = RPOT.begin(),
       RE = RPOT.end(); RI != RE; ++RI)
    Changed |= processBlock(*RI);
#else
  for (df_iterator<DomTreeNode*> DI = df_begin(DT->getRootNode()),
       DE = df_end(DT->getRootNode()); DI != DE; ++DI)
    Changed |= processBlock(DI->getBlock());
#endif

  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();
}

/// verifyRemoved - Verify that the specified instruction does not occur in our
/// internal data structures.
void GVN::verifyRemoved(const Instruction *Inst) const {
  VN.verifyRemoved(Inst);

  // Walk through the PHI map to make sure the instruction isn't hiding in there
  // somewhere.
  for (PhiMapType::iterator
         I = phiMap.begin(), E = phiMap.end(); I != E; ++I) {
    assert(I->first != Inst && "Inst is still a key in PHI map!");

    for (SmallPtrSet<Instruction*, 4>::iterator
           II = I->second.begin(), IE = I->second.end(); II != IE; ++II) {
      assert(*II != Inst && "Inst is still a value in PHI map!");
    }
  }

  // Walk through the value number scope to make sure the instruction isn't
  // ferreted away in it.
  for (DenseMap<BasicBlock*, ValueNumberScope*>::iterator
         I = localAvail.begin(), E = localAvail.end(); I != E; ++I) {
    const ValueNumberScope *VNS = I->second;

    while (VNS) {
      for (DenseMap<uint32_t, Value*>::iterator
             II = VNS->table.begin(), IE = VNS->table.end(); II != IE; ++II) {
        assert(II->second != Inst && "Inst still in value numbering scope!");
      }

      VNS = VNS->parent;
    }
  }
}