Fix differences in codegen between Linux and Windows toolchains

[mgrang]

Summary

There are differences in codegen between Linux and Windows due to:
1. Using std::sort which uses quicksort which is a non-stable sort.

2. Iterating over Set data structure where the iteration order is
   non deterministic.

[mgrang]

Here is a snippet of the generated code on Linux and Windows ( I cannot post the entire code since it is proprietary).

On Linux:

4ec:	e0882002 	add	r2, r8, r2
4f0:	e0881001 	add	r1, r8, r1
4f4:	f4e0083f 	vld1.32	{d16[0]}, [r0 :32]
4f8:	e5980898 	ldr	r0, [r8, #2200]	; 0x898
4fc:	e2800018 	add	r0, r0, #24
500:	f3c80a30 	vmovl.u8	q8, d16
504:	f4602a8f 	vld1.32	{d18-d19}, [r0]
508:	f3d00a30 	vmovl.u16	q8, d16

On Windows:

4ec:	e28e1044 	add	r1, lr, #68	; 0x44
4f0:	e28de901 	add	lr, sp, #16384	; 0x4000
4f4:	e0883003 	add	r3, r8, r3
4f8:	e0882002 	add	r2, r8, r2
4fc:	f4e0083f 	vld1.32	{d16[0]}, [r0 :32]
500:	e5980898 	ldr	r0, [r8, #2200]	; 0x898
504:	e2800018 	add	r0, r0, #24
508:	f3c80a30 	vmovl.u8	q8, d16

[MatzeB]

Seems sensible. What do you think about adding a tie-breaking rule in the comparator instead of switching to stable sorts?

struct MemOpInfo { ...
   bool operator<(const MemOpInfo&RHS) const {
     return std::tie(BaseReg, Offset, SU->NodeNum)
       < std::tie(RHS.BaseReg, RHS.Offset, RHS.SU->NodeNum);
   }
};

class FrameRef {
   bool operator<(const FrameRef &RHS) const {
     return std::tie(LocalOffset, FrameIndex) < std::tie(RHS.LocalOffset, FrameIndex);
   }
};

[mgrang]

Thanks Matthias for your suggestion.
I liked the idea of adding a tie-breaking rule instead of using std::stable_sort (mergesort would use more memory).
I will implement your suggestion and push another patch.

[MatzeB]

The operator < changes LGTM. Is the RegionInfo change accidental?

include/llvm/Analysis/RegionInfo.h

682

This was not part of your first commit, was it?

I could not figure out where this typedef is used. In fact when I remove the whole line llvm still builds without a problem for me. Am I missing something here?

lib/CodeGen/LocalStackSlotAllocation.cpp

325–330

This can stay array_pod_sort I presume?

[mgrang]

include/llvm/Analysis/RegionInfo.h

682

Yes this was part of my first commit. The RegionSet is used in Polly in a number of places.

lib/CodeGen/LocalStackSlotAllocation.cpp

325–330

No, it seems array_pod_sort uses its own comparator:

inline int array_pod_sort_comparator(const void *P1, const void *P2) {

if (std::less<T>()(*reinterpret_cast<const T*>(P1),
                   *reinterpret_cast<const T*>(P2)))
  return -1;
if (std::less<T>()(*reinterpret_cast<const T*>(P2),
                   *reinterpret_cast<const T*>(P1)))
  return 1;
return 0;

}

[MatzeB]

include/llvm/Analysis/RegionInfo.h

682

Probably best to get a comment from someone familiar with polly for this part then.

lib/CodeGen/LocalStackSlotAllocation.cpp

325–330

The default implementation of std::less<T> uses operator < so that should work, does it fail for you?

[mgrang]

Yes, if I use array_pod_sort I still see the diffs in codegen in Linux vs Windows.

[MatzeB]

In D25695#572463, @mgrang wrote:

Yes, if I use array_pod_sort I still see the diffs in codegen in Linux vs Windows.

I just checked here and array_pod_sort definitely ends up calling operator < (I put a printf there). Can you check on your side? It would be very troubling if that was not the case (broken std::less implementation?).

[arsenm]

I have a patch out for review which fixed this by tracking the program order and using that to tie break. The same frame index wit the same offset can appear multiple times

[grosser]

Some feedback on Polly:

llvm/trunk/include/llvm/Analysis/RegionInfo.h

682 ↗

(On Diff #74936)

I just deleted this line and Polly still compiles fine. This seems to be unused to me, so we should probably just drop this entirely.

(In general, in Polly we have been careful to not iterate over Maps/Sets. We may still have missed some by accident, tough).

[mgrang]

Matthias,

As Matt says he already has a patch (https://reviews.llvm.org/D25188) which fixes the non-deterministic behavior in LocalStackSlotAllocation.cpp, I can remove it from my patch.

Matt,
What are your thoughts on the tie-breaker for MachineScheduler.cpp. Are you fine with my implementation? Can there be multiple entries with the same BaseReg, Offset and NodeNum? Maybe I can add "Order" to this similar to your patch?

--Mandeep

[mgrang]

llvm/trunk/include/llvm/Analysis/RegionInfo.h

682 ↗

(On Diff #74936)

Removed here: https://reviews.llvm.org/D25744

include/llvm/Analysis/RegionInfo.h

 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_ANALYSIS_REGIONINFO_H
 #define LLVM_ANALYSIS_REGIONINFO_H
 
 #include "llvm/ADT/DepthFirstIterator.h"
 #include "llvm/ADT/PointerIntPair.h"
+#include "llvm/ADT/SetVector.h"
 #include "llvm/ADT/iterator_range.h"
 #include "llvm/IR/CFG.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/PassManager.h"
 #include <map>
 #include <memory>
 #include <set>
 
class RegionInfoBase {
   typedef GraphTraits<Inverse<BlockT *>> InvBlockTraits;
   typedef typename BlockTraits::ChildIteratorType SuccIterTy;
   typedef typename InvBlockTraits::ChildIteratorType PredIterTy;
 
   friend class RegionInfo;
   friend class MachineRegionInfo;
   typedef DenseMap<BlockT *, BlockT *> BBtoBBMap;
   typedef DenseMap<BlockT *, RegionT *> BBtoRegionMap;
-  typedef SmallPtrSet<RegionT *, 4> RegionSet;
+  typedef SmallSetVector<RegionT *, 4> RegionSet;
 
   RegionInfoBase();
   virtual ~RegionInfoBase();
 
   RegionInfoBase(const RegionInfoBase &) = delete;
   const RegionInfoBase &operator=(const RegionInfoBase &) = delete;
 
   RegionInfoBase(RegionInfoBase &&Arg)

lib/CodeGen/LocalStackSlotAllocation.cpp

lookupCandidateBaseReg(unsigned BaseReg,
                        const MachineInstr &MI,
                        const TargetRegisterInfo *TRI) {
   // Check if the relative offset from the where the base register references
   // to the target address is in range for the instruction.
   int64_t Offset = FrameSizeAdjust + LocalFrameOffset - BaseOffset;
   return TRI->isFrameOffsetLegal(&MI, BaseReg, Offset);
 }
 
+static bool compareFrameRefs(const FrameRef &LHS, const FrameRef &RHS) {
+  return LHS.getLocalOffset() < RHS.getLocalOffset();
+}
+
 bool LocalStackSlotPass::insertFrameReferenceRegisters(MachineFunction &Fn) {
   // Scan the function's instructions looking for frame index references.
   // For each, ask the target if it wants a virtual base register for it
   // based on what we can tell it about where the local will end up in the
   // stack frame. If it wants one, re-use a suitable one we've previously
   // allocated, or if there isn't one that fits the bill, allocate a new one
   // and ask the target to create a defining instruction for it.
   bool UsedBaseReg = false;
for (MachineInstr &MI : BB) {
             break;
           FrameReferenceInsns.push_back(FrameRef(&MI, LocalOffset, Idx));
           break;
         }
       }
     }
   }
 
-  // Sort the frame references by local offset
-  array_pod_sort(FrameReferenceInsns.begin(), FrameReferenceInsns.end());
+  // Sort the frame references by local offset.
+  // Note: We need to use a stable sort here as qsort does not guarantee
+  // relative order of MIs having the same local offset.
+  std::stable_sort(FrameReferenceInsns.begin(), FrameReferenceInsns.end(),
+                   compareFrameRefs);
 
   MachineBasicBlock *Entry = &Fn.front();
 
   unsigned BaseReg = 0;
   int64_t BaseOffset = 0;
 
   // Loop through the frame references and allocate for them as necessary.
   for (int ref = 0, e = FrameReferenceInsns.size(); ref < e ; ++ref) {
     FrameRef &FR = FrameReferenceInsns[ref];

lib/CodeGen/MachineScheduler.cpp

for (unsigned Idx = 0, End = MemOps.size(); Idx != End; ++Idx) {
     unsigned BaseReg;
     int64_t Offset;
     if (TII->getMemOpBaseRegImmOfs(*SU->getInstr(), BaseReg, Offset, TRI))
       MemOpRecords.push_back(MemOpInfo(SU, BaseReg, Offset));
   }
   if (MemOpRecords.size() < 2)
     return;
 
-  std::sort(MemOpRecords.begin(), MemOpRecords.end());
+  std::stable_sort(MemOpRecords.begin(), MemOpRecords.end());
   unsigned ClusterLength = 1;
   for (unsigned Idx = 0, End = MemOpRecords.size(); Idx < (End - 1); ++Idx) {
     if (MemOpRecords[Idx].BaseReg != MemOpRecords[Idx+1].BaseReg) {
       ClusterLength = 1;
       continue;
     }
 
     SUnit *SUa = MemOpRecords[Idx].SU;