todo.txt

[Language]
- meta
	+ function template
	+ struct/union template
	+ #assert
	- macros (templated function that is inlined and can access inline scope/insert stuff into outer scope)
	- meta types
		+ $alias
		+ $type
		- $value
		- $code
		- #parameter
		- #function
	- # introspection
		- $allMembers(symbol) -> $alias[]
		- $getAttributes(symbol) -> $alias[]
		- $is* -> bool
		- get parameter list with access to name, type, attributes and default value
	- # attributes
		DOC: Declarations after an attribute may not begin with `(`. To disambiguate wrap whole attribute into () like `@(foo)`.
		+ #inline
			- replace with @inline(bool) attribute
		+- #ctfe (only inferred right now)
			- replace with @ctfe(bool) attribute
			- functions calling ctfe-only functions are not inferred as ctfe-only, and end up being compiled
			  For now built-in functions will have an address of special stub that asserts.
			  Ideally ctfe-only functions should not be compiled at all.
		- #likely
		- #unlikely
		- #likely_when(<expr>)
		- #dllimport(id)
	+ template parameter inference (for function templates) IFTI
		- only simple types
		- ifti of member functions needs to account for this parameter, because ifti is done before providing this arg
	+ variadic template arguments (requires inference)
	- alias tuple auto-expansion / manual expansion.
		+ auto tuple expansion in function call
	- a way to perform IFTI from user code (pass template args with names and runtime types and get)
	- #parameter(#type type, string name, type default_value, #alias[] attributes)
	- #function(string name, #type return_type, #parameter[] parameters, #alias[] attributes)
	- Need to print instance trace for errors inside template instance

- CTFE
	+ constant to mem
	- mem to constant
		+ basic type
	+ constructors
	- frame layout for CTFE
		+ register offsets
		- stack slot offsets
	+ control flow
	+ arithmetics (need to check signedness)
	+ call
	- force semantic analisys of function on call
	- move eval calls to semantic pass (Can only do ctfe at codegen time rn)

- conditional compilation
	+ #if
	+ #foreach
	+ #version
	- #debug

- named arguments for functions and struct/union construction
	https://github.com/dlang/DIPs/blob/master/DIPs/accepted/DIP1030.md
	+ basic function call with named args
	+ avoid picking static members of structs/unions
	- stuct/union initializer with named arguments
		- struct
		- union
	+ anonymous parameters should not be named in the call
	- interaction with variadic arguments
	+ interaction with default arguments
	+ through function pointer
	- named template arguments

[Functions]
- overloading (Odin has explicit overloading)

[Attributes]
+ @extern(syscall, <int>)
+ @extern(module, <module>)
- User Defined Attributes UDAs
+ @static
	+ @static variables in the function body
	+ @static variables in the struct
		+ don't add them to the IR type
		+ access via type name `S.staticMember`
		+ access via instance `s.staticMember`
		+ access from method `staticMember`
		+ access from method through this `this.staticMember`
	+ @static functions
		+ Call through instance `s.staticMethod()`
		+ Call through type name `S.staticMethod()`
		+ forbid access from @static methods to non-@static members
	+ forbid @static parameters
	- Calling static methods via `Type.method` syntax
	- struct constructor must ignore static members
- need to decide what to do when attribute is found before a statement that is not a declaration
- check that broadcasted attributes propagate into #version and #if #foreach

[Types]
- auto
	+ auto for variables in a function
+ integers
	+ + -
	+ pointer arithmetics
		+ add/sub int to ptr
		+ sub pointer of the same type
		+ compare pointers
		+ pre/post increment/decrement ptr
	+ unary -
	+ * / %
	+ <<, >>, >>>
	+ ~ | & ^
	+ op=
	+ v++ v-- ++v --v
	- check conversions to bool
+ void
	+ returning expression of type void from void function
- pointers
	+ taking address
	+ dereferencing
	+ indexing
	+ implicit conversion to bool
+ function pointer type <ret> function(<args>)
	+ call by pointer
	+ take address of function
	+ parameter names must be registered, so that they can be queried when resolving named arguments
	+ parameter names should not be visible in outside scope
	- check member variable func ptr
- char literal / type
	+ literal (for now generates int literal expression)
+ escape sequences in string/char literals (\n)
	can be emitted into IrGlobalStorage.initializerBuffer
	+ in char literals
	- Replace \r\n with \n inside string literals
+ float double
	+ windows ABI
	+ sysv ABI
	+ +-*/
		+ var op var
		- const op var
	+ unary minus
	+ < > <= >= == !=
	+ passing xmm args
	+ mixed type args
	+ structs with floats
	+ arrays
	+ load/store/push
	+ pass/receive floats on stack
	+ f32 <-> f64 casts
	+ int <-> float casts
		+ CTFE
	+ regalloc needs to only work with current register class
	+ constants
		+ zero
		+ non-zero
		+ constants as instruction arguments need to be lowered to movs
		- legalization in all instructions
			+ fadd, fsub, fdiv, fmul, branch_binary, set_binary_cond
			- call
			- unary
			- test branch legalization
	+ constant folding
	+ int literal to initialize float
	- CTFE
	- xchg
	+ save/restore of callee saved xmm registers need to have proper size
	- scratch spill slot is hardcoded to 64bits (maybe it is a good idea to take max of all sizes that is being put into the thing and update the size of the slot)
	- check how conversions to bool work
+ union
	- more testing of construction and access
	- named arg construction
- struct
	+ struct methods
		+ access from inside method
		+ access from static functions
	+ members
		+ access from method
		+ access from static functions
	+ struct literal
	+ UFCS functions
	+ return small complex structs
	+ lower aggregates in IR by replacing phis taking in aggregates with scalar phis. Only non-phi users must remain.
	+ detect all zero members and emit constantZero
	+ separate func_pass_lower_aggregates pass
	- empty structs need to be 1 byte in size
- array literal
- slices (need better structs)
	+ assign string literal
	+ access .ptr, .length
	+ indexing
	- pass literal to function
	+ slicing slice[0..42]
	+ slice ptr
		+ ptr[0..b] -> slice(b, ptr)
		+ ptr[a..b] -> slice(b-a, ptr+a)
	- slice assign: slice[] = 42; and slice[] = slice2;
	+ static array to slice (implicit conversion, slicing)
	- static array to slice (explicit conversion with [], slicing)
	- casting between slice types
		- void[] -> T[]
	- check conversion to bool
- ref 
	- ref parameters
	- ref in foreach
	- this is ref in methods (it is ptr atm)
+ enum
	- enum with bigger than i32 values doesn't compile
	- autoincrementing enum member values
	- enum type
	- Decide if enums should implicitly convert to bool. There are cases where you don't want that

- context format/writefln
+ pipeline ordering (run all passes per function) will allow to release temporary memory (worse perf if no memory is released)

- foreach
	- over slice
	- over static array
	- over numeric range a..b
	- over D style range

- member alias
+ switch
	- exhaustive switch (aka final switch)
	- switch over enum
	- test parsing errors
		- duplicate case
		- missing else
		- duplicate else

- multi-indexing operator x[1, 2, 3]
- in passes with state pass context separately
o dll linking
	- @dllimport("lz4.dll") attribute on externals
	- @dllimport("lz4.dll") attribute on module
		pros: only symbols from specific module will be searched in a dll
	- .def file passing
	+ .dll file passing
		cons: simple passing allows all module externals to be searched for in passed .dll/.def
		pros: --optname=modulename:.dll/.def allows for benefit of above options
	- custom .def-like format (binary, combine all libs description in a single file)
- constant folding << >> >>> shifts needs to know type of left operand to mask the shift size
- Check that constants on either side of every instruction is correctly lowered to mov/load when needed

[Built-ins]
+ sizeof
- offsetof
	+ works on non-static members
	+ errors on non-static members such as enum, alias, static memeber
	- incorrect error for method and static method


[CLI]
- -run option
- -i option (compile all imported files)
- stats about LoC compiled, time per entity


[Testing]
- test escape sequences
- test all implicit conversions
- test parsing errors
- test all integer size code gen
- signed to unsigned should use casts
- test bools
- test constant folding of all operators
- test mismatched number of args/params to call/constructor
- test declarations that have cyclic dependency (compiler must detect them through AstNode.state)
- test all expressions that compile with error being used inside other expressions (semantic check must correctly assign error type and check it when necessary)
- make sure that `this` is being used outside methods
- test that sections get correct offsets in executable
- split struct tests
- all comptime expressions that must evaluate to bool (#if, #assert etc), check what happens with struct, array, slice, string, float... Must have the same logic as regular if.
- all call variants
- check all expressions being used as a statement


[Backend]
- implement _chkstk and call it at the start of functions with frame size > 1 page
- Keep in mind the need for fat binaries / compilation for multiple targets at the same time
- after calling noreturn function compiler still goes to exit block. Maybe introduce a fake jump instruction to denote that. Can't remove exit block altogether, because liveness analysis/register allocation needs block ordering and goes over blocks in reverse. Blocks calling noreturn function must jump straight to exit block though. Exit block can be dropped in the far backend when it sees that all jumps to it are fake jumps. Or set a bit in basic block. Or replace return instruction with other instruction to store that info.


[ABI]
+ separate ABI lowering pass for win64
+ linux_x64_syscall ABI for linux syscalls. We can attach it with UDA to all external declarations of linux API.
+ Initial ELF64 support
	- Add import section support

[MacOS]
+ target
- write executable

[Error messages]
- in error on unexpected EOF show unterminated ([{ symbol
- Better not capitalize all error messages because parametrized messages need to account for it everywhere


[Debug info]
- Propagate loc through instructions
- Implement pdb format write/read
- Add DWARF output

[Linking / Static data / Globals]
- Absolute references need relocations emitted (ObjectSymbolRefKind.absolute64)
	CoffFlags.RELOCS_STRIPPED is set for now
	executables can work without relocations
	dlls require reloc table
	*- https://docs.microsoft.com/en-us/cpp/build/reference/dynamicbase-use-address-space-layout-randomization?view=vs-2019
	* https://github.com/bitcoin/bitcoin/issues/8248
- First arrange globals by alignment for tighter packing, then fill sections with data.
- Perform full reachability analisys before codegen runs to not generate unused symbols (functions)
+ Do not emit zero inited globals, only track them. Important for executables.
+ Implement zero initialized data section (at the end of rw section)
+ globals need to be initialized
x globals need to have IrIndex to initializer and coexist with raw data initializer (like for strings), or use aggregate constant that is optimized for byte arrays. Then produce actual bytes of data at machine code emission pass. This way backend can look at initializer.


[IR]
+ Consider storing vreg users in hash map instead of array. (Now uses multihashset)
- Allocate argument stack slots for multiple calls from the same space (for structs copies that are passed by ptr)
- IrBuilder must prevent adding instructions from wrong instruction set
- inline instructions in IR for representing memory operands in x86 LIR
- IrIndex: small pointer type when basic type is store inline + pointer level for more than 1 indirection level
+ stack layout per IrFunction (use alloca?)
x don't store self-reference arguments in phi functions (we cannot alter order of args now, must have same order as blockIndex.predecessors)
+ store virtual registers, phi functions with arguments in separate arenas
	vreg will shrink from 7 slots to 4 slots
	+ need array arena for IR with per-function slices
- make sure that blocks for splitting critical edges are inserted after successor
+ Remove IR instruction structs, use enum values directly in emitInstr
+ Automatically use zero initialization when possible
- Constants
	+ Zeroinitializer
	- Add constant kind that inits all elements of an array with the same value
	- expression constant (required for expressions involving link-time constants like global address)
	- pointer constants are represented as numeric constants which do not have type associated.
	  zeroinit however does have a type.
- Validate all instructions
+ use actual arrays for users instead of linked lists
- Figure out recursive type printing (Either use named types or use hashset to mark visited types)
- Handle cases where multiple predecessors are the same block: https://c9x.me/notes/2017-02-09.html


[Optimizations]
- optimize pointer arithmetic into lea
- optimize branches on constants. They can't be omitted in loop header, because value is behind phi function
- tail call
- Inlining
	+ IR inliner is done
	- Deciding when to inline is not implemented
	+ Stack slots need to be copied on inline
	- Inlining call that passes u8 constant, and inside u8 is zero extended doesn't compile
	  because zext of contant is not possible in amd64. This needs to be constant folded in later pass.
	  Make worklist or recursive constant folder.
	- Do not save registers before calling noreturn function: https://old.reddit.com/r/Compilers/comments/o9k92y/95_branch_prediction_accuracy/h3cmrov/
- Outlining ; cold/hot code separation ; branch prediction: https://old.reddit.com/r/Compilers/comments/o9k92y/95_branch_prediction_accuracy/
+ DCE exhibits O(n^2) behavior, because for each removed instruction (O(n)), we remove user from the vreg user list (O(n)). - Switched to multihashset.
- Loop alignment (https://kunalspathak.github.io/2021-03-15-Loop-Alignment)


[Register allocator]
+ Do liveness + RA together on each function
+ reg alloc performance regression 1.9s -> 6.2s (Probably due to not reusing liveness info) [fixed by reusing state across all functions]
+ store use arrays in liveness info
+ store fixed intervals separately from virtual register intervals while doing RA
+ reuse spill stack slot
+ move solver needed to disambiguate mov from load from stack slot, because stack slot can occur as phi argument
- allow src operands to be stack slots
	- differentiate uses that require value in a register and ones that dont
	  phi uses do not require register location for example
- select optimal split position
- spill at definition if there are multiple spill points / spilled intervals detected.
- Use array for unhandled list
- Add special machine description for testing RA
- Write RA test suite
- Stack parameters need to have cached stack slot
- optimize multiple spills into single spill at definition
- For stack to stack moves in move solver we always spill scratch register. Check if there is free register available.
+ Spilling into xmm registers
- For syscalls we need to extend eax liveness range. It requires either having eax as an argument of syscall, or always pass function type in the instruction.
- Add validation for the results of register allocator
- Instead of rewriting all uses to point to physical register introduce a special IrValueKind to denote an allocated virtual register. Then each virtual register will have an array of locations, each use uses one of the locations. Locations can also track the range of instructions that they cover. This info can later be used for debug info. Maybe spill stack slots can also point to virtual register location.


[Old / Done]
+ default arguments
+ mutable globals need their own read-write section
+ AST Index
+ improve parser to detect all declaration kinds in statements (add slice and static array)
+ check if right operand of << >> >>> is constant and pass it as is. Recognize constants in codegen
+ empty string
+ alias
	+ type aliases
	+ variable aliases
	+ function aliases
	+ enum member alias
	+ alias of alias
+ UFCS
	+ without parentesis
	+ with parentesis
	+ with parameters
+ function call without parentesis
+ constant folding of expressions in enum initializers and static array length
+ allow arbitrary expressions used as static array length
+ .min, .max properties of numeric types
+ static array type expr `i32[4].sizeof`
+ null to empty slice
+ for loop
+ function signature IR type (needed to allow changing signature for ABI handling in IR to LIR pass)
+ multiple exported functions per test
+ true, false
+ || && !
	+ ||
	+ &&
	+ !
+ appveyor build/test/release
+ test error cases
+ parse .har in test runner
+ split tests from test runner
+ negative literal type
+ exe tests time
+ null
+ nogc hashmap and array
+ array arena in compiler
+ HAR support: HAR - Human Archive Format: https://github.com/marler8997/har
+ HAR tests
+ small int literal in IR
+ use GEP in index expression
+ Lazy imports
+ AST Arena
+ modules
	+ multiple files in context
	+ compile all files
	+ imports
+ cmdline interface
+ separate lexing
+ array
+ GEP instruction
+ IR types (pointer, struct, array)
	+ alignment
	+ correct struct size
+ generate .exe
	+ detect entry point (main)
+ symbols with references in backend
	+ linking
+ cast(T) operator
+ split ast.d
+ int literal typing
	+ virtual reg types
	+ global types
+ struct
	+ type definition
	+ IR type gen
	+ var definition
	+ member read
	+ member write
	+ call conv
+ string (u8* done / need slices)
+ Pratt parser
+ VariableExprNode -> NameUseExprNode
+ add fixed interval for parameters in registers
+ static data buffer
+ static data IR index
x parse keywords as identifiers and identify them through interning (slower than switch)
+ while
+ fix stack pointer operations are on ESP instead of RSP
+ var decl inialization (parsing is done)
+ refactor into multiple files
+ new AST to IR pass for new IR
+ new IR
+ Unify all IR levels (IR and LIR)
+ LIR
+ IrRef no longer points to instruction / phi function. It points to virtual (or physical) register instead, and virt reg points to either instruction or phi function
+ unify Ref Id Index
+ use high-level branches instead of cmp + branch
+ no pointers in IR
x more space for parameters, opcodes, IrValueTypes
+ store/load
+ Reg allocation
	+ loops
	+ proper phi resolution (parallel moves)
	- spilling
	- more than 4 parameters
	+ function calls
	+ two address form
+ Live intervals
+ Remove redundant blocks (that contain only jmp)
+ Code gen
+ Instruction set for IR

+ variable declarations
+ types
arrays
+ basic blocks
+ break continue for loops

+ pointer