MachineBasicBlock::iterator i)
: Offset(o), Reg(r), isKill(k), Position(p), MBBI(i), Merged(false) {}
};
- class UnitRegsMap {
- public:
- UnitRegsMap(const TargetRegisterInfo* _TRI) : TRI(_TRI) {}
- const SmallVector<unsigned, 4>& operator[](unsigned Reg) {
- DenseMap<unsigned, SmallVector<unsigned, 4> >::iterator found =
- Cache.find(Reg);
- if (found != Cache.end())
- return found->second;
- else
- return Cache.insert(std::make_pair(Reg, this->getUnitRegs(Reg)))
- .first->second;
- }
- private:
- SmallVector<unsigned, 4> getUnitRegs(unsigned Reg) {
- SmallVector<unsigned, 4> Res;
-
- const TargetRegisterClass* TRC = TRI->getMinimalPhysRegClass(Reg);
- if (TRC == &ARM::QPRRegClass) {
- if (Reg > ARM::Q7) {
- Res.push_back(TRI->getSubReg(Reg, ARM::dsub_0));
- Res.push_back(TRI->getSubReg(Reg, ARM::dsub_1));
- return Res;
- }
-
- Res.push_back(TRI->getSubReg(Reg, ARM::ssub_0));
- Res.push_back(TRI->getSubReg(Reg, ARM::ssub_1));
- Res.push_back(TRI->getSubReg(Reg, ARM::ssub_2));
- Res.push_back(TRI->getSubReg(Reg, ARM::ssub_3));
-
- return Res;
- }
-
- if (TRC == &ARM::DPRRegClass && Reg < ARM::D15) {
- Res.push_back(TRI->getSubReg(Reg, ARM::ssub_0));
- Res.push_back(TRI->getSubReg(Reg, ARM::ssub_1));
-
- return Res;
- }
-
- Res.push_back(Reg);
-
- return Res;
-
- }
- const TargetRegisterInfo* TRI;
- DenseMap<unsigned, SmallVector<unsigned, 4> > Cache;
- };
typedef SmallVector<MemOpQueueEntry,8> MemOpQueue;
typedef MemOpQueue::iterator MemOpQueueIter;
+ void findUsesOfImpDef(SmallVectorImpl<MachineOperand *> &UsesOfImpDefs,
+ const MemOpQueue &MemOps, unsigned DefReg,
+ unsigned RangeBegin, unsigned RangeEnd);
+
bool MergeOps(MachineBasicBlock &MBB, MachineBasicBlock::iterator MBBI,
int Offset, unsigned Base, bool BaseKill, int Opcode,
ARMCC::CondCodes Pred, unsigned PredReg, unsigned Scratch,
unsigned PredReg,
unsigned Scratch,
DebugLoc dl,
- SmallVector<MachineBasicBlock::iterator, 4> &Merges);
+ SmallVectorImpl<MachineBasicBlock::iterator> &Merges);
void MergeLDR_STR(MachineBasicBlock &MBB, unsigned SIndex, unsigned Base,
int Opcode, unsigned Size,
ARMCC::CondCodes Pred, unsigned PredReg,
unsigned Scratch, MemOpQueue &MemOps,
- SmallVector<MachineBasicBlock::iterator, 4> &Merges);
+ SmallVectorImpl<MachineBasicBlock::iterator> &Merges);
void AdvanceRS(MachineBasicBlock &MBB, MemOpQueue &MemOps);
bool FixInvalidRegPairOp(MachineBasicBlock &MBB,
MachineBasicBlock::iterator MBBI,
bool &Advance,
MachineBasicBlock::iterator &I);
- unsigned AddMemOp(MemOpQueue& MemOps,
- const MemOpQueueEntry newEntry,
- UnitRegsMap& UnitRegsInfo,
- SmallSet<unsigned, 4>& UsedUnitRegs,
- unsigned At = -1U);
bool LoadStoreMultipleOpti(MachineBasicBlock &MBB);
bool MergeReturnIntoLDM(MachineBasicBlock &MBB);
};
return true;
}
+/// \brief Find all instructions using a given imp-def within a range.
+///
+/// We are trying to combine a range of instructions, one of which (located at
+/// position RangeBegin) implicitly defines a register. The final LDM/STM will
+/// be placed at RangeEnd, and so any uses of this definition between RangeStart
+/// and RangeEnd must be modified to use an undefined value.
+///
+/// The live range continues until we find a second definition or one of the
+/// uses we find is a kill. Unfortunately MemOps is not sorted by Position, so
+/// we must consider all uses and decide which are relevant in a second pass.
+void ARMLoadStoreOpt::findUsesOfImpDef(
+ SmallVectorImpl<MachineOperand *> &UsesOfImpDefs, const MemOpQueue &MemOps,
+ unsigned DefReg, unsigned RangeBegin, unsigned RangeEnd) {
+ std::map<unsigned, MachineOperand *> Uses;
+ unsigned LastLivePos = RangeEnd;
+
+ // First we find all uses of this register with Position between RangeBegin
+ // and RangeEnd, any or all of these could be uses of a definition at
+ // RangeBegin. We also record the latest position a definition at RangeBegin
+ // would be considered live.
+ for (unsigned i = 0; i < MemOps.size(); ++i) {
+ MachineInstr &MI = *MemOps[i].MBBI;
+ unsigned MIPosition = MemOps[i].Position;
+ if (MIPosition <= RangeBegin || MIPosition > RangeEnd)
+ continue;
+
+ // If this instruction defines the register, then any later use will be of
+ // that definition rather than ours.
+ if (MI.definesRegister(DefReg))
+ LastLivePos = std::min(LastLivePos, MIPosition);
+
+ MachineOperand *UseOp = MI.findRegisterUseOperand(DefReg);
+ if (!UseOp)
+ continue;
+
+ // If this instruction kills the register then (assuming liveness is
+ // correct when we start) we don't need to think about anything after here.
+ if (UseOp->isKill())
+ LastLivePos = std::min(LastLivePos, MIPosition);
+
+ Uses[MIPosition] = UseOp;
+ }
+
+ // Now we traverse the list of all uses, and append the ones that actually use
+ // our definition to the requested list.
+ for (std::map<unsigned, MachineOperand *>::iterator I = Uses.begin(),
+ E = Uses.end();
+ I != E; ++I) {
+ // List is sorted by position so once we've found one out of range there
+ // will be no more to consider.
+ if (I->first > LastLivePos)
+ break;
+ UsesOfImpDefs.push_back(I->second);
+ }
+}
+
// MergeOpsUpdate - call MergeOps and update MemOps and merges accordingly on
// success.
void ARMLoadStoreOpt::MergeOpsUpdate(MachineBasicBlock &MBB,
ARMCC::CondCodes Pred, unsigned PredReg,
unsigned Scratch,
DebugLoc dl,
- SmallVector<MachineBasicBlock::iterator, 4> &Merges) {
+ SmallVectorImpl<MachineBasicBlock::iterator> &Merges) {
// First calculate which of the registers should be killed by the merged
// instruction.
const unsigned insertPos = memOps[insertAfter].Position;
SmallVector<std::pair<unsigned, bool>, 8> Regs;
SmallVector<unsigned, 8> ImpDefs;
+ SmallVector<MachineOperand *, 8> UsesOfImpDefs;
for (unsigned i = memOpsBegin; i < memOpsEnd; ++i) {
unsigned Reg = memOps[i].Reg;
// If we are inserting the merged operation after an operation that
unsigned DefReg = MO->getReg();
if (std::find(ImpDefs.begin(), ImpDefs.end(), DefReg) == ImpDefs.end())
ImpDefs.push_back(DefReg);
+
+ // There may be other uses of the definition between this instruction and
+ // the eventual LDM/STM position. These should be marked undef if the
+ // merge takes place.
+ findUsesOfImpDef(UsesOfImpDefs, memOps, DefReg, memOps[i].Position,
+ insertPos);
}
}
// Merge succeeded, update records.
Merges.push_back(prior(Loc));
+
+ // In gathering loads together, we may have moved the imp-def of a register
+ // past one of its uses. This is OK, since we know better than the rest of
+ // LLVM what's OK with ARM loads and stores; but we still have to adjust the
+ // affected uses.
+ for (SmallVectorImpl<MachineOperand *>::iterator I = UsesOfImpDefs.begin(),
+ E = UsesOfImpDefs.end();
+ I != E; ++I)
+ (*I)->setIsUndef();
+
for (unsigned i = memOpsBegin; i < memOpsEnd; ++i) {
// Remove kill flags from any memops that come before insertPos.
if (Regs[i-memOpsBegin].second) {
/// load / store multiple instructions.
void
ARMLoadStoreOpt::MergeLDR_STR(MachineBasicBlock &MBB, unsigned SIndex,
- unsigned Base, int Opcode, unsigned Size,
- ARMCC::CondCodes Pred, unsigned PredReg,
- unsigned Scratch, MemOpQueue &MemOps,
- SmallVector<MachineBasicBlock::iterator, 4> &Merges) {
+ unsigned Base, int Opcode, unsigned Size,
+ ARMCC::CondCodes Pred, unsigned PredReg,
+ unsigned Scratch, MemOpQueue &MemOps,
+ SmallVectorImpl<MachineBasicBlock::iterator> &Merges) {
bool isNotVFP = isi32Load(Opcode) || isi32Store(Opcode);
int Offset = MemOps[SIndex].Offset;
int SOffset = Offset;
if (Reg != ARM::SP &&
NewOffset == Offset + (int)Size &&
((isNotVFP && RegNum > PRegNum) ||
- ((Count < Limit) && RegNum == PRegNum+1))) {
+ ((Count < Limit) && RegNum == PRegNum+1)) &&
+ // On Swift we don't want vldm/vstm to start with a odd register num
+ // because Q register unaligned vldm/vstm need more uops.
+ (!STI->isSwift() || isNotVFP || Count != 1 || !(PRegNum & 0x1))) {
Offset += Size;
PRegNum = RegNum;
++Count;
return false;
}
-/// AddMemOp - helper for ARMLoadStoreOpt::LoadStoreMultipleOpti.
-/// It adds store mem ops with simple push_back/insert method,
-/// without any additional logic.
-/// For load operation it does the next:
-/// 1. Adds new load operation into MemOp collection at "At" position.
-/// 2. Removes any "load" operations from MemOps, that changes "Reg" register
-/// contents, prior to "At".
-/// UnitRegsInfo - Map of type Map< Register, UnitRegisters-vector >
-/// UsedUnitRegs - set of unit-registers currently in use.
-/// At - position at which it would added, and prior which the clean-up
-/// should be made (for load operation).
-/// FIXME: The clean-up also should be made for store operations,
-/// but the memory address should be analyzed instead of unit registers.
-unsigned ARMLoadStoreOpt::AddMemOp(MemOpQueue& MemOps,
- const MemOpQueueEntry NewEntry,
- UnitRegsMap& UnitRegsInfo,
- SmallSet<unsigned, 4>& UsedUnitRegs,
- unsigned At) {
- unsigned Cleaned = 0;
-
- if (At == -1U) {
- At = MemOps.size();
- MemOps.push_back(NewEntry);
- } else
- MemOps.insert(&MemOps[At], NewEntry);
-
- // FIXME:
- // If operation is not load, leave it as is by now,
- // So 0 overridden ops would cleaned in this case.
- if (!NewEntry.MBBI->mayLoad())
- return 0;
-
- const SmallVector<unsigned, 4>& NewEntryUnitRegs = UnitRegsInfo[NewEntry.Reg];
-
- bool FoundOverriddenLoads = false;
-
- for (unsigned i = 0, e = NewEntryUnitRegs.size(); i != e; ++i)
- if (UsedUnitRegs.count(NewEntryUnitRegs[i])) {
- FoundOverriddenLoads = true;
- break;
- }
-
- // If we detect that this register is used by load operations that are
- // predecessors for the new one, remove them from MemOps then.
- if (FoundOverriddenLoads) {
- MemOpQueue UpdatedMemOps;
-
- // Scan through MemOps entries.
- for (unsigned i = 0; i != At; ++i) {
- MemOpQueueEntry& MemOpEntry = MemOps[i];
-
- // FIXME: Skip non-load operations by now.
- if (!MemOpEntry.MBBI->mayLoad())
- continue;
-
- const SmallVector<unsigned, 4>& MemOpUnitRegs =
- UnitRegsInfo[MemOpEntry.Reg];
-
- // Lookup entry that loads contents into register used by new entry.
- bool ReleaseThisEntry = false;
- for (unsigned m = 0, em = MemOpUnitRegs.size(); m != em; ++m) {
- if (std::find(NewEntryUnitRegs.begin(), NewEntryUnitRegs.end(),
- MemOpUnitRegs[m]) != NewEntryUnitRegs.end()) {
- ReleaseThisEntry = true;
- ++Cleaned;
- break;
- }
- }
-
- if (ReleaseThisEntry) {
- const SmallVector<unsigned, 4>& RelesedRegs = UnitRegsInfo[MemOpEntry.Reg];
- for (unsigned r = 0, er = RelesedRegs.size(); r != er; ++r)
- UsedUnitRegs.erase(RelesedRegs[r]);
- } else
- UpdatedMemOps.push_back(MemOpEntry);
- }
-
- // Keep anything without changes after At position.
- for (unsigned i = At, e = MemOps.size(); i != e; ++i)
- UpdatedMemOps.push_back(MemOps[i]);
-
- MemOps.swap(UpdatedMemOps);
- }
-
- UsedUnitRegs.insert(NewEntryUnitRegs.begin(), NewEntryUnitRegs.end());
-
- return Cleaned;
-}
-
/// LoadStoreMultipleOpti - An optimization pass to turn multiple LDR / STR
/// ops of the same base and incrementing offset into LDM / STM ops.
bool ARMLoadStoreOpt::LoadStoreMultipleOpti(MachineBasicBlock &MBB) {
unsigned NumMerges = 0;
unsigned NumMemOps = 0;
MemOpQueue MemOps;
- UnitRegsMap UnitRegsInfo(TRI);
- SmallSet<unsigned, 4> UsedRegUnits;
unsigned CurrBase = 0;
int CurrOpc = -1;
unsigned CurrSize = 0;
// merge the ldr's so far, including this one. But don't try to
// combine the following ldr(s).
Clobber = (isi32Load(Opcode) && Base == MBBI->getOperand(0).getReg());
+
+ // Watch out for:
+ // r4 := ldr [r0, #8]
+ // r4 := ldr [r0, #4]
+ //
+ // The optimization may reorder the second ldr in front of the first
+ // ldr, which violates write after write(WAW) dependence. The same as
+ // str. Try to merge inst(s) already in MemOps.
+ bool Overlap = false;
+ for (MemOpQueueIter I = MemOps.begin(), E = MemOps.end(); I != E; ++I) {
+ if (TRI->regsOverlap(Reg, I->MBBI->getOperand(0).getReg())) {
+ Overlap = true;
+ break;
+ }
+ }
+
if (CurrBase == 0 && !Clobber) {
// Start of a new chain.
CurrBase = Base;
CurrSize = Size;
CurrPred = Pred;
CurrPredReg = PredReg;
-
MemOps.push_back(MemOpQueueEntry(Offset, Reg, isKill, Position, MBBI));
++NumMemOps;
- const SmallVector<unsigned, 4>& EntryUnitRegs = UnitRegsInfo[Reg];
- UsedRegUnits.insert(EntryUnitRegs.begin(), EntryUnitRegs.end());
Advance = true;
- } else {
+ } else if (!Overlap) {
if (Clobber) {
TryMerge = true;
Advance = true;
// No need to match PredReg.
// Continue adding to the queue.
if (Offset > MemOps.back().Offset) {
- unsigned OverridesCleaned =
- AddMemOp(MemOps,
- MemOpQueueEntry(Offset, Reg, isKill, Position, MBBI),
- UnitRegsInfo, UsedRegUnits) != 0;
- NumMemOps += 1 - OverridesCleaned;
+ MemOps.push_back(MemOpQueueEntry(Offset, Reg, isKill,
+ Position, MBBI));
+ ++NumMemOps;
Advance = true;
} else {
- for (unsigned I = 0; I != NumMemOps; ++I) {
- if (Offset < MemOps[I].Offset) {
- MemOpQueueEntry entry(Offset, Reg, isKill, Position, MBBI);
- unsigned OverridesCleaned =
- AddMemOp(MemOps, entry, UnitRegsInfo,
- UsedRegUnits, I) != 0;
- NumMemOps += 1 - OverridesCleaned;
-
+ for (MemOpQueueIter I = MemOps.begin(), E = MemOps.end();
+ I != E; ++I) {
+ if (Offset < I->Offset) {
+ MemOps.insert(I, MemOpQueueEntry(Offset, Reg, isKill,
+ Position, MBBI));
+ ++NumMemOps;
Advance = true;
break;
- } else if (Offset == MemOps[I].Offset) {
+ } else if (Offset == I->Offset) {
// Collision! This can't be merged!
break;
}
CurrPredReg = 0;
if (NumMemOps) {
MemOps.clear();
- UsedRegUnits.clear();
NumMemOps = 0;
}
unsigned &PredReg, ARMCC::CondCodes &Pred,
bool &isT2);
bool RescheduleOps(MachineBasicBlock *MBB,
- SmallVector<MachineInstr*, 4> &Ops,
+ SmallVectorImpl<MachineInstr *> &Ops,
unsigned Base, bool isLd,
DenseMap<MachineInstr*, unsigned> &MI2LocMap);
bool RescheduleLoadStoreInstrs(MachineBasicBlock *MBB);
return false;
// Make sure the base address satisfies i64 ld / st alignment requirement.
+ // At the moment, we ignore the memoryoperand's value.
+ // If we want to use AliasAnalysis, we should check it accordingly.
if (!Op0->hasOneMemOperand() ||
- !(*Op0->memoperands_begin())->getValue() ||
(*Op0->memoperands_begin())->isVolatile())
return false;
}
bool ARMPreAllocLoadStoreOpt::RescheduleOps(MachineBasicBlock *MBB,
- SmallVector<MachineInstr*, 4> &Ops,
+ SmallVectorImpl<MachineInstr *> &Ops,
unsigned Base, bool isLd,
DenseMap<MachineInstr*, unsigned> &MI2LocMap) {
bool RetVal = false;
if (!StopHere)
BI->second.push_back(MI);
} else {
- SmallVector<MachineInstr*, 4> MIs;
- MIs.push_back(MI);
- Base2LdsMap[Base] = MIs;
+ Base2LdsMap[Base].push_back(MI);
LdBases.push_back(Base);
}
} else {
if (!StopHere)
BI->second.push_back(MI);
} else {
- SmallVector<MachineInstr*, 4> MIs;
- MIs.push_back(MI);
- Base2StsMap[Base] = MIs;
+ Base2StsMap[Base].push_back(MI);
StBases.push_back(Base);
}
}
// Re-schedule loads.
for (unsigned i = 0, e = LdBases.size(); i != e; ++i) {
unsigned Base = LdBases[i];
- SmallVector<MachineInstr*, 4> &Lds = Base2LdsMap[Base];
+ SmallVectorImpl<MachineInstr *> &Lds = Base2LdsMap[Base];
if (Lds.size() > 1)
RetVal |= RescheduleOps(MBB, Lds, Base, true, MI2LocMap);
}
// Re-schedule stores.
for (unsigned i = 0, e = StBases.size(); i != e; ++i) {
unsigned Base = StBases[i];
- SmallVector<MachineInstr*, 4> &Sts = Base2StsMap[Base];
+ SmallVectorImpl<MachineInstr *> &Sts = Base2StsMap[Base];
if (Sts.size() > 1)
RetVal |= RescheduleOps(MBB, Sts, Base, false, MI2LocMap);
}
projects / oota-llvm.git / blobdiff