//===----------------------------------------------------------------------===//
#define DEBUG_TYPE "phielim"
+#include "llvm/BasicBlock.h"
+#include "llvm/Instructions.h"
#include "llvm/CodeGen/LiveVariables.h"
#include "llvm/CodeGen/Passes.h"
#include "llvm/CodeGen/MachineFunctionPass.h"
///
void analyzePHINodes(const MachineFunction& Fn);
+ // FindCopyInsertPoint - Find a safe place in MBB to insert a copy from
+ // SrcReg. This needs to be after any def or uses of SrcReg, but before
+ // any subsequent point where control flow might jump out of the basic
+ // block.
+ MachineBasicBlock::iterator FindCopyInsertPoint(MachineBasicBlock &MBB,
+ unsigned SrcReg);
+
+ // SkipPHIsAndLabels - Copies need to be inserted after phi nodes and
+ // also after any exception handling labels: in landing pads execution
+ // starts at the label, so any copies placed before it won't be executed!
+ MachineBasicBlock::iterator SkipPHIsAndLabels(MachineBasicBlock &MBB,
+ MachineBasicBlock::iterator I) {
+ // Rather than assuming that EH labels come before other kinds of labels,
+ // just skip all labels.
+ while (I != MBB.end() &&
+ (I->getOpcode() == TargetInstrInfo::PHI || I->isLabel()))
+ ++I;
+ return I;
+ }
+
typedef std::pair<const MachineBasicBlock*, unsigned> BBVRegPair;
typedef std::map<BBVRegPair, unsigned> VRegPHIUse;
// Get an iterator to the first instruction after the last PHI node (this may
// also be the end of the basic block).
- MachineBasicBlock::iterator AfterPHIsIt = MBB.begin();
- while (AfterPHIsIt != MBB.end() &&
- AfterPHIsIt->getOpcode() == TargetInstrInfo::PHI)
- ++AfterPHIsIt; // Skip over all of the PHI nodes...
+ MachineBasicBlock::iterator AfterPHIsIt = SkipPHIsAndLabels(MBB, MBB.begin());
while (MBB.front().getOpcode() == TargetInstrInfo::PHI)
LowerAtomicPHINode(MBB, AfterPHIsIt);
return true;
}
+// FindCopyInsertPoint - Find a safe place in MBB to insert a copy from SrcReg.
+// This needs to be after any def or uses of SrcReg, but before any subsequent
+// point where control flow might jump out of the basic block.
+MachineBasicBlock::iterator PNE::FindCopyInsertPoint(MachineBasicBlock &MBB,
+ unsigned SrcReg) {
+ // Handle the trivial case trivially.
+ if (MBB.empty())
+ return MBB.begin();
+
+ // If this basic block does not contain an invoke, then control flow always
+ // reaches the end of it, so place the copy there. The logic below works in
+ // this case too, but is more expensive.
+ if (!isa<InvokeInst>(MBB.getBasicBlock()->getTerminator()))
+ return MBB.getFirstTerminator();
+
+ // Discover any definition/uses in this basic block.
+ SmallPtrSet<MachineInstr*, 8> DefUsesInMBB;
+ for (MachineRegisterInfo::reg_iterator RI = MRI->reg_begin(SrcReg),
+ RE = MRI->reg_end(); RI != RE; ++RI) {
+ MachineInstr *DefUseMI = &*RI;
+ if (DefUseMI->getParent() == &MBB)
+ DefUsesInMBB.insert(DefUseMI);
+ }
+
+ MachineBasicBlock::iterator InsertPoint;
+ if (DefUsesInMBB.empty()) {
+ // No def/uses. Insert the copy at the start of the basic block.
+ InsertPoint = MBB.begin();
+ } else if (DefUsesInMBB.size() == 1) {
+ // Insert the copy immediately after the definition/use.
+ InsertPoint = *DefUsesInMBB.begin();
+ ++InsertPoint;
+ } else {
+ // Insert the copy immediately after the last definition/use.
+ InsertPoint = MBB.end();
+ while (!DefUsesInMBB.count(&*--InsertPoint)) {}
+ ++InsertPoint;
+ }
+
+ // Make sure the copy goes after any phi nodes however.
+ return SkipPHIsAndLabels(MBB, InsertPoint);
+}
+
/// LowerAtomicPHINode - Lower the PHI node at the top of the specified block,
/// under the assuption that it needs to be lowered in a way that supports
/// atomic execution of PHIs. This lowering method is always correct all of the
// each for each incoming block), the "def" block and instruction fields
// for the VarInfo is not filled in.
LV->addVirtualRegisterKilled(IncomingReg, PHICopy);
-
- LV->getVarInfo(IncomingReg).UsedBlocks[MBB.getNumber()] = true;
}
// Since we are going to be deleting the PHI node, if it is the last use of
// Find a safe location to insert the copy, this may be the first terminator
// in the block (or end()).
- MachineBasicBlock::iterator InsertPos = opBlock.getFirstTerminator();
+ MachineBasicBlock::iterator InsertPos = FindCopyInsertPoint(opBlock, SrcReg);
// Insert the copy.
TII->copyRegToReg(opBlock, InsertPos, IncomingReg, SrcReg, RC, RC);
// variables information so that it knows the copy source instruction kills
// the incoming value.
LiveVariables::VarInfo &InRegVI = LV->getVarInfo(SrcReg);
- InRegVI.UsedBlocks[opBlock.getNumber()] = true;
// Loop over all of the successors of the basic block, checking to see if
// the value is either live in the block, or if it is killed in the block.
// Is it alive in this successor?
unsigned SuccIdx = SuccMBB->getNumber();
- if (SuccIdx < InRegVI.AliveBlocks.size() &&
- InRegVI.AliveBlocks[SuccIdx]) {
+ if (InRegVI.AliveBlocks.test(SuccIdx)) {
ValueIsLive = true;
break;
}
// This vreg no longer lives all of the way through opBlock.
unsigned opBlockNum = opBlock.getNumber();
- if (opBlockNum < InRegVI.AliveBlocks.size())
- InRegVI.AliveBlocks[opBlockNum] = false;
+ InRegVI.AliveBlocks.reset(opBlockNum);
}
}