[compiler] Support the dynamic shape of StridedSlice

[shs-park]

What

Let's try to support dynamic shape inference for the StridedSlice operation.
The main goal of this work is to support models inference of dynamic shapes from #13697.

The below image is a part of some model we are looking into,
and the dimension marked with red circle can be dynamic.
like <1x18x?x80>.

Conditions

The StridedSlice operation cuts a portion of a tensor along a specific axis,
and since there are many cases, the implementation can be complicated.

In this issue, let's focus only when the following conditions are satisfied.

(I removed most of below conditions, because of #13932 (comment))

• begin is a constant (static)
• end is a constant (static)
• end
  • end is a constant (static), only if the input shape is all static
  • end is a input node, if any dimension of the input is dynamic
• stride is a constant and all the values are 1
• the input dimension of "axis" should NOT be dynamic, others can be dynamic

---

(Added)

Regardless of whether the input is static or dynamic,
if either begin or end is not constant,
the output of StridedSlice should be converted to dynamic shape.

This means all the dimensions should be ?.
i.e., if the input rank is 3, the shape of output will be <?x?x?>

---

Related from #13697

[shs-park]

Note

#13914 was the first DRAFT to support this.

[shs-park]

I'm going to try to create a similar but simpler model to replicate this scenario.
I'll share it with you when I'm done.
😅

[qsunki]

Does the "axis" in the sentence

the input dimension of axis is NOT dynamic

refers to the "axis" in the sentence below?

The StridedSlice operation cuts a portion of a tensor along a specific axis

[shs-park]

refers to the "axis" in the sentence below?

yes!

[shs-park]

I've modify this a little bit..

I found that if the dimension marked with the red circle is dynamic in #13932 (comment), the end of StridedSlice cannot be a constant.

The end needs to be a node with a variable, in order to properly represent the unknown full range of that dimension.

For example:

• Input shape: <Nx3x3>
• begin: [0, 0, 0] <3>
• end: [N, 3, 2] <3>
• stride: [1, 1, 1] <3>

In this case, the shape of the output should be <Nx3x2>.

However, since the end includes a variable N, it cannot be a constant.
Therefore, the end should be a circle node(not const).

---

Note: the notation of <> means shape, [ ] means value

[shs-park]

Conclusion

Regardless of whether the input is static or dynamic,
if either begin or end is not constant,
the output of StridedSlice should be converted to dynamic shape.

This means all the dimensions should be ?.
i.e., if the input rank is 3, <?x?x?>

[shs-park]

To-do

I made a test model for this.
Please find the below attached file.

Test Model: strided_slice.zip

$ ./onecc -C strided_slice_model_dynamic.cfg

Unzip and run above command, then you will get .circle and .opt.circle files.

Just like the Pad operation in this issue,
the output shape of optimized circle model is wrong (<1x1x1>).

This should be (<?x?x?>).

[qsunki]

When I tested this case with TensorFlow Lite,
Input shape: <Nx3x10>
begin: [0, 0, 0] <3>
end: [3, 3, 10] <3>
stride: [1, 1, 2] <3>

the results were as shown below.

Wouldn't it be okay to allow end to be a constant, with the appropriate inference logic?

[shs-park]

Wouldn't it be okay to allow end to be a constant, with the appropriate inference logic?

Oh, I mis-understood your question.
Sorry 😭

Yes, that's right.
But it's also correct that the dimension is ?.
The actual shape is going to be determined at runtime anyway, so it'll work fine.

It's up to you to decide what to do, but we usually follow the policy of leaving it as is in this case. 😅

[qsunki]

Conclusion

Regardless of whether the input is static or dynamic, if either begin or end is not constant, the output of StridedSlice should be converted to dynamic shape.

This means all the dimensions should be ?. i.e., if the input rank is 3, <?x?x?>

IMHO, In some cases, part of the output's dimensions can be determined.

Example 1: When the dimension of begin, end, or strides is smaller than the input's rank:
Input shape: <N1x3x3>
begin: [0, 0] <2>
end: [N2, N3] <2>
strides: [1, 1] <2>
output: <?x?x3>
The third dimension can be determined.

Example 2: When a new axis is added:
new_axis_mask=1
Input shape: <N1x3x3>
begin: [0, 0, 0] <3>
end: [N2, N3, N4] <3>
strides: [1, 1, 1] <3>
output: <1x?x?x?>
The added dimension can be determined.

[shs-park]

IMHO, In some cases, part of the output's dimensions can be determined.

@qsunki,

Yes, some dimensions can be calculated as you mentioned.

I think we should first implement the requirements in To-do and then think about this further.

FYI, in the optimization process, not only shape inference but also constant folding is performed, and in this process, the input and end could be determined as constants, so it is possible that the current inference code is already good enough.

For these detailed parts, it would be better to first proceed with the To-do requirement, then create a model corresponding to the actual test case you've mentioned, run it, and proceed further if there is a problem.

[glistening]

I made a test model for this. Please find the below attached file.

@Samsung/ssafy_2024 You can generate tflite using tflchef and existing recipes.

For StrideSlice,

• You can use several example recipes like StridedSlice_000/test.recipe
• Just modify a few bytes to -1.
• Then run tflchef (recipe → tflite)
• Then, run tflite2circle (tflite → circle)
• Check it is correct using netron.

[icodo98]

• Just modify a few bytes to -1.

I don't understand how to modify bytes in .recipe

I changed

operand {
  name: "ifm"
  type: FLOAT32
  shape { dim: 1 dim: 3 dim: 3 dim: 2 }
}

to

operand {
  name: "ifm"
  type: FLOAT32
  shape { dim: -1 dim: 3 dim: 3 dim: 2 }
}

then tflchef-file fails with Error parsing text-format tflchef.ModelRecipe: 4:16: Expected integer, got: - .

How can I make a recipe with dynamic shape?

[qsunki]

How can I make a recipe with dynamic shape?

try this.

  shape {
    dim: 0
    dim: 8
    dim: 0
    dim: 64
  }
  shape_signature {
    dim: -1
    dim: 8
    dim: -1
    dim: 64
  }

[glistening]

Error parsing text-format tflchef.ModelRecipe: 4:16: Expected integer, got: - .

I don't know the details of tflchef. ¹

Out of curiosity, I searched and found tflchef defined the schema as:

ONE/compiler/tflchef/proto/tflchef.proto

Lines 41 to 47 in 72349cc

	message TensorShape {
	repeated uint32 dim = 3;
	}
	message ShapeSignature {
	repeated int32 dim = 1;
	}

Please notice that uint32 for TensorShape, while ShapeSignature is defined as int32.

I didn't know this. My guide was based on circle schema.

circle schema says:

ONE/nnpackage/schema/circle_schema.fbs

Lines 224 to 228 in 72349cc

	table Tensor {
	// The tensor shape. The meaning of each entry is operator-specific but
	// builtin ops use: [batch size, height, width, number of channels] (That's
	// Tensorflow's NHWC).
	shape:[int];

It is the reason I said a few bytes.

Please modify a few lines as @qsunki wrote.

(Or you may edit a few bytes by editing circle directly using hex editor.)

Footnotes

1. Basically I am a runtime guy, not frontend. ↩