From e4ddbdfd3cf031034020671d03626f0373fbd5ca Mon Sep 17 00:00:00 2001 From: Bill Wendling Date: Fri, 6 Aug 2010 01:32:48 +0000 Subject: [PATCH] Add the Optimize Compares pass (disabled by default). This pass tries to remove comparison instructions when possible. For instance, if you have this code: sub r1, 1 cmp r1, 0 bz L1 and "sub" either sets the same flag as the "cmp" instruction or could be converted to set the same flag, then we can eliminate the "cmp" instruction all together. This is a important for ARM where the ALU instructions could set the CPSR flag, but need a special suffix ('s') to do so. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@110423 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/CodeGen/Passes.h | 4 + include/llvm/Target/TargetInstrInfo.h | 15 ++++ lib/CodeGen/LLVMTargetMachine.cpp | 1 + lib/CodeGen/OptimizeCmps.cpp | 112 ++++++++++++++++++++++++++ lib/Target/ARM/ARMBaseInstrInfo.cpp | 56 +++++++++++++ lib/Target/ARM/ARMBaseInstrInfo.h | 11 +++ 6 files changed, 199 insertions(+) create mode 100644 lib/CodeGen/OptimizeCmps.cpp diff --git a/include/llvm/CodeGen/Passes.h b/include/llvm/CodeGen/Passes.h index c881d74c110..0fcdf7a691b 100644 --- a/include/llvm/CodeGen/Passes.h +++ b/include/llvm/CodeGen/Passes.h @@ -180,6 +180,10 @@ namespace llvm { /// 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/include/llvm/Target/TargetInstrInfo.h b/include/llvm/Target/TargetInstrInfo.h index d5fe33ff88c..1c6ac1a61c7 100644 --- a/include/llvm/Target/TargetInstrInfo.h +++ b/include/llvm/Target/TargetInstrInfo.h @@ -576,6 +576,21 @@ public: /// register allocation. virtual ScheduleHazardRecognizer* CreateTargetPostRAHazardRecognizer(const InstrItineraryData&) const = 0; + + /// isCompareInstr - If the machine instruction is a comparison instruction, + /// then return true. Also return the source register in SrcReg and the value + /// it compares against in CmpValue. + virtual bool isCompareInstr(const MachineInstr *MI, + unsigned &SrcReg, int &CmpValue) const { + return false; + } + + /// convertToSetZeroFlag - Convert the instruction to set the zero flag so + /// that we can remove a "comparison with zero". + virtual bool convertToSetZeroFlag(MachineInstr *Instr, + MachineInstr *CmpInstr) const { + return false; + } }; /// TargetInstrInfoImpl - This is the default implementation of diff --git a/lib/CodeGen/LLVMTargetMachine.cpp b/lib/CodeGen/LLVMTargetMachine.cpp index 36c837d59fe..5b2d40b5857 100644 --- a/lib/CodeGen/LLVMTargetMachine.cpp +++ b/lib/CodeGen/LLVMTargetMachine.cpp @@ -354,6 +354,7 @@ bool LLVMTargetMachine::addCommonCodeGenPasses(PassManagerBase &PM, printAndVerify(PM, "After codegen DCE pass"); PM.add(createOptimizeExtsPass()); + PM.add(createOptimizeCmpsPass()); if (!DisableMachineLICM) PM.add(createMachineLICMPass()); PM.add(createMachineCSEPass()); diff --git a/lib/CodeGen/OptimizeCmps.cpp b/lib/CodeGen/OptimizeCmps.cpp new file mode 100644 index 00000000000..cd396cc2eae --- /dev/null +++ b/lib/CodeGen/OptimizeCmps.cpp @@ -0,0 +1,112 @@ +//===-- 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->isCompareInstr(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++; + Changed |= OptimizeCmpInstr(MI, MBB); + } + } + + return Changed; +} diff --git a/lib/Target/ARM/ARMBaseInstrInfo.cpp b/lib/Target/ARM/ARMBaseInstrInfo.cpp index b9784eec1bf..68e35ed75e3 100644 --- a/lib/Target/ARM/ARMBaseInstrInfo.cpp +++ b/lib/Target/ARM/ARMBaseInstrInfo.cpp @@ -1353,3 +1353,59 @@ bool llvm::rewriteARMFrameIndex(MachineInstr &MI, unsigned FrameRegIdx, Offset = (isSub) ? -Offset : Offset; return Offset == 0; } + +bool ARMBaseInstrInfo:: +isCompareInstr(const MachineInstr *MI, unsigned &SrcReg, int &CmpValue) const { + switch (MI->getOpcode()) { + default: break; + case ARM::t2CMPri: + case ARM::t2CMPzri: + SrcReg = MI->getOperand(0).getReg(); + CmpValue = MI->getOperand(1).getImm(); + return true; + } + + return false; +} + +/// convertToSetZeroFlag - Convert the instruction to set the "zero" flag so +/// that we can remove a "comparison with zero". +bool ARMBaseInstrInfo:: +convertToSetZeroFlag(MachineInstr *MI, MachineInstr *CmpInstr) const { + // Conservatively refuse to convert an instruction which isn't in the same BB + // as the comparison. + if (MI->getParent() != CmpInstr->getParent()) + return false; + + // Check that CPSR isn't set between the comparison instruction and the one we + // want to change. + MachineBasicBlock::const_iterator I = CmpInstr, E = MI; + --I; + for (; I != E; --I) { + const MachineInstr &Instr = *I; + + for (unsigned IO = 0, EO = Instr.getNumOperands(); IO != EO; ++IO) { + const MachineOperand &MO = Instr.getOperand(IO); + if (!MO.isDef() || !MO.isReg()) continue; + + // This instruction modifies CPSR before the one we want to change. We + // can't do this transformation. + if (MO.getReg() == ARM::CPSR) + return false; + } + } + + // Set the "zero" bit in CPSR. + switch (MI->getOpcode()) { + default: break; + case ARM::t2SUBri: { + MI->RemoveOperand(5); + MachineInstrBuilder MB(MI); + MB.addReg(ARM::CPSR, RegState::Define | RegState::Implicit); + CmpInstr->eraseFromParent(); + return true; + } + } + + return false; +} diff --git a/lib/Target/ARM/ARMBaseInstrInfo.h b/lib/Target/ARM/ARMBaseInstrInfo.h index 20fae2e54ee..4f1c4539243 100644 --- a/lib/Target/ARM/ARMBaseInstrInfo.h +++ b/lib/Target/ARM/ARMBaseInstrInfo.h @@ -336,6 +336,17 @@ public: unsigned NumInstrs) const { return NumInstrs && NumInstrs == 1; } + + /// isCompareInstr - If the machine instruction is a comparison instruction, + /// then return true. Also return the source register in SrcReg and the value + /// it compares against in CmpValue. + virtual bool isCompareInstr(const MachineInstr *MI, unsigned &SrcReg, + int &CmpValue) const; + + /// convertToSetZeroFlag - Convert the instruction to set the zero flag so + /// that we can remove a "comparison with zero". + virtual bool convertToSetZeroFlag(MachineInstr *Instr, + MachineInstr *CmpInstr) const; }; static inline -- 2.34.1