4
\$\begingroup\$

This is the first real program I have written in rust. What started as a clean piece of rust code, turned into a lifetime monstrosity when I decided to make my enums and structs use &str instead of String. The algorithm implemented is irrelevant; I just need help making my code more idiomatic and clean. Here is (quite simple) my code:

use std::collections::HashMap;
use std::hash::{Hash, Hasher};

#[derive(Debug, PartialEq, Eq)]
struct BasicBlock<'a> {
    block_id: u32,
    code: Vec<IRCode<'a>>,
    preds: Vec<Box<BasicBlock<'a>>>,
    succs: Vec<Box<BasicBlock<'a>>>,
}

#[derive(Debug, PartialEq, Eq)]
enum IRCode<'a> {
    Basic {
        value: &'a str,
        btype: Type,
        id: u32,
    },
    Quadruple {
        op: Op,
        params: Vec<IRCode<'a>>,
        location: Storage<'a>,
    },
    // and some more...
}

#[derive(Debug, PartialEq, Eq)]
enum Type {
    TVarRef,
    // and some more...
}

#[derive(Debug, PartialEq, Eq)]
enum Storage<'a> {
    Temp { name: &'a str },
}

#[derive(Debug, PartialEq, Eq)]
enum Op {
    Add,
    Sub,
}

impl<'a> Hash for BasicBlock<'a> {
    fn hash<H: Hasher>(&self, state: &mut H) {
        self.block_id.hash(state);
    }
}

#[derive(Debug)]
struct SSA<'a> {
    count: HashMap<&'a str, u32>,
    current_def: HashMap<&'a str, HashMap<Box<&'a BasicBlock<'a>>, Box<IRCode<'a>>>>,
}

impl<'a> SSA<'a> {
    fn new() -> SSA<'a> {
        SSA {
            count: HashMap::new(),
            current_def: HashMap::new(),
        }
    }

    fn new_variable(&mut self, name: &'a str, block: &'a BasicBlock<'a>) -> &Box<IRCode<'a>> {
        // If `name` is not in `count`, insert `(name, 0)`; else increment the count
        *self.count.entry(name).or_insert(0) += 1;
        self.current_def.entry(name).or_insert(HashMap::new());
        self.current_def.get_mut(&name).unwrap().insert(
            Box::new(block),
            Box::new(IRCode::Basic {
                value: name,
                btype: Type::TVarRef,
                id: *self.count.get(&name).unwrap(),
            }),
        );
        self.current_def.get(&name).unwrap().get(&block).unwrap()
    }
}

fn main() {
    // very simple test case
    let mut ssa = SSA::new();
    let bb0 = BasicBlock {
        block_id: 0,
        code: vec![],
        preds: vec![],
        succs: vec![],
    };
    println!("{:?}", ssa.new_variable("foo", &bb0));
    println!("{:?}", ssa);
}

Thanks!

\$\endgroup\$
3
  • 2
    \$\begingroup\$ The current question title, which states your concerns about the code, applies to too many questions on this site to be useful. The site standard is for the title to simply state the task accomplished by the code. Please see How do I ask a good question?. \$\endgroup\$
    – BCdotWEB
    Dec 1, 2020 at 9:11
  • 2
    \$\begingroup\$ Why do you want to use &str instead of String in these cases? The best way of approaching this will depend on what you are trying to accomplish. \$\endgroup\$ Dec 3, 2020 at 6:56
  • \$\begingroup\$ @WinstonEwert -- I had some trouble using String (that is what I initially used). Also, I've heard &str is better for just looking into strings (not modifying them). \$\endgroup\$
    – xilpex
    Dec 4, 2020 at 0:41

2 Answers 2

3
+100
\$\begingroup\$

Hello and welcome to the Rust community.

After a single read of your code, I have a couple comments.

  • your problems with &str as well as keying by block_id would be best remedied by putting interners in SSA. The best interner choice would be string-interner or internment.
  • in fn new_variable, you have repeated lookups for the same entry of current_def. LLVM will be unable to optimize out repeated accesses to HashMap. This may slow us down by something like 120~200ns per invocation of the function, because one HashMap lookup takes approx. 40~70ns.
  • you have Vec<Box<...>> and HashMap<Box<...>,Box<...>>. This inclusion of Box within another container immediately raises a flag in the mind of a Rust programmer that the code is not cleaned up. Wrapping in Box does not provide anything over wrapping in Vec, HashMap or any other container. All wraps provide unique ownership with memory indirection. To illustrate with an example, Box<[T]> is almost like Vec in that both are owned dynamic-length slices (indexable memory ranges) except that Box<[T]> does not allow any overprovisioning of memory (Vec can have capacity above length).
  • the SSA::current_def type expression is basically as long as your average tweet. Break down complex types longer than 30-40 characters into smaller definitions.

We will begin by changing SSA and fn new_variable, with new structure SSADef:

#[derive(Debug)]
struct SSA<'a> {
    content: HashMap<&'a str, SSADef<'a>>,
}

#[derive(Debug)]
struct SSADef<'a> {
    count: u32,
    current_def: HashMap<&'a BasicBlock<'a>, IRCode<'a>>,
}

impl<'a> SSA<'a> {
    fn new() -> SSA<'a> {
        SSA { content: HashMap::new() }
    }

    fn new_variable<'s>(&'s mut self, name: &'a str, block: &'a BasicBlock<'a>) -> &'s IRCode<'a> {
        // If `name` is not in `content`, insert `SSADef::new()`
        let def = self.content.entry(name).or_insert_with(SSADef::new);
        // Increment the count
        def.count += 1;
        def.current_def.entry(block).or_insert(
            IRCode::Basic {
                value: name,
                btype: Type::TVarRef,
                id: def.count,
            }
        )
    }
}

impl<'a> SSADef<'a> {
    fn new() -> SSADef<'a> {
        SSADef {
            count: 0,
            current_def: HashMap::new(),
        }
    }
}

One minor observation: you can derive Default for SSA and SSADef and call default from both news. This will put 0s and empty HashMaps and other default values in the fields of these structures.

We add the StringInterner. I assume the deeper functionality will always have easy access to top level SSA, and consequently easy access to the interner. If not, we can use some other crate such as internment which provides an appropriate API.

Changing the BasicBlocks for interning is left as an exercise for the reader. We arrive at the following code, which has very few 'as left. This is all I can do without knowledge of the algorithm, I believe:

use std::collections::HashMap;
use std::hash::{Hash, Hasher};

use string_interner::{StringInterner, DefaultSymbol as Sym};

#[derive(Debug, PartialEq, Eq)]
struct BasicBlock {
    block_id: u32,
    code: Vec<IRCode>,
    preds: Vec<BasicBlock>,
    succs: Vec<BasicBlock>,
}

#[derive(Debug, PartialEq, Eq)]
enum IRCode {
    Basic {
        value: Sym,
        btype: Type,
        id: u32,
    },
    Quadruple {
        op: Op,
        params: Vec<IRCode>,
        location: Storage,
    },
    // and some more...
}

#[derive(Debug, PartialEq, Eq)]
enum Type {
    TVarRef,
    // and some more...
}

#[derive(Debug, PartialEq, Eq)]
enum Storage {
    Temp { name: Sym },
}

#[derive(Debug, PartialEq, Eq)]
enum Op {
    Add,
    Sub,
}

impl Hash for BasicBlock {
    fn hash<H: Hasher>(&self, state: &mut H) {
        self.block_id.hash(state);
    }
}

#[derive(Debug, Default)]
struct SSA<'a> {
    content: HashMap<Sym, SSADef<'a>>,
    interner: StringInterner,
}

#[derive(Debug, Default)]
struct SSADef<'a> {
    count: u32,
    current_def: HashMap<&'a BasicBlock, IRCode>,
}

impl<'a> SSA<'a> {
    fn new() -> SSA<'a> {
        SSA::default()
    }

    fn new_variable<'s>(&'s mut self, name: &'a str, block: &'a BasicBlock) -> &'s IRCode {
        let name_sym = self.interner.get_or_intern(name);
        // If `name` is not in `content`, insert `SSADef::new()`
        let def = self.content.entry(name_sym).or_insert_with(SSADef::new);
        // Increment the count
        def.count += 1;
        def.current_def.entry(block).or_insert(
            IRCode::Basic {
                value: name_sym,
                btype: Type::TVarRef,
                id: def.count,
            }
        )
    }
}

impl<'a> SSADef<'a> {
    fn new() -> SSADef<'a> {
        SSADef::default()
    }
}

fn main() {
    // very simple test case
    let mut ssa = SSA::new();
    let bb0 = BasicBlock {
        block_id: 0,
        code: vec![],
        preds: vec![],
        succs: vec![],
    };
    println!("{:?}", ssa.new_variable("foo", &bb0));
    println!("{:?}", ssa);
}
```
\$\endgroup\$
2
  • \$\begingroup\$ Thanks for the great answer! I was wondering if I had another IRCode variant that had a field that was supposed to be a reference to a BasicBlock, would I add a lifetime? \$\endgroup\$
    – xilpex
    Dec 7, 2020 at 19:43
  • \$\begingroup\$ @xilpex you would best add Rc<BasicBlock> (or Arc) or a symbol from an interner. \$\endgroup\$ Dec 8, 2020 at 15:35
3
\$\begingroup\$

Peter Blackson has offered a lot of good points.

Here, I'll focus on one particular issue: your use of references and lifetimes. In particular, you store &str and &BasicBlock in your data structures. This is not a good idea. You should use plain String and BasicBlock.

To see why, let's make a slight change to your code:

 fn build_ssa() -> SSA 
    // very simple test case
    let mut ssa = SSA::new();
    let bb0 = BasicBlock {
        block_id: 0,
        code: vec![],
        preds: vec![],
        succs: vec![],
    };
    ssa.new_variable(&format!("&{}", 12), &bb0);
    ssa
}

You'll find that this won't work. The bb0 BasicBlock will be destroyed at the end of the build_ssa function. The string created by the format macro will be destroyed at the end of that line. Both will prevent you from returning the SSA struct from this function.

That's why you most likely want to have SSA take ownership of both the BasicBlocks and strings. To do so, use String and BasicBlock rather than &str and &BasicBlock.

Now, you've heard that you should use &str when you only need to read the string and not modify it. Here, however, you want to store the string in the SSA. Functions that store values will usually need to take ownership of the value, and not merely take a reference.

Now, there is a use case for the sort of structure you did here. That's when you want to share memory between two data structures. For example, if your SSA was produced following an AST, you might want to share memory used for the strings since they probably appear in both your AST and your SSA. On the other hand, you might not, since you plausibly want to throw away your AST when you are finished with it.

\$\endgroup\$
2
  • \$\begingroup\$ For example, if your SSA was produced following an AST -- I'm getting the feeling you know that algo I am implementing :) \$\endgroup\$
    – xilpex
    Dec 7, 2020 at 0:18
  • \$\begingroup\$ @xiipex, well there is very little other reason to be building an SSA :) \$\endgroup\$ Dec 7, 2020 at 17:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.