{
	//commutative ops
	_add    <- 0
	_and    <- 1
	_or     <- 2
	_xor    <- 3
	//non-commutative ops
	_sub    <- 4
	_cmp    <- 5
	_not    <- 6
	_sl     <- 7
	_asr    <- 8
	_lsr    <- 9
	_rol    <- 10
	_ror    <- 11
	_mov    <- 12
	_call   <- 13
	_ret    <- 14
	_skipif <- 15
	_save   <- 16

	_names <- #[
		"add"
		"and"
		"or"
		"xor"
		"sub"
		"cmp"
		"not"
		"sl"
		"asr"
		"lsr"
		"rol"
		"ror"
		"mov"
		"call"
		"ret"
		"skipIf"
		"save"
	]

	op3:a:b:out:size <- :_opcode :_ina :_inb :_out :_size {
		#{
			opcode <- { _opcode }
			ina <- { _ina }
			inb <- { _inb }
			commutative? <- { _opcode < _sub }
			out <- { _out }
			size <- { _size }
			numops <- { 3 }
			name <- { _names get: _opcode }
			string <- { name . " " . (string: _ina) . " " . (string: _inb) . " " . (string: _out) . " " . (string: _size) }
			recordUsage:at <- :tracker :address {
				if: (not: (_ina isInteger?)) {
					_ina recordUsage: tracker at: 0 | address withSize: _size
				}
				_inb recordUsage: tracker at: 0 | address withSize: _size
				_out recordUsage: tracker at: 1 | address withSize: _size
			}
			assignRegs:at:withSource:andUsage <- :assignments :at :regSrc :usage {
				newa <- if: (not: (_ina isInteger?)) {
					_ina assign: assignments withSource: regSrc
				} else: { _ina }
				newb <- _inb assign: assignments withSource: regSrc
				newout <- _out assign: assignments withSource: regSrc
				op3: _opcode a: newa b: newb out: newout size: _size
			}
		}
	}
	op2:in:out:size <- :_opcode :_in :_out :_size {
		#{
			opcode <- { _opcode }
			in <- { _in }
			out <- { _out }
			size <- { _size }
			numops <- { 2 }
			name <- { _names get: _opcode }
			string <- { name . " " . (string: _in) . " " . (string: _out) . " " . (string: _size) }
			recordUsage:at <- :tracker :address {
				if: (not: (_in isInteger?)) {
					_in recordUsage: tracker at: 0 | address withSize: _size
				}
				_out recordUsage: tracker at: 1 | address withSize: _size
			}
			assignRegs:at:withSource:andUsage <- :assignments :at :regSrc :usage {
				newin <- if: (not: (_in isInteger?)) {
					_in assign: assignments withSource: regSrc
				} else: { _in }
				newout <- _out assign: assignments withSource: regSrc
				op2: _opcode in: newin out: newout size: _size
			}
		}
	}
	op1:arg:size <- :_opcode :_arg :_size {
		#{
			opcode <- { _opcode }
			arg <- { _arg }
			size <- { _size }
			numops <- { 1 }
			name <- { _names get: _opcode }
			string <- { name . " " . (string: _arg) . " " . (string: _size) }
			recordUsage:at <- :tracker :address {
				if: (not: (_arg isInteger?)) {
					_arg recordUsage: tracker at: address withSize: _size
				}
			}
			assignRegs:at:withSource:andUsage <- :assignments :at :regSrc :usage {
				newarg <- if: (not: (_arg isInteger?)) {
					_arg assign: assignments withSource: regSrc
				} else: { _arg }
				op1: _opcode arg: newarg size: _size
			}
		}
	}

	_sizenames <- #["b" "w" "l" "q"]
	_size <- :_bytes {
		#{
			bytes <- { _bytes }
			string <- {
				idx <- if: _bytes = 8 { 3 } else: { _bytes / 2}
				_sizenames get: idx
			}
			= <- :other {
				_bytes = (other bytes)
			}
			<= <- :other {
				_bytes <= (other bytes)
			}
			>= <- :other {
				_bytes >= (other bytes)
			}
			> <- :other {
				_bytes > (other bytes)
			}
			< <- :other {
				_bytes < (other bytes)
			}
		}
	}
	byte <- _size: 1
	word <- _size: 2
	long <- _size: 4
	quad <- _size: 8

	_retr <- #{
		isInteger? <- { false }
		register? <- { true }
		argument? <- { false }
		return? <- { true }
		string <- { "retr" }
		= <- :other {
			(not: (other isInteger?)) && (other register?) && (other return?)
		}
		!= <- :other {
			not: self = other
		}
		recordUsage:at:withSize <- :tracker :address :size {
			//TODO: Figure out what tracking is necessary here
		}
		assign:withSource <- :assignments :regSrc {
			regSrc allocRet
		}
	}

	_condnames <- #[
		"eq"
		"neq"
		"ge"
		"le"
		"gr"
		"ls"
		"uge"
		"ule"
		"ugr"
		"uls"
	]
	condition <- :num {
		#{
			cc <- { num }
			string <- { _condnames get: num }
			= <- :other { num = (other cc) }
		}
	}
	_eq <- condition: 0
	_neq <- condition: 1
	_ge <- condition: 2
	_le <- condition: 3
	_gr <- condition: 4
	_ls <- condition: 5
	_uge <- condition: 6
	_ule <- condition: 7
	_ugr <- condition: 8
	_uls <- condition: 9

	#{
		b <- { byte }
		w <- { word }
		l <- { long }
		q <- { quad }

		eq <- { _eq }
		neq <- { _neq }

		//signed conditions
		ge <- { _ge }
		le <- { _le }
		gr <- { _gr }
		ls <- { _ls }

		//unsigned conditions
		uge <- { _uge }
		ule <- { _ule }
		ugr <- { _ugr }
		uls <- { _uls }


		reg <- :num {
			#{
				isInteger? <- { false }
				register? <- { true }
				argument? <- { false }
				return? <- { false }
				regnum <- { num }
				string <- { "r" . (string: num) }
				= <- :other {
					(not: (other isInteger?)) && (other register?) && (not: (other argument?)) && (not: (other return?)) && num = (other regnum)
				}
				!= <- :other {
					not: self = other
				}
				recordUsage:at:withSize <- :tracker :address :size {
					tracker reg: self usedAt: address withSize: size
				}
				assign:withSource <- :assignments :regSrc {
					assignments get: self
				}
			}
		}
		arg <- :num {
			#{
				isInteger? <- { false }
				register? <- { true }
				argument? <- { true }
				return? <- { false }
				argnum <- { num }
				string <- { "a" . (string: num) }
				= <- :other {
					(not: (other isInteger?)) && (other register?) && (other argument?)  && num = (other regnum)
				}
				!= <- :other {
					not: self = other
				}
				recordUsage:at:withSize <- :tracker :address :size {
					tracker arg: self usedAt: address withSize: size
				}
				assign:withSource <- :assignments :regSrc {
					regSrc allocArg: num
				}
			}
		}
		retr <- { _retr }

		base:offset <- :_base :_offset {
			#{
				base <- { _base }
				offset <- { _offset }
				string <- {
					start <- if: _offset = 0 { "" } else: { (string: _offset) }
					start . "[" . (string: _base) . "]"
				}
				recordUsage:at:withSize <- :tracker :address :size {
					_base recordUsage: tracker at: address withSize: size
				}
			}
		}

		add <- :ina inb out size {
			op3: _add a: ina b: inb out: out size: size
		}

		sub <- :ina inb out size {
			op3: _sub a: ina b: inb out: out size: size
		}

		cmp <- :ina inb out size {
			op3: _cmp a: ina b: inb out: out size: size
		}

		and <- :ina inb out size {
			op3: _and a: ina b: inb out: out size: size
		}

		or <- :ina inb out size {
			op3: _or a: ina b: inb out: out size: size
		}

		xor <- :ina inb out size {
			op3: _xor a: ina b: inb out: out size: size
		}

		bnot <- :in out size {
			op2: _not in: in out: out size: size
		}

		sl <- :shift in out size {
			op3: _sl a: shift b: in out: out size: size
		}

		asr <- :shift in out size {
			op3: _asr a: shift b: in out: out size: size
		}

		lsr <- :shift in out size {
			op3: _lsr a: shift b: in out: out size: size
		}

		rol <- :rot in out size {
			op3: _rol a: rot b: in out: out size: size
		}

		ror <- :rot in out size {
			op3: _ror a: rot b: in out: out size: size
		}

		mov <- :in out size {
			op2: _mov in: in out: out size: size
		}

		call:withArgs <- :_target :_args {
			#{
				opcode <- { _call }
				target <- { _target }
				args <- { _args }
				numops <- { 0 }
				name <- { _names get: _call }
				string <- {
					argstr <- _args map: :el {
						string: el
					}
					name . " " . (string: _target) . " " . (argstr join: " ")
				}
				recordUsage:at <- :tracker :address {
					if: (not: (_target isString?)) {
						//TODO: use size l for 32-bit targets or an abstract pointer size
						_target recordUsage: tracker at: address withSize: q
					}
					foreach: _args :_ arg {
						//TODO: have some mechanism for properly expressing sizes of arguments
						arg recordUsage: tracker at: address withSize: q
					}
				}
				assignRegs:at:withSource:andUsage <- :assignments :address :regSrc :usage {
					newtarget <- if: (_target isString?) { _target } else: {
						_target assign: assignments withSource: regSrc
					}
					newargs <- _args map: :arg {
						if: (arg isInteger?) { arg } else: {
							arg assign: assignments withSource: regSrc
						}
					}
					newcall <- call: newtarget withArgs: newargs
					regSrc returnAll
					raddress <- address reverse
					foreach: (usage liveArgsAt: raddress) :_ arg {
						regSrc allocArg: (arg num)
					}
					foreach: (usage liveRegsAt: raddress) :_ reg {
						regSrc allocSpecific: (assignments get: reg)
					}
					tosave <- regSrc needSaveForCall
					if: (tosave length) > 0 {
						save: tosave #[newcall]
					} else: {
						newcall
					}
				}
			}
		}

		return <- :val size {
			op1: _ret arg: val size: size
		}
		skipIf <- :_cond _toskip {
			#{
				opcode <- { _skipif }
				toskip <- { _toskip }
				cond <- { _cond }
				numops <- { 0 }
				name <- { _names get: _skipif }
				string <- {
					block <- (_toskip map: :el { string: el }) join: "\n\t"
					if: (_toskip length) > 0 {
						block <- "\n\t" . block . "\n"
					}
					name . " " . (string: _cond) . " {" . block .  "}"
				}
				recordUsage:at <- :tracker :address {
					foreach: _toskip :idx inst {
						inst recordUsage: tracker at: idx | address
					}
				}
				assignRegs:at:withSource:andUsage <- :assignments :address :regSrc :usage {
					newskip <- #[]
					foreach: _toskip :idx inst {
						newskip append: (inst assignRegs: assignments at: idx | address  withSource: regSrc andUsage: usage)
					}
					skipIf: _cond newskip
				}
				to2OpInst <- {
					skipIf: _cond (to2Op: _toskip)
				}
			}
		}
		save <- :regs :_scope{
			#{
				opcode <- { _save }
				numops <- { 0 }
				name <- { _names get: _save }
				tosave <- { regs }
				scope <- { _scope }
				string <- {
					block <- _scope join: "\n\t"
					if: (_scope length) > 0 {
						block <- "\n\t" . block . "\n"
					}
					name . " " . (regs join: " ") . " {" . block . "}"
				}
				to2OpInst <- {
					save: regs (to2Op: _scope)
				}
			}
		}

		allocRegs:withSource <- :instarr:regSrc {
			_regMap <- dict linear
			_argMap <- dict linear

			_usageTracker <- :_firstUsage {
				#{
					firstUsage <- _firstUsage
					lastUsage <- _firstUsage
					useCount <- 0
					maxSize <- byte
					usedAt:withSize <- :address :size {
						useCount <- useCount + 1
						lastUsage <- address
						if: size > maxSize {
							maxSize <- size
						}
					}
					string <- {
						"Uses: " . useCount . ", FirstUse: " . (firstUsage join: ":") . ", Last Use: " . (lastUsage join: ":") . ", Max Size: " . maxSize
					}
				}
			}

			_maxUses <- 0
			liveFrom:to <- :regs :from :to {
				live <- #[]
				foreach: regs :reg usage {
					if: ((usage lastUsage) addrGreatEq: from) && ((usage firstUsage) addrLessEq: to) {
						live append: reg
					}
				}
				live
			}
			regUsage <- #{
				reg:usedAt:withSize <- :reg :address :size {
					raddress <- address reverse
					usage <- _regMap get: reg elseSet: {
						_usageTracker: raddress
					}
					usage usedAt: raddress withSize: size
					if: (usage useCount) > _maxUses {
						_maxUses <- usage useCount
					}
				}
				arg:usedAt:withSize <- :arg :address :size {
					raddress <- address reverse
					usage <- _argMap get: arg elseSet: {
						_usageTracker: [0 0]
					}
					usage usedAt: raddress withSize: size
				}

				liveRegsAt <- :address {
					_regMap liveFrom: address to: address
				}
				liveArgsAt <- :address {
					_argMap liveFrom: address to: address
				}

				print <- {
					foreach: _regMap :reg usage {
						print: (string: reg) . " | " . (string: usage) . "\n"
					}
					foreach: _argMap :arg usage {
						print: (string: arg) . " | " . (string: usage) . "\n"
					}
				}
			}
			foreach: instarr :idx inst {
				inst recordUsage: regUsage at: [idx]
			}
			print: regUsage

			addrLessEq <- :left :right {
				lesseq <- true
				while: { lesseq && (not: (left empty?)) && (not: (right empty?)) } do: {
					if: (left value) > (right value) {
						lesseq <- false
					} else: {
						if:  (left value) < (right value) {
							left <- []
						} else: {
							left <- left tail
							right <- right tail
						}
					}
				}
				lesseq
			}

			addrGreatEq <- :left :right {
				greateq <- true
				while: { greateq && (not: (left empty?)) && (not: (right empty?)) } do: {
					if: (left value) < (right value) {
						greateq <- false
					} else: {
						if:  (left value) > (right value) {
							left <- []
						} else: {
							left <- left tail
							right <- right tail
						}
					}
				}
				greateq
			}

			_assignments <- dict linear
			curuses <- _maxUses
			while: { curuses > 0 && (_assignments length) < (_regMap length) } do: {
				foreach: _regMap  :reg usage {
					if: (usage useCount) = curuses {
						liveArgs <- _argMap liveFrom: (usage firstUsage) to: (usage lastUsage)
						foreach: liveArgs :_ arg {
							regSrc allocArg: (arg num)
						}

						liveRegs <- _regMap liveFrom: (usage firstUsage) to: (usage lastUsage)
						print: (string: reg) . " | Live: " . (liveRegs join: ", ") . ", Live Args: " . (liveArgs join: ", ") . "\n"
						foreach: liveRegs :_ reg {
							if: (_assignments contains?: reg) {
								regSrc allocSpecific: (_assignments get: reg)
							}
						}
						_assignments set: reg (regSrc alloc: (usage maxSize))

						regSrc returnAll
					}
				}
				curuses <- curuses - 1
			}
			print: "\n\nAssignments:\n\n"
			foreach: _assignments :reg assign {
				print: (string: reg) . " = " . assign . "\n"
			}

			withassign <- #[]
			foreach: instarr :idx inst {
				withassign append: (inst assignRegs: _assignments at: [idx] withSource: regSrc andUsage: regUsage)
			}
			psave <- regSrc needSaveProlog
			if: (psave length) > 0 {
				withassign <- #[save: psave withassign]
			}
			withassign
		}

		//used to convert IL to a format suitable for a 2-operand architecture
		//should be run after register allocation (I think....)
		to2Op <- :instarr {
			instarr fold: #[] with: :newarr inst {
				if: (inst numops) = 3 {
					if: (inst inb) = (inst out) {
						newarr append: (op2: (inst opcode) in: (inst ina) out: (inst out) size: (inst size))
					} else: {
						if: (inst commutative?) && (inst ina) = (inst out) {
							newarr append: (op2: (inst opcode) in: (inst inb) out: (inst out) size: (inst size))
						} else: {
							newarr append: (mov: (inst inb) (inst out) (inst size))
							newarr append: (op2: (inst opcode) in: (inst ina) out: (inst out) size: (inst size))
						}
					}
				} else: {
					if: (inst numops) = 2 && (inst opcode) != _mov {
						if: (inst in) != (inst out) {
							newarr append: (mov: (inst in) (inst out) (inst size))
						}
						newarr append: (op1: (inst opcode) val: (inst out) size: (inst size))
					} else: {
						if: (inst opcode) = _skipif || (inst opcode) = _save {
							newarr append: (inst to2OpInst)
						} else: {
							newarr append: inst
						}
					}
				}
			}
		}

		toBackend <- :program :backend {
			prepped <- program map: :fun {
				backend adjustIL: fun
			}
			labels <- prepped map: :_ {
				backend label
			}
			outprog <- #[]
			foreach: prepped :name instarr {
				outprog append: (labels get: name)
				foreach: instarr :_ inst {
					backend convertIL: inst to: outprog withLabels: labels
				}
			}
			outprog
		}

		main <- {
			prog <- dict linear

			fib <- #[
				sub: 2 (arg: 0) (reg: 0) q
				skipIf: ge #[
					return: 1 q
				]
				call: "fib" withArgs: #[reg: 0]
				mov: retr (reg: 1) q
				add: 1 (reg: 0) (reg: 2) q
				call: "fib" withArgs: #[reg: 2]
				add: retr (reg: 1) (reg: 3) q
				return: (reg: 3) q
			]
			print: "Original:\n\n"
			foreach: fib :idx inst {
				print: (string: inst) . "\n"
			}
			prog set: "fib" fib

			mprog <- prog toBackend: x86
			ba <- bytearray executableFromBytes: mprog
			res <- ba runWithArg: 30u64
			print: (string: res) . "\n"
			0
		}
	}
}