Index: include/llvm/CodeGen/TailDuplicator.h =================================================================== --- /dev/null +++ include/llvm/CodeGen/TailDuplicator.h @@ -0,0 +1,96 @@ +//===-- llvm/CodeGen/MachineRegisterInfo.h ----------------------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file defines the TailDuplicator class. Used by the +// TailDuplication pass, and MachineBlockPlacement. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CODEGEN_TAILDUPLICATOR_H +#define LLVM_CODEGEN_TAILDUPLICATOR_H + +#include "llvm/CodeGen/RegisterScavenging.h" +#include "llvm/CodeGen/MachineSSAUpdater.h" +#include "llvm/CodeGen/MachineBranchProbabilityInfo.h" +#include "llvm/CodeGen/MachineModuleInfo.h" +#include "llvm/CodeGen/MachineRegisterInfo.h" +#include "llvm/Target/TargetInstrInfo.h" +#include "llvm/Target/TargetRegisterInfo.h" +#include "llvm/Target/TargetSubtargetInfo.h" + +namespace llvm { + +/// Utility class to perform tail duplication. +class TailDuplicator { + const TargetInstrInfo *TII; + const TargetRegisterInfo *TRI; + const MachineBranchProbabilityInfo *MBPI; + const MachineModuleInfo *MMI; + MachineRegisterInfo *MRI; + std::unique_ptr RS; + bool PreRegAlloc; + + // A list of virtual registers for which to update SSA form. + SmallVector SSAUpdateVRs; + + // For each virtual register in SSAUpdateVals keep a list of source virtual + // registers. + typedef std::vector > AvailableValsTy; + + DenseMap SSAUpdateVals; + + +public: + void initMF(MachineFunction &MF, + const MachineModuleInfo* MMI, + const MachineBranchProbabilityInfo *MBPI); + bool tailDuplicateBlocks(MachineFunction &MF); + static bool isSimpleBB(MachineBasicBlock *TailBB); + bool shouldTailDuplicate(const MachineFunction &MF, + bool IsSimple, + MachineBasicBlock &TailBB); + bool tailDuplicateAndUpdate(MachineFunction &MF, + bool IsSimple, + MachineBasicBlock *MBB); + +private: + void addSSAUpdateEntry(unsigned OrigReg, unsigned NewReg, + MachineBasicBlock *BB); + void processPHI(MachineInstr *MI, MachineBasicBlock *TailBB, + MachineBasicBlock *PredBB, + DenseMap &LocalVRMap, + SmallVectorImpl > &Copies, + const DenseSet &UsedByPhi, + bool Remove); + void duplicateInstruction(MachineInstr *MI, + MachineBasicBlock *TailBB, + MachineBasicBlock *PredBB, + MachineFunction &MF, + DenseMap &LocalVRMap, + const DenseSet &UsedByPhi); + void updateSuccessorsPHIs(MachineBasicBlock *FromBB, bool isDead, + SmallVectorImpl &TDBBs, + SmallSetVector &Succs); + bool canCompletelyDuplicateBB(MachineBasicBlock &BB); + bool duplicateSimpleBB(MachineBasicBlock *TailBB, + SmallVectorImpl &TDBBs, + const DenseSet &RegsUsedByPhi, + SmallVectorImpl &Copies); + bool tailDuplicate(MachineFunction &MF, + bool IsSimple, + MachineBasicBlock *TailBB, + SmallVectorImpl &TDBBs, + SmallVectorImpl &Copies); + + void removeDeadBlock(MachineBasicBlock *MBB); +}; + +} // End llvm namespace + +#endif Index: lib/CodeGen/TailDuplication.cpp =================================================================== --- lib/CodeGen/TailDuplication.cpp +++ lib/CodeGen/TailDuplication.cpp @@ -17,21 +17,16 @@ #include "llvm/ADT/SetVector.h" #include "llvm/ADT/SmallSet.h" #include "llvm/ADT/Statistic.h" -#include "llvm/CodeGen/MachineBranchProbabilityInfo.h" #include "llvm/CodeGen/MachineFunctionPass.h" #include "llvm/CodeGen/MachineInstrBuilder.h" +#include "llvm/CodeGen/MachineBranchProbabilityInfo.h" #include "llvm/CodeGen/MachineModuleInfo.h" -#include "llvm/CodeGen/MachineRegisterInfo.h" -#include "llvm/CodeGen/MachineSSAUpdater.h" -#include "llvm/CodeGen/RegisterScavenging.h" +#include "llvm/CodeGen/TailDuplicator.h" #include "llvm/IR/Function.h" #include "llvm/Support/CommandLine.h" #include "llvm/Support/Debug.h" #include "llvm/Support/ErrorHandling.h" #include "llvm/Support/raw_ostream.h" -#include "llvm/Target/TargetInstrInfo.h" -#include "llvm/Target/TargetRegisterInfo.h" -#include "llvm/Target/TargetSubtargetInfo.h" using namespace llvm; #define DEBUG_TYPE "tailduplication" @@ -56,72 +51,20 @@ static cl::opt TailDupLimit("tail-dup-limit", cl::init(~0U), cl::Hidden); -typedef std::vector > AvailableValsTy; - namespace { - /// Perform tail duplication. + /// Perform tail duplication. Delegates to TailDuplicator class TailDuplicatePass : public MachineFunctionPass { - const TargetInstrInfo *TII; - const TargetRegisterInfo *TRI; - const MachineBranchProbabilityInfo *MBPI; - MachineModuleInfo *MMI; - MachineRegisterInfo *MRI; - std::unique_ptr RS; - bool PreRegAlloc; - - // A list of virtual registers for which to update SSA form. - SmallVector SSAUpdateVRs; - - // For each virtual register in SSAUpdateVals keep a list of source virtual - // registers. - DenseMap SSAUpdateVals; + TailDuplicator Duplicator; public: static char ID; explicit TailDuplicatePass() : - MachineFunctionPass(ID), PreRegAlloc(false) {} + MachineFunctionPass(ID) {} bool runOnMachineFunction(MachineFunction &MF) override; void getAnalysisUsage(AnalysisUsage &AU) const override; - private: - void AddSSAUpdateEntry(unsigned OrigReg, unsigned NewReg, - MachineBasicBlock *BB); - void ProcessPHI(MachineInstr *MI, MachineBasicBlock *TailBB, - MachineBasicBlock *PredBB, - DenseMap &LocalVRMap, - SmallVectorImpl > &Copies, - const DenseSet &UsedByPhi, - bool Remove); - void DuplicateInstruction(MachineInstr *MI, - MachineBasicBlock *TailBB, - MachineBasicBlock *PredBB, - MachineFunction &MF, - DenseMap &LocalVRMap, - const DenseSet &UsedByPhi); - void UpdateSuccessorsPHIs(MachineBasicBlock *FromBB, bool isDead, - SmallVectorImpl &TDBBs, - SmallSetVector &Succs); - bool TailDuplicateBlocks(MachineFunction &MF); - bool shouldTailDuplicate(const MachineFunction &MF, - bool IsSimple, MachineBasicBlock &TailBB); - bool isSimpleBB(MachineBasicBlock *TailBB); - bool canCompletelyDuplicateBB(MachineBasicBlock &BB); - bool duplicateSimpleBB(MachineBasicBlock *TailBB, - SmallVectorImpl &TDBBs, - const DenseSet &RegsUsedByPhi, - SmallVectorImpl &Copies); - bool TailDuplicate(MachineBasicBlock *TailBB, - bool IsSimple, - MachineFunction &MF, - SmallVectorImpl &TDBBs, - SmallVectorImpl &Copies); - bool TailDuplicateAndUpdate(MachineBasicBlock *MBB, - bool IsSimple, - MachineFunction &MF); - - void RemoveDeadBlock(MachineBasicBlock *MBB); }; char TailDuplicatePass::ID = 0; @@ -136,19 +79,13 @@ if (skipOptnoneFunction(*MF.getFunction())) return false; - TII = MF.getSubtarget().getInstrInfo(); - TRI = MF.getSubtarget().getRegisterInfo(); - MRI = &MF.getRegInfo(); - MMI = getAnalysisIfAvailable(); - MBPI = &getAnalysis(); + auto MMI = getAnalysisIfAvailable(); + auto MBPI = &getAnalysis(); - PreRegAlloc = MRI->isSSA(); - RS.reset(); - if (MRI->tracksLiveness() && TRI->trackLivenessAfterRegAlloc(MF)) - RS.reset(new RegScavenger()); + Duplicator.initMF(MF, MMI, MBPI); bool MadeChange = false; - while (TailDuplicateBlocks(MF)) + while (Duplicator.tailDuplicateBlocks(MF)) MadeChange = true; return MadeChange; @@ -159,6 +96,26 @@ MachineFunctionPass::getAnalysisUsage(AU); } +namespace llvm { + +void TailDuplicator::initMF(MachineFunction &MF, + const MachineModuleInfo *MMIin, + const MachineBranchProbabilityInfo *MBPIin) { + TII = MF.getSubtarget().getInstrInfo(); + TRI = MF.getSubtarget().getRegisterInfo(); + MRI = &MF.getRegInfo(); + MMI = MMIin; + MBPI = MBPIin; + + assert (MBPI != nullptr && "Machine Branch Probability Info required"); + + PreRegAlloc = MRI->isSSA(); + RS.reset(); + + if (MRI->tracksLiveness() && TRI->trackLivenessAfterRegAlloc(MF)) + RS.reset(new RegScavenger()); +} + static void VerifyPHIs(MachineFunction &MF, bool CheckExtra) { for (MachineFunction::iterator I = ++MF.begin(), E = MF.end(); I != E; ++I) { MachineBasicBlock *MBB = &*I; @@ -209,16 +166,16 @@ /// Tail duplicate the block and cleanup. bool -TailDuplicatePass::TailDuplicateAndUpdate(MachineBasicBlock *MBB, - bool IsSimple, - MachineFunction &MF) { +TailDuplicator::tailDuplicateAndUpdate(MachineFunction &MF, + bool IsSimple, + MachineBasicBlock *MBB) { // Save the successors list. SmallSetVector Succs(MBB->succ_begin(), MBB->succ_end()); SmallVector TDBBs; SmallVector Copies; - if (!TailDuplicate(MBB, IsSimple, MF, TDBBs, Copies)) + if (!tailDuplicate(MF, IsSimple, MBB, TDBBs, Copies)) return false; ++NumTails; @@ -231,12 +188,12 @@ // instructions. bool isDead = MBB->pred_empty() && !MBB->hasAddressTaken(); if (PreRegAlloc) - UpdateSuccessorsPHIs(MBB, isDead, TDBBs, Succs); + updateSuccessorsPHIs(MBB, isDead, TDBBs, Succs); // If it is dead, remove it. if (isDead) { NumInstrDups -= MBB->size(); - RemoveDeadBlock(MBB); + removeDeadBlock(MBB); ++NumDeadBlocks; } @@ -313,7 +270,7 @@ /// Look for small blocks that are unconditionally branched to and do not fall /// through. Tail-duplicate their instructions into their predecessors to /// eliminate (dynamic) branches. -bool TailDuplicatePass::TailDuplicateBlocks(MachineFunction &MF) { +bool TailDuplicator::tailDuplicateBlocks(MachineFunction &MF) { bool MadeChange = false; if (PreRegAlloc && TailDupVerify) { @@ -332,7 +289,7 @@ if (!shouldTailDuplicate(MF, IsSimple, *MBB)) continue; - MadeChange |= TailDuplicateAndUpdate(MBB, IsSimple, MF); + MadeChange |= tailDuplicateAndUpdate(MF, IsSimple, MBB); } if (PreRegAlloc && TailDupVerify) @@ -376,8 +333,8 @@ } /// Add a definition and source virtual registers pair for SSA update. -void TailDuplicatePass::AddSSAUpdateEntry(unsigned OrigReg, unsigned NewReg, - MachineBasicBlock *BB) { +void TailDuplicator::addSSAUpdateEntry(unsigned OrigReg, unsigned NewReg, + MachineBasicBlock *BB) { DenseMap::iterator LI= SSAUpdateVals.find(OrigReg); if (LI != SSAUpdateVals.end()) LI->second.push_back(std::make_pair(BB, NewReg)); @@ -391,7 +348,7 @@ /// Process PHI node in TailBB by turning it into a copy in PredBB. Remember the /// source register that's contributed by PredBB and update SSA update map. -void TailDuplicatePass::ProcessPHI( +void TailDuplicator::processPHI( MachineInstr *MI, MachineBasicBlock *TailBB, MachineBasicBlock *PredBB, DenseMap &LocalVRMap, SmallVectorImpl > &Copies, @@ -408,7 +365,7 @@ unsigned NewDef = MRI->createVirtualRegister(RC); Copies.push_back(std::make_pair(NewDef, SrcReg)); if (isDefLiveOut(DefReg, TailBB, MRI) || RegsUsedByPhi.count(DefReg)) - AddSSAUpdateEntry(DefReg, NewDef, PredBB); + addSSAUpdateEntry(DefReg, NewDef, PredBB); if (!Remove) return; @@ -422,7 +379,8 @@ /// Duplicate a TailBB instruction to PredBB and update /// the source operands due to earlier PHI translation. -void TailDuplicatePass::DuplicateInstruction(MachineInstr *MI, +void +TailDuplicator::duplicateInstruction(MachineInstr *MI, MachineBasicBlock *TailBB, MachineBasicBlock *PredBB, MachineFunction &MF, @@ -443,7 +401,7 @@ MO.setReg(NewReg); LocalVRMap.insert(std::make_pair(Reg, NewReg)); if (isDefLiveOut(Reg, TailBB, MRI) || UsedByPhi.count(Reg)) - AddSSAUpdateEntry(Reg, NewReg, PredBB); + addSSAUpdateEntry(Reg, NewReg, PredBB); } else { DenseMap::iterator VI = LocalVRMap.find(Reg); if (VI != LocalVRMap.end()) { @@ -463,9 +421,9 @@ /// have gained new predecessors. Update the PHI instructions in them /// accordingly. void -TailDuplicatePass::UpdateSuccessorsPHIs(MachineBasicBlock *FromBB, bool isDead, - SmallVectorImpl &TDBBs, - SmallSetVector &Succs) { +TailDuplicator::updateSuccessorsPHIs(MachineBasicBlock *FromBB, bool isDead, + SmallVectorImpl &TDBBs, + SmallSetVector &Succs) { for (SmallSetVector::iterator SI = Succs.begin(), SE = Succs.end(); SI != SE; ++SI) { MachineBasicBlock *SuccBB = *SI; @@ -547,9 +505,9 @@ /// Determine if it is profitable to duplicate this block. bool -TailDuplicatePass::shouldTailDuplicate(const MachineFunction &MF, - bool IsSimple, - MachineBasicBlock &TailBB) { +TailDuplicator::shouldTailDuplicate(const MachineFunction &MF, + bool IsSimple, + MachineBasicBlock &TailBB) { // Only duplicate blocks that end with unconditional branches. if (TailBB.canFallThrough()) return false; @@ -649,7 +607,7 @@ /// True if this BB has only one unconditional jump. bool -TailDuplicatePass::isSimpleBB(MachineBasicBlock *TailBB) { +TailDuplicator::isSimpleBB(MachineBasicBlock *TailBB) { if (TailBB->succ_size() != 1) return false; if (TailBB->pred_empty()) @@ -671,7 +629,7 @@ } bool -TailDuplicatePass::canCompletelyDuplicateBB(MachineBasicBlock &BB) { +TailDuplicator::canCompletelyDuplicateBB(MachineBasicBlock &BB) { for (MachineBasicBlock *PredBB : BB.predecessors()) { if (PredBB->succ_size() > 1) return false; @@ -688,7 +646,7 @@ } bool -TailDuplicatePass::duplicateSimpleBB(MachineBasicBlock *TailBB, +TailDuplicator::duplicateSimpleBB(MachineBasicBlock *TailBB, SmallVectorImpl &TDBBs, const DenseSet &UsedByPhi, SmallVectorImpl &Copies) { @@ -767,11 +725,11 @@ /// If it is profitable, duplicate TailBB's contents in each /// of its predecessors. bool -TailDuplicatePass::TailDuplicate(MachineBasicBlock *TailBB, - bool IsSimple, - MachineFunction &MF, - SmallVectorImpl &TDBBs, - SmallVectorImpl &Copies) { +TailDuplicator::tailDuplicate(MachineFunction &MF, + bool IsSimple, + MachineBasicBlock *TailBB, + SmallVectorImpl &TDBBs, + SmallVectorImpl &Copies) { DEBUG(dbgs() << "\n*** Tail-duplicating BB#" << TailBB->getNumber() << '\n'); DenseSet UsedByPhi; @@ -840,11 +798,11 @@ if (MI->isPHI()) { // Replace the uses of the def of the PHI with the register coming // from PredBB. - ProcessPHI(MI, TailBB, PredBB, LocalVRMap, CopyInfos, UsedByPhi, true); + processPHI(MI, TailBB, PredBB, LocalVRMap, CopyInfos, UsedByPhi, true); } else { // Replace def of virtual registers with new registers, and update // uses with PHI source register or the new registers. - DuplicateInstruction(MI, TailBB, PredBB, MF, LocalVRMap, UsedByPhi); + duplicateInstruction(MI, TailBB, PredBB, MF, LocalVRMap, UsedByPhi); } } MachineBasicBlock::iterator Loc = PredBB->getFirstTerminator(); @@ -894,7 +852,7 @@ // Replace the uses of the def of the PHI with the register coming // from PredBB. MachineInstr *MI = &*I++; - ProcessPHI(MI, TailBB, PrevBB, LocalVRMap, CopyInfos, UsedByPhi, true); + processPHI(MI, TailBB, PrevBB, LocalVRMap, CopyInfos, UsedByPhi, true); if (MI->getParent()) MI->eraseFromParent(); } @@ -905,7 +863,7 @@ // uses with PHI source register or the new registers. MachineInstr *MI = &*I++; assert(!MI->isBundle() && "Not expecting bundles before regalloc!"); - DuplicateInstruction(MI, TailBB, PrevBB, MF, LocalVRMap, UsedByPhi); + duplicateInstruction(MI, TailBB, PrevBB, MF, LocalVRMap, UsedByPhi); MI->eraseFromParent(); } MachineBasicBlock::iterator Loc = PrevBB->getFirstTerminator(); @@ -967,7 +925,7 @@ // Replace the uses of the def of the PHI with the register coming // from PredBB. MachineInstr *MI = &*I++; - ProcessPHI(MI, TailBB, PredBB, LocalVRMap, CopyInfos, UsedByPhi, false); + processPHI(MI, TailBB, PredBB, LocalVRMap, CopyInfos, UsedByPhi, false); } MachineBasicBlock::iterator Loc = PredBB->getFirstTerminator(); for (unsigned i = 0, e = CopyInfos.size(); i != e; ++i) { @@ -982,7 +940,7 @@ /// Remove the specified dead machine basic block from the function, updating /// the CFG. -void TailDuplicatePass::RemoveDeadBlock(MachineBasicBlock *MBB) { +void TailDuplicator::removeDeadBlock(MachineBasicBlock *MBB) { assert(MBB->pred_empty() && "MBB must be dead!"); DEBUG(dbgs() << "\nRemoving MBB: " << *MBB); @@ -993,3 +951,5 @@ // Remove the block. MBB->eraseFromParent(); } + +} // End llvm namespace