Lines Matching full:instruction
166 typedef SmallVector<Instruction *, 16> SmallInstructionVector;
167 typedef SmallSet<Instruction *, 16> SmallInstructionSet;
173 SimpleLoopReduction(Instruction *P, Loop *L)
175 assert(isa<PHINode>(P) && "First reduction instruction must be a PHI");
183 Instruction *getPHI() const {
188 Instruction *getReducedValue() const {
193 Instruction *get(size_t i) const {
198 Instruction *operator [] (size_t i) const { return get(i); }
230 // during loop instruction processing.
260 for (Instruction *J : PossibleReds[i]) {
271 bool isPairInSame(Instruction *J1, Instruction *J2) {
272 DenseMap<Instruction *, int>::iterator J1I = PossibleRedIdx.find(J1);
274 DenseMap<Instruction *, int>::iterator J2I = PossibleRedIdx.find(J2);
285 void recordPair(Instruction *J1, Instruction *J2, unsigned i) {
288 "Recording reduction vs. non-reduction instruction?");
303 // Is the provided instruction the PHI of a reduction selected for
305 bool isSelectedPHI(Instruction *J) {
312 if (cast<Instruction>(J) == PossibleReds[i].getPHI())
326 DenseMap<Instruction *, int> PossibleRedIdx;
327 DenseMap<Instruction *, int> PossibleRedIter;
338 // Base instruction -> i*3
355 // one for the Base instruction in each DAGRootSet.
358 Instruction *BaseInst;
367 DAGRootTracker(LoopReroll *Parent, Loop *L, Instruction *IV,
382 typedef MapVector<Instruction*, SmallBitVector> UsesTy;
384 bool findRootsRecursive(Instruction *IVU,
386 bool findRootsBase(Instruction *IVU, SmallInstructionSet SubsumedInsts);
387 bool collectPossibleRoots(Instruction *Base,
388 std::map<int64_t,Instruction*> &Roots);
394 DenseSet<Instruction *> &Users);
395 void collectInLoopUserSet(Instruction *Root,
398 DenseSet<Instruction *> &Users);
403 bool isBaseInst(Instruction *I);
404 bool isRootInst(Instruction *I);
405 bool instrDependsOn(Instruction *I,
418 Instruction *IV;
438 bool reroll(Instruction *IV, Loop *L, BasicBlock *Header, const SCEV *IterCount,
456 // Returns true if the provided instruction is used outside the given loop.
457 // This operates like Instruction::isUsedOutsideOfBlock, but considers PHIs in
459 static bool hasUsesOutsideLoop(Instruction *I, Loop *L) {
461 if (!L->contains(cast<Instruction>(U)))
500 // Add the remainder of the reduction-variable chain to the instruction vector
509 Instruction *C = Instructions.front();
514 C = cast<Instruction>(*C->user_begin());
532 // C is now the (potential) last instruction in the reduction chain.
535 if (L->contains(cast<Instruction>(U)))
536 if (cast<Instruction>(U) != Instructions.front())
565 // Collect the set of all users of the provided root instruction. This set of
566 // users contains not only the direct users of the root instruction, but also
578 Instruction *Root, const SmallInstructionSet &Exclude,
580 DenseSet<Instruction *> &Users) {
583 Instruction *I = Queue.pop_back_val();
589 Instruction *User = cast<Instruction>(U.getUser());
604 if (Instruction *Op = dyn_cast<Instruction>(*OI))
618 DenseSet<Instruction *> &Users) {
624 static bool isSimpleLoadStore(Instruction *I) {
638 if (Instruction *I = dyn_cast<Instruction>(IVU)) {
641 case Instruction::Add:
642 case Instruction::Sub:
643 case Instruction::Mul:
644 case Instruction::Shl:
645 case Instruction::AShr:
646 case Instruction::LShr:
647 case Instruction::GetElementPtr:
648 case Instruction::Trunc:
649 case Instruction::ZExt:
650 case Instruction::SExt:
657 static bool isLoopIncrement(User *U, Instruction *IV) {
659 if (!BO || BO->getOpcode() != Instruction::Add)
671 collectPossibleRoots(Instruction *Base, std::map<int64_t,Instruction*> &Roots) {
678 LoopIncs.push_back(cast<Instruction>(I));
684 if (BO->getOpcode() == Instruction::Add ||
685 BO->getOpcode() == Instruction::Or)
693 if (Instruction *II = dyn_cast<Instruction>(I)) {
697 DEBUG(dbgs() << "LRR: Aborting due to non-instruction: " << *I << "\n");
713 Roots[V] = cast<Instruction>(I);
751 findRootsRecursive(Instruction *I, SmallInstructionSet SubsumedInsts) {
757 if ((I->getOpcode() == Instruction::Mul ||
758 I->getOpcode() == Instruction::PHI) &&
766 Instruction *I = dyn_cast<Instruction>(V);
778 findRootsBase(Instruction *IVU, SmallInstructionSet SubsumedInsts) {
780 // The base instruction needs to be a multiply so
782 if (IVU->getOpcode() != Instruction::Mul &&
783 IVU->getOpcode() != Instruction::PHI)
786 std::map<int64_t, Instruction*> V;
830 LoopIncs.push_back(cast<Instruction>(IVU));
908 DenseSet<Instruction*> VBase;
916 DenseSet<Instruction*> V;
946 DenseSet<Instruction*> V;
956 /// Get the next instruction in "In" that is a member of set Val.
970 bool LoopReroll::DAGRootTracker::isBaseInst(Instruction *I) {
978 bool LoopReroll::DAGRootTracker::isRootInst(Instruction *I) {
986 /// Return true if instruction I depends on any instruction between
988 bool LoopReroll::DAGRootTracker::instrDependsOn(Instruction *I,
1020 // Populate "Uses" with where each instruction is used.
1033 DEBUG(dbgs() << "LRR: Aborting - instruction is not used in 1 iteration: "
1062 Instruction *BaseInst = BaseIt->first;
1063 Instruction *RootInst = RootIt->first;
1120 Instruction *I = LastRootIt->first;
1135 // Make sure that this instruction, which is in the use set of this
1136 // root instruction, does not also belong to the base set or the set of
1137 // some other root instruction.
1144 // Make sure that we don't alias with any instruction in the alias set
1156 // If we've past an instruction from a future iteration that may have
1157 // side effects, and this instruction might also, then we can't reorder
1191 if (Instruction *Op2I = dyn_cast<Instruction>(Op2))
1200 if (DRS.Roots[Iter-1] == (Instruction*) Op2) {
1211 // reduction above), and the instruction is commutative, then try
1262 Instruction *D = &*J;
1336 for (Instruction *J : PossibleReds[i]) {
1376 // Fixup reductions to refer to the last instruction associated with the
1391 Users.push_back(cast<Instruction>(U));
1426 // - Ensure that the next unmatched instruction in f(%iv) is isomorphic to
1427 // the next unmatched instruction in f(%iv.(i+1)).
1444 bool LoopReroll::reroll(Instruction *IV, Loop *L, BasicBlock *Header,
