diff --git a/llvm/lib/CodeGen/PrologEpilogInserter.cpp b/llvm/lib/CodeGen/PrologEpilogInserter.cpp --- a/llvm/lib/CodeGen/PrologEpilogInserter.cpp +++ b/llvm/lib/CodeGen/PrologEpilogInserter.cpp @@ -134,8 +134,8 @@ bool replaceFrameIndexDebugInstr(MachineFunction &MF, MachineInstr &MI, unsigned OpIdx, int SPAdj = 0); // Does same as replaceFrameIndices but using the backward MIR walk and - // backward register scavenger walk. Does not yet support call sequence - // processing. + // backward register scavenger walk. + void replaceFrameIndicesBackward(MachineFunction &MF); void replaceFrameIndicesBackward(MachineBasicBlock *BB, MachineFunction &MF, int &SPAdj); @@ -272,8 +272,16 @@ // Replace all MO_FrameIndex operands with physical register references // and actual offsets. - // - replaceFrameIndices(MF); + if (TFI->needsFrameIndexResolution(MF)) { + // Allow the target to determine this after knowing the frame size. + FrameIndexEliminationScavenging = (RS && !FrameIndexVirtualScavenging) || + TRI->requiresFrameIndexReplacementScavenging(MF); + + if (TRI->supportsBackwardScavenger()) + replaceFrameIndicesBackward(MF); + else + replaceFrameIndices(MF); + } // If register scavenging is needed, as we've enabled doing it as a // post-pass, scavenge the virtual registers that frame index elimination @@ -1327,20 +1335,51 @@ TFI.emitZeroCallUsedRegs(RegsToZero, MBB); } -/// replaceFrameIndices - Replace all MO_FrameIndex operands with physical -/// register references and actual offsets. -void PEI::replaceFrameIndices(MachineFunction &MF) { - const auto &ST = MF.getSubtarget(); - const TargetFrameLowering &TFI = *ST.getFrameLowering(); - if (!TFI.needsFrameIndexResolution(MF)) - return; +/// Replace all FrameIndex operands with physical register references and actual +/// offsets. +void PEI::replaceFrameIndicesBackward(MachineFunction &MF) { + const TargetInstrInfo &TII = *MF.getSubtarget().getInstrInfo(); - const TargetRegisterInfo *TRI = ST.getRegisterInfo(); + // Store SPAdj at exit of a basic block. + SmallVector SPState; + SPState.resize(MF.getNumBlockIDs()); - // Allow the target to determine this after knowing the frame size. - FrameIndexEliminationScavenging = (RS && !FrameIndexVirtualScavenging) || - TRI->requiresFrameIndexReplacementScavenging(MF); + // Iterate over the reachable blocks in DFS order to find the SPAdj at the end + // of each block. + // TODO: this extra walk over the function is expensive and is only required + // if there are infinite loops in the CFG. In all other cases we could process + // the blocks in reverse order starting from the exit nodes. + for (auto DFI = df_begin(&MF), DFE = df_end(&MF); DFI != DFE; ++DFI) { + int SPAdj = 0; + // Check the exit state of the DFS stack predecessor. + if (DFI.getPathLength() >= 2) { + MachineBasicBlock *StackPred = DFI.getPath(DFI.getPathLength() - 2); + SPAdj = SPState[StackPred->getNumber()]; + } + MachineBasicBlock &BB = **DFI; + bool InsideCallSequence = false; + for (auto &MI : BB) { + if (MI.getOpcode() == TII.getCallFrameSetupOpcode()) + InsideCallSequence = true; + if (InsideCallSequence) + SPAdj += TII.getSPAdjust(MI); + if (MI.getOpcode() == TII.getCallFrameDestroyOpcode()) + InsideCallSequence = false; + } + SPState[BB.getNumber()] = SPAdj; + } + + // Iterate over all blocks. Reachable blocks will have had their SPAdj set + // above. For unreachable blocks we will use an arbitrary SPAdj of 0. + for (auto &BB : MF) { + int SPAdj = SPState[BB.getNumber()]; + replaceFrameIndicesBackward(&BB, MF, SPAdj); + } +} +/// replaceFrameIndices - Replace all MO_FrameIndex operands with physical +/// register references and actual offsets. +void PEI::replaceFrameIndices(MachineFunction &MF) { // Store SPAdj at exit of a basic block. SmallVector SPState; SPState.resize(MF.getNumBlockIDs()); @@ -1459,64 +1498,57 @@ assert(MF.getSubtarget().getRegisterInfo() && "getRegisterInfo() must be implemented!"); + const TargetInstrInfo &TII = *MF.getSubtarget().getInstrInfo(); const TargetRegisterInfo &TRI = *MF.getSubtarget().getRegisterInfo(); + const TargetFrameLowering &TFI = *MF.getSubtarget().getFrameLowering(); - RS->enterBasicBlockEnd(*BB); + RegScavenger *LocalRS = FrameIndexEliminationScavenging ? RS : nullptr; + if (LocalRS) + LocalRS->enterBasicBlockEnd(*BB); - for (MachineInstr &MI : make_early_inc_range(reverse(*BB))) { + bool InsideCallSequence = false; + for (MachineBasicBlock::iterator I = BB->end(); I != BB->begin(); ) { + MachineInstr &MI = *std::prev(I); - // Register scavenger backward step - MachineBasicBlock::iterator Step(MI); - for (unsigned i = 0; i != MI.getNumOperands(); ++i) { - if (!MI.getOperand(i).isFI()) - continue; + if (TII.isFrameInstr(MI)) { + InsideCallSequence = !TII.isFrameSetup(MI); + SPAdj -= TII.getSPAdjust(MI); + TFI.eliminateCallFramePseudoInstr(MF, *BB, &MI); + continue; + } - if (replaceFrameIndexDebugInstr(MF, MI, i, SPAdj)) + // If we are looking at a call sequence, we need to keep track of + // the SP adjustment made by each instruction in the sequence. + // This includes both the frame setup/destroy pseudos (handled above), + // as well as other instructions that have side effects w.r.t the SP. + if (InsideCallSequence) + SPAdj -= TII.getSPAdjust(MI); + + // Step backwards to get the liveness state at (immedately after) MI. + if (LocalRS) + LocalRS->backward(MI); + + bool Removed = false; + for (const auto &[Idx, Op] : enumerate(MI.operands())) { + if (!Op.isFI()) continue; - // If this instruction has a FrameIndex operand, we need to - // use that target machine register info object to eliminate - // it. + if (replaceFrameIndexDebugInstr(MF, MI, Idx, SPAdj)) + continue; - // TRI.eliminateFrameIndex may lower the frame index to a sequence of - // instructions. It also can remove/change instructions passed by the - // iterator and invalidate the iterator. We have to take care of this. For - // that we support two iterators: *Step* - points to the position up to - // which the scavenger should scan by the next iteration to have liveness - // information up to date. *Curr* - keeps track of the correct RS->MBBI - - // the scan start point. It points to the currently processed instruction - // right before the frame lowering. - // - // ITERATORS WORK AS FOLLOWS: - // *Step* is shifted one step back right before the frame lowering and - // one step forward right after it. No matter how many instructions were - // inserted, *Step* will be right after the position which is going to be - // processed in the next iteration, thus, in the correct position for the - // scavenger to go up to. - // *Curr* is shifted one step forward right before calling - // TRI.eliminateFrameIndex and one step backward after. Thus, we make sure - // it points right to the position that is the correct starting point for - // the scavenger to scan. - MachineBasicBlock::iterator Curr = ++RS->getCurrentPosition(); - - // Shift back - --Step; - - bool Removed = TRI.eliminateFrameIndex(MI, SPAdj, i, RS); - // Restore to unify logic with a shift back that happens in the end of - // the outer loop. - ++Step; - RS->skipTo(--Curr); + // Eliminate this FrameIndex operand. + Removed = TRI.eliminateFrameIndex(MI, SPAdj, Idx, LocalRS); if (Removed) break; } - // Shift it to make RS collect reg info up to the current instruction. - if (Step != BB->begin()) - Step--; + // Refresh the scavenger's internal iterator in case it was invalidated by + // MI being removed. + if (LocalRS) + LocalRS->skipTo(std::prev(I)); - // Update register states. - RS->backward(Step); + if (!Removed) + --I; } } @@ -1528,9 +1560,6 @@ const TargetRegisterInfo &TRI = *MF.getSubtarget().getRegisterInfo(); const TargetFrameLowering *TFI = MF.getSubtarget().getFrameLowering(); - if (RS && TRI.supportsBackwardScavenger()) - return replaceFrameIndicesBackward(BB, MF, SPAdj); - if (RS && FrameIndexEliminationScavenging) RS->enterBasicBlock(*BB); diff --git a/llvm/lib/Target/X86/X86InstrInfo.cpp b/llvm/lib/Target/X86/X86InstrInfo.cpp --- a/llvm/lib/Target/X86/X86InstrInfo.cpp +++ b/llvm/lib/Target/X86/X86InstrInfo.cpp @@ -408,23 +408,23 @@ } // To know whether a call adjusts the stack, we need information - // that is bound to the following ADJCALLSTACKUP pseudo. - // Look for the next ADJCALLSTACKUP that follows the call. + // that is bound to the preceding ADJCALLSTACKDOWN pseudo. + // Look for the next ADJCALLSTACKDOWN that precedes the call. if (MI.isCall()) { const MachineBasicBlock *MBB = MI.getParent(); - auto I = ++MachineBasicBlock::const_iterator(MI); - for (auto E = MBB->end(); I != E; ++I) { - if (I->getOpcode() == getCallFrameDestroyOpcode() || + auto I = MachineBasicBlock::const_iterator(MI); + for (auto E = MBB->begin(); I-- != E; ) { + if (I->getOpcode() == getCallFrameSetupOpcode() || I->isCall()) break; } - // If we could not find a frame destroy opcode, then it has already + // If we could not find a frame setup opcode, then it has already // been simplified, so we don't care. - if (I->getOpcode() != getCallFrameDestroyOpcode()) + if (I->getOpcode() != getCallFrameSetupOpcode()) return 0; - return -(I->getOperand(1).getImm()); + return I->getOperand(1).getImm(); } // Currently handle only PUSHes we can reasonably expect to see diff --git a/llvm/lib/Target/X86/X86RegisterInfo.h b/llvm/lib/Target/X86/X86RegisterInfo.h --- a/llvm/lib/Target/X86/X86RegisterInfo.h +++ b/llvm/lib/Target/X86/X86RegisterInfo.h @@ -143,6 +143,8 @@ int SPAdj, unsigned FIOperandNum, RegScavenger *RS = nullptr) const override; + bool supportsBackwardScavenger() const override { return true; } + /// findDeadCallerSavedReg - Return a caller-saved register that isn't live /// when it reaches the "return" instruction. We can then pop a stack object /// to this register without worry about clobbering it.