# [RFC] Primitive Ops: add BroadcastOp to Linalg

## Context

[RFC] Primitive Ops: add MapOp, ReductionOp, TransposeOp, BroadcastOp to Linalg proposed adding new ops to Linalg dialect. There were still open questions about what BroadcastOp should look like. This document goes into concrete details how BroadcastOp can be implemented.

## Design

`linalg.broadcast`

is a static broadcast operation. There is no ambiguity at compile-time about shape information.

### Representation

The new op will have the following representation:

```
%bcast = linalg.broadcast
ins(%input:tensor<16xf32>)
inits(%init:tensor<16x64xf32>)
dimensions = [0]
optional-attrs
```

Each index in `dimensions`

attribute maps input dimension into the corresponding target dimension. The length of the `dimensions`

list should match the `input`

rank.

### Semantics

#### Dimensions attribute should be sorted

Which means that `linalg.broadcast`

does not support implicit transpose of the input. Broadcast ops from other dialects that support unsorted dimensions can be canonicalized by inserting an additional `linalg.transpose`

and then lowered to `linalg.broadcast`

.

### No size-1 expansion

In `linalg.broadcast`

all mapped dimensions should match.

The following IR is illegal:

```
%illegal_bcast = linalg.illegal_broadcast
ins(%input:tensor<16x1xf32>)
inits(%init:tensor<16x32x64xf32>)
dimensions = [0, 1]
```

Broadcast ops from other dialects can be canonicalized by removing size-1 dimensions with `tensor.collapse_shape`

. The previous example with have the equivalent form with

It can be canonicalized into an equivalent form without size-1 expansions:

```
%shaped_input = tensor.collapse_shape %input [[0, 1]] tensor<16x1xf32> into tensor<16xf32>
%illegal_bcast = linalg.broadcast
ins(%shaped_input:tensor<16xf32>)
inits(%init:tensor<16x32x64xf32>)
dimensions = [0]
```

It is permitted for mapped dimensions to be size 1 in both input and init. In that case `tensor.collapse_shape`

is not used to avoid unnecessary reshapes.