Add section of shape operatorsv0.90.0

Rework of the shape operations. Shape operations are now done in shape specific
operators rather than being based on type.

shape_t is reworked to a list of size_t values.

Signed-off-by: Eric Kunze <eric.kunze@arm.com>
Change-Id: I2fca0728f9caa6a6fc34a8ce9e389bb581eea959

5 files changed, 107 insertions, 26 deletions

diff --git a/chapters/data_layout.adoc b/chapters/data_layout.adoc
index 1ce92be..c6afc4f 100644
--- a/chapters/data_layout.adoc
+++ b/chapters/data_layout.adoc
@@ -35,7 +35,7 @@ include::{pseudocode}/operators/PAD.tosac[lines=10..-1]
 
 ==== DIM
 
-Returns a rank 0 tensor of the size of the input tensor for the given axis.
+Returns a length 1 shape_t of the size of the input tensor for the given axis.
 
 include::{generated}/operators/DIM.adoc[]
 
diff --git a/chapters/introduction.adoc b/chapters/introduction.adoc
index ae5c7b1..3922d13 100644
--- a/chapters/introduction.adoc
+++ b/chapters/introduction.adoc
@@ -415,27 +415,23 @@ Each element in the tensor shape describes the number of elements in the dimensi
 The tensor shape in each dimension must be greater than or equal to 1.
 For tensor access information, see <<Tensor Access Helpers>>.
 
-The shape of a tensor of non-zero rank is itself a tensor of rank 1 with elements of type shape_t.
-The single dimension has size which is the rank of the original tensor.
-In this specification a shape-tensor means a rank 1 tensor with elements of type shape_t.
-The components of a shape tensor are rank 0 tensors of type shape_t.
+The shape of a tensor of non-zero rank is a special type shape_t.
+shape_t is a one-dimensional list with the size equal to the rank of the original tensor.
+The components of a shape_t are of type size_t.
 
-Some operations can process rank 0 or rank 1 tensors of type shape_t.
-For these operations, shape_t is permitted as an input or output tensor data type.
 In this version of the specification, shape_t values must be resolvable to constants at backend compile time.
 
 ==== Tensor size limit
 
 The tensor overall size is limited by the data type size_t.
-This type must be able to hold integers in the range 0 to (1++<<++(MAX_LOG2_SIZE+1)) - 1 where MAX_LOG2_SIZE is defined in <<Levels>>.
-For each tensor, the number of tensor elements multiplied by the element size in bytes (which is taken to be 1 for elements smaller than a 8-bit) must be less than or equal to (1<<(MAX_LOG2_SIZE+1)) - 1.
+This type must be able to hold integers in the range 0 to (1 << (MAX_LOG2_SIZE + 1)) - 1 where MAX_LOG2_SIZE is defined in <<Levels>>.
+For each tensor, the number of tensor elements multiplied by the element size in bytes (which is taken to be 1 for elements smaller than a 8-bit) must be less than or equal to (1 << (MAX_LOG2_SIZE + 1)) - 1.
 
-The size of tensors along each of their dimensions is limited by the data type index_t.
-This type must be able to hold integers in the range 0 to (1++<<++MAX_LOG2_SIZE) - 1 where MAX_LOG2_SIZE is defined in <<Levels>>.
-This means that the maximum size of a tensor along each dimension is (1<<MAX_LOG2_SIZE) - 1 and therefore the maximum coordinate value is (1<<MAX_LOG2_SIZE) - 2.
+The size of tensors along each of their dimensions is limited by the data type size_t.
+
+This means that the maximum size of a tensor along each dimension is (1 << MAX_LOG2_SIZE) - 1 and therefore the maximum coordinate value is (1 << MAX_LOG2_SIZE) - 2.
 Indices used to access tensors must be non-negative.
 
-The type shape_t, used in shape tensors, must be able to hold integers in the range -(1++<<++MAX_LOG2_SIZE) to (1++<<++MAX_LOG2_SIZE) - 1.
 
 ==== Data Layouts
 
diff --git a/chapters/operators.adoc b/chapters/operators.adoc
index 698738f..d05ab08 100644
--- a/chapters/operators.adoc
+++ b/chapters/operators.adoc
@@ -1,7 +1,7 @@
 //
 // This confidential and proprietary software may be used only as
 // authorised by a licensing agreement from ARM Limited
-// (C) COPYRIGHT 2020-2021 ARM Limited
+// (C) COPYRIGHT 2020-2021,2024 ARM Limited
 // ALL RIGHTS RESERVED
 // The entire notice above must be reproduced on all authorised
 // copies and copies may only be made to the extent permitted
@@ -111,4 +111,6 @@ include::custom.adoc[]
 
 include::control_flow.adoc[]
 
-include::variable.adoc[]
\ No newline at end of file
+include::variable.adoc[]
+
+include::shape.adoc[]
\ No newline at end of file
diff --git a/chapters/pseudocode.adoc b/chapters/pseudocode.adoc
index 9e3b7bd..8954503 100644
--- a/chapters/pseudocode.adoc
+++ b/chapters/pseudocode.adoc
@@ -63,7 +63,7 @@ void LEVEL_CHECK(condition) {
 [source,c++]
 ----
 // Convert tensor index coordinates to an element offset
-size_t tensor_index_to_offset(dim_t shape, dim_t index) {
+size_t tensor_index_to_offset(shape_t shape, shape_t index) {
     size_t size = tensor_size(shape);  // check tensor shape is valid
     size_t offset = 0;
     for (int32_t i = 0; i < rank(shape); i++) {
@@ -74,10 +74,10 @@ size_t tensor_index_to_offset(dim_t shape, dim_t index) {
 }
 
 // Convert an element offset to tensor index coordinates
-dim_t tensor_offset_to_index(dim_t shape, size_t offset) {
+shape_t tensor_offset_to_index(shape_t shape, size_t offset) {
     size_t size = tensor_size(shape);  // check tensor shape is valid
     REQUIRE(offset < size);
-    dim_t index(rank(shape));    // index has rank(shape) indicies
+    shape_t index(rank(shape));    // index has rank(shape) indicies
     for(int32_t i = rank(shape) - 1; i >= 0; i--) {
         index[i] = offset % shape[i];
         offset /= shape[i];
@@ -86,7 +86,7 @@ dim_t tensor_offset_to_index(dim_t shape, size_t offset) {
 }
 
 // Check the tensor shape is valid and return the tensor size in elements
-size_t tensor_size(dim_t shape) {
+size_t tensor_size(shape_t shape) {
     size_t size = 1;
     for (int32_t i = 0; i < rank(shape); i++) {
         REQUIRE(1 <= shape[i] && shape[i] <= maximum<size_t> / size);
@@ -97,7 +97,7 @@ size_t tensor_size(dim_t shape) {
 
 // Return the size of the tensor in the given axis
 // For a rank=0 tensor, returns 1 for all axes
-size_t shape_dim(dim_t shape, int axis) {
+size_t shape_dim(shape_t shape, int axis) {
     return (axis >= rank(shape)) ? 1 : shape[axis];
 }
 ----
@@ -110,7 +110,7 @@ Index is the coordinates within the tensor of the value to be read.
 
 [source,c++]
 ----
-in_t tensor_read<in_t>(in_t *address, dim_t shape, dim_t index) {
+in_t tensor_read<in_t>(in_t *address, shape_t shape, shape_t index) {
     size_t offset = tensor_index_to_offset(shape, index);
     return address[offset];
 }
@@ -125,7 +125,7 @@ value is the value to be written to the given coordinate.
 
 [source,c++]
 ----
-void tensor_write<type>(<type> *address, dim_t shape, dim_t index, <type> value) {
+void tensor_write<type>(<type> *address, shape_t shape, shape_t index, <type> value) {
     size_t offset = tensor_index_to_offset(shape, index);
     address[offset] = value;
 }
@@ -139,7 +139,7 @@ The uid argument is a globally unique identifier for variable tensors.
 
 [source,c++]
 ----
-tensor_t* variable_tensor_allocate<in_t>(dim_t shape, int32_t uid) {
+tensor_t* variable_tensor_allocate<in_t>(shape_t shape, int32_t uid) {
     size_t size = tensor_size(shape);
     tensor_t *allocated_tensor = new tensor_t;
     allocated_tensor->data = new in_t[size];
@@ -176,9 +176,9 @@ The following function derives the broadcast output shape from the input shapes.
 
 [source,c++]
 ----
-dim_t broadcast_shape(dim_t shape1, dim_t shape2) {
+shape_t broadcast_shape(shape_t shape1, shape_t shape2) {
     ERROR_IF(rank(shape1) != rank(shape2));
-    dim_t shape = shape1;
+    shape_t shape = shape1;
     for (int32_t i = 0; i < rank(shape); i++) {
         if (shape[i] == 1) {
             shape[i] = shape2[i];
@@ -198,7 +198,7 @@ The following function maps an index in the output tensor to an index in the inp
 // The function returns the location within in_shape that contributes
 // to the output based on broadcasting rules.
 
-dim_t apply_broadcast(dim_t out_shape, dim_t in_shape, dim_t index) {
+shape_t apply_broadcast(shape_t out_shape, shape_t in_shape, shape_t index) {
     ERROR_IF(rank(out_shape) != rank(in_shape));
     ERROR_IF(rank(out_shape) != rank(index));
     for (int32_t i = 0; i < rank(out_shape); i++) {
diff --git a/chapters/shape.adoc b/chapters/shape.adoc
new file mode 100644
index 0000000..1b58465
--- /dev/null
+++ b/chapters/shape.adoc
@@ -0,0 +1,83 @@
+//
+// This confidential and proprietary software may be used only as
+// authorised by a licensing agreement from ARM Limited
+// (C) COPYRIGHT 2024 ARM Limited
+// ALL RIGHTS RESERVED
+// The entire notice above must be reproduced on all authorised
+// copies and copies may only be made to the extent permitted
+// by a licensing agreement from ARM Limited.
+
+=== Shape Operators
+
+The shape operators are operators which describe the shapes of parameters and the corresponding transformations.
+When tensor sizes are unknown, the relationship between sizes can be stored as a sequence of TOSA shape operations.
+At a later point when the shapes are provided, the shape operators are used to propagate shapes appropriately.
+After shape inference, the shape operators may be removed from the TOSA graph.
+
+Having separate shape operations allows easier tracking of shape propagation than would be possible by using the existing TOSA operators.
+
+==== ADD_SHAPE
+
+Elementwise addition of input1 and input2. Size of shapes must match.
+
+include::{generated}/operators/ADD_SHAPE.adoc[]
+
+[source,c++]
+----
+include::{pseudocode}/operators/ADD_SHAPE.tosac[lines=10..-1]
+----
+
+==== CONCAT_SHAPE
+
+Concatenates a list of shape_t to create a new shape_t with length the sum of lengths of all shape_t in input1.
+
+include::{generated}/operators/CONCAT_SHAPE.adoc[]
+
+[source,c++]
+----
+include::{pseudocode}/operators/CONCAT_SHAPE.tosac[lines=10..-1]
+----
+
+==== CONST_SHAPE
+
+A node containing a constant shape.
+
+include::{generated}/operators/CONST_SHAPE.adoc[]
+
+[source,c++]
+----
+include::{pseudocode}/operators/CONST_SHAPE.tosac[lines=10..-1]
+----
+
+==== DIV_SHAPE
+
+Elementwise integer divide of input1 by input2. The result of the divide is truncated towards zero.
+
+include::{generated}/operators/DIV_SHAPE.adoc[]
+
+[source,c++]
+----
+include::{pseudocode}/operators/DIV_SHAPE.tosac[lines=10..-1]
+----
+
+==== MUL_SHAPE
+
+Elementwise multiplication of input1 and input2.
+
+include::{generated}/operators/MUL_SHAPE.adoc[]
+
+[source,c++]
+----
+include::{pseudocode}/operators/MUL_SHAPE.tosac[lines=10..-1]
+----
+
+==== SUB_SHAPE
+
+Elementwise subtraction of input1 and input2.
+
+include::{generated}/operators/SUB_SHAPE.adoc[]
+
+[source,c++]
+----
+include::{pseudocode}/operators/SUB_SHAPE.tosac[lines=10..-1]
+----