Geeze. I asked for comments and was ignored. Tanya asks for it and she gets it right away. :-)
Evan On Jan 9, 2008, at 5:15 PM, Tanya Lattner wrote: > 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 _______________________________________________ llvm-commits mailing list llvm-commits@cs.uiuc.edu http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits
