similar to: [LLVMdev] Doubts about register interferences in register allocators

On Sep 17, 2013, at 5:15 AM, Leandro Santiago <leandrosansilva at gmail.com> wrote: > Hello to all. I'm trying to implement a simple register allocator using graph colouring (I know, everyone has already done that :-)) and I'm also using LLVM 3.4 from master branch. > > The algorithm I'm using is based on the one described on the "Modern Compiler Implementation in

I'm working on my project for completion undergraduate courses, consisting of an experimental analysis of registers allocation algorithms. For this task, I am using the set of tools from the LLVM project. However, I have read the documentation of the LLVM project and not yet found a way to put the pieces of the puzzle together. So far I know: - As passes work as engage them to LLVM and

David Greene wrote: > On Saturday 01 May 2010 08:34:50 Josef Eisl wrote: >> Hello, >> >> I want learn more about register allocation and do some analysis for a >> current research project. After reading some papers (eg. Chaitin, >> Briggs) I think its time to get my hands dirty :). > > Welcome! > >> First I plan to (re)implement some of the classic

Good Night. I'm implementing a Interference Graph in the Register Allocation pass. I'm building this graph BEFORE any assignment of a virtual register to physical register. But I have a doubt about how to check the interference between two Live Intervals (i.e. They live at same point), should I use: L1->overlaps(L2) Where L1 and L2 are two different Live Intervals. Or should I use:

Hi, Anton and Fernando have answered most of your questions. I don't have anything to add there. I do want to comment on the "conservative" nature of LiveIntervalAnalysis. I think the comment is misleading and is probably just a relic of early implementation. The biggest problem with the current implementation is the overly aggressive copy coalescer. Right now the

Ok, just to clarify, RegUnits, as far I understand, are Physical registers or alias to Physical registers. They exist because some instructions use physical registers directly rather than virtual register. It's right? And why this RegUnits should be present in the Interference Graph? I thought were only the Live Intervals would be the nodes of the graph. Sorry about the trouble to

Toward a better register allocator, I'm attempting to understand the dataflow information available to the allocator. What's the difference between LiveInterval information and LiveVariable information? If a LiveInterval is based on a linear ordering of the machine instructions, isn't it rather conservative in nature? Let's say I have a typical diamond CFG: A

LiveVariables gives you something like liveness analysis: where each variable is alive, that is, across each basic blocks, where it is defined, and where it is killed. LiveIntervals gives you a linear representation of the variables as a set of intervals. Yes, it handle holes in the live ranges. There is a very nice description of these analysis and related data structures here:

Hello, I want learn more about register allocation and do some analysis for a current research project. After reading some papers (eg. Chaitin, Briggs) I think its time to get my hands dirty :). First I plan to (re)implement some of the classic approaches to get familiar with the framework. At the beginning the following questions came up: - Is there some documentation about register allocation

On 4/3/07, David Greene <greened at obbligato.org> wrote: > > Toward a better register allocator, I'm attempting to understand > the dataflow information available to the allocator. > > What's the difference between LiveInterval information and LiveVariable > information? If a LiveInterval is based on a linear ordering of > the machine instructions, isn't it

On Saturday 01 May 2010 08:34:50 Josef Eisl wrote: > Hello, > > I want learn more about register allocation and do some analysis for a > current research project. After reading some papers (eg. Chaitin, > Briggs) I think its time to get my hands dirty :). Welcome! > First I plan to (re)implement some of the classic approaches to get > familiar with the framework. Before

Hi all, As I work toward improving LLVM register allocation, I've come across the need to do some refactoring. Specifically, I would like to separate register coalescing from live interval analysis. Right now LiveIntervals handles both. The reason I want to separate them is that other types of register allocators might like to do coalescing differently (e.g. graph coloring does it by

Fernando Magno Quintao Pereira wrote: > LiveVariables gives you something like liveness analysis: where each > variable is alive, that is, across each basic blocks, where it is defined, > and where it is killed. If I read this correctly, it means that at each instruction there's a list of live variables? I'm trying to figure out how to get at this information to build the

Here's a proposed patch for reworking register coalescing to allow pluggable coalescers. I think I've got the interfaces where I want them and am reasonably sure I've squashed most of the bugs. I'm still doing some testing and want to get through a whole regimen before committing. As a reminder, this patch has several goals: - Allow user-specified register coalescers, similar

On Tuesday 04 May 2010 05:45:36 Josef Eisl wrote: > >> - As far as I understand it, register allocators are implemented as > >> MachineFunctionPasses. Does a MachineFunction object contain all > >> information needed for a (classic) allocator? > > > > It has the instructions, operands and dependencies among them. There's > > a

Hi (Jakob), in reference to the prior message below, I have the following follow-up questions, as I also need a scheduling pass prior to regalloc. I need to do this in order to set VLIW-flags, so that the RA is aware of several MI's per cycle with a redefined LiveRange::overlap-function. On a multiple-issue cycle, a register that gets killed can be reused by another MI - these live ranges do

On Jul 11, 2007, at 11:39 AM, David Greene wrote: > On Wednesday 11 July 2007 12:41, Tanya M. Lattner wrote: > >> I think the coalescer should be flexible enough to be run >> independent of >> the register allocator. For example, you may want to expose the >> copies >> induced by transforming out of SSA to the scheduler. If the >> scheduler is

On May 24, 2011, at 8:22 AM, Jonas Paulsson wrote: > Hi (Jakob), > > in reference to the prior message below, I have the following follow-up questions, as I also need a scheduling pass > prior to regalloc. I need to do this in order to set VLIW-flags, so that the RA is aware of several MI's > per cycle with a redefined LiveRange::overlap-function. On a multiple-issue cycle, a

On 20/09/05, Chris Lattner <sabre at nondot.org> wrote: > > because LiveVariables do not provide an interface to iterate through > > all viritual registers. > > Ok, you could add a method to LiveVariables that returns > VirtRegInfo.size(). The virtual registers are defined by the range: > [MRegisterInfo::FirstVirtualRegister, >

Hi David, Thanks for this patch! Some comments: 1. typedef std::set<const LiveInterval *> IntervalSet; Please use SmallPtrSet instead. 2. + virtual void mergeIntervals(const LiveInterval &a, + const LiveInterval &b, + const MachineInstr &copy) {}; I find the name misleading. It's not actually