AArch64: Make AArch64A57FPLoadBalancing output stable.

[gberry]

Summary

Add tie breaker to colorChainSet() sort so that processing order doesn't
depend on std::set order, which depends on pointer order, which is
unstable from run to run.

[gberry]

Hi James,

No, I don’t think just switching to std::stable_sort() would solve the problem. The elements that are “equal” based on the sort comparison would remain in their original order before the sort, which I believe is determined by the order they occur in the EquivalenceClasses member iterator, which is in turn determined by pointer order since the EquivalenceClasses members are stored in a set<Chain*> in this case.

Hopefully that makes sense. If so, could you commit this change?

Thanks,

-Geoff

Geoff Berry

Employee of Qualcomm Innovation Center, Inc.

Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, a Linux Foundation Collaborative Project

From: James Molloy [mailto:[e-mail]]
Sent: Friday, January 30, 2015 3:41 AM
To: [e-mail]; [e-mail]; [e-mail]; [e-mail]; [e-mail]
Cc: [e-mail]; [e-mail]
Subject: Re: [PATCH] AArch64: Make AArch64A57FPLoadBalancing output stable.

Hi Geoff,

Thanks for fixing this! It looks ok as-is, but wouldn't switching simply from std::sort to std::stable_sort solve the problem easier? Stable_sort is used for this reason in other areas of the compiler.

Cheers,

James

[bmakam]

Adding Rafael to the review, since he had fixed similar issues in the past (r196520) relating to non-deterministic behavior.
Rafael, do you think this is a good fix to the non-deterministic behavior we are seeing?

[mcrosier]

Based on James' comments and Geoff's feedback, I'm going to go ahead and approve the change.

[mcrosier]

Committed in r227606.

lib/Target/AArch64/AArch64A57FPLoadBalancing.cpp

   }
 
   /// Return true if this chain starts before Other.
-  bool startsBefore(Chain *Other) {
+  bool startsBefore(const Chain *Other) const {
     return StartInstIdx < Other->StartInstIdx;
   }
 

   // chains that we cannot change before we look at those we can,
   // so the parity counter is updated and we know what color we should
   // change them to!
+  // Final tie-break with instruction order so pass output is stable (i.e. not
+  // dependent on malloc'd pointer values).
   std::sort(GV.begin(), GV.end(), [](const Chain *G1, const Chain *G2) {
       if (G1->size() != G2->size())
         return G1->size() > G2->size();
-      return G1->requiresFixup() > G2->requiresFixup();
+      if (G1->requiresFixup() != G2->requiresFixup())
+        return G1->requiresFixup() > G2->requiresFixup();
+      // Make sure startsBefore() produces a stable final order.
+      assert((G1 == G2 || (G1->startsBefore(G2) ^ G2->startsBefore(G1))) &&
+             "Starts before not total order!");
+      return G1->startsBefore(G2);
     });
 
   Color PreferredColor = Parity < 0 ? Color::Even : Color::Odd;