Optimizing the generated phi instructions – Basics of IR Code Generation

How can we optimize a phi instruction and why should we do it? Although the SSA form is advantageous for many optimizations, the phi instruction is often not interpreted by the algorithms and thus hinders the optimization in general. Therefore, the fewer phi instructions we generate, the better. Let’s take a closer look:

1. If the instruction has only one operand or all operands have the same value, then we replace the instruction with this value. If the instruction has no operand, then we replace the instruction with the special Undef value. Only if the instruction has two or more distinct operands do we have to keep the instruction:

llvm::Value *
CGProcedure::optimizePhi(llvm::PHINode *Phi) {
llvm::Value *Same = nullptr;
for (llvm::Value *V : Phi->incoming_values()) {
if (V == Same || V == Phi)
continue;
if (Same && V != Same)
return Phi;
Same = V;
}
if (Same == nullptr)
Same = llvm::UndefValue::get(Phi->getType());

2. Removing a phi instruction may lead to optimization opportunities in other phi instructions. Fortunately, LLVM keeps track of the users and the use of values (which is the use-def chain mentioned in the definition of SSA). We must search for all uses of the value in other phi instructions and try to optimize these instructions too: llvm::SmallVector CandidatePhis;
   for (llvm::Use &U : Phi->uses()) {
   if (auto *P =
   llvm::dyn_cast(U.getUser()))
   if (P != Phi)
   CandidatePhis.push_back(P);
   }
   Phi->replaceAllUsesWith(Same);
   Phi->eraseFromParent();
   for (auto *P : CandidatePhis)
   optimizePhi(P);
   return Same;
   }

If we want, we can improve this algorithm even further. Instead of always iterating the list of values for each phi instruction, we can pick and remember two distinct values. Then, in the optimizePhi function, we can check if these two values are still in the list of the phi instruction. If that is the case, then we know that there is nothing to optimize. But even without this optimization, this algorithm runs very fast, so we are not going to implement this now.
We are almost done. The only thing we haven’t done is implement the operation to seal a basic block. We will do this in the next section.
Sealing a block
As soon as we know that all the predecessors of a block are known, we can seal the block. If the source language contains only structured statements such as tinylang, then it is easy to determine where a block can be sealed. Take another look at the basic blocks that are generated for the WHILE statement.
The basic block that contains the condition can be sealed after the branch from the end of the body is added because this was the last missing predecessor. To seal a block, we can simply add the missing operands to the incomplete phi instructions and set the flag:

void CGProcedure::sealBlock(llvm::BasicBlock *BB) {
for (auto PhiDecl : CurrentDef[BB].IncompletePhis) {
addPhiOperands(BB, PhiDecl.second, PhiDecl.first);
}
CurrentDef[BB].IncompletePhis.clear();
CurrentDef[BB].Sealed = true;
}

With these methods, we are now ready to generate the IR code for expressions.