fn gen_expr(
    expr: &Expr,
    prog: &mut SirProgram,
    cur_func: FunctionId,
    cur_block: BasicBlockId,
    tracker: &mut StatementTracker,
) -> WeldResult<(FunctionId, BasicBlockId, Symbol)> {
    use self::StatementKind::*;
    use self::Terminator::*;

    match expr.kind {
        ExprKind::Ident(ref sym) => Ok((cur_func, cur_block, sym.clone())),

        ExprKind::Literal(ref lit) => {
            let kind = AssignLiteral(lit.clone());
            let res_sym = tracker.symbol_for_statement(prog, cur_func, cur_block, &expr.ty, kind);
            Ok((cur_func, cur_block, res_sym))
        }

        ExprKind::Let {
            ref name,
            ref value,
            ref body,
        } => {
            let (cur_func, cur_block, val_sym) =
                gen_expr(value, prog, cur_func, cur_block, tracker)?;

            let kind = Assign(val_sym);
            tracker.named_symbol_for_statement(
                prog,
                cur_func,
                cur_block,
                &value.ty,
                kind,
                name.clone(),
            );

            let (cur_func, cur_block, res_sym) =
                gen_expr(body, prog, cur_func, cur_block, tracker)?;
            Ok((cur_func, cur_block, res_sym))
        }

        ExprKind::BinOp {
            kind,
            ref left,
            ref right,
        } => {
            let (cur_func, cur_block, left_sym) =
                gen_expr(left, prog, cur_func, cur_block, tracker)?;
            let (cur_func, cur_block, right_sym) =
                gen_expr(right, prog, cur_func, cur_block, tracker)?;
            let kind = BinOp {
                op: kind,
                left: left_sym,
                right: right_sym,
            };
            let res_sym = tracker.symbol_for_statement(prog, cur_func, cur_block, &expr.ty, kind);
            Ok((cur_func, cur_block, res_sym))
        }

        ExprKind::UnaryOp { kind, ref value } => {
            let (cur_func, cur_block, value_sym) =
                gen_expr(value, prog, cur_func, cur_block, tracker)?;
            let kind = UnaryOp {
                op: kind,
                child: value_sym,
            };
            let res_sym = tracker.symbol_for_statement(prog, cur_func, cur_block, &expr.ty, kind);
            Ok((cur_func, cur_block, res_sym))
        }

        ExprKind::Negate(ref child_expr) => {
            let (cur_func, cur_block, child_sym) =
                gen_expr(child_expr, prog, cur_func, cur_block, tracker)?;
            let kind = Negate(child_sym);
            let res_sym = tracker.symbol_for_statement(prog, cur_func, cur_block, &expr.ty, kind);
            Ok((cur_func, cur_block, res_sym))
        }

        ExprKind::Not(ref child_expr) => {
            let (cur_func, cur_block, child_sym) =
                gen_expr(child_expr, prog, cur_func, cur_block, tracker)?;
            let kind = Not(child_sym);
            let res_sym = tracker.symbol_for_statement(prog, cur_func, cur_block, &expr.ty, kind);
            Ok((cur_func, cur_block, res_sym))
        }

        ExprKind::Assert(ref child_expr) => {
            let (cur_func, cur_block, child_sym) =
                gen_expr(child_expr, prog, cur_func, cur_block, tracker)?;
            let kind = Assert(child_sym);
            let res_sym = tracker.symbol_for_statement(prog, cur_func, cur_block, &expr.ty, kind);
            Ok((cur_func, cur_block, res_sym))
        }

        ExprKind::Broadcast(ref child_expr) => {
            let (cur_func, cur_block, child_sym) =
                gen_expr(child_expr, prog, cur_func, cur_block, tracker)?;
            let kind = Broadcast(child_sym);
            let res_sym = tracker.symbol_for_statement(prog, cur_func, cur_block, &expr.ty, kind);
            Ok((cur_func, cur_block, res_sym))
        }

        ExprKind::Serialize(ref child_expr) => {
            let (cur_func, cur_block, child_sym) =
                gen_expr(child_expr, prog, cur_func, cur_block, tracker)?;
            let kind = Serialize(child_sym);
            let res_sym = tracker.symbol_for_statement(prog, cur_func, cur_block, &expr.ty, kind);
            Ok((cur_func, cur_block, res_sym))
        }

        ExprKind::Deserialize { ref value, .. } => {
            let (cur_func, cur_block, child_sym) =
                gen_expr(value, prog, cur_func, cur_block, tracker)?;
            let kind = Deserialize(child_sym);
            let res_sym = tracker.symbol_for_statement(prog, cur_func, cur_block, &expr.ty, kind);
            Ok((cur_func, cur_block, res_sym))
        }

        ExprKind::Cast { ref child_expr, .. } => {
            let (cur_func, cur_block, child_sym) =
                gen_expr(child_expr, prog, cur_func, cur_block, tracker)?;
            let kind = Cast(child_sym, expr.ty.clone());
            let res_sym = tracker.symbol_for_statement(prog, cur_func, cur_block, &expr.ty, kind);
            Ok((cur_func, cur_block, res_sym))
        }

        ExprKind::Lookup {
            ref data,
            ref index,
        } => {
            let (cur_func, cur_block, data_sym) =
                gen_expr(data, prog, cur_func, cur_block, tracker)?;
            let (cur_func, cur_block, index_sym) =
                gen_expr(index, prog, cur_func, cur_block, tracker)?;

            let kind = Lookup {
                child: data_sym,
                index: index_sym,
            };
            let res_sym = tracker.symbol_for_statement(prog, cur_func, cur_block, &expr.ty, kind);
            Ok((cur_func, cur_block, res_sym))
        }

        ExprKind::OptLookup {
            ref data,
            ref index,
        } => {
            let (cur_func, cur_block, data_sym) =
                gen_expr(data, prog, cur_func, cur_block, tracker)?;
            let (cur_func, cur_block, index_sym) =
                gen_expr(index, prog, cur_func, cur_block, tracker)?;

            let kind = OptLookup {
                child: data_sym,
                index: index_sym,
            };
            let res_sym = tracker.symbol_for_statement(prog, cur_func, cur_block, &expr.ty, kind);
            Ok((cur_func, cur_block, res_sym))
        }

        ExprKind::KeyExists { ref data, ref key } => {
            let (cur_func, cur_block, data_sym) =
                gen_expr(data, prog, cur_func, cur_block, tracker)?;
            let (cur_func, cur_block, key_sym) = gen_expr(key, prog, cur_func, cur_block, tracker)?;
            let kind = KeyExists {
                child: data_sym,
                key: key_sym,
            };
            let res_sym = tracker.symbol_for_statement(prog, cur_func, cur_block, &expr.ty, kind);
            Ok((cur_func, cur_block, res_sym))
        }

        ExprKind::Slice {
            ref data,
            ref index,
            ref size,
        } => {
            let (cur_func, cur_block, data_sym) =
                gen_expr(data, prog, cur_func, cur_block, tracker)?;
            let (cur_func, cur_block, index_sym) =
                gen_expr(index, prog, cur_func, cur_block, tracker)?;
            let (cur_func, cur_block, size_sym) =
                gen_expr(size, prog, cur_func, cur_block, tracker)?;
            let kind = Slice {
                child: data_sym,
                index: index_sym,
                size: size_sym,
            };
            let res_sym = tracker.symbol_for_statement(prog, cur_func, cur_block, &expr.ty, kind);
            Ok((cur_func, cur_block, res_sym))
        }

        ExprKind::Sort {
            ref data,
            ref cmpfunc,
        } => {
            if let ExprKind::Lambda {
                ref params,
                ref body,
            } = cmpfunc.kind
            {
                let cmpfunc_id = prog.add_func();
                let cmpblock = prog.funcs[cmpfunc_id].add_block();
                let (cmpfunc_id, cmpblock, cmp_sym) =
                    gen_expr(body, prog, cmpfunc_id, cmpblock, tracker)?;
                prog.funcs[cmpfunc_id]
                    .params
                    .insert(params[0].name.clone(), params[0].ty.clone());
                prog.funcs[cmpfunc_id]
                    .params
                    .insert(params[1].name.clone(), params[1].ty.clone());
                prog.funcs[cmpfunc_id].blocks[cmpblock].terminator =
                    Terminator::EndFunction(cmp_sym);

                let (cur_func, cur_block, data_sym) =
                    gen_expr(data, prog, cur_func, cur_block, tracker)?;

                let kind = Sort {
                    child: data_sym,
                    cmpfunc: cmpfunc_id,
                };
                let res_sym =
                    tracker.symbol_for_statement(prog, cur_func, cur_block, &expr.ty, kind);
                Ok((cur_func, cur_block, res_sym))
            } else {
                compile_err!(
                    "Sort comparison function expected lambda type, instead {:?} provided",
                    cmpfunc.ty
                )
            }
        }
        ExprKind::Select {
            ref cond,
            ref on_true,
            ref on_false,
        } => {
            let (cur_func, cur_block, cond_sym) =
                gen_expr(cond, prog, cur_func, cur_block, tracker)?;
            let (cur_func, cur_block, true_sym) =
                gen_expr(on_true, prog, cur_func, cur_block, tracker)?;
            let (cur_func, cur_block, false_sym) =
                gen_expr(on_false, prog, cur_func, cur_block, tracker)?;
            let kind = Select {
                cond: cond_sym,
                on_true: true_sym,
                on_false: false_sym,
            };
            let res_sym = tracker.symbol_for_statement(prog, cur_func, cur_block, &expr.ty, kind);
            Ok((cur_func, cur_block, res_sym))
        }

        ExprKind::ToVec { ref child_expr } => {
            let (cur_func, cur_block, child_sym) =
                gen_expr(child_expr, prog, cur_func, cur_block, tracker)?;
            let kind = ToVec(child_sym);
            let res_sym = tracker.symbol_for_statement(prog, cur_func, cur_block, &expr.ty, kind);
            Ok((cur_func, cur_block, res_sym))
        }

        ExprKind::Length { ref data } => {
            let (cur_func, cur_block, child_sym) =
                gen_expr(data, prog, cur_func, cur_block, tracker)?;
            let kind = Length(child_sym);
            let res_sym = tracker.symbol_for_statement(prog, cur_func, cur_block, &expr.ty, kind);
            Ok((cur_func, cur_block, res_sym))
        }

        ExprKind::If {
            ref cond,
            ref on_true,
            ref on_false,
        } => {
            let (cur_func, cur_block, cond_sym) =
                gen_expr(cond, prog, cur_func, cur_block, tracker)?;
            let true_block = prog.funcs[cur_func].add_block();
            let false_block = prog.funcs[cur_func].add_block();
            prog.funcs[cur_func].blocks[cur_block].terminator = Branch {
                cond: cond_sym,
                on_true: true_block,
                on_false: false_block,
            };
            let (true_func, true_block, true_sym) =
                gen_expr(on_true, prog, cur_func, true_block, tracker)?;
            let (false_func, false_block, false_sym) =
                gen_expr(on_false, prog, cur_func, false_block, tracker)?;
            let res_sym = prog.add_local(&expr.ty, true_func);
            prog.funcs[true_func].blocks[true_block]
                .add_statement(Statement::new(Some(res_sym.clone()), Assign(true_sym)));
            prog.funcs[false_func].blocks[false_block]
                .add_statement(Statement::new(Some(res_sym.clone()), Assign(false_sym)));

            let cont_block = prog.funcs[cur_func].add_block();
            prog.funcs[true_func].blocks[true_block].terminator = JumpBlock(cont_block);
            prog.funcs[false_func].blocks[false_block].terminator = JumpBlock(cont_block);
            Ok((cur_func, cont_block, res_sym))
        }

        ExprKind::Iterate {
            ref initial,
            ref update_func,
        } => {
            // Generate the intial value.
            let (cur_func, cur_block, initial_sym) =
                gen_expr(initial, prog, cur_func, cur_block, tracker)?;

            // Pull out the argument name and function body and validate that things type-check.
            let argument_sym;
            let func_body;
            match update_func.kind {
                ExprKind::Lambda {
                    ref params,
                    ref body,
                } if params.len() == 1 => {
                    argument_sym = &params[0].name;
                    func_body = body;
                    if params[0].ty != initial.ty {
                        return compile_err!("Wrong argument type for body of Iterate");
                    }
                    if func_body.ty != Struct(vec![initial.ty.clone(), Scalar(ScalarKind::Bool)]) {
                        return compile_err!("Wrong return type for body of Iterate");
                    }
                    prog.add_local_named(&params[0].ty, argument_sym, cur_func);
                }
                _ => return compile_err!("Argument of Iterate was not a Lambda"),
            }

            prog.funcs[cur_func].blocks[cur_block].add_statement(Statement::new(
                Some(argument_sym.clone()),
                Assign(initial_sym),
            ));

            let body_start_block = prog.funcs[cur_func].add_block();

            // Jump to where the body starts
            prog.funcs[cur_func].blocks[cur_block].terminator = JumpBlock(body_start_block);

            // Generate the loop's body, which will work on argument_sym and produce result_sym.
            // The type of result_sym will be {ArgType, bool} and we will repeat the body if the bool is true.
            let (body_end_func, body_end_block, result_sym) =
                gen_expr(func_body, prog, cur_func, body_start_block, tracker)?;

            // After the body, unpack the {state, bool} struct into symbols argument_sym and continue_sym.
            let continue_sym = prog.add_local(&Scalar(ScalarKind::Bool), body_end_func);

            prog.funcs[body_end_func].blocks[body_end_block].add_statement(Statement::new(
                Some(argument_sym.clone()),
                GetField {
                    value: result_sym.clone(),
                    index: 0,
                },
            ));
            prog.funcs[body_end_func].blocks[body_end_block].add_statement(Statement::new(
                Some(continue_sym.clone()),
                GetField {
                    value: result_sym,
                    index: 1,
                },
            ));

            // Create two more blocks so we can branch on continue_sym
            let repeat_block = prog.funcs[body_end_func].add_block();
            let finish_block = prog.funcs[body_end_func].add_block();
            prog.funcs[body_end_func].blocks[body_end_block].terminator = Branch {
                cond: continue_sym,
                on_true: repeat_block,
                on_false: finish_block,
            };

            // Do a normal JumpBlock since it should be in the same function.
            assert!(body_end_func == cur_func);
            prog.funcs[body_end_func].blocks[repeat_block].terminator = JumpBlock(body_start_block);

            // Our final value is available in finish_block.
            Ok((body_end_func, finish_block, argument_sym.clone()))
        }

        ExprKind::Merge {
            ref builder,
            ref value,
        } => {
            // This expression doesn't return a symbol, so just add a statement for it directly
            // instead of calling the tracker.
            let (cur_func, cur_block, builder_sym) =
                gen_expr(builder, prog, cur_func, cur_block, tracker)?;
            let (cur_func, cur_block, elem_sym) =
                gen_expr(value, prog, cur_func, cur_block, tracker)?;
            prog.funcs[cur_func].blocks[cur_block].add_statement(Statement::new(
                None,
                Merge {
                    builder: builder_sym.clone(),
                    value: elem_sym,
                },
            ));
            Ok((cur_func, cur_block, builder_sym))
        }

        ExprKind::Res { ref builder } => {
            let (cur_func, cur_block, builder_sym) =
                gen_expr(builder, prog, cur_func, cur_block, tracker)?;
            let kind = Res(builder_sym);
            let res_sym = tracker.symbol_for_statement(prog, cur_func, cur_block, &expr.ty, kind);
            Ok((cur_func, cur_block, res_sym))
        }

        ExprKind::NewBuilder(ref arg) => {
            let (cur_func, cur_block, arg_sym) = if let Some(ref a) = *arg {
                let (cur_func, cur_block, arg_sym) =
                    gen_expr(a, prog, cur_func, cur_block, tracker)?;
                (cur_func, cur_block, Some(arg_sym))
            } else {
                (cur_func, cur_block, None)
            };

            // NewBuilder is special, since they are stateful objects - we can't alias them.
            let res_sym = prog.add_local(&expr.ty, cur_func);
            prog.funcs[cur_func].blocks[cur_block].add_statement(Statement::new(
                Some(res_sym.clone()),
                NewBuilder {
                    arg: arg_sym,
                    ty: expr.ty.clone(),
                },
            ));
            Ok((cur_func, cur_block, res_sym))
        }

        ExprKind::MakeStruct { ref elems } => {
            let mut syms = vec![];
            let (mut cur_func, mut cur_block, mut sym) =
                gen_expr(&elems[0], prog, cur_func, cur_block, tracker)?;
            syms.push(sym);
            for elem in elems.iter().skip(1) {
                let r = gen_expr(elem, prog, cur_func, cur_block, tracker)?;
                cur_func = r.0;
                cur_block = r.1;
                sym = r.2;
                syms.push(sym);
            }
            let kind = MakeStruct(syms);
            let res_sym = tracker.symbol_for_statement(prog, cur_func, cur_block, &expr.ty, kind);
            Ok((cur_func, cur_block, res_sym))
        }

        ExprKind::MakeVector { ref elems } => {
            let mut syms = vec![];
            let mut cur_func = cur_func;
            let mut cur_block = cur_block;
            for elem in elems.iter() {
                let r = gen_expr(elem, prog, cur_func, cur_block, tracker)?;
                cur_func = r.0;
                cur_block = r.1;
                let sym = r.2;
                syms.push(sym);
            }
            let kind = MakeVector(syms);
            let res_sym = tracker.symbol_for_statement(prog, cur_func, cur_block, &expr.ty, kind);
            Ok((cur_func, cur_block, res_sym))
        }

        ExprKind::CUDF {
            ref sym_name,
            ref args,
            ..
        } => {
            let mut syms = vec![];
            let mut cur_func = cur_func;
            let mut cur_block = cur_block;
            for arg in args.iter() {
                let r = gen_expr(arg, prog, cur_func, cur_block, tracker)?;
                cur_func = r.0;
                cur_block = r.1;
                let sym = r.2;
                syms.push(sym);
            }
            let kind = CUDF {
                args: syms,
                symbol_name: sym_name.clone(),
            };
            let res_sym = tracker.symbol_for_statement(prog, cur_func, cur_block, &expr.ty, kind);
            Ok((cur_func, cur_block, res_sym))
        }

        ExprKind::GetField { ref expr, index } => {
            let (cur_func, cur_block, struct_sym) =
                gen_expr(expr, prog, cur_func, cur_block, tracker)?;
            let field_ty = match expr.ty {
                super::ast::Type::Struct(ref v) => &v[index as usize],
                _ => compile_err!("Internal error: tried to get field of type {}", &expr.ty)?,
            };

            let kind = GetField {
                value: struct_sym,
                index,
            };
            let res_sym = tracker.symbol_for_statement(prog, cur_func, cur_block, &field_ty, kind);
            Ok((cur_func, cur_block, res_sym))
        }

        ExprKind::For {
            ref iters,
            ref builder,
            ref func,
        } => {
            if let ExprKind::Lambda {
                ref params,
                ref body,
            } = func.kind
            {
                let (cur_func, cur_block, builder_sym) =
                    gen_expr(builder, prog, cur_func, cur_block, tracker)?;
                let body_func = prog.add_func();
                prog.funcs[body_func].loop_body = true;
                let body_block = prog.funcs[body_func].add_block();
                prog.add_local_named(&params[0].ty, &params[0].name, body_func);
                prog.add_local_named(&params[1].ty, &params[1].name, body_func);
                prog.add_local_named(&params[2].ty, &params[2].name, body_func);

                // Register the data, index, and builder arguments are loop variables.
                prog.add_loop_variable(&params[0].name, body_func);
                prog.add_loop_variable(&params[1].name, body_func);
                prog.add_loop_variable(&params[2].name, body_func);

                prog.funcs[body_func]
                    .params
                    .insert(builder_sym.clone(), builder.ty.clone());
                let mut cur_func = cur_func;
                let mut cur_block = cur_block;
                let mut pf_iters: Vec<ParallelForIter> = Vec::new();
                for iter in iters.iter() {
                    let data_res = gen_expr(&iter.data, prog, cur_func, cur_block, tracker)?;
                    cur_func = data_res.0;
                    cur_block = data_res.1;
                    prog.funcs[body_func]
                        .params
                        .insert(data_res.2.clone(), iter.data.ty.clone());
                    let start_sym = get_iter_sym(
                        &iter.start,
                        prog,
                        &mut cur_func,
                        &mut cur_block,
                        tracker,
                        body_func,
                    )?;
                    let end_sym = get_iter_sym(
                        &iter.end,
                        prog,
                        &mut cur_func,
                        &mut cur_block,
                        tracker,
                        body_func,
                    )?;
                    let stride_sym = get_iter_sym(
                        &iter.stride,
                        prog,
                        &mut cur_func,
                        &mut cur_block,
                        tracker,
                        body_func,
                    )?;
                    let shape_sym = get_iter_sym(
                        &iter.shape,
                        prog,
                        &mut cur_func,
                        &mut cur_block,
                        tracker,
                        body_func,
                    )?;
                    let strides_sym = get_iter_sym(
                        &iter.strides,
                        prog,
                        &mut cur_func,
                        &mut cur_block,
                        tracker,
                        body_func,
                    )?;
                    pf_iters.push(ParallelForIter {
                        data: data_res.2,
                        start: start_sym,
                        end: end_sym,
                        stride: stride_sym,
                        kind: iter.kind.clone(),
                        shape: shape_sym,
                        strides: strides_sym,
                    });
                }
                let (body_end_func, body_end_block, result_sym) =
                    gen_expr(body, prog, body_func, body_block, tracker)?;
                prog.funcs[body_end_func].blocks[body_end_block].terminator =
                    EndFunction(result_sym);

                // Check whether the loop is the innermost one.
                let mut is_innermost = true;
                body.traverse(&mut |ref e| {
                    if let ExprKind::For { .. } = e.kind {
                        is_innermost = false;
                    }
                });
                prog.funcs[body_end_func].innermost_loop = is_innermost;

                let kind = ParallelFor(ParallelForData {
                    data: pf_iters,
                    builder: builder_sym,
                    builder_arg: params[0].name.clone(),
                    idx_arg: params[1].name.clone(),
                    data_arg: params[2].name.clone(),
                    body: body_func,
                    innermost: is_innermost,
                });

                let res_sym =
                    tracker.symbol_for_statement(prog, cur_func, cur_block, &builder.ty, kind);
                Ok((cur_func, cur_block, res_sym))
            } else {
                compile_err!("Argument to For was not a Lambda: {}", func.pretty_print())
            }
        }

        _ => compile_err!("Unsupported expression: {}", expr.pretty_print()),
    }
}
Generate code to compute the expression `expr` starting at the current tail of `cur_block`,
possibly creating new basic blocks and functions in the process. Return the function and
basic block that the expression will be ready in, and its symbol therein.
weld/src/sir/mod.rs