search for: builddepmap

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 LLVM? Thanks, S...

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 spends a significant amo...

...td::multimap<value_pair, value_pair> connPairs; > + computeConnPairs(candPairs, pairableInsts, connPairs); > + if (!connPairs.size()) return false; > + > + // Build the pairable-instruction dependency map > + DenseSet<value_pair> pairableInstUsers; > + buildDepMap(BB, candPairs, pairableInsts, pairableInstUsers); > + > + // There is now a graph of the connected pairs. For each variable, pick the > + // pairing with the largest tree meeting the depth requirement on at least > + // one branch. Then select all pairings that are part of that...

...be changed by 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 f...

...lue_pair> connPairs; > > + computeConnPairs(candPairs, pairableInsts, connPairs); > > + if (!connPairs.size()) return false; > > + > > + // Build the pairable-instruction dependency map > > + DenseSet<value_pair> pairableInstUsers; > > + buildDepMap(BB, candPairs, pairableInsts, pairableInstUsers); > > + > > + // There is now a graph of the connected pairs. For each variable, pick the > > + // pairing with the largest tree meeting the depth requirement on at least > > + // one branch. Then select all pairings t...

...ey, not both), but that could be changed by 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. Fundamen...

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

...); > + > + vojd computeConnectedPairs(std::multimap<Value *, Value *> &CandidatePairs, > + std::vector<Value *> &PairableInsts, > + std::multimap<ValuePair, ValuePair> &ConnectedPairs); > + > + void buildDepMap(BasicBlock&BB, > + std::multimap<Value *, Value *> &CandidatePairs, > + std::vector<Value *> &PairableInsts, > + DenseSet<ValuePair> &PairableInstUsers); > + > + void choosePairs...

...vojd computeConnectedPairs(std::multimap<Value *, Value *> &CandidatePairs, > > + std::vector<Value *> &PairableInsts, > > + std::multimap<ValuePair, ValuePair> &ConnectedPairs); > > + > > + void buildDepMap(BasicBlock&BB, > > + std::multimap<Value *, Value *> &CandidatePairs, > > + std::vector<Value *> &PairableInsts, > > + DenseSet<ValuePair> &PairableInstUsers); > > + > &...

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

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 >