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

459

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

1313

s/lowerest/lowest/

1327

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

private:
     void scanFunctionJumpTables();
     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);
+    bool findAvailableWater(CPUser &U, unsigned UserOffset,
+                            water_iterator &WaterIter, bool IgnoreGrowth);
     void createNewWater(unsigned CPUserIndex, unsigned UserOffset,
                         MachineBasicBlock *&NewMBB);
-    bool handleConstantPoolUser(unsigned CPUserIndex);
+    bool handleConstantPoolUser(unsigned CPUserIndex, bool IgnoreGrowth);
     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) {
 
   // 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);
+      CPChange |= handleConstantPoolUser(i, NoCPIters >= 15 /*Ignore Growth*/);
     if (CPChange && ++NoCPIters > 30)
       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();
 

 /// 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 IgnoreGrowth) {
   if (WaterList.empty())
     return false;
 
   unsigned BestGrowth = ~0u;
   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 IgnoreGrowth is true, we try to find the lowerest 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');
-
+      if (IgnoreGrowth && WaterBB == U.MI->getParent())
+        return true;
       // Keep looking unless it is perfect.
-      if (BestGrowth == 0)
+      if (!IgnoreGrowth && 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 IgnoreGrowth) {
   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, IgnoreGrowth)) {
     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);