데드 코드 제거
Dead-code elimination컴파일러 이론에서 데드 코드 제거(DCE, 데드 코드 제거, 데드 코드 제거 또는 데드 코드 스트립이라고도 함)는 프로그램 결과에 영향을 주지 않는 코드를 제거하기 위한 컴파일러 최적화입니다.이러한 코드를 삭제하면 몇 가지 이점이 있습니다.일부 컨텍스트에서 중요한 고려사항인 프로그램 크기를 축소하고 실행 중인 프로그램이 관련 없는 작업을 실행하는 것을 방지하여 실행 시간을 단축할 수 있습니다.또한 프로그램 구조를 단순화함으로써 추가적인 최적화를 가능하게 할 수 있습니다.데드 코드에는 실행할 수 없는 코드(도달할 수 없는 코드) 및 데드 변수에만 영향을 주는 코드(쓰기되었지만 다시 읽지 않음)가 포함됩니다. 즉, 프로그램과 무관합니다.
예
C에 기재되어 있는 다음의 예를 생각해 봅시다.
인트 후우(무효) { 인트 a = 24; 인트 b = 25; /* 데드 변수에 할당 */ 인트 c; c = a * 4; 돌아가다 c; b = 24; /* 도달 불능 코드 */ 돌아가다 0; }
값의 용도를 간단히 분석하면 다음과 같은 가치가 있습니다.b
첫 번째 할당이 내부에서 사용되지 않은 후foo
.더 나아가,b
내부 로컬 변수로 선언됩니다.foo
그 값은 외부에서는 사용할 수 없습니다.foo
따라서 변수는b
가 정지되어 있기 때문에, 옵티마이저는 스토리지 공간을 재확보해, 초기화를 없앨 수 있습니다.
또, 제1의 리턴 스테이트먼트가 무조건 실행되기 때문에, 실현 가능한 실행 패스는, 에의 제2의 할당에 이르지 않는다.b
따라서 할당에 도달할 수 없으며 삭제할 수 있습니다.절차에서 Return 스테이트먼트 뒤에 라벨이 붙어 있는 등 보다 복잡한 제어 플로우가 있는 경우goto
이 순서의 다른 곳에 할당에 실현 가능한 실행 경로가 존재할 수 있습니다.b
.
또한 함수에서 일부 계산이 수행되더라도 해당 값은 이 함수의 범위 밖에서 액세스할 수 있는 위치에 저장되지 않습니다.또한 함수가 정적 값(96)을 반환하면 반환 값으로 단순화할 수 있다(이 단순화를 연속 폴딩이라고 한다).
대부분의 고급 컴파일러에는 데드 코드 제거를 활성화하는 옵션이 있으며, 경우에 따라 다른 레벨로 사용할 수 있습니다.낮은 레벨에서는 실행할 수 없는 명령만 삭제될 수 있습니다.더 높은 수준에서는 사용되지 않는 변수에 대한 공간이 예약되지 않을 수도 있습니다.더 높은 레벨은 아무런 목적도 없는 명령이나 기능을 결정하여 제거할 수 있습니다.
데드 코드 제거의 일반적인 용도는 프리프로세서를 통한 선택적 코드 포함의 대체 수단입니다.다음 코드를 고려합니다.
인트 주된(무효) { 인트 a = 5; 인트 b = 6; 인트 c; c = a * (b / 2); 한다면 (0) { /* 디버깅 */ 인쇄물(%d\n", c); } 돌아가다 c; }
식 0은 항상 false로 평가되기 때문에 if 스테이트먼트 내의 코드는 실행할 수 없습니다.데드 코드를 삭제하면 최적화된 프로그램에서 완전히 삭제됩니다.이 기술은 디버깅에서 공통적으로 코드 블록을 선택적으로 활성화하기 위해 사용됩니다.데드 코드 제거 기능이 있는 옵티마이저를 사용하면 동일한 작업을 수행하기 위해 프리프로세서를 사용할 필요가 없습니다.
실제로 옵티마이저가 검출하는 데드코드의 대부분은 옵티마이저의 다른 변환에 의해 생성됩니다.예를 들어, 연산자 강도 감소를 위한 고전적인 기술은 코드에 새로운 연산을 삽입하여 더 오래되고 더 비싼 연산을 [1]중단시킵니다.그 후의 데드 코드를 삭제하면, 이러한 계산이 삭제되어 (강도 저감 알고리즘을 복잡하게 하지 않고) 효과가 완료됩니다.
과거에는 데이터 흐름 [2]분석에서 파생된 정보를 사용하여 데드 코드 제거가 수행되었습니다.정적 단일 할당 형식(SSA)에 기초한 알고리즘은 Ron Cytron [3]등의 SSA 형식에 관한 원본 저널 기사에 기재되어 있다.Robert Shillingsburg(일명 Shillner)는 알고리즘을 개선하고 불필요한 제어 흐름 [4]연산을 제거하기 위한 동반 알고리즘을 개발했습니다.
동적 데드 코드 제거
데드 코드는 일반적으로 무조건 데드로 간주됩니다.따라서 컴파일 시 데드코드 제거를 통해 데드코드를 제거하는 것이 합리적입니다.
그러나 실제로는 코드 섹션이 데드 또는 도달 불능 코드를 나타내는 것은 컴파일 또는 조립 시 알 수 없는 특정 조건에서만 일반적입니다.이러한 조건은, 다른 런타임 환경(예를 들면, operating system의 다른 버전, 또는 특정의 타겟 환경에 로드된 드라이버나 서비스의 다른 세트나 조합 등)에 의해서 발생하는 경우가 있습니다.이러한 환경에서는, 코드에 다른 특수한 케이스 세트가 필요하게 되는 경우가 있습니다만, 동시에, oth에 대해서는 조건부로 데드코드가 됩니다.er [5][6]케이스또, 소프트웨어(드라이버나 상주 서비스등)는, 유저의 기호에 따라 특정의 기능을 포함 또는 제외하도록 설정할 수 있기 때문에, 특정의 [5][6]시나리오에서는 미사용의 코드 부분을 사용할 수 없게 됩니다.모듈러 소프트웨어는 온디맨드 방식으로만 라이브러리를 동적으로 로드하도록 개발될 수 있지만, 대부분의 경우 특정 라이브러리에서 관련 루틴만 로드하는 것은 불가능하며, 이것이 지원된다 하더라도 루틴에는 특정 시나리오에서는 데드 코드로 간주될 수 있지만 com에서는 배제할 수 없는 코드 섹션이 포함될 수 있습니다.쌓기 시간이야, 이미.
디맨드를 동적으로 검출하고, 의존관계를 특정 및 해결하며, 이러한 조건부 데드 코드를 제거하고, 로드 시 또는 실행 시 나머지 코드를 재결합하기 위해 사용되는 기술을 동적 데드 코드 제거[5][6][7][8][9][10][11][12][13][14][15][16][17] 또는 동적 데드 명령 [18]제거라고 합니다.
대부분의 프로그래밍 언어, 컴파일러 및 운영체제는 라이브러리의 동적 로딩 및 지연 링크보다 더 많은 지원을 제공하지 않습니다.따라서 동적 데드코드 제거를 사용하는 소프트웨어는 사전에 컴파일된 언어 [7][11][8]또는 어셈블리 언어로 작성된 언어와 함께 매우 드물기 때문입니다.다만, 적시 컴파일을 실시하는 언어 실장은, 데드 코드의 [17][19][20]제거를 위해서 동적으로 최적화할 수 있습니다.
초점은 다르지만 동적 소프트웨어 업데이트 및 핫 패치에도 유사한 접근 방식이 사용될 수 있습니다.
「 」를 참조해 주세요.
- 용장코드
- 심플화(심볼 계산)
- 부분 용장성 제거
- 연결 제거
- 동적 소프트웨어 업데이트
- 동적 결합(컴퓨팅)
- 자기 재배치
- 소프트웨어 크러프트
- 나무 흔들림
- 패스 후 최적화
- 프로파일 가이드 최적화
- 슈퍼 옵티마이저
- 함수 다중 버전
레퍼런스
- ^ Allen, Frances; Cocke, John; Kennedy, Ken (June 1981). "Reduction of Operator Strength". In Jones, Neil D.; Muchnick, Steven Stanley (eds.). Program Flow Analysis: Theory & Application. Prentice-Hall. ISBN 0-13729681-9.
- ^ Kennedy, Ken (June 1981). "A Survey of Data-flow Analysis Techniques". In Jones, Neil D.; Muchnick, Steven Stanley (eds.). Program Flow Analysis: Theory & Application. Prentice-Hall. ISBN 0-13729681-9.
- ^ Cytron, Ron K.; Ferrante, Jeanne; Rosen, Barry K.; Zadeck, F. Kenneth (1991). Efficiently Computing Static Single Assignment Form and the Program Dependence Graph. ACM TOPLAS 13(4).
- ^ Cooper, Keith D.; Torczon, Linda (2003) [2002-01-01]. Engineering a Compiler. Morgan Kaufmann. pp. 498ff. ISBN 978-1-55860698-2.
- ^ a b c Paul, Matthias R. (2002-04-03) [2001-06-18]. "[fd-dev] Ctrl+Alt+Del". freedos-dev. Archived from the original on 2017-09-09. Retrieved 2017-09-09.
[…] any of the […] options can be "permanently" excluded at installation time (will also save the memory for the corresponding code excerpts due to our Dynamic Dead Code Elimination), or it can be disabled or enabled at any later time via API functions in case someone wants to keep a user from being able to reboot the machine. […] we are considering to add more synchronous cache flush calls […] Due to our Dynamic Dead Code Elimination method this would not cause any kind of bloating when not needed in a particular target configuration as a particular cache flush call would be included in FreeKEYB's runtime image only if the corresponding disk cache is loaded as well or FreeKEYB was told by command line switches to load the corresponding support.
- ^ a b c Paul, Matthias R. (2002-04-06). "[fd-dev] Ctrl+Alt+Del". freedos-dev. Archived from the original on 2019-04-27. Retrieved 2019-04-27.
[…] FreeKEYB builds the driver's runtime image at initialization time depending on the type of machine it is being loaded on, the type of keyboard, layout, country and code page used, the type of mouse and video adapter(s) installed, the other drivers loaded on that system, the operating system and the load and relocation method(s) used, the individual features included, and the configuration options specified in the command line. Due to the large number of command line switches and options supported […] (around fifty switches […] with multiple possible settings) there is a high number of feature combinations with uncountable dependencies […] resulting in […] endless number of […] different target images. FreeKEYB's Dynamic Dead Code Elimination technique manages to resolve […] these […] dependencies and […] remove dead code and data […] is not restricted to […] include or exclude a somewhat limited number of modules or whole sub-routines and fix up some dispatch tables as in classical TSR programming, but […] works […] at […] byte level […] able to remove […] individual instructions in the middle of larger routines […] distributed all over the code to handle a particular case or support a specific feature […] special tools are used to analyze the code […] and create […] fixup tables […] automated […] using conditional defines […] to declare the various cases […] not only optional at assembly time but at initialization time […] without the […] overhead of having at least some amount of dead code left in the runtime image […] to keep track of all the dependencies between […] these conditionals, dynamically build and relocate the runtime image, fix up all the references between these small, changing, and moving binary parts […] still allowing to use the tiny .COM/.SYS style […] model […] is done at initialization time […] API to import and export object structures between FreeKEYB and the calling application […] to transparently resize and move them internally […] at runtime […]
- ^ a b Paul, Matthias R.; Frinke, Axel C. (1997-10-13) [first published 1991], FreeKEYB - Enhanced DOS keyboard and console driver (User Manual) (v6.5 ed.) [1] (NB).FreeKEYB는 대부분의 키보드 레이아웃, 코드 페이지 및 국가 코드를 지원하는 Unicode 기반의 동적 구성 가능한 K3PLUS의 후속 버전입니다.시판 매크로 어셈블러와 자동 전처리 및 후처리 분석 툴의 프레임워크를 사용하여 바이너리 코드와 함께 실행 파일에 내장되는 의존관계 및 코드 모핑 메타 데이터를 생성하고, 로더를 스스로 폐기, 완화 및 재배치함으로써 드라이버는 바이트 수준의 세분화된 동적 데드 코드를 구현합니다.e 부하 시 제거 및 재배치 기술, 실행 시 자체 코드 및 재구성 가능.기본 하드웨어, 운영체제, 드라이버 구성 및 선택한 기능 세트 및 로케일에 따라 메모리 설치 공간을 최소화하고 표준 형식을 닫습니다(약 60개의 구성 스위치 위트).h 거의 무제한의 조합에 대해 수백 개의 옵션을 선택할 수 있습니다).이러한 복잡성과 역동성은 기존 드라이버와 마찬가지로 단일 실행 파일을 처리하는 사용자에게 숨겨져 있습니다.K3PLUS는 그 당시 독일에서 널리 보급되어 있던 DOS용 확장 키보드 드라이버로, 그 외의 유럽 언어에도 대응하고 있습니다.이미 서브세트의 기능을 서포트하고 있습니다만, 다이나믹한 데드 코드 삭제는 실장하고 있지 않습니다).
- ^ a b 폴, 마티아스 R.(2001-04-10)."[ANN]프리 도스 출시 6베타"(독일어로).뉴스:de.comp.os.msdos.그 2017-09-09에 원래에서 Archived.2017-07-02 Retrieved.[…]brandneue[s]형상 derdynamischen Dead-Code-Elimination, Bestandteile 데 Treibers 이전에 zum Installationszeitpunkt zusammenbastelt 운트 reloziert, 그렇게daßkeineungenutzten Code- 냄새 Datenbereichemehr 주민 bleiben(z.B.wenn jemand ein bestimmtes FreeKEYB-Feature nicht benötigt)notwendigen 다이 jeweils 죽는다.[…](NB다.이.)소프트웨어를byte-level 입상 동적dead-code 제거거나 컴파일되 ahead-of-time 조립의 첫번째로 알려지구현을 나타냅니다.
- ^ Paul, Matthias R. (2001-08-21). "[fd-dev] Changing codepages in FreeDOS". freedos-dev. Archived from the original on 2019-04-19. Retrieved 2019-04-20.
[…] a […] unique feature […] we call dynamic dead code elimination, so you can at installation time […] specify which components of the driver you want and which you don't. This goes to an extent of dynamic loadable modularization and late linkage I have not seen under DOS so far. If you do not like the screen saver, macros, the calculator, or mouse support, or <almost anything else>, you can specify this at the command line, and FreeKEYB, while taking all the dependencies between the routines into account, will completely remove all the code fragments, which deal with that feature and are not necessary to provide the requested functionality, before the driver relocates the image into the target location and makes itself resident. Removing some smaller features just saves a couple of bytes but excluding more complex components can save you half a Kb and more. You can also specify the size of the data areas […]
- ^ Paul, Matthias R. (2001-12-30). "KEYBOARD.SYS internal structure". Newsgroup: comp.os.msdos.programmer. Archived from the original on 2017-09-09. Retrieved 2017-07-03.
[…] the loader will dynamically optimize the resident data areas and code sections at byte level to remove any redundancy from the driver depending on the given hardware/software/driver configuration and locale. […]
- ^ a b Paul, Matthias R.; Frinke, Axel C. (2006-01-16), FreeKEYB - Advanced international DOS keyboard and console driver (User Manual) (v7 preliminary ed.)
- ^ Paul, Matthias R. (2002-02-02). "Treiber dynamisch nachladen (Intra-Segment-Offset-Relokation zum Laden von TSRs in die HMA)" [Loading drivers dynamically (Intra-segment offset relocation to load TSRs into the HMA)] (in German). Newsgroup: de.comp.os.msdos. Archived from the original on 2017-09-09. Retrieved 2017-07-02.
- ^ Paul, Matthias R. (2002-02-24). "GEOS/NDO info for RBIL62?". Newsgroup: comp.os.geos.programmer. Archived from the original on 2019-04-20. Retrieved 2019-04-20.
[…] Since FreeKEYB uses our dynamic dead-code-elimination to optimize its memory image for the target environment at load time, I would certainly like to add special support into FreeKEYB for GEOS which could be controlled by a command line option, so the extra code is only loaded when GEOS is used as well. […]
- ^ Paul, Matthias R. (2002-03-15). "AltGr keyboard layer under GEOS?". Newsgroup: comp.os.geos.misc. Archived from the original on 2019-04-20. Retrieved 2019-04-20.
[…] I would be willing to add special hooks into FreeKEYB, our much advanced DOS keyboard driver, would it prove to improve the usability under GEOS […] Due to our sophisticated new Dynamic Dead Code Elimination technology which removes at byte level any code snippets unused in a particular given driver, user, or system configuration and hardware environment when the driver's installer builds and relocates the load image of itself, this would have no memory impact for non-GEOS users at all, so there's not much to worry about (memory footprint etc.) as in traditionally coded DOS drivers. […]
- ^ Thammanur, Sathyanarayan (2001-01-31). A Just in Time Register Allocation and Code Optimization Framework for Embedded Systems (MS thesis). University of Cincinnati, Engineering: Computer Engineering. ucin982089462. [2][3]
- ^ Glew, Andy (2011-03-02). "Dynamic dead code elimination and hardware futures". [4] [5]
- ^ a b 콘웨이, 앤드류(1995-12-04)."고리 데이터 구조".뉴스:comp.lang.functional.그 2017-09-09에 원래에서 Archived.2017-07-03 Retrieved.[…] 느긋한 계산 법은 기본적으로 역동적인 불필요한 코드의 제거.[…](NB다.용어 동적dead-code 제거 가능 최초의 공개 사용, 비록 관념적으로만과 게으른 평가에 대한 실용적인 언어로 된 것에 초점을 맞추고 있다.).
- ^ Butts, J. Adam; Sohi, Guri (October 2002). "Dynamic Dead-Instruction Detection and Elimination" (PDF). San Jose, CA, USA: Computer Science Department, University of Wisconsin-Madison. ASPLOS X ACM 1-58113-574-2/02/0010. Archived (PDF) from the original on 2019-04-20. Retrieved 2017-06-23.
- ^ Johng, Yessong; Danielsson, Per; Ehnsiö, Per; Hermansson, Mats; Jolanki, Mika; Moore, Scott; Strander, Lars; Wettergren, Lars (2002-11-08). "Chapter 5. Java overview and iSeries implementation - 5.1.1. Miscellaneous components". Intentia Movex Java on the IBM iSeries Server - An Implementation Guide - Overview of Movex Java on the iSeries server - Movex Java on iSeries installation and configuration - Operational tips and techniques (PDF). Red Books. IBM Corp. p. 41. ISBN 0-73842461-7. SG24-6545-00. Archived (PDF) from the original on 2013-10-08. Retrieved 2019-04-20. [6]
- ^ Polito, Guillermo (2015). "Virtualization Support for Application Runtime Specialization and Extension - Programming Languages" (PDF). Universite des Sciences et Technologies de Lille. pp. 111–124. HAL Id: tel-01251173. Archived (PDF) from the original on 2017-06-23. Retrieved 2017-06-23.
추가 정보
- Bodík, Rastislav; Gupta, Rajiv (June 1997). "Partial dead code elimination using slicing transformations". Proceedings of the ACM SIGPLAN 1997 Conference on Programming Language Design and Implementation (PLDI '97): 682–694.
- Aho, Alfred Vaino; Sethi, Ravi; Ullman, Jeffrey David (1986). Compilers - Principles, Techniques and Tools. Addison Wesley Publishing Company. ISBN 0-201-10194-7.
- Muchnick, Steven Stanley (1997). Advanced Compiler Design and Implementation. Morgan Kaufmann Publishers. ISBN 1-55860-320-4.
- Grune, Dick; Bal, Henri Elle; Jacobs, Ceriel J. H.; Langendoen, Koen G. (2000). Modern Compiler Design. John Wiley & Sons, Inc. ISBN 0-471-97697-0.
- Kennedy, Ken; Allen, Randy (2002). "Chapter 4.4. Data Flow Analysis - Chapter 4.4.2. Dead Code Elimination". Optimizing Compilers for Modern Architectures: A Dependence-Based Approach (2011 digital print of 1st ed.). Academic Press / Morgan Kaufmann Publishers / Elsevier. pp. 137, 145–147, 167. ISBN 978-1-55860-286-1. LCCN 2001092381.
- Muth, Robert; Debray, Saumya K.; Watterson, Scott; De Bosschere, Koen (January 2001) [1999-11-02]. "alto: a link-time optimizer for the Compaq Alpha". Software: Practice and Experience. 31 (1): 67–101. CiteSeerX 10.1.1.33.4933. doi:10.1002/1097-024X(200101)31:1<67::AID-SPE357>3.0.CO;2-A. S2CID 442062. [7]