Nice! On Jan 9, 2008, at 4:47 PM, Owen Anderson wrote:
> Author: resistor > Date: Wed Jan 9 18:47:01 2008 > New Revision: 45799 > > URL: http://llvm.org/viewvc/llvm-project?rev=45799&view=rev > Log: > Add more comments explaining the basics of how the decision of when > to rename and when to insert > copies is made. > > Modified: > llvm/trunk/lib/CodeGen/StrongPHIElimination.cpp > > Modified: llvm/trunk/lib/CodeGen/StrongPHIElimination.cpp > URL: http://llvm.org/viewvc/llvm-project/llvm/trunk/lib/CodeGen/ > StrongPHIElimination.cpp?rev=45799&r1=45798&r2=45799&view=diff > > ====================================================================== > ======== > --- llvm/trunk/lib/CodeGen/StrongPHIElimination.cpp (original) > +++ llvm/trunk/lib/CodeGen/StrongPHIElimination.cpp Wed Jan 9 > 18:47:01 2008 > @@ -390,7 +390,10 @@ > return interference; > } > > -/// processBlock - Eliminate PHIs in the given block > +/// processBlock - Determine how to break up PHIs in the current > block. Each > +/// PHI is broken up by some combination of renaming its operands > and inserting > +/// copies. This method is responsible for determining which > operands receive > +/// which treatment. > void StrongPHIElimination::processBlock(MachineBasicBlock* MBB) { > LiveVariables& LV = getAnalysis<LiveVariables>(); > > @@ -398,21 +401,37 @@ > // before the current one. > std::set<unsigned> ProcessedNames; > > + // Iterate over all the PHI nodes in this block > MachineBasicBlock::iterator P = MBB->begin(); > while (P != MBB->end() && P->getOpcode() == TargetInstrInfo::PHI) { > LiveVariables::VarInfo& PHIInfo = LV.getVarInfo(P->getOperand > (0).getReg()); > > unsigned DestReg = P->getOperand(0).getReg(); > > - // Hold the names that are currently in the candidate set. > + // PHIUnion is the set of incoming registers to the PHI node that > + // are going to be renames rather than having copies > inserted. This set > + // is refinded over the course of this function. > UnionedBlocks is the set > + // of corresponding MBBs. > std::set<unsigned> PHIUnion; > std::set<MachineBasicBlock*> UnionedBlocks; > > + // Iterate over the operands of the PHI node > for (int i = P->getNumOperands() - 1; i >= 2; i-=2) { > unsigned SrcReg = P->getOperand(i-1).getReg(); > LiveVariables::VarInfo& SrcInfo = LV.getVarInfo(SrcReg); > > - // Check for trivial interferences > + // Check for trivial interferences via liveness information, > allowing us > + // to avoid extra work later. Any registers that interfere > cannot both > + // be in the renaming set, so choose one and add copies for > it instead. > + // The conditions are: > + // 1) if the operand is live into the PHI node's block OR > + // 2) if the PHI node is live out of the operand's > defining block OR > + // 3) if the operand is itself a PHI node and the original > PHI is > + // live into the operand's defining block OR > + // 4) if the operand is already being renamed for another > PHI node > + // in this block OR > + // 5) if any two operands are defined in the same block, > insert copies > + // for one of them > if (isLiveIn(SrcInfo, P->getParent()) || > isLiveOut(PHIInfo, SrcInfo.DefInst->getParent()) || > ( PHIInfo.DefInst->getOpcode() == TargetInstrInfo::PHI && > @@ -420,24 +439,32 @@ > ProcessedNames.count(SrcReg) || > UnionedBlocks.count(SrcInfo.DefInst->getParent())) { > > - // add a copy from a_i to p in Waiting[From[a_i]] > + // Add a copy for the selected register > MachineBasicBlock* From = P->getOperand(i).getMBB(); > Waiting[From].insert(std::make_pair(SrcReg, DestReg)); > UsedByAnother.insert(SrcReg); > } else { > + // Otherwise, add it to the renaming set > PHIUnion.insert(SrcReg); > UnionedBlocks.insert(SrcInfo.DefInst->getParent()); > } > } > > + // Compute the dominator forest for the renaming set. This is > a forest > + // where the nodes are the registers and the edges represent > dominance > + // relations between the defining blocks of the registers > std::vector<StrongPHIElimination::DomForestNode*> DF = > > computeDomForest(PHIUnion); > > - // Walk DomForest to resolve interferences > + // Walk DomForest to resolve interferences at an inter-block > level. This > + // will remove registers from the renaming set (and insert > copies for them) > + // if interferences are found. > std::vector<std::pair<unsigned, unsigned> > localInterferences; > processPHIUnion(P, PHIUnion, DF, localInterferences); > > - // Check for local interferences > + // The dominator forest walk may have returned some register > pairs whose > + // interference cannot be determines from dominator analysis. > We now > + // examine these pairs for local interferences. > for (std::vector<std::pair<unsigned, unsigned> >::iterator I = > localInterferences.begin(), E = localInterferences.end(); > I != E; ++I) { > std::pair<unsigned, unsigned> p = *I; > @@ -481,10 +508,13 @@ > } > } > > - // Cache renaming information > + // Add the renaming set for this PHI node to our overal > renaming information > RenameSets.insert(std::make_pair(P->getOperand(0).getReg(), > PHIUnion)); > > + // Remember which registers are already renamed, so that we > don't try to > + // rename them for another PHI node in this block > ProcessedNames.insert(PHIUnion.begin(), PHIUnion.end()); > + > ++P; > } > } > > > _______________________________________________ > llvm-commits mailing list > llvm-commits@cs.uiuc.edu > http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits _______________________________________________ llvm-commits mailing list llvm-commits@cs.uiuc.edu http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits
