CanonicalizeFreezeInLoops.cpp Source File (original) (raw)

48using namespace llvm;

50#define DEBUG_TYPE "canon-freeze"

52namespace {

54class CanonicalizeFreezeInLoops : public LoopPass {

55public:

56 static char ID;

58 CanonicalizeFreezeInLoops();

60private:

63};

65class CanonicalizeFreezeInLoopsImpl {

74 auto Opc = I->getOpcode();

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

77 Opc == Instruction::Mul;

78 }

80 void InsertFreezeAndForgetFromSCEV(Use &U);

82public:

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

85 bool run();

86};

88}

90namespace llvm {

100

103

105};

106

111 }

112

116 }

117

120 };

121

124 return LHS.FI == RHS.FI;

125 };

126};

127

128}

129

130

131

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

133 auto *PH = L->getLoopPreheader();

134

135 auto *UserI = cast(U.getUser());

136 auto *ValueToFr = U.get();

137 assert(L->contains(UserI->getParent()) &&

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

140 return;

141

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

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

145

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

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

148

149 SE.forgetValue(UserI);

150}

151

152bool CanonicalizeFreezeInLoopsImpl::run() {

153

154 if (->isLoopSimplifyForm())

155 return false;

156

158

159 for (auto &PHI : L->getHeader()->phis()) {

162 continue;

163

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

167

168

169 continue;

170 }

171

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

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

174 if (auto *StepI = dyn_cast(StepV)) {

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

176

177

178 continue;

179 }

180 }

181

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

183 if (auto *FI = dyn_cast(U)) {

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

185 Info.FI = FI;

186 Candidates.insert(Info);

187 }

188 };

191 }

192

193 if (Candidates.empty())

194 return false;

195

197 for (const auto &Info : Candidates) {

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

200 continue;

201

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

204

205

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

209 SE.forgetValue(StepI);

210 }

211

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

213

214 unsigned OperandIdx =

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

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

217 }

218

219

220 for (const auto &Item : Candidates) {

221 auto *FI = Item.FI;

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

223 SE.forgetValue(FI);

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

225 FI->eraseFromParent();

226 }

227

228 return true;

229}

230

231CanonicalizeFreezeInLoops::CanonicalizeFreezeInLoops() : LoopPass(ID) {

233}

234

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

244}

245

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

247 if (skipLoop(L))

248 return false;

249

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

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

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

253}

254

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

261

263}

264

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

272

274 return new CanonicalizeFreezeInLoops();

275}

276

277char CanonicalizeFreezeInLoops::ID = 0;

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)

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

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

This file defines the SmallSet class.

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

Represent the analysis usage information of a pass.

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.

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

Legacy analysis pass which computes a DominatorTree.

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 ...

A struct for saving information about induction variables.

static 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.

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...

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

virtual bool runOnLoop(Loop *L, LPPassManager &LPM)=0

Represents a single loop in the control flow graph.

static PassRegistry * getPassRegistry()

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

Pass interface - Implemented by all 'passes'.

virtual void getAnalysisUsage(AnalysisUsage &) const

getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...

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.

bool empty() const

Determine if the SetVector is empty or not.

bool insert(const value_type &X)

Insert a new element into the SetVector.

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

SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...

std::pair< const_iterator, bool > insert(const T &V)

insert - Insert an element into the set if it isn't already there.

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

const Use & getOperandUse(unsigned i) const

LLVM Value Representation.

unsigned ID

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

This is an optimization pass for GlobalISel generic memory operations.

UnaryFunction for_each(R &&Range, UnaryFunction F)

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

raw_ostream & dbgs()

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

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.

PreservedAnalyses getLoopPassPreservedAnalyses()

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

Pass * createCanonicalizeFreezeInLoopsPass()

void initializeCanonicalizeFreezeInLoopsPass(PassRegistry &)

static FrozenIndPHIInfo getEmptyKey()

static FrozenIndPHIInfo getTombstoneKey()

static unsigned getHashValue(const FrozenIndPHIInfo &Val)

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

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

FrozenIndPHIInfo(PHINode *PHI, BinaryOperator *StepInst)

bool operator==(const FrozenIndPHIInfo &Other)

BinaryOperator * StepInst

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