)]}'
{
  "commit": "29a925abb660104b413b15075b3a19793825f57e",
  "tree": "0b8d50b42dfd163d62eab48c36fbdb405324f2ed",
  "parents": [
    "2c31bc7c0455e2167dcaef6b284cb0574406fc72"
  ],
  "author": {
    "name": "Benjamin Maxwell",
    "email": "benjamin.maxwell@arm.com",
    "time": "Wed Jun 05 11:35:13 2024 +0100"
  },
  "committer": {
    "name": "GitHub",
    "email": "noreply@github.com",
    "time": "Wed Jun 05 11:35:13 2024 +0100"
  },
  "message": "[mlir][affine][Analysis] Add conservative bounds for semi-affine mods (#93576)\n\nThis patch adds support for computing bounds for semi-affine mod\r\nexpression to FlatLinearConstraints. This is then enabled within the\r\nScalableValueBoundsConstraintSet to allow computing the bounds of\r\nscalable remainder loops.\r\n\r\nE.g. computing the bound of something like:\r\n```\r\n// `1000 mod s0` is a semi-affine.\r\n#remainder_start_index \u003d affine_map\u003c()[s0] -\u003e (-(1000 mod s0) + 1000)\u003e\r\n#remaining_iterations \u003d affine_map\u003c(d0) -\u003e (-d0 + 1000)\u003e\r\n\r\n%0 \u003d affine.apply #remainder_start_index()[%c8_vscale]\r\nscf.for %i \u003d %0 to %c1000 step %c8_vscale {\r\n  %remaining_iterations \u003d affine.apply #remaining_iterations(%i)\r\n  // The upper bound for the remainder loop iterations should be:\r\n  // %c8_vscale - 1  (expressed as an affine map,\r\n  // affine_map\u003c()[s0] -\u003e (s0 * 8 - 1)\u003e, where s0 is vscale)\r\n  %bound \u003d \"test.reify_bound\"(%remaining_iterations) \u003c{scalable, ...}\u003e\r\n}\r\n```\r\n\r\nThere are caveats to this implementation. To be able to add a bound for\r\na `mod` we need to assume the rhs is positive (\u003e 0). This may not be\r\nknown when adding the bounds for the `mod` expression. So to handle this\r\na constraint is added for `rhs \u003e 0`, this may later be found not to hold\r\n(in which case the constraints set becomes empty/invalid).\r\n\r\nThis is not a problem for computing scalable bounds where it\u0027s safe to\r\nassume `s0` is vscale (or some positive multiple of it). But this may\r\nneed to be considered when enabling this feature elsewhere (to ensure\r\ncorrectness).",
  "tree_diff": [
    {
      "type": "modify",
      "old_id": "29c19442a7c7c3f948ed3133dac1e44958e45c20",
      "old_mode": 33188,
      "old_path": "mlir/include/mlir/Analysis/FlatLinearValueConstraints.h",
      "new_id": "cc6ab64b4b7d7784e29a3e61a9c0c20218c5afaf",
      "new_mode": 33188,
      "new_path": "mlir/include/mlir/Analysis/FlatLinearValueConstraints.h"
    },
    {
      "type": "modify",
      "old_id": "67a6581eb2fb4b3fe55a9f23032d46bbf89c2ca9",
      "old_mode": 33188,
      "old_path": "mlir/include/mlir/Dialect/Vector/IR/ScalableValueBoundsConstraintSet.h",
      "new_id": "93b3c92533c54f8cd32eeaaf6298c04ab41e48d6",
      "new_mode": 33188,
      "new_path": "mlir/include/mlir/Dialect/Vector/IR/ScalableValueBoundsConstraintSet.h"
    },
    {
      "type": "modify",
      "old_id": "27c49cd80018e9f4e329a5dade030ce6e062622e",
      "old_mode": 33188,
      "old_path": "mlir/include/mlir/IR/AffineExprVisitor.h",
      "new_id": "fc4cd915d8453861c83525067eb405778f3bd463",
      "new_mode": 33188,
      "new_path": "mlir/include/mlir/IR/AffineExprVisitor.h"
    },
    {
      "type": "modify",
      "old_id": "ac17ace5a976d2043fbe423ebb10449b775137a9",
      "old_mode": 33188,
      "old_path": "mlir/include/mlir/Interfaces/ValueBoundsOpInterface.h",
      "new_id": "337314143c80c257a60147670e22776758535719",
      "new_mode": 33188,
      "new_path": "mlir/include/mlir/Interfaces/ValueBoundsOpInterface.h"
    },
    {
      "type": "modify",
      "old_id": "8b38016d614980e854abf650d368c40e3b5636c4",
      "old_mode": 33188,
      "old_path": "mlir/lib/Analysis/FlatLinearValueConstraints.cpp",
      "new_id": "bf7e3121ea32a4da15cb124def2cd198ea0b1b89",
      "new_mode": 33188,
      "new_path": "mlir/lib/Analysis/FlatLinearValueConstraints.cpp"
    },
    {
      "type": "modify",
      "old_id": "f8df34843a36312f4af8a0457bb76e23ff194f3b",
      "old_mode": 33188,
      "old_path": "mlir/lib/Dialect/Vector/IR/ScalableValueBoundsConstraintSet.cpp",
      "new_id": "9c365376c84c9008b30705d3304b4be6cf4a5c73",
      "new_mode": 33188,
      "new_path": "mlir/lib/Dialect/Vector/IR/ScalableValueBoundsConstraintSet.cpp"
    },
    {
      "type": "modify",
      "old_id": "94562d0f15a24ac57afd5f0f7ebb391a02e37bcc",
      "old_mode": 33188,
      "old_path": "mlir/lib/IR/AffineExpr.cpp",
      "new_id": "5f2016470b25f6a3802869174c2cf42faef3b265",
      "new_mode": 33188,
      "new_path": "mlir/lib/IR/AffineExpr.cpp"
    },
    {
      "type": "modify",
      "old_id": "87937591e60ad856b2f0020bf56aaf457d6db8bc",
      "old_mode": 33188,
      "old_path": "mlir/lib/Interfaces/ValueBoundsOpInterface.cpp",
      "new_id": "6420c192b257d4986a388f132dc263ef2f6f8ca2",
      "new_mode": 33188,
      "new_path": "mlir/lib/Interfaces/ValueBoundsOpInterface.cpp"
    },
    {
      "type": "modify",
      "old_id": "d549c5bd1c3785d7f2e92c54156ccb22db406e92",
      "old_mode": 33188,
      "old_path": "mlir/test/Dialect/Vector/test-scalable-bounds.mlir",
      "new_id": "673e03f05c1b828247caee8eea3b9afd001b3321",
      "new_mode": 33188,
      "new_path": "mlir/test/Dialect/Vector/test-scalable-bounds.mlir"
    }
  ]
}