[mlir] Fix bug in computing operation order

[jmolloy]

Summary

When attempting to compute a differential orderIndex we were calculating the
bailout condition correctly, but then an errant "+ 1" meant the orderIndex we
created was invalid.

Added test.

[ftynse]

mlir/unittests/IR/OperationSupportTest.cpp

173

Style nit: MLIR doesn't use const on stack variables.

[jmolloy]

Removed errant "const".

mlir/lib/IR/Operation.cpp

void Operation::updateOrderIfNecessary() {
   Operation *prevNode = getPrevNode(), *nextNode = getNextNode();
   if (!prevNode->hasValidOrder() || !nextNode->hasValidOrder())
     return block->recomputeOpOrder();
   unsigned prevOrder = prevNode->orderIndex, nextOrder = nextNode->orderIndex;
 
   // Check to see if there is a valid order between the two.
   if (prevOrder + 1 == nextOrder)
     return block->recomputeOpOrder();
-  orderIndex = prevOrder + 1 + ((nextOrder - prevOrder) / 2);
+  orderIndex = prevOrder + ((nextOrder - prevOrder) / 2);
 }
 
 //===----------------------------------------------------------------------===//
 // ilist_traits for Operation
 //===----------------------------------------------------------------------===//
 
 auto llvm::ilist_detail::SpecificNodeAccess<
     typename llvm::ilist_detail::compute_node_options<

mlir/unittests/IR/OperationSupportTest.cpp

 #include "mlir/IR/StandardTypes.h"
 #include "gtest/gtest.h"
 
 using namespace mlir;
 using namespace mlir::detail;
 
 static Operation *createOp(MLIRContext *context,
                            ArrayRef<Value> operands = llvm::None,
-                           ArrayRef<Type> resultTypes = llvm::None) {
+                           ArrayRef<Type> resultTypes = llvm::None,
+                           unsigned int numRegions = 0) {
   context->allowUnregisteredDialects();
   return Operation::create(UnknownLoc::get(context),
                            OperationName("foo.bar", context), resultTypes,
-                           operands, llvm::None, llvm::None, 0);
+                           operands, llvm::None, llvm::None, numRegions);
 }
 
 namespace {
 TEST(OperandStorageTest, NonResizable) {
   MLIRContext context(false);
   Builder builder(&context);
 
   Operation *useOp =
TEST(OperandStorageTest, MutableRange) {
   EXPECT_EQ(mutableOperands.size(), 0u);
   EXPECT_EQ(user->getNumOperands(), 0u);
 
   // Destroy the operations.
   user->destroy();
   useOp->destroy();
 }
 
+TEST(OperationOrderTest, OrderIsAlwaysValid) {
+  MLIRContext context(false);
+  Builder builder(&context);
+
+  Operation *containerOp =
+      createOp(&context, /*operands=*/llvm::None, /*resultTypes=*/llvm::None,
+               /*numRegions=*/1);
+  Region &region = containerOp->getRegion(0);
+  Block *block = new Block();
+  region.push_back(block);
+
+  // Insert two operations, then iteratively add more operations in the middle
+  // of them. Eventually we will insert more than kOrderStride operations and
+  // the block order will need to be recomputed.
+  Operation *frontOp = createOp(&context);
+  Operation *backOp = createOp(&context);
+  block->push_back(frontOp);
+  block->push_back(backOp);
+
+  // Chosen to be larger than Operation::kOrderStride.
+  int kNumOpsToInsert = 10;
+  for (int i = 0; i < kNumOpsToInsert; ++i) {
+    Operation *op = createOp(&context);
+    block->getOperations().insert(backOp->getIterator(), op);
+    ASSERT_TRUE(op->isBeforeInBlock(backOp));
+    // Note verifyOpOrder() returns false if the order is valid.
+    ASSERT_FALSE(block->verifyOpOrder());
+  }
+
+  containerOp->destroy();
+}
+
 } // end namespace