fn generate_bindings(
        &mut self,
        expr: &mut Expr,
        bindings: &mut HashMap<Symbol, Expr>,
        generated: &mut HashSet<Symbol>,
        current_site: &mut Site,
        stack: &mut Vec<Vec<Binding>>,
        sites: &mut SiteMap,
    ) {
        // NOTE: Because of the way paths are built, this method must traverse Lambdas and If
        // statements in the exact same order as build_site_map_helper!
        let handled = match expr.kind {
            Lambda { ref mut body, .. } => {
                self.generate_bindings_scoped(
                    body,
                    bindings,
                    generated,
                    current_site,
                    stack,
                    sites,
                );
                true
            }
            Let {
                ref mut value,
                ref mut body,
                ..
            } => {
                self.generate_bindings(value, bindings, generated, current_site, stack, sites);
                self.generate_bindings_scoped(
                    body,
                    bindings,
                    generated,
                    current_site,
                    stack,
                    sites,
                );
                true
            }
            If {
                ref mut cond,
                ref mut on_true,
                ref mut on_false,
            } => {
                // Generate bindings for the condition, since we won't recurse down into
                // subexpressions.
                self.generate_bindings(cond, bindings, generated, current_site, stack, sites);

                // We want to keep definitions of If/Else statements within the branch target
                // to prevent moving expressions out from behind a branch condition.

                self.generate_bindings_scoped(
                    on_true,
                    bindings,
                    generated,
                    current_site,
                    stack,
                    sites,
                );
                self.generate_bindings_scoped(
                    on_false,
                    bindings,
                    generated,
                    current_site,
                    stack,
                    sites,
                );
                true
            }
            Ident(ref mut sym) if bindings.contains_key(sym) => {
                // If the site list for this symbol contains an ancestor or the current site, we
                // have not resolved it yet. Generate the binding at the appropriate site and
                // remove the site from the list.
                if sites.get(&sym).unwrap().contains(&current_site) {
                    // Generate the definition of this identifier and its dependencies.
                    let mut value = bindings.get(sym).cloned().unwrap();
                    self.generate_bindings(
                        &mut value,
                        bindings,
                        generated,
                        current_site,
                        stack,
                        sites,
                    );

                    let site_list = sites.get_mut(&sym).unwrap();

                    let delete_index =
                        if let Some(ref result) = site_list.get_with_index(&current_site) {
                            let index_in_list = result.0;
                            let site_with_expr = result.1;

                            // The depth gives us the index into the stack holding the bindings (e.g.,
                            // if the site is (0,1), we access the second Binding list in `stack`).
                            let index = site_with_expr.depth() - 1;
                            let binding_list = &mut stack[index];
                            binding_list.push((sym.clone(), value));
                            index_in_list
                        } else {
                            // We checked whether sites contains the current_site, and an identifier's dependencies
                            // can't depend on that identifier!
                            unreachable!()
                        };

                    // Delete this site - this implicitly marks the binding as generated for this
                    // site and all its children.
                    site_list.delete_index(delete_index);
                }
                true
            }
            _ => false,
        };

        if !handled {
            for child in expr.children_mut() {
                self.generate_bindings(child, bindings, generated, current_site, stack, sites);
            }
        }
    }
Generates bindings in the expression.

This injects the definition of each symbol into the correct position in the final
expression. Specifically, a symbol is defined in the highest site that symbol is used in.

The function updates `expr` with the symbol to value mappings in `bindings`. Bindings that
are already inserted are tracked in `generated`. The `stack` tracks sites to generate the
bindings in (where each site holds bindings to be generated at a particular site in the
expression tree), and `sites` maps each symbol to its highest site.
weld/src/optimizer/transforms/cse.rs