Editing Aliasing (computing)

{{Short description|Multiple names for the same data location}}
{{About|aliasing in computing|other uses|Aliasing (disambiguation)}}
In [[computing]], '''aliasing''' describes a situation in which a data location in [[Memory (computers)|memory]] can be accessed through different symbolic names in the program. Thus, modifying the data through one name implicitly modifies the values associated with all aliased names, which may not be expected by the programmer. As a result, aliasing makes it particularly difficult to understand, analyze and optimize programs. [[Alias analysis|Aliasing analysers]] intend to make and compute useful information for understanding aliasing in programs.

== Aliased pointers ==
Aliasing can occur in any language that can refer to one location in memory with more than one name (for example, with [[pointer (computer programming)|pointers]]). This is a common problem with functions that accept pointer arguments, and their tolerance (or the lack thereof) for aliasing must be carefully documented, particularly for functions that perform complex manipulations on memory areas passed to them.

== Specified aliasing ==
Controlled aliasing behaviour may be desirable in some cases (that is, aliasing behaviour that is specified, unlike that enabled by memory layout in C). It is common practice in [[Fortran]]. The [[Perl]] [[programming language]] specifies, in some constructs, aliasing behaviour, such as in {{code|foreach}} loops. This allows certain data structures to be modified directly with less code. For example,

<syntaxhighlight lang="perl">
my @array = (1, 2, 3);

foreach my $element (@array) {
    # Increment $element, thus automatically
    # modifying @array, since $element is ''aliased''
    # to each of @array's elements in turn.
    $element++;
}

print "@array \n";
</syntaxhighlight>
will print out "2 3 4" as a result. If one wanted to bypass aliasing effects, one could copy the contents of the index variable into another and change the copy.

== Conflicts with optimization ==
[[Optimizing compiler|Optimizers]] often have to make conservative assumptions about variables when aliasing is possible. For example, knowing the value of a variable (such as <code>x</code> is 5) normally allows certain optimizations (such as [[constant folding#Constant propagation|constant propagation]]). However, the compiler cannot use this information after an assignment to another variable (for example, in C, <code>*y = 10</code>) because it could be that <code>*y</code> is an alias of <code>x</code>. This could be the case after an assignment like <code>y = &x</code>. As an effect of this assignment to <code>*y</code>, the value of <code>x</code> would be changed as well, so propagating the information that <code>x</code> is 5 to the statements following <code>*y = 10</code> would be potentially wrong (if <code>*y</code> is indeed an alias of <code>x</code>). However, if there is information about pointers, the constant propagation process could make a query like: can <code>x</code> be an alias of <code>*y</code>? Then, if the answer is no, <code>x = 5</code> can be propagated safely.

Another optimization impacted by aliasing is code reordering. If the compiler decides that <code>x</code> is not aliased by <code>*y</code>, then code that uses or changes the value of <code>x</code> can be moved before the assignment <code>*y = 10</code>, if this would improve [[instruction scheduling|scheduling]] or enable more [[loop optimization]]s to be carried out.

To enable such optimizations in a predictable manner, [[C (programming language)#ANSI C and ISO C|the ISO standard]] for the [[C (programming language)|C programming language]] (including its newer [[C (programming language)#C99|C99]] edition, see section 6.5, paragraph 7) specifies that it is illegal (with some exceptions) to access the same memory location using pointers of different types. A compiler may therefore assume that such pointers do not alias. This rule, known as the '''strict aliasing rule''', sometimes allows for impressive increases in performance,<ref>{{cite web | url=http://cellperformance.beyond3d.com/articles/2006/06/understanding-strict-aliasing.html |author=Mike Acton |date=2006-06-01 |title=Understanding Strict Aliasing}}</ref> but has been known to break some otherwise valid code. Several software projects intentionally violate this portion of the C99 standard. For example, [[CPython|Python 2.x]] did so to implement [[reference counting]],<ref>{{cite web | url=http://mail.python.org/pipermail/python-dev/2003-July/036898.html |author=Neil Schemenauer |date=2003-07-17 |title=ANSI strict aliasing and Python}}</ref> and required changes to the basic object structs in Python 3 to enable this optimization. The [[Linux kernel]] does this because strict aliasing causes problems with optimization of inlined code.<ref>{{cite web | url=https://lkml.org/lkml/2003/2/26/158 |author=Linus Torvalds |date=2003-02-26 |title=Re: Invalid compilation without -fno-strict-aliasing}}</ref> In such cases, when compiled with [[GNU Compiler Collection|gcc]], the option <code>-fno-strict-aliasing</code> is invoked to prevent unwanted optimizations that could yield unexpected code.

== Hardware aliasing ==
The term ''aliasing'' is also used to describe the situation where, due to either a hardware design choice or a hardware failure, one or more of the available address bits is not used in the memory selection process.<ref>{{cite web | url=http://www.esacademy.com/en/library/technical-articles-and-documents/miscellaneous/software-based-memory-testing.html |author=Michael Barr |date=2012-07-27 |title=Software Based Memory Testing}}</ref> This may be a design decision if there are more address bits available than are necessary to support the installed memory device(s). In a failure, one or more address bits may be shorted together, or may be forced to [[Ground (electricity)|ground]] (logic 0) or the supply voltage (logic 1).

;Example
For this example,  assuming a memory design with 8 locations, requiring only 3 address lines (or [[bit]]s, since 2<sup>3</sup> = 8).  Address bits (named A2 through A0) are decoded to select unique memory locations as follows, in standard [[Counter (digital)|binary counter]] fashion:

{| class="wikitable" style="text-align:center"
|-
! A2 !! A1 !! A0 !! Memory location
|-
| 0 || 0 || 0 || 0
|-
| 0 || 0 || 1 || 1
|-
| 0 || 1 || 0 || 2
|-
| 0 || 1 || 1 || 3
|-
| 1 || 0 || 0 || 4
|-
| 1 || 0 || 1 || 5
|-
| 1 || 1 || 0 || 6
|-
| 1 || 1 || 1 || 7
|-
|}
In the table above, each of the 8 unique combinations of address bits selects a different memory location. However, if one address bit (say A2) were to be shorted to ground, the table would be modified as follows:

{| class="wikitable" style="text-align:center"
|-
! A2 !! A1 !! A0 !! Memory location
|-
| 0 || 0 || 0 || 0
|-
| 0 || 0 || 1 || 1
|-
| 0 || 1 || 0 || 2
|-
| 0 || 1 || 1 || 3
|-
| <span style="color:red">'''0'''</span> || 0 || 0 || <span style="color:red">'''0'''</span>
|-
| <span style="color:red">'''0'''</span> || 0 || 1 || <span style="color:red">'''1'''</span>
|-
| <span style="color:red">'''0'''</span> || 1 || 0 || <span style="color:red">'''2'''</span>
|-
| <span style="color:red">'''0'''</span> || 1 || 1 || <span style="color:red">'''3'''</span>
|-
|}

In this case, with A2 always being zero, the first four memory locations are duplicated and appear again as the second four.  Memory locations 4 through 7 have become inaccessible.

If this change occurred to a different address bit, the decoding results would be different, but in general the effect would be the same: the loss of a single address bit cuts the available memory space in half, with resulting duplication (aliasing) of the remaining space.

== See also ==
* [[Anti-aliasing]]
* [[Aliasing]] for uses of the word when applied to signal processing, including computer graphics

== References ==
{{reflist}}

== External links ==
* [http://mail-index.netbsd.org/tech-kern/2003/08/11/0001.html Aliasing, pointer casts and gcc 3.3] – informational article on NetBSD mailing list
* [http://www.ddj.com/cpp/184404273;jsessionid=NV5BWY3EOHMFSQSNDLPCKH0CJUNN2JVN?_requestid=510121 Type-based alias analysis in C++] – Informational article on type-based alias analysis in C++
* [http://dbp-consulting.com/tutorials/StrictAliasing.html Understand C/C++ Strict Aliasing] – article on strict aliasing originally from the boost developer's wiki

[[Category:Compiler construction]]
[[Category:Program analysis]]
[[Category:Articles with example Perl code]]