323 lines · cpp
1//===- CodeGeneration.cpp - Code generate the Scops using ISL. ---------======//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------------===//8//9// The CodeGeneration pass takes a Scop created by ScopInfo and translates it10// back to LLVM-IR using the ISL code generator.11//12// The Scop describes the high level memory behavior of a control flow region.13// Transformation passes can update the schedule (execution order) of statements14// in the Scop. ISL is used to generate an abstract syntax tree that reflects15// the updated execution order. This clast is used to create new LLVM-IR that is16// computationally equivalent to the original control flow region, but executes17// its code in the new execution order defined by the changed schedule.18//19//===----------------------------------------------------------------------===//20 21#include "polly/CodeGen/CodeGeneration.h"22#include "polly/CodeGen/IRBuilder.h"23#include "polly/CodeGen/IslAst.h"24#include "polly/CodeGen/IslNodeBuilder.h"25#include "polly/CodeGen/PerfMonitor.h"26#include "polly/CodeGen/Utils.h"27#include "polly/DependenceInfo.h"28#include "polly/Options.h"29#include "polly/ScopInfo.h"30#include "polly/Support/ScopHelper.h"31#include "llvm/ADT/Statistic.h"32#include "llvm/Analysis/LoopInfo.h"33#include "llvm/Analysis/RegionInfo.h"34#include "llvm/IR/BasicBlock.h"35#include "llvm/IR/Dominators.h"36#include "llvm/IR/Function.h"37#include "llvm/IR/Verifier.h"38#include "llvm/Support/Debug.h"39#include "llvm/Support/ErrorHandling.h"40#include "llvm/Support/raw_ostream.h"41#include "llvm/Transforms/Utils/LoopUtils.h"42#include "isl/ast.h"43#include <cassert>44 45using namespace llvm;46using namespace polly;47 48#include "polly/Support/PollyDebug.h"49#define DEBUG_TYPE "polly-codegen"50 51static cl::opt<bool> Verify("polly-codegen-verify",52 cl::desc("Verify the function generated by Polly"),53 cl::Hidden, cl::cat(PollyCategory));54 55bool polly::PerfMonitoring;56 57static cl::opt<bool, true>58 XPerfMonitoring("polly-codegen-perf-monitoring",59 cl::desc("Add run-time performance monitoring"), cl::Hidden,60 cl::location(polly::PerfMonitoring),61 cl::cat(PollyCategory));62 63STATISTIC(ScopsProcessed, "Number of SCoP processed");64STATISTIC(CodegenedScops, "Number of successfully generated SCoPs");65STATISTIC(CodegenedAffineLoops,66 "Number of original affine loops in SCoPs that have been generated");67STATISTIC(CodegenedBoxedLoops,68 "Number of original boxed loops in SCoPs that have been generated");69 70namespace polly {71 72/// Mark a basic block unreachable.73///74/// Marks the basic block @p Block unreachable by equipping it with an75/// UnreachableInst.76void markBlockUnreachable(BasicBlock &Block, PollyIRBuilder &Builder) {77 auto OrigTerminator = Block.getTerminator()->getIterator();78 Builder.SetInsertPoint(&Block, OrigTerminator);79 Builder.CreateUnreachable();80 OrigTerminator->eraseFromParent();81}82} // namespace polly83 84static void verifyGeneratedFunction(Scop &S, Function &F, IslAstInfo &AI) {85 if (!Verify || !verifyFunction(F, &errs()))86 return;87 88 POLLY_DEBUG({89 errs() << "== ISL Codegen created an invalid function ==\n\n== The "90 "SCoP ==\n";91 errs() << S;92 errs() << "\n== The isl AST ==\n";93 AI.print(errs());94 errs() << "\n== The invalid function ==\n";95 F.print(errs());96 });97 98 llvm_unreachable("Polly generated function could not be verified. Add "99 "-polly-codegen-verify=false to disable this assertion.");100}101 102// CodeGeneration adds a lot of BBs without updating the RegionInfo103// We make all created BBs belong to the scop's parent region without any104// nested structure to keep the RegionInfo verifier happy.105static void fixRegionInfo(Function &F, Region &ParentRegion, RegionInfo &RI) {106 for (BasicBlock &BB : F) {107 if (RI.getRegionFor(&BB))108 continue;109 110 RI.setRegionFor(&BB, &ParentRegion);111 }112}113 114/// Remove all lifetime markers (llvm.lifetime.start, llvm.lifetime.end) from115/// @R.116///117/// CodeGeneration does not copy lifetime markers into the optimized SCoP,118/// which would leave the them only in the original path. This can transform119/// code such as120///121/// llvm.lifetime.start(%p)122/// llvm.lifetime.end(%p)123///124/// into125///126/// if (RTC) {127/// // generated code128/// } else {129/// // original code130/// llvm.lifetime.start(%p)131/// }132/// llvm.lifetime.end(%p)133///134/// The current StackColoring algorithm cannot handle if some, but not all,135/// paths from the end marker to the entry block cross the start marker. Same136/// for start markers that do not always cross the end markers. We avoid any137/// issues by removing all lifetime markers, even from the original code.138///139/// A better solution could be to hoist all llvm.lifetime.start to the split140/// node and all llvm.lifetime.end to the merge node, which should be141/// conservatively correct.142static void removeLifetimeMarkers(Region *R) {143 for (auto *BB : R->blocks()) {144 auto InstIt = BB->begin();145 auto InstEnd = BB->end();146 147 while (InstIt != InstEnd) {148 auto NextIt = InstIt;149 ++NextIt;150 151 if (auto *IT = dyn_cast<IntrinsicInst>(&*InstIt)) {152 switch (IT->getIntrinsicID()) {153 case Intrinsic::lifetime_start:154 case Intrinsic::lifetime_end:155 IT->eraseFromParent();156 break;157 default:158 break;159 }160 }161 162 InstIt = NextIt;163 }164 }165}166 167static bool generateCode(Scop &S, IslAstInfo &AI, LoopInfo &LI,168 DominatorTree &DT, ScalarEvolution &SE,169 RegionInfo &RI) {170 // Check whether IslAstInfo uses the same isl_ctx. Since -polly-codegen171 // reports itself to preserve DependenceInfo and IslAstInfo, we might get172 // those analysis that were computed by a different ScopInfo for a different173 // Scop structure. When the ScopInfo/Scop object is freed, there is a high174 // probability that the new ScopInfo/Scop object will be created at the same175 // heap position with the same address. Comparing whether the Scop or ScopInfo176 // address is the expected therefore is unreliable.177 // Instead, we compare the address of the isl_ctx object. Both, DependenceInfo178 // and IslAstInfo must hold a reference to the isl_ctx object to ensure it is179 // not freed before the destruction of those analyses which might happen after180 // the destruction of the Scop/ScopInfo they refer to. Hence, the isl_ctx181 // will not be freed and its space not reused as long there is a182 // DependenceInfo or IslAstInfo around.183 IslAst &Ast = AI.getIslAst();184 if (Ast.getSharedIslCtx() != S.getSharedIslCtx()) {185 POLLY_DEBUG(dbgs() << "Got an IstAst for a different Scop/isl_ctx\n");186 return false;187 }188 189 // Check if we created an isl_ast root node, otherwise exit.190 isl::ast_node AstRoot = Ast.getAst();191 if (AstRoot.is_null())192 return false;193 194 // Collect statistics. Do it before we modify the IR to avoid having it any195 // influence on the result.196 auto ScopStats = S.getStatistics();197 ScopsProcessed++;198 199 auto &DL = S.getFunction().getDataLayout();200 Region *R = &S.getRegion();201 assert(!R->isTopLevelRegion() && "Top level regions are not supported");202 203 ScopAnnotator Annotator;204 205 simplifyRegion(R, &DT, &LI, &RI);206 assert(R->isSimple());207 BasicBlock *EnteringBB = S.getEnteringBlock();208 assert(EnteringBB);209 PollyIRBuilder Builder(EnteringBB->getContext(), ConstantFolder(),210 IRInserter(Annotator));211 Builder.SetInsertPoint(EnteringBB,212 EnteringBB->getTerminator()->getIterator());213 214 // Only build the run-time condition and parameters _after_ having215 // introduced the conditional branch. This is important as the conditional216 // branch will guard the original scop from new induction variables that217 // the SCEVExpander may introduce while code generating the parameters and218 // which may introduce scalar dependences that prevent us from correctly219 // code generating this scop.220 BBPair StartExitBlocks =221 std::get<0>(executeScopConditionally(S, Builder.getTrue(), DT, RI, LI));222 BasicBlock *StartBlock = std::get<0>(StartExitBlocks);223 BasicBlock *ExitBlock = std::get<1>(StartExitBlocks);224 225 removeLifetimeMarkers(R);226 auto *SplitBlock = StartBlock->getSinglePredecessor();227 228 IslNodeBuilder NodeBuilder(Builder, Annotator, DL, LI, SE, DT, S, StartBlock);229 230 // All arrays must have their base pointers known before231 // ScopAnnotator::buildAliasScopes.232 NodeBuilder.allocateNewArrays(StartExitBlocks);233 Annotator.buildAliasScopes(S);234 235 if (PerfMonitoring) {236 PerfMonitor P(S, EnteringBB->getParent()->getParent());237 P.initialize();238 P.insertRegionStart(SplitBlock->getTerminator());239 240 BasicBlock *MergeBlock = ExitBlock->getUniqueSuccessor();241 P.insertRegionEnd(MergeBlock->getTerminator());242 }243 244 // First generate code for the hoisted invariant loads and transitively the245 // parameters they reference. Afterwards, for the remaining parameters that246 // might reference the hoisted loads. Finally, build the runtime check247 // that might reference both hoisted loads as well as parameters.248 // If the hoisting fails we have to bail and execute the original code.249 Builder.SetInsertPoint(SplitBlock,250 SplitBlock->getTerminator()->getIterator());251 if (!NodeBuilder.preloadInvariantLoads()) {252 // Patch the introduced branch condition to ensure that we always execute253 // the original SCoP.254 auto *FalseI1 = Builder.getFalse();255 auto *SplitBBTerm = Builder.GetInsertBlock()->getTerminator();256 SplitBBTerm->setOperand(0, FalseI1);257 258 // Since the other branch is hence ignored we mark it as unreachable and259 // adjust the dominator tree accordingly.260 auto *ExitingBlock = StartBlock->getUniqueSuccessor();261 assert(ExitingBlock);262 auto *MergeBlock = ExitingBlock->getUniqueSuccessor();263 assert(MergeBlock);264 markBlockUnreachable(*StartBlock, Builder);265 markBlockUnreachable(*ExitingBlock, Builder);266 auto *ExitingBB = S.getExitingBlock();267 assert(ExitingBB);268 DT.changeImmediateDominator(MergeBlock, ExitingBB);269 DT.eraseNode(ExitingBlock);270 } else {271 NodeBuilder.addParameters(S.getContext().release());272 Value *RTC = NodeBuilder.createRTC(AI.getRunCondition().release());273 274 Builder.GetInsertBlock()->getTerminator()->setOperand(0, RTC);275 276 auto *CI = dyn_cast<ConstantInt>(RTC);277 // The code below annotates the "llvm.loop.vectorize.enable" to false278 // for the code flow taken when RTCs fail. Because we don't want the279 // Loop Vectorizer to come in later and vectorize the original fall back280 // loop when Polly is enabled. This avoids loop versioning on fallback281 // loop by Loop Vectorizer. Don't do this when Polly's RTC value is282 // false (due to code generation failure), as we are left with only one283 // version of Loop.284 if (!(CI && CI->isZero())) {285 for (Loop *L : LI.getLoopsInPreorder()) {286 if (S.contains(L))287 addStringMetadataToLoop(L, "llvm.loop.vectorize.enable", 0);288 }289 }290 291 // Explicitly set the insert point to the end of the block to avoid that a292 // split at the builder's current293 // insert position would move the malloc calls to the wrong BasicBlock.294 // Ideally we would just split the block during allocation of the new295 // arrays, but this would break the assumption that there are no blocks296 // between polly.start and polly.exiting (at this point).297 Builder.SetInsertPoint(StartBlock,298 StartBlock->getTerminator()->getIterator());299 300 NodeBuilder.create(AstRoot.release());301 NodeBuilder.finalize();302 fixRegionInfo(*EnteringBB->getParent(), *R->getParent(), RI);303 304 CodegenedScops++;305 CodegenedAffineLoops += ScopStats.NumAffineLoops;306 CodegenedBoxedLoops += ScopStats.NumBoxedLoops;307 }308 309 Function *F = EnteringBB->getParent();310 verifyGeneratedFunction(S, *F, AI);311 for (auto *SubF : NodeBuilder.getParallelSubfunctions())312 verifyGeneratedFunction(S, *SubF, AI);313 314 // Mark the function such that we run additional cleanup passes on this315 // function (e.g. mem2reg to rediscover phi nodes).316 F->addFnAttr("polly-optimized");317 return true;318}319 320bool polly::runCodeGeneration(Scop &S, RegionInfo &RI, IslAstInfo &AI) {321 return generateCode(S, AI, *S.getLI(), *S.getDT(), *S.getSE(), RI);322}323