search for: getcandidatepairs

Hi, I see that there are two functions in your code that are O(n^2) in number of instructions of the program: getCandidatePairs and buildDepMap. I think that you could make these two functions faster if you work on some form of factored def-use chains for memory, like the VUSE/VDEFs of GCC. I was trying to find a similar representation in LLVM: isn't there already a virtual SSA representation for memory references in...

On Tue, 2011-12-20 at 13:57 -0600, Sebastian Pop wrote: > Hi, > > I see that there are two functions in your code that are O(n^2) in > number of instructions of the program: getCandidatePairs and > buildDepMap. I think that you could make these two functions faster > if you work on some form of factored def-use chains for memory, like > the VUSE/VDEFs of GCC. Thanks for the comment! I am not aware of anything along these lines, although it would be quite helpful. The pass spe...

...of view I am not yet completely convinced the >> algorithm itself is not worse than N^2. I really want to understand this >> part better and plan to look into problematic behaviour in functions not >> directly visible in the core routines. > > Here are my thoughts: > > getCandidatePairs - This is O(N^2) in the number of instructions in BB. > [This assumes that all of the external helper functions, especially > queries to alias and scalar-evolution analysis don't make the complexity > worse]. Yes. Alias analysis and scalar-evolution are queries that may not be fast e...

...> On the algorithmic point of view I am not yet completely convinced the > algorithm itself is not worse than N^2. I really want to understand this > part better and plan to look into problematic behaviour in functions not > directly visible in the core routines. Here are my thoughts: getCandidatePairs - This is O(N^2) in the number of instructions in BB. [This assumes that all of the external helper functions, especially queries to alias and scalar-evolution analysis don't make the complexity worse]. computeConnectedPairs - For each candidate pair, there are O(N^2) in the worse case, this l...

...d::pair<std::multimap<ValuePair, ValuePair>::iterator, > + std::multimap<ValuePair, ValuePair>::iterator> > + VPPIteratorPair; > + > + // FIXME: const correct? > + > + bool vectorizePairs(BasicBlock&BB); > + > + void getCandidatePairs(BasicBlock&BB, > + std::multimap<Value *, Value *> &CandidatePairs, > + std::vector<Value *> &PairableInsts); > + > + vojd computeConnectedPairs(std::multimap<Value *, Value *> &CandidatePairs, > +...

...aluePair>::iterator, > > + std::multimap<ValuePair, ValuePair>::iterator> > > + VPPIteratorPair; > > + > > + // FIXME: const correct? > > + > > + bool vectorizePairs(BasicBlock&BB); > > + > > + void getCandidatePairs(BasicBlock&BB, > > + std::multimap<Value *, Value *> &CandidatePairs, > > + std::vector<Value *> &PairableInsts); > > + > > + vojd computeConnectedPairs(std::multimap<Value *, Value *> &Candi...

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

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 >