| //===- ARCOptAddrMode.cpp ---------------------------------------------===// |
| // |
| // 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 |
| // |
| //===----------------------------------------------------------------------===// |
| // |
| /// \file |
| /// This pass folds LD/ST + ADD pairs into Pre/Post-increment form of |
| /// load/store instructions. |
| //===----------------------------------------------------------------------===// |
| |
| #include "ARC.h" |
| #define GET_INSTRMAP_INFO |
| #include "ARCInstrInfo.h" |
| #include "ARCTargetMachine.h" |
| #include "llvm/CodeGen/MachineBasicBlock.h" |
| #include "llvm/CodeGen/MachineDominators.h" |
| #include "llvm/CodeGen/MachineFunctionPass.h" |
| #include "llvm/CodeGen/MachineInstr.h" |
| #include "llvm/CodeGen/MachineInstrBuilder.h" |
| #include "llvm/CodeGen/TargetRegisterInfo.h" |
| #include "llvm/IR/Function.h" |
| #include "llvm/InitializePasses.h" |
| #include "llvm/Support/CommandLine.h" |
| #include "llvm/Support/Debug.h" |
| #include "llvm/Support/raw_ostream.h" |
| |
| using namespace llvm; |
| |
| #define OPTADDRMODE_DESC "ARC load/store address mode" |
| #define OPTADDRMODE_NAME "arc-addr-mode" |
| #define DEBUG_TYPE "arc-addr-mode" |
| |
| namespace llvm { |
| |
| static cl::opt<unsigned> ArcKillAddrMode("arc-kill-addr-mode", cl::init(0), |
| cl::ReallyHidden, cl::ZeroOrMore); |
| |
| #define DUMP_BEFORE() ((ArcKillAddrMode & 0x0001) != 0) |
| #define DUMP_AFTER() ((ArcKillAddrMode & 0x0002) != 0) |
| #define VIEW_BEFORE() ((ArcKillAddrMode & 0x0004) != 0) |
| #define VIEW_AFTER() ((ArcKillAddrMode & 0x0008) != 0) |
| #define KILL_PASS() ((ArcKillAddrMode & 0x0010) != 0) |
| |
| FunctionPass *createARCOptAddrMode(); |
| void initializeARCOptAddrModePass(PassRegistry &); |
| } // end namespace llvm |
| |
| namespace { |
| class ARCOptAddrMode : public MachineFunctionPass { |
| public: |
| static char ID; |
| |
| ARCOptAddrMode() : MachineFunctionPass(ID) {} |
| |
| StringRef getPassName() const override { return OPTADDRMODE_DESC; } |
| |
| void getAnalysisUsage(AnalysisUsage &AU) const override { |
| AU.setPreservesCFG(); |
| MachineFunctionPass::getAnalysisUsage(AU); |
| AU.addRequired<MachineDominatorTree>(); |
| AU.addPreserved<MachineDominatorTree>(); |
| } |
| |
| bool runOnMachineFunction(MachineFunction &MF) override; |
| |
| private: |
| const ARCSubtarget *AST = nullptr; |
| const ARCInstrInfo *AII = nullptr; |
| MachineRegisterInfo *MRI = nullptr; |
| MachineDominatorTree *MDT = nullptr; |
| |
| // Tries to combine \p Ldst with increment of its base register to form |
| // single post-increment instruction. |
| MachineInstr *tryToCombine(MachineInstr &Ldst); |
| |
| // Returns true if result of \p Add is not used before \p Ldst |
| bool noUseOfAddBeforeLoadOrStore(const MachineInstr *Add, |
| const MachineInstr *Ldst); |
| |
| // Returns true if load/store instruction \p Ldst can be hoisted up to |
| // instruction \p To |
| bool canHoistLoadStoreTo(MachineInstr *Ldst, MachineInstr *To); |
| |
| // // Returns true if load/store instruction \p Ldst can be sunk down |
| // // to instruction \p To |
| // bool canSinkLoadStoreTo(MachineInstr *Ldst, MachineInstr *To); |
| |
| // Check if instructions \p Ldst and \p Add can be moved to become adjacent |
| // If they can return instruction which need not to move. |
| // If \p Uses is not null, fill it with instructions after \p Ldst which use |
| // \p Ldst's base register |
| MachineInstr *canJoinInstructions(MachineInstr *Ldst, MachineInstr *Add, |
| SmallVectorImpl<MachineInstr *> *Uses); |
| |
| // Returns true if all instruction in \p Uses array can be adjusted |
| // to accomodate increment of register \p BaseReg by \p Incr |
| bool canFixPastUses(const ArrayRef<MachineInstr *> &Uses, |
| MachineOperand &Incr, unsigned BaseReg); |
| |
| // Update all instructions in \p Uses to accomodate increment |
| // of \p BaseReg by \p Offset |
| void fixPastUses(ArrayRef<MachineInstr *> Uses, unsigned BaseReg, |
| int64_t Offset); |
| |
| // Change instruction \p Ldst to postincrement form. |
| // \p NewBase is register to hold update base value |
| // \p NewOffset is instruction's new offset |
| void changeToAddrMode(MachineInstr &Ldst, unsigned NewOpcode, |
| unsigned NewBase, MachineOperand &NewOffset); |
| |
| bool processBasicBlock(MachineBasicBlock &MBB); |
| }; |
| |
| } // end anonymous namespace |
| |
| char ARCOptAddrMode::ID = 0; |
| INITIALIZE_PASS_BEGIN(ARCOptAddrMode, OPTADDRMODE_NAME, OPTADDRMODE_DESC, false, |
| false) |
| INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree) |
| INITIALIZE_PASS_END(ARCOptAddrMode, OPTADDRMODE_NAME, OPTADDRMODE_DESC, false, |
| false) |
| |
| // Return true if \p Off can be used as immediate offset |
| // operand of load/store instruction (S9 literal) |
| static bool isValidLoadStoreOffset(int64_t Off) { return isInt<9>(Off); } |
| |
| // Return true if \p Off can be used as immediate operand of |
| // ADD/SUB instruction (U6 literal) |
| static bool isValidIncrementOffset(int64_t Off) { return isUInt<6>(Off); } |
| |
| static bool isAddConstantOp(const MachineInstr &MI, int64_t &Amount) { |
| int64_t Sign = 1; |
| switch (MI.getOpcode()) { |
| case ARC::SUB_rru6: |
| Sign = -1; |
| LLVM_FALLTHROUGH; |
| case ARC::ADD_rru6: |
| assert(MI.getOperand(2).isImm() && "Expected immediate operand"); |
| Amount = Sign * MI.getOperand(2).getImm(); |
| return true; |
| default: |
| return false; |
| } |
| } |
| |
| // Return true if \p MI dominates of uses of virtual register \p VReg |
| static bool dominatesAllUsesOf(const MachineInstr *MI, unsigned VReg, |
| MachineDominatorTree *MDT, |
| MachineRegisterInfo *MRI) { |
| |
| assert(Register::isVirtualRegister(VReg) && "Expected virtual register!"); |
| |
| for (auto it = MRI->use_nodbg_begin(VReg), end = MRI->use_nodbg_end(); |
| it != end; ++it) { |
| MachineInstr *User = it->getParent(); |
| if (User->isPHI()) { |
| unsigned BBOperandIdx = User->getOperandNo(&*it) + 1; |
| MachineBasicBlock *MBB = User->getOperand(BBOperandIdx).getMBB(); |
| if (MBB->empty()) { |
| const MachineBasicBlock *InstBB = MI->getParent(); |
| assert(InstBB != MBB && "Instruction found in empty MBB"); |
| if (!MDT->dominates(InstBB, MBB)) |
| return false; |
| continue; |
| } |
| User = &*MBB->rbegin(); |
| } |
| |
| if (!MDT->dominates(MI, User)) |
| return false; |
| } |
| return true; |
| } |
| |
| // Return true if \p MI is load/store instruction with immediate offset |
| // which can be adjusted by \p Disp |
| static bool isLoadStoreThatCanHandleDisplacement(const TargetInstrInfo *TII, |
| const MachineInstr &MI, |
| int64_t Disp) { |
| unsigned BasePos, OffPos; |
| if (!TII->getBaseAndOffsetPosition(MI, BasePos, OffPos)) |
| return false; |
| const MachineOperand &MO = MI.getOperand(OffPos); |
| if (!MO.isImm()) |
| return false; |
| int64_t Offset = MO.getImm() + Disp; |
| return isValidLoadStoreOffset(Offset); |
| } |
| |
| bool ARCOptAddrMode::noUseOfAddBeforeLoadOrStore(const MachineInstr *Add, |
| const MachineInstr *Ldst) { |
| Register R = Add->getOperand(0).getReg(); |
| return dominatesAllUsesOf(Ldst, R, MDT, MRI); |
| } |
| |
| MachineInstr *ARCOptAddrMode::tryToCombine(MachineInstr &Ldst) { |
| assert(Ldst.mayLoadOrStore() && "LD/ST instruction expected"); |
| |
| unsigned BasePos, OffsetPos; |
| |
| LLVM_DEBUG(dbgs() << "[ABAW] tryToCombine " << Ldst); |
| if (!AII->getBaseAndOffsetPosition(Ldst, BasePos, OffsetPos)) { |
| LLVM_DEBUG(dbgs() << "[ABAW] Not a recognized load/store\n"); |
| return nullptr; |
| } |
| |
| MachineOperand &Base = Ldst.getOperand(BasePos); |
| MachineOperand &Offset = Ldst.getOperand(OffsetPos); |
| |
| assert(Base.isReg() && "Base operand must be register"); |
| if (!Offset.isImm()) { |
| LLVM_DEBUG(dbgs() << "[ABAW] Offset is not immediate\n"); |
| return nullptr; |
| } |
| |
| Register B = Base.getReg(); |
| if (Register::isStackSlot(B) || !Register::isVirtualRegister(B)) { |
| LLVM_DEBUG(dbgs() << "[ABAW] Base is not VReg\n"); |
| return nullptr; |
| } |
| |
| // TODO: try to generate address preincrement |
| if (Offset.getImm() != 0) { |
| LLVM_DEBUG(dbgs() << "[ABAW] Non-zero offset\n"); |
| return nullptr; |
| } |
| |
| for (auto &Add : MRI->use_nodbg_instructions(B)) { |
| int64_t Incr; |
| if (!isAddConstantOp(Add, Incr)) |
| continue; |
| if (!isValidLoadStoreOffset(Incr)) |
| continue; |
| |
| SmallVector<MachineInstr *, 8> Uses; |
| MachineInstr *MoveTo = canJoinInstructions(&Ldst, &Add, &Uses); |
| |
| if (!MoveTo) |
| continue; |
| |
| if (!canFixPastUses(Uses, Add.getOperand(2), B)) |
| continue; |
| |
| LLVM_DEBUG(MachineInstr *First = &Ldst; MachineInstr *Last = &Add; |
| if (MDT->dominates(Last, First)) std::swap(First, Last); |
| dbgs() << "[ABAW] Instructions " << *First << " and " << *Last |
| << " combined\n"; |
| |
| ); |
| |
| MachineInstr *Result = Ldst.getNextNode(); |
| if (MoveTo == &Add) { |
| Ldst.removeFromParent(); |
| Add.getParent()->insertAfter(Add.getIterator(), &Ldst); |
| } |
| if (Result == &Add) |
| Result = Result->getNextNode(); |
| |
| fixPastUses(Uses, B, Incr); |
| |
| int NewOpcode = ARC::getPostIncOpcode(Ldst.getOpcode()); |
| assert(NewOpcode > 0 && "No postincrement form found"); |
| unsigned NewBaseReg = Add.getOperand(0).getReg(); |
| changeToAddrMode(Ldst, NewOpcode, NewBaseReg, Add.getOperand(2)); |
| Add.eraseFromParent(); |
| |
| return Result; |
| } |
| return nullptr; |
| } |
| |
| MachineInstr * |
| ARCOptAddrMode::canJoinInstructions(MachineInstr *Ldst, MachineInstr *Add, |
| SmallVectorImpl<MachineInstr *> *Uses) { |
| assert(Ldst && Add && "NULL instruction passed"); |
| |
| MachineInstr *First = Add; |
| MachineInstr *Last = Ldst; |
| if (MDT->dominates(Ldst, Add)) |
| std::swap(First, Last); |
| else if (!MDT->dominates(Add, Ldst)) |
| return nullptr; |
| |
| LLVM_DEBUG(dbgs() << "canJoinInstructions: " << *First << *Last); |
| |
| unsigned BasePos, OffPos; |
| |
| if (!AII->getBaseAndOffsetPosition(*Ldst, BasePos, OffPos)) { |
| LLVM_DEBUG( |
| dbgs() |
| << "[canJoinInstructions] Cannot determine base/offset position\n"); |
| return nullptr; |
| } |
| |
| Register BaseReg = Ldst->getOperand(BasePos).getReg(); |
| |
| // prohibit this: |
| // v1 = add v0, c |
| // st v1, [v0, 0] |
| // and this |
| // st v0, [v0, 0] |
| // v1 = add v0, c |
| if (Ldst->mayStore() && Ldst->getOperand(0).isReg()) { |
| Register StReg = Ldst->getOperand(0).getReg(); |
| if (Add->getOperand(0).getReg() == StReg || BaseReg == StReg) { |
| LLVM_DEBUG(dbgs() << "[canJoinInstructions] Store uses result of Add\n"); |
| return nullptr; |
| } |
| } |
| |
| SmallVector<MachineInstr *, 4> UsesAfterLdst; |
| SmallVector<MachineInstr *, 4> UsesAfterAdd; |
| for (MachineInstr &MI : MRI->use_nodbg_instructions(BaseReg)) { |
| if (&MI == Ldst || &MI == Add) |
| continue; |
| if (&MI != Add && MDT->dominates(Ldst, &MI)) |
| UsesAfterLdst.push_back(&MI); |
| else if (!MDT->dominates(&MI, Ldst)) |
| return nullptr; |
| if (MDT->dominates(Add, &MI)) |
| UsesAfterAdd.push_back(&MI); |
| } |
| |
| MachineInstr *Result = nullptr; |
| |
| if (First == Add) { |
| // n = add b, i |
| // ... |
| // x = ld [b, o] or x = ld [n, o] |
| |
| if (noUseOfAddBeforeLoadOrStore(First, Last)) { |
| Result = Last; |
| LLVM_DEBUG(dbgs() << "[canJoinInstructions] Can sink Add down to Ldst\n"); |
| } else if (canHoistLoadStoreTo(Ldst, Add)) { |
| Result = First; |
| LLVM_DEBUG(dbgs() << "[canJoinInstructions] Can hoist Ldst to Add\n"); |
| } |
| } else { |
| // x = ld [b, o] |
| // ... |
| // n = add b, i |
| Result = First; |
| LLVM_DEBUG(dbgs() << "[canJoinInstructions] Can hoist Add to Ldst\n"); |
| } |
| if (Result && Uses) |
| *Uses = (Result == Ldst) ? UsesAfterLdst : UsesAfterAdd; |
| return Result; |
| } |
| |
| bool ARCOptAddrMode::canFixPastUses(const ArrayRef<MachineInstr *> &Uses, |
| MachineOperand &Incr, unsigned BaseReg) { |
| |
| assert(Incr.isImm() && "Expected immediate increment"); |
| int64_t NewOffset = Incr.getImm(); |
| for (MachineInstr *MI : Uses) { |
| int64_t Dummy; |
| if (isAddConstantOp(*MI, Dummy)) { |
| if (isValidIncrementOffset(Dummy + NewOffset)) |
| continue; |
| return false; |
| } |
| if (isLoadStoreThatCanHandleDisplacement(AII, *MI, -NewOffset)) |
| continue; |
| LLVM_DEBUG(dbgs() << "Instruction cannot handle displacement " << -NewOffset |
| << ": " << *MI); |
| return false; |
| } |
| return true; |
| } |
| |
| void ARCOptAddrMode::fixPastUses(ArrayRef<MachineInstr *> Uses, |
| unsigned NewBase, int64_t NewOffset) { |
| |
| for (MachineInstr *MI : Uses) { |
| int64_t Amount; |
| unsigned BasePos, OffPos; |
| if (isAddConstantOp(*MI, Amount)) { |
| NewOffset += Amount; |
| assert(isValidIncrementOffset(NewOffset) && |
| "New offset won't fit into ADD instr"); |
| BasePos = 1; |
| OffPos = 2; |
| } else if (AII->getBaseAndOffsetPosition(*MI, BasePos, OffPos)) { |
| MachineOperand &MO = MI->getOperand(OffPos); |
| assert(MO.isImm() && "expected immediate operand"); |
| NewOffset += MO.getImm(); |
| assert(isValidLoadStoreOffset(NewOffset) && |
| "New offset won't fit into LD/ST"); |
| } else |
| llvm_unreachable("unexpected instruction"); |
| |
| MI->getOperand(BasePos).setReg(NewBase); |
| MI->getOperand(OffPos).setImm(NewOffset); |
| } |
| } |
| |
| bool ARCOptAddrMode::canHoistLoadStoreTo(MachineInstr *Ldst, MachineInstr *To) { |
| if (Ldst->getParent() != To->getParent()) |
| return false; |
| MachineBasicBlock::const_iterator MI(To), ME(Ldst), |
| End(Ldst->getParent()->end()); |
| |
| bool IsStore = Ldst->mayStore(); |
| for (; MI != ME && MI != End; ++MI) { |
| if (MI->isDebugValue()) |
| continue; |
| if (MI->mayStore() || MI->isCall() || MI->isInlineAsm() || |
| MI->hasUnmodeledSideEffects()) |
| return false; |
| if (IsStore && MI->mayLoad()) |
| return false; |
| } |
| |
| for (auto &O : Ldst->explicit_operands()) { |
| if (!O.isReg() || !O.isUse()) |
| continue; |
| MachineInstr *OpDef = MRI->getVRegDef(O.getReg()); |
| if (!OpDef || !MDT->dominates(OpDef, To)) |
| return false; |
| } |
| return true; |
| } |
| |
| // bool ARCOptAddrMode::canSinkLoadStoreTo(MachineInstr *Ldst, MachineInstr *To) { |
| // // Can only sink load/store within same BB |
| // if (Ldst->getParent() != To->getParent()) |
| // return false; |
| // MachineBasicBlock::const_iterator MI(Ldst), ME(To), |
| // End(Ldst->getParent()->end()); |
| |
| // bool IsStore = Ldst->mayStore(); |
| // bool IsLoad = Ldst->mayLoad(); |
| |
| // Register ValReg = IsLoad ? Ldst->getOperand(0).getReg() : Register(); |
| // for (; MI != ME && MI != End; ++MI) { |
| // if (MI->isDebugValue()) |
| // continue; |
| // if (MI->mayStore() || MI->isCall() || MI->isInlineAsm() || |
| // MI->hasUnmodeledSideEffects()) |
| // return false; |
| // if (IsStore && MI->mayLoad()) |
| // return false; |
| // if (ValReg && MI->readsVirtualRegister(ValReg)) |
| // return false; |
| // } |
| // return true; |
| // } |
| |
| void ARCOptAddrMode::changeToAddrMode(MachineInstr &Ldst, unsigned NewOpcode, |
| unsigned NewBase, |
| MachineOperand &NewOffset) { |
| bool IsStore = Ldst.mayStore(); |
| unsigned BasePos, OffPos; |
| MachineOperand Src = MachineOperand::CreateImm(0xDEADBEEF); |
| AII->getBaseAndOffsetPosition(Ldst, BasePos, OffPos); |
| |
| Register BaseReg = Ldst.getOperand(BasePos).getReg(); |
| |
| Ldst.RemoveOperand(OffPos); |
| Ldst.RemoveOperand(BasePos); |
| |
| if (IsStore) { |
| Src = Ldst.getOperand(BasePos - 1); |
| Ldst.RemoveOperand(BasePos - 1); |
| } |
| |
| Ldst.setDesc(AST->getInstrInfo()->get(NewOpcode)); |
| Ldst.addOperand(MachineOperand::CreateReg(NewBase, true)); |
| if (IsStore) |
| Ldst.addOperand(Src); |
| Ldst.addOperand(MachineOperand::CreateReg(BaseReg, false)); |
| Ldst.addOperand(NewOffset); |
| LLVM_DEBUG(dbgs() << "[ABAW] New Ldst: " << Ldst); |
| } |
| |
| bool ARCOptAddrMode::processBasicBlock(MachineBasicBlock &MBB) { |
| bool Changed = false; |
| for (auto MI = MBB.begin(), ME = MBB.end(); MI != ME; ++MI) { |
| if (MI->isDebugValue()) |
| continue; |
| if (!MI->mayLoad() && !MI->mayStore()) |
| continue; |
| if (ARC::getPostIncOpcode(MI->getOpcode()) < 0) |
| continue; |
| MachineInstr *Res = tryToCombine(*MI); |
| if (Res) { |
| Changed = true; |
| // Res points to the next instruction. Rewind to process it |
| MI = std::prev(Res->getIterator()); |
| } |
| } |
| return Changed; |
| } |
| |
| bool ARCOptAddrMode::runOnMachineFunction(MachineFunction &MF) { |
| if (skipFunction(MF.getFunction()) || KILL_PASS()) |
| return false; |
| |
| #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) |
| if (DUMP_BEFORE()) |
| MF.dump(); |
| #endif |
| if (VIEW_BEFORE()) |
| MF.viewCFG(); |
| |
| AST = &MF.getSubtarget<ARCSubtarget>(); |
| AII = AST->getInstrInfo(); |
| MRI = &MF.getRegInfo(); |
| MDT = &getAnalysis<MachineDominatorTree>(); |
| |
| bool Changed = false; |
| for (auto &MBB : MF) |
| Changed |= processBasicBlock(MBB); |
| |
| #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) |
| if (DUMP_AFTER()) |
| MF.dump(); |
| #endif |
| if (VIEW_AFTER()) |
| MF.viewCFG(); |
| return Changed; |
| } |
| |
| //===----------------------------------------------------------------------===// |
| // Public Constructor Functions |
| //===----------------------------------------------------------------------===// |
| |
| FunctionPass *llvm::createARCOptAddrMode() { return new ARCOptAddrMode(); } |