* How could I get alias set information from data_reference_p @ 2009-07-14 6:01 Li Feng 2009-07-14 8:54 ` Richard Guenther 0 siblings, 1 reply; 22+ messages in thread From: Li Feng @ 2009-07-14 6:01 UTC (permalink / raw) To: GCC; +Cc: richard.guenther Hi, I'm now working on Graphite branch and need to know the alias set information for each data_reference_p, which would be an integer (or alias_set_type) stands for which alias set it is in. I tried to get the alias set information with get_alias_set (tree) (I've no idea how this function works, just a experimental trying), for my testcase, it returns 2 for all the data_reference_p->ref, which I think is unreasonable. So I think I may go wrong somewhere. The question will be: how could I get it's relevant alias set information from data_reference_p? p.s. : In Graphite, the data reference was built for each gimple stmt with: get_references_in_stmt (stmt, &references); then for each ref in references, data reference is created with: dr = create_data_ref (nest, *ref->pos, stmt, ref->is_read); Thanks, Li ^ permalink raw reply [flat|nested] 22+ messages in thread
* Re: How could I get alias set information from data_reference_p 2009-07-14 6:01 How could I get alias set information from data_reference_p Li Feng @ 2009-07-14 8:54 ` Richard Guenther 2009-07-14 9:12 ` Li Feng 0 siblings, 1 reply; 22+ messages in thread From: Richard Guenther @ 2009-07-14 8:54 UTC (permalink / raw) To: Li Feng; +Cc: GCC On Tue, Jul 14, 2009 at 8:01 AM, Li Feng<nemokingdom@gmail.com> wrote: > Hi, > > I'm now working on Graphite branch and need to know > the alias set information for each data_reference_p, which > would be an integer (or alias_set_type) stands for which > alias set it is in. > > I tried to get the alias set information with get_alias_set (tree) > (I've no idea how this function works, just a experimental > trying), for my testcase, it returns 2 for all the > data_reference_p->ref, which I think is unreasonable. > So I think I may go wrong somewhere. > > The question will be: how could I get it's relevant > alias set information from data_reference_p? > > p.s. : > In Graphite, the data reference was built for each > gimple stmt with: > get_references_in_stmt (stmt, &references); > then for each ref in references, data reference is created with: > dr = create_data_ref (nest, *ref->pos, stmt, ref->is_read); get_alias_set (dr->ref) is the correct thing. Why do you think it is unreasonable to return 2 for all of them? Why do you need alias-set information anyway? Thanks, Richard. > Thanks, > Li > ^ permalink raw reply [flat|nested] 22+ messages in thread
* Re: How could I get alias set information from data_reference_p 2009-07-14 8:54 ` Richard Guenther @ 2009-07-14 9:12 ` Li Feng 2009-07-14 9:40 ` Richard Guenther 0 siblings, 1 reply; 22+ messages in thread From: Li Feng @ 2009-07-14 9:12 UTC (permalink / raw) To: Richard Guenther; +Cc: GCC Hi Richard, On Tue, Jul 14, 2009 at 4:54 PM, Richard Guenther<richard.guenther@gmail.com> wrote: > On Tue, Jul 14, 2009 at 8:01 AM, Li Feng<nemokingdom@gmail.com> wrote: >> Hi, >> >> I'm now working on Graphite branch and need to know >> the alias set information for each data_reference_p, which >> would be an integer (or alias_set_type) stands for which >> alias set it is in. >> >> I tried to get the alias set information with get_alias_set (tree) >> (I've no idea how this function works, just a experimental >> trying), for my testcase, it returns 2 for all the >> data_reference_p->ref, which I think is unreasonable. >> So I think I may go wrong somewhere. >> >> The question will be: how could I get it's relevant >> alias set information from data_reference_p? >> >> p.s. : >> In Graphite, the data reference was built for each >> gimple stmt with: >> get_references_in_stmt (stmt, &references); >> then for each ref in references, data reference is created with: >> dr = create_data_ref (nest, *ref->pos, stmt, ref->is_read); > > get_alias_set (dr->ref) is the correct thing. Why do you think it > is unreasonable to return 2 for all of them? Why do you need > alias-set information anyway? The testcase looks like this, where I assume that p and a in the same alias set, while q and Q in another, and so on. But between them, the alias set number should be different, otherwise maybe I misunderstood somewhere about the alias set. int Q[10]; int foo() { int i; int a[10], b[20]; int *p = a; int *q = Q; for (i = 0; i < 10; i++) { p[i] = i; a[i]= i - 5; b[i] = i*i; q[i] = 5; } return Q[3]*a[2]*b[10]; } For you question, We are using this information before dependency checking under polyhedron, if 2 data references get different dimensions and they are not in the same alias set, we could conclude that they takes no dependency. Li ^ permalink raw reply [flat|nested] 22+ messages in thread
* Re: How could I get alias set information from data_reference_p 2009-07-14 9:12 ` Li Feng @ 2009-07-14 9:40 ` Richard Guenther 2009-07-14 15:14 ` Sebastian Pop 0 siblings, 1 reply; 22+ messages in thread From: Richard Guenther @ 2009-07-14 9:40 UTC (permalink / raw) To: Li Feng; +Cc: GCC On Tue, Jul 14, 2009 at 11:12 AM, Li Feng<nemokingdom@gmail.com> wrote: > Hi Richard, > On Tue, Jul 14, 2009 at 4:54 PM, Richard > Guenther<richard.guenther@gmail.com> wrote: >> On Tue, Jul 14, 2009 at 8:01 AM, Li Feng<nemokingdom@gmail.com> wrote: >>> Hi, >>> >>> I'm now working on Graphite branch and need to know >>> the alias set information for each data_reference_p, which >>> would be an integer (or alias_set_type) stands for which >>> alias set it is in. >>> >>> I tried to get the alias set information with get_alias_set (tree) >>> (I've no idea how this function works, just a experimental >>> trying), for my testcase, it returns 2 for all the >>> data_reference_p->ref, which I think is unreasonable. >>> So I think I may go wrong somewhere. >>> >>> The question will be: how could I get it's relevant >>> alias set information from data_reference_p? >>> >>> p.s. : >>> In Graphite, the data reference was built for each >>> gimple stmt with: >>> get_references_in_stmt (stmt, &references); >>> then for each ref in references, data reference is created with: >>> dr = create_data_ref (nest, *ref->pos, stmt, ref->is_read); >> >> get_alias_set (dr->ref) is the correct thing. Why do you think it >> is unreasonable to return 2 for all of them? Why do you need >> alias-set information anyway? > > The testcase looks like this, where I assume that > p and a in the same alias set, while q and Q in another, and so on. > But between them, the alias set number should be different, otherwise > maybe I misunderstood somewhere about the alias set. > > int Q[10]; > > int foo() > { > int i; > int a[10], b[20]; > int *p = a; > int *q = Q; > > for (i = 0; i < 10; i++) > { > p[i] = i; > a[i]= i - 5; > b[i] = i*i; > q[i] = 5; > } > > return Q[3]*a[2]*b[10]; > } You misunderstood what alias-set numbers represent. Alias-set numbers encode type-based alias information only - which in your case cannot disambiguate a or Q. > For you question, > We are using this information before dependency checking under > polyhedron, if 2 data references get different dimensions and they > are not in the same alias set, we could conclude that they > takes no dependency. For dependency checking you should use the dependence checking routines or query the alias-oracle. Richard. > Li > ^ permalink raw reply [flat|nested] 22+ messages in thread
* Re: How could I get alias set information from data_reference_p 2009-07-14 9:40 ` Richard Guenther @ 2009-07-14 15:14 ` Sebastian Pop 2009-07-14 15:26 ` Richard Guenther 0 siblings, 1 reply; 22+ messages in thread From: Sebastian Pop @ 2009-07-14 15:14 UTC (permalink / raw) To: Richard Guenther; +Cc: Li Feng, GCC Hi Richi, On Tue, Jul 14, 2009 at 04:40, Richard Guenther<richard.guenther@gmail.com> wrote: > You misunderstood what alias-set numbers represent. Alias-set > numbers encode type-based alias information only - which in > your case cannot disambiguate a or Q. > I also have misunderstood this. > For dependency checking you should use the dependence > checking routines or query the alias-oracle. How could we use the alias-oracle to output a different number for each alias set? Could you provide some directions to implement such a function? Thanks, Sebastian ^ permalink raw reply [flat|nested] 22+ messages in thread
* Re: How could I get alias set information from data_reference_p 2009-07-14 15:14 ` Sebastian Pop @ 2009-07-14 15:26 ` Richard Guenther 2009-07-14 16:03 ` Sebastian Pop 0 siblings, 1 reply; 22+ messages in thread From: Richard Guenther @ 2009-07-14 15:26 UTC (permalink / raw) To: Sebastian Pop; +Cc: Li Feng, GCC On Tue, Jul 14, 2009 at 5:14 PM, Sebastian Pop<sebpop@gmail.com> wrote: > Hi Richi, > > On Tue, Jul 14, 2009 at 04:40, Richard > Guenther<richard.guenther@gmail.com> wrote: >> You misunderstood what alias-set numbers represent. Alias-set >> numbers encode type-based alias information only - which in >> your case cannot disambiguate a or Q. >> > > I also have misunderstood this. > >> For dependency checking you should use the dependence >> checking routines or query the alias-oracle. > > How could we use the alias-oracle to output a different number for > each alias set? Could you provide some directions to implement such a > function? What do you mean by 'different number for each alias set'? If you want to have a number that is the same for all conflicting memory references then you have to build the full conflict map and partition it. Likely not what you want? Why do you need alias-set numbers? Thanks, Richard. > Thanks, > Sebastian > ^ permalink raw reply [flat|nested] 22+ messages in thread
* Re: How could I get alias set information from data_reference_p 2009-07-14 15:26 ` Richard Guenther @ 2009-07-14 16:03 ` Sebastian Pop 2009-07-14 16:09 ` Sebastian Pop 0 siblings, 1 reply; 22+ messages in thread From: Sebastian Pop @ 2009-07-14 16:03 UTC (permalink / raw) To: Richard Guenther; +Cc: Li Feng, GCC On Tue, Jul 14, 2009 at 10:26, Richard Guenther<richard.guenther@gmail.com> wrote: > What do you mean by 'different number for each alias set'? An alias set numbering maps alias sets to integer numbers, and that map is one-to-one. > If you want to have a number that is the same for all conflicting > memory references then you have to build the full conflict map and > partition it. > Likely not what you want? maybe > Why do you need alias-set numbers? We want to represent the alias set information as an extra subscript on memory accesses: for example, if we have A[10] and supposing that A is in alias set 6, this would be represented as "memory_access[6][10]". For B[3][4] with base array B in alias set 7 and 8, we would represent this as "memory_access[7][3][4] or memory_access[8][3][4]". The data dependence test that we currently have in the graphite branch would work with alias sets represented by an extra dimension to the array dimensions. Sebastian ^ permalink raw reply [flat|nested] 22+ messages in thread
* Re: How could I get alias set information from data_reference_p 2009-07-14 16:03 ` Sebastian Pop @ 2009-07-14 16:09 ` Sebastian Pop 2009-07-14 21:34 ` Richard Guenther 0 siblings, 1 reply; 22+ messages in thread From: Sebastian Pop @ 2009-07-14 16:09 UTC (permalink / raw) To: Richard Guenther; +Cc: Li Feng, GCC On Tue, Jul 14, 2009 at 11:03, Sebastian Pop<sebpop@gmail.com> wrote: >> Why do you need alias-set numbers? > > We want to represent the alias set information as an extra subscript > on memory accesses: for example, > > if we have A[10] and supposing that A is in alias set 6, this would be > represented as "memory_access[6][10]". > > For B[3][4] with base array B in alias set 7 and 8, we would represent > this as "memory_access[7][3][4] or memory_access[8][3][4]". > > The data dependence test that we currently have in the graphite branch > would work with alias sets represented by an extra dimension to the > array dimensions. And by the way, right now we consider that all the data refs alias each other, that means that we set the alias dimension of the memory accesses to 1 for every data reference. This makes the test very conservative: in the example above, with the current implementation, we would have: A: memory_access[1][10] B: memory_access[1][3][4] Sebastian ^ permalink raw reply [flat|nested] 22+ messages in thread
* Re: How could I get alias set information from data_reference_p 2009-07-14 16:09 ` Sebastian Pop @ 2009-07-14 21:34 ` Richard Guenther 2009-07-15 7:59 ` Li Feng 2009-07-15 11:02 ` Tobias Grosser 0 siblings, 2 replies; 22+ messages in thread From: Richard Guenther @ 2009-07-14 21:34 UTC (permalink / raw) To: Sebastian Pop; +Cc: Li Feng, GCC On Tue, Jul 14, 2009 at 6:08 PM, Sebastian Pop<sebpop@gmail.com> wrote: > On Tue, Jul 14, 2009 at 11:03, Sebastian Pop<sebpop@gmail.com> wrote: >>> Why do you need alias-set numbers? >> >> We want to represent the alias set information as an extra subscript >> on memory accesses: for example, >> >> if we have A[10] and supposing that A is in alias set 6, this would be >> represented as "memory_access[6][10]". >> >> For B[3][4] with base array B in alias set 7 and 8, we would represent >> this as "memory_access[7][3][4] or memory_access[8][3][4]". >> >> The data dependence test that we currently have in the graphite branch >> would work with alias sets represented by an extra dimension to the >> array dimensions. > > And by the way, right now we consider that all the data refs alias each > other, that means that we set the alias dimension of the memory > accesses to 1 for every data reference. This makes the test very > conservative: in the example above, with the current implementation, > we would have: > > A: memory_access[1][10] > B: memory_access[1][3][4] Well, so you really want to have sort-of the base objects partitioned into must(!)-conflict sets? Thus, (*p)[1][2] (*q)[1][3] is only correct if the resulting accesses may not alias? (that is, p == q?) No, we don't have such information readily available. You have to compute it. Likely by building a complete conflict map of the bases of all memory references and partitioning it. Which doesn't sound like a great idea - it's quadratic. Thus, can't you represent this in a more sparse way? Richard. > Sebastian > ^ permalink raw reply [flat|nested] 22+ messages in thread
* Re: How could I get alias set information from data_reference_p 2009-07-14 21:34 ` Richard Guenther @ 2009-07-15 7:59 ` Li Feng 2009-07-15 11:02 ` Tobias Grosser 1 sibling, 0 replies; 22+ messages in thread From: Li Feng @ 2009-07-15 7:59 UTC (permalink / raw) To: Richard Guenther; +Cc: Sebastian Pop, GCC Hi Richard, Maybe you could look into this thread and give us some suggestion/confirmation. Now we plan to use dr_may_alias_p (DR1, DR2) to partition the alias set. http://groups.google.de/group/gcc-graphite/browse_thread/thread/7bffbe9037b5adf4?hl=en Thanks, Li On Wed, Jul 15, 2009 at 5:34 AM, Richard Guenther<richard.guenther@gmail.com> wrote: > On Tue, Jul 14, 2009 at 6:08 PM, Sebastian Pop<sebpop@gmail.com> wrote: >> On Tue, Jul 14, 2009 at 11:03, Sebastian Pop<sebpop@gmail.com> wrote: >>>> Why do you need alias-set numbers? >>> >>> We want to represent the alias set information as an extra subscript >>> on memory accesses: for example, >>> >>> if we have A[10] and supposing that A is in alias set 6, this would be >>> represented as "memory_access[6][10]". >>> >>> For B[3][4] with base array B in alias set 7 and 8, we would represent >>> this as "memory_access[7][3][4] or memory_access[8][3][4]". >>> >>> The data dependence test that we currently have in the graphite branch >>> would work with alias sets represented by an extra dimension to the >>> array dimensions. >> >> And by the way, right now we consider that all the data refs alias each >> other, that means that we set the alias dimension of the memory >> accesses to 1 for every data reference. This makes the test very >> conservative: in the example above, with the current implementation, >> we would have: >> >> A: memory_access[1][10] >> B: memory_access[1][3][4] > > Well, so you really want to have sort-of the base objects partitioned > into must(!)-conflict sets? Thus, > > (*p)[1][2] > (*q)[1][3] > > is only correct if the resulting accesses may not alias? (that is, > p == q?) > > No, we don't have such information readily available. You have > to compute it. Likely by building a complete conflict map of > the bases of all memory references and partitioning it. > > Which doesn't sound like a great idea - it's quadratic. Thus, can't > you represent this in a more sparse way? > > Richard. > >> Sebastian >> > ^ permalink raw reply [flat|nested] 22+ messages in thread
* Re: How could I get alias set information from data_reference_p 2009-07-14 21:34 ` Richard Guenther 2009-07-15 7:59 ` Li Feng @ 2009-07-15 11:02 ` Tobias Grosser 2009-07-15 11:26 ` Richard Guenther 1 sibling, 1 reply; 22+ messages in thread From: Tobias Grosser @ 2009-07-15 11:02 UTC (permalink / raw) To: Richard Guenther; +Cc: Sebastian Pop, Li Feng, GCC On Tue, 2009-07-14 at 23:34 +0200, Richard Guenther wrote: > On Tue, Jul 14, 2009 at 6:08 PM, Sebastian Pop<sebpop@gmail.com> wrote: > > On Tue, Jul 14, 2009 at 11:03, Sebastian Pop<sebpop@gmail.com> wrote: > >>> Why do you need alias-set numbers? > >> > >> We want to represent the alias set information as an extra subscript > >> on memory accesses: for example, > >> > >> if we have A[10] and supposing that A is in alias set 6, this would be > >> represented as "memory_access[6][10]". > >> > >> For B[3][4] with base array B in alias set 7 and 8, we would represent > >> this as "memory_access[7][3][4] or memory_access[8][3][4]". > >> > >> The data dependence test that we currently have in the graphite branch > >> would work with alias sets represented by an extra dimension to the > >> array dimensions. > > > > And by the way, right now we consider that all the data refs alias each > > other, that means that we set the alias dimension of the memory > > accesses to 1 for every data reference. This makes the test very > > conservative: in the example above, with the current implementation, > > we would have: > > > > A: memory_access[1][10] > > B: memory_access[1][3][4] > > Well, so you really want to have sort-of the base objects partitioned > into must(!)-conflict sets? Thus, Is there anything like must-conflict? I thought the alias oracle just returns may conflict relations. This information should be passed to graphite without loosing any information. > (*p)[1][2] > (*q)[1][3] > > is only correct if the resulting accesses may not alias? (that is, > p == q?) What do you mean by is correct? > > No, we don't have such information readily available. You have > to compute it. Likely by building a complete conflict map of > the bases of all memory references and partitioning it. > > Which doesn't sound like a great idea - it's quadratic. Thus, can't > you represent this in a more sparse way? It is quadratic in what? In the number of data references? If the only way we can get the information if two data references may alias is asking the oracle, I do not think there is an alternative. We have to get at least this information. So there will be nb_of_drs^2 calls to the alias oracle. Or is there any alternative? I think the only way to get to less complexity is to limit the information passed to graphite. E.g. we can put everything in the same alias set as we do now. This is very conservative but definitely faster. I tend to take the high complexity at the moment, as I do not think we get many SCoPs that are too big to handle and passing all the details allows Graphite to do more optimizations. However we can switch to the old approach if the number of data references passes a certain limit, so gcc's speed will not suffer. Tobi ^ permalink raw reply [flat|nested] 22+ messages in thread
* Re: How could I get alias set information from data_reference_p 2009-07-15 11:02 ` Tobias Grosser @ 2009-07-15 11:26 ` Richard Guenther 2009-07-15 19:16 ` Tobias Grosser 0 siblings, 1 reply; 22+ messages in thread From: Richard Guenther @ 2009-07-15 11:26 UTC (permalink / raw) To: gcc; +Cc: Sebastian Pop, Li Feng On Wed, Jul 15, 2009 at 1:00 PM, Tobias Grosser<grosser@fim.uni-passau.de> wrote: > On Tue, 2009-07-14 at 23:34 +0200, Richard Guenther wrote: >> On Tue, Jul 14, 2009 at 6:08 PM, Sebastian Pop<sebpop@gmail.com> wrote: >> > On Tue, Jul 14, 2009 at 11:03, Sebastian Pop<sebpop@gmail.com> wrote: >> >>> Why do you need alias-set numbers? >> >> >> >> We want to represent the alias set information as an extra subscript >> >> on memory accesses: for example, >> >> >> >> if we have A[10] and supposing that A is in alias set 6, this would be >> >> represented as "memory_access[6][10]". >> >> >> >> For B[3][4] with base array B in alias set 7 and 8, we would represent >> >> this as "memory_access[7][3][4] or memory_access[8][3][4]". >> >> >> >> The data dependence test that we currently have in the graphite branch >> >> would work with alias sets represented by an extra dimension to the >> >> array dimensions. >> > >> > And by the way, right now we consider that all the data refs alias each >> > other, that means that we set the alias dimension of the memory >> > accesses to 1 for every data reference. This makes the test very >> > conservative: in the example above, with the current implementation, >> > we would have: >> > >> > A: memory_access[1][10] >> > B: memory_access[1][3][4] >> >> Well, so you really want to have sort-of the base objects partitioned >> into must(!)-conflict sets? Thus, > > Is there anything like must-conflict? I thought the alias oracle just > returns may conflict relations. True. This is why I ask ;) > This information should be passed to graphite without loosing any > information. > >> (*p)[1][2] >> (*q)[1][3] >> >> is only correct if the resulting accesses may not alias? (that is, >> p == q?) > > What do you mean by is correct? I try to ask what you are going to do with the computed alias-set numbers and what is the property required for the alias-set numbers so that their use do not result in invalid transformations from graphite. So, what does the 1 in (*p)[1][2] semantically mean? >> >> No, we don't have such information readily available. You have >> to compute it. Likely by building a complete conflict map of >> the bases of all memory references and partitioning it. >> >> Which doesn't sound like a great idea - it's quadratic. Thus, can't >> you represent this in a more sparse way? > > It is quadratic in what? In the number of data references? Yes. You need to build the full conflict map (or a conflict graph, as Li proposes in his final algorithm). > If the only way we can get the information if two data references may > alias is asking the oracle, I do not think there is an alternative. We > have to get at least this information. So there will be nb_of_drs^2 > calls to the alias oracle. Or is there any alternative? I don't know. It depends on how you are going to use the information. > I think the only way to get to less complexity is to limit the > information passed to graphite. E.g. we can put everything in the same > alias set as we do now. This is very conservative but definitely faster. > > I tend to take the high complexity at the moment, as I do not think we > get many SCoPs that are too big to handle and passing all the details > allows Graphite to do more optimizations. However we can switch to the > old approach if the number of data references passes a certain limit, so > gcc's speed will not suffer. A note on Lis final graph algorithm. I don't understand why you want to allow data-references to be part of multiple alias-sets? (Of course I don't know how you are going to use the alias-sets ...) IMHO what you want is to assign a different alias-set to all partitions of the graph. Where for two partitions P1 and P2 there is no edge between them in the conflict graph. That may of course be just as precise as using a single alias set. Note that you likely want to distinguish read-read conflicts from true or anti dependences, no? Depending on how you are going to use them again ... Richard. ^ permalink raw reply [flat|nested] 22+ messages in thread
* Re: How could I get alias set information from data_reference_p 2009-07-15 11:26 ` Richard Guenther @ 2009-07-15 19:16 ` Tobias Grosser 2009-07-15 20:46 ` Richard Guenther 0 siblings, 1 reply; 22+ messages in thread From: Tobias Grosser @ 2009-07-15 19:16 UTC (permalink / raw) To: Richard Guenther; +Cc: gcc, Sebastian Pop, Li Feng, gcc-graphite On Wed, 2009-07-15 at 13:26 +0200, Richard Guenther wrote: > On Wed, Jul 15, 2009 at 1:00 PM, Tobias > Grosser<grosser@fim.uni-passau.de> wrote: > > On Tue, 2009-07-14 at 23:34 +0200, Richard Guenther wrote: > >> On Tue, Jul 14, 2009 at 6:08 PM, Sebastian Pop<sebpop@gmail.com> wrote: > >> > On Tue, Jul 14, 2009 at 11:03, Sebastian Pop<sebpop@gmail.com> wrote: > >> >>> Why do you need alias-set numbers? > >> >> > >> >> We want to represent the alias set information as an extra subscript > >> >> on memory accesses: for example, > >> >> > >> >> if we have A[10] and supposing that A is in alias set 6, this would be > >> >> represented as "memory_access[6][10]". > >> >> > >> >> For B[3][4] with base array B in alias set 7 and 8, we would represent > >> >> this as "memory_access[7][3][4] or memory_access[8][3][4]". > >> >> > >> >> The data dependence test that we currently have in the graphite branch > >> >> would work with alias sets represented by an extra dimension to the > >> >> array dimensions. > >> > > >> > And by the way, right now we consider that all the data refs alias each > >> > other, that means that we set the alias dimension of the memory > >> > accesses to 1 for every data reference. This makes the test very > >> > conservative: in the example above, with the current implementation, > >> > we would have: > >> > > >> > A: memory_access[1][10] > >> > B: memory_access[1][3][4] > >> > >> Well, so you really want to have sort-of the base objects partitioned > >> into must(!)-conflict sets? Thus, > > > > Is there anything like must-conflict? I thought the alias oracle just > > returns may conflict relations. > > True. This is why I ask ;) > > > This information should be passed to graphite without loosing any > > information. > > > >> (*p)[1][2] > >> (*q)[1][3] > >> > >> is only correct if the resulting accesses may not alias? (that is, > >> p == q?) > > > > What do you mean by is correct? > > I try to ask what you are going to do with the computed alias-set > numbers and what is the property required for the alias-set numbers > so that their use do not result in invalid transformations from graphite. > > So, what does the 1 in (*p)[1][2] semantically mean? > > >> > >> No, we don't have such information readily available. You have > >> to compute it. Likely by building a complete conflict map of > >> the bases of all memory references and partitioning it. > >> > >> Which doesn't sound like a great idea - it's quadratic. Thus, can't > >> you represent this in a more sparse way? > > > > It is quadratic in what? In the number of data references? > > Yes. You need to build the full conflict map (or a conflict graph, > as Li proposes in his final algorithm). > > > If the only way we can get the information if two data references may > > alias is asking the oracle, I do not think there is an alternative. We > > have to get at least this information. So there will be nb_of_drs^2 > > calls to the alias oracle. Or is there any alternative? > I don't know. It depends on how you are going to use the information. The idea is that we want to get rid of the need to call a function, to know if two data references alias, but - as Sebastian explained - to map them to virtual memory locations. Lets say we have some data references A, B, C, D, E, F, G that alias like this: A -- B F -- G | / | | / | C -- D -- E What I would like is to create groups of the data references that may touch the same memory location. So every pair of data references that may alias has to share at least one alias set. The easiest solution is to put all of them in one big set. This is always correct, but very conservative. AS1 = {A,B,C,D,E,F,G} The next step would be to make groups of all connected components of the graph. AS1 = {A,B,C,D,E} AS2 = {F,G} The most exact solution I can think of is to take all maximal complete sub graphs. This means all sub graphs where there is between every two elements E1, E2 an edge. AS1 = {A,B,C} AS2 = {B,C,D} AS3 = {D,E} AS4 = {F,G} So a statement D[i][4j-5] = B [2j]; has these effects: may-write [2] [i] [4j-5] may-write [3] [i] [4j-5] read [1] [2j] read [2] [2j] Another statement might be ... = E[5i][5i+j] read [3] [5i] [5i+j] The information is used in our data dependency checks to check and calculate which dependencies exist. There we have conflict equalities for every subscript. Lets look at the possible conflict in between the write to D and the read of E. It has to fulfill these conditions for some iterations (i,j) and (i',j') (s0 == 2 == 3 == s0' and s1 == i == 5i' == s1' and s2 == 4j-5 == 5i'+j' == s2') or (s0 == 3 == 3 == s0' and s1 == i == 5i' == s1' and s2 == 4j-5 == 5i'+j' == s2') The first set is impossible as they are part of different alias sets and therefor s0 != s0', however the second one might be possible e.g. for j = 2, i = 0, i' = 0, j' = 3 The exact solution can be calculated by our linear programming solver taking into concern even more restrictions. > > I think the only way to get to less complexity is to limit the > > information passed to graphite. E.g. we can put everything in the same > > alias set as we do now. This is very conservative but definitely faster. > > > > I tend to take the high complexity at the moment, as I do not think we > > get many SCoPs that are too big to handle and passing all the details > > allows Graphite to do more optimizations. However we can switch to the > > old approach if the number of data references passes a certain limit, so > > gcc's speed will not suffer. > > A note on Lis final graph algorithm. I don't understand why you want > to allow data-references to be part of multiple alias-sets? (Of course > I don't know how you are going to use the alias-sets ...) Just to pass more information to Graphite. The easiest example might be something like A -- B -- C if we have AS1 = {A,B} AS2 = {B,C} we know that A and C do not alias and therefore do not have any dependencies. If we put A,B,C in one big set we can not say this. > IMHO what you want is to assign a different alias-set to all partitions > of the graph. Where for two partitions P1 and P2 there is no edge > between them in the conflict graph. > > That may of course be just as precise as using a single alias set. > > Note that you likely want to distinguish read-read conflicts from > true or anti dependences, no? Depending on how you are going > to use them again ... Sure. Actually we even want to be able to distinguish between read, write and may-write accesses. At the moment we do not take advantage of the difference in between write and may-write, but as soon as we do this there might show up more interesting problems, as it is preferable to be sure a write happened as it removes a lot of dependencies. Tobi ^ permalink raw reply [flat|nested] 22+ messages in thread
* Re: How could I get alias set information from data_reference_p 2009-07-15 19:16 ` Tobias Grosser @ 2009-07-15 20:46 ` Richard Guenther 2009-07-15 20:49 ` Richard Guenther [not found] ` <15137_1247690941_4A5E40BC_15137_586_1_84fc9c000907151348s41395cc5u6cfacb60cde78bfa@mail.gmail.com> 0 siblings, 2 replies; 22+ messages in thread From: Richard Guenther @ 2009-07-15 20:46 UTC (permalink / raw) To: gcc; +Cc: Sebastian Pop, Li Feng, gcc-graphite On Wed, Jul 15, 2009 at 9:15 PM, Tobias Grosser<grosser@fim.uni-passau.de> wrote: >> A note on Lis final graph algorithm. I don't understand why you want >> to allow data-references to be part of multiple alias-sets? (Of course >> I don't know how you are going to use the alias-sets ...) > > Just to pass more information to Graphite. The easiest example might be > something like > > A -- B -- C > > if we have > > AS1 = {A,B} > AS2 = {B,C} > > we know that A and C do not alias and therefore do not have any No, from the above you _don't_ know that. How would you arrive at that conclusion? > dependencies. If we put A,B,C in one big set we can not say this. But that is what would be correct. (?) Richard. ^ permalink raw reply [flat|nested] 22+ messages in thread
* Re: How could I get alias set information from data_reference_p 2009-07-15 20:46 ` Richard Guenther @ 2009-07-15 20:49 ` Richard Guenther [not found] ` <15137_1247690941_4A5E40BC_15137_586_1_84fc9c000907151348s41395cc5u6cfacb60cde78bfa@mail.gmail.com> 1 sibling, 0 replies; 22+ messages in thread From: Richard Guenther @ 2009-07-15 20:49 UTC (permalink / raw) To: gcc; +Cc: Sebastian Pop, Li Feng, gcc-graphite On Wed, Jul 15, 2009 at 10:46 PM, Richard Guenther<richard.guenther@gmail.com> wrote: > On Wed, Jul 15, 2009 at 9:15 PM, Tobias > Grosser<grosser@fim.uni-passau.de> wrote: >>> A note on Lis final graph algorithm. I don't understand why you want >>> to allow data-references to be part of multiple alias-sets? (Of course >>> I don't know how you are going to use the alias-sets ...) >> >> Just to pass more information to Graphite. The easiest example might be >> something like >> >> A -- B -- C >> >> if we have >> >> AS1 = {A,B} >> AS2 = {B,C} >> >> we know that A and C do not alias and therefore do not have any > > No, from the above you _don't_ know that. How would you arrive > at that conclusion? What I want to say is that, if A -- B -- C is supposed to be the alias graph resulting from querying the alias oracle for the pairs (A, B), (A, C), (B, C) then this is a result that will never occur. Because if (A, B) is true and (B, C) is true then (A, C) will be true as well. Richard. >> dependencies. If we put A,B,C in one big set we can not say this. > > But that is what would be correct. (?) > > Richard. > ^ permalink raw reply [flat|nested] 22+ messages in thread
[parent not found: <15137_1247690941_4A5E40BC_15137_586_1_84fc9c000907151348s41395cc5u6cfacb60cde78bfa@mail.gmail.com>]
* Re: How could I get alias set information from data_reference_p [not found] ` <15137_1247690941_4A5E40BC_15137_586_1_84fc9c000907151348s41395cc5u6cfacb60cde78bfa@mail.gmail.com> @ 2009-07-15 23:16 ` Tobias Grosser 2009-07-16 8:39 ` Richard Guenther 0 siblings, 1 reply; 22+ messages in thread From: Tobias Grosser @ 2009-07-15 23:16 UTC (permalink / raw) To: Richard Guenther; +Cc: gcc, Sebastian Pop, Li Feng, gcc-graphite On Wed, 2009-07-15 at 22:48 +0200, Richard Guenther wrote: > On Wed, Jul 15, 2009 at 10:46 PM, Richard > Guenther<richard.guenther@gmail.com> wrote: > > On Wed, Jul 15, 2009 at 9:15 PM, Tobias > > Grosser<grosser@fim.uni-passau.de> wrote: > >>> A note on Lis final graph algorithm. I don't understand why you want > >>> to allow data-references to be part of multiple alias-sets? (Of course > >>> I don't know how you are going to use the alias-sets ...) > >> > >> Just to pass more information to Graphite. The easiest example might be > >> something like > >> > >> A -- B -- C > >> > >> if we have > >> > >> AS1 = {A,B} > >> AS2 = {B,C} > >> > >> we know that A and C do not alias and therefore do not have any > > > > No, from the above you _don't_ know that. How would you arrive > > at that conclusion? > > What I want to say is that, if A -- B -- C is supposed to be the alias graph > resulting from querying the alias oracle for the pairs (A, B), (A, C), (B, C) > then this is a result that will never occur. Because if (A, B) is true > and (B, C) is true then (A, C) will be true as well. What for example for this case: void foo (*b) { int *a int *c if (bar()) a = b; else c = b; } I thought this may give us the example above, but it seems I am wrong. If the alias oracle is transitive that would simplify the algorithm a lot. Can we rely on the transitivity? Tobi ^ permalink raw reply [flat|nested] 22+ messages in thread
* Re: How could I get alias set information from data_reference_p 2009-07-15 23:16 ` Tobias Grosser @ 2009-07-16 8:39 ` Richard Guenther 2009-07-16 9:00 ` Li Feng 0 siblings, 1 reply; 22+ messages in thread From: Richard Guenther @ 2009-07-16 8:39 UTC (permalink / raw) To: Tobias Grosser; +Cc: gcc, Sebastian Pop, Li Feng, gcc-graphite On Thu, Jul 16, 2009 at 1:15 AM, Tobias Grosser<grosser@fim.uni-passau.de> wrote: > On Wed, 2009-07-15 at 22:48 +0200, Richard Guenther wrote: >> On Wed, Jul 15, 2009 at 10:46 PM, Richard >> Guenther<richard.guenther@gmail.com> wrote: >> > On Wed, Jul 15, 2009 at 9:15 PM, Tobias >> > Grosser<grosser@fim.uni-passau.de> wrote: >> >>> A note on Lis final graph algorithm. I don't understand why you want >> >>> to allow data-references to be part of multiple alias-sets? (Of course >> >>> I don't know how you are going to use the alias-sets ...) >> >> >> >> Just to pass more information to Graphite. The easiest example might be >> >> something like >> >> >> >> A -- B -- C >> >> >> >> if we have >> >> >> >> AS1 = {A,B} >> >> AS2 = {B,C} >> >> >> >> we know that A and C do not alias and therefore do not have any >> > >> > No, from the above you _don't_ know that. How would you arrive >> > at that conclusion? >> >> What I want to say is that, if A -- B -- C is supposed to be the alias graph >> resulting from querying the alias oracle for the pairs (A, B), (A, C), (B, C) >> then this is a result that will never occur. Because if (A, B) is true >> and (B, C) is true then (A, C) will be true as well. > > What for example for this case: > > void foo (*b) { > int *a > int *c > > if (bar()) > a = b; > else > c = b; > } > > I thought this may give us the example above, but it seems I am wrong. > If the alias oracle is transitive that would simplify the algorithm a > lot. Can we rely on the transitivity? Actually I was too fast (or rather it was too late), an example with A -- B -- C would be int a, c; void foo(int *p) with B == (*p). B may alias a and c but a may not alias c. So, back to my first question then, which is still valid. Just to pass more information to Graphite. The easiest example might be something like A -- B -- C if we have AS1 = {A,B} AS2 = {B,C} we know that A and C do not alias and therefore do not have any dependencies. How do you derive at 'A and C do not alias' from looking at the alias set numbers for AS1 and AS2. How do you still figure out that B aliases A and C just from looking at the alias set numbers? Or rather, what single alias set number does B get? Richard. > Tobi > > > > ^ permalink raw reply [flat|nested] 22+ messages in thread
* Re: How could I get alias set information from data_reference_p 2009-07-16 8:39 ` Richard Guenther @ 2009-07-16 9:00 ` Li Feng 2009-07-16 9:16 ` Richard Guenther 2009-07-16 15:45 ` Daniel Berlin 0 siblings, 2 replies; 22+ messages in thread From: Li Feng @ 2009-07-16 9:00 UTC (permalink / raw) To: Richard Guenther; +Cc: Tobias Grosser, gcc, Sebastian Pop, gcc-graphite Hi Richard, On 7/16/09, Richard Guenther <richard.guenther@gmail.com> wrote: > On Thu, Jul 16, 2009 at 1:15 AM, Tobias > Grosser<grosser@fim.uni-passau.de> wrote: >> On Wed, 2009-07-15 at 22:48 +0200, Richard Guenther wrote: >>> On Wed, Jul 15, 2009 at 10:46 PM, Richard >>> Guenther<richard.guenther@gmail.com> wrote: >>> > On Wed, Jul 15, 2009 at 9:15 PM, Tobias >>> > Grosser<grosser@fim.uni-passau.de> wrote: >>> >>> A note on Lis final graph algorithm. I don't understand why you >>> >>> want >>> >>> to allow data-references to be part of multiple alias-sets? (Of >>> >>> course >>> >>> I don't know how you are going to use the alias-sets ...) >>> >> >>> >> Just to pass more information to Graphite. The easiest example might >>> >> be >>> >> something like >>> >> >>> >> A -- B -- C >>> >> >>> >> if we have >>> >> >>> >> AS1 = {A,B} >>> >> AS2 = {B,C} >>> >> >>> >> we know that A and C do not alias and therefore do not have any >>> > >>> > No, from the above you _don't_ know that. How would you arrive >>> > at that conclusion? >>> >>> What I want to say is that, if A -- B -- C is supposed to be the alias >>> graph >>> resulting from querying the alias oracle for the pairs (A, B), (A, C), >>> (B, C) >>> then this is a result that will never occur. Because if (A, B) is true >>> and (B, C) is true then (A, C) will be true as well. >> >> What for example for this case: >> >> void foo (*b) { >> int *a >> int *c >> >> if (bar()) >> a = b; >> else >> c = b; >> } >> >> I thought this may give us the example above, but it seems I am wrong. >> If the alias oracle is transitive that would simplify the algorithm a >> lot. Can we rely on the transitivity? > > Actually I was too fast (or rather it was too late), an example with > A -- B -- C would be > > int a, c; > void foo(int *p) > > with B == (*p). B may alias a and c but a may not alias c. > > So, back to my first question then, which is still valid. > > Just to pass more information to Graphite. The easiest example might be > something like > > A -- B -- C > > if we have > > AS1 = {A,B} > AS2 = {B,C} > > we know that A and C do not alias and therefore do not have any > dependencies. > > How do you derive at 'A and C do not alias' from looking at > the alias set numbers for AS1 and AS2. How do you still > figure out that B aliases A and C just from looking at > the alias set numbers? Or rather, what single alias set number > does B get? AS1 = {A,B} AS2 = {B,C} B is not neccessary to have only a single alias set number, for this situation, B will have alias number both 1 and 2 (it is in both alias set), A will be with alias number 1 and C will be with alias number 2. So A and C got different alias set number, we could conclude that they are not alias. While for A and B or B and C, as B got alias number both 1 and 2, so they may alias. Li ^ permalink raw reply [flat|nested] 22+ messages in thread
* Re: How could I get alias set information from data_reference_p 2009-07-16 9:00 ` Li Feng @ 2009-07-16 9:16 ` Richard Guenther 2009-07-16 15:45 ` Daniel Berlin 1 sibling, 0 replies; 22+ messages in thread From: Richard Guenther @ 2009-07-16 9:16 UTC (permalink / raw) To: Li Feng; +Cc: Tobias Grosser, gcc, Sebastian Pop, gcc-graphite On Thu, Jul 16, 2009 at 11:00 AM, Li Feng<nemokingdom@gmail.com> wrote: > Hi Richard, > On 7/16/09, Richard Guenther <richard.guenther@gmail.com> wrote: >> On Thu, Jul 16, 2009 at 1:15 AM, Tobias >> Grosser<grosser@fim.uni-passau.de> wrote: >>> On Wed, 2009-07-15 at 22:48 +0200, Richard Guenther wrote: >>>> On Wed, Jul 15, 2009 at 10:46 PM, Richard >>>> Guenther<richard.guenther@gmail.com> wrote: >>>> > On Wed, Jul 15, 2009 at 9:15 PM, Tobias >>>> > Grosser<grosser@fim.uni-passau.de> wrote: >>>> >>> A note on Lis final graph algorithm. I don't understand why you >>>> >>> want >>>> >>> to allow data-references to be part of multiple alias-sets? (Of >>>> >>> course >>>> >>> I don't know how you are going to use the alias-sets ...) >>>> >> >>>> >> Just to pass more information to Graphite. The easiest example might >>>> >> be >>>> >> something like >>>> >> >>>> >> A -- B -- C >>>> >> >>>> >> if we have >>>> >> >>>> >> AS1 = {A,B} >>>> >> AS2 = {B,C} >>>> >> >>>> >> we know that A and C do not alias and therefore do not have any >>>> > >>>> > No, from the above you _don't_ know that. How would you arrive >>>> > at that conclusion? >>>> >>>> What I want to say is that, if A -- B -- C is supposed to be the alias >>>> graph >>>> resulting from querying the alias oracle for the pairs (A, B), (A, C), >>>> (B, C) >>>> then this is a result that will never occur. Because if (A, B) is true >>>> and (B, C) is true then (A, C) will be true as well. >>> >>> What for example for this case: >>> >>> void foo (*b) { >>> int *a >>> int *c >>> >>> if (bar()) >>> a = b; >>> else >>> c = b; >>> } >>> >>> I thought this may give us the example above, but it seems I am wrong. >>> If the alias oracle is transitive that would simplify the algorithm a >>> lot. Can we rely on the transitivity? >> >> Actually I was too fast (or rather it was too late), an example with >> A -- B -- C would be >> >> int a, c; >> void foo(int *p) >> >> with B == (*p). B may alias a and c but a may not alias c. >> >> So, back to my first question then, which is still valid. >> >> Just to pass more information to Graphite. The easiest example might be >> something like >> >> A -- B -- C >> >> if we have >> >> AS1 = {A,B} >> AS2 = {B,C} >> >> we know that A and C do not alias and therefore do not have any >> dependencies. >> >> How do you derive at 'A and C do not alias' from looking at >> the alias set numbers for AS1 and AS2. How do you still >> figure out that B aliases A and C just from looking at >> the alias set numbers? Or rather, what single alias set number >> does B get? > AS1 = {A,B} > AS2 = {B,C} > > B is not neccessary to have only a single alias set number, > for this situation, B will have alias number both 1 and 2 (it > is in both alias set), > A will be with alias number 1 and > C will be with alias number 2. > So A and C got different alias set number, we could conclude > that they are not alias. > While for A and B or B and C, as B got alias number both 1 and 2, > so they may alias. I see. That would work. Richard. > Li > ^ permalink raw reply [flat|nested] 22+ messages in thread
* Re: How could I get alias set information from data_reference_p 2009-07-16 9:00 ` Li Feng 2009-07-16 9:16 ` Richard Guenther @ 2009-07-16 15:45 ` Daniel Berlin 2009-07-16 16:04 ` Sebastian Pop 2009-07-17 1:36 ` Li Feng 1 sibling, 2 replies; 22+ messages in thread From: Daniel Berlin @ 2009-07-16 15:45 UTC (permalink / raw) To: Li Feng Cc: Richard Guenther, Tobias Grosser, gcc, Sebastian Pop, gcc-graphite On Thu, Jul 16, 2009 at 5:00 AM, Li Feng<nemokingdom@gmail.com> wrote: > Hi Richard, > On 7/16/09, Richard Guenther <richard.guenther@gmail.com> wrote: >> On Thu, Jul 16, 2009 at 1:15 AM, Tobias >> Grosser<grosser@fim.uni-passau.de> wrote: >>> On Wed, 2009-07-15 at 22:48 +0200, Richard Guenther wrote: >>>> On Wed, Jul 15, 2009 at 10:46 PM, Richard >>>> Guenther<richard.guenther@gmail.com> wrote: >>>> > On Wed, Jul 15, 2009 at 9:15 PM, Tobias >>>> > Grosser<grosser@fim.uni-passau.de> wrote: >>>> >>> A note on Lis final graph algorithm. I don't understand why you >>>> >>> want >>>> >>> to allow data-references to be part of multiple alias-sets? (Of >>>> >>> course >>>> >>> I don't know how you are going to use the alias-sets ...) >>>> >> >>>> >> Just to pass more information to Graphite. The easiest example might >>>> >> be >>>> >> something like >>>> >> >>>> >> A -- B -- C >>>> >> >>>> >> if we have >>>> >> >>>> >> AS1 = {A,B} >>>> >> AS2 = {B,C} >>>> >> >>>> >> we know that A and C do not alias and therefore do not have any >>>> > >>>> > No, from the above you _don't_ know that. How would you arrive >>>> > at that conclusion? >>>> >>>> What I want to say is that, if A -- B -- C is supposed to be the alias >>>> graph >>>> resulting from querying the alias oracle for the pairs (A, B), (A, C), >>>> (B, C) >>>> then this is a result that will never occur. Because if (A, B) is true >>>> and (B, C) is true then (A, C) will be true as well. >>> >>> What for example for this case: >>> >>> void foo (*b) { >>> int *a >>> int *c >>> >>> if (bar()) >>> a = b; >>> else >>> c = b; >>> } >>> >>> I thought this may give us the example above, but it seems I am wrong. >>> If the alias oracle is transitive that would simplify the algorithm a >>> lot. Can we rely on the transitivity? >> >> Actually I was too fast (or rather it was too late), an example with >> A -- B -- C would be >> >> int a, c; >> void foo(int *p) >> >> with B == (*p). B may alias a and c but a may not alias c. >> >> So, back to my first question then, which is still valid. >> >> Just to pass more information to Graphite. The easiest example might be >> something like >> >> A -- B -- C >> >> if we have >> >> AS1 = {A,B} >> AS2 = {B,C} >> >> we know that A and C do not alias and therefore do not have any >> dependencies. >> >> How do you derive at 'A and C do not alias' from looking at >> the alias set numbers for AS1 and AS2. How do you still >> figure out that B aliases A and C just from looking at >> the alias set numbers? Or rather, what single alias set number >> does B get? > AS1 = {A,B} > AS2 = {B,C} > > B is not neccessary to have only a single alias set number, > for this situation, B will have alias number both 1 and 2 (it > is in both alias set), > A will be with alias number 1 and > C will be with alias number 2. > So A and C got different alias set number, we could conclude > that they are not alias. > While for A and B or B and C, as B got alias number both 1 and 2, > so they may alias. So if i understand you right, it seems all you've done is inverted the existing alias/points-to sets. IE instead of saying A has B, C, D in it's alias set, you are saying B is in the alias set of A, C is in the alias set of A, D is in the alias set of A. Effectively, A -> {B, C, D} B -> {C, D, E} becomes B -> A C -> A, B D -> A ,B E -> B Then you are assigning numbers to the sets that appear on the RHS. You still end up with bitmaps, and you still have to intersect them (or describe containment some other way and do containment queries). For a large program, this mapping is actually massive and quite expensive to compute (In points-to, normally you use location equivalence and BDD's to compress the sets. I never got around to finishing location equivalence inside GCC, though it is in the LLVM implementation i did if you want to look). --Dan ^ permalink raw reply [flat|nested] 22+ messages in thread
* Re: How could I get alias set information from data_reference_p 2009-07-16 15:45 ` Daniel Berlin @ 2009-07-16 16:04 ` Sebastian Pop 2009-07-17 1:36 ` Li Feng 1 sibling, 0 replies; 22+ messages in thread From: Sebastian Pop @ 2009-07-16 16:04 UTC (permalink / raw) To: Daniel Berlin Cc: Li Feng, Richard Guenther, Tobias Grosser, gcc, gcc-graphite On Thu, Jul 16, 2009 at 10:45, Daniel Berlin<dberlin@dberlin.org> wrote: > So if i understand you right, it seems all you've done is inverted the > existing alias/points-to sets. > IE instead of saying A has B, C, D in it's alias set, you are saying B > is in the alias set of A, C is in the alias set of A, D is in the > alias set of A. > > Effectively, > > A -> {B, C, D} > B -> {C, D, E} > becomes > B -> A > C -> A, B > D -> A ,B > E -> B > Yes, this is correct. > Then you are assigning numbers to the sets that appear on the RHS. Correct. > You still end up with bitmaps, and you still have to intersect them > (or describe containment some other way and do containment queries). > > For a large program, this mapping is actually massive and quite > expensive to compute In the case of Graphite, the queries are limited to the data references within a SCoP. Usually a SCoP does not necessarily contain huge amount of data references. In the future, we may also set restrictions on the number of data references that we allow in a SCoP. Sebastian ^ permalink raw reply [flat|nested] 22+ messages in thread
* Re: How could I get alias set information from data_reference_p 2009-07-16 15:45 ` Daniel Berlin 2009-07-16 16:04 ` Sebastian Pop @ 2009-07-17 1:36 ` Li Feng 1 sibling, 0 replies; 22+ messages in thread From: Li Feng @ 2009-07-17 1:36 UTC (permalink / raw) To: Daniel Berlin Cc: Richard Guenther, Tobias Grosser, gcc, Sebastian Pop, gcc-graphite Hi Daniel, On Thu, Jul 16, 2009 at 11:45 PM, Daniel Berlin<dberlin@dberlin.org> wrote: > On Thu, Jul 16, 2009 at 5:00 AM, Li Feng<nemokingdom@gmail.com> wrote: >> Hi Richard, >> On 7/16/09, Richard Guenther <richard.guenther@gmail.com> wrote: >>> On Thu, Jul 16, 2009 at 1:15 AM, Tobias >>> Grosser<grosser@fim.uni-passau.de> wrote: >>>> On Wed, 2009-07-15 at 22:48 +0200, Richard Guenther wrote: >>>>> On Wed, Jul 15, 2009 at 10:46 PM, Richard >>>>> Guenther<richard.guenther@gmail.com> wrote: >>>>> > On Wed, Jul 15, 2009 at 9:15 PM, Tobias >>>>> > Grosser<grosser@fim.uni-passau.de> wrote: >>>>> >>> A note on Lis final graph algorithm. I don't understand why you >>>>> >>> want >>>>> >>> to allow data-references to be part of multiple alias-sets? (Of >>>>> >>> course >>>>> >>> I don't know how you are going to use the alias-sets ...) >>>>> >> >>>>> >> Just to pass more information to Graphite. The easiest example might >>>>> >> be >>>>> >> something like >>>>> >> >>>>> >> A -- B -- C >>>>> >> >>>>> >> if we have >>>>> >> >>>>> >> AS1 = {A,B} >>>>> >> AS2 = {B,C} >>>>> >> >>>>> >> we know that A and C do not alias and therefore do not have any >>>>> > >>>>> > No, from the above you _don't_ know that. How would you arrive >>>>> > at that conclusion? >>>>> >>>>> What I want to say is that, if A -- B -- C is supposed to be the alias >>>>> graph >>>>> resulting from querying the alias oracle for the pairs (A, B), (A, C), >>>>> (B, C) >>>>> then this is a result that will never occur. Because if (A, B) is true >>>>> and (B, C) is true then (A, C) will be true as well. >>>> >>>> What for example for this case: >>>> >>>> void foo (*b) { >>>> int *a >>>> int *c >>>> >>>> if (bar()) >>>> a = b; >>>> else >>>> c = b; >>>> } >>>> >>>> I thought this may give us the example above, but it seems I am wrong. >>>> If the alias oracle is transitive that would simplify the algorithm a >>>> lot. Can we rely on the transitivity? >>> >>> Actually I was too fast (or rather it was too late), an example with >>> A -- B -- C would be >>> >>> int a, c; >>> void foo(int *p) >>> >>> with B == (*p). B may alias a and c but a may not alias c. >>> >>> So, back to my first question then, which is still valid. >>> >>> Just to pass more information to Graphite. The easiest example might be >>> something like >>> >>> A -- B -- C >>> >>> if we have >>> >>> AS1 = {A,B} >>> AS2 = {B,C} >>> >>> we know that A and C do not alias and therefore do not have any >>> dependencies. >>> >>> How do you derive at 'A and C do not alias' from looking at >>> the alias set numbers for AS1 and AS2. How do you still >>> figure out that B aliases A and C just from looking at >>> the alias set numbers? Or rather, what single alias set number >>> does B get? >> AS1 = {A,B} >> AS2 = {B,C} >> >> B is not neccessary to have only a single alias set number, >> for this situation, B will have alias number both 1 and 2 (it >> is in both alias set), >> A will be with alias number 1 and >> C will be with alias number 2. >> So A and C got different alias set number, we could conclude >> that they are not alias. >> While for A and B or B and C, as B got alias number both 1 and 2, >> so they may alias. > > So if i understand you right, it seems all you've done is inverted the > existing alias/points-to sets. > IE instead of saying A has B, C, D in it's alias set, you are saying B > is in the alias set of A, C is in the alias set of A, D is in the > alias set of A. > > Effectively, > > A -> {B, C, D} > B -> {C, D, E} > becomes > B -> A > C -> A, B > D -> A ,B > E -> B > I'm not sure about your meaning by B,C,D in A's alias set. If that means BandCandD may alias to A, but without saying B,C,D will alias to each other or not, then I think we may misunderstand somewhere. If I understand you correctly, in your example, you mean that B,C,D is connected(may alias) to A, and C,D,E is connected to B. And no other relation ship between these A,B...E. If this is true, then I think there will be 4 alias set. (We could consider this problem as finding all the maximum cliques in an undirected graph.) alias set 1{A,B,C} alias set 2{B,E} alias set 3{B,D} alias set 4{A,D} So in our definition: some data reference will be said in one alias set if they may alias each other. e.g. If we have the following alias set {A,B,C} Then we should get A alias B, B alias C and C alias A. > Then you are assigning numbers to the sets that appear on the RHS. > You still end up with bitmaps, and you still have to intersect them > (or describe containment some other way and do containment queries). > Bitmap is not necessary, in Graphite, we would like to pass these alias information through access polyhedron, which will need this alias set number. So in Graphite, a poly_dr(polyhedron representation with data reference) will hold this access polyhedron( a polyhedron which will hold access function inforamtion and alias information), where we could got the information we need when we would like to check dependency between 2 poly_drs. > For a large program, this mapping is actually massive and quite > expensive to compute (In points-to, normally you use location > equivalence and BDD's to compress the sets. I never got around to > finishing location equivalence inside GCC, though it is in the LLVM > implementation i did if you want to look). > I can't quite understand this paragraph(especially the reason that the mapping is expensive), can you explain with more detailed information. Thanks for your comment, Li ^ permalink raw reply [flat|nested] 22+ messages in thread
end of thread, other threads:[~2009-07-17 1:36 UTC | newest] Thread overview: 22+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2009-07-14 6:01 How could I get alias set information from data_reference_p Li Feng 2009-07-14 8:54 ` Richard Guenther 2009-07-14 9:12 ` Li Feng 2009-07-14 9:40 ` Richard Guenther 2009-07-14 15:14 ` Sebastian Pop 2009-07-14 15:26 ` Richard Guenther 2009-07-14 16:03 ` Sebastian Pop 2009-07-14 16:09 ` Sebastian Pop 2009-07-14 21:34 ` Richard Guenther 2009-07-15 7:59 ` Li Feng 2009-07-15 11:02 ` Tobias Grosser 2009-07-15 11:26 ` Richard Guenther 2009-07-15 19:16 ` Tobias Grosser 2009-07-15 20:46 ` Richard Guenther 2009-07-15 20:49 ` Richard Guenther [not found] ` <15137_1247690941_4A5E40BC_15137_586_1_84fc9c000907151348s41395cc5u6cfacb60cde78bfa@mail.gmail.com> 2009-07-15 23:16 ` Tobias Grosser 2009-07-16 8:39 ` Richard Guenther 2009-07-16 9:00 ` Li Feng 2009-07-16 9:16 ` Richard Guenther 2009-07-16 15:45 ` Daniel Berlin 2009-07-16 16:04 ` Sebastian Pop 2009-07-17 1:36 ` Li Feng
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox; as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).