search for: pairable

Hi Arnaud, I'm glad to hear that your test case is working. I however still get my wrong allocation in some non trivial cases : the > pairing constraint is not fulfilled. > > I have tried to modify the 'ensure pairable' pass (the pass undoing some > of the coalescer's work) to always insert register copies for > instructions with the pairable constraint, instead of being smart and > inserting the copy only when needed. This had no visible effect. > Although I am deriving from PBQPBuilder, the...

...>> This is very interesting work. Thanks. Quick questions / comments. >> >> 1. What's the algorithm complexity? > > Roughly, it is O(N^2), where N is the number of instructions in a basic > block, but: > - The run time only *really* grows with the number of "pairable" > instructions; this is *generally* a much smaller number than the total > number of instructions (except in test cases). Also determining whether > two loads or stores are pairable is more expensive than for other kinds > of instructions because scalar-evolution analysis is used....

Hi Lang, The assert is not triggered any longer on my testcases :) I however still get my wrong allocation in some non trivial cases : the pairing constraint is not fulfilled. I have tried to modify the 'ensure pairable' pass (the pass undoing some of the coalescer's work) to always insert register copies for instructions with the pairable constraint, instead of being smart and inserting the copy only when needed. This had no visible effect. Although I am deriving from PBQPBuilder, the PBQP seems to be coa...

...t; > > the > > > edge costs, and they look ok. > > > > > > I also attached my target's pbqp related file in case you want to > > > double check what I did. This is llvm-3.0 based. It comprises 2 > > > passes : the FemtoPBQPBuilder, plus a FemtoPairablepass, which undo > > > some of the coalescer's work. The insertRegCopy may specifically > > > need a double check, as I am not 100% sure to have updated > > > correctly the LiveInterval information. > > > > > > In terms of registers, the Femto target...

Which options are you seeing that cause the largest difference, and on which targets? As Chandler mentioned there has been a large amount of variation in x86 targets, and there are certain optimizations that can be done, on say a Pentium (scheduling instructions which are pairable and non-dependent so the U and V pipelines are saturated without contention, for example) that don't make sense to take the time with on a true i386 target. Likewise there were certain optimizations on the i386 such as decomposing multiplications into left shifts which generally wouldn't b...

..., etc) should be nouns and start with an upper-case letter (e.g. TextFileReader)." > + void getCandPairs(unsigned vBits, BasicBlock&BB, > + std::multimap<Value *, Value *> &candPairs, > + std::vector<Value *> &pairableInsts); "Variable names should be nouns (as they represent state). The name should be camel case, and start with an upper case letter (e.g. Leader or Boats)." This happens at several places. Can you check your code for this. > + void replValues(BasicBlock&BB, > +...

This is very interesting work. Thanks. Quick questions / comments. 1. What's the algorithm complexity? 2. Please rename -vectorize to -bb-vectorize since this is a specific kind of vectorization. 3. Have you tried non-x86 targets? Does it work? If not, what would it take to make it work? I am concerned that LLVM currently does not have a cost model for vectorization. That's necessary for

...nd start with an upper-case letter (e.g. TextFileReader)." > > > > + void getCandPairs(unsigned vBits, BasicBlock&BB, > > + std::multimap<Value *, Value *> &candPairs, > > + std::vector<Value *> &pairableInsts); > > "Variable names should be nouns (as they represent state). The name > should be camel case, and start with an upper case letter (e.g. Leader > or Boats)." > > This happens at several places. Can you check your code for this. > > > + void replV...

I have been doing some benchmarking on x86 using llvm 2.9 with the llvm-gcc 4.2 front end. I noticed that the -march and -mtune options make a significant positive difference in x86-32 mode but hardly make any difference in x86-64 mode. The small difference that I am measuring when the target is x86-64 could easily be random variation, while for the x86-32 target I am measuring a huge difference

On Mon, 2011-11-21 at 11:55 -0600, Hal Finkel wrote: > Tobias, > > I've attached an updated patch. It contains a few bug fixes and many > (refactoring and coding-convention) changes inspired by your comments. > > I'm currently trying to fix the bug responsible for causing a compile > failure when compiling >

Tobias, et al., Attached is the my autovectorization pass. I've fixed a bug that appears when using -bb-vectorize-aligned-only, fixed some 80-col violations, etc., and at least on x86_64, all test cases pass except for a few; and all of these failures look like instruction-selection bugs. For example: MultiSource/Applications/ClamAV - fails to compile shared_sha256.c with an error: error in

Tobias, I've attached the latest version of my autovectorization patch. I was able to add support for using the ScalarEvolution analysis for load/store pairing (thanks for your help!). This led to a modest performance increase and a modest compile-time increase. This version also has a cutoff as you suggested (although the default value is set high (4000 instructions between pairs) because

...using a different (or additional) data structure to hold the candidate pairs. I should probably add a candidate-pair DenseSet to clean this up, then it will be O(N^2) [note that if an instruction has many uses, then it cannot be in many candidate pairs]. buildDepMap - This records all uses of each pairable instruction; as implemented, this is also O(N^2). choosePairs - As you point out, this is the most complicated to figure out. The reason is that it deals with connected pairs and that, as pairs are selected, other pairs are dropped from contention. Fundamentally, it is considering pair-to-pair int...

...---------------------------------------------------------------------===// > +// > +// This file implements a basic-block vectorization pass. The algorithm was > +// inspired by that used by the Vienna MAP Vectorizor by Franchetti and Kral, > +// et al. It works by looking for chains of pairable operations and then > +// pairing them. > +// > +//===----------------------------------------------------------------------===// > + > +#define BBV_NAME "bb-vectorize" > +#define DEBUG_TYPE BBV_NAME > +#include "llvm/Constants.h" > +#include "llvm/D...

...-------------------------------------------------===// > > +// > > +// This file implements a basic-block vectorization pass. The algorithm was > > +// inspired by that used by the Vienna MAP Vectorizor by Franchetti and Kral, > > +// et al. It works by looking for chains of pairable operations and then > > +// pairing them. > > +// > > +//===----------------------------------------------------------------------===// > > + > > +#define BBV_NAME "bb-vectorize" > > +#define DEBUG_TYPE BBV_NAME > > +#include "llvm/Constants....

On Mon, 2011-11-21 at 21:22 -0600, Hal Finkel wrote: > On Mon, 2011-11-21 at 11:55 -0600, Hal Finkel wrote: > > Tobias, > > > > I've attached an updated patch. It contains a few bug fixes and many > > (refactoring and coding-convention) changes inspired by your comments. > > > > I'm currently trying to fix the bug responsible for causing a compile

...nal) > data structure to hold the candidate pairs. I should probably add a > candidate-pair DenseSet to clean this up, then it will be O(N^2) [note > that if an instruction has many uses, then it cannot be in many > candidate pairs]. > > buildDepMap - This records all uses of each pairable instruction; as > implemented, this is also O(N^2). > > choosePairs - As you point out, this is the most complicated to figure > out. The reason is that it deals with connected pairs and that, as pairs > are selected, other pairs are dropped from contention. Fundamentally, it > is...

...t; > > > > > On Fri, Oct 21, 2011 at 7:04 PM, Hal Finkel <hfinkel at anl.gov> > > > wrote: > > > > I've attached an initial version of a basic-block > > > > autovectorization > > > > pass. It works by searching a basic block for pairable > > > > (independent) > > > > instructions, and, using a chain-seeking heuristic, selects > > > > pairings > > > > likely to provide an overall speedup (if such pairings can be > > > > found). > > > > The selected pairs are the...

...gt; > On Fri, Oct 21, 2011 at 7:04 PM, Hal Finkel <hfinkel at anl.gov> > > > > wrote: > > > > > I've attached an initial version of a basic-block > > > > > autovectorization > > > > > pass. It works by searching a basic block for pairable > > > > > (independent) > > > > > instructions, and, using a chain-seeking heuristic, selects > > > > > pairings > > > > > likely to provide an overall speedup (if such pairings can be > > > > > found). > > > > &...

..., Hal Finkel <hfinkel at anl.gov> > > > > > > wrote: > > > > > > > I've attached an initial version of a basic-block > > > > > > > autovectorization > > > > > > > pass. It works by searching a basic block for pairable > > > > > > > (independent) > > > > > > > instructions, and, using a chain-seeking heuristic, selects > > > > > > > pairings > > > > > > > likely to provide an overall speedup (if such pairings can be > > >...