Page MenuHomePhabricator
Differential D130769 Diff 454777 llvm/lib/Target/RISCV/RISCVAddSubCombiner.cpp

Changeset View

Standalone View

View Options

llvm/lib/Target/RISCV/RISCVAddSubCombiner.cpp

  • This file was added.
//===- RISCVAddSubCombiner.cpp - RISCV add/sub combiner pass -------===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
//
// This file contains a pass that performs add/sub operations combining and
// removing redundant ones.
//
//===----------------------------------------------------------------------===//
#include "RISCV.h"
#include "RISCVInstrInfo.h"
#include "RISCVMachineFunctionInfo.h"
#include "RISCVSubtarget.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/CodeGen/MachineBasicBlock.h"
#include "llvm/CodeGen/MachineFunction.h"
#include "llvm/CodeGen/MachineFunctionPass.h"
#include "llvm/CodeGen/MachineInstr.h"
#include "llvm/CodeGen/MachineInstrBuilder.h"
#include "llvm/CodeGen/MachineOperand.h"
#include "llvm/CodeGen/TargetRegisterInfo.h"
#include "llvm/IR/DebugLoc.h"
#include "llvm/Pass.h"
#include "llvm/Support/Debug.h"
#include <cassert>
using namespace llvm;
#define DEBUG_TYPE "riscv-addsub-comb"
STATISTIC(NumRemovedInstructions, "Number of removed add/sub instructions");
#define RISCV_ADD_SUB_COMB_NAME "RISCV add/sub combiner pass"
namespace {
class RISCVAddSubCombiner : public MachineFunctionPass {
// Instructions that are possible candidates to be combined keyed by
// destination registers.
craig.topperUnsubmitted
Done
ReplyInline Actions

"divided by" -> "keyed by"?

craig.topper: "divided by" -> "keyed by"?
DenseMap<Register, MachineInstr *> CandidatesToBeCombined;
// Destination registers of add/sub instructions that can potentially
// be optimized.
SmallVector<Register, 8> DestinationRegistersToCheck;
// List of ignored registers as far as they are used to work with frames.
SmallVector<Register, 8> IgnoredFrameRegisters;
// Registers that are used as operands and are monitored not to be modified.
DenseMap<Register, SmallVector<std::pair<Register, bool>, 4>>
ModificationRegisterMonitor;
const RISCVInstrInfo *TII;
const RISCVSubtarget *Subtarget;
bool optimizeBlock(MachineBasicBlock &MBB);
bool tryToCombineInstructions(MachineBasicBlock::iterator &MBBI,
unsigned Opcode);
void excludeFromCandidatesByRegister(const Register Reg);
unsigned getInverseInstructionOpcode(const MachineInstr &MI);
bool isAddOrSubInstr(const MachineInstr &MI);
void eraseInstructions(MachineBasicBlock::iterator &MBBI,
MachineInstr *CheckedInstr,
MachineInstr *CurrentInstr);
public:
static char ID;
RISCVAddSubCombiner() : MachineFunctionPass(ID) {
initializeRISCVAddSubCombinerPass(*PassRegistry::getPassRegistry());
}
void getAnalysisUsage(AnalysisUsage &AU) const override {
MachineFunctionPass::getAnalysisUsage(AU);
}
bool runOnMachineFunction(MachineFunction &MF) override;
MachineFunctionProperties getRequiredProperties() const override {
return MachineFunctionProperties().set(
MachineFunctionProperties::Property::NoVRegs);
}
StringRef getPassName() const override { return RISCV_ADD_SUB_COMB_NAME; }
};
char RISCVAddSubCombiner::ID = 0;
} // end anonymous namespace
INITIALIZE_PASS(RISCVAddSubCombiner, "riscv-addsub-comb",
RISCV_ADD_SUB_COMB_NAME, false, false)
void RISCVAddSubCombiner::eraseInstructions(MachineBasicBlock::iterator &MBBI,
MachineInstr *CheckedInstr,
MachineInstr *CurrentInstr) {
if (CurrentInstr)
MBBI--;
if (&*MBBI == CheckedInstr)
MBBI--;
// Remove both instructions.
LLVM_DEBUG(dbgs() << "Erase instruction " << *CheckedInstr << "\n");
CheckedInstr->eraseFromParent();
if (CurrentInstr) {
LLVM_DEBUG(dbgs() << "Erase instruction " << *CurrentInstr << "\n");
CurrentInstr->eraseFromParent();
}
}
bool RISCVAddSubCombiner::tryToCombineInstructions(
MachineBasicBlock::iterator &MBBI, unsigned Opcode) {
Register BaseRegister = MBBI->getOperand(0).getReg();
// Now supports only case when destination and source registers are the same.
if (BaseRegister != MBBI->getOperand(1).getReg())
craig.topperUnsubmitted
Done
ReplyInline Actions

Move this above the earlier if and use BaseRegister in the if

craig.topper: Move this above the earlier if and use `BaseRegister` in the if
return false;
if (MachineInstr *CheckedInstr = CandidatesToBeCombined[BaseRegister]) {
MachineInstr *CurrentInstr = &*MBBI;
craig.topperUnsubmitted
Done
ReplyInline Actions

Drop curly braces

craig.topper: Drop curly braces
if (Opcode != CheckedInstr->getOpcode())
return false;
// If the last operands are immediates combine instructions.
if (CheckedInstr->getOperand(2).isImm() && MBBI->getOperand(2).isImm()) {
int64_t ResultImm =
CheckedInstr->getOperand(2).getImm() + MBBI->getOperand(2).getImm();
// Validate result immediate.
if (!isInt<12>(ResultImm))
return false;
if (ResultImm != 0) {
MachineFunction *MF = MBBI->getParent()->getParent();
craig.topperUnsubmitted
Not Done
ReplyInline Actions

Can we update the immediate for MBBI instead of creating a new instruction?

craig.topper: Can we update the immediate for MBBI instead of creating a new instruction?
LLVM_DEBUG(dbgs() << "Replacing instructions:\n ");
LLVM_DEBUG(CheckedInstr->print(dbgs()));
LLVM_DEBUG(dbgs() << " ");
LLVM_DEBUG(MBBI->print(dbgs()));
LLVM_DEBUG(dbgs() << " with instruction:\n ");
// Combine instructions to one.
MBBI->getOperand(2).setImm(ResultImm);
MBBI->setFlags(CheckedInstr->mergeFlagsWith(*MBBI));
MBBI->cloneMergedMemRefs(*MF, {&*CheckedInstr, &*MBBI});
LLVM_DEBUG(MBBI->print(dbgs()));
LLVM_DEBUG(dbgs() << "\n");
CandidatesToBeCombined[BaseRegister] = &*MBBI;
NumRemovedInstructions++;
CurrentInstr = nullptr;
craig.topperUnsubmitted
Done
ReplyInline Actions

Why is the cast to MachineInstr* needed? Isn't there an operator-> on MIB?

craig.topper: Why is the cast to MachineInstr* needed? Isn't there an `operator->` on MIB?
} else {
excludeFromCandidatesByRegister(BaseRegister);
NumRemovedInstructions += 2;
}
eraseInstructions(MBBI, CheckedInstr, CurrentInstr);
return true;
}
// If the second operand is register, check that it isn't written.
if (CheckedInstr->getOperand(2).isReg() && MBBI->getOperand(2).isReg() &&
CheckedInstr->getOperand(2).getReg() == MBBI->getOperand(2).getReg()) {
assert(CheckedInstr->getOpcode() != MBBI->getOpcode());
// Can't combine if the last operand was modified between current
// instructions.
auto RegisterUsageIter = ModificationRegisterMonitor.find(MBBI->getOperand(2).getReg());
if (RegisterUsageIter != ModificationRegisterMonitor.end()) {
for (const auto &Users : RegisterUsageIter->second) {
if (Users.first == BaseRegister && Users.second) {
excludeFromCandidatesByRegister(BaseRegister);
return false;
craig.topperUnsubmitted
Done
ReplyInline Actions

Remove extra space before RegisterUsageIter

craig.topper: Remove extra space before `RegisterUsageIter`
craig.topperUnsubmitted
Not Done
ReplyInline Actions

Extra space here

craig.topper: Extra space here
}
}
}
craig.topperUnsubmitted
Done
ReplyInline Actions

Cann't -> Can't

craig.topper: Cann't -> Can't
eraseInstructions(MBBI, CheckedInstr, CurrentInstr);
excludeFromCandidatesByRegister(BaseRegister);
NumRemovedInstructions += 2;
return true;
}
craig.topperUnsubmitted
Done
ReplyInline Actions

Reuse the iterator returned from find above

craig.topper: Reuse the iterator returned from find above
}
return false;
}
void RISCVAddSubCombiner::excludeFromCandidatesByRegister(const Register Reg) {
for (auto &RegistersInfo : ModificationRegisterMonitor) {
erase_if(RegistersInfo.second, [&Reg](std::pair<Register, bool> Element) {
return Element.first == Reg;
});
}
erase_value(DestinationRegistersToCheck, Reg);
craig.topperUnsubmitted
Done
ReplyInline Actions

Can this use llvm::erase_if?

craig.topper: Can this use llvm::erase_if?
CandidatesToBeCombined.erase(Reg);
craig.topperUnsubmitted
Done
ReplyInline Actions

Something looks weird here. [&Reg](std::pair<Register, bool> Element) { is repeated

craig.topper: Something looks weird here. `[&Reg](std::pair<Register, bool> Element) {` is repeated
eklepilkinaAuthorUnsubmitted
Done
ReplyInline Actions

Sorry, cherry-picked and merged badly.

eklepilkina: Sorry, cherry-picked and merged badly.
}
bool RISCVAddSubCombiner::isAddOrSubInstr(const MachineInstr &MI) {
switch (MI.getOpcode()) {
craig.topperUnsubmitted
Done
ReplyInline Actions

Register is wrapper around unsigned. Pass it by value not reference

craig.topper: Register is wrapper around unsigned. Pass it by value not reference
default:
return false;
case RISCV::ADD:
craig.topperUnsubmitted
Done
ReplyInline Actions

llvm::find_if

craig.topper: llvm::find_if
case RISCV::ADDI:
craig.topperUnsubmitted
Done
ReplyInline Actions

llvm::erase_value?

craig.topper: llvm::erase_value?
case RISCV::ADDIW:
case RISCV::SUB:
return true;
}
}
// TODO: Rewrite with TableGen InstrMapping?
unsigned
RISCVAddSubCombiner::getInverseInstructionOpcode(const MachineInstr &MI) {
switch (MI.getOpcode()) {
default:
llvm_unreachable("Opcode has no inverse instruction!");
case RISCV::ADD:
return RISCV::SUB;
case RISCV::SUB:
return RISCV::ADD;
}
}
bool RISCVAddSubCombiner::optimizeBlock(MachineBasicBlock &MBB) {
CandidatesToBeCombined.clear();
DestinationRegistersToCheck.clear();
ModificationRegisterMonitor.clear();
bool Modified = false;
LLVM_DEBUG(dbgs() << MBB);
for (MachineBasicBlock::iterator MBBI = MBB.begin(), E = MBB.end(); MBBI != E;
MBBI++) {
if (isAddOrSubInstr(*MBBI) &&
(MBBI->getOperand(2).isImm() || MBBI->getOperand(2).isReg())) {
// Check if the instruction can be combined with existing candidates.
unsigned CheckedInstrOpcode = MBBI->getOperand(2).isImm()
? MBBI->getOpcode()
: getInverseInstructionOpcode(*MBBI);
bool Combined = tryToCombineInstructions(MBBI, CheckedInstrOpcode);
if (Combined) {
Modified = true;
LLVM_DEBUG(dbgs() << "Successfully combined\n");
continue;
}
craig.topperUnsubmitted
Done
ReplyInline Actions

It doesn't look like Modified is assigned anywhere else in this function

craig.topper: It doesn't look like Modified is assigned anywhere else in this function
}
// Check operands of instruction.
for (const auto &Operand : reverse(MBBI->operands())) {
if (Operand.isReg()) {
Register OperandRegister = Operand.getReg();
if (ModificationRegisterMonitor.find(OperandRegister) !=
ModificationRegisterMonitor.end() &&
MBBI->modifiesRegister(OperandRegister)) {
for (auto &Users : ModificationRegisterMonitor[OperandRegister])
Users.second = true;
}
if (is_contained(DestinationRegistersToCheck, OperandRegister)) {
if (Operand.isDef() && !Operand.isImplicit()) {
// Result of instruction is forbidden, can erase it.
LLVM_DEBUG(dbgs() << "Erase instruction "
<< *CandidatesToBeCombined[Operand.getReg()]
<< " as redundant\n");
CandidatesToBeCombined[Operand.getReg()]->eraseFromParent();
craig.topperUnsubmitted
Done
ReplyInline Actions

This should be a reference.

craig.topper: This should be a reference.
Modified = true;
NumRemovedInstructions++;
}
craig.topperUnsubmitted
Done
ReplyInline Actions

llvm::is_contained?

craig.topper: llvm::is_contained?
// Value of add/sub expressions is used.
excludeFromCandidatesByRegister(Operand.getReg());
craig.topperUnsubmitted
Done
ReplyInline Actions

Why do you need to check Operand.isDef() and modifiedRegister? Isn't isDef enough?

craig.topper: Why do you need to check `Operand.isDef()` and `modifiedRegister`? Isn't `isDef` enough?
}
}
craig.topperUnsubmitted
Done
ReplyInline Actions

Drop curly braces

craig.topper: Drop curly braces
}
if (isAddOrSubInstr(*MBBI) &&
(MBBI->getOperand(2).isImm() || MBBI->getOperand(2).isReg()) &&
MBBI->getOperand(0).getReg() == MBBI->getOperand(1).getReg()) {
// Ignore registers used for work with frames.
if (MBBI->getFlag(MachineInstr::FrameDestroy) ||
craig.topperUnsubmitted
Done
ReplyInline Actions

Do we have to assume there is only 1 def? Can we check isDef on the operand instead of checking 0?

craig.topper: Do we have to assume there is only 1 def? Can we check isDef on the operand instead of checking…
MBBI->getFlag(MachineInstr::FrameSetup)) {
IgnoredFrameRegisters.push_back(MBBI->getOperand(0).getReg());
continue;
}
if (is_contained(IgnoredFrameRegisters, MBBI->getOperand(0).getReg())) {
continue;
}
// Found an instruction that is possible to combine later. Add it as
// possible candidates.
Register DestRegister = MBBI->getOperand(0).getReg();
CandidatesToBeCombined[DestRegister] = &*MBBI;
DestinationRegistersToCheck.push_back(DestRegister);
// Save operand register to check it isn't modified.
if (MBBI->getOperand(2).isReg()) {
ModificationRegisterMonitor[MBBI->getOperand(2).getReg()].push_back(
std::make_pair(DestRegister, false));
}
}
}
return Modified;
}
craig.topperUnsubmitted
Done
ReplyInline Actions

Can this be llvm::is_contained?

craig.topper: Can this be llvm::is_contained?
bool RISCVAddSubCombiner::runOnMachineFunction(MachineFunction &MF) {
if (skipFunction(MF.getFunction()))
return false;
Subtarget = &MF.getSubtarget<RISCVSubtarget>();
TII = Subtarget->getInstrInfo();
bool Modified = false;
for (auto &MBB : MF) {
Modified |= optimizeBlock(MBB);
}
craig.topperUnsubmitted
Done
ReplyInline Actions

You don't need to manually construct an empty vector here. Calling operator[] on line 310 will default construct the vector if it doesn't already exist. Then the push_back will be called.

craig.topper: You don't need to manually construct an empty vector here. Calling operator[] on line 310 will…
return Modified;
}
/// createRISCVAddSubCombinerPass - returns an instance of the
/// add/sub combine pass.
FunctionPass *llvm::createRISCVAddSubCombinerPass() {
return new RISCVAddSubCombiner();
}
craig.topperUnsubmitted
Done
ReplyInline Actions

RISCVSubtarget::getInstrINfo returns a RISCVInstrInfo *. No need for static_cast

craig.topper: RISCVSubtarget::getInstrINfo returns a RISCVInstrInfo *. No need for static_cast