CanonicalizeFreezeInLoops.cpp Source File (original) (raw)

47using namespace llvm;

49#define DEBUG_TYPE "canon-freeze"

51namespace {

53class CanonicalizeFreezeInLoops : public LoopPass {

54public:

55 static char ID;

57 CanonicalizeFreezeInLoops();

59private:

61 void getAnalysisUsage(AnalysisUsage &AU) const override;

62};

64class CanonicalizeFreezeInLoopsImpl {

73 auto Opc = I->getOpcode();

75 return Opc == Instruction::Add || Opc == Instruction::Sub ||

76 Opc == Instruction::Mul;

77 }

79 void InsertFreezeAndForgetFromSCEV(Use &U);

81public:

83 : L(L), SE(SE), DT(DT) {}

84 bool run();

85};

87struct FrozenIndPHIInfo {

94 unsigned StepValIdx = 0;

97 : PHI(PHI), StepInst(StepInst) {}

100};

101

102}

103

109

114

118

119 static bool isEqual(const FrozenIndPHIInfo &LHS,

120 const FrozenIndPHIInfo &RHS) {

121 return LHS.FI == RHS.FI;

122 };

123};

124

125

126

127void CanonicalizeFreezeInLoopsImpl::InsertFreezeAndForgetFromSCEV(Use &U) {

129

131 auto *ValueToFr = U.get();

133 "Should not process an instruction that isn't inside the loop");

135 return;

136

137 LLVM_DEBUG(dbgs() << "canonfr: inserting freeze:\n");

138 LLVM_DEBUG(dbgs() << "\tUser: " << *U.getUser() << "\n");

139 LLVM_DEBUG(dbgs() << "\tOperand: " << *U.get() << "\n");

140

141 U.set(new FreezeInst(ValueToFr, ValueToFr->getName() + ".frozen",

142 PH->getTerminator()->getIterator()));

143

145}

146

147bool CanonicalizeFreezeInLoopsImpl::run() {

148

150 return false;

151

152 SmallSetVector<FrozenIndPHIInfo, 4> Candidates;

153

155 InductionDescriptor ID;

157 continue;

158

160 FrozenIndPHIInfo Info(&PHI, ID.getInductionBinOp());

161 if ( Info .StepInst || !canHandleInst(Info.StepInst)) {

162

163

164 continue;

165 }

166

167 Info.StepValIdx = Info.StepInst->getOperand(0) == &PHI;

168 Value *StepV = Info.StepInst->getOperand(Info.StepValIdx);

170 if (L->contains(StepI->getParent())) {

171

172

173 continue;

174 }

175 }

176

177 auto Visit = [&](User *U) {

179 LLVM_DEBUG(dbgs() << "canonfr: found: " << *FI << "\n");

180 Info.FI = FI;

182 }

183 };

186 }

187

188 if (Candidates.empty())

189 return false;

190

191 SmallPtrSet<PHINode *, 8> ProcessedPHIs;

192 for (const auto &Info : Candidates) {

194 if (!ProcessedPHIs.insert(Info.PHI).second)

195 continue;

196

197 BinaryOperator *StepI = Info.StepInst;

198 assert(StepI && "Step instruction should have been found");

199

200

202 LLVM_DEBUG(dbgs() << "canonfr: drop flags: " << *StepI << "\n");

205 }

206

207 InsertFreezeAndForgetFromSCEV(StepI->getOperandUse(Info.StepValIdx));

208

209 unsigned OperandIdx =

210 PHI->getOperandNumForIncomingValue(PHI->getIncomingValue(0) == StepI);

211 InsertFreezeAndForgetFromSCEV(PHI->getOperandUse(OperandIdx));

212 }

213

214

215 for (const auto &Item : Candidates) {

216 auto *FI = Item.FI;

217 LLVM_DEBUG(dbgs() << "canonfr: removing " << *FI << "\n");

219 FI->replaceAllUsesWith(FI->getOperand(0));

220 FI->eraseFromParent();

221 }

222

223 return true;

224}

225

226CanonicalizeFreezeInLoops::CanonicalizeFreezeInLoops() : LoopPass(ID) {

228}

229

230void CanonicalizeFreezeInLoops::getAnalysisUsage(AnalysisUsage &AU) const {

239}

240

241bool CanonicalizeFreezeInLoops::runOnLoop(Loop *L, LPPassManager &) {

242 if (skipLoop(L))

243 return false;

244

245 auto &SE = getAnalysis().getSE();

246 auto &DT = getAnalysis().getDomTree();

247 return CanonicalizeFreezeInLoopsImpl(L, SE, DT).run();

248}

249

254 if (!CanonicalizeFreezeInLoopsImpl(&L, AR.SE, AR.DT).run())

256

258}

259

261 "Canonicalize Freeze Instructions in Loops", false, false)

266 "Canonicalize Freeze Instructions in Loops", false, false)

267

269 return new CanonicalizeFreezeInLoops();

270}

271

272char CanonicalizeFreezeInLoops::ID = 0;

assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")

Analysis containing CSE Info

This file defines DenseMapInfo traits for DenseMap.

This header provides classes for managing per-loop analyses.

#define INITIALIZE_PASS_DEPENDENCY(depName)

#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)

#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)

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

Represent the analysis usage information of a pass.

LLVM_ABI AnalysisUsage & addRequiredID(const void *ID)

AnalysisUsage & addPreservedID(const void *ID)

AnalysisUsage & addRequired()

AnalysisUsage & addPreserved()

Add the specified Pass class to the set of analyses preserved by this pass.

iterator_range< const_phi_iterator > phis() const

Returns a range that iterates over the phis in the basic block.

PreservedAnalyses run(Loop &L, LoopAnalysisManager &AM, LoopStandardAnalysisResults &AR, LPMUpdater &U)

Definition CanonicalizeFreezeInLoops.cpp:251

Legacy analysis pass which computes a DominatorTree.

DominatorTree & getDomTree()

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

This class represents a freeze function that returns random concrete value if an operand is either a ...

static LLVM_ABI bool isInductionPHI(PHINode *Phi, const Loop *L, ScalarEvolution *SE, InductionDescriptor &D, const SCEV *Expr=nullptr, SmallVectorImpl< Instruction * > *CastsToIgnore=nullptr)

Returns true if Phi is an induction in the loop L.

LLVM_ABI void dropPoisonGeneratingFlags()

Drops flags that may cause this instruction to evaluate to poison despite having non-poison inputs.

This class provides an interface for updating the loop pass manager based on mutations to the loop ne...

bool contains(const LoopT *L) const

Return true if the specified loop is contained within in this loop.

BlockT * getHeader() const

BlockT * getLoopPreheader() const

If there is a preheader for this loop, return it.

The legacy pass manager's analysis pass to compute loop information.

Represents a single loop in the control flow graph.

bool isLoopSimplifyForm() const

Return true if the Loop is in the form that the LoopSimplify form transforms loops to,...

static LLVM_ABI PassRegistry * getPassRegistry()

getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...

Pass interface - Implemented by all 'passes'.

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.

The main scalar evolution driver.

LLVM_ABI void forgetValue(Value *V)

This method should be called by the client when it has changed a value in a way that may effect its v...

bool empty() const

Determine if the SetVector is empty or not.

bool insert(const value_type &X)

Insert a new element into the SetVector.

std::pair< iterator, bool > insert(PtrType Ptr)

Inserts Ptr if and only if there is no element in the container equal to Ptr.

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

const Use & getOperandUse(unsigned i) const

unsigned ID

LLVM IR allows to use arbitrary numbers as calling convention identifiers.

@ User

could "use" a pointer

This is an optimization pass for GlobalISel generic memory operations.

FunctionAddr VTableAddr Value

UnaryFunction for_each(R &&Range, UnaryFunction F)

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

decltype(auto) dyn_cast(const From &Val)

dyn_cast - Return the argument parameter cast to the specified type.

LLVM_ABI void initializeCanonicalizeFreezeInLoopsPass(PassRegistry &)

LLVM_ABI char & LoopSimplifyID

bool operator==(const AddressRangeValuePair &LHS, const AddressRangeValuePair &RHS)

AnalysisManager< Loop, LoopStandardAnalysisResults & > LoopAnalysisManager

The loop analysis manager.

LLVM_ABI raw_ostream & dbgs()

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

LLVM_ABI bool isGuaranteedNotToBeUndefOrPoison(const Value *V, AssumptionCache *AC=nullptr, const Instruction *CtxI=nullptr, const DominatorTree *DT=nullptr, unsigned Depth=0)

Return true if this function can prove that V does not have undef bits and is never poison.

decltype(auto) cast(const From &Val)

cast - Return the argument parameter cast to the specified type.

LLVM_ABI PreservedAnalyses getLoopPassPreservedAnalyses()

Returns the minimum set of Analyses that all loop passes must preserve.

LLVM_ABI Pass * createCanonicalizeFreezeInLoopsPass()

Definition CanonicalizeFreezeInLoops.cpp:268

static FrozenIndPHIInfo getEmptyKey()

Definition CanonicalizeFreezeInLoops.cpp:105

static FrozenIndPHIInfo getTombstoneKey()

Definition CanonicalizeFreezeInLoops.cpp:110

static unsigned getHashValue(const FrozenIndPHIInfo &Val)

Definition CanonicalizeFreezeInLoops.cpp:115

static bool isEqual(const FrozenIndPHIInfo &LHS, const FrozenIndPHIInfo &RHS)

Definition CanonicalizeFreezeInLoops.cpp:119

An information struct used to provide DenseMap with the various necessary components for a given valu...

The adaptor from a function pass to a loop pass computes these analyses and makes them available to t...