MEMO

Documentation Notes
^^^^^^^^^^^^^^^^^^^

- Need to clarify fundamental difference between constants baked into code
  and things that remain variable. (ISL parameters, symbolic shapes)

Things to consider
^^^^^^^^^^^^^^^^^^

- Dependencies are pointwise for shared loop dimensions
  and global over non-shared ones (between dependent and ancestor)

- multiple insns could fight over which iname gets local axis 0
  -> complicated optimization problem

- Every loop in loopy is opened at most once.
  Too restrictive?

- Why do precomputes necessarily have to duplicate the inames?
  -> because that would be necessary for a sequential prefetch

- Cannot do slab decomposition on inames that share a tag with
  other inames
  -> Is that reasonable?

- Entering a loop means:
  - setting up conditionals related to it (slabs/bounds)
  - allowing loops nested inside to depend on loop state

- Not using all hw loop dimensions causes an error, as
  is the case for variant 3 in the rank_one test.

- Measure efficiency of corner cases

- Loopy as a data model for implementing custom rewritings

- We won't generate WAW barrier-needing dependencies
  from one instruction to itself.

- Loopy is semi-interactive.

- Limitation: base index for parallel axes is 0.

- Dependency on order of operations is ill-formed

- Dependency on non-local global writes is ill-formed

- No substitution rules allowed on lhs of insns

To-do
^^^^^

- Kernel fusion

- when are link_inames, duplicate_inames safe?

- rename IndexTag -> InameTag

- Data implementation tags
  - turn base_indices into offset
  - vectorization
  - write_image()
  - change_arg_to_image (test!)

- Make tests run on GPUs

- Test array access with modulo

- Derive all errors from central hierarchy

- Provide context for more errors?

- Allow mixing computed and stored strides

Fixes:

- applied_iname_rewrites tracking for prefetch footprints isn't bulletproof
  old inames may still be around, so the rewrite may or may not have to be
  applied.

- Group instructions by dependency/inames for scheduling, to
  increase sched. scalability

- What if no universally valid precompute base index expression is found?
  (test_intel_matrix_mul with n = 6*16, e.g.?)

- If finding a maximum proves troublesome, move parameters into the domain

Future ideas
^^^^^^^^^^^^

- subtract_domain_lower_bound

- Storage sharing for temporaries?

- Kernel splitting (via what variables get computed in a kernel)

- Put all OpenCL functions into mangler

- Fuse: store/fetch elimination?

- Array language

- reg rolling

- When duplicating inames, use iname aliases to relieve burden on isl

- (Web) UI

- Check for unordered (no-dependency) writes to the same location

- Vanilla C string instructions?

- Barriers for data exchanged via global vars?

- Float4 joining on fetch/store?

- Better for loop bound generation
  -> Try a triangular loop

- Eliminate the first (pre-)barrier in a loop.

- Generate automatic test against sequential code.

- Reason about generated code, give user feedback on potential
  improvements.

- Convolutions, Stencils

- DMA engine threads?

- Try, fix indirect addressing

- Nested slab decomposition (in conjunction with conditional hoisting) could
  generate nested conditional code.

- Better code for strides.

Dealt with
^^^^^^^^^^

- How can one automatically generate something like microblocks?
  -> Some sort of axis-adding transform?

- RuleAwareIdentityMapper
  extract_subst -> needs WalkMapper [actually fine as is]
  padding [DONE]
  replace make_unique_var_name [DONE]
  join_inames [DONE]
  duplicate_inames [DONE]
  split_iname [DONE]
  CSE [DONE]

- rename iname

- delete unused inames

- Expose iname-duplicate-and-rename as a primitive.

- make sure simple side effects work

- Loop bounds currently may not depend on parallel dimensions
  Does it make sense to relax this?

- Streamline argument specification

- syntax for linear array access

- Test divisibility constraints

- Test join_inames

- Divisibility, modulo, strides?
  -> Tested, gives correct (but suboptimal) code.

- *_dimension -> *_iname

- Use gists (why do disjoint sets arise?)

- Automatically verify that all array access is within bounds.

- : (as in, Matlab full-slice) in prefetches

- Add dependencies after the fact

- Scalar insn priority

- ScalarArg is a bad name
  -> renamed to ValueArg

- What to do about constants in codegen? (...f suffix, complex types)
  -> dealt with by type contexts

- relating to Multi-Domain [DONE]
  - Reenable codegen sanity check. [DONE]

  - Incorporate loop-bound-mediated iname dependencies into domain
    parenthood. [DONE]

  - Make sure that variables that enter into loop bounds are only written
    exactly once. [DONE]

  - Make sure that loop bound writes are scheduled before the relevant
    loops. [DONE]

- add_prefetch tagging

- nbody GPU
  -> pending better prefetch spec
  - Prefetch by sample access

- How is intra-instruction ordering of ILP loops going to be determined?
  (taking into account that it could vary even per-instruction?)

- Sharing of checks across ILP instances

- Differentiate ilp.unr from ilp.seq

- Allow complex-valued arithmetic, despite CL's best efforts.

- "No schedule found" debug help:

  - Find longest dead-end
  - Automatically report on what hinders progress there

- CSE should be more like variable assignment

- Deal with equality constraints.
  (These arise, e.g., when partitioning a loop of length 16 into 16s.)

- dim_{min,max} caching

- Exhaust the search for a no-boost solution first, before looking
  for a schedule with boosts.

- Pick not just axis 0, but all axes by lowest available stride

- Scheduler tries too many boostability-related options

- Automatically generate testing code vs. sequential.

- If isl can prove that all operands are positive, may use '/' instead of
  'floor_div'.

- For forced workgroup sizes: check that at least one iname
  maps to them.

- variable shuffle detection
  -> will need unification

- Dimension joining

- user interface for dim length prescription

- Restrict-to-sequential and tagging have nothing to do with each other.
  -> Removed SequentialTag and turned it into a separate computed kernel
  property.

- Just touching a variable written to by a non-idempotent
  instruction makes that instruction also not idempotent
  -> Idempotent renamed to boostable.
  -> Done.

- Give the user control over which reduction inames are
  duplicated.

- assert dependencies <= parent_inames in loopy/__init__.py
  -> Yes, this must be the case.
  -> If you include reduction inames.

- Give a good error message if a parameter assignment in get_problems()
  is missing.

- Slab decomposition for ILP
  -> I don't think that's possible.

- It is hard to understand error messages that referred to instructions that
  are generated during preprocessing.

  -> Expose preprocessing to the user so she can inspect the preprocessed
     kernel.

- Which variables need to be duplicated for ILP?
  -> Only reduction

- implemented_domain may end up being smaller than requested in cse
  evaluations--check that!

- Allow prioritization of loops in scheduling.

- Make axpy better.

- Screwy lower bounds in slab decomposition

- reimplement add_prefetch

- Flag, exploit idempotence

- Some things involving CSEs might be impossible to schedule
  a[i,j] = cse(b[i]) * cse(c[j])

- Be smarter about automatic local axis choice
  -> What if we run out of axes?

- Implement condition hoisting
  (needed, e.g., by slab decomposition)

- Check for non-use of hardware axes

- Slab decomposition for parallel dimensions
  - implement at the outermost nesting level regardless
  - bound *all* tagged inames
  - can't slab inames that share tags with other inames (for now)

- Make syntax for iname dependencies

- make syntax for insn dependencies

- Implement get_problems()

- CSE iname duplication might be unnecessary?
  (don't think so: It might be desired to do a full fetch before a mxm k loop
  even if that requires going iterative.)

- Reduction needs to know a neutral element

- Types of reduction variables?

- Generalize reduction to be over multiple variables

- duplicate_dimensions can be implemented without having to muck around 
  with individual constraints:
  - add_dims
  - move_dims
  - intersect

Should a dependency on an iname be forced in a CSE?
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

Local var:

l  | n
g  | y
dl | Err
d  | Err

Private var:

l  | y
g  | y
dl | Err
d  | Err

dg: Invalid-> error

d: is duplicate
l: is tagged as local idx
g: is tagged as group idx

Raise error if dl is targeting a private variable, regardless of whether it's
a dependency or not.