Re: Memory Disambiguation

"Anton Ertl" <anton@mips.complang.tuwien.ac.at>
24 Aug 2002 11:59:49 -0400

          From comp.compilers

Related articles
Memory Disambiguation husainahmed154@hotmail.com (Husain) (2002-08-23)
Re: Memory Disambiguation anton@mips.complang.tuwien.ac.at (Anton Ertl) (2002-08-24)
| List of all articles for this month |

From: "Anton Ertl" <anton@mips.complang.tuwien.ac.at>
Newsgroups: comp.compilers
Date: 24 Aug 2002 11:59:49 -0400
Organization: Institut fuer Computersprachen, Technische Universitaet Wien
References: 02-08-068
Keywords: architecture, optimize
Posted-Date: 24 Aug 2002 11:59:49 EDT

"Husain" <husainahmed154@hotmail.com> writes:
>Problem:-
>1) How to know about the exact memory dependencies. Uptil now i have assumed
>that any memory access actually accesses a variable MEM. With this assumption
> (i) *(A0+56) = R0;
> (ii) R1 = *(A1);
...
>(2) Dynamic which is applied on low level language. This method is
>more accurate than Static method, but it requires some hardware
>support also.


No architectural support is needed. You can transform the code above into


  R1 = *(A1);
  *(A0+56) = R0;
  R2 = *(A1);
  if R1!=R2 goto repair_code;
ok:
  ...
repair_code:
  R1 = R2;
  goto ok;


Then you can move the first load further up. I presume you know how
to move code from below the "ok:" further up after this
transformation.


The transformation given above was presented in


Mayan Moudgill and Jaime Moreno
Run-Time Detection and Recovery From Incorrectly Reordered Memory Operations


Another transformation was presented in


@Article{nicolau89,
    author = "Alexandru Nicolau",
    title = "Run-Time Disambiguation: Coping with Statically
Unpredictable Dependencies",
    journal = ieeetc,
    year = "1989",
    volume = "38",
    number = "5",
    pages = "663--678",
    month = may,
    annote = "Static alias analysis often cannot determine whether
two memory accesses refer to the same location.
Conventionally the worst case is assumed, and the
resulting dependency prohibits good schedules.
Run-time Disambiguation assumes
the best case, and checks this assumption at
run-time. The application of this idea in the
{Bulldog} trace scheduling compiler is discussed. The
speedup achieved over {Bulldog} without RTD is up
to~7. The code expansion is about proportional to the
speedup, but can be reduced without too much effect
on speed by not applying RTD to rarely-executed parts
and by combining the routines handling the
exceptional cases."
}


- anton
--
M. Anton Ertl
anton@mips.complang.tuwien.ac.at
http://www.complang.tuwien.ac.at/anton/home.html


Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.