346 lines · cpp
1//===- FactsGenerator.cpp - Lifetime Facts Generation -----------*- C++ -*-===//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#include "clang/Analysis/Analyses/LifetimeSafety/FactsGenerator.h"10#include "clang/Analysis/Analyses/LifetimeSafety/LifetimeAnnotations.h"11#include "clang/Analysis/Analyses/PostOrderCFGView.h"12#include "llvm/Support/Casting.h"13#include "llvm/Support/TimeProfiler.h"14 15namespace clang::lifetimes::internal {16using llvm::isa_and_present;17 18static bool isPointerType(QualType QT) {19 return QT->isPointerOrReferenceType() || isGslPointerType(QT);20}21// Check if a type has an origin.22static bool hasOrigin(const Expr *E) {23 return E->isGLValue() || isPointerType(E->getType());24}25 26static bool hasOrigin(const VarDecl *VD) {27 return isPointerType(VD->getType());28}29 30/// Creates a loan for the storage path of a given declaration reference.31/// This function should be called whenever a DeclRefExpr represents a borrow.32/// \param DRE The declaration reference expression that initiates the borrow.33/// \return The new Loan on success, nullptr otherwise.34static const Loan *createLoan(FactManager &FactMgr, const DeclRefExpr *DRE) {35 if (const auto *VD = dyn_cast<ValueDecl>(DRE->getDecl())) {36 AccessPath Path(VD);37 // The loan is created at the location of the DeclRefExpr.38 return &FactMgr.getLoanMgr().addLoan(Path, DRE);39 }40 return nullptr;41}42 43void FactsGenerator::run() {44 llvm::TimeTraceScope TimeProfile("FactGenerator");45 // Iterate through the CFG blocks in reverse post-order to ensure that46 // initializations and destructions are processed in the correct sequence.47 for (const CFGBlock *Block : *AC.getAnalysis<PostOrderCFGView>()) {48 CurrentBlockFacts.clear();49 EscapesInCurrentBlock.clear();50 for (unsigned I = 0; I < Block->size(); ++I) {51 const CFGElement &Element = Block->Elements[I];52 if (std::optional<CFGStmt> CS = Element.getAs<CFGStmt>())53 Visit(CS->getStmt());54 else if (std::optional<CFGLifetimeEnds> LifetimeEnds =55 Element.getAs<CFGLifetimeEnds>())56 handleLifetimeEnds(*LifetimeEnds);57 }58 CurrentBlockFacts.append(EscapesInCurrentBlock.begin(),59 EscapesInCurrentBlock.end());60 FactMgr.addBlockFacts(Block, CurrentBlockFacts);61 }62}63 64void FactsGenerator::VisitDeclStmt(const DeclStmt *DS) {65 for (const Decl *D : DS->decls())66 if (const auto *VD = dyn_cast<VarDecl>(D))67 if (hasOrigin(VD))68 if (const Expr *InitExpr = VD->getInit())69 killAndFlowOrigin(*VD, *InitExpr);70}71 72void FactsGenerator::VisitDeclRefExpr(const DeclRefExpr *DRE) {73 handleUse(DRE);74 // For non-pointer/non-view types, a reference to the variable's storage75 // is a borrow. We create a loan for it.76 // For pointer/view types, we stick to the existing model for now and do77 // not create an extra origin for the l-value expression itself.78 79 // TODO: A single origin for a `DeclRefExpr` for a pointer or view type is80 // not sufficient to model the different levels of indirection. The current81 // single-origin model cannot distinguish between a loan to the variable's82 // storage and a loan to what it points to. A multi-origin model would be83 // required for this.84 if (!isPointerType(DRE->getType())) {85 if (const Loan *L = createLoan(FactMgr, DRE)) {86 OriginID ExprOID = FactMgr.getOriginMgr().getOrCreate(*DRE);87 CurrentBlockFacts.push_back(88 FactMgr.createFact<IssueFact>(L->ID, ExprOID));89 }90 }91}92 93void FactsGenerator::VisitCXXConstructExpr(const CXXConstructExpr *CCE) {94 if (isGslPointerType(CCE->getType())) {95 handleGSLPointerConstruction(CCE);96 return;97 }98}99 100void FactsGenerator::VisitCXXMemberCallExpr(const CXXMemberCallExpr *MCE) {101 // Specifically for conversion operators,102 // like `std::string_view p = std::string{};`103 if (isGslPointerType(MCE->getType()) &&104 isa_and_present<CXXConversionDecl>(MCE->getCalleeDecl())) {105 // The argument is the implicit object itself.106 handleFunctionCall(MCE, MCE->getMethodDecl(),107 {MCE->getImplicitObjectArgument()},108 /*IsGslConstruction=*/true);109 }110 if (const CXXMethodDecl *Method = MCE->getMethodDecl()) {111 // Construct the argument list, with the implicit 'this' object as the112 // first argument.113 llvm::SmallVector<const Expr *, 4> Args;114 Args.push_back(MCE->getImplicitObjectArgument());115 Args.append(MCE->getArgs(), MCE->getArgs() + MCE->getNumArgs());116 117 handleFunctionCall(MCE, Method, Args, /*IsGslConstruction=*/false);118 }119}120 121void FactsGenerator::VisitCallExpr(const CallExpr *CE) {122 handleFunctionCall(CE, CE->getDirectCallee(),123 {CE->getArgs(), CE->getNumArgs()});124}125 126void FactsGenerator::VisitCXXNullPtrLiteralExpr(127 const CXXNullPtrLiteralExpr *N) {128 /// TODO: Handle nullptr expr as a special 'null' loan. Uninitialized129 /// pointers can use the same type of loan.130 FactMgr.getOriginMgr().getOrCreate(*N);131}132 133void FactsGenerator::VisitImplicitCastExpr(const ImplicitCastExpr *ICE) {134 if (!hasOrigin(ICE))135 return;136 // An ImplicitCastExpr node itself gets an origin, which flows from the137 // origin of its sub-expression (after stripping its own parens/casts).138 killAndFlowOrigin(*ICE, *ICE->getSubExpr());139}140 141void FactsGenerator::VisitUnaryOperator(const UnaryOperator *UO) {142 if (UO->getOpcode() == UO_AddrOf) {143 const Expr *SubExpr = UO->getSubExpr();144 // Taking address of a pointer-type expression is not yet supported and145 // will be supported in multi-origin model.146 if (isPointerType(SubExpr->getType()))147 return;148 // The origin of an address-of expression (e.g., &x) is the origin of149 // its sub-expression (x). This fact will cause the dataflow analysis150 // to propagate any loans held by the sub-expression's origin to the151 // origin of this UnaryOperator expression.152 killAndFlowOrigin(*UO, *SubExpr);153 }154}155 156void FactsGenerator::VisitReturnStmt(const ReturnStmt *RS) {157 if (const Expr *RetExpr = RS->getRetValue()) {158 if (hasOrigin(RetExpr)) {159 OriginID OID = FactMgr.getOriginMgr().getOrCreate(*RetExpr);160 EscapesInCurrentBlock.push_back(161 FactMgr.createFact<OriginEscapesFact>(OID, RetExpr));162 }163 }164}165 166void FactsGenerator::VisitBinaryOperator(const BinaryOperator *BO) {167 if (BO->isAssignmentOp())168 handleAssignment(BO->getLHS(), BO->getRHS());169}170 171void FactsGenerator::VisitConditionalOperator(const ConditionalOperator *CO) {172 if (hasOrigin(CO)) {173 // Merge origins from both branches of the conditional operator.174 // We kill to clear the initial state and merge both origins into it.175 killAndFlowOrigin(*CO, *CO->getTrueExpr());176 flowOrigin(*CO, *CO->getFalseExpr());177 }178}179 180void FactsGenerator::VisitCXXOperatorCallExpr(const CXXOperatorCallExpr *OCE) {181 // Assignment operators have special "kill-then-propagate" semantics182 // and are handled separately.183 if (OCE->isAssignmentOp() && OCE->getNumArgs() == 2) {184 handleAssignment(OCE->getArg(0), OCE->getArg(1));185 return;186 }187 handleFunctionCall(OCE, OCE->getDirectCallee(),188 {OCE->getArgs(), OCE->getNumArgs()},189 /*IsGslConstruction=*/false);190}191 192void FactsGenerator::VisitCXXFunctionalCastExpr(193 const CXXFunctionalCastExpr *FCE) {194 // Check if this is a test point marker. If so, we are done with this195 // expression.196 if (handleTestPoint(FCE))197 return;198 if (isGslPointerType(FCE->getType()))199 killAndFlowOrigin(*FCE, *FCE->getSubExpr());200}201 202void FactsGenerator::VisitInitListExpr(const InitListExpr *ILE) {203 if (!hasOrigin(ILE))204 return;205 // For list initialization with a single element, like `View{...}`, the206 // origin of the list itself is the origin of its single element.207 if (ILE->getNumInits() == 1)208 killAndFlowOrigin(*ILE, *ILE->getInit(0));209}210 211void FactsGenerator::VisitMaterializeTemporaryExpr(212 const MaterializeTemporaryExpr *MTE) {213 if (!hasOrigin(MTE))214 return;215 // A temporary object's origin is the same as the origin of the216 // expression that initializes it.217 killAndFlowOrigin(*MTE, *MTE->getSubExpr());218}219 220void FactsGenerator::handleLifetimeEnds(const CFGLifetimeEnds &LifetimeEnds) {221 /// TODO: Handle loans to temporaries.222 const VarDecl *LifetimeEndsVD = LifetimeEnds.getVarDecl();223 if (!LifetimeEndsVD)224 return;225 // Iterate through all loans to see if any expire.226 for (const auto &Loan : FactMgr.getLoanMgr().getLoans()) {227 const AccessPath &LoanPath = Loan.Path;228 // Check if the loan is for a stack variable and if that variable229 // is the one being destructed.230 if (LoanPath.D == LifetimeEndsVD)231 CurrentBlockFacts.push_back(FactMgr.createFact<ExpireFact>(232 Loan.ID, LifetimeEnds.getTriggerStmt()->getEndLoc()));233 }234}235 236void FactsGenerator::handleGSLPointerConstruction(const CXXConstructExpr *CCE) {237 assert(isGslPointerType(CCE->getType()));238 if (CCE->getNumArgs() != 1)239 return;240 if (hasOrigin(CCE->getArg(0)))241 killAndFlowOrigin(*CCE, *CCE->getArg(0));242 else243 // This could be a new borrow.244 handleFunctionCall(CCE, CCE->getConstructor(),245 {CCE->getArgs(), CCE->getNumArgs()},246 /*IsGslConstruction=*/true);247}248 249/// Checks if a call-like expression creates a borrow by passing a value to a250/// reference parameter, creating an IssueFact if it does.251/// \param IsGslConstruction True if this is a GSL construction where all252/// argument origins should flow to the returned origin.253void FactsGenerator::handleFunctionCall(const Expr *Call,254 const FunctionDecl *FD,255 ArrayRef<const Expr *> Args,256 bool IsGslConstruction) {257 // Ignore functions returning values with no origin.258 if (!FD || !hasOrigin(Call))259 return;260 auto IsArgLifetimeBound = [FD](unsigned I) -> bool {261 const ParmVarDecl *PVD = nullptr;262 if (const auto *Method = dyn_cast<CXXMethodDecl>(FD);263 Method && Method->isInstance()) {264 if (I == 0)265 // For the 'this' argument, the attribute is on the method itself.266 return implicitObjectParamIsLifetimeBound(Method);267 if ((I - 1) < Method->getNumParams())268 // For explicit arguments, find the corresponding parameter269 // declaration.270 PVD = Method->getParamDecl(I - 1);271 } else if (I < FD->getNumParams())272 // For free functions or static methods.273 PVD = FD->getParamDecl(I);274 return PVD ? PVD->hasAttr<clang::LifetimeBoundAttr>() : false;275 };276 if (Args.empty())277 return;278 bool killedSrc = false;279 for (unsigned I = 0; I < Args.size(); ++I)280 if (IsGslConstruction || IsArgLifetimeBound(I)) {281 if (!killedSrc) {282 killedSrc = true;283 killAndFlowOrigin(*Call, *Args[I]);284 } else285 flowOrigin(*Call, *Args[I]);286 }287}288 289/// Checks if the expression is a `void("__lifetime_test_point_...")` cast.290/// If so, creates a `TestPointFact` and returns true.291bool FactsGenerator::handleTestPoint(const CXXFunctionalCastExpr *FCE) {292 if (!FCE->getType()->isVoidType())293 return false;294 295 const auto *SubExpr = FCE->getSubExpr()->IgnoreParenImpCasts();296 if (const auto *SL = dyn_cast<StringLiteral>(SubExpr)) {297 llvm::StringRef LiteralValue = SL->getString();298 const std::string Prefix = "__lifetime_test_point_";299 300 if (LiteralValue.starts_with(Prefix)) {301 StringRef Annotation = LiteralValue.drop_front(Prefix.length());302 CurrentBlockFacts.push_back(303 FactMgr.createFact<TestPointFact>(Annotation));304 return true;305 }306 }307 return false;308}309 310void FactsGenerator::handleAssignment(const Expr *LHSExpr,311 const Expr *RHSExpr) {312 if (!hasOrigin(LHSExpr))313 return;314 // Find the underlying variable declaration for the left-hand side.315 if (const auto *DRE_LHS =316 dyn_cast<DeclRefExpr>(LHSExpr->IgnoreParenImpCasts())) {317 markUseAsWrite(DRE_LHS);318 if (const auto *VD_LHS = dyn_cast<ValueDecl>(DRE_LHS->getDecl())) {319 // Kill the old loans of the destination origin and flow the new loans320 // from the source origin.321 killAndFlowOrigin(*VD_LHS, *RHSExpr);322 }323 }324}325 326// A DeclRefExpr will be treated as a use of the referenced decl. It will be327// checked for use-after-free unless it is later marked as being written to328// (e.g. on the left-hand side of an assignment).329void FactsGenerator::handleUse(const DeclRefExpr *DRE) {330 if (isPointerType(DRE->getType())) {331 UseFact *UF = FactMgr.createFact<UseFact>(DRE, FactMgr.getOriginMgr());332 CurrentBlockFacts.push_back(UF);333 assert(!UseFacts.contains(DRE));334 UseFacts[DRE] = UF;335 }336}337 338void FactsGenerator::markUseAsWrite(const DeclRefExpr *DRE) {339 if (!isPointerType(DRE->getType()))340 return;341 assert(UseFacts.contains(DRE));342 UseFacts[DRE]->markAsWritten();343}344 345} // namespace clang::lifetimes::internal346