+#endif
+ return(false);
+ }
+}
+
+/// ComputeSameTails - Look through all the blocks in MergePotentials that have
+/// hash CurHash (guaranteed to match the last element). Build the vector
+/// SameTails of all those that have the (same) largest number of instructions
+/// in common of any pair of these blocks. SameTails entries contain an
+/// iterator into MergePotentials (from which the MachineBasicBlock can be
+/// found) and a MachineBasicBlock::iterator into that MBB indicating the
+/// instruction where the matching code sequence begins.
+/// Order of elements in SameTails is the reverse of the order in which
+/// those blocks appear in MergePotentials (where they are not necessarily
+/// consecutive).
+unsigned BranchFolder::ComputeSameTails(unsigned CurHash,
+ unsigned minCommonTailLength) {
+ unsigned maxCommonTailLength = 0U;
+ SameTails.clear();
+ MachineBasicBlock::iterator TrialBBI1, TrialBBI2;
+ MPIterator HighestMPIter = prior(MergePotentials.end());
+ for (MPIterator CurMPIter = prior(MergePotentials.end()),
+ B = MergePotentials.begin();
+ CurMPIter!=B && CurMPIter->first==CurHash;
+ --CurMPIter) {
+ for (MPIterator I = prior(CurMPIter); I->first==CurHash ; --I) {
+ unsigned CommonTailLen = ComputeCommonTailLength(
+ CurMPIter->second,
+ I->second,
+ TrialBBI1, TrialBBI2);
+ // If we will have to split a block, there should be at least
+ // minCommonTailLength instructions in common; if not, at worst
+ // we will be replacing a fallthrough into the common tail with a
+ // branch, which at worst breaks even with falling through into
+ // the duplicated common tail, so 1 instruction in common is enough.
+ // We will always pick a block we do not have to split as the common
+ // tail if there is one.
+ // (Empty blocks will get forwarded and need not be considered.)
+ if (CommonTailLen >= minCommonTailLength ||
+ (CommonTailLen > 0 &&
+ (TrialBBI1==CurMPIter->second->begin() ||
+ TrialBBI2==I->second->begin()))) {
+ if (CommonTailLen > maxCommonTailLength) {
+ SameTails.clear();
+ maxCommonTailLength = CommonTailLen;
+ HighestMPIter = CurMPIter;
+ SameTails.push_back(std::make_pair(CurMPIter, TrialBBI1));
+ }
+ if (HighestMPIter == CurMPIter &&
+ CommonTailLen == maxCommonTailLength)
+ SameTails.push_back(std::make_pair(I, TrialBBI2));
+ }
+ if (I==B)
+ break;
+ }
+ }
+ return maxCommonTailLength;
+}
+
+/// RemoveBlocksWithHash - Remove all blocks with hash CurHash from
+/// MergePotentials, restoring branches at ends of blocks as appropriate.
+void BranchFolder::RemoveBlocksWithHash(unsigned CurHash,
+ MachineBasicBlock* SuccBB,
+ MachineBasicBlock* PredBB) {
+ MPIterator CurMPIter, B;
+ for (CurMPIter = prior(MergePotentials.end()), B = MergePotentials.begin();
+ CurMPIter->first==CurHash;
+ --CurMPIter) {
+ // Put the unconditional branch back, if we need one.
+ MachineBasicBlock *CurMBB = CurMPIter->second;
+ if (SuccBB && CurMBB != PredBB)
+ FixTail(CurMBB, SuccBB, TII);
+ if (CurMPIter==B)
+ break;
+ }
+ if (CurMPIter->first!=CurHash)
+ CurMPIter++;
+ MergePotentials.erase(CurMPIter, MergePotentials.end());
+}
+
+/// CreateCommonTailOnlyBlock - None of the blocks to be tail-merged consist
+/// only of the common tail. Create a block that does by splitting one.
+unsigned BranchFolder::CreateCommonTailOnlyBlock(MachineBasicBlock *&PredBB,
+ unsigned maxCommonTailLength) {
+ unsigned i, commonTailIndex;
+ unsigned TimeEstimate = ~0U;
+ for (i=0, commonTailIndex=0; i<SameTails.size(); i++) {
+ // Use PredBB if possible; that doesn't require a new branch.
+ if (SameTails[i].first->second==PredBB) {
+ commonTailIndex = i;
+ break;
+ }
+ // Otherwise, make a (fairly bogus) choice based on estimate of
+ // how long it will take the various blocks to execute.
+ unsigned t = EstimateRuntime(SameTails[i].first->second->begin(),
+ SameTails[i].second);
+ if (t<=TimeEstimate) {
+ TimeEstimate = t;
+ commonTailIndex = i;
+ }
+ }
+
+ MachineBasicBlock::iterator BBI = SameTails[commonTailIndex].second;
+ MachineBasicBlock *MBB = SameTails[commonTailIndex].first->second;
+
+ DOUT << "\nSplitting " << MBB->getNumber() << ", size " <<
+ maxCommonTailLength;
+
+ MachineBasicBlock *newMBB = SplitMBBAt(*MBB, BBI);
+ SameTails[commonTailIndex].first->second = newMBB;
+ SameTails[commonTailIndex].second = newMBB->begin();
+ // If we split PredBB, newMBB is the new predecessor.
+ if (PredBB==MBB)
+ PredBB = newMBB;
+
+ return commonTailIndex;