[mlir] Set random starting index

[jpienaar]

Summary

Example prodding the start of the printed ID sequence to identify cases where a
test is depending on current numbering starting at 0. Might be useful to flag
tests too constrained that will cause pain when updating.

Using MINSTD and LINE as simple (and might even be overkill as 5 as
starting value would work too).

More of an exploration than something we have to do :)

[rdzhabarov]

mlir/lib/IR/AsmPrinter.cpp

559

qq: do we document anywhere these keys used for tweaking different things?

[rriddle]

mlir/lib/IR/AsmPrinter.cpp

559

I think we should align under fewer macros, if this is something that we actually want to do. Seems like randomized naming starts, could be something under EXPENSIVE_CHECKS.

568

Is this guaranteed not to produce duplicates?

[rdzhabarov]

mlir/lib/IR/AsmPrinter.cpp

559

+1 to River's point.

568

I was playing with different seeds and seems like i have not found collisions after 10M+ iterations.
Curious, if there is math supporting this for any seeds we could use potentially use?

(also for our purposes, we could fix seed to predefined value, this will guarantee non duplicates for large number of iterations and also would work for our testing purposes).

[mehdi_amini]

mlir/lib/IR/AsmPrinter.cpp

559

This isn't an "expensive" check though. Seems closer to the LLVM_ENABLE_REVERSE_ITERATION macro in the mindset.

[jpienaar]

mlir/lib/IR/AsmPrinter.cpp

559

Correct, this isn't too expensive nor a would fit in with the other expensive checks. It just makes debug string printing more expensive.

Re: documentation, this was currently just for discussion so I didn't add any and we don't have anything this invasive with ifdefs at the moment (NDEBUG is almost as much as we have I think). If folks think useful to flush out bad tests, we could document in a separate md file. Depends on how many of these we add, we could either also document in cmake or use a config file.

568

Re: duplicates, not until it has gone full cycle back to the start (once we hit 2^31 value IDs in a module). Seed of 0 doesn't work, beyond that any 32-bit seed should work I believe.

This is:

Park, Stephen K.; Miller, Keith W. (1988). "Random Number Generators: Good Ones Are Hard To Find" (PDF). Communications of the ACM. 31 (10): 1192–1201. doi:10.1145/63039.63042.

[nicolasvasilache]

Stupid Q, if the end-goal is to detect SSA value names being used, can't we just switch the pretty printer to print "letter counters" instead ?
I.e. by default print SSA names in basis 10, when enabled print in basis "a-z" ?
I don't see a need for worrying about collisions with such a scheme.

[jpienaar]

In D90573#3831822, @nicolasvasilache wrote:

Stupid Q, if the end-goal is to detect SSA value names being used, can't we just switch the pretty printer to print "letter counters" instead ?
I.e. by default print SSA names in basis 10, when enabled print in basis "a-z" ?
I don't see a need for worrying about collisions with such a scheme.

Yes, even counting with letters rather than numbers should work ... I don't think anywhere someone would have a sort along the way which this would break too (but that's not a safe thing to do in general).

Visually random does break things a bit more and gets folks out of mindset of number reflecting order in function and or believing SSA ID is retained in some way. Goal is towards avoiding relying on the incidental esp in tests.

mlir/lib/IR/AsmPrinter.cpp

private:
   DenseMap<Block *, unsigned> blockIDs;
 
   /// This keeps track of all of the non-numeric names that are in flight,
   /// allowing us to check for duplicates.
   /// Note: the value of the map is unused.
   llvm::ScopedHashTable<StringRef, char> usedNames;
   llvm::BumpPtrAllocator usedNameAllocator;
 
+  // If testing that SSA IDs are being used in tests directly.
+#ifdef MLIR_TEST_SSA_ID_SEQUENCE_ASSUMED
+  static constexpr unsigned initID() {
+    // This could be more random seed, but given the intention is just to
+    // ensure 0 is not assumged, should suffice.
+    return __LINE__ + 42;
+  }
+
+  static unsigned incrementID(unsigned &id) {
+    unsigned int ij = id;
+    // Use MINSTD to increment (period 2^31-1).
+    id = (16807l * ij) % 2147483647;
+    return ij;
+  };
+#else
+  static constexpr unsigned initID() { return 0; }
+
+  static unsigned incrementID(unsigned &id) { return id++; }
+#endif
+
   /// This is the next value ID to assign in numbering.
-  unsigned nextValueID = 0;
+  unsigned nextValueID;
   /// This is the next ID to assign to a region entry block argument.
-  unsigned nextArgumentID = 0;
+  unsigned nextArgumentID;
   /// This is the next ID to assign when a name conflict is detected.
-  unsigned nextConflictID = 0;
+  unsigned nextConflictID;
 };
 } // end anonymous namespace
 
 SSANameState::SSANameState(
     Operation *op,
-    DialectInterfaceCollection<OpAsmDialectInterface> &interfaces) {
+    DialectInterfaceCollection<OpAsmDialectInterface> &interfaces)
+    : nextValueID(initID()), nextArgumentID(initID()),
+      nextConflictID(initID()) {
   llvm::ScopedHashTable<StringRef, char>::ScopeTy usedNamesScope(usedNames);
   numberValuesInOp(*op, interfaces);
 
   for (auto &region : op->getRegions())
     numberValuesInRegion(region, interfaces);
 }
 
 void SSANameState::printValueID(Value value, bool printResultNo,
void SSANameState::numberValuesInBlock(
   // 'arg'.
   SmallString<32> specialNameBuffer(isEntryBlock ? "arg" : "");
   llvm::raw_svector_ostream specialName(specialNameBuffer);
   for (auto arg : block.getArguments()) {
     if (valueIDs.count(arg))
       continue;
     if (isEntryBlock) {
       specialNameBuffer.resize(strlen("arg"));
-      specialName << nextArgumentID++;
+      specialName << incrementID(nextArgumentID);
     }
     setValueName(arg, specialName.str());
   }
 
   // Number the operations in this block.
   for (auto &op : block)
     numberValuesInOp(op, interfaces);
 }
void SSANameState::numberValuesInOp(
   };
   if (OpAsmOpInterface asmInterface = dyn_cast<OpAsmOpInterface>(&op))
     asmInterface.getAsmResultNames(setResultNameFn);
   else if (auto *asmInterface = interfaces.getInterfaceFor(op.getDialect()))
     asmInterface->getAsmResultNames(&op, setResultNameFn);
 
   // If the first result wasn't numbered, give it a default number.
   if (valueIDs.try_emplace(resultBegin, nextValueID).second)
-    ++nextValueID;
+    incrementID(nextValueID);
 
   // If this operation has multiple result groups, mark it.
   if (resultGroups.size() != 1) {
     llvm::array_pod_sort(resultGroups.begin(), resultGroups.end());
     opResultGroups.try_emplace(&op, std::move(resultGroups));
   }
 }
 
void SSANameState::getResultIDAndNumber(OpResult result, Value &lookupValue,
   if (groupSize != 1)
     lookupResultNo = resultNo - groupResultNo;
   lookupValue = owner->getResult(groupResultNo);
 }
 
 void SSANameState::setValueName(Value value, StringRef name) {
   // If the name is empty, the value uses the default numbering.
   if (name.empty()) {
-    valueIDs[value] = nextValueID++;
+    valueIDs[value] = incrementID(nextValueID);
     return;
   }
 
   valueIDs[value] = NameSentinel;
   valueNames[value] = uniqueValueName(name);
 }
 
 /// Returns true if 'c' is an allowable punctuation character: [$._-]
StringRef SSANameState::uniqueValueName(StringRef name) {
   } else {
     // Otherwise, we had a conflict - probe until we find a unique name. This
     // is guaranteed to terminate (and usually in a single iteration) because it
     // generates new names by incrementing nextConflictID.
     SmallString<64> probeName(name);
     probeName.push_back('_');
     while (true) {
       probeName.resize(name.size() + 1);
-      probeName += llvm::utostr(nextConflictID++);
+      probeName += llvm::utostr(incrementID(nextConflictID));
       if (!usedNames.count(probeName)) {
         name = StringRef(probeName).copy(usedNameAllocator);
         break;
       }
     }
   }
 
   usedNames.insert(name, char());