book

LLVM Code Generation

Name: LLVM Code Generation
Author: Quentin Colombet
ISBN: 9781837637782

by Quentin Colombet

May 2025

Beginner to intermediate

620 pages

18h 10m

English

Packt Publishing

Read now

Unlock full access

Preface
Who this book is forWhat this book coversTo get the most out of this bookGet in touch
Part 1: Getting Started with LLVM
Building LLVM and Understanding the Directory Structure
Getting the most out of this book – get to know your free benefits Technical requirementsGetting ready for LLVM’s worldPrerequisitesIdentifying the right version of the toolsInstalling the right toolsBuilding a compilerWhat is a compiler?Opening Clang’s hoodBuilding ClangExperimenting with ClangBuilding LLVMConfiguring the build systemCrash course on NinjaBuilding the core LLVM projectTesting a compilerCrash course on the Google test infrastructureCrash course on the LLVM Integrated TesterTesting in litDirectivesDescribing the RUN commandThe lit driver – llvm-litCrash course on FileCheckFileCheck by exampleLLVM unit testsFinding the source of a testRunning unit tests manuallyThe unit tests pass, what now?LLVM functional testsThe LLVM test suiteThe functional tests fail – what do you do?Understanding the directory structureHigh-level directory structureFocusing on the core LLVM projectA word on the include filesPrivate headersWhat is the deal with <project>/include/<project>?What is include/<project>-c?Overview of some of the LLVM componentsGeneric LLVM goodnessWorking with the LLVM IRGeneric backend infrastructureTarget-specific constructsSummaryQuiz time
Contributing to LLVM
Reporting an issueEngaging with the communityReviewing patchesContributing patchesUnderstanding patch contribution in a nutshellFollowing up with your contributionA word on adding testsSummaryQuiz time
Compiler Basics and How They Map to LLVM APIs
Technical requirementsA word on APIsUnderstanding compiler jargonTargetHostLoweringCanonical formBuild time, compile time, and runtimeBackend and middle-endApplication binary interfaceEncodingWorking with basic structuresModuleA module at the LLVM IR levelA module at the Machine IR levelFunctionA function in the LLVM IRA function in the Machine IRBasic blockA basic block in the LLVM IRA basic block in the Machine IRInstructionAn instruction in the LLVM IRAn instruction in the Machine IRControl flow graphReverse post-order traversalBackedgeCritical edgeIrreducible graphBuilding your first IRsBuilding your first LLVM IRA walk over the required APIsYour turnBuilding your first Machine IRA walk over the required APIsYour turnSummaryQuiz time
Writing Your First Optimization
Technical requirementsThe concept of valueSSAConstructing the SSA formDominanceDef-use and use-def chainsDef-use and use-def chains in the LLVM IRDef-use and use-def chains in the Machine IRTackling optimizationsLegalityInteger overflow/underflowFast-math flagsSide effectsProfitabilityInstruction lowering – TargetTransformInfo and TargetLoweringLibrary support – TargetLibraryInfoDatatype properties – DataLayoutRegister pressureBasic block frequencyMore precise instruction properties – scheduling model and instruction descriptionTransformation jargonInstcombineFixed pointLivenessHoistingSinkingFoldingLoopsTerminologyPreheaderHeaderExiting blockLatchExit blockWhere to get loop informationWriting a simple constant propagation optimizationThe optimizationSimplifying assumptionsMissing APIsThe Constant classThe APInt classCreating a constantReplacing a valueYour turnGoing furtherLegalityProfitabilityPropagating constants across typesSummaryQuiz time
Dealing with Pass Managers
Technical requirementsWhat is a pass?What is a pass manager?The legacy and new pass managerPass managers’ capabilitiesPopulating a pass managerInner workings of pass managersCreating a passWriting a pass for the legacy pass managerUsing the proper base classExpressing the dependencies of a passPreserving analysesSpecificities of the Pass classWriting a pass for the new pass managerImplementing the right methodRegistering an analysisDescribing the effects of your passInspecting the pass pipelineAvailable developer toolsPlumbing up the information you needInterpreting the logs of pass managersThe pass pipeline structureTime profileYour turnWriting your own passWriting your own pass pipelineSummaryFurther readingQuiz time
TableGen – LLVM Swiss Army Knife for Modeling
Technical requirementsGetting started with TableGenThe TableGen programming languageTypesProgramming with TableGenDefining multiple records at onceAssigning fieldsDiscovering a TableGen backendGeneral information on TableGen backends for LLVMDiscovering a TableGen backendThe implementation of intrinsicsThe content of a generated fileThe source of a TableGen backendDebugging the TableGen frameworkIdentifying the failing componentCracking open a TableGen backendSummaryFurther readingQuiz time
Part 2: Middle-End: LLVM IR to LLVM IR
Understanding LLVM IR
Technical requirementsUnderstanding the need for an IRWhat an IR isWhy use an IR?Introducing LLVM IRIdentifiersFunctionsBasic blocksInstructionsTypesSingle-value typesThe label typeAggregate typesTypes in the LLVM IR APIWalking through an exampleTarget-specific elements in LLVM IRIntrinsic functionsTripleFunction attributesData layoutApplication binary interfaceTextual versus binary formatLLVM IR API – cheat sheetSummaryFurther readingQuiz time

Survey of the Existing Passes
Technical requirementsHow to find the unknownLeveraging optUsing the LLVM code baseStarting from the implementationSurvey of the helper passesThe verifierThe printerAnalysis passesTarget transformation informationLoop informationAlias analysisBlock frequency infoDominator tree informationValue trackingCanonicalization passesThe instruction combinerAn example of a canonical rewriteAn example of an optimizationHow to use instcombineThe memory to register rewriterThe converter to loop-closed-SSA formOptimization passesInterprocedural optimizationsScalar optimizationsVectorizationSummaryFurther readingQuiz time
Introducing Target-Specific Constructs
Technical requirementsAdding a new backend in LLVMConnecting your target to the build systemRegistering your target with ClangAdding a new architecture to the Triple classPopulating the Target instancePlumbing your Target through ClangCreating your own intrinsicsThe pros and cons of intrinsicsCreating an intrinsic in the backendDefining our intrinsicsHooking up the TableGen backendTeaching LLVM IR about our intrinsicsConnecting an intrinsic to ClangWriting the .def file by handUsing the TableGen capabilitiesHooking up the built-in informationEstablishing the code generation linkAdding a target-specific TargetTransformInfo implementationEstablishing a connection to your target-specific informationIntroducing target-specific costsCustomizing the default middle-end pipelineUsing the new pass managerUsing the legacy pass managerA one-time setup – assembling a codegen pipelineFaking the instruction selectorFaking the lowering of the object fileCreating a skeleton for the assembly informationUsing the right abstractionSummaryFurther readingQuiz time
Hands-On Debugging LLVM IR Passes
Technical requirementsThe logging capabilities in LLVMPrinting the IR between passesPrinting the debug logPrinting high-level information about what happenedReducing the input IR sizeExtracting a subset of the input IRShrinking the IR automaticallyUsing sanitizersA crash course on LLDBStarting a debugging sessionControlling the executionStopping the programCommand resolutionResuming the executionInspecting the state of a programThe LLVM code base through a debuggerSummaryFurther readingQuiz time
Part 3: Introduction to the Backend
Getting Started with the Backend
Technical requirementsIntroducing the Machine IRHere comes the Machine IRThe Machine IR textual representationThe .mir file formatA primer on the YAML syntaxThe semantics of the different fieldsMapping the content of a .mir file to the C++ APIA deep dive into the body of a MachineFunction instanceWorking with a .mir fileGenerating a .mir fileRunning passesShrinking a .mir fileThe anatomy of a MachineInstr instanceIntroducing the MC layerWorking with MachineOperand instancesUnboxing a MachineOperand instanceDealing with explicit and implicit operandsUnderstanding the constraints of an operandWorking with registersThe concept of the register classThe concept of sub-registersThe concept of register tuplesThe concept of register unitsThe registers and SSA and non-SSA formsInteracting with registers in the debuggerCreating MachineInstr objectsDescribing registersWriting the target descriptionDescribing instructionsSummaryFurther readingQuiz time
Getting Started with the Machine Code Layer
Technical requirementsThe use of the MC layerConnecting the MC layerWhat instructions to describeAugmenting the target description with MC informationDefining the MC layer for the registersDefining the MC layer for the instructionsEnabling MC-based toolsLeveraging TableGenImplementing the missing piecesImplementing your own MCInstPrinter classImplementing your own MCCodeEmitter classImplementing your own XXXAsmParser classSummaryQuiz time
The Machine Pass Pipeline
Technical requirementsThe Machine pass pipeline at a glanceInjecting passesUsing the generic Machine optimizationsGeneric passes worth mentioningThe CodeGenPrepare passThe PeepholeOptimizer passThe MachineCombiner passSummaryFurther readingQuiz time
Part 4: LLVM IR to Machine IR
Getting Started with Instruction Selection
Technical requirementsOverview of the instruction selection frameworksHow does instruction selection work?Framework complementarityOverall differences between the selectorsCompile timeModularity and testabilityScopeWhich selector to use?FastISelSDISelGlobalISelSelectors’ inner workingsUnderstanding the DAG representationTextual representation of the SelectionDAG classManipulating a DAGUnderstanding the generic Machine IRTextual representation of generic attributesLowering constraints of the generic Machine IRAPIs to work with the generic Machine IRGroundwork to connect the codegen pipelineInstantiating the codegen pass pipelineProviding the key target APIs to the codegen pipelineConnecting SDISel to the codegen pipelineConnecting FastISel to the codegen pipelineConnecting GlobalISel to the codegen pipelineChoosing between different selectorsSummaryFurther readingQuiz time
Instruction Selection: The IR Building Phase
Technical requirementsOverview of the IR buildingDescribing the calling conventionWriting your target description of the calling conventionConnecting the gen-callingconv TableGen backendAnatomy of the CCValAssign classLowering the ABI with SDISelImplementing the lowering of formal argumentsProviding custom description for the SDNode classHandling of stack locationsLowering the ABI with FastISelLowering the ABI with GlobalISelSummaryFurther readingQuiz time
Instruction Selection: The Legalization Phase
Technical requirementsLegalization overviewLegalization actionsLegalization in SDISelDescribing your legal typesDescribing your legalization actionsImplementing a custom legalization actionLegalization in GlobalISelDescribing your legalization actions with the LegalizeRuleSet classCustom legalization in GlobalISelSummaryQuiz time
Instruction Selection: The Selection Phase and Beyond
Technical requirementsRegister bank selectionThe goal of the register bank selectionDescribing the register banksImplementing your RegisterBankInfo classInstruction selectionExpressing your selection patternsIntroduction to the selection patternsAdvanced selection patternsSelection in SDISelSelection in FastISelSelection in GlobalISelSetting up the InstructionSelector classImporting the selection patternsGoing beyond patternsFinalizing the selection pipelineUsing custom insertersCustomizing the TargetLowering::finalizeLowering methodOptimizationsUsing the DAGCombiner frameworkLeveraging the combiner frameworkDebugging the selectorsDebugging SDISelDebugging the GlobalISel match tableSummaryQuiz time
Part 5: Final Lowering and Optimizations
Instruction Scheduling
Technical requirementsOverview of the instruction scheduling frameworkThe ScheduleDAGInstrs classChanging the scheduling algorithmThe scheduling modelThe scheduling eventsThe processing unitsThe scheduling bindingsGluing everything togetherImplementing your scheduling modelConnecting your scheduling modelDescribing a processor modelInstantiating your subtargetGuidelines to get started with your scheduling modelSummaryQuiz time
Register Allocation
Technical requirementsOverview of register allocation in LLVMEnabling the register allocation infrastructureIntroducing the slot indexesIntroducing the live intervalsMaintaining the live intervalsSummaryFurther readingQuiz time
Lowering of the Stack Layout
Technical requirementsOverview of stack loweringHandling of stack slotsFrom frame index to stack slotThe lowering of the stack frameIntroducing the reserved call frameImplementing the frame-lowering target hooksThe expansion of the frame indicesIntroducing register scavengingProvisioning an emergency spill slotExpanding the frame indicesSummaryQuiz time
Getting Started with the Assembler
Technical requirementsOverview of the lowering of a textual assembly fileAssembling with the LLVM infrastructureImplementing an assemblerProviding the MCCodeEmitter classHandling the fixups with the MCAsmBackend classRecording the relocations with the MCObjectTargetWriter classSummaryFurther readingQuiz time
Unlock Your Book’s Exclusive Benefits
How to unlock these benefits in three easy stepsNeed help?
Other Books You May Enjoy
Index

Content preview from LLVM Code Generation

17 Instruction Selection: The Selection Phase and Beyond

The instruction selection phase, or selection phase for short, is the last phase of the instruction selection pipeline. It is responsible for translating the generic, yet legal, intermediate representation (IR) used by the instruction selection framework to the target-specific incantation of the Machine IR.

In LLVM, this translation can match sequences of instructions to produce highly optimized code right off the bat.

In this chapter, you will learn how to do the following:

Describe the matching of these sequences of instructions with patterns
Integrate this matching into all the instruction selection frameworks – that is, the SelectionDAG instruction selection (SDISel) framework, the ...

Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.

Read now

Unlock full access

More than 5,000 organizations count on O’Reilly

O’Reilly covers everything we've got, with content to help us build a world-class technology community, upgrade the capabilities and competencies of our teams, and improve overall team performance as well as their engagement.

Julian F.

Head of Cybersecurity

I wanted to learn C and C++, but it didn't click for me until I picked up an O'Reilly book. When I went on the O’Reilly platform, I was astonished to find all the books there, plus live events and sandboxes so you could play around with the technology.

Addison B.

Field Engineer

I’ve been on the O’Reilly platform for more than eight years. I use a couple of learning platforms, but I'm on O'Reilly more than anybody else. When you're there, you start learning. I'm never disappointed.

Amir M.

Data Platform Tech Lead

I'm always learning. So when I got on to O'Reilly, I was like a kid in a candy store. There are playlists. There are answers. There's on-demand training. It's worth its weight in gold, in terms of what it allows me to do.

Mark W.

Embedded Software Engineer

Building Low Latency Applications with C++

Publisher Resources

ISBN: 9781837637782

Cloud Computing

Data Engineering

Data Science

AI & ML

Programming Languages

Software Architecture

IT/Ops

Security

Design

Business

Soft Skills

LLVM Code Generation

by Quentin Colombet

17

Instruction Selection: The Selection Phase and Beyond

Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.