Fix PR25339: ARM Constant Island

[weimingz]

Summary

Currently, the ARM Constant Island may not converge (or not converge quickly).
This patch let it move to the closest water after the user if it doesn't converge after 15 iterations.

This address https://llvm.org/bugs/show_bug.cgi?id=25339

[rengolin]

Hi Weiming,

I'd like to know how you got to the magic number of 15. So, showing a small program that doesn't converge, then showing that this change makes it at least stop and produce whatever result is acceptable.

Constant islands are a major pain to get right because some relocations are only handled later and merging two islands can grow the distance of a third beyond the range of some load far away. In the same way, *not* merging could cause the same effects.

Would be good to see the results of compiling large pieces of code (say, LNT, Chromium, Firefox) which have plenty of opportunities to get this wrong. Without tests, it's hard to see what kind of problem you're trying to avoid, here.

cheers,
--renato

lib/Target/ARM/ARMConstantIslandPass.cpp

463–464

Shouldn't this 15 be in a constant somewhere? Maybe a hidden command line options, which defaults to 15, but can be changed?

1336

s/lowerest/lowest/

1348–1349

Update the comment to reflect the new flag

[weimingz]

Hi Renato,

I'll post the test case shortly. Since it's based on proprietary code,
it needs to complete some internal review process.
So far, I can only give a brief description of the problematic code.
Please see https://llvm.org/bugs/show_bug.cgi?id=25339

The number 15 is half of the max threshold of 30.
I did a measurement of building SPEC and the highest iteration number I
see is 3.

Thanks,
Weiming

[rengolin]

In D16890#345099, @weimingz wrote:

I'll post the test case shortly. Since it's based on proprietary code,
it needs to complete some internal review process.

I completely understand. No worries.

So far, I can only give a brief description of the problematic code.
Please see https://llvm.org/bugs/show_bug.cgi?id=25339

Ah, excellent! That bug was on my radar, and I'm glad someone is looking at it. When you submit a review based on a bug, it's good to put the bug number like "Addresses bug #NNNN", so we can grab the rest of the context.

The number 15 is half of the max threshold of 30.

Right. If the max is hard-coded, then maybe say max/2 in there?

It's also not clear to me why 15 is better than 30. If the algorithm fails to converge on both, than clearly either hard-coded numbers would be ok as long as the safe option is implemented. This patch seems to be doing both: forcing a convergence, even if a bad one (which would also work with 30 iterations, I think), and reducing the threshold to 15 (which doesn't make much sense per se).

I did a measurement of building SPEC and the highest iteration number I
see is 3.

This means that the application itself is problematic in that respect, so any number beyond 5 would be a good bet, with higher numbers better because they would only hit the worse cases.

What's the impact if you keep the original threshold?

cheers,
--renato

[llvm-commits]

Hi Renato,

I uploaded the test case to bugzilla.
https://llvm.org/bugs/show_bug.cgi?id=25339

This patch doesn't reduce the threshold to 15. It tries to accelerate
the converge after 15th iteration by ignoring the "best growth".

Thanks,
Weiming

[rengolin]

In D16890#356160, @llvm-commits wrote:

This patch doesn't reduce the threshold to 15. It tries to accelerate
the converge after 15th iteration by ignoring the "best growth".

Ok, so then we need the number 15 to be on the same place as the number 30. If both are magic constants, we need to make them into some kind of static const global or a hidden compiler flag.

cheers,
--renato

[weimingz]

I uploaded another test case to https://llvm.org/bugs/show_bug.cgi?id=25339.
That test case exposes different issues with CP. In that case, we want to split BB to accelerate converge.

[rengolin]

Looks much better, thanks!

There's only the typo on the comment "lowerest" -> "lowest", but LGTM with that fix.

[weimingz]

fixed the typo and updated comments

[weimingz]

In D16890#359642, @rengolin wrote:

Looks much better, thanks!

There's only the typo on the comment "lowerest" -> "lowest", but LGTM with that fix.

Hi Renato,

Thanks for reviewing. I will fix the comment and merge it.

[srhines]

To be perfectly clear, this was submitted as r261665.

[weimingz]

This comment was removed by weimingz.

lib/Target/ARM/ARMConstantIslandPass.cpp

 STATISTIC(NumJTMoved,    "Number of jump table destination blocks moved");
 STATISTIC(NumJTInserted, "Number of jump table intermediate blocks inserted");
 
 
 static cl::opt<bool>
 AdjustJumpTableBlocks("arm-adjust-jump-tables", cl::Hidden, cl::init(true),
           cl::desc("Adjust basic block layout to better use TB[BH]"));
 
+static cl::opt<unsigned>
+CPMaxIteration("arm-constant-island-max-iteration", cl::Hidden, cl::init(30),
+          cl::desc("The max number of iteration for converge"));
+
+
 /// UnknownPadding - Return the worst case padding that could result from
 /// unknown offset bits.  This does not include alignment padding caused by
 /// known offset bits.
 ///
 /// @param LogAlign log2(alignment)
 /// @param KnownBits Number of known low offset bits.
 static inline unsigned UnknownPadding(unsigned LogAlign, unsigned KnownBits) {
   if (KnownBits < LogAlign)
private:
     void initializeFunctionInfo(const std::vector<MachineInstr*> &CPEMIs);
     MachineBasicBlock *splitBlockBeforeInstr(MachineInstr *MI);
     void updateForInsertedWaterBlock(MachineBasicBlock *NewBB);
     void adjustBBOffsetsAfter(MachineBasicBlock *BB);
     bool decrementCPEReferenceCount(unsigned CPI, MachineInstr* CPEMI);
     unsigned getCombinedIndex(const MachineInstr *CPEMI);
     int findInRangeCPEntry(CPUser& U, unsigned UserOffset);
     bool findAvailableWater(CPUser&U, unsigned UserOffset,
-                            water_iterator &WaterIter);
+                            water_iterator &WaterIter, bool CloserWater);
     void createNewWater(unsigned CPUserIndex, unsigned UserOffset,
                         MachineBasicBlock *&NewMBB);
-    bool handleConstantPoolUser(unsigned CPUserIndex);
+    bool handleConstantPoolUser(unsigned CPUserIndex, bool CloserWater);
     void removeDeadCPEMI(MachineInstr *CPEMI);
     bool removeUnusedCPEntries();
     bool isCPEntryInRange(MachineInstr *MI, unsigned UserOffset,
                           MachineInstr *CPEMI, unsigned Disp, bool NegOk,
                           bool DoDump = false);
     bool isWaterInRange(unsigned UserOffset, MachineBasicBlock *Water,
                         CPUser &U, unsigned &Growth);
     bool isBBInRange(MachineInstr *MI, MachineBasicBlock *BB, unsigned Disp);
bool ARMConstantIslands::runOnMachineFunction(MachineFunction &mf) {
   MadeChange |= removeUnusedCPEntries();
 
   // Iteratively place constant pool entries and fix up branches until there
   // is no change.
   unsigned NoCPIters = 0, NoBRIters = 0;
   while (true) {
     DEBUG(dbgs() << "Beginning CP iteration #" << NoCPIters << '\n');
     bool CPChange = false;
     for (unsigned i = 0, e = CPUsers.size(); i != e; ++i)
-      CPChange |= handleConstantPoolUser(i);
-    if (CPChange && ++NoCPIters > 30)
+      // For most inputs, it converges in no more than 5 iterations.
+      // If it doens't end in 10, the input may have huge BB or many CPEs.
+      // In this case, we will try differnt heuristics.
+      CPChange |= handleConstantPoolUser(i, NoCPIters >= CPMaxIteration / 2);
+    if (CPChange && ++NoCPIters > CPMaxIteration)
       report_fatal_error("Constant Island pass failed to converge!");
     DEBUG(dumpBBs());
 
     // Clear NewWaterList now.  If we split a block for branches, it should
     // appear as "new water" for the next iteration of constant pool placement.
     NewWaterList.clear();
 
     DEBUG(dbgs() << "Beginning BR iteration #" << NoBRIters << '\n');

 /// we can place the CPE referenced from U so it's within range of U's MI.
 /// Returns true if found, false if not.  If it returns true, WaterIter
 /// is set to the WaterList entry.  For Thumb, prefer water that will not
 /// introduce padding to water that will.  To ensure that this pass
 /// terminates, the CPE location for a particular CPUser is only allowed to
 /// move to a lower address, so search backward from the end of the list and
 /// prefer the first water that is in range.
 bool ARMConstantIslands::findAvailableWater(CPUser &U, unsigned UserOffset,
-                                      water_iterator &WaterIter) {
+                                            water_iterator &WaterIter,
+                                            bool CloserWater) {
   if (WaterList.empty())
     return false;
 
   unsigned BestGrowth = ~0u;
+  // The nearest water without splitting the UserBB is right after it.
+  // If the distance is still large (we have a big BB), then we need to split it
+  // if we don't converge after certain iterations. This helps the following
+  // situation to converge:
+  //   BB0:
+  //      Big BB
+  //   BB1:
+  //      Constant Pool
+  // When a CP access is out of range, BB0 may be used as water. However,
+  // inserting islands between BB0 and BB1 makes other accesses out of range.
+  MachineBasicBlock *UserBB = U.MI->getParent();
+  unsigned MinNoSplitDisp =
+      BBInfo[UserBB->getNumber()].postOffset(getCPELogAlign(U.CPEMI));
+  if (CloserWater && MinNoSplitDisp > U.getMaxDisp() / 2)
+    return false;
   for (water_iterator IP = std::prev(WaterList.end()), B = WaterList.begin();;
        --IP) {
     MachineBasicBlock* WaterBB = *IP;
     // Check if water is in range and is either at a lower address than the
     // current "high water mark" or a new water block that was created since
     // the previous iteration by inserting an unconditional branch.  In the
     // latter case, we want to allow resetting the high water mark back to
     // this new water since we haven't seen it before.  Inserting branches
     // should be relatively uncommon and when it does happen, we want to be
     // sure to take advantage of it for all the CPEs near that block, so that
     // we don't insert more branches than necessary.
+    // When CloserWater is true, we try to find the lowest address after (or
+    // equal to) user MI's BB no matter of padding growth.
     unsigned Growth;
     if (isWaterInRange(UserOffset, WaterBB, U, Growth) &&
         (WaterBB->getNumber() < U.HighWaterMark->getNumber() ||
          NewWaterList.count(WaterBB) || WaterBB == U.MI->getParent()) &&
         Growth < BestGrowth) {
       // This is the least amount of required padding seen so far.
       BestGrowth = Growth;
       WaterIter = IP;
       DEBUG(dbgs() << "Found water after BB#" << WaterBB->getNumber()
                    << " Growth=" << Growth << '\n');
 
-      // Keep looking unless it is perfect.
-      if (BestGrowth == 0)
+      if (CloserWater && WaterBB == U.MI->getParent())
+        return true;
+      // Keep looking unless it is perfect and we're not looking for the lowest
+      // possible address.
+      if (!CloserWater && BestGrowth == 0)
         return true;
     }
     if (IP == B)
       break;
   }
   return BestGrowth != ~0u;
 }
 
void ARMConstantIslands::createNewWater(unsigned CPUserIndex,
 
   NewMBB = splitBlockBeforeInstr(MI);
 }
 
 /// handleConstantPoolUser - Analyze the specified user, checking to see if it
 /// is out-of-range.  If so, pick up the constant pool value and move it some
 /// place in-range.  Return true if we changed any addresses (thus must run
 /// another pass of branch lengthening), false otherwise.
-bool ARMConstantIslands::handleConstantPoolUser(unsigned CPUserIndex) {
+bool ARMConstantIslands::handleConstantPoolUser(unsigned CPUserIndex,
+                                                bool CloserWater) {
   CPUser &U = CPUsers[CPUserIndex];
   MachineInstr *UserMI = U.MI;
   MachineInstr *CPEMI  = U.CPEMI;
   unsigned CPI = getCombinedIndex(CPEMI);
   unsigned Size = CPEMI->getOperand(2).getImm();
   // Compute this only once, it's expensive.
   unsigned UserOffset = getUserOffset(U);
 
   // See if the current entry is within range, or there is a clone of it
   // in range.
   int result = findInRangeCPEntry(U, UserOffset);
   if (result==1) return false;
   else if (result==2) return true;
 
   // No existing clone of this CPE is within range.
   // We will be generating a new clone.  Get a UID for it.
   unsigned ID = AFI->createPICLabelUId();
 
   // Look for water where we can place this CPE.
   MachineBasicBlock *NewIsland = MF->CreateMachineBasicBlock();
   MachineBasicBlock *NewMBB;
   water_iterator IP;
-  if (findAvailableWater(U, UserOffset, IP)) {
+  if (findAvailableWater(U, UserOffset, IP, CloserWater)) {
     DEBUG(dbgs() << "Found water in range\n");
     MachineBasicBlock *WaterBB = *IP;
 
     // If the original WaterList entry was "new water" on this iteration,
     // propagate that to the new island.  This is just keeping NewWaterList
     // updated to match the WaterList, which will be updated below.
     if (NewWaterList.erase(WaterBB))
       NewWaterList.insert(NewIsland);