[RewriteStatepointsForGC] Stabilise rematerialization order

[igor-laevsky]

Summary

This patch fixes non-determinism we had during rematerialization of the live values. There were two sources of it:

1. We need to iterate through rematerialization candidates in a stable order. Fix is achieved by sorting them prior to the loop (similarly to other places in this pass)
2. We used DenseSet to keep already rematerialized values. Fixed by changing storage from DenseSet to vector of pairs.

[sanjoy]

Hi Igor,

I had something different in mind: I'd have preferred a systematic
"deterministic by construction" approach, not "at a certain point,
stabilize the order to something quasi-deterministic". For instance,
I think you're still relying on pointer comparison in order_by_name
for unnamed values.

I'd prefer that we figure out why there is any non-determinism in the
first place (e.g. one suspicious bit is that StatepointLiveSetTy is
a DenseSet, perhaps it should be a SetVector?), fix those sources
of non-determinism and ultimately get rid of these stabilization steps
altogether.

Does that sound reasonable?

[igor-laevsky]

Hi Sanjoy,

It would be preferable to have determinism by construction. However in order to
get it we will need to not only change StatepointLiveSetTy type, but also
change all data types associated with liveness/basepointer analysis.

I'm afraid by doing so we will spend considerable amount of resources
(SetVector's and MapVector's are more expensive). And since this issue is not
directly related to correctness I would go with this non-perfect approach.

[igor-laevsky]

So what do you think? Basically we will consume twice as much memory for sustaining order via SetVector/MapVector. And since we only need stable order in certain points and not during whole pass run, I think it's fine to keep explicit sorting. We should probably hoist such code into a clear helper function though.

[sanjoy]

In D19421#413633, @igor-laevsky wrote:

So what do you think? Basically we will consume twice as much memory for sustaining order via SetVector/MapVector. And since we only need stable order in certain points and not during whole pass run, I think it's fine to keep explicit sorting. We should probably hoist such code into a clear helper function though.

I'd say if the additional time or space consumption creates trouble, we can consider moving to a cleverer algorithm (i.e. doing less work because doing the same units of work is more expensive). For now, given that non-determinism in this pass leads to actual codegen differences, I'm fairly inclined to make things deterministic by construction.

[igor-laevsky]

Ok, makes sense. Please take a look at the http://reviews.llvm.org/D19669

lib/Transforms/Scalar/RewriteStatepointsForGC.cpp

 // In the actual implementation this caches two relations:
 // - The base relation itself (i.e. this pointer is based on that one)
 // - The base defining value relation (i.e. before base_phi insertion)
 // Generally, after the execution of a full findBasePointer call, only the
 // base relation will remain.  Internally, we add a mixture of the two
 // types, then update all the second type to the first type
 typedef DenseMap<Value *, Value *> DefiningValueMapTy;
 typedef DenseSet<Value *> StatepointLiveSetTy;
-typedef DenseMap<AssertingVH<Instruction>, AssertingVH<Value>>
+typedef SmallVector<std::pair<AssertingVH<Instruction>, AssertingVH<Value>>, 32>
     RematerializedValueMapTy;
 
 struct PartiallyConstructedSafepointRecord {
   /// The set of values known to be live across this safepoint
   StatepointLiveSetTy LiveSet;
 
   /// Mapping from live pointers to a base-defining-value
   DenseMap<Value *, Value *> PointerToBase;
 

 // statepoint and record them in "Info" structure. Note that similar to
 // relocated values we don't do any user adjustments here.
 static void rematerializeLiveValues(CallSite CS,
                                     PartiallyConstructedSafepointRecord &Info,
                                     TargetTransformInfo &TTI) {
   const unsigned int ChainLengthThreshold = 10;
 
   // Record values we are going to delete from this statepoint live set.
-  // We can not di this in following loop due to iterator invalidation.
+  // We can't do this in a single loop due to iterator invalidation.
   SmallVector<Value *, 32> LiveValuesToBeDeleted;
 
-  for (Value *LiveValue: Info.LiveSet) {
+  // Stabilize iteration order over LiveSet. We want deterministic naming of
+  // the rematerialized values.
+  SmallVector<Value *, 64> OrderedLiveSet;
+  OrderedLiveSet.insert(OrderedLiveSet.end(), Info.LiveSet.begin(),
+                        Info.LiveSet.end());
+  std::sort(OrderedLiveSet.begin(), OrderedLiveSet.end(), order_by_name);
+
+  for (Value *LiveValue: OrderedLiveSet) {
     // For each live pointer find it's defining chain
     SmallVector<Instruction *, 3> ChainToBase;
     assert(Info.PointerToBase.count(LiveValue));
     bool FoundChain =
       findRematerializableChainToBasePointer(ChainToBase,
                                              LiveValue,
                                              Info.PointerToBase[LiveValue]);
     // Nothing to do, or chain is too long
#endif
     };
 
     // Different cases for calls and invokes. For invokes we need to clone
     // instructions both on normal and unwind path.
     if (CS.isCall()) {
       Instruction *InsertBefore = CS.getInstruction()->getNextNode();
       assert(InsertBefore);
       Instruction *RematerializedValue = rematerializeChain(InsertBefore);
-      Info.RematerializedValues[RematerializedValue] = LiveValue;
+      Info.RematerializedValues.emplace_back(RematerializedValue, LiveValue);
     } else {
       InvokeInst *Invoke = cast<InvokeInst>(CS.getInstruction());
 
       Instruction *NormalInsertBefore =
           &*Invoke->getNormalDest()->getFirstInsertionPt();
       Instruction *UnwindInsertBefore =
           &*Invoke->getUnwindDest()->getFirstInsertionPt();
 
       Instruction *NormalRematerializedValue =
           rematerializeChain(NormalInsertBefore);
       Instruction *UnwindRematerializedValue =
           rematerializeChain(UnwindInsertBefore);
 
-      Info.RematerializedValues[NormalRematerializedValue] = LiveValue;
-      Info.RematerializedValues[UnwindRematerializedValue] = LiveValue;
+      Info.RematerializedValues.emplace_back(NormalRematerializedValue,
+                                             LiveValue);
+      Info.RematerializedValues.emplace_back(UnwindRematerializedValue,
+                                             LiveValue);
     }
   }
 
   // Remove rematerializaed values from the live set
   for (auto LiveValue: LiveValuesToBeDeleted) {
     Info.LiveSet.erase(LiveValue);
   }
 }