+/// 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) == PREPred) {
+ 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;
+}
+