Reaching definition

In compiler theory, a reaching definition for a given instruction is an earlier instruction whose target variable can reach (be assigned to) the given one without an intervening assignment. For example, in the following code:

d1 : y := 3
d2 : x := y

d1 is a reaching definition for d2. In the following, example, however:

d1 : y := 3
d2 : y := 4
d3 : x := y

d1 is no longer a reaching definition for d3, because d2 kills its reach: the value defined in d1 is no longer available and cannot reach d3.

As analysis

The similarly named reaching definitions is a data-flow analysis which statically determines which definitions may reach a given point in the code. Because of its simplicity, it is often used as the canonical example of a data-flow analysis in textbooks. The data-flow confluence operator used is set union, and the analysis is forward flow. Reaching definitions are used to compute use-def chains.

The data-flow equations used for a given basic block $S$ in reaching definitions are:

${\rm {REACH}}_{\rm {in}}[S]=\bigcup _{p\in pred[S]}{\rm {REACH}}_{\rm {out}}[p]$
${\rm {REACH}}_{\rm {out}}[S]={\rm {GEN}}[S]\cup ({\rm {REACH}}_{\rm {in}}[S]-{\rm {KILL}}[S])$

In other words, the set of reaching definitions going into $S$ are all of the reaching definitions from $S$ 's predecessors, $pred[S]$ . $pred[S]$ consists of all of the basic blocks that come before $S$ in the control-flow graph. The reaching definitions coming out of $S$ are all reaching definitions of its predecessors minus those reaching definitions whose variable is killed by $S$ plus any new definitions generated within $S$ .

For a generic instruction, we define the ${\rm {GEN}}$ and ${\rm {KILL}}$ sets as follows:

${\rm {GEN}}[d:y\leftarrow f(x_{1},\cdots ,x_{n})]=\{d\}$ , a set of locally available definitions in a basic block
${\rm {KILL}}[d:y\leftarrow f(x_{1},\cdots ,x_{n})]={\rm {DEFS}}[y]-\{d\}$ , a set of definitions (not locally available, but in the rest of the program) killed by definitions in the basic block.

where ${\rm {DEFS}}[y]$ is the set of all definitions that assign to the variable $y$ . Here $d$ is a unique label attached to the assigning instruction; thus, the domain of values in reaching definitions are these instruction labels.

Worklist algorithm

Reaching definition is usually calculated using an iterative worklist algorithm.

Input: control-flow graph CFG = (Nodes, Edges, Entry, Exit)

// Initialize
for all CFG nodes n in N,
    OUT[n] = emptyset; // can optimize by OUT[n] = GEN[n];

// put all nodes into the changed set
// N is all nodes in graph,
Changed = N;

// Iterate 
while (Changed != emptyset)
{
    choose a node n in Changed;
    // remove it from the changed set
    Changed = Changed -{ n };

    // init IN[n] to be empty
    IN[n] = emptyset;

    // calculate IN[n] from predecessors' OUT[p]
    for all nodes p in predecessors(n)
         IN[n] = IN[n] Union OUT[p];

    oldout = OUT[n]; // save old OUT[n]
    
    // update OUT[n] using transfer function f_n ()
    OUT[n] = GEN[n] Union (IN[n] -KILL[n]);

    // any change to OUT[n] compared to previous value?
    if (OUT[n] changed) // compare oldout vs. OUT[n]
    {    
        // if yes, put all successors of n into the changed set
        for all nodes s in successors(n)
             Changed = Changed U { s };
    }
}

Read other articles:

Serie C 1946-1947 (Lega Interregionale Centro)

Voce principale: Serie C 1946-1947. Lega Interregionale Centro fu l'ente federale che gestì uno dei tre tornei che composero il campionato di Serie C della stagione sportiva 1946-1947[1]. Ricomprendendo le società aventi sede fra l'Emilia e il Lazio, fu organizzata dalla neonata Lega Interregionale Centro avente sede a Firenze. Alla competizione parteciparono 83 squadre suddivise in sei gironi. Le prime classificate di ogni raggruppamento accedevano ad un unico girone finale che po...

Tom and Jerry Tales

Tom and Jerry TalesTelop Tom & Jerry TalesPenggubah lagu temaTom ErbaNegara asal Amerika SerikatJmlh. episode78ProduksiDurasi30 menitRilis asliJaringanThe CW Television Network (Kids' WB! The CW4Kids) Indonesia: Trans7 GTV RCTIRilis23 September 2006 –22 Maret 2008 Tom & Jerry Tales adalah serial animasi komedi yang merupakan kelanjutan dari serial TV Tom & Jerry dan pertama kali diciptakan khusus serial TV. Serial ini ditayangkan dari tanggal 23 September 2006 - 22 Ma...

Exo

EXO엑소Exo pada Juni 2016 Dari kiri ke kanan, berdiri: Baekhyun, Chen, Lay, Sehun, Chanyeol, D.O., KaiDari kiri ke kanan, berlutut: Suho, XiuminInformasi latar belakangAsalSeoul, Korea SelatanGenre Pop Korea Hip hop R&B kontemporer Musik dansa elektronik Pop Tionghoa Pop Jepang Pop elektronik Pop dansa Tahun aktif2012–sekarangLabel SM Avex Artis terkait Exo-CBX Exo-SC SM Town Situs webexo.smtown.comAnggota Xiumin Suho Lay Baekhyun Chen Chanyeol D.O. Kai Sehun Mantan anggota Luhan Kris...

HDNet Movies

Television channel HDNet MoviesCountryUnited StatesBroadcast areaNationalHeadquartersDenver, ColoradoProgrammingLanguage(s)EnglishPicture format1080i (HDTV)OwnershipOwnerHDNet LLC[1](AXS TV LLC)Sister channelsAXS TVHistoryLaunchedJanuary 13, 2003 (January 13, 2003)LinksWebsitewww.hdnetmovies.com HDNet Movies is an American digital cable and satellite television network owned and operated by HDNet LLC,[1] operating as a subsidiary of AXS TV LLC. Launched by founder Mark Cu...

Steve Lamacq

British DJ (born 1964) Steve LamacqLamacq at Camden Crawl in 2011BornStephen Paul Lamacq (1964-10-16) 16 October 1964 (age 59)SpouseDr Jen Willis (2019–present)Children1CareerShowSteve LamacqStationBBC Radio 6 MusicTime slot16:00 – 19:00 MondaysStyleDisc JockeyCountryUnited KingdomPrevious show(s)The Evening SessionIn New Music We Trust, BBC Radio 1Steve Lamacq's Rock College, BBC Radio 2 Websitewww.bbc.co.uk/6music/shows/steve_lamacq Stephen Paul Lamacq (born 16 October 1964), somet...

Gram stain

Investigative procedure in microbiology Micrograph of a gram-positive coccus and a gram-negative rod. A Gram stain of mixed Staphylococcus aureus (S. aureus ATCC 25923, gram-positive cocci, in purple) and Escherichia coli (E. coli ATCC 11775, gram-negative bacilli, in red), the most common Gram stain reference bacteria Gram stain (Gram staining or Gram's method), is a method of staining used to classify bacterial species into two large groups: gram-positive bacteria and gram-negative bacteria...

信徒 (电视剧)

信徒Believe类型奇幻、科幻开创阿方索·卡隆主演 Johnny Sequoyah Jake McLaughlin Delroy Lindo 凯尔·麦克拉克伦西耶娜·盖尔利鄭智麟 Tracy Howe Arian Moayed 国家／地区美国语言英语季数1集数12每集长度43分钟制作执行制作阿方索·卡隆 J·J·艾布拉姆斯 Mark Friedman 布赖恩·伯克机位多镜头制作公司坏机器人制片公司华纳兄弟电视公司播出信息首播频道全国广播公司播出日期2014年3月10日...

Shinbundang Line

Driverless subway line in Gyeonggi-do and Seoul, South Korea Shinbundang Line(DX Line) Shinbundang line trainOverviewNative name신분당선(新盆唐線)SinbundangseonStatusOperationalTerminiSinsaGwanggyoStations16ServiceTypeCommuter RailSystemSeoul Metropolitan SubwayOperator(s)Shinbundang Railroad Corporation, Gyeonggi Railroad Co., Ltd., New Seoul Railroad Co., Ltd., Neo TransHistoryOpened28 October 2011TechnicalLine length33.4 km (20.8 mi)Number of tracks2Track gauge1,435 ...

美国众议院

此條目需要补充更多来源。 (2021年7月4日)请协助補充多方面可靠来源以改善这篇条目，无法查证的内容可能會因為异议提出而被移除。致使用者：请搜索一下条目的标题（来源搜索：美国众议院 — 网页、新闻、书籍、学术、图像），以检查网络上是否存在该主题的更多可靠来源（判定指引）。美國眾議院 United States House of Representatives第118届美国国会众议院徽章众议院旗...

哈萨克斯坦总统

此条目序言章节没有充分总结全文内容要点。 (2019年3月21日)请考虑扩充序言，清晰概述条目所有重點。请在条目的讨论页讨论此问题。哈萨克斯坦總統哈薩克總統旗現任Қасым-Жомарт Кемелұлы Тоқаев卡瑟姆若马尔特·托卡耶夫自2019年3月20日在任任期7年首任努尔苏丹·纳扎尔巴耶夫设立1990年4月24日（哈薩克蘇維埃社會主義共和國總統）哈萨克斯坦哈萨克斯坦政府...

Tish (Hasidic celebration)

Hasidic celebration Not to be confused with Shabbat meals. This article does not cite any sources. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed.Find sources: Tish Hasidic celebration – news · newspapers · books · scholar · JSTOR (September 2023) (Learn how and when to remove this message) A tish in the court of Nadvorna A Tish, also tische (Yiddish: טיש, lit. &#...

显德府

显德府為遠東地區中世紀古國渤海国五都之一，稱中京，下领七州（卢州、顯州、鐵州、湯州、榮州、興州、涑州独奏州）。現有遺址位於中華人民共和國吉林省延邊朝鮮族自治州和龙市西城镇。相关渤海國行政區劃渤海中京城遗址查论编渤海国行政区划五京制上京龙泉府龙州 | 湖州 | 渤州 | 铜州（独奏州）中京显德府卢州 | 顯州...

Antiproton

Subatomic particle AntiprotonThe quark content of the antiproton.ClassificationAntibaryonComposition2 up antiquarks, 1 down antiquarkStatisticsFermionicFamilyHadronInteractionsStrong, weak, electromagnetic, gravitySymbolpAntiparticleProtonTheorisedPaul Dirac (1933)DiscoveredEmilio Segrè & Owen Chamberlain (1955)Mass1.67262192595(52)×10−27 kg[1] 938.27208943(29) MeV/c2[2]Electric charge−1 eMagnetic moment−2.7928473441(42) μN [3]...

ليندا هاميلتون

ليندا هاميلتون (بالإنجليزية: Linda Carroll Hamilton)‏ ليندا هاميلتون تتحدث في معرض سان دييغو للكوميكون في 18 يوليو 2019 في سان دييغو، كاليفورنيا. معلومات شخصية اسم الولادة ليندا كارول هاملتون الميلاد 26 سبتمبر 1956 (العمر 67 سنة)سالزبوري، ماريلاند الإقامة تشيلي مواطنة الولايات المت...

Zone extraterritoriali della Santa Sede in Italia

Le zone extraterritoriali della Santa Sede in Italia sono aree di extraterritorialità che si trovano principalmente a Roma e altri luoghi della città metropolitana di Roma. A parte il Pontificio Seminario Romano Minore, tutti i territori nella città di Roma sono stati dichiarati patrimonio dell'umanità dall'UNESCO[1]. Le zone si trovano sul suolo italiano: la sovranità territoriale è stata concordata in occasione della firma dei Patti Lateranensi (11 febbraio 1929); con la risol...

Corde à piano

Cordes de piano. La corde à piano est un type spécialisé de corde d'acier produite pour être utilisée dans un piano et autres instruments de musique à corde. Elle est fabriquée en acier au carbone trempé, également connu comme acier à ressort. Fabrication et usage Le fil d'acier à haute teneur en carbone utilisé dans les instruments musicaux (comme le ASTM A228) est fabriqué avec des diamètres de 0,15 mm à 4,8 mm. Un nombre restreint d'entreprises produisent des corde...

Filip Horanský

Slovak tennis player Filip HoranskýHoranský at the 2019 French OpenCountry (sports) SlovakiaResidencePiešťany, SlovakiaBorn (1993-01-07) 7 January 1993 (age 31)Piešťany, SlovakiaHeight1.91 m (6 ft 3 in)Turned pro2012PlaysRight Handed (Double Handed Backhand)CoachKarol KučeraPrize moneyUS$380,674SinglesCareer record2–9 (ATP Tour level, Grand Slam level, and Davis Cup)Career titles0Highest rankingNo. 161 (20 May 2019)Current rankin...

Vita nuova

Disambiguazione – Se stai cercando altri significati, vedi Vita nuova (disambigua). Vita novaTitolo originaleVita nova Dante e Beatrice, disegno di Ezio Anichini AutoreDante Alighieri 1ª ed. originaletra il 1292 e il 1294 Genereautobiografia in prosimetro Lingua originaleitaliano (volgare fiorentino) Modifica dati su Wikidata · Manuale Frammento Trespiano, Firenze, Carmelo Santa Maria degli Angeli e S. Maria Maddalena de' Pazzi La Vita nuova è la prima opera di attribuzione cer...

حذف وزيادة

جزء من سلسلة مقالات حولالنحو والتصريف في العربية الإعراب أقسام الكلام اسم فعل حرف أقسام الجُمَل اسمية فعلية شبه جملة أنواع الكلام من حيث البناء والإعراب مُعرب لفظي تقديري محلي مبني حالات الإعراب رفع نصب جر جزم علامات الإعراب حركات حروف إعراب الجُمل جُمل معربة جُمَل لا محل...

Jovan Aćimović

Questa voce o sezione sull'argomento calciatori jugoslavi non cita le fonti necessarie o quelle presenti sono insufficienti. Puoi migliorare questa voce aggiungendo citazioni da fonti attendibili secondo le linee guida sull'uso delle fonti. Segui i suggerimenti del progetto di riferimento. Questa voce sull'argomento calciatori jugoslavi è solo un abbozzo. Contribuisci a migliorarla secondo le convenzioni di Wikipedia. Segui i suggerimenti del progetto di riferimento. Jovan Aćimov...

M656

/profillengkap.com/index.php/article/2017–18 in Australian soccer

العلاقات الجيبوتية الغواتيمالية

2017–18 Purdue Boilermakers women's basketball team

Sun Luban

Sinta Nuriyah

Wrestling at the 1924 Summer Olympics – Men's Greco-Roman light heavyweight