Avoid leak when parsing fails and BasicBlock has no use/function.

Associate BasicBlocks with the function being parsed to avoid leaks in the case of parse failures. Associating with the function means that we can no longer determine if defined/fwd declared simply by considering if a BasicBlock has an associated function, so track forward declared block references explicitly (this should also allow flagging multiple undeclared fwd references). Split out getting the named block from defining it, in the case of definition move the block to the end of the function.

Also destroy all forward reference placeholders in FunctionParser.

Return parse failure in parseAttributeDict if there is no left brace instead of
asserting.

PiperOrigin-RevId: 217049507

Various improvements to pattern matching and other infra:
 - Make it so OpPointer implicitly converts to SSAValue* when the underlying op
   has a single value.  This eliminates a lot more ->getResult() calls and makes
   the behavior more LLVM-like
 - Fill out PatternBenefit to be typed instead of just a typedef for int with
   magic numbers.
 - Simplify various code due to these changes.

PiperOrigin-RevId: 217020717

Add Operation Properties field to operations.

Start the OperationProperties, add no side-effect and commutative properties.

PiperOrigin-RevId: 217009199

Create private exclusive / single use affine computation slice for an op stmt.

- add util to create a private / exclusive / single use affine
  computation slice for an op stmt (see method doc comment); a single
  multi-result affine_apply op is prepended to the op stmt to provide all
  results needed for its operands as a function of loop iterators and symbols.
- use it for DMA pipelining (to create private slices for DMA start stmt's);
  resolve TODOs/feature request (b/117159533)
- move createComposedAffineApplyOp to Transforms/Utils; free it from taking a
  memref as input / generalize it.

PiperOrigin-RevId: 216926818

Implement a super sketched out pattern match/rewrite framework and a sketched
out canonicalization pass to drive it, and a simple (x-x) === 0 pattern match
as a test case.

There is a tremendous number of improvements that need to land, and the
matcher/rewriter and patterns will be split out of this file, but this is a
starting point.

PiperOrigin-RevId: 216788604

Create function builder wrapper to enable common interface for creating ops using either builder.

PiperOrigin-RevId: 216781727

Missed change - remove 1-d tag memref restriction while parsing DmaStartOp.

Fixing oversight from cl/216429885.

PiperOrigin-RevId: 216768516

Add MLFunction::walk/walkPostOrder methods for doing a simple traversal of
operations.  This is a simplified form for the existing walker API.

PiperOrigin-RevId: 216754991

Split BuiltinOps out of StandardOps.

* Move Return, Constant and AffineApply out into BuiltinOps;
* BuiltinOps are always registered, while StandardOps follow the same dynamic registration;
* Kept isValidX in MLValue as we don't have a verify on AffineMap so need to keep it callable from Parser (I wanted to move it to be called in verify instead);

PiperOrigin-RevId: 216592527

Add assert in Operation->printAssembly to check improperly created Op's.

We allow the name of an operation to be different from the name of the
'ConcreteType' op it was instantiated with. This can happen when you sub-class
an existing op and provide a getOperationName for it. Such a situation leads to
an assertion too deep and at a place seeminly unrelated, and typically when the
module is printed with the trace:

printOperation, printAssembly, Op::print, getOperand, dyn_cast<OperationStmt>,
isa. 'isa' will complain about being called on a null pointer, and the null
pointer actually comes from the getAs<> in printAssembly. This should have been
caught in printAssembly.

On another note, it is also weird that we allow setting the op's name to
something independent of the ConcreteType that op was instantiated with - so,
getAs<ConcreteType> will fail since ConcreteType::isClassFor won't succeed on
it.

PiperOrigin-RevId: 216580294

Simplify simplify functions as follow up on previous CL.

Addressing comment from post submit + simplifying the logic.

PiperOrigin-RevId: 216560688

Only simplify floor div, ceil div or mod if the rhs constant >= 1.

Else we hit asserts in MathExtras.

PiperOrigin-RevId: 216553595

[MLIR] IntegerSet value type

This CL applies the same pattern as AffineMap to IntegerSet: a simple struct
that acts as the storage is allocated in the bump pointer. The IntegerSet is
immutable and accessed everywhere by value.

Note that unlike AffineMap, it is not possible to remove the MLIRContext
parameter when constructing an IntegerSet for now. One possible way to achieve
this would be to add an enum to distinguish between the mathematically empty
set, the universe set and other sets.

This is left for future discussion.

PiperOrigin-RevId: 216545361

Add support to constant splat vector/tensor attribute.

This attribute represents a reference to a splat vector or tensor, where all
the elements have the same value. The syntax of the attribute is:

`splat<` (tensor-type | vector-type)`,` attribute-value `>`

PiperOrigin-RevId: 216537997

Change the representation of an operation name to be either an
AbstractOperation* or an Identifier.  This makes it possible to get to stuff in
AbstractOperation faster than going through a hash table lookup.  This makes
constant folding a bit faster now, but will become more important with
subsequent changes.

PiperOrigin-RevId: 216476772

Support `getShape`, `hasStaticShape` and `getDimSize` methods for all the Vector and Tensor Types.

PiperOrigin-RevId: 216447553

[MLIR] AffineMap value type

This CL applies the same pattern as AffineExpr to AffineMap: a simple struct
that acts as the storage is allocated in the bump pointer. The AffineMap is
immutable and accessed everywhere by value.

PiperOrigin-RevId: 216445930

Add target independent standard DMA ops: dma.start, dma.wait

Add target independent standard DMA ops: dma.start, dma.wait. Update pipeline
data transfer to use these to detect DMA ops.

While on this
- return failure from mlir-opt::performActions if a pass generates invalid output
- improve error message for verify 'n' operand traits

PiperOrigin-RevId: 216429885

Fix some leak and crash found via fuzzing.

Tried adding a fuzzer target (cl/216378253) and ran into a few problems, and fixing two of these.

PiperOrigin-RevId: 216425403

[MLIR] Sketch AffineExpr value type

This CL sketches what it takes for AffineExpr to fully have by-value semantics
and not be a not-so-smart pointer anymore.

This essentially makes the underyling class a simple storage struct and
implements the operations on the value type directly. Since there is no
forwarding of operations anymore, we can full isolate the storage class and
make a hard visibility barrier by moving detail::AffineExpr into
AffineExprDetail.h.

AffineExprDetail.h is only included where storage-related information is
needed.

PiperOrigin-RevId: 216385459

Address comments from previous CL/216216446

PiperOrigin-RevId: 216298139

[MLIR] AffineExpr final cleanups

This CL:
1. performs the global codemod AffineXExpr->AffineXExprClass and
AffineXExprRef -> AffineXExpr;
2. simplifies function calls by removing the redundant MLIRContext parameter;
3. adds missing binary operator versions of scalar op AffineExpr where it
makes sense.

PiperOrigin-RevId: 216242674

Affine map composition.
*) Implements AffineValueMap forward substitution for AffineApplyOps.
*) Adds ComposeAffineMaps transformation pass, which composes affine maps for all loads/stores in an MLFunction.
*) Adds multiple affine map composition tests.

PiperOrigin-RevId: 216216446

[MLIR] Cleanup AffineExpr

This CL introduces a series of cleanups for AffineExpr value types:
1. to make it clear that the value types should be used, the pointer
AffineExpr types are put in the detail namespace. Unfortunately, since the
value type operator-> only forwards to the underlying pointer type, we
still
need to expose this in the include file for now;
2. AffineExprKind is ok to use, it thus comes out of detail and thus of
AffineExpr
3. getAffineDimExpr, getAffineSymbolExpr, getAffineConstantExpr are
similarly
extracted as free functions and their naming is mande consistent across
Builder, MLContext and AffineExpr
4. AffineBinaryOpEx::simplify functions are made into static free
functions.
In particular it is moved away from AffineMap.cpp where it does not belong
5. operator AffineExprType is made explicit
6. uses the binary operators everywhere possible
7. drops the pointer usage everywhere outside of AffineExpr.cpp,
MLIRContext.cpp and AsmPrinter.cpp

PiperOrigin-RevId: 216207212

[MLIR] Value types for AffineXXXExpr

This CL makes AffineExprRef into a value type.

Notably:
1. drops llvm isa, cast, dyn_cast on pointer type and uses member functions on
the value type. It may be possible to still use classof  (in a followup CL)
2. AffineBaseExprRef aggressively casts constness away: if we mean the type is
immutable then let's jump in with both feet;
3. Drop implicit casts to the underlying pointer type because that always
results in surprising behavior and is not needed in practice once enough
cleanup has been applied.

The remaining negative I see is that we still need to mix operator. and
operator->. There is an ugly solution that forwards the methods but that ends
up duplicating the class hierarchy which I tried to avoid as much as
possible. But maybe it's not that bad anymore since AffineExpr.h would still
contain a single class hierarchy (the duplication would be impl detail in.cpp)

PiperOrigin-RevId: 216188003

Rename affineint type to index type.  The name 'index' may not be perfect, but is better than the old name.  Here is some justification:

1) affineint (as it is named) is not a type suitable for general computation (e.g. the multiply/adds in an integer matmul).  It has undefined width and is undefined on overflow.  They are used as the indices for forstmt because they are intended to be used as indexes inside the loop.

2) It can be used in both cfg and ml functions, and in cfg functions.  As you mention, “symbols” are not affine, and we use affineint values for symbols.

3) Integers aren’t affine, the algorithms applied to them can be. :)

4) The only suitable use for affineint in MLIR is for indexes and dimension sizes (i.e. the bounds of those indexes).

PiperOrigin-RevId: 216057974

Constant folding for loop bounds.

- Fold the lower/upper bound of a loop to a constant whenever the result of the
  application of the bound's affine map on the operand list yields a constant.

- Update/complete 'for' stmt's API to set lower/upper bounds with operands.
  Resolve TODOs for ForStmt::set{Lower,Upper}Bound.

- Moved AffineExprConstantFolder into AffineMap.cpp and added
  AffineMap::constantFold to be used by both AffineApplyOp and
  ForStmt::constantFoldBound.

PiperOrigin-RevId: 215997346

Fix opt build breakage - lib/Transforms/Utils.cpp

PiperOrigin-RevId: 215924308

Implement support for constant folding operations even when their operands are
not all constant.  Implement support for folding dim, x*0, and affine_apply.

PiperOrigin-RevId: 215917432

Introduce memref replacement/rewrite support: to replace an existing memref
with a new one (of a potentially different rank/shape) with an optional index
remapping.

- introduce Utils::replaceAllMemRefUsesWith
- use this for DMA double buffering

(This CL also adds a few temporary utilities / code that will be done away with
once:
1) abstract DMA op's are added
2) memref deferencing side-effect / trait is available on op's
3) b/117159533 is resolved (memref index computation slices).
PiperOrigin-RevId: 215831373

[RFC][MLIR] Use AffineExprRef in place of AffineExpr* in IR

This CL starts by replacing AffineExpr* with value-type AffineExprRef in a few
places in the IR. By a domino effect that is pretty telling of the
inconsistencies in the codebase, const is removed where it makes sense.

The rationale is that the decision was concisously made that unique'd types
have pointer semantics without const specifier. This is fine but we should be
consistent. In the end, the only logical invariant is that there should never
be such a thing as a const AffineExpr*, const AffineMap* or const IntegerSet*
in our codebase.

This CL takes a number of shortcuts to killing const with fire, in particular
forcing const AffineExprRef to return the underlying non-const
AffineExpr*. This will be removed once AffineExpr* has disappeared in
containers but for now such shortcuts allow a bit of sanity in this long quest
for cleanups.

The **only** places where const AffineExpr*, const AffineMap* or const
IntegerSet* may still appear is by transitive needs from containers,
comparison operators etc.

There is still one major thing remaining here: figure out why cast/dyn_cast
return me a const AffineXXX*, which in turn requires a bunch of ugly
const_casts. I suspect this is due to the classof
taking const AffineXXXExpr*. I wonder whether this is a side effect of 1., if
it is coming from llvm itself (I'd doubt it) or something else (clattner@?)

In light of this, the whole discussion about const makes total sense to me now
and I would systematically apply the rule that in the end, we should never
have any const XXX in our codebase for unique'd types (assuming we can remove
them all in containers and no additional constness constraint is added on us
from the outside world).

PiperOrigin-RevId: 215811554

[MLIR] Templated AffineExprBaseRef

This CL implements AffineExprBaseRef as a templated type to allow LLVM-style
casts to work properly. This also allows making AffineExprBaseRef::expr
private.

To achieve this, it is necessary to use llvm::simplify_type and make
AffineConstExpr derive from both AffineExpr and llvm::simplify<AffineExprRef>.
Note that llvm::simplify_type is just an interface to enable the proper
template resolution of isa/cast/dyn_cast but it otherwise holds no value.

Lastly note that certain dyn_cast operations wanted the const AffineExpr* form
of AffineExprBaseRef so I made the implicit constructor take that by default
and documented the immutable behavior. I think this is consistent with the
decision to make unique'd type immutable by convention and never use const on
them.

PiperOrigin-RevId: 215642247

[MLIR] Remove uses of AffineExpr* outside of IR

This CL uniformizes the uses of AffineExprWrap outside of IR.
The public API of AffineExpr builder is modified to only use AffineExprWrap.
A few places access AffineExprWrap.expr, this is only while the API is in
transition to easily keep track (i.e. make expr private and let the compiler
track the errors).

Parser.cpp exhibits patterns that are dependent on nullptr values so
converting it is left for another CL.

PiperOrigin-RevId: 215642005

[MLIR] AffineExpr lightweight value type for operators

This CL proposes adding MLIRContext* to AffineExpr as discussed previously.
This allows the value class to not require the context in its constructor and
makes it a POD that it makes sense to pass by value everywhere.
A list of other RFC CLs will build on this. The RFC CLs are small incremental
pushes of the API which would be a pretty big change otherwise.

Pushing the thinking a little bit more it seems reasonable to use implicit
cast/constructor to/from AffineExpr*.
As this thing evolves, it looks to me like IR (and
probably Parser, for not so good reasons) want to operate on AffineExpr* and
the rest of the code wants to operate on the value type.

For this reason I think AffineExprImpl*/AffineExpr may also make sense but I
do not have a particular naming preference.
The jury is still out for naming decision between the above and
AffineExprBase*/AffineExpr or AffineExpr*/AffineExprRef.

PiperOrigin-RevId: 215641596

[MLIR] Use chainable ligthweight wrapper for AffineExpr

This CL argues that the builder API for AffineExpr should be used
with a lightweight wrapper that supports operators chaining.
This CL takes the ill-named AffineExprWrap and proposes a simple
set of operators with builtin constant simplifications.

This allows:
1. removing the getAddMulPureAffineExpr function;
2. avoiding concerns about constant vs non-constant simplifications
at **every call site**;
3. writing the mathematical expressions we want to write without unnecessary
obfuscations.

The points above represent pure technical debt that we don't want to carry on.
It is important to realize that this is not a mere convenience or "just sugar"
but reduction in cognitive overhead.

This thinking can be pushed significantly further, I have added some comments
with some basic ideas but we could make AffineMap, AffineApply and other
objects that use map applications more functional and value-based.

I am putting this out to get a first batch of reviews and see what people
think.

I think in my preferred design I would have the Builder directly return such
AffineExprPtr objects by value everywhere and avoid the boilerplate explicit
creations that I am doing by hand at this point.

Yes this AffineExprPtr would implicitly convert to AffineExpr* because that is
what it is.

PiperOrigin-RevId: 215641317

Fix MLIR's floordiv, ceildiv, and mod for constant inputs (for negative lhs's)

- introduce mlir::{floorDiv, ceilDiv, mod} for constant inputs in
  mlir/Support/MathExtras.h
- consistently use these everywhere in IR, Analysis, and Transforms.

PiperOrigin-RevId: 215580677

Add support to Add, Sub, Mul for both Integer and Float types.

The new operations are registered and also the const folding of them are implemented.

PiperOrigin-RevId: 215575999

Introduce loop body skewing / loop pipelining / loop shifting utility.

- loopBodySkew shifts statements of a loop body by stmt-wise delays, and is
  typically meant to be used to:
  - allow overlap of non-blocking start/wait until completion operations with
    other computation
  - allow shifting of statements (for better register
    reuse/locality/parallelism)
  - software pipelining (when applied to the innermost loop)
- an additional argument specifies whether to unroll the prologue and epilogue.
- add method to check SSA dominance preservation.
- add a fake loop pipeline pass to test this utility.

Sample input/output are below. While on this, fix/add following:

- fix minor bug in getAddMulPureAffineExpr
- add additional builder methods for common affine map cases
- fix const_operand_iterator's for ForStmt, etc. When there is no such thing
  as 'const MLValue', the iterator shouldn't be returning const MLValue's.
  Returning MLValue is const correct.

Sample input/output examples:

1) Simplest case: shift second statement by one.

Input:

for %i = 0 to 7 {
  %y = "foo"(%i) : (affineint) -> affineint
  %x = "bar"(%i) : (affineint) -> affineint
}

Output:

#map0 = (d0) -> (d0 - 1)
mlfunc @loop_nest_simple1() {
  %c8 = constant 8 : affineint
  %c0 = constant 0 : affineint
  %0 = "foo"(%c0) : (affineint) -> affineint
  for %i0 = 1 to 7 {
    %1 = "foo"(%i0) : (affineint) -> affineint
    %2 = affine_apply #map0(%i0)
    %3 = "bar"(%2) : (affineint) -> affineint
  }
  %4 = affine_apply #map0(%c8)
  %5 = "bar"(%4) : (affineint) -> affineint
  return
}

2) DMA overlap: shift dma.wait and compute by one.

Input
  for %i = 0 to 7 {
    %pingpong = affine_apply (d0) -> (d0 mod 2) (%i)
    "dma.enqueue"(%pingpong) : (affineint) -> affineint
    %pongping = affine_apply (d0) -> (d0 mod 2) (%i)
    "dma.wait"(%pongping) : (affineint) -> affineint
    "compute1"(%pongping) : (affineint) -> affineint
  }

Output

#map0 = (d0) -> (d0 mod 2)
#map1 = (d0) -> (d0 - 1)
#map2 = ()[s0] -> (s0 + 7)
mlfunc @loop_nest_dma() {
  %c8 = constant 8 : affineint
  %c0 = constant 0 : affineint
  %0 = affine_apply #map0(%c0)
  %1 = "dma.enqueue"(%0) : (affineint) -> affineint
  for %i0 = 1 to 7 {
    %2 = affine_apply #map0(%i0)
    %3 = "dma.enqueue"(%2) : (affineint) -> affineint
    %4 = affine_apply #map1(%i0)
    %5 = affine_apply #map0(%4)
    %6 = "dma.wait"(%5) : (affineint) -> affineint
    %7 = "compute1"(%5) : (affineint) -> affineint
  }
  %8 = affine_apply #map1(%c8)
  %9 = affine_apply #map0(%8)
  %10 = "dma.wait"(%9) : (affineint) -> affineint
  %11 = "compute1"(%9) : (affineint) -> affineint
  return
}

3) With arbitrary affine bound maps:

Shift last two statements by two.

Input:

  for %i = %N to ()[s0] -> (s0 + 7)()[%N] {
    %y = "foo"(%i) : (affineint) -> affineint
    %x = "bar"(%i) : (affineint) -> affineint
    %z = "foo_bar"(%i) : (affineint) -> (affineint)
    "bar_foo"(%i) : (affineint) -> (affineint)
  }

Output

#map0 = ()[s0] -> (s0 + 1)
#map1 = ()[s0] -> (s0 + 2)
#map2 = ()[s0] -> (s0 + 7)
#map3 = (d0) -> (d0 - 2)
#map4 = ()[s0] -> (s0 + 8)
#map5 = ()[s0] -> (s0 + 9)

  for %i0 = %arg0 to #map0()[%arg0] {
    %0 = "foo"(%i0) : (affineint) -> affineint
    %1 = "bar"(%i0) : (affineint) -> affineint
  }
  for %i1 = #map1()[%arg0] to #map2()[%arg0] {
    %2 = "foo"(%i1) : (affineint) -> affineint
    %3 = "bar"(%i1) : (affineint) -> affineint
    %4 = affine_apply #map3(%i1)
    %5 = "foo_bar"(%4) : (affineint) -> affineint
    %6 = "bar_foo"(%4) : (affineint) -> affineint
  }
  for %i2 = #map4()[%arg0] to #map5()[%arg0] {
    %7 = affine_apply #map3(%i2)
    %8 = "foo_bar"(%7) : (affineint) -> affineint
    %9 = "bar_foo"(%7) : (affineint) -> affineint
  }

4) Shift one by zero, second by one, third by two

  for %i = 0 to 7 {
    %y = "foo"(%i) : (affineint) -> affineint
    %x = "bar"(%i) : (affineint) -> affineint
    %z = "foobar"(%i) : (affineint) -> affineint
  }

#map0 = (d0) -> (d0 - 1)
#map1 = (d0) -> (d0 - 2)
#map2 = ()[s0] -> (s0 + 7)

  %c9 = constant 9 : affineint
  %c8 = constant 8 : affineint
  %c1 = constant 1 : affineint
  %c0 = constant 0 : affineint
  %0 = "foo"(%c0) : (affineint) -> affineint
  %1 = "foo"(%c1) : (affineint) -> affineint
  %2 = affine_apply #map0(%c1)
  %3 = "bar"(%2) : (affineint) -> affineint
  for %i0 = 2 to 7 {
    %4 = "foo"(%i0) : (affineint) -> affineint
    %5 = affine_apply #map0(%i0)
    %6 = "bar"(%5) : (affineint) -> affineint
    %7 = affine_apply #map1(%i0)
    %8 = "foobar"(%7) : (affineint) -> affineint
  }
  %9 = affine_apply #map0(%c8)
  %10 = "bar"(%9) : (affineint) -> affineint
  %11 = affine_apply #map1(%c8)
  %12 = "foobar"(%11) : (affineint) -> affineint
  %13 = affine_apply #map1(%c9)
  %14 = "foobar"(%13) : (affineint) -> affineint

5) SSA dominance violated; no shifting if a shift is specified for the second
statement.

  for %i = 0 to 7 {
    %x = "foo"(%i) : (affineint) -> affineint
    "bar"(%x) : (affineint) -> affineint
  }

PiperOrigin-RevId: 214975731

Change loop step to be a positive integral constant

Changing this per discussion on mlir-team. Spec updated.

PiperOrigin-RevId: 214868483

Change behavior of loopUnrollFull with unroll factor 1

Using loopUnrollFull with unroll factor 1 should promote the loop body as
opposed to doing nothing.

PiperOrigin-RevId: 214812126

Add support for expected-warning and expected-note markers in mlir-opt -verify
mode.  We even diagnose mistakes nicely (aside from the a/an vowel confusion
which isn't worth worrying about):

test/IR/invalid.mlir split at line tensorflow/mlir#399:8:34: error: 'note' diagnostic emitted when expecting a 'error'
  %x = "bar"() : () -> i32    // expected-error {{operand defined here}}
                                 ^

PiperOrigin-RevId: 214773208

Add support to TF f32_ref type in MLIR

PiperOrigin-RevId: 214722005

Fix b/116749799, an issue where the ZeroResult trait's verifier hook left in an old
form.  Upgrade it, and move all the trait verifier implementations consistently
out of line to reduce template bloat.

PiperOrigin-RevId: 214718242

[MLIR] Add DimOp build support

This CL introduces basic support to build a DimOp as well as a standalone test.

PiperOrigin-RevId: 214688910

Rename OpBase -> Op.

PiperOrigin-RevId: 214676460

Use statement walker for constant folding.

- makes the code compact (gets rid of MLFunction walking logic)
- makes it natural to extend to fold affine map loop bounds
  and if conditions (upcoming CL)

PiperOrigin-RevId: 214668957

Introduce a new BinaryOp to commonize simple binary ops, introduce traits for
ResultIsFloatLike/ResultIsIntegerLike, move some code out of templates into
shared code, keep the ops in StandardOps.cpp/h sorted.

This significantly reduces the boilerplate for Add/Mul sorts of ops.  In a subsequent patch, I plan to rename OpBase to Op, but didn't want to clutter this diff.

PiperOrigin-RevId: 214622871

[MLIR] Fix AsmPrinter for short-hand bound notation

This CL retricts shorthand notation printing to only the bounds that can
be roundtripped unambiguously; i.e.:
1. ()[]->(%some_cst) ()[]
2. ()[s0]->(s0) ()[%some_symbol]

Upon inspection it turns out that the constant case was lossy so this CL also
updates it.

Note however that fixing this issue exhibits a potential issues in unroll.mlir.
L488 exhibits a map ()[s0] -> (1)()[%arg0] which could be simplified down to
()[]->(1)()[].
This does not seem like a bug but maybe an undesired complexity in the maps
generated by unrolling.
bondhugula@, care to take a look?

PiperOrigin-RevId: 214531410

[MLIR] Add support for MulFOp

This CL adds support for `mulf` which is necessary to write/emit a simple scalar
matmul in MLIR. This CL does not consider automation of generation of ops but
mulf is important and useful enough to be added on its own atm.

PiperOrigin-RevId: 214496098

Add MLIR (addf) -> MLIR HLO thin slice.

Super thin slice that can convert a MLIR program (with addfs) to MLIR HLO dialect. Add this as translations to mlir-translate. Also add hlo::AddOp op and HLO op registration.

PiperOrigin-RevId: 214480409

Adds constant folding hook for AffineApplyOp.

PiperOrigin-RevId: 214287780

[MLIR] Fix AsmPrinter.cpp for single ssa-id AffineMap

The AsmPrinter wrongly assumes that all single ssa-id AffineMap
are the identity map for the purpose of printing.
This CL adds the missing level of indirection as well as a test.

This bug was originally shaken off by the experimental TC->MLIR path.

Before this CL, the test would print:
```
mlfunc @mlfuncsimplemap(%arg0 : affineint, %arg1 : affineint, %arg2 : affineint) {
  for %i0 = 0 to %arg0 {
    for %i1 = 0 to %i0 {
                   ~~~   should be %arg1
      %c42_i32 = constant 42 : i32
    }
  }
  return
}
```

PiperOrigin-RevId: 214120817

Add op registry for registering MLIR ops.

Instead of linking in different initializeMLIRContext functions, add a registry mechanism and function to initialize all registered ops in a given MLIRContext. Initialize all registered ops along with the StandardOps when constructing a MLIRContext.

PiperOrigin-RevId: 214073842

Move the GraphTraits implementations for CFGs out to their own header,
consolidate the implementations in CFGFunctionViewGraph.cpp into it, and
implement the missing const specializations for functions.  NFC.

PiperOrigin-RevId: 214048649

Introduce [post]dominator tree and related infrastructure, use it in CFG func
verifier.  We get most of this infrastructure directly from LLVM, we just
need to adapt it to our CFG abstraction.

This has a few unrelated changes engangled in it:
 - getFunction() in various classes was const incorrect, fix it.
 - This moves Verifier.cpp to the analysis library, since Verifier depends on
   dominance and these are both really analyses.
 - IndexedAccessorIterator::reference was defined wrong, leading to really
   exciting template errors that were fun to diagnose.
 - This flips the boolean sense of the foldOperation() function in constant
   folding pass in response to previous patch feedback.

PiperOrigin-RevId: 214046593

Supports TF Complex64/Complex128 types in the tf/mlir roundtrip pass.

Alternatively, we can defined a TFComplexType with a width parameter in the
mlir, then both types can be converted to the same mlir type with different width (like IntegerType).
We chose to use a direct mapping because there are only two TF Complex types.

PiperOrigin-RevId: 213856651

Add verification for AllocOp.

PiperOrigin-RevId: 213829386

Implement support for constant folding operations and a simple constant folding
optimization pass:

 - Give the ability for operations to implement a constantFold hook (a simple
   one for single-result ops as well as general support for multi-result ops).
 - Implement folding support for constant and addf.
 - Implement support in AbstractOperation and Operation to make this usable by
   clients.
 - Implement a very simple constant folding pass that does top down folding on
   CFG and ML functions, with a testcase that exercises all the above stuff.

Random cleanups:
 - Improve the build APIs for ConstantOp.
 - Stop passing "-o -" to mlir-opt in the testsuite, since that is the default.

PiperOrigin-RevId: 213749809

Support TF Variant type in the tf/mlir roundtrip pass.

PiperOrigin-RevId: 213748573

Handle the TF resource data type in the TF/XLA roundtrip pass.

PiperOrigin-RevId: 213650346

Add missing verifier logic for addf, and fix b/116054838 - Parser crash handling alloc with no affine mappings.

PiperOrigin-RevId: 213639056

Add function attributes for ExtFunction, CFGFunction and MLFunction.

PiperOrigin-RevId: 213540509

Switch from positional argument to explicit flags for mlir-translate

This results in uniform behavior with mlir-opt. Exactly one transformation is allowed.

PiperOrigin-RevId: 213493415

Extend loop unroll/unroll-and-jam to affine bounds + refactor related code.

- extend loop unroll-jam similar to loop unroll for affine bounds
- extend both loop unroll/unroll-jam to deal with cleanup loop for non multiple
  of unroll factor.
- extend promotion of single iteration loops to work with affine bounds
- fix typo bugs in loop unroll
- refactor common code b/w loop unroll and loop unroll-jam
- move prototypes of non-pass transforms to LoopUtils.h
- add additional builder methods.
- introduce loopUnrollUpTo(factor) to unroll by either factor or trip count,
  whichever is less.
- remove Statement::isInnermost (not used for now - will come back at the right
  place/in right form later)

PiperOrigin-RevId: 213471227

Moving success/failure to Pass.

These should be methods on Pass instead of global members.

PiperOrigin-RevId: 213389032

Tool for translating from/to MLIR.

mlir-translate is a tool to translate from/to MLIR. The translations are registered at link time and intended for use in tests. An identity transformation (mlir-to-mlir) is registered by default as example and used in the parser test where simply parsing & printing required.

The TranslateFunctions take filenames (instead of MemoryBuffer) to allow translations special write behavior (e.g., writing to uncommon filesystems).

PiperOrigin-RevId: 213370448

Store 'then' clause statements directly in the 'if' statement.

Also a few minor changes.

PiperOrigin-RevId: 213359024

Misc changes to builder's and Transforms/ API to allow code generation.

- add builder method for ReturnOp
- expose API from Transforms/ to work on specific ML statements (do this for
  LoopUnroll, LoopUnrollAndJam)
- add MLFuncBuilder::getForStmtBodyBuilder, ::getBlock

PiperOrigin-RevId: 213074178

Add PassResult and have passes return PassResult to indicate failure/success.

For FunctionPass's for passes that want to stop upon error encountered.

PiperOrigin-RevId: 213058651

Change unranked tensor syntax from tensor<??f32> to tensor<*xf32> per
discussion on the list.

PiperOrigin-RevId: 212838226

Introduce pretty syntax for shape_cast as discussed on the list last week.

PiperOrigin-RevId: 212823681

Add misc builder convenience methods for AffineMap's, for statement's.

Use these methods to simplify existing code. Rename getConstantMap
getConstantAffineMap. Move declarations to group similar ones together.

PiperOrigin-RevId: 212814829

Extend getConstantTripCount to deal with a larger subset of loop bounds; make loop
unroll/unroll-and-jam more powerful; add additional affine expr builder methods

- use previously added analysis/simplification to infer multiple of unroll
  factor trip counts, making loop unroll/unroll-and-jam more general.

- for loop unroll, support bounds that are single result affine map's with the
  same set of operands. For unknown loop bounds, loop unroll will now work as
  long as trip count can be determined to be a multiple of unroll factor.

- extend getConstantTripCount to deal with single result affine map's with the
  same operands. move it to mlir/Analysis/LoopAnalysis.cpp

- add additional builder utility methods for affine expr arithmetic
  (difference, mod/floordiv/ceildiv w.r.t postitive constant). simplify code to
  use the utility methods.

- move affine analysis routines to AffineAnalysis.cpp/.h from
  AffineStructures.cpp/.h.

- Rename LoopUnrollJam to LoopUnrollAndJam to match class name.

- add an additional simplification for simplifyFloorDiv, simplifyCeilDiv

- Rename AffineMap::getNumOperands() getNumInputs: an affine map by itself does
  not have operands. Operands are passed to it through affine_apply, from loop
  bounds/if condition's, etc., operands are stored in the latter.

This should be sufficiently powerful for now as far as unroll/unroll-and-jam go for TPU
code generation, and can move to other analyses/transformations.

Loop nests like these are now unrolled without any cleanup loop being generated.

  for %i = 1 to 100 {
    // unroll factor 4: no cleanup loop will be generated.
    for %j = (d0) -> (d0) (%i) to (d0) -> (5*d0 + 3) (%i) {
      %x = "foo"(%j) : (affineint) -> i32
    }
  }

  for %i = 1 to 100 {
    // unroll factor 4: no cleanup loop will be generated.
    for %j = (d0) -> (d0) (%i) to (d0) -> (d0 - d mod 4 - 1) (%i) {
      %y = "foo"(%j) : (affineint) -> i32
    }
  }

  for %i = 1 to 100 {
    for %j = (d0) -> (d0) (%i) to (d0) -> (d0 + 128) (%i) {
      %x = "foo"() : () -> i32
    }
  }

TODO(bondhugula): extend this to LoopUnrollAndJam as well in the next CL (with minor
changes).

PiperOrigin-RevId: 212661212

Fix cast in AffineMap::getSingleConstantValue and rename to
getSingleConstantResult.

PiperOrigin-RevId: 212544394

Update error message for invalid operand token while parsing operand list.

Previously the error could mislead into thinking it was a parser bug instead of the input being erroneous. Update to make it clearer.

PiperOrigin-RevId: 212271145

rework the custom op verifier hooks to use the diagnostic emission
infrastructure, instead of returning a const char*.  This allows custom
formatting and more interesting diagnostics.

This patch regresses the error message quality from the control flow
lowering pass, I'll address this in a subsequent patch.

PiperOrigin-RevId: 212210681

Check for absence of delimiters when delimiters is None and fixed number of operands expected.

Ensure delimiters are absent where not expected. This is only checked in the case where operand count is known. This allows for the currently accepted case where there is a operand list with no delimiter and variable number of operands (which could be empty), followed by a delimited operand list.

PiperOrigin-RevId: 212202064

Return error status when number of operands don't match while parsing.

Previously an error would be emitted but parsing would continue as false was being returned.

PiperOrigin-RevId: 212192167

Change SourgeMgr to const reference in Parser/Lexer.

SourceMgr is not be mutated during parsing/lexing.

PiperOrigin-RevId: 212145759

Add utility to promote single iteration loops. Add methods for getting constant
loop counts. Improve / refactor loop unroll / loop unroll and jam.

- add utility to remove single iteration loops.
- use this utility to promote single iteration loops after unroll/unroll-and-jam
- use loopUnrollByFactor for loopUnrollFull and remove most of the latter.
- add methods for getting constant loop trip count

PiperOrigin-RevId: 212039569

Internal change.

PiperOrigin-RevId: 212018532

Add location specifier to MLIR Functions, and:
 - Compress the identifier/kind of a Function into a single word.
 - Eliminate otherFailure from verifier now that we always have a location
 - Eliminate the error string from the verifier now that we always have
   locations.
 - Simplify the parser's handling of fn forward references, using the location
   tracked by the function.

PiperOrigin-RevId: 211985101

Improve location reporting in the verifier for return instructions and other
terminators.  Improve mlir-opt to print better location info in the split-files
case.

Before:

error: unexpected error: branch has 2 operands, but target block has 1
  br bb1(%0tensorflow/mlir#1, %0tensorflow/mlir#0 : i17, i1)
  ^

after:

invalid.mlir split at line tensorflow/mlir#305:6:3: error: unexpected error: branch has 2 operands, but target block has 1
  br bb1(%0tensorflow/mlir#1, %0tensorflow/mlir#0 : i17, i1)
  ^

It still isn't optimal (it would be better to have just the original file and
line number but is a step forward, and doing the optimal thing would be a lot
more complicated.

PiperOrigin-RevId: 211917067

Teach RaiseControlFlow to handle IfOp's with partially infered shapes,
inserting shape_casts as necessary.

Along the way:
 - Add some missing accessors to the AtLeastNOperands trait.
 - Implement shape_cast / ShapeCastOp standard op.
 - Improve handling of errors in mlir-opt, making it easier to understand
   errors when invalid IR is rejected by the verifier.

PiperOrigin-RevId: 211897877

Several minor infra improvements:
 - Make the tf-lower-control flow handle error cases better.  Add a testcase
   that (currently) fails due to type mismatches.
 - Factor more code in the verifier for basic block argument checking, and
   check more invariants.
 - Fix a crasher in the asmprinter on null instructions (which only occurs on
   invalid code).
 - Fix a bug handling conditional branches with no block operands, it would
   access &operands[0] instead of using operands.data().
 - Enhance the mlir-opt driver to use the verifier() in a non-crashing mode,
   allowing issues to be reported as diagnostics.

PiperOrigin-RevId: 211818291

Implement getFunction() helpers on the various value types, and use it to
implement some simple checks in the Verifier.

PiperOrigin-RevId: 211729987

Fix opt build where compiled out assert leaves unused local variable.

PiperOrigin-RevId: 211631896

Add GraphTraits and DOTGraphTraits for CFGFunction in debug builds.

Enable using GraphWriter to dump graphviz in debug mode (kept to debug builds completely as this is only for debugging). Add option to mlir-opt to print CFGFunction after every transform in debug mode.

PiperOrigin-RevId: 211578699

Complete AffineExprFlattener based simplification for floordiv/ceildiv.

- handle floordiv/ceildiv in AffineExprFlattener; update the simplification to
  work even if mod/floordiv/ceildiv expressions appearing in the tree can't be eliminated.
- refactor the flattening / analysis to move it out of lib/Transforms/
- fix MutableAffineMap::isMultipleOf
- add AffineBinaryOpExpr:getAdd/getMul/... utility methods

PiperOrigin-RevId: 211540536

Add parseSourceString method to make it easy for clients to parse a string to a module.

PiperOrigin-RevId: 211354628

Continue revising diagnostic handling to simplify and generalize it, and improve related infra.
 - Add a new -verify mode to the mlir-opt tool that allows writing test cases
   for optimization and other passes that produce diagnostics.
 - Refactor existing the -check-parser-errors flag to mlir-opt into a new
   -split-input-file option which is orthogonal to -verify.
 - Eliminate the special error hook the parser maintained and use the standard
   MLIRContext's one instead.
 - Enhance the default MLIRContext error reporter to print file/line/col of
   errors when it is available.
 - Add new createChecked() methods to the builder that create ops and invoke
   the verify hook on them, use this to detected unhandled code in the
   RaiseControlFlow pass.
 - Teach mlir-opt about expected-error @+, it previously only worked with @-

PiperOrigin-RevId: 211305770

Fix the underlying cause for the asan test failure introduced by cl/210618122.

Restored the order of deleting then-clause before else-clause in if-statement destructor, since it does not and should not matter.

PiperOrigin-RevId: 211273720

Fix asan failure introduced by cl/210618122 and statement walker crash for if statements without else clause.

PiperOrigin-RevId: 211186361

Add builders for memory ops that did not have them (tested in forthcoming CL).

PiperOrigin-RevId: 211147994

Add support for iterating through uses to SSAValueImpl.
Note: I've tested this in a forth coming transformation pass CL that iterates through all uses, but do not have an associated unit test in this CL.

PiperOrigin-RevId: 211104365

Affine expression analysis and simplification.

Outside of IR/
- simplify a MutableAffineMap by flattening the affine expressions
- add a simplify affine expression pass that uses this analysis
- update the FlatAffineConstraints API (to be used in the next CL)

In IR:
- add isMultipleOf and getKnownGCD for AffineExpr, and make the in-IR
  simplication of simplifyMod simpler and more powerful.
- rename the AffineExpr visitor methods to distinguish b/w visiting and
  walking, and to simplify API names based on context.

The next CL will use some of these for the loop unrolling/unroll-jam to make
the detection for the need of cleanup loop powerful/non-trivial.

A future CL will finally move this simplification to FlatAffineConstraints to
make it more powerful. For eg., currently, even if a mod expr appearing in a
part of the expression tree can't be simplified, the whole thing won't be
simplified.

PiperOrigin-RevId: 211012256

Introduce loop unroll jam transformation.

- for test purposes, the unroll-jam pass unroll jams the first outermost loop.

While on this:
- fix StmtVisitor to allow overriding of function to iterate walk over children
  of a stmt.

PiperOrigin-RevId: 210644813

Implement operands for the 'if' statement.

This CL also includes two other minor changes:
- change the implemented syntax from 'if (cond)' to 'if cond', as specified by MLIR spec.
- a minor fix to the implementation of the ForStmt.

PiperOrigin-RevId: 210618122

Introduce a new Location abstraction to represent location data in a structured
(and more useful) way rather than hacking up a pile of attributes for it.  In
the future this will grow to represent inlined locations, fusion cases etc, but
for now we start with simple Unknown and File/Line/Col locations.  NFC.

PiperOrigin-RevId: 210485775

Avoid hardcoded 4096 constant

This commit creates a static constexpr limit for the IntegerType
bitwidth and uses it. The check had to be moved because Token is
not aware of IR/Type and it was a sign the abstraction leaked:
bitwidth limit is not a property of the Token but of the IntegerType.

Added a positive and a negative test at the limit.

PiperOrigin-RevId: 210388192