// Returns a new tensor type with the shape transposed according to the
  // permutation. The rank of `type` and the size of `permutation` must be
  // equal.
  TensorType GetTransposedTensorType(
      const TensorType type, const ArrayRef<int64_t> permutation) const {
    const SmallVector<int64_t> after_shape =
        Permute<int64_t>(type.getShape(), permutation);
    return type.cloneWith(after_shape, type.getElementType());
  }
};

	permutation(t, h, []uint32{0, 1}, 20)
	permutation(t, h, []uint32{0, 1 << 31}, 20)
	permutation(t, h, []uint32{0, 1, 2, 3, 4, 5, 6, 7, 1 << 29, 2 << 29, 3 << 29, 4 << 29, 5 << 29, 6 << 29, 7 << 29}, 6)
}
func permutation(t *testing.T, h *hashSet, s []uint32, n int) {
	b := make([]byte, n*4)
	genPerm(h, b, s, 0)
	h.check(t)
}

    ],
)

cc_library(
    name = "permutation",
    hdrs = ["permutation.h"],
    compatible_with = get_compatible_with_portable(),
    deps = [
        "@llvm-project//llvm:Support",
        "@llvm-project//mlir:Support",
    ],
)

tf_cc_test(
    name = "permutation_test",
    srcs = ["permutation_test.cc"],
    deps = [
        ":permutation",
        "@com_google_googletest//:gtest_main",

		t.Skip("Too long for race mode")
	}
	testenv.ParallelOn64Bit(t)
	h := newHashSet()
	permutation(t, h, []uint32{0, 1, 2, 3, 4, 5, 6, 7}, 8)
	permutation(t, h, []uint32{0, 1 << 29, 2 << 29, 3 << 29, 4 << 29, 5 << 29, 6 << 29, 7 << 29}, 8)
	permutation(t, h, []uint32{0, 1}, 20)
	permutation(t, h, []uint32{0, 1 << 31}, 20)
	permutation(t, h, []uint32{0, 1, 2, 3, 4, 5, 6, 7, 1 << 29, 2 << 29, 3 << 29, 4 << 29, 5 << 29, 6 << 29, 7 << 29}, 6)
}

//
//  The update needs permuting to be in the form (a,b,d,e,f) so that the update
//  window dims are the trailing dimensions.
//
// To canonicalize the updates above, replace the updates with:
//   transpose(updates, permutation={3,4,0,1,2})
//
// Note: NormalizeIndexVector is assumed to have run on the indices already so
// that the index_vector_dim is the trailing dimension in `indices`.
LogicalResult CanonicalizeScatterUpdates(

    //       input_shape[M+1], ..., input_shape[N-1]]
    SmallVector<int64_t> permutation(reshaped_shape.size());
    permutation[0] = block_rank;
    for (int i = 0; i < block_rank; ++i) {
      permutation[1 + 2 * i] = block_rank + 1 + i;
      permutation[1 + 2 * i + 1] = i;
    }
    std::iota(permutation.begin() + 1 + block_rank * 2, permutation.end(),
              1 + block_rank * 2);

    if (!isKernelFormatHWOI(dnums)) {
      SmallVector<int64_t, 4> permutation;
      for (int64_t dim : dnums.getKernelSpatialDimensions()) {
        permutation.push_back(dim);
      }
      permutation.push_back(dnums.getKernelOutputFeatureDimension());
      permutation.push_back(dnums.getKernelInputFeatureDimension());

      auto filter_transposed = rewriter.create<mhlo::TransposeOp>(

      // Create a 1D I32 tensor for representing the dimension permutation.
      auto permuation_tensor_type =
          RankedTensorType::get({input_rank}, rewriter.getIntegerType(32));
      llvm::SmallVector<Attribute, 4> permute;
      permute.reserve(input_rank);
      // First create an identity permutation tensor.
      for (int i = 0; i < input_rank; i++) {

      redux_op);
}

TF::TransposeOp createTransposeOp(Value value, Location loc,
                                  llvm::ArrayRef<int32_t> permutation,
                                  PatternRewriter* rewriter) {
  auto perm_op = createI32ConstantOp(permutation, loc, rewriter);
  auto value_type = mlir::cast<RankedTensorType>(value.getType());
  auto shape = value_type.getShape();

          PushTransposeThroughEwisePass> {
 public:
  MLIR_DEFINE_EXPLICIT_INTERNAL_INLINE_TYPE_ID(PushTransposeThroughEwisePass)
  void runOnOperation() override;
};

// Compute the permutation that would take `arr` to the identity.
llvm::SmallVector<int32_t> InvertPermutation(llvm::SmallVector<int32_t> arr) {
  llvm::SmallVector<int32_t> inverse_arr(arr.size());
  for (int32_t i = 0; i < arr.size(); ++i) {