15-745 Fall '03
Notes on Assignments and Exams

In the following, the term HOME745 refers to the home directory for the course, namely /afs/cs.cmu.edu/academic/class/15745-f03/public.

The following information is in reverse order of assignment, i.e., the most recent assignment appears first.

Assignment 3: PS | PDF

Deadline extended to Tuesday, 10/21 at 5pm

The Muchnick algorithm is somewhat lacking when it comes to handling control dependencies. You should find the "Fixing DCE" section of the "SSA & CCP & DCE & CDG" lecture helpful in figuring out the correct approach. In addition, you can pick up the relevant chapter from Robert Morgan's book "Building an Optimizing Compiler" from outside my office (Weh 3723). Both sources assume that the graph is in SSA form, but the control dependence finding portion is useful even without SSA.

Marking all instructions that have any note attached to them may not delete very many instructions. Only marking those instructions with the k_header_trailer note should be sufficient.

Assignment 2: PS | PDF

The source code for the testing program (do_rd_test) can be found at 

/afs/cs.cmu.edu/academic/class/15745-f03/public/Linux/machsuif-2.02.07.15/rd_test
There's an executable at 
/afs/cs/academic/class/15745-f03/public/Linux/nci/bin/do_rd_test
Feel free to copy the source code and build your own binary. Keep in mind that this will link to libbvd.so at runtime. The way we've setup your environment, this will first attempt to link against any local copies (in your localnci/solib directory) and then against the global copies. The global copy (/afs/cs.cmu.edu/academic/class/15745-f03/public/Linux/nci/solib/libbvd.so) contains a fully implemented reaching definitions pass. This is what you need to implement in your local copy.

When testing, make sure you are testing your locally built libbvd.so

Here's an example of what the output of do_rd_test should look like: 

test.c:
int foo(int a)
{
  if(a < 0)
    return -a;
  else
    return a;
}

do_print test.afg:
        # [target_lib: "x86"]
        .file   "test.c"        # 2
        .text
        .align  2
        .align  2
        .globl  foo
        # .loc  2 0
foo:
        movl    $0,$vr0
        cmpl    $vr0,foo.a
        jge     foo._testTmp0
        # .loc  2, 4
        movl    foo.a,$vr1
        negl    $vr1
        movl    $vr1,%eax
        # [regs_defd: "sparse", 8, 12]
        ret
        # [instr_ret: s32]
        # [regs_used: "sparse", 0]
        # [incomplete_proc_exit]
        jmp     foo._testTmp1
foo._testTmp0:
        # .loc  2, 6
        movl    foo.a,%eax
        # [regs_defd: "sparse", 8, 12]
        ret
        # [instr_ret: s32]
        # [regs_used: "sparse", 0]
        # [incomplete_proc_exit]
foo._testTmp1:
        ret
        # [instr_ret]
        # [incomplete_proc_exit]


do_rd_test test.afg:
Processing file test.c

Processing unit "foo"

Definitions reaching entry of node 0: {}
Definitions reaching exit  of node 0: {}

Definitions reaching entry of node 1: {}
[0>             [proc entry]
[1>             movl    $0,$vr0
                cmpl    $vr0,foo.a
                jge     foo._testTmp0
Definitions reaching exit  of node 1: {0-1}

Definitions reaching entry of node 2: {0-1}
[2>             movl    foo.a,$vr1
[3>             negl    $vr1
                movl    $vr1,%eax
                ret
Definitions reaching exit  of node 2: {0-1,3}

Definitions reaching entry of node 3: {}
                jmp     foo._testTmp1
Definitions reaching exit  of node 3: {}

Definitions reaching entry of node 4: {0-1}
        foo._testTmp0:
                movl    foo.a,%eax
                ret
Definitions reaching exit  of node 4: {0-1}

Definitions reaching entry of node 5: {}
        foo._testTmp1:
                ret
Definitions reaching exit  of node 5: {}

Definitions reaching entry of node 6: {0-1,3}
Definitions reaching exit  of node 6: {0-1,3}

Assignment 1: PS | PDF

The first assignment should be done individually. Future assignments will require partners.

Back to CS745 home page.