Using tablegen

Also today I figured out the problem with the tablegen tool. I have to include the directory where the intrinsic information can be found. The right syntax in my working environment is:
tblgen X86.td -I="$HOME/Programs/x86_llvm/include/".
For the PowerPC, use
tblgen PPC.td -I="$HOME/Programs/ppc_llvm/include/" -I="$HOME/Programs/ppc_llvm/lib/Target/".
Maybe I should point this, for the help in the page does not talk about the directory.

Graphic help

Hi, today I've used LLVM tool to visualize the dataflow graph. It is very cool, and very easy to use. Add Fn.viewCFG() to your application, where Fn is a MachineFunction object. It will open the gv window, and it is all. The guy who coded this functionality is great :) The graph that is produces is this one here. If you are using a remote machine, to open the gv window you have to set your environment. Do like this:

local.machine: open an xterm application
local.machine: ssh -X remote.machine
local.machine: xhost + remote.machine
remote.machine: export DISPLAY=local.machine:0.0
remote.machine: // any graphical program, e.g. gv cfg.ps &
local.machine: xhost - remote.machine // after having used the window

Hum... I am still having problem with those physical registers though. Where are they being defined? They are not in the in set of the function. EAX is in the out set, but this is clear in the control flow graph.

Done with liveness.

I think I finished my liveness analysis. Well, at least for virtual registers. You can check my API here. The implementation is here. Most of my problems were due to forgetting the '&' when trying to obtain references to vectors in the matrix... living and learning... Also, the matrix tends to be quite sparse, for basic blocks only have two branches at most. I may try to optimize it later. Tomorrow I will improve the control flow visualizer with the liveness analysis information. Also, I have to incorporate physical registers in the analysis, but I think such registers are not alive outside basic blocks. Wanna see the result of today's toils? Check it here. It is quite beautiful to me. Tomorrow: "que venha o visualizador"...

The weird world of C++

Today I just discovered that the matrix I had coded yesterday was completely messed up. Well, I am learning C++, and I start wondering if there is any logic underlying the semantics of this language. After dating Java, and enjoying the rude elegance of ANSI C, what is C++? Basically, There are three main ways you can refer to a data object in C++: As the object itself - by value; As the memory address of the object - by pointer; with an alias to the object - by reference. God, what is that? Why to add so much complexity to a programming language? Anyways, if you are as puzzled as me, you can find some very nice explanations about all this complexity in Mr. Crawford's webpage. Although I am frustrated with C++, I am getting the feeling that this language is like a wild horse, that, after tamed, may be a loyal friend.

Oh, about today. Well, the matrix class from yesterday now works fine. It is necessary to pass the objects that it holds by references. I just discovered that when a value is returned from a function (I thought it only occurred when the object was passed as parameter...), it is returned by value. The fixed code is here. A program that uses it is this one here.

Generic Matrix

Today I started coding my liveness analysis. I start preparing a pass that collects the liveness information of the control flow graph. For each pair of basic blocks u and v, it records the set of variables alive between u and v. The requirements in terms of space is O(N*N*T), where N is the number of basic blocks, and T is the total number of temporaries in the control flow graph. Notice that this program only records information about virtual registers. Physical registers are not supposed to be alive between basic blocks. The time complexity of the analysis will be O(T*N). Basically, each block is traversed once, and, for each temporary used, some blocks may have to be traversed in a backward fashion. The pass uses a matrix data structure. Each cell of the matrix is a vector. I coded a generic implementation of the matrix here.

Battling LiveVariables

Still battling with the class LiveVariables. I don't like the way it stores live range information. Also I don't like the traditional way of storing it. In/out sets simply do not reflect the state of a SSA program. I think liveness information should be stored in the edges of the control flow graph. The out set is the same for each instruction, but sometimes the same instruction has different branches, and the set of temporaries alive at each branch is not the same. Of course, this problem never happens with PHI functions. I will implement a liveness algorithm by myself.

But, what did I do today? Well, I worked with the LiveVariables class, and end up printing a graph like this one here... The source code of the class to print live ranges is in Fernando_LiveSet.cpp and Fernando_LiveSet.h. I shall have problems with Bernie...

Printing the live ranges of virtual registers.

Today I coded a little pass to print all the live range information.
LLVM stores this information in the LiveVariables class.
Basically, for each variable it holds:

• Unique definition point;
  
  
• Blocks that are crossed by the live range of the variable;
  
  
• Blocks where the live range is killed, that is, where it is used for the last time.
  
  

The code to print such information is very simple.