SCCP.cpp Source File (original) (raw)

35using namespace llvm;

37#define DEBUG_TYPE "sccp"

39 STATISTIC(NumInstRemoved, "Number of instructions removed");

40 STATISTIC(NumArgsElimed ,"Number of arguments constant propagated");

41 STATISTIC(NumGlobalConst, "Number of globals found to be constant");

42 STATISTIC(NumDeadBlocks , "Number of basic blocks unreachable");

44 "Number of instructions replaced with (simpler) instruction");

48 "The maximum number of iterations function specialization is run"));

55 return;

60 << "Can't zap returns of the function : " << F.getName()

61 << " due to present musttail or \"clang.arc.attachedcall\" call of "

62 "it\n");

63 return;

64 }

68 [&Solver](User *U) {

69 if (isa(U) &&

70 !Solver.isBlockExecutable(cast(U)->getParent()))

71 return true;

76 if (!isa(U))

77 return true;

78 if (U->getType()->isStructTy()) {

79 return all_of(Solver.getStructLatticeValueFor(U),

80 [](const ValueLatticeElement &LV) {

81 return !SCCPSolver::isOverdefined(LV);

82 });

83 }

87 if (auto *II = dyn_cast(U)) {

88 if (II->isAssumeLikeIntrinsic())

89 return true;

90 }

93 }) &&

94 "We can only zap functions where all live users have a concrete value");

97 if (CallInst *CI = BB.getTerminatingMustTailCall()) {

98 LLVM_DEBUG(dbgs() << "Can't zap return of the block due to present "

99 << "musttail call : " << *CI << "\n");

100 (void)CI;

101 return;

102 }

103

104 if (auto *RI = dyn_cast(BB.getTerminator()))

105 if (!isa(RI->getOperand(0)))

106 ReturnsToZap.push_back(RI);

107 }

108}

109

117 bool IsFuncSpecEnabled) {

118 SCCPSolver Solver(DL, GetTLI, M.getContext());

120 GetAC);

121

122

123

125 if (F.isDeclaration())

126 continue;

127

131

132

133

136

137

138

141 continue;

142 }

143

144

146

149 }

150

151

152

153

155 G.removeDeadConstantUsers();

158 }

159

160

162

163 if (IsFuncSpecEnabled) {

164 unsigned Iters = 0;

166 }

167

168

169

170 bool MadeChanges = false;

172 if (F.isDeclaration())

173 continue;

174

176

178 bool ReplacedPointerArg = false;

181 ReplacedPointerArg |= Arg.getType()->isPointerTy();

182 ++NumArgsElimed;

183 }

184 }

185

186

187

188 if (ReplacedPointerArg) {

192 return AL;

193

195 ME.getModRef(IRMemLocation::ArgMem));

196 return AL.addFnAttribute(

197 F.getContext(),

199 };

200

201 F.setAttributes(UpdateAttrs(F.getAttributes()));

202 for (User *U : F.users()) {

203 auto *CB = dyn_cast(U);

204 if (!CB || CB->getCalledFunction() != &F)

205 continue;

206

207 CB->setAttributes(UpdateAttrs(CB->getAttributes()));

208 }

209 }

210 MadeChanges |= ReplacedPointerArg;

211 }

212

217 ++NumDeadBlocks;

218

219 MadeChanges = true;

220

221 if (&BB != &F.front())

223 continue;

224 }

225

227 BB, InsertedValues, NumInstRemoved, NumInstReplaced);

228 }

229

232 DomTreeUpdater DTU(DT, PDT, DomTreeUpdater::UpdateStrategy::Lazy);

233

234

235

236

237 for (BasicBlock *BB : BlocksToErase) {

239 false, &DTU);

240 }

243 false, &DTU);

244

245 BasicBlock *NewUnreachableBB = nullptr;

248

249 for (BasicBlock *DeadBB : BlocksToErase)

250 if (!DeadBB->hasAddressTaken())

251 DTU.deleteBB(DeadBB);

252

256 if (auto *II = dyn_cast(&Inst)) {

257 if (II->getIntrinsicID() == Intrinsic::ssa_copy) {

259 Inst.replaceAllUsesWith(Op);

260 Inst.eraseFromParent();

261 }

262 }

263 }

264 }

265 }

266 }

267

268

269

270

271

272

273

274

275

276

277

279

283 assert(->getReturnType()->isVoidTy() &&

284 "should not track void functions");

287 }

288

290 assert(F->getReturnType()->isStructTy() &&

291 "The return type should be a struct");

292 StructType *STy = cast(F->getReturnType());

295 }

296

297

299 for (ReturnInst *RI : ReturnsToZap) {

300 Function *F = RI->getParent()->getParent();

302

303 FuncZappedReturn.insert(F);

304 }

305

306

307

308

309

312 for (Function *F : FuncZappedReturn) {

314 F->removeParamAttr(A.getArgNo(), Attribute::Returned);

315 F->removeRetAttrs(UBImplyingAttributes);

316 for (Use &U : F->uses()) {

317 CallBase *CB = dyn_cast(U.getUser());

318 if (!CB) {

319 assert(isa(U.getUser()) ||

320 (isa(U.getUser()) &&

321 all_of(U.getUser()->users(), [](const User *UserUser) {

322 return cast(UserUser)->isAssumeLikeIntrinsic();

323 })));

324 continue;

325 }

326

327 for (Use &Arg : CB->args())

330 }

331 }

332

333

334

338 continue;

340 << "' is constant!\n");

342

343

344 assert((isa(U) || isa(U)) &&

345 "Only Store|Load Instruction can be user of GlobalVariable at "

346 "reaching here.");

347 cast(U)->eraseFromParent();

348 }

349

350

351

354 if (GVEs.size() == 1) {

358 GVEs[0]->replaceOperandWith(1, InitExpr);

359 }

360

361 MadeChanges = true;

362 M.eraseGlobalVariable(GV);

363 ++NumGlobalConst;

364 }

365

366 return MadeChanges;

367}

368

374 };

377 };

380 };

383 };

386 };

387

388

389 if ( runIPSCCP (M, DL, &FAM, GetTLI, GetTTI, GetAC, GetDT, GetBFI,

392

397 return PA;

398}

MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL

static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")

This file contains the declarations for the subclasses of Constant, which represent the different fla...

static void findReturnsToZap(Function &F, SmallVector< ReturnInst *, 8 > &ReturnsToZap, SCCPSolver &Solver)

static cl::opt< unsigned > FuncSpecMaxIters("funcspec-max-iters", cl::init(10), cl::Hidden, cl::desc("The maximum number of iterations function specialization is run"))

static bool runIPSCCP(Module &M, const DataLayout &DL, FunctionAnalysisManager *FAM, std::function< const TargetLibraryInfo &(Function &)> GetTLI, std::function< TargetTransformInfo &(Function &)> GetTTI, std::function< AssumptionCache &(Function &)> GetAC, std::function< DominatorTree &(Function &)> GetDT, std::function< BlockFrequencyInfo &(Function &)> GetBFI, bool IsFuncSpecEnabled)

uint64_t IntrinsicInst * II

FunctionAnalysisManager FAM

assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())

This file implements a set that has insertion order iteration characteristics.

#define STATISTIC(VARNAME, DESC)

This pass exposes codegen information to IR-level passes.

A container for analyses that lazily runs them and caches their results.

PassT::Result * getCachedResult(IRUnitT &IR) const

Get the cached result of an analysis pass for a given IR unit.

PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)

Get the result of an analysis pass for a given IR unit.

This class represents an incoming formal argument to a Function.

A function analysis which provides an AssumptionCache.

A cache of @llvm.assume calls within a function.

static Attribute getWithMemoryEffects(LLVMContext &Context, MemoryEffects ME)

LLVM Basic Block Representation.

Analysis pass which computes BlockFrequencyInfo.

BlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate IR basic block frequen...

Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...

void removeParamAttr(unsigned ArgNo, Attribute::AttrKind Kind)

Removes the attribute from the given argument.

void removeRetAttrs(const AttributeMask &AttrsToRemove)

Removes the attributes from the return value.

iterator_range< User::op_iterator > args()

Iteration adapter for range-for loops.

unsigned getArgOperandNo(const Use *U) const

Given a use for a arg operand, get the arg operand number that corresponds to it.

This class represents a function call, abstracting a target machine's calling convention.

This class represents an Operation in the Expression.

A parsed version of the target data layout string in and methods for querying it.

Analysis pass which computes a DominatorTree.

Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.

bool run()

Attempt to specialize functions in the module to enable constant propagation across function boundari...

Type * getValueType() const

const Constant * getInitializer() const

getInitializer - Return the initializer for this global variable.

void getDebugInfo(SmallVectorImpl< DIGlobalVariableExpression * > &GVs) const

Fill the vector with all debug info attachements.

bool isFuncSpecEnabled() const

PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM)

An analysis over an "outer" IR unit that provides access to an analysis manager over an "inner" IR un...

ModRefInfo getModRef(Location Loc) const

Get ModRefInfo for the given Location.

static MemoryEffectsBase unknown()

Create MemoryEffectsBase that can read and write any memory.

A Module instance is used to store all the information related to an LLVM module.

static PoisonValue * get(Type *T)

Static factory methods - Return an 'poison' object of the specified type.

Analysis pass which computes a PostDominatorTree.

PostDominatorTree Class - Concrete subclass of DominatorTree that is used to compute the post-dominat...

A set of analyses that are preserved following a run of a transformation pass.

static PreservedAnalyses all()

Construct a special preserved set that preserves all passes.

void preserve()

Mark an analysis as preserved.

Return a value (possibly void), from a function.

SCCPSolver - This interface class is a general purpose solver for Sparse Conditional Constant Propaga...

const DenseMap< GlobalVariable *, ValueLatticeElement > & getTrackedGlobals()

getTrackedGlobals - Get and return the set of inferred initializers for global variables.

void trackValueOfGlobalVariable(GlobalVariable *GV)

trackValueOfGlobalVariable - Clients can use this method to inform the SCCPSolver that it should trac...

bool tryToReplaceWithConstant(Value *V)

void inferArgAttributes() const

bool isStructLatticeConstant(Function *F, StructType *STy)

void addPredicateInfo(Function &F, DominatorTree &DT, AssumptionCache &AC)

void trackValueOfArgument(Argument *V)

trackValueOfArgument - Mark the specified argument overdefined unless it have range attribute.

void addTrackedFunction(Function *F)

addTrackedFunction - If the SCCP solver is supposed to track calls into and out of the specified func...

void solveWhileResolvedUndefsIn(Module &M)

const PredicateBase * getPredicateInfoFor(Instruction *I)

void addArgumentTrackedFunction(Function *F)

const SmallPtrSet< Function *, 16 > getMRVFunctionsTracked()

getMRVFunctionsTracked - Get the set of functions which return multiple values tracked by the pass.

bool simplifyInstsInBlock(BasicBlock &BB, SmallPtrSetImpl< Value * > &InsertedValues, Statistic &InstRemovedStat, Statistic &InstReplacedStat)

const ValueLatticeElement & getLatticeValueFor(Value *V) const

bool removeNonFeasibleEdges(BasicBlock *BB, DomTreeUpdater &DTU, BasicBlock *&NewUnreachableBB) const

bool isBlockExecutable(BasicBlock *BB) const

void inferReturnAttributes() const

bool markBlockExecutable(BasicBlock *BB)

markBlockExecutable - This method can be used by clients to mark all of the blocks that are known to ...

static bool isConstant(const ValueLatticeElement &LV)

const MapVector< Function *, ValueLatticeElement > & getTrackedRetVals() const

getTrackedRetVals - Get the inferred return value map.

bool mustPreserveReturn(Function *F)

Returns true if the return of the given function cannot be modified.

static bool isOverdefined(const ValueLatticeElement &LV)

bool isArgumentTrackedFunction(Function *F)

Returns true if the given function is in the solver's set of argument-tracked functions.

bool insert(const value_type &X)

Insert a new element into the SetVector.

SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.

A SetVector that performs no allocations if smaller than a certain size.

void push_back(const T &Elt)

This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.

Class to represent struct types.

Analysis pass providing the TargetTransformInfo.

Analysis pass providing the TargetLibraryInfo.

Provides information about what library functions are available for the current target.

This pass provides access to the codegen interfaces that are needed for IR-level transformations.

A Use represents the edge between a Value definition and its users.

LLVM Value Representation.

iterator_range< user_iterator > users()

StringRef getName() const

Return a constant reference to the value's name.

AttributeMask getUBImplyingAttributes()

Get param/return attributes which imply immediate undefined behavior if an invalid value is passed.

initializer< Ty > init(const Ty &Val)

This is an optimization pass for GlobalISel generic memory operations.

bool all_of(R &&range, UnaryPredicate P)

Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.

iterator_range< early_inc_iterator_impl< detail::IterOfRange< RangeT > > > make_early_inc_range(RangeT &&Range)

Make a range that does early increment to allow mutation of the underlying range without disrupting i...

bool canTrackGlobalVariableInterprocedurally(GlobalVariable *GV)

Determine if the value maintained in the given global variable can be tracked interprocedurally.

MemoryEffectsBase< IRMemLocation > MemoryEffects

Summary of how a function affects memory in the program.

DIExpression * getExpressionForConstant(DIBuilder &DIB, const Constant &C, Type &Ty)

Given a constant, create a debug information expression.

raw_ostream & dbgs()

dbgs() - This returns a reference to a raw_ostream for debugging messages.

unsigned changeToUnreachable(Instruction *I, bool PreserveLCSSA=false, DomTreeUpdater *DTU=nullptr, MemorySSAUpdater *MSSAU=nullptr)

Insert an unreachable instruction before the specified instruction, making it and the rest of the cod...

bool canTrackReturnsInterprocedurally(Function *F)

Determine if the values of the given function's returns can be tracked interprocedurally.

bool canTrackArgumentsInterprocedurally(Function *F)

Determine if the values of the given function's arguments can be tracked interprocedurally.