Weekend's results.

I had to substantially change the phi-elimination algorithm, because I had not considered spills when I first wrote it. Now I think the algorithm is practically done. All the programs in this directory have been compiled with only [R2, R3, R4, R5, R30, R29, R31, R0, R1, LR]

spill, arghhh

Today I discovered that spills are crashing the phi deconstruction algorithm. Short story: it is possible that a phi equation uses the same physical registers in different definitions. Consequence: the phi functions are not in SSA form. I don't know how to handle this case. I will have to study it tomorrow more carefully.

Changing number regs

I have reduced the number of available registers to test my results. This allows me to see how the spilling algorithm is working. Well, the algorithm is working, somehow... but there are still some bugs to be fixed. The problem is that the code been generated is not good. Anyways, to change the number of registers in the target architecture is fairly easy, and I own this information to a nice gentleman who answered my question in the discussion list. Copying his words: "inside the TargetRegsterInfo.td file just search for RegisterClass - the last parameter of which is a list of registers. Just commenting some out is one way to avoid them being used. More polite is to explicitly exclude some registers from the "allocation order" - see IA64RegisterInfo.td:443 for an example of this (there, numReservedRegs worth of registers are hidden.)"

Spill code

I am working on the spilling part of the algorithm. Today I sort of finished a wrong implementation... but I have high hopes that I can fix it by Thursday.

Spills

I have decided to use the VirtRegMap class in order to place the spill code. I have been working on this yesterday, and today. The main problem is that I had to change much of my data structures to accommodate the creation of new virtual registers. For example, the interference graph now looks like this. Besides this, I have not been able to put the whole code running. But I know where the bugs are (I know some of them - no one knows all of them).

cr0/cr7

So, I am back! And I discovered a very sinister bug in my allocator... well, I cannot solve it yet. I don't know exactly what is happening. Let me tell the whole story. Can you see this assembly? So, my allocator is
assigning cr0 where linear scan is using cr7. Now, how linear scan knows that it should be cr7 instead of cr0? There is no conflict between the original temporaries. You can check this in the control flow graph here. I will postpone this bug for the moment, because tomorrow I will be dealing with spill. Oh, if you want to see the program that caused this weird bug, it is this one.

Travel tomorrow

Tomorrow I am traveling to San Francisco! This is good news, because I really want to rest for a while. The bad news is that I will only start working on Summer of Code this next Saturday. Well, how is the project going? I can compile some programs. Check here. But I am still getting some bugs, even without spilling. I hope to work on these bugs next week. I think I have still one more month to go.

Pre-colored registers

I am currently having problems with pre-colored registers. Those are virtual registers that must be assigned a fixed color. Well, one can think on them as physical registers that exist before register allocation. The problem is that, without the pre-colored registers, a simple linear scan of the SSA-code would generate optimal coloring. But, because of them, this does not happen. In order to avoid them, I am building a little interference graph. It only includes interferences between physical and virtual registers. This helps not assigning a register p to a virtual v when p and v interfere (p is pre-colored). The spilling algorithm is looking something like:

allocate(Virt op) {
  if(reg_mappping->there_is_free_reg(class(op))) {
    Phys color = reg_mappping->get_free_reg(class(op));
    reg_mappping->allocate_reg(op, color);
  } else {
    if(reg_mappping->there_is_unused_reg(class(op))) {
      Phys pre_col = reg_mappping->unused_reg(class(op));
      reg_mappping->allocate_reg(op, pre_col);
      spill(op);
    } else {
      Virt spill_c =
      reg_mappping->choose_reg_to_spill(class(op));
      Phys color = reg_mappping->get_color(color);
      spill(spill_c);
      reg_mappping->allocate_reg(op, color);
      if(reg_mappping->interfere(op, color)) {
        spill(op);
      }
    }
  }
}

The first if is used if there are free registers to be allocated to op. In this case, nothing very fancy has to be done: the free color is simply assigned to the operand. The else handles the case when spills must happen. In the first test, there are, indeed, free registers, but they will interfere with the operand later, because they are alive as pre-colored registers. So, the operand is spilled. In the other case, there are no free register at all, and a virtual register must be spilled. After a good candidate is found, it is spilled, and its color is now used to allocate the operand. If the operand and the new color interfere, the operand will have to be spilled too.

Good news!

More programs correctly compiled! As I told before, I had finished the algorithm of elimination of phi-functions. The algorithm is cute. The problem were the critical edges. They might be still a problem, for I have not done many tests. But I am very proud of the programs that I am compiling right now. Check for example loop.c, or base1sum.c.

Done with critical edges?

Ok, I think I am done with the remotion of critical edges. Well, semi-done, for I'm only removing the edges that are inserted during the dag selection phase. I think this is enough, for I am also using LLVM pass to break critical edges. My machine pass to break critical edges is given here: (cpp and h). The code is so simple... even though, it took me almost forever to figure it how to insert branches in basic blocks, or simply how to discover the end of a basic block. Now I think the code is working fine. But the compiler still has bugs :(

Incorrect control flow graph

I could not work on LLVM these last two days. Well, it was the first gap, I think, since the project started. I am still having problems with critical edges. But today I changed the implementation of PPCInstrInfo to accommodate goto instructions. The code looks better, but I am still having problems with producing a correct control flow graph.

Frustrating

Today I inserted the break critical edge pass. It indeed broke some critical edges, but not all. I am getting a very weird basic block, and the pass did not broke its critical edge. Trying to find what is going on here was a quite frustrating experience: the code is gigantic, and I could not find where some passes are inserted. The list of passes that is been invoked is here.

I hate Critical Edges!

I finished coding the algorithm to destroy phi-functions. Actually, I had finished this algorithm two days ago, but I could not test it properly, because the control flow graphs that I was getting from LLVM still have critical edges. Well, I tried to use the LLVM pass to remove critical edges (lib/Transforms/Utils/BreakCriticalEdges.cpp), but I could not. For some reason, this pass conflicts with other passes, and it turns out that it does not work simply to call this pass in my register allocator. I end up adapting it to be used as an analysis pass, and I think the code is all right (I did not write comments and update the file, because it is not working, and I think I will have to throw it away). The only problem is that it does not work. The changes that it performs in the control flow graph are not reflected in the final code :( I really wish I could understand what is going on here... but I also discovered that the code in lib/Transforms/Utils/BreakCriticalEdges.cpp is indeed called by the compiler. I will try to modify it, because there is still two pesky critical edges in the final loop.