From 6cdb1abe4e4f6364649e7ef656589441754e82ae Mon Sep 17 00:00:00 2001 From: Bill Wendling Date: Mon, 9 Aug 2010 23:59:04 +0000 Subject: [PATCH] Merge the OptimizeExts and OptimizeCmps passes into one PeepholeOptimizer pass. This pass should expand with all of the small, fine-grained optimization passes to reduce compile time and increase happiment. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@110627 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/CodeGen/Passes.h | 10 +- lib/CodeGen/LLVMTargetMachine.cpp | 3 +- lib/CodeGen/OptimizeCmps.cpp | 112 ----------- ...OptimizeExts.cpp => PeepholeOptimizer.cpp} | 174 +++++++++++++----- 4 files changed, 127 insertions(+), 172 deletions(-) delete mode 100644 lib/CodeGen/OptimizeCmps.cpp rename lib/CodeGen/{OptimizeExts.cpp => PeepholeOptimizer.cpp} (52%) diff --git a/include/llvm/CodeGen/Passes.h b/include/llvm/CodeGen/Passes.h index b9d97b185ae..3e6b3e15d22 100644 --- a/include/llvm/CodeGen/Passes.h +++ b/include/llvm/CodeGen/Passes.h @@ -172,18 +172,14 @@ namespace llvm { /// instructions. FunctionPass *createMachineSinkingPass(); - /// createOptimizeExtsPass - This pass performs sign / zero extension - /// optimization by increasing uses of extended values. - FunctionPass *createOptimizeExtsPass(); + /// createPeepholeOptimizerPass - This pass performs peephole optimizations - + /// like extension and comparison eliminations. + FunctionPass *createPeepholeOptimizerPass(); /// createOptimizePHIsPass - This pass optimizes machine instruction PHIs /// to take advantage of opportunities created during DAG legalization. FunctionPass *createOptimizePHIsPass(); - /// createOptimizeCmpsPass - This pass performs redundant comparison removal - /// optimization. - FunctionPass *createOptimizeCmpsPass(); - /// createStackSlotColoringPass - This pass performs stack slot coloring. FunctionPass *createStackSlotColoringPass(bool); diff --git a/lib/CodeGen/LLVMTargetMachine.cpp b/lib/CodeGen/LLVMTargetMachine.cpp index 5b2d40b5857..f5112f7f62b 100644 --- a/lib/CodeGen/LLVMTargetMachine.cpp +++ b/lib/CodeGen/LLVMTargetMachine.cpp @@ -353,8 +353,7 @@ bool LLVMTargetMachine::addCommonCodeGenPasses(PassManagerBase &PM, PM.add(createDeadMachineInstructionElimPass()); printAndVerify(PM, "After codegen DCE pass"); - PM.add(createOptimizeExtsPass()); - PM.add(createOptimizeCmpsPass()); + PM.add(createPeepholeOptimizerPass()); if (!DisableMachineLICM) PM.add(createMachineLICMPass()); PM.add(createMachineCSEPass()); diff --git a/lib/CodeGen/OptimizeCmps.cpp b/lib/CodeGen/OptimizeCmps.cpp deleted file mode 100644 index 209c8b95047..00000000000 --- a/lib/CodeGen/OptimizeCmps.cpp +++ /dev/null @@ -1,112 +0,0 @@ -//===-- OptimizeCmps.cpp - Optimize comparison instrs ---------------------===// -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// -// -// This pass performs optimization of comparison instructions. For instance, in -// this code: -// -// sub r1, 1 -// cmp r1, 0 -// bz L1 -// -// If the "sub" instruction all ready sets (or could be modified to set) the -// same flag that the "cmp" instruction sets and that "bz" uses, then we can -// eliminate the "cmp" instruction. -// -//===----------------------------------------------------------------------===// - -#define DEBUG_TYPE "opt-compares" -#include "llvm/CodeGen/Passes.h" -#include "llvm/CodeGen/MachineFunctionPass.h" -#include "llvm/CodeGen/MachineInstrBuilder.h" -#include "llvm/CodeGen/MachineRegisterInfo.h" -#include "llvm/Target/TargetInstrInfo.h" -#include "llvm/Target/TargetRegisterInfo.h" -#include "llvm/Support/CommandLine.h" -#include "llvm/ADT/Statistic.h" -using namespace llvm; - -STATISTIC(NumEliminated, "Number of compares eliminated"); - -static cl::opt -EnableOptCmps("enable-optimize-cmps", cl::init(false), cl::Hidden); - -namespace { - class OptimizeCmps : public MachineFunctionPass { - const TargetMachine *TM; - const TargetInstrInfo *TII; - MachineRegisterInfo *MRI; - - bool OptimizeCmpInstr(MachineInstr *MI, MachineBasicBlock *MBB); - - public: - static char ID; // Pass identification - OptimizeCmps() : MachineFunctionPass(ID) {} - - virtual bool runOnMachineFunction(MachineFunction &MF); - - virtual void getAnalysisUsage(AnalysisUsage &AU) const { - AU.setPreservesCFG(); - MachineFunctionPass::getAnalysisUsage(AU); - } - }; -} - -char OptimizeCmps::ID = 0; -INITIALIZE_PASS(OptimizeCmps, "opt-cmps", - "Optimize comparison instrs", false, false); - -FunctionPass *llvm::createOptimizeCmpsPass() { return new OptimizeCmps(); } - -/// OptimizeCmpInstr - If the instruction is a compare and the previous -/// instruction it's comparing against all ready sets (or could be modified to -/// set) the same flag as the compare, then we can remove the comparison and use -/// the flag from the previous instruction. -bool OptimizeCmps::OptimizeCmpInstr(MachineInstr *MI, MachineBasicBlock *MBB) { - // If this instruction is a comparison against zero and isn't comparing a - // physical register, we can try to optimize it. - unsigned SrcReg; - int CmpValue; - if (!TII->AnalyzeCompare(MI, SrcReg, CmpValue) || - TargetRegisterInfo::isPhysicalRegister(SrcReg) || CmpValue != 0) - return false; - - MachineRegisterInfo::def_iterator DI = MRI->def_begin(SrcReg); - if (llvm::next(DI) != MRI->def_end()) - // Only support one definition. - return false; - - // Attempt to convert the defining instruction to set the "zero" flag. - if (TII->ConvertToSetZeroFlag(&*DI, MI)) { - ++NumEliminated; - return true; - } - - return false; -} - -bool OptimizeCmps::runOnMachineFunction(MachineFunction &MF) { - TM = &MF.getTarget(); - TII = TM->getInstrInfo(); - MRI = &MF.getRegInfo(); - - if (!EnableOptCmps) return false; - - bool Changed = false; - for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; ++I) { - MachineBasicBlock *MBB = &*I; - for (MachineBasicBlock::iterator - MII = MBB->begin(), ME = MBB->end(); MII != ME; ) { - MachineInstr *MI = &*MII++; - if (MI->getDesc().isCompare()) - Changed |= OptimizeCmpInstr(MI, MBB); - } - } - - return Changed; -} diff --git a/lib/CodeGen/OptimizeExts.cpp b/lib/CodeGen/PeepholeOptimizer.cpp similarity index 52% rename from lib/CodeGen/OptimizeExts.cpp rename to lib/CodeGen/PeepholeOptimizer.cpp index 288f58b5083..7ed41f4011f 100644 --- a/lib/CodeGen/OptimizeExts.cpp +++ b/lib/CodeGen/PeepholeOptimizer.cpp @@ -1,4 +1,4 @@ -//===-- OptimizeExts.cpp - Optimize sign / zero extension instrs -----===// +//===-- PeepholeOptimizer.cpp - Peephole Optimizations --------------------===// // // The LLVM Compiler Infrastructure // @@ -7,17 +7,33 @@ // //===----------------------------------------------------------------------===// // -// This pass performs optimization of sign / zero extension instructions. It -// may be extended to handle other instructions of similar property. +// Perform peephole optimizations on the machine code: // -// On some targets, some instructions, e.g. X86 sign / zero extension, may -// leave the source value in the lower part of the result. This pass will -// replace (some) uses of the pre-extension value with uses of the sub-register -// of the results. +// - Optimize Extensions // +// Optimization of sign / zero extension instructions. It may be extended to +// handle other instructions with similar properties. +// +// On some targets, some instructions, e.g. X86 sign / zero extension, may +// leave the source value in the lower part of the result. This optimization +// will replace some uses of the pre-extension value with uses of the +// sub-register of the results. +// +// - Optimize Comparisons +// +// Optimization of comparison instructions. For instance, in this code: +// +// sub r1, 1 +// cmp r1, 0 +// bz L1 +// +// If the "sub" instruction all ready sets (or could be modified to set) the +// same flag that the "cmp" instruction sets and that "bz" uses, then we can +// eliminate the "cmp" instruction. +// //===----------------------------------------------------------------------===// -#define DEBUG_TYPE "ext-opt" +#define DEBUG_TYPE "peephole-opt" #include "llvm/CodeGen/Passes.h" #include "llvm/CodeGen/MachineDominators.h" #include "llvm/CodeGen/MachineInstrBuilder.h" @@ -29,21 +45,29 @@ #include "llvm/ADT/Statistic.h" using namespace llvm; -static cl::opt Aggressive("aggressive-ext-opt", cl::Hidden, - cl::desc("Aggressive extension optimization")); +// Optimize Extensions +static cl::opt +Aggressive("aggressive-ext-opt", cl::Hidden, + cl::desc("Aggressive extension optimization")); STATISTIC(NumReuse, "Number of extension results reused"); +// Optimize Comparisons +static cl::opt +EnableOptCmps("enable-optimize-cmps", cl::init(false), cl::Hidden); + +STATISTIC(NumEliminated, "Number of compares eliminated"); + namespace { - class OptimizeExts : public MachineFunctionPass { + class PeepholeOptimizer : public MachineFunctionPass { const TargetMachine *TM; const TargetInstrInfo *TII; - MachineRegisterInfo *MRI; - MachineDominatorTree *DT; // Machine dominator tree + MachineRegisterInfo *MRI; + MachineDominatorTree *DT; // Machine dominator tree public: static char ID; // Pass identification - OptimizeExts() : MachineFunctionPass(ID) {} + PeepholeOptimizer() : MachineFunctionPass(ID) {} virtual bool runOnMachineFunction(MachineFunction &MF); @@ -57,27 +81,32 @@ namespace { } private: - bool OptimizeInstr(MachineInstr *MI, MachineBasicBlock *MBB, - SmallPtrSet &LocalMIs); + bool OptimizeCmpInstr(MachineInstr *MI, MachineBasicBlock *MBB); + bool OptimizeExtInstr(MachineInstr *MI, MachineBasicBlock *MBB, + SmallPtrSet &LocalMIs); }; } -char OptimizeExts::ID = 0; -INITIALIZE_PASS(OptimizeExts, "opt-exts", - "Optimize sign / zero extensions", false, false); - -FunctionPass *llvm::createOptimizeExtsPass() { return new OptimizeExts(); } - -/// OptimizeInstr - If instruction is a copy-like instruction, i.e. it reads -/// a single register and writes a single register and it does not modify -/// the source, and if the source value is preserved as a sub-register of -/// the result, then replace all reachable uses of the source with the subreg -/// of the result. -/// Do not generate an EXTRACT that is used only in a debug use, as this -/// changes the code. Since this code does not currently share EXTRACTs, just -/// ignore all debug uses. -bool OptimizeExts::OptimizeInstr(MachineInstr *MI, MachineBasicBlock *MBB, - SmallPtrSet &LocalMIs) { +char PeepholeOptimizer::ID = 0; +INITIALIZE_PASS(PeepholeOptimizer, "peephole-opts", + "Peephole Optimizations", false, false); + +FunctionPass *llvm::createPeepholeOptimizerPass() { + return new PeepholeOptimizer(); +} + +/// OptimizeExtInstr - If instruction is a copy-like instruction, i.e. it reads +/// a single register and writes a single register and it does not modify the +/// source, and if the source value is preserved as a sub-register of the +/// result, then replace all reachable uses of the source with the subreg of the +/// result. +/// +/// Do not generate an EXTRACT that is used only in a debug use, as this changes +/// the code. Since this code does not currently share EXTRACTs, just ignore all +/// debug uses. +bool PeepholeOptimizer:: +OptimizeExtInstr(MachineInstr *MI, MachineBasicBlock *MBB, + SmallPtrSet &LocalMIs) { LocalMIs.insert(MI); unsigned SrcReg, DstReg, SubIdx; @@ -93,20 +122,21 @@ bool OptimizeExts::OptimizeInstr(MachineInstr *MI, MachineBasicBlock *MBB, // No other uses. return false; - // Ok, the source has other uses. See if we can replace the other uses - // with use of the result of the extension. + // The source has other uses. See if we can replace the other uses with use of + // the result of the extension. SmallPtrSet ReachedBBs; UI = MRI->use_nodbg_begin(DstReg); for (MachineRegisterInfo::use_nodbg_iterator UE = MRI->use_nodbg_end(); UI != UE; ++UI) ReachedBBs.insert(UI->getParent()); - bool ExtendLife = true; // Uses that are in the same BB of uses of the result of the instruction. SmallVector Uses; + // Uses that the result of the instruction can reach. SmallVector ExtendedUses; + bool ExtendLife = true; UI = MRI->use_nodbg_begin(SrcReg); for (MachineRegisterInfo::use_nodbg_iterator UE = MRI->use_nodbg_end(); UI != UE; ++UI) { @@ -114,6 +144,7 @@ bool OptimizeExts::OptimizeInstr(MachineInstr *MI, MachineBasicBlock *MBB, MachineInstr *UseMI = &*UI; if (UseMI == MI) continue; + if (UseMI->isPHI()) { ExtendLife = false; continue; @@ -144,15 +175,15 @@ bool OptimizeExts::OptimizeInstr(MachineInstr *MI, MachineBasicBlock *MBB, // Local uses that come after the extension. if (!LocalMIs.count(UseMI)) Uses.push_back(&UseMO); - } else if (ReachedBBs.count(UseMBB)) - // Non-local uses where the result of extension is used. Always replace - // these unless it's a PHI. + } else if (ReachedBBs.count(UseMBB)) { + // Non-local uses where the result of the extension is used. Always + // replace these unless it's a PHI. Uses.push_back(&UseMO); - else if (Aggressive && DT->dominates(MBB, UseMBB)) - // We may want to extend live range of the extension result in order to - // replace these uses. + } else if (Aggressive && DT->dominates(MBB, UseMBB)) { + // We may want to extend the live range of the extension result in order + // to replace these uses. ExtendedUses.push_back(&UseMO); - else { + } else { // Both will be live out of the def MBB anyway. Don't extend live range of // the extension result. ExtendLife = false; @@ -161,7 +192,7 @@ bool OptimizeExts::OptimizeInstr(MachineInstr *MI, MachineBasicBlock *MBB, } if (ExtendLife && !ExtendedUses.empty()) - // Ok, we'll extend the liveness of the extension result. + // Extend the liveness of the extension result. std::copy(ExtendedUses.begin(), ExtendedUses.end(), std::back_inserter(Uses)); @@ -169,12 +200,13 @@ bool OptimizeExts::OptimizeInstr(MachineInstr *MI, MachineBasicBlock *MBB, bool Changed = false; if (!Uses.empty()) { SmallPtrSet PHIBBs; + // Look for PHI uses of the extended result, we don't want to extend the // liveness of a PHI input. It breaks all kinds of assumptions down // stream. A PHI use is expected to be the kill of its source values. UI = MRI->use_nodbg_begin(DstReg); - for (MachineRegisterInfo::use_nodbg_iterator UE = MRI->use_nodbg_end(); - UI != UE; ++UI) + for (MachineRegisterInfo::use_nodbg_iterator + UE = MRI->use_nodbg_end(); UI != UE; ++UI) if (UI->isPHI()) PHIBBs.insert(UI->getParent()); @@ -185,10 +217,12 @@ bool OptimizeExts::OptimizeInstr(MachineInstr *MI, MachineBasicBlock *MBB, MachineBasicBlock *UseMBB = UseMI->getParent(); if (PHIBBs.count(UseMBB)) continue; + unsigned NewVR = MRI->createVirtualRegister(RC); BuildMI(*UseMBB, UseMI, UseMI->getDebugLoc(), TII->get(TargetOpcode::COPY), NewVR) .addReg(DstReg, 0, SubIdx); + UseMO->setReg(NewVR); ++NumReuse; Changed = true; @@ -198,11 +232,41 @@ bool OptimizeExts::OptimizeInstr(MachineInstr *MI, MachineBasicBlock *MBB, return Changed; } -bool OptimizeExts::runOnMachineFunction(MachineFunction &MF) { - TM = &MF.getTarget(); +/// OptimizeCmpInstr - If the instruction is a compare and the previous +/// instruction it's comparing against all ready sets (or could be modified to +/// set) the same flag as the compare, then we can remove the comparison and use +/// the flag from the previous instruction. +bool PeepholeOptimizer::OptimizeCmpInstr(MachineInstr *MI, + MachineBasicBlock *MBB) { + if (!EnableOptCmps) return false; + + // If this instruction is a comparison against zero and isn't comparing a + // physical register, we can try to optimize it. + unsigned SrcReg; + int CmpValue; + if (!TII->AnalyzeCompare(MI, SrcReg, CmpValue) || + TargetRegisterInfo::isPhysicalRegister(SrcReg) || CmpValue != 0) + return false; + + MachineRegisterInfo::def_iterator DI = MRI->def_begin(SrcReg); + if (llvm::next(DI) != MRI->def_end()) + // Only support one definition. + return false; + + // Attempt to convert the defining instruction to set the "zero" flag. + if (TII->ConvertToSetZeroFlag(&*DI, MI)) { + ++NumEliminated; + return true; + } + + return false; +} + +bool PeepholeOptimizer::runOnMachineFunction(MachineFunction &MF) { + TM = &MF.getTarget(); TII = TM->getInstrInfo(); MRI = &MF.getRegInfo(); - DT = Aggressive ? &getAnalysis() : 0; + DT = Aggressive ? &getAnalysis() : 0; bool Changed = false; @@ -210,10 +274,18 @@ bool OptimizeExts::runOnMachineFunction(MachineFunction &MF) { for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; ++I) { MachineBasicBlock *MBB = &*I; LocalMIs.clear(); - for (MachineBasicBlock::iterator MII = I->begin(), ME = I->end(); MII != ME; - ++MII) { + + for (MachineBasicBlock::iterator + MII = I->begin(), ME = I->end(); MII != ME; ) { MachineInstr *MI = &*MII; - Changed |= OptimizeInstr(MI, MBB, LocalMIs); + + if (MI->getDesc().isCompare()) { + ++MII; // The iterator may become invalid if the compare is deleted. + Changed |= OptimizeCmpInstr(MI, MBB); + } else { + Changed |= OptimizeExtInstr(MI, MBB, LocalMIs); + ++MII; + } } } -- 2.34.1