[AArch64] Fix non-determinism in A57 FP Load Balancing

[ssijaric]

Summary

Change the type of AllChains from std::set<unique_ptr<Chain>> to std::vector<unique_ptr<Chain>>, as traversing pointers contained in std::set doesn't guarantee a well-defined order. We have observed differences in register assignment in .s files produced with the exact same build. I don't see that duplicate entries can be added to AllChains, so it should be safe to replace std::set with std::vector. This way, traversal of AllChains will be well defined.

Example debug output with -debug-only=aarch64-a57-fp-load-balancing resulting in different traversal:

Compile #1:

 colorChainSet(): #sets=4
- Parity=2, Color=Odd
- colorChain({%S19<def> = FMULSrr -> %S19<def> = FMULSrr}, Odd)
- Scavenged register: S3
- Destination register not changed.
- Parity=1, Color=Odd
- {%S18<def> = FMULSrr -> %S18<def> = FMULSrr} - not worthwhile changing; color remains Even
- colorChain({%S18<def> = FMULSrr -> %S18<def> = FMULSrr}, Even)
- Scavenged register: S2
- Destination register not changed.
- Parity=2, Color=Odd
- colorChain({%S6<def> = FMULSrr -> %S6<def> = FMULSrr (kill @ %S18<def> = FMULSrr)}, Odd)
- Scavenged register: S3
- Kill instruction seen.
- Parity=1, Color=Odd
- colorChain({%S16<def> = FMULSrr -> %S16<def> = FMULSrr (kill @ %S19<def> = FMULSrr)}, Odd)
- Scavenged register: S5
- Kill instruction seen.

Compile #2:

colorChainSet(): #sets=4

• Parity=2, Color=Odd
• colorChain({%S19<def> = FMULSrr -> %S19<def> = FMULSrr}, Odd)
• Scavenged register: S3
• Destination register not changed.
• Parity=1, Color=Odd
• {%S18<def> = FMULSrr -> %S18<def> = FMULSrr} - not worthwhile changing; color remains Even
• colorChain({%S18<def> = FMULSrr -> %S18<def> = FMULSrr}, Even)
• Scavenged register: S2
• Destination register not changed.
• Parity=2, Color=Odd
• colorChain({%S16<def> = FMULSrr -> %S16<def> = FMULSrr (kill @ %S19<def> = FMULSrr)}, Odd)
• Scavenged register: S3
• Kill instruction seen.
• Parity=1, Color=Odd
• colorChain({%S6<def> = FMULSrr -> %S6<def> = FMULSrr (kill @ %S18<def> = FMULSrr)}, Odd)
• Scavenged register: S5
• Kill instruction seen.

Cannot have a reproducible test case for this.

[ssijaric]

Hi James,

Separately, Geoff ran into the same problem. He found that the problem occurs during sorting in AArch64A57FPLoadBalancing::colorChainSet(…). He will upload his patch for review.

I didn’t see the need for the uniqueness property of the set for AllChains, but changing from std::set to std::vector (or SetVector) may be just hiding the problem. Geoff’s patch should address this.

Thanks,

Sanjin

From: James Molloy [mailto:[e-mail]]
Sent: Wednesday, January 28, 2015 12:01 PM
To: [e-mail]; [e-mail]; [e-mail]; [e-mail]; [e-mail]
Cc: [e-mail]; [e-mail]
Subject: Re: [PATCH] [AArch64] Fix non-determinism in A57 FP Load Balancing

Hi Sanjin,

Are you sure we don't need the uniqueness property of a set any more?

If not, SetVector seems like the right solution.

James

[jmolloy]

Rejecting this, because Geoff fixed this in a different revision.

lib/Target/AArch64/AArch64A57FPLoadBalancing.cpp

   int scavengeRegister(Chain *G, Color C, MachineBasicBlock &MBB);
   void scanInstruction(MachineInstr *MI, unsigned Idx,
                        std::map<unsigned, Chain*> &Active,
-                       std::set<std::unique_ptr<Chain>> &AllChains);
+                       std::vector<std::unique_ptr<Chain>> &AllChains);
   void maybeKillChain(MachineOperand &MO, unsigned Idx,
                       std::map<unsigned, Chain*> &RegChains);
   Color getColor(unsigned Register);

   // been killed yet. This is keyed by register - all chains can only have one
   // "link" register between each inst in the chain.
   std::map<unsigned, Chain*> ActiveChains;
-  std::set<std::unique_ptr<Chain>> AllChains;
+  std::vector<std::unique_ptr<Chain>> AllChains;
   unsigned Idx = 0;
   for (auto &MI : MBB)
     scanInstruction(&MI, Idx++, ActiveChains, AllChains);

 void AArch64A57FPLoadBalancing::
 scanInstruction(MachineInstr *MI, unsigned Idx, 
                 std::map<unsigned, Chain*> &ActiveChains,
-                std::set<std::unique_ptr<Chain>> &AllChains) {
+                std::vector<std::unique_ptr<Chain>> &AllChains) {
   // Inspect "MI", updating ActiveChains and AllChains.
 
   if (isMul(MI)) {

 
     auto G = llvm::make_unique<Chain>(MI, Idx, getColor(DestReg));
     ActiveChains[DestReg] = G.get();
-    AllChains.insert(std::move(G));
+    AllChains.push_back(std::move(G));
 
   } else if (isMla(MI)) {
 

           << TRI->getName(DestReg) << "\n");
     auto G = llvm::make_unique<Chain>(MI, Idx, getColor(DestReg));
     ActiveChains[DestReg] = G.get();
-    AllChains.insert(std::move(G));
+    AllChains.push_back(std::move(G));
 
   } else {