use std::collections::BTreeMap;
use std::fmt::{Error, Write};
use std::iter::zip;
use std::mem::transmute;
use std::sync::atomic::{AtomicUsize, Ordering};
use hercules_ir::*;
use crate::*;
static NUM_FILLER_REGS: AtomicUsize = AtomicUsize::new(0);
/*
* The top level function to compile a Hercules IR function into LLVM IR for
* execution on the CPU. We generate LLVM IR textually, since there are no good
* LLVM bindings for Rust, and we are *not* writing any C++.
*/
pub fn cpu_codegen<W: Write>(
module_name: &str,
function: &Function,
types: &Vec<Type>,
constants: &Vec<Constant>,
dynamic_constants: &Vec<DynamicConstant>,
typing: &Vec<TypeID>,
control_subgraph: &Subgraph,
bbs: &BasicBlocks,
backing_allocation: &FunctionBackingAllocation,
w: &mut W,
) -> Result<(), Error> {
let ctx = CPUContext {
module_name,
function,
types,
constants,
dynamic_constants,
typing,
control_subgraph,
bbs,
backing_allocation,
};
ctx.codegen_function(w)
}
struct CPUContext<'a> {
module_name: &'a str,
function: &'a Function,
types: &'a Vec<Type>,
constants: &'a Vec<Constant>,
dynamic_constants: &'a Vec<DynamicConstant>,
typing: &'a Vec<TypeID>,
control_subgraph: &'a Subgraph,
bbs: &'a BasicBlocks,
backing_allocation: &'a FunctionBackingAllocation,
}
#[derive(Default, Debug)]
struct LLVMBlock {
phis: String,
body: String,
term: String,
}
impl<'a> CPUContext<'a> {
fn codegen_function<W: Write>(&self, w: &mut W) -> Result<(), Error> {
// Dump the function signature.
if self.function.return_types.len() == 1 {
let return_type = self.function.return_types[0];
if self.types[return_type.idx()].is_primitive() {
write!(
w,
"define dso_local {} @{}_{}(",
self.get_type(return_type),
self.module_name,
self.function.name,
)?;
} else {
write!(
w,
"define dso_local nonnull noundef {} @{}_{}(",
self.get_type(return_type),
self.module_name,
self.function.name,
)?;
}
} else {
write!(
w,
"%return.{} = type {{ {} }}\n",
self.function.name,
self.function
.return_types
.iter()
.map(|t| self.get_type(*t))
.collect::<Vec<_>>()
.join(", "),
)?;
write!(
w,
"define dso_local void @{}_{}(",
self.module_name, self.function.name,
)?;
}
let mut first_param = true;
// The first parameter is a pointer to CPU backing memory, if it's
// needed.
if self.backing_allocation.contains_key(&Device::LLVM) {
first_param = false;
write!(w, "ptr %backing")?;
}
// The second set of parameters are dynamic constants.
for idx in 0..self.function.num_dynamic_constants {
if first_param {
first_param = false;
} else {
write!(w, ", ")?;
}
write!(w, "i64 %dc_p{}", idx)?;
}
// The third set of parameters are normal parameters.
for (idx, ty) in self.function.param_types.iter().enumerate() {
if first_param {
first_param = false;
} else {
write!(w, ", ")?;
}
if self.types[ty.idx()].is_primitive() {
write!(w, "{} %p{}", self.get_type(*ty), idx)?;
} else {
write!(
w,
"{} noalias nofree nonnull noundef align({}) %p{}",
self.get_type(*ty),
get_type_alignment(&self.types, *ty),
idx
)?;
}
}
// Lastly, if the function has multiple returns, is a pointer to the return struct
if self.function.return_types.len() != 1 {
if !first_param {
write!(w, ", ")?;
}
write!(
w,
"ptr noalias nofree nonnull noundef sret(%return.{}) %ret.ptr",
self.function.name,
)?;
}
write!(w, ") {{\n")?;
let mut blocks: BTreeMap<_, _> = (0..self.function.nodes.len())
.filter(|idx| self.function.nodes[*idx].is_control())
.map(|idx| (NodeID::new(idx), LLVMBlock::default()))
.collect();
// Emit calculation of dynamic constants into the start block. Calculate
// every valid dynamic constant, and let LLVM clean them up.
self.codegen_dynamic_constants(
blocks.get_mut(&NodeID::new(0)).unwrap(),
self.function.num_dynamic_constants,
)?;
// Emit data flow into basic blocks.
for block in self.bbs.1.iter() {
for id in block {
self.codegen_data_node(*id, &mut blocks)?;
}
}
// Emit control flow into basic blocks.
for id in (0..self.function.nodes.len()).map(NodeID::new) {
if !self.function.nodes[id.idx()].is_control() {
continue;
}
self.codegen_control_node(id, &mut blocks)?;
}
// Dump the emitted basic blocks.
for (id, block) in blocks {
write!(
w,
"{}:\n{}{}{}",
self.get_block_name(id),
block.phis,
block.body,
block.term
)?;
}
write!(w, "}}\n")?;
Ok(())
}
/*
* While control nodes in Hercules IR are predecessor-centric (each take a
* control input that defines the predecessor relationship), LLVM IR basic
* blocks are successor centric (each branch to successor blocks with a
* branch instruction). This difference requires explicit translation.
*/
fn codegen_control_node(
&self,
id: NodeID,
blocks: &mut BTreeMap<NodeID, LLVMBlock>,
) -> Result<(), Error> {
match self.function.nodes[id.idx()] {
// Start, region, and projection control nodes all have exactly one
// successor and are otherwise simple.
Node::Start
| Node::Region { preds: _ }
| Node::ControlProjection {
control: _,
selection: _,
} => {
let term = &mut blocks.get_mut(&id).unwrap().term;
let succ = self.control_subgraph.succs(id).next().unwrap();
write!(term, " br label %{}\n", self.get_block_name(succ))?
}
// If nodes have two successors - examine the projections to
// determine which branch is which, and branch between them.
Node::If { control: _, cond } => {
let term = &mut blocks.get_mut(&id).unwrap().term;
let mut succs = self.control_subgraph.succs(id);
let succ1 = succs.next().unwrap();
let succ2 = succs.next().unwrap();
let succ1_is_true = self.function.nodes[succ1.idx()]
.try_control_projection(1)
.is_some();
write!(
term,
" br {}, label %{}, label %{}\n",
self.get_value(cond, true),
self.get_block_name(if succ1_is_true { succ1 } else { succ2 }),
self.get_block_name(if succ1_is_true { succ2 } else { succ1 }),
)?
}
Node::Return {
control: _,
ref data,
} => {
if data.len() == 1 {
let ret_data = data[0];
let term = &mut blocks.get_mut(&id).unwrap().term;
write!(term, " ret {}\n", self.get_value(ret_data, true))?
} else {
let term = &mut blocks.get_mut(&id).unwrap().term;
// Generate gep and stores into the output pointer
for (idx, val) in data.iter().enumerate() {
write!(
term,
" %ret_ptr.{} = getelementptr inbounds %return.{}, ptr %ret.ptr, i32 0, i32 {}\n",
idx,
self.function.name,
idx,
)?;
write!(
term,
" store {}, ptr %ret_ptr.{}\n",
self.get_value(*val, true),
idx,
)?;
}
// Finally return void
write!(term, " ret void\n")?
}
}
_ => panic!(
"PANIC: Can't lower {:?} in {}.",
self.function.nodes[id.idx()],
self.function.name
),
}
Ok(())
}
/*
* Lower data nodes in Hercules IR into LLVM instructions.
*/
fn codegen_data_node(
&self,
id: NodeID,
blocks: &mut BTreeMap<NodeID, LLVMBlock>,
) -> Result<(), Error> {
match self.function.nodes[id.idx()] {
Node::Phi { control, ref data } => {
let phis = &mut blocks.get_mut(&self.bbs.0[id.idx()]).unwrap().phis;
let preds = self.function.nodes[control.idx()].try_region().unwrap();
write!(
phis,
" {} = phi {} ",
self.get_value(id, false),
self.get_type(self.typing[id.idx()])
)?;
for idx in 0..preds.len() {
if idx != 0 {
write!(phis, ", ")?;
}
write!(
phis,
"[ {}, %{} ]",
self.get_value(data[idx], false),
self.get_block_name(preds[idx])
)?;
}
write!(phis, "\n")?;
}
Node::Parameter { index } => {
let body = &mut blocks.get_mut(&self.bbs.0[id.idx()]).unwrap().body;
let ty = self.get_type(self.typing[id.idx()]);
write!(
body,
" {} = bitcast {} %p{} to {}\n",
self.get_value(id, false),
ty,
index,
ty
)?;
}
Node::Constant { id: cons_id } => {
let body = &mut blocks.get_mut(&self.bbs.0[id.idx()]).unwrap().body;
if self.constants[cons_id.idx()].is_scalar() {
write!(body, " {} = bitcast ", self.get_value(id, false))?;
match self.constants[cons_id.idx()] {
Constant::Boolean(val) => write!(body, "i1 {} to i1\n", val)?,
Constant::Integer8(val) => write!(body, "i8 {} to i8\n", val)?,
Constant::Integer16(val) => write!(body, "i16 {} to i16\n", val)?,
Constant::Integer32(val) => write!(body, "i32 {} to i32\n", val)?,
Constant::Integer64(val) => write!(body, "i64 {} to i64\n", val)?,
Constant::UnsignedInteger8(val) => write!(body, "i8 {} to i8\n", val)?,
Constant::UnsignedInteger16(val) => write!(body, "i16 {} to i16\n", val)?,
Constant::UnsignedInteger32(val) => write!(body, "i32 {} to i32\n", val)?,
Constant::UnsignedInteger64(val) => write!(body, "i64 {} to i64\n", val)?,
Constant::Float32(val) => {
write!(body, "float 0x{:016x} to float\n", unsafe {
transmute::<f64, u64>(*val as f64)
})?;
}
Constant::Float64(val) => {
write!(body, "float 0x{:016x} to float\n", unsafe {
transmute::<f64, u64>(*val)
})?;
}
_ => unreachable!(),
}
} else {
let (_, offsets) = &self.backing_allocation[&Device::LLVM];
let offset = offsets[&id].0;
write!(
body,
" {} = getelementptr i8, ptr %backing, i64 %dc{}\n",
self.get_value(id, false),
offset.idx()
)?;
if !self.function.schedules[id.idx()].contains(&Schedule::NoResetConstant) {
let data_size = self.codegen_type_size(self.typing[id.idx()], body)?;
write!(
body,
" call void @llvm.memset.p0.i64({}, i8 0, i64 {}, i1 false)\n",
self.get_value(id, true),
data_size,
)?;
}
}
}
Node::DynamicConstant { id: dc_id } => {
let body = &mut blocks.get_mut(&self.bbs.0[id.idx()]).unwrap().body;
// Dynamic constants are all pre-calculated at the top of the
// function.
write!(
body,
" {} = bitcast i64 %dc{} to i64\n",
self.get_value(id, false),
dc_id.idx()
)?
}
Node::Unary { op, input } => {
let body = &mut blocks.get_mut(&self.bbs.0[id.idx()]).unwrap().body;
match op {
UnaryOperator::Not => write!(
body,
" {} = xor {}, -1\n",
self.get_value(id, false),
self.get_value(input, true)
)?,
UnaryOperator::Neg => {
if self.types[self.typing[input.idx()].idx()].is_float() {
write!(
body,
" {} = fneg {}",
self.get_value(id, false),
self.get_value(input, true)
)?
} else {
write!(
body,
" {} = mul {}, -1",
self.get_value(id, false),
self.get_value(input, true)
)?
}
}
UnaryOperator::Cast(dst_ty_id) => {
let src_ty_id = self.typing[input.idx()];
let dst_ty = &self.types[dst_ty_id.idx()];
let src_ty = &self.types[src_ty_id.idx()];
let opcode = if src_ty.is_integer()
&& dst_ty.is_integer()
&& src_ty.num_bits() > dst_ty.num_bits()
{
"trunc"
} else if src_ty.is_signed()
&& dst_ty.is_integer()
&& src_ty.num_bits() < dst_ty.num_bits()
{
"sext"
} else if src_ty.is_integer()
&& dst_ty.is_integer()
&& src_ty.num_bits() < dst_ty.num_bits()
{
"zext"
} else if src_ty.is_integer() && dst_ty.is_integer() {
// A no-op.
"bitcast"
} else if src_ty.is_float()
&& dst_ty.is_float()
&& src_ty.num_bits() > dst_ty.num_bits()
{
"fptrunc"
} else if src_ty.is_float()
&& dst_ty.is_float()
&& src_ty.num_bits() < dst_ty.num_bits()
{
"fpext"
} else if src_ty.is_float() && dst_ty.is_float() {
// A no-op.
"bitcast"
} else if src_ty.is_float() && dst_ty.is_signed() {
"fptosi"
} else if src_ty.is_float() && dst_ty.is_integer() {
"fptoui"
} else if src_ty.is_signed() && dst_ty.is_float() {
"sitofp"
} else if src_ty.is_integer() && dst_ty.is_float() {
"uitofp"
} else {
panic!("PANIC: Invalid cast type combination.");
};
write!(
body,
" {} = {} {} to {}\n",
self.get_value(id, false),
opcode,
self.get_value(input, true),
self.get_type(dst_ty_id),
)?
}
}
}
Node::Binary { op, left, right } => {
enum OpTy {
Float,
Unsigned,
Signed,
}
let left_ty = &self.types[self.typing[left.idx()].idx()];
let op_ty = if left_ty.is_float() {
OpTy::Float
} else if left_ty.is_unsigned() {
OpTy::Unsigned
} else {
OpTy::Signed
};
let opcode = match (op, op_ty) {
(BinaryOperator::Add, OpTy::Float) => "fadd",
(BinaryOperator::Add, _) => "add",
(BinaryOperator::Sub, OpTy::Float) => "fsub",
(BinaryOperator::Sub, _) => "sub",
(BinaryOperator::Mul, OpTy::Float) => "fmul",
(BinaryOperator::Mul, _) => "mul",
(BinaryOperator::Div, OpTy::Float) => "fdiv",
(BinaryOperator::Div, OpTy::Unsigned) => "udiv",
(BinaryOperator::Div, OpTy::Signed) => "sdiv",
(BinaryOperator::Rem, OpTy::Float) => "frem",
(BinaryOperator::Rem, OpTy::Unsigned) => "urem",
(BinaryOperator::Rem, OpTy::Signed) => "srem",
(BinaryOperator::LT, OpTy::Float) => "fcmp olt",
(BinaryOperator::LT, OpTy::Unsigned) => "icmp ult",
(BinaryOperator::LT, OpTy::Signed) => "icmp slt",
(BinaryOperator::LTE, OpTy::Float) => "fcmp ole",
(BinaryOperator::LTE, OpTy::Unsigned) => "icmp ule",
(BinaryOperator::LTE, OpTy::Signed) => "icmp sle",
(BinaryOperator::GT, OpTy::Float) => "fcmp ogt",
(BinaryOperator::GT, OpTy::Unsigned) => "icmp ugt",
(BinaryOperator::GT, OpTy::Signed) => "icmp sgt",
(BinaryOperator::GTE, OpTy::Float) => "fcmp oge",
(BinaryOperator::GTE, OpTy::Unsigned) => "icmp uge",
(BinaryOperator::GTE, OpTy::Signed) => "icmp sge",
(BinaryOperator::EQ, OpTy::Float) => "fcmp oeq",
(BinaryOperator::EQ, _) => "icmp eq",
(BinaryOperator::NE, OpTy::Float) => "fcmp one",
(BinaryOperator::NE, _) => "icmp ne",
(BinaryOperator::Or, _) => "or",
(BinaryOperator::And, _) => "and",
(BinaryOperator::Xor, _) => "xor",
(BinaryOperator::LSh, _) => "lsh",
(BinaryOperator::RSh, OpTy::Unsigned) => "lshr",
(BinaryOperator::RSh, _) => "ashr",
};
let body = &mut blocks.get_mut(&self.bbs.0[id.idx()]).unwrap().body;
write!(
body,
" {} = {} {}, {}\n",
self.get_value(id, false),
opcode,
self.get_value(left, true),
self.get_value(right, false),
)?
}
Node::Ternary {
op,
first,
second,
third,
} => {
let body = &mut blocks.get_mut(&self.bbs.0[id.idx()]).unwrap().body;
match op {
TernaryOperator::Select => write!(
body,
" {} = select {}, {}, {}\n",
self.get_value(id, false),
self.get_value(first, true),
self.get_value(second, true),
self.get_value(third, true)
)?,
}
}
Node::IntrinsicCall {
intrinsic,
ref args,
} => {
let body = &mut blocks.get_mut(&self.bbs.0[id.idx()]).unwrap().body;
write!(
body,
" {} = call {} {}(",
self.get_value(id, false),
self.get_type(self.typing[id.idx()]),
convert_intrinsic(&intrinsic, &self.types[self.typing[id.idx()].idx()]),
)?;
for idx in 0..args.len() {
if idx != 0 {
write!(body, ", ")?;
}
write!(body, "{}", self.get_value(args[idx], true))?;
}
write!(body, ")\n")?
}
Node::Read {
collect,
ref indices,
} => {
let body = &mut blocks.get_mut(&self.bbs.0[id.idx()]).unwrap().body;
let collect_name = self.get_value(collect, false);
let collect_ty = self.typing[collect.idx()];
let index_ptr_name =
self.codegen_index_math(&collect_name, collect_ty, indices, body)?;
let self_ty = self.typing[id.idx()];
if self.types[self_ty.idx()].is_primitive() {
// If this read reaches a primitive type, actually perform a
// load.
write!(
body,
" {} = load {}, ptr {}\n",
self.get_value(id, false),
self.get_type(self_ty),
index_ptr_name,
)?;
} else {
// If this read doesn't reach a primitive type, just return
// the calculated offset pointer for the sub-collection.
write!(
body,
" {} = bitcast ptr {} to ptr\n",
self.get_value(id, false),
index_ptr_name
)?;
}
}
Node::Write {
collect,
data,
ref indices,
} => {
let body = &mut blocks.get_mut(&self.bbs.0[id.idx()]).unwrap().body;
let collect_name = self.get_value(collect, false);
let collect_ty = self.typing[collect.idx()];
let index_ptr_name =
self.codegen_index_math(&collect_name, collect_ty, indices, body)?;
let data_ty = self.typing[data.idx()];
if self.types[data_ty.idx()].is_primitive() {
// If the data item being written is a primitive type,
// perform a single store of the data value.
write!(
body,
" store {}, ptr {}\n",
self.get_value(data, true),
index_ptr_name,
)?;
} else {
// If the data item being written is not a primitive type,
// then perform a memcpy from the data collection to the
// destination collection.
let data_size = self.codegen_type_size(data_ty, body)?;
write!(
body,
" call void @llvm.memcpy.p0.p0.i64(ptr {}, {}, i64 {}, i1 false)\n",
index_ptr_name,
self.get_value(data, true),
data_size
)?;
}
write!(
body,
" {} = bitcast {} to ptr\n",
self.get_value(id, false),
self.get_value(collect, true)
)?;
}
Node::Undef { ty } => {
let body = &mut blocks.get_mut(&self.bbs.0[id.idx()]).unwrap().body;
let ty = self.get_type(ty);
write!(
body,
" {} = bitcast {} undef to {}\n",
self.get_value(id, false),
ty,
ty
)?;
}
_ => panic!("PANIC: Can't lower {:?}.", self.function.nodes[id.idx()]),
}
Ok(())
}
/*
* Calculate all of the dynamic constants upfront.
*/
fn codegen_dynamic_constants(
&self,
block: &mut LLVMBlock,
num_dc_params: u32,
) -> Result<(), Error> {
let body = &mut block.body;
for dc in dynamic_constants_bottom_up(&self.dynamic_constants) {
match &self.dynamic_constants[dc.idx()] {
DynamicConstant::Constant(val) => {
write!(body, " %dc{} = bitcast i64 {} to i64\n", dc.idx(), val)?
}
DynamicConstant::Parameter(idx) => {
if *idx < num_dc_params as usize {
write!(
body,
" %dc{} = bitcast i64 %dc_p{} to i64\n",
dc.idx(),
idx
)?
} else {
write!(body, " %dc{} = bitcast i64 0 to i64\n", dc.idx())?
}
}
DynamicConstant::Add(xs) => {
let mut xs = xs.iter().peekable();
let mut cur_value = format!("%dc{}", xs.next().unwrap().idx());
let mut idx = 0;
while let Some(x) = xs.next() {
let new_val = format!(
"%dc{}{}",
dc.idx(),
if xs.peek().is_some() {
format!(".{}", idx)
} else {
"".to_string()
}
);
write!(
body,
" {} = add i64{},%dc{}\n",
new_val,
cur_value,
x.idx()
)?;
cur_value = new_val;
idx += 1;
}
}
DynamicConstant::Sub(left, right) => write!(
body,
" %dc{} = sub i64%dc{},%dc{}\n",
dc.idx(),
left.idx(),
right.idx()
)?,
DynamicConstant::Mul(xs) => {
let mut xs = xs.iter().peekable();
let mut cur_value = format!("%dc{}", xs.next().unwrap().idx());
let mut idx = 0;
while let Some(x) = xs.next() {
let new_val = format!(
"%dc{}{}",
dc.idx(),
if xs.peek().is_some() {
format!(".{}", idx)
} else {
"".to_string()
}
);
write!(
body,
" {} = mul i64{},%dc{}\n",
new_val,
cur_value,
x.idx()
)?;
cur_value = new_val;
idx += 1;
}
}
DynamicConstant::Div(left, right) => write!(
body,
" %dc{} = udiv i64%dc{},%dc{}\n",
dc.idx(),
left.idx(),
right.idx()
)?,
DynamicConstant::Rem(left, right) => write!(
body,
" %dc{} = urem i64%dc{},%dc{}\n",
dc.idx(),
left.idx(),
right.idx()
)?,
DynamicConstant::Min(xs) => {
let mut xs = xs.iter().peekable();
let mut cur_value = format!("%dc{}", xs.next().unwrap().idx());
let mut idx = 0;
while let Some(x) = xs.next() {
let new_val = format!(
"%dc{}{}",
dc.idx(),
if xs.peek().is_some() {
format!(".{}", idx)
} else {
"".to_string()
}
);
write!(
body,
" {} = call i64 @llvm.umin.i64(i64{},i64%dc{})\n",
new_val,
cur_value,
x.idx()
)?;
cur_value = new_val;
idx += 1;
}
}
DynamicConstant::Max(xs) => {
let mut xs = xs.iter().peekable();
let mut cur_value = format!("%dc{}", xs.next().unwrap().idx());
let mut idx = 0;
while let Some(x) = xs.next() {
let new_val = format!(
"%dc{}{}",
dc.idx(),
if xs.peek().is_some() {
format!(".{}", idx)
} else {
"".to_string()
}
);
write!(
body,
" {} = call i64 @llvm.umax.i64(i64{},i64%dc{})\n",
new_val,
cur_value,
x.idx()
)?;
cur_value = new_val;
idx += 1;
}
}
}
}
Ok(())
}
/*
* Emit logic to index into an collection.
*/
fn codegen_index_math(
&self,
collect_name: &str,
mut collect_ty: TypeID,
indices: &[Index],
body: &mut String,
) -> Result<String, Error> {
let mut acc_ptr = collect_name.to_string();
for index in indices {
match index {
Index::Field(idx) => {
let Type::Product(ref fields) = self.types[collect_ty.idx()] else {
panic!()
};
// Get the offset of the field at index `idx` by calculating
// the product's size up to field `idx`, then offseting the
// base pointer by that amount.
let mut acc_offset = "0".to_string();
for field in &fields[..*idx] {
let field_align = get_type_alignment(&self.types, *field);
let field = self.codegen_type_size(*field, body)?;
acc_offset = Self::round_up_to(&acc_offset, field_align, body)?;
acc_offset = Self::append(&acc_offset, &field, body)?;
}
acc_offset = Self::round_up_to(
&acc_offset,
get_type_alignment(&self.types, fields[*idx]),
body,
)?;
acc_ptr = Self::gep(&acc_ptr, &acc_offset, body)?;
collect_ty = fields[*idx];
}
Index::Variant(idx) => {
// The tag of a summation is at the end of the summation, so
// the variant pointer is just the base pointer. Do nothing.
let Type::Summation(ref variants) = self.types[collect_ty.idx()] else {
panic!()
};
collect_ty = variants[*idx];
}
Index::Position(ref pos) => {
let Type::Array(elem, ref dims) = self.types[collect_ty.idx()] else {
panic!()
};
// The offset of the position into an array is:
//
// ((0 * s1 + p1) * s2 + p2) * s3 + p3 ...
let elem_size = self.codegen_type_size(elem, body)?;
let elem_align = get_type_alignment(&self.types, elem);
let aligned_elem_size = Self::round_up_to(&elem_size, elem_align, body)?;
let mut acc_offset = "0".to_string();
for (p, s) in zip(pos, dims) {
let p = self.get_value(*p, false);
let s = format!("%dc{}", s.idx());
acc_offset = Self::multiply(&acc_offset, &s, body)?;
acc_offset = Self::append(&acc_offset, &p, body)?;
}
// Convert offset in # elements -> # bytes.
acc_offset = Self::multiply(&acc_offset, &aligned_elem_size, body)?;
acc_ptr = Self::gep(&acc_ptr, &acc_offset, body)?;
collect_ty = elem;
}
}
}
Ok(acc_ptr)
}
/*
* Emit logic to calculate the size of a type. This needs to be emitted as
* IR since the size of an array may depend on array constants.
*/
fn codegen_type_size(&self, ty: TypeID, body: &mut String) -> Result<String, Error> {
match self.types[ty.idx()] {
Type::Control | Type::MultiReturn(_) => panic!(),
Type::Boolean | Type::Integer8 | Type::UnsignedInteger8 | Type::Float8 => {
Ok("1".to_string())
}
Type::Integer16 | Type::UnsignedInteger16 | Type::BFloat16 => Ok("2".to_string()),
Type::Integer32 | Type::UnsignedInteger32 | Type::Float32 => Ok("4".to_string()),
Type::Integer64 | Type::UnsignedInteger64 | Type::Float64 => Ok("8".to_string()),
Type::Product(ref fields) => {
let fields_align = fields
.into_iter()
.map(|id| get_type_alignment(&self.types, *id));
let fields: Result<Vec<String>, Error> = fields
.into_iter()
.map(|id| self.codegen_type_size(*id, body))
.collect();
// Emit LLVM IR to round up to the alignment of the next field,
// and then add the size of that field. At the end, round up to
// the alignment of the whole struct.
let mut acc_size = "0".to_string();
for (field_align, field) in zip(fields_align, fields?) {
acc_size = Self::round_up_to(&acc_size, field_align, body)?;
acc_size = Self::append(&acc_size, &field, body)?;
}
Self::round_up_to(&acc_size, get_type_alignment(&self.types, ty), body)
}
Type::Summation(ref variants) => {
let variants: Result<Vec<String>, Error> = variants
.into_iter()
.map(|id| self.codegen_type_size(*id, body))
.collect();
// The size of a summation is the size of the largest field,
// plus 1 byte and alignment for the discriminant.
let mut acc_size = "0".to_string();
for variant in variants? {
acc_size = Self::max(&acc_size, &variant, body)?;
}
// No alignment is necessary for the 1 byte discriminant.
acc_size = Self::append(&acc_size, "1", body)?;
Self::round_up_to(&acc_size, get_type_alignment(&self.types, ty), body)
}
Type::Array(elem, ref bounds) => {
// The size of an array is the size of the element multipled by
// the dynamic constant bounds.
let mut acc_size = self.codegen_type_size(elem, body)?;
acc_size =
Self::round_up_to(&acc_size, get_type_alignment(&self.types, elem), body)?;
for dc in bounds {
acc_size = Self::multiply(&acc_size, &format!("%dc{}", dc.idx()), body)?;
}
Ok(acc_size)
}
}
}
fn get_value(&self, id: NodeID, ty: bool) -> String {
if ty {
format!("{} %v{}", self.get_type(self.typing[id.idx()]), id.idx())
} else {
format!("%v{}", id.idx())
}
}
fn get_block_name(&self, id: NodeID) -> String {
format!("bb_{}", id.idx())
}
fn get_type(&self, id: TypeID) -> &'static str {
convert_type(&self.types[id.idx()])
}
// Use the trick that given a number `x` and a power of two `m`, we can
// compute rounding up `x` to the next multiple of
// `m` via:
//
// (x + m - 1) & -m
//
// Which is equivalent to the following LLVM IR (`m` is a constant):
//
// %1 = add i64 %x, (m-1)
// %2 = and i64 %1, -m
fn round_up_to(x: &str, m: usize, body: &mut String) -> Result<String, Error> {
let init_body_len = Self::gen_filler_id();
write!(
body,
" %round_up_to.{} = add i64 {}, {}\n",
init_body_len,
x,
m - 1
)?;
let name = format!("%round_up_to.{}", Self::gen_filler_id());
write!(
body,
" {} = and i64 %round_up_to.{}, -{}\n",
name, init_body_len, m
)?;
Ok(name)
}
// Emit LLVM IR to add the size of the next field.
fn append(x: &str, f: &str, body: &mut String) -> Result<String, Error> {
let name = format!("%append.{}", Self::gen_filler_id());
write!(body, " {} = add i64 {}, {}\n", name, x, f)?;
Ok(name)
}
// Emit LLVM IR to get the maximum of two sizes.
fn max(a: &str, b: &str, body: &mut String) -> Result<String, Error> {
let name = format!("%max.{}", Self::gen_filler_id());
write!(
body,
" {} = call i64 @llvm.umax.i64(i64 {}, i64 {})\n",
name, a, b
)?;
Ok(name)
}
// Emit LLVM IR to multiply two sizes.
fn multiply(a: &str, b: &str, body: &mut String) -> Result<String, Error> {
let name = format!("%multiply.{}", Self::gen_filler_id());
write!(body, " {} = mul i64 {}, {}\n", name, a, b)?;
Ok(name)
}
// Emit LLVM IR to gep a pointer from a byte size.
fn gep(ptr: &str, size: &str, body: &mut String) -> Result<String, Error> {
let name = format!("%gep.{}", Self::gen_filler_id());
write!(
body,
" {} = getelementptr i8, ptr {}, i64 {}\n",
name, ptr, size
)?;
Ok(name)
}
fn gen_filler_id() -> usize {
NUM_FILLER_REGS.fetch_add(1, Ordering::Relaxed)
}
}
fn convert_type(ty: &Type) -> &'static str {
match ty {
Type::Boolean => "i1",
Type::Integer8 | Type::UnsignedInteger8 => "i8",
Type::Integer16 | Type::UnsignedInteger16 => "i16",
Type::Integer32 | Type::UnsignedInteger32 => "i32",
Type::Integer64 | Type::UnsignedInteger64 => "i64",
Type::Float32 => "float",
Type::Float64 => "double",
Type::Product(_) | Type::Summation(_) | Type::Array(_, _) => "ptr",
_ => panic!(),
}
}
fn convert_intrinsic(intrinsic: &Intrinsic, ty: &Type) -> String {
let intrinsic = match intrinsic {
Intrinsic::Abs => {
if ty.is_float() {
"fabs"
} else if ty.is_signed() {
"abs"
} else if ty.is_unsigned() {
panic!("llvm doesn't define abs for unsigned integers")
} else {
panic!()
}
}
Intrinsic::ACos => "acos",
Intrinsic::ASin => "asin",
Intrinsic::ATan => "atan",
Intrinsic::ATan2 => "atan2",
Intrinsic::Ceil => "ceil",
Intrinsic::Cos => "cos",
Intrinsic::Cosh => "cosh",
Intrinsic::Exp => "exp",
Intrinsic::Exp2 => "exp2",
Intrinsic::Floor => "floor",
Intrinsic::Ln => "log",
Intrinsic::Log10 => "log10",
Intrinsic::Log2 => "log2",
Intrinsic::Max => {
if ty.is_float() {
"maxnum"
} else if ty.is_unsigned() {
"umax"
} else if ty.is_signed() {
"smax"
} else {
panic!()
}
}
Intrinsic::Min => {
if ty.is_float() {
"minnum"
} else if ty.is_unsigned() {
"umin"
} else if ty.is_signed() {
"smin"
} else {
panic!()
}
}
Intrinsic::Pow => "pow",
Intrinsic::Powf => "pow",
Intrinsic::Powi => "powi",
Intrinsic::Round => "round",
Intrinsic::Sin => "sin",
Intrinsic::Sinh => "sinh",
Intrinsic::Sqrt => "sqrt",
Intrinsic::Tan => "tan",
Intrinsic::Tanh => "tanh",
_ => panic!(),
};
// We can't just use our previous routines for emitting types, because only
// inside intrinsics does LLVM use "f32" and "f64" properly!
let ty = match ty {
Type::Boolean => "i1",
Type::Integer8 | Type::UnsignedInteger8 => "i8",
Type::Integer16 | Type::UnsignedInteger16 => "i16",
Type::Integer32 | Type::UnsignedInteger32 => "i32",
Type::Integer64 | Type::UnsignedInteger64 => "i64",
Type::Float32 => "f32",
Type::Float64 => "f64",
_ => panic!(),
};
format!("@llvm.{}.{}", intrinsic, ty)
}